Перыядычна ўзнікае задача пошуку злучаных дадзеных па наборы ключоў, пакуль не набяром патрэбную сумарную колькасць запісаў.
Найбольш «жыццёвы» прыклад - вывесці 20 самых старых задач, якія лічацца на спісе супрацоўнікаў (напрыклад, у рамках аднаго падраздзялення). Для розных кіраўніцкіх "дашбордаў" з кароткімі выцісканнямі па ўчастках працы падобная тэма патрабуецца досыць часта.
У артыкуле разгледзім рэалізацыю на PostgreSQL "наіўнага" варыянты рашэння такой задачы, "разумнейшы" і зусім складаны алгарытм "цыкла" на SQL з умовай выхаду ад знойдзеных дадзеных, Які можа быць карысны як для агульнага развіцця, так і для прымянення ў іншых падобных выпадках.
Возьмем тэставы набор дадзеных з
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;
Як чуецца, так і пішацца
Спачатку накідаем самы просты варыянт запыту, перадаючы ID выканаўцаў.
SELECT
*
FROM
task
WHERE
owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
task_date, id
LIMIT 20;
Трохі сумна - мы заказвалі ўсяго 20 запісаў, а Index Scan вярнуў нам 960 радкоў, Якія потым яшчэ і сартаваць прыйшлося ... А давайце паспрабуем чытаць паменш.
unnest + ARRAY
Першае меркаванне, якое нам дапаможа - калі нам трэба ўсяго 20 адсартаваных запісаў, то дастаткова чытаць не больш за 20 адсартаваных у тым жа парадку па кожным ключу. Добра, прыдатны індэкс (owner_id, task_date, id) у нас ёсць.
Скарыстаемся тым жа механізмам вымання і "развароту ў слупкі" цэласнага запісу табліцы, што і ў ARRAY()
:
WITH T AS (
SELECT
unnest(ARRAY(
SELECT
t
FROM
task t
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 20 -- ограничиваем тут...
)) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
(r).*
FROM
T
ORDER BY
(r).task_date, (r).id
LIMIT 20; -- ... и тут - тоже
О, ужо нашмат лепш! На 40% хутчэй, і ў 4.5 разы менш дадзеных прыйшлося чытаць.
Матэрыялізацыя запісаў табліц праз CTEЗвярну ўвагу, што у некаторых выпадках спроба адразу працаваць з палямі запісу пасля яе пошуку ў подзапросе, без «абарочвання» у CTE можа прыводзіць да «мнажэнню» InitPlan прапарцыйна колькасці гэтых самых палёў:
SELECT
((
SELECT
t
FROM
task t
WHERE
owner_id = 1
ORDER BY
task_date, id
LIMIT 1
).*);
Result (cost=4.77..4.78 rows=1 width=16) (actual time=0.063..0.063 rows=1 loops=1)
Buffers: shared hit=16
InitPlan 1 (returns $0)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.031..0.032 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t (cost=0.42..387.57 rows=500 width=48) (actual time=0.030..0.030 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 2 (returns $1)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_1 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 3 (returns $2)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_2 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4"
InitPlan 4 (returns $3)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_3 (cost=0.42..387.57 rows=500 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
Адзін і той жа запіс "пашукаўся" 4 разы… Аж да PostgreSQL 11 такія паводзіны сустракаюцца рэгулярна, і рашэннем з'яўляецца "абарочванне" у CTE, што з'яўляецца безумоўнай мяжой для аптымізатара ў гэтых версіях.
Рэкурсіўны акумулятар
У папярэднім варыянце сумарна мы прачыталі 200 радкоў дзеля патрэбных 20. Ужо не 960, але яшчэ менш - можна?
Давайце паспрабуем скарыстацца веданнем, што нам трэба ўсяго 20 запісаў. Гэта значыць будзем ітэраваць вычытку дадзеных толькі да дасягнення патрэбнай нам колькасці.
Крок 1: стартавы спіс
Відавочна, што наш "мэтавы" спіс з 20 запісаў павінен пачынацца з "першых" запісаў па адным з нашых owner_id-ключоў. Таму спачатку знойдзем такія "самыя першыя" па кожным з ключоў і занясем у спіс, адсартаваўшы яго ў парадку, які жадаем - (task_date, id).
Крок 2: знаходзім "наступныя" запісы
Цяпер, калі мы возьмем з нашага спісу першы запіс і пачнем крочыць далей па індэксе з захаваннем owner_id-ключа, то ўсе знойдзеныя запісы - як раз наступныя ў выніковай выбарцы. Вядома, толькі пакуль мы не перасячэм прыкладны ключ другі запісы ў спісе.
Калі атрымалася, што мы другі запіс "перасеклі", то апошні прачытаны запіс павінен быць дададзены ў спіс замест першай (з тым жа owner_id), пасля чаго спіс ізноў перасартоўваем.
Гэта значыць, у нас увесь час атрымліваецца, што ў спісе ёсць не больш за адзін запіс па кожным з ключоў (калі запісы скончыліся, а мы не «перасеклі», то са спісу першы запіс проста знікне і нічога не дадасца), прычым яны заўсёды адсартаваны у парадку ўзрастання прыкладнога ключа (task_date, id).
Крок 3: фільтруем і "разгортваем" запісы
У частцы радкоў нашай рэкурсіўнай выбаркі некаторыя запісы rv
дублююцца — спачатку мы знаходзім такія як «перасякаючую мяжу 2-га запісу спісу», а потым падстаўляем як 1-ю са спісу. Дык вось першае з'яўленне трэба адфільтраваць.
Страшны выніковы запыт
WITH RECURSIVE T AS (
-- #1 : заносим в список "первые" записи по каждому из ключей набора
WITH wrap AS ( -- "материализуем" record'ы, чтобы обращение к полям не вызывало умножения InitPlan/SubPlan
WITH T AS (
SELECT
(
SELECT
r
FROM
task r
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 1
) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
array_agg(r ORDER BY (r).task_date, (r).id) list -- сортируем список в нужном порядке
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNION ALL
-- #2 : вычитываем записи 1-го по порядку ключа, пока не перешагнем через запись 2-го
SELECT
CASE
-- если ничего не найдено для ключа 1-й записи
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- убираем ее из списка
-- если мы НЕ пересекли прикладной ключ 2-й записи
WHEN X.not_cross THEN
T.list -- просто протягиваем тот же список без модификаций
-- если в списке уже нет 2-й записи
WHEN T.list[2] IS NULL THEN
-- просто возвращаем пустой список
'{}'
-- пересортировываем словарь, убирая 1-ю запись и добавляя последнюю из найденных
ELSE (
SELECT
coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
FROM
unnest(T.list[3:] || X._r) r
)
END
, X._r
, X.not_cross
, T.size + X.not_cross::integer
FROM
T
, LATERAL(
WITH wrap AS ( -- "материализуем" record
SELECT
CASE
-- если все-таки "перешагнули" через 2-ю запись
WHEN NOT T.not_cross
-- то нужная запись - первая из спписка
THEN T.list[1]
ELSE ( -- если не пересекли, то ключ остался как в предыдущей записи - отталкиваемся от нее
SELECT
_r
FROM
task _r
WHERE
owner_id = (rv).owner_id AND
(task_date, id) > ((rv).task_date, (rv).id)
ORDER BY
task_date, id
LIMIT 1
)
END _r
)
SELECT
_r
, CASE
-- если 2-й записи уже нет в списке, но мы хоть что-то нашли
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- ничего не нашли или "перешагнули"
coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
END not_cross
FROM
wrap
) X
WHERE
T.size < 20 AND -- ограничиваем тут количество
T.list IS DISTINCT FROM '{}' -- или пока список не кончился
)
-- #3 : "разворачиваем" записи - порядок гарантирован по построению
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- берем только "непересекающие" записи
Такім чынам, мы абмянялі 50% чытанняў дадзеных на 20% часу выканання. Гэта значыць калі ў вас ёсць чыннікі меркаваць, што чытанне можа быць доўгім (напрыклад, дадзеныя часцяком не ў кэшы, і даводзіцца за імі хадзіць на дыск), то такім спосабам можна залежаць ад чытання менш.
У любым выпадку, час выканання атрымалася лепш, чым у "наіўным" першым варыянце. Але якім з гэтых 3 варыянтаў карыстацца - выбіраць вам.
Крыніца: habr.com