PostgreSQL Antipatterns: История за итеративно усъвършенстване на търсенето по име или „Оптимизиране напред и назад“

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

Ето защо не е изненадващо, че за пореден път анализирайки „тежките“ заявки към една от най-натоварените бази данни – нашата собствена VLIS корпоративен акаунт, намерих "в горната част" заявка за "бързо" търсене по име за визитки.

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

0: какво иска потребителят

[KDPV следователно]

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

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

1: ограничете задачата

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

Като цяло, правилно формулирането на изискванията към проблема е повече от половината решение. Понякога внимателен анализ на случаите на употреба може значително да повлияе на резултата..

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

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;

[вижте expand.tensor.ru]

Ами такива... 26ms, 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;

[вижте expand.tensor.ru]

Паралелизирането на изпълнението на заявката ни помогна малко тук, съкращавайки времето наполовина 11ms. Да, и трябваше да четем 1.5 пъти по-малко - общо 20MB. И тук колкото по-малко - толкова по-добре, защото колкото по-голям обем изваждаме, толкова по-големи са шансовете да получим пропуск в кеша, а всяка допълнителна страница с данни, прочетена от диска, е потенциална "спирачка" за заявката.

1.3: все още ХАРЕСВАТЕ?

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

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

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

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

[вижте expand.tensor.ru]

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

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

[вижте expand.tensor.ru]

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

1.4: "завършете с файл"

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

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;

[вижте expand.tensor.ru]

Отлично - и сортирането работи, а потреблението на ресурси остава "микроскопично", хиляди пъти по-ефективен от "чистия" 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 -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

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

Така че да, сега имаме btree и 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;

[вижте expand.tensor.ru]

2: как исканията се влошават

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

Не, разбира се, и нашият бизнес се разрасна, и натоварването се увеличи, но не със същата сума! И така, нещо не е чисто тук - нека да го разберем.

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

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

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

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

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

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

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

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

И дори така, не е лошо, тъй като подзаявката се оценява само за 10 върнати записа, ако не ...

2.3: ЯСНО безсмислено и безмилостно

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

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

• удвоете размера първоначални проби
• налагат РАЗЛИЧНИза да получите само единични екземпляри от всеки ред

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

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

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

2.4: сътрудничеството преди всичко!

И така, разработчиците живяха - те не скърбяха, защото в регистъра се „завинтват“ до значителни стойности на N с хронично забавяне на получаването на всяка следваща „страница“, потребителят очевидно не е имал търпение.

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

Общо взето в уловен екземпляр N достигна почти 17K, и само за ден поне 4K такива заявки бяха изпълнени „по веригата“. Последният от тях смело сканиран вече от 1GB памет на итерация...

Общо

Източник: www.habr.com