I komplexa affärssystem många enheter har en hierarkisk karaktärnär homogena föremål radas in träd av relationer mellan anfäder och ättlingar - detta är företagets organisationsstruktur (alla dessa grenar, avdelningar och arbetsgrupper), och katalogen över varor och arbetsområden, och geografin för försäljningsställen,...
Det finns faktiskt ingen , där det inte skulle bli någon hierarki som ett resultat. Men även om du inte arbetar "för företaget" kan du fortfarande lätt stöta på hierarkiska relationer. Det är banalt, till och med ditt släktträd eller planlösning för lokaler i ett köpcentrum har samma struktur.
Det finns många sätt att lagra ett sådant träd i en DBMS, men idag kommer vi att fokusera på endast ett alternativ:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Och medan du kikar in i hierarkins djup, väntar den tålmodigt på att se hur [in]effektiva dina "naiva" sätt att arbeta med en sådan struktur kommer att vara.
Låt oss titta på typiska problem som uppstår, deras implementering i SQL, och försöka förbättra deras prestanda.
#1. Hur djupt är kaninhålet?
Låt oss för tydlighetens skull acceptera att denna struktur kommer att återspegla avdelningarnas underordning i organisationens struktur: avdelningar, avdelningar, sektorer, grenar, arbetsgrupper... - vad du än kallar dem.
Låt oss först skapa vårt "träd" med 10K element
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;Låt oss börja med den enklaste uppgiften - att hitta alla anställda som arbetar inom en specifik sektor, eller i termer av hierarki - hitta alla barn till en nod. Det vore också trevligt att få "djupet" i ättlingen... Allt detta kan behövas för att till exempel bygga någon form av .
Allt skulle vara bra om det bara finns ett par nivåer av dessa ättlingar och antalet är inom ett dussin, men om det finns fler än 5 nivåer och det redan finns dussintals ättlingar kan det uppstå problem. Låt oss titta på hur traditionella sökalternativ skrivs (och fungerar). Men först, låt oss avgöra vilka noder som kommer att vara mest intressanta för vår forskning.
Mest "djup" underträd:
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}
...Mest "bred" underträd:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
För dessa frågor använde vi den typiska rekursiv JOIN:
Uppenbarligen, med denna begäran modell antalet iterationer kommer att matcha det totala antalet avkomlingar (och det finns flera dussin av dem), och detta kan ta ganska betydande resurser och, som ett resultat, tid.
Låt oss kolla på det "bredaste" underträdet:
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;
Som väntat hittade vi alla 30 skivorna. Men de spenderade 60 % av den totala tiden på detta – eftersom de också gjorde 30 sökningar i indexet. Är det möjligt att göra mindre?
Masskorrekturläsning efter index
Behöver vi göra en separat indexfråga för varje nod? Det visar sig att nej - vi kan läsa från indexet använda flera knappar samtidigt i ett samtal via = ANY(array).
Och i varje sådan grupp av identifierare kan vi ta alla ID:n som hittades i föregående steg med "noder". Det vill säga, vid varje nästa steg kommer vi att göra det söka efter alla ättlingar på en viss nivå samtidigt.
Bara här är problemet, i rekursivt urval kan du inte komma åt sig själv i en kapslad fråga, men vi behöver på något sätt bara välja det som hittades på föregående nivå... Det visar sig att det är omöjligt att göra en kapslad fråga för hela urvalet, men för dess specifika fält är det möjligt. Och det här fältet kan också vara en array - vilket är vad vi behöver använda ANY.
Det låter lite galet, men i diagrammet är allt enkelt.
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;
Och här är det viktigaste inte ens vinna 1.5 gånger i tid, och att vi subtraherade färre buffertar, eftersom vi bara har 5 anrop till index istället för 30!
En ytterligare bonus är det faktum att efter den sista olyckan kommer identifierarna att förbli sorterade efter "nivåer".
Nod tecken
Nästa övervägande som kommer att bidra till att förbättra prestandan är − "löv" kan inte få barn, det vill säga för dem finns det inget behov av att titta "nedåt" alls. I utformningen av vårt uppdrag innebär det att om vi följt avdelningskedjan och nått en anställd så finns det ingen anledning att leta längre längs denna gren.
Låt oss gå in i vårt bord ytterligare boolean-fält, som omedelbart kommer att berätta för oss om just denna post i vårt träd är en "nod" - det vill säga om den överhuvudtaget kan ha ättlingar.
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 мс.Bra! Det visar sig att endast lite mer än 30 % av alla trädelement har ättlingar.
Låt oss nu använda en lite annan mekanik - kopplingar till den rekursiva delen genom LATERAL, vilket gör det möjligt för oss att omedelbart komma åt fälten i den rekursiva "tabellen", och använda en aggregerad funktion med ett filtreringsvillkor baserat på en nod för att minska uppsättningen nycklar:
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;
Vi kunde minska ytterligare ett indexsamtal och vunnit mer än 2 gånger i volym korrekturläst.
#2. Låt oss gå tillbaka till rötterna
Denna algoritm kommer att vara användbar om du behöver samla in poster för alla element "upp i trädet", samtidigt som du behåller information om vilket källblad (och med vilka indikatorer) som gjorde att det inkluderades i provet - till exempel för att generera en sammanfattande rapport med aggregering till noder.
Det som följer ska endast ses som ett proof-of-concept, eftersom begäran visar sig vara mycket krånglig. Men om det dominerar din databas bör du tänka på att använda liknande tekniker.
Låt oss börja med ett par enkla påståenden:
- Samma post från databasen Det är bäst att läsa den bara en gång.
- Uppgifter från databasen Det är mer effektivt att läsa i omgångarän ensam.
Låt oss nu försöka konstruera den begäran vi behöver.
Steg 1
Uppenbarligen, när vi initierar rekursion (var skulle vi vara utan den!) måste vi subtrahera posterna för själva bladen baserat på uppsättningen av initiala identifierare:
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
...
Om det verkade konstigt för någon att "uppsättningen" lagras som en sträng och inte en array, så finns det en enkel förklaring till detta. Det finns en inbyggd aggregerande "limnings"-funktion för strängar string_agg, men inte för arrayer. Fast hon .
Steg 2
Nu skulle vi få en uppsättning sektions-ID:n som kommer att behöva läsas vidare. Nästan alltid kommer de att dupliceras i olika skivor av originaluppsättningen - så vi skulle gruppera dem, samtidigt som information om källbladen bevaras.
Men här väntar oss tre problem:
- Den "subrekursiva" delen av frågan kan inte innehålla aggregerade funktioner med
GROUP BY. - En referens till en rekursiv "tabell" kan inte finnas i en kapslad underfråga.
- En begäran i den rekursiva delen kan inte innehålla en CTE.
Lyckligtvis är alla dessa problem ganska lätta att komma runt. Låt oss börja från slutet.
CTE i rekursiv del
Här så ingen Arbetar:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Och så fungerar det, parenteserna gör skillnaden!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Kapslad fråga mot en rekursiv "tabell"
Hmm... En rekursiv CTE kan inte nås i en underfråga. Men det kan vara inne i CTE! Och en kapslad begäran kan redan komma åt denna CTE!
GROUP BY inre rekursion
Det är obehagligt, men... Vi har ett enkelt sätt att efterlikna GROUP BY att använda DISTINCT ON och fönsterfunktioner!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Och så här fungerar det!
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 ser vi varför det numeriska ID:t förvandlades till text - så att de kunde sammanfogas åtskilda av kommatecken!
Steg 3
Till finalen har vi ingenting kvar:
- vi läser "sektions"-poster baserat på en uppsättning grupperade ID:n
- vi jämför de subtraherade sektionerna med "uppsättningarna" av originalarken
- "expandera" set-strängen med
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;
Källa: will.com