التعرّف على أنماط الصفوف تعمّق تقني
جولة موجَّهة في ISO/IEC 19075-5 · SQL R020 ضمن PostgreSQL — ما الذي بنيناه، وما الذي لم يُكتب بعد، وكيف يعمل فعلًا.
تصفّح المعيار، استعرض الأمثلة العملية، تفحّص التصميم، ثم شغّل محاكي NFA حيًّا بأنماطك الخاصة.
النقاش: سلسلة pgsql-hackers · أحدث ترقيع (v55) · commitfest #4460.
ترجمة مسبقة بالذكاء الاصطناعي — قد توجد أخطاء.
§1. المعيار، والمجموعة الجزئية، والأسئلة المفتوحة
1.1 نطاق المعيار
أُدخل التعرّف على أنماط الصفوف إلى SQL في معيار ISO/IEC 9075-2:2016، وهو موصوف في الوثيقة المرافقة ISO/IEC 19075-5:2021 (الجزء 5، "Row Pattern Recognition").
يحدّد المعيار واجهتين لنفس الآلية الكامنة. الميزة R010 تضع جملة MATCH_RECOGNIZE في قائمة FROM لإنتاج جدول مشتق؛ بينما الميزة R020 تطوي منطق النمط ذاته داخل مواصفة WINDOW لإنتاج مخرجات دوال النوافذ. تشترك الواجهتان في قدر كبير من البنية النحوية والدلالات (تذكر 19075-5 في §6.3.3 بعض الفروق الخاصة بـR020)، إلا أنّهما نقطتا دخول وظيفيّتان متمايزتان — وقد تُنفّذ قاعدة البيانات إحداهما أو كلتيهما.
سلسلة الترقيعات قيد النقاش هنا تُنفّذ مجموعة جزئية من R020 فقط؛ أمّا صيغة جملة الجدول فهي خارج النطاق عمدًا.
واجهة R020 صغيرة لكنّها معبّرة. يربط الاستعلام نمطًا بنافذة بإضافة جُمل داخل مواصفة نافذة إطارها ROWS BETWEEN CURRENT ROW AND …: PATTERN تصف تعبيرًا منتظمًا فوق متغيّرات نمط مُسمّاة، وDEFINE توفّر المُسند البولياني الذي يُعرّف كلّ متغيّر، وAFTER MATCH SKIP الاختيارية (الافتراضي PAST LAST ROW) تتحكّم في كيفية ترتيب المطابقات المتتالية داخل القسم.
تكتمل الميزة بـMEASURES، وSUBSET، وINITIAL/SEEK الاختيارية، إضافة إلى الدالة المساعدة CLASSIFIER(). (تنتمي دالة MATCH_NUMBER() المعيارية إلى واجهة R010 فقط — إذ تستثنيها 19075-5 §6.3.3 (6) صراحةً من R020.)
يغطّي الترقيع ما يكفي من هذه المفردات لجعل الاستعلامات غير التافهة تعمل، لكنّه يتوقّف دون عدّة بنى يعتمد تنفيذها على بنية تحتية لم تُبنَ بعد.
يقسم ما تبقّى من هذا القسم مفردات المعيار إلى ما يدعمه الترقيع فعلًا وما تركه عمدًا لمراحل لاحقة. تعكس القوائم أدناه الحالة الراهنة لسلسلة الترقيعات.
1.2 الميزات المُنفَّذة
تكفي المفردات المُنفَّذة للتعبير عن الأنماط الكلاسيكية: الشكل V، والشكل W، وأنماط الانعكاس التي تشكّل الدافع الأساسي للتعرّف على أنماط الصفوف. كما تغطّي كلّ المُكمِّمات المعيارية — بما في ذلك جميع المتغيّرات السبع المتمنّعة (reluctant) *?، +?، ??، {n}?، {n,}?، {,m}?، {n,m}? — وأوّليّات الملاحة الأربع التي تحتاجها شروط DEFINE لمقارنة الصفوف المتجاورة.
- جملة PATTERN
- تُعرّف نمط الصفوف داخل مواصفة النافذة؛ بحدّ أقصى 240 متغيّر نمط متمايز.
- إطار النافذة
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGأوROWS BETWEEN CURRENT ROW ANDnFOLLOWINGحيث n ≥ 1 (19075-5 §6.10.2)؛ ويُرفض أيّ إطار آخر، وEXCLUDE NO OTHERSهو الاستبعاد الوحيد المقبول.- التعابير المنتظمة: + * ? |
- المُكمِّمات المعيارية والتبديل.
- التعابير المنتظمة: تجميع ( )
- أنماط فرعية بين قوسين.
- التعابير المنتظمة: {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))— وتقبل كلّ من الخطوة الداخلية والخارجية إزاحتها الخاصة. - أسماء الملاحة
PREVوNEXTوFIRSTوLASTالمكتوبة استدعاءاتٍ غير مؤهَّلة داخلDEFINEتعني الملاحة دائمًا؛ ويجب تأهيل دالّة المستخدم التي تحمل الاسم نفسه باسم المخطّط (schema) هناك.- وسائط الملاحة
- في
PREVوNEXTوFIRSTوLAST، يجب أن يحتوي الوسيط الداخلي على إشارة واحدة إلى عمود على الأقل، ويجب أن تكون الإزاحة ثابتًا في وقت التشغيل. - INITIAL
- يجب أن تبدأ مطابقات النمط عند الصف الحالي (الافتراضي).
- AFTER MATCH SKIP PAST LAST ROW
- وضع التخطّي الافتراضي؛ مؤهّل لامتصاص السياق.
- AFTER MATCH SKIP TO NEXT ROW
- يسمح بمطابقات متداخلة؛ يُعطّل الامتصاص.
1.3 غير المُنفَّذ
تنقسم الميزات التي لم تُنفَّذ بعد إلى ثلاث مجموعات فضفاضة. الأولى — وهي الأكبر بفارق كبير — هي عائلة البنى المتمحورة حول MEASURES: جملة MEASURES ذاتها، وSUBSET، وCLASSIFIER()، والإشارات إلى الأعمدة المُؤهَّلة بالنمط مثل B.price، والملاحة المُؤهَّلة بالنمط مثل LAST(B.price) أو PREV(B.price).
وهذه ليست فجوات مستقلّة بقدر ما هي إطلالات مختلفة على قطعة مفقودة واحدة: إذ سيتعيّن على المنفّذ الاحتفاظ بـتاريخ لكلّ مطابقة — سجلّ يبيّن، لكلّ صف في المطابقة، إلى أيّ متغيّر نمط جرى ربطه — ولا تملك أيّ من هذه البنى تعريفًا ذا معنى دون ذلك. تقرأ CLASSIFIER() اسم المتغيّر من ذلك السجلّ؛ ويقرأ B.price عمود السعر من الصفوف التي تنصّ مدخلات سجلّها على B؛ ويتجوّل LAST(B.price) في المجموعة نفسها ويختار آخر صف؛ وتُعرّف SUBSET U = (A, B) متغيّرًا افتراضيًا يُجمِّع فوق الدلوين معًا؛ وتُقيِّم MEASURES تعابير مثل AVG(U.Price) باستخدام هذا التجميع بالضبط.
يقيّم المنفّذ الحالي مُسندات DEFINE صفًّا بصف، لكنّه لا يُسجّل أيًّا من تخصيصات المتغيّرات الناتجة في مكان ما — فلا شيء يمكن الاستعلام عنه لاحقًا. لذا فإنّ بناء البنية التحتية للتاريخ هو الشرط المسبق لكامل المجموعة؛ وتنبثق الميزات الفردية بوصفها إسقاطات صغيرة بمجرّد وجود السجلّات.
تتعلّق المجموعة الثانية بأهداف تخطٍّ بديلة: AFTER MATCH SKIP TO FIRST متغيّر وAFTER MATCH SKIP TO [LAST] متغيّر (فـSKIP TO متغيّر المجرّدة تعني SKIP TO LAST متغيّر). وهذه أيضًا تعتمد على تاريخ المطابقات، إذ يجب أن يكون المنفّذ قادرًا على الإشارة إلى الصف المربوط بمتغيّر معيّن داخل أحدث مطابقة.
أمّا العناصر المتبقّية فذيل غير متجانس: كلمة SEEK المفتاحية (بديل INITIAL)، والنمط الفارغ ()، وصيغة الاستبعاد {- … -}، ومُعامل PERMUTE غير المتأثّر بالترتيب، ودوال التجميع والاستعلامات الفرعية في DEFINE، وكلاهما مرفوض حاليًا (فالتجميع المؤهَّل بمتغيّر سيحتاج أيضًا إلى تاريخ المطابقات).
- MEASURES
- تعابير مخرجات مُسمّاة لكلّ مطابقة، مثل
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg؛ تُعرض في R020 عبرOVERكدالّة نافذة. تقبل الكلمتين المفتاحيّتين FINAL / RUNNING (19075-5 §5.4)، وتنهاران في R020 إلى القيمة ذاتها لأنّ القياسات تُقيَّم دائمًا عند آخر صف في المطابقة (19075-5 §6.9 (3)). - SUBSET
- اتّحادات مُسمّاة لمتغيّرات النمط، مثل
SUBSET U = (A, B, C). قابلة للاستخدام أينما يمكن الإشارة إلى متغيّر نمط —MEASURES، والإشارات المُؤهَّلة بالنمط فيDEFINE، وCLASSIFIER(U)— وكلّها تحتاج إلى تاريخ المطابقات. - CLASSIFIER()
- تُرجع اسم متغيّر النمط الذي طوبق به الصف. مُعرَّفة لكلّ من DEFINE وMEASURES (19075-5 §5.9)؛ والإجابة عند أيّ صف هي اسم المتغيّر المُسجَّل في تاريخ المطابقة لذلك الصف.
- الإشارة إلى عمود مُؤهَّل بالنمط
- استخدام
B.priceالمجرّد فيDEFINEأوMEASURES— قيمة العمود من الصف المُربط بوصفه المتغيّر المُسمَّى. - الملاحة المُؤهَّلة بالنمط
- تقييد الملاحة بالصفوف المطابِقة لمتغيّر مُسمَّى، مثل
LAST(B.price)، وFIRST(B.price)، وPREV(B.price)، وNEXT(B.price). - SEEK
- قد تبدأ المطابقة عند أيّ صف من الصف الحالي إلى نهاية إطار النافذة الكامل (في مقابل INITIAL).
- AFTER MATCH SKIP TO FIRST var
- التخطّي إلى أوّل صف طوبق بوصفه المتغيّر المُسمَّى.
- AFTER MATCH SKIP TO [LAST] var
- التخطّي إلى آخر صف طوبق بوصفه المتغيّر المُسمَّى.
- التعبير المنتظم: {- -}
- الاستبعاد — يُزيل الصفوف المطابِقة من مخرجات
ALL ROWS PER MATCH. وهذا الخيار لا ينطبق على النوافذ (19075-5 §6.3.3 (4))، لذا فالصيغة مسموح بها في النافذة (§6.13) لكن لا مخرجات لها لتعمل عليها. - التعبير المنتظم: ()
- النمط الفارغ — يطابق التسلسل الفارغ.
- PERMUTE(...)
- مطابقة غير حسّاسة للترتيب عبر المتغيّرات المُدرَجة. يُتعرَّف على الكلمة المفتاحية وتُرفض ("PERMUTE is not supported")؛ ويبقى
permuteصالحًا اسمًا لمتغيّر نمط. - دوال التجميع في DEFINE
- لا تُسمح دوال التجميع مثل
SUM، وAVG، وCOUNTداخل مُسنداتDEFINE. يسمح بها المعيار بوصفها تجميعات جارية فوق المطابقة الجزئية؛ والتجميع المؤهَّل بمتغيّر مثلAVG(B.Price)يعتمد على تاريخ المطابقة ذاته الذي تحتاجهMEASURES/CLASSIFIER()، بينما يمتدّ التجميع غير المؤهَّل على جميع صفوف المطابقة حتى الآن. - الاستعلامات الفرعية في DEFINE
- يُرفض كلّ استعلام فرعي في
DEFINE. يسمح المعيار بالاستعلام الفرعي الذي لا يُجري تعرّفًا على أنماط الصفوف ولا يشير إلى أيّ متغيّر نمط صفوف؛ والترقيع يرفض أكثر من اللازم في الوقت الحالي.
تجدر الإشارة هنا إلى أربع نقاط إضافية، إذ يسهل الخلط بينها وبين الإغفالات.
الأولى أنّ مرسيتي النمط ^ و$ غير مسموح بهما مع 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 الإشارة إلى متغيّرات نمط الصفوف (ويذهب الترقيع أبعد فيرفض كلّ الاستعلامات الفرعية في DEFINE، كما ورد أعلاه)؛ ولا يجوز استخدام RPR داخل استعلام تكراري. يفرض الترقيع قاعدة الإشارات الخارجية ("cannot use outer query column in DEFINE clause") وقاعدة التكرار، والأخيرة على كلّ عنصر من عناصر جملة WITH RECURSIVE. كما يرفض الدوال المتقلّبة (volatile) والإشارات إلى الصف كاملًا في DEFINE.
والرابعة أنّ 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 صفوف (الافتراضي n = 1). استشراف أمامي؛ غير شائع في صيغة النافذة لأنّ النافذة رتيبة.
- FIRST(expr [, n])
- الصف الذي يلي أوّل صفّ في المطابقة الحالية بـn صفوف (الافتراضي n = 0، أي الصف الأوّل ذاته). "قارن بالصف الذي بدأت هذه المطابقة عنده."
- LAST(expr [, n])
- الصف الذي يسبق آخر صفّ مُطابَق بـn صفوف (الافتراضي n = 0). داخل
DEFINEيكون آخر صفّ مُطابَق هو الصف الحالي، لذا فإنّLAST(price)يقرأ الصف الحالي.
تتراكب الأوّليّات الأربع: يمكن لـPREV وNEXT أن تُغلّف استدعاءً لـFIRST أو LAST، فتنتج أربع صيغ مركّبة دلالتها "اذهب إلى صفّ نسبيّ للمطابقة، ثم اخطُ مسافة ثابتة بعيدًا عنه". وهذا ما يتيح لتعبير DEFINE قراءة الصف الذي يسبق بداية المطابقة مباشرةً، مثلًا.
- PREV(FIRST(expr [, n]) [, m])
- اخطُ m صفوف إلى الوراء من الصف الذي يقرؤه
FIRST(expr, n)(الافتراضيّان n = 0، m = 1). "ما القيمة قبيل بداية هذه المطابقة؟" - NEXT(FIRST(expr [, n]) [, m])
- اخطُ m صفوف إلى الأمام من الصف الذي يقرؤه
FIRST(expr, n). تصل إلى داخل المطابقة دون الاعتماد على الصف الحالي. - PREV(LAST(expr [, n]) [, m])
- اخطُ m صفوف إلى الوراء من الصف الذي يقرؤه
LAST(expr, n). "قارن بصفّ سابق على آخر صفّ مُطابَق بقليل." - NEXT(LAST(expr [, n]) [, m])
- اخطُ m صفوف إلى الأمام من الصف الذي يقرؤه
LAST(expr, n).
تجدر الإشارة إلى نقطتين عمليّتين. أوّلًا، يمكن تركيب الملاحة: PREV(FIRST(price)) يقرأ الصف الذي يسبق بداية المطابقة مباشرةً، والترقيع يدعم ذلك. ثانيًا، للملاحة عواقب على تحسينات المنفّذ. PREV وNEXT المجرّدتان نسبيّتان للصف الحالي وآمنتان دائمًا؛ أمّا FIRST ومتغيّرات LAST ذات الإزاحة، منفردةً أو داخل PREV/NEXT مركّبة، فهي نسبيّة لحدود المطابقة، وهو ما يتفاعل مع امتصاص السياق: إذ يُعطّل المُخطِّط حينها الامتصاص للنمط كلّه. آليّة هذا التفاعل هي موضوع §2.6.
2.3 المثال العملي 1 — حركة NFA
SKIP PAST LAST ROW بمجرّد تسجيل مطابقته.SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (START UP+ DOWN+) DEFINE UP AS price > PREV(price), DOWN AS price < PREV(price) );
يتسطّح النمط إلى أربعة عناصر:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
لسلسلة الأسعار 100, 110, 120, 115, 108, 130:
| الصف | السعر | المتغيّرات الصحيحة | الإجراء |
|---|---|---|---|
| 0 | 100 | START | سياق جديد. تطابق START وتخرج فورًا (max=1)؛ تتقدّم الحالة إلى UP+. |
| 1 | 110 | START, UP | تطابق UP. يتفرّع التقدّم: حالة تدور عند UP، وأخرى تخرج إلى DOWN+. |
| 2 | 120 | START, UP | تطابق UP في الحالة الدائرة وتتفرّع مجدّدًا. تموت حالة DOWN من الصف 1 (120 ≮ 110). |
| 3 | 115 | START, DOWN | تفشل UP على الحالة الدائرة فتموت. تطابق حالة DOWN من الصف 2. يتفرّع التقدّم: دوران عند DOWN، وخروج إلى #FIN — ويُسجَّل مرشّح مطابقة للصفوف 0–3. |
| 4 | 108 | START, DOWN | تطابق DOWN في الحالة الدائرة وتتفرّع مجدّدًا؛ ويحلّ مرشّح FIN الجديد للصفوف 0–4 محلّ المرشّح الأقصر. |
| 5 | 130 | START, UP | تفشل حالة DOWN الدائرة (130 ≮ 108). بانعدام أيّ حالة حيّة متبقّية في هذا السياق، يُحسم المرشّح المُسجَّل (الصفوف 0–4) بوصفه المطابقة. تبدأ المحاولة التالية عند الصف 5؛ تطابق START، لكنّ القسم ينتهي قبل أيّ UP. |
النقطة الجوهرية: عند الصف 3، يُلبّي الصفّ كلًّا من START (الصحيحة دائمًا) وDOWN، لكنّ START لا تهمّ إلا سياقًا يبدأ عند الصف 3؛ ففي هذا السياق تموت حالة UP الدائرة ولا تتقدّم إلا الحالة المنتظرة عند DOWN+. تظهر طبيعة تعدّد الحالات في §2.1 بوصفها تفرّعًا عند كلّ مطابقة لـUP (إذ يمكن للحالة أن تبقى عند UP+ أو أن تتقدّم نحو DOWN+). والتفضيل الجشع هو "كرّر الدوران قبل الخروج"، فبما يكفي من البيانات تمدّ الفروع الدائرة المطابقة أكثر؛ هنا تموت DOWN الدائرة عند الصف 5 (130 ≮ 108)، ويُحسم آخر مرشّح FIN (الصفوف 0–4) — الناتج عند خروج DOWN في الصف 4، والذي حلّ محلّ مرشّح الصف 3 — بوصفه المطابقة.
تنبثق نتيجة الاستعلام مباشرة من هذا الأثر. تحت دلالات RPR، تُقيَّم دالّتا النافذة first_value(price) وlast_value(price) عند الصف الذي بدأت عنده المطابقة فقط — وأيّ صفّ آخر داخل المطابقة يُنتج NULL لهاتين الدالّتين، لأنّ إطاره المُختزل فارغ. ولذلك تبدو مخرجات بياناتنا كالجدول الذي يعرضه الملصق في لوحته العلوية اليمنى:
| الصف | السعر | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
الصف 0 هو بداية المطابقة، فيغطّي إطاره الصفوف 0–4، وتُبلِّغ دوالّ النافذة عن سعر افتتاح الشكل V ($100) وسعر القاع ($108). الصفوف 1–4 داخل المطابقة لكنّها ليست بدايتها، فتأخذ NULL. والصف 5 (السعر $130) خارج أيّ مطابقة، فيأخذ NULL أيضًا.
2.4 المثال العملي 2 — التبديل والترتيب المعجمي
تمنح صيغة (A | B) المُطابق خيارًا: عند أيّ صفّ، يُختبر البديلان مستقلَّين، ويمكن لأيّ عدد منهما أن يطابق. هنا تتجلّى طبيعة تعدّد الحالات في §2.1 داخل سياق واحد — لا عبر السياقات (تلك الامتصاص)، بل على فروع متوازية يستكشفها المنفّذ بترتيب النمط، الفرع الأسبق أوّلًا.
PATTERN ((UP | HIGH) DONE) DEFINE UP AS price > PREV(price), HIGH AS price > 100, DONE AS volume > 1000
تخيّل صفًّا يكون فيه السعر قد ارتفع وتجاوز 100 دولار في آنٍ واحد — كلٌّ من UP وHIGH صحيح. يُولّد كلّ بديل حالته الخاصة: واحدة تسير على فرع UP، وأخرى على فرع HIGH. ثم تتقدّم كلتاهما إلى DONE، حيث تلتقيان.
| الصف | المتغيّرات الصحيحة | الحالات الحيّة |
|---|---|---|
| R | UP, HIGH | تتقدّم الحالة A (فرع UP) والحالة B (فرع HIGH) كلتاهما إلى DONE بالأعداد ذاتها؛ B نسخة مكرّرة من A فتُسقَط |
| R+1 | DONE | تطابق الحالة A DONE وتصل إلى #FIN |
بمصطلحات المعيار، ينتج كلا الفرعين مطابقة بطول متماثل على الصفوف ذاتها، فيعطي مسارَين مرشَّحَين — أحدهما موسوم بـUP, DONE والآخر بـHIGH, DONE. ويحسم المعيار ذلك وفق الترتيب المعجمي: من بين البدائل المكتوبة في (UP | HIGH)، يفوز المكتوب أوّلًا، بصرف النظر عن طول المطابقة. وبما أنّ UP يسبق HIGH، فالمسار الناجي هو UP, DONE. ويفرض المنفّذ ذلك عند الصف R لا عند FIN: إذ يُضيف حالة فرع UP أوّلًا، فتُبقيها nfa_append_state_unique() وتُسقط حالة فرع HIGH المطابقة لها.
الترتيب المعجمي هو ما يجعل CLASSIFIER() ذات تعريف قاطع حين تُنفَّذ لاحقًا — فهو يتيح لوقت التشغيل أن يقول للمستخدم "طُوبق هذا الصفّ بـUP، لا HIGH" حتى عندما يكون كلا المُسندين صحيحين. والترتيب المعجمي هو القاعدة الأساسية للتبديل: يفوز فرع أسبق معجميًا على فرع أحدث حتى لو أنتج الفرع الأحدث مطابقة أطول، ومع ذلك يمكن لفرع أحدث (وربّما أقصر) أن يفوز إذا مات كلّ فرع أسبق قبل أن يصل إلى FIN. أمّا طول الجشع فيُحسم داخل مُكمِّم واحد — فبين إكمالين لذات فرع التبديل، يفضّل المُكمِّم الجشع التكرارات الأكثر.
2.5 المثال العملي 3 — امتصاص السياق (المصير ذاته)
أبسط نمط يُظهر الامتصاص هو PATTERN (A+) مع DEFINE A AS TRUE. كلّ صفّ يطابق A، ويتطلّب المعيار من المُطابق اعتبار كلّ صفّ بداية مطابقة محتملة. ساذجًا، يعني هذا N من السياقات لقسم بحجم N صفًّا. لنأخذ قسمًا من خمسة صفوف (أيّ بيانات — المُسند ثابت الصدق):
| الصف | سياقات ساذجة | مع الامتصاص |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — امتُصّت C2 |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | خمسة سياقات | C1[A:5] |
تنخفض السياقات الحيّة من O(n) إلى O(1)، فينخفض المجموع على امتداد القسم من O(n²) إلى O(n). وقاعدة الامتصاص التي تُسوّغ هذا الإسقاط مباشرة عند مُكمِّم غير محدود:
اللوحة السفلية اليسرى من الملصق ("① Context Absorption") هي بالضبط هذه القاعدة مُمثَّلة بصريًا على خمسة صفوف.
تكمن نقطة دقيقة لكنّها مهمّة في القاعدة: الإسقاط آمن لأنّ المُسند A AS TRUE يُقيَّم بالقيمة ذاتها عند كلّ صفّ بصرف النظر عن السياق السائل. وهذا ينطبق على أيّ مُسند يشير إلى الصف الحالي وحده أو إلى إزاحة ثابتة منه — بما في ذلك PREV. ينتقل المثال التالي إلى أسبوع تداول ملموس باستخدام مُسند مبنيّ على PREV، وستعيد §2.6 استخدام الأسبوع ذاته لتُظهر التماثل بين الامتصاص الآمن وغير الآمن:
PATTERN (RISE+) DEFINE RISE AS price > PREV(price)
لنأخذ أسبوع التداول $100, $108, $112, $116, $110 من الإثنين إلى الجمعة — أربع ارتفاعات يتبعها هبوط مفاجئ. لنفترض أنّ C1 يبدأ يوم الثلاثاء (أوّل يوم تطابق فيه RISE: 108$ > 100$)، وأنّ المنفّذ يتعقّب أيضًا تخمينيًا C2 الذي يبدأ يوم الأربعاء. شرط RISE عند كلّ صفّ يقارن سعر الصفّ بسلفه المباشر — وهو حقيقة على مستوى القسم لا على مستوى السياق — فيُجبَر السياقان على حساب البولياني ذاته عند كلّ صفّ مشترك:
| اليوم | السعر | C1 — بدء الثلاثاء price > PREV(price) | C2 — بدء الأربعاء price > PREV(price) |
|---|---|---|---|
| الإثنين | $100 | — | — |
| الثلاثاء | $108 | $108 > $100 ✓ (بدأت للتو) | — |
| الأربعاء | $112 | $112 > $108 ✓ | $112 > $108 ✓ (بدأت للتو) |
| الخميس | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| الجمعة | $110 | $110 > $116 ✗ — تُحسم | $110 > $116 ✗ — تُحسم |
تنكسر القصّة لحظة يبدأ المُسند بالاعتماد على حدود كلّ سياق — وهذا موضوع §2.6.
2.6 المثال العملي 4 — حين يصبح الامتصاص غير آمن
DEFINE إلى FIRST — تسقط قاعدة الامتصاص، ويُعطّل المُخطِّط الامتصاص للنمط.
لنفترض أنّ محلّلًا يريد إيجاد أيّام تداول متتالية بقي فيها السهم ضمن عشرة دولارات من اليوم الذي بدأت فيه السلسلة — نوع من نافذة التماسك. يبدو النمط وDEFINE هكذا:
PATTERN (STABLE+) DEFINE STABLE AS price < FIRST(price) + 10
يقارن الشرط الآن سعر الصف الحالي بسعر بداية السلسلة الحالية. سلسلتان بدأتا في يومين مختلفين لهما قيمتان مختلفتان لـFIRST(price)، فلم تعد حالتان عند العنصر النمطي ذاته وبالعدد ذاته قابلتين للتبادل: مستقبلهما يعتمد على الحدّ الذي كان الامتصاص على وشك التخلّص منه.
لنأخذ أسبوع التداول ذاته كما في §2.5 — $100, $108, $112, $116, $110 من الإثنين إلى الجمعة. يُبقي وقت التشغيل مرّة أخرى سلسلتين مرشَّحتين حيّتين في آنٍ واحد: C1 بدأت يوم الإثنين، وC2 بدأت يوم الثلاثاء (كلّ صفّ بداية محتملة لسلسلة تحت STABLE+).
| اليوم | السعر | C1 — بدء الإثنين FIRST = $100 price < $100 + 10 | C2 — بدء الثلاثاء FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| الإثنين | $100 | $100 < $110 ✓ | — |
| الثلاثاء | $108 | $108 < $110 ✓ | $108 < $118 ✓ (بدأت للتو) |
| الأربعاء | $112 | $112 < $110 ✗ — تُحسم الإثنين–الثلاثاء | $112 < $118 ✓ |
| الخميس | $116 | — | $116 < $118 ✓ |
| الجمعة | $110 | — | $110 < $118 ✓ (لا تزال جارية) |
تحت الامتصاص، كانت C2 ستُدمج في C1 يوم الثلاثاء — والسياق المُدمَج يحتفظ بسقف C1 وحده ($110)، فلا يغطّي مستقبلُ C1 رؤيةَ C2 المتميّزة (سقف $118، سلسلة من أربعة أيّام حتى الجمعة). في هذا الأسبوع تحديدًا لا تتغيّر المخرجات مصادفةً: تُسجّل C1 الإثنين–الثلاثاء، وC2 بدأت داخل تلك المطابقة فتُسقطها SKIP PAST LAST ROW، وتبدأ المحاولة التالية يوم الأربعاء بسقفها الخاص ($122) وتطابق الأربعاء–الجمعة. لكن عمومًا، لم تعد نتيجة DEFINE لسياق أسبق تشمل نتيجة سياق لاحق، فتبطل مقارنة الأعداد التي يعتمد عليها الامتصاص. ولذا، كلّما حمل مُسند DEFINE اعتماديّة على بداية المطابقة، يُعطّل المُخطِّط الامتصاص استباقيًا.
(حين تنجح مطابقة السياق الرائد، فإنّ السياقات التي بدأت داخل مدى قبوله — في ظلّ AFTER MATCH SKIP PAST LAST ROW الافتراضي — تُسقَط ببساطة؛ وقد بقيت حيّة فقط لتوفير ملاذ لوقت التشغيل في حال فشل المطابقة الرائدة.)
يوسّع الجدول أدناه اللوحة السفلية اليمنى من الملصق ("② Navigation") بالصيغ المركّبة، ويلخّص صيغ الملاحة التي تُنشئ اعتماديّة على بداية المطابقة:
| الملاحة | اعتماديّة على بداية المطابقة | قابلة للامتصاص؟ |
|---|---|---|
| PREV, NEXT | لا شيء | نعم |
| LAST (بلا إزاحة) | لا شيء | نعم |
| LAST بإزاحة | فحص حدود | لا |
| FIRST (أيّ صيغة) | مباشرة | لا |
| مركّبة (FIRST داخلية) | مباشرة | لا |
| مركّبة (LAST داخلية، بلا إزاحة) | لا شيء | نعم |
| مركّبة (LAST داخلية بإزاحة) | فحص حدود | لا |
يُختزل المثالان في §2.5 و§2.6 إلى قاعدة واحدة. المصير ذاته هو ما يجعل الامتصاص آمنًا: إذا كانت كلّ السياقات عند العنصر النمطي ذاته ستحسب الإجابة ذاتها على كلّ مُسند مستقبلي، فلا حاجة سوى للأقدم. المصائر المختلفة تجعل الامتصاص غير آمن: فبمجرّد أن تتفرّع المُسندات على حالة خاصّة بالسياق — وهو بالضبط ما تفعله FIRST وLAST ذات الإزاحة — فإنّ كلّ سياق حيّ يمثّل مستقبلًا لا يُضمَن أن يغطّيه أيّ سياق آخر، فلا يعود بالإمكان إثبات أنّ إسقاط أحدها آمن.
يكتشف المُخطِّط هذا التمييز عند الترجمة ويُشغّل الامتصاص أو يُعطّله للنمط كلّه؛ وحين يكون مُعطَّلًا يدفع وقت التشغيل كلفة تعدّد السياقات. لا يستخدم قياس الأداء في اللوحة ③ من الملصق FIRST، فيبقى الامتصاص مُفعَّلًا، ولهذا تبقى PostgreSQL خطّية في حالتي النجاح والفشل.
أرقام قياس الأداء على الملصق هي الخوارزمية ذاتها وهي تتجلّى على نطاق واسع. على نمط النجاح (A+ B+ C+ D)، تتدرّج كلٌّ من PostgreSQL وTrino بمعدّل O(n) تقريبًا بمجرّد تأكيد المطابقة، وتتفوّق PostgreSQL بنحو 16× إلى 33× (وأرقام Trino تستثني أصلًا زمن إقلاع JVM).
على نمط الفشل (A+ B+ C+ E)، يلاحق Trino، الذي يبدو أنّه يفتقر إلى الامتصاص، كلّ بداية مطابقة محتملة فينحدر أسرع حتى من O(n²) (نحو 56× من الزمن مقابل 5× من الصفوف)؛ عند 100,000 صفّ يستغرق أكثر من خمس ساعات، بينما تنتهي PostgreSQL في 92 مل ث، أي تسريع نحو 217,000×.
تلك الفجوة ليست تحسينًا هندسيًا — بل هي بالضبط تمييز المصير ذاته/المختلف من §2.5 و§2.6، مُطبَّقًا على كلّ صفّ من كلّ بداية مطابقة محتملة في القسم.
2.7 المثال العملي 5 — حين تُعطّل SKIP الامتصاص
كسر المثال السابق الامتصاص من جانب البيانات: FIRST في DEFINE جعل كلّ سياق يقيّم المُسندات بطريقة مختلفة. ويمكن للامتصاص أن ينكسر أيضًا من جانب المخرجات، وجملة AFTER MATCH SKIP هي ما يتحكّم في ذلك.
لنتأمّل النمط PATTERN (A+) مع DEFINE A AS TRUE فوق خمسة صفوف تطابق كلّها A. تحت AFTER MATCH SKIP PAST LAST ROW الافتراضي، يجد المُطابق أطول مطابقة تبدأ من أبكر صفّ ثم يقفز خلفها؛ وأيّ سياق بدأ داخل تلك المطابقة يُسقَط ضمنيًا بوصفه زائدًا — وهو بالضبط الموقف الذي صُمّم الامتصاص للتعامل معه. المخرجات مطابقة واحدة، الصفوف 0–4، ولا يحتاج وقت التشغيل إلا إلى سياق حيّ واحد.
بدّل وضع التخطّي إلى AFTER MATCH SKIP TO NEXT ROW ويتغيّر العقد:
PATTERN (A+) DEFINE A AS TRUE AFTER MATCH SKIP TO NEXT ROW
الآن يجب تقرير كلّ موضع بداية محتمل منفصلًا، حتى عند تداخل المطابقات. للصفوف الخمسة ذاتها، مطلوب من وقت التشغيل أن يُصدر خمس مطابقات: الصفوف 0–4، و1–4، و2–4، و3–4، و4–4. لا يمكن استبدال أيّ منها بـ"أطول واحدة بدأت أبكر"، لأنّ المعيار يقول إنّ المستخدم يريدها كلّها.
| الصف | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | تبدأ المطابقة؛ الصفوف 0–4 ستكون المطابقة الوحيدة | تبدأ المطابقة عند الصف 0 |
| 1 | (داخل المطابقة 0) | تبدأ المطابقة عند الصف 1 — يجب إبقاؤها حيّة |
| 2 | (داخل المطابقة 0) | تبدأ المطابقة عند الصف 2 — يجب إبقاؤها حيّة |
| 3 | (داخل المطابقة 0) | تبدأ المطابقة عند الصف 3 — يجب إبقاؤها حيّة |
| 4 | تُحسم المطابقة 0 (الصفوف 0–4) | تُحسم خمس مطابقات: 0–4، 1–4، 2–4، 3–4، 4–4 |
AFTER MATCH SKIP TO NEXT ROW، كلّ سياق يبدأ متأخّرًا هو صفّ مخرجات بحدّ ذاته. لم يعد سياقان عند العنصر النمطي ذاته زائدين — بل كلاهما مخرجان مطلوبان، وإسقاط أحدهما سيُسقط بصمت مطابقة طلبها المستخدم.
لاحظ أنّ المُسند لم يتغيّر. A AS TRUE يُقيَّم بالطريقة ذاتها عند كلّ صفّ بصرف النظر عن السياق السائل، فلا يزال شرط "المصير ذاته" في §2.5 محقّقًا. ما يتغيّر هو متطلّب المخرجات: حتى السياقات ذات المستقبل المتطابق يجب أن تتعايش لأنّها تقابل صفوفًا متمايزة من النتيجة. ولذلك يُعطّل المُخطِّط امتصاص السياق كلّما كانت AFTER MATCH SKIP TO NEXT ROW سارية، بصرف النظر عن جملة DEFINE.
وضع §2.6 و§2.7 جنبًا إلى جنب يُعطي الطريقتين اللتين تستبعد بهما دلالات الاستعلام الامتصاص:
FIRST أو LAST ذات الإزاحة في DEFINE.AFTER MATCH SKIP TO NEXT ROW.
أيٌّ من الشرطين كافٍ لتعطيل الامتصاص للنمط كلّه، وكذلك إطار لا ينتهي عند UNBOUNDED FOLLOWING. حين لا يكون أيٌّ منها ساريًا — أي AFTER MATCH SKIP PAST LAST ROW الافتراضي، ونهاية إطار غير محدودة، وشروط DEFINE التي تستخدم فقط PREV أو NEXT أو LAST المجرّدة — يُفعَّل الامتصاص، لكن فقط للحالات الواقعة في المنطقة القابلة للامتصاص من النمط: متغيّر جشع غير محدود في البداية مثل A+ أو A*، أو مجموعة ثابتة الطول بمُكمِّم جشع غير محدود مثل (A B)+، أو مجموعة جشعة يبدأ جسمها بأحد هذين مثل (A+ B)+ أو (A+ B){2}، أو فروع تبديل مبنيّة منها؛ والمجموعة المتمنّعة تُقصي شجرتها الفرعية كاملة. وحيث يتحقّق ذلك، كما في A+ في §2.5، ينهار وقت التشغيل إلى سياق واحد ويبقى خطّيًا؛ أمّا START UP+ DOWN+ من §2.3 فلا يحصل على أيّ منطقة قابلة للامتصاص.
§3. التصميم — من المحلّل النحوي إلى المنفّذ
يُنفَّذ التعرّف على أنماط الصفوف بثلاث مراحل تُسلِّم العمل عبر صيغ وسيطة محدّدة. يحوّل المحلّل النحوي نصّ 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، ويجب أن تكون حدود النهاية UNBOUNDED FOLLOWING أو إزاحة موجبة FOLLOWING (فيُرفض الإطار الافتراضي أيضًا)، وخيارات EXCLUDE غير EXCLUDE NO OTHERS ممنوعة. هذه فحوص مطابقة لا تحسينات — فمفهوم الإطار في RPR هو مدى المطابقة، ولا يتصوّر المعيار ملأه بشيء غير الصفوف المطابِقة.
بمجرّد اجتياز الإطار التحقّق، يحوّل المحلّل جملة PATTERN إلى شجرة مبنيّة من أربعة أنواع من العقد — مرجع متغيّر، وتسلسل (وصل)، وتبديل، ومجموعة (نمط فرعي بين قوسين). تحمل كلّ عقدة المُكمِّم بثلاثة أرقام — حدّ أدنى، وحدّ أعلى (قد يكون لانهائيًا)، وعَلَمًا للمطابقة المتمنّعة:
| المصدر | ترميز الشجرة |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
يُفحَص بعدها كلّ مُسند DEFINE من حيث النوع تجاه أعمدة القسم ويُحوَّل إلى تعبير بولياني. ويترتّب على ذلك أمران عمليّان. أوّلًا، لا يضيف التحليل الدلالي (parse analysis) شيئًا إلى قائمة أهداف الاستعلام من أجل DEFINE؛ بل يُعلِّم المُخطِّط كلّ عمود يشير إليه مُسند DEFINE بأنّه مطلوب، كما يفعل مع HAVING، ويُمرّر تلك الأعمدة إلى مرحلة المنفّذ حتى لو لم يُحدّدها الاستعلام المحيط — وإلا فلن يكون لدى وقت التشغيل ما يقيّمه. ثانيًا، المتغيّرات التي تظهر في 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
يثمر التحسين مرّتين: مرّة في العدد الساكن لعناصر المصفوفة المسطّحة، ومرّة في كلّ صفّ يُعالَج عند التشغيل. كلّ تحويل يقلّل فضاء الحالة الذي على وقت التشغيل تعداده. يطبّق المُحسِّن تسع قواعد إعادة كتابة في تمريرة واحدة من الأسفل إلى الأعلى (وداخل التسلسل يُعاد دمج المجموعات مرّة أخرى، لأنّ عمليات الدمج السابقة قد تجمع مجموعتين متطابقتين متجاورتين):
- تسطيح SEQ
SEQ(A, SEQ(B, C))→SEQ(A, B, C)- دمج متغيّرات متتالية
-
A A→A{2}
A{2,3} A{1,2}→A{3,5} - دمج مجموعات متتالية
(A B)+ (A B)+→(A B){2,∞}- دمج ALT متتالية
(A | B) (A | B) (A | B)→(A | B){3}- دمج بادئة/لاحقة
A B (A B)+→(A B){2,∞}- تسطيح ALT وإزالة التكرار
-
(A | (B | C))→(A | B | C)
(A | B | A)→(A | B) - ضرب المُكمِّمات
-
(A+)+→A+
(A{2,3}){5}→A{10,15} - إزالة غلاف الطفل المنفرد
-
SEQ(A)→A
(A){1,1}→A - تسوية التمنّع
A{2}?→A{2}(يُزال التمنّع حيثما min = max)
لا يطوي ضرب المُكمِّمات إلا حين تُشكّل الأعداد الممكنة فترة متّصلة واحدة ولا تتحرّك المطابقة المفضّلة: خارجي بالضبط ((A{2,3}){5} → A{10,15})، أو طفل حدّه الأدنى 0، أو فترات طفل متلامسة مع حدّ أدنى للطفل لا يتجاوز 1 أو حدّ أعلى للطفل غير محدود ((A+)+ → A+، (A{1,3}){2,4} → A{2,12})، على أنّ الخارجي ذا الحدّ الأدنى 0 يحتاج أيضًا إلى حدّ أدنى للطفل لا يتجاوز 1 ((A{2,})* يبقى، لأنّ A* سيقبل صفًّا واحدًا). والطفل الذي هو مجموعة لا يكون مُكمِّمها بالضبط يجب أوّلًا أن يكون جسمها ثابت الطول، لذا يبقى ((A | B B){1,2}){2} سليمًا حتى تحت خارجي بالضبط. تركيبات أخرى قد تُدخل ثغرات يفوّتها الشكل المسطّح — مثلًا، (A{2}){2,3} يقبل فقط {4, 6}، لكنّ A{4,6} الساذج سيقبل أيضًا 5 — أو تُزيح المطابقة المفضّلة ((A{2,3}){1,2} يفضّل ثلاثة صفوف حيث يأخذ A{2,6} أربعة)، فيتركها المُحسِّن سليمة. وليس هذا التحويل الوحيد المشروط: فدمج المجموعات ودمج اللاحقة يستلزمان جسمًا يستهلك عددًا ثابتًا من الصفوف، ودمج البادئة يرفض مجموعة حدّها الأدنى 0 وحدّها الأعلى منتهٍ ومحتواها قابل للنفي، والعقد المتمنّعة لا تُدمج ولا تُضرب ((A+?)+ يبقى)، وتُرفض إعادة الكتابة التي يفيض حدّها الجديد.
شكل العنصر
يمثّل كلّ عنصر من المصفوفة المسطّحة موضعًا واحدًا في النمط. ثمّة ستّة أنواع منطقية: مرجع متغيّر (النوع الوحيد الذي يستهلك صفًّا)؛ ومُعلِّمَا بداية المجموعة ونهاية المجموعة، اللذان يفتحان نمطًا فرعيًا بين قوسين ويغلقانه؛ ومُعلِّم تبديل يتصدّر قائمة فروع؛ وفاصل فروع يُنهي كلّ فرع؛ ومُعلِّم انتهاء في نهاية النمط.
يحمل كلّ عنصر أيضًا عمقًا (مستوى تعشيش مجموعته)، والمُكمِّم (عدد تكرار أدنى وأعلى، قد يكون لانهائيًا)، ومؤشّرَيْ انتقال — next، "إلى أين أذهب بعد استهلاك هذا العنصر"، وjump، "إلى أين أتخطّى" (يستخدمه مُعلِّم التبديل وفواصل الفروع لتسلسل الفروع، وبداية المجموعة لتسمية نهاية مجموعتها — والمجموعة التي يسمح مُكمِّمها بالصفر تُتخطّى عبر next لتلك النهاية — ونهاية المجموعة للعودة إلى الجسم).
لـPATTERN ((A B)+) تبدو المصفوفة المُترجَمة هكذا:
PATTERN ((A B)+) compiles to:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(يفتح المجموعة؛ jump يسمّي
الـ END الخاص بها)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(يغلق المجموعة؛ jump يعود في حلقة)
[4] FIN اكتمال النمط
يُقرأ النمط من اليسار إلى اليمين عبر next، بينما يتولّى jump الحواف غير الخطّية. عند idx 3 يشير jump الخاص بـEND إلى idx 1، وبهذا يدور المُكمِّم الخارجي غير المحدود؛ وعند idx 0 يسمّي jump الخاص بـBEGIN نهايته END عند idx 3، ولو كانت المجموعة اختيارية لخرج التخطّي عبر next الخاص بتلك النهاية إلى idx 4 دون الوصول إلى END. لا يحتاج وقت التشغيل أبدًا إلى بناء رسم بياني عند التشغيل — بل يتبع هذين المؤشّرين فحسب وهو يتجوّل في المصفوفة.
سمات لكلّ عنصر
إلى جانب الشكل، يحمل كلّ عنصر خمس سمات منطقية توجّه سلوك وقت التشغيل عند ذلك الموضع:
- متمنّع
- يعكس ترتيب توسعة المُكمِّم. المُكمِّمات الجشعة تحاول "الدوران مجدّدًا" قبل "الخروج"؛ والمتمنّعة تحاول "الخروج" أوّلًا. يحمله المتغيّر لـ
A+?؛ ويحمله BEGIN وEND للمجموعة لـ((…)+?). - قابل للدوران الفارغ
- يُضبط على نهايات المجموعات التي يكون جسمها قابلًا للنفي (
(A? B?)+،(A | B*)+؛ أمّا(A?)*فيُضرب أوّلًا إلىA*ولا يترك نهاية مجموعة). يُخبر وقت التشغيل بإضافة خروج سريع إلى جانب الالتفاف العادي دون الحدّ الأدنى، حتى لا يقتل حارس الدورة المطابقات المشروعة في المجموعات القادرة على إنتاج تكرارات فارغة. - مُفضِّل للفراغ
- يُضبط على نهايات المجموعات التي يفضّل جسمها المطابقة الفارغة، كما في
(A?? B??){2}. يُقدِّم الخروج السريع على الالتفاف دون الحدّ الأدنى، حيث لا يقول جشع المجموعة ذاتها شيئًا. - داخل منطقة قابلة للامتصاص
- يُعلّم كلّ عنصر يقع ضمن منطقة مؤهَّلة للامتصاص — يستخدمه وقت التشغيل لتعقّب ما إذا كانت الحالة الحالية لا تزال في منطقة آمنة.
- نقطة مقارنة الامتصاص
- يُعلّم العنصر المحدّد الذي يجب إجراء مقارنات الامتصاص عنده. لـ
A+البسيطة يقع على المتغيّر؛ ولمجموعة غير محدودة كـ(A B)+يقع على نهاية المجموعة وحدها.
التمييز بين "داخل المنطقة" و"نقطة المقارنة" مهمّ، لأنّ الامتصاص لا يكون له معنى إلا عند النقاط التي تُغلَق فيها التكرارات. داخل جسم (A B)+، يكون وقت التشغيل في منتصف تكرار ولم يصل العدّ بعد إلى قيمته النهائية لتلك الجولة؛ والمقارنة هنا تعني مقارنة قيم غير قابلة للمقارنة. يجب أن تصل الحالة إلى نهاية المجموعة قبل أن يقرّر وقت التشغيل. لذا تقول السمة الأولى "أنت لا تزال في منطقة قابلة للامتصاص"؛ بينما تقول الثانية "وصلت إلى نقطة المقارنة — افحص الآن".
تحليل قابليّة الامتصاص
الخطوة 6 من الترجمة هي التي تمنح قاعدة "المصير ذاته" في §2.5 شاهدها في وقت الترجمة. القرار متعدّد الطبقات:
isAbsorbable(query):
إذا وضع SKIP != SKIP PAST LAST ROW
→ return false
إذا نهاية frame != UNBOUNDED FOLLOWING
→ return false
إذا أيّ DEFINE يعتمد على match_start
→ return false
مرّ على المصفوفة المسطّحة من
العنصر 0 وحدّد العناصر
التي تستوفي حالة بنيوية
الفحوص الثلاثة الأولى على مستوى الاستعلام: تطابق تمامًا شروط §2.7 (جانب المخرجات: وضع SKIP)، والإطار المقيّد (الحدود تكسر الرتابة)، و§2.6 (جانب البيانات: FIRST أو LAST ذات الإزاحة في DEFINE). حين يفشل أيٌّ منها، لا يضع التحليل أيّ أعلام ويُعطَّل الامتصاص على مستوى الاستعلام. حين تنجح جميعها، يقبل التجوّل أربعة أشكال بنيوية:
- الحالة 1 — متغيّر بسيط غير محدود
-
كلّ تكرار يساوي صفًّا واحدًا تمامًا. عدّ السياق الأقدم دائمًا ≥ عدّ الأحدث عند كلّ موضع مشترك.
A+،A*،A{2,∞} - الحالة 2 — مجموعة بطول ثابت، خارجي غير محدود
-
كلّ طفل له
(A B)+،(A B{2})+،((A (B C){2}){2})+min == max، فالجسم مكافئ دلاليًا لصيغته المُفكَّكة{1,1}—(A B{2})+يتصرّف كـ(A B B)+. كلّ تكرار يستهلك عددًا ثابتًا من الصفوف؛ وتظلّ هيمنة العدّ سارية. - الحالة 3 — مجموعة يبدأ جسمها بمتغيّر غير محدود
-
المتغيّر غير المحدود في المقدّمة قابل للامتصاص بحدّ ذاته (الحالة 1) ويحمي السياقات الأقدم. يتوقّف الامتصاص بمجرّد تجاوز الحالة لـA — فبقيّة الجسم بلا ضمان رتابة، فيحصل A على العَلَمين، ويحصل BEGIN المحيط على عَلَم داخل المنطقة، ولا يحصل B وEND على شيء.
(A+ B)+،(A+ B){2} - الحالة 4 — التبديل
-
كلّ فرع، يُوصَل إليه عبر سلسلة الفواصل، يُحكم عليه منفردًا وفق الحالات أعلاه؛ ويحصل مُعلِّم التبديل على عَلَم داخل المنطقة حين يتأهّل أيّ فرع.
A+ | B+،A+ | C D
الحالات البنيوية غير المغطّاة بهذه الأشكال الأربعة مفيدة بالقدر ذاته. A B+ لا يمكن امتصاصه بالقاعدة الحالية لأنّ A في المقدّمة يستهلك صفًّا قبل بدء الجزء غير المحدود، فالسياقات التي تبدأ بفارق صفّ واحد تكون في مواضع مختلفة داخل الجسم غير المحدود. المُكمِّمات المتمنّعة كـA+? مستثناة بالبناء: قاعدة الامتصاص تفترض دلالات جشعة، حيث تستوعب المطابقات الأطول الأقصرَ، والمطابقة المتمنّعة تعكس ذلك الاتّجاه.
والنتيجة قرار لكلّ عنصر بدلًا من قرار لكلّ نمط. يمكن لخطّة استعلام واحدة أن يكون لديها امتصاص مُفعَّل لـA+ الرائد في أنماط مثل (A+ B+ C) أو (A+ B+)+ — وهذه الأخيرة هي الحالة 3 مطبَّقة على عنصرها الرائد — وأن يكون مُعطَّلًا لكلّ ما يأتي بعده؛ ويستشير وقت التشغيل ببساطة سمة نقطة المقارنة على عنصر الحالة الراهنة كلّما فكّر في تمريرة امتصاص. وبمجرّد أن تنتقل الحالة إلى منطقة غير قابلة للامتصاص، يُعطَّل الامتصاص لتلك الحالة بشكل دائم — وهذا بالضبط ما تحتاجه §2.5 و§2.6 لتصحّ على المستوى الخوارزمي.
3.3 الملاحة — مبادلة المُتعلِّق ذات المقعد الواحد
تعابير 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 != currentPos:
اجلب الصف عند targetPos
إلى nav_slot
وجّه المقعد الخارجي إلى nav_slot
result = eval_inner_expression()
استعد current_row_slot
انسخ النتيجة by-ref خارج nav_slot
return result
الخدعة أنّ ثمّة مقعدًا واحدًا فقط يُحفظ ويُستعاد. التعبير الداخلي — أيًّا كان، بما في ذلك الحساب أو استدعاءات الدوال أو إشارات الأعمدة الأخرى — يجري تجاه المقعد المُبدَّل عبر مسار التقييم ذاته الذي سيستخدمه للصف الحالي. لا مُقيِّم بديل ولا مقعد لكلّ إشارة؛ وحين يكون الهدف هو الصف الحالي، يُتخطّى الجلب والمبادلة كلّيًا. ينسخ الجلب الصف الهدف إلى مقعد الملاحة (ما لم يكن المقعد يحمله أصلًا)، وتنسخ خطوة الاستعادة النتيجة الممرَّرة بالمرجع (pass-by-reference) إلى ذاكرة per-tuple حتى لا يُحرّرها الجلب التالي.
تُسطَّح الملاحة المركّبة عند التحليل النحوي حتى تبقى المبادلة مرّة واحدة. يُتعرَّف على PREV(FIRST(price)) بوصفه ملاحة من خطوتين — "اذهب إلى أوّل صفّ مطابِق، ثم اخطُ صفًّا للوراء" — ويُخزَّن استدعاء ملاحة واحدًا من نوع مركّب. يحسب وقت التشغيل الموضع الهدف على مرحلتين، لكنّه ينفّذ مبادلة مقعد واحدة فقط لجلب الصف النهائي:
compute_target_position(call):
# نسبة إلى الصف الحالي
PREV(n):
return currentPos − n
NEXT(n):
return currentPos + n
# نسبة إلى المطابقة
FIRST(n):
return matchStart + n
LAST(n):
return currentPos − n
# مركّب: نسبة إلى match ثم خطوة
PREV(FIRST(n), m):
return (matchStart + n) − m
NEXT(FIRST(n), m):
return (matchStart + n) + m
PREV(LAST(n), m):
return (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − n) + m
تَحقَّق وفق النطاق المناسب
(نطاق المطابقة للداخلية FIRST/LAST،
نطاق التجزئة للخطوة الخارجية)
تُختصر مخبّأة المواضع جلب tuplestore حين تستهدف عدّة استدعاءات ملاحة في DEFINE ذاته الصف نفسه — وهو شائع في تعابير مثل price > PREV(price) AND volume > PREV(volume) حيث يحلّ كلا الاستدعاءين إلى الصف السابق. تخزّن المخبّأة فقط "آخر موضع مجلوب"، وتبقى المبادلة ذاتها عملية واحدة.
تصنيف استدعاءات الملاحة هو إسهام المُخطِّط في قرار الامتصاص. يتجوّل المُخطِّط في كلّ تعبير DEFINE ويفرز كلّ متغيّر إلى أحد دلوَين، بناءً على ما إذا كانت جميع السياقات ستحسب البولياني ذاته عند الصف ذاته، أم سيحسب كلّ سياق بوليانه الخاص. يحدّد الدلو شيئين عند التشغيل: عدد مرّات تقييم المتغيّر (مرّة مشتركة، أو مرّة لكلّ سياق متأثّر — §3.5 المرحلة 1)، وما إذا كان امتصاص السياق ممكنًا أصلًا (§2.5 مقابل §2.6): فمتغيّر واحد معتمد على بداية المطابقة يُعطّله للنمط كلّه.
- لا ملاحة
PREV/NEXTفقطLASTدون إزاحة- مركّب بـ
LASTداخلية (دون إزاحة)
LASTبإزاحةFIRST(بأيّ صيغة)- مركّب بـ
FIRSTداخلية - مركّب بـ
LASTداخلية (بإزاحة)
يُجرى التصنيف في وقت التخطيط ويُخزَّن إلى جانب كلّ متغيّر DEFINE، فلا يقضي وقت التشغيل وقتًا في القرار — بل يقرأ ببساطة الدلو لكلّ متغيّر أثناء معالجته صفًّا.
ميزانية الاحتفاظ
تصل الملاحة إلى صفوف كانت آلية دوال النوافذ ستكون قد تجاوزتها. ولإبقاء تلك الصفوف متاحة، يُبنى المنفّذ فوق tuplestore يحتفظ بنافذة منزلقة من الصفوف الحديثة؛ والسؤال هو ما عرض تلك النافذة المطلوب. يحسب المنفّذ ذلك انطلاقًا من إزاحتين متكاملتين، محلًّا كلّ إزاحة مرّة واحدة لكلّ مسح (والإزاحات الثابتة أيضًا عند تهيئة المنفّذ، كي يستطيع EXPLAIN العادي عرضها):
- ميزانية الاسترجاع
- كم تستطيع أيّ استدعاء DEFINE الوصول إلى الوراء من الصف الحالي.
- ميزانية الاستشراف من البداية
- أدنى وصول إلى الأمام (إلى الوراء، حين يكون سالبًا) من بداية مطابقة أقدم سياق حيّ — أي أبكر صفّ قد يحتاجه أيّ استدعاء DEFINE.
عند التشغيل، تُضبط علامة تشذيب tuplestore على الأبكر بين موضعين — الصف الحالي ناقص ميزانية الاسترجاع، وبداية مطابقة أقدم سياق حيّ زائد ميزانية الاستشراف. أيّ شيء قبل تلك العلامة لا يمكن لأيّ استدعاء ملاحة في أيّ سياق حيّ الوصول إليه، ويستطيع tuplestore إسقاطه. سطرا Nav Mark اللذان يُبلِّغ عنهما EXPLAIN (§3.7) — Lookback وLookahead — هما هاتان الميزانيتان، لا ذروتان مقاستان. يُطبع كلّ منهما فقط حين تغذّيه ملاحةٌ ما، ويظهر حتى دون ANALYZE؛ والإزاحة التي لا تُعرف قيمتها إلا عند التشغيل (معامل خطّة عامّة، مثلًا) تُطبع runtime تحت EXPLAIN العادي وقيمتها المحلولة تحت EXPLAIN ANALYZE، وتُعلِّم retain all (Lookback) أو infinite (Lookahead) الإزاحةَ التي تفيض.
3.4 حدود المطابقة — SKIP، وINITIAL، والإطار المقيّد
تُسجَّل نتيجة المطابقة بقيمتين: الصف الذي تبدأ عنده المطابقة، وطولها. البداية السالبة تعني أنّ الموضع لم يُقيَّم بعد؛ وبمجرّد ضبط البداية، يمكن للاستعلامات اللاحقة على المنفّذ — "هل هذا الصف داخل مطابقة؟" — الإجابة بـO(1) عبر فحص الزوج. ويُرمّز الطول النتيجة: -1 لصفّ غير مُطابَق، و0 لمطابقة فارغة، وعدد الصفوف لمطابقة حقيقية. والطول الصفر نتيجة حقيقية لا خطأ: يمثّل نمطًا طوبق دون استهلاك أيّ صفّ، ويجب على المنفّذ تمييزه من الصف غير المُطابَق ومن "لم تُحاوَل أيّ مطابقة عند هذا الموضع بعد" كليهما.
تقرّر جملة 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 محرّك الصف الواحد ذو المراحل الثلاث
يستدعي مُحرّك الصف الواحد للمنفّذ آليّة دوال النوافذ المحيطة كلّما احتاجت معرفة ما إذا كان صفّ ما ينتمي إلى إطار مُطابَق. يجد المحرّك أو يُنشئ السياق لموضع البداية الحالي، ثم يدفع NFA إلى الأمام صفًّا صفًّا — مُعيدًا لكلّ صفّ ضبط مصفوفة مطابقة لكلّ متغيّر إلى "غير مُقيَّم" — حتى لا تبقى لذلك السياق حالات حيّة أو ينتهي القسم. تُقيَّم مُسندات DEFINE كسولًا: يُقيَّم المتغيّر أوّل مرّة تستهلكه فيها حالة ما، فالمتغيّر الذي لا تختبره أيّ حالة حيّة في هذا الصف لا يُقيَّم أبدًا. خطوة التقدّم نفسها ثلاث مراحل بترتيب ثابت — 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)
إذا سجّل مطابقة وكان
SKIP PAST LAST ROW:
قلّم contexts اللاحقة
التي تبدأ داخل المطابقة
الترتيب ليس خيارًا أسلوبيًا. يجب أن يعمل 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]
assert أنّ elem متغيّر
# advance لا يُوقف إلا المتغيّرات
إذا كان varMatched[elem.varId]
غير مُقيَّم:
قيّم DEFINE الخاص به الآن
إذا ليس 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 حين تُزال حالة غير قابلة للامتصاص) إلى أن يُسجّل السياق مطابقة، فيُثبَّت على false — إذ إنّ الامتصاص سيُحرّر مطابقة لا يستطيع أيّ سياق ماتصّ إعادة إنتاجها. يُفحَص العَلَمان في زمن ثابت قبل بدء مسح التغطية، فلا يدفع الامتصاص كلفته الكاملة إلا على السياقات التي لديها فرصة فعلية لتُمتصّ.
المرحلة 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 (بالترتيب، متوقّفًا
حالما يُسجَّل FIN)،
BEGIN (دخول المجموعة؛ ومسار تخطٍّ
اختياري إذا min = 0),
END (loop back / exit / fast-forward —
انظر أدناه),
FIN (سجّل matchEndRow،
واحفظ matchedState، وعلِّم
context كي تُقلَّم contexts
اللاحقة داخل مدى هذا
المرشح — انظر أدناه),
مع التوقّف عند كلّ متغيّر يُصادَف:
أضف state إلى ctx.states
(مع إزالة التكرار بـ elemIdx + counts)
تسجيل حالة وصلت إلى FIN يفعل أكثر من مجرّد وضع علامة على المطابقة المرشّحة. تحت AFTER MATCH SKIP PAST LAST ROW، يجب أن تبدأ المطابقة القابلة للتقرير التالية تمامًا بعد الحالية — فبمجرّد أن ينتهي Advance من السياق الذي سجّل المرشّحة، يُشذَّب في الصف ذاته كلّ سياق لاحق يقع صف بدايته داخل مدى المرشّحة، رغم أنّ السياق الذي أصاب FIN قد يستمرّ في البحث عن مطابقة أطول عبر تراجع جشع.
التشذيب آمن لأنّه مهما انتهى ذلك البحث (مطابقة أطول تستبدل المرشّحة، أو تثبت المرشّحة)، فإنّ كلّ السياقات المشذّبة بدأت داخل مدى يجب أن تتخطّاه المطابقة التالية القابلة للتقرير، فلن تنتج مخرجاتها أبدًا.
هذه خطوة تشذيب وقت FIN العابرة للسياقات. وداخل السياق، يقطع FIN أيضًا العمل الأدنى معجميًا: يُسقط Advance الحالات المتبقّية في الطابور (الموصوف سابقًا في هذا القسم)، وداخل DFS واحد يتوقّف كلّ مسار أقلّ تفضيلًا — فروع ALT اللاحقة، والآخر من مسارَي التخطّي والدخول لـBEGIN، ومسار الدخول لمتغيّر متمنّع، والآخر من مسارَي الدوران والخروج لـEND — حالما تُسجَّل مطابقة، فلا يُسجّل تقدّم واحد أكثر من مطابقة واحدة.
أكثر منطق لكلّ عنصر دقّة يعيش في معالج END. حين يكون عدّ تكرار المجموعة أقلّ من الحدّ الأدنى، يجب على وقت التشغيل العودة إلى الالتفاف؛ وحين يكون عند الحدّ الأعلى أو فوقه، يجب أن يخرج؛ وبين ذلك يكون الخياران صحيحين، ويقرّر جشع المُكمِّم أيّهما يحاول أوّلًا:
advance_end(state, elem):
count = state.counts[elem.depth]
إذا count < elem.min:
عُد بالتكرار إلى الجسم
إذا elem كان empty-loopable:
# جسم nullable، انظر §3.2
استنسخ أيضًا حالة fast-forward
تخرج من المجموعة مع
إيفاء count
(fast-forward أولًا إذا كان
الجسم يفضّل الفراغ؛ ويُسقَط
المسار الثاني إذا بلغ
الأوّل FIN)
وإلا إذا count >= elem.max:
صفِّر counts عند هذا العمق
اخرج عبر next
(END→END: زِد count
الـ END الخارجي)
وإلا:
# min <= count < max: تفرّع
ابنِ حالة خروج
(counts عند هذا العمق مُصفَّرة)
إذا greedy:
loop أولًا
إذا loop بلغ FIN:
أسقط الـ exit
# تفضيل الأطول
وإلا exit ثانيًا
وإلا (reluctant):
exit أولًا
إذا exit بلغ FIN:
أسقط الـ loop
# تفضيل الأقصر
وإلا loop ثانيًا
كلّ حالة تُضاف إلى سياق تمرّ بفحص إزالة تكرار يقارن موضعها وأعدادها بقائمة الحالات الموجودة. ولأنّ Advance يعالج الفروع بترتيب DFS، فإنّ الحالة من الفرع الأوّل لأيّ تبديل تستقرّ أوّلًا — وأيّ فرع لاحق يُنتج الموضع والأعداد ذاتها يُرفض عند الإدراج. وهذا بالضبط ما تطلبه قاعدة الترتيب المعجمي في §2.4، مُنفَّذةً في قاع وقت التشغيل دون تمريرة منفصلة.
المجموعات القابلة للدوران الفارغ
حالة دقيقة على وقت التشغيل تفكيكها هي المجموعة القابلة للنفي — مجموعة يستطيع جسمها مطابقة صفر صفًّا لأنّ كلّ طفل من الجسم اختياري بحدّ ذاته. أنماط مثل (A? B?)+ و(A | B*)+ لها هذه الخاصّية: بحسب البيانات، يستطيع الجسم إكمال تكرار دون استهلاك أيّ صفّ على الإطلاق. (الطفل الاختياري المنفرد مثل (A?)* يُعاد كتابته إلى A* وقت الترجمة ولا يُخلّف مجموعة.) ذلك حسن من حيث المبدأ، لكنّه يُنشئ خطرًا حقيقيًا على توسيع إبسيلون لـNFA. إذا أنتج الجسم مطابقة فارغة، يلتفّ عنصر END عائدًا إلى الجسم (فـjump الخاص به هو أوّل طفل في المجموعة)، فينتج الجسم مطابقة فارغة من جديد، ويصل إلى END ثانيةً، وهكذا. دون ما يوقفه، لن ينتهي DFS لـAdvance أبدًا.
يُحسم الحارس في وقت الترجمة ويُنفَّذ في وقت التشغيل. كلّما رأى المُخطِّط مجموعة جسمها قابل للنفي، يَسِم عنصر END لتلك المجموعة بـقابل للدوران الفارغ. ويحتفظ وقت التشغيل بمصفوفة بتّات للزيارة، تُمسح قبل كلّ توسيع DFS لحالة، ولا يُعلَّم فيها إلا عناصر END الموسومة تلك — فلا شيء آخر يمكنه الدوران، لأنّ أيّ التفاف آخر يكون قد استهلك صفًّا. الوصول إلى END مُعلَّم يعني أنّ الجسم اشتقّ للتوّ تكرارًا فارغًا، ولا تُهمَل الحالة: فعند الحدّ الأدنى أو فوقه تغادر المجموعة هناك (فالتكرار الفارغ يوقف المُكمِّم)، ودونه تنتقل الحالة إلى الالتفاف العادي، فيظلّ كلّ وصول فارغ يرفع العدّ حتى يبلغ min. خذ (A? B?){2,3} دون أن يطابق أيّ من المتغيّرين في أيّ مكان من تدفّق الصفوف:
iter 1: A? B? يطابقان صفر صفوف
→ END, count = 1 (دون min)
END مُعلَّم سلفًا (عند دخول
المجموعة)، لكنّه دون min:
→ عُد بالتكرار إلى A?
iter 2: A? B? يطابقان صفر صفوف
→ END, count = 2 (يستوفي min)
END مُعلَّم سلفًا، عند min:
→ غادر المجموعة
اخرج بمطابقة طول صفر
دون الحدّ الأدنى، تُخبر وسمة الدوران الفارغ معالج END أيضًا باستنساخ حالة تخطٍّ سريع إضافية إلى جانب مسار الالتفاف العادي:
advance_end (count دون min):
مسار الالتفاف:
عُد بالتكرار إلى الجسم
(يُبقي الباب مفتوحًا لمطابقة
حقيقية غير فارغة في
التكرار التالي)
إذا elem كان empty-loopable:
مسار fast-forward:
صفِّر count هذا العمق
اخرج من المجموعة عبر next،
معاملًا التكرارات المطلوبة المتبقية
بوصفها مطابقات فارغة
يلعب المساران دورين متكاملين. الالتفاف يلتقط الحالة التي لا يزال للجسم فيها مطابقات حقيقية ينتجها لاحقًا — مثلًا، في (A? B?){2,3} متبوعًا ببيانات لا يطابق فيها A إلا في صفوف لاحقة، فالالتفاف هو ما يُتيح للتكرارَيْن الثاني والثالث إيجاد مطابقات غير فارغة. والتخطّي السريع يخرج من المجموعة فورًا، مُعلِنًا "بقيّة التكرارات المطلوبة فارغة"، فيُنجح المطابقة بجسم بطول صفر. الجسم، لا جشع المجموعة ذاتها، هو ما يقرّر الترتيب: يأتي التخطّي السريع أوّلًا تحديدًا حين يفضّل الجسم المطابقة الفارغة (جسم متمنّع مثل (A?? B??))، وإذا بلغ المسار الأوّل FIN أُسقط الثاني، فلا يمكن لمسار أقلّ تفضيلًا أن يحلّ محلّ المطابقة المفضّلة. ويمنع فحص إزالة التكرار عند الإدراج أيًّا من المسارين من إنجاب أكثر من حصّته من الحالات.
إلى جانب حارس الدورة، تخفّف خدعة بدء أخرى التباس النتائج صفرية الصفوف عند بداية السياق تمامًا. خطوة إنشاء السياق عند كلّ صف بداية محتمل تُجري تقدّمًا أوّليًا عبر انتقالات إبسيلون قبل استهلاك أيّ صفّ، باستخدام موضع يسبق البداية الفعلية بصفّ. أيّ مسار يصل إلى رمز FIN عبر انتقالات إبسيلون وحدها — دون استهلاك صفّ — يُنتج موضع نهاية أصغر من موضع البداية؛ وذلك الإحداثي ذو المدى السالب، مع ما إذا كان FIN قد بُلِغ فعلًا، يُشفِّر الفرق بين مطابقة فارغة (مطابقة بطول صفر مقبولة) وبداية غير مطابِقة دون الحاجة إلى عَلَم منفصل.
3.6 كيف يبقى فضاء الحالة محدودًا
إبقاء وقت التشغيل محدودًا ليس نتيجة تحسين منفرد. بل هي الأثر التراكمي لمجموعة طبقية من قواعد التشذيب، تلتقط كلٌّ منها سببًا مختلفًا لنموّ فضاء الحالة عند نقطة مختلفة من دورة الصف. بعضها يُحسم وقت الترجمة ولا يُستشار إلا وقت التشغيل؛ والبعض الآخر يُطلق ديناميكيًا. بعضها يقتل حالات مفردة؛ والآخر يقتل سياقات بأكملها. قدّمت الأقسام أعلاه كلًّا منها في سياقه؛ والجدول أدناه يضعها على صفحة واحدة.
- مُسند فاشل Match
- حالات متغيّرات قُيِّمَت DEFINE الخاصة بها false على الصف الحالي — فروع ميتة.
- تقدّم سلسلة END المضمَّن Match
- متغيّرات بلغت حدّها الأقصى وكانت ستترك الحالة في منتصف التكرار؛ تُقدَّم عبر نهايات المجموعات ذات الطول الثابت ليتسنّى للامتصاص المقارنة عند النقطة الصحيحة.
- امتصاص السياق Absorb
- سياقات أحدث تقع كلّ حالاتها على نقطة مقارنة وتغطّيها حالة قابلة للامتصاص لسياق أقدم عند العنصر ذاته بعدّ أكبر أو مساوٍ — راجع §2.5 للقاعدة المفهومية، و§3.2 للأهلية وقت الترجمة، و§3.5 للفحص بين كلّ زوج.
- إزالة تكرار الحالات Advance
- حالات بُلِغت عبر فروع DFS مختلفة وانتهت إلى الموضع ذاته بالأعداد ذاتها — تنجو الأولى فقط (الأسبق معجميًا)؛ وتُسقَط المكافئات اللاحقة بصمت، وهو أيضًا كيفيّة فرض التفضيل (§2.4).
- إنهاء FIN المبكّر (داخل السياق) Advance
- حالات لا تزال معلّقة في طابور DFS حين يصل فرع إلى FIN — وفق الترتيب المعجمي، كلّ الحالات المتبقّية أقلّ تفضيلًا ويمكن إسقاطها فورًا.
- تشذيب المطابقة المرشّحة (عبر السياقات) Advance
- سياقات أخرى يقع صف بدايتها داخل مدى المطابقة المرشّحة — قد يستمرّ السياق الذي أصاب FIN في البحث عن مطابقة أطول (تراجع جشع)، لكن تحت
AFTER MATCH SKIP PAST LAST ROWفإنّ أيّ سياق داخل مدى المرشّحة لم يعد قادرًا على إنتاج مخرجات قابلة للتقرير، بصرف النظر عن كيفيّة انتهاء ذلك البحث، فيُشذَّب بمجرّد أن ينتهي Advance من السياق الذي سجّل المرشّحة. - حارس الدورة Advance
- توسيعات إبسيلون تصل إلى END لمجموعة قابلة للنفي مُعلَّم سلفًا ضمن DFS ذاته (عُلِّم عند الدخول عبر BEGIN، أو عند وصول سابق) — لكانت لولا ذلك لتلتفّ إلى الأبد؛ تغادر الحالة المجموعة هناك عند الحدّ الأدنى أو فوقه، وتواصل الالتفاف دونه.
- التخطّي السريع للدوران الفارغ Advance
- دون الحدّ الأدنى لمجموعة قابلة للنفي، مسار إضافي يخرج من المجموعة معلنًا التكرارات المتبقّية المطلوبة فارغة، ويُرتَّب مقابل الالتفاف وفق تفضيل الجسم.
- قطع الإطار المقيّد Match
- سياقات وصلت مطابقتها إلى الحدّ الأعلى للإطار الذي حدّده المستخدم — تُجبَر على عدم المطابقة فلا يمكنها التمدّد خلفه (§3.4).
قراءة المداخل بحسب وسم مرحلتها تتعقّب عمر السياق: يُطلق التشذيب عند كلّ صفّ عبر المراحل الرئيسة الثلاث (Match وAbsorb وAdvance). أمّا قراءة الأوصاف فتجمع القواعد بحسب ما تستهدفه: فروع ميتة، وسياقات زائدة، وحالات مكافئة، وحلقات لانهائية، وامتداد متجاوز للحدود التي يفرضها المستخدم.
لا تكفي قاعدة منفردة بحدّ ذاتها. التخطّي السريع للدوران الفارغ وحده لن يوقف حلقات إبسيلون اللانهائية؛ والامتصاص وحده سيُفرط في التوحيد حين يُشير DEFINE إلى بداية المطابقة؛ وإزالة التكرار وحدها لن تُزيل السياقات الزائدة، بل الحالات الزائدة فقط. يبقى وقت التشغيل خطّيًا في الحالات التي تهمّ — PATTERN (A+ B+ C+ D) على 100,000 صفّ، قياس اللوحة ③ في الملصق — فقط لأنّ كلّ طبقة تلتقط ما تفوّته الطبقات فوقها. ويوثّق المصدر حالات لا تلتقطها الطبقات: إزالة التكرار تُبقي متمايزةً الحالاتِ التي لا تختلف إلا في الأعداد فوق min، لذا فإنّ (A{2,} B)+ C مع C غير صحيحة أبدًا يحمل Θ(n²) حالة في الذروة ويُنشئ Θ(n³) منها (37 ث على 320 صفًّا)، وسلسلة من تبديلات قابلة للنفي بالكامل تُعدَّد مسارًا مسارًا، لذا يستغرق (A?|B?){30} أكثر من نصف ساعة.
3.7 مخرجات EXPLAIN
EXPLAIN ANALYZE على استعلام بـRPR يُظهر إحصاءات على مستوى NFA لا توجد لدوال النوافذ العادية. في الصيغة النصّية تُصدَر إلى جانب مُشغِّل النافذة، بعد سطر Pattern: وأيّ أسطر Nav Mark (التي يُظهرها EXPLAIN العادي أيضًا) وسطر Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(each only when DEFINE uses navigation
that feeds it)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
N skipped (len min/max/avg)
(second NFA line only when either
count is nonzero; a zero count
prints without its (len ...))
الصيغ غير النصّية تُصدر كلّ عدد بوصفه خاصّية مستقلّة. Peak وtotal أدوات قياس مباشرة لوقت التشغيل: كم حالة كانت حيّة في آنٍ واحد، وكم أُنشئت على مدى عمر الاستعلام، وكم دُمج بإزالة التكرار؛ ويعدّ pruned السياقات التي فشلت بعد صفّ واحد. تَفصِل توزيعات أطوال المطابقات أربع نتائج — مطابقات ناجحة، ومحاولات مطابقة فشلت بعد أكثر من صفّ واحد (mismatched)، وسياقات مُمتصّة، وسياقات حرّرتها AFTER MATCH SKIP PAST LAST ROW لأنّها بدأت داخل مطابقة مُسجَّلة (skipped) — والإبلاغ عنها بـmin/max/avg يُبيّن الباثولوجيات الأدائية بنظرة: في الجولة السليمة تظهر معظم السياقات إمّا مطابِقة وإمّا مُمتصّة، وأطوال غير المطابقة صغيرة.
عدّادَا Nav Mark يُبلِّغان عن ميزانية احتفاظ tuplestore التي تستنبطها §3.3 من DEFINE. Lookback هو أعمق وصول إلى الوراء من الصف الحالي عبر PREV وLAST بأيّ إزاحة (بما فيها الافتراضية 0) والصيغ المركّبة بـLAST داخلية؛ بينما Lookahead هو أدنى وصول إلى الأمام (سالب حين ينظر إلى ما قبل بداية المطابقة) مقاسًا من بداية مطابقة أقدم سياق حيّ، تساهم به FIRST والصيغ المركّبة بـFIRST داخلية.
يُطبَع كلّ عدّاد عددًا صحيحًا ثابتًا حين تكون الإزاحة ثابتًا، و"runtime" حين تكون الإزاحة تعبيرًا غير ثابت لا يُعرف إلا لكلّ مسح، و— لـLookback وحده — "retain all" حين تفيض الإزاحة؛ أمّا Lookahead الذي يفيض فيُطبع "infinite". لا يُصدَر كلّ سطر إلا حين تغذّيه ملاحةٌ ما في DEFINE، ويظهر كلاهما تحت EXPLAIN العادي أيضًا: تُحسم الإزاحات الثابتة عند تهيئة المنفّذ، بينما الإزاحة التي لا تُعرف إلا عند التشغيل (معامل خطّة عامّة، مثلًا) تُطبع "runtime" هناك وعددها الصحيح المحلول تحت EXPLAIN ANALYZE.
معًا، تُتيح هذه العدّادات تنقيح أداء RPR دون توصيل gdb بالخادم.
إلى جانب العدّادات، يطبع EXPLAIN سطر Pattern: مبنيًّا من مصفوفة العناصر المُترجَمة، فيُظهر النمط بعد إعادات الكتابة وقت الترجمة (PATTERN (A A) يُشرَح بوصفه a{2}) ويحمل مُعلِّمَي الامتصاص # (نقطة المقارنة) و~ (منطقة قابلة للامتصاص)؛ ولا يُعرض DEFINE ولا خيار AFTER MATCH SKIP. أمّا إعادة إنتاج الجُمل كما كُتبت، بما في ذلك المُكمِّمات المتمنّعة وتكرار المجموعات وخيار التخطّي، فهي مهمّة pg_get_viewdef()، التي تبذل جهدًا لجعل هذه الرحلة الذهابية والإيابية مستقرّة، ليتمكّن pg_dump وpg_upgrade من حفظ كائنات RPR دون انجراف دلالي — وتتحقّق سلسلة الانحدار rpr_explain منها حالةً حالة (راجع §4).
§4. الاختبارات — خريطة التغطية
يأتي الترقيع مع خمس سلاسل انحدار تُمارس معًا كلّ طبقة وُصفت في §3 — نحو 22,000 سطر من SQL، كلّ سلسلة تركّز على شأن مختلف. الفصل متعمَّد: إبقاء شؤون المحلّل النحوي وصحّة وقت التشغيل وتفاعلات المُخطِّط وتنسيق المخرجات في ملفّات منفصلة يُسهّل توطين الأخطاء، ويمنع تغييرًا غير ذي صلة في طبقة من إبطال اختبارات في أخرى عَرَضًا. السلاسل الخمس هي:
- rpr
- التكامل مع جملة WINDOW — سيناريوهات نوافذ واقعية على بيانات أسهم اصطناعية (شكل V، شكل W، ارتفاعات متتالية، انعكاسات)، إضافة إلى دلالات الملاحة وأخطاء قيود DEFINE.
- rpr_base
- طبقة المحلّل النحوي — قبول الكلمات المفتاحية، وأشكال البنية النحوية، والمُكمِّمات، وتحليل الملاحة، ورسائل الأخطاء، واستقرار رحلة pg_dump/pg_upgrade ذهابًا وإيابًا؛ إضافة إلى طبقة المُخطِّط — تحسين النمط، وأعلام الامتصاص، والتراجع عن التحسين، والتكامل مع المُخطِّط.
- rpr_nfa
- وقت تشغيل NFA — الحلقة ثلاثية المراحل، والامتصاص في كلّ شكل قابل للامتصاص، وحالات حافة دورة حياة السياق.
- rpr_explain
- تنسيق المخرجات — إحصاءات NFA، وتفكيك النمط، واقتباس المعرّفات، واستقرار التنسيق عبر إعادة التحميل.
- rpr_integration
- تفاعلات المُخطِّط — حراسات تمنع تحسينات نافذة غير ذات صلة من إفساد دلالات RPR.
4.1 rpr — السيناريوهات الشاملة
سلسلة السيناريو هي الواجهة العامّة لمجموعة الاختبارات: تستخدم مجموعة بيانات أسعار أسهم اصطناعية بنحو 1,600 صفّ وتشغّل عليها استعلامات واقعية — تعافي شكل V، شكل W (قاع مزدوج)، ارتفاعات وانخفاضات متتالية، أنماط انعكاس، أقسام متعدّدة الرموز. وهذه السيناريوهات هي الاختبارات الوحيدة التي تُقرأ مدخلاتها ومخرجاتها كاستعلامات قد يكتبها مستخدم فعلًا؛ أمّا بقيّة الملفّ، كالسلاسل الأخرى، فاختزالية — تعشيش PREV/NEXT وأخطاء الإزاحات غير الثابتة، وقواعد الإشارة في DEFINE، ودلالات إزاحات الملاحة.
لأنّ هذه الاستعلامات تجمع كلّ طبقة (المحلّل النحوي، والمُخطِّط، والمنفّذ، و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. تتّبع اختباراتها نمطًا متّسقًا: صفوف VALUES مضمّنة تحمل مصفوفة أسماء متغيّرات تُعلن أيّ متغيّرات DEFINE تطابق عند كلّ صفّ، مقترنة بنمط يستجوب سلوكًا محدّدًا في وقت التشغيل. تفصل تعبيرة المصفوفة اختبار وقت التشغيل عن آلية تقييم DEFINE — فما يُختبر هو "بافتراض أنّ هذه المتغيّرات تطابق هنا، هل تُنتج حلقة NFA مدى المطابقة المتوقَّع؟" لا "هل يحسب مُقيِّم تعابير DEFINE هذه البوليانيّات بصواب؟" يُختبر مُقيِّم DEFINE في مكان آخر (rpr_base للتحليل، وrpr للسلوك الشامل).
تركيبة اختبار نموذجية تبدو هكذا — عمود مصفوفات أسماء متغيّرات، كلّ مدخل يبيّن أيّ متغيّرات DEFINE تُطلق على ذلك الصف، مع نمط تختبر جُمل DEFINE فيه تلك الأسماء مباشرةً:
SELECT id, flags, first_value(id) OVER w AS ms, last_value(id) OVER w AS me FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A','B']), (3, ARRAY['A','B']), (4, ARRAY['B']), (5, ARRAY['_']), (6, ARRAY['A'])) AS t(id, flags) WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING INITIAL PATTERN (A+ B+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));
قراءة عمود المصفوفة عموديًا هي قراءة لسيناريو الاختبار مباشرةً. الصفّان 2 و3 يحملان كلا الاسمين — A وB يُطلَقان هناك معًا، فللـNFA خيار حقيقي بشأن أين يتحوّل من ساق A إلى ساق B. المطابقة المتوقَّعة (A في الصفوف 1–3 يليها B في الصف 4، تحت التفضيل الجشع للمعيار) تُحدَّد بتلك الأعلام وحدها، دون تقييم تعابير ذي شأن هنا — = ANY ليس إلا الطبقة التافهة التي تُعرّض عمود المصفوفة لـDEFINE، ليس ما يُختبر. كتابة السيناريو ذاته بمُسند رقمي (price > PREV(price) ونحوه) ستُشَبِّك اختبار NFA بسلوك مُقيِّم المُسندات؛ بينما تُبقي تعبيرة المصفوفة الاثنين منفصلَين بنظافة، ويشير الفشل هنا مباشرةً إلى حلقة NFA.
تغطية الامتصاص شاملة بشكل خاص، لأنّ الامتصاص هو التحسين الأرجح لإنتاج إجابات خاطئة بصمت إذا اشتغل في غير محلّه. تغطّي الاختبارات كلّ شكل من تحليل حالات §3.2:
- متغيّر بسيط غير محدود (
A+) — الانهيار الكلاسيكي من N إلى 1؛ - مجموعات بطول ثابت (
(A B)+، و(A B{2})+، ومُعشَّش بثلاثة مستويات((A (B C){2}){2})+)؛ - متغيّر غير محدود رائد بلاحقة ثابتة (
A+ B) — يحمل الـA+الرائد فقط أعلام الامتصاص دون اللاحقة؛ - امتصاص لكلّ فرع داخل تبديل (
B+ C | B+ D)؛ - متغيّرات غير محدودة متعدّدة (
A+ B+) — الرائد فقط قابل للامتصاص؛ - مُكمِّمات متمنّعة (
A+?) — تَحقَّقَ من استثنائها من الامتصاص؛ - غير محدود غير رائد (
A B+) — تَحقَّقَ من استثنائه.
إلى جانب الامتصاص، تُغطّي السلسلة دورة حياة السياق: السياقات المتداخلة تحت AFTER MATCH SKIP TO NEXT ROW، وتنظيف السياق الفاشل في منتصف التدفّق، وحسم نهاية القسم للسياقات غير المكتملة، والسياقات التي تُلتقى بها بعد تسجيل مطابقة مرشّحة في السياق الرأس. كلٌّ منها يقابل قاعدة تشذيب محدّدة في §3.6، وكُتبت الاختبارات لتفشل بصوت عالٍ إذا أساءت القاعدة الإطلاق (إمّا بإبقاء سياقات زائدة حيّة، أو بقتل سياق كان عليه أن يُنتج مخرجات).
4.4 rpr_explain — استقرار المخرجات
مخرجات EXPLAIN جزء من العقد المواجه للمستخدم — تُحلّلها أدوات طرف ثالث (لوحات المراقبة، وقارئات السجلّات)، والتغييرات التي تبدو تجميلية قد تكسرها. تتحقّق سلسلة rpr_explain من ثلاثة أمور:
- عدّادات NFA تظهر في المكان الصحيح — إحصاءات كلّ WindowAgg (الحالات peak/total/merged، والسياقات peak/total/pruned، وتوزيعات الأطوال لـmatched/mismatched/absorbed/skipped) تظهر تحت
EXPLAIN ANALYZEفي النصّ وJSON وXML بالتسميات الموثّقة، ويظهر Nav Mark Lookback وLookahead تحديدًا حين تغذّيهما ملاحةٌ في DEFINE. - الأنماط تُفكَّك بشكل صحيح — كلّ شكل مُكمِّم، بما في ذلك المتغيّرات المتمنّعة والصيغ المقيّدة؛ وكلّ تبديل؛ وكلّ مجموعة؛ وكلّ صيغ
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لدوال النوافذ المستقلّة عن الإطار مثلrow_numberوrankوntile. إطار RPR هو مدى المطابقة، لا نافذة تجميع، ويجب أن يبقى حرفيًا. - دفع شرط التشغيل
- يمكن عادة دفع مرشِّح
WHEREرتيب على مخرجات دالّة نافذة إلى مُشغِّل النافذة بوصفه شرط توقّف. لـRPR هذا سينهي مطابقة النمط مبكّرًا، وقد يقطع مطابقات في منتصف التمدّد. - إزالة تكرار النوافذ (RPR مقابل غير RPR)
- عادةً تُدمج نافذتان بـ
ORDER BYوإطار متطابقَين في واحدة. لا يمكن لنافذة RPR وغير RPR أن تتشاركا الحالة لأنّ جانب RPR يحمل نتائج المطابقة. - إزالة تكرار النوافذ (DEFINE أو SKIP مختلف)
- نافذتا RPR بنفس
PATTERNوجُملDEFINEمختلفة أوAFTER MATCH SKIPمختلف تُنتجان مطابقات مختلفة ويجب أن تبقيا متمايزتين، حتى لو كان شكلهما البنيوي متطابقًا. - إسقاط المخرجات غير المستخدمة
- هذا التحسين مسموح بتطبيقه: حين لا يقرأ الاستعلام المحيط مخرجات النافذة، تصبح دالّة النافذة NULL ويُسقَط WindowAgg الخاص بها، ويبقى عدد الصفوف دون تغيير. تتحقّق الاختبارات من أنّ الأعمدة التي يقرؤها DEFINE لا تزال تصل إلى WindowAgg حين يبقى، ومن أنّ النافذة تُبقى حين تُقرأ قيمتها.
- الانتقالات المعكوسة للتجميعات المتحرّكة
- تجميعات النوافذ ذات دالّة الانتقال المعكوسة يمكن عادة تقييمها تدريجيًا مع تحرّك الإطار. الإطار المختزل لـRPR ليس نافذة منزلقة؛ ومسار الانتقال المعكوس سيُنتج نتائج خاطئة.
وتتحقّق حالات أخرى من أنّ تقدير الكلفة يأخذ DEFINE في الحسبان، وأنّ الاستعلام الفرعي الحامل لنافذة RPR لا يُسطَّح، وأنّ تعابير DEFINE لا تتسرّب إلى WindowAgg أعلى، وأنّ LIMIT يبقى فوق WindowAgg؛ وتُشغّل مجموعة ثانية RPR إلى جانب CTE، والوصلات، وعمليات المجموعات، والجُمل المُعدّة، والجداول المُقسَّمة وبنى مشابهة. تتّبع معظم الحالات المحروسة الشكل ذاته: خطّ مرجعي يُحفّز التحسين (غالبًا استعلام غير RPR، يُفحص في EXPLAIN)، ثم استعلام RPR ذو شكل بنيوي مماثل لا يُطبَّق فيه التحسين — في حالة إزالة التكرار بحسب DEFINE/SKIP يكون الخطّ المرجعي نافذتي RPR متطابقتين، وتتحقّق حالة الانتقال المعكوس من التجاوز بتجميع يكتب في السجلّ بدلًا من EXPLAIN. الشطران معًا يثبتان أنّ الحارس في المُخطِّط يقوم بعمل حقيقي، لا أنّه يُجيز كلّ استعلام دون تحقّق فعلي.
هذه السلسلة هي أيضًا سبب قصر §3.4. آليّات "حدود المطابقة" — الإطار المختزل، وSKIP، وINITIAL، وقطع الإطار المقيّد — تُختبر تشغيليًا في مكان آخر؛ وما يتحقّق منه rpr_integration هو أنّ لا مرحلة مُحسِّن أخرى تعبث بها أثناء المرور. نجاح rpr_integration هو ما يتيح لبقيّة السلاسل الثقة بأنّ مدخلاتها تصل إلى المنفّذ سليمة.