PostgreSQL Antipatterns: A Tale of Iterative Refinement of Search by Name, eller "Optimera fram och tillbaka"

Tusentals chefer från försäljningskontor över hela landet rekord vårt CRM-system tiotusentals kontakter dagligen — Fakta om kommunikation med potentiella eller befintliga kunder. Och för detta måste du först hitta en kund, och helst mycket snabbt. Och detta händer oftast med namn.

Därför är det inte förvånande att vi återigen analyserar "tunga" frågor på en av de mest laddade databaserna - vår egen VLSI företagskonto, jag hittade "i toppen" begäran om en "snabb" sökning efter namn för organisationskort.

Dessutom visade ytterligare undersökningar ett intressant exempel först optimering och sedan prestandaförsämring begäran med dess sekventiella förfining av flera team, som var och en handlade enbart med de bästa avsikterna.

0: vad ville användaren ha?

[KDPV hence]

Vad menar en användare vanligtvis när de talar om en "snabb" sökning efter namn? Det visar sig nästan aldrig vara en "ärlig" sökning efter en delsträng som ... LIKE '%роза%' – för då ingår inte bara resultatet 'Розалия' и 'Магазин Роза'Men 'Гроза' och även 'Дом Деда Мороза'.

Användaren antar på vardagsnivå att du kommer att förse honom med sök efter början av ordet i rubriken och göra det mer relevant det börjar med gick in i. Och du kommer att göra det nästan omedelbart - för interlinjär ingång.

1: begränsa uppgiften

Och ännu mer så kommer en person inte specifikt att gå in 'роз магаз', så att du måste söka efter varje ord med prefix. Nej, det är mycket lättare för en användare att svara på en snabb ledtråd för det sista ordet än att målmedvetet "underspecificera" de föregående - titta på hur vilken sökmotor som helst hanterar detta.

i allmänhet, korrekt att formulera kraven för problemet är mer än halva lösningen. Ibland noggrann användningsfallsanalys kan påverka resultatet avsevärt.

Vad gör en abstrakt utvecklare?

1.0: extern sökmotor

Åh, det är svårt att söka, jag vill inte göra någonting alls - låt oss ge det till devops! Låt dem distribuera en sökmotor utanför databasen: Sphinx, ElasticSearch,...

Ett fungerande alternativ, om än arbetskrävande vad gäller synkronisering och förändringshastighet. Men inte i vårt fall, eftersom sökningen utförs för varje kund endast inom ramen för hans kontodata. Och uppgifterna har en ganska stor variation - och om chefen nu har lagt in kortet 'Магазин Роза', sedan kanske han redan efter 5-10 sekunder kommer ihåg att han glömt att ange sin e-post där och vill hitta den och rätta till den.

Därför - låt oss sök "direkt i databasen". Lyckligtvis tillåter PostgreSQL oss att göra detta, och inte bara ett alternativ - vi kommer att titta på dem.

1.1: "ärlig" delsträng

Vi håller fast vid ordet "delsträng". Men för indexsökning efter delsträng (och även med reguljära uttryck!) finns det en utmärkt modul pg_trgm! Först då blir det nödvändigt att sortera rätt.

Låt oss försöka ta följande platta för att förenkla modellen:

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

Vi laddar upp 7.8 miljoner register över riktiga organisationer där och indexerar dem:

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

Låt oss leta efter de första 10 posterna för interlinjär sökning:

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

[titta på explain.tensor.ru]

Tja, sånt... 26ms, 31MB läst data och mer än 1.7K filtrerade poster - för 10 sökta. Omkostnaderna är för höga, finns det inte något mer effektivt?

1.2: sök med text? Det är FTS!

Faktum är att PostgreSQL ger en mycket kraftfull fulltext sökmotor (Fulltextsökning), inklusive möjligheten att söka prefix. Ett utmärkt alternativ, du behöver inte ens installera tillägg! Låt oss försöka:

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;

[titta på explain.tensor.ru]

Här hjälpte parallellisering av exekveringen av frågor oss lite, halverade tiden till 11 ms. Och vi fick läsa 1.5 gånger mindre – totalt 20MB. Men här, ju mindre, desto bättre, för ju större volym vi läser, desto större är chansen att få en cachemiss, och varje extra sida med data som läses från disken är en potentiell "broms" för begäran.

1.3: GILLAR fortfarande?

Den tidigare begäran är bra för alla, men bara om du drar den hundratusen gånger om dagen kommer den 2TB läsa data. I bästa fall från minnet, men om du har otur, då från disken. Så låt oss försöka göra det mindre.

Låt oss komma ihåg vad användaren vill se först "som börjar med...". Så detta är i sin renaste form prefixsökning via text_pattern_ops! Och bara om vi "inte har tillräckligt med" upp till 10 poster vi letar efter, då måste vi läsa klart dem med FTS-sökning:

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

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

[titta på explain.tensor.ru]

Utmärkt prestanda - totalt 0.05ms och lite mer än 100KB läsa! Bara vi glömde sortera efter namnså att användaren inte går vilse i resultaten:

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

[titta på explain.tensor.ru]

Åh, något är inte så vackert längre - det verkar som om det finns ett index, men sorteringen flyger förbi det... Det är naturligtvis redan många gånger effektivare än det tidigare alternativet, men...

1.4: "avsluta med en fil"

Men det finns ett index som låter dig söka efter intervall och fortfarande använda sortering normalt - vanligt bträd!

CREATE INDEX ON firms(lower(name));

Endast begäran om det måste "samlas in manuellt":

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

[titta på explain.tensor.ru]

Utmärkt - sorteringen fungerar och resursförbrukningen förblir "mikroskopisk", tusentals gånger effektivare än "ren" FTS! Allt som återstår är att sätta ihop det till en enda begäran:

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

Observera att den andra underfrågan exekveras bara om den första gav mindre än förväntat den sista LIMIT antal rader. Jag pratar om den här metoden för frågeoptimering redan skrivit förut.

Så ja, vi har nu både btree och gin på bordet, men statistiskt visar det sig det mindre än 10 % av förfrågningarna når exekveringen av det andra blocket. Det vill säga, med sådana typiska begränsningar kända i förväg för uppgiften, kunde vi minska den totala förbrukningen av serverresurser med nästan tusen gånger!

1.5*: vi klarar oss utan fil

Högre LIKE Vi hindrades från att använda felsortering. Men det kan "ställas på rätt väg" genom att ange operatorn USING:

Som standard antas det ASC. Dessutom kan du ange namnet på en specifik sorteringsoperator i en sats USING. Sorteringsoperatorn måste vara medlem av mindre än eller större än i någon familj av B-trädoperatorer. ASC vanligtvis likvärdig USING < и DESC vanligtvis likvärdig USING >.

I vårt fall är "mindre". ~<~:

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

[titta på explain.tensor.ru]

2: hur förfrågningar blir sura

Nu lämnar vi vår begäran om att "sjuda" i sex månader eller ett år, och vi är förvånade över att hitta den igen "på toppen" med indikatorer på den totala dagliga "pumpningen" av minne (buffertar delad träff) i 5.5TB – det vill säga ännu mer än vad det var från början.

Nej, visst, vår verksamhet har växt och vår arbetsbelastning har ökat, men inte lika mycket! Det betyder att något är skumt här - låt oss ta reda på det.

2.1: födelsen av personsökning

Vid något tillfälle ville ett annat utvecklingsteam göra det möjligt att "hoppa" från en snabb prenumerationssökning till registret med samma, men utökade resultat. Vad är ett register utan sidnavigering? Låt oss förstöra det!

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

Nu var det möjligt att visa registret över sökresultat med "sida-för-sida"-laddning utan någon stress för utvecklaren.

Naturligtvis, faktiskt, för varje efterföljande sida med data läses mer och mer (allt från föregående gång, som vi kommer att kassera, plus den nödvändiga "svansen") - det vill säga detta är ett tydligt antimönster. Men det vore mer korrekt att starta sökningen vid nästa iteration från nyckeln lagrad i gränssnittet, men om det en annan gång.

2.2: Jag vill ha något exotiskt

Vid något tillfälle ville utvecklaren diversifiera det resulterande urvalet med data från en annan tabell, för vilken hela föregående begäran skickades till CTE:

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

Och trots det är det inte dåligt, eftersom underfrågan endast utvärderas för 10 returnerade poster, om inte ...

2.3: DISTINCT är meningslöst och skoningslöst

Någonstans i processen med en sådan utveckling från den andra underfrågan förlorat NOT LIKE tillstånd. Det är klart att efter detta UNION ALL började återvända några poster två gånger - hittas först i början av raden och sedan igen - i början av det första ordet i denna rad. I gränsen kan alla poster i den andra underfrågan matcha posterna för den första.

Vad gör en utvecklare istället för att leta efter orsaken?.. Ingen fråga!

• dubbla storleken originalprover
• tillämpa DISTINCTför att bara få enstaka instanser av varje rad

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

Det vill säga, det är tydligt att resultatet i slutändan är exakt detsamma, men chansen att "flyga" in i den andra CTE-underfrågan har blivit mycket högre, och även utan detta, klart mer läsbar.

Men det här är inte det tråkigaste. Eftersom utvecklaren bad om att välja DISTINCT inte för specifika, utan för alla fält samtidigt poster, så inkluderades sub_query-fältet - resultatet av underfrågan - automatiskt där. Nu, att utföra DISTINCT, var databasen redan tvungen att köras inte 10 underfrågor, utan alla <2 * N> + 10!

2.4: samarbete framför allt!

Så utvecklarna levde vidare - de brydde sig inte, eftersom användaren uppenbarligen inte hade tillräckligt med tålamod för att "justera" registret till signifikanta N-värden med en kronisk nedgång i att ta emot varje efterföljande "sida".

Tills utvecklare från en annan avdelning kom till dem och ville använda en sådan bekväm metod för iterativ sökning - det vill säga, vi tar en bit från något prov, filtrerar det efter ytterligare förhållanden, ritar resultatet, sedan nästa bit (som i vårt fall uppnås genom att öka N), och så vidare tills vi fyller skärmen.

I allmänhet i det fångade exemplaret N nådde värden på nästan 17K, och på bara en dag utfördes minst 4K av sådana förfrågningar "längs kedjan". De sista av dem skannades djärvt av 1 GB minne per iteration.

Totalt

Källa: will.com