🥇PostgreSQL հակապատկերներ. Որքա՞ն խորն է նապաստակի անցքը: անցնենք հիերարխիայի միջով

Բարդ ERP համակարգերում շատ սուբյեկտներ ունեն հիերարխիկ բնույթերբ միատարր առարկաները շարվում են իրար մեջ նախնի-հետնորդ հարաբերությունների ծառ - սա ձեռնարկության կազմակերպչական կառուցվածքն է (այս բոլոր մասնաճյուղերը, ստորաբաժանումները և աշխատանքային խմբերը), և ապրանքների կատալոգը և աշխատանքի ոլորտները, և վաճառքի կետերի աշխարհագրությունը,...

Փաստորեն, չկա բիզնեսի ավտոմատացման տարածքներ, որտեղ արդյունքում որևէ հիերարխիա չէր լինի։ Բայց նույնիսկ եթե դուք չեք աշխատում «բիզնեսի համար», դուք դեռ հեշտությամբ կարող եք հանդիպել հիերարխիկ հարաբերությունների: Դա սովորական է, նույնիսկ ձեր տոհմածառը կամ առևտրի կենտրոնում գտնվող տարածքների հատակագիծը նույն կառուցվածքն է:

Նման ծառը DBMS-ում պահելու բազմաթիվ եղանակներ կան, բայց այսօր մենք կկենտրոնանանք միայն մեկ տարբերակի վրա.

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

Եվ մինչ դուք նայում եք հիերարխիայի խորքերը, նա համբերատար սպասում է, թե որքան [անարդյունավետ] կլինեն նման կառույցի հետ աշխատելու ձեր «միամիտ» ձևերը:

Եկեք նայենք առաջացող բնորոշ խնդիրներին, դրանց ներդրմանը SQL-ում և փորձենք բարելավել դրանց կատարումը։

#1. Որքա՞ն խորն է նապաստակի անցքը:

Հաստատության համար եկեք ընդունենք, որ այս կառույցը կազմակերպության կառուցվածքում արտացոլելու է ստորաբաժանումների ստորաբաժանումները՝ բաժիններ, բաժիններ, ոլորտներ, մասնաճյուղեր, աշխատանքային խմբեր... - ինչպես էլ կոչեք:

Նախ, եկեք ստեղծենք մեր «ծառը» 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;

Սկսենք ամենապարզ առաջադրանքից՝ գտնել բոլոր աշխատակիցներին, ովքեր աշխատում են կոնկրետ հատվածում, կամ հիերարխիայի առումով. գտնել հանգույցի բոլոր երեխաներին. Հաճելի կլինի նաև ստանալ հետնորդի «խորությունը»... Այս ամենը կարող է անհրաժեշտ լինել, օրինակ, ինչ-որ տեսակի կառուցելու համար. համալիր ընտրություն՝ հիմնված այդ աշխատողների անձը հաստատող փաստաթղթերի ցանկի վրա.

Ամեն ինչ լավ կլինի, եթե այդ սերունդների ընդամենը մի քանի մակարդակ լինի, և թիվը լինի մեկ տասնյակի սահմաններում, բայց եթե լինեն 5-ից ավելի մակարդակներ, և արդեն կան տասնյակ ժառանգներ, կարող են խնդիրներ լինել: Եկեք նայենք, թե ինչպես են գրված (և աշխատում) ավանդական որոնման տարբերակները: Բայց նախ որոշենք, թե որ հանգույցներն են ամենահետաքրքիրը մեր հետազոտության համար:

Առավելագույնը «խորը» ենթածառեր:

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}
...

Առավելագույնը "լայն" ենթածառեր:

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

Այս հարցումների համար մենք օգտագործեցինք բնորոշը ռեկուրսիվ JOIN:

Ակնհայտ է, որ այս խնդրանքի մոդելով կրկնությունների թիվը կհամապատասխանի ժառանգների ընդհանուր թվին (և դրանցից մի քանի տասնյակ կա), և դա կարող է խլել բավականին զգալի ռեսուրսներ և, որպես հետևանք, ժամանակ:

Եկեք ստուգենք «ամենալայն» ենթածառը.

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;

[նայեք բացատրություն.tensor.ru-ին]

Ինչպես և սպասվում էր, մենք գտանք բոլոր 30 ձայնագրությունները: Բայց նրանք դրա վրա ծախսեցին ընդհանուր ժամանակի 60%-ը, քանի որ նրանք նաև 30 որոնումներ կատարեցին ինդեքսում: Հնարավո՞ր է ավելի քիչ անել:

Զանգվածային սրբագրում ըստ ինդեքսների

Արդյո՞ք մենք պետք է առանձին ինդեքսային հարցում կատարենք յուրաքանչյուր հանգույցի համար: Ստացվում է, որ ոչ, մենք կարող ենք կարդալ ինդեքսից օգտագործելով մի քանի ստեղներ միանգամից մեկ զանգի ընթացքում միջոցով = ANY(array).

Եվ նույնացուցիչների յուրաքանչյուր նման խմբում մենք կարող ենք նախորդ քայլում հայտնաբերված բոլոր ID-ները վերցնել «հանգույցներով»: Այսինքն՝ յուրաքանչյուր հաջորդ քայլին մենք կանենք որոնել որոշակի մակարդակի բոլոր ժառանգներին միանգամից.

Միայն թե այստեղ է խնդիրը, ռեկուրսիվ ընտրության դեպքում դուք չեք կարող մուտք գործել ինքն իրեն տեղադրված հարցումով, բայց մենք պետք է ինչ-որ կերպ ընտրենք միայն այն, ինչ գտնվել է նախորդ մակարդակում... Ստացվում է, որ ամբողջ ընտրության համար անհնար է կատարել nested հարցում, բայց դրա կոնկրետ դաշտի համար դա հնարավոր է։ Եվ այս դաշտը կարող է լինել նաև զանգված, որը մենք պետք է օգտագործենք ANY.

Մի փոքր խենթ է թվում, բայց գծապատկերում ամեն ինչ պարզ է։

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;

[նայեք բացատրություն.tensor.ru-ին]

Եվ այստեղ ամենակարեւորը նույնիսկ չէ ժամանակին հաղթել 1.5 անգամ, և որ մենք ավելի քիչ բուֆերներ ենք հանել, քանի որ 5-ի փոխարեն ունենք ընդամենը 30 զանգ դեպի ինդեքս:

Լրացուցիչ բոնուս է այն փաստը, որ վերջնական ապամոնտաժումից հետո նույնացուցիչները կմնան դասավորված ըստ «մակարդակների»:

Հանգույցի նշան

Հաջորդ նկատառումը, որը կօգնի բարելավել կատարողականը, − է «տերեւները» չեն կարող երեխա ունենալ, այսինքն՝ նրանց համար ամենևին պետք չէ «ներքև» նայել։ Մեր առաջադրանքի ձևակերպման մեջ սա նշանակում է, որ եթե մենք հետևել ենք գերատեսչությունների շղթային և հասել ենք աշխատողի, ապա այս ճյուղով ավելի հեռուն նայելու կարիք չկա։

Եկեք մտնենք մեր սեղանը լրացուցիչ boolean- դաշտ, որն անմիջապես մեզ կասի՝ արդյոք մեր ծառի այս կոնկրետ մուտքը «հանգույց» է, այսինքն՝ արդյոք այն ընդհանրապես կարող է ունենալ ժառանգներ։

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 мс.

Հիանալի Պարզվում է, որ բոլոր ծառերի տարրերի միայն 30%-ից մի փոքր ավելին ունի ժառանգներ:

Այժմ եկեք օգտագործենք մի փոքր այլ մեխանիկ՝ միացումներ ռեկուրսիվ մասի միջոցով LATERAL, որը մեզ թույլ կտա անմիջապես մուտք գործել ռեկուրսիվ «աղյուսակի» դաշտեր և օգտագործել ագրեգատ ֆունկցիա՝ ֆիլտրման պայմանով, որը հիմնված է հանգույցի վրա՝ ստեղների հավաքածուն կրճատելու համար.

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;

[նայեք բացատրություն.tensor.ru-ին]

Մենք կարողացանք կրճատել ևս մեկ ինդեքսային զանգ և հաղթեց ավելի քան 2 անգամ ծավալով սրբագրել.

#2. Վերադառնանք արմատներին

Այս ալգորիթմը օգտակար կլինի, եթե դուք պետք է հավաքեք գրառումներ բոլոր տարրերի համար «վերև ծառի վրա»՝ միաժամանակ պահպանելով տեղեկատվություն այն մասին, թե որ աղբյուրի թերթիկը (և ինչ ցուցանիշներով) հանգեցրել է այն ներառված նմուշի մեջ, օրինակ՝ ամփոփ հաշվետվություն ստեղծելու համար։ հանգույցների մեջ ագրեգացիայի հետ:

Հետևյալը պետք է ընդունվի բացառապես որպես հայեցակարգի ապացույց, քանի որ խնդրանքը պարզվում է, որ շատ ծանր է: Բայց եթե այն գերակշռում է ձեր տվյալների բազայում, դուք պետք է մտածեք նմանատիպ տեխնիկայի օգտագործման մասին:

Սկսենք մի քանի պարզ պնդումներից.

Նույն գրառումը տվյալների բազայից Ավելի լավ է կարդալ այն ընդամենը մեկ անգամ.
Գրառումներ տվյալների բազայից Ավելի արդյունավետ է խմբաքանակով կարդալըքան միայնակ:

Հիմա եկեք փորձենք կառուցել մեզ անհրաժեշտ հարցումը:

Քայլ 1

Ակնհայտ է, որ ռեկուրսիան սկզբնավորելիս (որտե՞ղ կլինեինք մենք առանց դրա) մենք ստիպված կլինենք հանել տերևների գրառումները՝ հիմնվելով սկզբնական նույնացուցիչների բազմության վրա.

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
  ...

Եթե ինչ-որ մեկին տարօրինակ թվաց, որ «կոմպլեկտը» պահվում է որպես տող, այլ ոչ թե զանգված, ապա սա պարզ բացատրություն ունի: Կա ներկառուցված ագրեգացիոն «սոսնձման» ֆունկցիա լարերի համար string_agg, բայց ոչ զանգվածների համար։ Չնայած նա հեշտ է իրականացնել ինքնուրույն.

Քայլ 2

Այժմ մենք կստանանք մի շարք բաժինների ID-ներ, որոնք պետք է շարունակեն կարդալ: Գրեթե միշտ դրանք կկրկնօրինակվեն սկզբնական հավաքածուի տարբեր ձայնագրություններում, այնպես որ մենք կանեինք խմբավորել դրանք, պահպանելով սկզբնաղբյուրի մասին տեղեկությունները։

Բայց այստեղ մեզ երեք դժվարություններ են սպասում.

Հարցման «ենթակուրսիվ» մասը չի կարող պարունակել ագրեգատ գործառույթներ GROUP BY.
Ռեկուրսիվ «աղյուսակի» հղումը չի կարող լինել ներդիր ենթահարցման մեջ:
Ռեկուրսիվ մասի հարցումը չի կարող պարունակել CTE:

Բարեբախտաբար, այս բոլոր խնդիրները բավականին հեշտ է լուծել: Սկսենք վերջից։

CTE ռեկուրսիվ մասում

Ահա այստեղ ոչ աշխատանքները:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

Եվ այսպես, այն աշխատում է, փակագծերը տարբերությունն են դարձնում:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

Ներդրված հարցում ռեկուրսիվ «աղյուսակի» նկատմամբ

Հմմ... Ռեկուրսիվ CTE-ին չեն կարող մուտք գործել ենթահարցում: Բայց դա կարող է լինել CTE-ի ներսում: Եվ ներդիր հարցումն արդեն կարող է մուտք գործել այս CTE:

GROUP BY ներքին ռեկուրսիա

Տհաճ է, բայց... Մենք ունենք GROUP BY-ի նմանակման պարզ միջոց DISTINCT ON և պատուհանի գործառույթները:

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

Եվ ահա թե ինչպես է այն աշխատում։

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

Այժմ մենք տեսնում ենք, թե ինչու է թվային ID-ն վերածվել տեքստի, որպեսզի դրանք իրար միացվեն՝ բաժանված ստորակետերով:

Քայլ 3

Եզրափակչի համար մեզ ոչինչ չի մնում.

մենք կարդում ենք «բաժնի» գրառումները՝ հիմնված մի շարք խմբավորված ID-ների վրա
մենք համեմատում ենք հանված հատվածները սկզբնական թերթերի «կոմպլեկտների» հետ
«ընդլայնել» set-string-ը՝ օգտագործելով 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;

[նայեք բացատրություն.tensor.ru-ին]

Source: www.habr.com

PostgreSQL հակապատկերներ. որքան խորն է նապաստակի անցքը: եկեք անցնենք հիերարխիայի միջով

#1. Որքա՞ն խորն է նապաստակի անցքը:

Զանգվածային սրբագրում ըստ ինդեքսների

Հանգույցի նշան

#2. Վերադառնանք արմատներին

Քայլ 1

Քայլ 2

CTE ռեկուրսիվ մասում

Ներդրված հարցում ռեկուրսիվ «աղյուսակի» նկատմամբ

GROUP BY ներքին ռեկուրսիա

Քայլ 3

Добавить комментарий Չեղարկել պատասխանել