זיהוי תבניות שורה צלילה מעמיקה

§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 לשם הפקת פלט של פונקציית חלון. שני הממשקים חולקים את רוב התחביר ואת כלל הסמנטיקה, אך מהווים נקודות כניסה פונקציונליות שונות — מסד נתונים יכול לממש אחת מהן או את שתיהן.

סדרת הטלאים הנדונה כאן מממשת תת־קבוצה של R020 בלבד; טופס פסוקית הטבלה נמצא במפורש מחוץ להיקף.

ממשק R020 הוא קטן אך עשיר ביכולות. שאילתה מצרפת תבנית לחלון על ידי הוספת שלוש פסוקיות בתוך מפרט החלון: PATTERN מתארת ביטוי רגולרי מעל משתני תבנית בעלי שם, DEFINE מספקת את הפרדיקט הבוליאני שמזהה כל משתנה, ו־AFTER MATCH SKIP שולטת באופן שבו התאמות עוקבות ממוקמות בתוך המחיצה.

הפסוקיות האופציונליות 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

מגדירה את תבנית השורה בתוך מפרט החלון.

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)) — גם השלב הפנימי וגם החיצוני מקבלים היסט משלהם.

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 label, AFTER MATCH SKIP TO FIRST var, ו־AFTER MATCH SKIP TO LAST var. גם אלה תלויים בהיסטוריית ההתאמה, שכן ה־executor חייב להיות מסוגל להצביע על שורה מסומנת ספציפית בתוך ההתאמה האחרונה.

שאר הפריטים הם זנב הטרוגני: מילת המפתח SEEK (החלופה ל־INITIAL), התבנית הריקה (), צורת ההחרגה {- … -}, והאופרטור חסר־הסדר PERMUTE.

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 label

דילוג לשורה מסומנת.

AFTER MATCH SKIP TO FIRST var

דילוג לשורה הראשונה שהותאמה כמשתנה הנקוב.

AFTER MATCH SKIP TO LAST var

דילוג לשורה האחרונה שהותאמה כמשתנה הנקוב.

Regex: {- -}

החרגה — מסירה שורות שהותאמו מהפלט פר־התאמה.

Regex: ()

תבנית ריקה — מתאימה את הרצף הריק.

PERMUTE(...)

התאמה חסרת־סדר על פני המשתנים הנקובים.

פונקציות צבירה ב־DEFINE

פונקציות צבירה כגון SUM, AVG, COUNT אסורות בפרדיקטי DEFINE. התקן מתיר אותן כצבירות רצות מעל ההתאמה החלקית (הערכה פר־שורה על שורות שכבר מופו למשתנה), מה שתלוי באותה היסטוריית התאמה ש־MEASURES/CLASSIFIER() דורשות.

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

הראשונה היא שעוגני התבנית ^ ו־$ אסורים עם 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 לא יכולות להפנות למשתני תבנית; ו־RPR אינו יכול לשמש בתוך שאילתה רקורסיבית.

הרביעית היא ש־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 שורות אחרי השורה הנוכחית. הצצה קדימה; נדירה בצורת חלון משום שהחלון מונוטוני.

FIRST(expr [, n])

השורה ה־n־ית שהותאמה בהתאמה הנוכחית, נספרת מההתחלה. "השווה לשורה שפתחה את ההתאמה הזו."

LAST(expr [, n])

השורה ה־n־ית שהותאמה לאחרונה. "השווה לשורה שהותאמה לאחרונה."

ארבעת הפרימיטיבים מתחברים זה לזה: PREV ו־NEXT יכולים לעטוף קריאת FIRST או LAST, ולתת ארבעה טפסים מורכבים שסמנטיקתם היא "לך לשורה יחסית להתאמה, ואז צעד מרחק קבוע ממנה." זה מה שמאפשר לביטוי DEFINE לקרוא, למשל, את השורה שמיד לפני שההתאמה התחילה.

PREV(FIRST(expr [, n]) [, m])

צעד m שורות אחורה מהשורה ה־n־ית של ההתאמה (ברירת מחדל m = 1). "מה היה הערך מיד לפני שהתאמה זו החלה?"

NEXT(FIRST(expr [, n]) [, m])

צעד m שורות קדימה מהשורה ה־n־ית של ההתאמה. מגיע עמוק יותר אל תוך ההתאמה ללא תלות בשורה הנוכחית.

PREV(LAST(expr [, n]) [, m])

צעד m שורות אחורה מהשורה ה־n־ית שהותאמה לאחרונה. "השווה לשורה זמן קצר לפני ההתאמה האחרונה."

NEXT(LAST(expr [, n]) [, m])

צעד m שורות קדימה מהשורה ה־n־ית שהותאמה לאחרונה.

שתי נקודות מעשיות ראויות לציון כאן. ראשית, ניתן למשלב ניווט: PREV(FIRST(price)) קוראת את השורה שמיד לפני שההתאמה החלה, והטלאי תומך בכך. שנית, לניווט יש השלכות על האופטימיזציות של ה־executor. PREV ו־NEXT הם יחסיים לשורה הנוכחית ובטוחים תמיד; FIRST וגרסאות עם היסט של LAST הם יחסיים לגבולות ההתאמה, מה שמתערב עם ספיגת ההקשר ומאלץ את ה־planner להשאיר חלק מההקשרים פעילים שאחרת היה מסיר. המנגנון מאחורי האינטראקציה הזו הוא נושא §2.6.

2.3 דוגמה מפותחת 1 — תנועת NFA

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:

הנקודה המרכזית: בשורה 3, השורה מקיימת גם את START (תמיד אמת) וגם את DOWN, אך המצב היחיד ששרד את שורה 2 נמצא בענף יציאת DOWN, ולכן רק המעבר UP → DOWN מתבצע. האופי הרב־מצבי של §2.1 נראה כפיצול ענפים בכל התאמת UP (המצב יכול להישאר ב־UP+ או להתקדם לעבר DOWN+). העדפת הגרידי היא "לולאה נוספת לפני יציאה", ולכן בנתונים מספיקים הענפים בלולאה היו מאריכים את ההתאמה; כאן ה־DOWN בלולאה מת בשורה 5 (130 ≮ 108), והמועמד FIN הקודם (שורות 0–4) — שנוצר כש־DOWN יצא בשורה 4 — ננעל כהתאמה.

התוצאה של השאילתה נובעת ישירות מהמעקב הזה. תחת סמנטיקת RPR, פונקציות החלון first_value(price) ו־last_value(price) מוערכות רק בשורה שפתחה את ההתאמה — כל שורה אחרת בהתאמה תפיק NULL עבור פונקציות החלון הללו, מכיוון שמסגרתה המצומצמת ריקה. הפלט עבור הנתונים שלנו נראה אפוא כמו הטבלה שהפוסטר מציג בפאנל הימני העליון שלו:

שורה 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 מכריע ביניהם.

שני הענפים מפיקים התאמה באותו אורך מעל אותן שורות, ומשאירים למתאם שני נתיבים מועמדים — אחד מתויג UP, DONE ואחד HIGH, DONE. התקן פותר זאת באמצעות סדר לקסיקלי: בין החלופות שנכתבו ב־(UP | HIGH), זו שנכתבה ראשונה מנצחת, ללא תלות באורך ההתאמה. מאחר ש־UP מופיע לפני HIGH, הנתיב שורד הוא UP, DONE.

הסדר הלקסיקלי הוא מה שיהפוך את CLASSIFIER() למוגדר היטב כשיממשו אותו בסופו של דבר — הוא מאפשר לזמן הריצה לומר למשתמש "השורה הזו הותאמה כ־UP, לא כ־HIGH" גם כששני הפרדיקטים אמת. הסדר הלקסיקלי הוא הכלל העיקרי לחילופין: ענף מוקדם לקסיקלית מנצח ענף מאוחר ממנו גם אם הענף המאוחר היה מפיק התאמה ארוכה יותר, וענף מאוחר לקסיקלית (קצר יותר אולי) עדיין יכול לנצח אם כל ענף מוקדם ממנו מת לפני שהגיע ל־FIN. אורך גרידי נחתך בתוך קוונטיפיקטור יחיד — בהינתן שתי השלמות של אותו ענף חילופין, הקוונטיפיקטור הגרידי מעדיף יותר חזרות.

2.5 דוגמה מפותחת 3 — ספיגת הקשר (אותו גורל)

התבנית הפשוטה ביותר שמדגימה ספיגה היא PATTERN (A+) עם DEFINE A AS TRUE. כל שורה מתאימה ל־A, והתקן דורש מהמתאם לשקול כל שורה כתחילת התאמה אפשרית. נאיבית, פירוש הדבר N הקשרים עבור מחיצה בת N שורות. ניקח מחיצה של חמש שורות (כל נתונים — הפרדיקט אמת קבועה):

הזיכרון גדל מ־O(n) ל־O(1). כלל הספיגה שמצדיק את ההשלכה פשוט כאשר הקוונטיפיקטור בלתי חסום:

הפאנל השמאלי התחתון בפוסטר ("① 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 של כל שורה משווה את מחיר השורה לקודם המיידי שלה — עובדה ברמת המחיצה, ולא ברמת ההקשר — ולכן שני ההקשרים נאלצים לחשב את אותו בוליאני בכל שורה משותפת:

הסיפור נשבר ברגע שהפרדיקט מתחיל להיות תלוי בגבולות של כל הקשר בעצמו — וזה הנושא של §2.6.

2.6 דוגמה מפותחת 4 — כשהספיגה הופכת ללא־בטוחה

נניח שאנליסט רוצה למצוא ימי מסחר רצופים שבהם מניה נשארה בטווח של עשרה דולרים מהיום שבו הרצף החל — מעין חלון התמתנות. התבנית וה־DEFINE נראים כך:

PATTERN (STABLE+)
DEFINE STABLE AS price < FIRST(price) + 10

התנאי משווה כעת את מחיר השורה הנוכחית למחיר בהתחלת הרצף הנוכחי. שני רצפים שהתחילו בימים שונים מקבלים ערכים שונים של FIRST(price), ולכן שני מצבים באותו אלמנט תבנית ובאותה ספירה כבר אינם החלפיים: עתידיהם תלויים בגבול שהספיגה עמדה להשליך.

ניקח את אותו שבוע מסחר ממש כמו ב־§2.5 — $100, $108, $112, $116, $110 מיום שני עד יום שישי. שוב זמן הריצה שומר שני רצפים מועמדים בו־זמנית: C1 התחיל ביום שני, C2 התחיל ביום שלישי (כל שורה היא תחילת רצף פוטנציאלית תחת STABLE+).

תחת ספיגה, C2 היה ממוזג לתוך C1 ביום שלישי — ההקשר הממוזג שומר תקרה אחת בלבד, ולכן הראייה הייחודית של C2 (תקרה $118, הרצף בן ארבעת הימים שמסתיים רק בשבת) כבר אינה ניתנת לשחזור ממצב פנימי. C2 חייב להישאר בחיים מכיוון שהוא מועמד התאמה עצמאי שזמן הריצה עדיין עשוי להזדקק לו: כאשר ההתאמה של C1 מסתיימת ביום רביעי, הניסיון הבא חייב להמשיך מ־C2 שעדיין רץ במקום להתחיל מאפס. בכל פעם שפרדיקט DEFINE נושא תלות בתחילת ההתאמה, ה־planner משבית אפוא את הספיגה באופן יזום.

(כאשר ההתאמה של ההקשר המוביל אכן מצליחה, הקשרים שהתחילו בתוך טווח הקבלה שלו — תחת ברירת המחדל AFTER MATCH SKIP PAST LAST ROW — מושלכים פשוט; הם נשמרים בחיים רק כדי שלזמן הריצה תהיה לאן ליפול חזרה אם ההתאמה המובילה תיכשל.)

טבלת התלויות בפאנל הימני התחתון של הפוסטר ("② Navigation") מסכמת אילו טפסי ניווט יוצרים תלות בתחילת ההתאמה:

שתי הדוגמאות ב־§2.5 ו־§2.6 מסתכמות בכלל יחיד. אותו גורל הוא מה שהופך את הספיגה לבטוחה: אם כל הקשר באותו אלמנט תבנית יחשב את אותה תשובה לכל פרדיקט עתידי, רק הוותיק ביותר צריך להישמר. גורלות שונים הופכים את הספיגה ללא־בטוחה: ברגע שהפרדיקטים מסתעפים על מצב פרטי להקשר — וזה בדיוק מה ש־FIRST ו־LAST נושא־היסט עושים — כל הקשר חי מייצג עתיד שאף הקשר אחר לא יוכל לשחזר, והשלכת אחד מהם מסכנת בייצור תשובה שגויה.

ה־planner מזהה את ההבחנה הזו בזמן הקומפילציה ומחליט פר־הקשר אם הספיגה חלה. זו גם הסיבה שהבנצ'מרק שבפוסטר בפאנל ③ נשאר לינארי גם במקרה ההצלחה וגם במקרה הכישלון: כשהספיגה בטוחה, זמן הריצה מקפל הקשרים, וכשלא, ה־planner מקבל את עלות ריבוי ההקשרים במקום לסכן בתשובה שגויה.

מספרי הבנצ'מרק שעל הפוסטר הם אותו אלגוריתם פועל בקנה מידה. על תבנית ההצלחה (A+ B+ C+ D), גם PostgreSQL וגם Trino מסתעפים בקנה מידה O(n) לאחר שהתאמה אושרה, וההובלה של PostgreSQL — כפי 16× עד 33× בערך — נובעת בעיקרה מפער ה־JVM.

על תבנית הכישלון (A+ B+ C+ E), ל־Trino אין ספיגה והוא מתדרדר ל־O(n²) במרדף אחרי כל תחילת התאמה אפשרית; ב־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. אף אחת מהן אינה ניתנת להחלפה ב"ארוכה יותר שמתחילה מוקדם יותר", מכיוון שהתקן אומר שהמשתמש רוצה את כולן.

שימו לב שהפרדיקט לא השתנה. A AS TRUE מוערך באותו אופן בכל שורה ללא תלות באיזה הקשר שואל, ולכן תנאי "אותו גורל" מ־§2.5 עדיין מתקיים. מה שמשתנה הוא דרישת הפלט: גם הקשרים עם עתידים זהים חייבים להתקיים זה לצד זה משום שהם מתאימים לשורות נפרדות של התוצאה. ה־planner משבית אפוא את ספיגת ההקשרים בכל פעם ש־AFTER MATCH SKIP TO NEXT ROW בתוקף, ללא תלות בפסוקית ה־DEFINE.

הצבת §2.6 ו־§2.7 זה לצד זה נותנת את התמונה המלאה מתי הספיגה נכשלת:

כל אחד מהתנאים מספיק כדי להשבית את הספיגה עבור ההקשרים המושפעים. כששניהם אינם בתוקף — ברירת המחדל AFTER MATCH SKIP PAST LAST ROW עם תנאי DEFINE שמשתמשים רק ב־PREV, NEXT, או LAST חשוף — זמן הריצה מקפל להקשר יחיד פר־מיקום בתבנית ונשאר לינארי לכל אורך הדרך.

§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, ואופציות EXCLUDE אסורות. אלו בדיקות תאימות, ולא אופטימיזציות — תפיסת המסגרת ב־RPR היא טווח ההתאמה, והתקן אינו מעלה על דעתו למלא אותה במשהו אחר מלבד שורות שהותאמו.

לאחר שהמסגרת עוברת אימות, ה־parser הופך את פסוקית PATTERN לעץ הבנוי מארבעה סוגי צמתים — הפניית משתנה, רצף (שרשור), חילופין, וקבוצה (תת־תבנית בסוגריים). כל צומת נושא את הקוונטיפיקטור כשלושה מספרים — חסם תחתון, חסם עליון (אולי אינסופי), ודגל למצב חששני:

כל פרדיקט DEFINE נבדק לאחר מכן מבחינת טיפוס מול עמודות המחיצה ומכופה לביטוי בוליאני. שני דברים מעשיים קורים כחלק מכך. ראשית, כל עמודה שמופנית על ידי פרדיקט DEFINE נרשמת כחלק מדרישות הפלט של השאילתה, כדי שה־planner יפיץ את העמודות הללו לשלב ה־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

האופטימיזציה משתלמת פעמיים: פעם אחת במספר האלמנטים הסטטי של המערך השטוח, ושוב בכל שורה שמעובדת בזמן ריצה. כל טרנספורמציה מצמצמת את מרחב המצבים שזמן הריצה חייב לספור. האופטימייזר מיישם שמונה כללי כתיבה־מחדש ברצף עד שה־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+)+ → A+), חיצוני מדויק ((A{2,3}){5} → A{10,15}), או ילד טריוויאלי {1,1} ((A){2,5} → A{2,5}). שילובים אחרים עלולים להכניס פערים שהצורה השטוחה תפספס — למשל, (A{2}){2,3} מקבל רק {4, 6}, אך A{4,6} נאיבי היה מקבל גם 5 — ולכן האופטימייזר משאיר אותם בעינם.

צורת אלמנט

כל אלמנט במערך השטוח מייצג מיקום יחיד בתבנית. ישנם חמישה סוגים לוגיים: הפניית משתנה (היחידי שצורך שורה); סמני תחילת קבוצה וסוף קבוצה, שפותחים וסוגרים תת־תבנית בסוגריים; סמן חילופין, שעומד בראש רשימת ענפים; וסמן סיום בקצה התבנית.

כל אלמנט נושא גם עומק (רמת הקינון של הקבוצה שלו), את הקוונטיפיקטור (ספירת חזרה מינ' ומקס', אולי אינסופית), ושני מצביעי מעבר — next, "לאן ללכת אחרי שצרכנו את האלמנט הזה," ו־jump, "לאן לדלג" (משמש את החילופין לשרשור ענפים, את תחילת הקבוצה כדי לעקוף את הגוף כשהקוונטיפיקטור מאפשר אפס, ואת סוף הקבוצה כדי לחזור בלולאה אל הגוף).

עבור PATTERN ((A B)+) המערך המהודר נראה כך:

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (פותח קבוצה; jump מדלג
     ל־FIN כש־min = 0)

[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 4 אם הקבוצה הייתה אופציונלית. זמן הריצה לעולם אינו צריך לבנות גרף בזמן ריצה — הוא פשוט עוקב אחר שני המצביעים הללו תוך טיול במערך.

תכונות פר־אלמנט

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

חששני

הופך את סדר הרחבת הקוונטיפיקטור. קוונטיפיקטורים גרידיים מנסים "לולאה נוספת" לפני "יציאה"; קוונטיפיקטורים חששניים מנסים "יציאה" קודם. נישא על ידי המשתנה עבור A+?; נישא על ידי BEGIN ו־END של הקבוצה עבור ((…)+?).

בר־לולאה־ריקה

נקבע על סופי קבוצות שגופן ניתן להאפסה ((A?)*, (A? B?)+, (A | B*)). מורה לזמן הריצה להוסיף יציאה מהירה לצד החזרה הרגילה ללולאה, כדי ששומר המחזור לא יהרוג התאמות לגיטימיות בקבוצות שיכולות להפיק חזרות ריקות.

באזור־בר־ספיגה

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

נקודת־השוואה־לספיגה

מסמן את האלמנט הספציפי שבו אמורות לרוץ השוואות הספיגה. עבור 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
  עברו על ה־AST וסמנו
  אלמנטים העונים על
  מקרה מבני

שלוש הבדיקות הראשונות הן ברמת השאילתה: הן מתאימות בדיוק לתנאי §2.7 (צד פלט: מצב SKIP), מסגרת חסומה (גבול שובר מונוטוניות), ו־§2.6 (צד נתונים: FIRST או LAST נושא־היסט ב־DEFINE). כשמי מהן נכשלת, הניתוח אינו קובע דגלים והספיגה מושבתת לרוחב השאילתה. כשכולן עוברות, הסיור על ה־AST מקבל שלוש צורות מבניות:

מקרה 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 — קבוצה שגופה מתחיל במשתנה בלתי חסום

(A+ B)+

המשתנה הבלתי חסום המוביל הוא בעצמו בר־ספיגה (מקרה 1) ומגן על הקשרים ותיקים. הספיגה נעצרת ברגע שהמצב עובר את A — לשאר הגוף אין ערובה למונוטוניות, ולכן דגלים נקבעים רק על A.

המקרים המבניים שאינם מכוסים על ידי שלוש הצורות הללו מאלפים לא פחות. A B+ אינו ניתן לספיגה על ידי הכלל הנוכחי משום ש־A המוביל צורך שורה לפני שהחלק הבלתי חסום מתחיל, ולכן הקשרים שמתחילים שורה אחת זה מזה נמצאים במיקומים שונים בתוך הגוף הבלתי חסום. (הרחבת המשך בשם "ספיגת PREFIX" שמטפלת בקידומות באורך קבוע באמצעות נתיב צל תוכננה ומתוכננת לטלאי נפרד.) קוונטיפיקטורים חששניים כמו 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
    ל־current_row_slot
  result = eval_inner_expression()
  שחזר current_row_slot
  return result

הטריק הוא שיש בדיוק חריץ אחד לשמור ולשחזר. הביטוי הפנימי — מה שלא יהיה, כולל אריתמטיקה, קריאות פונקציה, או הפניות עמודה אחרות — רץ מול החריץ המוחלף באמצעות אותו נתיב הערכה שהיה רץ מול השורה הנוכחית. ללא מעריך חלופי, ללא חריץ צל, ללא העתקת 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 lastMatchedRow − n

  # מורכב: match-rel, ואז צעד
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  אמת מול הטווח המתאים
  (טווח התאמה ל־FIRST/LAST פנימי,
   טווח partition לצעד החיצוני)

מטמון מיקומים קוצר מעקף את שליפת ה־tuplestore כשמספר קריאות ניווט באותה DEFINE מכוונות לאותה שורה — נפוץ בביטויים כמו price > PREV(price) AND volume > PREV(volume) שבהם שתי הקריאות מתפרשות לשורה הקודמת. המטמון שומר רק "מיקום שהובא לאחרונה", וההחלפה עצמה נשארת פעולה יחידה.

הסיווג של קריאות ניווט הוא תרומת ה־planner להחלטת הספיגה. ה־planner מטייל בכל ביטוי DEFINE וממיין כל משתנה לאחת משתי דליים, על פי אם כל ההקשרים יחשבו את אותו בוליאני באותה שורה, או שכל הקשר יחשב את שלו. הדלי קובע שני דברים בזמן ריצה: כמה פעמים המשתנה מוערך (פעם אחת משותפת, או פעם לכל הקשר מושפע — §3.5 פאזה 1), והאם המצב הסובב כשיר לספיגת הקשרים (§2.5 לעומת §2.6).

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

תקציב שמירה

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

תקציב Lookback

עד כמה אחורה מהשורה הנוכחית כל קריאת DEFINE עשויה להגיע.

תורמים: PREV, LAST עם היסט, PREV(LAST(...)), NEXT(LAST(...))

תקציב Lookahead מההתחלה

עד כמה קדימה (או אחורה, כשהוא שלילי) מתחילת ההתאמה של ההקשר החי הוותיק ביותר כל קריאת DEFINE עשויה להגיע.

תורמים: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

בזמן ריצה סימון הגיזום של ה־tuplestore נקבע לפי המוקדם מבין שני המיקומים — השורה הנוכחית פחות תקציב ה־Lookback, ותחילת ההתאמה של ההקשר החי הוותיק ביותר ועוד תקציב ה־Lookahead. כל מה שלפני הסימון הזה אינו ניתן להגעה על ידי שום קריאת ניווט בשום הקשר חי, וה־tuplestore חופשי לזרוק אותו. שני מוני ה־Nav Mark ש־EXPLAIN מדווח (§3.7) — Lookback ו־Lookahead — הם השיאים הנמדדים של שני התקציבים, העומק הרב ביותר שה־executor אי פעם נדרש להגיע אליו בכל כיוון במהלך השאילתה.

3.4 גבולות התאמה — SKIP, INITIAL, ומסגרת חסומה

התאמה מוצלחת מתועדת כצרור ערכים קטן: דגל תקפות, דגל הצלחה/כישלון, השורה שבה ההתאמה מתחילה, ומספר השורות שצרכה. כשדגל התקפות קבוע, שאילתות נוספות מול ה־executor — "האם השורה הזו בתוך התאמה?" — יכולות להשיב ב־O(1) על ידי בחינת הצרור. אורך אפס הוא תוצאה אמיתית, לא שגיאה: הוא מייצג תבנית שהתאימה מבלי לצרוך שורה כלשהי, מצב שה־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 נקרא על ידי מכניזם פונקציות החלון הסובב בכל פעם שצריך לדעת אם שורה נתונה שייכת למסגרת מותאמת. הדרייבר מוצא או יוצר את ההקשר עבור מיקום ההתחלה הנוכחי, מעריך כל פרדיקט DEFINE פעם אחת מול השורה הנוכחית כדי להפיק מערך בוליאני פר־משתנה, ואז מניע את ה־NFA קדימה בשורה אחת. הצעד קדימה עצמו הוא שלוש פאזות בסדר קבוע — Match, Absorb, Advance — עטוף באותה לולאה חיצונית:

processRow(currentPos):

  # שלב 1 — MATCH (התכנסות)
  עבור כל context:
      אם context חורג מ־frame חסום:
          אכוף mismatch (סיום מוקדם)
          continue
      אם matchStartRow שונה ממיקום
         ההערכה המשותף:
          העריכו מחדש משתני DEFINE
          תלויי התחלת־התאמה (§3.3)
      match(context, varMatched)

  # שלב 2 — ABSORB
  אם pattern הוא absorbable:
      רעננו דגלים של כל context
      absorb_contexts()

  # שלב 3 — ADVANCE (התפצלות)
  עבור כל context:
      advance(context, currentPos)

הסדר אינו בחירה סגנונית. 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]
      אם elem אינו משתנה:
          continue   # advance מטפל בזה

      אם לא 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 כשמצב לא־בר־ספיגה מוסר). שני הדגלים נבדקים בזמן קבוע לפני שסריקת הכיסוי בכלל מתחילה, כך שהספיגה משלמת את מלוא עלותה רק על הקשרים שיש להם סיכוי אמיתי להיבלע.

פאזה 3 — Advance

Advance היא פאזת ה"התפצלות": כל מצב ששרד מורחב דרך מעברי אפסילון עד שכל ענף מגיע למשתנה שממתין לשורה הבאה או לסמן ה־FIN. ההרחבה היא בעומק תחילה, והסדר שבו ענפים אחים נסרקים הוא מה שגורם לכלל ההעדפה של התקן באמת לקבל תוקף — הענף הראשון לקסיקלית מתווסף תמיד ראשון, ושלב הדה־דופליקציה בעת הוספת מצב משליך בשקט תוספות מאוחרות שקולות.

advance(context, currentPos):
  שלוף את כל המצבים הנוכחיים;
  בנה מחדש את ctx.states מאפס
  עבור כל מצב בסדר לקסיקלי:
      נקה את bitmap האלמנטים שביקרו
      advance_state(state)   # DFS

      # העדפה: ברגע ש־DFS מגיע ל־FIN,
      # המצבים הנותרים פחות מועדפים
      # וניתן להשליך אותם.
      אם FIN הושג ונותרו מצבים:
          שחרר את היתר
          break

advance_state(state):
  הלך דרך state.elemIdx,
  רקורסיה דרך:
    ענפי ALT (לפי סדר),
    BEGIN (כניסה לקבוצה; ועוד מסלול
           דילוג אופציונלי אם min = 0),
    END (loop back / exit / fast-forward —
         ראו למטה),
    FIN (רישום matchEndRow,
         שמירת matchedState, ועקיצה
         של הקשרים מאוחרים יותר בתוך
         טווח המועמד — ראו למטה),
  עצירה בכל משתנה שנפגש:
      הוסף מצב ל־ctx.states
      (דה־דופליקציה לפי elemIdx + counts)

תיעוד מצב שהגיע ל־FIN עושה יותר מאשר רק לסמן את ההתאמה המועמדת. תחת AFTER MATCH SKIP PAST LAST ROW, ההתאמה הבאה הניתנת לדיווח חייבת להתחיל בקפדנות אחרי הנוכחית — ולכן ברגע שמועמד נרשם, כל הקשר עוקב ששורת ההתחלה שלו נופלת בתוך טווח המועמד נגזם מיד, גם אם ההקשר שפגע ב־FIN ממשיך לחפש התאמה ארוכה יותר באמצעות חזרה גרידית.

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

זהו אחד משני שלבי הגיזום בזמן FIN — השני, שתואר מוקדם יותר בחלק זה כחלק מ־Advance, משליך מצבים נחותים לקסיקלית בתוך אותו הקשר.

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

advance_end(state, elem):
  count = state.counts[elem.depth]

  אם count < elem.min:
      חזור בלולאה אל הגוף
      אם elem הוא empty-loopable:
          # גוף nullable, ראו §3.2
          שכפל גם מצב fast-forward
          שיוצא מהקבוצה כש־
          count מסופק
          (חולץ התאמות לגיטימיות
           ש־cycle guard היה
           אחרת הורג)

  אחרת אם count >= elem.max:
      אפס את counts בעומק זה
      צא דרך next
      (END→END: הגדל את count
       של END החיצוני)

  אחרת:
      # min <= count < max: התפצלות
      בנה מצב יציאה
      (counts בעומק זה אופסו)
      אם greedy:
          קודם loop, אחר־כך exit
          # העדף ארוך יותר
      אחרת (reluctant):
          קודם exit
          אם exit הגיע ל־FIN:
              השלך את ה־loop
              # העדף קצר יותר
          אחרת loop שני

כל מצב שמתווסף להקשר עובר בדיקת דה־דופליקציה שמשווה את מיקומו ואת ספירותיו לרשימת המצבים הקיימת. מאחר ש־Advance מעבדת ענפים בסדר DFS, המצב מהענף הראשון של כל חילופין נוחת ראשון — וכל ענף מאוחר יותר שמפיק את אותו מיקום ואותן ספירות נדחה בעת ההוספה. זה בדיוק מה שכלל הסדר הלקסיקלי מ־§2.4 דורש, מיושם בתחתית זמן הריצה ללא מעבר נפרד.

קבוצות בנות־לולאה־ריקה

מקרה דק שזמן הריצה חייב לפרק הוא הקבוצה הניתנת להאפסה — קבוצה שגופה יכול להתאים אפס שורות מאחר שכל ילד של הגוף הוא בעצמו אופציונלי. תבניות כמו (A?)*, (A? B?)+, ו־(A | B*) כולן בעלות תכונה זו: בהתאם לנתונים, הגוף יכול להשלים חזרה מבלי לצרוך שום שורה כלל. זה בסדר עקרונית, אבל זה יוצר סיכון אמיתי להרחבת האפסילון של ה־NFA. אם הגוף מפיק התאמה ריקה, אלמנט ה־END חוזר בלולאה ל־BEGIN, הגוף שוב מפיק התאמה ריקה, BEGIN חוזר ל־END, וכן הלאה. ללא משהו שיעצור זאת, ה־DFS של Advance לעולם לא יסתיים.

זמן הריצה עוצר זאת באמצעות בִּיטמַפ של אלמנטים שביקרו (ביט אחד לכל אלמנט תבנית), שנמחק לפני הרחבת ה־DFS של כל מצב: ברגע שאלמנט כלשהו מבוקר בפעם השנייה בתוך אותה הרחבה, נתיב זה ננטש. שומר המחזור הוא ללא תנאי וזול, אך יש לו תופעת לוואי — הוא יכול לנטוש גם נתיבים שצריכים להגיע לחסם התחתון דרך חזרות ריקות לגיטימיות. ניקח את (A?){2,3} כש־A אינו מתאים בשום מקום בזרם השורות:

התנהגות רצויה:
  iter 1: A? מתאים אפס שורות
          → END, count = 1 (מתחת ל־min)
  iter 2: A? מתאים אפס שורות
          → END, count = 2 (מקיים min)
  צא בהתאמה באורך אפס

מה ש־cycle guard עושה לבדו:
  iter 1: A? דולג → END, count = 1
          → חזרה בלולאה ל־BEGIN
  iter 2: BEGIN כבר בוקר
          → DFS מתבטל
  count לעולם לא מגיע ל־min
  → ההתאמה נכשלת (שגוי)

התיקון מוחלט בזמן הקומפילציה ומופעל בזמן הריצה. בכל פעם שה־planner רואה קבוצה שגופה ניתן להאפסה, הוא מתייג את אלמנט ה־END של אותה קבוצה כ־בר־לולאה־ריקה. בזמן הריצה, כאשר מטפל ה־END עומד לחזור בלולאה מאחר שספירת החזרות עדיין מתחת לחסם התחתון, התג של לולאה ריקה מורה לו לשכפל מצב fast-forward נוסף לצד נתיב החזרה ללולאה הרגיל:

advance_end (count מתחת ל־min):

  נתיב ראשי:
    חזור בלולאה אל הגוף
    (משאיר את הדלת פתוחה
     להתאמה אמיתית, לא־ריקה
     באיטרציה הבאה)

  אם elem הוא empty-loopable:
    נתיב fast-forward:
      אפס את count של עומק זה
      צא מהקבוצה דרך next,
      בהתייחסות לאיטרציות הנדרשות
      הנותרות כהתאמות ריקות

שני הנתיבים ממלאים תפקידים משלימים. החזרה ללולאה הראשית היא מה שתופס את המקרה שבו לגוף עדיין יש התאמות אמיתיות להפיק מאוחר יותר — למשל, ב־(A?){2,3} שאחריו נתונים שבהם A מתאים רק בשורות מאוחרות יותר, החזרה ללולאה היא מה שמאפשר לחזרות השנייה והשלישית למצוא התאמות לא־ריקות. ה־fast-forward הוא מה שתופס את המקרה שבו הגוף לעולם אינו מפיק דבר: הוא עוקף את שומר המחזור על ידי יציאה מהקבוצה כליל, ומכריז "שאר החזרות הנדרשות ריקות", ומאפשר להתאמה להצליח עם גוף באורך אפס. שני המצבים מתווספים להקשר; זה שמתרחב בהצלחה מנצח, ובדיקת הדה־דופליקציה בעת ההוספה מונעת מכל אחד מהנתיבים להוליד יותר מצבים מחלקו.

מעבר לשומר המחזור, טריק התחלה אחד נוסף מבהיר תוצאות אפס־שורות בתחילת הקשר. שלב יצירת ההקשר בכל שורת התחלה אפשרית מריץ advance ראשוני דרך מעברי אפסילון לפני שצורכים שורה כלשהי, באמצעות מיקום שורה אחת לפני ההתחלה האמיתית. כל נתיב שמגיע לסמן ה־FIN רק דרך מעברי אפסילון — מבלי לצרוך שורה — מפיק לפיכך מיקום סיום קטן ממיקום ההתחלה; הקואורדינטה השלילית הזו, יחד עם השאלה אם FIN אכן הושג, מקודדת את ההבדל בין התאמה ריקה (התאמה באורך אפס שהתקבלה) לבין התחלה ללא התאמה ללא צורך בדגל נפרד.

3.6 כיצד מרחב המצבים נשאר חסום

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

פרדיקט שנכשל Match

מצבי משתנים שה־DEFINE שלהם הוערך לשקר בשורה הנוכחית — ענפים מתים.

קידום שרשרת END בשורה Match

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

ספיגת הקשר Absorb

הקשרים חדשים שכל מצב שלהם מכוסה על ידי מצב של הקשר ותיק עם ספירה גבוהה יותר — ראו §2.5 לכלל הרעיוני, §3.2 לכשירות בזמן הקומפילציה, §3.5 לבדיקה הפר־זוגית.

דה־דופליקציה של מצבים Advance

מצבים שהושגו דרך ענפי DFS שונים שמסתיימים באותו מיקום עם אותן ספירות — רק הראשון (המוקדם לקסיקלית) שורד; שקולים מאוחרים יותר מושלכים בשקט, וזו גם הדרך שבה כפיית ההעדפה מתממשת (§2.4).

סיום מוקדם ב־FIN (בתוך הקשר) Advance

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

גיזום התאמת מועמד (בין הקשרים) בעת FIN

הקשרים אחרים ששורת ההתחלה שלהם נופלת בתוך טווח ההתאמה המועמדת — ההקשר שפגע ב־FIN רשאי עדיין להמשיך לחפש התאמה ארוכה יותר (חזרה גרידית), אך תחת AFTER MATCH SKIP PAST LAST ROW כל הקשר בתוך טווח המועמד כבר אינו יכול להפיק פלט שניתן לדיווח, ללא קשר לאופן סיום החיפוש, ונגזם מיד.

שומר מחזור Advance

הרחבות אפסילון שמבקרות שוב את אותו אלמנט תבנית בתוך אותו DFS — היו אחרת מסתובבות לנצח בקבוצות הניתנות להאפסה.

Fast-forward של לולאה ריקה Advance

התאמות חזרה ריקה לגיטימיות ששומר המחזור היה הורג בקבוצות הניתנות להאפסה — עוקף את המחזור על ידי יציאה מהקבוצה כשהחזרות הנדרשות הנותרות מוכרזות ריקות.

חיתוך מסגרת חסומה Match

הקשרים שהתאמתם הגיעה לחסם העליון של המסגרת שהגדיר המשתמש — נכפים להיכשל כדי שלא יוכלו להתרחב מעבר לכך (§3.4).

קריאת הערכים לפי תג הפאזה שלהם משרטטת את מחזור החיים של הקשר: הגיזום מופעל בכל שורה דרך שלוש הפאזות העיקריות (Match, Absorb, Advance), ושוב בעת השלמת ההתאמה (בעת FIN). קריאת התיאורים, לעומת זאת, מקבצת את הכללים לפי מה שהם מכוונים אליו: ענפים מתים, הקשרים מיותרים, מצבים שקולים, לולאות אינסופיות, והרחבת יתר מעבר לגבולות שהמשתמש הטיל.

שום כלל יחיד לא היה מספיק. שומר המחזור לבדו היה הורג התאמות לגיטימיות בקבוצות הניתנות להאפסה; ה־fast-forward של לולאה ריקה לבדו לא היה עוצר לולאות אפסילון אינסופיות; הספיגה לבדה הייתה מאחדת יתר על המידה כש־DEFINE מפנה לתחילת ההתאמה; דה־דופליקציה לבדה לא הייתה מסירה הקשרים מיותרים, רק מצבים מיותרים. זמן הריצה נשאר לינארי במקרים החשובים — PATTERN (A+ B+ C+ D) על 100,000 שורות, הבנצ'מרק של פאנל ③ בפוסטר — רק משום שכל שכבה תופסת את מה שהשכבות שמעליה מפספסות.

3.7 פלט EXPLAIN

EXPLAIN ANALYZE על שאילתה עם RPR חושף סטטיסטיקות ברמת ה־NFA שאינן נוכחות בפונקציות חלון רגילות. שלוש קבוצות של מונים נפלטות לצד אופרטור החלון:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (only when the query uses FIRST,
   PREV(FIRST(...)), or NEXT(FIRST(...)))

Peak ו־total הם תיעוד ישיר של זמן הריצה: כמה מצבים אי פעם היו חיים בו־זמנית, כמה נוצרו במהלך חיי השאילתה, וכמה מוזגו על ידי דה־דופליקציה. ההיסטוגרמות של אורך ההתאמה מפרידות בין ארבע תוצאות — התאמות מוצלחות, ניסיונות התאמה שנכשלו, הקשרים שנספגו, והקשרים שנגזמו (skipped) מבלי שהוערכו — ודיווח עליהן עם min/max/avg הופך פתולוגיות ביצועים לגלויות במבט חטוף: הרצה תקינה מראה את רוב ההקשרים כ־matched או absorbed, עם אורכי mismatched קטנים.

שני מוני ה־Nav Mark מדווחים על תקציב השמירה של ה־tuplestore ש־§3.3 גוזרת בזמן הקומפילציה. Lookback הוא ההגעה האחורה העמוקה ביותר על פני PREV, LAST עם היסט, והטפסים המורכבים עם LAST פנימי; Lookahead הוא ההגעה קדימה (או אחורה, כשהיא שלילית) העמוקה ביותר הנמדדת מתחילת ההתאמה של ההקשר החי הוותיק ביותר, נתרמת על ידי FIRST והטפסים המורכבים עם FIRST פנימי.

כל מונה מודפס כמספר שלם קבוע כשההיסט הוא קבוע, "runtime" כשההיסט הוא ביטוי לא־קבוע שצריך להיות מוערך בכל קריאה, ו־"retain all" כשזמן הריצה זקוק לתקציב בלתי חסום. Lookahead נפלט רק כשהשאילתה אכן משתמשת בניווט יחסי לתחילת ההתאמה.

יחד, המונים הללו מאפשרים לאתר באגים בביצועי RPR מבלי לחבר gdb ל־backend.

מעבר למונים, EXPLAIN גם משחזר נאמנה את פסוקיות ה־PATTERN וה־DEFINE המקוריות, כולל קוונטיפיקטורים חששניים, חזרת קבוצות, ואופציית AFTER MATCH SKIP. המימוש משקיע מאמץ מסוים כדי להפוך את הסיבוב הזה ליציב כך ש־pg_dump ו־pg_upgrade יוכלו לשמר אובייקטי RPR ללא סחיפה סמנטית — חבילת הרגרסיה תחת rpr_explain מאמתת זאת מקרה אחר מקרה (ראו §4).

§4. בדיקות — מפת כיסוי

הטלאי מגיע עם חמש חבילות רגרסיה שיחד מפעילות כל שכבה שתוארה ב־§3 — בערך 13,000 שורות SQL, כל חבילה ממוקדת בעניין שונה. הפיצול מכוון: שמירת ענייני ה־parser, נכונות זמן הריצה, אינטראקציות ה־planner ועיצוב הפלט בקבצים נפרדים מקלה על איתור כשלים, ומונעת משינוי לא קשור בשכבה אחת לבטל בטעות בדיקות בשכבה אחרת. חמש החבילות הן:

rpr

סמנטיקת שאילתות מקצה לקצה — תרחישי חלון מציאותיים על נתוני מניות סינתטיים (תבנית V, תבנית W, עליות רצופות, היפוכים).

rpr_base

שכבת ה־parser — קבלת מילות מפתח, צורות תחביר, קוונטיפיקטורים, ניתוח ניווט, הודעות שגיאה, ויציבות סיבוב pg_dump/pg_upgrade.

rpr_nfa

זמן הריצה של ה־NFA — הלולאה התלת־פאזית, ספיגה בכל צורה ברת־ספיגה, ומקרי קצה במחזור החיים של ההקשר.

rpr_explain

עיצוב פלט — סטטיסטיקות NFA, deparse של תבנית, ציטוט מזהים, יציבות פורמט בין טעינות מחדש.

rpr_integration

אינטראקציות planner — שומרים שמונעים מאופטימיזציות חלון לא קשורות לשבש את סמנטיקת RPR.

4.1 rpr — תרחישים מקצה לקצה

חבילת התרחישים היא הפנים הציבוריות של מערך הבדיקות: היא משתמשת במערך נתוני מחירי מניות סינתטי בן כ־1,600 שורות ומריצה מולו שאילתות מציאותיות — התאוששות תבנית V, תבנית W (תחתית כפולה), עליות וירידות רצופות, תבניות היפוך, מחיצות רב־סימוליות. זו החבילה היחידה שבה הקלט והפלט קוראים כמו שאילתות שמשתמש עשוי באמת לכתוב; האחרות הן רדוקטיביות במכוון, ממוקדות בשכבה אחת בכל פעם.

מאחר שהשאילתות הללו משלבות כל שכבה (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 נדחית עם שגיאה שימושית, ושכל צורה מקובלת שורדת סיבוב סריאליזציה. רובה בנוי כקטעים קטנים וממוקדים — אחד לכל תכונה תחבירית — ולא כשאילתות מציאותיות ארוכות, מאחר שהמטרה היא כיסוי ולא ריאליזם תרחישי.

בדיקות הסריאליזציה ראויות לתשומת לב מיוחדת. אובייקטי RPR (תצוגות, תצוגות ממומשות, פלט pg_dump) חייבים לעבור סיבוב דרך ייצוג הקטלוג ללא סחיפה סמנטית, כולל דקויות כמו דגל החששנות על קוונטיפיקטור או הצורה המדויקת של ביטוי ניווט מורכב. קבוצה קטנה של אובייקטים ספציפיים לסריאליזציה (התצוגות rpr_serial_v* והטבלאות שמאחוריהן) נשארת במכוון בסוף ההרצה, כדי שתשתית הרגרסיה הסובבת תוכל לקלוט אותם ולהפעיל מולם pg_dump ו־pg_upgrade. שאר הפיגומים של הבדיקה מוסרים כרגיל. באגים שנתפסים כך (כמו דגל חששני שאובד בין deparse ל־re-parse) צצים רק כשהסיבוב מופעל מקצה לקצה.

4.3 rpr_nfa — מנוע זמן הריצה

זוהי החבילה שמפעילה כל מנגנון שתואר ב־§3.5 וב־§3.6. הבדיקות שלה עוקבות אחר תבנית עקבית: טבלת קלט ששורותיה הן מערכים בוליאניים מפורשים שמכריזים אילו משתני 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 הוא חלק מההסכם המופנה למשתמש — כלים של צד שלישי (השלמה אוטומטית של psql, לוחות מחוונים לניטור, מגרדי לוגים) מנתחים אותו, ושינויים שנראים קוסמטיים יכולים לשבור אותם. חבילת rpr_explain מאמתת שלושה דברים:

• מוני NFA מופיעים במקום הנכון — סטטיסטיקות פר־WindowAgg (peak/total/merged של מצבים, peak/total/pruned של הקשרים, היסטוגרמות אורך של matched/mismatched/absorbed/skipped, Nav Mark Lookback, ו־Nav Mark Lookahead כשניווט יחסי לתחילת התאמה בשימוש) כולן מופיעות תחת EXPLAIN ANALYZE עם התוויות המתועדות.
• תבניות עוברות 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 עבור אגרגציות מונוטוניות. המסגרת של RPR היא טווח ההתאמה, לא חלון אגרגציה, וחייבת להישאר מילה במילה.

דחיפת תנאי ריצה

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

דה־דופליקציה של חלונות (RPR מול לא־RPR)

שני חלונות עם ORDER BY ומסגרת זהים היו ממוזגים בדרך כלל לאחד. חלון RPR וחלון לא־RPR לעולם אינם יכולים לחלוק מצב מאחר שצד ה־RPR נושא תוצאות התאמה.

דה־דופליקציה של חלונות (DEFINE שונה)

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

היטל פלט לא־בשימוש

גם אם השאילתה הסובבת לעולם אינה קוראת את הפלט הפר־שורה של החלון, חלון ה־RPR אינו ניתן להסרה: תופעות הלוואי של מתאם התבנית (אילו שורות בתוך איזו התאמה) מזינות חישובי מסגרת מצומצמת במקומות אחרים בתכנית.

מעברים הופכיים של אגרגציה נעה

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

התבנית בכל הבדיקות הללו זהה: כל אחת מספקת קו בסיס לא־RPR שמפעיל את האופטימיזציה (ומאמת ש־EXPLAIN מציג שהיא מיושמת), ואז מריצה שאילתת RPR בעלת צורה דומה מבנית ומאמתת שהאופטימיזציה אינה מיושמת. שני החצאים יחד מוכיחים שהשומר ב־planner עושה עבודה אמיתית, ולא מאשר כל שאילתה ללא אימות אמיתי.

חבילה זו היא גם הסיבה ש־§3.4 קצר. מנגנוני "גבולות ההתאמה" — מסגרת מצומצמת, SKIP, INITIAL, חיתוך מסגרת חסומה — נבדקים אופרטיבית במקום אחר; מה ש־rpr_integration מאמת הוא ששום שלב אופטימייזר אחר לא נוגע בהם בדרך. rpr_integration שעובר הוא מה שמאפשר לשאר החבילות לסמוך על כך שהקלט שלהן מגיע ל־executor ללא שיבוש.