Langsame Volltextsuche nach Begriffen mit hohem Vorkommen

8

Ich habe eine Tabelle, die Daten enthält, die aus Textdokumenten extrahiert werden. Die Daten werden in einer Spalte gespeichert, "CONTENT"für die ich diesen Index mit GIN erstellt habe:

CREATE INDEX "File_contentIndex"
  ON "File"
  USING gin
  (setweight(to_tsvector('english'::regconfig
           , COALESCE("CONTENT", ''::character varying)::text), 'C'::"char"));

Ich verwende die folgende Abfrage, um eine Volltextsuche für die Tabelle durchzuführen:

SELECT "ITEMID",
  ts_rank(setweight(to_tsvector('english', coalesce("CONTENT",'')), 'C') , 
  plainto_tsquery('english', 'searchTerm')) AS "RANK"
FROM "File"
WHERE setweight(to_tsvector('english', coalesce("CONTENT",'')), 'C') 
  @@ plainto_tsquery('english', 'searchTerm')
ORDER BY "RANK" DESC
LIMIT 5;

Die Dateitabelle enthält 250 000 Zeilen und jeder "CONTENT"Eintrag besteht aus einem zufälligen Wort und einer Textzeichenfolge, die für alle Zeilen gleich ist.

Wenn ich jetzt nach einem zufälligen Wort suche (1 Treffer in der gesamten Tabelle), wird die Abfrage sehr schnell ausgeführt (<100 ms). Wenn ich jedoch nach einem Wort suche, das in allen Zeilen vorhanden ist, wird die Abfrage extrem langsam ausgeführt (10 Minuten oder länger).

EXPLAIN ANALYZEzeigt, dass für die 1-Treffer-Suche ein Bitmap-Index-Scan gefolgt von einem Bitmap-Heap-Scan durchgeführt wird. Für die langsame Suche wird stattdessen ein Seq-Scan durchgeführt, was so lange dauert.

Zugegeben, es ist nicht realistisch, in allen Zeilen dieselben Daten zu haben. Da ich jedoch weder die von den Benutzern hochgeladenen Textdokumente noch die von ihnen durchgeführten Suchvorgänge steuern kann, tritt möglicherweise ein ähnliches Szenario auf (Suche nach Begriffen mit sehr hohem Vorkommen in der Datenbank). Wie kann ich die Leistung meiner Suchanfrage für ein solches Szenario steigern?

Ausführen von PostgreSQL 9.3.4

Abfragepläne von EXPLAIN ANALYZE:

Schnellsuche (1 Treffer in DB)

"Limit  (cost=2802.89..2802.90 rows=5 width=26) (actual time=0.037..0.037 rows=1 loops=1)"
"  ->  Sort  (cost=2802.89..2806.15 rows=1305 width=26) (actual time=0.037..0.037 rows=1 loops=1)"
"        Sort Key: (ts_rank(setweight(to_tsvector('english'::regconfig, (COALESCE("CONTENT", ''::character varying))::text), 'C'::"char"), '''wfecg'''::tsquery))"
"        Sort Method: quicksort  Memory: 25kB"
"        ->  Bitmap Heap Scan on "File"  (cost=38.12..2781.21 rows=1305 width=26) (actual time=0.030..0.031 rows=1 loops=1)"
"              Recheck Cond: (setweight(to_tsvector('english'::regconfig, (COALESCE("CONTENT", ''::character varying))::text), 'C'::"char") @@ '''wfecg'''::tsquery)"
"              ->  Bitmap Index Scan on "File_contentIndex"  (cost=0.00..37.79 rows=1305 width=0) (actual time=0.012..0.012 rows=1 loops=1)"
"                    Index Cond: (setweight(to_tsvector('english'::regconfig, (COALESCE("CONTENT", ''::character varying))::text), 'C'::"char") @@ '''wfecg'''::tsquery)"
"Total runtime: 0.069 ms"

Langsame Suche (250.000 Treffer in der DB)

"Limit  (cost=14876.82..14876.84 rows=5 width=26) (actual time=519667.404..519667.405 rows=5 loops=1)"
"  ->  Sort  (cost=14876.82..15529.37 rows=261017 width=26) (actual time=519667.402..519667.402 rows=5 loops=1)"
"        Sort Key: (ts_rank(setweight(to_tsvector('english'::regconfig, (COALESCE("CONTENT", ''::character varying))::text), 'C'::"char"), '''cyberspace'''::tsquery))"
"        Sort Method: top-N heapsort  Memory: 25kB"
"        ->  Seq Scan on "File"  (cost=0.00..10541.43 rows=261017 width=26) (actual time=2.097..519465.953 rows=261011 loops=1)"
"              Filter: (setweight(to_tsvector('english'::regconfig, (COALESCE("CONTENT", ''::character varying))::text), 'C'::"char") @@ '''cyberspace'''::tsquery)"
"              Rows Removed by Filter: 6"
"Total runtime: 519667.429 ms"
Danjo
quelle
1
Aus dem Kopf: GIN-Indizes wurden in Postgres 9.4 (und in den kommenden 9.5) noch erheblich verbessert. Ein Upgrade auf die aktuelle Version 9.4 wird sich sicherlich lohnen. Und ich würde auch die Leistung von GiST anstelle des GIN-Index untersuchen. Der Schuldige in Ihrer Anfrage ist ORDER BY "RANK" DESC. Ich würde pg_trgmmit dem GiST-Index und den Ähnlichkeits- / Distanzoperatoren als Alternative untersuchen. Bedenken Sie: dba.stackexchange.com/questions/56224/… . Könnte sogar "bessere" Ergebnisse liefern (außer schneller zu sein).
Erwin Brandstetter
Auf welchem ​​Betriebssystem führen Sie Ihre PostgreSQL-Instanz aus?
Kassandry
Können Sie diese wiederholen explain (analyze, buffers), vorzugsweise mit track_io_timing auf ON? Es sollte auf keinen Fall 520 Sekunden dauern, bis diese Tabelle gescannt wurde, es sei denn, Sie haben sie auf einem RAID von Disketten gespeichert. Dort ist definitiv etwas pathologisch. Was ist Ihre Einstellung random_page_costund die anderen Kostenparameter?
jjanes
@danjo Ich habe die gleichen Probleme, auch wenn ich keine Bestellung verwende. Kannst du mir sagen, wie du es repariert hast?
Sahil Bahl

Antworten:

11

Fragwürdiger Anwendungsfall

... jeder CONTENT-Eintrag besteht aus einem zufälligen Wort und einer Textzeichenfolge, die für alle Zeilen gleich ist.

Eine Textzeichenfolge, die für alle Zeilen gleich ist, ist nur tote Fracht. Entfernen Sie es und verketten Sie es in einer Ansicht, wenn Sie es anzeigen müssen.

Offensichtlich sind Sie sich dessen bewusst:

Zugegeben, es ist nicht realistisch ... Aber da ich den Text nicht kontrollieren kann ...

Aktualisieren Sie Ihre Postgres-Version

Ausführen von PostgreSQL 9.3.4

Während Sie noch mit Postgres 9.3 arbeiten, sollten Sie mindestens auf die neueste Punktversion (derzeit 9.3.9) aktualisieren. Die offizielle Empfehlung des Projekts:

Wir empfehlen immer, dass alle Benutzer die neueste verfügbare Nebenversion für die jeweils verwendete Hauptversion ausführen.

Besser noch, aktualisieren Sie auf 9.4, das wesentliche Verbesserungen für GIN-Indizes erhalten hat .

Hauptproblem 1: Kostenvoranschläge

Die Kosten einiger Textsuchfunktionen wurden bis einschließlich Version 9.4 stark unterschätzt. Diese Kosten werden in der kommenden Version 9.5 um den Faktor 100 erhöht, wie @jjanes in seiner jüngsten Antwort beschreibt:

Hier sind der jeweilige Thread, in dem dies besprochen wurde, und die Commit-Nachricht von Tom Lane.

Wie Sie in der Commit-Nachricht sehen können, to_tsvector()gehört zu diesen Funktionen. Sie können die Änderung sofort (als Superuser) anwenden:

ALTER FUNCTION to_tsvector (regconfig, text) COST 100;

Dies sollte es viel wahrscheinlicher machen, dass Ihr Funktionsindex verwendet wird.

Hauptproblem 2: KNN

Das Kernproblem besteht darin, dass Postgres einen Rang mit ts_rank()für 260.000 Zeilen ( rows=261011) berechnen muss, bevor es nach den Top 5 bestellen und diese auswählen kann. Dies wird teuer , selbst nachdem Sie andere Probleme wie beschrieben behoben haben. Es handelt sich von Natur aus um ein K-Nearest-Neighbour-Problem (KNN), und es gibt Lösungen für verwandte Fälle. Ich kann mir jedoch keine allgemeine Lösung für Ihren Fall vorstellen, da die Rangberechnung selbst von Benutzereingaben abhängt. Ich würde versuchen, den Großteil der Spiele mit niedrigem Rang frühzeitig zu eliminieren, damit die vollständige Berechnung nur für wenige gute Kandidaten durchgeführt werden muss.

Eine Möglichkeit, die ich mir vorstellen kann , besteht darin , Ihre Volltextsuche mit der Suche nach Trigrammähnlichkeit zu kombinieren - eine funktionierende Implementierung für das KNN-Problem. Auf diese Weise können Sie die "besten" Übereinstimmungen mit LIKEPrädikat als Kandidaten vorab auswählen ( LIMIT 50z. B. in einer Unterabfrage mit ) und dann die 5 Zeilen mit dem höchsten Rang gemäß Ihrer Rangberechnung in der Hauptabfrage auswählen.

Oder wenden Sie beide Prädikate in derselben Abfrage an und wählen Sie die engsten Übereinstimmungen gemäß der Trigrammähnlichkeit (die zu unterschiedlichen Ergebnissen führen würde) wie in dieser verwandten Antwort aus:

Ich habe noch etwas recherchiert und Sie sind nicht die Ersten, die auf dieses Problem stoßen. Verwandte Beiträge zu pgsql-general:

Es wird daran gearbeitet, einen tsvector <-> tsqueryOperator zu implementieren .

Oleg Bartunov und Alexander Korotkov stellten sogar einen funktionierenden Prototyp vor (der damals ><als Operator verwendet wurde <->), aber die Integration in Postgres ist sehr komplex. Die gesamte Infrastruktur für GIN-Indizes muss überarbeitet werden (die meisten davon sind inzwischen erledigt).

Hauptproblem 3: Gewichte und Index

Und ich habe einen weiteren Faktor identifiziert, der zur Langsamkeit der Abfrage beiträgt. Pro Dokumentation:

GIN-Indizes sind für Standardabfragen nicht verlustbehaftet, ihre Leistung hängt jedoch logarithmisch von der Anzahl der eindeutigen Wörter ab. ( In GIN-Indizes werden jedoch nur die Wörter (Lexeme) von tsvectorWerten und nicht deren Gewichtungsbezeichnungen gespeichert . Daher ist eine erneute Überprüfung der Tabellenzeilen erforderlich, wenn eine Abfrage mit Gewichten verwendet wird.)

Meine kühne Betonung. Sobald es um Gewicht geht, muss jede Zeile vom Haufen geholt werden (nicht nur eine billige Sichtbarkeitsprüfung) und lange Werte müssen entgeröst werden, was die Kosten erhöht. Aber dafür scheint es eine Lösung zu geben:

Indexdefinition

Wenn Sie sich Ihren Index noch einmal ansehen, scheint es zunächst nicht sinnvoll zu sein. Sie weisen einer einzelnen Spalte eine Gewichtung zu, was bedeutungslos ist , solange Sie keine anderen Spalten mit einer anderen Gewichtung verketten .

COALESCE() macht auch keinen Sinn, solange Sie nicht mehr Spalten verketten.

Vereinfachen Sie Ihren Index:

CREATE INDEX "File_contentIndex" ON "File" USING gin
(to_tsvector('english', "CONTENT");

Und Ihre Frage:

SELECT "ITEMID", ts_rank(to_tsvector('english', "CONTENT")
                       , plainto_tsquery('english', 'searchTerm')) AS rank
FROM   "File"
WHERE  to_tsvector('english', "CONTENT")
       @@ plainto_tsquery('english', 'searchTerm')
ORDER  BY rank DESC
LIMIT  5;

Immer noch teuer für einen Suchbegriff, der zu jeder Zeile passt, aber wahrscheinlich viel weniger.

Nebenbei

All diese Probleme zusammen ergeben die wahnsinnigen Kosten von 520 Sekunden für Ihre zweite Abfrage allmählich Sinn. Aber es kann noch mehr Probleme geben. Haben Sie Ihren Server konfiguriert?
Es gelten alle üblichen Hinweise zur Leistungsoptimierung.

Es erleichtert Ihnen das Leben, wenn Sie nicht mit CaMeL-Fallkennungen in doppelten Anführungszeichen arbeiten:

Erwin Brandstetter
quelle
Ich stoße auch darauf. In Postgresql 9.6 verwenden wir das Umschreiben von Abfragen für Synonyme, sodass ich nicht denke, dass die Verwendung der Trigram-Ähnlichkeitssuche zur Begrenzung der Anzahl der Dokumente gut funktioniert.
Pholly
Tolle! USING gin (to_tsvector('english', "CONTENT")
K-Gun
1

Ich hatte ein ähnliches Problem. Ich habe mich darum gekümmert, indem ich den ts_rank jedes gängigen Textabfragebegriffs für ein Feld: Tabellentupel vorberechnet und in einer Nachschlagetabelle gespeichert habe. Dies sparte mir viel Zeit (Faktor 40X) bei der Suche nach beliebten Wörtern im textlastigen Korpus.

  1. Holen Sie sich beliebte Wörter in den Korpus, indem Sie das Dokument scannen und seine Vorkommen zählen.
  2. Sortieren nach dem beliebtesten Wort.
  3. Berechnen Sie ts_rank der beliebten Wörter vor und speichern Sie es in einer Tabelle.

Abfrage: Suchen Sie in dieser Tabelle nach den sortierten Dokument-IDs nach ihrem jeweiligen Rang. Wenn nicht, mach es auf die alte Art und Weise.

Pari Rajaram
quelle