Ann an siostaman ERP iom-fhillte tha nàdar rangachd aig mòran bhuidhneannuair a thig nithean aon-ghnèitheach a-steach craobh nan dàimhean sinnsear-sliochd - is e seo structar eagrachaidh na h-iomairt (na meuran sin, na roinnean agus na buidhnean obrach sin), agus an catalog bathair, agus raointean obrach, agus cruinn-eòlas puingean reic, ...
Gu dearbh, chan eil gin ann , far nach biodh rangachd sam bith mar thoradh air. Ach eadhon mura h-eil thu ag obair “airson a’ ghnìomhachas, ”faodaidh tu fhathast coinneachadh gu furasta ri dàimhean rangachd. Tha e trite, eadhon do chraobh teaghlaich no plana làir togalach ann an ionad bhùthan den aon structar.
Tha iomadh dòigh ann airson a leithid de chraobh a stòradh ann an DBMS, ach an-diugh cuiridh sinn fòcas air aon roghainn:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Agus fhad ‘s a tha thu a’ coimhead a-steach do dhoimhneachd na rangachd, tha e gu foighidneach a’ feitheamh gus faicinn dè cho èifeachdach sa bhios na dòighean “naive” agad air a bhith ag obair le structar mar sin.
Bheir sinn sùil air duilgheadasan àbhaisteach a thig am bàrr, am buileachadh ann an SQL, agus feuchaidh sinn ris an coileanadh aca a leasachadh.
#1. Dè cho domhainn 'sa tha an toll coineanach?
Gabhaidh sinn, gu deimhinnte, gum bi an structar seo a’ nochdadh fo-òrdanachadh roinnean ann an structar na buidhne: roinnean, roinnean, roinnean, meuran, buidhnean obrach ... - ge bith dè a chanas tu riutha.
An toiseach, cruthaichidh sinn ar 'craobh' de eileamaidean 10K
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;Feuch an tòisich sinn leis a’ ghnìomh as sìmplidh - a’ lorg gach neach-obrach a tha ag obair taobh a-staigh roinn shònraichte, no a thaobh rangachd - lorg a h-uile leanabh de nod. Bhiodh e math cuideachd “doimhneachd” an t-sliochd fhaighinn... Is dòcha gum bi seo uile riatanach, mar eisimpleir, airson seòrsa de sheòrsa a thogail. .
Bhiodh a h-uile dad gu math mura h-eil ach ìre no dhà den t-sliochd sin ann agus gu bheil an àireamh taobh a-staigh dusan, ach ma tha barrachd air ìrean 5 ann, agus gu bheil dusanan de shliochd ann mu thràth, dh’ fhaodadh gum bi duilgheadasan ann. Bheir sinn sùil air mar a tha roghainnean luirg traidiseanta sìos-chraobhan air an sgrìobhadh (agus ag obair). Ach an toiseach, leig dhuinn a-mach dè na nodan a bhios as inntinniche don rannsachadh againn.
A ’mhòr-chuid "domhainn" fo-chraobhan:
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}
...A ’mhòr-chuid "leathann" fo-chraobhan:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Airson na ceistean sin chleachd sinn an àbhaist JOIN ath-chuairteach:
Gu follaiseach, leis a 'mhodail iarrtas seo bidh an àireamh de thursan a rèir àireamh iomlan an t-sliochd (agus tha grunn dhusan dhiubh ann), agus faodaidh seo goireasan fìor chudromach a ghabhail, agus, mar thoradh air sin, ùine.
Bheir sinn sùil air an fho-chraobh “as fharsainge”:
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;
Mar a bhiodh dùil, lorg sinn a h-uile clàr 30. Ach chuir iad seachad 60% den ùine iomlan air seo - oir rinn iad cuideachd 30 rannsachadh anns a' chlàr-amais. A bheil e comasach nas lugha a dhèanamh?
Leughadh dearbhaidh mòr a rèir clàr-amais
Am feum sinn ceist clàr-amais fa leth a dhèanamh airson gach nód? Tha e a 'tionndadh a-mach nach eil - faodaidh sinn a leughadh bhon chlàr-amais a’ cleachdadh grunn iuchraichean aig an aon àm ann an aon ghairm le cuideachadh = ANY(array).
Agus anns gach buidheann de dh’ aithnichearan mar sin is urrainn dhuinn a h-uile ID a lorgadh sa cheum roimhe a thoirt le “nodan”. Is e sin, aig gach ath cheum nì sinn lorg a h-uile sliochd aig ìre sònraichte aig an aon àm.
A-mhàin, seo an duilgheadas, ann an taghadh ath-chuairteach, chan urrainn dhut faighinn thuige ann an ceist neadachaidh, ach feumaidh sinn dòigh air choireigin a thaghadh a-mhàin na chaidh a lorg aig an ìre roimhe... Tha e a’ tionndadh a-mach gu bheil e do-dhèanta ceist neadachaidh a dhèanamh airson an taghadh gu lèir, ach airson an raon sònraichte aige tha e comasach. Agus faodaidh an raon seo a bhith na raon cuideachd - is e sin a dh'fheumas sinn a chleachdadh ANY.
Tha e beagan craicte, ach anns an diagram tha a h-uile dad sìmplidh.
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;
Agus an seo chan eil an rud as cudromaiche eadhon buannachadh 1.5 uair ann an ùine, agus gun tug sinn air falbh nas lugha de bhufairean, leis nach eil againn ach 5 fiosan chun chlàr-amais an àite 30!
Is e buannachd a bharrachd an fhìrinn, às deidh an aimhreit mu dheireadh, gum fuirich na h-aithnichearan air an òrdachadh le “ìrean”.
Soidhne nod
Is e an ath bheachdachadh a chuidicheas le coileanadh a leasachadh - - Chan urrainn dha "fàgail" clann a bhith aca, is e sin, dhaibhsan chan eil feum air coimhead “sìos” idir. Ann a bhith a 'cruthachadh ar gnìomh, tha seo a' ciallachadh ma lean sinn an t-sreath de roinnean agus gun ruigeadh sinn neach-obrach, chan fheumar coimhead nas fhaide air adhart air a 'mheur seo.
Rachamaid a-steach don bhòrd againn a bharrachd boolean-achadh, a dh’ innseas dhuinn sa bhad an e “nód” a th’ anns an inntrigeadh shònraichte seo nar craobh - is e sin, am faod sliochd a bhith aice idir.
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 мс.Sgoinneil! Tha e a 'tionndadh a-mach nach eil ach beagan a bharrachd air 30% de na h-eileamaidean craoibhe uile aig a bheil sliochd.
A-nis cleachdamaid meacanaig beagan eadar-dhealaichte - ceanglaichean ris a’ phàirt ath-chuairteach troimhe LATERAL, a leigeas leinn faighinn gu raointean a’ “bhòrd” ath-chuairteach sa bhad, agus gnìomh iomlan a chleachdadh le suidheachadh sìolaidh stèidhichte air nód gus an seata iuchraichean a lughdachadh:
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;
B’ urrainn dhuinn aon ghairm clàr-amais eile a lughdachadh agus bhuannaich barrachd air 2 uair ann an tomhas-lìonaidh leughadh dearbhaidh.
#2. Rachamaid air ais gu na freumhaichean
Bidh an algairim seo feumail ma dh’ fheumas tu clàran a chruinneachadh airson a h-uile eileamaid “suas an craobh”, fhad ‘s a chumas tu fiosrachadh mu dè an duilleag stòr (agus dè na comharran) a dh’ adhbhraich a bhith air a ghabhail a-steach san sampall - mar eisimpleir, gus geàrr-chunntas a chruthachadh le cruinneachadh ann an nodan.
Bu chòir na leanas a ghabhail a-mhàin mar dhearbhadh air bun-bheachd, leis gu bheil an t-iarrtas a’ tionndadh a-mach gu bhith uamhasach duilich. Ach ma tha smachd aige air an stòr-dàta agad, bu chòir dhut smaoineachadh air dòighean coltach ris a chleachdadh.
Feuch an tòisich sinn le dà aithris shìmplidh:
- An aon chlàr bhon stòr-dàta Tha e nas fheàrr a leughadh dìreach aon turas.
- Clàraidhean bhon stòr-dàta Tha e nas èifeachdaiche leughadh ann an baidseanna aonar.
A-nis feuchaidh sinn ris an iarrtas a tha a dhìth oirnn a thogail.
ceum 1
Gu follaiseach, nuair a thòisicheas sinn air ais (càit am biodh sinn às aonais!) feumaidh sinn clàran nan duilleagan fhèin a thoirt air falbh stèidhichte air an t-seata de luchd-aithneachaidh tùsail:
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
...
Ma bha coltas neònach air cuideigin gu bheil an “seata” air a stòradh mar shreang agus chan e sreath, tha mìneachadh sìmplidh ann airson seo. Tha gnìomh “gluing” aonaichte ann airson sreangan string_agg, ach chan ann airson arrays. Ged a tha i .
ceum 2
A-nis gheibheadh sinn seata de IDan earrannan a dh’ fheumar a leughadh tuilleadh. Cha mhòr an-còmhnaidh bidh iad air an dùblachadh ann an clàran eadar-dhealaichte den t-seata tùsail - mar sin bhiodh sinn buidheann dhiubh, fhad 'sa tha e a' gleidheadh fiosrachadh mu na duilleagan stòr.
Ach seo trì trioblaidean a’ feitheamh oirnn:
- Chan fhaod gnìomhan iomlan le
GROUP BY. - Chan fhaod iomradh air “clàr” ath-chuairteach a bhith ann am fo-cheist neadachaidh.
- Chan fhaod CTE a bhith ann an iarrtas anns a’ phàirt ath-chuairteach.
Gu fortanach, tha na duilgheadasan sin uile gu math furasta obrachadh mun cuairt. Feuch an tòisich sinn bhon deireadh.
CTE ann am pàirt ath-chuairteach
An seo chan eil obraichean:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Agus mar sin bidh e ag obair, bidh na bragan a’ dèanamh an diofar!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ceist neadachaidh mu choinneamh "clàr" ath-chuairteachaidh
Hmm... Chan fhaighear cothrom air CTE ath-chuairteachail ann am fo-iarrtas. Ach dh’ fhaodadh e a bhith taobh a-staigh CTE! Agus faodaidh iarrtas neadachaidh faighinn chun CTE seo mu thràth!
GRÙP A MHÒR taobh a-staigh ath-chuairteachaidh
Tha e mì-chàilear, ach... Tha dòigh shìmplidh againn air GRÙPA ath-aithris LE bhith a’ cleachdadh DISTINCT ON agus gnìomhan uinneig!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Agus seo mar a tha e ag obair!
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 NULLA-nis chì sinn carson a chaidh an ID àireamhach a thionndadh gu teacsa - gus am faodadh iad a bhith air an ceangal le cromagan!
ceum 3
Airson a’ chuairt dheireannaich chan eil dad air fhàgail againn:
- leugh sinn clàran “earrann” stèidhichte air seata de IDan buidhne
- bidh sinn a’ dèanamh coimeas eadar na h-earrannan air an toirt air falbh agus na “seata” de na duilleagan tùsail
- “leudaich” an t-sreath-seata a’ cleachdadh
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;
Source: www.habr.com