Row Pattern Recognition Derinlemesine İnceleme

§1. Standart, Alt Küme ve Açık Sorular

1.1 Standart kapsamı

Satır Örüntü Tanıma, SQL'e ISO/IEC 9075-2:2016 ile dahil edilmiş ve tamamlayıcı belge olan ISO/IEC 19075-5:2021'de (Bölüm 5, "Row Pattern Recognition") açıklanmıştır.

Standart, aynı temel mekanizma için iki yüzey tanımlar. R010 özelliği, türetilmiş bir tablo üretmek için FROM listesine bir MATCH_RECOGNIZE yan tümcesi yerleştirir; R020 özelliği ise aynı örüntü mantığını pencere işlevi çıktısı üretmek üzere bir WINDOW belirtimine katlar. İki yüzey, sözdizimlerinin büyük bölümünü ve tüm anlamlarını paylaşır, ancak işlevsel olarak farklı giriş noktalarıdır — bir veritabanı bunlardan birini veya her ikisini birden uygulayabilir.

Burada ele alınan yama serisi yalnızca R020'nin bir alt kümesini gerçekler; tablo yan tümcesi biçimi bilinçli olarak kapsam dışıdır.

R020 yüzeyi küçük ama anlatım gücü yüksektir. Bir sorgu, pencere belirtimi içine üç yan tümce ekleyerek pencereye bir örüntü iliştirir: PATTERN, adlandırılmış örüntü değişkenleri üzerinde bir düzenli ifade tanımlar; DEFINE, her değişkeni belirleyen Boole yüklemini sağlar; AFTER MATCH SKIP ise ardışık eşleşmelerin bölüm içinde nasıl konumlandırılacağını denetler.

İsteğe bağlı MEASURES, SUBSET, INITIAL/SEEK ve yardımcı CLASSIFIER() işlevi özelliği tamamlar. (Standardın MATCH_NUMBER() işlevi yalnızca R010 yüzeyine aittir — 19075-5 §6.3.3 (6) bunu R020'den açıkça hariç tutar.)

Yama, bu sözcük dağarcığını önemsiz olmayan sorguları çalıştırmaya yetecek kadar kapsar; ancak gerçeklenmesi henüz inşa edilmemiş altyapıya bağlı olan birkaç yapı için durur.

Bu bölümün geri kalanı, standardın sözcük dağarcığını yamanın halihazırda desteklediği ve bilinçli olarak sonraya bıraktığı şeyler olarak ikiye ayırır. Aşağıdaki listeler yama serisinin mevcut durumunu yansıtır.

1.2 Gerçeklenen özellikler

Gerçeklenen sözcük dağarcığı, en başta satır örüntü tanımayı motive eden kanonik V şekli, W şekli ve tersine çevirme örüntülerini ifade etmek için yeterlidir. Ayrıca tüm standart niceleyicileri — yedi gönülsüz değişkenin tamamı dahil *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — ve DEFINE koşullarının komşu satırları karşılaştırması için ihtiyaç duyduğu dört gezinme ilkesi de kapsanır.

PATTERN yan tümcesi

Bir pencere belirtimi içinde satır örüntüsünü tanımlar.

Regex: + * ? |

Standart niceleyiciler ve seçenek (alternation).

Regex: ( ) gruplama

Parantezli alt örüntüler.

Regex: {n} {n,} {,m} {n,m}

Sınırlı tekrar sayıları.

Gönülsüz *? +? ?? {n}? {n,}? {,m}? {n,m}?

Standardın tanımladığı yedi gönülsüz (non-greedy) varyantın tamamı (absorption optimizasyonundan hariç tutulmuştur).

DEFINE yan tümcesi

Her örüntü değişkenini belirleyen Boole koşulları.

Evrensel satır örüntüsü değişkeni

DEFINE içinde nitelendirilmemiş sütun referansları (ör. yalın Price) geçerli satıra çözümlenir, 19075-5 §4.10/§4.16'ya göre.

PREV, NEXT (ofset ile)

Geçerli satırdan n satır önceye/sonraya erişir (varsayılan 1); içteki argüman, gezilen satırda değerlendirilen rastgele bir değer ifadesidir.

FIRST, LAST (ofset ile)

Eşleşmeye göreli bir satıra erişir; FIRST(expr, n), eşleşmenin başlangıcından n sonraki satırı; LAST(expr, n) ise en son eşleşme satırından n önceki satırı hedefler.

Bileşik gezinme (dört biçim)

Bir iç FIRST/LAST üzerine katmanlanmış dış PREV/NEXT adımı: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — hem iç hem dış adım kendi ofsetini kabul eder.

INITIAL

Örüntü eşleşmeleri geçerli satırdan başlamak zorundadır (varsayılan).

AFTER MATCH SKIP PAST LAST ROW

Varsayılan atlama modu; bağlam emilimine uygundur.

AFTER MATCH SKIP TO NEXT ROW

Örtüşen eşleşmelere izin verir; emilimi devre dışı bırakır.

1.3 Gerçeklenmemiş

Gerçeklenmemiş kalan özellikler üç gevşek gruba ayrılır. Birincisi — açık ara en büyüğü — MEASURES etrafında kümelenen yapılar ailesidir: MEASURES yan tümcesinin kendisi, SUBSET, CLASSIFIER(), B.price gibi örüntüyle nitelenmiş sütun referansları ve LAST(B.price) ya da PREV(B.price) gibi örüntüyle nitelenmiş gezinme.

Bunlar bağımsız boşluklar olmaktan çok, tek bir eksik parçanın farklı görünümleridir: yürütücünün eşleşme başına bir tarihçe — eşleşmedeki her satır için, o satırın hangi örüntü değişkenine eşlendiğini gösteren bir kayıt — tutması gerekirdi ve bu yapıların hiçbirinin bu olmadan anlamlı bir tanımı yoktur. CLASSIFIER() bu kayıttan değişken adını okur; B.price, kayıt girdisi B diyen satırların price sütununu okur; LAST(B.price) aynı satır kümesini gezerek sonuncusunu seçer; SUBSET U = (A, B) her iki bucket üzerinde toplulaştırma yapan sanal bir değişken tanımlar; MEASURES ise tam da bu toplulaştırmayı kullanarak AVG(U.Price) gibi ifadeleri değerlendirir.

Mevcut yürütücü, DEFINE yüklemlerini satır satır değerlendirir ama ortaya çıkan değişken atamalarını hiçbir yere kaydetmez — sonradan sorgulanacak hiçbir şey yoktur. Bu nedenle tarihçe altyapısının inşası tüm grup için ön koşuldur; kayıtlar var olduğunda ayrı özellikler küçük projeksiyonlar olarak ortaya çıkar.

İkinci gruplama alternatif atlama hedefleriyle ilgilidir: AFTER MATCH SKIP TO etiket, AFTER MATCH SKIP TO FIRST değişken ve AFTER MATCH SKIP TO LAST değişken. Bunlar da eşleşme tarihçesine bağlıdır; çünkü yürütücünün en son eşleşme içindeki belirli bir etiketli satırı işaret edebilmesi gerekir.

Geriye kalan maddeler heterojen bir kuyruktur: SEEK anahtar sözcüğü (INITIAL'in alternatifi), boş örüntü (), dışlama biçimi {- … -} ve sıralamadan bağımsız PERMUTE operatörü.

MEASURES

Eşleşme başına adlandırılmış çıktı ifadeleri, örn. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; R020'de bir pencere işlevi gibi OVER aracılığıyla ortaya çıkar. FINAL / RUNNING anahtar sözcüklerini kabul eder (19075-5 §5.4); R020'de bu ikisi aynı değere indirgenir, çünkü ölçümler her zaman eşleşmenin son satırında değerlendirilir (19075-5 §6.9 (3)).

SUBSET

Örüntü değişkenlerinin adlandırılmış birleşimleri, örn. SUBSET U = (A, B, C). Bir örüntü değişkeninin referans gösterilebildiği her yerde kullanılabilir — MEASURES, DEFINE içindeki örüntüyle nitelenmiş referanslar, CLASSIFIER(U) — bunların hepsi eşleşme tarihçesini gerektirir.

CLASSIFIER()

Belirli bir satırın hangi örüntü değişkeni olarak eşleştirildiğini döndürür. Hem DEFINE hem MEASURES için tanımlıdır (19075-5 §5.9); herhangi bir satırdaki yanıt, o satır için eşleşme tarihçesinde kayıtlı değişken adıdır.

Örüntüyle nitelenmiş sütun referansı

DEFINE veya MEASURES içinde çıplak B.price — adlandırılmış değişken olarak eşleştirilen satırın o sütununun değeri.

Örüntüyle nitelenmiş gezinme

Gezinmeyi adlandırılmış değişken olarak eşleştirilen satırlarla sınırlar, örn. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Eşleşme pencerede herhangi bir yerden başlayabilir (INITIAL'in tersine).

AFTER MATCH SKIP TO etiket

Etiketli bir satıra atlar.

AFTER MATCH SKIP TO FIRST değişken

Adlandırılmış değişken olarak eşleştirilen ilk satıra atlar.

AFTER MATCH SKIP TO LAST değişken

Adlandırılmış değişken olarak eşleştirilen son satıra atlar.

Regex: {- -}

Dışlama — eşleşen satırları eşleşme başına çıktıdan çıkarır.

Regex: ()

Boş örüntü — boş diziyle eşleşir.

PERMUTE(...)

Listelenen değişkenler arasında sıralamadan bağımsız eşleşme.

DEFINE içinde toplama işlevleri

SUM, AVG, COUNT gibi toplamlara DEFINE yüklemlerinde izin verilmez. Standart bunlara kısmi eşleşme üzerinden çalışan toplamlar olarak (zaten bir değişkene eşleştirilmiş satırlara karşı satır başına değerlendirme) izin verir; bu da MEASURES/CLASSIFIER()'ın gerektirdiği aynı eşleşme tarihçesine bağlıdır.

Burada belirtilmeye değer dört nokta daha vardır; çünkü bunlar eksiklik sanılmaya açıktır.

İlki, ^ ve $ örüntü çıpalarının WINDOW yan tümcesinde RPR ile birlikte standardın kendisi tarafından izin verilmemesidir (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; temel tanım 19075-5 §4.14.1'dedir); yokluğu bir boşluk değil, uyumdur.

İkincisi, MATCH_NUMBER() de R020'den standart tarafından dışlanmıştır (19075-5 §6.3.3 (6) ve 19075-5 §6.9 (1)) — yalnızca R010 yüzeyinin parçasıdır ve buradaki yokluğu da eksik bir özellik değil, yine uyumdur.

Üçüncüsü, standardın R020'ye dayattığı yapısal yasaklar kümesidir (19075-5 §6.17): satır örüntü tanıma, başka bir satır örüntü tanımanın içine yerleştirilemez; MEASURES ve DEFINE dış referans içeremez; MEASURES veya DEFINE içindeki alt sorgular, satır örüntü değişkenlerine referans veremez; ve RPR özyinelemeli bir sorgunun içinde kullanılamaz.

Dördüncüsü, MATCH_RECOGNIZE'ın kendisi — aynı mekanizmanın tablo yan tümcesi yüzeyi olan R010 özelliği — bu yamanın kapsamı dışındadır. PostgreSQL'in eninde sonunda R010'u ekleyip eklemeyeceği gelecekteki bir seri için soru olacaktır, bunun ölçütü değil.

§2. Örnekler — Gerçekte Nasıl Çalışır

Bu bölümdeki örnekler artımlı olarak ilerler. Satır örüntü eşleşmesinin metin örüntü eşleşmesinden gerçekten neden farklı olduğunun kavramsal nedeniyle başlıyor, ardından DEFINE koşullarını ilginç kılan dört gezinme işlevini tanıtıyor ve son olarak uçtan uca üç izlemeyi adım adım inceliyoruz: tek bir eşleşme (NFA hareketi), kolay durumda bağlam emilimi ve emilimin güvensiz hale geldiği durum.

Gezinmeyi ucuz kılan iç mekanizma — 1 yuvalı tuple takası — yürütücünün tasarımına aittir ve burada değil, sonraki bölümde ele alınmıştır.

2.1 Satır örüntülerinin metin örüntülerinden farkı

Bir metin düzenli ifadesi karakter akışıyla eşleşir ve her konumda dikkate alınacak tam olarak bir simge vardır. Çalışma zamanı sorusu — "geçerli simge 'A''ya eşit mi?" — tek bir evet/hayır yanıtına sahiptir. Geri izlemeli otomatlar bunu kullanır: karakter başına en fazla bir dal hayatta kalır ve belirsizliğin maliyeti girdiyi yeniden okuyarak ödenir.

Bir satır örüntüsü temel bir biçimde farklıdır. Satır tek bir simge değildir; bir Boole yüklemleri kümesine, yani DEFINE koşullarına karşı değerlendirilen sütunlardan oluşan bir tuple'dır. Aynı satırda iki yüklem aynı anda doğru olabilir ve standartta bu yüklemlerin karşılıklı olarak dışlayıcı olması gerektiğini söyleyen hiçbir şey yoktur. Şu örneği düşünün:

DEFINE
  A AS price > 100,
  B AS volume > 1000,
  C AS price > 200

price = 150, volume = 2000 olan bir satır hem A'yı hem B'yi karşılar ama C'yi karşılamaz. Örüntü eşleştirici bunu tek bir duruma indirgeyemez — iki örüntü değişkeni canlıdır ve bunlardan herhangi birini adlandıran herhangi bir örüntü öğesi ilerleyebilir. Bu nedenle NFA, bölüm satırı başına bir değil birden fazla eşzamanlı durum taşımak zorundadır.

Bu tek gözlem, mimarinin geri kalanını yönlendirir. Yürütme durumu bir bağlamlar listesidir, her bağlam bir durumlar listesidir ve her satırda çalışma zamanı her duruma şunu sorar: "burada doğru olan değişkenler verildiğinde, nereye gidebilirim?" Ortaya çıkan dallanmalar, çalışma zamanının birkaç katmanlı budamaya — bağlam içinde durum tekilleştirme, bağlamlar arası emilim ve §3.6'da incelenen diğer kurallar — neden ihtiyaç duyduğunun nedenidir; bunlar olmadan canlı durum ve bağlam sayısı bölümle birlikte büyür ve örüntü eşleştirme süper-doğrusal hale gelir.

2.2 Gezinme işlevleri

Yalnızca geçerli satıra başvuran DEFINE koşulları sınırlıdır; ilginç olan neredeyse her örüntü, geçerli satırı komşularıyla veya eşleşmenin daha erken kabul edilmiş satırlarıyla karşılaştırmayı gerektirir. Standart bunun için dört gezinme işlevi sağlar ve yama bunların hepsini gerçekler.

PREV(expr [, n])

Geçerli satırdan n satır önceki satır (varsayılan n = 1). "Bugün vs. dün" karşılaştırmaları için kullanılır.

NEXT(expr [, n])

Geçerli satırdan n satır sonraki satır. İleriye dönük bakış; pencere monoton olduğundan pencere biçiminde nadirdir.

FIRST(expr [, n])

Mevcut eşleşmenin baştan sayılarak n'inci eşleşmiş satırı. "Bu eşleşmeyi başlatan satırla karşılaştır."

LAST(expr [, n])

En son eşleşmiş satırlardan n'incisi. "En son eşleşmiş satırla karşılaştır."

Dört ilkel birleşebilir: PREV ve NEXT, bir FIRST veya LAST çağrısını sarmalayarak anlamı "eşleşmeye göreli bir satıra git, ardından ondan sabit bir mesafe adımla" olan dört bileşik biçim verir. Bu, bir DEFINE ifadesinin, örneğin, eşleşme başlamadan hemen önceki satırı okumasına olanak tanır.

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

Eşleşmenin n'inci satırından m satır geriye adımla (varsayılan m = 1). "Bu eşleşme başlamadan hemen önceki değer neydi?"

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

Eşleşmenin n'inci satırından m satır ileriye adımla. Geçerli satıra bağlı kalmaksızın eşleşmenin daha derinine ulaşır.

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

En son eşleşmiş satırlardan n'incisinden m satır geriye adımla. "En son eşleşmenin biraz öncesindeki bir satırla karşılaştır."

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

En son eşleşmiş satırlardan n'incisinden m satır ileriye adımla.

Burada iki pratik nokta belirtmeye değer. İlki, gezinme bileşik olabilir: PREV(FIRST(price)), eşleşme başlamadan hemen önceki satırı okur ve yama bunu destekler. İkincisi, gezinmenin yürütücü optimizasyonları üzerinde sonuçları vardır. PREV ve NEXT geçerli satıra göredir ve her zaman güvenlidir; FIRST ve LAST'ın ofsetli varyantları eşleşme sınırlarına göredir ve bu, bağlam emilimi ile etkileşir, planlayıcıyı aksi takdirde atacağı bazı bağlamları canlı tutmaya zorlar. Bu etkileşimin arkasındaki mekanizma §2.6'nın konusudur.

2.3 Uygulamalı örnek 1 — NFA hareketi

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)
);

Örüntü dört öğeye düzleştirilir:

[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 fiyat serisi için:

Anahtar nokta: 3. satırda, satır hem START (her zaman doğru) hem DOWN'u karşılar; ama 2. satırdan hayatta kalan tek durum DOWN-çıkış dalındadır, bu nedenle yalnızca UP → DOWN geçişi alınır. §2.1'in çok-durumlu doğası, her UP eşleşmesinde dallanma olarak görünür (durum UP+'ta kalabilir veya DOWN+'a doğru ilerleyebilir). Açgözlü tercih "çıkmadan önce tekrar döng"dür; dolayısıyla yeterli veri altında döngü dalları eşleşmeyi daha da uzatırdı; burada döngüdeki DOWN 5. satırda ölür (130 ≮ 108) ve önceki FIN adayı (0–4 satırları) — DOWN 4. satırda çıktığında üretilen — eşleşme olarak kesinleşir.

Sorgunun sonucu doğrudan bu izlemeden çıkar. RPR anlamları altında, first_value(price) ve last_value(price) pencere işlevleri yalnızca eşleşmeyi başlatan satırda değerlendirilir — eşleşmedeki diğer her satır bu pencere işlevleri için NULL üretir, çünkü onun indirgenmiş çerçevesi boştur. Bu nedenle verilerimiz için çıktı, posterin sağ üst panelinde gösterdiği tabloya benzer:

0. satır eşleşmenin başlangıcıdır, bu nedenle çerçevesi 0–4 satırlarını kapsar ve pencere işlevleri V şeklinin açılış fiyatını ($100) ve dip fiyatını ($108) raporlar. 1–4 satırları eşleşmenin içindedir ama başlangıcı değildir, bu nedenle NULL alırlar. 5. satır (fiyat $130) herhangi bir eşleşmenin dışındadır ve aynı şekilde NULL alır.

2.4 Uygulamalı örnek 2 — Seçenek ve sözcüksel sıra

(A | B) biçimi eşleştiriciye bir seçim verir: herhangi bir satırda iki seçenek bağımsız olarak test edilir ve herhangi bir sayıda seçenek eşleşebilir. §2.1'in çok-durumlu doğası tam burada tek bir bağlamın içinde görünür hale gelir — bağlamlar arasında değil (bu emilimdir), yürütücünün eşgüdümlü olarak keşfettiği paralel dallar boyunca.

PATTERN ((UP | HIGH) DONE)
DEFINE
  UP   AS price > PREV(price),
  HIGH AS price > 100,
  DONE AS volume > 1000

Fiyatın hem yükseldiği hem de 100 doları aştığı bir satır düşünün — hem UP hem HIGH doğrudur. Her seçenek kendi durumunu üretir: biri UP dalında yürür, biri HIGH dalında yürür. DONE onları çözene kadar paralel ilerlerler.

Her iki dal aynı satırlar üzerinde aynı uzunlukta bir eşleşme üretir; bu da eşleştiriciye iki aday yol bırakır — biri UP, DONE, diğeri HIGH, DONE etiketli. Standart bunu sözcüksel sıra ile çözer: (UP | HIGH) içinde yazılan seçenekler arasında, eşleşme uzunluğundan bağımsız olarak önce yazılan kazanır. UP, HIGH'tan önce göründüğü için hayatta kalan yol UP, DONE'dir.

Sözcüksel sıra, CLASSIFIER() sonunda gerçeklendiğinde onu iyi tanımlı kılan şeydir — her iki yüklem de doğru olduğunda bile çalışma zamanının kullanıcıya "bu satır HIGH değil, UP olarak eşleşti" diyebilmesini sağlar. Sözcüksel sıra, seçenek için birincil kuraldır: sözcüksel olarak daha erken bir dal, sözcüksel olarak daha geç bir dal daha uzun bir eşleşme üretecek olsa bile ona karşı kazanır; ve sözcüksel olarak daha geç (muhtemelen daha kısa) bir dal, sözcüksel olarak daha erken her dal FIN'e ulaşmadan önce ölürse yine de kazanabilir. Açgözlü uzunluk tek bir niceleyici içinde kararlaştırılır — aynı seçenek dalının iki tamamlamasında, açgözlü niceleyici daha fazla yinelemeyi tercih eder.

2.5 Uygulamalı örnek 3 — Bağlam emilimi (aynı kader)

Emilimi sergileyen en basit örüntü, DEFINE A AS TRUE ile PATTERN (A+)'dır. Her satır A ile eşleşir ve standart, eşleştiricinin her satırı olası bir eşleşme başlangıcı olarak değerlendirmesini gerektirir. Naif olarak, bu, N satırlı bir bölüm için N bağlam demektir. Beş satırlı bir bölüm alalım (herhangi bir veri — yüklem sabit doğrudur):

Bellek O(n)'den O(1)'e düşer. Atmayı haklı çıkaran emilim kuralı, niceleyici sınırsız olduğunda basittir:

Posterin sol alt paneli ("① Bağlam Emilimi") tam olarak bu kuralın beş satır üzerinde görselleştirilmiş halidir.

Kuralda ince ama önemli bir nokta gizlidir: atma güvenlidir, çünkü A AS TRUE yüklemi, hangi bağlam soruyor olursa olsun her satırda aynı değere değerlendirilir. Yalnızca geçerli satıra veya ondan sabit bir ofsete başvuran her yüklem için aynı şey geçerlidir — PREV dahil. Sonraki örnek, PREV tabanlı bir yüklem kullanarak somut bir fiyat haftasına geçer ve §2.6 tam olarak aynı haftayı tekrar kullanarak güvenli ve güvensiz emilim arasındaki simetriyi belirgin hale getirecektir:

PATTERN (RISE+)
DEFINE RISE AS price > PREV(price)

Pazartesi'den Cuma'ya $100, $108, $112, $116, $110 işlem haftasını alın — dört yükselişi ani bir düşüş izliyor. C1'in Salı günü başladığını varsayın (RISE'ın eşleştiği ilk gün: $108 > $100) ve yürütücü, Çarşamba günü başlayan C2'yi de spekülatif olarak izlesin. Her satırın RISE koşulu, satırın fiyatını hemen önceki ile karşılaştırır — bağlam düzeyinde değil, bölüm düzeyinde bir gerçektir — bu nedenle iki bağlam, paylaştıkları her satırda aynı Boole değerini hesaplamaya zorlanır:

Yüklem, her bağlamın kendi sınırlarına bağlı olmaya başladığı anda hikâye kırılır — ve §2.6 tam olarak bununla ilgilidir.

2.6 Uygulamalı örnek 4 — Emilim ne zaman güvensiz hale gelir

Bir analistin, bir hisse senedinin koşunun başladığı günden itibaren on dolar içinde kaldığı ardışık işlem günlerini bulmak istediğini varsayın — bir tür konsolidasyon penceresi. Örüntü ve DEFINE şöyledir:

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

Koşul artık geçerli satırın fiyatını mevcut koşunun başlangıcındaki fiyatla karşılaştırır. Farklı günlerde başlayan iki koşunun farklı FIRST(price) değerleri vardır, dolayısıyla aynı örüntü öğesinde ve aynı sayıdaki iki durum artık değiştirilebilir değildir: gelecekleri, emilimin atmak üzere olduğu sınıra bağlıdır.

§2.5'tekiyle tam olarak aynı işlem haftasını alın — Pazartesi'den Cuma'ya $100, $108, $112, $116, $110. Çalışma zamanı yine aynı anda iki aday koşuyu canlı tutar: C1 Pazartesi başladı, C2 Salı başladı (STABLE+ altında her satır potansiyel bir koşu başlangıcıdır).

Emilim altında C2, Salı günü C1'e birleştirilirdi — birleştirilen bağlam yalnızca tek bir tavanı tutar, dolayısıyla C2'nin farklı görünümü (tavan $118, yalnızca Cumartesi sona eren dört günlük koşu) iç durumdan artık geri kazanılamaz. C2'nin canlı kalması gerekir, çünkü çalışma zamanının hâlâ ihtiyaç duyabileceği bağımsız bir eşleşme adayıdır: C1'in eşleşmesi Çarşamba sona erdiğinde, sonraki deneme sıfırdan başlamak yerine hâlâ çalışan bir C2'den devam etmek zorundadır. Bir DEFINE yüklemi eşleşme başlangıcı bağımlılığı taşıdığında, planlayıcı bu nedenle emilimi önleyici olarak devre dışı bırakır.

(Önde giden bağlamın eşleşmesi başarılı olduğunda, kabul edilen aralığının içinde başlayan bağlamlar — varsayılan AFTER MATCH SKIP PAST LAST ROW altında — basitçe atılır; yalnızca önde giden eşleşme başarısız olursa çalışma zamanının geri dönebileceği bir yer olması için canlı tutulurlar.)

Posterin sağ alt panelindeki bağımlılık tablosu ("② Gezinme"), hangi gezinme biçimlerinin eşleşme başlangıcı bağımlılığı yarattığını özetler:

§2.5 ve §2.6'daki iki örnek tek bir kurala indirgenir. Emilimi güvenli kılan şey aynı kaderdir: aynı örüntü öğesindeki her bağlam, gelecekteki her yükleme aynı yanıtı hesaplayacaksa, yalnızca en eskisinin tutulması gerekir. Farklı kaderler emilimi güvensiz kılar: yüklemler bağlama özel duruma göre dallandığı anda — ki bu tam olarak FIRST ve ofsetli LAST'ın yaptığı şeydir — her canlı bağlam, başka hiçbir bağlamın geri kazanamayacağı bir geleceği temsil eder ve bunlardan herhangi birini atmak yanlış bir yanıt üretme riski taşır.

Planlayıcı bu ayrımı derleme zamanında saptar ve bağlam başına emilimin uygulanıp uygulanmayacağına karar verir. Bu aynı zamanda posterin ③ panelindeki kıyaslamanın hem başarı hem başarısızlık durumlarında doğrusal kalmasının nedenidir: emilim güvenli olduğunda çalışma zamanı bağlamları çöker; olmadığında planlayıcı yanlış bir yanıt riski almak yerine çoklu bağlam maliyetini kabul eder.

Posterdeki kıyaslama sayıları, aynı algoritmanın ölçekte oynamasıdır. Başarı örüntüsü (A+ B+ C+ D)'de, bir eşleşme onaylandıktan sonra hem PostgreSQL hem Trino O(n) ölçeklenir ve PostgreSQL'in önderliği — kabaca 16× ile 33× arası — çoğunlukla JVM farkıdır.

Başarısızlık örüntüsü (A+ B+ C+ E)'de, Trino'nun emilimi yoktur ve her potansiyel eşleşme başlangıcını kovalayarak O(n²)'ye düşer; 100.000 satırda beş saatten fazla sürer, oysa PostgreSQL hâlâ 92 ms'de bitirir; yaklaşık 217.000× hızlanma.

Bu fark mühendislik cilası değildir — tam olarak §2.5 ve §2.6'daki aynı-kader / farklı-kader ayrımının, bölümdeki her potansiyel eşleşme başlangıcının her satırına uygulanmasıdır.

2.7 Uygulamalı örnek 5 — SKIP emilimi ne zaman devre dışı bırakır

Önceki örnek emilimi veri tarafından kırdı: DEFINE'daki FIRST, her bağlamın yüklemleri farklı değerlendirmesine neden oldu. Emilim çıktı tarafından da kırılabilir ve bunu AFTER MATCH SKIP yan tümcesi denetler.

DEFINE A AS TRUE ile PATTERN (A+) örüntüsünü, hepsi A ile eşleşen beş satır üzerinde düşünün. Varsayılan AFTER MATCH SKIP PAST LAST ROW altında, eşleştirici en erken satırdan başlayan en uzun eşleşmeyi bulur ve ardından üstüne atlar; bu eşleşmenin içinde başlayan herhangi bir bağlam gereksiz olarak örtük şekilde atılır — tam olarak emilimin ele almak için tasarlandığı durum. Çıktı tek bir eşleşmedir, 0–4 satırları; ve çalışma zamanının yalnızca tek canlı bir bağlama ihtiyacı vardır.

Atlama modunu AFTER MATCH SKIP TO NEXT ROW'a değiştirin ve sözleşme değişir:

PATTERN (A+)
DEFINE A AS TRUE
AFTER MATCH SKIP TO NEXT ROW

Şimdi her potansiyel başlangıç konumu, eşleşmeler örtüştüğünde bile ayrı raporlanmalıdır. Aynı beş satır için çalışma zamanının beş eşleşme yayması gerekir: 0–4, 1–4, 2–4, 3–4 ve 4–4 satırları. Bunlardan hiçbiri "daha erken başlayan daha uzun bir tanesi" ile değiştirilemez, çünkü standart kullanıcının hepsini istediğini söyler.

Yüklem'in değişmediğine dikkat edin. A AS TRUE, hangi bağlamın sorduğundan bağımsız olarak her satırda aynı şekilde değerlendirilir, dolayısıyla §2.5 aynı-kader koşulu hâlâ karşılanır. Değişen şey çıktı gerekliliğidir: özdeş geleceklere sahip bağlamlar bile birlikte var olmalıdır, çünkü sonucun farklı satırlarına karşılık gelirler. Bu nedenle planlayıcı, DEFINE yan tümcesinden bağımsız olarak AFTER MATCH SKIP TO NEXT ROW yürürlükteyken bağlam emilimini devre dışı bırakır.

§2.6 ve §2.7'yi yan yana koymak, emilimin ne zaman başarısız olduğunun tam resmini verir:

Her iki koşul da etkilenen bağlamlar için emilimi devre dışı bırakmaya yeter. Hiçbiri yürürlükte değilken — varsayılan AFTER MATCH SKIP PAST LAST ROW, yalnızca PREV, NEXT veya çıplak LAST kullanan DEFINE koşullarıyla — çalışma zamanı her örüntü konumu için tek bir bağlama çöker ve baştan sona doğrusal kalır.

§3. Tasarım — Ayrıştırıcıdan Yürütücüye

Satır Örüntü Tanıma, iyi tanımlanmış ara biçimler üzerinden iş aktaran üç aşama olarak gerçeklenir. Ayrıştırıcı, SQL metnini bir örüntü ağacı ile bir DEFINE yüklemleri listesine çevirir; planlayıcı ağacı, örüntü öğelerinin düz bir dizisine derler ve hangilerinin bağlam emilimine katılabileceğine karar verir; yürütücü diziyi, üç aşamalı bir döngüde bölüm satırları üzerinde satır satır çalıştırır. Her aşamanın kendi veri biçimi vardır ve tasarım yaratıcılığının çoğu sınırlardadır: önbelleğe sığan düz bir NFA, başvuru başına bir tane materyalleştirmek yerine tek bir tuple yuvasını yeniden kullanan bir gezinme modeli ve O(n²) belleği O(n)'e indiren bir emilim kuralı.

SQL metin
  │
  │  ayrıştırıcı aşaması
  ▼    çerçeveyi doğrula
       örüntü ağacını kur
       DEFINE'ı tip kontrolü

örüntü ağacı + DEFINE listesi
  │
  │  planlayıcı aşaması
  ▼    ağacı optimize et
       düz NFA dizisine derle
       emilebilirliğe karar ver

düz NFA + emilim bayrakları
  │
  │  yürütücü aşaması
  ▼    satır başına motor:
       Eşleştir → Em → İlerle

eşleşme sonucu:
  başlangıç satırı, uzunluk, başarı/başarısızlık

Aşağıdaki bölümler bu boru hattını takip eder. §3.1 ayrıştırıcıyı ve örüntü ağacının biçimini kapsar; §3.2 ağacı düz NFA'ya dönüştüren derlemeyi kapsar; §3.3 DEFINE yüklemlerinin komşu satırlara bakmak için kullandığı gezinme modelini kapsar; §3.4 eşleşme sınırı işlemini — bir eşleşmenin nerede başlayıp nerede biteceğini sabitleyen SKIP, INITIAL ve sınırlı çerçeve kurallarını — kapsar; §3.5 üç aşamalı satır başına motordur; §3.6 durum uzayını sınırlı tutan tüm budama mekanizmalarını derler; §3.7 ise gerçeklemenin EXPLAIN çıktısında ortaya çıkardıklarını inceler.

3.1 Ayrıştırıcı — örüntü ağacının inşası

Ayrıştırıcı, örüntü tanımayı bir pencere belirtimi içindeki PATTERN yan tümcesinin varlığıyla tanır. İlk işi çerçeve doğrulamasıdır; çünkü RPR sıradan pencere sorgularının dayatmadığı kısıtlamalar getirir: çerçeve modu ROWS olmalıdır (RANGE veya GROUPS değil), başlangıç sınırı CURRENT ROW olmalıdır ve EXCLUDE seçeneklerine izin verilmez. Bunlar optimizasyon değil, uyum kontrolleridir — RPR'nin çerçeve kavramı eşleşme aralığıdır ve standart, bunu eşleşmiş satırlardan başka bir şeyle doldurmayı düşünmez.

Çerçeve doğrulamayı geçtikten sonra, ayrıştırıcı PATTERN yan tümcesini dört tür düğümden oluşan bir ağaca çevirir — bir değişken referansı, bir dizi (birleştirme), bir seçenek ve bir grup (parantezli alt örüntü). Her düğüm, niceleyiciyi üç sayı olarak taşır — alt sınır, üst sınır (sonsuz olabilir) ve gönülsüz eşleşme bayrağı:

Daha sonra her DEFINE yüklemi bölümün sütunlarına karşı tip kontrolüne tabi tutulur ve bir Boole ifadesine zorlanır. Bunun bir parçası olarak iki pratik şey gerçekleşir. İlk olarak, bir DEFINE yüklemi tarafından başvurulan her sütun, sorgunun çıktı gereksinimlerinin parçası olarak kaydedilir; böylece çevredeki sorgu bunları seçmese bile planlayıcı bu sütunları yürütücü aşamasına yayar — bu olmadan çalışma zamanının değerlendirebileceği hiçbir şey olmazdı. İkinci olarak, PATTERN'de görünen ama DEFINE'da hiç görünmeyen değişkenler örtük olarak doğrudur: her satırla eşleşirler.

3.2 Derleme — AST'tan düz NFA'ya

Planlayıcı, ayrıştırıcının ağacını yürütücünün çalıştıracağı veri yapısına dönüştürür: indeksle adreslenen, örüntü öğelerinden oluşan düz bir dizi. Derleme altı adımlı bir boru hattı olarak ilerler:

compile(astTree):
  1. AST'ı optimize et
  2. boyutu ve derinliği ölç
  3. öğe dizisini tahsis et
  4. AST'tan doldur
       (next/jump işaretçilerini ata)
  5. sonlandır — FIN nöbetçisini kur
  6. emilime uygun öğeleri işaretle

Düz biçim basit bir nedenle seçilmiştir: yürütücünün örüntüyü bölüm başına birçok kez dolaşması gerekir ve bitişik, indekslenebilir bir dizi, dolaşılacak en ucuz veri yapısıdır. İlginç olanlar 1. ve 6. adımlardır — 1. adım dizinin ne kadar büyük olacağını belirlediği için, 6. adım ise §2.5'teki emilim optimizasyonunun hiç devreye girip girmeyeceğine karar verdiği için.

AST optimizasyonu

Optimizasyon iki kez kazanç sağlar: bir kez düz dizinin statik öğe sayısında, bir kez de çalışma zamanında işlenen her satırda. Her dönüşüm, çalışma zamanının numaralandırması gereken durum uzayını azaltır. Optimize edici, AST değişmeyi bırakana kadar art arda sekiz yeniden yazma kuralını uygular:

SEQ düzleştirme

SEQ(A, SEQ(B, C)) → SEQ(A, B, C)

Ardışık değişken birleştirme

A A → A{2}
A{2,3} A{1,2} → A{3,5}

Ardışık grup birleştirme

(A B)+ (A B)+ → (A B){2,∞}

Ardışık ALT birleştirme

(A | B) (A | B) (A | B) → (A | B){3}

Önek/sonek emilimi

A B (A B)+ → (A B){2,∞}

ALT düzleştirme & tekilleştirme

(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)

Niceleyici çarpımı

(A+)+ → A+
(A{2,3}){5} → A{10,15}

Tek çocuk soyma

SEQ(A) → A
(A){1,1} → A

Niceleyici çarpımı, güvenlik kontrolü gerektiren tek dönüşümdür: optimize edici yalnızca üç güvenli durumda çöker — her iki niceleyici sınırsız ((A+)+ → A+), dış kesin ((A{2,3}){5} → A{10,15}) ya da çocuk önemsiz {1,1} ((A){2,5} → A{2,5}). Diğer kombinasyonlar, düz biçimin gözden kaçıracağı boşluklar getirebilir — örn. (A{2}){2,3} yalnızca {4, 6}'yı kabul eder, ama naif bir A{4,6} 5'i de kabul ederdi — bu yüzden optimize edici bunları olduğu gibi bırakır.

Öğe biçimi

Düz dizinin her öğesi örüntüde tek bir konumu temsil eder. Beş mantıksal tür vardır: bir değişken referansı (satır tüketen tek tür); grup başlangıcı ve grup sonu işaretleri (parantezli bir alt örüntüyü açıp kapatırlar); seçenek işareti (bir dallar listesinin başını çeker); ve örüntünün sonunda bir bitiş işareti.

Her öğe ayrıca bir derinlik (grup yuvalama düzeyi), niceleyici (bir min ve max yineleme sayısı, sonsuz olabilir) ve iki geçiş işaretçisi taşır — next, "bu öğeyi tükettikten sonra nereye gidileceği" ve jump, "nereye atlanacağı" (seçenek tarafından dalları zincirlemek için, grup başlangıcı tarafından niceleyici sıfıra izin verdiğinde gövdeyi atlamak için ve grup sonu tarafından gövdeye geri dönmek için kullanılır).

PATTERN ((A B)+) için derlenen dizi şöyle görünür:

PATTERN ((A B)+) şuna derlenir:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (grubu açar; min = 0 olduğunda
     jump FIN'e atlar)

[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
    (grubu kapatır; jump geri döner)

[4] FIN    örüntü tamamlandı

Örüntü next aracılığıyla soldan sağa okunur, doğrusal olmayan kenarları jump ele alır. idx 3'te END'in jump'ı idx 1'e geri işaret eder; sınırsız dış niceleyici böyle döngüye girer; idx 0'da BEGIN'in jump'ı, grup isteğe bağlı olsaydı END'i atlayarak idx 4'e atlardı. Çalışma zamanı asla çalışma zamanında bir grafik kurmak zorunda kalmaz — diziyi dolaşırken yalnızca bu iki işaretçiyi takip eder.

Öğe başına nitelikler

Biçimin ötesinde, her öğe çalışma zamanının o konumdaki davranışını yönlendiren dört mantıksal nitelik taşır:

Reluctant

Niceleyici genişlemesinin sırasını tersine çevirir. Açgözlü niceleyiciler "çıkış"tan önce "tekrar döng"ü dener; gönülsüz niceleyiciler önce "çıkış"ı dener. A+? için değişken tarafından taşınır; ((…)+?) için grubun BEGIN ve END'i tarafından taşınır.

Boş-döngülenebilir

Gövdesi nullable olan grup sonlarına atanır ((A?)*, (A? B?)+, (A | B*)). Çalışma zamanına, normal geri döngünün yanı sıra hızlı ileri sarma çıkışı eklemesini söyler; böylece döngü koruması, boş yinelemeler üretebilen gruplarda meşru eşleşmeleri öldürmez.

Emilebilir-bölgenin-içinde

Bir emilime uygun bölgenin içinde kalan her öğeyi işaretler — çalışma zamanı tarafından geçerli durumun hâlâ güvenli bölgede olup olmadığını izlemek için kullanılır.

Emilim-karşılaştırma-noktası

Emilim karşılaştırmalarının çalışması gereken belirli öğeyi işaretler. Basit bir A+ için değişkene düşer; (A B)+ gibi sınırsız bir grup için yalnızca grup sonuna düşer.

"Bölge içinde" ile "karşılaştırma noktası" arasındaki ayrım önemlidir, çünkü emilim yalnızca yinelemelerin kapandığı noktalarda anlamlıdır. (A B)+'nın gövdesinin içinde, çalışma zamanı yineleme ortasındadır ve sayı henüz o tur için son değerine ulaşmamıştır; burada karşılaştırma, karşılaştırılamaz değerleri karşılaştırmak demek olurdu. Çalışma zamanı karar verebilmeden önce durumun grup sonuna ulaşması gerekir. Bu nedenle ilk nitelik "hâlâ emilebilir bölgedesin" der; ikincisi "karşılaştırma noktasına ulaştın — şimdi kontrol et" der.

Emilebilirlik analizi

Derlemenin 6. adımı, §2.5'in "aynı kader" kuralına derleme zamanı tanığını veren şeydir. Karar katmanlıdır:

isAbsorbable(query):
  if SKIP modu != SKIP PAST LAST ROW
      → return false
  if çerçeve sonu != UNBOUNDED FOLLOWING
      → return false
  if herhangi bir DEFINE match_start'a bağımlıysa
      → return false
  AST'ı dolaş ve
  yapısal bir duruma uyan
  öğeleri işaretle

İlk üç kontrol sorgu düzeyindedir: tam olarak §2.7 (çıktı tarafı: SKIP modu), sınırlı çerçeve (sınır monotonluğu kırar) ve §2.6 (veri tarafı: DEFINE'da FIRST veya ofsetli LAST) koşullarına karşılık gelirler. Bunlardan herhangi biri başarısız olduğunda analiz hiçbir bayrak ayarlamaz ve emilim sorgu çapında devre dışı bırakılır. Hepsi geçtiğinde, AST yürüyüşü üç yapısal biçimi kabul eder:

Durum 1 — Basit sınırsız değişken

A+, A*, A{2,∞}

Her yineleme tam olarak bir satırdır. Daha eski bir bağlamın sayısı paylaşılan her konumda her zaman ≥ daha yenisinin sayısıdır.

Durum 2 — Sabit uzunluklu grup, sınırsız dış

(A B)+, (A B{2})+, ((A (B C){2}){2})+

Her çocuğun min == max değeri vardır, dolayısıyla gövde anlamsal olarak açılmış {1,1} biçimine eşdeğerdir — (A B{2})+, (A B B)+ gibi davranır. Her yineleme sabit sayıda satır tüketir; sayı baskınlığı hâlâ geçerlidir.

Durum 3 — Gövdesi sınırsız bir değişkenle başlayan grup

(A+ B)+

Önde gelen sınırsız değişkenin kendisi emilebilirdir (Durum 1) ve daha eski bağlamları korur. Durum A'yı geçer geçmez emilim durur — gövdenin geri kalanında monotonluk garantisi yoktur, bu yüzden bayraklar yalnızca A üzerinde ayarlanır.

Bu üç biçimin kapsamadığı yapısal durumlar da en az o kadar öğreticidir. A B+ mevcut kuralla emilemez, çünkü önde gelen A, sınırsız kısım başlamadan önce bir satır tüketir, dolayısıyla bir satır arayla başlayan bağlamlar sınırsız gövde içinde farklı konumlardadır. (Sabit uzunluklu önekleri bir gölge yol aracılığıyla işleyen bir takip "PREFIX absorption" uzantısı tasarlanmıştır ve ayrı bir yama için planlanmıştır.) A+? gibi gönülsüz niceleyiciler yapı gereği hariçtir: emilim kuralı, daha uzun eşleşmelerin daha kısaları kapsadığı açgözlü anlamları varsayar ve gönülsüz eşleşme bu yönü tersine çevirir.

Sonuç, örüntü başına değil öğe başına bir karardır. Tek bir sorgu planı, (A+ B+ C) veya (A+ B+)+ gibi örüntülerin önde gelen A+'sı için emilimi etkin tutabilir — ikincisi, önde gelen öğeye uygulanan Durum 3'tür — ve sonrası için her şey için devre dışı bırakılabilir; çalışma zamanı, emilim geçişini her düşündüğünde geçerli durumun öğesindeki karşılaştırma-noktası niteliğine bakar. Bir durum emilebilir olmayan bir bölgeye girdiğinde, o durum için emilim kalıcı olarak kapanır — §2.5 ve §2.6'nın algoritmik düzeyde doğru olmasını gerektirdiği şey tam olarak budur.

3.3 Gezinme — 1 yuvalı tuple takası

DEFINE ifadeleri, bir satıra karşı değerlendirilen sıradan SQL ifadeleridir, ancak PREV, NEXT, FIRST veya LAST içerebilirler — farklı satırlara işaret eden başvurular. Satırların kendileri zaten pencerenin tuplestore'unda tamponlanmıştır; yürütücünün hâlâ yönetmesi gereken şey, SQL ifade mekanizmasının okuduğu tuple yuvasıdır; çünkü ifadenin içindeki sütun başvuruları plan zamanında bir yuvaya bağlanır. Gerçekleme her gezinme çağrısı için tek bir gezinme yuvasını yeniden kullanır: yuva, iç ifade değerlendirilmeden önce takılır ve sonra geri yüklenir; böylece SQL ifade mekanizmasının geri kalanı hiçbir zaman farkı bilmez.

Yürütücünün gördüğü model küçüktür: DEFINE ifadesinin değerlendirildiği satırı tutan bir geçerli satır yuvası ve çalışma zamanının geçici olarak farklı bir satıra yönlendirebileceği bir gezinme yuvası vardır. Çalışma zamanı, herhangi bir gezinme çağrısının çevresinde gezinme yuvasını ayarlar, iç ifadeyi sanki geçerli satırı okuyormuş gibi değerlendirir, sonra orijinal satırı geri yükler. Sözde kod:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos geçerli aralığının dışındaysa:
      return NULL

  current_row_slot'u kaydet
  targetPos'taki satırı
    current_row_slot'a getir
  result = eval_inner_expression()
  current_row_slot'u geri yükle
  return result

Hile, kaydedilip geri yüklenecek tam olarak bir yuva olmasıdır. İç ifade — aritmetik, işlev çağrıları veya diğer sütun referansları dahil her ne ise — geçerli satır için kullanacağı aynı değerlendirme yolunu kullanarak takas edilen yuvaya karşı çalışır. Alternatif değerlendirici yok, gölge yuva yok, tuple kopyası yok.

Bileşik gezinme, takasın hâlâ bir kez gerçekleşmesi için ayrıştırma zamanında düzleştirilir. PREV(FIRST(price)) iki adımlı bir gezinme olarak tanınır — "ilk eşleşmiş satıra git, ardından bir satır önceye adımla" — ve bileşik türde tek bir gezinme çağrısı olarak saklanır. Çalışma zamanı hedef konumu iki aşamada hesaplar ama son satırı getirmek için yalnızca tek bir yuva takası gerçekleştirir:

compute_target_position(call):

  # geçerli satıra göreli
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # eşleşmeye göreli
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # bileşik: eşleşmeye göreli, sonra adımla
  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

  uygun aralığa karşı doğrula
  (FIRST/LAST iç için eşleşme aralığı,
   dış adım için bölüm aralığı)

Aynı DEFINE'daki birkaç gezinme çağrısı aynı satırı hedeflediğinde — price > PREV(price) AND volume > PREV(volume) gibi her iki çağrının önceki satıra çözüldüğü yaygın ifadeler gibi — bir konum önbelleği tuplestore getirmesini kısa devre yapar. Önbellek yalnızca "son getirilen konumu" saklar ve takasın kendisi tek bir işlem olarak kalır.

Gezinme çağrılarının sınıflandırılması, planlayıcının emilim kararına katkısıdır. Planlayıcı her DEFINE ifadesini dolaşır ve her değişkeni iki kovadan birine ayırır; tüm bağlamların aynı satırda aynı Boole değerini hesaplayıp hesaplamayacağına ya da her bağlamın kendininkini hesaplayıp hesaplamayacağına dayanır. Kova çalışma zamanında iki şeyi belirler: değişkenin ne sıklıkla değerlendirildiği (bir kez paylaşılmış veya etkilenen bağlam başına bir kez — §3.5 1. Aşama) ve çevredeki durumun bağlam emilimi için uygun olup olmadığı (§2.5 vs §2.6).

Sınıflandırma plan zamanında gerçekleştirilir ve her DEFINE değişkeninin yanında saklanır, dolayısıyla çalışma zamanı karar vermek için zaman harcamaz — bir satırı işlerken her değişken için kovayı basitçe okur.

Tutma bütçesi

Gezinme, pencere işlevi mekanizmasının aksi takdirde akıtıp geçtiği satırlara erişir. Bu satırları erişilebilir tutmak için yürütücü, son satırların kayan bir penceresini tutan bir tuplestore üzerine inşa edilmiştir; soru, o pencerenin ne kadar geniş olması gerektiğidir. Yama derleme zamanında, iki tamamlayıcı ofsetten karar verir:

Geriye bakma bütçesi

Herhangi bir DEFINE çağrısının geçerli satırdan ne kadar geriye uzanabileceği.

Katkıda bulunanlar: PREV, ofsetli LAST, PREV(LAST(...)), NEXT(LAST(...))

Başlangıçtan ileriye bakma bütçesi

Herhangi bir DEFINE çağrısının en eski canlı bağlamın eşleşme başlangıcından ne kadar ileri (veya negatifse geriye) uzanabileceği.

Katkıda bulunanlar: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Çalışma zamanında tuplestore'un kırpma işareti, iki konumdan hangisi daha erkense ona ayarlanır — geçerli satır eksi geriye bakma bütçesi ve en eski canlı bağlamın eşleşme başlangıcı artı ileriye bakma bütçesi. Bu işaretten önceki hiçbir şey, herhangi bir canlı bağlamdaki herhangi bir gezinme çağrısı tarafından erişilemez ve tuplestore bunu düşürmekte serbesttir. EXPLAIN'in raporladığı iki Nav Mark sayacı (§3.7) — Lookback ve Lookahead — iki bütçenin ölçülen tepe değerleridir, yürütücünün sorgu boyunca her iki yönde de ulaşmak zorunda kaldığı en derin noktalar.

3.4 Eşleşme sınırları — SKIP, INITIAL ve sınırlı çerçeve

Başarılı bir eşleşme küçük bir değer demeti olarak kaydedilir: bir geçerlilik bayrağı, bir başarı/başarısızlık bayrağı, eşleşmenin başladığı satır ve tükettiği satır sayısı. Geçerlilik bayrağı ayarlandığında, yürütücüye yönelik sonraki sorgular — "bu satır bir eşleşmenin içinde mi?" — demete bakarak O(1) ile yanıtlanabilir. Sıfır uzunluk bir hata değil, gerçek bir sonuçtur: hiçbir satır tüketmeden eşleşen bir örüntüyü temsil eder ve yürütücünün bunu "bu konumda henüz eşleşme denenmedi"den ayırması gerekir.

AFTER MATCH SKIP yan tümcesi, sonraki eşleşme denemesinin nereden başlayacağına karar verir. AFTER MATCH SKIP PAST LAST ROW eşleşme sonundan sonraki satıra geçer, çoğu sorgunun istediği örtüşmeyen çıktıyı üretir ve emilim optimizasyonunu etkinleştirir.

AFTER MATCH SKIP TO NEXT ROW yalnızca eşleşme başlangıcından sonraki satıra geçer, örtüşen eşleşmelere izin verir; bu nedenle bu mod yürürlükteyken planlayıcı tüm sorgu planı için emilimi devre dışı bırakır.

Standardın tanımladığı diğer iki atlama hedefi — AFTER MATCH SKIP TO FIRST değişken ve AFTER MATCH SKIP TO LAST değişken — bu yamanın tutmadığı eşleşme başına tarihçeye bağlıdır. Bunlar dilbilgisinde hiç bulunmaz, bu nedenle ikisinden biri verilirse ayrıştırıcı genel bir sözdizimi hatası verir.

Aynı şey, spesifikasyonun INITIAL'a alternatifi olan SEEK için de geçerlidir. SEEK altında, R satırından başlayan bir eşleşme denemesi, yalnızca R'de değil, R'den çerçevenin sonuna kadar herhangi bir satırda başarılı olabilir. Yama yalnızca INITIAL'ı gerçekler: her potansiyel eşleşme belirli bir satıra çapalanır. SEEK istenirse ayrıştırıcı bir hata verir. Sınırlı çerçeveler kendi muamelesini alır — kullanıcı UNBOUNDED FOLLOWING yerine ROWS BETWEEN CURRENT ROW AND N FOLLOWING yazdığında, yürütücü eşleşmesi sınıra ulaşmış herhangi bir bağlamı bir uyumsuzluk zorlayarak kısa devre yapar ve emilim devre dışı bırakılır, çünkü sınır, emilimin dayandığı monotonluk varsayımını kırar.

3.5 Üç aşamalı satır başına motor

Yürütücünün satır başına sürücüsü, çevredeki pencere işlevi mekanizması tarafından, belirli bir satırın eşleşmiş bir çerçeveye ait olup olmadığını bilmesi gerektiğinde çağrılır. Sürücü, geçerli başlangıç konumu için bağlamı bulur veya oluşturur, her DEFINE yüklemini geçerli satıra karşı bir kez değerlendirerek değişken başına bir Boole dizisi üretir, ardından NFA'yı bir satır ileriye sürer. İleri adımın kendisi sabit sırayla üç aşamadır — Eşleştir, Em, İlerle — aynı dış döngüde sarılmıştır:

processRow(currentPos):

  # 1. Aşama — EŞLEŞTİR (yakınsama)
  for each context:
      if bağlam sınırlı çerçeveyi aşıyorsa:
          uyumsuzluğu zorla (erken kesinleştir)
          continue
      if matchStartRow paylaşılan
         değerlendirme konumundan farklıysa:
          eşleşme başlangıcına bağımlı
          DEFINE değişkenlerini yeniden değerlendir (§3.3)
      match(context, varMatched)

  # 2. Aşama — EM
  if örüntü emilebilirse:
      her bağlamın bayraklarını yenile
      absorb_contexts()

  # 3. Aşama — İLERLE (ıraksama)
  for each context:
      advance(context, currentPos)

Sıralama bir biçim seçimi değildir. Eşleştir önce çalışmalıdır, çünkü emilim eşleşme sonrası sayıları karşılaştırır; Em'i Eşleştir'den önce çalıştırmak, ölmek üzere olan durumları karşılaştırırdı. İlerle en son çalışmalıdır, çünkü yeni durumlar yaratan tek aşamadır — hayatta kalan her durumu, her dal sonraki satırı bekleyen bir değişkene veya FIN nöbetçisine ulaşana kadar epsilon geçişleri yoluyla genişletir. Em'i İlerle'den sonra çalıştırmak, ıraksamış ardılları karşılaştırmak demek olurdu ve durumların en temiz şekilde karşılaştırılabileceği noktayı kaçırırdı.

1. Aşama — Eşleştir

Eşleştir bir "yakınsama" aşamasıdır: durumlar ya artırılmış sayı ile hayatta kalır ya da ölür. İnce bir nokta şudur: emilebilir bir bölgede oturan değişkenler için Eşleştir, Em'in temiz karşılaştırma yapabilmesi için küçük bir miktar ileri ilerleme de gerçekleştirir. Kapsama koşulu yalnızca emilebilir karşılaştırma noktasında — sınırsız grubun END'inde — ateşlenir, dolayısıyla yineleme ortası değişkenleri (örneğin (A B)+ içindeki B) yeni eşleştirmiş durumların Eşleştir sırasında o karşılaştırma noktasına kadar yürütülmesi gerekir; aksi takdirde Em karşılaştırılacak uygun bir şey bulamaz ve optimizasyon hiçbir zaman devreye girmez.

match(context, varMatched):
  for each state in context:
      elem = pattern[state.elemIdx]
      if elem değişken değilse:
          continue   # advance bunu işler

      if not varMatched[elem.varId]:
          drop state   # ölü dal
          continue

      state.counts[elem.depth] += 1

      # Sonraki aşamanın yineleme
      # ortası yerine karşılaştırma
      # noktası öğesinde karşılaştırma
      # yapabilmesi için satır içi ileri ilerleme.
      if elem bölge içindeyse ama
         karşılaştırma noktası değilse,
         ve max sayısına ulaştıysa,
         ve elem.next bir grup sonu ise:

          END zincirini yürü:
            dış grup sayısını artır
            state.elemIdx'ı END'e ilerlet
            hâlâ bölge içinde, çıkmak
              zorunda ve next END iken devam et
          (karşılaştırma noktasında veya
           hâlâ döngülenebilir bir öğede durur)

END zinciri yürüyüşü, iç içe sabit uzunluklu grupları emilebilir kılan şeydir. ((A B){2})+'da, B max'a ulaştığında (B, {1,1}'dir), iç grubun sayısı artmalıdır; o sayı da max'a ulaşırsa — iç {2}'yi kapatarak — dış grubun sayısı da artmalıdır ve böyle devam eder; ta ki durum en dıştaki emilim noktasına — sınırsız dış grubun (+) END'ine — düşene kadar. Bu işi Eşleştir'de yapmak, Em'in yineleme sonrası sayılarını zaten konsolide etmiş bağlamlara karşı karşılaştırma yapmasını sağlar.

2. Aşama — Em

Em geçişi bağlamları en yenisinden (kuyruktan) en eskisine (başa) doğru yürür. Tamamen emilebilir olan, devam eden her bağlam için, kendisini kapsayan daha eski, devam eden bir bağlam için geriye doğru tarar ve bulursa daha yenisini serbest bırakır. Bağlamlar oluşturma sırasıyla tutulduğundan ve her satır en fazla bir bağlam oluşturduğundan, "daha yeni" ve "daha eski" gerçekten "daha sonra başlamış" ve "daha önce başlamış" anlamına gelir.

absorb_contexts():
  for ctx kuyruktan geriye:
      if ctx bitti
         veya emilebilir olmayan herhangi bir durumu varsa:
          skip
      for older ctx.prev'den geriye:
          if older bitti
         veya emilebilir durumu yoksa:
              skip
          if covered(older, ctx):
              free(ctx)
              emilim uzunluğunu kaydet
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem karşılaştırma noktası değilse:
          return false
      if older'da şu özelliklere sahip durum yoksa:
            aynı elemIdx
            ve isAbsorbable
            ve older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Bundan iki mikro karar çıkar. İlki, kapsama kontrolünün, yeni bağlamdaki herhangi bir durum karşılaştırma noktası dışında bir yerdeyse hemen reddetmesidir — yargı dışı noktalarda karşılaştırma anlamlı bir karşılaştırma olmazdı.

İkincisi, her bağlamdaki asimetrik bayrak çiftidir: has-absorbable-state, "bu bağlam daha yeni bir bağlamı emebilir mi?" sorusuna yanıt verir ve monotondur (yalnızca durumlar öldükçe true→false gidebilir); oysa all-states-absorbable, "bu bağlam emilebilir mi?" sorusuna yanıt verir ve dinamiktir (emilebilir olmayan bir durum kaldırıldığında true'ya geri döner). Her iki bayrak da kapsama taraması başlamadan bile önce sabit zamanda kontrol edilir, dolayısıyla emilim tam maliyetini yalnızca emilme şansı gerçekten olan bağlamlarda öder.

3. Aşama — İlerle

İlerle "ıraksama" aşamasıdır: hayatta kalan her durum, her dal ya sonraki satırı bekleyen bir değişkene ya da FIN nöbetçisine ulaşana kadar epsilon geçişleri yoluyla genişletilir. Genişletme derinliğine önceliklidir ve kardeş dalların yürütüldüğü sıra, standardın tercih kuralının gerçekten yürürlüğe girmesini sağlayan şeydir — sözcüksel olarak ilk dal her zaman önce eklenir ve durum eklemedeki tekilleştirme adımı, eşdeğer sonraki eklemeleri sessizce atar.

advance(context, currentPos):
  tüm mevcut durumları çıkar;
  ctx.states'i sıfırdan yeniden inşa et
  her durum için sözlük sırasında:
      ziyaret edilmiş öğe bit haritasını temizle
      advance_state(state)   # DFS

      # Tercih: bir DFS FIN'e ulaştığında,
      # kalan durumlar daha az tercih edilir
      # ve atılabilir.
      if FIN'e ulaşıldı ve durumlar kaldıysa:
          kalanları serbest bırak
          break

advance_state(state):
  state.elemIdx üzerinden yürü,
  şunlardan özyinele:
    ALT dalları (sırayla),
    BEGIN (gruba gir; ayrıca min = 0 ise
           isteğe bağlı atlama yolu),
    END (geri döng / çıkış / hızlı ileri sarma —
         aşağıya bakın),
    FIN (matchEndRow'u kaydet,
         matchedState'i sakla ve bu adayın
         aralığındaki sonraki bağlamları
         buda — aşağıya bakın),
  karşılaşılan her değişkende durarak:
      durumu ctx.states'a ekle
      (elemIdx + counts ile tekilleştir)

FIN'e ulaşan bir durumu kaydetmek yalnızca aday eşleşmeyi yer imlemekten fazlasını yapar. AFTER MATCH SKIP PAST LAST ROW altında, raporlanabilir sonraki eşleşme kesinlikle mevcuttan ilerde başlamalıdır — bu yüzden bir aday kaydedildiği anda, başlangıç satırı adayın aralığına düşen sonraki her bağlam hemen budanır; FIN'e ulaşan bağlam açgözlü geri dönüş yoluyla daha uzun bir eşleşme aramaya devam ediyor olsa bile.

Bu budama güvenlidir, çünkü o arama nasıl biterse bitsin (daha uzun bir eşleşme adayın yerini alır veya aday kalır), budanan tüm bağlamlar, raporlanabilir sonraki eşleşmenin atlamak zorunda olduğu bir aralığın içinde başlamıştır ve bu nedenle kendi başlarına asla çıktı üretemezler.

Bu, iki FIN-zamanı budama adımından biridir — diğeri, bu bölümde daha önce İlerle'nin bir parçası olarak açıklanan, aynı bağlam içindeki sözcüksel olarak aşağı durumları atan adımdır.

En zor öğe başına mantık END işleyicisindedir. Bir grubun yineleme sayısı alt sınırın altındayken, çalışma zamanı geriye dönmek zorundadır; üst sınırda veya üzerindeyken, çıkmak zorundadır; arada, her iki seçenek de geçerlidir ve önce hangisinin denenmesine niceleyicinin açgözlülüğü karar verir:

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

  if count < elem.min:
      gövdeye geri döng
      if elem boş-döngülenebilir ise:
          # nullable gövde, §3.2'ye bakın
          ayrıca grubu sayım karşılanmış
          olarak terk eden bir hızlı ileri
          sarma durumu klonla
          (döngü korumasının aksi
           takdirde öldüreceği meşru
           eşleşmeleri kurtarır)

  elif count >= elem.max:
      bu derinlikteki sayıları sıfırla
      next üzerinden çık
      (END→END: dış END'in
       sayısını artır)

  else:
      # min <= count < max: dallan
      bir çıkış durumu kur
      (bu derinlikteki sayılar sıfırlanır)
      if greedy:
          önce döng, sonra çık
          # daha uzunu tercih et
      else (reluctant):
          önce çık
          if çıkış FIN'e ulaştıysa:
              döngüyü at
              # daha kısayı tercih et
          aksi takdirde ikinci olarak döng

Bir bağlama eklenen her durum, konumunu ve sayılarını mevcut durum listesiyle karşılaştıran bir tekilleştirme kontrolünden geçer. İlerle, dalları DFS sırasıyla işlediği için, herhangi bir seçeneğin ilk dalından gelen durum önce düşer — ve aynı konumu ve sayıları üreten herhangi bir sonraki dal eklemede reddedilir. Bu tam olarak §2.4'ün sözcüksel sıra kuralının istediği şeydir, ayrı bir geçiş olmadan çalışma zamanının dibinde gerçeklenir.

Boş-döngülenebilir gruplar

Çalışma zamanının etkisizleştirmesi gereken ince bir durum nullable grup'tur — gövdesinin her çocuğu kendi başına isteğe bağlı olduğundan gövdesi sıfır satırla eşleşebilen bir grup. (A?)*, (A? B?)+ ve (A | B*) gibi örüntülerin hepsi bu özelliğe sahiptir: veriye bağlı olarak, gövde hiç satır tüketmeden bir yinelemeyi tamamlayabilir. Bu prensipte iyidir, ama NFA'nın epsilon genişletmesi için gerçek bir tehlike yaratır. Gövde boş bir eşleşme üretirse, END öğesi BEGIN'e geri döner, gövde yine boş bir eşleşme üretir, BEGIN END'e döner ve böyle devam eder. Onu durduracak bir şey olmadan İlerle'nin DFS'i asla sonlanmazdı.

Çalışma zamanı bunu, her durumun DFS genişletmesinden önce temizlenen bir ziyaret edilmiş öğe bit haritası (örüntü öğesi başına bir bit) ile durdurur: aynı genişletme içinde herhangi bir öğe ikinci kez ziyaret edilir edilmez, o yol terk edilir. Döngü koruması koşulsuz ve ucuzdur, ama bir yan etkisi vardır — meşru boş yinelemeler yoluyla alt sınıra ulaşması gereken yolları da terk edebilir. Satır akışında hiçbir yerde A eşleşmeyen (A?){2,3}'ü ele alın:

istenen davranış:
  yin 1: A? sıfır satırla eşleşir
          → END, sayı = 1 (min altı)
  yin 2: A? sıfır satırla eşleşir
          → END, sayı = 2 (min karşılanır)
  sıfır uzunluklu eşleşmeyle çık

döngü koruması tek başına ne yapar:
  yin 1: A? atlandı → END, sayı = 1
          → BEGIN'e geri döng
  yin 2: BEGIN zaten ziyaret edildi
          → DFS iptal
  sayı min'e asla ulaşmaz
  → eşleşme başarısız (yanlış)

Düzeltme derleme zamanında kararlaştırılır ve çalışma zamanında uygulanır. Planlayıcı, gövdesi nullable olan bir grup gördüğünde, o grubun END öğesini boş-döngülenebilir olarak etiketler. Çalışma zamanında, END işleyicisi yineleme sayısı hâlâ alt sınırın altında olduğu için geriye dönmek üzereyken, boş-döngü etiketi normal geri döngü yolunun yanı sıra ek bir hızlı ileri sarma durumu klonlamasını söyler:

advance_end (sayı min altında):

  birincil yol:
    gövdeye geri döng
    (sonraki yinelemede gerçek,
     boş olmayan bir eşleşme için
     kapıyı açık tutar)

  if elem boş-döngülenebilir ise:
    hızlı ileri sarma yolu:
      bu derinliğin sayısını sıfırla
      grubu next üzerinden terk et,
      kalan gerekli yinelemeleri
      boş eşleşmeler olarak ele alarak

İki yol tamamlayıcı roller oynar. Birincil geri döngü, gövdenin daha sonra üreteceği gerçek eşleşmeleri olduğu durumu yakalayan şeydir — örneğin, (A?){2,3}'ün ardından A'nın yalnızca sonraki satırlarda eşleştiği veride, geri döngü ikinci ve üçüncü yinelemelerin boş olmayan eşleşmeler bulmasına olanak tanır. Hızlı ileri sarma, gövdenin hiçbir şey üretmediği durumu yakalayan şeydir: grubu tamamen terk ederek, "gerekli yinelemelerin geri kalanı boştur" diyerek döngü korumasını atlar ve eşleşmenin sıfır uzunluklu bir gövde ile başarılı olmasını sağlar. Her iki durum da bağlama eklenir; başarılı bir şekilde uzayan kazanır ve eklemedeki tekilleştirme kontrolü, her iki yolun payından fazla durum üretmesini önler.

Döngü korumasının ötesinde, bir başlangıç hilesi bağlamın en başında sıfır satırlı sonuçları belirsizlikten kurtarır. Her potansiyel başlangıç satırındaki bağlam oluşturma adımı, gerçek başlangıçtan bir satır önceki bir konumu kullanarak, herhangi bir satır tüketilmeden önce epsilon geçişleri yoluyla bir başlangıç ilerlemesi çalıştırır. Yalnızca epsilon geçişleri yoluyla — bir satır tüketmeden — FIN nöbetçisine ulaşan herhangi bir yol bu nedenle başlangıç konumundan daha küçük bir bitiş konumu üretir; bu negatif aralıklı koordinat, FIN'e gerçekten ulaşılıp ulaşılmadığıyla birleştiğinde, ayrı bir bayrak gerektirmeden boş bir eşleşme (uzunluk-0 eşleşme kabul edildi) ile eşleşmeyen bir başlangıç arasındaki farkı kodlar.

3.6 Durum uzayı nasıl sınırlı kalır

Çalışma zamanının doğrusallığı tek bir optimizasyonun sonucu değildir. Her biri satır başına döngünün farklı bir noktasında durum uzayı büyümesinin farklı bir nedenini yakalayan, katmanlı bir budama kuralları kümesinin kümülatif etkisidir. Bazıları derleme zamanında kararlaştırılır ve çalışma zamanında yalnızca başvurulur; bazıları dinamik olarak ateşlenir. Bazıları tek tek durumları öldürür; bazıları tüm bağlamları öldürür. Yukarıdaki bölümler bunların her birini bağlamında tanıttı; aşağıdaki tablo bunları tek bir sayfaya koyar.

Başarısız yüklem Eşleştir

DEFINE'ı geçerli satırda yanlış değerlendirilen değişken durumları — ölü dallar.

Satır içi END zinciri ilerlemesi Eşleştir

Max sayısına ulaşmış ve aksi takdirde durumu yineleme ortasında bırakacak değişkenler; emilim doğru noktada karşılaştırma yapabilsin diye sabit uzunluklu grup sonları boyunca ilerletilir.

Bağlam emilimi Em

Her durumu daha eski bir bağlamın daha yüksek sayılı bir durumuyla kapsanan daha yeni bağlamlar — kavramsal kural için §2.5'e, derleme zamanı uygunluğu için §3.2'ye, çift başına kontrol için §3.5'e bakın.

Durum tekilleştirme İlerle

Aynı konumda aynı sayılarla biten farklı DFS dalları aracılığıyla ulaşılan durumlar — yalnızca ilki (sözcüksel olarak en erken) hayatta kalır; sonraki eşdeğerler sessizce atılır; bu aynı zamanda tercihin nasıl uygulandığıdır (§2.4).

FIN erken sonlandırma (bağlam içinde) İlerle

Bir dal FIN'e ulaştığında DFS kuyruğunda hâlâ bekleyen durumlar — sözcüksel sıraya göre, kalan tüm durumlar daha az tercih edilir ve hemen atılabilir.

Aday eşleşme budama (bağlamlar arasında) FIN'de

Başlangıç satırı aday eşleşmenin aralığına düşen diğer bağlamlar — FIN'e ulaşan bağlam daha uzun bir eşleşme aramaya devam edebilir (açgözlü geri dönüş), ancak AFTER MATCH SKIP PAST LAST ROW altında, adayın aralığındaki herhangi bir bağlam, o aramanın nasıl bittiğinden bağımsız olarak artık raporlanabilir bir çıktı üretemez ve hemen budanır.

Döngü koruması İlerle

Aynı DFS içinde aynı örüntü öğesini yeniden ziyaret eden epsilon genişletmeleri — aksi takdirde nullable gruplarda sonsuza kadar döngü oluştururdu.

Boş-döngü hızlı ileri sarma İlerle

Döngü korumasının nullable gruplarda öldüreceği meşru boş yineleme eşleşmeleri — kalan gerekli yinelemeler boş ilan edilerek grubu terk ederek döngüyü atlar.

Sınırlı çerçeve kesimi Eşleştir

Eşleşmesi kullanıcının belirttiği çerçeve üst sınırına ulaşan bağlamlar — onu aşmamaları için uyumsuzluğa zorlanır (§3.4).

Girişleri aşama rozetlerine göre okumak bir bağlamın yaşam süresini izler: budama, üç ana aşama (Eşleştir, Em, İlerle) boyunca her satırda ve eşleşme tamamlandığında (FIN'de) yine ateşlenir. Açıklamaları okumak ise kuralları hedefledikleri şeye göre gruplar: ölü dallar, gereksiz bağlamlar, eşdeğer durumlar, sonsuz döngüler ve kullanıcı tarafından dayatılan sınırların ötesine genişleme.

Hiçbir tek kural tek başına yeterli olmazdı. Döngü koruması tek başına nullable gruplarda meşru eşleşmeleri öldürürdü; boş-döngü hızlı ileri sarma tek başına sonsuz epsilon döngülerini durdurmazdı; emilim tek başına DEFINE eşleşme başlangıcına başvurduğunda aşırı konsolide ederdi; tekilleştirme tek başına gereksiz bağlamları değil, yalnızca gereksiz durumları kaldırırdı. Çalışma zamanı önemli olan durumlarda doğrusal kalır — 100.000 satırda PATTERN (A+ B+ C+ D), posterin ③ paneli kıyaslaması — yalnızca her katman, üstündeki katmanların kaçırdığını yakaladığı için.

3.7 EXPLAIN çıktısı

RPR'lı bir sorguda EXPLAIN ANALYZE, sıradan pencere işlevleri için bulunmayan NFA düzeyinde istatistikleri ortaya çıkarır. Pencere operatörünün yanında üç sayaç grubu yayılır:

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
  (yalnızca sorgu FIRST,
   PREV(FIRST(...)) veya NEXT(FIRST(...))
   kullandığında)

Peak ve total, çalışma zamanının doğrudan ölçümüdür: aynı anda kaç durumun canlı olduğunu, sorgunun yaşam süresi boyunca kaçının oluşturulduğunu ve tekilleştirme tarafından kaçının birleştirildiğini gösterir. Eşleşme uzunluğu histogramları dört sonucu ayırır — başarılı eşleşmeler, başarısız eşleşme denemeleri, emilen bağlamlar ve değerlendirilmeden budanan (atlanan) bağlamlar — ve bunları min/max/avg ile raporlamak performans patolojilerini bir bakışta görünür kılar: sağlıklı bir çalışma, bağlamların çoğunu eşleşmiş veya emilmiş olarak gösterir; uyumsuz uzunluklar küçüktür.

İki Nav Mark sayacı, §3.3'ün derleme zamanında türettiği tuplestore tutma bütçesini raporlar. Lookback, PREV, ofsetli LAST ve iç LAST'lı bileşik biçimlerdeki en derin geriye uzanmadır; Lookahead, en eski canlı bağlamın eşleşme başlangıcından ölçülen, FIRST ve iç FIRST'li bileşik biçimler tarafından katkılanan en derin ileri (veya negatifse geriye) uzanmadır.

Her sayaç, ofset sabit olduğunda sabit bir tamsayı olarak; her çağrıda değerlendirilmesi gereken sabit olmayan bir ifade olduğunda "runtime"; çalışma zamanı sınırsız bir bütçe gerektirdiğinde "retain all" olarak yazdırılır. Lookahead yalnızca sorgu gerçekten eşleşme başlangıcına göreli gezinme kullandığında yayılır.

Bu sayaçlar birlikte, arka uca gdb iliştirmeden RPR performansını ayıklamayı mümkün kılar.

Sayaçların ötesinde, EXPLAIN ayrıca orijinal PATTERN ve DEFINE yan tümcelerini gönülsüz niceleyiciler, grup tekrarı ve AFTER MATCH SKIP seçeneği dahil sadık bir biçimde yeniden üretir. Gerçekleme, pg_dump ve pg_upgrade'in RPR nesnelerini anlamsal kayma olmadan koruyabilmesi için bu gidiş-dönüşü kararlı kılmak için belli bir çaba harcar — rpr_explain altındaki regresyon paketi bunu durum durum doğrular (bkz. §4).

§4. Testler — Kapsam Haritası

Yama, §3'te açıklanan her katmanı birlikte sınayan beş regresyon paketiyle birlikte gelir — kabaca 13.000 satır SQL, her paket farklı bir kaygıya odaklıdır. Bölüm bilinçlidir: ayrıştırıcı kaygılarını, çalışma zamanı doğruluğunu, planlayıcı etkileşimlerini ve çıktı biçimlendirmesini ayrı dosyalarda tutmak, başarısızlıkları konumlandırmayı kolaylaştırır ve bir katmandaki ilgisiz bir değişikliğin başka bir katmandaki testleri yanlışlıkla geçersiz kılmasını önler. Beş paket şunlardır:

rpr

Uçtan uca sorgu anlamları — sentetik hisse senedi verisinde gerçekçi pencere senaryoları (V şekli, W şekli, ardışık yükselişler, tersine çevirmeler).

rpr_base

Ayrıştırıcı katmanı — anahtar sözcük kabulü, sözdizimi biçimleri, niceleyiciler, gezinme ayrıştırma, hata mesajları ve pg_dump/pg_upgrade gidiş-dönüş kararlılığı.

rpr_nfa

NFA çalışma zamanı — üç aşamalı döngü, her emilebilir biçimde emilim ve bağlam yaşam döngüsü uç durumları.

rpr_explain

Çıktı biçimlendirmesi — NFA istatistikleri, örüntü deparse, tanımlayıcı tırnaklama, yeniden yükleme boyunca biçim kararlılığı.

rpr_integration

Planlayıcı etkileşimleri — ilgisiz pencere optimizasyonlarının RPR anlamlarını bozmasını önleyen korumalar.

4.1 rpr — uçtan uca senaryolar

Senaryo paketi, test setinin halka açık yüzüdür: yaklaşık 1.600 satırlık sentetik bir hisse fiyatı veri kümesi kullanır ve buna karşı gerçekçi sorgular çalıştırır — V şekli toparlanma, W şekli (çift dip), ardışık yükselişler ve düşüşler, tersine çevirme örüntüleri, çoklu sembol bölümleri. Girdi ve çıktıların kullanıcının gerçekten yazabileceği sorgular gibi okunduğu tek pakettir; diğerleri bilinçli olarak indirgemecidir, her seferinde tek bir katmana odaklanır.

Bu sorgular her katmanı (ayrıştırıcı, planlayıcı, yürütücü, EXPLAIN) birleştirdiğinden, rpr'daki tek bir başarısızlık size hatanın nerede olduğunu nadiren söyler. Takip eden dört paket biseksiyondur: rpr'da bir başarısızlık artı geçen bir rpr_base ayrıştırıcıyı eler; artı geçen bir rpr_nfa bunu senaryoya özgü veri biçimlerine daraltır; artı geçen bir rpr_integration planlayıcı müdahalesini eler; herhangi bir deparse kayması rpr_explain'de ortaya çıkar.

4.2 rpr_base — ayrıştırıcı yüzeyi

Temel paket en büyüğüdür ve bir nedenle en büyüğüdür: §1.2'deki her yasal sözdizimi parçasının gerçekten ayrıştığını, §1.3'teki her yasadışı parçanın faydalı bir hatayla reddedildiğini ve kabul edilen her biçimin bir serileştirme gidiş-dönüşünden sağ çıktığını kanıtlamaktan sorumludur. Çoğu, uzun gerçekçi sorgular yerine küçük odaklı parçalar olarak biçimlendirilmiştir — sözdizimsel özellik başına bir tane — çünkü amaç senaryo gerçekçiliği değil kapsamadır.

Serileştirme testleri özel ilgiyi hak eder. RPR nesneleri (görünümler, somutlaştırılmış görünümler, pg_dump çıktısı), bir niceleyicideki gönülsüz bayrak veya bileşik bir gezinme ifadesinin tam biçimi gibi incelikler dahil, anlamsal kayma olmadan katalog gösteriminden gidiş-dönüş yapmalıdır. Çevredeki regresyon altyapısının onları alıp pg_dump ve pg_upgrade'ı bunlara karşı çalıştırabilmesi için, küçük bir serileştirmeye özgü nesne kümesi (rpr_serial_v* görünümleri ve onların destek tabloları) çalışma sonunda bilinçli olarak yerinde bırakılır. Test iskelesinin geri kalanı her zamanki gibi düşürülür. Bu yolla yakalanan hatalar (deparse ve yeniden ayrıştırma boyunca kaybolan bir gönülsüz bayrak gibi) yalnızca gidiş-dönüş uçtan uca çalıştırıldığında ortaya çıkar.

4.3 rpr_nfa — çalışma zamanı motoru

Bu, §3.5 ve §3.6'da açıklanan her mekanizmayı sınayan pakettir. Testleri tutarlı bir desen izler: satırları her satırda hangi DEFINE değişkenlerinin eşleştiğini bildiren açık Boole dizileri olan bir girdi tablosu, belirli bir çalışma zamanı davranışını araştıran bir örüntüyle eşleştirilir. Boole dizisi deyimi, çalışma zamanı testini DEFINE değerlendirme mekanizmasından ayırır — test edilen şey "DEFINE ifade değerlendiricisi bu Boole değerlerini doğru hesaplıyor mu?" değil, "bu değişkenler burada eşleştiğine göre, NFA döngüsü beklenen eşleşme aralığını üretiyor mu?" sorusudur. DEFINE değerlendiricisi başka yerde test edilir (ayrıştırma için rpr_base, uçtan uca davranış için rpr).

Tipik bir test düzeneği şöyle görünür — her girdinin o satırda hangi DEFINE değişkenlerinin ateşlendiğini söylediği değişken adı dizilerinden bir sütun ve DEFINE yan tümceleri o adları doğrudan test eden bir örüntü:

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));

Dizi sütununu aşağı doğru okumak, test senaryosunu doğrudan okumaktır. 2. ve 3. satırlar her iki adı da taşır — A ve B her ikisi de orada ateşlenir, dolayısıyla NFA'nın A bacağından B bacağına nereden geçileceği konusunda gerçek bir seçimi vardır. Beklenen eşleşme (1–3 satırlarında A'yı 4. satırda B'nin izlemesi, standardın açgözlü tercih kuralı altında) yalnızca o bayraklarla sabittir, burada sonucu olan hiçbir ifade değerlendirmesi yoktur — = ANY, dizi sütununu DEFINE'a açan basit katmandır, testin sınadığı şey değil. Aynı senaryoyu sayısal bir yüklemle (price > PREV(price) vb.) yazmak NFA testini yüklem değerlendiricisinin davranışıyla iç içe geçirirdi; dizi deyimi ikisini temiz bir şekilde ayrı tutar ve buradaki bir başarısızlık doğrudan NFA döngüsüne işaret eder.

Emilim kapsamı özellikle kapsamlıdır, çünkü emilim, devreye girmemesi gereken yerde devreye girerse sessizce yanlış yanıtlar üretme olasılığı en yüksek olan optimizasyondur. Testler §3.2'nin durum analizinden her biçimi kapsar:

• basit sınırsız değişken (A+) — kanonik N-1 çökmesi;
• sabit uzunluklu gruplar ((A B)+, (A B{2})+, üç düzey iç içe ((A (B C){2}){2})+);
• sabit son ekli önde gelen sınırsız değişken (A+ B) — yalnızca önde gelen A+ emilim bayrakları taşır, son ek taşımaz;
• bir seçenek içinde dal başına emilim (B+ C | B+ D);
• birden çok sınırsız değişken (A+ B+) — yalnızca önde geleni emilebilir;
• gönülsüz niceleyiciler (A+?) — emilimden hariç tutulduğu doğrulandı;
• önde gelmeyen sınırsız (A B+) — hariç tutulduğu doğrulandı.

Emilimin ötesinde, paket bağlam yaşam döngüsünü kapsar: AFTER MATCH SKIP TO NEXT ROW altında örtüşen bağlamlar, akış ortasında başarısız bağlam temizliği, eksik bağlamların bölüm sonu kesinleştirilmesi ve baş bağlamda zaten bir aday eşleşme kaydedildikten sonra karşılaşılan bağlamlar. Bunların her biri §3.6'daki belirli bir budama kuralına eşlenir ve testler kural yanlış ateşlerse (ya gereksiz bağlamları canlı bırakarak ya da çıktı üretmesi gereken bir bağlamı öldürerek) yüksek sesle başarısız olacak şekilde yazılmıştır.

4.4 rpr_explain — çıktı kararlılığı

EXPLAIN çıktısı, kullanıcıya yönelik sözleşmenin parçasıdır — üçüncü taraf araçlar (psql otomatik tamamlama, izleme panoları, log toplayıcıları) bunu ayrıştırır ve kozmetik gibi görünen değişiklikler bunları bozabilir. rpr_explain paketi üç şeyi doğrular:

• NFA sayaçları doğru yerde görünür — WindowAgg başına istatistikler (peak/total/merged states, peak/total/pruned contexts, matched/mismatched/absorbed/skipped için uzunluk histogramları, Nav Mark Lookback ve — eşleşme başlangıcına göreli gezinme kullanıldığında — Nav Mark Lookahead) EXPLAIN ANALYZE altında belgelenmiş etiketlerle görünür.
• Örüntüler doğru deparse edilir — her niceleyici biçimi, gönülsüz varyantlar ve sınırlı biçimler dahil; her seçenek; her grup; her AFTER MATCH SKIP biçimi; INITIAL; ofsetli gezinme çağrıları; bileşik gezinme. Deparse edilmiş metin, ayrıştırıcıdan değişmeden gidiş-dönüş yapmalıdır.
• Tanımlayıcı tırnaklama doğrudur — örüntü değişkenleri ve DEFINE ifadeleri sıradan SQL tanımlayıcılarıyla aynı tırnaklama kurallarıyla yayılır, dolayısıyla olağandışı değişken adları pg_dump çıktısını bozmaz.

rpr_base gibi, bu paket de nesnelerini çalışma sonunda bilinçli olarak yerinde bırakır; böylece pg_dump ve pg_upgrade kapsamı, açıklama tarafındaki yapıtlara da uzanır.

4.5 rpr_integration — planlayıcı etkileşimleri

PostgreSQL'in planlayıcısı pencere sorguları üzerinde çalışan birçok optimizasyona sahiptir — çerçeve kanonikleştirme, run-condition pushdown, özdeş pencere tekilleştirme, kullanılmayan çıktı projeksiyonu, hareketli toplam ters geçişleri — ve bunların her biri RPR akılda tutulmadan tasarlanmıştır. Bir pencerenin PATTERN yan tümcesi olduğunda çoğunun uygulanması güvensizdir: çerçeve eşleşme sözleşmesinin parçasıdır, eşleşmiş çıktı artık herhangi bariz bir biçimde monoton değildir ve aynı belirtime ama farklı DEFINE'lara sahip iki pencere gerçekten farklı sonuçlar üretir. Entegrasyon paketi, bu optimizasyonların her birinin RPR pencereleri için doğru biçimde devre dışı bırakıldığını veya atlandığını doğrular:

Çerçeve kanonikleştirme

Planlayıcı normalde ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING'i monoton toplamlar için ROWS UNBOUNDED PRECEDING'e yeniden yazar. RPR'nin çerçevesi bir toplama penceresi değil, eşleşme aralığıdır ve aynen kalmalıdır.

Run-condition pushdown

Bir pencere işlevinin çıktısı üzerindeki monoton bir WHERE filtresi normalde pencere operatörüne durdurma koşulu olarak itilebilir. RPR için bu örüntü eşleştirmesini erkenden sonlandırır, muhtemelen genişleme ortasında eşleşmeleri keser.

Pencere tekilleştirme (RPR vs RPR olmayan)

Aynı ORDER BY ve çerçeveye sahip iki pencere normalde tek olarak birleştirilir. Bir RPR penceresi ve bir RPR olmayan pencere asla durum paylaşamaz, çünkü RPR tarafı eşleşme sonuçları taşır.

Pencere tekilleştirme (farklı DEFINE)

Aynı PATTERN'a ama farklı DEFINE yan tümcelerine sahip iki RPR penceresi farklı eşleşmeler üretir ve yapısal biçimleri özdeş olsa bile farklı kalmalıdır.

Kullanılmayan çıktı projeksiyonu

Çevredeki sorgu pencerenin satır başına çıktısını hiç okumasa bile, RPR penceresi kaldırılamaz: örüntü eşleştiricinin yan etkileri (hangi satırların hangi eşleşmenin içinde olduğu) plandaki başka yerlerde indirgenmiş çerçeve hesaplamalarını besler.

Hareketli toplam ters geçişleri

Bir ters geçiş işlevine sahip pencere toplamları normalde çerçeve hareket ettikçe artımlı olarak değerlendirilebilir. RPR'nin indirgenmiş çerçevesi bir kayan pencere değildir; ters geçiş yolu yanlış sonuçlar üretirdi.

Bu testlerdeki desen aynıdır: her biri optimizasyonu tetikleyen RPR olmayan bir taban çizgisi sağlar (ve EXPLAIN'in bunun uygulandığını gösterdiğini doğrular), ardından yapısal olarak benzer biçimde bir RPR sorgusu çalıştırır ve optimizasyonun uygulanmadığını doğrular. İki yarısı birlikte planlayıcıdaki korumanın gerçek doğrulama olmadan her sorguyu onaylamak yerine gerçek iş yaptığını kanıtlar.

Bu paket §3.4'ün kısa olmasının da nedenidir. "Eşleşme sınırları" mekanizmaları — indirgenmiş çerçeve, SKIP, INITIAL, sınırlı çerçeve kesimi — operasyonel olarak başka yerde test edilir; rpr_integration'ın doğruladığı şey, başka hiçbir optimize edici aşamanın bunlara giderken müdahale etmediğidir. Geçen bir rpr_integration, paketlerin geri kalanının girdilerinin yürütücüye dokunulmadan ulaştığına güvenmesini sağlayan şeydir.