In complexe ERP-systemen veel entiteiten hebben een hiërarchisch karakterwanneer homogene objecten op één lijn staan boom van voorouders-afstammelingenrelaties - dit is de organisatiestructuur van de onderneming (al deze filialen, afdelingen en werkgroepen), en de catalogus van goederen en werkgebieden, en de geografie van verkooppunten,...
In feite is er geen , waar er daardoor geen hiërarchie zou bestaan. Maar zelfs als u niet ‘voor het bedrijf’ werkt, kunt u nog steeds gemakkelijk hiërarchische relaties tegenkomen. Het is banaal, zelfs uw stamboom of plattegrond van een pand in een winkelcentrum heeft dezelfde structuur.
Er zijn veel manieren om zo'n boom in een DBMS op te slaan, maar vandaag zullen we ons op slechts één optie concentreren:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
En terwijl jij in de diepten van de hiërarchie tuurt, is het geduldig wachten om te zien hoe [in]effectief jouw ‘naïeve’ manier van werken met een dergelijke structuur zal zijn.
Laten we eens kijken naar typische problemen die zich voordoen, hun implementatie in SQL, en proberen hun prestaties te verbeteren.
#1. Hoe diep is het konijnenhol?
Laten we met zekerheid aanvaarden dat deze structuur de ondergeschiktheid van afdelingen in de structuur van de organisatie zal weerspiegelen: afdelingen, divisies, sectoren, afdelingen, werkgroepen... - hoe je ze ook noemt.
Laten we eerst onze 'boom' van 10 elementen genereren
INSERT INTO hier
WITH RECURSIVE T AS (
SELECT
1::integer id
, '{1}'::integer[] pids
UNION ALL
SELECT
id + 1
, pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
FROM
T
WHERE
id < 10000
)
SELECT
pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
T;Laten we beginnen met de eenvoudigste taak: het vinden van alle werknemers die binnen een specifieke sector werken, of in termen van hiërarchie - vind alle kinderen van een knooppunt. Het zou ook leuk zijn om de “diepte” van de afstammeling te krijgen... Dit alles kan bijvoorbeeld nodig zijn om een soort van te bouwen .
Alles zou in orde zijn als er maar een paar niveaus van deze nakomelingen zijn en het aantal binnen een dozijn ligt, maar als er meer dan 5 niveaus zijn en er al tientallen nakomelingen zijn, kunnen er problemen optreden. Laten we eens kijken hoe traditionele zoekopties in de boomstructuur worden geschreven (en werken). Maar laten we eerst bepalen welke knooppunten het meest interessant zullen zijn voor ons onderzoek.
Meest "diep" subbomen:
WITH RECURSIVE T AS (
SELECT
id
, pid
, ARRAY[id] path
FROM
hier
WHERE
pid IS NULL
UNION ALL
SELECT
hier.id
, hier.pid
, T.path || hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC; id | pid | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...Meest "breed" subbomen:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Voor deze zoekopdrachten gebruikten we de standaard recursieve JOIN:
Uiteraard met dit verzoekmodel het aantal iteraties komt overeen met het totale aantal nakomelingen (en er zijn er enkele tientallen), en dit kan behoorlijk wat middelen vergen, en als gevolg daarvan ook tijd.
Laten we eens kijken naar de “breedste” subboom:
WITH RECURSIVE T AS (
SELECT
id
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T;
Zoals verwacht hebben we alle 30 records gevonden. Maar ze besteedden hier 60% van de totale tijd aan – omdat ze ook 30 zoekopdrachten in de index deden. Is het mogelijk om minder te doen?
Bulkproeflezen per index
Moeten we voor elk knooppunt een afzonderlijke indexquery maken? Het blijkt dat nee - we kunnen uit de index lezen meerdere toetsen tegelijk gebruiken tijdens één gesprek via = ANY(array).
En in elke dergelijke groep identificatiegegevens kunnen we alle ID's die we in de vorige stap hebben gevonden, per "knooppunt" nemen. Dat wil zeggen: bij elke volgende stap zullen we dat doen zoek in één keer naar alle nakomelingen van een bepaald niveau.
Alleen, hier is het probleem, bij recursieve selectie heeft u geen toegang tot zichzelf in een geneste query, maar we moeten op de een of andere manier alleen selecteren wat er op het vorige niveau is gevonden... Het blijkt dat het onmogelijk is om een geneste query voor de hele selectie te maken, maar voor het specifieke veld is het wel mogelijk. En dit veld kan ook een array zijn, en dat is wat we moeten gebruiken ANY.
Het klinkt een beetje gek, maar in het diagram is alles eenvoudig.
WITH RECURSIVE T AS (
SELECT
ARRAY[id] id$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
ARRAY(
SELECT
id
FROM
hier
WHERE
pid = ANY(T.id$)
) id$
FROM
T
WHERE
coalesce(id$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
unnest(id$) id
FROM
T;
En hier is het belangrijkste niet eens win 1.5 keer in de tijd, en dat we minder buffers hebben afgetrokken, omdat we slechts 5 oproepen naar de index hebben in plaats van 30!
Een extra bonus is het feit dat de identificatiegegevens na de laatste ontnesing geordend blijven op “niveaus”.
Knooppunt teken
De volgende overweging die de prestaties zal helpen verbeteren is − "bladeren" kunnen geen kinderen krijgen, dat wil zeggen dat het voor hen helemaal niet nodig is om “naar beneden” te kijken. Bij het formuleren van onze taak betekent dit dat als we de keten van afdelingen volgen en een medewerker bereiken, het niet nodig is om verder in deze branche te kijken.
Laten we onze tafel binnengaan extra boolean-veld, wat ons onmiddellijk zal vertellen of dit specifieke item in onze boom een “knooppunt” is, dat wil zeggen of het überhaupt nakomelingen kan hebben.
ALTER TABLE hier
ADD COLUMN branch boolean;
UPDATE
hier T
SET
branch = TRUE
WHERE
EXISTS(
SELECT
NULL
FROM
hier
WHERE
pid = T.id
LIMIT 1
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.Geweldig! Het blijkt dat slechts iets meer dan 30% van alle boomelementen nakomelingen heeft.
Laten we nu een iets ander mechanisme gebruiken: verbindingen met het recursieve deel door LATERAL, waarmee we onmiddellijk toegang krijgen tot de velden van de recursieve "tabel", en een aggregatiefunctie kunnen gebruiken met een filtervoorwaarde op basis van een knooppunt om de set sleutels te verkleinen:
WITH RECURSIVE T AS (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
X.*
FROM
T
JOIN LATERAL (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
pid = ANY(T.ns$)
) X
ON coalesce(T.ns$, '{}') <> '{}'
)
SELECT
unnest(id$) id
FROM
T;
We hebben nog een indexoproep kunnen verminderen en won meer dan 2 keer in volume proefgelezen.
#2. Laten we teruggaan naar de wortels
Dit algoritme is handig als u records moet verzamelen voor alle elementen “bovenop de boom”, terwijl u informatie moet bewaren over welk bronblad (en met welke indicatoren) ervoor heeft gezorgd dat dit in de steekproef is opgenomen, bijvoorbeeld om een samenvattend rapport te genereren met aggregatie in knooppunten.
Wat volgt moet uitsluitend worden opgevat als een proof-of-concept, aangezien het verzoek erg omslachtig blijkt te zijn. Maar als het uw database domineert, moet u overwegen soortgelijke technieken te gebruiken.
Laten we beginnen met een paar eenvoudige uitspraken:
- Hetzelfde record uit de database Het is het beste om het een keer te lezen.
- Records uit de database Het is efficiënter om in batches te lezendan alleen.
Laten we nu proberen het verzoek te construeren dat we nodig hebben.
Stap 1
Het is duidelijk dat we bij het initialiseren van recursie (waar zouden we zijn zonder!) de records van de bladeren zelf moeten aftrekken op basis van de reeks initiële identificatiegegevens:
WITH RECURSIVE tree AS (
SELECT
rec -- это цельная запись таблицы
, id::text chld -- это "набор" приведших сюда исходных листьев
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
...
Als het iemand vreemd leek dat de “set” is opgeslagen als een string en niet als een array, dan is daar een eenvoudige verklaring voor. Er is een ingebouwde aggregerende “lijm”-functie voor strings string_agg, maar niet voor arrays. Hoewel zij .
Stap 2
Nu krijgen we een reeks sectie-ID's die verder moeten worden gelezen. Bijna altijd zullen ze worden gedupliceerd in verschillende records van de originele set - en dat zouden wij ook doen groepeer ze, terwijl informatie over de bronbladeren behouden blijft.
Maar hier wachten ons drie problemen:
- Het "subrecursieve" deel van de query kan geen aggregatiefuncties bevatten
GROUP BY. - Een verwijzing naar een recursieve “tabel” kan niet in een geneste subquery voorkomen.
- Een verzoek in het recursieve deel kan geen CTE bevatten.
Gelukkig zijn al deze problemen vrij eenvoudig te omzeilen. Laten we vanaf het einde beginnen.
CTE in recursief deel
Hier dus geen werken:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)En zo werkt het, de haakjes maken het verschil!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Geneste zoekopdracht op basis van een recursieve 'tabel'
Hmm... Een recursieve CTE is niet toegankelijk in een subquery. Maar het zou binnen CTE kunnen zijn! En een genest verzoek heeft al toegang tot deze CTE!
GROEPEREN OP binnenrecursie
Het is onaangenaam, maar... We hebben een eenvoudige manier om GROUP BY te emuleren met behulp van DISTINCT ON en raamfuncties!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!En dit is hoe het werkt!
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULLNu zien we waarom de numerieke ID in tekst werd omgezet - zodat ze met elkaar konden worden samengevoegd, gescheiden door komma's!
Stap 3
Voor de finale hebben we niets meer:
- we lezen ‘sectie’-records op basis van een reeks gegroepeerde ID’s
- we vergelijken de afgetrokken secties met de “sets” van de originele vellen
- "breid" de set-string uit met behulp van
unnest(string_to_array(chld, ',')::integer[])
WITH RECURSIVE tree AS (
SELECT
rec
, id::text chld
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
(
WITH prnt AS (
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
)
, nodes AS (
SELECT
rec
FROM
hier rec
WHERE
id = ANY(ARRAY(
SELECT
id
FROM
prnt
))
)
SELECT
nodes.rec
, prnt.chld
FROM
prnt
JOIN
nodes
ON (nodes.rec).id = prnt.id
)
)
SELECT
unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
tree;
Bron: www.habr.com