🥇Mga Antipattern sa PostgreSQL: Unsa ka lawom ang lungag sa kuneho? moagi ta sa hierarchy

Sa komplikado nga sistema sa ERP daghang entidad adunay hierarchical nga kinaiyakung ang mga homogenous nga mga butang maglinya kahoy sa relasyon sa katigulangan-kaliwat - kini ang istruktura sa organisasyon sa negosyo (tanan kini nga mga sanga, departamento ug mga grupo sa trabaho), ug ang katalogo sa mga butang, ug mga lugar sa trabaho, ug ang geograpiya sa mga punto sa pagpamaligya,...

Sa pagkatinuod, wala negosyo automation nga mga dapit, diin walay bisan unsang hierarchy isip resulta. Apan bisan kung dili ka magtrabaho "alang sa negosyo," dali ka nga makasugat og hierarchical nga mga relasyon. Talagsa ra, bisan ang imong punoan sa pamilya o plano sa salog sa lugar sa usa ka shopping center parehas nga istruktura.

Adunay daghang mga paagi sa pagtipig sa ingon nga kahoy sa usa ka DBMS, apan karon magpunting kami sa usa lamang ka kapilian:

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

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

Ug samtang nagtan-aw ka sa kahiladman sa hierarchy, mapailubon kini nga naghulat aron makita kung unsa ka epektibo ang imong "walay hinungdan" nga mga paagi sa pagtrabaho sa ingon nga istruktura.

Atong tan-awon ang kasagaran nga mga problema nga mitungha, ang ilang pagpatuman sa SQL, ug pagsulay sa pagpalambo sa ilang performance.

#1. Unsa ka lawom ang lungag sa kuneho?

Atong, alang sa katinoan, dawaton nga kini nga istruktura magpakita sa subordination sa mga departamento sa istruktura sa organisasyon: mga departamento, mga dibisyon, mga sektor, mga sanga, mga grupo sa pagtrabaho ... - bisan unsa ang imong tawag kanila.

Una, atong mugnaon ang atong 'kahoy' sa 10K nga mga elemento

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;

Magsugod kita sa pinakasimple nga buluhaton - pagpangita sa tanan nga mga empleyado nga nagtrabaho sulod sa usa ka piho nga sektor, o sa mga termino sa hierarchy - pangitaa ang tanan nga mga anak sa usa ka node. Maayo usab nga makuha ang "kalalim" sa kaliwat... Kining tanan mahimong gikinahanglan, pananglitan, sa pagtukod og usa ka matang sa komplikado nga pagpili base sa listahan sa mga ID niini nga mga empleyado.

Maayo ra ang tanan kung adunay duha ra nga lebel sa kini nga mga kaliwat ug ang gidaghanon naa sa sulod sa usa ka dosena, apan kung adunay labaw pa sa 5 nga lebel, ug adunay daghang mga kaliwat, mahimo’g adunay mga problema. Atong tan-awon kung giunsa gisulat ang tradisyonal nga mga kapilian sa pagpangita sa ubos (ug nagtrabaho). Apan una, atong mahibal-an kung unsang mga node ang labing makapaikag alang sa among panukiduki.

Ang labing "lawom" mga subtree:

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

Ang labing "lapad" mga subtree:

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

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

Alang niini nga mga pangutana among gigamit ang kasagaran recursive API:

Dayag, uban niini nga modelo sa hangyo ang gidaghanon sa mga pag-uli motakdo sa kinatibuk-ang gidaghanon sa mga kaliwat (ug adunay ubay-ubay nga dosena niini), ug kini mahimo’g magkinahanglan labi ka hinungdanon nga mga kapanguhaan, ug, ingon usa ka sangputanan, oras.

Atong susihon ang "labing lapad" nga subtree:

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;

[tan-awa sa explain.tensor.ru]

Sama sa gipaabot, among nakit-an ang tanang 30 ka rekord. Apan gigugol nila ang 60% sa kinatibuk-ang oras niini - tungod kay naghimo usab sila og 30 nga pagpangita sa indeks. Posible ba nga gamay ra ang mahimo?

Bulk proofreading pinaagi sa index

Kinahanglan ba nga maghimo kami usa ka lahi nga pangutana sa indeks alang sa matag node? Kini nahimo nga dili - kita makabasa gikan sa indeks gamit ang daghang mga yawe sa usa ka tawag sa panabang = ANY(array).

Ug sa matag ingon nga grupo sa mga identifier mahimo naton makuha ang tanan nga mga ID nga nakit-an sa miaging lakang pinaagi sa "mga node". Sa ato pa, sa matag sunod nga lakang atong buhaton pangitaa ang tanan nga mga kaliwat sa usa ka lebel sa usa ka higayon.

Lamang, ania ang problema, sa recursive nga pagpili, dili nimo ma-access ang kaugalingon sa usa ka nested nga pangutana, apan kinahanglan natong pilion lamang ang nakit-an sa miaging lebel... Mopatim-aw nga imposible ang paghimo og nested nga pangutana alang sa tibuok nga pagpili, apan posible kini alang sa espesipikong natad niini. Ug kini nga uma mahimo usab nga usa ka laray - nga mao ang kinahanglan naton gamiton ANY.

Kini morag usa ka gamay nga buang, apan sa diagram ang tanan yano ra.

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;

[tan-awa sa explain.tensor.ru]

Ug dinhi ang labing importante nga butang dili gani pagdaog 1.5 ka beses sa oras, ug nga among gikuha ang mas gamay nga buffer, tungod kay kami adunay 5 lang ka tawag sa indeks imbes nga 30!

Ang usa ka dugang nga bonus mao ang kamatuoran nga pagkahuman sa katapusang unnest, ang mga identifier magpabilin nga gimando sa "mga lebel".

Node sign

Ang sunod nga konsiderasyon nga makatabang sa pagpauswag sa performance mao ang − Ang "mga dahon" dili makaanak, nga mao, alang kanila dili na kinahanglan nga motan-aw sa "ubos" sa tanan. Sa pormulasyon sa among buluhaton, kini nagpasabut nga kung nagsunod kami sa kadena sa mga departamento ug nakaabot sa usa ka empleyado, nan dili na kinahanglan nga tan-awon pa sa kini nga sanga.

Sulod ta sa atong lamesa dugang boolean- kapatagan, nga mosulti dayon kanato kung kini nga partikular nga pagsulod sa atong kahoy usa ka "node" - nga mao, kung kini mahimo nga adunay mga kaliwat.

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

Nindot! Mogawas nga gamay ra sa 30% sa tanan nga mga elemento sa kahoy adunay mga kaliwat.

Karon atong gamiton ang usa ka gamay nga lahi nga mekaniko - mga koneksyon sa recursive nga bahin pinaagi sa LATERAL, nga magtugot kanamo nga ma-access dayon ang mga natad sa recursive nga "table", ug mogamit usa ka aggregate function nga adunay kondisyon sa pagsala base sa usa ka node aron makunhuran ang set sa mga yawe:

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;

[tan-awa sa explain.tensor.ru]

Nahimo namon ang pagpakunhod sa usa pa ka tawag sa indeks ug nakadaog labaw pa sa 2 ka beses sa gidaghanon proofread.

#2. Balik ta sa mga ugat

Mapuslanon kini nga algorithm kung kinahanglan nimo nga mangolekta mga rekord alang sa tanan nga mga elemento "sa punoan", samtang gitipigan ang kasayuran kung unsang gigikanan nga sheet (ug kung unsang mga timailhan) ang hinungdan nga naapil kini sa sample - pananglitan, aron makamugna usa ka summary report. nga adunay panagsama sa mga node.

Ang mosunod kinahanglan nga isipon lamang isip usa ka pamatuod-sa-konsepto, tungod kay ang hangyo nahimong lisud kaayo. Apan kung kini nagdominar sa imong database, kinahanglan nimong hunahunaon ang paggamit sa parehas nga mga pamaagi.

Magsugod kita sa pipila ka yano nga mga pahayag:

Ang sama nga rekord gikan sa database Labing maayo nga basahon lang kini kausa.
Mga rekord gikan sa database Mas episyente ang pagbasa sa mga batchkaysa mag-inusara.

Karon atong sulayan ang paghimo sa hangyo nga atong gikinahanglan.

lakang 1

Dayag nga, sa diha nga ang pagsugod sa recursion (diin man kita kung wala kini!) kinahanglan naton nga ibawas ang mga rekord sa mga dahon mismo base sa set sa mga inisyal nga identifier:

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

Kung kini ingon katingad-an sa usa ka tawo nga ang "set" gitipigan ingon usa ka hilo ug dili usa ka laray, nan adunay usa ka yano nga katin-awan alang niini. Adunay usa ka built-in nga aggregating "gluing" function alang sa mga string string_agg, apan dili alang sa mga arrays. Bisan siya sayon nga ipatuman sa imong kaugalingon.

lakang 2

Karon makakuha kami usa ka hugpong sa mga ID sa seksyon nga kinahanglan nga basahon pa. Hapit kanunay sila madoble sa lain-laing mga rekord sa orihinal nga set - mao nga atong buhaton grupo sila, samtang nagpreserbar sa impormasyon bahin sa tinubdan nga mga dahon.

Apan aniay tulo ka kasamok nga naghulat kanato:

Ang "subrecursive" nga bahin sa pangutana dili maglangkob sa mga aggregate function nga adunay GROUP BY.
Ang usa ka pakisayran sa usa ka recursive nga "table" dili mahimong sa usa ka nested subquery.
Ang usa ka hangyo sa recursive nga bahin dili mahimong adunay CTE.

Maayo na lang, kining tanan nga mga problema sayon ra nga masulbad. Magsugod ta sa kataposan.

CTE sa recursive nga bahin

Dinhi dili mga buhat:

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

Ug busa kini molihok, ang mga parentesis naghimo sa kalainan!

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

Nested nga pangutana batok sa usa ka recursive nga "table"

Hmm... Ang usa ka recursive CTE dili ma-access sa usa ka subquery. Apan mahimo kini sa sulod sa CTE! Ug ang usa ka nested request maka-access na niining CTE!

GROUP BY inside recursion

Kini dili maayo, apan ... Kami adunay usa ka yano nga paagi sa pagsundog GROUP PINAAGI sa paggamit DISTINCT ON ug mga function sa bintana!

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

Ug mao kini kung giunsa kini molihok!

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

Karon atong nakita ngano nga ang numeric ID gihimong teksto - aron sila madugtong nga gibulag sa mga koma!

lakang 3

Alang sa katapusan wala na kami nahabilin:

atong basahon ang "seksyon" nga mga rekord base sa usa ka hugpong sa mga grupo nga ID
atong itandi ang gikuha nga mga seksyon sa mga "set" sa orihinal nga mga palid
"palapad" ang set-string gamit 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;

[tan-awa sa explain.tensor.ru]

Source: www.habr.com

Mga Antipattern sa PostgreSQL: Unsa ka lawom ang lungag sa kuneho? adto ta sa hierarchy

#1. Unsa ka lawom ang lungag sa kuneho?

Bulk proofreading pinaagi sa index

Node sign

#2. Balik ta sa mga ugat

lakang 1

lakang 2

CTE sa recursive nga bahin

Nested nga pangutana batok sa usa ka recursive nga "table"

GROUP BY inside recursion

lakang 3

Idugang sa usa ka comment Отменить ответ