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

Tisuće menadžera iz prodajnih ureda diljem zemlje rekord naš CRM sustav desetke tisuća kontakata dnevno — činjenice komunikacije s potencijalnim ili postojećim klijentima. A za to prvo morate pronaći klijenta, i to po mogućnosti vrlo brzo. I to se najčešće događa imenom.

Stoga ne čudi što smo ponovno analizirajući “teške” upite na jednoj od najopterećenijih baza podataka – vlastitoj VLSI korporativni račun, našao sam "na vrhu" zahtjev za “brzu” pretragu po imenu za organizacijske kartice.

Štoviše, daljnja istraga otkrila je zanimljiv primjer prvo optimizacija, a zatim degradacija performansi zahtjev uz njegovu uzastopnu doradu od strane nekoliko timova, od kojih je svaki djelovao isključivo u najboljim namjerama.

0: što je korisnik želio?

[KDPV stoga]

Što korisnik obično misli kada govori o "brzoj" pretrazi po imenu? Gotovo nikada ne ispadne "pošteno" traženje podniza poput ... LIKE '%роза%' - jer tada rezultat uključuje ne samo 'Розалия' и 'Магазин Роза'Ali 'Гроза' , pa čak i 'Дом Деда Мороза'.

Korisnik na svakodnevnoj razini pretpostavlja da ćete mu vi pružiti pretraživanje po početku riječi u naslovu i učiniti ga relevantnijim da počinje na ušao. I ti ćeš to učiniti gotovo trenutno - za interlinearni unos.

1: ograničite zadatak

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

općenito, ispravno formuliranje zahtjeva za problem više je od pola rješenja. Ponekad pažljiva analiza slučaja upotrebe može značajno utjecati na rezultat.

Što radi apstraktni programer?

1.0: vanjska tražilica

Oh, pretraga je teška, ne želim učiniti ništa - dajmo to devopsima! Neka implementiraju tražilicu izvan baze podataka: Sphinx, ElasticSearch,...

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

Zato – hajmo pretraži “izravno u bazi podataka”. Srećom, PostgreSQL nam to omogućuje, a ne samo jednu opciju - pogledat ćemo ih.

1.1: podniz "pošten".

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 da pojednostavimo model:

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

Tamo prenosimo 7.8 milijuna 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 interlinearno pretraživanje:

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

[pogledajte na expand.tensor.ru]

Pa, to je... 26 ms, 31 MB čitati podatke i više od 1.7K filtriranih zapisa - za 10 pretraženih. Previsoki su režijski troškovi, zar ne postoji nešto učinkovitije?

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

Doista, PostgreSQL pruža vrlo moćan tražilica punog teksta (Full Text Search), uključujući mogućnost pretraživanja prefiksa. Izvrsna opcija, ne morate čak ni instalirati ekstenzije! Pokušajmo:

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 na expand.tensor.ru]

Ovdje nam je malo pomogla paralelizacija izvođenja upita, prepolovivši vrijeme 11 ms. 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 predmemorije, a svaka dodatna stranica podataka pročitana s diska potencijalna je “kočnica” za zahtjev.

1.3: još uvijek vam se sviđa?

Prethodni zahtjev je dobar za sve, ali samo ako ga povučete sto tisuća puta dnevno, doći će 2TB čitati podatke. U najboljem slučaju iz memorije, ali ako nemate sreće, onda s diska. Pa pokušajmo ga učiniti manjim.

Sjetimo se što korisnik želi vidjeti prvo “koje počinju sa...”. Dakle, ovo je u svom najčišćem obliku pretraživanje prefiksa uz pomoć text_pattern_ops! I samo ako "nemamo dovoljno" do 10 zapisa koje tražimo, tada ćemo ih morati dovršiti čitati pomoću FTS pretraživanja:

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

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

[pogledajte na expand.tensor.ru]

Izvrsna izvedba - ukupno 0.05ms i malo više od 100KB čitati! Samo smo mi zaboravili poredati po imenukako se korisnik ne bi izgubio u rezultatima:

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

[pogledajte na expand.tensor.ru]

Oh, nešto više nije tako lijepo - čini se da postoji indeks, ali sortiranje leti pored njega ... To je, naravno, već mnogo puta učinkovitije od prethodne opcije, ali ...

1.4: "završi s datotekom"

Ali postoji indeks koji vam omogućuje pretraživanje po rasponu i dalje normalno korištenje sortiranja - redovito btree!

CREATE INDEX ON firms(lower(name));

Samo će zahtjev za to morati biti "ručno prikupljen":

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

[pogledajte na expand.tensor.ru]

Izvrsno - razvrstavanje radi, a potrošnja resursa ostaje "mikroskopska", tisuće puta učinkovitiji od "čistog" FTS-a! Sve što preostaje je spojiti ga 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 je drugi podupit izvršen samo ako je prvi vratio manje od očekivanog posljednji LIMIT broj linija. Govorim o ovoj metodi optimizacije upita već prije napisao.

Dakle, da, sada imamo i btree i gin na stolu, ali statistički se pokazalo da manje od 10% zahtjeva stigne do izvršenja drugog bloka. To jest, s takvim tipičnim ograničenjima koja su unaprijed poznata za zadatak, uspjeli smo smanjiti ukupnu potrošnju resursa poslužitelja za gotovo tisuću puta!

1.5*: možemo i bez datoteke

Iznad LIKE Bili smo spriječeni u korištenju netočnog sortiranja. Ali može se "postaviti na pravi put" navođenjem operatora USING:

Prema zadanim postavkama pretpostavlja se ASC. Osim toga, u klauzuli možete navesti naziv određenog operatora sortiranja USING. Operator sortiranja mora biti član manje od ili veće od neke obitelji 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 na expand.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 opet nalazimo "na vrhu" s pokazateljima ukupnog dnevnog "pumpanja" memorije (međuspremnici dijeljeni pogodak) u 5.5TB - odnosno čak i više nego što je bilo izvorno.

Ne, naravno, posao nam je porastao i obim posla se povećao, ali ne u istoj mjeri! To znači da ovdje nešto nije u redu - idemo to shvatiti.

2.1: rođenje straničenja

U jednom je trenutku drugi razvojni tim želio omogućiti "skok" s brzog pretplatničkog pretraživanja na registar s istim, ali proširenim rezultatima. Što je registar bez navigacije stranicama? Hajdemo zeznuti stvar!

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

Sada je bilo moguće prikazati registar rezultata pretraživanja s učitavanjem "stranica po stranica" bez ikakvog stresa za programera.

Naravno, zapravo, za svaku sljedeću stranicu podataka čita se sve više i više (sve iz prethodnog puta, koje ćemo odbaciti, plus potrebni "rep") - to jest, ovo je jasan antiuzorak. Ali ispravnije bi bilo započeti pretragu u sljedećoj iteraciji od ključa pohranjenog u sučelju, ali o tome drugom prilikom.

2.2: Želim nešto egzotično

U nekom trenutku programer je htio diverzificirati dobiveni uzorak podacima iz druge tablice, 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>;

Čak i tako, nije loše, budući da se podupit 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 NOT LIKE stanje. Jasno je da nakon ovoga UNION ALL počeo vraćati neki unosi dvaput - prvo se nalazi na početku retka, a zatim opet - na početku prve riječi ovog retka. U ograničenju, svi zapisi 2. podupita mogu se podudarati sa zapisima prvog.

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

• udvostručiti veličinu originalni uzorci
• primijeniti DISTINCTda biste dobili 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 je šansa da se "uleti" u 2. CTE podupit znatno veća, a čak i bez toga, jasno čitljiviji.

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

2.4: suradnja iznad svega!

Dakle, programeri su živjeli bez muke, jer korisnik očito nije imao dovoljno strpljenja da "prilagodi" registar značajnim N vrijednostima s kroničnim usporavanjem primanja svake sljedeće "stranice".

Sve dok im nisu došli programeri iz drugog odjela i htjeli koristiti tako prikladnu metodu za iterativno pretraživanje - odnosno uzmemo dio iz nekog uzorka, filtriramo ga po dodatnim uvjetima, izvučemo rezultat, pa sljedeći komad (što se kod nas postiže povećanjem N) i tako dok ne popunimo ekran.

Općenito, u ulovljenom primjerku N je dosegao vrijednosti od gotovo 17K, a samo u jednom danu “po lancu” izvršeno je najmanje 4K takvih zahtjeva. Posljednje od njih hrabro su skenirali 1 GB memorije po iteraciji...

Ukupno

Izvor: www.habr.com