In komplekse ERP-stelsels baie entiteite het 'n hiërargiese aardwanneer homogene voorwerpe in lyn is boom van voorvader-afstammelinge verhoudings - dit is die organisasiestruktuur van die onderneming (al hierdie takke, departemente en werkgroepe), en die katalogus van goedere, en werksareas, en die geografie van verkoopspunte,...
Trouens, daar is geen , waar daar geen hiërargie as gevolg daarvan sou wees nie. Maar selfs as jy nie "vir die besigheid" werk nie, kan jy steeds maklik hiërargiese verhoudings teëkom. Dit is eenvoudig, selfs jou stamboom of vloerplan van 'n perseel in 'n winkelsentrum is dieselfde struktuur.
Daar is baie maniere om so 'n boom in 'n DBBS te stoor, maar vandag sal ons net op een opsie fokus:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
En terwyl jy in die dieptes van die hiërargie loer, wag dit geduldig om te sien hoe [in]effektief jou "naïewe" maniere van werk met so 'n struktuur sal wees.
Kom ons kyk na tipiese probleme wat opduik, hul implementering in SQL, en probeer om hul werkverrigting te verbeter.
#1. Hoe diep is die konyngat?
Kom ons, vir beslis, aanvaar dat hierdie struktuur die ondergeskiktheid van departemente in die struktuur van die organisasie sal weerspieël: departemente, afdelings, sektore, takke, werkgroepe... - wat jy hulle ook al noem.
Kom ons genereer eers ons 'boom' van 10K elemente
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;Kom ons begin met die eenvoudigste taak - om alle werknemers te vind wat binne 'n spesifieke sektor werk, of in terme van hiërargie - vind alle kinders van 'n nodus. Dit sal ook lekker wees om die “diepte” van die afstammeling te kry... Dit alles mag nodig wees, byvoorbeeld om een of ander .
Alles sal goed wees as daar net 'n paar vlakke van hierdie afstammelinge is en die getal binne 'n dosyn is, maar as daar meer as 5 vlakke is, en daar is reeds dosyne afstammelinge, kan daar probleme wees. Kom ons kyk hoe tradisionele onder-die-boom soekopsies geskryf (en werk). Maar eers, kom ons bepaal watter nodusse die interessantste vir ons navorsing sal wees.
Die meeste "diep" subbome:
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}
...Die meeste "wyd" subbome:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Vir hierdie navrae het ons die tipiese rekursiewe JOIN:
Natuurlik, met hierdie versoek model die aantal iterasies sal ooreenstem met die totale aantal afstammelinge (en daar is 'n paar dosyn van hulle), en dit kan baie beduidende hulpbronne neem, en as gevolg daarvan tyd.
Kom ons kyk na die "wydste" 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;
Soos verwag, het ons al 30 rekords gevind. Maar hulle het 60% van die totale tyd hieraan bestee – want hulle het ook 30 soektogte in die indeks gedoen. Is dit moontlik om minder te doen?
Grootmaat proeflees volgens indeks
Moet ons 'n aparte indeksnavraag vir elke nodus maak? Dit blyk dat nee - ons kan lees uit die indeks gebruik verskeie sleutels gelyktydig in een oproep met die hulp = ANY(array).
En in elke so 'n groep identifiseerders kan ons al die ID's wat in die vorige stap gevind is deur "nodes" neem. Dit wil sê, by elke volgende stap sal ons soek op een slag na alle afstammelinge van 'n sekere vlak.
Net hier is die probleem, in rekursiewe seleksie kan jy nie toegang tot homself in 'n geneste navraag kry nie, maar ons moet op een of ander manier net kies wat op die vorige vlak gevind is... Dit blyk dat dit onmoontlik is om 'n geneste navraag vir die hele seleksie te maak, maar vir sy spesifieke veld is dit moontlik. En hierdie veld kan ook 'n skikking wees - dit is wat ons moet gebruik ANY.
Dit klink 'n bietjie mal, maar in die 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 die belangrikste ding nie eens nie wen 1.5 keer betyds, en dat ons minder buffers afgetrek het, aangesien ons net 5 oproepe na die indeks het in plaas van 30!
'n Bykomende bonus is die feit dat die identifiseerders na die finale onrus gerangskik sal bly volgens "vlakke".
Node teken
Die volgende oorweging wat sal help om prestasie te verbeter, is − "blare" kan nie kinders hê nie, dit wil sê, vir hulle is dit glad nie nodig om “af” te kyk nie. In die formulering van ons taak beteken dit dat as ons die ketting van departemente gevolg het en 'n werknemer bereik het, dit nie nodig is om verder langs hierdie tak te kyk nie.
Kom ons betree ons tabel bykomende boolean-veld, wat ons dadelik sal vertel of hierdie spesifieke inskrywing in ons boom 'n "knoop" is - dit wil sê of dit hoegenaamd afstammelinge kan hê.
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 мс.Puik! Dit blyk dat net 'n bietjie meer as 30% van alle boomelemente afstammelinge het.
Kom ons gebruik nou 'n effens ander werktuigkundige - verbindings met die rekursiewe deel deur LATERAL, wat ons in staat sal stel om onmiddellik toegang tot die velde van die rekursiewe "tabel" te kry, en 'n totale funksie te gebruik met 'n filtervoorwaarde gebaseer op 'n nodus om die stel sleutels te verminder:
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;
Ons kon nog een indeksoproep verminder en het meer as 2 keer in volume gewen proeflees.
#2. Kom ons gaan terug na die wortels
Hierdie algoritme sal nuttig wees as jy rekords vir alle elemente “op die boom” moet versamel, terwyl jy inligting behou oor watter bronblad (en met watter aanwysers) veroorsaak het dat dit by die steekproef ingesluit is - byvoorbeeld om 'n opsommende verslag te genereer met samevoeging in nodusse.
Wat volg moet uitsluitlik as 'n bewys-van-konsep geneem word, aangesien die versoek baie omslagtig blyk te wees. Maar as dit jou databasis oorheers, moet jy daaraan dink om soortgelyke tegnieke te gebruik.
Kom ons begin met 'n paar eenvoudige stellings:
- Dieselfde rekord vanaf die databasis Dit is die beste om dit net een keer te lees.
- Rekords uit die databasis Dit is meer doeltreffend om in bondels te leesas alleen.
Kom ons probeer nou om die versoek wat ons benodig saam te stel.
Stap 1
Natuurlik, wanneer rekursie geïnisialiseer word (waar sou ons daarsonder wees!) sal ons die rekords van die blare self moet aftrek op grond van die stel aanvanklike identifiseerders:
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
...
As dit vir iemand vreemd gelyk het dat die "stel" as 'n string gestoor word en nie 'n skikking nie, dan is daar 'n eenvoudige verduideliking hiervoor. Daar is 'n ingeboude samevoegende "gom"-funksie vir snare string_agg, maar nie vir skikkings nie. Alhoewel sy .
Stap 2
Nou sal ons 'n stel afdeling-ID's kry wat verder gelees sal moet word. Byna altyd sal hulle in verskillende rekords van die oorspronklike stel gedupliseer word - so ons sou groepeer hulle, terwyl inligting oor die bronblaaie bewaar word.
Maar hier wag drie probleme op ons:
- Die "subrekursiewe" deel van die navraag kan nie saamgestelde funksies met
GROUP BY. - 'n Verwysing na 'n rekursiewe "tabel" kan nie in 'n geneste subnavraag wees nie.
- 'n Versoek in die rekursiewe deel kan nie 'n CTE bevat nie.
Gelukkig is al hierdie probleme redelik maklik om om te werk. Kom ons begin van die einde af.
CTE in rekursiewe deel
Hier so geen werk:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)En so werk dit, die hakies maak die verskil!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Geneste navraag teen 'n rekursiewe "tabel"
Hmm... 'n Rekursiewe CTE kan nie in 'n subnavraag verkry word nie. Maar dit kan binne CTE wees! En 'n geneste versoek het reeds toegang tot hierdie CTE!
GROEP DEUR binne-rekursie
Dit is onaangenaam, maar ... Ons het 'n eenvoudige manier om GROEP DEUR te gebruik DISTINCT ON en vensterfunksies!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!En dit is hoe dit werk!
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 NULLNou sien ons hoekom die numeriese ID in teks verander is - sodat hulle saamgevoeg kon word, geskei deur kommas!
Stap 3
Vir die eindstryd het ons niks oor nie:
- ons lees "afdeling"-rekords gebaseer op 'n stel gegroepeerde ID's
- ons vergelyk die afgetrekte afdelings met die "stelle" van die oorspronklike velle
- "brei" die stel-string 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: will.com