So durchsuchen Sie schnell eine sehr große Liste von Zeichenfolgen / Datensätzen in einer Datenbank

32

Ich habe das folgende Problem: Ich habe eine Datenbank mit mehr als 2 Millionen Datensätzen. Jeder Datensatz hat ein Zeichenkettenfeld X und ich möchte eine Liste von Datensätzen anzeigen, für die Feld X eine bestimmte Zeichenkette enthält. Jeder Datensatz ist ungefähr 500 Byte groß.

Um es konkreter zu machen: In der Benutzeroberfläche meiner Anwendung habe ich ein Textfeld, in das ich eine Zeichenfolge eingeben kann. Über dem Textfeld befindet sich eine Tabelle mit den (ersten N, z. B. 100) Datensätzen, die mit der Zeichenfolge im Textfeld übereinstimmen. Wenn ich ein Zeichen in das Textfeld eingebe oder lösche, muss der Tabelleninhalt sofort aktualisiert werden.

Ich frage mich, ob es einen effizienten Weg gibt, dies mit geeigneten Indexstrukturen und / oder Caching zu tun. Wie oben erläutert, möchte ich nur die ersten N Elemente anzeigen, die der Abfrage entsprechen. Daher sollte es für N, das klein genug ist, kein großes Problem sein, die übereinstimmenden Elemente aus der Datenbank zu laden. Außerdem kann das Zwischenspeichern von Elementen im Hauptspeicher das Abrufen beschleunigen.

Ich denke, das Hauptproblem ist, wie man die zusammenpassenden Einzelteile schnell findet, gegeben der Musterzeichenkette. Kann ich mich auf einige DBMS-Funktionen verlassen oder muss ich selbst einen speicherinternen Index erstellen? Irgendwelche Ideen?

BEARBEITEN

Ich habe ein erstes Experiment durchgeführt. Ich habe die Datensätze in verschiedene Textdateien aufgeteilt (höchstens 200 Datensätze pro Datei) und die Dateien in verschiedene Verzeichnisse gestellt (ich habe den Inhalt eines Datenfelds verwendet, um den Verzeichnisbaum zu bestimmen). Am Ende habe ich ungefähr 50000 Dateien in ungefähr 40000 Verzeichnissen. Ich habe dann Lucene ausgeführt, um die Dateien zu indizieren. Die Suche nach einer Zeichenfolge mit dem Lucene-Demoprogramm ist ziemlich schnell. Das Aufteilen und Indizieren dauerte einige Minuten. Dies ist für mich völlig akzeptabel, da es sich um einen statischen Datensatz handelt, den ich abfragen möchte.

Der nächste Schritt besteht darin, Lucene in das Hauptprogramm zu integrieren und die von Lucene zurückgegebenen Treffer zu verwenden, um die relevanten Datensätze in den Hauptspeicher zu laden.

Giorgio
quelle
2
2 Millionen Datensätze * 500 Byte = 1 GB Daten. Das sind eine Menge Daten, die durchsucht werden müssen, unabhängig davon, wie Sie vorgehen - ist es wahrscheinlich, dass jeder Wert von X eindeutig ist, oder werden Sie viele Datensätze mit demselben Wert von X haben?
1
Das wären auch viele Daten, die im Speicher gespeichert werden müssen, um sie schnell abzurufen. Das entspricht mehr als 1 GB pro Benutzersitzung.
maple_shaft
Mein vorheriger Kommentar geht von einer Webanwendung aus. Ist das eine Webanwendung?
maple_shaft
Es ist eine Desktop-Anwendung. Werte in den Datensätzen sind nicht unbedingt eindeutig. Außerdem suche ich nach einem Teilstring, der nicht exakt übereinstimmt.
Giorgio
@maple_shaft: Ich würde nur die Datensätze zwischenspeichern, auf die ich kürzlich zugegriffen habe. Wenn ich die Abfragezeichenfolge ändere und ein Datensatz immer noch übereinstimmt, befindet er sich immer noch im Cache.
Giorgio

Antworten:

20

Anstatt Ihre Daten in der Datenbank abzulegen, können Sie sie als eine Reihe von Dokumenten (Textdateien) separat aufbewahren und die Verknüpfung (Pfad / URL usw.) in der Datenbank aufbewahren.

Dies ist wichtig, da SQL-Abfragen aufgrund ihres Designs sowohl bei der Suche nach Unterzeichenfolgen als auch beim Abrufen sehr langsam sind.

Nun ist Ihr Problem so formuliert, dass Sie die Textdateien durchsuchen müssen, die die Zeichenfolgen enthalten. Hier gibt es zwei Möglichkeiten.

  1. Übereinstimmung der Unterzeichenfolge Wenn Ihre Text-Blobs ein einzelnes Wort oder ein einzelnes Wort (ohne Leerzeichen) sind und Sie eine beliebige Unterzeichenfolge darin suchen müssen. In solchen Fällen müssen Sie jede Datei analysieren, um die bestmöglichen Dateien zu finden, die übereinstimmen. Man benutzt Algorithmen wie den Boyer Moor-Algorithmus. Siehe dies und das für Details. Dies ist auch gleichbedeutend mit grep - da grep ähnliche Inhalte verwendet. Aber Sie können immer noch mindestens 100 Grep (Worst Case 2 Millionen) machen, bevor Sie zurückkehren.

  2. Indizierte Suche. In diesem Beispiel wird davon ausgegangen, dass der Text mehrere Wörter enthält und die Suche auf feste Wortlängen beschränkt ist. In diesem Fall wird das Dokument über alle möglichen Vorkommen von Wörtern indiziert. Dies wird häufig als "Volltextsuche" bezeichnet. Dazu gibt es eine Reihe von Algorithmen und Open Source-Projekte, die direkt verwendet werden können. Viele von ihnen unterstützen auch die Platzhaltersuche, die ungefähre Suche usw. wie folgt:
    a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
    b. OpenFTS: http://openfts.sourceforge.net/
    c. Sphinx http://sphinxsearch.com/

Wenn Sie "feste Wörter" als Abfragen benötigen, ist der zweite Ansatz höchstwahrscheinlich sehr schnell und effektiv.

Dipan Mehta
quelle
2
Dies ist ein interessantes Konzept, aber es ist unwahrscheinlich, dass ein Entwickler problemlos 1 GB Textdaten schneller und effizienter durchsuchen kann als eine Datenbank-Engine. Viel klügere Leute als Sie und ich haben uns Mühe gegeben, genau das mit den Abfrageoptimierern zu tun, und es ist ein bisschen naiv zu glauben, dass Sie das irgendwie effizienter machen können.
maple_shaft
4
@maple_shaft Die Beispiele, die ich gegeben habe, sind keine RDBMS-Datenbank-Engines. Sie sind eher wie "Suchmaschinen", wenn Sie es nennen möchten. Es gibt einen großen konzeptionellen Unterschied zwischen dem Abrufen einer Liste aus einem Index (oder einer Hash-Tabelle) und dem erneuten Durchsuchen von 1 GB Daten bei jedem Auslösen einer Abfrage. Also, was ich vorschlage, ist keine kleine Veränderung.
Dipan Mehta
Dies scheint eine interessante Idee zu sein, aber ich frage mich, wie es funktionieren würde. Ich hätte mehr als 2 000 000 Dateien mit einer Größe von jeweils etwa einem halben Kilobyte. Oder schlagen Sie mehr als einen Datensatz pro Datei vor? Was wäre der Unterschied zu einer Datenbank?
Giorgio
Ich bin nicht davon überzeugt, dass dies notwendigerweise besser abschneiden würde als beispielsweise der SQL-Volltextindex.
Kirk Broadhurst
@Giorgio - ja so würden Volltextsuchmaschinen funktionieren. Der Hauptunterschied besteht darin, dass vorindizierte Seiten im Vergleich zur Suche im Arbeitsspeicher (bei jeder Abfrage) vorindiziert sind.
Dipan Mehta
21

Die Technologie, nach der Sie suchen, ist die Volltextindizierung. Die meisten RDBMS haben eine Art von integrierten Funktionen, die hier funktionieren könnten, oder Sie könnten etwas wie Lucene verwenden, wenn Sie schicker werden und / oder es einfach im Speicher ausführen möchten.

Wyatt Barnett
quelle
1
Meiner Meinung nach sind die Volltextoptionen in jedem RDBMS eine Problemumgehung, um etwas zu tun, für das es nicht entwickelt wurde: "Suche in einem Stapel unstrukturierter, nicht verwandter Daten". Wenn Sie eine Suchmaschine bauen, verwenden Sie einfach kein RDBMS. Es kann für kleine Datenmengen funktionieren, lässt jedoch jede Art von Skalierung zu. Das Durchsuchen von unstrukturierten Daten ist kein Nagel, verwenden Sie also keinen Hammer. Verwenden Sie das richtige Werkzeug für den Job.
Pieter B
8

Hast du über einen Versuch nachgedacht ? Grundsätzlich erstellen Sie einen Baum mit gemeinsamen Präfixen, sodass alle Wörter, die mit denselben Buchstaben beginnen, untergeordnete Elemente desselben Knotens sind. Wenn Sie Matching für einen beliebigen Teilstring unterstützen möchten, müssen Sie eine Art permutierten Index generieren und daraus Ihren Versuch erstellen. Das kann jedoch dazu führen, dass Ihre Speicheranforderungen in die Knie gezwungen werden.

TMN
quelle
1
JA! Ich dachte über eine Baumstruktur nach und erinnerte mich, dass es etwas Ähnliches gab, das zu mir passen könnte, aber ich erinnerte mich nicht an die Tries, weil ich sie nie benutzt habe. Zur Speicheranforderung: Denken Sie daran, dass ich nur die ersten N Einträge abrufen muss (z. B. N = 100), da es keinen Sinn macht, eine Tabelle mit 20000 Treffern zu füllen. Jeder Knoten des Versuchs würde also auf höchstens N Einträge verweisen. Außerdem habe ich vergessen zu erwähnen, dass ich einen schnellen Zugriff benötige, aber kein schnelles Update, da die Daten nur einmal geladen werden. Die erste Idee für einen permutierten Index könnte wirklich funktionieren!
Giorgio
1
Gute Antwort , aber wie Sie beachten, ist ein Trie groß für den passenden Start Ihrer Worte , sondern wird schnell bekommen komplex und sehr groß , wenn jeder Teil passenden ...
Kirk Broadhurst
Als erstes Experiment habe ich versucht, die Menge aller Unterstrings zu erstellen, die in den zu suchenden Strings vorkommen und die, wenn ich das richtig verstehe, den Pfaden des Versuchs entsprechen. Ich habe eine Out-of-Memory-Ausnahme (mit 256M Heap für die JVM) bei Teilstrings der Länge 6 erhalten. Ich fürchte, diese Lösung ist nicht durchführbar, es sei denn, ich mache etwas falsch.
Giorgio,
5

Ich möchte Wyatt Barnetts Antwort hinzufügen, dass eine RDBMS-Lösung mit Volltextindizierung für die entsprechende Spalte funktioniert. Wenn Sie jedoch einen lokalen Cache mit zuvor abgerufenen Datensätzen verwenden möchten, müssen Sie einen Plan erstellen, um diese zwischengespeicherten Datensätze zu verwenden zu Ihrem Vorteil.

Eine Möglichkeit besteht darin, die eindeutigen Bezeichner dieser Datensätze zu erfassen, die Sie AUSSCHLIESSLICH nicht aus der Abfrage abrufen möchten, und sie möglicherweise in a NOT INoder a aufzunehmen NOT EXISTS.

Vorsichtshinweis: Die Verwendung von NOT INoder ist NOT EXISTSin der Regel nicht billig und kann die Abfrageleistung oder den Abfrageplan je nach verwendetem Datenbankmodul negativ beeinflussen. Führen Sie einen EXPLAIN-Plan für Ihre endgültige Abfrage aus, um sicherzustellen, dass alle Ihre Indizes für die betroffenen Spalten verwendet werden.

Es schadet auch nicht, einen Leistungsvergleich zwischen den beiden Ansätzen durchzuführen, um festzustellen, welche schneller sind. Es kann Sie überraschen, dass das Verwalten eines lokalen Caches und das explizite Filtern dieser aus Ihrer Abfrage möglicherweise eine schlechtere Leistung aufweist als eine fein abgestimmte Abfrage, die alle Datensätze abruft.

maple_shaft
quelle
maple_shaft und @Wyatt Barnett: Vielen Dank für die Vorschläge. Ich muss etwas lesen und verschiedene Lösungen ausprobieren. Nicht alle Datenbanken unterstützen die vollständige Indizierung, MySQL (das ich derzeit verwende) ( dev.mysql.com/doc/refman/5.5/en/fulltext-search.html ). Ich werde versuchen, einige Tests durchzuführen und dann hier Bericht erstatten.
Giorgio
2

Nur für den Fall, dass Sie es verpasst haben. Wenn Sie für Ihre Datenbank Lucene anstelle einer von In-DB unterstützten Textsuche verwenden, müssen Sie beim Ändern Ihrer Datenbank äußerst vorsichtig sein. Wie stellen Sie sicher, dass Sie atomar arbeiten können, wenn Sie sowohl in der Datenbank als auch in den externen Ressourcen (Lucene) Änderungen vornehmen müssen? Ja, es kann getan werden, aber es wird viel Arbeit geben.

Kurz gesagt, Sie verlieren die DB-Transaktionsunterstützung, wenn Sie Lucene in Ihr Datenschema aufnehmen.

InformedA
quelle
1
Wie bereits erwähnt, scheint das Problem ohnehin nicht für ein RDMS geeignet zu sein.
Pieter B
1

Haben Sie an Sphinx gedacht? http://sphinxsearch.com Wenn Sie ein Tool eines Drittanbieters verwenden können, ist dies ideal für das, was Sie erreichen möchten. Es ist bei der Volltextsuche viel effizienter als jedes RDBMS, das ich persönlich verwendet habe.

Zweig
quelle
3
und die Abstimmung ist für?
Twigg
1

Es ist etwas seltsam, dass keine der Antworten den Begriff "invertierter Index" enthielt , die Technologie, die allen Lösungen ähnlich wie Apache Lucene und anderen zugrunde liegt.

Der invertierte Index ist eine Zuordnung von Wörtern zu Dokumenten ("invertierter Index auf Datensatzebene") oder sogar zu genauen Wortpositionen innerhalb des Dokuments ("invertierter Index auf Wortebene").

UND- und ODER-Verknüpfungen sind einfach zu implementieren. Wenn Sie über genaue Wortpositionen verfügen, können Sie nach benachbarten Wörtern suchen und so die Suche nach Phrasen ermöglichen.

Stellen Sie sich also einen Index vor, der Tupel (Wort, Datei, Speicherort) enthält. Wenn Sie zB ("inverted", "foo.txt", 123) haben, prüfen Sie einfach, ob ("index", "foo.txt", 124) Teil des Index ist, um nach der vollständigen Phrase "inverted index" zu suchen. .

Ich empfehle Ihnen zwar nicht, eine Volltextsuchmaschine von Grund auf neu zu implementieren, es ist jedoch hilfreich zu wissen, wie Technologien wie Apache Lucene funktionieren.

Daher empfehle ich, zu lernen, wie invertierte Indizes funktionieren, und eine Technologie wie Apache Lucene zu wählen. Dann haben Sie zumindest ein solides Verständnis dafür, was getan werden kann und was nicht.

juhist
quelle