التعرّف على أنماط الصفوف تعمّق تقني

§1. المعيار، والمجموعة الجزئية، والأسئلة المفتوحة

1.1 نطاق المعيار

أُدخل التعرّف على أنماط الصفوف إلى 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

تُعرّف نمط الصفوف داخل مواصفة النافذة.

التعابير المنتظمة: + * ? |

المُكمِّمات المعيارية والتبديل.

التعابير المنتظمة: تجميع ( )

أنماط فرعية بين قوسين.

التعابير المنتظمة: {n} {n,} {,m} {n,m}

أعداد تكرار مقيّدة.

المتمنّعة *? +? ?? {n}? {n,}? {,m}? {n,m}?

جميع المتغيّرات السبع المتمنّعة (غير الجشعة) التي يحدّدها المعيار (مُستثناة من تحسين الامتصاص).

جملة 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).

وهذه ليست فجوات مستقلّة بقدر ما هي إطلالات مختلفة على قطعة مفقودة واحدة: إذ سيتعيّن على المنفّذ الاحتفاظ بـتاريخ لكلّ مطابقة — سجلّ يبيّن، لكلّ صف في المطابقة، إلى أيّ متغيّر نمط جرى ربطه — ولا تملك أيّ من هذه البنى تعريفًا ذا معنى دون ذلك. تقرأ CLASSIFIER() اسم المتغيّر من ذلك السجلّ؛ ويقرأ B.price عمود السعر من الصفوف التي تنصّ مدخلات سجلّها على B؛ ويتجوّل LAST(B.price) في المجموعة نفسها ويختار آخر صف؛ وتُعرّف SUBSET U = (A, B) متغيّرًا افتراضيًا يُجمِّع فوق الدلوين معًا؛ وتُقيِّم MEASURES تعابير مثل AVG(U.Price) باستخدام هذا التجميع بالضبط.

يقيّم المنفّذ الحالي مُسندات DEFINE صفًّا بصف، لكنّه لا يُسجّل أيًّا من تخصيصات المتغيّرات الناتجة في مكان ما — فلا شيء يمكن الاستعلام عنه لاحقًا. لذا فإنّ بناء البنية التحتية للتاريخ هو الشرط المسبق لكامل المجموعة؛ وتنبثق الميزات الفردية بوصفها إسقاطات صغيرة بمجرّد وجود السجلّات.

تتعلّق المجموعة الثانية بأهداف تخطٍّ بديلة: AFTER MATCH SKIP TO تسمية، وAFTER MATCH SKIP TO FIRST متغيّر، وAFTER MATCH SKIP TO LAST متغيّر. وهذه أيضًا تعتمد على تاريخ المطابقات، إذ يجب أن يكون المنفّذ قادرًا على الإشارة إلى صف مُسمَّى محدّد داخل أحدث مطابقة.

أمّا العناصر المتبقّية فذيل غير متجانس: كلمة SEEK المفتاحية (بديل INITIAL)، والنمط الفارغ ()، وصيغة الاستبعاد {- … -}، ومُعامل PERMUTE غير المتأثّر بالترتيب.

MEASURES

تعابير مخرجات مُسمّاة لكلّ مطابقة، مثل MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg؛ تُعرض في R020 عبر OVER كدالّة نافذة. تقبل الكلمتين المفتاحيّتين FINAL / RUNNING (19075-5 §5.4)، وتنهاران في R020 إلى القيمة ذاتها لأنّ القياسات تُقيَّم دائمًا عند آخر صف في المطابقة (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

التخطّي إلى آخر صف طوبق بوصفه المتغيّر المُسمَّى.

التعبير المنتظم: {- -}

الاستبعاد — يُزيل الصفوف المطابِقة من مخرجات كلّ مطابقة.

التعبير المنتظم: ()

النمط الفارغ — يطابق التسلسل الفارغ.

PERMUTE(...)

مطابقة غير حسّاسة للترتيب عبر المتغيّرات المُدرَجة.

دوال التجميع في DEFINE

لا تُسمح دوال التجميع مثل SUM، وAVG، وCOUNT داخل مُسندات DEFINE. يسمح بها المعيار بوصفها تجميعات جارية فوق المطابقة الجزئية (تقييم لكلّ صف بالنسبة إلى الصفوف المربوطة سابقًا بمتغيّر)، وهو ما يعتمد على تاريخ المطابقة ذاته الذي تحتاجه MEASURES/CLASSIFIER().

تجدر الإشارة هنا إلى أربع نقاط إضافية، إذ يسهل الخلط بينها وبين الإغفالات.

الأولى أنّ مرسيتي النمط ^ و$ غير مسموح بهما مع RPR في جملة WINDOW وفق المعيار ذاته (19075-5 §6.13: "المرسيتان (^ و$) غير مسموح بهما مع مطابقة أنماط الصفوف في النوافذ"؛ مع التعريف الأساسي في 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)، وامتصاص السياق في الحالة السهلة، والحالة التي يصبح فيها الامتصاص غير آمن.

أمّا الآلية الداخلية التي تجعل الملاحة رخيصة — مبادلة المُتعلِّق ذات المقعد الواحد — فهي تنتمي إلى تصميم المنفّذ وستُغطَّى في القسم التالي، لا هنا.

2.1 لماذا تختلف أنماط الصفوف عن أنماط النصوص

يطابق التعبير المنتظم النصّي تدفّقًا من المحارف، وعند كلّ موضع ثمّة رمز واحد فقط للنظر فيه. والسؤال أثناء التشغيل — "هل الرمز الحالي يساوي 'A'؟" — له إجابة واحدة بنعم أو لا. تستغلّ آليات التراجع التلقائي هذا: فرع واحد على الأكثر يبقى لكلّ محرف، وتُدفع كلفة الالتباس بإعادة قراءة المدخل.

نمط الصفوف مختلف اختلافًا جوهريًا. فالصف ليس رمزًا منفردًا، بل هو مُتعلِّق من الأعمدة يُقيَّم تجاه مجموعة من المُسندات البوليانية، وهي شروط 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)) يقرأ الصف الذي يسبق بداية المطابقة مباشرةً، والترقيع يدعم ذلك. ثانيًا، للملاحة عواقب على تحسينات المنفّذ. PREV وNEXT نسبيّتان للصف الحالي وآمنتان دائمًا؛ أمّا FIRST ومتغيّرات LAST ذات الإزاحة فهي نسبيّة لحدود المطابقة، وهو ما يتفاعل مع امتصاص السياق ويُجبر المُخطِّط على إبقاء بعض السياقات حيّة كانت ستُتجاهل لولا ذلك. آليّة هذا التفاعل هي موضوع §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 داخل سياق واحد — لا عبر السياقات (تلك الامتصاص)، بل على فروع متوازية يستكشفها المنفّذ بالتوازي.

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$)، وأنّ المنفّذ يتعقّب أيضًا تخمينيًا 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 اعتماديّة على بداية المطابقة، يُعطّل المُخطِّط الامتصاص استباقيًا.

(حين تنجح مطابقة السياق الرائد، فإنّ السياقات التي بدأت داخل مدى قبوله — في ظلّ AFTER MATCH SKIP PAST LAST ROW الافتراضي — تُسقَط ببساطة؛ وقد بقيت حيّة فقط لتوفير ملاذ لوقت التشغيل في حال فشل المطابقة الرائدة.)

يلخّص جدول الاعتماديّة في اللوحة السفلية اليمنى من الملصق ("② Navigation") صيغ الملاحة التي تُنشئ اعتماديّة على بداية المطابقة:

يُختزل المثالان في §2.5 و§2.6 إلى قاعدة واحدة. المصير ذاته هو ما يجعل الامتصاص آمنًا: إذا كانت كلّ السياقات عند العنصر النمطي ذاته ستحسب الإجابة ذاتها على كلّ مُسند مستقبلي، فلا حاجة سوى للأقدم. المصائر المختلفة تجعل الامتصاص غير آمن: فبمجرّد أن تتفرّع المُسندات على حالة خاصّة بالسياق — وهو بالضبط ما تفعله FIRST وLAST ذات الإزاحة — فإنّ كلّ سياق حيّ يمثّل مستقبلًا لا يمكن لأيّ سياق آخر استعادته، وإسقاط أيٍّ منها يخاطر بإنتاج إجابة خاطئة.

يكتشف المُخطِّط هذا التمييز عند الترجمة ويقرّر لكلّ سياق ما إذا كان الامتصاص ينطبق. وهذا أيضًا سبب بقاء قياس الأداء في اللوحة ③ من الملصق خطّيًا في حالتي النجاح والفشل: عندما يكون الامتصاص آمنًا يطوي وقت التشغيل السياقات، وعندما لا يكون كذلك يقبل المُخطِّط بكلفة تعدّد السياقات بدل المخاطرة بإجابة خاطئة.

أرقام قياس الأداء على الملصق هي الخوارزمية ذاتها وهي تتجلّى على نطاق واسع. على نمط النجاح (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 محقّقًا. ما يتغيّر هو متطلّب المخرجات: حتى السياقات ذات المستقبل المتطابق يجب أن تتعايش لأنّها تقابل صفوفًا متمايزة من النتيجة. ولذلك يُعطّل المُخطِّط امتصاص السياق كلّما كانت AFTER MATCH SKIP TO NEXT ROW سارية، بصرف النظر عن جملة DEFINE.

وضع §2.6 و§2.7 جنبًا إلى جنب يُعطي الصورة الكاملة لمتى يفشل الامتصاص:

أيٌّ من الشرطين كافٍ لتعطيل الامتصاص للسياقات المتأثّرة. حين لا يكون أيٌّ منهما ساريًا — أي AFTER MATCH SKIP PAST LAST ROW الافتراضي مع شروط DEFINE التي تستخدم فقط PREV أو NEXT أو LAST المجرّدة — ينهار وقت التشغيل إلى سياق واحد لكلّ موضع نمطي ويبقى خطّيًا حتى النهاية.

§3. التصميم — من المحلّل النحوي إلى المنفّذ

يُنفَّذ التعرّف على أنماط الصفوف بثلاث مراحل تُسلِّم العمل عبر صيغ وسيطة محدّدة. يحوّل المحلّل النحوي نصّ SQL إلى شجرة نمط وقائمة بمُسندات DEFINE؛ ويُترجم المُخطِّط الشجرة إلى مصفوفة مسطّحة من العناصر النمطية ويقرّر أيّها يمكن أن يشارك في امتصاص السياق؛ وينفّذ المنفّذ المصفوفة على القسم صفًّا صفًّا في حلقة من ثلاث مراحل. لكلّ مرحلة شكل بياناتها الخاصّ، ومعظم براعة التصميم تقع عند الحدود: NFA مسطّح يتسع في الذاكرة المخبّأة، ونموذج ملاحة يُعيد استخدام مقعد مُتعلِّق واحد بدلًا من توليد واحد لكلّ إشارة، وقاعدة امتصاص تُحوّل ذاكرة 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 المحلّل النحوي وشكل شجرة النمط؛ وتغطّي §3.2 الترجمة التي تحوّل الشجرة إلى NFA المسطّح؛ وتغطّي §3.3 نموذج الملاحة الذي تستخدمه مُسندات DEFINE للنظر في الصفوف المجاورة؛ وتغطّي §3.4 معالجة حدود المطابقة — قواعد SKIP، وINITIAL، والإطار المقيّد التي تُثبت أين تبدأ المطابقة وأين تنتهي؛ و§3.5 هي محرّك الصف الواحد ذو المراحل الثلاث؛ وتجمع §3.6 كلّ آليّات التشذيب التي تُبقي فضاء الحالة محدودًا؛ وتستعرض §3.7 ما يُظهره التنفيذ في مخرجات EXPLAIN.

3.1 المحلّل النحوي — بناء شجرة النمط

يتعرّف المحلّل النحوي على معالجة الأنماط بوجود جملة PATTERN داخل مواصفة نافذة. ووظيفته الأولى التحقّق من الإطار، إذ يفرض RPR قيودًا لا تفرضها استعلامات النوافذ العادية: يجب أن يكون وضع الإطار ROWS (لا RANGE ولا GROUPS)، ويجب أن تكون حدود البداية CURRENT ROW، وخيارات EXCLUDE ممنوعة. هذه فحوص مطابقة لا تحسينات — فمفهوم الإطار في RPR هو مدى المطابقة، ولا يتصوّر المعيار ملأه بشيء غير الصفوف المطابِقة.

بمجرّد اجتياز الإطار التحقّق، يحوّل المحلّل جملة PATTERN إلى شجرة مبنيّة من أربعة أنواع من العقد — مرجع متغيّر، وتسلسل (وصل)، وتبديل، ومجموعة (نمط فرعي بين قوسين). تحمل كلّ عقدة المُكمِّم بثلاثة أرقام — حدّ أدنى، وحدّ أعلى (قد يكون لانهائيًا)، وعَلَمًا للمطابقة المتمنّعة:

يُفحَص بعدها كلّ مُسند DEFINE من حيث النوع تجاه أعمدة القسم ويُحوَّل إلى تعبير بولياني. ويحدث في إطار ذلك أمران عمليّان. أوّلًا، كلّ عمود يشار إليه بمُسند DEFINE يُسجَّل ضمن متطلّبات مخرجات الاستعلام، فيُمرّر المُخطِّط تلك الأعمدة إلى مرحلة المنفّذ حتى لو لم يُحدّدها الاستعلام المحيط — وإلا فلن يكون لدى وقت التشغيل ما يقيّمه. ثانيًا، المتغيّرات التي تظهر في PATTERN ولا تظهر أبدًا في DEFINE صحيحة ضمنيًا: تطابق كلّ صفّ.

3.2 الترجمة — من AST إلى NFA مسطّح

يحوّل المُخطِّط شجرة المحلّل إلى بنية البيانات التي سيشغّلها المنفّذ: مصفوفة مسطّحة من العناصر النمطية تُعنوَن بالفهرس. تتقدّم الترجمة كخطّ أنابيب من ست خطوات:

compile(astTree):
  1. حسِّن الـ AST
  2. قِس الحجم والعمق
  3. خصِّص مصفوفة العناصر
  4. املأ من الـ AST
       (عيّن مؤشّري next/jump)
  5. أنهِ — جهِّز sentinel الـ FIN
  6. حدِّد العناصر الصالحة للامتصاص

اختير الشكل المسطّح لسبب بسيط: يحتاج المنفّذ إلى التجوّل في النمط مرّات كثيرة لكلّ قسم، والمصفوفة المتجاورة المُعنوَنة بالفهرس هي أرخص بنية بيانات للتجوّل. الخطوتان 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    اكتمال النمط

The pattern reads left-to-right via next, with jump handling the non-linear edges. At idx 3 the END's jump points back to idx 1, which is how the unbounded outer quantifier loops; at idx 0 the BEGIN's jump would skip past the END to idx 4 if the group were optional. The runtime never has to construct a graph at runtime — it just follows these two pointers as it walks the array.

سمات لكلّ عنصر

إلى جانب الشكل، يحمل كلّ عنصر أربع سمات منطقية توجّه سلوك وقت التشغيل عند ذلك الموضع:

متمنّع

يعكس ترتيب توسعة المُكمِّم. المُكمِّمات الجشعة تحاول "الدوران مجدّدًا" قبل "الخروج"؛ والمتمنّعة تحاول "الخروج" أوّلًا. يحمله المتغيّر لـ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 absorption" يعالج البادئات ذات الطول الثابت عبر مسار ظلّ، ومخطّط لترقيع منفصل.) المُكمِّمات المتمنّعة كـA+? مستثناة بالبناء: قاعدة الامتصاص تفترض دلالات جشعة، حيث تستوعب المطابقات الأطول الأقصرَ، والمطابقة المتمنّعة تعكس ذلك الاتّجاه.

والنتيجة قرار لكلّ عنصر بدلًا من قرار لكلّ نمط. يمكن لخطّة استعلام واحدة أن يكون لديها امتصاص مُفعَّل لـA+ الرائد في أنماط مثل (A+ B+ C) أو (A+ B+)+ — وهذه الأخيرة هي الحالة 3 مطبَّقة على عنصرها الرائد — وأن يكون مُعطَّلًا لكلّ ما يأتي بعده؛ ويستشير وقت التشغيل ببساطة سمة نقطة المقارنة على عنصر الحالة الراهنة كلّما فكّر في تمريرة امتصاص. وبمجرّد أن تنتقل الحالة إلى منطقة غير قابلة للامتصاص، يُعطَّل الامتصاص لتلك الحالة بشكل دائم — وهذا بالضبط ما تحتاجه §2.5 و§2.6 لتصحّ على المستوى الخوارزمي.

3.3 الملاحة — مبادلة المُتعلِّق ذات المقعد الواحد

تعابير DEFINE تعابير SQL عادية تُقيَّم على صفّ، لكنّها قد تشمل PREV أو NEXT أو FIRST أو LAST — إشارات تشير إلى صفوف مختلفة. الصفوف نفسها مخزّنة بالفعل في tuplestore النافذة؛ وما يتعيّن على المنفّذ إدارته هو مقعد المُتعلِّق الذي تقرأ منه آلية تعابير SQL، إذ ترتبط الإشارات إلى الأعمدة داخل التعبير بمقعد عند زمن التخطيط. ويُعيد التنفيذ استخدام مقعد ملاحة واحد لكلّ استدعاء ملاحة: يُبدَّل المقعد قبل تقييم التعبير الداخلي ثم يُستعاد بعده، فلا تشعر بقيّة آلية تعابير SQL بالفرق.

النموذج الذي يراه المنفّذ صغير: ثمّة مقعد الصف الحالي يحمل الصف الذي يُقيَّم تعبير 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

الخدعة أنّ ثمّة مقعدًا واحدًا فقط يُحفظ ويُستعاد. التعبير الداخلي — أيًّا كان، بما في ذلك الحساب أو استدعاءات الدوال أو إشارات الأعمدة الأخرى — يجري تجاه المقعد المُبدَّل عبر مسار التقييم ذاته الذي سيستخدمه للصف الحالي. لا مُقيِّم بديل، ولا مقعد ظلّ، ولا نسخ مُتعلِّق.

تُسطَّح الملاحة المركّبة عند التحليل النحوي حتى تبقى المبادلة مرّة واحدة. يُتعرَّف على 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 ثم خطوة
  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،
   نطاق التجزئة للخطوة الخارجية)

تُختصر مخبّأة المواضع جلب tuplestore حين تستهدف عدّة استدعاءات ملاحة في DEFINE ذاته الصف نفسه — وهو شائع في تعابير مثل price > PREV(price) AND volume > PREV(volume) حيث يحلّ كلا الاستدعاءين إلى الصف السابق. تخزّن المخبّأة فقط "آخر موضع مجلوب"، وتبقى المبادلة ذاتها عملية واحدة.

تصنيف استدعاءات الملاحة هو إسهام المُخطِّط في قرار الامتصاص. يتجوّل المُخطِّط في كلّ تعبير DEFINE ويفرز كلّ متغيّر إلى أحد دلوَين، بناءً على ما إذا كانت جميع السياقات ستحسب البولياني ذاته عند الصف ذاته، أم سيحسب كلّ سياق بوليانه الخاص. يحدّد الدلو شيئين عند التشغيل: عدد مرّات تقييم المتغيّر (مرّة مشتركة، أو مرّة لكلّ سياق متأثّر — §3.5 المرحلة 1)، وما إذا كانت الحالة المحيطة مؤهَّلة لامتصاص السياق (§2.5 مقابل §2.6).

يُجرى التصنيف في وقت التخطيط ويُخزَّن إلى جانب كلّ متغيّر DEFINE، فلا يقضي وقت التشغيل وقتًا في القرار — بل يقرأ ببساطة الدلو لكلّ متغيّر أثناء معالجته صفًّا.

ميزانية الاحتفاظ

تصل الملاحة إلى صفوف كانت آلية دوال النوافذ ستكون قد تجاوزتها. ولإبقاء تلك الصفوف متاحة، يُبنى المنفّذ فوق tuplestore يحتفظ بنافذة منزلقة من الصفوف الحديثة؛ والسؤال هو ما عرض تلك النافذة المطلوب. يقرّر الترقيع ذلك في وقت الترجمة، انطلاقًا من إزاحتين متكاملتين:

ميزانية الاسترجاع

كم تستطيع أيّ استدعاء DEFINE الوصول إلى الوراء من الصف الحالي.

المساهمات: PREV، وLAST بإزاحة، وPREV(LAST(...))، وNEXT(LAST(...))

ميزانية الاستشراف من البداية

كم تستطيع أيّ استدعاء DEFINE الوصول إلى الأمام (أو الوراء، حين تكون سالبة) من بداية مطابقة أقدم سياق حيّ.

المساهمات: FIRST، وPREV(FIRST(...))، وNEXT(FIRST(...))

عند التشغيل، تُضبط علامة تشذيب tuplestore على الأبكر بين موضعين — الصف الحالي ناقص ميزانية الاسترجاع، وبداية مطابقة أقدم سياق حيّ زائد ميزانية الاستشراف. أيّ شيء قبل تلك العلامة لا يمكن لأيّ استدعاء ملاحة في أيّ سياق حيّ الوصول إليه، ويستطيع tuplestore إسقاطه. عدّادَا Nav Mark اللذان يُبلَّغ عنهما في EXPLAIN (§3.7) — Lookback وLookahead — هما الذروتان المقاستان للميزانيتين، أي أبعد ما اضطُرّ المنفّذ للوصول إليه في كلّ اتّجاه على مدى الاستعلام.

3.4 حدود المطابقة — SKIP، وINITIAL، والإطار المقيّد

تُسجَّل المطابقة الناجحة بحزمة قيم صغيرة: عَلَم صلاحية، وعَلَم نجاح/فشل، والصف الذي تبدأ عنده المطابقة، وعدد الصفوف التي استهلكتها. حين يكون عَلَم الصلاحية مضبوطًا، يمكن للاستعلامات اللاحقة على المنفّذ — "هل هذا الصف داخل مطابقة؟" — الإجابة بـO(1) عبر فحص الحزمة. والطول الصفر نتيجة حقيقية لا خطأ: يمثّل نمطًا طوبق دون استهلاك أيّ صفّ، ويجب على المنفّذ تمييزه من "لم تُحاوَل أيّ مطابقة عند هذا الموضع بعد".

تقرّر جملة AFTER MATCH SKIP أين تبدأ محاولة المطابقة التالية. AFTER MATCH SKIP PAST LAST ROW ينتقل إلى الصف الذي يلي نهاية المطابقة، فينتج المخرجات غير المتداخلة التي تريدها معظم الاستعلامات ويُمكِّن تحسين الامتصاص.

AFTER MATCH SKIP TO NEXT ROW ينتقل فقط إلى الصف الذي يلي بداية المطابقة، مسموحًا بمطابقات متداخلة؛ ولذلك يُعطّل المُخطِّط الامتصاص لخطّة الاستعلام بأكملها حين يكون هذا الوضع ساريًا.

هدفا التخطّي الآخران اللذان يُعرّفهما المعيار — AFTER MATCH SKIP TO FIRST متغيّر وAFTER MATCH SKIP TO LAST متغيّر — يعتمدان على تاريخ كلّ مطابقة الذي لا يحتفظ به هذا الترقيع. وهما غائبان عن القواعد النحوية أصلًا، فيُصدِر المحلّل خطأ نحويًا عامًّا إذا قُدِّم أيٌّ منهما.

وينطبق الأمر ذاته على SEEK، بديل المواصفة لـINITIAL. تحت SEEK، قد تنجح محاولة مطابقة تبدأ عند الصف R في أيّ صفّ من R إلى نهاية الإطار، لا عند R وحده. يُنفّذ الترقيع INITIAL فقط: كلّ مطابقة محتملة تترسّى عند صفّ محدّد. يصدر المحلّل خطأ إذا طُلب SEEK. تتلقّى الأطر المقيّدة معالجتها الخاصة — حين يكتب المستخدم ROWS BETWEEN CURRENT ROW AND N FOLLOWING بدل UNBOUNDED FOLLOWING، يقصر المنفّذ أيّ سياق وصلت مطابقته إلى الحدود بإجبار عدم مطابقة، ويُعطَّل الامتصاص لأنّ الحدود تكسر افتراض الرتابة الذي يقوم عليه.

3.5 محرّك الصف الواحد ذو المراحل الثلاث

يستدعي مُحرّك الصف الواحد للمنفّذ آليّة دوال النوافذ المحيطة كلّما احتاجت معرفة ما إذا كان صفّ ما ينتمي إلى إطار مُطابَق. يجد المحرّك أو يُنشئ السياق لموضع البداية الحالي، ويُقيِّم كلّ مُسند DEFINE مرّة واحدة تجاه الصف الحالي لينتج مصفوفة بوليانية لكلّ متغيّر، ثم يدفع NFA إلى الأمام صفًّا واحدًا. خطوة التقدّم نفسها ثلاث مراحل بترتيب ثابت — Match، Absorb، Advance — ملفوفة في الحلقة الخارجية ذاتها:

processRow(currentPos):

  # المرحلة 1 — MATCH (تقارب)
  لكلّ context:
      إذا context تجاوز frame محدودًا:
          افرض mismatch (إنهاء مبكّر)
          continue
      إذا اختلف matchStartRow عن
         موضع التقييم المشترك:
          أعد تقييم متغيرات DEFINE
          المعتمدة على بدء المطابقة (§3.3)
      match(context, varMatched)

  # المرحلة 2 — ABSORB
  إذا كان pattern قابلًا للامتصاص:
      حدّث أعلام كلّ 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):
  لكلّ state في context:
      elem = pattern[state.elemIdx]
      إذا elem ليس متغيّرًا:
          continue   # advance يتولّاه

      إذا ليس varMatched[elem.varId]:
          أسقط state   # فرع ميّت
          continue

      state.counts[elem.depth] += 1

      # تقدّم أمامي inline حتى
      # تستطيع المرحلة التالية
      # المقارنة عند عنصر نقطة
      # المقارنة بدلاً من منتصف
      # التكرار.
      إذا elem في in-region لكن ليس
         نقطة المقارنة،
         وبلغ count الأقصى،
         وكان elem.next group end:

          سِرْ في سلسلة END:
            زِد count المجموعة الخارجية
            قدّم state.elemIdx إلى END
            تابع ما دام in-region،
              must-exit، وnext يساوي END
          (يتوقّف عند نقطة المقارنة
           أو عند عنصر لا يزال loopable)

تجوّل سلسلة END هو ما يجعل المجموعات المُعشَّشة ذات الطول الثابت قابلة للامتصاص. في ((A B){2})+، حين يبلغ B حدّه الأعلى (B هو {1,1})، يجب أن يُزاد عدّ المجموعة الداخلية؛ وإذا بلغ ذلك العدّ حدّه الأعلى أيضًا — مُغلقًا الـ{2} الداخلية — يجب أن يُزاد عدّ المجموعة الخارجية أيضًا، وهكذا، حتى تستقرّ الحالة على نقطة الامتصاص الأبعد — END للمجموعة الخارجية غير المحدودة (الـ+). فعل هذا العمل في Match يتيح لـAbsorb المقارنة بسياقات وحّدت أعدادها لما بعد التكرار.

المرحلة 2 — Absorb

تتجوّل تمريرة Absorb في السياقات من الأحدث (الذيل) إلى الأقدم (الرأس). لكلّ سياق قيد التقدّم وقابل للامتصاص بالكامل، تمسح إلى الوراء بحثًا عن سياق أقدم قيد التقدّم يغطّيه، وتُحرّر الأحدث إذا وُجد. ولأنّ السياقات تُحفظ بترتيب الإنشاء وكلّ صفّ يُنشئ سياقًا واحدًا على الأكثر، فإنّ "أحدث" و"أقدم" تعني فعلًا "بدأ متأخّرًا" و"بدأ مبكّرًا".

absorb_contexts():
  لـ ctx من الذيل إلى الخلف:
      إذا انتهى ctx
         أو لديه أيّ state غير قابل للامتصاص:
          تخطَّ
      لـ older من ctx.prev إلى الخلف:
          إذا انتهى older
             أو ليس لديه state قابل للامتصاص:
              تخطَّ
          إذا covered(older, ctx):
              free(ctx)
              سجّل طول الامتصاص
              break

covered(older, newer):
  لكلّ state في newer:
      elem = pattern[state.elemIdx]
      إذا elem ليس نقطة المقارنة:
          return false
      إذا لا يوجد state في 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):
  استخرج كلّ states الحالية؛
  أعد بناء ctx.states من الصفر
  لكلّ state بالترتيب المعجمي:
      امسح bitmap العناصر المزارة
      advance_state(state)   # DFS

      # تفضيل: حالما يبلغ DFS الـ FIN،
      # تكون states المتبقية أقلّ
      # تفضيلًا ويمكن إسقاطها.
      إذا بُلِغَ FIN وبقيت states:
          حرّر الباقي
          break

advance_state(state):
  سِرْ عبر state.elemIdx،
  وكرّر تعاوديًا عبر:
    فروع ALT (بالترتيب)،
    BEGIN (دخول المجموعة؛ ومسار تخطٍّ
           اختياري إذا min = 0),
    END (loop back / exit / fast-forward —
         انظر أدناه),
    FIN (سجّل matchEndRow،
         واحفظ matchedState، وقلّم
         contexts اللاحقة داخل
         مدى هذا المرشح — انظر أدناه),
  مع التوقّف عند كلّ متغيّر يُصادَف:
      أضف state إلى 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 أبدًا
  → تفشل المطابقة (خاطئ)

يُحسم الإصلاح في وقت الترجمة ويُنفَّذ في وقت التشغيل. كلّما رأى المُخطِّط مجموعة جسمها قابل للنفي، يَسِم عنصر END لتلك المجموعة بـقابل للدوران الفارغ. وعند التشغيل، حين يهمّ معالج END بالعودة إلى الالتفاف لأنّ عدّ التكرار لا يزال دون الحدّ الأدنى، تُخبره وسمة الدوران الفارغ باستنساخ حالة تخطٍّ سريع إضافية إلى جانب مسار الالتفاف العادي:

advance_end (count دون min):

  المسار الأساسي:
    عُد بالتكرار إلى الجسم
    (يُبقي الباب مفتوحًا لمطابقة
     حقيقية غير فارغة في
     التكرار التالي)

  إذا elem كان empty-loopable:
    مسار fast-forward:
      صفِّر count هذا العمق
      اخرج من المجموعة عبر next،
      معاملًا التكرارات المطلوبة المتبقية
      بوصفها مطابقات فارغة

يلعب المساران دورين متكاملين. الالتفاف الأساسي يلتقط الحالة التي لا يزال للجسم فيها مطابقات حقيقية ينتجها لاحقًا — مثلًا، في (A?){2,3} متبوعًا ببيانات لا يطابق فيها A إلا في صفوف لاحقة، فالالتفاف هو ما يُتيح للتكرارَيْن الثاني والثالث إيجاد مطابقات غير فارغة. والتخطّي السريع يلتقط الحالة التي لا ينتج فيها الجسم شيئًا أبدًا: يلتفّ على حارس الدورة بالخروج من المجموعة كلّيًا، مُعلِنًا "بقيّة التكرارات المطلوبة فارغة"، فيُنجح المطابقة بجسم بطول صفر. تُضاف الحالتان إلى السياق؛ وأيّتهما تُمدّد بنجاح تفوز، ويمنع فحص إزالة التكرار عند الإدراج أيًّا منهما من إنجاب أكثر من حصّتها من الحالات.

إلى جانب حارس الدورة، تخفّف خدعة بدء أخرى التباس النتائج صفرية الصفوف عند بداية السياق تمامًا. خطوة إنشاء السياق عند كلّ صف بداية محتمل تُجري تقدّمًا أوّليًا عبر انتقالات إبسيلون قبل استهلاك أيّ صفّ، باستخدام موضع يسبق البداية الفعلية بصفّ. أيّ مسار يصل إلى رمز FIN عبر انتقالات إبسيلون وحدها — دون استهلاك صفّ — يُنتج موضع نهاية أصغر من موضع البداية؛ وذلك الإحداثي ذو المدى السالب، مع ما إذا كان FIN قد بُلِغ فعلًا، يُشفِّر الفرق بين مطابقة فارغة (مطابقة بطول صفر مقبولة) وبداية غير مطابِقة دون الحاجة إلى عَلَم منفصل.

3.6 كيف يبقى فضاء الحالة محدودًا

خطّية وقت التشغيل ليست نتيجة تحسين منفرد. بل هي الأثر التراكمي لمجموعة طبقية من قواعد التشذيب، تلتقط كلٌّ منها سببًا مختلفًا لنموّ فضاء الحالة عند نقطة مختلفة من دورة الصف. بعضها يُحسم وقت الترجمة ولا يُستشار إلا وقت التشغيل؛ والبعض الآخر يُطلق ديناميكيًا. بعضها يقتل حالات مفردة؛ والآخر يقتل سياقات بأكملها. قدّمت الأقسام أعلاه كلًّا منها في سياقه؛ والجدول أدناه يضعها على صفحة واحدة.

مُسند فاشل Match

حالات متغيّرات قُيِّمَت DEFINE الخاصة بها false على الصف الحالي — فروع ميتة.

تقدّم سلسلة END المضمَّن Match

متغيّرات بلغت حدّها الأقصى وكانت ستترك الحالة في منتصف التكرار؛ تُقدَّم عبر نهايات المجموعات ذات الطول الثابت ليتسنّى للامتصاص المقارنة عند النقطة الصحيحة.

امتصاص السياق Absorb

سياقات أحدث كلّ حالاتها مغطّاة بحالة سياق أقدم بعدّ أعلى — راجع §2.5 للقاعدة المفهومية، و§3.2 للأهلية وقت الترجمة، و§3.5 للفحص بين كلّ زوج.

إزالة تكرار الحالات Advance

حالات بُلِغت عبر فروع DFS مختلفة وانتهت إلى الموضع ذاته بالأعداد ذاتها — تنجو الأولى فقط (الأسبق معجميًا)؛ وتُسقَط المكافئات اللاحقة بصمت، وهو أيضًا كيفيّة فرض التفضيل (§2.4).

إنهاء FIN المبكّر (داخل السياق) Advance

حالات لا تزال معلّقة في طابور DFS حين يصل فرع إلى FIN — وفق الترتيب المعجمي، كلّ الحالات المتبقّية أقلّ تفضيلًا ويمكن إسقاطها فورًا.

تشذيب المطابقة المرشّحة (عبر السياقات) On FIN

سياقات أخرى يقع صف بدايتها داخل مدى المطابقة المرشّحة — قد يستمرّ السياق الذي أصاب FIN في البحث عن مطابقة أطول (تراجع جشع)، لكن تحت AFTER MATCH SKIP PAST LAST ROW فإنّ أيّ سياق داخل مدى المرشّحة لم يعد قادرًا على إنتاج مخرجات قابلة للتقرير، بصرف النظر عن كيفيّة انتهاء ذلك البحث، فيُشذَّب فورًا.

حارس الدورة Advance

توسيعات إبسيلون تُعيد زيارة العنصر النمطي ذاته ضمن DFS ذاته — لكانت لولا ذلك لتلتفّ إلى الأبد في المجموعات القابلة للنفي.

التخطّي السريع للدوران الفارغ Advance

مطابقات تكرار فارغ مشروعة كان حارس الدورة سيقتلها في المجموعات القابلة للنفي — يلتفّ على الدورة بالخروج من المجموعة وإعلان التكرارات المتبقّية المطلوبة فارغة.

قطع الإطار المقيّد Match

سياقات وصلت مطابقتها إلى الحدّ الأعلى للإطار الذي حدّده المستخدم — تُجبَر على عدم المطابقة فلا يمكنها التمدّد خلفه (§3.4).

قراءة المداخل بحسب وسم مرحلتها تتعقّب عمر السياق: يُطلق التشذيب عند كلّ صفّ عبر المراحل الرئيسة الثلاث (Match وAbsorb وAdvance)، ومرّة أخرى عند اكتمال المطابقة (On FIN). أمّا قراءة الأوصاف فتجمع القواعد بحسب ما تستهدفه: فروع ميتة، وسياقات زائدة، وحالات مكافئة، وحلقات لانهائية، وامتداد متجاوز للحدود التي يفرضها المستخدم.

لا تكفي قاعدة منفردة بحدّ ذاتها. حارس الدورة وحده سيقتل مطابقات مشروعة في المجموعات القابلة للنفي؛ والتخطّي السريع للدوران الفارغ وحده لن يوقف حلقات إبسيلون اللانهائية؛ والامتصاص وحده سيُفرط في التوحيد حين يُشير 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 أدوات قياس مباشرة لوقت التشغيل: كم حالة كانت حيّة في آنٍ واحد، وكم أُنشئت على مدى عمر الاستعلام، وكم دُمج بإزالة التكرار. تَفصِل توزيعات أطوال المطابقات أربع نتائج — مطابقات ناجحة، ومحاولات مطابقة فاشلة، وسياقات مُمتصّة، وسياقات شُذِّبت (سُكِبَت) دون تقييم — والإبلاغ عنها بـmin/max/avg يُبيّن الباثولوجيات الأدائية بنظرة: في الجولة السليمة تظهر معظم السياقات إمّا مطابِقة وإمّا مُمتصّة، وأطوال غير المطابقة صغيرة.

عدّادَا Nav Mark يُبلِّغان عن ميزانية احتفاظ tuplestore التي تستنبطها §3.3 وقت الترجمة. Lookback هو أعمق وصول إلى الوراء عبر PREV وLAST بإزاحة والصيغ المركّبة بـLAST داخلية؛ بينما Lookahead هو أعمق وصول إلى الأمام (أو الوراء، حين يكون سالبًا) مقاسًا من بداية مطابقة أقدم سياق حيّ، تساهم به FIRST والصيغ المركّبة بـFIRST داخلية.

يُطبَع كلّ عدّاد عددًا صحيحًا ثابتًا حين تكون الإزاحة ثابتًا، و"runtime" حين تكون الإزاحة تعبيرًا غير ثابت يجب تقييمه عند كلّ استدعاء، و"retain all" حين يحتاج وقت التشغيل إلى ميزانية غير محدودة. لا يُصدَر Lookahead إلا حين يستخدم الاستعلام فعلًا ملاحة نسبية لبداية المطابقة.

معًا، تُتيح هذه العدّادات تنقيح أداء RPR دون توصيل gdb بالخادم.

إلى جانب العدّادات، يُعيد EXPLAIN أيضًا إنتاج جُمل PATTERN وDEFINE الأصلية بأمانة، بما في ذلك المُكمِّمات المتمنّعة، وتكرار المجموعات، وخيار AFTER MATCH SKIP. ويبذل التنفيذ جهدًا لجعل هذه الرحلة الذهابية والإيابية مستقرّة، ليتمكّن pg_dump وpg_upgrade من حفظ كائنات RPR دون انجراف دلالي — وتتحقّق سلسلة الانحدار rpr_explain منها حالةً حالة (راجع §4).

§4. الاختبارات — خريطة التغطية

يأتي الترقيع مع خمس سلاسل انحدار تُمارس معًا كلّ طبقة وُصفت في §3 — نحو 13,000 سطر من SQL، كلّ سلسلة تركّز على شأن مختلف. الفصل متعمَّد: إبقاء شؤون المحلّل النحوي وصحّة وقت التشغيل وتفاعلات المُخطِّط وتنسيق المخرجات في ملفّات منفصلة يُسهّل توطين الأخطاء، ويمنع تغييرًا غير ذي صلة في طبقة من إبطال اختبارات في أخرى عَرَضًا. السلاسل الخمس هي:

rpr

دلالات الاستعلام الشاملة — سيناريوهات نوافذ واقعية على بيانات أسهم اصطناعية (شكل V، شكل W، ارتفاعات متتالية، انعكاسات).

rpr_base

طبقة المحلّل النحوي — قبول الكلمات المفتاحية، وأشكال البنية النحوية، والمُكمِّمات، وتحليل الملاحة، ورسائل الأخطاء، واستقرار رحلة pg_dump/pg_upgrade ذهابًا وإيابًا.

rpr_nfa

وقت تشغيل NFA — الحلقة ثلاثية المراحل، والامتصاص في كلّ شكل قابل للامتصاص، وحالات حافة دورة حياة السياق.

rpr_explain

تنسيق المخرجات — إحصاءات NFA، وتفكيك النمط، واقتباس المعرّفات، واستقرار التنسيق عبر إعادة التحميل.

rpr_integration

تفاعلات المُخطِّط — حراسات تمنع تحسينات نافذة غير ذات صلة من إفساد دلالات RPR.

4.1 rpr — السيناريوهات الشاملة

سلسلة السيناريو هي الواجهة العامّة لمجموعة الاختبارات: تستخدم مجموعة بيانات أسعار أسهم اصطناعية بنحو 1,600 صفّ وتشغّل عليها استعلامات واقعية — تعافي شكل V، شكل W (قاع مزدوج)، ارتفاعات وانخفاضات متتالية، أنماط انعكاس، أقسام متعدّدة الرموز. وهي السلسلة الوحيدة التي تُقرأ مدخلاتها ومخرجاتها كاستعلامات قد يكتبها مستخدم فعلًا؛ والأخريات تختزل عمدًا، تركّز على طبقة واحدة في كلّ مرّة.

لأنّ هذه الاستعلامات تجمع كلّ طبقة (المحلّل النحوي، والمُخطِّط، والمنفّذ، وEXPLAIN)، فإنّ فشلًا منفردًا في rpr نادرًا ما يخبرك أين يقطن الخلل. السلاسل الأربع التي تليه هي التنصيف: فشل في rpr مع نجاح rpr_base يستبعد المحلّل النحوي؛ مع نجاح rpr_nfa يضيّق النطاق إلى أشكال بيانات خاصّة بالسيناريو؛ مع نجاح rpr_integration يستبعد تدخّل المُخطِّط؛ وأيّ انجراف في التفكيك يظهر في rpr_explain.

4.2 rpr_base — واجهة المحلّل النحوي

سلسلة base هي الأكبر، وهي كذلك لسبب: مسؤوليّتها إثبات أنّ كلّ قطعة بنية شرعيّة في §1.2 تتحلّل فعلًا، وأنّ كلّ قطعة غير شرعيّة في §1.3 تُرفض برسالة خطأ مفيدة، وأنّ كلّ صيغة مقبولة تنجو من رحلة سَلسَلة. معظمها على هيئة مقتطفات صغيرة مركّزة — واحد لكلّ سمة نحوية — لا استعلامات واقعية طويلة، إذ الهدف التغطية لا واقعيّة السيناريو.

تستحقّ اختبارات السَلسَلة اهتمامًا خاصًّا. يجب على كائنات RPR (المشاهدات، والمشاهدات الموصّدة، ومخرجات pg_dump) أن تجتاز رحلة العودة عبر تمثيل الكتالوج دون انجراف دلالي، بما في ذلك دقائق مثل عَلَم التمنّع على المُكمِّم أو الصيغة الدقيقة لتعبير ملاحة مركّب. مجموعة صغيرة من الكائنات الخاصّة بالسَلسَلة (مشاهدات rpr_serial_v* وجداولها الداعمة) تُترك عمدًا في مكانها في نهاية الجولة، لتلتقطها بنية الانحدار المحيطة وتُمارس عليها pg_dump وpg_upgrade. أمّا بقيّة سقالة الاختبار فتُسقَط كالعادة. الأخطاء التي تُلتقَط بهذه الطريقة (مثل ضياع عَلَم التمنّع عبر التفكيك وإعادة التحليل) لا تظهر إلا حين تُمارَس الرحلة من طرف إلى طرف.

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 بالتسميات الموثّقة.
• الأنماط تُفكَّك بشكل صحيح — كلّ شكل مُكمِّم، بما في ذلك المتغيّرات المتمنّعة والصيغ المقيّدة؛ وكلّ تبديل؛ وكلّ مجموعة؛ وكلّ صيغ AFTER MATCH SKIP؛ وINITIAL؛ واستدعاءات الملاحة بإزاحات؛ والملاحة المركّبة. ويجب أن يعود النصّ المُفكَّك عبر المحلّل النحوي دون تغيير.
• اقتباس المعرّفات صحيح — تُصدَر متغيّرات النمط وتعابير DEFINE بقواعد الاقتباس ذاتها لمعرّفات SQL العادية، فلا تُكسر أسماء المتغيّرات غير المعتادة مخرجات pg_dump.

كحال rpr_base، تترك هذه السلسلة كائناتها عمدًا في مكانها في نهاية الجولة لتمتدّ تغطية pg_dump وpg_upgrade إلى آثار جانب explain أيضًا.

4.5 rpr_integration — تفاعلات المُخطِّط

لمُخطِّط PostgreSQL تحسينات عديدة تعمل على استعلامات النوافذ — توحيد الإطار الكنسي، ودفع شرط التشغيل، وإزالة تكرار النوافذ المتطابقة، وإسقاط المخرجات غير المستخدمة، وانتقالات معكوسة لتجميعات متحرّكة — وقد صُمِّم كلّ منها دون اعتبار لـRPR. ومعظمها غير آمن للتطبيق حين تحمل النافذة جملة PATTERN: فالإطار جزء من عقد المطابقة، والمخرجات المطابِقة لم تعد رتيبة بأيّ شكل واضح، ونافذتان بمواصفة واحدة وDEFINE مختلفين تُنتجان نتائج مختلفة فعلًا. تتحقّق سلسلة التكامل من أنّ كلّ تحسين منها مُعطَّل أو مُتجاوَز بشكل صحيح لنوافذ RPR:

توحيد الإطار الكنسي

عادةً يُعيد المُخطِّط كتابة 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 ذا شكل بنيوي مماثل ويتحقّق من عدم تطبيق التحسين. الشطران معًا يثبتان أنّ الحارس في المُخطِّط يقوم بعمل حقيقي، لا أنّه يُجيز كلّ استعلام دون تحقّق فعلي.

هذه السلسلة هي أيضًا سبب قصر §3.4. آليّات "حدود المطابقة" — الإطار المختزل، وSKIP، وINITIAL، وقطع الإطار المقيّد — تُختبر تشغيليًا في مكان آخر؛ وما يتحقّق منه rpr_integration هو أنّ لا مرحلة مُحسِّن أخرى تعبث بها أثناء المرور. نجاح rpr_integration هو ما يتيح لبقيّة السلاسل الثقة بأنّ مدخلاتها تصل إلى المنفّذ سليمة.