Monimutkaisissa ERP-järjestelmissä monet entiteetit ovat luonteeltaan hierarkkisiakun homogeeniset esineet asettuvat riviin esivanhempien ja jälkeläisten suhteiden puu - tämä on yrityksen organisaatiorakenne (kaikki nämä haarat, osastot ja työryhmät) ja tavaraluettelo ja työalueet sekä myyntipisteiden maantiede,...
Itse asiassa sellaista ei ole , jossa ei sen seurauksena olisi hierarkiaa. Mutta vaikka et työskentele "yrityksen hyväksi", voit silti kohdata helposti hierarkkisia suhteita. Se on tylsää, jopa sukupuusi tai kauppakeskuksen tilojen pohjapiirros on sama rakenne.
On monia tapoja tallentaa tällainen puu DBMS:ään, mutta tänään keskitymme vain yhteen vaihtoehtoon:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Ja samalla kun katselet hierarkian syvyyksiä, se odottaa kärsivällisesti nähdäkseen, kuinka [epä]tehokkaita "naiivit" tapasi työskennellä tällaisen rakenteen kanssa ovat.
Katsotaanpa tyypillisiä esiin tulevia ongelmia, niiden toteutusta SQL:ssä ja yritetään parantaa niiden suorituskykyä.
#1. Kuinka syvä kanin reikä on?
Hyväksykäämme varmuuden vuoksi, että tämä rakenne heijastelee organisaation rakenteessa olevien osastojen alisteisuutta: osastot, osastot, sektorit, haarat, työryhmät... - miksi niitä sitten kutsutaankin.
Luodaan ensin 10 XNUMX elementin "puu".
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;Aloitetaan yksinkertaisimmasta tehtävästä - kaikkien tietyllä alalla tai hierarkiassa työskentelevien työntekijöiden löytämisestä - löytää kaikki solmun lapset. Olisi myös kiva saada jälkeläisen "syvyys"... Kaikki tämä voi olla tarpeen esimerkiksi jonkinlaisen .
Kaikki olisi hyvin, jos näitä jälkeläisiä on vain pari tasoa ja lukumäärä on tusinan sisällä, mutta jos tasoja on enemmän kuin 5 ja jälkeläisiä on jo kymmeniä, voi olla ongelmia. Katsotaanpa, kuinka perinteiset alas-puusta hakuvaihtoehdot kirjoitetaan (ja toimivat). Mutta ensin määritetään, mitkä solmut ovat mielenkiintoisimmat tutkimuksellemme.
Eniten "syvä" alipuut:
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}
...Eniten "leveä" alipuut:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Näihin kyselyihin käytimme tyypillistä rekursiivinen JOIN:
Ilmeisesti tällä pyyntömallilla iteraatioiden määrä vastaa jälkeläisten kokonaismäärää (ja niitä on useita kymmeniä), ja tämä voi viedä melko merkittäviä resursseja ja sen seurauksena aikaa.
Tarkastetaan "levein" alipuu:
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;
Kuten odotettiin, löysimme kaikki 30 tietuetta. Mutta he käyttivät 60 % koko ajasta tähän - koska he tekivät myös 30 hakua hakemistosta. Onko mahdollista tehdä vähemmän?
Joukkooikolukeminen hakemiston mukaan
Pitääkö jokaiselle solmulle tehdä erillinen indeksikysely? Osoittautuu, että ei - voimme lukea hakemistosta käyttämällä useita näppäimiä kerralla yhdessä puhelussa kautta = ANY(array).
Ja jokaisessa tällaisessa tunnisteryhmässä voimme ottaa kaikki edellisessä vaiheessa löydetyt tunnukset "solmuittain". Eli jokaisessa seuraavassa vaiheessa teemme etsiä kaikkia tietyn tason jälkeläisiä kerralla.
Vain tässä on ongelma, rekursiivisessa valinnassa et voi käyttää itseään sisäkkäisessä kyselyssä, mutta meidän on jotenkin valittava vain se, mikä löydettiin edelliseltä tasolta... Osoittautuu, että sisäkkäistä kyselyä on mahdotonta tehdä koko valinnalle, mutta sen tietylle kentälle se on mahdollista. Ja tämä kenttä voi olla myös matriisi - mitä meidän on käytettävä ANY.
Se kuulostaa hieman hullulta, mutta kaaviossa kaikki on yksinkertaista.
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;
Ja tässä tärkein asia ei ole tasainen voittaa 1.5 kertaa ajallaan, ja että vähennimme vähemmän puskureita, koska meillä on vain 5 kutsua indeksiin 30:n sijaan!
Lisäbonuksena on se, että tunnisteet pysyvät "tasojen" mukaisessa järjestyksessä viimeisen pesän jälkeen.
Solmumerkki
Seuraava näkökohta, joka auttaa parantamaan suorituskykyä, on − "lehdet" eivät voi saada lapsia, eli heidän ei tarvitse katsoa "alaspäin" ollenkaan. Tehtävämme muotoilussa tämä tarkoittaa sitä, että jos seurasimme osastoketjua ja tavoitimme työntekijän, ei tätä haaraa tarvitse katsoa pidemmälle.
Mennään pöytäämme lisää boolean-kenttä, joka kertoo meille välittömästi, onko tämä tietty merkintä puussamme "solmu" - eli voiko sillä ylipäätään olla jälkeläisiä.
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 мс.Loistava! Osoittautuu, että vain hieman yli 30 prosentilla kaikista puuelementeistä on jälkeläisiä.
Käytetään nyt hieman erilaista mekaniikkaa - yhteydet rekursiiviseen osaan läpi LATERAL, jonka avulla voimme välittömästi käyttää rekursiivisen "taulukon" kenttiä ja käyttää aggregaattifunktiota, jossa on solmuun perustuva suodatusehto avainten määrän vähentämiseksi:
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;
Pystyimme vähentämään vielä yhden indeksipuhelun ja voitti määrällisesti yli 2 kertaa oikoluku.
#2. Palataan juurille
Tämä algoritmi on hyödyllinen, jos sinun on kerättävä tietueita kaikista elementeistä "puussa ylös", säilyttäen samalla tiedot siitä, mikä lähdearkki (ja millä indikaattoreilla) aiheutti sen sisällyttämisen otokseen - esimerkiksi luodaksesi yhteenvetoraportin. solmuiksi yhdistämisen kanssa.
Seuraavaa tulisi pitää vain konseptin todisteena, koska pyyntö osoittautuu erittäin hankalaksi. Mutta jos se hallitsee tietokantaasi, sinun tulee harkita samanlaisten tekniikoiden käyttöä.
Aloitetaan parilla yksinkertaisella lauseella:
- Sama tietue tietokannasta On parasta lukea se vain kerran.
- Tietueita tietokannasta On tehokkaampaa lukea erissäkuin yksin.
Yritetään nyt rakentaa tarvitsemamme pyyntö.
Vaihe 1
Ilmeisesti, kun alustetaan rekursiota (missä olisimme ilman sitä!) meidän on vähennettävä itse lehtien tietueet alkuperäisten tunnisteiden joukon perusteella:
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
...
Jos joku tuntui oudolta, että "joukko" on tallennettu merkkijonona eikä taulukkona, tälle on yksinkertainen selitys. Jousille on sisäänrakennettu yhdistämistoiminto "liimaus". string_agg, mutta ei taulukoille. Vaikka hän .
Vaihe 2
Nyt saisimme joukon osiotunnuksia, jotka on luettava tarkemmin. Melkein aina ne kopioidaan alkuperäisen sarjan eri tietueille - niin tekisimme ryhmittele ne, säilyttäen samalla tiedot lähdelehdistä.
Mutta tässä meitä odottaa kolme ongelmaa:
- Kyselyn "alikurssiivinen" osa ei voi sisältää koostefunktioita
GROUP BY. - Viittaus rekursiiviseen "taulukkoon" ei voi olla sisäkkäisessä alikyselyssä.
- Rekursiivisen osan pyyntö ei voi sisältää CTE:tä.
Onneksi kaikki nämä ongelmat on melko helppo kiertää. Aloitetaan lopusta.
CTE rekursiivisessa osassa
näin ei toimii:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Ja niin se toimii, suluilla on ero!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Sisäkkäinen kysely rekursiivista "taulukkoa" vastaan
Hmm... Rekursiivista CTE:tä ei voi käyttää alikyselyssä. Mutta se voi olla CTE:n sisällä! Ja sisäkkäinen pyyntö voi jo käyttää tätä CTE:tä!
GROUP BY sisäinen rekursio
Se on epämiellyttävää, mutta... Meillä on yksinkertainen tapa jäljitellä GROUP BY:tä käyttämällä DISTINCT ON ja ikkunatoiminnot!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Ja näin se toimii!
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 NULLNyt näemme, miksi numeerinen tunnus muutettiin tekstiksi - jotta ne voitaisiin yhdistää pilkuilla erotettuina!
Vaihe 3
Finaaliin meillä ei ole mitään jäljellä:
- luemme "osio"-tietueita ryhmiteltyjen tunnusten perusteella
- vertaamme vähennettyjä osia alkuperäisten arkkien "sarjoihin".
- "laajenna" asetusmerkkijonoa käyttämällä
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;
Lähde: will.com