ProHoster > Blog > fitantanan-draharaha > Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

Amin'ny rafitra ERP sarotra sampana maro no manana toetra ara-jeografikarehefa milahatra ny zavatra homogeneous hazo fifandraisana amin'ny razana - izany no firafitry ny fandaminana ny orinasa (ireo sampana rehetra, sampana ary vondrona miasa), sy ny katalaogin'ny entana, sy ny sehatry ny asa, ary ny jeografia ny varotra,...

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

Raha ny marina dia tsy misy izany faritra automation orinasa, izay tsy hisy ambaratongam-pahefana vokatr'izany. Saingy na dia tsy miasa "ho an'ny orinasa" aza ianao, dia mbola afaka miatrika fifandraisana ara-jeografika mora foana ianao. Tsy misy dikany izany, na ny tetiaranao na ny drafitry ny gorodona amin'ny toeram-pivarotana iray dia mitovy rafitra.

Misy fomba maro hitahirizana hazo toy izany ao amin'ny DBMS, saingy ankehitriny isika dia hifantoka amin'ny safidy tokana:

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

CREATE INDEX ON hier(pid); -- Π½Π΅ Π·Π°Π±Ρ‹Π²Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ FK Π½Π΅ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°Π΅Ρ‚ автосозданиС индСкса, Π² ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ PK

Ary raha mibanjina ny halalin'ny ambaratongam-pahefana ianao, dia miandry amim-paharetana ny hahita ny fahombiazan'ny fomba fiasanao amin'ny rafitra toy izany.

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
Andeha hojerentsika ny olana mahazatra mitranga, ny fampiharana azy amin'ny SQL, ary miezaka manatsara ny fahombiazany.

#1. Hatraiza ny halalin'ny lavaka bitro?

Aoka ho azo antoka, hanaiky fa io rafitra io dia haneho ny fanambanin'ny sampana amin'ny firafitry ny fikambanana: sampana, sampana, sehatra, sampana, vondrona miasa... - na inona na inona iantsoanao azy.
Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

Voalohany, andao hamorona ny 'hazo' misy singa 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;

Andeha isika hanomboka amin'ny asa tsotra indrindra - fitadiavana mpiasa rehetra miasa ao anatin'ny sehatra iray manokana, na amin'ny resaka ambaratongam-pahefana - mahita ny zanaky ny node rehetra. Tsara ihany koa ny mahazo ny "halalin'ny" ny taranaka ... Mety ilaina izany rehetra izany, ohatra, ny fananganana karazana fifantenana sarotra mifototra amin'ny lisitry ny karapanondron'ireo mpiasa ireo.

Hilamina ny zava-drehetra raha toa ka misy ambaratonga roa amin'ireo taranaka ireo ary ao anatin'ny folo ny isa, fa raha mihoatra ny 5 ny ambaratonga, ary efa am-polony ny taranaka dia mety hisy ny olana. Andeha hojerentsika ny fomba nanoratana (sy miasa) ny safidy fikarohana midina amin'ny hazo. Fa aloha, andeha hojerentsika hoe inona no node ho mahaliana indrindra amin'ny fikarohana ataontsika.

Ny be indrindra "lalina" zana-kazo:

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

Ny be indrindra "malalaka" zana-kazo:

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

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

Ho an'ireo fanontaniana ireo dia nampiasa ny mahazatra izahay recursive JOIN:
Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

Mazava ho azy, miaraka amin'ity modely fangatahana ity ny isan'ny famerimberenana dia hifanaraka amin'ny fitambaran'ny isan'ny taranaka (ary misy am-polony maromaro amin'izy ireo), ary mety haka loharanon-karena lehibe izany, ary, vokatr'izany, fotoana.

Andeha hojerentsika ny zana-kazo "lehibe indrindra":

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;

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
[jereo ao amin'ny explain.tensor.ru]

Araka ny efa nampoizina dia hitanay avokoa ny rakitra 30. Saingy nandany ny 60% tamin'ny fotoana rehetra tamin'izany izy ireo - satria nanao fikarohana 30 tao amin'ny index. Azo atao ve ny manao kely kokoa?

Fanamarinana betsaka amin'ny fanondroana

Mila manao fangatahana fanondroana manokana ho an'ny node tsirairay ve isika? Hita fa tsia - afaka mamaky avy amin'ny fanondroana isika mampiasa fanalahidy maromaro indray mandeha amin'ny antso iray miaraka amin'ny fanampian'ny = ANY(array).

Ary isaky ny vondrona famantarana toy izany dia afaka maka ny ID rehetra hita tamin'ny dingana teo aloha amin'ny "nodes". Izany hoe, isaky ny dingana manaraka isika mitady ny taranaka rehetra amin'ny ambaratonga iray indray mandeha.

Izao ihany no olana, amin'ny fifantenana miverimberina dia tsy afaka miditra amin'ny fanontaniana misy akany ianao, saingy tsy maintsy misafidy izay hita tamin'ny ambaratonga teo aloha ihany isika... Hita fa tsy azo atao ny manao fangatahana nested ho an'ny fifantenana manontolo, fa ho an'ny saha manokana dia azo atao izany. Ary ity saha ity dia mety ho array ihany koa - izay no ilaintsika ampiasaina ANY.

Toa adala kely izany, saingy amin'ny diagram dia tsotra ny zava-drehetra.

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

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;

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
[jereo ao amin'ny explain.tensor.ru]

Ary eto dia tsy ny zava-dehibe indrindra mandresy in-1.5 amin'ny fotoana, ary nalaintsika vitsy kokoa ny buffer, satria 5 ihany no antso ho an'ny index fa tsy 30!

Ny tombony fanampiny dia ny hoe aorian'ny tsy fisian'ny farany, ny mpamantatra dia hijanona ho baiko amin'ny "ambaratonga".

famantarana node

Ny fiheverana manaraka izay hanampy amin'ny fanatsarana ny fampisehoana dia βˆ’ "ravina" dia tsy afaka miteraka, izany hoe ho azy ireo dia tsy ilaina ny mijery "midina" mihitsy. Amin'ny fandrafetana ny asantsika dia midika izany fa raha manaraka ny rojo sampan-draharaha isika ary mahatratra mpiasa iray, dia tsy ilaina ny mijery lavitra an'io sampana io.

Andeha isika hiditra ao amin'ny latabatry FANAMPINY boolean- saha, izay hilaza amintsika avy hatrany raha β€œnode” io fidirana manokana ao amin'ny hazontsika io - izany hoe mety hanana taranaka mihitsy.

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

Mahafinaritra! Hita fa maherin’ny 30% monja amin’ireo singa hazo rehetra no manana taranaka.

Andeha isika hampiasa mekanika hafa kely - fifandraisana amin'ny ampahany miverimberina LATERAL, izay ahafahantsika miditra avy hatrany amin'ny sahan'ny "latabatra" miverimberina ary mampiasa fiasa mitambatra miaraka amin'ny fepetra sivana mifototra amin'ny node mba hampihenana ny fitambaran'ny fanalahidy:

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana

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;

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
[jereo ao amin'ny explain.tensor.ru]

Afaka nampihena ny antso fanondroana indray izahay ary nandresy mihoatra ny in-2 tamin'ny volume proofread.

#2. Andao hiverina amin'ny fotony

Ity algorithm ity dia ilaina raha toa ka mila manangona rakitsoratra ho an'ny singa rehetra "any amin'ny hazo" ianao, raha mitazona fampahalalana momba ny takelaka loharano (ary miaraka amin'ny famantarana inona) nahatonga azy ho tafiditra ao amin'ny santionany - ohatra, mba hamoronana tatitra famintinana. miaraka amin'ny aggregation ho nodes.

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
Ity manaraka ity dia tokony horaisina ho porofon'ny hevitra fotsiny, satria ny fangatahana dia lasa sarotra be. Fa raha manjaka ny angon-drakitrao dia tokony hieritreritra ny hampiasa teknika mitovy amin'izany ianao.

Andeha isika hanomboka amin'ny fanambarana tsotra roa:

  • Ny rakitra mitovy amin'ny angon-drakitra Aleo mamaky azy indray mandeha monja.
  • Firaketana avy amin'ny angon-drakitra Mahomby kokoa ny mamaky andianynoho ny irery.

Andeha isika hanandrana hanorina ny fangatahana ilaintsika.

dingana 1

Mazava ho azy, rehefa manomboka ny recursion (aiza isika raha tsy misy izany!) Tsy maintsy manaisotra ny rakitsoratry ny ravin-kazo isika mifototra amin'ny andiana famantarana voalohany:

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

Raha toa hafahafa amin'ny olona iray fa ny "set" dia voatahiry ho tady fa tsy array, dia misy fanazavana tsotra momba izany. Misy fiasa "gluing" mitambatra ho an'ny tady string_agg, fa tsy ho an'ny array. Na dia izy aza mora ampiharina samirery.

dingana 2

Ankehitriny dia hahazo andiana ID fizarana izay mila vakiana bebe kokoa. Saika adika matetika amin'ny rakitsoratra samihafa amin'ny andiany voalohany izy ireo - izany no hataontsika vondrona azy ireo, sady mitahiry vaovao momba ny ravin-kazo.

Fa olana telo no miandry antsika:

  1. Ny ampahany "subrecursive" amin'ny fangatahana dia tsy afaka mirakitra fiasa mitambatra GROUP BY.
  2. Ny fanondroana "tabilao" miverimberina dia tsy azo atao amin'ny subquery misy akany.
  3. Ny fangatahana ao amin'ny ampahany miverimberina dia tsy misy CTE.

Soa ihany fa ireo olana rehetra ireo dia mora vahana. Andeha isika hanomboka amin'ny farany.

CTE amin'ny ampahany recursive

Here so tsy miasa:

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

Ary izany dia miasa, ny fononteny no manova ny fiovana!

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

Fanontaniana miompana amin'ny "latabatra" miverimberina

Hmm... Tsy azo idirana amin'ny subquery ny CTE miverimberina. Saingy mety ho ao anatin'ny CTE izany! Ary ny fangatahana nested dia efa afaka miditra amin'ity CTE ity!

GROUP BY anatiny recursion

Tsy mahafinaritra izany, saingy ... Manana fomba tsotra izahay hanahafana ny GROUP BY mampiasa DISTINCT ON ary ny fiasan'ny varavarankely!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- Π½Π΅ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚!

Ary izao no fomba fiasa!

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

Hitantsika izao ny antony nahatonga ny ID nomerika ho lahatsoratra - mba hahafahan'izy ireo mitambatra miaraka amin'ny faingo!

dingana 3

Ho an'ny famaranana dia tsy manana na inona na inona izahay:

  • mamaky ny firaketana "fizarana" mifototra amin'ny andiana ID mivondrona izahay
  • ampitahainay amin'ny "set" amin'ny takelaka tany am-boalohany ny fizarana nalaina
  • "manitarana" ny tady napetraka mampiasa 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;

Antipatterns PostgreSQL: Hatraiza ny halalin'ny lavaka bitro? andao handeha hamaky ny ambaratongam-pahefana
[jereo ao amin'ny explain.tensor.ru]

Source: www.habr.com

Add a comment