PostgreSQL Antipatterns: оповідь про ітеративне доопрацювання пошуку за назвою, або «Оптимізація туди і назад»

Тисячі менеджерів з офісів продажів по всій країні фіксують у нашій CRM-системі щодня десятки тисяч контактів - фактів спілкування з потенційними або вже працюючими з нами клієнтами. А для цього клієнта треба спочатку знайти і бажано дуже швидко. І відбувається це найчастіше за назвою.

Тому не дивно, що, в черговий раз розбираючи «важкі» запити на одній із найбільш навантажених баз — нашого власного. корпоративного акаунту НВІС, я виявив «у топі» запит для «швидкого» пошуку за назвою для карток організацій.

Причому подальше розслідування виявило цікавий приклад спочатку оптимізації, а потім деградації продуктивності запиту при послідовному його доопрацюванні силами кількох команд, кожна з яких діяла виключно з кращих спонукань.

0: чого ж хотів користувач

[КДПВ звідси]

Що взагалі зазвичай має на увазі користувач, коли говорить про «швидкий» пошук за назвою? Майже ніколи це не виявляється «чесний» пошук по підрядку типу ... LIKE '%роза%' - Адже тоді в результат потрапляють не тільки 'Розалия' и 'Магазин Роза', Але й 'Гроза' і навіть 'Дом Деда Мороза'.

Користувач же має на увазі на побутовому рівні, що ви йому забезпечите пошук на початку слова у назві і покажете більш релевантним те, що починається на введене. І зробите це практично миттєво - При підрядковому введенні.

1: обмежуємо завдання

І тим більше не буде людина спеціально вводити 'роз магаз'щоб кожне слово вам доводилося шукати префіксно. Ні, користувачеві відреагувати на швидку підказку для останнього слова набагато простіше, ніж цілеспрямовано "недоводити" попередні - подивіться, як це відпрацьовує будь-який пошуковик.

Взагалі, правильно сформулювати вимоги до завдання – більше половини рішення. Іноді уважний аналіз use case може суттєво впливати на результат.

Що робить абстрактний розробник?

1.0: зовнішній пошуковий двигун

Ой, пошук це складно, щось взагалі їм займатися не хочеться - віддамо це devops! Нехай вони нам розгорнуть зовнішню щодо БД пошукову систему: Sphinx, ElasticSearch...

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

Тому – давайте шукати «прямо по базі». На щастя, 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;

[Подивитися на explain.tensor.ru]

Ну, таке… 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;

[Подивитися на explain.tensor.ru]

Тут нам трохи допомогла паралелізація виконання запиту, скоротивши час удвічі до 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;

[Подивитися на explain.tensor.ru]

Відмінні показники 0.05мс і трохи більше 100KB прочитано! Тільки ми ж забули сортування за назвою, щоб користувач не заблукав у результатах:

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

[Подивитися на explain.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;

[Подивитися на explain.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 кількості рядків. Про такий спосіб оптимізації запитів я вже писав раніше.

Такі так, ми тепер маємо на таблиці одночасно 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;

[Подивитися на explain.tensor.ru]

2: як «прокисають» запити

Тепер залишаємо наш запит настоятися півроку-рік, і з подивом знову виявляємо його в топі з показниками сумарного добового прокачування пам'яті (buffers shared hit) В 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: DISTINCT безглуздий і нещадний

Десь у процесі такої еволюції з 2-го підзапиту загубилося NOT LIKE умова. Зрозуміло, що після цього UNION ALL почав повертати деякі записи двічі — спочатку знайдені на початку рядка, а потім ще раз — на початку першого слова цього рядка. У межі, всі записи 2го підзапиту могли збігтися із записами першого.

Що робить розробник замість пошуку причини? Не питання!

• розширимо вдвічі розмір вихідних вибірок
• накладемо DISTINCTщоб вийшли тільки одинарні екземпляри кожного рядка

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 пам'яті на кожній ітерації...

Разом

Джерело: habr.com