it-swarm-eu.dev

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

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

Um es konkreter zu machen: In der GUI 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 passenden Elemente angesichts der Musterzeichenfolge schnell findet. Kann ich mich auf einige DBMS-Funktionen verlassen oder muss ich selbst einen In-Memory-Index erstellen? Irgendwelche Ideen?

EDIT

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 einem String mit dem Lucene-Demo-Programm 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.

33
Giorgio

Anstatt Ihre Daten in der Datenbank abzulegen, können Sie sie als Satz von Dokumenten (Textdateien) separat aufbewahren und den Link (Pfad/URL usw.) in der Datenbank behalten.

Dies ist wichtig, da die SQL-Abfrage von Entwurf sowohl bei der Suche nach Teilzeichenfolgen als auch beim Abrufen sehr langsam ist.

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

  1. Sub-String-Übereinstimmung Wenn Ihr Text-Blobs ein einzelner Stich oder ein Wort (ohne Leerzeichen) ist und Sie einen beliebigen Sub-String darin suchen müssen. In solchen Fällen müssen Sie jede Datei analysieren, um die bestmöglichen Dateien zu finden, die übereinstimmen. Man verwendet Algorithmen wie den Boyer Moor-Algorithmus. Siehe this und this für Details. Dies ist auch gleichbedeutend mit grep - da grep ähnliche Inhalte verwendet. Aber Sie können immer noch mindestens 100+ Grep (schlimmster Fall 2 Millionen) machen, bevor Sie zurückkehren.

  2. Indizierte Suche. Hier nehmen Sie an, dass Text eine Reihe von Wörtern 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 oft als "Volltextsuche" bezeichnet. Hierfür 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:
    ein. 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.

20
Dipan Mehta

Die Technologie, nach der Sie suchen, ist die Volltextindizierung. Die meisten RDBMS verfügen über integrierte 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.

21
Wyatt Barnett

Haben Sie ein trie in Betracht gezogen? 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 das Matching auf einem Teilstring unterstützen möchten, müssen Sie eine Art permutierter Index generieren und daraus Ihren Versuch erstellen. Dies kann jedoch dazu führen, dass Ihre Speicheranforderungen erheblich beeinträchtigt werden.

8
TMN

Ich möchte zusätzlich zu 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 zur Verwendung dieser zwischengespeicherten Datensätze erstellen zu Ihrem Vorteil.

Eine Möglichkeit besteht darin, die eindeutigen Kennungen dieser Datensätze zu sammeln, die Sie AUSSCHLIESSLICH nicht aus der Abfrage abrufen möchten, und sie möglicherweise in einen NOT IN Oder einen NOT EXISTS Einzuschließen.

Vorsicht, die Verwendung von NOT IN Oder NOT EXISTS Ist in der Regel nicht billig und kann die Abfrageleistung oder den Abfrageplan je nach verwendetem Datenbankmodul negativ beeinflussen. Führen Sie bei Ihrer letzten Abfrage einen Erklärungsplan 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, welcher schneller ist. 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.

5
maple_shaft

Nur für den Fall, dass Sie es verpasst haben. Wenn Sie Lucene für Ihre Datenbank anstelle der von der Datenbank unterstützten Textsuche verwenden, müssen Sie bei Änderungen an Ihrer Datenbank äußerst vorsichtig sein. Wie stellen Sie sicher, dass Sie atomar sein können, wenn Sie Änderungen sowohl an der Datenbank als auch an den externen Ressourcen (Lucene) 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.

2
InformedA

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

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

AND und OR logische Operationen sind trivial zu implementieren. Wenn Sie genaue Wortpositionen haben, 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 (Word, Datei, Speicherort) enthält. Wenn Sie z. ("invertiert", "foo.txt", 123) dann prüfen Sie einfach, ob ("index", "foo.txt", 124) Teil des Index ist, um nach der vollständigen Phrase "invertierter Index" zu suchen.

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

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

1
juhist

Haben Sie über Sphinx nachgedacht? 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 habe benutzt.

1
twigg