PostgreSQL antiuzorci: priča o iterativnom usavršavanju pretraživanja po imenu ili "Optimiziranje naprijed-nazad"

Hiljade menadžera iz prodajnih ureda širom zemlje su rekordne naš CRM sistem desetine hiljada kontakata dnevno — činjenice komunikacije sa potencijalnim ili postojećim klijentima. A za to prvo morate pronaći klijenta, i to po mogućnosti vrlo brzo. A to se najčešće dešava po imenu.

Stoga ne čudi da, još jednom analizirajući “teške” upite na jednoj od najopterećenijih baza podataka - našoj VLSI korporativni račun, našao sam "u vrhu" zahtjev za "brzo" pretraživanje po imenu za organizacione kartice.

Štaviše, dalja istraga otkrila je zanimljiv primjer prvo optimizacija, a zatim degradacija performansi zahtjev sa njegovim uzastopnim doradom od strane nekoliko timova, od kojih je svaki djelovao isključivo u najboljoj namjeri.

0: šta je korisnik želio?

[KDPV odavde]

Šta korisnik obično misli kada govori o „brzoj“ pretrazi po imenu? Gotovo nikad se ne ispostavi da je to “iskrena” potraga za podnizom poput ... LIKE '%роза%' - jer onda rezultat uključuje ne samo 'Розалия' и 'Магазин Роза'Ali 'Гроза' i čak 'Дом Деда Мороза'.

Korisnik na svakodnevnom nivou pretpostavlja da ćete mu vi pružiti traži po početku riječi u naslovu i učiniti ga relevantnijim počinje sa ušao. I uradićeš to skoro trenutno - za međulinijski unos.

1: ograničiti zadatak

I još više, osoba neće posebno ući 'роз магаз', tako da morate tražiti svaku riječ po prefiksu. Ne, korisniku je mnogo lakše odgovoriti na brzi savjet za posljednju riječ nego namjerno "podspecificirati" prethodne - pogledajte kako bilo koja tražilica to rješava.

Generalno, desno formulisanje zahteva za problem je više od pola rešenja. Ponekad pažljiva analiza slučaja upotrebe može značajno uticati na rezultat.

Šta radi apstraktni programer?

1.0: eksterni pretraživač

O, pretraga je teška, ne želim ništa da radim - dajmo to devopsu! Neka implementiraju pretraživač izvan baze podataka: Sphinx, ElasticSearch,...

Radna opcija, iako radno intenzivna u smislu sinhronizacije i brzine promjena. Ali ne u našem slučaju, jer se pretraga vrši za svakog klijenta samo u okviru podataka o njegovom računu. I podaci imaju prilično veliku varijabilnost - i ako je menadžer sada unio karticu 'Магазин Роза', onda se nakon 5-10 sekundi možda već sjeti da je zaboravio navesti svoju e-poštu i želi da je pronađe i ispravi.

Stoga - hajde pretraži "direktno u bazi podataka". Na sreću, PostgreSQL nam to omogućava, a ne samo jednu opciju – pogledaćemo ih.

1.1: "pošten" podniz

Držimo se riječi "podniz". Ali za pretraživanje indeksa po podnizu (pa čak i po regularnim izrazima!) postoji odličan modul pg_trgm! Tek tada će biti potrebno pravilno sortirati.

Pokušajmo uzeti sljedeću ploču kako bismo pojednostavili model:

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

Tamo postavljamo 7.8 miliona zapisa stvarnih organizacija i indeksiramo ih:

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

Potražimo prvih 10 zapisa za međulinijsko pretraživanje:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;

[pogledajte objasni.tensor.ru]

Pa to je... 26ms, 31MB čitanje podataka i više od 1.7K filtriranih zapisa - za 10 pretraživanih. Režijski troškovi su previsoki, zar ne postoji nešto efikasnije?

1.2: pretraživanje po tekstu? To je FTS!

Zaista, PostgreSQL pruža veoma moćan pretraživač celog teksta (Pretraga punog teksta), uključujući mogućnost pretraživanja prefiksa. Odlična opcija, ne morate čak ni instalirati ekstenzije! Pokusajmo:

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', 'роза:*')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;

[pogledajte objasni.tensor.ru]

Ovdje nam je malo pomogla paralelizacija izvršavanja upita, prepolovivši vrijeme na 11ms. A morali smo čitati 1.5 puta manje – ukupno 20MB. Ali ovdje, što manje, to bolje, jer što je veći volumen koji čitamo, veće su šanse da dobijemo promašaj keša, a svaka dodatna stranica podataka pročitanih s diska potencijalna je „kočnica“ za zahtjev.

1.3: i dalje LIKE?

Prethodni zahtjev je dobar za sve, ali samo ako ga povučete sto hiljada puta dnevno, doći će 2TB čitanje podataka. U najboljem slučaju, iz memorije, ali ako nemate sreće, onda s diska. Pa pokušajmo ga smanjiti.

Prisjetimo se šta korisnik želi vidjeti prvo "koji počinje sa...". Dakle, ovo je u svom najčistijem obliku pretraga prefiksa uz pomoć text_pattern_ops! I samo ako „nemamo dovoljno“ do 10 zapisa koje tražimo, onda ćemo morati da završimo čitanje pomoću FTS pretrage:

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

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
LIMIT 10;

[pogledajte objasni.tensor.ru]

Odlične performanse - ukupno 0.05 ms i nešto više od 100 KB čitaj! Samo smo mi zaboravili sortiraj po imenukako se korisnik ne bi izgubio u rezultatima:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[pogledajte objasni.tensor.ru]

Joj, nešto više nije tako lijepo - izgleda da postoji indeks, ali sortiranje proleti pored njega... To je, naravno, već višestruko efikasnije od prethodne opcije, ali...

1.4: "završi sa fajlom"

Ali postoji indeks koji vam omogućava da pretražujete po opsegu i dalje normalno koristite sortiranje - redovno btree!

CREATE INDEX ON firms(lower(name));

Samo zahtjev za to će se morati "prikupiti ručno":

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'роза' AND
  lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[pogledajte objasni.tensor.ru]

Odlično - sortiranje radi, a potrošnja resursa ostaje "mikroskopska", hiljadama puta efikasniji od "čistog" FTS-a! Ostaje samo da to spojite u jedan zahtjev:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'роза' AND
    lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
    lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
  ORDER BY
    lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Imajte na umu da se izvršava drugi potupit samo ako se prvi vrati manje od očekivanog zadnji LIMIT broj linija. Govorim o ovoj metodi optimizacije upita već pisao ranije.

Dakle, da, sada imamo i btree i gin na stolu, ali statistički se ispostavilo da manje od 10% zahtjeva stigne do izvršenja drugog bloka. Odnosno, sa takvim tipičnim ograničenjima koja su unapred poznata za zadatak, uspeli smo da smanjimo ukupnu potrošnju serverskih resursa za skoro hiljadu puta!

1.5*: možemo i bez datoteke

Iznad LIKE Spriječeni smo da koristimo pogrešno sortiranje. Ali može se "postaviti na pravi put" navođenjem operatora USING:

Podrazumevano se pretpostavlja ASC. Dodatno, možete specificirati ime specifičnog operatora sortiranja u klauzuli USING. Operator sortiranja mora biti član manje ili veće od neke porodice operatora B-stabla. ASC obično ekvivalentan USING < и DESC obično ekvivalentan USING >.

U našem slučaju, „manje“ je ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[pogledajte objasni.tensor.ru]

2: kako zahtjevi postaju kiseli

Sada ostavljamo naš zahtjev da se “krčka” šest mjeseci ili godinu dana, i iznenađeni smo što ga ponovo nalazimo “na vrhu” s indikatorima ukupnog dnevnog “pumpanja” memorije (baferi zajednički pogodak) u 5.5TB - to jest, čak i više nego što je prvobitno bilo.

Ne, naravno, naš posao je narastao i obim posla je povećan, ali ne za isti iznos! To znači da je ovdje nešto sumnjivo - hajde da to shvatimo.

2.1: rođenje stranica

U nekom trenutku, drugi razvojni tim je želio da omogući „skok“ sa brzog pretraživanja indeksa na registar sa istim, ali proširenim rezultatima. Šta je registar bez navigacije stranica? Hajde da zeznemo!

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

Sada je bilo moguće prikazati registar rezultata pretraživanja sa učitavanjem „stranica po stranicu“ bez ikakvog stresa za programera.

naravno, u stvari, za svaku narednu stranicu podataka čita se sve više i više (sve iz prethodnog puta, što ćemo odbaciti, plus potreban „rep“) - to jest, ovo je jasan antiuzorak. Ali bilo bi ispravnije započeti pretragu u sljedećoj iteraciji od ključa pohranjenog u interfejsu, ali o tome drugi put.

2.2: Želim nešto egzotično

U nekom trenutku programer je htio diverzificirajte rezultirajući uzorak podacima iz druge tabele, za koju je cijeli prethodni zahtjev poslan CTE-u:

WITH q AS (
  ...
  LIMIT <N> + 10
)
SELECT
  *
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
  q
LIMIT 10 OFFSET <N>;

Pa čak i tako, nije loše, budući da se potupit procjenjuje samo za 10 vraćenih zapisa, ako ne...

2.3: DISTINCT je besmislen i nemilosrdan

Negdje u procesu takve evolucije od 2. podupita Izgubio sam se NOT LIKE stanje. Jasno je da nakon ovoga UNION ALL počeo da se vraća neki unosi dva puta - prvo se nalazi na početku reda, a zatim ponovo - na početku prve riječi ovog reda. U ograničenju, svi zapisi 2. potupita mogu se podudarati sa zapisima prvog.

Šta programer radi umjesto da traži uzrok?.. Nema sumnje!

• duplo veće originalni uzorci
• primijeniti DISTINCTda dobijete samo pojedinačne instance svake linije

WITH q AS (
  ( ... LIMIT <2 * N> + 10)
  UNION ALL
  ( ... LIMIT <2 * N> + 10)
  LIMIT <2 * N> + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET <N>;

Odnosno, jasno je da je rezultat, na kraju, potpuno isti, ali šansa da se „uleti“ u 2. CTE potupit je postala mnogo veća, a čak i bez toga, jasno čitljiviji.

Ali to nije najtužnija stvar. Budući da je programer tražio odabir DISTINCT ne za određena, već za sva polja odjednom zapisa, tada je polje pod_upit — rezultat podupita — automatski uključeno tamo. Sada, da izvršimo DISTINCT, baza podataka se već morala izvršiti ne 10 potupita, već svih <2 * N> + 10!

2.4: saradnja iznad svega!

Dakle, programeri su živjeli - nisu se trudili, jer korisnik očito nije imao dovoljno strpljenja da "prilagodi" registar na značajne N vrijednosti uz kronično usporavanje primanja svake sljedeće "stranice".

Sve dok programeri iz drugog odjela nisu došli do njih i htjeli koristiti tako pogodnu metodu za iterativno pretraživanje - to jest, uzmemo komad iz nekog uzorka, filtriramo ga po dodatnim uslovima, nacrtamo rezultat, zatim sledeći komad (što se u našem slučaju postiže povećanjem N), i tako sve dok ne popunimo ekran.

Općenito, u ulovljenom primjerku N je dostigao vrijednosti od skoro 17K, a u samo jednom danu je izvršeno najmanje 4K ovakvih zahtjeva „u lancu“. Posljednje od njih su hrabro pregledali 1 GB memorije po iteraciji...

Ukupno

izvor: www.habr.com