Mewn systemau ERP cymhleth mae gan lawer o endidau natur hierarchaiddpan fydd gwrthrychau homogenaidd yn cyd-fynd coeden o berthynas hynafiad-disgynnydd - dyma strwythur trefniadol y fenter (yr holl ganghennau, adrannau a grwpiau gwaith hyn), a'r catalog nwyddau, a meysydd gwaith, a daearyddiaeth y pwyntiau gwerthu, ...
Mewn gwirionedd, nid oes dim , lle na fyddai unrhyw hierarchaeth o ganlyniad. Ond hyd yn oed os nad ydych chi'n gweithio “i'r busnes,” gallwch chi ddod ar draws perthnasoedd hierarchaidd yn hawdd o hyd. Mae'n wirion, mae hyd yn oed eich coeden deulu neu gynllun llawr o eiddo mewn canolfan siopa yr un strwythur.
Mae yna lawer o ffyrdd i storio coeden o'r fath mewn DBMS, ond heddiw byddwn yn canolbwyntio ar un opsiwn yn unig:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
A thra’ch bod chi’n edrych ar ddyfnderoedd yr hierarchaeth, mae’n aros yn amyneddgar i weld pa mor [mewn]effeithiol fydd eich ffyrdd “naïf” o weithio gyda strwythur o’r fath.
Gadewch i ni edrych ar broblemau nodweddiadol sy'n codi, eu gweithrediad yn SQL, a cheisio gwella eu perfformiad.
#1. Pa mor ddwfn yw'r twll cwningen?
Gadewch inni, i fod yn bendant, dderbyn y bydd y strwythur hwn yn adlewyrchu is-drefniant adrannau yn strwythur y sefydliad: adrannau, isadrannau, sectorau, canghennau, gweithgorau... - beth bynnag yr ydych yn eu galw.
Yn gyntaf, gadewch i ni gynhyrchu ein 'coeden' o elfennau 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;Gadewch i ni ddechrau gyda'r dasg symlaf - dod o hyd i'r holl weithwyr sy'n gweithio o fewn sector penodol, neu o ran hierarchaeth - dod o hyd i bob plentyn o nod. Byddai hefyd yn braf cael “dyfnder” y disgynnydd... Efallai y bydd hyn i gyd yn angenrheidiol, er enghraifft, i adeiladu rhyw fath o .
Byddai popeth yn iawn os mai dim ond cwpl o lefelau o'r disgynyddion hyn a bod y nifer o fewn dwsin, ond os oes mwy na 5 lefel, a bod dwsinau o ddisgynyddion eisoes, efallai y bydd problemau. Gadewch i ni edrych ar sut mae opsiynau chwilio i lawr coed traddodiadol yn cael eu hysgrifennu (a gweithio). Ond yn gyntaf, gadewch i ni benderfynu pa nodau fydd y rhai mwyaf diddorol ar gyfer ein hymchwil.
Y rhan fwyaf "dwfn" is-goed:
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}
...Y rhan fwyaf "llydan" is-goed:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Ar gyfer yr ymholiadau hyn, defnyddiwyd yr un nodweddiadol YMUNWCH ailadroddus:
Yn amlwg, gyda'r model cais hwn bydd nifer yr iteriadau yn cyfateb i gyfanswm y disgynyddion (ac mae yna sawl dwsin ohonyn nhw), a gall hyn gymryd adnoddau eithaf sylweddol, ac, o ganlyniad, amser.
Gadewch i ni wirio ar yr is-goeden “ehangaf”:
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;
Yn ôl y disgwyl, daethom o hyd i bob un o'r 30 cofnod. Ond fe dreulion nhw 60% o'r holl amser ar hyn - oherwydd fe wnaethon nhw hefyd 30 chwiliad yn y mynegai. A yw'n bosibl gwneud llai?
Prawfddarllen swmp yn ôl mynegai
A oes angen i ni wneud ymholiad mynegai ar wahân ar gyfer pob nod? Mae'n troi allan nad oes - gallwn ddarllen o'r mynegai defnyddio sawl allwedd ar unwaith mewn un alwad gyda help = ANY(array).
Ac ym mhob grŵp o'r fath o ddynodwyr gallwn gymryd yr holl IDs a ddarganfuwyd yn y cam blaenorol gan “nodau”. Hynny yw, ym mhob cam nesaf y byddwn chwiliwch am yr holl ddisgynyddion o lefel benodol ar unwaith.
Dim ond, dyma'r broblem, mewn dewis ailadroddus, ni allwch gael mynediad iddo'i hun mewn ymholiad nythu, ond mae angen i ni rywsut ddewis dim ond yr hyn a ddarganfuwyd ar y lefel flaenorol ... Mae'n troi allan ei bod yn amhosibl gwneud ymholiad nythu ar gyfer y detholiad cyfan, ond ar gyfer ei faes penodol mae'n bosibl. A gall y maes hwn hefyd fod yn arae - sef yr hyn y mae angen i ni ei ddefnyddio ANY.
Mae'n swnio ychydig yn wallgof, ond yn y diagram mae popeth yn syml.
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;
Ac yma nid yw'r peth pwysicaf yn gyfartal ennill 1.5 gwaith mewn amser, a'n bod wedi tynnu llai o glustogau, gan mai dim ond 5 galwad sydd gennym i'r mynegai yn lle 30!
Bonws ychwanegol yw'r ffaith y bydd y dynodwyr yn parhau i gael eu harchebu yn ôl “lefelau” ar ôl yr anghydfod terfynol.
Arwydd nod
Yr ystyriaeth nesaf a fydd yn helpu i wella perfformiad yw − ni all "dail" gael plant, hynny yw, ar eu cyfer nid oes angen edrych “i lawr” o gwbl. Wrth lunio ein tasg, mae hyn yn golygu pe baem yn dilyn y gadwyn o adrannau ac yn cyrraedd gweithiwr, yna nid oes angen edrych ymhellach ar hyd y gangen hon.
Gadewch i ni fynd i mewn i'n bwrdd ychwanegol boolean-maes, a fydd yn dweud wrthym ar unwaith a yw'r cofnod penodol hwn yn ein coeden yn “nod” - hynny yw, a all gael disgynyddion o gwbl.
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 мс.Gwych! Mae'n ymddangos mai dim ond ychydig yn fwy na 30% o'r holl elfennau coed sydd â disgynyddion.
Nawr, gadewch i ni ddefnyddio mecanic ychydig yn wahanol - cysylltiadau â'r rhan ailadroddus drwodd LATERAL, a fydd yn caniatáu inni gael mynediad ar unwaith i feysydd y “bwrdd” ailadroddus, a defnyddio swyddogaeth agregau gyda chyflwr hidlo yn seiliedig ar nod i leihau'r set o allweddi:
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;
Roeddem yn gallu lleihau un galwad mynegai arall a ennill mwy na 2 gwaith mewn cyfaint prawf ddarllen.
#2. Gadewch i ni fynd yn ôl at y gwreiddiau
Bydd yr algorithm hwn yn ddefnyddiol os oes angen i chi gasglu cofnodion ar gyfer yr holl elfennau “i fyny'r goeden”, tra'n cadw gwybodaeth am ba ddalen ffynhonnell (a pha ddangosyddion) a achosodd iddo gael ei gynnwys yn y sampl - er enghraifft, i gynhyrchu adroddiad cryno ag agregu yn nodau.
Dylid cymryd yr hyn sy'n dilyn fel prawf o gysyniad yn unig, gan fod y cais yn troi allan i fod yn feichus iawn. Ond os yw'n dominyddu eich cronfa ddata, dylech feddwl am ddefnyddio technegau tebyg.
Gadewch i ni ddechrau gyda rhai datganiadau syml:
- Yr un cofnod o'r gronfa ddata Mae'n well ei ddarllen unwaith yn unig.
- Cofnodion o'r gronfa ddata Mae'n fwy effeithlon darllen mewn sypiaunag yn unig.
Nawr, gadewch i ni geisio llunio'r cais sydd ei angen arnom.
Cam 1
Yn amlwg, wrth gychwyn dychweliad (ble fyddem hebddo!) bydd yn rhaid i ni dynnu cofnodion y dail eu hunain yn seiliedig ar y set o ddynodwyr cychwynnol:
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
...
Os oedd rhywun yn meddwl ei bod yn rhyfedd bod y “set” wedi'i storio fel llinyn ac nid arae, yna mae esboniad syml am hyn. Mae swyddogaeth “gludo” agregu adeiledig ar gyfer llinynnau string_agg, ond nid ar gyfer araeau. Er bod hi .
Cam 2
Nawr byddem yn cael set o IDau adran y bydd angen eu darllen ymhellach. Bron bob amser byddant yn cael eu dyblygu mewn cofnodion gwahanol o'r set wreiddiol - felly byddem eu grwpio, tra'n cadw gwybodaeth am y dail ffynhonnell.
Ond dyma dair helynt yn ein disgwyl:
- Ni all y rhan "subcursive" o'r ymholiad gynnwys ffwythiannau cyfanredol gyda
GROUP BY. - Ni all cyfeiriad at “bwrdd” ailadroddus fod mewn subquery nythu.
- Ni all cais yn y rhan ailadroddol gynnwys CTE.
Yn ffodus, mae'r holl broblemau hyn yn eithaf hawdd i'w datrys. Gadewch i ni ddechrau o'r diwedd.
CTE yn rhan ailadroddus
Yma felly dim yn gweithio:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Ac felly mae'n gweithio, mae'r cromfachau'n gwneud gwahaniaeth!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ymholiad wedi'i nythu yn erbyn "bwrdd" ailadroddus
Hmm... Ni ellir cyrchu CTE ailadroddus mewn subquery. Ond gallai fod y tu mewn i CTE! A gall cais nythu eisoes gael mynediad at y CTE hwn!
GRŴP GAN recursion tu mewn
Mae'n annymunol, ond... Mae gennym ni ffordd syml o efelychu GRWP TRWY ddefnyddio DISTINCT ON a swyddogaethau ffenestr!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!A dyma sut mae'n gweithio!
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 NULLNawr fe welwn pam y cafodd yr ID rhifol ei droi'n destun - fel y gellid eu cysylltu â'i gilydd gan atalnodau!
Cam 3
Ar gyfer y rownd derfynol nid oes gennym unrhyw beth ar ôl:
- darllenasom gofnodion “adran” yn seiliedig ar set o IDau wedi'u grwpio
- rydym yn cymharu'r adrannau a dynnwyd â “setiau” y dalennau gwreiddiol
- “ehangu” y llinyn set gan ddefnyddio
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;
Ffynhonnell: hab.com