Periodyk ûntstiet de taak fan it sykjen nei besibbe gegevens mei in set fan kaaien. oant wy krije it fereaske totale oantal records.
It meast "echte libben" foarbyld is te werjaan 20 âldste problemen, listed op de list fan meiwurkers (bygelyks binnen ien divyzje). Foar ferskate bestjoerlike "dashboards" mei koarte gearfettings fan wurkgebieten is in ferlykber ûnderwerp frij faak nedich.
Yn dit artikel sille wy sjen nei de ymplemintaasje yn PostgreSQL fan in "naïve" oplossing foar sa'n probleem, in "tûker" en heul kompleks algoritme "loop" yn SQL mei in útgong betingst fan de fûn gegevens, dy't nuttich wêze kin sawol foar algemiene ûntwikkeling as foar gebrûk yn oare ferlykbere gefallen.
Lit ús nimme in test gegevens set út . Om foar te kommen dat de werjûn records fan tiid ta tiid "springe" as de sorteare wearden gearfalle, wreidzje de ûnderwerpyndeks út troch in primêre kaai ta te foegjen. Tagelyk sil dit it direkt unyk jaan en ús garandearje dat de sortearfolchoarder ûndûbelsinnich is:
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;Sa't it heard wurdt, sa is it skreaun
Litte wy earst de ienfâldichste ferzje fan it fersyk sketsje, de ID's fan 'e artysten trochjaan :
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;
In bytsje tryst - wy hawwe mar 20 records besteld, mar Index Scan joech it ús werom 960 lyn, dy't dan ek sortearre wurde moast... Litte wy besykje minder te lêzen.
unnest + ARRAY
De earste konsideraasje dy't ús sil helpe is as wy nedich binne allinnich 20 sortearre records, dan gewoan lêze net mear as 20 sortearre yn deselde folchoarder foar elk kaai. Goed, geskikt yndeks (owner_id, task_date, id) wy hawwe.
Litte wy itselde meganisme brûke foar ekstrahearje en "fersprieden yn kolommen" yntegraal tabel record, lykas . Wy kinne ek folding tapasse yn in array mei de funksje 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; -- ... и тут - тоже
Och, folle better al! 40% flugger en 4.5 kear minder gegevens Ik moast it lêze.
Materialisaasje fan tabelrecords fia CTELit my jo oandacht op it feit dat yn guon gefallen In besykjen om fuortendaliks te wurkjen mei de fjilden fan in record nei it sykjen nei it yn in subquery, sûnder it yn in CTE te "wikkeljen", kin liede ta "fermannichfâldigje" InitPlan evenredich mei it oantal fan deselde fjilden:
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
Itselde rekord waard 4 kear "opsocht" ... Oant PostgreSQL 11 komt dit gedrach regelmjittich foar, en de oplossing is om it yn in CTE te "wrapjen", wat in absolute limyt is foar de optimizer yn dizze ferzjes.
Rekursive accumulator
Yn 'e foarige ferzje lêze wy yn totaal 200 lyn om 'e wille fan' e fereaske 20. Net 960, mar noch minder - is it mooglik?
Litte wy besykje de kennis te brûken dy't wy nedich binne totaal 20 records. Dat is, wy sille it lêzen fan gegevens allinich iterearje oant wy it bedrach berikke dat wy nedich binne.
Stap 1: Startlist
Fansels soe ús "doel" list fan 20 records moatte begjinne mei de "earste" records foar ien fan ús owner_id-kaaien. Dêrom sille wy earst soks fine "heul earste" foar elk fan 'e kaaien en foegje it ta oan de list, sortearje it yn 'e folchoarder dy't wy wolle - (task_date, id).
Stap 2: Fyn de "folgjende" yngongen
No as wy de earste yngong fan ús list nimme en begjinne "stap" fierder lâns de yndeks it behâld fan 'e owner_id-kaai, dan binne alle fûn records krekt de folgjende yn 'e resultearjende seleksje. Fansels, allinnich oant wy oer de kont kaai twadde yngong yn 'e list.
As bliken docht dat wy it twadde rekôr "oerstutsen" binne, dan de lêste yngong lêzen moat wurde tafoege oan de list ynstee fan de earste (mei deselde eigener_id), wêrnei't wy de list opnij sortearje.
Dat is, wy krije altyd dat de list net mear as ien yngong hat foar elk fan 'e kaaien (as de yngongen oprinne en wy net "krúsje", dan sil de earste yngong út 'e list gewoan ferdwine en neat wurdt tafoege ), en hja altyd sortearre yn oprinnende folchoarder fan de applikaasje kaai (task_date, id).
Stap 3: filterje en "útwreidzje" records
Yn guon fan 'e rigen fan ús rekursive seleksje, guon records rv wurde duplikearre - earst fine wy sa as "de grins oerstekke fan 'e 2e yngong fan' e list", en ferfange it dan as de 1e fan 'e list. Dus it earste foarkommen moat wurde filtere.
De freze lêste fraach
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; -- берем только "непересекающие" записи
Sa, wy ferhannele 50% fan gegevens lêzen foar 20% fan útfiering tiid. Dat is, as jo redenen hawwe om te leauwen dat it lêzen lang duorje kin (bygelyks binne de gegevens faak net yn 'e cache, en jo moatte der foar nei skiif gean), dan kinne jo op dizze manier minder ôfhinklik wêze fan it lêzen .
Yn alle gefallen, de útfiering tiid wie better as yn de "naïve" earste opsje. Mar hokker fan dizze 3 opsjes te brûken is oan jo.
Boarne: www.habr.com