Povremeno se javlja zadatak traženja povezanih podataka pomoću skupa ključeva. dok ne dobijemo potreban ukupan broj zapisa.
Najviše „stvarnog života“ primjer je prikazivanje 20 najstarijih problema, navedeno na spisku zaposlenih (na primjer, unutar jedne divizije). Za različite upravljačke „kontrolne table“ sa kratkim rezimeima oblasti rada, slična tema je često potrebna.
U ovom članku ćemo pogledati implementaciju u PostgreSQL "naivnog" rješenja za takav problem, "pametnijeg" i vrlo složenog algoritma “petlja” u SQL-u sa izlaznim uvjetom iz pronađenih podataka, što može biti korisno i za opći razvoj i za korištenje u drugim sličnim slučajevima.
Uzmimo skup testnih podataka iz . Da biste spriječili da prikazani zapisi s vremena na vrijeme "skaču" kada se sortirane vrijednosti poklapaju, proširite predmetni indeks dodavanjem primarnog ključa. Istovremeno, to će mu odmah dati jedinstvenost i garantirati nam da je redoslijed sortiranja nedvosmislen:
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;Kako se čuje, tako se i piše
Prvo, skicirajmo najjednostavniju verziju zahtjeva, prenoseći ID-ove izvođača :
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;
Malo tužno - naručili smo samo 20 zapisa, ali nam ih je Index Scan vratio 960 linija, koji je onda takođe morao biti sređen... Hajde da pokušamo manje čitati.
unnest + NIZ
Prva stvar koja će nam pomoći je da li nam treba samo 20 sortiranih zapise, pa samo pročitajte ne više od 20 sortiranih istim redoslijedom za svaku ključ. dobro, odgovarajući indeks (owner_id, task_date, id) imamo.
Koristimo isti mehanizam za izdvajanje i „širivanje u kolone“ integralni tabelarni zapiskao u . Također možemo primijeniti savijanje u niz pomoću funkcije 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; -- ... и тут - тоже
Oh, već mnogo bolje! 40% brže i 4.5 puta manje podataka Morao sam to pročitati.
Materijalizacija tabličnih zapisa putem CTE-aDozvolite mi da vam skrenem pažnju na to u nekim slučajevima Pokušaj da se odmah radi s poljima zapisa nakon traženja u potupitu, bez "umotavanja" u CTE, može dovesti do "umnoži" InitPlan proporcionalno broju ovih istih polja:
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
Isti zapis je "pretražen" 4 puta... Sve do PostgreSQL 11, ovakvo ponašanje se dešavalo redovno, a rešenje je da se "umota" u CTE, što je apsolutna granica za optimizator u ovim verzijama.
Rekurzivni akumulator
U prethodnoj verziji, ukupno čitamo 200 linija radi potrebnih 20. Ne 960, ali još manje - da li je moguće?
Pokušajmo iskoristiti znanje koje nam je potrebno ukupno 20 evidencije. Odnosno, ponavljaćemo čitanje podataka samo dok ne dostignemo količinu koja nam je potrebna.
Korak 1: Početna lista
Očigledno, naša "ciljna" lista od 20 zapisa bi trebala početi s "prvim" zapisima za jedan od naših ključeva owner_id. Stoga ćemo prvo pronaći takve "prvi" za svaki od ključeva i dodajte ga na listu, sortirajući ga redoslijedom kojim želimo - (datum_zadatka, id).
Korak 2: Pronađite „sljedeće“ unose
Sada ako uzmemo prvi unos sa naše liste i počnemo “koraknuti” dalje duž indeksa čuvajući ključ owner_id, tada su svi pronađeni zapisi upravo sljedeći u rezultirajućem odabiru. Naravno, samo dok ne pređemo ključ drugi unos na listi.
Ako se pokaže da smo "prešli" drugi rekord, onda posljednji pročitani unos treba dodati na listu umjesto prvog (sa istim owner_id), nakon čega ponovo sortiramo listu.
Odnosno, uvijek dobijemo da lista nema više od jednog unosa za svaki ključ (ako unosi ponestane i ne "ukrstimo", onda će prvi unos sa liste jednostavno nestati i ništa se neće dodati ), i oni uvek sortirano u rastućem redoslijedu ključa aplikacije (task_date, id).
Korak 3: filtrirajte i “proširite” zapise
U nekim redovima naše rekurzivne selekcije, neki zapisi rv se dupliraju - prvo nalazimo kao što je "prelazak granice 2. unosa na listi", a zatim ga zamjenjujemo kao 1. sa liste. Dakle, prvo pojavljivanje treba filtrirati.
Zastrašujući konačni upit
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; -- берем только "непересекающие" записи
Dakle, mi trgovali sa 50% čitanja podataka za 20% vremena izvršenja. Odnosno, ako imate razloga vjerovati da čitanje može potrajati (na primjer, podaci često nisu u kešu, a za to morate ići na disk), onda na ovaj način možete manje ovisiti o čitanju .
U svakom slučaju, pokazalo se da je vrijeme izvršenja bolje nego u „naivnoj“ prvoj opciji. Ali koju od ove 3 opcije koristiti, odlučujete sami.
izvor: www.habr.com