🥇PostgreSQL एंटीपैटर्न: खरगोश का छेद कितना गहरा है? आइए पदानुक्रम के माध्यम से चलें

जटिल ईआरपी सिस्टम में कई संस्थाओं की प्रकृति पदानुक्रमित होती हैजब सजातीय वस्तुएँ पंक्तिबद्ध हो जाती हैं पूर्वज-वंशज संबंधों का वृक्ष - यह उद्यम की संगठनात्मक संरचना है (ये सभी शाखाएँ, विभाग और कार्य समूह), और माल की सूची, और कार्य के क्षेत्र, और बिक्री बिंदुओं का भूगोल,...

वास्तव में, वहाँ कोई नहीं है व्यवसाय स्वचालन क्षेत्र, जहां परिणामस्वरूप कोई पदानुक्रम नहीं होगा। लेकिन भले ही आप "व्यवसाय के लिए" काम नहीं करते हैं, फिर भी आप आसानी से पदानुक्रमित संबंधों का सामना कर सकते हैं। यह घिसी-पिटी बात है, यहां तक कि आपके परिवार के पेड़ या शॉपिंग सेंटर में परिसर के फर्श की योजना भी एक ही संरचना है।

ऐसे ट्री को 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

इन प्रश्नों के लिए हमने ठेठ का उपयोग किया पुनरावर्ती शामिल हों:

जाहिर है, इस अनुरोध मॉडल के साथ पुनरावृत्तियों की संख्या वंशजों की कुल संख्या से मेल खाएगी (और उनमें से कई दर्जन हैं), और इसमें काफी महत्वपूर्ण संसाधन लग सकते हैं, और, परिणामस्वरूप, समय।

आइए "सबसे चौड़े" उपवृक्ष पर जाँच करें:

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;

[देखें व्याख्या.टेंसर.आरयू]

जैसी कि उम्मीद थी, हमें सभी 30 रिकॉर्ड मिल गये। लेकिन उन्होंने कुल समय का 60% इसी पर खर्च किया - क्योंकि उन्होंने इंडेक्स में 30 खोजें भी कीं। क्या इससे कम करना संभव है?

सूचकांक द्वारा थोक प्रूफरीडिंग

क्या हमें प्रत्येक नोड के लिए एक अलग सूचकांक क्वेरी बनाने की आवश्यकता है? यह पता चला कि नहीं - हम सूचकांक से पढ़ सकते हैं एक कॉल में एक साथ कई कुंजियों का उपयोग करना के माध्यम से = ANY(array).

और पहचानकर्ताओं के ऐसे प्रत्येक समूह में हम पिछले चरण में मिली सभी आईडी को "नोड्स" द्वारा ले सकते हैं। यानी हर अगले कदम पर हम करेंगे एक निश्चित स्तर के सभी वंशजों को एक साथ खोजें.

बस, यहीं समस्या है, पुनरावर्ती चयन में, आप नेस्टेड क्वेरी में स्वयं तक नहीं पहुंच सकते, लेकिन हमें किसी तरह केवल वही चुनने की ज़रूरत है जो पिछले स्तर पर पाया गया था... यह पता चला है कि संपूर्ण चयन के लिए नेस्टेड क्वेरी बनाना असंभव है, लेकिन इसके विशिष्ट क्षेत्र के लिए यह संभव है। और यह फ़ील्ड एक सरणी भी हो सकती है - जिसका हमें उपयोग करने की आवश्यकता है 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;

[देखें व्याख्या.टेंसर.आरयू]

और यहां सबसे महत्वपूर्ण बात यह भी नहीं है समय में 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;

[देखें व्याख्या.टेंसर.आरयू]

हम एक और इंडेक्स कॉल को कम करने में सक्षम थे वॉल्यूम में 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 कदम

अब हमें अनुभाग आईडी का एक सेट मिलेगा जिसे आगे पढ़ने की आवश्यकता होगी। लगभग हमेशा उन्हें मूल सेट के विभिन्न रिकॉर्ड में डुप्लिकेट किया जाएगा - इसलिए हम करेंगे उन्हें समूहित करें, स्रोत पत्तों के बारे में जानकारी संरक्षित करते हुए।

लेकिन यहां तीन परेशानियां हमारा इंतजार कर रही हैं:

क्वेरी के "सबरिकर्सिव" भाग में समग्र फ़ंक्शन शामिल नहीं हो सकते 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 का अनुकरण करने का एक सरल तरीका है 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

अब हम देखते हैं कि संख्यात्मक आईडी को टेक्स्ट में क्यों बदल दिया गया - ताकि उन्हें अल्पविराम से अलग करके एक साथ जोड़ा जा सके!

3 कदम

फाइनल के लिए हमारे पास कुछ भी नहीं बचा है:

हम समूहीकृत आईडी के एक सेट के आधार पर "अनुभाग" रिकॉर्ड पढ़ते हैं
हम घटाए गए अनुभागों की तुलना मूल शीट के "सेट" से करते हैं
का उपयोग करके सेट-स्ट्रिंग का "विस्तार" करें 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;

[देखें व्याख्या.टेंसर.आरयू]

स्रोत: www.habr.com

PostgreSQL एंटीपैटर्न: खरगोश का छेद कितना गहरा है? आइए पदानुक्रम से गुजरें

#1. खरगोश का बिल कितना गहरा है?

सूचकांक द्वारा थोक प्रूफरीडिंग

नोड चिन्ह

#2. आइए जड़ों की ओर वापस चलें

1 कदम

2 कदम

पुनरावर्ती भाग में CTE

पुनरावर्ती "तालिका" के विरुद्ध नेस्टेड क्वेरी

आंतरिक प्रत्यावर्तन द्वारा समूहीकृत करें

3 कदम

एक टिप्पणी जोड़ें उत्तर रद्द