أنماط 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. ما مدى عمق حفرة الأرنب؟

ولنقبل، على وجه اليقين، أن هذا الهيكل سيعكس تبعية الأقسام في هيكل المنظمة: إدارات، أقسام، قطاعات، فروع، مجموعات عمل... - مهما سميتها.

أولاً، دعونا ننشئ "شجرة" مكونة من 10 آلاف عنصر

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;

[انظر إلىشرح.tensor.ru]

كما هو متوقع، وجدنا جميع السجلات الثلاثين. لكنهم أمضوا 30% من إجمالي الوقت في هذا الأمر - لأنهم أجروا أيضًا 60 عملية بحث في الفهرس. هل من الممكن أن تفعل أقل؟

التدقيق اللغوي بالجملة حسب الفهرس

هل نحتاج إلى إجراء استعلام فهرس منفصل لكل عقدة؟ اتضح أن لا - يمكننا أن نقرأ من الفهرس باستخدام عدة مفاتيح في وقت واحد في مكالمة واحدة من خلال = 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;

[انظر إلىشرح.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. دعونا نعود إلى الجذور

ستكون هذه الخوارزمية مفيدة إذا كنت بحاجة إلى جمع سجلات لجميع العناصر "أعلى الشجرة"، مع الاحتفاظ بالمعلومات حول ورقة المصدر (وبأي مؤشرات) التي تسببت في تضمينها في العينة - على سبيل المثال، لإنشاء تقرير ملخص مع التجميع في العقد.

ما يلي يجب أن يؤخذ فقط كدليل على المفهوم، حيث أن الطلب مرهق للغاية. ولكن إذا كانت تهيمن على قاعدة البيانات الخاصة بك، فيجب عليك التفكير في استخدام تقنيات مماثلة.

لنبدأ بعبارتين بسيطتين:

• نفس السجل من قاعدة البيانات من الأفضل قراءتها مرة واحدة فقط.
• السجلات من قاعدة البيانات إنها أكثر كفاءة للقراءة على دفعاتمن وحده.

الآن دعونا نحاول بناء الطلب الذي نحتاجه.

الخطوة 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

سنحصل الآن على مجموعة من معرفات الأقسام التي ستحتاج إلى مزيد من القراءة. سيتم تكرارها دائمًا تقريبًا في سجلات مختلفة للمجموعة الأصلية - وهذا ما نفعله مجموعة منهممع الحفاظ على المعلومات حول أوراق المصدر.

ولكن هنا تنتظرنا ثلاث مشاكل:

1. لا يمكن أن يحتوي الجزء "التكراري" من الاستعلام على وظائف مجمعة بها GROUP BY.
2. لا يمكن أن تكون الإشارة إلى "جدول" متكرر في استعلام فرعي متداخل.
3. لا يمكن أن يحتوي الطلب في الجزء العودي على 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

الآن نرى لماذا تم تحويل المعرف الرقمي إلى نص - بحيث يمكن ضمهما معًا مفصولين بفواصل!

الخطوة 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;

[انظر إلىشرح.tensor.ru]

المصدر: www.habr.com