Die Trigrammsuche wird viel langsamer, je länger die Suchzeichenfolge wird

16

In einer Postgres 9.1-Datenbank habe ich eine Tabelle table1mit ~ 1,5 Millionen Zeilen und einer Spalte label(vereinfachte Namen für diese Frage).

Es gibt einen funktionalen Trigramm-Index für lower(unaccent(label))( unaccent()wurde unveränderlich gemacht, damit er im Index verwendet werden kann).

Die folgende Abfrage ist ziemlich schnell:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword%')));
 count 
-------
     1
(1 row)

Time: 394,295 ms

Die folgende Abfrage ist jedoch langsamer:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword and some more%')));
 count 
-------
     1
(1 row)

Time: 1405,749 ms

Das Hinzufügen weiterer Wörter ist sogar noch langsamer, obwohl die Suche strenger ist.

Ich habe einen einfachen Trick ausprobiert, um eine Unterabfrage für das erste Wort und dann eine Abfrage mit der vollständigen Suchzeichenfolge auszuführen, aber (leider) hat der Abfrageplaner meine Aktionen durchgesehen:

EXPLAIN ANALYZE
SELECT * FROM (
   SELECT id, title, label from table1
   WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(unaccent(label)) like lower(unaccent('%someword and some more%'));
Bitmap-Heap-Scan für Tabelle 1 (Kosten = 16216.01..16220.04 Zeilen = 1 Breite = 212) (tatsächliche Zeit = 1824.017..1824.019 Zeilen = 1 Schleifen = 1)
  Überprüfen Sie erneut Cond: ((lower (unaccent ((label) :: text)) ~~ '% someword%' :: text) UND (lower (unaccent ((label) :: text)) ~~ '% someword und einige mehr %'::Text))
  -> Bitmap-Index-Scan für table1_label_hun_gin_trgm (Kosten = 0,00..16216,01 Zeilen = 1 Breite = 0) (tatsächliche Zeit = 1823.900..1823.900 Zeilen = 1 Schleifen = 1)
        Indexbedingung: ((niedriger (unaccent ((label) :: text)) ~~ '% someword%' :: text) UND (niedriger (unaccent ((label) :: text)) ~~ '% someword und einige mehr %'::Text))
Gesamtlaufzeit: 1824.064 ms

Mein letztendliches Problem ist, dass die Suchzeichenfolge von einer Webschnittstelle stammt, die möglicherweise sehr lange Zeichenfolgen sendet und daher sehr langsam ist und möglicherweise auch einen DOS-Vektor darstellt.

Meine Fragen sind also:

  • Wie kann die Abfrage beschleunigt werden?
  • Gibt es eine Möglichkeit, es in Unterabfragen aufzuteilen, damit es schneller ist?
  • Vielleicht ist eine spätere Version von Postgres besser? (Ich habe 9.4 ausprobiert und es scheint nicht schneller: immer noch der gleiche Effekt. Vielleicht eine spätere Version?)
  • Möglicherweise ist eine andere Indizierungsstrategie erforderlich?
P.Péter
quelle
1
Es muss erwähnt werden, dass dies unaccent()auch durch ein zusätzliches Modul bereitgestellt wird und Postgres standardmäßig keine Indizes für die Funktion unterstützt, da dies nicht der Fall ist IMMUTABLE. Sie müssen etwas geändert haben und Sie sollten in Ihrer Frage genau angeben, was Sie getan haben. Mein ständiger Rat: stackoverflow.com/a/11007216/939860 . Darüber hinaus unterstützen Trigrammindizes den Abgleich ohne Berücksichtigung der Groß- und Kleinschreibung. Sie können vereinfachen: WHERE f_unaccent(label) ILIKE f_unaccent('%someword%')- mit einem passenden Index. Details: stackoverflow.com/a/28636000/939860 .
Erwin Brandstetter
Ich erklärte einfach unaccentunveränderlich. Ich habe dies der Frage hinzugefügt.
P.Péter,
Beachten Sie, dass der Hack beim Aktualisieren des unaccentModuls überschrieben wird. Einer der Gründe, warum ich stattdessen einen Funktionswrapper vorschlage.
Erwin Brandstetter

Antworten:

34

In PostgreSQL 9.6 wird es eine neue Version von pg_trgm 1.2 geben, die diesbezüglich viel besser sein wird. Mit ein wenig Aufwand können Sie diese neue Version auch unter PostgreSQL 9.4 zum Laufen bringen (Sie müssen den Patch anwenden, das Erweiterungsmodul selbst kompilieren und installieren).

In der ältesten Version wird nach jedem Trigramm in der Abfrage gesucht, und die Vereinigung der Trigramme wird vorgenommen. Anschließend wird ein Filter angewendet. In der neuen Version wird nur das seltenste Trigramm in der Abfrage ausgewählt, nach genau diesem gesucht und der Rest später gefiltert.

Die Maschinerie dazu existiert in 9.1 nicht. In 9.4 wurde diese Maschinerie hinzugefügt, aber pg_trgm war zu diesem Zeitpunkt nicht dafür angepasst, sie zu nutzen.

Sie hätten immer noch ein potenzielles DOS-Problem, da die böswillige Person eine Abfrage erstellen kann, die nur allgemeine Trigramme enthält. wie '% and%' oder sogar '% a%'


Wenn Sie nicht auf pg_trgm 1.2 upgraden können, wäre eine andere Möglichkeit, den Planer auszutricksen:

WHERE (lower(unaccent(label)) like lower(unaccent('%someword%'))) 
AND   (lower(unaccent(label||'')) like 
      lower(unaccent('%someword and some more%')));

Durch die Verkettung der leeren Zeichenfolge mit der Bezeichnung wird der Planer zu dem Schluss verleitet, dass der Index für diesen Teil der where-Klausel nicht verwendet werden kann. Es verwendet also den Index nur für% someword% und wendet einen Filter nur auf diese Zeilen an.


Wenn Sie immer nach ganzen Wörtern suchen, können Sie die Zeichenfolge mit einer Funktion in ein Array von Wörtern zerlegen und einen regulären integrierten GIN-Index (nicht pg_trgm) für diese Array-Rückgabefunktion verwenden.

jjanes
quelle
13
Erwähnenswert, dass Sie derjenige waren, der den Patch geschrieben hat. Und vorläufige Leistungstests sind beeindruckend. Dies verdient wirklich mehr Gegenstimmen (auch für die Erklärung und Problemumgehung mit der aktuellen Version).
Erwin Brandstetter,
Es würde mich mehr interessieren, zumindest einen Verweis auf die Maschine, mit der Sie den Patch implementiert haben, der in 9.1 nicht vorhanden war. Aber ich bin damit einverstanden, dass Erwin einen schlechten Arsch beantwortet.
Evan Carroll
3

Ich habe eine Möglichkeit gefunden, den Abfrageplaner zu betrügen. Es ist ein recht einfacher Hack:

SELECT *
FROM (
   select id, title, label
   from   table1
   where  lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

EXPLAIN Ausgabe:

Bitmap-Heap-Scan für Tabelle 1 (Kosten = 6749.11..7332.71 Zeilen = 1 Breite = 212) (tatsächliche Zeit = 256.607..256.609 Zeilen = 1 Schleifen = 1)
  Erneut prüfen Cond: (lower (unaccent ((label_hun) :: text)) ~~ '% someword%' :: text)
  Filter: (untere (untere (unaccent ((label) :: text))) ~~ '% someword and some more%' :: text)
  -> Bitmap Index Scan auf table1_label_hun_gin_trgm (Kosten = 0.00..6749.11 Zeilen = 147 Breite = 0) (aktuelle Zeit = 256.499..256.499 Zeilen = 1 Schleifen = 1)
        Indexbedingung: (niedriger (unaccent ((label) :: text)) ~~ '% someword%' :: text)
Gesamtlaufzeit: 256.653 ms

Da es also keinen Index für gibt lower(lower(unaccent(label))), würde dies einen sequentiellen Scan erzeugen, sodass daraus ein einfacher Filter wird. Darüber hinaus bewirkt ein einfaches UND dasselbe:

SELECT id, title, label
FROM table1
WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
AND   lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

Natürlich ist dies eine Heuristik, die möglicherweise nicht gut funktioniert, wenn der im Index-Scan verwendete Ausschnitt sehr häufig ist. Aber in unserer Datenbank gibt es nicht wirklich so viele Wiederholungen, wenn ich ungefähr 10-15 Zeichen benutze.

Es bleiben zwei kleine Fragen:

  • Warum kann Postgres nicht herausfinden, dass so etwas von Vorteil ist?
  • Was macht Postgres im Zeitbereich 0..256.499 (siehe Output analysieren)?
P.Péter
quelle
1
Im Zeitbereich zwischen 0 und 256.499 wird die Bitmap erstellt. Bei 256.499 erzeugt es seine erste Ausgabe, die Bitmap. Dies ist auch die letzte Ausgabe, da nur eine einzige Ausgabe erstellt wird - eine einzelne fertige Bitmap.
Jjanes