Wyszukiwanie Trigram staje się znacznie wolniejsze, ponieważ ciąg wyszukiwania staje się dłuższy

16

W bazie danych Postgres 9.1 mam tabelę table1z ~ 1,5 mln wierszy i kolumnęlabel (uproszczone nazwy ze względu na to pytanie).

Istnieje funkcjonalny indeks trigram na lower(unaccent(label))(unaccent() został unieruchomiony, aby umożliwić jego użycie w indeksie).

Następujące zapytanie jest dość szybkie:

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

Time: 394,295 ms

Ale następujące zapytanie jest wolniejsze:

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

Time: 1405,749 ms

Dodanie większej liczby słów jest jeszcze wolniejsze, mimo że wyszukiwanie jest bardziej rygorystyczne.

Próbowałem prostej sztuczki, aby uruchomić podkwerendę dla pierwszego słowa, a następnie kwerendy z pełnym ciągiem wyszukiwania, ale (niestety) planista zapytań przejrzał moje machinacje:

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%'));
Skan stosu bitmap w tabeli 1 (koszt = 16216.01..16220.04 wierszy = 1 szerokość = 212) (rzeczywisty czas = 1824.017..1824.019 wierszy = 1 pętli = 1)
  Ponownie sprawdź Cond: ((lower (unaccent ((label) :: text)) ~~ '% someord%' :: text) AND (lower (unaccent ((label) :: text)) ~~ '% nieco i trochę więcej %'::tekst))
  -> Skanowanie indeksu bitmap na table1_label_hun_gin_trgm (koszt = 0,00..16216.01 wierszy = 1 szerokość = 0) (rzeczywisty czas = 1823.900..1823.900 wierszy = 1 pętli = 1)
        Index Cond: ((lower (unaccent ((label) :: text)) ~~ '% someord%' :: text) AND (lower (unaccent ((label) :: text)) ~~ '% nieco i trochę więcej %'::tekst))
Całkowity czas działania: 1824.064 ms

Moim największym problemem jest to, że ciąg wyszukiwania pochodzi z interfejsu internetowego, który może wysyłać dość długie ciągi, a zatem może być bardzo wolny i może również stanowić wektor DOS.

Więc moje pytania to:

  • Jak przyspieszyć zapytanie?
  • Czy istnieje sposób na podzielenie go na podkwerendy, aby było szybsze?
  • Może późniejsza wersja Postgresa jest lepsza? (Próbowałem 9.4 i nie wydaje się to szybsze: wciąż ten sam efekt. Może późniejsza wersja?)
  • Może potrzebna jest inna strategia indeksowania?
P.Péter
źródło
1
Należy wspomnieć, że unaccent()jest on również zapewniany przez dodatkowy moduł, a Postgres domyślnie nie obsługuje indeksów funkcji, ponieważ tak nie jest IMMUTABLE. Musiałeś coś zmienić i powinieneś wspomnieć o tym, co zrobiłeś dokładnie w swoim pytaniu. Moja stała rada: stackoverflow.com/a/11007216/939860 . Ponadto indeksy trigram obsługują dopasowanie bez rozróżniania wielkości liter po wyjęciu z pudełka. Możesz uprościć: WHERE f_unaccent(label) ILIKE f_unaccent('%someword%')- z pasującym indeksem. Szczegóły: stackoverflow.com/a/28636000/939860 .
Erwin Brandstetter,
Po prostu ogłosiłem unaccentniezmienność. Dodałem to do pytania.
P.Péter
Pamiętaj, że włamanie jest zastępowane podczas aktualizacji unaccentmodułu. Jednym z powodów, dla których sugeruję opakowanie funkcji.
Erwin Brandstetter,

Odpowiedzi:

34

W PostgreSQL 9.6 pojawi się nowa wersja pg_trgm, 1.2, która będzie znacznie lepsza. Przy odrobinie wysiłku możesz także sprawić, aby ta nowa wersja działała pod PostgreSQL 9.4 (musisz zastosować łatkę i sam skompilować moduł rozszerzenia i zainstalować go).

Najstarsza wersja to wyszukiwanie każdego trygramu w zapytaniu i łączenie ich, a następnie stosowanie filtra. Nowa wersja zrobi to wybranie najrzadszego trygramu w zapytaniu i poszukiwanie tylko tego, a następnie filtrowanie pozostałej części później.

Maszyny do tego nie istnieją w 9.1. W wersji 9.4 dodano tę maszynę, ale pg_trgm nie było w tym czasie przystosowane do korzystania z niej.

Nadal będziesz mieć potencjalny problem z DOS, ponieważ złośliwa osoba może stworzyć zapytanie, które ma tylko typowe trygramy. jak „% i%”, a nawet „% a%”


Jeśli nie możesz zaktualizować do wersji pg_trgm 1.2, innym sposobem na oszukanie planisty byłoby:

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

Łącząc pusty ciąg z etykietą, oszukasz planistę, aby pomyślał, że nie może użyć indeksu w tej części klauzuli where. Używa więc indeksu tylko w%%% i stosuje filtr tylko do tych wierszy.


Ponadto, jeśli zawsze szukasz całych słów, możesz użyć funkcji, aby tokenizować ciąg znaków na tablicę słów i użyć zwykłego wbudowanego indeksu GIN (nie pg_trgm) na tej funkcji zwracającej tablicę.

jjanes
źródło
13
Warto wspomnieć, że to ty napisałeś łatkę. A wstępne testy wydajności są imponujące. To naprawdę zasługuje na więcej głosów pozytywnych (również dla wyjaśnienia i obejścia obecnej wersji).
Erwin Brandstetter,
Byłbym bardziej zainteresowany przynajmniej odniesieniem do maszyny użytej do wdrożenia łatki, której nie było w wersji 9.1. Ale zgadzam się z odpowiedzią Erwina na złą dupę.
Evan Carroll,
3

Znalazłem sposób na oszustwo w narzędziu do planowania zapytań, jest to dość prosty 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 wynik:

Skan stosu bitmap w tabeli 1 (koszt = 6749.11..7332.71 wierszy = 1 szerokość = 212) (rzeczywisty czas = 256.607..256.609 wierszy = 1 pętli = 1)
  Ponownie sprawdź Cond: (niższy (unaccent ((label_hun) :: tekst)) ~~ '% Someord%' :: text)
  Filtr: (niższy (niższy (unaccent ((etykieta) :: tekst))) ~~ '% w pewnym stopniu i trochę więcej%' :: tekst)
  -> Skanowanie indeksu bitmap na table1_label_hun_gin_trgm (koszt = 0,00..6749.11 wierszy = 147 szerokość = 0) (rzeczywisty czas = 256.499..256,499 wierszy = 1 pętla = 1)
        Indeks Cond: (niższy (unaccent ((etykieta) :: tekst)) ~~ '% somord%' :: text)
Całkowity czas działania: 256,653 ms

Ponieważ nie ma indeksu dla lower(lower(unaccent(label))), utworzyłoby to skanowanie sekwencyjne, dzięki czemu zostałby przekształcony w prosty filtr. Co więcej, prosty AND zrobi to samo:

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%'))

Oczywiście jest to heurystyka, która może nie działać dobrze, jeśli wycinana część używana w skanie indeksu jest bardzo powszechna. Ale w naszej bazie danych nie ma tak wiele powtórzeń, jeśli użyję około 10-15 znaków.

Pozostały jeszcze dwa małe pytania:

  • Dlaczego postgres nie może zrozumieć, że coś takiego byłoby korzystne?
  • Co robi postgres w przedziale czasowym 0..256,499 (patrz analiza wyników)?
P.Péter
źródło
1
W przedziale czasu od 0 do 256.499 buduje mapę bitową. Przy 256.499 produkuje swoje pierwsze wyjście, którym jest bitmapa. Co jest także ostatnim wyjściem, ponieważ tworzy tylko jedno wyjście - pojedynczą ukończoną bitmapę.
jjanes