Suche in großer Tabelle

Ich habe eine Tabelle mit 6 Spalten und 1.000.000 Einträgen und muss einen Eintrag finden. Dabei sind mir 6 Werte bekannt, der Eintrag ist gefunden wenn alle diese 6 Werte auftauchen in einer Zeile. (1 Wert pro Spalte)

Ich habe mir zwei Möglichkeiten überlegt und würde gerne wissen was davon schneller wäre.

Möglichkeit 1:
Ich bilde eine Abfrage Wenn wert1 in Spalte 1 UND wert2 in spalte 2 UND wert 3 in spalte 3 UND…

Möglichkeit 2:
Ich bilde noch vor dem Befüllen der 1.000.000 Zeile, einen eindeutigen HashCode die jeweilige Zeile würde dann in der zeilennummer = hashcode gespeichert.
Wenn ich jetzt nach einem Eintrag suchen will, dann brauche ich den HashCode zu berechnen und dann einfach in dieser Zeile gucken.

Bsp: A,B,C,D,E,F,G = HashCode: 25176 also ist der Eintrag in der Tabelle an der Stelle 25176

Das Problem bei der Möglichkeit 2 ist defininit die aufgeblasene Datenbank, den ich bin sicher es werden paar millionen leere Zeilen auftauchen.

Was ist besser?

Moin,

Kannst Du nicht einfach Deinen Hashwert als weitere Spalte in die vorhandenen Sätze einfügen?

Gruß Klaus

Ich würde sagen das kommt auf verschiedene Einflussfaktoren darauf an.

Werden viele Daten hinzugefügt, wird natürlich beim Einfügen die Dauer deutlich länger wenn ich für jeden Datensatz immer noch den Hashcode berechnen muss,…
Besteht die Gefahr das der Hashcode nicht eindeutig ist und ich somit bei einem Zugriff auf den Hashcode mehr als ein Objekt bekomme.
Von welchem Typ sind die Spalten, die in meinem Schlüssel überprüft werden?
Sind die Spalten Indiziert?

Aber generell würde ich sagen, hat vor allem beim suchen die Version mit dem Hashcode den Vorteil das es keine Suche sondern ein direkter Zugriff ist und ich so sehr Performant bin.

[Edit]

Ohh grade gesehen, du wolltest nicht eine neue Spalte mit dem Hashcode ala ID einführen sondern Zeilen erstellen. Das würde ich eher nicht machen, da es das dann übersichtlich macht und je nach Datenbank und Datentypen auch viel Speicherplatz benötigt, da eine Zeile ohne Information nicht gleich keinen Speicherplatz benötigt.
Und ich glaube generell sollte bei einer anständigen DB 1.000.000 Datensätze noch kein Problem da stellen.

wie auch in Java ist bei HashCode, Verringerung des Informationsgehalt, immer von Doppelten auszugehen,
theoretisch kannst du auch tausende bis sämtliche Einträge mit demselben Code haben

nachträgliche Prüfung nötig, etwa auf die Liste der Ergebnisse der Query


die weitere Binsenweisheit gilt auch hier: will man etwas schneller unter bestimmten Bedingungen haben (Cache, Suche)
dann kann man vorher Zeit und Platz für Indexe, Datenaufbereitung investieren,
Tradeoff den man selbst entscheiden muss


für deinen Fall nicht so spannend, aber als Idee allgemein verwandt:

wenn man noch z.B. ein oder mehrere Begriffe hat, die irgendwo in den 6 Spalten vorkommen,
dann kann man statt (such in Spalte1 OR such in Spalte2 OR .. )
noch (such in Spalte1 || Spalte2 || .. ) in Betracht ziehen, also den dynamischen Zusammenbau aller Spalten zu einem String zur Laufzeit der Query,
gegenüber mehreren LIKE-Abfragen vielleicht sogar schneller

oder auch als eine genauere, aber mit anderen Nachteilen verbundene Variante statt HashCode die Spalten zusammengesetzt in eine 7 Spalte speicherm

sql - Search all columns of a table using a single where condition with single keyword in mysql - Stack Overflow

[QUOTE=vfl_freak;125426]Moin,

Kannst Du nicht einfach Deinen Hashwert als weitere Spalte in die vorhandenen Sätze einfügen?

Gruß Klaus[/QUOTE]

Hi

Diese Möglichkeit kam mir, nachdem ich hier schon gepostet habe. Ich würde dann eine neue Spalte einsetzten mit dem HashCode. Diese muss ich dann unique am besten setzen oder?

Dann würde ich in der Tabelle einfach in HashCode Spalte nach dem richtigen Wert suchen. An dieser Stelle noch eine Frage, ist die Suche schneller wenn die Tabelle nach den HashWert sortiert ist?

man kann eine DB-Tabelle nicht in der DB sortieren, oder?
maximal kann man die Einträge in einer bestimmten Reihenfolge erstellen und annehmen, dass das etwas bewirkt

wenn du alle Einträge vorher planst, wie ich nun sehe, dann doch sicher eh sortiert, wie würdest du denn sonst die Werte von 1 bis 1 Mio. eintragen,
erst 4, dann 564890, dann 19, …? :wink:

edit: aber du bist da ja schon bei der zweiten Idee, ok, die normalen Einträge speichern mit HashCode, ich war wieder bei der ersten…


dein Posting zuletzt läßt nicht erkennen, dass du realisiert hast, dass es zwei String mit demselben Hashcode geben kann?

wenn du (wieder zurück zur ersten Idee) alle Einträge vorher erstellst wäre das ja noch einen Schritt zur HashMap ähnlicher,
allerdings das Doppelten-Problem,
in der mächtigen Programmiersprache kann man es damit lösen, dass beim Eintrag zum HashCode im Array auch mehrere Daten stehen können,
untereinander verknüpft, dynamisch zu durchsuchen,

die Verknüpfung mehrerer Einträge könnte man noch durch eine Spalte irgendwie schaffen, wenn auch bereits komplex beim Einfügen,
Abfrage der weiteren Einträge in SQL in einer Query wäre aber endgültig unpraktikabel

Ist denn überhaupt schon irgendwas implementiert?

Ist denn überhaupt schon einmal gemessen worden wie lange es dauert?

Ist denn überhaupt festgelegt, wie lange es überhaupt dauern darf?

Einfache In-Memory-Lösung in Java, benötigt ca. 70 ms um in 1.000.000 Einträge nach 6 Merkmalen zu durchsuchen.

import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author ionutbaiu
 */
public class Search {

    public static void main(String[] args) {
        Logger log = Logger.getLogger("Search");
        log.info("Start Application");
        class Item {
            
            int a, b, c, d, e, f;

            public Item(int a, int b, int c, int d, int e, int f) {
                this.a = a;
                this.b = b;
                this.c = c;
                this.d = d;
                this.e = e;
                this.f = f;
            }

            @Override
            public String toString() {
                return "Item{" + "a=" + a + ", b=" + b + ", c=" + c + ", d=" + d + ", e=" + e + ", f=" + f + '}';
            }
            
        }
        log.info("Building List");
        Random random = new Random(0);
        List<Item> list = new LinkedList<>();
        for (int i = 0; i < 1_000_000; i++) {
            list.add(new Item(random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt()));
        }
        log.log(Level.INFO, "List has #{0} items", list.size());
        log.log(Level.INFO, "Starting Search {0}", System.currentTimeMillis());
        list.stream().filter((item) -> item.a == 1 && item.b == 2 && item.c == 3 && item.d == 1 && item.e == 2 && item.f == 3).forEach(System.out::println);        
        log.log(Level.INFO, "Search done!    {0}", System.currentTimeMillis());                
    }
}```


Hashing bringt meines Wissens nach Hauptsächlich etwas um die existenz eines Eintrags auszuschliessen.

Primitives Beispiel:
```    public static void main(String[] args) {
       
        System.out.println("Searching for 7, Binary"+Integer.toBinaryString(7));
        
        int hashA = createHash(1,9,5);
        int hashB = createHash(5,10);
        int hashC = createHash(1,5,7,9);
        
        System.out.println("Can A contain 7 "+canContain(7, hashA));
        System.out.println("Can B contain 7 "+canContain(7, hashB));
        System.out.println("Can C contain 7 "+canContain(7, hashC));
        
        System.out.println("Can A contain 17 "+canContain(17, hashA));
        System.out.println("Can B contain 19 "+canContain(19, hashB));
        System.out.println("Can C contain 23 "+canContain(23, hashC));
        
    }
    
    private static int createHash(int...items) {
        for(int item: items) {
            System.out.println(item+": "+Integer.toBinaryString(item));
        }
        
        int hash = 0;
        for(int item: items) {
            hash |= item;
        }
        System.out.println("Hash is "+Integer.toBinaryString(hash));
        return hash;
    }

    private static boolean canContain(int searched, int hash) {        
        
        boolean canContain = ((hash & searched) == searched);
        
        return canContain;
    }```

Gesucht wird die 7, Binär ausgedrückt 0111.

Aus den Daten, also einer Spalte in der Datenbank, wird ein Hashwert gebildet, durch ein Binäres-Oder aller Elemente.

Wenn die 7 nun enthalten sein muss. dann müssen auch alle Binären-Einsen der Sieben im Hash gesetzt sein.

Ist dies nicht, der Fall, dann braucht man auch nicht alle Zahlen durchsuchen und man kann zurückgeben, dass die 7 nicht vorhanden ist.

Wenn im Hash alle 3 Einsen vorhanden sind, dann muss man dennoch den ganzen Datensatz durchgehen um Sicherzustellen ob die 7 Tatsächlich vorhanden ist.
Oder man zieht eine beliebige Anzahl anderer Hashwerte zu Rate. (z.B. Maximum,Minimum in der Spalte)

Probleme gibt es allerdings wenn oft gelöscht wird. Zudem ist die Art und Anzahl der Daten entscheidend gute Hashfunktionen zu finden.

Allerdings sollten solche Dinge von einer guten Datenbank bereits abgedeckt sein, weshalb der Sinn und Zweck dies selbst zu implementieren eher akademischer Natur ist.

Das Problem ist nicht nur die Aufblasung, sondern die Tatsache, dass die Zeilen “berechnete Werte” enthalten - etwas, das man IMMER vermeiden sollte

  1. Ist es überhaupt ein Problem - 1000000 ist nicht viel??

  2. Index auf einige oder alle 6 Spalten

  3. Du kannst deinen Hash auch in einer SELECT-Anweisung verwenden und dann mit WHERE arbeiten

  4. Wenn du ALLE sechs Werte kennst, dann brauchst du doch gar nicht zu suchen - es geht ja dann nur darum, den PK zu finden? Und in dem Fall kannst du ja gleich deinen HashCode als PK verwenden und suchst dann nach dem PK, was immer am schnellsten ist

Nein, denn so etwas können Datenbanken nicht :wink:

Mach es mit einem simplen SELECT. Dafür sind Datenbanken da.

Was ist das denn für eine “Datenbank”? Wenn es eine normale SQL-Datenbank ist, dann brauchst Du die Indizierung i.d.R nicht selbst zu machen. Du kannst ihn die Datenbank anlegen lassen “CREATE INDEX tbl_name (column_names 1-n)” SQL CREATE INDEX Statement

Edit:
Ups, Bleiglanz hatte es schon geschrieben…

[quote=Logic]Zitat Zitat von SlaterB Beitrag anzeigen
man kann eine DB-Tabelle nicht in der DB sortieren, oder?
Nein, denn so etwas können Datenbanken nicht[/quote]
Naja, AFAIK macht MySql das für den PK automatisch so. Nur darauf verlassen sollte man sich nicht…

bye
TT

Ob es die Daten sortiert oder nur tolle Bäume für die Indexe-erstellt (die dadurch sortiert sind) ist für den Zugriff relativ egal, da nur in dem Index gesucht wird und dann ja direkt auf dieses Feld (Zeile) zugegriffen wird.
Wenn man nun alle seine 6 Felder in den Index aufnimmt sollte es also genau das machen, was der TO will.