Row Pattern Recognition Szczegółowa analiza
Przewodnik po ISO/IEC 19075-5 · SQL R020 w PostgreSQL — co zostało zbudowane, co wciąż pozostaje do napisania i jak to faktycznie działa.
Przeglądnij standard, przeanalizuj omówione przykłady, zapoznaj się z projektem, a następnie wypróbuj działający symulator NFA z własnymi wzorcami.
Dyskusja: wątek pgsql-hackers · najnowsza łatka (v55) · commitfest #4460.
Tłumaczenie wstępne AI — możliwe błędy.
§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 mają wiele wspólnego w składni i semantyce (19075-5 odnotowuje w §6.3.3 kilka różnic specyficznych dla R020), 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 klauzule wewnątrz specyfikacji okna, której ramką jest ROWS BETWEEN CURRENT ROW AND …: PATTERN opisuje wyrażenie regularne nad nazwanymi zmiennymi wzorca, DEFINE dostarcza predykat logiczny identyfikujący każdą zmienną, a opcjonalne AFTER MATCH SKIP (domyślnie PAST LAST ROW) 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; do 240 różnych zmiennych wzorca.
- Ramka okna
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGlubROWS BETWEEN CURRENT ROW ANDnFOLLOWINGz n ≥ 1 (19075-5 §6.10.2); każda inna ramka jest odrzucana, aEXCLUDE NO OTHERSto jedyne akceptowane wykluczenie.- 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. samoPrice) 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 jest ewaluowany 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. - Nazwy nawigacji
PREV,NEXT,FIRSTiLASTzapisane jako nieskwalifikowane wywołania wewnątrzDEFINEzawsze oznaczają nawigację; funkcja użytkownika o tej samej nazwie musi być tam kwalifikowana schematem.- Argumenty nawigacji
- Dla
PREV,NEXT,FIRSTiLASTwewnętrzny argument musi zawierać co najmniej jedno odwołanie do kolumny, a przesunięcie musi być stałą czasu wykonania. - 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 FIRST zmienna oraz AFTER MATCH SKIP TO [LAST] zmienna (samo SKIP TO zmienna oznacza SKIP TO LAST zmienna). One również zależą od historii dopasowania, ponieważ executor musi być w stanie wskazać wiersz odwzorowany na daną zmienną wewnątrz ostatniego dopasowania.
Pozostałe elementy stanowią heterogeniczny ogon: słowo kluczowe SEEK (alternatywa dla INITIAL), pusty wzorzec (), forma wykluczenia {- … -}, operator PERMUTE niewrażliwy na kolejność oraz funkcje agregujące i podzapytania w DEFINE, obecnie oba odrzucane (agregat kwalifikowany zmienną również potrzebowałby historii dopasowania).
- MEASURES
- Nazwane wyrażenia wyjściowe na dopasowanie, np.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; w R020 udostępniane przezOVERjak 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 wDEFINE,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.pricewDEFINElubMEASURES— 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 wierszu od bieżącego do końca pełnej ramki okna (w odróżnieniu od INITIAL).
- 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
ALL ROWS PER MATCH. Ta opcja nie dotyczy okien (19075-5 §6.3.3 (4)), więc w oknie składnia jest dozwolona (§6.13), lecz nie ma wyjścia, na które mogłaby działać. - Regex: ()
- Pusty wzorzec — dopasowuje pustą sekwencję.
- PERMUTE(...)
- Dopasowywanie niewrażliwe na kolejność dla wymienionych zmiennych. Słowo kluczowe jest rozpoznawane i odrzucane („PERMUTE is not supported");
permutepozostaje dopuszczalne jako nazwa zmiennej wzorca. - Funkcje agregujące w DEFINE
- Agregaty takie jak
SUM,AVG,COUNTnie są dozwolone w predykatachDEFINE. Standard dopuszcza je jako agregaty bieżące po częściowym dopasowaniu; agregat kwalifikowany zmienną, taki jakAVG(B.Price), zależy od tej samej historii dopasowania, której wymagająMEASURES/CLASSIFIER(), natomiast nieskwalifikowany obejmuje wszystkie dotychczasowe wiersze dopasowania. - Podzapytania w DEFINE
- Każde podzapytanie w
DEFINEjest odrzucane. Standard dopuszcza takie, które nie wykonuje row pattern recognition i nie odwołuje się do żadnej zmiennej wzorca wierszy; łatka na razie odrzuca więcej, niż trzeba.
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 (łatka idzie dalej i odrzuca wszystkie podzapytania w DEFINE, jak wymieniono powyżej); a RPR nie może być użyte wewnątrz zapytania rekurencyjnego. Łatka egzekwuje regułę odwołań zewnętrznych („cannot use outer query column in DEFINE clause") oraz regułę rekursji, tę drugą dla każdego elementu klauzuli WITH RECURSIVE. Odrzuca też funkcje ulotne (volatile) i odwołania do całego wiersza w DEFINE.
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 pięć omówionych przykładów: pojedyncze dopasowanie (ruch NFA), alternatywę, absorpcję kontekstu w łatwym przypadku i dwa przypadki, w których absorpcja jest wyłączona.
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 (domyślnie n = 1). Wgląd w przód; niespotykane w postaci okna, ponieważ okno jest monotoniczne.
- FIRST(expr [, n])
- Wiersz n wierszy po pierwszym wierszu bieżącego dopasowania (domyślnie n = 0, czyli sam pierwszy wiersz). „Porównaj do wiersza, który rozpoczął to dopasowanie."
- LAST(expr [, n])
- Wiersz n wierszy przed ostatnim dopasowanym wierszem (domyślnie n = 0). Wewnątrz
DEFINEostatnim dopasowanym wierszem jest wiersz bieżący, więcLAST(price)odczytuje wiersz bieżący.
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 wiersza, który odczytuje
FIRST(expr, n)(domyślnie n = 0, 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 wiersza, który odczytuje
FIRST(expr, n). 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 wiersza, który odczytuje
LAST(expr, n). „Porównaj do wiersza krótko przed najnowszym dopasowanym wierszem." - NEXT(LAST(expr [, n]) [, m])
- Przesuń się o m wierszy do przodu od wiersza, który odczytuje
LAST(expr, n).
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. Proste PREV i NEXT są relatywne względem bieżącego wiersza i są zawsze bezpieczne; FIRST i warianty LAST z przesunięciem, samodzielnie lub wewnątrz złożonego PREV/NEXT, są relatywne względem granic dopasowania, co wchodzi w interakcję z absorpcją kontekstu: planer wyłącza wtedy absorpcję dla całego wzorca. Mechanizm tej interakcji jest tematem §2.6.
2.3 Przykład 1 — ruch NFA
SKIP PAST LAST ROW, gdy tylko jego dopasowanie zostanie zapisane.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:
| Wiersz | Cena | Prawdziwe zmienne | Działanie |
|---|---|---|---|
| 0 | 100 | START | Nowy kontekst. START dopasowuje się i natychmiast wychodzi (max=1); stan przechodzi do UP+. |
| 1 | 110 | START, UP | UP dopasowuje się. Rozwidlenie: jeden stan zapętla się przy UP, inny wychodzi do DOWN+. |
| 2 | 120 | START, UP | UP dopasowuje się w zapętlonym stanie i znów się rozwidla. Stan DOWN z wiersza 1 ginie (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP zawodzi w zapętlonym stanie i ginie. Stan DOWN z wiersza 2 dopasowuje się. Rozwidlenie: pętla przy DOWN i wyjście do #FIN — zapisany zostaje kandydat dopasowania obejmujący wiersze 0–3. |
| 4 | 108 | START, DOWN | DOWN dopasowuje się w zapętlonym stanie i znów się rozwidla; nowy kandydat FIN obejmujący wiersze 0–4 zastępuje krótszy. |
| 5 | 130 | START, UP | Zapętlony stan DOWN zawodzi (130 ≮ 108). Gdy w tym kontekście nie pozostał żaden aktywny stan, zapisany kandydat (wiersze 0–4) zostaje sfinalizowany jako dopasowanie. Następna próba startuje od wiersza 5; START się dopasowuje, ale partycja kończy się przed jakimkolwiek UP. |
Kluczowy punkt: w wierszu 3 wiersz spełnia zarówno START (zawsze prawdziwy), jak i DOWN, ale START ma znaczenie tylko dla kontekstu startującego w wierszu 3; w tym kontekście zapętlony stan UP ginie i przechodzi dalej jedynie stan czekający przy 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 ostatni kandydat FIN (wiersze 0–4) — wytworzony, gdy DOWN wyszedł w wierszu 4, w miejsce kandydata z wiersza 3 — 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 | Cena | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 w kolejności wzorca, wcześniejszą gałąź najpierw.
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. Oba następnie przechodzą do DONE, gdzie się spotykają.
| Wiersz | Prawdziwe zmienne | Aktywne stany |
|---|---|---|
| R | UP, HIGH | Stan A (gałąź UP) i stan B (gałąź HIGH) przechodzą do DONE z tymi samymi licznikami; B jest duplikatem A i zostaje odrzucony |
| R+1 | DONE | Stan A dopasowuje DONE i osiąga #FIN |
W kategoriach standardu obie gałęzie wytwarzają dopasowanie tej samej długości na tych samych wierszach, dając dwie kandydujące ścieżki — 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. Executor egzekwuje to w wierszu R, a nie przy FIN: najpierw dodaje stan z gałęzi UP, więc nfa_append_state_unique() go zachowuje i odrzuca identyczny stan z gałęzi HIGH.
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):
| Wiersz | Konteksty naiwne | Z absorpcją |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 wchłonięte |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | pięć kontekstów | C1[A:5] |
Liczba aktywnych kontekstów spada z O(n) do O(1), więc suma po partycji spada z O(n²) do O(n). 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ą:
| Dzień | Cena | C1 — start wt. price > PREV(price) | C2 — start śr. price > PREV(price) |
|---|---|---|---|
| pon. | $100 | — | — |
| wt. | $108 | $108 > $100 ✓ (dopiero co wystartował) | — |
| śr. | $112 | $112 > $108 ✓ | $112 > $108 ✓ (dopiero co wystartował) |
| czw. | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| pt. | $110 | $110 > $116 ✗ — finalizacja | $110 > $116 ✗ — finalizacja |
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
DEFINE odwołuje się do FIRST — reguła absorpcji już nie obowiązuje, a planer wyłącza absorpcję dla wzorca.
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+).
| Dzień | Cena | C1 — start pon. FIRST = $100 price < $100 + 10 | C2 — start wt. FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| pon. | $100 | $100 < $110 ✓ | — |
| wt. | $108 | $108 < $110 ✓ | $108 < $118 ✓ (dopiero co wystartował) |
| śr. | $112 | $112 < $110 ✗ — finalizacja pon.–wt. | $112 < $118 ✓ |
| czw. | $116 | — | $116 < $118 ✓ |
| pt. | $110 | — | $110 < $118 ✓ (wciąż trwa) |
Przy absorpcji C2 zostałoby wchłonięte do C1 we wtorek — scalony kontekst trzyma tylko pułap C1 ($110), więc odrębne ujęcie C2 (pułap $118, czterodniowa seria do piątku) nie jest pokryte przez przyszłość C1. W tym konkretnym tygodniu wyjście akurat się nie zmienia: C1 zapisuje pon.–wt., C2 wystartowało wewnątrz tego dopasowania i zostaje odrzucone przez SKIP PAST LAST ROW, a kolejna próba startuje w środę z własnym pułapem ($122) i dopasowuje śr.–pt. Ogólnie jednak wynik DEFINE wcześniejszego kontekstu nie obejmuje już wyniku późniejszego, więc porównanie liczników, na którym opiera się absorpcja, jest nieważne. 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.)
Poniższa tabela rozszerza prawy dolny panel posteru („② Navigation") o formy złożone i podsumowuje, które formy nawigacji tworzą zależność od początku dopasowania:
| Nawigacja | Zależność od startu | Absorbowalna? |
|---|---|---|
| PREV, NEXT | brak | tak |
| LAST (bez przesunięcia) | brak | tak |
| LAST z przesunięciem | kontrola granicy | nie |
| FIRST (dowolne) | bezpośrednia | nie |
| Złożona (wewnętrzne FIRST) | bezpośrednia | nie |
| Złożona (wewnętrzne LAST, bez przesunięcia) | brak | tak |
| Złożona (wewnętrzne LAST z przesunięciem) | kontrola granicy | nie |
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 ma zagwarantowanego pokrycia, więc nie da się już wykazać, że odrzucenie któregoś jest bezpieczne.
Planer wykrywa to rozróżnienie podczas kompilacji i włącza lub wyłącza absorpcję dla całego wzorca; gdy jest wyłączona, runtime ponosi koszt wielokontekstowy. Benchmark posteru w panelu ③ nie używa FIRST, więc absorpcja pozostaje włączona — i dlatego PostgreSQL pozostaje liniowy zarówno w przypadkach sukcesu, jak i porażki.
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ę z grubsza O(n) po potwierdzeniu dopasowania, a PostgreSQL prowadzi z grubsza 16× do 33× (wyniki Trino już nie obejmują startu JVM).
Na wzorcu porażki (A+ B+ C+ E) Trino, które najwyraźniej nie ma absorpcji, goni za każdym potencjalnym początkiem dopasowania i degraduje się nawet szybciej niż O(n²) (około 56× więcej czasu przy 5× więcej wierszy); 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.
| Wiersz | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | start dopasowania; wiersze 0–4 będą jedynym dopasowaniem | start dopasowania w wierszu 0 |
| 1 | (wewnątrz dopasowania 0) | start dopasowania w wierszu 1 — musi być utrzymany |
| 2 | (wewnątrz dopasowania 0) | start dopasowania w wierszu 2 — musi być utrzymany |
| 3 | (wewnątrz dopasowania 0) | start dopasowania w wierszu 3 — musi być utrzymany |
| 4 | finalizacja dopasowania 0 (wiersze 0–4) | finalizuje się pięć dopasowań: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW każdy późno-startujący kontekst stanowi własny wiersz wyjścia. Dwa konteksty w tym samym elemencie wzorca nie są już redundantne — oba są wymaganymi wyjściami, a odrzucenie jednego po cichu pominęłoby dopasowanie, o które prosił użytkownik.
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 dwa sposoby, na jakie semantyka zapytania wyklucza absorpcję:
FIRST lub LAST z przesunięciem w DEFINE.AFTER MATCH SKIP TO NEXT ROW.
Każdy z tych warunków wystarczy, by wyłączyć absorpcję dla całego wzorca; podobnie działa ramka, która nie kończy się na UNBOUNDED FOLLOWING. Gdy żaden nie obowiązuje — domyślne AFTER MATCH SKIP PAST LAST ROW, nieograniczony koniec ramki i warunki DEFINE używające wyłącznie PREV, NEXT lub samego LAST — absorpcja jest włączona, ale tylko dla stanów w regionie absorbowalnym wzorca: wiodącej nieograniczonej zmiennej greedy, takiej jak A+ lub A*, grupy o stałej długości z nieograniczonym kwantyfikatorem greedy, takiej jak (A B)+, grupy greedy, której ciało zaczyna się od jednej z nich, takiej jak (A+ B)+ lub (A+ B){2}, albo gałęzi alternatywy zbudowanych z powyższych; grupa leniwa dyskwalifikuje całe swoje poddrzewo. Tam, gdzie to zachodzi, jak dla A+ w §2.5, runtime zwija się do jednego kontekstu i pozostaje liniowy; START UP+ DOWN+ z §2.3 nie ma żadnego regionu absorbowalnego.
§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 pracę 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, granica końcowa musi być UNBOUNDED FOLLOWING lub dodatnim przesunięciem FOLLOWING (więc ramka domyślna również jest odrzucana), a opcje EXCLUDE inne niż EXCLUDE NO OTHERS 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:
| Źródło | Kodowanie w drzewie |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
Każdy predykat DEFINE zostaje następnie sprawdzony typowo względem kolumn partycji i sprowadzony do wyrażenia Boolowskiego. Wynikają z tego dwie praktyczne rzeczy. Po pierwsze, analiza parsowania nie dodaje niczego do listy docelowej zapytania dla DEFINE; zamiast tego planer oznacza jako potrzebną każdą kolumnę, do której odwołuje się predykat DEFINE, tak jak robi to dla HAVING, i 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 dziewięć reguł przepisywania w jednym przejściu od dołu do góry (wewnątrz sekwencji scalanie grup uruchamiane jest jeszcze raz, ponieważ wcześniejsze scalenia mogą zestawić obok siebie dwie identyczne grupy):
- 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}- Scalanie 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 - Normalizacja leniwości
A{2}?→A{2}(leniwość jest usuwana wszędzie tam, gdzie min = max)
Mnożenie kwantyfikatorów zwija tylko wtedy, gdy osiągalne liczniki tworzą jeden ciągły przedział, a preferowane dopasowanie się nie przesuwa: dokładny zewnętrzny ((A{2,3}){5} → A{10,15}), dziecko z min 0 lub przedziały dziecka, które się stykają, przy min dziecka co najwyżej 1 lub nieograniczonym max dziecka ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), przy czym zewnętrzny z min 0 również wymaga min dziecka co najwyżej 1 ((A{2,})* pozostaje, ponieważ A* akceptowałoby jeden wiersz). Dziecko będące grupą, którego własny kwantyfikator nie jest dokładny, musi najpierw mieć ciało o stałej długości, więc ((A | B B){1,2}){2} pozostaje nietknięte nawet przy dokładnym zewnętrznym. 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 — lub przesuwać preferowane dopasowanie ((A{2,3}){1,2} preferuje trzy wiersze tam, gdzie A{2,6} bierze cztery), więc optymalizator pozostawia je nietknięte. Nie jest to jedyne warunkowe przepisanie: scalanie grup i scalanie przyrostka wymagają ciała konsumującego stałą liczbę wierszy, scalanie przedrostka odrzuca grupę z min 0, skończonym max i zawartością nullable, węzły leniwe nie są ani scalane, ani mnożone ((A+?)+ pozostaje), a przepisanie, którego nowe ograniczenie przepełniłoby się, jest odrzucane.
Kształt elementu
Każdy element płaskiej tablicy reprezentuje jedną pozycję we wzorcu. Istnieje sześć 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; separator gałęzi kończący każdą gałąź; 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 znacznik alternatywy i separatory gałęzi do łączenia gałęzi, przez group begin do wskazania własnego group end — grupa, której kwantyfikator dopuszcza zero, jest omijana przez next tego enda — 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 → 3
(otwiera grupę; jump wskazuje
jej własny END)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(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 wskazuje jego END w idx 3, a gdyby grupa była opcjonalna, pominięcie wyszłoby przez next tego END-a do idx 4, nie docierając do END-a. 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 pięć atrybutów logicznych kierujących 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? B?)+,(A | B*)+;(A?)*jest najpierw mnożone doA*i nie pozostawia enda grupy). Mówi runtime'owi, by poniżej min dodał szybkie wyjście obok zwykłego nawrotu, aby zabezpieczenie cyklu nie zabijało prawowitych dopasowań w grupach mogących produkować puste iteracje. - Preferujący pusto
- Ustawiany na endach grup, których ciało preferuje puste dopasowanie, jak w
(A?? B??){2}. Poniżej min ustawia szybkie wyjście przed nawrotem, gdzie własna zachłanność grupy nic nie rozstrzyga. - 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ź płaską tablicę od
elementu 0 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 dopuszcza cztery kształty strukturalne:
- Przypadek 1 — prosta zmienna nieograniczona
-
Każda iteracja to dokładnie jeden wiersz. Licznik wcześniejszego kontekstu jest zawsze ≥ od późniejszego w każdej dzielonej pozycji.
A+,A*,A{2,∞} - Przypadek 2 — grupa o stałej długości, zewnętrzna nieograniczona
-
Każde dziecko ma
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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 A otrzymuje obie flagi, otaczający BEGIN otrzymuje flagę w-regionie, a B i END nie otrzymują żadnej.
(A+ B)+,(A+ B){2} - Przypadek 4 — alternatywa
-
Każda gałąź, osiągana przez łańcuch separatorów, oceniana jest samodzielnie według powyższych przypadków; znacznik alternatywy otrzymuje flagę w-regionie, gdy kwalifikuje się którakolwiek gałąź.
A+ | B+,A+ | C D
Przypadki strukturalne nieobjęte tymi czterema 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. 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
if targetPos != currentPos:
pobierz wiersz w targetPos
do nav_slot
wskaż zewnętrznym slotem nav_slot
result = eval_inner_expression()
przywróć current_row_slot
skopiuj wynik by-ref z nav_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 i bez slotu na każde odwołanie; gdy celem jest bieżący wiersz, pobranie i wymiana są całkowicie pomijane. Pobranie kopiuje docelowy wiersz do slotu nawigacji (chyba że slot już go zawiera), a krok przywracania kopiuje wynik przekazywany przez referencję do pamięci per-krotkowej, by następne pobranie nie mogło go zwolnić.
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 currentPos − 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 (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − 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 absorpcja kontekstu jest w ogóle możliwa (§2.5 vs §2.6): pojedyncza zmienna zależna od początku dopasowania wyłącza ją dla całego wzorca.
- Brak nawigacji
- Wyłącznie
PREV/NEXT LASTbez przesunięcia- Złożone z wewnętrznym
LAST(bez przesunięcia)
LASTz przesunięciemFIRST(dowolna forma)- Złożone z wewnętrznym
FIRST - Złożone z wewnętrznym
LAST(z przesunięciem)
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. Executor ustala to na podstawie dwóch komplementarnych przesunięć, rozwiązując każde przesunięcie raz na skan (stałe także przy inicjalizacji executora, by zwykły EXPLAIN mógł je pokazać):
- Budżet wsteczny
- Jak daleko wstecz od bieżącego wiersza może sięgnąć dowolne wywołanie DEFINE.
- Budżet wyprzedzenia od początku
- Minimalny zasięg w przód (wstecz, gdy ujemny) od początku dopasowania najstarszego aktywnego kontekstu — najwcześniejszy wiersz, którego może potrzebować dowolne wywołanie DEFINE.
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ć. Wiersze Nav Mark, które raportuje EXPLAIN (§3.7) — Lookback i Lookahead — to te dwa budżety, a nie zmierzone szczyty. Każdy jest wypisywany tylko wtedy, gdy zasila go jakaś nawigacja, i jest pokazywany nawet bez ANALYZE; przesunięcie, którego wartość znana jest dopiero w czasie wykonania (np. parametr planu generycznego), wypisywane jest jako runtime w zwykłym EXPLAIN i jako rozwiązana wartość w EXPLAIN ANALYZE, a retain all (Lookback) lub infinite (Lookahead) oznacza przesunięcie, które się przepełnia.
3.4 Granice dopasowania — SKIP, INITIAL i ramka ograniczona
Wynik dopasowania zapisywany jest jako dwie wartości: wiersz, w którym zaczyna się dopasowanie, oraz jego długość. Ujemny początek oznacza, że pozycja nie została jeszcze ewaluowana; gdy początek jest ustawiony, kolejne zapytania do executora — „czy ten wiersz jest wewnątrz dopasowania?" — mogą odpowiedzieć w O(1), inspekcjonując tę parę. Długość koduje wynik: -1 dla niedopasowanego wiersza, 0 dla pustego dopasowania i liczbę wierszy dla rzeczywistego dopasowania. Długość zero jest rzeczywistym wynikiem, nie błędem: reprezentuje wzorzec dopasowany bez skonsumowania jakiegokolwiek wiersza, co executor musi odróżnić zarówno od niedopasowanego wiersza, jak i 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 wzorca tego okna, 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, a następnie napędza NFA naprzód wiersz po wierszu — resetując dla każdego wiersza tablicę dopasowań per zmienna do stanu „nieewaluowane" — aż ten kontekst nie ma już aktywnych stanów lub partycja się kończy. Predykaty DEFINE ewaluowane są leniwie: zmienna jest ewaluowana za pierwszym razem, gdy jakiś stan ją konsumuje, więc zmienna, której żaden aktywny stan nie testuje w tym wierszu, nigdy nie jest ewaluowana. 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 osiągnął koniec swojej ramki:
wymuś niedopasowanie (wczesna finalizacja)
continue
if matchStartRow różni się od
wspólnej pozycji ewaluacji:
zresetuj zmienne DEFINE zależne od
początku dopasowania do nieewaluowanych (§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)
if zapisał dopasowanie i
SKIP PAST LAST ROW:
przytnij późniejsze konteksty
startujące wewnątrz dopasowania
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]
assert elem jest zmienną
# advance parkuje tylko zmienne
if varMatched[elem.varId] jest
nieewaluowane:
ewaluuj teraz jej DEFINE
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
lub trzyma zapisane dopasowanie:
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), dopóki kontekst nie zapisze dopasowania, co przypina go do false — wchłonięcie zwolniłoby dopasowanie, którego żaden wchłaniający kontekst nie może odtworzyć. 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
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, kończąc,
gdy FIN zostanie zapisany),
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 oznacz
kontekst, by późniejsze konteksty
wewnątrz zakresu tego kandydata
zostały przycięte — 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 gdy Advance skończy z kontekstem, który zapisał kandydata, każdy kolejny kontekst, którego wiersz startu mieści się wewnątrz zakresu kandydata, jest przycinany w tym samym wierszu, 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 międzykontekstowy krok przycinania w czasie FIN. Wewnątrz kontekstu FIN również odcina leksykalnie gorszą pracę: Advance odrzuca pozostałe stany w kolejce (opisane wcześniej w tej sekcji), a w obrębie jednego DFS każda mniej preferowana ścieżka — późniejsze gałęzie ALT, druga z dwóch ścieżek BEGIN (pominięcia i wejścia), ścieżka wejścia zmiennej leniwej, druga z dwóch ścieżek END (pętli i wyjścia) — zatrzymuje się, gdy dopasowanie zostanie zapisane, więc jeden advance zapisuje najwyżej jedno dopasowanie.
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
(najpierw fast-forward, jeśli
ciało preferuje puste; druga
ścieżka jest porzucana, jeśli
pierwsza osiągnęła FIN)
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
if pętla osiągnęła FIN:
porzuć wyjście
# preferuj dłuższe
else wyjście jako drugie
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? 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. (Pojedyncze opcjonalne dziecko, jak (A?)*, jest przepisywane na A* w czasie kompilacji i nie pozostawia grupy.) 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 ciała (jego jump to pierwsze dziecko grupy), ciało znów produkuje puste dopasowanie, ponownie osiąga END, i tak dalej. Bez czegoś, co by to zatrzymało, DFS Advance nigdy by nie zakończył.
Zabezpieczenie decydowane jest w czasie kompilacji i wykonywane w czasie wykonania. Gdy planer widzi grupę o ciele nullable, taguje element END tej grupy jako empty-loopable. Runtime utrzymuje bitmapę odwiedzonych, czyszczoną przed rozszerzaniem DFS każdego stanu, w której oznaczane są wyłącznie te otagowane END-y — nic innego nie może tworzyć cyklu, ponieważ każdy inny nawrót skonsumował wiersz. Osiągnięcie oznaczonego END oznacza, że ciało właśnie wyprowadziło pustą iterację, a stan nie jest odrzucany: na lub powyżej dolnej granicy opuszcza tam grupę (pusta iteracja zatrzymuje kwantyfikator), a poniżej niej stan przechodzi do normalnego nawrotu, więc każde puste dotarcie wciąż podnosi licznik, aż osiągnie min. Weźmy (A? B?){2,3} bez żadnej ze zmiennych dopasowującej się gdziekolwiek w strumieniu wierszy:
iter 1: A? B? dopasowują zero wierszy
→ END, count = 1 (poniżej min)
END już oznaczony (przy wejściu
do grupy), ale poniżej min:
→ pętla wstecz do A?
iter 2: A? B? dopasowują zero wierszy
→ END, count = 2 (spełnia min)
END już oznaczony, na min:
→ opuść grupę
wyjście z dopasowaniem o długości zero
Poniżej dolnej granicy tag empty-loop mówi też handlerowi END, by sklonował dodatkowy stan fast-forward obok normalnej ścieżki pętli wstecznej:
advance_end (count poniżej min):
ścieżka pętli wstecznej:
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. Pętla wsteczna łapie przypadek, gdzie ciało wciąż ma realne dopasowania do wyprodukowania później — np. w (A? B?){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 od razu wychodzi z grupy, deklarując „pozostałe wymagane iteracje są puste", i pozwala dopasowaniu się powieść z ciałem o długości zero. O kolejności decyduje ciało, a nie własna zachłanność grupy: fast-forward idzie pierwszy dokładnie wtedy, gdy ciało preferuje puste dopasowanie (ciało leniwe, takie jak (A?? B??)), a jeśli pierwsza ścieżka osiągnie FIN, druga jest porzucana, więc mniej preferowana ścieżka nie może zastąpić preferowanego dopasowania. 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
Utrzymanie runtime'u w ograniczeniach 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 znajduje się w punkcie porównania i jest pokryty przez absorbowalny stan starszego kontekstu w tym samym elemencie z licznikiem większym lub równym — 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) Advance
- 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 to wyszukiwanie się skończy, i jest przycinany, gdy tylko Advance skończy z kontekstem, który zapisał kandydata. - Guard cyklu Advance
- Rozszerzania epsilon docierające do END grupy nullable już oznaczonego w tym samym DFS (oznaczonego przy wejściu przez BEGIN lub przy wcześniejszym dotarciu) — w przeciwnym razie pętlowałyby w nieskończoność; na lub powyżej dolnej granicy stan opuszcza tam grupę, a poniżej niej pętluje dalej.
- Fast-forward pustej pętli Advance
- Poniżej dolnej granicy grupy nullable — dodatkowa ścieżka wychodząca z grupy z pozostałymi wymaganymi iteracjami zadeklarowanymi jako puste, uporządkowana względem pętli wstecznej według preferencji ciała.
- 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). 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 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ą. Źródło dokumentuje przypadki, których warstwy nie łapią: deduplikacja zachowuje osobno stany różniące się jedynie licznikami powyżej min, więc (A{2,} B)+ C przy C nigdy niespełnionym trzyma w szczycie Θ(n²) stanów i tworzy ich Θ(n³) (37 s na 320 wierszach), a ciąg alternatyw złożonych wyłącznie z elementów nullable wyliczany jest ścieżka po ścieżce, więc (A?|B?){30} zajmuje ponad pół godziny.
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. W formacie tekstowym emitowane są obok operatora okna, po linii Pattern:, ewentualnych liniach Nav Mark (które pokazuje też zwykły EXPLAIN) i linii Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(każda tylko wtedy, gdy DEFINE używa
nawigacji, która ją zasila)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
N skipped (len min/max/avg)
(druga linia NFA tylko wtedy, gdy
któryś licznik jest niezerowy; zerowy
licznik drukuje się bez swojego (len ...))
Formaty inne niż tekstowy emitują każdy licznik jako osobną właściwość. 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ę; pruned liczy konteksty, które zawiodły po jednym wierszu. Histogramy długości dopasowania rozdzielają cztery wyniki — udane dopasowania, próby dopasowania, które zawiodły po więcej niż jednym wierszu (mismatched), wchłonięte konteksty oraz konteksty zwolnione przez AFTER MATCH SKIP PAST LAST ROW, ponieważ wystartowały wewnątrz zapisanego dopasowania (skipped) — 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, który §3.3 wywodzi z DEFINE. Lookback to najgłębsze sięgnięcie wstecz od bieżącego wiersza przez PREV, LAST z dowolnym przesunięciem (w tym domyślnym 0) i formy złożone z wewnętrznym LAST; Lookahead to minimalny zasięg w przód (ujemny, gdy sięga przed początek dopasowania) mierzony 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 znanym dopiero dla danego skanu, i — tylko dla Lookback — „retain all", gdy przesunięcie się przepełnia; Lookahead, który się przepełnia, drukuje się jako „infinite". Każda linia emitowana jest tylko wtedy, gdy zasila ją jakaś nawigacja w DEFINE, i obie pojawiają się też w zwykłym EXPLAIN: stałe przesunięcia ustalane są przy inicjalizacji executora, natomiast przesunięcie znane dopiero w czasie wykonania (np. parametr planu generycznego) drukuje się tam jako „runtime", a jako rozwiązana liczba całkowita w EXPLAIN ANALYZE.
Razem te liczniki pozwalają debugować wydajność RPR bez podłączania gdb do backendu.
Poza licznikami EXPLAIN drukuje linię Pattern: zbudowaną ze skompilowanej tablicy elementów, więc pokazuje wzorzec po przepisaniach czasu kompilacji (PATTERN (A A) wyjaśnia się jako a{2}) i niesie znaczniki absorpcji # (punkt porównania) i ~ (region absorbowalny); DEFINE ani opcja AFTER MATCH SKIP nie są pokazywane. Odtwarzanie klauzul w zapisanej postaci, w tym kwantyfikatorów leniwych, powtarzania grup i opcji pominięcia, to zadanie pg_get_viewdef(), które 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 22 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
- Integracja z klauzulą WINDOW — realistyczne scenariusze okienne na syntetycznych danych giełdowych (kształt V, kształt W, kolejne wzrosty, odwrócenia), a także semantyka nawigacji i błędy ograniczeń DEFINE.
- 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; do tego warstwa planera — optymalizacja wzorca, flagi absorpcji, wycofanie optymalizacji, integracja z planerem.
- 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. Te scenariusze to jedyne testy, których wejścia i wyjścia czytają się jak zapytania, które użytkownik mógłby faktycznie napisać; reszta pliku, podobnie jak pozostałe pakiety, jest redukcyjna — zagnieżdżanie PREV/NEXT i błędy niestałych przesunięć, reguły odwołań DEFINE oraz semantyka przesunięć nawigacji.
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. Druga część, warstwa planera, pokrywa optymalizację wzorca, wyświetlanie i analizę flag absorpcji, wycofanie optymalizacji oraz integrację z planerem (podzapytania, złączenia, operacje na zbiorach, sortowanie i grupowanie).
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. Defekty takie jak 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: wiersze inline VALUES niosące tablicę nazw zmiennych, która deklaruje, które zmienne DEFINE dopasowują się w każdym wierszu, sparowane ze wzorcem badającym konkretne zachowanie runtime'u. Idiom tablicowy 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ąceA+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 (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) pojawiają się pod
EXPLAIN ANALYZEw formacie tekstowym, JSON i XML z udokumentowanymi etykietami, a Nav Mark Lookback i Lookahead pojawiają się dokładnie wtedy, gdy zasila je nawigacja w DEFINE. - 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, jak każda z tych optymalizacji traktuje okna RPR — większość musi być wyłączona lub omijana:
- Kanonizacja ramki
- Planer normalnie przepisuje
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGnaROWS UNBOUNDED PRECEDINGdla funkcji okna niezależnych od ramki, takich jakrow_number,rankintile. Ramka RPR to rozpięcie dopasowania, nie okno agregacyjne, i musi pozostać dosłowna. - Pushdown warunków serii
- Monotoniczny filtr
WHEREna 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 BYi 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 lub SKIP)
- Dwa okna RPR z tym samym
PATTERN, lecz różnymi klauzulamiDEFINElub innymAFTER MATCH SKIP, produkują różne dopasowania i muszą pozostać odrębne, nawet jeśli ich kształt strukturalny jest identyczny. - Projekcja nieużywanego wyjścia
- Ta optymalizacja może zostać zastosowana: gdy otaczające zapytanie nigdy nie czyta wyjścia okna, funkcja okna staje się NULL, a jej WindowAgg zostaje usunięty, bez zmiany liczby wierszy. Testy sprawdzają, że kolumny czytane przez DEFINE wciąż docierają do WindowAgg, gdy ten pozostaje, oraz że okno jest zachowywane, gdy jego wartość jest czytana.
- 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.
Dalsze przypadki sprawdzają, że szacowanie kosztu uwzględnia DEFINE, że podzapytanie zawierające okno RPR nie jest spłaszczane, że wyrażenia DEFINE nie przeciekają do wyższego WindowAgg oraz że LIMIT pozostaje nad WindowAgg; druga grupa uruchamia RPR razem z CTE, złączeniami, operacjami na zbiorach, przygotowanymi instrukcjami, tabelami partycjonowanymi i podobnymi konstrukcjami. Większość zabezpieczonych przypadków ma ten sam kształt: linia bazowa wyzwalająca optymalizację (zwykle zapytanie nie-RPR, sprawdzane w EXPLAIN), a następnie zapytanie RPR strukturalnie podobnego kształtu, w którym optymalizacja nie jest stosowana — dla przypadku deduplikacji DEFINE/SKIP linią bazową są dwa identyczne okna RPR, a przypadek tranzycji odwrotnej sprawdza ominięcie agregatem logującym, a nie przez EXPLAIN. 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.