PostgreSQL Antipatterns: "אינסוף הוא לא הגבול!", או קצת על רקורסיה

רקורסיה - מנגנון חזק ונוח מאוד אם מבוצעות אותן פעולות "מעמיקות" על נתונים קשורים. אבל רקורסיה בלתי מבוקרת היא רוע שיכול להוביל לשניהם ביצוע אינסופי תהליך, או (מה שקורה לעתים קרובות יותר). "אוכלים" את כל הזיכרון הפנוי.

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

ב-PostgreSQL, היכולת להשתמש בשאילתות רקורסיביות באמצעות WITH RECURSIVE הופיע מאז ומתמיד של גרסה 8.4, אבל אתה עדיין יכול להיתקל בקביעות בבקשות "חסרות הגנה" שעלולות להיות פגיעות. איך להיפטר מבעיות מהסוג הזה?

אל תכתוב שאילתות רקורסיביות

וכתוב לא רקורסיביים. בכבוד רב, K.O.

למעשה, PostgreSQL מספק די הרבה פונקציונליות שתוכל להשתמש בה לא להחיל רקורסיה.

השתמש בגישה שונה מהותית לבעיה

לפעמים אתה יכול פשוט להסתכל על הבעיה מ"הצד השונה". נתתי דוגמה למצב כזה במאמר "SQL HowTo: 1000 ודרך צבירה אחת" - הכפלה של קבוצת מספרים ללא שימוש בפונקציות צבירה מותאמות אישית:

WITH RECURSIVE src AS (
  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr
)
, T(i, val) AS (
  SELECT
    1::bigint
  , 1
UNION ALL
  SELECT
    i + 1
  , val * arr[i]
  FROM
    T
  , src
  WHERE
    i <= array_length(arr, 1)
)
SELECT
  val
FROM
  T
ORDER BY -- отбор финального результата
  i DESC
LIMIT 1;

ניתן להחליף בקשה זו באופציה של מומחי מתמטיקה:

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

השתמש ב-generated_series במקום בלולאות

נניח שאנו עומדים בפני המשימה של יצירת כל הקידומות האפשריות למחרוזת 'abcdefgh':

WITH RECURSIVE T AS (
  SELECT 'abcdefgh' str
UNION ALL
  SELECT
    substr(str, 1, length(str) - 1)
  FROM
    T
  WHERE
    length(str) > 1
)
TABLE T;

האם אתה בטוח שאתה צריך רקורסיה כאן?.. אם אתה משתמש LATERAL и generate_series, אז אפילו לא תצטרך CTE:

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

שנה את מבנה מסד הנתונים

לדוגמה, יש לך טבלה של הודעות בפורום עם קשרים ממי שהגיב למי, או שרשור פנימה רשת חברתית:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

ובכן, בקשה טיפוסית להוריד את כל ההודעות בנושא אחד נראית בערך כך:

WITH RECURSIVE T AS (
  SELECT
    *
  FROM
    message
  WHERE
    message_id = $1
UNION ALL
  SELECT
    m.*
  FROM
    T
  JOIN
    message m
      ON m.reply_to = T.message_id
)
TABLE T;

אבל מכיוון שאנחנו תמיד צריכים את כל הנושא מההודעה הבסיסית, אז למה שלא הוסף את המזהה שלו לכל ערך אוֹטוֹמָטִי?

-- добавим поле с общим идентификатором темы и индекс на него
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- инициализируем идентификатор темы в триггере при вставке
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события
    ELSE ( -- или из сообщения, на которое отвечаем
      SELECT
        theme_id
      FROM
        message
      WHERE
        message_id = NEW.reply_to
    )
  END;
  RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER ins BEFORE INSERT
  ON message
    FOR EACH ROW
      EXECUTE PROCEDURE ins();

כעת ניתן לצמצם את כל השאילתה הרקורסיבית שלנו רק לזה:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

השתמש ב"מגבילים" שהוחלו

אם אנחנו לא מצליחים לשנות את מבנה מסד הנתונים מסיבה כלשהי, בואו נראה על מה אנחנו יכולים לסמוך כדי שאפילו נוכחות של שגיאה בנתונים לא תוביל לרקורסיה אינסופית.

מונה עומק רקורסיה

אנחנו פשוט מגדילים את המונה באחד בכל שלב רקורסיה עד שנגיע לגבול שנראה לנו כלא מספק:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

פרו: כשאנחנו מנסים לעשות לולאה, עדיין לא נעשה יותר מהמגבלה שצוינה של איטרציות "בעומק".
חסרונות: אין ערובה שלא נעבד את אותה רשומה שוב - לדוגמה, בעומק של 15 ו-25, ולאחר מכן כל 10+. ואף אחד לא הבטיח שום דבר על "רוחב".

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

ראה "בעיית הדגנים על לוח שחמט"

שומר "הנתיב"

אנו מוסיפים לסירוגין את כל מזהי האובייקטים שפגשנו לאורך נתיב הרקורסיה למערך, שהוא "נתיב" ייחודי אליו:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

פרו: אם יש מחזור בנתונים, אנו לחלוטין לא נעבד את אותה רשומה שוב ושוב באותו נתיב.
חסרונות: אבל יחד עם זאת, אנחנו יכולים ממש לעקוף את כל הרשומות מבלי לחזור על עצמנו.

ראה "בעיית מהלך האביר"

מגבלת אורך נתיב

כדי להימנע ממצב של רקורסיה "נדידה" בעומק בלתי מובן, נוכל לשלב את שתי השיטות הקודמות. לחלופין, אם אנחנו לא רוצים לתמוך בשדות מיותרים, השלימו את התנאי להמשך הרקורסיה עם אומדן של אורך הנתיב:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) AND
    array_length(T.path, 1) < 10
)

בחרו שיטה לטעמכם!

מקור: www.habr.com