Periodisk opstår opgaven med at søge efter relaterede data ved hjælp af et sæt nøgler. indtil vi får det nødvendige samlede antal poster.
Det mest "virkelige liv" eksempel er at vise 20 ældste problemer, opført på listen over medarbejdere (f.eks. inden for én division). For forskellige ledelses-"dashboards" med korte opsummeringer af arbejdsområder kræves et lignende emne ret ofte.
I denne artikel vil vi se på implementeringen i PostgreSQL af en "naiv" løsning på et sådant problem, en "smartere" og meget kompleks algoritme "loop" i SQL med en udgangsbetingelse fra de fundne data, som kan være nyttig både til generel udvikling og til brug i andre lignende tilfælde.
Lad os tage et testdatasæt fra . For at forhindre de viste poster i at "hoppe" fra tid til anden, når de sorterede værdier falder sammen, udvide emneindekset ved at tilføje en primær nøgle. Samtidig vil dette øjeblikkeligt give det unikhed og garantere os, at sorteringsrækkefølgen er entydig:
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;Som det høres, sådan er det skrevet
Lad os først skitsere den enkleste version af anmodningen ved at videregive kunstnernes ID'er :
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;
Lidt trist - vi bestilte kun 20 plader, men Index Scan returnerede den til os 960 linjer, som så også skulle sorteres... Lad os prøve at læse mindre.
unnest + ARRAY
Den første overvejelse, der vil hjælpe os, er, om vi har brug for det kun 20 sorteret optegnelser, så er det bare at læse ikke mere end 20 sorteret i samme rækkefølge for hver nøgle. Godt, passende indeks (owner_id, task_date, id) vi har.
Lad os bruge den samme mekanisme til at udtrække og "spredning i kolonner" integreret tabelpost, som i . Vi kan også anvende foldning til et array ved hjælp af funktionen 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; -- ... и тут - тоже
Åh, meget bedre allerede! 40 % hurtigere og 4.5 gange færre data Jeg var nødt til at læse den.
Materialisering af tabelposter via CTELad mig henlede din opmærksomhed på det faktum i nogle tilfælde Et forsøg på straks at arbejde med felterne i en post efter at have søgt efter den i en underforespørgsel, uden at "pakke" den ind i en CTE, kan føre til "multiplicer" InitPlan proportionalt med antallet af de samme felter:
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
Den samme post blev "slået op" 4 gange... Indtil PostgreSQL 11 forekommer denne adfærd regelmæssigt, og løsningen er at "pakke" den ind i en CTE, hvilket er en absolut grænse for optimizeren i disse versioner.
Rekursiv akkumulator
I den tidligere version læste vi i alt 200 linjer af hensyn til de nødvendige 20. Ikke 960, men endnu mindre - er det muligt?
Lad os prøve at bruge den viden, vi har brug for i alt 20 optegnelser. Det vil sige, at vi kun gentager datalæsning, indtil vi når den mængde, vi har brug for.
Trin 1: Startliste
Det er klart, at vores "mål"-liste med 20 poster skal starte med de "første" poster for en af vores ejer_id-nøgler. Derfor vil vi først finde sådanne "allerførst" for hver af tasterne og føj det til listen, sorter det i den rækkefølge, vi ønsker - (opgavedato, id).
Trin 2: Find de "næste" poster
Hvis vi nu tager den første post fra vores liste og starter "trin" længere hen ad indekset ved at bevare nøglen ejer_id, så er alle de fundne poster nøjagtigt de næste i det resulterende valg. Selvfølgelig kun indtil vi krydser numsenøglen anden post på listen.
Hvis det viser sig, at vi "krydsede" den anden rekord, så den sidste læste post skal tilføjes til listen i stedet for den første (med samme ejer_id), hvorefter vi omsorterer listen igen.
Det vil sige, at vi altid får, at listen ikke har mere end én post for hver af tasterne (hvis indtastningerne løber tør, og vi ikke "krydser", så forsvinder den første post fra listen simpelthen, og intet vil blive tilføjet ), og de altid sorteret i stigende rækkefølge af applikationsnøglen (opgavedato, id).
Trin 3: filtrer og "udvid" poster
I nogle af rækkerne i vores rekursive udvalg, nogle poster rv er duplikeret - først finder vi f.eks. "krydser grænsen til listens 2. post", og erstatter den derefter som den 1. fra listen. Så den første forekomst skal filtreres.
Den frygtede sidste forespørgsel
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; -- берем только "непересекающие" записи
Således, vi handlede 50 % af datalæsninger i 20 % af eksekveringstiden. Det vil sige, at hvis du har grunde til at tro, at læsning kan tage lang tid (dataene er f.eks. ofte ikke i cachen, og du skal på disk for det), så kan du på denne måde være mindre afhængig af læsning .
Under alle omstændigheder viste udførelsestiden sig at være bedre end i den "naive" første mulighed. Men hvilken af disse 3 muligheder du skal bruge er op til dig.
Kilde: www.habr.com