🥇PostgreSQL Antipatterns: история за итеративната доработка на търсенето по заглавие, или "Оптимизация напред и назад"

Хиляди мениджъри от търговските офиси в цялата страна записват в нашата CRM система ежедневно десетки хиляди контакта — факти на комуникация с потенциални или вече работещи с нас клиенти. А за това клиентът първо трябва да бъде намерен, и желателно много бързо. И това обикновено става по наименование.

Затова не е изненадващо, че като анализирах поредните "тежки" заявки на една от най-натоварените бази — нашия собствен корпоративен акаунт СБИС, открих "в топа" заявка за "бързо" търсене по наименование за картите на организациите.

В допълнение, по-нататъшното разследване разкри интересен пример първо за оптимизация, а след това за деградация на производителността на заявката при последователната й обработка от няколко екипа, всеки от които е действал изключително с добри намерения.

0: какво всъщност искаше потребителят

[КДПВ оттук]

Какво всъщност потребителят обикновено има предвид, когато говори за "бързо" търсене по наименование? Почти никога не се оказва "честно" търсене по подстрока като ... LIKE '%роза%' — защото иначе в резултата влизат не само 'Розалия' и 'Магазин Роза', но и 'Гроза' и дори 'Дом на Дядо Мороза'.

Потребителят обаче на простичко ниво предполага, че вие трябва да осигурите търсене по начало на думата в наименованието и да покажете по-релевантно това, което започва на въведеното. И ще направите това практически мигновено — при въвеждане на подстрока.

1: ограничава задача

И няма как човек специално да въведе 'роз магаз', за да търсите префиксно всяка дума. Не, на потребителя му е много по-лесно да реагира на бързото предложение за последната дума, отколкото целенасочено "да не въвежда" предишните — вижте как това работи при всеки търсач.

Всъщност, правилно да формулирате изискванията към задачата — е повече от половината решение. Понякога внимателният анализ на use case може съществено да влияе на резултата..

Какво прави абстрактният разработчик?

1.0: външен поисков двигател

Ой, търсенето е сложно, не искам изобщо да се занимавам с това — давайте да го предадем на devops! Нека те да ни развърнат външна търсачка, относно БД: Sphinx, ElasticSearch,…

Работещ вариант, въпреки че е трудоемък по отношение на синхронизацията и бързината на промените. Но не в нашия случай, тъй като търсенето се извършва за всеки клиент само в рамките на данните от неговия акаунт. А данните имат доста висока изменчивост — и ако сега мениджърът е добавил карта 'Магазин Роза', след 5-10 секунди той вече може да припомни, че е забравил да посочи имейл и да иска да я намери и поправи.

Затова — нека търсим "директно по базата". За щастие, PostgreSQL ни позволява да го направим, и не само с един вариант — ще ги разгледаме.

1.1: "честна" подстрока

Задържаме се на думата "подстрока". А всъщност точно за индексно търсене по подстрока (и дори по регулярни изрази!) има отличен модул pg_trgm! Само после трябва да ги сортираме правилно.

Нека опитаме да вземем за простота такава таблица:

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

Зареждаме там 7.8 милиона записи на реални организации и индексируем:

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

Нека потърсим за подстрочно търсене първите 10 записи:

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

Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

Е, така… 26мс, 31MB прочетени данни и над 1.7K отфилтрирани записи — за 10 търсения. Разходите са твърде високи, не може ли да се направи по-ефективно?

1.2: търсене по текст? това е FTS!

Наистина, PostgreSQL предлага много мощен механизъм за пълнотекстово търсене (Full Text Search), включително с възможност за префиксно търсене. Отличен вариант, дори не е нужно да се инсталират разширения! Нека опитаме:

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;

Тук ни помогна малко паралелизацията на изпълнението на заявката, намалявайки времето до 11мс. И прочетохме с 1.5 пъти по-малко — само 20MB. А тук колкото по-малко, толкова по-добре, защото колкото по-голям обем четем, толкова по-високи са шансовете за получаване на cache miss, и всяка излишна прочетена от диска страница данни — потенциални "забавяния" за заявката.

1.3: все пак LIKE?

Предишната заявка е добра, но ако я извикаме сто хиляди пъти за един ден, ще се натрупа вече 2TB прочетени данни. В най-добрия случай — от паметта, но ако ни няма късмет, и от диска. Нека опитаме да го направим по-малък.

Нека си припомним, че потребителят иска да види първо „които започват с …“. Но това е чиста същност префиксно търсене чрез text_pattern_ops! И само ако ни „недостигнат“ до 10 търсени записа, ще трябва да ги довършим с помощта на FTS-търсенето:

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

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

Отлични показатели — само 0.05ms и малко над 100KB прочетени! Само, че забравихме сортировката по име, за да не се загуби потребителят в резултатите:

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

Ох, нещо вече не изглежда красиво — изглежда, че индексът съществува, но сортировката минава покрай него… Разбира се, вече е многократно по-ефективно от предишния вариант, но…

1.4: „допълнително да доработим“

Но има индекс, който позволява да търсим и по диапазон, и нормално да използваме сортиране — обикновен B-tree!

CREATE INDEX ON firms(lower(name));

Само, че заявката под него ще трябва да се „сглобява ръчно“:

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

Отлично — и сортирането работи, и потреблението на ресурси остана „микроскопично“ , в хиляди пъти по-ефективно от „чистото“ FTS! Остава да съберем в една заявка:

(
  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 -- използваме същата сортировка, за да НЕ се насочим към B-tree индекса
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Забележете, че втората подзаявка се изпълнява само ако първата върне по-малко от очакваното последният LIMIT брой редове. За този метод на оптимизация на заявките съм писал по-рано.

Такива, имаме сега на таблицата едновременно B-tree и GIN, но статистически стана така, че по-малко от 10% от заявките достигат до изпълнение на втория блок.. Тоест, при тези известни предварително типични ограничения за задачата успяхме да намалим общото потребление на ресурси на сървъра практически хиляди пъти!

1.5*: ще се справим без допълнителна обработка

По-горе LIKE не позволява да използваме неправилно подреждане. Но можем да я „насочим по правилния път“ с помощта на оператора USING:

По подразбиране се подразбира ASC. Освен това, можем да зададем името на специфичен сортировъчен оператор в израза USING. Сортировъчният оператор трябва да бъде член на семейството оператори B-дерево „по-малко“ или „по-голямо“. ASC обикновено е равно на USING < и DESC обикновено е равно на USING >.

В нашия случай „по-малко“ е ~<~:

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

2: как „извратяват“ заявките

Сега оставяме нашата заявка „да отлежи“ половин година-година и с изненада отново я откриваме „в топа“ с показатели на сумарното ежедневното „покачване“ на паметта (buffers shared hit) в 5.5TB — тоест, дори повече, отколкото е било първоначално.

Не, разбира се, бизнесът ни се увеличи и натоварването нарасна, но не до такава степен! Значи нещо не е наред — нека разберем.

2.1: рождение на пейджинга

В един момент на друг екип разработчици им се прииска да направят възможност за „скок“ от бързо подтекстово търсене в регистъра с идентични, но разширени резултати. А какъв регистър без странична навигация? Нека го прикачим!

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

Сега можеше без напрежение за разработчика да се показва регистър на резултатите от търсенето с „типично-странично“ зареждане.

Разбира се, всъщност, за всяка следваща страница данни се чете все повече и повече (всички от предишния път, които ще отхвърлим, плюс нужния „остртъ“) — т.е. това е еднозначен антипатърн. А по-правилно би било — да стартираме търсенето на следващата итерация от запомненото в интерфейса ключово поле, но за това — друг път.

2.2: искам екзотика

В един момент на разработчика му се прииска да разнообрази резултатната извадка с данни от друга таблица, за което целият предишен запрос беше изпратен в CTE:

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

И дори така — не е лошо, тъй като вложената заявка се изчислява само за 10-те възстановени записа, ако не беше...

2.3: DISTINCT безсмислен и безмилостен

Някъде в процеса на такава еволюция от 2-рия подзапрос се загуби NOT LIKE условие. Разбира се, че след това UNION ALL започна да връща някои записи два пъти — първо намерените по начало на редовете, а след това отново — по началото на първата дума от този ред. Всички записи от втория подзапрос в крайна сметка можеха да съвпаднат с тези от първия.

Какво прави разработчикът вместо да търси причината?.. Няма проблем!

да удвоим размера на изходните извадки
ще наложим DISTINCT, за да получим само единствени екземпляри на всеки ред

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

Тоест, ясно е, че резултатът в крайна сметка е абсолютно същият, но шансът да "пропуснеш" втория подзапрос CTE стана значително по-висок и без това, явно се чете повече.

Но това не е най-лошото. Тъй като разработчикът помоли да изберат DISTINCT не по конкретни, а веднага по всички полета записи, автоматично влезе и полето sub_query — резултатът от подзапроса. Сега, за да се изпълни DISTINCT, базата трябваше да извърши вече не 10 подзапроса, а всичките + 10!

2.4: кооперацията над всичко!

Така живееха разработчиците — не се оплакваха, защото в регистъра "да увеличат" до значителни стойности N при хронично забавяне на получаването на всяка следваща "страница" явно им липсваше търпение.

Докато не дойдоха разработчиците от друг отдел и не поискаха да използват този удобен метод за итеративно търсене — тоест взимаме част от някаква извадка, филтрираме по допълнителни условия, извеждаме резултата, след това следващата част (което в нашия случай се постига чрез увеличаване на N), и така продължаваме, докато не запълним екрана.

По принцип, в уцеления екземпляр N достигна стойности почти 17K, а за 24 часа бяха извършени "по веригата" не по-малко от 4K такива заявки. Последните от тях смело сканираха вече по 1GB памет при всяка итерация…