זיהוי תבניות שורה צלילה מעמיקה
סיור מודרך ב־ISO/IEC 19075-5 · SQL R020 בתוך PostgreSQL — מה בנינו, מה עדיין לא נכתב, וכיצד זה רץ בפועל.
סקרו את התקן, עברו על דוגמאות מעשיות, עיינו בתכנון, ולבסוף הפעילו סימולטור NFA חי עם התבניות שלכם.
דיון: שרשור pgsql-hackers · הטלאי העדכני (v55) · commitfest #4460.
תרגום מקדים בבינה מלאכותית — ייתכנו שגיאות.
§1. התקן, תת־הקבוצה, והשאלות הפתוחות
1.1 היקף התקן
זיהוי תבניות שורה (Row Pattern Recognition) הוכנס ל־SQL במסגרת ISO/IEC 9075-2:2016, ומתואר במסמך הנלווה ISO/IEC 19075-5:2021 (חלק 5, "Row Pattern Recognition").
התקן מגדיר שני ממשקים שעובדים מעל אותה תשתית בסיסית. תכונה R010 ממקמת פסוקית MATCH_RECOGNIZE ברשימת FROM לשם יצירת טבלה נגזרת; תכונה R020 משלבת את אותה לוגיקת תבנית בתוך מפרט WINDOW לשם הפקת פלט של פונקציית חלון. לשני הממשקים חלק ניכר משותף בתחביר ובסמנטיקה (19075-5 מציין ב־§6.3.3 כמה הבדלים הייחודיים ל־R020), אך הם מהווים נקודות כניסה פונקציונליות שונות — מסד נתונים יכול לממש אחת מהן או את שתיהן.
סדרת הטלאים הנדונה כאן מממשת תת־קבוצה של R020 בלבד; טופס פסוקית הטבלה נמצא במפורש מחוץ להיקף.
ממשק R020 הוא קטן אך עשיר ביכולות. שאילתה מצרפת תבנית לחלון על ידי הוספת פסוקיות בתוך מפרט חלון שהמסגרת שלו היא ROWS BETWEEN CURRENT ROW AND …: PATTERN מתארת ביטוי רגולרי מעל משתני תבנית בעלי שם, DEFINE מספקת את הפרדיקט הבוליאני שמזהה כל משתנה, ו־AFTER MATCH SKIP האופציונלית (ברירת מחדל PAST LAST ROW) שולטת באופן שבו התאמות עוקבות ממוקמות בתוך המחיצה.
הפסוקיות האופציונליות MEASURES, SUBSET, INITIAL/SEEK, והפונקציה העזר CLASSIFIER() משלימות את התכונה. (הפונקציה MATCH_NUMBER() שבתקן שייכת לממשק R010 בלבד — 19075-5 §6.3.3 (6) מוציאה אותה במפורש מ־R020.)
הטלאי מכסה מספיק מהאוצר־מילים הזה כדי לאפשר שאילתות לא־טריוויאליות, אך עוצר לפני מספר מבנים שמימושם תלוי בתשתית שטרם נבנתה.
המשך החלק הזה מחלק את אוצר המילים של התקן למה שהטלאי כבר תומך בו, ולמה שהוא משאיר במכוון לעתיד. הרשימות שלהלן משקפות את מצב סדרת הטלאים הנוכחית.
1.2 תכונות ממומשות
אוצר המילים הממומש מספיק כדי להביע את התבניות הקאנוניות מסוג V, W והיפוך, אשר היוו את המוטיבציה הראשונית לזיהוי תבניות שורה. הוא גם מכסה את כל הקוונטיפיקטורים שבתקן — כולל כל שבעת הווריאנטים החששניים (reluctant) *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — ואת ארבעת פרימיטיבי הניווט הנדרשים לתנאי DEFINE כדי להשוות שורות סמוכות.
- פסוקית PATTERN
- מגדירה את תבנית השורה בתוך מפרט החלון; עד 240 משתני תבנית נבדלים.
- מסגרת החלון
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGאוROWS BETWEEN CURRENT ROW ANDnFOLLOWINGעם n ≥ 1 (19075-5 §6.10.2); כל מסגרת אחרת נדחית, ו־EXCLUDE NO OTHERSהיא ההחרגה היחידה המתקבלת.- Regex: + * ? |
- קוונטיפיקטורים סטנדרטיים וחילופין.
- Regex: ( ) קיבוץ
- תת־תבניות מסוגריות.
- Regex: {n} {n,} {,m} {n,m}
- ספירות חזרה חסומות.
- חששניים *? +? ?? {n}? {n,}? {,m}? {n,m}?
- כל שבעת הווריאנטים החששניים (non-greedy) שמגדיר התקן (לא נכללים באופטימיזציית הספיגה).
- פסוקית DEFINE
- תנאים בוליאניים המזהים כל משתנה תבנית.
- משתנה תבנית שורה אוניברסלי
- הפניות עמודה לא מוסמכות ב־
DEFINE(למשלPriceלבדו) נפתרות לשורה הנוכחית, לפי 19075-5 §4.10/§4.16. - PREV, NEXT (עם היסט)
- הגעה ל־n שורות לפני/אחרי השורה הנוכחית (ברירת מחדל 1); הארגומנט הפנימי מוערך בשורה המנווטת.
- FIRST, LAST (עם היסט)
- הגעה לשורה יחסית להתאמה;
FIRST(expr, n)מכוון לשורה n אחרי תחילת ההתאמה, ו־LAST(expr, n)מכוון לשורה n לפני שורת ההתאמה האחרונה. - ניווט מורכב (ארבעה טפסים)
- שלב חיצוני של PREV/NEXT מעל שלב פנימי של FIRST/LAST:
PREV(FIRST(expr)),NEXT(FIRST(expr)),PREV(LAST(expr)),NEXT(LAST(expr))— גם השלב הפנימי וגם החיצוני מקבלים היסט משלהם. - שמות ניווט
PREV,NEXT,FIRSTו־LASTהנכתבים כקריאות לא מוסמכות בתוךDEFINEמשמעם תמיד ניווט; פונקציית משתמש בעלת אותו שם חייבת להיות מוסמכת־סכמה שם.- ארגומנטי ניווט
- עבור
PREV,NEXT,FIRSTו־LAST, הארגומנט הפנימי חייב להכיל לפחות הפניית עמודה אחת, וההיסט חייב להיות קבוע בזמן ריצה. - INITIAL
- התאמות תבנית חייבות להתחיל בשורה הנוכחית (ברירת מחדל).
- AFTER MATCH SKIP PAST LAST ROW
- מצב הדילוג הברירת מחדל; כשיר לספיגת הקשר.
- AFTER MATCH SKIP TO NEXT ROW
- מאפשר התאמות חופפות; משבית את הספיגה.
1.3 לא ממומש
התכונות שטרם מומשו מתחלקות לשלוש קבוצות רופפות. הראשונה — והגדולה ביותר בהפרש ניכר — היא משפחת המבנים שמרכזם MEASURES: פסוקית MEASURES עצמה, SUBSET, CLASSIFIER(), הפניות לעמודות מוסמכות־תבנית כמו B.price, וניווט מוסמך־תבנית כמו LAST(B.price) או PREV(B.price).
אלה אינן פרצות עצמאיות אלא תצוגות שונות של חתיכה חסרה אחת: ה־executor יידרש לשמור היסטוריית התאמה — רישום, לכל שורה בהתאמה, של משתנה התבנית שאליו היא מופתה — ובלעדיו אף אחד מהמבנים הללו אינו מקבל הגדרה משמעותית. CLASSIFIER() קורא את שם המשתנה מתוך אותו רישום; B.price קורא את עמודת המחיר של השורות שרישומן הוא B; LAST(B.price) צועד באותה קבוצת שורות ובוחר את האחרונה; SUBSET U = (A, B) מגדיר משתנה וירטואלי המאחד את שתי הקבוצות; ו־MEASURES מעריך ביטויים כגון AVG(U.Price) תוך שימוש בדיוק באיחוד הזה.
ה־executor הנוכחי מעריך פרדיקטי DEFINE שורה אחר שורה, אך אינו מתעד את הקצאות המשתנים שמתקבלות בשום מקום — אין מה לתשאל מאוחר יותר. בניית תשתית ההיסטוריה היא אפוא תנאי מקדים לכל הקבוצה; התכונות הפרטניות נופלות מאליהן כהיטלים קטנים ברגע שהרישומים קיימים.
הקבוצה השנייה עוסקת ביעדי דילוג חלופיים: AFTER MATCH SKIP TO FIRST var ו־AFTER MATCH SKIP TO [LAST] var (SKIP TO var לבדו משמעו SKIP TO LAST var). גם אלה תלויים בהיסטוריית ההתאמה, שכן ה־executor חייב להיות מסוגל להצביע על השורה שמופתה למשתנה נתון בתוך ההתאמה האחרונה.
שאר הפריטים הם זנב הטרוגני: מילת המפתח SEEK (החלופה ל־INITIAL), התבנית הריקה (), צורת ההחרגה {- … -}, האופרטור חסר־הסדר PERMUTE, ופונקציות צבירה ושאילתות משנה ב־DEFINE, ששתיהן נדחות כעת (צבירה מוסמכת־משתנה תזדקק אף היא להיסטוריית ההתאמה).
- MEASURES
- ביטויי פלט בעלי שם פר־התאמה, למשל
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; ב־R020 מוצגים דרךOVERבדומה לפונקציית חלון. מקבל את מילות המפתח FINAL / RUNNING (19075-5 §5.4), אשר ב־R020 מתמזגות לאותו ערך, מאחר שה־measures מוערכות תמיד על השורה האחרונה של ההתאמה (19075-5 §6.9 (3)). - SUBSET
- איחודים בעלי שם של משתני תבנית, למשל
SUBSET U = (A, B, C). שמיש בכל מקום שבו ניתן להפנות למשתנה תבנית —MEASURES, הפניות מוסמכות־תבנית ב־DEFINE,CLASSIFIER(U)— כולם זקוקים להיסטוריית התאמה. - CLASSIFIER()
- מחזיר את משתנה התבנית שאליו הותאמה שורה נתונה. מוגדר עבור DEFINE וגם MEASURES (19075-5 §5.9); התשובה בכל שורה היא שם המשתנה שתועד עבורה בהיסטוריית ההתאמה.
- הפניית עמודה מוסמכת־תבנית
B.priceחשוף ב־DEFINEאוMEASURES— הערך של העמודה מתוך השורה שמופתה למשתנה הנקוב.- ניווט מוסמך־תבנית
- הגבלת ניווט לשורות שהותאמו למשתנה נקוב, למשל
LAST(B.price),FIRST(B.price),PREV(B.price),NEXT(B.price). - SEEK
- ההתאמה רשאית להתחיל בכל שורה, מהשורה הנוכחית ועד סוף מסגרת החלון המלאה (לעומת INITIAL).
- AFTER MATCH SKIP TO FIRST var
- דילוג לשורה הראשונה שהותאמה כמשתנה הנקוב.
- AFTER MATCH SKIP TO [LAST] var
- דילוג לשורה האחרונה שהותאמה כמשתנה הנקוב.
- Regex: {- -}
- החרגה — מסירה שורות שהותאמו מהפלט של
ALL ROWS PER MATCH. אפשרות זו אינה חלה על חלונות (19075-5 §6.3.3 (4)), ולכן בחלון התחביר מותר (§6.13) אך אין לו פלט לפעול עליו. - Regex: ()
- תבנית ריקה — מתאימה את הרצף הריק.
- PERMUTE(...)
- התאמה חסרת־סדר על פני המשתנים הנקובים. מילת המפתח מזוהה ונדחית ("PERMUTE is not supported");
permuteנותר שמיש כשם של משתנה תבנית. - פונקציות צבירה ב־DEFINE
- פונקציות צבירה כגון
SUM,AVG,COUNTאסורות בפרדיקטיDEFINE. התקן מתיר אותן כצבירות רצות מעל ההתאמה החלקית; צבירה מוסמכת־משתנה כגוןAVG(B.Price)תלויה באותה היסטוריית התאמה ש־MEASURES/CLASSIFIER()דורשות, בעוד שצבירה לא מוסמכת משתרעת על כל שורות ההתאמה עד כה. - שאילתות משנה ב־DEFINE
- כל שאילתת משנה ב־
DEFINEנדחית. התקן מתיר שאילתת משנה שאינה מבצעת זיהוי תבניות שורה ואינה מפנה לשום משתנה תבנית שורה; הטלאי דוחה לעת עתה יותר מן הנדרש.
ארבע נקודות נוספות ראויות לציון כאן, מאחר שקל לטעות בהן ולחשוב שמדובר בהשמטות.
הראשונה היא שעוגני התבנית ^ ו־$ אסורים עם RPR בפסוקית WINDOW על פי התקן עצמו (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; עם ההגדרה הבסיסית ב־19075-5 §4.14.1); היעדרם הוא תאימות, ולא פער.
השנייה היא ש־MATCH_NUMBER() מוצא אף הוא מ־R020 על ידי התקן (19075-5 §6.3.3 (6) ו־19075-5 §6.9 (1)) — הוא חלק מממשק R010 בלבד, והיעדרו כאן הוא שוב תאימות ולא תכונה חסרה.
השלישית היא קבוצת איסורים מבניים שהתקן מטיל על R020 (19075-5 §6.17): זיהוי תבניות שורה אינו יכול להיות מקונן בתוך זיהוי תבניות שורה אחר; MEASURES ו־DEFINE לא יכולים להכיל הפניות חיצוניות; שאילתות משנה בתוך MEASURES או DEFINE לא יכולות להפנות למשתני תבנית (הטלאי מרחיק לכת ודוחה כל שאילתת משנה ב־DEFINE, כמפורט לעיל); ו־RPR אינו יכול לשמש בתוך שאילתה רקורסיבית. הטלאי אוכף את כלל ההפניות החיצוניות ("cannot use outer query column in DEFINE clause") ואת כלל הרקורסיה, את האחרון עבור כל רכיב של פסוקית WITH RECURSIVE. הוא גם דוחה פונקציות נדיפות (volatile) והפניות לשורה שלמה ב־DEFINE.
הרביעית היא ש־MATCH_RECOGNIZE עצמו — תכונה R010, ממשק פסוקית הטבלה של אותה תשתית — מחוץ להיקף הטלאי הזה. השאלה אם PostgreSQL יוסיף בסופו של דבר את R010 תהיה עניין לסדרה עתידית, ולא מדד לסדרה הנוכחית.
§2. דוגמאות — כיצד זה רץ בפועל
הדוגמאות בחלק זה מצטברות בהדרגה. נתחיל בסיבה הרעיונית לכך שהתאמת תבניות שורה שונה באמת מהתאמת תבניות מחרוזת, נציג את ארבע פונקציות הניווט ההופכות את תנאי DEFINE למעניינים, ולבסוף נעבור על חמש דוגמאות מפותחות: התאמה בודדת (תנועת NFA), חילופין, ספיגת הקשר במקרה הקל, ושני מקרים שבהם הספיגה מושבתת.
המנגנון הפנימי שהופך את הניווט לזול — החלפת tuple של חריץ אחד — שייך לתכנון ה־executor ומכוסה בחלק הבא, לא כאן.
2.1 מדוע תבניות שורה שונות מתבניות טקסט
ביטוי רגולרי בטקסט מתאים זרם של תווים, ובכל מיקום יש בדיוק סמל אחד לשקול. שאלת זמן הריצה — "האם הסמל הנוכחי שווה ל־'A'?" — מקבלת תשובה יחידה של כן/לא. אוטומטים עם backtracking מנצלים זאת: לכל היותר ענף אחד שורד לכל תו, ועלות העמימות משולמת על ידי קריאה חוזרת של הקלט.
תבנית שורה שונה באופן מהותי. שורה אינה סמל יחיד; היא tuple של עמודות המוערך כנגד קבוצה של פרדיקטים בוליאניים — תנאי DEFINE. שני פרדיקטים יכולים להיות אמת באותה שורה במקביל, ושום דבר בתקן לא אומר שהם חייבים להיות הדדית בלעדיים. שקלו:
DEFINE A AS price > 100, B AS volume > 1000, C AS price > 200
שורה עם price = 150, volume = 2000 מקיימת גם את A וגם את B אך לא את C. מתאם התבנית אינו יכול לקפל זאת למצב יחיד — שני משתני תבנית פעילים, וכל אלמנט תבנית שנוקב באחד מהם רשאי להתקדם. ה־NFA חייב לפיכך לשאת מצבים בו־זמניים מרובים לכל שורת מחיצה, ולא אחד.
תצפית יחידה זו מניעה את שאר הארכיטקטורה. מצב הביצוע הוא רשימה של הקשרים, כל הקשר הוא רשימה של מצבים, ובכל שורה זמן הריצה שואל לגבי כל מצב, "בהינתן המשתנים שאמת כאן, לאן ניתן ללכת?" הפיצולים שנובעים מכך הם הסיבה שזמן הריצה זקוק למספר שכבות גיזום — דה־דופליקציה של מצבים בתוך הקשר, ספיגה בין הקשרים, ושאר הכללים שנסקרים ב־§3.6 — שבלעדיהן מספר המצבים וההקשרים הפעילים גדל עם המחיצה והתאמת התבנית הופכת לעל־לינארית.
2.2 פונקציות ניווט
תנאי DEFINE המתייחסים רק לשורה הנוכחית מוגבלים; כמעט כל תבנית מעניינת זקוקה להשוות בין השורה הנוכחית לבין שכנותיה או לבין שורות שכבר התקבלו מוקדם יותר בהתאמה. התקן מספק לכך ארבע פונקציות ניווט, והטלאי מממש את כולן.
- PREV(expr [, n])
- השורה n שורות לפני השורה הנוכחית (ברירת מחדל n = 1). משמשת להשוואות "היום מול אתמול".
- NEXT(expr [, n])
- השורה n שורות אחרי השורה הנוכחית (ברירת מחדל n = 1). הצצה קדימה; נדירה בצורת חלון משום שהחלון מונוטוני.
- FIRST(expr [, n])
- השורה n שורות אחרי השורה הראשונה של ההתאמה הנוכחית (ברירת מחדל n = 0, השורה הראשונה עצמה). "השווה לשורה שפתחה את ההתאמה הזו."
- LAST(expr [, n])
- השורה n שורות לפני השורה האחרונה שהותאמה (ברירת מחדל n = 0). בתוך
DEFINEהשורה האחרונה שהותאמה היא השורה הנוכחית, ולכןLAST(price)קוראת את השורה הנוכחית.
ארבעת הפרימיטיבים מתחברים זה לזה: PREV ו־NEXT יכולים לעטוף קריאת FIRST או LAST, ולתת ארבעה טפסים מורכבים שסמנטיקתם היא "לך לשורה יחסית להתאמה, ואז צעד מרחק קבוע ממנה." זה מה שמאפשר לביטוי DEFINE לקרוא, למשל, את השורה שמיד לפני שההתאמה התחילה.
- PREV(FIRST(expr [, n]) [, m])
- צעד m שורות אחורה מהשורה ש־
FIRST(expr, n)קוראת (ברירות מחדל n = 0, m = 1). "מה היה הערך מיד לפני שהתאמה זו החלה?" - NEXT(FIRST(expr [, n]) [, m])
- צעד m שורות קדימה מהשורה ש־
FIRST(expr, n)קוראת. מגיע עמוק יותר אל תוך ההתאמה ללא תלות בשורה הנוכחית. - PREV(LAST(expr [, n]) [, m])
- צעד m שורות אחורה מהשורה ש־
LAST(expr, n)קוראת. "השווה לשורה זמן קצר לפני השורה האחרונה שהותאמה." - NEXT(LAST(expr [, n]) [, m])
- צעד m שורות קדימה מהשורה ש־
LAST(expr, n)קוראת.
שתי נקודות מעשיות ראויות לציון כאן. ראשית, ניתן למשלב ניווט: PREV(FIRST(price)) קוראת את השורה שמיד לפני שההתאמה החלה, והטלאי תומך בכך. שנית, לניווט יש השלכות על האופטימיזציות של ה־executor. PREV ו־NEXT פשוטים הם יחסיים לשורה הנוכחית ובטוחים תמיד; FIRST וגרסאות עם היסט של LAST, לבדם או בתוך PREV/NEXT מורכב, הם יחסיים לגבולות ההתאמה, מה שמתערב עם ספיגת ההקשר: ה־planner משבית אז את הספיגה עבור התבנית כולה. המנגנון מאחורי האינטראקציה הזו הוא נושא §2.6.
2.3 דוגמה מפותחת 1 — תנועת NFA
SKIP PAST LAST ROW ברגע שההתאמה שלו נרשמת.SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (START UP+ DOWN+) DEFINE UP AS price > PREV(price), DOWN AS price < PREV(price) );
התבנית משתטחת לארבעה אלמנטים:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
עבור סדרת המחירים 100, 110, 120, 115, 108, 130:
| שורה | מחיר | משתנים אמת | פעולה |
|---|---|---|---|
| 0 | 100 | START | הקשר חדש. START מתאים ויוצא מיד (max=1); המצב מתקדם ל־UP+. |
| 1 | 110 | START, UP | UP מתאים. ההתקדמות מתפצלת: מצב אחד נשאר בלולאה ב־UP, אחר יוצא אל DOWN+. |
| 2 | 120 | START, UP | UP מתאים במצב הלולאה ושוב מתפצל. מצב ה־DOWN מהשורה 1 מת (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP נכשל במצב הלולאה ומת. מצב ה־DOWN מהשורה 2 מתאים. ההתקדמות מתפצלת: לולאה ב־DOWN, ויציאה אל #FIN — מועמד להתאמה מעל שורות 0–3 נרשם. |
| 4 | 108 | START, DOWN | DOWN מתאים במצב הלולאה ושוב מתפצל; מועמד ה־FIN החדש מעל שורות 0–4 מחליף את הקצר יותר. |
| 5 | 130 | START, UP | מצב ה־DOWN בלולאה נכשל (130 ≮ 108). כשלא נותר מצב חי בהקשר הזה, המועמד הרשום (שורות 0–4) ננעל כהתאמה. הניסיון הבא מתחיל בשורה 5; START מתאים, אך המחיצה מסתיימת לפני כל UP. |
הנקודה המרכזית: בשורה 3, השורה מקיימת גם את START (תמיד אמת) וגם את DOWN, אך ל־START יש משמעות רק עבור הקשר שמתחיל בשורה 3; בהקשר הזה מצב ה־UP בלולאה מת, ורק המצב הממתין ב־DOWN+ מתקדם. האופי הרב־מצבי של §2.1 נראה כפיצול ענפים בכל התאמת UP (המצב יכול להישאר ב־UP+ או להתקדם לעבר DOWN+). העדפת הגרידי היא "לולאה נוספת לפני יציאה", ולכן בנתונים מספיקים הענפים בלולאה היו מאריכים את ההתאמה; כאן ה־DOWN בלולאה מת בשורה 5 (130 ≮ 108), ומועמד ה־FIN האחרון (שורות 0–4) — שנוצר כש־DOWN יצא בשורה 4, והחליף את המועמד של שורה 3 — ננעל כהתאמה.
התוצאה של השאילתה נובעת ישירות מהמעקב הזה. תחת סמנטיקת RPR, פונקציות החלון first_value(price) ו־last_value(price) מוערכות רק בשורה שפתחה את ההתאמה — כל שורה אחרת בהתאמה תפיק NULL עבור פונקציות החלון הללו, מכיוון שמסגרתה המצומצמת ריקה. הפלט עבור הנתונים שלנו נראה אפוא כמו הטבלה שהפוסטר מציג בפאנל הימני העליון שלו:
| שורה | מחיר | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
שורה 0 היא תחילת ההתאמה, ולכן מסגרתה מכסה את שורות 0–4, ופונקציות החלון מדווחות על מחיר הפתיחה של תבנית ה־V ($100) ועל מחיר התחתית ($108). שורות 1–4 נמצאות בתוך ההתאמה אך אינן תחילתה, ולכן מקבלות NULL. שורה 5 (מחיר $130) נמצאת מחוץ לכל התאמה ומקבלת אף היא NULL.
2.4 דוגמה מפותחת 2 — חילופין וסדר לקסיקלי
הצורה (A | B) נותנת למתאם בחירה: בכל שורה, שתי החלופות נבדקות באופן עצמאי, וכל אחת מהן יכולה להתאים. זהו המקום שבו האופי הרב־מצבי מ־§2.1 נראה בתוך הקשר יחיד — לא בין הקשרים (זו ספיגה), אלא לאורך ענפים מקביליים שה־executor חוקר בסדר התבנית, הענף המוקדם תחילה.
PATTERN ((UP | HIGH) DONE) DEFINE UP AS price > PREV(price), HIGH AS price > 100, DONE AS volume > 1000
דמיינו שורה שבה המחיר גם עלה וגם חצה את $100 — גם UP וגם HIGH אמת. כל חלופה משחררת מצב משלה: אחד צועד בענף UP, אחר בענף HIGH. שניהם מתקדמים אז אל DONE, ושם הם נפגשים.
| שורה | משתנים אמת | מצבים פעילים |
|---|---|---|
| R | UP, HIGH | מצב A (ענף UP) ומצב B (ענף HIGH) מתקדמים שניהם אל DONE עם אותן ספירות; B הוא כפיל של A ומושלך |
| R+1 | DONE | מצב A מתאים ל־DONE ומגיע ל־#FIN |
במונחי התקן, שני הענפים מפיקים התאמה באותו אורך מעל אותן שורות, ונותנים שני נתיבים מועמדים — אחד מתויג UP, DONE ואחד HIGH, DONE. התקן פותר זאת באמצעות סדר לקסיקלי: בין החלופות שנכתבו ב־(UP | HIGH), זו שנכתבה ראשונה מנצחת, ללא תלות באורך ההתאמה. מאחר ש־UP מופיע לפני HIGH, הנתיב שורד הוא UP, DONE. ה־executor אוכף זאת בשורה R, לא ב־FIN: הוא מוסיף את מצב ענף ה־UP ראשון, ולכן nfa_append_state_unique() שומרת אותו ומשליכה את מצב ענף ה־HIGH הזהה.
הסדר הלקסיקלי הוא מה שיהפוך את CLASSIFIER() למוגדר היטב כשיממשו אותו בסופו של דבר — הוא מאפשר לזמן הריצה לומר למשתמש "השורה הזו הותאמה כ־UP, לא כ־HIGH" גם כששני הפרדיקטים אמת. הסדר הלקסיקלי הוא הכלל העיקרי לחילופין: ענף מוקדם לקסיקלית מנצח ענף מאוחר ממנו גם אם הענף המאוחר היה מפיק התאמה ארוכה יותר, וענף מאוחר לקסיקלית (קצר יותר אולי) עדיין יכול לנצח אם כל ענף מוקדם ממנו מת לפני שהגיע ל־FIN. אורך גרידי נחתך בתוך קוונטיפיקטור יחיד — בהינתן שתי השלמות של אותו ענף חילופין, הקוונטיפיקטור הגרידי מעדיף יותר חזרות.
2.5 דוגמה מפותחת 3 — ספיגת הקשר (אותו גורל)
התבנית הפשוטה ביותר שמדגימה ספיגה היא PATTERN (A+) עם DEFINE A AS TRUE. כל שורה מתאימה ל־A, והתקן דורש מהמתאם לשקול כל שורה כתחילת התאמה אפשרית. נאיבית, פירוש הדבר N הקשרים עבור מחיצה בת N שורות. ניקח מחיצה של חמש שורות (כל נתונים — הפרדיקט אמת קבועה):
| שורה | הקשרים נאיביים | עם ספיגה |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 נספג |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | חמישה הקשרים | C1[A:5] |
ההקשרים החיים יורדים מ־O(n) ל־O(1), ולכן הסך הכולל על פני המחיצה יורד מ־O(n²) ל־O(n). כלל הספיגה שמצדיק את ההשלכה פשוט כאשר הקוונטיפיקטור בלתי חסום:
הפאנל השמאלי התחתון בפוסטר ("① Context Absorption") הוא בדיוק הכלל הזה ממומחש על פני חמש שורות.
נקודה דקה אך חשובה מסתתרת בכלל: ההשלכה בטוחה מכיוון שהפרדיקט A AS TRUE מוערך לאותו ערך בכל שורה, ללא תלות באיזה הקשר שואל. אותו דבר נכון לכל פרדיקט שמתייחס רק לשורה הנוכחית או להיסט קבוע ממנה — כולל PREV. הדוגמה הבאה עוברת לשבוע מסחר קונקרטי של מחירים, תוך שימוש בפרדיקט מבוסס־PREV, ו־§2.6 יחזור לאותו שבוע בדיוק כדי להמחיש את הסימטריה בין ספיגה בטוחה ולא־בטוחה:
PATTERN (RISE+) DEFINE RISE AS price > PREV(price)
ניקח את שבוע המסחר $100, $108, $112, $116, $110 מיום שני עד יום שישי — ארבע עליות שאחריהן ירידה פתאומית. נניח ש־C1 מתחיל ביום שלישי (היום הראשון שבו RISE מתאים: $108 > $100), וה־executor מנהל ספקולטיבית גם את C2 שמתחיל ביום רביעי. תנאי ה־RISE של כל שורה משווה את מחיר השורה לקודם המיידי שלה — עובדה ברמת המחיצה, ולא ברמת ההקשר — ולכן שני ההקשרים נאלצים לחשב את אותו בוליאני בכל שורה משותפת:
| יום | מחיר | C1 — תחילה ב־ג' price > PREV(price) | C2 — תחילה ב־ד' price > PREV(price) |
|---|---|---|---|
| ב' | $100 | — | — |
| ג' | $108 | $108 > $100 ✓ (התחיל זה עתה) | — |
| ד' | $112 | $112 > $108 ✓ | $112 > $108 ✓ (התחיל זה עתה) |
| ה' | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| ו' | $110 | $110 > $116 ✗ — נעילה | $110 > $116 ✗ — נעילה |
הסיפור נשבר ברגע שהפרדיקט מתחיל להיות תלוי בגבולות של כל הקשר בעצמו — וזה הנושא של §2.6.
2.6 דוגמה מפותחת 4 — כשהספיגה הופכת ללא־בטוחה
DEFINE מפנה ל־FIRST — כלל הספיגה כבר אינו תקף, וה־planner משבית את הספיגה עבור התבנית.
נניח שאנליסט רוצה למצוא ימי מסחר רצופים שבהם מניה נשארה בטווח של עשרה דולרים מהיום שבו הרצף החל — מעין חלון התמתנות. התבנית וה־DEFINE נראים כך:
PATTERN (STABLE+) DEFINE STABLE AS price < FIRST(price) + 10
התנאי משווה כעת את מחיר השורה הנוכחית למחיר בהתחלת הרצף הנוכחי. שני רצפים שהתחילו בימים שונים מקבלים ערכים שונים של FIRST(price), ולכן שני מצבים באותו אלמנט תבנית ובאותה ספירה כבר אינם החלפיים: עתידיהם תלויים בגבול שהספיגה עמדה להשליך.
ניקח את אותו שבוע מסחר ממש כמו ב־§2.5 — $100, $108, $112, $116, $110 מיום שני עד יום שישי. שוב זמן הריצה שומר שני רצפים מועמדים בו־זמנית: C1 התחיל ביום שני, C2 התחיל ביום שלישי (כל שורה היא תחילת רצף פוטנציאלית תחת STABLE+).
| יום | מחיר | C1 — תחילה ב־ב' FIRST = $100 price < $100 + 10 | C2 — תחילה ב־ג' FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| ב' | $100 | $100 < $110 ✓ | — |
| ג' | $108 | $108 < $110 ✓ | $108 < $118 ✓ (התחיל זה עתה) |
| ד' | $112 | $112 < $110 ✗ — נעילת ב'–ג' | $112 < $118 ✓ |
| ה' | $116 | — | $116 < $118 ✓ |
| ו' | $110 | — | $110 < $118 ✓ (עדיין רץ) |
תחת ספיגה, C2 היה ממוזג לתוך C1 ביום שלישי — ההקשר הממוזג שומר רק את התקרה של C1 ($110), ולכן הראייה הייחודית של C2 (תקרה $118, רצף בן ארבעה ימים עד יום שישי) אינה מכוסה על ידי העתיד של C1. בשבוע המסוים הזה הפלט במקרה אינו משתנה: C1 רושם את ב'–ג', C2 התחיל בתוך ההתאמה הזו ומושלך על ידי SKIP PAST LAST ROW, והניסיון הבא מתחיל ביום רביעי עם תקרה משלו ($122) ומתאים את ד'–ו'. אולם באופן כללי, תוצאת ה־DEFINE של הקשר מוקדם כבר אינה מכסה את זו של הקשר מאוחר, ולכן השוואת הספירות שהספיגה נשענת עליה אינה תקפה. בכל פעם שפרדיקט DEFINE נושא תלות בתחילת ההתאמה, ה־planner משבית אפוא את הספיגה באופן יזום.
(כאשר ההתאמה של ההקשר המוביל אכן מצליחה, הקשרים שהתחילו בתוך טווח הקבלה שלו — תחת ברירת המחדל AFTER MATCH SKIP PAST LAST ROW — מושלכים פשוט; הם נשמרים בחיים רק כדי שלזמן הריצה תהיה לאן ליפול חזרה אם ההתאמה המובילה תיכשל.)
הטבלה שלהלן מרחיבה את הפאנל הימני התחתון של הפוסטר ("② Navigation") בטפסים המורכבים, ומסכמת אילו טפסי ניווט יוצרים תלות בתחילת ההתאמה:
| ניווט | תלות בתחילת התאמה | ניתן לספיגה? |
|---|---|---|
| PREV, NEXT | אין | כן |
| LAST (ללא היסט) | אין | כן |
| LAST עם היסט | בדיקת גבול | לא |
| FIRST (כל) | ישירה | לא |
| מורכב (FIRST פנימי) | ישירה | לא |
| מורכב (LAST פנימי, ללא היסט) | אין | כן |
| מורכב (LAST פנימי עם היסט) | בדיקת גבול | לא |
שתי הדוגמאות ב־§2.5 ו־§2.6 מסתכמות בכלל יחיד. אותו גורל הוא מה שהופך את הספיגה לבטוחה: אם כל הקשר באותו אלמנט תבנית יחשב את אותה תשובה לכל פרדיקט עתידי, רק הוותיק ביותר צריך להישמר. גורלות שונים הופכים את הספיגה ללא־בטוחה: ברגע שהפרדיקטים מסתעפים על מצב פרטי להקשר — וזה בדיוק מה ש־FIRST ו־LAST נושא־היסט עושים — כל הקשר חי מייצג עתיד שאין ודאות שהקשר אחר יכסה אותו, ולכן כבר לא ניתן להראות שהשלכת אחד מהם בטוחה.
ה־planner מזהה את ההבחנה הזו בזמן הקומפילציה ומפעיל או מכבה את הספיגה עבור התבנית כולה; כשהיא כבויה, זמן הריצה משלם את עלות ריבוי ההקשרים. הבנצ'מרק שבפוסטר בפאנל ③ אינו משתמש ב־FIRST, ולכן הספיגה נשארת פעילה, וזו הסיבה ש־PostgreSQL נשאר לינארי גם במקרה ההצלחה וגם במקרה הכישלון.
מספרי הבנצ'מרק שעל הפוסטר הם אותו אלגוריתם פועל בקנה מידה. על תבנית ההצלחה (A+ B+ C+ D), גם PostgreSQL וגם Trino גדלים בקירוב לפי O(n) לאחר שהתאמה אושרה, ו־PostgreSQL מוביל בכפי 16× עד 33× בערך (נתוני Trino כבר אינם כוללים את זמן האתחול של ה־JVM).
על תבנית הכישלון (A+ B+ C+ E), Trino, שככל הנראה חסרה לו ספיגה, רודף אחרי כל תחילת התאמה אפשרית ומתדרדר אף מהר יותר מ־O(n²) (כ־56× מהזמן עבור 5× מהשורות); ב־100,000 שורות הדבר אורך יותר מחמש שעות, בעוד PostgreSQL עדיין מסיים ב־92 מילישניות, האצה של כפי 217,000× בערך.
הפער הזה אינו ליטוש הנדסי — הוא בדיוק ההבחנה בין אותו גורל / גורל שונה מ־§2.5 ו־§2.6, מיושמת על כל שורה של כל תחילת התאמה אפשרית במחיצה.
2.7 דוגמה מפותחת 5 — כש־SKIP משבית את הספיגה
הדוגמה הקודמת שברה את הספיגה מצד הנתונים: FIRST ב־DEFINE גרם לכל הקשר להעריך פרדיקטים אחרת. ספיגה יכולה גם להישבר מצד הפלט, ופסוקית AFTER MATCH SKIP היא זו ששולטת בכך.
שקלו את התבנית PATTERN (A+) עם DEFINE A AS TRUE מעל חמש שורות שכולן מתאימות ל־A. תחת ברירת המחדל AFTER MATCH SKIP PAST LAST ROW, המתאם מוצא את ההתאמה הארוכה ביותר שמתחילה בשורה המוקדמת ביותר ואז קופץ מעבר לה; כל הקשר שהתחיל בתוך אותה התאמה מושלך באופן מובלע כמיותר — בדיוק המצב שהספיגה תוכננה לטפל בו. הפלט הוא התאמה יחידה, שורות 0–4, וזמן הריצה זקוק רק להקשר חי אחד.
החלפו את מצב הדילוג ל־AFTER MATCH SKIP TO NEXT ROW וההסכם משתנה:
PATTERN (A+) DEFINE A AS TRUE AFTER MATCH SKIP TO NEXT ROW
כעת על כל מיקום תחילה אפשרי לדווח בנפרד, גם כאשר ההתאמות חופפות. עבור אותן חמש שורות זמן הריצה נדרש לפלוט חמש התאמות: שורות 0–4, 1–4, 2–4, 3–4, ו־4–4. אף אחת מהן אינה ניתנת להחלפה ב"ארוכה יותר שמתחילה מוקדם יותר", מכיוון שהתקן אומר שהמשתמש רוצה את כולן.
| שורה | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | ההתאמה מתחילה; שורות 0–4 יהיו ההתאמה היחידה | ההתאמה מתחילה בשורה 0 |
| 1 | (בתוך התאמה 0) | ההתאמה מתחילה בשורה 1 — חייבת להישמר חיה |
| 2 | (בתוך התאמה 0) | ההתאמה מתחילה בשורה 2 — חייבת להישמר חיה |
| 3 | (בתוך התאמה 0) | ההתאמה מתחילה בשורה 3 — חייבת להישמר חיה |
| 4 | התאמה 0 ננעלת (שורות 0–4) | חמש התאמות ננעלות: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW, כל הקשר מאוחר־התחלה הוא שורת פלט בפני עצמו. שני הקשרים באותו אלמנט תבנית אינם מיותרים יותר — הם שניהם פלטים נדרשים, והשלכת אחד מהם תוריד בשקט התאמה שהמשתמש ביקש.
שימו לב שהפרדיקט לא השתנה. A AS TRUE מוערך באותו אופן בכל שורה ללא תלות באיזה הקשר שואל, ולכן תנאי "אותו גורל" מ־§2.5 עדיין מתקיים. מה שמשתנה הוא דרישת הפלט: גם הקשרים עם עתידים זהים חייבים להתקיים זה לצד זה משום שהם מתאימים לשורות נפרדות של התוצאה. ה־planner משבית אפוא את ספיגת ההקשרים בכל פעם ש־AFTER MATCH SKIP TO NEXT ROW בתוקף, ללא תלות בפסוקית ה־DEFINE.
הצבת §2.6 ו־§2.7 זה לצד זה נותנת את שתי הדרכים שבהן הסמנטיקה של שאילתה שוללת את הספיגה:
FIRST או LAST נושא־היסט ב־DEFINE.AFTER MATCH SKIP TO NEXT ROW.
כל אחד מהתנאים מספיק כדי להשבית את הספיגה עבור התבנית כולה, וכך גם מסגרת שאינה מסתיימת ב־UNBOUNDED FOLLOWING. כשאף אחד מהם אינו בתוקף — ברירת המחדל AFTER MATCH SKIP PAST LAST ROW, סוף מסגרת בלתי חסום, ותנאי DEFINE שמשתמשים רק ב־PREV, NEXT, או LAST חשוף — הספיגה מופעלת, אך רק עבור מצבים באזור הבר־ספיגה של התבנית: משתנה גרידי בלתי חסום מוביל כגון A+ או A*, קבוצה באורך קבוע עם קוונטיפיקטור גרידי בלתי חסום כגון (A B)+, קבוצה גרידית שגופה מתחיל באחד מאלה כגון (A+ B)+ או (A+ B){2}, או ענפי חילופין הבנויים מאלה; קבוצה חששנית פוסלת את כל תת־העץ שלה. היכן שזה מתקיים, כמו עבור A+ ב־§2.5, זמן הריצה מקפל להקשר יחיד ונשאר לינארי; START UP+ DOWN+ מ־§2.3 אינה מקבלת אזור בר־ספיגה כלל.
§3. תכנון — מ־Parser ל־Executor
זיהוי תבניות שורה ממומש כשלושה שלבים שמעבירים עבודה דרך טפסי ביניים מוגדרים היטב. ה־parser הופך טקסט SQL לעץ תבנית ולרשימת פרדיקטי DEFINE; ה־planner מהדר את העץ למערך שטוח של אלמנטי תבנית ומחליט מי מהם יכול להשתתף בספיגת הקשרים; ה־executor מריץ את המערך כנגד המחיצה שורה אחר שורה בלולאה תלת־פאזית. לכל שלב יש את צורת הנתונים שלו, ורוב הברק התכנוני נמצא בגבולות: NFA שטוח שנכנס למטמון, מודל ניווט שמשתמש מחדש בחריץ tuple יחיד במקום לחלק אחד לכל הפניה, וכלל ספיגה שהופך עבודה של O(n²) ל־O(n).
SQL text
│
│ parser stage
▼ validate frame
build pattern tree
type-check DEFINE
pattern tree + DEFINE list
│
│ planner stage
▼ optimize the tree
compile to flat NFA array
decide absorbability
flat NFA + absorption flags
│
│ executor stage
▼ per-row engine:
Match → Absorb → Advance
match result:
start row, length, success/fail
החלקים שלהלן יורדים לאורך הצנרת הזו. §3.1 מכסה את ה־parser ואת צורת עץ התבנית; §3.2 מכסה את הקומפילציה שהופכת את העץ ל־NFA שטוח; §3.3 מכסה את מודל הניווט שפרדיקטי DEFINE משתמשים בו כדי להציץ בשורות שכנות; §3.4 מכסה את טיפול גבולות ההתאמה — כללי SKIP, INITIAL ומסגרת חסומה שקובעים היכן מתחילה ומסתיימת התאמה; §3.5 הוא מנוע פר־שורה תלת־פאזי; §3.6 אוסף את כל מנגנוני הגיזום ששומרים את מרחב המצבים חסום; ו־§3.7 סוקר את מה שהמימוש חושף בפלט EXPLAIN.
3.1 Parser — בניית עץ התבנית
ה־parser מזהה זיהוי תבניות לפי נוכחות פסוקית PATTERN בתוך מפרט חלון. תפקידו הראשון הוא אימות מסגרת, מאחר ש־RPR מטיל אילוצים שאין בשאילתות חלון רגילות: מצב המסגרת חייב להיות ROWS (ולא RANGE או GROUPS), גבול ההתחלה חייב להיות CURRENT ROW, גבול הסיום חייב להיות UNBOUNDED FOLLOWING או offset חיובי FOLLOWING (כך שגם מסגרת ברירת מחדל נדחית), ואופציות EXCLUDE שאינן EXCLUDE NO OTHERS אסורות. אלו בדיקות תאימות, ולא אופטימיזציות — תפיסת המסגרת ב־RPR היא טווח ההתאמה, והתקן אינו מעלה על דעתו למלא אותה במשהו אחר מלבד שורות שהותאמו.
לאחר שהמסגרת עוברת אימות, ה־parser הופך את פסוקית PATTERN לעץ הבנוי מארבעה סוגי צמתים — הפניית משתנה, רצף (שרשור), חילופין, וקבוצה (תת־תבנית בסוגריים). כל צומת נושא את הקוונטיפיקטור כשלושה מספרים — חסם תחתון, חסם עליון (אולי אינסופי), ודגל למצב חששני:
| מקור | קידוד עץ |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
כל פרדיקט DEFINE נבדק לאחר מכן מבחינת טיפוס מול עמודות המחיצה ומכופה לביטוי בוליאני. שני דברים מעשיים נובעים מכך. ראשית, ניתוח הפרסור (parse analysis) אינו מוסיף דבר לרשימת היעד (target list) של השאילתה עבור DEFINE; במקום זאת ה־planner מסמן כל עמודה שפרדיקט DEFINE מפנה אליה כנדרשת, כפי שהוא עושה עבור HAVING, ומפיץ את העמודות הללו לשלב ה־executor גם אם השאילתה הסובבת אינה בוחרת אותן — בלי זה, לזמן הריצה לא יהיה מה להעריך מולו. שנית, משתנים שמופיעים ב־PATTERN אך לעולם לא ב־DEFINE אמת באופן מובלע: הם מתאימים לכל שורה.
3.2 קומפילציה — מ־AST ל־NFA שטוח
ה־planner הופך את עץ ה־parser למבנה הנתונים שה־executor יריץ: מערך שטוח של אלמנטי תבנית הממוען לפי אינדקס. הקומפילציה מתקדמת כצנרת בת שישה שלבים:
compile(astTree):
1. אופטימיזציה של AST
2. מדידת גודל ועומק
3. הקצאת מערך אלמנטים
4. מילוי מתוך ה־AST
(הקצאת מצביעי next/jump)
5. סופי — הגדרת סנטינל FIN
6. סימון אלמנטים זכאים לספיגה
הצורה השטוחה נבחרה מסיבה פשוטה: ה־executor צריך לעבור על התבנית פעמים רבות פר־מחיצה, ומערך רציף הממוען לפי אינדקס הוא מבנה הנתונים הזול ביותר לטיול. שלבים 1 ו־6 הם המעניינים — שלב 1 כי הוא קובע כמה גדול יהיה המערך, ושלב 6 כי הוא קובע אם אופטימיזציית הספיגה מ־§2.5 תופעל בכלל.
אופטימיזציית AST
האופטימיזציה משתלמת פעמיים: פעם אחת במספר האלמנטים הסטטי של המערך השטוח, ושוב בכל שורה שמעובדת בזמן ריצה. כל טרנספורמציה מצמצמת את מרחב המצבים שזמן הריצה חייב לספור. האופטימייזר מיישם תשעה כללי כתיבה־מחדש במעבר יחיד מלמטה למעלה (בתוך רצף, מיזוג הקבוצות רץ פעם נוספת, מאחר שמיזוגים מוקדמים יותר עשויים להפגיש שתי קבוצות זהות):
- שיטוח SEQ
SEQ(A, SEQ(B, C))→SEQ(A, B, C)- מיזוג משתנים רצופים
-
A A→A{2}
A{2,3} A{1,2}→A{3,5} - מיזוג קבוצות רצופות
(A B)+ (A B)+→(A B){2,∞}- מיזוג ALT רצופים
(A | B) (A | B) (A | B)→(A | B){3}- מיזוג קידומת/סיומת
A B (A B)+→(A B){2,∞}- שיטוח ALT ודה־דופ
-
(A | (B | C))→(A | B | C)
(A | B | A)→(A | B) - הכפלת קוונטיפיקטורים
-
(A+)+→A+
(A{2,3}){5}→A{10,15} - פתיחת ילד יחיד
-
SEQ(A)→A
(A){1,1}→A - נרמול חששנות
A{2}?→A{2}(החששנות מנוקה בכל מקום שבו min = max)
הכפלת קוונטיפיקטורים מקפלת רק כאשר הספירות הניתנות להשגה יוצרות מרווח רציף אחד וההתאמה המועדפת אינה זזה: חיצוני מדויק ((A{2,3}){5} → A{10,15}), ילד עם min 0, או מרווחי ילד הנוגעים זה בזה עם min ילד של לכל היותר 1 או max ילד בלתי חסום ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), כאשר חיצוני עם min 0 דורש גם min ילד של לכל היותר 1 ((A{2,})* נשאר, מאחר ש־A* היה מקבל שורה אחת). ילד שהוא קבוצה שהקוונטיפיקטור שלה אינו מדויק חייב תחילה להיות בעל גוף באורך קבוע, ולכן ((A | B B){1,2}){2} נשאר בעינו אף תחת חיצוני מדויק. שילובים אחרים עלולים להכניס פערים שהצורה השטוחה תפספס — למשל, (A{2}){2,3} מקבל רק {4, 6}, אך A{4,6} נאיבי היה מקבל גם 5 — או להזיז את ההתאמה המועדפת ((A{2,3}){1,2} מעדיף שלוש שורות היכן ש־A{2,6} לוקח ארבע), ולכן האופטימייזר משאיר אותם בעינם. זו אינה הכתיבה־מחדש המוגבלת היחידה: מיזוג קבוצות ומיזוג הסיומת דורשים גוף שצורך מספר קבוע של שורות, מיזוג הקידומת מסרב לקבוצה עם min 0, max סופי ותוכן הניתן להאפסה, צמתים חששניים אינם ממוזגים ואינם מוכפלים ((A+?)+ נשאר), וכתיבה־מחדש שהחסם החדש שלה היה גולש נדחית.
צורת אלמנט
כל אלמנט במערך השטוח מייצג מיקום יחיד בתבנית. ישנם שישה סוגים לוגיים: הפניית משתנה (היחידי שצורך שורה); סמני תחילת קבוצה וסוף קבוצה, שפותחים וסוגרים תת־תבנית בסוגריים; סמן חילופין, שעומד בראש רשימת ענפים; מפריד ענפים שמסיים כל ענף; וסמן סיום בקצה התבנית.
כל אלמנט נושא גם עומק (רמת הקינון של הקבוצה שלו), את הקוונטיפיקטור (ספירת חזרה מינ' ומקס', אולי אינסופית), ושני מצביעי מעבר — next, "לאן ללכת אחרי שצרכנו את האלמנט הזה," ו־jump, "לאן לדלג" (משמש את סמן החילופין ואת מפרידי הענפים לשרשור ענפים, את תחילת הקבוצה כדי לנקוב בסוף הקבוצה שלה — קבוצה שהקוונטיפיקטור שלה מאפשר אפס מדולגת דרך ה־next של אותו סוף — ואת סוף הקבוצה כדי לחזור בלולאה אל הגוף).
עבור PATTERN ((A B)+) המערך המהודר נראה כך:
PATTERN ((A B)+) compiles to:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(פותח קבוצה; jump נוקב
ב־END שלו)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(סוגר קבוצה; jump חוזר בלולאה)
[4] FIN תבנית הושלמה
התבנית נקראת משמאל לימין דרך next, ו־jump מטפל בקצוות הלא־לינאריים. ב־idx 3, ה־jump של END מצביע חזרה אל idx 1, וכך הקוונטיפיקטור החיצוני הבלתי חסום עושה לולאה; ב־idx 0, ה־jump של BEGIN נוקב ב־END שלו ב־idx 3, ואם הקבוצה הייתה אופציונלית, הדילוג היה יוצא דרך ה־next של אותו END אל idx 4 מבלי להגיע ל־END. זמן הריצה לעולם אינו צריך לבנות גרף בזמן ריצה — הוא פשוט עוקב אחר שני המצביעים הללו תוך טיול במערך.
תכונות פר־אלמנט
מעבר לצורה, כל אלמנט נושא חמש תכונות לוגיות שמכוונות את התנהגות זמן הריצה במיקום זה:
- חששני
- הופך את סדר הרחבת הקוונטיפיקטור. קוונטיפיקטורים גרידיים מנסים "לולאה נוספת" לפני "יציאה"; קוונטיפיקטורים חששניים מנסים "יציאה" קודם. נישא על ידי המשתנה עבור
A+?; נישא על ידי BEGIN ו־END של הקבוצה עבור((…)+?). - בר־לולאה־ריקה
- נקבע על סופי קבוצות שגופן ניתן להאפסה (
(A? B?)+,(A | B*)+;(A?)*מוכפל תחילה ל־A*ואינו משאיר סוף קבוצה). מורה לזמן הריצה להוסיף יציאה מהירה לצד החזרה הרגילה ללולאה מתחת ל־min, כדי ששומר המחזור לא יהרוג התאמות לגיטימיות בקבוצות שיכולות להפיק חזרות ריקות. - מעדיף־ריק
- נקבע על סופי קבוצות שגופן מעדיף את ההתאמה הריקה, כמו ב־
(A?? B??){2}. מסדר את היציאה המהירה לפני החזרה ללולאה מתחת ל־min, היכן שהגרידיות של הקבוצה עצמה אינה קובעת דבר. - באזור־בר־ספיגה
- מסמן כל אלמנט שנמצא בתוך אזור הכשיר לספיגה — משמש את זמן הריצה כדי לעקוב אם המצב הנוכחי עדיין בטריטוריה בטוחה.
- נקודת־השוואה־לספיגה
- מסמן את האלמנט הספציפי שבו אמורות לרוץ השוואות הספיגה. עבור
A+פשוט הוא נופל על המשתנה; עבור קבוצה בלתי חסומה כמו(A B)+הוא נופל על סוף הקבוצה לבדו.
הפיצול בין "באזור" ל"נקודת השוואה" חשוב משום שספיגה הגיונית רק בנקודות שבהן חזרות נסגרות. בתוך הגוף של (A B)+, זמן הריצה נמצא באמצע חזרה והספירה טרם הגיעה לערכה הסופי לסבב הזה; השוואה כאן הייתה משמעה השוואת ערכים בלתי השוואים. המצב חייב להגיע לסוף הקבוצה לפני שזמן הריצה יוכל להחליט. התכונה הראשונה אומרת אפוא "אתה עדיין בטריטוריה ברת ספיגה"; השנייה אומרת "הגעת לנקודת ההשוואה — בדוק עכשיו."
ניתוח כשירות־לספיגה
שלב 6 של הקומפילציה הוא מה שמעניק לכלל "אותו גורל" מ־§2.5 את הצידוק שלו בזמן הקומפילציה. ההחלטה רב־שכבתית:
isAbsorbable(query):
אם מצב SKIP != SKIP PAST LAST ROW
→ return false
אם סוף frame != UNBOUNDED FOLLOWING
→ return false
אם DEFINE כלשהו תלוי ב־match_start
→ return false
עברו על המערך השטוח
מאלמנט 0 וסמנו אלמנטים
העונים על מקרה מבני
שלוש הבדיקות הראשונות הן ברמת השאילתה: הן מתאימות בדיוק לתנאי §2.7 (צד פלט: מצב SKIP), מסגרת חסומה (גבול שובר מונוטוניות), ו־§2.6 (צד נתונים: FIRST או LAST נושא־היסט ב־DEFINE). כשמי מהן נכשלת, הניתוח אינו קובע דגלים והספיגה מושבתת לרוחב השאילתה. כשכולן עוברות, הסיור מקבל ארבע צורות מבניות:
- מקרה 1 — משתנה בלתי חסום פשוט
-
כל חזרה היא בדיוק שורה אחת. הספירה של הקשר ותיק היא תמיד ≥ מזו של הקשר חדש בכל מיקום משותף.
A+,A*,A{2,∞} - מקרה 2 — קבוצה באורך קבוע, חיצוני בלתי חסום
-
לכל ילד
(A B)+,(A B{2})+,((A (B C){2}){2})+min == max, ולכן הגוף שקול סמנטית לצורתו הפרושה{1,1}—(A B{2})+מתנהג כמו(A B B)+. כל חזרה צורכת מספר קבוע של שורות; דומיננטיות הספירה עדיין תקפה. - מקרה 3 — קבוצה שגופה מתחיל במשתנה בלתי חסום
-
המשתנה הבלתי חסום המוביל הוא בעצמו בר־ספיגה (מקרה 1) ומגן על הקשרים ותיקים. הספיגה נעצרת ברגע שהמצב עובר את A — לשאר הגוף אין ערובה למונוטוניות, ולכן A מקבל את שני הדגלים, ה־BEGIN העוטף מקבל את דגל האזור, ו־B ו־END אינם מקבלים אף אחד מהם.
(A+ B)+,(A+ B){2} - מקרה 4 — חילופין
-
כל ענף, שאליו מגיעים דרך שרשרת המפרידים, נשפט בנפרד לפי המקרים שלעיל; סמן החילופין מקבל את דגל האזור כאשר ענף כלשהו כשיר.
A+ | B+,A+ | C D
המקרים המבניים שאינם מכוסים על ידי ארבע הצורות הללו מאלפים לא פחות. A B+ אינו ניתן לספיגה על ידי הכלל הנוכחי משום ש־A המוביל צורך שורה לפני שהחלק הבלתי חסום מתחיל, ולכן הקשרים שמתחילים שורה אחת זה מזה נמצאים במיקומים שונים בתוך הגוף הבלתי חסום. קוונטיפיקטורים חששניים כמו A+? מוצאים מההגדרה: כלל הספיגה מניח סמנטיקה גרידית, שבה התאמות ארוכות יותר בולעות קצרות יותר, וההתאמה החששנית הופכת את הכיוון.
התוצאה היא החלטה פר־אלמנט ולא פר־תבנית. תכנית שאילתה יחידה יכולה לאפשר ספיגה ל־A+ המוביל של תבניות כמו (A+ B+ C) או (A+ B+)+ — האחרונה היא פשוט מקרה 3 שמיושם על האלמנט המוביל שלה — ולהשבית עבור כל מה שאחריו; זמן הריצה פשוט מתייעץ עם תכונת נקודת ההשוואה על האלמנט של המצב הנוכחי בכל פעם שהוא שוקל מעבר ספיגה. ברגע שמצב נכנס לאזור לא־בר־ספיגה, הספיגה כבויה לצמיתות עבור אותו מצב — בדיוק מה ש־§2.5 ו־§2.6 צריכים שיהיה אמת ברמה האלגוריתמית.
3.3 ניווט — החלפת tuple של חריץ אחד
ביטויי DEFINE הם ביטויי SQL רגילים המוערכים מול שורה, אך הם רשאים לכלול PREV, NEXT, FIRST, או LAST — הפניות שמכוונות לשורות שונות. השורות עצמן כבר מאוחסנות ב־tuplestore של החלון; מה שה־executor עדיין צריך לנהל הוא חריץ ה־tuple שמכניזם הביטויים של SQL קורא ממנו, מאחר שהפניות עמודה בתוך הביטוי קשורות לחריץ בזמן התכנון. המימוש משתמש מחדש בחריץ ניווט יחיד לכל קריאת ניווט: החריץ מוחלף לפני הערכת הביטוי הפנימי ומוחזר אחריו, כך ששאר מכניזם ביטויי ה־SQL לעולם לא מבחין בהבדל.
המודל שה־executor רואה קטן: יש חריץ שורה נוכחית שמחזיק את השורה שביטוי DEFINE מוערך מולה, וחריץ ניווט שזמן הריצה יכול להפנות באופן זמני לשורה אחרת. סביב כל קריאת ניווט זמן הריצה מקים את חריץ הניווט, מעריך את הביטוי הפנימי כאילו היה קורא את השורה הנוכחית, ואז משחזר את השורה המקורית. פסאודו־קוד:
eval_navigation(call):
targetPos = compute_target_position(call)
אם targetPos מחוץ לטווח התקף שלו:
return NULL
שמור current_row_slot
אם targetPos != currentPos:
הבא שורה ב־targetPos
ל־nav_slot
הפנה את החריץ החיצוני ל־nav_slot
result = eval_inner_expression()
שחזר current_row_slot
העתק תוצאת by-ref אל מחוץ ל־nav_slot
return result
הטריק הוא שיש בדיוק חריץ אחד לשמור ולשחזר. הביטוי הפנימי — מה שלא יהיה, כולל אריתמטיקה, קריאות פונקציה, או הפניות עמודה אחרות — רץ מול החריץ המוחלף באמצעות אותו נתיב הערכה שהיה רץ מול השורה הנוכחית. ללא מעריך חלופי וללא חריץ לכל הפניה; כשהיעד הוא השורה הנוכחית, ההבאה וההחלפה מדולגות לגמרי. ההבאה מעתיקה את שורת היעד לחריץ הניווט (אלא אם החריץ כבר מחזיק אותה), ושלב השחזור מעתיק תוצאה המועברת לפי הפניה (pass-by-reference) לזיכרון פר־tuple, כדי שההבאה הבאה לא תוכל לשחרר אותה.
ניווט מורכב משוטח בזמן ה־parsing כדי שההחלפה עדיין תתרחש פעם אחת. PREV(FIRST(price)) מזוהה כניווט דו־שלבי — "לך לשורה הראשונה שהותאמה, ואז צעד שורה אחת אחורה" — ונשמר כקריאת ניווט יחידה מסוג מורכב. זמן הריצה מחשב את מיקום היעד בשני שלבים אך מבצע רק החלפת חריץ אחת כדי להביא את השורה הסופית:
compute_target_position(call):
# יחסית לשורה הנוכחית
PREV(n):
return currentPos − n
NEXT(n):
return currentPos + n
# יחסית להתאמה
FIRST(n):
return matchStart + n
LAST(n):
return currentPos − n
# מורכב: match-rel, ואז צעד
PREV(FIRST(n), m):
return (matchStart + n) − m
NEXT(FIRST(n), m):
return (matchStart + n) + m
PREV(LAST(n), m):
return (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − n) + m
אמת מול הטווח המתאים
(טווח התאמה ל־FIRST/LAST פנימי,
טווח partition לצעד החיצוני)
מטמון מיקומים קוצר מעקף את שליפת ה־tuplestore כשמספר קריאות ניווט באותה DEFINE מכוונות לאותה שורה — נפוץ בביטויים כמו price > PREV(price) AND volume > PREV(volume) שבהם שתי הקריאות מתפרשות לשורה הקודמת. המטמון שומר רק "מיקום שהובא לאחרונה", וההחלפה עצמה נשארת פעולה יחידה.
הסיווג של קריאות ניווט הוא תרומת ה־planner להחלטת הספיגה. ה־planner מטייל בכל ביטוי DEFINE וממיין כל משתנה לאחת משתי דליים, על פי אם כל ההקשרים יחשבו את אותו בוליאני באותה שורה, או שכל הקשר יחשב את שלו. הדלי קובע שני דברים בזמן ריצה: כמה פעמים המשתנה מוערך (פעם אחת משותפת, או פעם לכל הקשר מושפע — §3.5 פאזה 1), והאם ספיגת הקשרים אפשרית בכלל (§2.5 לעומת §2.6): משתנה יחיד התלוי בתחילת ההתאמה משבית אותה עבור התבנית כולה.
- ללא ניווט
PREV/NEXTבלבדLASTללא היסט- מורכב עם
LASTפנימי (ללא היסט)
LASTעם היסטFIRST(כל צורה)- מורכב עם
FIRSTפנימי - מורכב עם
LASTפנימי (עם היסט)
הסיווג מתבצע בזמן התכנון ונשמר לצד כל משתנה DEFINE, כך שזמן הריצה אינו מבזבז זמן על החלטה — הוא פשוט קורא את הדלי של כל משתנה כשהוא מעבד שורה.
תקציב שמירה
הניווט מגיע לשורות שמכניזם פונקציות החלון אחרת זרם מעבר להן. כדי לשמור על שורות אלו זמינות, ה־executor בנוי מעל tuplestore ששומר חלון נע של שורות אחרונות; השאלה היא כמה רחב החלון הזה חייב להיות. ה־executor מחשב אותו משני היסטים משלימים, ופותר כל היסט פעם אחת בכל סריקה (את הקבועים גם באתחול ה־executor, כדי ש־EXPLAIN רגיל יוכל להציגם):
- תקציב Lookback
- עד כמה אחורה מהשורה הנוכחית כל קריאת DEFINE עשויה להגיע.
- תקציב Lookahead מההתחלה
- ההגעה קדימה המינימלית (אחורה, כשהיא שלילית) מתחילת ההתאמה של ההקשר החי הוותיק ביותר — השורה המוקדמת ביותר שקריאת DEFINE כלשהי עשויה להזדקק לה.
בזמן ריצה סימון הגיזום של ה־tuplestore נקבע לפי המוקדם מבין שני המיקומים — השורה הנוכחית פחות תקציב ה־Lookback, ותחילת ההתאמה של ההקשר החי הוותיק ביותר ועוד תקציב ה־Lookahead. כל מה שלפני הסימון הזה אינו ניתן להגעה על ידי שום קריאת ניווט בשום הקשר חי, וה־tuplestore חופשי לזרוק אותו. שורות ה־Nav Mark ש־EXPLAIN מדווח (§3.7) — Lookback ו־Lookahead — הן שני התקציבים הללו, ולא שיאים נמדדים. כל אחת מודפסת רק כאשר ניווט כלשהו מזין אותה, ומוצגת גם ללא ANALYZE; היסט שערכו ידוע רק בזמן ריצה (פרמטר של generic plan, למשל) מודפס כ־runtime תחת EXPLAIN רגיל וכערכו שנפתר תחת EXPLAIN ANALYZE, ו־retain all (Lookback) או infinite (Lookahead) מסמנים היסט שגולש.
3.4 גבולות התאמה — SKIP, INITIAL, ומסגרת חסומה
תוצאת התאמה מתועדת כשני ערכים: השורה שבה ההתאמה מתחילה, ואורכה. התחלה שלילית פירושה שהמיקום טרם הוערך; ברגע שההתחלה נקבעה, שאילתות נוספות מול ה־executor — "האם השורה הזו בתוך התאמה?" — יכולות להשיב ב־O(1) על ידי בחינת הזוג. האורך מקודד את התוצאה: -1 לשורה שלא הותאמה, 0 להתאמה ריקה, ומספר השורות להתאמה ממשית. אורך אפס הוא תוצאה אמיתית, לא שגיאה: הוא מייצג תבנית שהתאימה מבלי לצרוך שורה כלשהי, מצב שה־executor חייב להבחין בינו לבין שורה שלא הותאמה וגם לבין "טרם נוסה התאמה במיקום זה."
פסוקית AFTER MATCH SKIP מחליטה היכן יתחיל ניסיון ההתאמה הבא. AFTER MATCH SKIP PAST LAST ROW עוברת לשורה שאחרי קצה ההתאמה, ומפיקה את הפלט הלא־חופף שרוב השאילתות רוצות, ומאפשרת את אופטימיזציית הספיגה.
AFTER MATCH SKIP TO NEXT ROW עוברת רק לשורה שאחרי תחילת ההתאמה, ומאפשרת התאמות חופפות; ה־planner לפיכך משבית את הספיגה עבור התבנית של אותו חלון כאשר מצב זה בתוקף.
שני יעדי הדילוג שהתקן מגדיר — AFTER MATCH SKIP TO FIRST var ו־AFTER MATCH SKIP TO LAST var — תלויים בהיסטוריית התאמה שהטלאי הזה אינו שומר. הם אינם נוכחים בדקדוק בכלל, ולכן ה־parser מעלה שגיאת תחביר כללית אם אחד מהם מסופק.
אותו דבר נכון לגבי SEEK, החלופה של המפרט ל־INITIAL. תחת SEEK, ניסיון התאמה שמתחיל בשורה R רשאי להצליח בכל שורה מ־R ועד סוף המסגרת, לא רק ב־R עצמה. הטלאי מממש רק את INITIAL: כל התאמה אפשרית מעוגנת בשורה ספציפית. ה־parser מעלה שגיאה אם SEEK מתבקש. מסגרות חסומות מקבלות טיפול משלהן — כשהמשתמש כותב ROWS BETWEEN CURRENT ROW AND N FOLLOWING במקום UNBOUNDED FOLLOWING, ה־executor מקצר כל הקשר שהתאמתו הגיעה לגבול על ידי כפיית כשל התאמה, והספיגה מושבתת מאחר שהגבול שובר את הנחת המונוטוניות שעליה נשענת הספיגה.
3.5 מנוע פר־שורה תלת־פאזי
דרייבר הפר־שורה של ה־executor נקרא על ידי מכניזם פונקציות החלון הסובב בכל פעם שצריך לדעת אם שורה נתונה שייכת למסגרת מותאמת. הדרייבר מוצא או יוצר את ההקשר עבור מיקום ההתחלה הנוכחי, ואז מניע את ה־NFA קדימה שורה אחר שורה — תוך איפוס מערך התאמה פר־משתנה ל"טרם הוערך" עבור כל שורה — עד שלא נותרו בהקשר הזה מצבים חיים או שהמחיצה מסתיימת. פרדיקטי DEFINE מוערכים בעצלתיים: משתנה מוערך בפעם הראשונה שמצב כלשהו צורך אותו, כך שמשתנה שאף מצב חי אינו בודק בשורה זו לעולם אינו מוערך. הצעד קדימה עצמו הוא שלוש פאזות בסדר קבוע — Match, Absorb, Advance — עטוף באותה לולאה חיצונית:
processRow(currentPos):
# שלב 1 — MATCH (התכנסות)
עבור כל context:
אם context הגיע לסוף ה־frame שלו:
אכוף mismatch (סיום מוקדם)
continue
אם matchStartRow שונה ממיקום
ההערכה המשותף:
אפסו משתני DEFINE תלויי
התחלת־התאמה ל־unevaluated (§3.3)
match(context, varMatched)
# שלב 2 — ABSORB
אם pattern הוא absorbable:
רעננו דגלים של כל context
absorb_contexts()
# שלב 3 — ADVANCE (התפצלות)
עבור כל context:
advance(context, currentPos)
אם הוא רשם התאמה
ו־SKIP PAST LAST ROW:
גזום הקשרים מאוחרים יותר
שמתחילים בתוך ההתאמה
הסדר אינו בחירה סגנונית. Match חייב לרוץ ראשון משום שהספיגה משווה ספירות שלאחר ההתאמה; הרצת Absorb לפני Match הייתה משווה מצבים שעומדים למות. Advance חייב לרוץ אחרון משום שהוא הפאזה היחידה שיוצרת מצבים חדשים — הוא מרחיב כל מצב ששרד דרך מעברי אפסילון עד שכל אחד מגיע למשתנה שממתין לשורה הבאה. הרצת Absorb לאחר Advance הייתה משמעה השוואת ממשיכים שכבר התפצלו, ופספוס הנקודה שבה המצבים ניתנים להשוואה בצורה הנקייה ביותר.
פאזה 1 — Match
Match היא פאזת "התכנסות": מצבים או שורדים עם ספירה מוגדלת, או מתים. נקודה דקה היא שעבור משתנים היושבים באזור בר־ספיגה, Match גם מבצעת מעט התקדמות קדימה, כדי ש־Absorb תוכל להשוות בצורה נקייה. תנאי הכיסוי מופעל רק בנקודת ההשוואה ברת־הספיגה — ה־END של הקבוצה הבלתי חסומה — ולכן מצבים שזה עתה התאימו משתני אמצע־חזרה (כמו B בתוך (A B)+) צריכים להיות מקודמים עד אותה נקודת השוואה במהלך Match עצמה; אחרת Absorb לא תמצא דבר כשיר להשוואה והאופטימיזציה לעולם לא תופעל.
match(context, varMatched):
עבור כל מצב ב־context:
elem = pattern[state.elemIdx]
assert ש־elem הוא משתנה
# advance עוצר רק במשתנים
אם varMatched[elem.varId] הוא
unevaluated:
העריכו את ה־DEFINE שלו כעת
אם לא varMatched[elem.varId]:
השלך מצב # ענף מת
continue
state.counts[elem.depth] += 1
# התקדמות־קדימה inline כך
# שהשלב הבא יוכל להשוות
# באלמנט נקודת ההשוואה
# במקום באמצע איטרציה.
אם elem הוא in-region אך לא
נקודת ההשוואה,
והגיע למניין המקסימלי,
ו־elem.next הוא group end:
טייל בשרשרת ה־END:
הגדל את מניין הקבוצה החיצונית
קדם state.elemIdx ל־END
המשך כל עוד in-region,
must-exit, ו־next הוא END
(עוצר בנקודת ההשוואה
או באלמנט שעדיין ניתן ללולאה)
סיור שרשרת ה־END הוא מה שהופך קבוצות מקוננות באורך קבוע לברות־ספיגה. ב־((A B){2})+, כש־B מגיע למקסימום שלו (B הוא {1,1}), הספירה של הקבוצה הפנימית חייבת לגדול; אם גם הספירה הזו מגיעה למקסימום שלה — וסוגרת את ה־{2} הפנימי — הספירה של הקבוצה החיצונית חייבת לגדול אף היא, וכן הלאה, עד שהמצב נוחת על נקודת הספיגה החיצונית ביותר — ה־END של הקבוצה החיצונית הבלתי חסומה (ה־+). ביצוע העבודה הזו ב־Match מאפשר ל־Absorb להשוות מול הקשרים שכבר אחדו את ספירותיהם שלאחר החזרה.
פאזה 2 — Absorb
מעבר ה־Absorb מטייל בהקשרים מהחדש ביותר (זנב) לוותיק ביותר (ראש). עבור כל הקשר בתהליך שניתן לספיגה מלאה, הוא סורק לאחור עבור הקשר ותיק יותר בתהליך שמכסה אותו, ומשחרר את החדש אם נמצא. מאחר שהקשרים נשמרים בסדר היצירה וכל שורה יוצרת לכל היותר הקשר אחד, "חדש יותר" ו"ותיק יותר" באמת אומרים "התחיל מאוחר יותר" ו"התחיל מוקדם יותר."
absorb_contexts():
עבור ctx מהזנב אחורה:
אם ctx הסתיים
או יש לו מצב לא־ספיג
או מחזיק התאמה רשומה:
דלג
עבור older מ־ctx.prev אחורה:
אם older הסתיים
או אין לו מצב ספיג:
דלג
אם covered(older, ctx):
free(ctx)
רשום אורך ספיגה
break
covered(older, newer):
עבור כל מצב ב־newer:
elem = pattern[state.elemIdx]
אם elem אינו נקודת ההשוואה:
return false
אם אין מצב ב־older עם:
אותו elemIdx
ו־isAbsorbable
ו־older.counts[depth]
>= newer.counts[depth]:
return false
return true
שתי החלטות קטנות נובעות מכך. הראשונה היא שבדיקת הכיסוי דוחה מיידית אם מצב כלשהו בהקשר החדש יושב במקום אחר מנקודת השוואה — השוואה בנקודות שאינן נקודות הכרעה לא תהיה השוואה משמעותית.
השנייה היא זוג הדגלים האסימטרי על כל הקשר: has-absorbable-state משיב "האם ההקשר הזה יכול לבלוע הקשר חדש יותר?" והוא מונוטוני (יכול לעבור רק true→false כשמצבים מתים), בעוד all-states-absorbable משיב "האם ההקשר הזה יכול להיבלע?" והוא דינמי (חוזר ל־true כשמצב לא־בר־ספיגה מוסר) עד שההקשר רושם התאמה, מה שמקבע אותו על false — ספיגה הייתה משחררת התאמה שאף הקשר סופג אינו יכול לשחזר. שני הדגלים נבדקים בזמן קבוע לפני שסריקת הכיסוי בכלל מתחילה, כך שהספיגה משלמת את מלוא עלותה רק על הקשרים שיש להם סיכוי אמיתי להיבלע.
פאזה 3 — Advance
Advance היא פאזת ה"התפצלות": כל מצב ששרד מורחב דרך מעברי אפסילון עד שכל ענף מגיע למשתנה שממתין לשורה הבאה או לסמן ה־FIN. ההרחבה היא בעומק תחילה, והסדר שבו ענפים אחים נסרקים הוא מה שגורם לכלל ההעדפה של התקן באמת לקבל תוקף — הענף הראשון לקסיקלית מתווסף תמיד ראשון, ושלב הדה־דופליקציה בעת הוספת מצב משליך בשקט תוספות מאוחרות שקולות.
advance(context, currentPos):
שלוף את כל המצבים הנוכחיים;
בנה מחדש את ctx.states מאפס
עבור כל מצב בסדר לקסיקלי:
נקה את bitmap הביקורים
advance_state(state) # DFS
# העדפה: ברגע ש־DFS מגיע ל־FIN,
# המצבים הנותרים פחות מועדפים
# וניתן להשליך אותם.
אם FIN הושג ונותרו מצבים:
שחרר את היתר
break
advance_state(state):
הלך דרך state.elemIdx,
רקורסיה דרך:
ענפי ALT (לפי סדר, עוצרים
ברגע ש־FIN נרשם),
BEGIN (כניסה לקבוצה; ועוד מסלול
דילוג אופציונלי אם min = 0),
END (loop back / exit / fast-forward —
ראו למטה),
FIN (רישום matchEndRow,
שמירת matchedState, וסימון
ההקשר כך שהקשרים מאוחרים
יותר בתוך טווח המועמד
ייגזמו — ראו למטה),
עצירה בכל משתנה שנפגש:
הוסף מצב ל־ctx.states
(דה־דופליקציה לפי elemIdx + counts)
תיעוד מצב שהגיע ל־FIN עושה יותר מאשר רק לסמן את ההתאמה המועמדת. תחת AFTER MATCH SKIP PAST LAST ROW, ההתאמה הבאה הניתנת לדיווח חייבת להתחיל בקפדנות אחרי הנוכחית — ולכן ברגע ש־Advance סיימה עם ההקשר שרשם מועמד, כל הקשר עוקב ששורת ההתחלה שלו נופלת בתוך טווח המועמד נגזם באותה שורה, גם אם ההקשר שפגע ב־FIN ממשיך לחפש התאמה ארוכה יותר באמצעות חזרה גרידית.
הגיזום בטוח משום שלא משנה איך החיפוש הזה ייגמר (התאמה ארוכה יותר תחליף את המועמד, או שהמועמד יישאר), כל ההקשרים הגזומים התחילו בתוך טווח שההתאמה הבאה הניתנת לדיווח חייבת לדלג מעבר אליו, ולכן לעולם לא היו יכולים להפיק פלט משלהם.
זהו שלב הגיזום בזמן FIN שבין הקשרים. בתוך ההקשר, FIN חותך גם עבודה נחותה לקסיקלית: Advance משליכה את המצבים שנותרו בתור (כפי שתואר מוקדם יותר בחלק זה), ובתוך DFS יחיד כל נתיב פחות מועדף — ענפי ALT מאוחרים יותר, האחר מבין נתיבי הדילוג והכניסה של BEGIN, נתיב הכניסה של משתנה חששני, האחר מבין נתיבי הלולאה והיציאה של END — נעצר ברגע שהתאמה נרשמת, כך ש־advance אחד רושם לכל היותר התאמה אחת.
הלוגיקה הפר־אלמנט המסובכת ביותר שוכנת במטפל ה־END. כשספירת החזרות של קבוצה מתחת לחסם התחתון, זמן הריצה חייב לחזור בלולאה; כשהיא בחסם העליון או מעליו, הוא חייב לצאת; ביניהם, שתי האפשרויות תקפות והגרידיות של הקוונטיפיקטור מחליטה במה לנסות תחילה:
advance_end(state, elem):
count = state.counts[elem.depth]
אם count < elem.min:
חזור בלולאה אל הגוף
אם elem הוא empty-loopable:
# גוף nullable, ראו §3.2
שכפל גם מצב fast-forward
שיוצא מהקבוצה כש־
count מסופק
(fast-forward ראשון אם
הגוף מעדיף ריק; הנתיב
השני מושלך אם הראשון
הגיע ל־FIN)
אחרת אם count >= elem.max:
אפס את counts בעומק זה
צא דרך next
(END→END: הגדל את count
של END החיצוני)
אחרת:
# min <= count < max: התפצלות
בנה מצב יציאה
(counts בעומק זה אופסו)
אם greedy:
קודם loop
אם loop הגיע ל־FIN:
השלך את ה־exit
# העדף ארוך יותר
אחרת exit שני
אחרת (reluctant):
קודם exit
אם exit הגיע ל־FIN:
השלך את ה־loop
# העדף קצר יותר
אחרת loop שני
כל מצב שמתווסף להקשר עובר בדיקת דה־דופליקציה שמשווה את מיקומו ואת ספירותיו לרשימת המצבים הקיימת. מאחר ש־Advance מעבדת ענפים בסדר DFS, המצב מהענף הראשון של כל חילופין נוחת ראשון — וכל ענף מאוחר יותר שמפיק את אותו מיקום ואותן ספירות נדחה בעת ההוספה. זה בדיוק מה שכלל הסדר הלקסיקלי מ־§2.4 דורש, מיושם בתחתית זמן הריצה ללא מעבר נפרד.
קבוצות בנות־לולאה־ריקה
מקרה דק שזמן הריצה חייב לפרק הוא הקבוצה הניתנת להאפסה — קבוצה שגופה יכול להתאים אפס שורות מאחר שכל ילד של הגוף הוא בעצמו אופציונלי. תבניות כמו (A? B?)+ ו־(A | B*)+ בעלות תכונה זו: בהתאם לנתונים, הגוף יכול להשלים חזרה מבלי לצרוך שום שורה כלל. (ילד אופציונלי יחיד כמו (A?)* נכתב מחדש ל־A* בזמן הקומפילציה ואינו משאיר קבוצה אחריו.) זה בסדר עקרונית, אבל זה יוצר סיכון אמיתי להרחבת האפסילון של ה־NFA. אם הגוף מפיק התאמה ריקה, אלמנט ה־END חוזר בלולאה אל תוך הגוף (ה־jump שלו הוא הילד הראשון של הקבוצה), הגוף שוב מפיק התאמה ריקה, מגיע שוב ל־END, וכן הלאה. ללא משהו שיעצור זאת, ה־DFS של Advance לעולם לא יסתיים.
השומר מוחלט בזמן הקומפילציה ומופעל בזמן הריצה. בכל פעם שה־planner רואה קבוצה שגופה ניתן להאפסה, הוא מתייג את אלמנט ה־END של אותה קבוצה כ־בר־לולאה־ריקה. זמן הריצה מחזיק בִּיטמַפ ביקורים, שנמחק לפני הרחבת ה־DFS של כל מצב, ובו מסומנים רק ה־END המתויגים הללו — שום דבר אחר אינו יכול ליצור מחזור, משום שכל חזרה אחרת ללולאה כבר צרכה שורה. הגעה ל־END מסומן פירושה שהגוף זה עתה גזר חזרה ריקה, והמצב אינו מושלך: בחסם התחתון או מעליו הוא יוצא שם מהקבוצה (חזרה ריקה עוצרת את הקוונטיפיקטור), ומתחתיו המצב ממשיך אל החזרה הרגילה ללולאה, כך שכל הגעה ריקה עדיין מעלה את הספירה עד שהיא מגיעה ל־min. ניקח את (A? B?){2,3} כששני המשתנים אינם מתאימים בשום מקום בזרם השורות:
iter 1: A? B? מתאימים אפס שורות
→ END, count = 1 (מתחת ל־min)
END כבר מסומן (בכניסה
לקבוצה), אך מתחת ל־min:
→ חזרה בלולאה אל A?
iter 2: A? B? מתאימים אפס שורות
→ END, count = 2 (מקיים min)
END כבר מסומן, ב־min:
→ צא מהקבוצה
צא בהתאמה באורך אפס
מתחת לחסם התחתון, התג של לולאה ריקה מורה גם למטפל ה־END לשכפל מצב fast-forward נוסף לצד נתיב החזרה ללולאה הרגיל:
advance_end (count מתחת ל־min):
נתיב החזרה ללולאה:
חזור בלולאה אל הגוף
(משאיר את הדלת פתוחה
להתאמה אמיתית, לא־ריקה
באיטרציה הבאה)
אם elem הוא empty-loopable:
נתיב fast-forward:
אפס את count של עומק זה
צא מהקבוצה דרך next,
בהתייחסות לאיטרציות הנדרשות
הנותרות כהתאמות ריקות
שני הנתיבים ממלאים תפקידים משלימים. החזרה ללולאה היא מה שתופס את המקרה שבו לגוף עדיין יש התאמות אמיתיות להפיק מאוחר יותר — למשל, ב־(A? B?){2,3} שאחריו נתונים שבהם A מתאים רק בשורות מאוחרות יותר, החזרה ללולאה היא מה שמאפשר לחזרות השנייה והשלישית למצוא התאמות לא־ריקות. ה־fast-forward יוצא מהקבוצה מיד, מכריז "שאר החזרות הנדרשות ריקות", ומאפשר להתאמה להצליח עם גוף באורך אפס. הגוף, ולא הגרידיות של הקבוצה עצמה, קובע את הסדר: ה־fast-forward הולך ראשון בדיוק כאשר הגוף מעדיף את ההתאמה הריקה (גוף חששני כמו (A?? B??)), ואם הנתיב הראשון מגיע ל־FIN השני מושלך, כך שנתיב פחות מועדף אינו יכול להחליף את ההתאמה המועדפת. בדיקת הדה־דופליקציה בעת ההוספה מונעת מכל אחד מהנתיבים להוליד יותר מצבים מחלקו.
מעבר לשומר המחזור, טריק התחלה אחד נוסף מבהיר תוצאות אפס־שורות בתחילת הקשר. שלב יצירת ההקשר בכל שורת התחלה אפשרית מריץ advance ראשוני דרך מעברי אפסילון לפני שצורכים שורה כלשהי, באמצעות מיקום שורה אחת לפני ההתחלה האמיתית. כל נתיב שמגיע לסמן ה־FIN רק דרך מעברי אפסילון — מבלי לצרוך שורה — מפיק לפיכך מיקום סיום קטן ממיקום ההתחלה; הקואורדינטה השלילית הזו, יחד עם השאלה אם FIN אכן הושג, מקודדת את ההבדל בין התאמה ריקה (התאמה באורך אפס שהתקבלה) לבין התחלה ללא התאמה ללא צורך בדגל נפרד.
3.6 כיצד מרחב המצבים נשאר חסום
שמירת זמן הריצה חסום אינה תוצאה של אופטימיזציה יחידה. היא ההשפעה המצטברת של קבוצה רב־שכבתית של כללי גיזום, כל אחד תופס סיבה אחרת לגדילת מרחב מצבים בנקודה אחרת במחזור הפר־שורה. חלקם מוחלטים בזמן הקומפילציה ופשוט נצרכים בזמן ריצה; אחרים מופעלים דינמית. חלקם הורגים מצבים יחידניים; אחרים הורגים הקשרים שלמים. החלקים לעיל הציגו כל אחד מהם בהקשרו; הטבלה למטה מציבה אותם כולם בעמוד אחד.
- פרדיקט שנכשל Match
- מצבי משתנים שה־DEFINE שלהם הוערך לשקר בשורה הנוכחית — ענפים מתים.
- קידום שרשרת END בשורה Match
- משתנים שהגיעו לספירת המקס' שלהם והיו אחרת משאירים את המצב באמצע חזרה; מקודמים דרך סופי קבוצות באורך קבוע כדי שהספיגה תוכל להשוות בנקודה הנכונה.
- ספיגת הקשר Absorb
- הקשרים חדשים שכל מצב שלהם יושב בנקודת השוואה ומכוסה על ידי מצב בר־ספיגה של הקשר ותיק באותו אלמנט עם ספירה גדולה או שווה — ראו §2.5 לכלל הרעיוני, §3.2 לכשירות בזמן הקומפילציה, §3.5 לבדיקה הפר־זוגית.
- דה־דופליקציה של מצבים Advance
- מצבים שהושגו דרך ענפי DFS שונים שמסתיימים באותו מיקום עם אותן ספירות — רק הראשון (המוקדם לקסיקלית) שורד; שקולים מאוחרים יותר מושלכים בשקט, וזו גם הדרך שבה כפיית ההעדפה מתממשת (§2.4).
- סיום מוקדם ב־FIN (בתוך הקשר) Advance
- מצבים שעדיין ממתינים בתור ה־DFS כשענף אחד מגיע ל־FIN — לפי הסדר הלקסיקלי, כל המצבים הנותרים פחות מועדפים וניתן להשליך אותם מיד.
- גיזום התאמת מועמד (בין הקשרים) Advance
- הקשרים אחרים ששורת ההתחלה שלהם נופלת בתוך טווח ההתאמה המועמדת — ההקשר שפגע ב־FIN רשאי עדיין להמשיך לחפש התאמה ארוכה יותר (חזרה גרידית), אך תחת
AFTER MATCH SKIP PAST LAST ROWכל הקשר בתוך טווח המועמד כבר אינו יכול להפיק פלט שניתן לדיווח, ללא קשר לאופן סיום החיפוש, ונגזם ברגע ש־Advance סיימה עם ההקשר שרשם את המועמד. - שומר מחזור Advance
- הרחבות אפסילון שמגיעות ל־END של קבוצה הניתנת להאפסה שכבר סומן באותו DFS (סומן בכניסה דרך BEGIN, או בהגעה מוקדמת יותר) — היו אחרת מסתובבות לנצח; בחסם התחתון או מעליו המצב יוצא שם מהקבוצה, ומתחתיו הוא ממשיך בלולאה.
- Fast-forward של לולאה ריקה Advance
- מתחת לחסם התחתון של קבוצה הניתנת להאפסה, נתיב נוסף שיוצא מהקבוצה כשהחזרות הנדרשות הנותרות מוכרזות ריקות, ומסודר ביחס לחזרה ללולאה לפי ההעדפה של הגוף.
- חיתוך מסגרת חסומה Match
- הקשרים שהתאמתם הגיעה לחסם העליון של המסגרת שהגדיר המשתמש — נכפים להיכשל כדי שלא יוכלו להתרחב מעבר לכך (§3.4).
קריאת הערכים לפי תג הפאזה שלהם משרטטת את מחזור החיים של הקשר: הגיזום מופעל בכל שורה דרך שלוש הפאזות העיקריות (Match, Absorb, Advance). קריאת התיאורים, לעומת זאת, מקבצת את הכללים לפי מה שהם מכוונים אליו: ענפים מתים, הקשרים מיותרים, מצבים שקולים, לולאות אינסופיות, והרחבת יתר מעבר לגבולות שהמשתמש הטיל.
שום כלל יחיד לא היה מספיק. ה־fast-forward של לולאה ריקה לבדו לא היה עוצר לולאות אפסילון אינסופיות; הספיגה לבדה הייתה מאחדת יתר על המידה כש־DEFINE מפנה לתחילת ההתאמה; דה־דופליקציה לבדה לא הייתה מסירה הקשרים מיותרים, רק מצבים מיותרים. זמן הריצה נשאר לינארי במקרים החשובים — PATTERN (A+ B+ C+ D) על 100,000 שורות, הבנצ'מרק של פאנל ③ בפוסטר — רק משום שכל שכבה תופסת את מה שהשכבות שמעליה מפספסות. המקור מתעד מקרים שהשכבות אינן תופסות: הדה־דופליקציה שומרת בנפרד מצבים הנבדלים רק בספירות שמעל min, ולכן (A{2,} B)+ C כש־C לעולם אינו אמת מחזיק Θ(n²) מצבים בשיא ויוצר Θ(n³) מהם (37 שניות על פני 320 שורות), ורצף של חילופין שכולם ניתנים להאפסה נמנה נתיב אחר נתיב, ולכן (A?|B?){30} לוקח יותר מחצי שעה.
3.7 פלט EXPLAIN
EXPLAIN ANALYZE על שאילתה עם RPR חושף סטטיסטיקות ברמת ה־NFA שאינן נוכחות בפונקציות חלון רגילות. בפורמט טקסט הן נפלטות לצד אופרטור החלון, אחרי שורת ה־Pattern:, שורות Nav Mark כלשהן (ש־EXPLAIN רגיל מציג גם הוא) ושורת ה־Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(each only when DEFINE uses navigation
that feeds it)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
N skipped (len min/max/avg)
(second NFA line only when either
count is nonzero; a zero count
prints without its (len ...))
פורמטים שאינם טקסט פולטים כל מונה כמאפיין נפרד. Peak ו־total הם תיעוד ישיר של זמן הריצה: כמה מצבים אי פעם היו חיים בו־זמנית, כמה נוצרו במהלך חיי השאילתה, וכמה מוזגו על ידי דה־דופליקציה; pruned סופר הקשרים שנכשלו אחרי שורה אחת. ההיסטוגרמות של אורך ההתאמה מפרידות בין ארבע תוצאות — התאמות מוצלחות, ניסיונות התאמה שנכשלו אחרי יותר משורה אחת (mismatched), הקשרים שנספגו, והקשרים ששוחררו על ידי AFTER MATCH SKIP PAST LAST ROW משום שהתחילו בתוך התאמה רשומה (skipped) — ודיווח עליהן עם min/max/avg הופך פתולוגיות ביצועים לגלויות במבט חטוף: הרצה תקינה מראה את רוב ההקשרים כ־matched או absorbed, עם אורכי mismatched קטנים.
שני מוני ה־Nav Mark מדווחים על תקציב השמירה של ה־tuplestore ש־§3.3 גוזרת מ־DEFINE. Lookback הוא ההגעה האחורה העמוקה ביותר מהשורה הנוכחית על פני PREV, LAST עם כל היסט (כולל ברירת המחדל 0), והטפסים המורכבים עם LAST פנימי; Lookahead הוא ההגעה קדימה המינימלית (שלילית כשהיא מביטה לפני תחילת ההתאמה) הנמדדת מתחילת ההתאמה של ההקשר החי הוותיק ביותר, נתרמת על ידי FIRST והטפסים המורכבים עם FIRST פנימי.
כל מונה מודפס כמספר שלם קבוע כשההיסט הוא קבוע, "runtime" כשההיסט הוא ביטוי לא־קבוע הידוע רק בכל סריקה, ועבור Lookback בלבד, "retain all" כשההיסט גולש; Lookahead שגולש מודפס כ־"infinite". כל שורה נפלטת רק כאשר ניווט כלשהו ב־DEFINE מזין אותה, ושתיהן מופיעות גם תחת EXPLAIN רגיל: היסטים קבועים מוכרעים באתחול ה־executor, בעוד שהיסט הידוע רק בזמן ריצה (פרמטר של generic plan, למשל) מודפס שם כ־"runtime", וכמספר השלם שנפתר תחת EXPLAIN ANALYZE.
יחד, המונים הללו מאפשרים לאתר באגים בביצועי RPR מבלי לחבר gdb ל־backend.
מעבר למונים, EXPLAIN מדפיס שורת Pattern: הבנויה ממערך האלמנטים המהודר, ולכן היא מציגה את התבנית לאחר הכתיבות־מחדש של זמן הקומפילציה (PATTERN (A A) מוסבר כ־a{2}) ונושאת את סמני הספיגה # (נקודת השוואה) ו־~ (אזור בר־ספיגה); DEFINE ואופציית AFTER MATCH SKIP אינם מוצגים. שחזור הפסוקיות כפי שנכתבו, כולל קוונטיפיקטורים חששניים, חזרת קבוצות ואופציית הדילוג, הוא תפקידה של pg_get_viewdef(), שמשקיעה מאמץ מסוים כדי להפוך את הסיבוב הזה ליציב כך ש־pg_dump ו־pg_upgrade יוכלו לשמר אובייקטי RPR ללא סחיפה סמנטית — חבילת הרגרסיה תחת rpr_explain מאמתת זאת מקרה אחר מקרה (ראו §4).
§4. בדיקות — מפת כיסוי
הטלאי מגיע עם חמש חבילות רגרסיה שיחד מפעילות כל שכבה שתוארה ב־§3 — בערך 22,000 שורות SQL, כל חבילה ממוקדת בעניין שונה. הפיצול מכוון: שמירת ענייני ה־parser, נכונות זמן הריצה, אינטראקציות ה־planner ועיצוב הפלט בקבצים נפרדים מקלה על איתור כשלים, ומונעת משינוי לא קשור בשכבה אחת לבטל בטעות בדיקות בשכבה אחרת. חמש החבילות הן:
- rpr
- שילוב בפסוקית WINDOW — תרחישי חלון מציאותיים על נתוני מניות סינתטיים (תבנית V, תבנית W, עליות רצופות, היפוכים), ובנוסף סמנטיקת ניווט ושגיאות של הגבלות DEFINE.
- rpr_base
- שכבת ה־parser — קבלת מילות מפתח, צורות תחביר, קוונטיפיקטורים, ניתוח ניווט, הודעות שגיאה, ויציבות סיבוב pg_dump/pg_upgrade; ובנוסף שכבת planner — אופטימיזציית תבניות, דגלי ספיגה, נסיגה מאופטימיזציה, שילוב ב־planner.
- rpr_nfa
- זמן הריצה של ה־NFA — הלולאה התלת־פאזית, ספיגה בכל צורה ברת־ספיגה, ומקרי קצה במחזור החיים של ההקשר.
- rpr_explain
- עיצוב פלט — סטטיסטיקות NFA, deparse של תבנית, ציטוט מזהים, יציבות פורמט בין טעינות מחדש.
- rpr_integration
- אינטראקציות planner — שומרים שמונעים מאופטימיזציות חלון לא קשורות לשבש את סמנטיקת RPR.
4.1 rpr — תרחישים מקצה לקצה
חבילת התרחישים היא הפנים הציבוריות של מערך הבדיקות: היא משתמשת במערך נתוני מחירי מניות סינתטי בן כ־1,600 שורות ומריצה מולו שאילתות מציאותיות — התאוששות תבנית V, תבנית W (תחתית כפולה), עליות וירידות רצופות, תבניות היפוך, מחיצות רב־סימוליות. תרחישים אלה הם הבדיקות היחידות שהקלט והפלט שלהן קוראים כמו שאילתות שמשתמש עשוי באמת לכתוב; שאר הקובץ, כמו החבילות האחרות, רדוקטיבי — קינון PREV/NEXT ושגיאות היסט לא־קבוע, כללי הפניה ב־DEFINE, וסמנטיקת היסטי ניווט.
מאחר שהשאילתות הללו משלבות כל שכבה (parser, planner, executor, EXPLAIN), כשל יחיד ב־rpr נדיר שיגיד לכם היכן הבאג חי. ארבע החבילות שאחריו הן הביסקציה: כשל ב־rpr בתוספת rpr_base שעובר שולל את ה־parser; בתוספת rpr_nfa שעובר מצמצם זאת לצורות נתונים ספציפיות לתרחיש; בתוספת rpr_integration שעובר שולל הפרעת planner; וכל סחיפת deparse תופיע ב־rpr_explain.
4.2 rpr_base — משטח ה־parser
חבילת הבסיס היא הגדולה ביותר, והיא הגדולה ביותר מסיבה: היא אחראית להוכיח שכל פיסת תחביר חוקית מ־§1.2 אכן מנותחת, שכל פיסה לא־חוקית מ־§1.3 נדחית עם שגיאה שימושית, ושכל צורה מקובלת שורדת סיבוב סריאליזציה. רובה בנוי כקטעים קטנים וממוקדים — אחד לכל תכונה תחבירית — ולא כשאילתות מציאותיות ארוכות, מאחר שהמטרה היא כיסוי ולא ריאליזם תרחישי. חלק שני, שכבת ה־planner, מכסה אופטימיזציית תבניות, הצגה וניתוח של דגלי ספיגה, נסיגה מאופטימיזציה, ושילוב ב־planner (שאילתות משנה, צירופים, פעולות קבוצה, מיון וקיבוץ).
בדיקות הסריאליזציה ראויות לתשומת לב מיוחדת. אובייקטי RPR (תצוגות, תצוגות ממומשות, פלט pg_dump) חייבים לעבור סיבוב דרך ייצוג הקטלוג ללא סחיפה סמנטית, כולל דקויות כמו דגל החששנות על קוונטיפיקטור או הצורה המדויקת של ביטוי ניווט מורכב. קבוצה קטנה של אובייקטים ספציפיים לסריאליזציה (התצוגות rpr_serial_v* והטבלאות שמאחוריהן) נשארת במכוון בסוף ההרצה, כדי שתשתית הרגרסיה הסובבת תוכל לקלוט אותם ולהפעיל מולם pg_dump ו־pg_upgrade. שאר הפיגומים של הבדיקה מוסרים כרגיל. פגמים כמו דגל חששני שאובד בין deparse ל־re-parse צצים רק כשהסיבוב מופעל מקצה לקצה.
4.3 rpr_nfa — מנוע זמן הריצה
זוהי החבילה שמפעילה כל מנגנון שתואר ב־§3.5 וב־§3.6. הבדיקות שלה עוקבות אחר תבנית עקבית: שורות VALUES מוטמעות הנושאות מערך של שמות משתנים שמכריז אילו משתני DEFINE מתאימים בכל שורה, יחד עם תבנית שבוחנת התנהגות זמן ריצה ספציפית. ניב המערך מנתק את בדיקת זמן הריצה ממכניזם הערכת DEFINE — מה שנבדק הוא "בהינתן שהמשתנים האלה מתאימים כאן, האם לולאת ה־NFA מפיקה את טווח ההתאמה הצפוי?" ולא "האם מעריך ביטוי DEFINE מחשב נכונה את הבוליאנים האלה?" מעריך ה־DEFINE נבדק במקום אחר (rpr_base לניתוח, rpr להתנהגות מקצה לקצה).
התקנת בדיקה אופיינית נראית כך — עמודה של מערכי שמות־משתנה שכל ערך אומר אילו משתני DEFINE מופעלים באותה שורה, ותבנית שפסוקיות ה־DEFINE שלה בודקות את השמות הללו ישירות:
SELECT id, flags, first_value(id) OVER w AS ms, last_value(id) OVER w AS me FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A','B']), (3, ARRAY['A','B']), (4, ARRAY['B']), (5, ARRAY['_']), (6, ARRAY['A'])) AS t(id, flags) WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING INITIAL PATTERN (A+ B+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));
קריאת עמודת המערך כלפי מטה היא קריאת תרחיש הבדיקה ישירות. שורות 2 ו־3 נושאות את שני השמות — A ו־B שניהם מופעלים שם, ולכן ל־NFA יש בחירה אמיתית היכן לעבור מהזרוע של A לזרוע של B. ההתאמה הצפויה (A בשורות 1–3 ואחריה B בשורה 4, תחת ההעדפה הגרידית של התקן) קבועה לפי הדגלים הללו לבדם, ללא הערכת ביטוי בעלת משמעות כאן — = ANY היא רק השכבה הטריוויאלית שחושפת את עמודת המערך ל־DEFINE, לא מה שהבדיקה מפעילה. כתיבת אותו תרחיש עם פרדיקט מספרי (price > PREV(price) וכדומה) הייתה מבלבלת את בדיקת ה־NFA עם התנהגות מעריך הפרדיקטים; הניב של המערך מפריד בין השניים בצורה נקייה, וכשל כאן מצביע ישירות על לולאת ה־NFA.
כיסוי הספיגה יסודי במיוחד, מאחר שהספיגה היא האופטימיזציה שהכי סביר שתפיק תשובות שגויות בשקט אם תופעל כשלא צריך. הבדיקות מכסות כל צורה מניתוח המקרים של §3.2:
- משתנה בלתי חסום פשוט (
A+) — הקיפול הקאנוני של N־ל־1; - קבוצות באורך קבוע (
(A B)+,(A B{2})+, מקונן בשלוש רמות((A (B C){2}){2})+); - משתנה בלתי חסום מוביל עם סיומת קבועה (
A+ B) — רקA+המוביל נושא דגלי ספיגה, הסיומת לא; - ספיגה פר־ענף בתוך חילופין (
B+ C | B+ D); - מספר משתנים בלתי חסומים (
A+ B+) — רק המוביל בר־ספיגה; - קוונטיפיקטורים חששניים (
A+?) — מאומתים כמוצאים מהספיגה; - בלתי חסום שאינו מוביל (
A B+) — מאומת כמוצא.
מעבר לספיגה, החבילה מכסה את מחזור החיים של ההקשר: הקשרים חופפים תחת AFTER MATCH SKIP TO NEXT ROW, ניקוי הקשרים שנכשלו באמצע הזרם, נעילת הקשרים לא־שלמים בסוף המחיצה, והקשרים הנפגשים לאחר שהתאמה מועמדת כבר נרשמה בהקשר הראש. כל אחד מאלה ממופה לכלל גיזום ספציפי ב־§3.6, והבדיקות נכתבות לכשול בקול אם הכלל מתפקד לא נכון (בין אם על ידי השארת הקשרים מיותרים בחיים, או על ידי הריגת הקשר שהיה אמור להפיק פלט).
4.4 rpr_explain — יציבות פלט
פלט EXPLAIN הוא חלק מההסכם המופנה למשתמש — כלים של צד שלישי (לוחות מחוונים לניטור, מגרדי לוגים) מנתחים אותו, ושינויים שנראים קוסמטיים יכולים לשבור אותם. חבילת rpr_explain מאמתת שלושה דברים:
- מוני NFA מופיעים במקום הנכון — סטטיסטיקות פר־WindowAgg (peak/total/merged של מצבים, peak/total/pruned של הקשרים, היסטוגרמות אורך של matched/mismatched/absorbed/skipped) מופיעות תחת
EXPLAIN ANALYZEבטקסט, JSON ו־XML עם התוויות המתועדות, ו־Nav Mark Lookback ו־Lookahead מופיעים בדיוק כאשר ניווט ב־DEFINE מזין אותם. - תבניות עוברות deparse נכון — כל צורת קוונטיפיקטור, כולל וריאנטים חששניים וצורות חסומות; כל חילופין; כל קבוצה; כל צורת
AFTER MATCH SKIP;INITIAL; קריאות ניווט עם היסט; ניווט מורכב. הטקסט שעבר deparse חייב לעבור סיבוב חזרה דרך ה־parser ללא שינוי. - ציטוט מזהים נכון — משתני תבנית וביטויי DEFINE נפלטים עם אותם כללי ציטוט כמו מזהי SQL רגילים, כך ששמות משתנים יוצאי דופן לא ישברו את פלט
pg_dump.
כמו rpr_base, חבילה זו משאירה במכוון את האובייקטים שלה במקום בסוף ההרצה, כדי שכיסוי pg_dump ו־pg_upgrade יתפרס גם על ארטיפקטים בצד ה־explain.
4.5 rpr_integration — אינטראקציות planner
ל־planner של PostgreSQL יש אופטימיזציות רבות הפועלות על שאילתות חלון — נירמול מסגרת, דחיפת תנאי ריצה כלפי מטה, דה־דופליקציה של חלונות זהים, היטל פלט לא־בשימוש, מעברים הופכיים של אגרגציה נעה — וכל אחת מהן תוכננה בלי לחשוב על RPR. רובן אינן בטוחות לישום כשלחלון יש פסוקית PATTERN: המסגרת היא חלק מהסכם ההתאמה, הפלט המותאם כבר אינו מונוטוני באף דרך מובנת מאליה, ושני חלונות עם אותו מפרט אך DEFINE שונה מפיקים תוצאות שונות באמת. חבילת האינטגרציה מאמתת כיצד כל אחת מהאופטימיזציות הללו מתייחסת לחלונות RPR — רובן חייבות להיות מושבתות או נעקפות:
- נירמול מסגרת
- ה־planner בדרך כלל כותב מחדש
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGל־ROWS UNBOUNDED PRECEDINGעבור פונקציות חלון שאינן תלויות במסגרת, כגוןrow_number,rankו־ntile. המסגרת של RPR היא טווח ההתאמה, לא חלון אגרגציה, וחייבת להישאר מילה במילה. - דחיפת תנאי ריצה
- פילטר
WHEREמונוטוני על פלט של פונקציית חלון יכול בדרך כלל להידחף לתוך אופרטור החלון כתנאי עצירה. עבור RPR הדבר היה מסיים את התאמת התבנית בטרם עת, ואולי חותך התאמות באמצע הרחבה. - דה־דופליקציה של חלונות (RPR מול לא־RPR)
- שני חלונות עם
ORDER BYומסגרת זהים היו ממוזגים בדרך כלל לאחד. חלון RPR וחלון לא־RPR לעולם אינם יכולים לחלוק מצב מאחר שצד ה־RPR נושא תוצאות התאמה. - דה־דופליקציה של חלונות (DEFINE או SKIP שונים)
- שני חלונות RPR עם אותו
PATTERNאך פסוקיותDEFINEשונות אוAFTER MATCH SKIPשונה מפיקים התאמות שונות וחייבים להישאר נפרדים, גם אם צורתם המבנית זהה. - היטל פלט לא־בשימוש
- זו מותרת לחול: כשהשאילתה הסובבת לעולם אינה קוראת את הפלט של החלון, פונקציית החלון הופכת ל־NULL וה־WindowAgg שלה מוסר, ומספר השורות נותר ללא שינוי. הבדיקות מוודאות שהעמודות ש־DEFINE קורא עדיין מגיעות ל־WindowAgg כשהוא נשאר, ושהחלון נשמר כאשר ערכו נקרא.
- מעברים הופכיים של אגרגציה נעה
- אגרגציות חלון עם פונקציית מעבר הופכית יכולות בדרך כלל להיות מוערכות באופן הדרגתי תוך כדי שהמסגרת זזה. המסגרת המצומצמת של RPR אינה חלון נע; נתיב המעבר ההופכי היה מפיק תוצאות שגויות.
מקרים נוספים בודקים שהערכת העלות מביאה בחשבון את DEFINE, ששאילתת משנה המחזיקה חלון RPR אינה משוטחת, שביטויי DEFINE אינם דולפים ל־WindowAgg עליון, וש־LIMIT נשאר מעל ה־WindowAgg; קבוצה שנייה מריצה RPR לצד CTE־ים, צירופים, פעולות קבוצה, משפטים מוכנים (prepared statements), טבלאות מחולקות ומבנים דומים. רוב המקרים המוגנים עוקבים אחר אותה צורה: קו בסיס שמפעיל את האופטימיזציה (בדרך כלל שאילתה לא־RPR, הנבדקת ב־EXPLAIN), ואז שאילתת RPR בעלת צורה דומה מבנית שבה האופטימיזציה אינה מיושמת — עבור מקרה הדה־דופליקציה של DEFINE/SKIP קו הבסיס הוא שני חלונות RPR זהים, ומקרה המעבר ההופכי בודק את העקיפה באמצעות אגרגציה רושמת־לוג ולא באמצעות EXPLAIN. שני החצאים יחד מוכיחים שהשומר ב־planner עושה עבודה אמיתית, ולא מאשר כל שאילתה ללא אימות אמיתי.
חבילה זו היא גם הסיבה ש־§3.4 קצר. מנגנוני "גבולות ההתאמה" — מסגרת מצומצמת, SKIP, INITIAL, חיתוך מסגרת חסומה — נבדקים אופרטיבית במקום אחר; מה ש־rpr_integration מאמת הוא ששום שלב אופטימייזר אחר לא נוגע בהם בדרך. rpr_integration שעובר הוא מה שמאפשר לשאר החבילות לסמוך על כך שהקלט שלהן מגיע ל־executor ללא שיבוש.