🥇PostgreSQL Antipatterns: opowieść o iteracyjnej poprawie wyszukiwania według nazwy, czyli "Optymalizacja tam i z powrotem"

Tysiące menedżerów z biur sprzedaży w całym kraju rejestrują w naszym systemie CRM codziennie dziesiątki tysięcy kontaktów — faktów komunikacji z potencjalnymi lub już współpracującymi z nami klientami. Aby to zrobić, musimy najpierw znaleźć klienta, i to najlepiej bardzo szybko. Najczęściej odbywa się to według nazwy.

Dlatego nie dziwi, że analizując kolejny raz "ciężkie" zapytania w jednej z najbardziej obciążonych baz — naszej własnej firmowej konta SBS, odkryłem "w czołówce" zapytanie do "szybkiego" wyszukiwania według nazwy dla kartotek organizacji.

Ponadto dalsze śledztwo wykazało interesujący przykład najpierw optymalizacji, a następnie degradacji wydajności zapytania przy jego kolejnej obróbce przez kilka zespołów, z których każdy działał wyłącznie z najlepszych pobudek.

0: czego więc oczekiwał użytkownik

[KDPW stąd]

Czego właściwie zazwyczaj oczekuje użytkownik, gdy mówi o "szybkiej" wyszukiwarce według nazwy? Prawie nigdy nie okazuje się, że to "uczciwe" wyszukiwanie pod ciągiem znaków jak ... LIKE '%róża%' — ponieważ wtedy w wynikach znajdują się nie tylko 'Róża' i 'Sklep Róża', ale także 'Gróża' i nawet 'Dom Deda Róża'.

Użytkownik na poziomie codziennym oczekuje, że zapewnicie mu wyszukiwanie po początku słowa w nazwie i pokażecie bardziej relewantne to, co zaczyna się na wpisane. I zrobicie to praktycznie natychmiastowo — przy wprowadzaniu pod ciągiem.

1: ograniczamy zadanie

I tym bardziej nikt nie będzie specjalnie wpisywał 'róż sklep', aby każde słowo musiało być wyszukiwane prefiksowo. Nie, znacznie łatwiej jest użytkownikowi zareagować na szybką sugestię dla ostatniego słowa, niż celowo "nie wpisać" poprzednich — zobaczcie, jak działa to w każdej wyszukiwarce.

W ogóle, prawidłowo sformułowanie wymagań do zadania to więcej niż połowa rozwiązania. Czasami dokładna analiza use case może znacząco wpłynąć na wynik.

Co robi abstrakcyjny programista?

1.0: zewnętrzny silnik wyszukiwania

Och, wyszukiwanie to skomplikowane, w ogóle nie chcę się tym zajmować — dajmy to devops! Niech nam rozwiną zewnętrzny system wyszukiwania relatywnie do bazy danych: Sphinx, ElasticSearch,…

Tożsy, chociaż pracochłonny w kontekście synchronizacji i szybkiej wprowadzania zmian. Ale nie w naszym przypadku, ponieważ wyszukiwanie odbywa się dla każdego klienta wyłącznie w ramach danych jego konta. A dane mają stosunkowo wysoką zmienność — jeśli teraz menedżer wprowadził kartę 'Sklep Róża', to w ciągu 5-10 sekund może sobie przypomnieć, że zapomniał podać email i zechce ją znaleźć i poprawić.

Dlatego — zacznijmy szukać „bezpośrednio w bazie”. Na szczęście PostgreSQL pozwala nam to robić, i to na więcej niż jeden sposób — przyjrzyjmy się im.

1.1: «uczciwy» podciąg

Skupmy się na słowie „podciąg”. Istnieje doskonały moduł pg_trgm! Jednak potem trzeba to poprawnie posortować.

Spróbujmy wziąć dla uproszczenia taką tabelę:

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

Wprowadźmy tam 7,8 miliona rekordów rzeczywistych organizacji i zindeksujmy:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

Wyszukajmy pierwsze 10 rekordów do przeszukiwania podciągu:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'róża')
ORDER BY
  lower(name) ~ ('^' || 'róża') DESC -- najpierw "zaczynające się na"
, lower(name) -- reszta alfabetycznie
LIMIT 10;

[zobacz na explain.tensor.ru]

Cóż, tak... 26ms, 31MB przeczytanych danych i ponad 1.7K odfiltrowanych rekordów — dla 10 poszukiwanych. Koszty operacyjne są zbyt wysokie, czy nie można jakoś bardziej efektywnie?

1.2: wyszukiwanie pełnotekstowe? to przecież FTS!

Rzeczywiście, PostgreSQL oferuje bardzo potężny mechanizm wyszukiwania pełnotekstowego (Full Text Search), w tym z możliwością wyszukiwania prefiksowego. Świetna opcja, nawet nie trzeba instalować rozszerzeń! Spróbujmy:

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'róża:*')
ORDER BY
  lower(name) ~ ('^' || 'róża') DESC
, lower(name)
LIMIT 10;

[zobacz na explain.tensor.ru]

Tu trochę pomogła nam równoległość wykonywania zapytania, skracając czas o połowę do 11ms. A musieliśmy odczytać o 1.5 raza mniej — zaledwie 20MB. A tutaj im mniej — tym lepiej, ponieważ im większą ilość odczytujemy, tym wyższe są szanse na wystąpienie awarii cache miss, a każda dodatkowa strona odczytana z dysku to potencjalne „spowolnienie” zapytania.

1.3: czy jednak LIKE?

Całe wcześniejsze zapytanie jest dobre, ale jeśli zrobimy to sto tysięcy razy dziennie, to już uzbiera się 2TB przeczytanych danych. W najlepszym przypadku — z pamięci, ale jeśli nie będzie szczęścia, to z dysku. Spróbujmy więc to zmniejszyć.

Pamiętajmy, że użytkownik chce zobaczyć najpierw „które zaczynają się od …”. No bo to czysta wyszukiwanie prefiksowe z pomocą text_pattern_ops! I tylko jeśli będzie „za mało” do 10 wyszukiwanych rekordów, będzie trzeba je dokończyć za pomocą wyszukiwania FTS:

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('róża' || '%')
LIMIT 10;

[zobacz na explain.tensor.ru]

Świetne wyniki — zaledwie 0,05ms i nieco ponad 100KB przeczytane! Tylko zapomnieliśmy o sortowaniu według nazwy, żeby użytkownik nie zgubił się w wynikach:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('róża' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[zobacz na explain.tensor.ru]

Oj, coś już tak nieładnie — wygląda na to, że index jest, ale sortowanie omija go... Oczywiście, jest to o wiele bardziej efektywne niż poprzednia wersja, ale...

1.4: „dopasować ręcznie”

Ale jest index, który pozwala na wyszukiwanie w zakresie i używanie sortowania — zwykły btree!

CREATE INDEX ON firms(lower(name));

Tylko zapytanie do niego trzeba będzie „zbudować ręcznie”:

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'róża' AND
  lower(name) <= ('róża' || chr(65535)) -- dla UTF8, dla pojedynczych bajtów - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[zobacz na explain.tensor.ru]

Świetnie — sortowanie działa, a zużycie zasobów pozostaje „mikroskopijne”, o tysiąc razy efektywniejsze niż „czyste” FTS! Pozostało złączyć w jedno zapytanie:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'róża' AND
    lower(name) <= ('róża' || chr(65535)) -- dla UTF8, dla jednow bajtowych kodowań - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'róża:*') AND
    lower(name) NOT LIKE ('róża' || '%') -- „zaczynające się od” już znaleźliśmy wyżej
  ORDER BY
    lower(name) ~ ('^' || 'róża') DESC -- używamy tego samego sortowania, żeby NIE iść po indeksie btree
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Zauważam, że drugi podzapytanie wykonuje się tylko jeśli pierwsze zwróciło mniej oczekiwanego liczby wierszy. O tym sposobie optymalizacji zapytań LIMIT już wcześniej pisałem Tak więc teraz mamy na tabeli jednocześnie btree i gin, a statystycznie wyszło, że.

mniej niż 10% zapytań dochodzi do wykonania drugiego bloku. To znaczy, przy takich znanych z góry typowych ograniczeniach dla zadania, udało nam się zmniejszyć całkowite zużycie zasobów serwera praktycznie tysiąc razy!1.5*: obejdziemy się bez ręcznego dopasowania

Wyżej

Wyżej LIKE Mieliśmy problem z używaniem niewłaściwego sortowania. Można jednak „naprawić to” poprzez wskazanie operatora USING:

Domyślnie rozumie się ASC. Można również określić nazwę specyficznego operatora sortowania w zapytaniu USING. Operator sortowania musi być członkiem „mniejsze” lub „większe” jakiejś rodziny operatorów B-drzewa. ASC zwykle równoważne USING < i DESC zwykle równoważne USING >.

W naszym przypadku „mniejsze” to ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('róża' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[zobacz na explain.tensor.ru]

2: jak „fermentują” zapytania

Teraz pozostawiamy nasze zapytanie „do dojrzewania” na pół roku-rok, i z zdziwieniem odkrywamy je znowu „w czołówce” z wskaźnikami całkowitego dziennego „podkręcania” pamięci (buffers shared hit) w 5.5 TB — czyli jeszcze więcej niż było pierwotnie.

Nie, oczywiście, i nasz biznes się rozwinął, a obciążenie wzrosło, ale nie aż tak! Oznacza to, że coś tutaj jest nie tak — zajmijmy się tym.

2.1: narodziny paginacji

W pewnym momencie inny zespół deweloperów chciał dodać możliwość „przejścia” z szybkiego wyszukiwania wierszowego do rejestru z tymi samymi, ale rozszerzonymi wynikami. A jaki rejestr bez paginacji? Dodajmy to!

( ... LIMIT  + 10)
UNION ALL
( ... LIMIT  + 10)
LIMIT 10 OFFSET ;

Teraz można było bez problemu pokazać rejestr wyników wyszukiwania z „typu-paginacji” ładowaniu.

Oczywiście, w rzeczywistości, dla każdej następnej strony danych odczytywane są coraz większe ilości (wszystkie z poprzedniego razu, które odrzucimy, plus potrzebny „ogon”) — to wyraźny antywzorzec. A poprawniej byłoby — uruchomić wyszukiwanie na następnej iteracji od zapamiętanego w interfejsie klucza, ale o tym — innym razem.

2.2: Tęsknota za egzotyką

W pewnym momencie deweloper zapragnął uatrakcyjnić wynikowy zbiór danymi z innej tabeli, w tym celu cały poprzedni zapytanie zostało wysłane do CTE:

WITH q AS (
  ...
  LIMIT  + 10
)
SELECT
  *
, (SELECT ...) sub_query -- jakiś zapytanie do powiązanej tabeli
FROM
  q
LIMIT 10 OFFSET ;

I nawet tak — całkiem nieźle, ponieważ zagnieżdżone zapytanie jest obliczane tylko dla 10 zwracanych rekordów, gdyby nie…

2.3: DISTINCT bezsensowny i bezlitosny

Gdzieś w trakcie tej ewolucji z 2-go podzapytania utracono NOT LIKE warunek. Oczywiście, że po tym UNION ALL zaczął zwracać niektóre rekordy dwukrotnie — najpierw znalezione według początku wiersza, a potem jeszcze raz — według początku pierwszego słowa tego wiersza. Ostatecznie wszystkie wpisy drugiego podzapytania mogły pokryć się z wpisami pierwszego.

Co robi programista zamiast szukać przyczyny?.. Żaden problem!

powiększymy rozmiar dwukrotnie wyjściowe próbki
nałożymy DISTINCT, aby otrzymać tylko pojedyncze wystąpienia każdego wiersza

WITH q AS (
  ( ... LIMIT  + 10)
  UNION ALL
  ( ... LIMIT  + 10)
  LIMIT  + 10
)
SELECT DISTINCT
  *
, (SELECT ...) pod_zapytanie
FROM
  q
LIMIT 10 OFFSET ;

To znaczy, że wynik w końcu jest dokładnie ten sam, ale szansa na "przelot" w drugim podzapytaniu CTE znacznie wzrosła, a i bez tego, czyta się wyraźnie więcej.

Ale to nie jest największy problem. Ponieważ programista poprosił o wybór UNIKALNE nie według konkretnych, a od razu według wszystkich pól rekordów, to automatycznie wpadło tam i pole sub_query — wynik podzapytania. Teraz, aby wykonać UNIKALNE, baza musiała wykonać już nie 10 podzapytań, a wszystkie + 10!

2.4: kooperacja ponad wszystko!

Tak to było, programiści żyli — nie narzekali, ponieważ w rejestrze "wykręcić" do istotnych wartości N przy chronicznym spowolnieniu uzyskiwania każdej kolejnej "strony" użytkownikowi zdecydowanie brakowało cierpliwości.

Dopóki nie przyszli do nich programiści z innego działu i nie chcieli skorzystać z tak wygodnej metody do iteracyjnego wyszukiwania — to znaczy bierzemy z jakiejś próbki kawałek, filtrujemy według dodatkowych warunków, tworzymy wynik, potem następny kawałek (co w naszym przypadku osiągane jest przez zwiększenie N), i tak dalej, aż wypełnimy ekran.

Ogólnie, w złapanym egzemplarzu N osiągnęło wartości prawie 17K, a w ciągu jednego dnia wykonano "w łańcuszku" nie mniej niż 4K takich zapytań. Ostatnie z nich odważnie skanowano już po 1GB pamięci na każdą iterację…