Protivzorci PostgreSQL: zgodba o ponavljajočem se izboljšanju iskanja po imenu ali »Optimizacija naprej in nazaj«

Rekord na tisoče menedžerjev iz prodajnih pisarn po vsej državi naš sistem CRM več deset tisoč stikov dnevno — dejstva komunikacije s potencialnimi ali obstoječimi strankami. In za to morate najprej najti stranko in po možnosti zelo hitro. In to se najpogosteje zgodi po imenu.

Zato ne preseneča, da ob ponovni analizi »težkih« poizvedb v eni najbolj obremenjenih baz podatkov – naši VLSI korporativni račun, našel sem "na vrhu" zahteva za "hitro" iskanje po imenu za organizacijske kartice.

Poleg tega je nadaljnja preiskava razkrila zanimiv primer najprej optimizacija in nato degradacija zmogljivosti zahtevo z njeno zaporedno izpopolnitvijo s strani več ekip, od katerih je vsaka delovala izključno z najboljšimi nameni.

0: kaj je želel uporabnik?

[KDPV zato]

Kaj uporabnik običajno misli, ko govori o »hitrem« iskanju po imenu? Skoraj nikoli se ne izkaže za "pošteno" iskanje podniza, kot je ... LIKE '%роза%' - ker potem rezultat ne vključuje samo 'Розалия' и 'Магазин Роза'Vendar 'Гроза' in celo 'Дом Деда Мороза'.

Uporabnik na vsakodnevni ravni predvideva, da mu boste zagotovili iskanje po začetku besede v naslovu in ga naredite bolj relevantnega se začne z vneseno. In naredil boš skoraj takoj - za medvrstični vnos.

1: omeji nalogo

In še več, oseba ne bo posebej vstopila 'роз магаз', tako da morate iskati vsako besedo po predponi. Ne, uporabniku je veliko lažje odgovoriti na hiter namig za zadnjo besedo, kot da namenoma "premalo določi" prejšnje - poglejte, kako kateri koli iskalnik to obravnava.

Na splošno pravilno oblikovanje zahtev za problem je več kot polovica rešitve. Včasih skrbna analiza primerov uporabe lahko bistveno vpliva na rezultat.

Kaj počne abstraktni razvijalec?

1.0: zunanji iskalnik

Oh, iskanje je težko, sploh nočem narediti ničesar - dajmo to devopsu! Naj namestijo iskalnik zunaj baze podatkov: Sphinx, ElasticSearch,...

Delujoča možnost, čeprav delovno intenzivna v smislu sinhronizacije in hitrosti sprememb. Vendar ne v našem primeru, saj se iskanje izvaja za vsako stranko samo v okviru podatkov o njenem računu. In podatki imajo precej veliko variabilnost - in če je upravitelj zdaj vnesel kartico 'Магазин Роза', nato pa se po 5-10 sekundah morda že spomni, da je tam pozabil navesti svoj e-poštni naslov in ga želi poiskati in popraviti.

Zato – dajmo išči »neposredno v bazi podatkov«. Na srečo nam PostgreSQL omogoča to in ne samo eno možnost – pogledali jih bomo.

1.1: podniz "pošten".

Oklepamo se besede "podniz". Toda za iskanje po indeksu po podnizu (in celo po regularnih izrazih!) obstaja odličen modul pg_trgm! Šele takrat bo treba pravilno sortirati.

Poskusimo vzeti naslednjo ploščo, da poenostavimo model:

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

Tja naložimo 7.8 milijona zapisov resničnih organizacij in jih indeksiramo:

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

Poiščimo prvih 10 zapisov za medvrstično iskanje:

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

[ogled na expand.tensor.ru]

No, to je ... 26 ms, 31 MB prebrani podatki in več kot 1.7K filtriranih zapisov - za 10 iskanih. Režijski stroški so previsoki, ali ni kaj bolj učinkovitega?

1.2: iskanje po besedilu? To je FTS!

Dejansko PostgreSQL ponuja zelo zmogljivo iskalnik po celotnem besedilu (Iskanje po celotnem besedilu), vključno z možnostjo iskanja s predpono. Odlična možnost, razširitev vam sploh ni treba nameščati! Poskusimo:

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;

[ogled na expand.tensor.ru]

Pri tem nam je nekoliko pomagala paralelizacija izvajanja poizvedb, saj smo čas prepolovili na 11ms. In prebrati smo morali 1.5-krat manj – skupaj 20MB. Tukaj pa velja, da čim manj, tem bolje, saj večji kot obseg beremo, večja je možnost, da pride do zgrešenega predpomnilnika, vsaka dodatna stran podatkov, prebrana z diska, pa je potencialna "zavora" za zahtevo.

1.3: še VŠEČ?

Prejšnja zahteva je dobra za vse, a le če jo potegnete sto tisočkrat na dan, bo prišla 2TB branje podatkov. V najboljšem primeru iz spomina, če pa nimate sreče, pa z diska. Zato ga poskusimo zmanjšati.

Spomnimo se, kaj uporabnik želi videti prvi "ki se začne z...". To je torej v najčistejši obliki iskanje po predponi s pomočjo text_pattern_ops! In le če »nimamo dovolj« do 10 zapisov, ki jih iščemo, jih bomo morali do konca prebrati z iskanjem FTS:

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

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

[ogled na expand.tensor.ru]

Odlična zmogljivost - skupaj 0.05ms in nekaj več kot 100KB preberi! Samo mi smo pozabili razvrsti po imenuda se uporabnik ne izgubi v rezultatih:

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

[ogled na expand.tensor.ru]

Oh, nekaj ni več tako lepo - zdi se, da obstaja indeks, vendar razvrščanje leti mimo njega ... Seveda je že velikokrat bolj učinkovito kot prejšnja možnost, vendar ...

1.4: »dokončaj z datoteko«

Obstaja pa indeks, ki vam omogoča iskanje po obsegu in še vedno normalno uporabo razvrščanja - običajno btree!

CREATE INDEX ON firms(lower(name));

Samo zahtevo zanjo bo treba "zbrati ročno":

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

[ogled na expand.tensor.ru]

Odlično - razvrščanje deluje, poraba virov pa ostaja "mikroskopska", tisočkrat bolj učinkovit kot "čisti" FTS! Vse kar ostane je, da ga združimo v eno samo zahtevo:

(
  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;

Upoštevajte, da se izvaja druga podpoizvedba le če je prvi vrnil manj od pričakovanega zadnji LIMIT število vrstic. Govorim o tej metodi optimizacije poizvedb že prej napisal.

Tako da, zdaj imamo na mizi btree in gin, a statistično se izkaže, da manj kot 10% zahtevkov doseže izvedbo drugega bloka. To pomeni, da smo s tako tipičnimi vnaprej znanimi omejitvami naloge lahko zmanjšali skupno porabo strežniških virov za skoraj tisočkrat!

1.5*: lahko brez datoteke

Zgoraj LIKE Preprečili so nam uporabo napačnega razvrščanja. Vendar ga je mogoče "nastaviti na pravo pot" z navedbo operatorja USING:

Privzeto se predpostavlja ASC. Poleg tega lahko v klavzuli določite ime določenega operaterja razvrščanja USING. Operator razvrščanja mora biti član manjšega ali večjega neke družine operatorjev B-drevesa. ASC običajno enakovredna USING < и DESC običajno enakovredna USING >.

V našem primeru je "manj". ~<~:

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

[ogled na expand.tensor.ru]

2: kako zahteve postanejo kisle

Zdaj pustimo našo zahtevo, da "vre" šest mesecev ali leto, in presenečeni smo, da jo spet najdemo "na vrhu" s kazalniki skupnega dnevnega "črpanja" pomnilnika (medpomnilniki skupnega zadetka) v 5.5TB - torej še več, kot je bilo prvotno.

Ne, seveda, naš posel se je povečal in obseg dela se je povečal, vendar ne za enako! To pomeni, da je tu nekaj dvomljivega - ugotovimo.

2.1: rojstvo straničenja

Na neki točki je druga razvojna ekipa želela omogočiti »skok« s hitrega iskanja v registru z enakimi, vendar razširjenimi rezultati. Kaj je register brez navigacije po straneh? Zajebimo ga!

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

Zdaj je bilo mogoče prikazati register rezultatov iskanja z nalaganjem »stran za stranjo« brez stresa za razvijalca.

Seveda v resnici za vsako naslednjo stran podatkov se prebere vedno več (vse iz prejšnjega časa, ki ga bomo zavrgli, plus potreben "rep") - to je jasen antivzorec. Bolj pravilno pa bi bilo iskanje začeti pri naslednji iteraciji iz ključa, shranjenega v vmesniku, a o tem drugič.

2.2: Želim si nekaj eksotičnega

Na neki točki je razvijalec želel dobljeni vzorec popestrite s podatki iz druge tabele, za katero je bila celotna prejšnja zahteva poslana CTE:

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

In kljub temu ni slabo, saj je podpoizvedba ovrednotena samo za 10 vrnjenih zapisov, če ne ...

2.3: DISTINCT je nesmiselno in neusmiljeno

Nekje v procesu takšnega razvoja od 2. podpoizvedbe se izgubil NOT LIKE pogoj. Jasno je, da po tem UNION ALL začel vračati nekateri vnosi dvakrat - najprej najdemo na začetku vrstice, nato pa spet - na začetku prve besede te vrstice. V omejitvi se lahko vsi zapisi 2. podpoizvedbe ujemajo z zapisi prve.

Kaj počne razvijalec, namesto da bi iskal vzrok?.. Brez dvoma!

• dvojno velikost originalni vzorci
• uporabite DISTINCTda dobite samo posamezne primerke vsake vrstice

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>;

To pomeni, da je jasno, da je rezultat na koncu popolnoma enak, vendar je možnost "letenja" v 2. podpoizvedbo CTE postala veliko večja in tudi brez tega, očitno bolj berljiv.

A to ni najbolj žalostno. Ker je razvijalec zahteval izbiro DISTINCT ne za določena, ampak za vsa polja hkrati zapisov, potem je bilo polje sub_query — rezultat podpoizvedbe — samodejno vključeno tja. Zdaj pa k izvedbi DISTINCT, se je morala baza podatkov že izvesti ne 10 podpoizvedb, ampak vse <2 * N> + 10!

2.4: sodelovanje predvsem!

Torej so razvijalci živeli naprej - niso se trudili, ker uporabnik očitno ni imel dovolj potrpljenja, da bi "prilagodil" register na pomembne vrednosti N s kronično upočasnitvijo prejemanja vsake naslednje "strani".

Dokler k njim niso prišli razvijalci iz drugega oddelka in želeli uporabiti tako priročno metodo za iterativno iskanje - torej iz nekega vzorca vzamemo delček, ga filtriramo po dodatnih pogojih, izrišemo rezultat, nato naslednji delček (kar v našem primeru dosežemo z večanjem N) in tako naprej, dokler ne zapolnimo zaslona.

Na splošno v ulovljenem osebku N je dosegel vrednosti skoraj 17K, samo v enem dnevu pa je bilo "po verigi" izvedenih vsaj 4K takšnih zahtev. Zadnje med njimi so pogumno skenirali 1 GB pomnilnika na ponovitev...

Skupno

Vir: www.habr.com