CTE רקורסיבי ב-SQLite: WITH RECURSIVE לעצים ולסדרות

רקורסיה ב-SQL נשמעת מוזר, עד שרואים אותה

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

המבנה תמיד זהה:

WITH RECURSIVE name(columns) AS (
    -- עוגן: שורות ההתחלה
    SELECT ...
    UNION ALL
    -- רקורסיבי: שורות שנגזרות מהשלב הקודם
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

עוגן למעלה, UNION ALL, ושאילתה רקורסיבית מתחת. SQLite מריצה את העוגן פעם אחת, ואז ממשיכה להריץ את החלק הרקורסיבי, בכל פעם עם השורות שנוצרו בסבב הקודם, עד שהוא לא מחזיר שורות חדשות. ואז היא עוצרת.

ספירה מ-1 עד 10

ה-CTE הרקורסיבי הפשוט ביותר מייצר סדרה. אין צורך בטבלאות:

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10
)
SELECT n FROM counter;

עקבו אחרי הריצה:

1. העוגן מייצר שורה אחת: n = 1.
2. הצעד הרקורסיבי לוקח את השורה הזו, מחשב n + 1 = 2, ו-2 < 10 אמת, אז הוא שומר את השורה.
3. האיטרציה הבאה לוקחת n = 2 ומייצרת n = 3. וכן הלאה.
4. כש-n מגיע ל-10, 10 < 10 שקר, הצעד הרקורסיבי לא מחזיר שורות, ו-SQLite עוצרת.

WHERE n < 10 הוא תנאי העצירה. בלעדיו השאילתה רצה לנצח.

יצירת סדרת תאריכים

אותו רעיון, שימושי בדוחות אמיתיים: למלא כל יום בטווח, גם ימים שבהם לא קרה כלום:

WITH RECURSIVE days(d) AS (
    SELECT date('2024-01-01')
    UNION ALL
    SELECT date(d, '+1 day') FROM days WHERE d < '2024-01-07'
)
SELECT d FROM days;

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

מעבר על עץ של הורה וילד

מקרה השימוש הקלאסי. הנה טבלת עובדים שבה כל שורה מצביעה על המנהל שלה:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE org(id, name, manager_id, depth) AS (
    SELECT id, name, manager_id, 0
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, org.depth + 1
    FROM employees e
    JOIN org ON e.manager_id = org.id
)
SELECT printf('%.*c%s', depth * 2, ' ', name) AS tree
FROM org;

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

זה עובד לעצים בכל עומק. שתי רמות, עשר רמות: השאילתה לא משתנה.

מציאת כל האבות של שורה מסוימת

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

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE chain(id, name, manager_id) AS (
    SELECT id, name, manager_id
    FROM employees
    WHERE name = 'Diego'
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN chain ON chain.manager_id = e.id
)
SELECT name FROM chain;

העוגן הוא העובד שממנו מתחילים. כל צעד רקורסיבי קופץ להורה. SQLite עוצרת כשהיא מגיעה לשורש: manager_id IS NULL, ולכן ה-JOIN לא מוצא כלום.

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

תנאי עצירה ולולאות אינסופיות

הבאג הנפוץ ביותר הוא לשכוח את תנאי העצירה או לכתוב תנאי שאף פעם לא מתקיים. השוו:

-- רצה לנצח:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

אין פסוקית WHERE שתחזיר אי פעם אפס שורות. SQLite תנסה בשמחה לספור עד אינסוף.

שני הרגלים הגנתיים:

1. תמיד שימו פסוקית WHERE בחלק הרקורסיבי שמגבילה את הגדילה.
2. הוסיפו LIMIT ל-SELECT החיצוני כרשת ביטחון בזמן הפיתוח: אם טעיתם בתנאי העצירה, השאילתה עדיין מסתיימת.

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter
)
SELECT n FROM counter LIMIT 5;

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

מעגלים בגרפים

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

CREATE TABLE edges (a INTEGER, b INTEGER);
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (3, 4);

WITH RECURSIVE walk(node, path) AS (
    SELECT 1, ',1,'
    UNION ALL
    SELECT e.b, path || e.b || ','
    FROM edges e
    JOIN walk ON e.a = walk.node
    WHERE instr(path, ',' || e.b || ',') = 0
)
SELECT node, path FROM walk;

path היא מחרוזת של צמתים שכבר ביקרתם בהם, מופרדים בפסיקים. לפני הוספת צומת חדש, פסוקית ה-WHERE בודקת שהוא לא נמצא בה. בלי ההגנה הזו, המעגל 1 → 2 → 3 → 1 היה נמשך לנצח.

אין ב-SQL "קבוצת ביקורים" מובנית: בונים אותה בעצמכם, בדרך כלל כמחרוזת או על ידי JOIN מול ה-CTE עד כה.

CTE רקורסיבי מול Self Join

אם צריך רק רמה אחת או שתיים, self join פשוט ומהיר יותר:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

SELECT e.name AS employee, m.name AS manager
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

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

• עומק קבוע וקטן: self join, אולי שניים או שלושה כאלה.
• עומק לא ידוע או שרירותי: WITH RECURSIVE.

מודל מנטלי

CTE רקורסיבי הוא לולאה שנכתבת באופן הצהרתי:

• העוגן הוא הערך ההתחלתי של הלולאה.
• השאילתה הרקורסיבית היא גוף הלולאה: היא מייצרת את קבוצת השורות הבאה מהנוכחיות.
• תנאי העצירה הוא בדיקת היציאה של הלולאה: כשהיא מחזירה אפס שורות, הלולאה מסתיימת.
• UNION ALL צובר הכול לקבוצת התוצאות הסופית.

ברגע שהמיפוי הזה יושב לכם בראש, התחביר מפסיק להרגיש מוזר. אתם כותבים לולאת for ב-SQL.

הבא: אינדקסים

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