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