Row Pattern Recognition Szczegółowa analiza

§1. Standard, podzbiór i otwarte pytania

1.1 Zakres standardu

Row Pattern Recognition zostało wprowadzone do SQL przez ISO/IEC 9075-2:2016 i opisane w towarzyszącym dokumencie ISO/IEC 19075-5:2021 (część 5, „Row Pattern Recognition").

Standard definiuje dwie powierzchnie dla tej samej leżącej u podstaw maszynerii. Cecha R010 umieszcza klauzulę MATCH_RECOGNIZE na liście FROM, by wytworzyć tabelę pochodną; cecha R020 osadza tę samą logikę wzorców w specyfikacji WINDOW, by wytworzyć wynik funkcji okna. Obie powierzchnie dzielą większość składni i całą semantykę, ale stanowią funkcjonalnie odrębne punkty wejścia — baza danych może zaimplementować jedną lub obie.

Omawiana tu seria łatek implementuje wyłącznie podzbiór R020; postać klauzuli tabelarycznej została celowo pominięta.

Powierzchnia R020 jest niewielka, lecz ekspresyjna. Zapytanie dołącza wzorzec do okna, dodając trzy klauzule wewnątrz specyfikacji okna: PATTERN opisuje wyrażenie regularne nad nazwanymi zmiennymi wzorca, DEFINE dostarcza predykat logiczny identyfikujący każdą zmienną, a AFTER MATCH SKIP kontroluje sposób pozycjonowania kolejnych dopasowań w obrębie partycji.

Opcjonalne MEASURES, SUBSET, INITIAL/SEEK oraz pomocnicza funkcja CLASSIFIER() dopełniają funkcjonalność. (Standardowa funkcja MATCH_NUMBER() należy wyłącznie do powierzchni R010 — 19075-5 §6.3.3 (6) wyraźnie wyklucza ją z R020.)

Łatka pokrywa tyle z tego słownika, by umożliwić działanie nietrywialnych zapytań, lecz pomija kilka konstrukcji, których implementacja zależy od infrastruktury jeszcze nie zbudowanej.

Pozostała część tej sekcji dzieli słownik standardu na to, co łatka już wspiera, oraz to, co celowo pozostawia na później. Poniższe listy odzwierciedlają bieżący stan serii łatek.

1.2 Zaimplementowane cechy

Zaimplementowany słownik wystarcza do wyrażenia kanonicznych wzorców o kształcie V, W oraz wzorców odwrócenia, które są pierwotną motywacją row pattern recognition. Obejmuje też każdy standardowy kwantyfikator — w tym wszystkie siedem wariantów leniwych *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — oraz cztery prymitywy nawigacji, które warunki DEFINE potrzebują do porównywania sąsiednich wierszy.

Klauzula PATTERN

Definiuje wzorzec wierszy wewnątrz specyfikacji okna.

Regex: + * ? |

Standardowe kwantyfikatory i alternatywa.

Regex: ( ) grupowanie

Podwzorce w nawiasach.

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

Ograniczone liczby powtórzeń.

Leniwe *? +? ?? {n}? {n,}? {,m}? {n,m}?

Wszystkich siedem wariantów leniwych (nieograbiających) zdefiniowanych w standardzie (wykluczone z optymalizacji absorpcji).

Klauzula DEFINE

Warunki logiczne identyfikujące każdą zmienną wzorca.

Uniwersalna zmienna wzorca wiersza

Nieskwalifikowane odwołania do kolumn w DEFINE (np. samo Price) odnoszą się do bieżącego wiersza, zgodnie z 19075-5 §4.10/§4.16.

PREV, NEXT (z przesunięciem)

Sięgają do n wierszy przed/po wierszu bieżącym (domyślnie 1); wewnętrzny argument to dowolne wyrażenie wartościowe ewaluowane w wierszu, do którego nastąpiła nawigacja.

FIRST, LAST (z przesunięciem)

Sięgają do wiersza relatywnego względem dopasowania; FIRST(expr, n) celuje w wiersz n po początku dopasowania, LAST(expr, n) — w wiersz n przed ostatnim wierszem dopasowania.

Nawigacja złożona (cztery formy)

Zewnętrzny krok PREV/NEXT nałożony na wewnętrzny FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — zarówno krok wewnętrzny, jak i zewnętrzny przyjmują własne przesunięcie.

INITIAL

Dopasowania wzorca muszą rozpoczynać się od wiersza bieżącego (domyślnie).

AFTER MATCH SKIP PAST LAST ROW

Domyślny tryb pominięcia; kwalifikuje się do absorpcji kontekstu.

AFTER MATCH SKIP TO NEXT ROW

Pozwala na nakładające się dopasowania; wyłącza absorpcję.

1.3 Niezaimplementowane

Cechy, które pozostają niezaimplementowane, dzielą się na trzy luźne grupy. Pierwsza — i zdecydowanie największa — to rodzina konstrukcji skupionych wokół MEASURES: sama klauzula MEASURES, SUBSET, CLASSIFIER(), kwalifikowane wzorcem odwołania do kolumn, takie jak B.price, oraz nawigacja kwalifikowana wzorcem, np. LAST(B.price) czy PREV(B.price).

Nie są to niezależne luki, lecz raczej różne ujęcia jednego brakującego elementu: executor musiałby zachowywać historię pojedynczego dopasowania — zapis, dla każdego wiersza w dopasowaniu, do której zmiennej wzorca został on przypisany — a żadna z tych konstrukcji nie ma sensownej definicji bez tego. CLASSIFIER() odczytuje nazwę zmiennej z tego zapisu; B.price odczytuje kolumnę price wierszy, których wpis w zapisie wskazuje B; LAST(B.price) przechodzi ten sam zestaw wierszy i wybiera ostatni; SUBSET U = (A, B) definiuje zmienną wirtualną agregującą po obu kubełkach; a MEASURES ewaluuje wyrażenia takie jak AVG(U.Price) dokładnie z użyciem tej agregacji.

Bieżący executor ewaluuje predykaty DEFINE wiersz po wierszu, lecz nie zapisuje wynikowych przypisań zmiennych nigdzie — nie ma czego zapytać później. Budowa infrastruktury historii jest zatem warunkiem koniecznym dla całej grupy; poszczególne cechy stają się drobnymi rzutami, gdy tylko zapisy istnieją.

Druga grupa dotyczy alternatywnych celów pominięcia: AFTER MATCH SKIP TO etykieta, AFTER MATCH SKIP TO FIRST zmienna oraz AFTER MATCH SKIP TO LAST zmienna. One również zależą od historii dopasowania, ponieważ executor musi być w stanie wskazać konkretny etykietowany wiersz wewnątrz ostatniego dopasowania.

Pozostałe elementy stanowią heterogeniczny ogon: słowo kluczowe SEEK (alternatywa dla INITIAL), pusty wzorzec (), forma wykluczenia {- … -} oraz operator PERMUTE niewrażliwy na kolejność.

MEASURES

Nazwane wyrażenia wyjściowe na dopasowanie, np. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; w R020 udostępniane przez OVER jak funkcja okna. Przyjmuje słowa kluczowe FINAL / RUNNING (19075-5 §5.4), które w R020 sprowadzają się do tej samej wartości, ponieważ miary są zawsze ewaluowane na ostatnim wierszu dopasowania (19075-5 §6.9 (3)).

SUBSET

Nazwane sumy zmiennych wzorca, np. SUBSET U = (A, B, C). Użyteczne wszędzie tam, gdzie można odwołać się do zmiennej wzorca — MEASURES, kwalifikowane wzorcem odwołania w DEFINE, CLASSIFIER(U) — z których wszystkie wymagają historii dopasowania.

CLASSIFIER()

Zwraca, jako która zmienna wzorca dany wiersz został dopasowany. Zdefiniowane zarówno dla DEFINE, jak i MEASURES (19075-5 §5.9); odpowiedź w dowolnym wierszu to nazwa zmiennej zapisana w historii dopasowania dla tego wiersza.

Odwołanie do kolumny kwalifikowane wzorcem

Samo B.price w DEFINE lub MEASURES — wartość kolumny z wiersza odwzorowanego jako nazwana zmienna.

Nawigacja kwalifikowana wzorcem

Ograniczenie nawigacji do wierszy dopasowanych jako nazwana zmienna, np. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Dopasowanie może zaczynać się w dowolnym miejscu okna (w odróżnieniu od INITIAL).

AFTER MATCH SKIP TO etykieta

Pominięcie do etykietowanego wiersza.

AFTER MATCH SKIP TO FIRST zmienna

Pominięcie do pierwszego wiersza dopasowanego jako nazwana zmienna.

AFTER MATCH SKIP TO LAST zmienna

Pominięcie do ostatniego wiersza dopasowanego jako nazwana zmienna.

Regex: {- -}

Wykluczenie — usuwa dopasowane wiersze z wyjścia danego dopasowania.

Regex: ()

Pusty wzorzec — dopasowuje pustą sekwencję.

PERMUTE(...)

Dopasowywanie niewrażliwe na kolejność dla wymienionych zmiennych.

Funkcje agregujące w DEFINE

Agregaty takie jak SUM, AVG, COUNT nie są dozwolone w predykatach DEFINE. Standard dopuszcza je jako agregaty bieżące po częściowym dopasowaniu (ewaluacja per wiersz względem wierszy już odwzorowanych na zmienną), co zależy od tej samej historii dopasowania, której wymagają MEASURES/CLASSIFIER().

Cztery dalsze punkty warte odnotowania tutaj, ponieważ łatwo pomylić je z pominięciami.

Pierwszy: kotwice wzorca ^ i $ nie są dozwolone z RPR w klauzuli WINDOW przez sam standard (19075-5 §6.13: „kotwice (^ i $) nie są dozwolone w dopasowywaniu wzorca wierszy w oknach"; z bazową definicją w 19075-5 §4.14.1); ich brak jest zgodnością, nie luką.

Drugi: MATCH_NUMBER() jest również wykluczone z R020 przez standard (19075-5 §6.3.3 (6) i 19075-5 §6.9 (1)) — należy wyłącznie do powierzchni R010, a jego brak tutaj również jest zgodnością, nie brakującą cechą.

Trzeci: zbiór strukturalnych zakazów, jakie standard nakłada na R020 (19075-5 §6.17): row pattern recognition nie może być zagnieżdżone w innym row pattern recognition; MEASURES i DEFINE nie mogą zawierać odwołań zewnętrznych; podzapytania wewnątrz MEASURES lub DEFINE nie mogą odwoływać się do zmiennych wzorca wierszy; a RPR nie może być użyte wewnątrz zapytania rekurencyjnego.

Czwarty: samo MATCH_RECOGNIZE — cecha R010, powierzchnia klauzuli tabelarycznej tej samej maszynerii — pozostaje poza zakresem tej łatki. Pytanie, czy PostgreSQL ostatecznie doda R010, należy do przyszłej serii, a nie jest miarą tej.

§2. Przykłady — jak to faktycznie działa

Przykłady w tej sekcji budowane są przyrostowo. Zaczynamy od pojęciowego powodu, dla którego dopasowywanie wzorca wierszy jest istotnie różne od dopasowywania wzorca łańcuchów, następnie wprowadzamy cztery funkcje nawigacji, które czynią warunki DEFINE interesującymi, a na końcu prowadzimy przez trzy pełne ślady: pojedyncze dopasowanie (ruch NFA), absorpcję kontekstu w łatwym przypadku i przypadek, w którym absorpcja staje się niebezpieczna.

Wewnętrzny mechanizm, który czyni nawigację tanią — wymiana krotek na pojedynczym slocie — należy do projektu executora i omawiany jest w następnej sekcji, nie tutaj.

2.1 Dlaczego wzorce wierszy różnią się od wzorców tekstowych

Tekstowe wyrażenie regularne dopasowuje strumień znaków i w każdej pozycji jest dokładnie jeden symbol do rozważenia. Pytanie wykonawcze — „czy bieżący symbol równa się 'A'?" — ma jedną odpowiedź tak/nie. Automaty z nawrotami to wykorzystują: na znak ocaleje co najwyżej jedna gałąź, a koszt niejednoznaczności płaci się przez ponowne czytanie wejścia.

Wzorzec wierszy jest różny w fundamentalny sposób. Wiersz nie jest pojedynczym symbolem; jest krotką kolumn ewaluowaną względem zbioru predykatów logicznych — warunków DEFINE. Dwa predykaty mogą być prawdziwe w tym samym wierszu jednocześnie i nic w standardzie nie mówi, że muszą się wzajemnie wykluczać. Rozważmy:

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

Wiersz z price = 150, volume = 2000 spełnia zarówno A, jak i B, ale nie C. Mechanizm dopasowywania wzorca nie może zredukować tego do pojedynczego stanu — dwie zmienne wzorca są aktywne i każdy element wzorca, który nazywa którąkolwiek z nich, może przejść dalej. NFA musi zatem nieść wiele równoczesnych stanów na wiersz partycji, nie jeden.

Ta jedna obserwacja napędza pozostałą część architektury. Stan wykonania to lista kontekstów, każdy kontekst to lista stanów, a w każdym wierszu runtime pyta każdy stan: „mając zmienne prawdziwe tutaj, dokąd mogę pójść?" Powstające w ten sposób rozwidlenia są powodem, dla którego runtime potrzebuje kilku warstw przycinania — deduplikacji stanów w obrębie kontekstu, absorpcji między kontekstami oraz innych reguł omówionych w §3.6 — bez których liczba aktywnych stanów i kontekstów rośnie z partycją, a dopasowywanie wzorca staje się superliniowe.

2.2 Funkcje nawigacji

Warunki DEFINE odwołujące się wyłącznie do bieżącego wiersza są ograniczone; niemal każdy interesujący wzorzec potrzebuje porównać bieżący wiersz z jego sąsiadami lub z wierszami już zaakceptowanymi wcześniej w dopasowaniu. Standard udostępnia w tym celu cztery funkcje nawigacji, a łatka implementuje je wszystkie.

PREV(expr [, n])

Wiersz n wierszy przed bieżącym (domyślnie n = 1). Używane do porównań „dziś vs. wczoraj".

NEXT(expr [, n])

Wiersz n wierszy po bieżącym. Wgląd w przód; niespotykane w postaci okna, ponieważ okno jest monotoniczne.

FIRST(expr [, n])

n-ty dopasowany wiersz bieżącego dopasowania, licząc od początku. „Porównaj do wiersza, który rozpoczął to dopasowanie."

LAST(expr [, n])

n-ty ostatnio dopasowany wiersz. „Porównaj do najnowszego dopasowanego wiersza."

Cztery prymitywy się komponują: PREV i NEXT mogą obejmować wywołanie FIRST lub LAST, dając cztery formy złożone, których semantyka brzmi: „przejdź do wiersza relatywnego względem dopasowania, a następnie wykonaj krok o ustaloną odległość od niego." To pozwala wyrażeniu DEFINE odczytać na przykład wiersz bezpośrednio poprzedzający rozpoczęcie dopasowania.

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

Cofnij się o m wierszy od n-tego wiersza dopasowania (domyślnie m = 1). „Jaka była wartość tuż przed rozpoczęciem tego dopasowania?"

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

Przesuń się o m wierszy do przodu od n-tego wiersza dopasowania. Sięga dalej w głąb dopasowania bez zależności od bieżącego wiersza.

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

Cofnij się o m wierszy od n-tego ostatnio dopasowanego wiersza. „Porównaj do wiersza krótko przed najnowszym dopasowaniem."

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

Przesuń się o m wierszy do przodu od n-tego ostatnio dopasowanego wiersza.

Dwa praktyczne punkty warte zaznaczenia tutaj. Po pierwsze, nawigacja może być złożona: PREV(FIRST(price)) odczytuje wiersz bezpośrednio przed rozpoczęciem dopasowania i łatka to wspiera. Po drugie, nawigacja ma konsekwencje dla optymalizacji executora. PREV i NEXT są relatywne względem bieżącego wiersza i są zawsze bezpieczne; FIRST i warianty LAST z przesunięciem są relatywne względem granic dopasowania, co wchodzi w interakcję z absorpcją kontekstu i zmusza planer do utrzymywania przy życiu niektórych kontekstów, które w przeciwnym razie zostałyby odrzucone. Mechanizm tej interakcji jest tematem §2.6.

2.3 Przykład 1 — ruch NFA

SELECT company, tdate, price,
  first_value(price) OVER w AS start_price,
  last_value(price)  OVER w AS end_price
FROM stock
WINDOW w AS (
  PARTITION BY company ORDER BY tdate
  ROWS BETWEEN CURRENT ROW
       AND UNBOUNDED FOLLOWING
  AFTER MATCH SKIP PAST LAST ROW
  PATTERN (START UP+ DOWN+)
  DEFINE
    UP   AS price > PREV(price),
    DOWN AS price < PREV(price)
);

Wzorzec spłaszcza się do czterech elementów:

[0] START  quant 1..1   next → 1
[1] UP     quant 1..∞   next → 2
[2] DOWN   quant 1..∞   next → 3
[3] #FIN

Dla serii cen 100, 110, 120, 115, 108, 130:

Kluczowy punkt: w wierszu 3 wiersz spełnia zarówno START (zawsze prawdziwy), jak i DOWN, ale jedyny stan, który przeżył wiersz 2, znajduje się na gałęzi wyjścia DOWN, więc wykonywana jest wyłącznie tranzycja UP → DOWN. Wielostanowy charakter z §2.1 widoczny jest jako rozwidlenie przy każdym dopasowaniu UP (stan mógłby pozostać w UP+ lub przejść w stronę DOWN+). Greedy preferuje „pętlę raz jeszcze przed wyjściem", więc przy odpowiedniej ilości danych zapętlone gałęzie wydłużyłyby dopasowanie; tutaj zapętlony DOWN ginie w wierszu 5 (130 ≮ 108), a wcześniejszy kandydat FIN (wiersze 0–4) — wytworzony, gdy DOWN wyszedł w wierszu 4 — zostaje sfinalizowany jako dopasowanie.

Wynik zapytania wynika bezpośrednio z tego śladu. Zgodnie z semantyką RPR funkcje okna first_value(price) i last_value(price) są ewaluowane wyłącznie w wierszu, który rozpoczął dopasowanie — każdy inny wiersz w dopasowaniu daje NULL dla tych funkcji okna, ponieważ jego zredukowana ramka jest pusta. Wyjście dla naszych danych wygląda zatem jak tabela pokazana w prawym górnym panelu posteru:

Wiersz 0 jest początkiem dopasowania, więc jego ramka obejmuje wiersze 0–4, a funkcje okna raportują cenę otwarcia kształtu V ($100) oraz cenę dna ($108). Wiersze 1–4 znajdują się wewnątrz dopasowania, lecz nie są jego początkiem, więc otrzymują NULL. Wiersz 5 (cena $130) znajduje się poza jakimkolwiek dopasowaniem i również otrzymuje NULL.

2.4 Przykład 2 — alternatywa i porządek leksykalny

Postać (A | B) daje mechanizmowi dopasowania wybór: w dowolnym wierszu obie alternatywy testowane są niezależnie i dopasować się może dowolna ich liczba. To tutaj wielostanowy charakter z §2.1 staje się widoczny wewnątrz pojedynczego kontekstu — nie pomiędzy kontekstami (to jest absorpcja), lecz wzdłuż równoległych gałęzi, które executor eksploruje krokiem ramię w ramię.

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

Wyobraźmy sobie wiersz, w którym cena zarówno wzrosła, jak i przekroczyła 100 USD — zarówno UP, jak i HIGH są prawdziwe. Każda alternatywa rodzi własny stan: jeden chodzący po gałęzi UP, drugi po gałęzi HIGH. Postępują równolegle, dopóki DONE ich nie rozstrzygnie.

Obie gałęzie wytwarzają dopasowanie tej samej długości na tych samych wierszach, pozostawiając mechanizm dopasowania z dwiema kandydującymi ścieżkami — jedną oznaczoną UP, DONE i drugą oznaczoną HIGH, DONE. Standard rozstrzyga to przez porządek leksykalny: spośród alternatyw zapisanych w (UP | HIGH) wygrywa ta zapisana jako pierwsza, niezależnie od długości dopasowania. Ponieważ UP pojawia się przed HIGH, ocalałą ścieżką jest UP, DONE.

Porządek leksykalny czyni CLASSIFIER() dobrze zdefiniowanym, gdy zostanie ostatecznie zaimplementowany — pozwala runtime'owi powiedzieć użytkownikowi „ten wiersz dopasowany jest do UP, nie do HIGH", nawet gdy oba predykaty były prawdziwe. Porządek leksykalny jest pierwotną regułą dla alternatywy: gałąź lex-wcześniejsza wygrywa z lex-późniejszą, nawet jeśli ta druga wytworzyłaby dłuższe dopasowanie, a gałąź lex-późniejsza (być może krótsza) może wygrać, jeśli każda lex-wcześniejsza gałąź ginie przed osiągnięciem FIN. Długość greedy rozstrzygana jest wewnątrz pojedynczego kwantyfikatora — mając dwa zakończenia tej samej gałęzi alternatywy, kwantyfikator greedy preferuje więcej iteracji.

2.5 Przykład 3 — absorpcja kontekstu (ten sam los)

Najprostszym wzorcem demonstrującym absorpcję jest PATTERN (A+) z DEFINE A AS TRUE. Każdy wiersz dopasowuje się do A, a standard wymaga od mechanizmu dopasowania rozważenia każdego wiersza jako możliwego początku dopasowania. Naiwnie oznacza to N kontekstów dla N-wierszowej partycji. Weźmy partycję pięciowierszową (dowolne dane — predykat jest stałą true):

Pamięć rośnie z O(n) do O(1). Reguła absorpcji uzasadniająca odrzucenie jest prosta, gdy kwantyfikator jest nieograniczony:

Lewy dolny panel posteru („① Context Absorption") to dokładnie ta reguła zwizualizowana na pięciu wierszach.

W regule kryje się subtelny, lecz ważny punkt: odrzucenie jest bezpieczne, ponieważ predykat A AS TRUE ewaluuje się do tej samej wartości w każdym wierszu niezależnie od tego, który kontekst pyta. To samo dotyczy każdego predykatu odwołującego się wyłącznie do bieżącego wiersza lub stałego przesunięcia od niego — w tym PREV. Następny przykład przełącza się na konkretny tydzień cen z użyciem predykatu opartego na PREV, a §2.6 wykorzysta dokładnie ten sam tydzień, by uwypuklić symetrię między bezpieczną a niebezpieczną absorpcją:

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

Weźmy tydzień handlowy $100, $108, $112, $116, $110 od poniedziałku do piątku — cztery wzrosty, po których następuje nagły spadek. Załóżmy, że C1 startuje we wtorek (pierwszy dzień, w którym RISE się dopasowuje: $108 > $100), a executor spekulacyjnie śledzi również C2 startujący w środę. Warunek RISE każdego wiersza porównuje cenę wiersza z jego bezpośrednim poprzednikiem — fakt na poziomie partycji, nie kontekstu — więc oba konteksty są zmuszone obliczyć tę samą wartość Boolowską w każdym wierszu, który dzielą:

Historia łamie się w momencie, gdy predykat zaczyna zależeć od własnych granic każdego kontekstu — i o tym jest §2.6.

2.6 Przykład 4 — kiedy absorpcja staje się niebezpieczna

Załóżmy, że analityk chce znaleźć kolejne dni handlowe, w których akcja pozostała w granicach dziesięciu dolarów od dnia, w którym seria się zaczęła — rodzaj okna konsolidacji. Wzorzec i DEFINE wyglądają tak:

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

Warunek teraz porównuje cenę bieżącego wiersza z ceną na początku bieżącej serii. Dwie serie, które rozpoczęły się w różne dni, mają różne wartości FIRST(price), więc dwa stany w tym samym elemencie wzorca i z tym samym licznikiem nie są już wymienne: ich przyszłości zależą od granicy, którą absorpcja właśnie miała odrzucić.

Weźmy ten sam tydzień handlowy co w §2.5 — $100, $108, $112, $116, $110 od poniedziałku do piątku. Runtime znów utrzymuje dwie kandydujące serie naraz: C1 startujące w poniedziałek, C2 startujące we wtorek (każdy wiersz jest potencjalnym startem serii w STABLE+).

Przy absorpcji C2 zostałoby wchłonięte do C1 we wtorek — scalony kontekst trzyma tylko jeden pułap, więc odrębne ujęcie C2 (pułap $118, czterodniowa seria kończąca się dopiero w sobotę) nie jest już odzyskiwalne ze stanu wewnętrznego. C2 musi pozostać aktywne, ponieważ jest niezależnym kandydatem dopasowania, którego runtime może wciąż potrzebować: gdy dopasowanie C1 kończy się w środę, kolejna próba musi podjąć z wciąż trwającego C2, zamiast zaczynać od zera. Ilekroć predykat DEFINE niesie zależność od początku dopasowania, planer prewencyjnie wyłącza absorpcję.

(Gdy dopasowanie kontekstu wiodącego powiedzie się, konteksty, które wystartowały wewnątrz jego zaakceptowanego rozpięcia — przy domyślnym AFTER MATCH SKIP PAST LAST ROW — są po prostu odrzucane; utrzymywane są przy życiu wyłącznie po to, by runtime miał, do czego się wycofać, jeśli wiodące dopasowanie zawiedzie.)

Tabela zależności w prawym dolnym panelu posteru („② Navigation") podsumowuje, które formy nawigacji tworzą zależność od początku dopasowania:

Oba przykłady w §2.5 i §2.6 sprowadzają się do jednej reguły. Ten sam los czyni absorpcję bezpieczną: jeśli każdy kontekst w tym samym elemencie wzorca obliczy tę samą odpowiedź na każdy przyszły predykat, trzeba zachować tylko najstarszy. Różne losy czynią absorpcję niebezpieczną: gdy tylko predykaty rozgałęziają się na stan prywatny dla kontekstu — a to dokładnie czynią FIRST i LAST z przesunięciem — każdy aktywny kontekst reprezentuje przyszłość, której żaden inny kontekst nie odzyska, a odrzucenie któregokolwiek grozi wytworzeniem błędnej odpowiedzi.

Planer wykrywa to rozróżnienie podczas kompilacji i decyduje per kontekst, czy absorpcja ma zastosowanie. To również powód, dla którego benchmark posteru w panelu ③ pozostaje liniowy zarówno w przypadkach sukcesu, jak i porażki: gdy absorpcja jest bezpieczna, runtime zwija konteksty, a gdy nie jest, planer akceptuje koszt wielokontekstowy, zamiast ryzykować błędną odpowiedź.

Liczby benchmarków na posterze to ten sam algorytm rozgrywający się na większą skalę. Na wzorcu sukcesu (A+ B+ C+ D) zarówno PostgreSQL, jak i Trino skalują się O(n) po potwierdzeniu dopasowania, a przewaga PostgreSQL — z grubsza 16× do 33× — wynika głównie z luki JVM.

Na wzorcu porażki (A+ B+ C+ E) Trino nie ma absorpcji i degraduje się do O(n²), goniąc za każdym potencjalnym początkiem dopasowania; przy 100 000 wierszy zajmuje to ponad pięć godzin, podczas gdy PostgreSQL wciąż kończy w 92 ms — przyspieszenie o około 217 000×.

Ta luka to nie szlif inżynieryjny — to dokładnie rozróżnienie ten-sam-los / różne-losy z §2.5 i §2.6, zastosowane do każdego wiersza każdego potencjalnego początku dopasowania w partycji.

2.7 Przykład 5 — kiedy SKIP wyłącza absorpcję

Poprzedni przykład złamał absorpcję od strony danych: FIRST w DEFINE sprawiło, że każdy kontekst ewaluował predykaty inaczej. Absorpcja może też złamać się od strony wyjścia, a klauzula AFTER MATCH SKIP to kontroluje.

Rozważmy wzorzec PATTERN (A+) z DEFINE A AS TRUE nad pięcioma wierszami, z których wszystkie dopasowują się do A. Przy domyślnym AFTER MATCH SKIP PAST LAST ROW mechanizm dopasowania znajduje najdłuższe dopasowanie zaczynające się od najwcześniejszego wiersza, a następnie przeskakuje za nie; każdy kontekst, który wystartował wewnątrz tego dopasowania, jest niejawnie odrzucany jako redundantny — dokładnie sytuacja, do której absorpcja została zaprojektowana. Wyjściem jest pojedyncze dopasowanie, wiersze 0–4, a runtime potrzebuje tylko jednego aktywnego kontekstu.

Przełącz tryb pominięcia na AFTER MATCH SKIP TO NEXT ROW, a kontrakt się zmienia:

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

Teraz każda potencjalna pozycja startu musi zostać zaraportowana osobno, nawet gdy dopasowania się nakładają. Dla tych samych pięciu wierszy runtime musi wyemitować pięć dopasowań: wiersze 0–4, 1–4, 2–4, 3–4 i 4–4. Żadne z nich nie może zostać zastąpione „dłuższym zaczynającym się wcześniej", ponieważ standard mówi, że użytkownik chce ich wszystkich.

Zwróćmy uwagę, że predykat się nie zmienił. A AS TRUE ewaluuje się tak samo w każdym wierszu niezależnie od tego, który kontekst pyta, więc warunek tego-samego-losu z §2.5 jest wciąż spełniony. Zmienia się wymóg wyjścia: nawet konteksty o identycznych przyszłościach muszą współistnieć, bo odpowiadają odrębnym wierszom wyniku. Planer wyłącza zatem absorpcję kontekstu, ilekroć obowiązuje AFTER MATCH SKIP TO NEXT ROW, niezależnie od klauzuli DEFINE.

Zestawienie §2.6 i §2.7 obok siebie daje pełen obraz tego, kiedy absorpcja zawodzi:

Każdy z tych warunków wystarczy, by wyłączyć absorpcję dla dotkniętych kontekstów. Gdy żaden nie obowiązuje — domyślne AFTER MATCH SKIP PAST LAST ROW z warunkami DEFINE używającymi wyłącznie PREV, NEXT lub samego LAST — runtime zwija się do jednego kontekstu na pozycję wzorca i pozostaje liniowy aż do końca.

§3. Projekt — od parsera do executora

Row Pattern Recognition zaimplementowane jest jako trzy etapy przekazujące sobie pracę poprzez dobrze zdefiniowane formy pośrednie. Parser zamienia tekst SQL w drzewo wzorca i listę predykatów DEFINE; planer kompiluje drzewo w płaską tablicę elementów wzorca i decyduje, które z nich mogą uczestniczyć w absorpcji kontekstu; executor uruchamia tablicę względem partycji wiersz po wierszu w trójfazowej pętli. Każdy etap ma własny kształt danych, a większość pomysłowości projektowej znajduje się na granicach: płaski NFA mieszczący się w cache, model nawigacji wielokrotnie wykorzystujący pojedynczy slot krotki zamiast materializowania po jednym na odwołanie oraz reguła absorpcji zamieniająca pamięć O(n²) w O(n).

tekst SQL
  │
  │  etap parsera
  ▼    walidacja ramki
       budowa drzewa wzorca
       sprawdzenie typów DEFINE

drzewo wzorca + lista DEFINE
  │
  │  etap planera
  ▼    optymalizacja drzewa
       kompilacja do płaskiej tablicy NFA
       decyzja o absorbowalności

płaski NFA + flagi absorpcji
  │
  │  etap executora
  ▼    silnik per-wierszowy:
       Match → Absorb → Advance

wynik dopasowania:
  wiersz startu, długość, sukces/porażka

Poniższe sekcje przechodzą przez ten potok. §3.1 omawia parser i kształt drzewa wzorca; §3.2 omawia kompilację zamieniającą drzewo w płaski NFA; §3.3 omawia model nawigacji, którego predykaty DEFINE używają do podglądu sąsiednich wierszy; §3.4 omawia obsługę granic dopasowania — reguły SKIP, INITIAL i ograniczonej ramki ustalające, gdzie dopasowanie się zaczyna i kończy; §3.5 to trójfazowy silnik per-wierszowy; §3.6 zbiera wszystkie mechanizmy przycinania utrzymujące przestrzeń stanów ograniczoną; a §3.7 omawia, co implementacja udostępnia w wyjściu EXPLAIN.

3.1 Parser — budowa drzewa wzorca

Parser rozpoznaje pattern recognition po obecności klauzuli PATTERN wewnątrz specyfikacji okna. Jego pierwszym zadaniem jest walidacja ramki, ponieważ RPR nakłada ograniczenia, których zwykłe zapytania okienne nie mają: tryb ramki musi być ROWS (nie RANGE ani GROUPS), granica początkowa musi być CURRENT ROW, a opcje EXCLUDE są zabronione. Są to kontrole zgodności, nie optymalizacje — pojęcie ramki w RPR to rozpięcie dopasowania, a standard nie przewiduje wypełniania jej czymkolwiek innym niż dopasowane wiersze.

Gdy ramka przejdzie walidację, parser zamienia klauzulę PATTERN w drzewo zbudowane z czterech rodzajów węzłów — odwołania do zmiennej, sekwencji (konkatenacji), alternatywy i grupy (podwzorca w nawiasach). Każdy węzeł niesie kwantyfikator jako trzy liczby — dolne ograniczenie, górne ograniczenie (być może nieskończone) oraz flagę dopasowania leniwego:

Każdy predykat DEFINE zostaje następnie sprawdzony typowo względem kolumn partycji i sprowadzony do wyrażenia Boolowskiego. W ramach tego dzieją się dwie praktyczne rzeczy. Po pierwsze, każda kolumna, do której odwołuje się predykat DEFINE, jest rejestrowana jako część wymagań wyjściowych zapytania, więc planer propaguje te kolumny aż do etapu executora, nawet jeśli otaczające zapytanie ich nie wybiera — bez tego runtime nie miałby do czego ewaluować. Po drugie, zmienne, które pojawiają się w PATTERN, lecz nigdy w DEFINE, są niejawnie prawdziwe: dopasowują każdy wiersz.

3.2 Kompilacja — od AST do płaskiego NFA

Planer zamienia drzewo parsera w strukturę danych, którą uruchomi executor: płaską tablicę elementów wzorca adresowaną indeksem. Kompilacja przebiega jako sześciostopniowy potok:

compile(astTree):
  1. optymalizuj AST
  2. zmierz rozmiar i głębokość
  3. zaalokuj tablicę elementów
  4. wypełnij z AST
       (przypisz wskaźniki next/jump)
  5. sfinalizuj — ustaw wartownik FIN
  6. oznacz elementy kwalifikujące się do absorpcji

Płaski kształt został wybrany z prostego powodu: executor musi przechodzić wzorzec wielokrotnie na partycję, a ciągła tablica adresowana indeksem jest najtańszą strukturą danych do przejścia. Kroki 1 i 6 są najciekawsze — krok 1, ponieważ określa, jak duża będzie tablica, oraz krok 6, ponieważ decyduje, czy optymalizacja absorpcji z §2.5 w ogóle się zaangażuje.

Optymalizacja AST

Optymalizacja opłaca się dwukrotnie: raz w statycznej liczbie elementów płaskiej tablicy i ponownie w każdym wierszu przetwarzanym w czasie wykonania. Każda transformacja redukuje przestrzeń stanów, którą runtime musi wyliczyć. Optymalizator stosuje osiem reguł przepisywania kolejno, aż AST przestanie się zmieniać:

Spłaszczenie SEQ

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

Scalanie kolejnych zmiennych

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

Scalanie kolejnych grup

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

Scalanie kolejnych ALT

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

Absorpcja przedrostka/przyrostka

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

Spłaszczenie i deduplikacja ALT

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

Mnożenie kwantyfikatorów

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

Rozpakowanie pojedynczego dziecka

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

Mnożenie kwantyfikatorów to jedyna transformacja wymagająca kontroli bezpieczeństwa: optymalizator zwija tylko w trzech bezpiecznych przypadkach — oba kwantyfikatory nieograniczone ((A+)+ → A+), zewnętrzny dokładny ((A{2,3}){5} → A{10,15}) lub dziecko trywialne {1,1} ((A){2,5} → A{2,5}). Inne kombinacje mogą wprowadzać luki, które płaska forma by pominęła — np. (A{2}){2,3} akceptuje tylko {4, 6}, lecz naiwne A{4,6} akceptowałoby również 5 — więc optymalizator pozostawia je nietknięte.

Kształt elementu

Każdy element płaskiej tablicy reprezentuje jedną pozycję we wzorcu. Istnieje pięć rodzajów logicznych: odwołanie do zmiennej (jedyny rodzaj konsumujący wiersz); znaczniki begin grupy i end grupy otwierające i zamykające podwzorzec w nawiasach; znacznik alternatywy stojący na czele listy gałęzi; oraz znacznik zakończenia na końcu wzorca.

Każdy element niesie też głębokość (poziom zagnieżdżenia w grupach), kwantyfikator (min i max liczby powtórzeń, być może nieskończone) oraz dwa wskaźniki tranzycji — next, „dokąd pójść po skonsumowaniu tego elementu", i jump, „dokąd przeskoczyć" (używany przez alternatywę do łączenia gałęzi, przez group begin do ominięcia ciała, gdy kwantyfikator dopuszcza zero, oraz przez group end do nawrotu do ciała).

Dla PATTERN ((A B)+) skompilowana tablica wygląda tak:

PATTERN ((A B)+) kompiluje się do:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (otwiera grupę; jump przeskakuje
     do FIN, gdy min = 0)

[1] A      depth 1  quant 1..1
    next → 2

[2] B      depth 1  quant 1..1
    next → 3

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (zamyka grupę; jump wraca w pętli)

[4] FIN    wzorzec zakończony

Wzorzec czytany jest od lewej do prawej przez next, a jump obsługuje krawędzie nieliniowe. W idx 3 jump END-a wskazuje wstecz na idx 1, co jest mechanizmem pętli nieograniczonego kwantyfikatora zewnętrznego; w idx 0 jump BEGIN-a przeskoczyłby za END do idx 4, gdyby grupa była opcjonalna. Runtime nigdy nie musi konstruować grafu w czasie wykonania — po prostu podąża tymi dwoma wskaźnikami, przechodząc tablicę.

Atrybuty per element

Poza kształtem każdy element niesie cztery atrybuty logiczne kierujące zachowaniem runtime'u w tej pozycji:

Leniwy

Odwraca kolejność rozwijania kwantyfikatora. Kwantyfikatory greedy próbują „pętli ponownie" przed „wyjściem"; leniwe próbują najpierw „wyjścia". Niesione przez zmienną dla A+?; niesione przez BEGIN i END grupy dla ((…)+?).

Pętlowalny pusto

Ustawiany na endach grup, których ciało jest nullable ((A?)*, (A? B?)+, (A | B*)). Mówi runtime'owi, by dodał szybkie wyjście obok zwykłego nawrotu, aby zabezpieczenie cyklu nie zabijało prawowitych dopasowań w grupach mogących produkować puste iteracje.

W-regionie-absorbowalnym

Oznacza każdy element leżący wewnątrz regionu kwalifikującego się do absorpcji — używany przez runtime do śledzenia, czy bieżący stan wciąż znajduje się w bezpiecznym obszarze.

Punkt-porównania-absorpcji

Oznacza konkretny element, w którym mają być uruchamiane porównania absorpcji. Dla prostego A+ trafia na zmienną; dla nieograniczonej grupy jak (A B)+ trafia wyłącznie na end grupy.

Podział na „w-regionie" i „punkt-porównania" ma znaczenie, ponieważ absorpcja ma sens tylko w punktach, gdzie iteracje się zamykają. Wewnątrz ciała (A B)+ runtime jest w trakcie iteracji, a licznik nie osiągnął jeszcze swojej finalnej wartości dla tej rundy; porównywanie tutaj oznaczałoby porównywanie nieporównywalnych wartości. Stan musi osiągnąć end grupy, zanim runtime może zdecydować. Pierwszy atrybut mówi zatem „wciąż jesteś w obszarze absorbowalnym"; drugi mówi „osiągnąłeś punkt porównania — sprawdź teraz".

Analiza absorbowalności

Krok 6 kompilacji nadaje regule „tego samego losu" z §2.5 świadectwo czasu kompilacji. Decyzja jest warstwowa:

isAbsorbable(query):
  if tryb SKIP != SKIP PAST LAST ROW
      → return false
  if koniec ramki != UNBOUNDED FOLLOWING
      → return false
  if jakikolwiek DEFINE zależy od match_start
      → return false
  przejdź AST i oznacz
  elementy spełniające
  przypadek strukturalny

Pierwsze trzy kontrole są na poziomie zapytania: odpowiadają dokładnie warunkom §2.7 (strona wyjścia: tryb SKIP), ograniczonej ramki (granica łamie monotoniczność) oraz §2.6 (strona danych: FIRST lub LAST z przesunięciem w DEFINE). Gdy któraś zawiedzie, analiza nie ustawia flag i absorpcja jest wyłączona w całym zapytaniu. Gdy wszystkie przejdą, przejście AST dopuszcza trzy kształty strukturalne:

Przypadek 1 — prosta zmienna nieograniczona

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

Każda iteracja to dokładnie jeden wiersz. Licznik wcześniejszego kontekstu jest zawsze ≥ od późniejszego w każdej dzielonej pozycji.

Przypadek 2 — grupa o stałej długości, zewnętrzna nieograniczona

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

Każde dziecko ma min == max, więc ciało jest semantycznie równoważne swojej rozwiniętej formie {1,1} — (A B{2})+ zachowuje się jak (A B B)+. Każda iteracja konsumuje stałą liczbę wierszy; dominacja licznika wciąż obowiązuje.

Przypadek 3 — grupa, której ciało zaczyna się od zmiennej nieograniczonej

(A+ B)+

Wiodąca zmienna nieograniczona sama jest absorbowalna (Przypadek 1) i osłania wcześniejsze konteksty. Absorpcja zatrzymuje się, gdy tylko stan przejdzie poza A — reszta ciała nie ma gwarancji monotoniczności, więc flagi ustawiane są wyłącznie na A.

Przypadki strukturalne nieobjęte tymi trzema kształtami są równie pouczające. A B+ nie może być absorbowane przez bieżącą regułę, ponieważ wiodące A konsumuje wiersz, zanim część nieograniczona się rozpocznie, więc konteksty startujące jeden wiersz od siebie znajdują się w różnych pozycjach wewnątrz nieograniczonego ciała. (Zaprojektowano kontynuacyjne rozszerzenie „absorpcji PREFIX" obsługujące przedrostki o stałej długości przez ścieżkę cienia, planowane do osobnej łatki.) Kwantyfikatory leniwe jak A+? są wykluczone z konstrukcji: reguła absorpcji zakłada semantykę greedy, gdzie dłuższe dopasowania pochłaniają krótsze, a dopasowanie leniwe odwraca ten kierunek.

Wynikiem jest decyzja per element, a nie per wzorzec. Pojedynczy plan zapytania może mieć absorpcję włączoną dla wiodącego A+ wzorców jak (A+ B+ C) lub (A+ B+)+ — to drugie to po prostu Przypadek 3 zastosowany do swojego wiodącego elementu — i wyłączoną dla wszystkiego, co po nim; runtime po prostu konsultuje atrybut punktu-porównania na elemencie bieżącego stanu za każdym razem, gdy rozważa przejście absorpcji. Gdy stan przejdzie do regionu nieabsorbowalnego, absorpcja jest dla tego stanu permanentnie wyłączona — dokładnie to, co §2.5 i §2.6 wymagają na poziomie algorytmicznym.

3.3 Nawigacja — wymiana krotki na pojedynczym slocie

Wyrażenia DEFINE są zwykłymi wyrażeniami SQL ewaluowanymi względem wiersza, lecz mogą zawierać PREV, NEXT, FIRST lub LAST — odwołania wskazujące na różne wiersze. Same wiersze są już buforowane w tuplestore okna; to, czym executor wciąż musi zarządzać, to slot krotki, z którego maszyneria wyrażeń SQL czyta, ponieważ odwołania do kolumn wewnątrz wyrażenia są związane ze slotem w czasie planowania. Implementacja wielokrotnie wykorzystuje pojedynczy slot nawigacji dla każdego wywołania nawigacji: slot jest podmieniany przed ewaluacją wyrażenia wewnętrznego i przywracany po niej, dzięki czemu pozostała maszyneria wyrażeń SQL nigdy nie zauważa różnicy.

Model widziany przez executor jest niewielki: jest slot bieżącego wiersza trzymający wiersz, względem którego ewaluowane jest wyrażenie DEFINE, oraz slot nawigacji, który runtime może tymczasowo przekierować na inny wiersz. Wokół dowolnego wywołania nawigacji runtime przygotowuje slot nawigacji, ewaluuje wyrażenie wewnętrzne tak, jakby czytało bieżący wiersz, a następnie przywraca oryginalny wiersz. Pseudokod:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos jest poza prawidłowym zakresem:
      return NULL

  zachowaj current_row_slot
  pobierz wiersz w targetPos
    do current_row_slot
  result = eval_inner_expression()
  przywróć current_row_slot
  return result

Trik polega na tym, że jest dokładnie jeden slot do zachowania i przywrócenia. Wyrażenie wewnętrzne — cokolwiek to jest, w tym arytmetyka, wywołania funkcji lub inne odwołania do kolumn — działa względem podmienionego slotu, używając tej samej ścieżki ewaluacji co dla bieżącego wiersza. Bez alternatywnego ewaluatora, bez slotu cienia, bez kopii krotki.

Nawigacja złożona jest spłaszczana w czasie parsowania, tak by wymiana wciąż odbywała się raz. PREV(FIRST(price)) jest rozpoznawane jako nawigacja dwustopniowa — „przejdź do pierwszego dopasowanego wiersza, następnie cofnij się o jeden wiersz" — i przechowywane jako pojedyncze wywołanie nawigacji rodzaju złożonego. Runtime oblicza pozycję docelową w dwóch etapach, lecz wykonuje tylko jedną wymianę slotu, by pobrać ostateczny wiersz:

compute_target_position(call):

  # względem bieżącego wiersza
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # względem dopasowania
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # złożone: względem dop., następnie krok
  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

  zwaliduj względem odpowiedniego zakresu
  (zakres dopasowania dla FIRST/LAST wewn.,
   zakres partycji dla zewn. kroku)

Cache pozycji omija pobieranie z tuplestore, gdy kilka wywołań nawigacji w tym samym DEFINE celuje w ten sam wiersz — częste w wyrażeniach jak price > PREV(price) AND volume > PREV(volume), gdzie oba wywołania rozwiązują się do poprzedniego wiersza. Cache przechowuje tylko „ostatnio pobraną pozycję", a sama wymiana pozostaje pojedynczą operacją.

Klasyfikacja wywołań nawigacji to wkład planera w decyzję o absorpcji. Planer przechodzi każde wyrażenie DEFINE i sortuje każdą zmienną do jednego z dwóch kubełków na podstawie tego, czy wszystkie konteksty obliczą tę samą wartość Boolowską w tym samym wierszu, czy każdy kontekst obliczy własną. Kubełek determinuje dwie rzeczy w czasie wykonania: jak często zmienna jest ewaluowana (raz wspólnie czy raz na dotknięty kontekst — §3.5 Faza 1) oraz czy otaczający stan kwalifikuje się do absorpcji kontekstu (§2.5 vs §2.6).

Klasyfikacja wykonywana jest w czasie planowania i przechowywana obok każdej zmiennej DEFINE, więc runtime nie spędza czasu na decyzji — po prostu czyta kubełek dla każdej zmiennej, gdy przetwarza wiersz.

Budżet zachowania

Nawigacja sięga do wierszy, które maszyneria funkcji okna w innym wypadku już zestrumieniowała. By te wiersze były dostępne, executor zbudowany jest na tuplestore zachowującym przesuwne okno ostatnich wierszy; pytanie brzmi, jak szerokie ma być to okno. Łatka decyduje w czasie kompilacji na podstawie dwóch komplementarnych przesunięć:

Budżet wsteczny

Jak daleko wstecz od bieżącego wiersza może sięgnąć dowolne wywołanie DEFINE.

Wkład: PREV, LAST z przesunięciem, PREV(LAST(...)), NEXT(LAST(...))

Budżet wyprzedzenia od początku

Jak daleko w przód (lub wstecz, gdy ujemne) od początku dopasowania najstarszego aktywnego kontekstu może sięgnąć dowolne wywołanie DEFINE.

Wkład: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

W czasie wykonania znacznik przycięcia tuplestore ustawiany jest na wcześniejszą z dwóch pozycji — bieżący wiersz minus budżet wsteczny i początek dopasowania najstarszego aktywnego kontekstu plus budżet wyprzedzenia. Wszystko przed tym znacznikiem nie może być osiągnięte przez żadne wywołanie nawigacji w żadnym aktywnym kontekście, a tuplestore może to swobodnie odrzucić. Dwa liczniki Nav Mark, które raportuje EXPLAIN (§3.7) — Lookback i Lookahead — to zmierzone szczyty obu budżetów, najgłębsze, do których executor musiał kiedykolwiek sięgnąć w którymkolwiek kierunku w trakcie zapytania.

3.4 Granice dopasowania — SKIP, INITIAL i ramka ograniczona

Udane dopasowanie zapisywane jest jako mały zestaw wartości: flaga ważności, flaga sukcesu/porażki, wiersz, w którym zaczyna się dopasowanie, oraz liczba wierszy, które skonsumowało. Gdy flaga ważności jest ustawiona, kolejne zapytania do executora — „czy ten wiersz jest wewnątrz dopasowania?" — mogą odpowiedzieć w O(1), inspekcjonując zestaw. Długość zero jest rzeczywistym wynikiem, nie błędem: reprezentuje wzorzec dopasowany bez skonsumowania jakiegokolwiek wiersza, co executor musi odróżnić od „nie podjęto próby dopasowania w tej pozycji jeszcze".

Klauzula AFTER MATCH SKIP decyduje, gdzie zaczyna się kolejna próba dopasowania. AFTER MATCH SKIP PAST LAST ROW przechodzi do wiersza po końcu dopasowania, produkując nienakładające się wyjście, którego oczekuje większość zapytań, i włączając optymalizację absorpcji.

AFTER MATCH SKIP TO NEXT ROW przechodzi tylko do wiersza po początku dopasowania, dopuszczając nakładające się dopasowania; planer wyłącza zatem absorpcję dla całego planu zapytania, gdy ten tryb obowiązuje.

Dwa cele pominięcia, które standard również definiuje — AFTER MATCH SKIP TO FIRST zmienna i AFTER MATCH SKIP TO LAST zmienna — zależą od historii dopasowania, której ta łatka nie zachowuje. Nie są w ogóle obecne w gramatyce, więc parser zgłasza ogólny błąd składniowy, jeśli któryś zostanie podany.

To samo dotyczy SEEK, alternatywy standardu dla INITIAL. Przy SEEK próba dopasowania zaczynająca się w wierszu R może powieść się w dowolnym wierszu od R do końca ramki, nie tylko w samym R. Łatka implementuje wyłącznie INITIAL: każde potencjalne dopasowanie zakotwiczone jest w konkretnym wierszu. Parser zgłasza błąd, jeśli zażądano SEEK. Ograniczone ramki otrzymują własne traktowanie — gdy użytkownik zapisze ROWS BETWEEN CURRENT ROW AND N FOLLOWING zamiast UNBOUNDED FOLLOWING, executor zwiera dowolny kontekst, którego dopasowanie osiągnęło granicę, wymuszając niedopasowanie, a absorpcja zostaje wyłączona, ponieważ granica łamie założenie monotoniczności, na którym opiera się absorpcja.

3.5 Trójfazowy silnik per-wierszowy

Sterownik per-wierszowy executora wywoływany jest przez otaczającą maszynerię funkcji okna zawsze, gdy potrzebuje wiedzieć, czy dany wiersz należy do dopasowanej ramki. Sterownik znajduje lub tworzy kontekst dla bieżącej pozycji startu, ewaluuje każdy predykat DEFINE raz względem bieżącego wiersza, by wyprodukować tablicę Boolowską per zmienna, a następnie napędza NFA naprzód o jeden wiersz. Sam krok naprzód to trzy fazy w ustalonej kolejności — Match, Absorb, Advance — owinięte w tę samą zewnętrzną pętlę:

processRow(currentPos):

  # Faza 1 — MATCH (konwergencja)
  for each context:
      if context przekracza ramkę ograniczoną:
          wymuś niedopasowanie (wczesna finalizacja)
          continue
      if matchStartRow różni się od
         wspólnej pozycji ewaluacji:
          re-ewaluuj zmienne DEFINE zależne
          od początku dopasowania (§3.3)
      match(context, varMatched)

  # Faza 2 — ABSORB
  if wzorzec jest absorbowalny:
      odśwież flagi każdego kontekstu
      absorb_contexts()

  # Faza 3 — ADVANCE (dywergencja)
  for each context:
      advance(context, currentPos)

Kolejność nie jest wyborem stylistycznym. Match musi wykonać się pierwszy, ponieważ absorpcja porównuje liczniki po dopasowaniu; uruchomienie Absorb przed Match porównywałoby stany, które za chwilę umrą. Advance musi wykonać się ostatni, ponieważ jest jedyną fazą tworzącą nowe stany — rozszerza każdy ocalały stan poprzez tranzycje epsilon, aż każdy osiągnie zmienną oczekującą na następny wiersz. Uruchomienie Absorb po Advance oznaczałoby porównywanie rozbieżnych następców, mijając punkt, w którym stany są najczyściej porównywalne.

Faza 1 — Match

Match to faza „konwergencji": stany albo przeżywają z inkrementowanym licznikiem, albo umierają. Subtelnym punktem jest to, że dla zmiennych siedzących w regionie absorbowalnym Match wykonuje też niewielki postęp w przód, by Absorb mógł porównywać czysto. Warunek pokrycia uruchamia się tylko w punkcie porównania absorpcji — END nieograniczonej grupy — więc stany, które właśnie dopasowały zmienne mid-iteracji (jak B wewnątrz (A B)+), muszą zostać przesunięte aż do tego punktu porównania w trakcie samego Match; w przeciwnym razie Absorb nie znajdzie nic kwalifikującego się do porównania i optymalizacja nigdy się nie zaangażuje.

match(context, varMatched):
  for each state in context:
      elem = pattern[state.elemIdx]
      if elem nie jest zmienną:
          continue   # advance to obsługuje

      if not varMatched[elem.varId]:
          odrzuć stan   # martwa gałąź
          continue

      state.counts[elem.depth] += 1

      # Wbudowany postęp w przód, by
      # następna faza mogła porównywać
      # w elemencie punktu porównania,
      # a nie w trakcie iteracji.
      if elem jest in-region, lecz nie
         punktem porównania,
         i osiągnął swój max licznik,
         a elem.next to end grupy:

          przejdź łańcuch END:
            inkrementuj licznik grupy zewn.
            przesuń state.elemIdx do END
            kontynuuj, póki wciąż in-region,
              must-exit i next to END
          (zatrzymuje się w punkcie porównania
           lub na elemencie wciąż pętlowalnym)

Przejście łańcuchem end czyni zagnieżdżone grupy o stałej długości absorbowalnymi. W ((A B){2})+, gdy B osiąga swój max (B to {1,1}), licznik grupy wewnętrznej musi się inkrementować; jeśli ten licznik też osiągnie swój max — zamykając wewnętrzne {2} — licznik grupy zewnętrznej musi się także inkrementować, i tak dalej, aż stan wyląduje na najbardziej zewnętrznym punkcie absorpcji — END nieograniczonej grupy zewnętrznej (+). Wykonanie tej pracy w Match pozwala Absorb porównywać z kontekstami, które już skonsolidowały swoje liczniki po-iteracyjne.

Faza 2 — Absorb

Przejście absorpcji idzie od kontekstów najnowszych (ogon) do najstarszych (głowa). Dla każdego trwającego kontekstu, który jest w pełni absorbowalny, skanuje wstecz w poszukiwaniu starszego trwającego kontekstu, który go pokrywa, i zwalnia nowszy, jeśli znajdzie. Ponieważ konteksty trzymane są w kolejności tworzenia, a każdy wiersz tworzy najwyżej jeden kontekst, „nowszy" i „starszy" naprawdę oznaczają „wystartowany później" i „wystartowany wcześniej".

absorb_contexts():
  for ctx od ogona wstecz:
      if ctx jest zakończony
         lub ma jakikolwiek stan nieabsorbowalny:
          skip
      for older od ctx.prev wstecz:
          if older jest zakończony
             lub nie ma stanu absorbowalnego:
              skip
          if covered(older, ctx):
              free(ctx)
              zapisz długość absorpcji
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem nie jest punktem porównania:
          return false
      if brak stanu w older z:
            tym samym elemIdx
            i isAbsorbable
            i older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Z tego wynikają dwie mikro-decyzje. Pierwsza: kontrola pokrycia odrzuca natychmiast, jeśli jakikolwiek stan w nowszym kontekście znajduje się gdziekolwiek poza punktem porównania — porównywanie w punktach nieoceniających nie byłoby sensownym porównaniem.

Druga to asymetryczna para flag na każdym kontekście: has-absorbable-state odpowiada „czy ten kontekst mógłby wchłonąć nowszy?" i jest monotoniczny (może iść tylko true→false, gdy stany umierają), podczas gdy all-states-absorbable odpowiada „czy ten kontekst może zostać wchłonięty?" i jest dynamiczny (przełącza się z powrotem na true, gdy stan nieabsorbowalny zostaje usunięty). Obie flagi są sprawdzane w stałym czasie, zanim w ogóle rozpocznie się skan pokrycia, więc absorpcja ponosi swój pełny koszt wyłącznie na kontekstach, które mają realną szansę zostać wchłonięte.

Faza 3 — Advance

Advance to faza „dywergencji": każdy ocalały stan jest rozszerzany przez tranzycje epsilon, aż każda gałąź osiągnie albo zmienną czekającą na następny wiersz, albo wartownik FIN. Rozszerzanie jest depth-first, a kolejność, w której przechodzone są gałęzie rodzeństwa, sprawia, że reguła preferowania standardu faktycznie obowiązuje — leksykalnie pierwsza gałąź jest zawsze dodawana jako pierwsza, a krok deduplikacji przy wstawianiu stanu po cichu odrzuca równoważne późniejsze dodania.

advance(context, currentPos):
  wyciągnij wszystkie bieżące stany;
  odbuduj ctx.states od zera
  for each state w porządku leksykalnym:
      wyczyść bitmapę odwiedzonych elementów
      advance_state(state)   # DFS

      # Preferowanie: gdy DFS osiągnie FIN,
      # pozostałe stany są mniej preferowane
      # i mogą zostać odrzucone.
      if FIN osiągnięte i stany pozostają:
          zwolnij resztę
          break

advance_state(state):
  przejdź przez state.elemIdx,
  rekurencja przez:
    gałęzie ALT (w kolejności),
    BEGIN (wejdź do grupy; plus opcjonalna
           ścieżka pominięcia, gdy min = 0),
    END (pętla wstecz / wyjście / fast-forward —
         patrz niżej),
    FIN (zapisz matchEndRow,
         zachowaj matchedState i przytnij
         późniejsze konteksty wewnątrz zakresu
         tego kandydata — patrz niżej),
  zatrzymując się przy każdej napotkanej zmiennej:
      dodaj stan do ctx.states
      (deduplikując po elemIdx + counts)

Zapisanie stanu, który osiągnął FIN, robi więcej niż tylko zaznacza kandydata na dopasowanie. Przy AFTER MATCH SKIP PAST LAST ROW kolejne raportowalne dopasowanie musi zaczynać się ściśle za bieżącym — więc w chwili zapisania kandydata każdy kolejny kontekst, którego wiersz startu mieści się wewnątrz zakresu kandydata, jest natychmiast przycinany, nawet jeśli kontekst, który trafił FIN, może wciąż szukać dłuższego dopasowania przez wycofanie greedy.

Przycinanie jest bezpieczne, bo niezależnie od tego, jak ta wyszukiwarka zakończy (dłuższe dopasowanie zastąpi kandydata lub kandydat się utrzyma), wszystkie przycięte konteksty wystartowały wewnątrz zakresu, który kolejne raportowalne dopasowanie musi przeskoczyć, a więc nigdy nie mogłyby wyprodukować własnego wyjścia.

Jest to jeden z dwóch kroków przycinania w czasie FIN — drugi, opisany wcześniej w tej sekcji jako część Advance, odrzuca stany leksykalnie gorsze wewnątrz tego samego kontekstu.

Najtrudniejsza logika per element żyje w handlerze END. Gdy licznik iteracji grupy jest poniżej dolnej granicy, runtime musi pętlować wstecz; gdy jest na lub powyżej górnej granicy, musi wyjść; pomiędzy oba opcje są ważne, a greediness kwantyfikatora decyduje, którą próbować jako pierwszą:

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

  if count < elem.min:
      pętla wstecz do ciała
      if elem jest empty-loopable:
          # ciało nullable, patrz §3.2
          sklonuj też stan fast-forward
          wychodzący z grupy
          z licznikiem spełnionym
          (ratuje prawowite dopasowania,
           które guard cyklu inaczej
           by zabił)

  elif count >= elem.max:
      zresetuj liczniki na tej głębokości
      wyjście via next
      (END→END: inkrementuj zewnętrzny
       licznik END)

  else:
      # min <= count < max: rozwidlenie
      zbuduj stan wyjścia
      (liczniki na tej głębokości reset)
      if greedy:
          najpierw pętla, potem wyjście
          # preferuj dłuższe
      else (leniwe):
          najpierw wyjście
          if wyjście osiągnęło FIN:
              porzuć pętlę
              # preferuj krótsze
          else pętla jako drugie

Każdy stan dodawany do kontekstu przechodzi przez kontrolę deduplikacji porównującą jego pozycję i liczniki z istniejącą listą stanów. Ponieważ Advance przetwarza gałęzie w kolejności DFS, stan z pierwszej gałęzi dowolnej alternatywy ląduje jako pierwszy — a dowolna późniejsza gałąź produkująca tę samą pozycję i liczniki jest odrzucana przy wstawianiu. Jest to dokładnie to, czego wymaga reguła porządku leksykalnego z §2.4, zaimplementowane na samym dnie runtime'u bez osobnego przejścia.

Grupy pętlowalne pusto

Subtelnym przypadkiem, który runtime musi rozbroić, jest grupa nullable — grupa, której ciało może dopasować zero wierszy, ponieważ każde dziecko ciała samo jest opcjonalne. Wzorce jak (A?)*, (A? B?)+ i (A | B*) mają tę właściwość: w zależności od danych ciało może zakończyć iterację bez konsumowania jakiegokolwiek wiersza. To w zasadzie w porządku, ale stwarza realne zagrożenie dla rozszerzania epsilon NFA. Gdy ciało produkuje puste dopasowanie, element END pętluje wstecz do BEGIN, ciało znów produkuje puste dopasowanie, BEGIN pętluje do END, i tak dalej. Bez czegoś, co by to zatrzymało, DFS Advance nigdy by nie zakończył.

Runtime zatrzymuje to bitmapą odwiedzonych elementów (jeden bit na element wzorca), czyszczoną przed rozszerzaniem DFS każdego stanu: gdy tylko jakikolwiek element zostanie odwiedzony po raz drugi w tym samym rozszerzaniu, ścieżka jest porzucana. Guard cyklu jest bezwarunkowy i tani, lecz ma efekt uboczny — może też porzucić ścieżki, które powinny osiągnąć dolną granicę przez prawowite puste iteracje. Weźmy (A?){2,3} bez żadnego A dopasowującego się gdziekolwiek w strumieniu wierszy:

pożądane zachowanie:
  iter 1: A? dopasowuje zero wierszy
          → END, count = 1 (poniżej min)
  iter 2: A? dopasowuje zero wierszy
          → END, count = 2 (spełnia min)
  wyjście z dopasowaniem o długości zero

co guard cyklu robi sam z siebie:
  iter 1: A? pominięte → END, count = 1
          → pętla wstecz do BEGIN
  iter 2: BEGIN już odwiedzony
          → DFS przerywa
  count nigdy nie osiąga min
  → dopasowanie zawodzi (niepoprawnie)

Naprawa decydowana jest w czasie kompilacji i wykonywana w czasie wykonania. Gdy planer widzi grupę o ciele nullable, taguje element END tej grupy jako empty-loopable. W czasie wykonania, gdy handler END ma pętlować wstecz, ponieważ licznik iteracji jest wciąż poniżej dolnej granicy, tag empty-loop mówi mu, by sklonował dodatkowy stan fast-forward obok normalnej ścieżki pętli wstecznej:

advance_end (count poniżej min):

  ścieżka główna:
    pętla wstecz do ciała
    (pozostawia drzwi otwarte na realne,
     niepuste dopasowanie w następnej
     iteracji)

  if elem jest empty-loopable:
    ścieżka fast-forward:
      zresetuj licznik tej głębokości
      wyjdź z grupy via next,
      traktując pozostałe wymagane
      iteracje jako puste dopasowania

Obie ścieżki grają komplementarne role. Główna pętla wsteczna łapie przypadek, gdzie ciało wciąż ma realne dopasowania do wyprodukowania później — np. w (A?){2,3} z danymi, w których A dopasowuje się tylko w późniejszych wierszach, pętla wsteczna pozwala drugiej i trzeciej iteracji znaleźć niepuste dopasowania. Fast-forward łapie przypadek, gdzie ciało nigdy nic nie produkuje: omija guard cyklu, wychodząc z grupy w całości, deklarując „pozostałe wymagane iteracje są puste", i pozwala dopasowaniu się powieść z ciałem o długości zero. Oba stany dodawane są do kontekstu; ten, który rozszerzy się pomyślnie, wygrywa, a kontrola deduplikacji przy wstawianiu zapobiega temu, by którakolwiek ścieżka zrodziła więcej stanów niż jej należny udział.

Poza guardem cyklu, jeszcze jedna sztuczka rozruchowa rozróżnia wyniki zerowierszowe na samym początku kontekstu. Krok tworzenia kontekstu w każdym potencjalnym wierszu startowym uruchamia initial advance poprzez tranzycje epsilon przed skonsumowaniem jakiegokolwiek wiersza, używając pozycji jeden wiersz przed faktycznym startem. Każda ścieżka, która osiągnie wartownik FIN samymi tranzycjami epsilon — bez konsumowania wiersza — produkuje zatem pozycję końca mniejszą od pozycji startu; ta współrzędna o ujemnym rozpięciu, w połączeniu z tym, czy FIN został faktycznie osiągnięty, koduje różnicę między pustym dopasowaniem (długość-0 dopasowanie zaakceptowane) a niedopasowanym startem bez potrzeby osobnej flagi.

3.6 Jak przestrzeń stanów pozostaje ograniczona

Liniowość runtime'u nie jest wynikiem pojedynczej optymalizacji. Jest skumulowanym efektem warstwowego zestawu reguł przycinania, z których każda łapie inną przyczynę wzrostu przestrzeni stanów w innym punkcie cyklu per-wierszowego. Niektóre decydowane są w czasie kompilacji i jedynie konsultowane w czasie wykonania; inne odpalają dynamicznie. Niektóre zabijają pojedyncze stany; inne — całe konteksty. Powyższe sekcje wprowadziły każdą z nich w kontekście; poniższa tabela zbiera je na jednej stronie.

Niepowodzenie predykatu Match

Stany zmiennych, których DEFINE ewaluował się do false w bieżącym wierszu — martwe gałęzie.

Wbudowany advance łańcucha end Match

Zmienne, które osiągnęły swój max licznik i w innym wypadku zostawiłyby stan w trakcie iteracji; przesunięte przez endy grup o stałej długości, by absorpcja mogła porównywać we właściwym punkcie.

Absorpcja kontekstu Absorb

Nowsze konteksty, których każdy stan jest pokryty przez stan starszego kontekstu z wyższym licznikiem — patrz §2.5 dla reguły pojęciowej, §3.2 dla kwalifikowalności kompilacji, §3.5 dla kontroli per para.

Deduplikacja stanów Advance

Stany osiągnięte różnymi gałęziami DFS, które kończą w tej samej pozycji z tymi samymi licznikami — przeżywa tylko pierwszy (leksykalnie najwcześniejszy); późniejsze równoważne są po cichu odrzucane, co także realizuje preferowanie (§2.4).

Wczesne zakończenie FIN (wewnątrz kontekstu) Advance

Stany wciąż oczekujące w kolejce DFS, gdy jedna gałąź osiąga FIN — zgodnie z porządkiem leksykalnym wszystkie pozostałe stany są mniej preferowane i mogą zostać natychmiast odrzucone.

Przycinanie kandydata-dopasowania (między kontekstami) Na FIN

Inne konteksty, których wiersz startu mieści się wewnątrz zakresu kandydata-dopasowania — kontekst, który trafił FIN, może wciąż szukać dłuższego dopasowania (wycofanie greedy), ale przy AFTER MATCH SKIP PAST LAST ROW żaden kontekst wewnątrz zakresu kandydata nie może już wyprodukować raportowalnego wyjścia, niezależnie od tego, jak ta wyszukiwarka się skończy, i jest natychmiast przycinany.

Guard cyklu Advance

Rozszerzania epsilon ponownie odwiedzające ten sam element wzorca w tym samym DFS — w przeciwnym razie pętlowałyby w nieskończoność w grupach nullable.

Fast-forward pustej pętli Advance

Prawowite dopasowania pustych iteracji, które guard cyklu zabiłby w grupach nullable — omija cykl, wychodząc z grupy z pozostałymi wymaganymi iteracjami zadeklarowanymi jako puste.

Odcięcie ramki ograniczonej Match

Konteksty, których dopasowanie osiągnęło zdefiniowaną przez użytkownika górną granicę ramki — wymuszone niedopasowanie, by nie mogły wykraczać poza nią (§3.4).

Czytanie wpisów po znaczku fazy odtwarza życie kontekstu: przycinanie odpala w każdym wierszu przez trzy główne fazy (Match, Absorb, Advance) i ponownie przy zakończeniu dopasowania (Na FIN). Czytanie opisów zamiast tego grupuje reguły według tego, w co celują: martwe gałęzie, redundantne konteksty, równoważne stany, nieskończone pętle i przedłużanie poza granice nałożone przez użytkownika.

Żadna pojedyncza reguła sama w sobie by nie wystarczyła. Sam guard cyklu zabijałby prawowite dopasowania w grupach nullable; sam fast-forward pustej pętli nie zatrzymywałby nieskończonych pętli epsilon; sama absorpcja nadkonsolidowałaby, gdy DEFINE odwołuje się do początku dopasowania; sama deduplikacja nie usuwałaby redundantnych kontekstów, tylko redundantne stany. Runtime pozostaje liniowy w przypadkach, które mają znaczenie — PATTERN (A+ B+ C+ D) na 100 000 wierszy, benchmark panelu ③ posteru — wyłącznie dlatego, że każda warstwa łapie to, co warstwy powyżej omijają.

3.7 Wyjście EXPLAIN

EXPLAIN ANALYZE na zapytaniu z RPR udostępnia statystyki na poziomie NFA, których nie ma dla zwykłych funkcji okna. Trzy grupy liczników emitowane są obok operatora okna:

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
  (tylko gdy zapytanie używa FIRST,
   PREV(FIRST(...)) lub NEXT(FIRST(...)))

Peak i total to bezpośrednia instrumentacja runtime'u: ile stanów było jednocześnie aktywnych w szczycie, ile zostało utworzonych przez życie zapytania i ile scalono przez deduplikację. Histogramy długości dopasowania rozdzielają cztery wyniki — udane dopasowania, nieudane próby dopasowania, wchłonięte konteksty i konteksty przycięte (skipped) bez ewaluacji — a raportowanie ich z min/max/avg czyni patologie wydajności widocznymi na pierwszy rzut oka: zdrowy przebieg pokazuje większość kontekstów jako matched lub absorbed, z małymi długościami mismatched.

Dwa liczniki Nav Mark raportują budżet zachowania tuplestore wywodzony przez §3.3 w czasie kompilacji. Lookback to najgłębsze sięgnięcie wstecz przez PREV, LAST z przesunięciem i formy złożone z wewnętrznym LAST; Lookahead to najgłębsze sięgnięcie w przód (lub wstecz, gdy ujemne) mierzone od początku dopasowania najstarszego aktywnego kontekstu, którego wkład wnoszą FIRST i formy złożone z wewnętrznym FIRST.

Każdy licznik drukuje się jako stała liczba, gdy przesunięcie jest stałą, „runtime", gdy przesunięcie jest niestałym wyrażeniem ewaluowanym przy każdym wywołaniu, i „retain all", gdy runtime potrzebuje nieograniczonego budżetu. Lookahead emitowany jest tylko wtedy, gdy zapytanie faktycznie używa nawigacji relatywnej względem początku dopasowania.

Razem te liczniki pozwalają debugować wydajność RPR bez podłączania gdb do backendu.

Poza licznikami EXPLAIN wiernie odtwarza też oryginalne klauzule PATTERN i DEFINE, w tym kwantyfikatory leniwe, powtarzanie grup oraz opcję AFTER MATCH SKIP. Implementacja kładzie nacisk na to, by ten okrąg był stabilny, aby pg_dump i pg_upgrade mogły zachowywać obiekty RPR bez semantycznego dryfu — pakiet regresji rpr_explain weryfikuje to przypadek po przypadku (patrz §4).

§4. Testy — mapa pokrycia

Łatka dostarcza pięć pakietów regresyjnych, które razem ćwiczą każdą warstwę opisaną w §3 — z grubsza 13 000 linii SQL, każdy pakiet skupiony na innym aspekcie. Podział jest celowy: trzymanie spraw parsera, poprawności runtime'u, interakcji planera i formatowania wyjścia w osobnych plikach ułatwia lokalizację awarii i zapobiega temu, by niezwiązana zmiana w jednej warstwie przypadkowo unieważniła testy w innej. Pięć pakietów to:

rpr

Semantyka end-to-end zapytań — realistyczne scenariusze okienne na syntetycznych danych giełdowych (kształt V, kształt W, kolejne wzrosty, odwrócenia).

rpr_base

Warstwa parsera — akceptacja słów kluczowych, kształty składni, kwantyfikatory, parsowanie nawigacji, komunikaty o błędach oraz stabilność okrągu pg_dump/pg_upgrade.

rpr_nfa

Runtime NFA — pętla trójfazowa, absorpcja w każdym absorbowalnym kształcie i przypadki brzegowe cyklu życia kontekstu.

rpr_explain

Formatowanie wyjścia — statystyki NFA, deparsowanie wzorca, cytowanie identyfikatorów, stabilność formatu po przeładowaniu.

rpr_integration

Interakcje planera — zabezpieczenia uniemożliwiające niezwiązanym optymalizacjom okiennym popsucie semantyki RPR.

4.1 rpr — scenariusze end-to-end

Pakiet scenariuszowy jest publicznym obliczem zestawu testów: używa syntetycznego zbioru cen giełdowych o około 1600 wierszach i uruchamia na nim realistyczne zapytania — odbicie w kształcie V, kształt W (podwójne dno), kolejne wzrosty i spadki, wzorce odwrócenia, partycje wielosymbolowe. Jest to jedyny pakiet, w którym wejścia i wyjścia czytają się jak zapytania, które użytkownik mógłby faktycznie napisać; pozostałe są celowo redukcyjne, skupione na jednej warstwie na raz.

Ponieważ te zapytania łączą każdą warstwę (parser, planer, executor, EXPLAIN), pojedyncza awaria w rpr rzadko mówi, gdzie żyje błąd. Cztery następujące pakiety to bisekcja: awaria w rpr plus przechodzący rpr_base wyklucza parser; plus przechodzący rpr_nfa zawęża to do kształtów danych specyficznych dla scenariusza; plus przechodzący rpr_integration wyklucza ingerencję planera; a wszelki dryf deparsowania pojawia się w rpr_explain.

4.2 rpr_base — powierzchnia parsera

Pakiet bazowy jest największy i jest największy nie bez powodu: jest odpowiedzialny za udowodnienie, że każdy legalny fragment składni z §1.2 faktycznie się parsuje, każdy nielegalny fragment z §1.3 jest odrzucany z użytecznym błędem, a każda zaakceptowana forma przeżywa okrąg serializacji. Większość ma postać małych skupionych fragmentów — jeden na cechę składniową — a nie długich realistycznych zapytań, ponieważ celem jest pokrycie, a nie realizm scenariusza.

Testy serializacji zasługują na szczególną uwagę. Obiekty RPR (widoki, widoki zmaterializowane, wyjście pg_dump) muszą przechodzić okrąg przez reprezentację katalogu bez semantycznego dryfu, włącznie z subtelnościami jak flaga leniwa na kwantyfikatorze czy dokładna forma złożonego wyrażenia nawigacji. Niewielki zestaw obiektów specyficznych dla serializacji (widoki rpr_serial_v* i ich tabele bazowe) jest celowo pozostawiany w miejscu na końcu przebiegu, aby otaczająca infrastruktura regresji mogła je podjąć i ćwiczyć na nich pg_dump i pg_upgrade. Reszta rusztowania testowego jest jak zwykle usuwana. Błędy złapane w ten sposób (np. flaga leniwa zgubiona między deparsowaniem a ponownym parsowaniem) ujawniają się tylko wtedy, gdy okrąg jest ćwiczony end-to-end.

4.3 rpr_nfa — silnik runtime'u

Jest to pakiet ćwiczący każdy mechanizm opisany w §3.5 i §3.6. Jego testy podążają za spójnym wzorcem: tabela wejściowa, której wiersze są jawnymi tablicami Boolowskimi deklarującymi, które zmienne DEFINE dopasowują się w każdym wierszu, sparowana ze wzorcem badającym konkretne zachowanie runtime'u. Idiom tablicy Boolowskiej oddziela test runtime'u od maszynerii ewaluacji DEFINE — testowane jest „skoro te zmienne pasują tutaj, czy pętla NFA produkuje oczekiwane rozpięcie dopasowania?", a nie „czy ewaluator wyrażeń DEFINE poprawnie liczy te Boole?". Ewaluator DEFINE testowany jest gdzie indziej (rpr_base dla parsowania, rpr dla zachowania end-to-end).

Typowy fixture testowy wygląda tak — kolumna tablic nazw zmiennych, gdzie każdy wpis mówi, które zmienne DEFINE odpalają w tym wierszu, oraz wzorzec, którego klauzule DEFINE testują wprost te nazwy:

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

Czytanie kolumny tablicy w dół to czytanie scenariusza testowego wprost. Wiersze 2 i 3 niosą obie nazwy — A i B oba odpalają tam, więc NFA ma realny wybór, gdzie przełączyć się z gałęzi A na gałąź B. Oczekiwane dopasowanie (A w wierszach 1–3, po którym B w wierszu 4, przy greedy preferowaniu standardu) jest ustalone wyłącznie przez te flagi, bez ewaluacji wyrażeń o jakimkolwiek znaczeniu tutaj — = ANY to tylko trywialna warstwa udostępniająca kolumnę tablicy dla DEFINE, a nie to, co test ćwiczy. Napisanie tego samego scenariusza z predykatem numerycznym (price > PREV(price) i podobnymi) splątywałoby test NFA z zachowaniem ewaluatora predykatu; idiom tablicowy trzyma oba czysto rozdzielone, a awaria tutaj wskazuje wprost na pętlę NFA.

Pokrycie absorpcji jest szczególnie szerokie, ponieważ absorpcja to optymalizacja najbardziej podatna na ciche produkowanie błędnych odpowiedzi, jeśli się włączy, gdy nie powinna. Testy obejmują każdy kształt z analizy przypadków §3.2:

• prosta zmienna nieograniczona (A+) — kanoniczne zwinięcie N-do-1;
• grupy o stałej długości ((A B)+, (A B{2})+, trzypoziomowe zagnieżdżone ((A (B C){2}){2})+);
• wiodąca zmienna nieograniczona ze stałym przyrostkiem (A+ B) — tylko wiodące A+ niesie flagi absorpcji, przyrostek nie;
• absorpcja per gałąź wewnątrz alternatywy (B+ C | B+ D);
• wiele zmiennych nieograniczonych (A+ B+) — tylko wiodąca jest absorbowalna;
• kwantyfikatory leniwe (A+?) — zweryfikowane jako wykluczone z absorpcji;
• niewiodące nieograniczone (A B+) — zweryfikowane jako wykluczone.

Poza absorpcją pakiet pokrywa cykl życia kontekstu: nakładające się konteksty przy AFTER MATCH SKIP TO NEXT ROW, czyszczenie nieudanych kontekstów w trakcie strumienia, finalizację niedokończonych kontekstów na końcu partycji oraz konteksty napotkane po tym, jak kandydat dopasowania został już zapisany w kontekście-głowie. Każde z nich mapuje się na konkretną regułę przycinania w §3.6, a testy napisano tak, by głośno zawodziły, gdy reguła nie zadziała (albo zostawiając redundantne konteksty przy życiu, albo zabijając kontekst, który powinien był wyprodukować wyjście).

4.4 rpr_explain — stabilność wyjścia

Wyjście EXPLAIN jest częścią kontraktu z użytkownikiem — narzędzia stron trzecich (autouzupełnianie psql, dashboardy monitorujące, scrapery logów) parsują je, a zmiany wyglądające kosmetycznie mogą je zepsuć. Pakiet rpr_explain weryfikuje trzy rzeczy:

• Liczniki NFA pojawiają się we właściwym miejscu — statystyki per WindowAgg (peak/total/merged stany, peak/total/pruned konteksty, histogramy długości dla matched/mismatched/absorbed/skipped, Nav Mark Lookback i — gdy używana jest nawigacja relatywna względem początku dopasowania — Nav Mark Lookahead) wszystkie pojawiają się pod EXPLAIN ANALYZE z udokumentowanymi etykietami.
• Wzorce poprawnie się deparsują — każdy kształt kwantyfikatora, w tym warianty leniwe i formy ograniczone; każda alternatywa; każda grupa; każda forma AFTER MATCH SKIP; INITIAL; wywołania nawigacji z przesunięciami; nawigacja złożona. Zdeparsowany tekst musi przejść okrąg przez parser bez zmian.
• Cytowanie identyfikatorów jest poprawne — zmienne wzorca i wyrażenia DEFINE emitowane są z tymi samymi regułami cytowania co zwykłe identyfikatory SQL, więc nietypowe nazwy zmiennych nie psują wyjścia pg_dump.

Podobnie jak rpr_base, ten pakiet celowo zostawia swoje obiekty w miejscu na końcu przebiegu, aby pokrycie pg_dump i pg_upgrade rozciągało się także na artefakty po stronie explain.

4.5 rpr_integration — interakcje planera

Planer PostgreSQL ma wiele optymalizacji operujących na zapytaniach okiennych — kanonizacja ramki, pushdown warunków serii, deduplikacja identycznych okien, projekcja nieużywanego wyjścia, odwrotne tranzycje agregatów ruchomych — a każda z nich została zaprojektowana bez myślenia o RPR. Większość z nich jest niebezpieczna do zastosowania, gdy okno ma klauzulę PATTERN: ramka jest częścią kontraktu dopasowania, dopasowane wyjście nie jest już monotoniczne w żaden oczywisty sposób, a dwa okna z tą samą specyfikacją, lecz różnymi DEFINE, produkują rzeczywiście różne wyniki. Pakiet integracyjny weryfikuje, że każda z tych optymalizacji jest poprawnie wyłączana lub omijana dla okien RPR:

Kanonizacja ramki

Planer normalnie przepisuje ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING na ROWS UNBOUNDED PRECEDING dla monotonicznych agregatów. Ramka RPR to rozpięcie dopasowania, nie okno agregacyjne, i musi pozostać dosłowna.

Pushdown warunków serii

Monotoniczny filtr WHERE na wyjściu funkcji okna może być normalnie pchnięty do operatora okna jako warunek zatrzymania. Dla RPR zakończyłoby to dopasowywanie wzorca przedwcześnie, potencjalnie odcinając dopasowania w trakcie rozszerzania.

Deduplikacja okien (RPR vs nie-RPR)

Dwa okna z identycznym ORDER BY i ramką byłyby normalnie scalone w jedno. Okno RPR i okno nie-RPR nigdy nie mogą dzielić stanu, ponieważ strona RPR niesie wyniki dopasowań.

Deduplikacja okien (różne DEFINE)

Dwa okna RPR z tym samym PATTERN, lecz różnymi klauzulami DEFINE, produkują różne dopasowania i muszą pozostać odrębne, nawet jeśli ich kształt strukturalny jest identyczny.

Projekcja nieużywanego wyjścia

Nawet jeśli otaczające zapytanie nigdy nie czyta wyjścia per-wierszowego okna, okno RPR nie może zostać usunięte: efekty uboczne mechanizmu dopasowania wzorca (które wiersze są wewnątrz którego dopasowania) zasilają obliczenia zredukowanej ramki gdzie indziej w planie.

Odwrotne tranzycje agregatu ruchomego

Agregaty okienne z funkcją tranzycji odwrotnej mogą być normalnie ewaluowane przyrostowo, gdy ramka się porusza. Zredukowana ramka RPR nie jest oknem przesuwnym; ścieżka tranzycji odwrotnej produkowałaby błędne wyniki.

Wzór tych testów jest ten sam: każdy dostarcza linię bazową nie-RPR wyzwalającą optymalizację (i weryfikuje, że EXPLAIN pokazuje jej zastosowanie), a następnie uruchamia zapytanie RPR strukturalnie podobnego kształtu i weryfikuje, że optymalizacja nie jest stosowana. Obie połowy razem dowodzą, że zabezpieczenie w planerze wykonuje realną pracę, a nie zatwierdza każdego zapytania bez realnej weryfikacji.

Ten pakiet jest też powodem, dla którego §3.4 jest krótki. Mechanizmy „granic dopasowania" — zredukowana ramka, SKIP, INITIAL, odcięcie ramki ograniczonej — testowane są operacyjnie gdzie indziej; rpr_integration weryfikuje, że żaden inny etap optymalizatora nie majstruje przy nich po drodze. Przechodzący rpr_integration pozwala pozostałym pakietom zaufać, że ich wejścia docierają do executora niewzruszone.