PostgreSQL Antipatterns: כמה עמוק חור הארנב? בואו נעבור בהיררכיה

במערכות 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;

[הסתכל ב-explain.tensor.ru]

כצפוי, מצאנו את כל 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;

[הסתכל ב-explain.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;

[הסתכל ב-explain.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

כעת נקבל קבוצה של מזהי מקטעים שיהיה צורך לקרוא עוד יותר. כמעט תמיד הם ישוכפלו ברשומות שונות של הסט המקורי - כך היינו לקבץ אותם, תוך שמירה על מידע על דפי המקור.

אבל כאן מחכות לנו שלוש צרות:

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;

[הסתכל ב-explain.tensor.ru]

מקור: www.habr.com