Row Pattern Recognition Derinlemesine İnceleme
PostgreSQL'de ISO/IEC 19075-5 · SQL R020 üzerinden rehberli bir tur — ne inşa ettiğimiz, hâlâ yazılmamış olanlar ve gerçekte nasıl çalıştığı.
Standardı hızlıca tarayın, uygulamalı örneklerden geçin, tasarıma göz atın ve ardından kendi örüntülerinizle canlı bir NFA simülatörünü çalıştırın.
Tartışma: pgsql-hackers ileti dizisi · en son yama (v55) · commitfest #4460.
Yapay zekâ ön çevirisi — hata olabilir.
§1. Standart, Alt Küme ve Açık Sorular
1.1 Standart kapsamı
Satır Örüntü Tanıma, SQL'e ISO/IEC 9075-2:2016 ile dahil edilmiş ve tamamlayıcı belge olan ISO/IEC 19075-5:2021'de (Bölüm 5, "Row Pattern Recognition") açıklanmıştır.
Standart, aynı temel mekanizma için iki yüzey tanımlar. R010 özelliği, türetilmiş bir tablo üretmek için FROM listesine bir MATCH_RECOGNIZE yan tümcesi yerleştirir; R020 özelliği ise aynı örüntü mantığını pencere işlevi çıktısı üretmek üzere bir WINDOW belirtimine katlar. İki yüzeyin sözdizimi ve anlamlarının önemli bir kısmı ortaktır (19075-5, R020'ye özgü birkaç farkı §6.3.3'te belirtir), ancak işlevsel olarak farklı giriş noktalarıdır — bir veritabanı bunlardan birini veya her ikisini birden uygulayabilir.
Burada ele alınan yama serisi yalnızca R020'nin bir alt kümesini gerçekler; tablo yan tümcesi biçimi bilinçli olarak kapsam dışıdır.
R020 yüzeyi küçük ama anlatım gücü yüksektir. Bir sorgu, çerçevesi ROWS BETWEEN CURRENT ROW AND … olan bir pencere belirtimi içine yan tümceler ekleyerek pencereye bir örüntü iliştirir: PATTERN, adlandırılmış örüntü değişkenleri üzerinde bir düzenli ifade tanımlar; DEFINE, her değişkeni belirleyen Boole yüklemini sağlar; isteğe bağlı AFTER MATCH SKIP (varsayılan PAST LAST ROW) ise ardışık eşleşmelerin bölüm içinde nasıl konumlandırılacağını denetler.
İsteğe bağlı MEASURES, SUBSET, INITIAL/SEEK ve yardımcı CLASSIFIER() işlevi özelliği tamamlar. (Standardın MATCH_NUMBER() işlevi yalnızca R010 yüzeyine aittir — 19075-5 §6.3.3 (6) bunu R020'den açıkça hariç tutar.)
Yama, bu sözcük dağarcığını önemsiz olmayan sorguları çalıştırmaya yetecek kadar kapsar; ancak gerçeklenmesi henüz inşa edilmemiş altyapıya bağlı olan birkaç yapı için durur.
Bu bölümün geri kalanı, standardın sözcük dağarcığını yamanın halihazırda desteklediği ve bilinçli olarak sonraya bıraktığı şeyler olarak ikiye ayırır. Aşağıdaki listeler yama serisinin mevcut durumunu yansıtır.
1.2 Gerçeklenen özellikler
Gerçeklenen sözcük dağarcığı, en başta satır örüntü tanımayı motive eden kanonik V şekli, W şekli ve tersine çevirme örüntülerini ifade etmek için yeterlidir. Ayrıca tüm standart niceleyicileri — yedi gönülsüz değişkenin tamamı dahil *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — ve DEFINE koşullarının komşu satırları karşılaştırması için ihtiyaç duyduğu dört gezinme ilkesi de kapsanır.
- PATTERN yan tümcesi
- Bir pencere belirtimi içinde satır örüntüsünü tanımlar; en fazla 240 farklı örüntü değişkeni.
- Pencere çerçevesi
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGveya n ≥ 1 olmak üzereROWS BETWEEN CURRENT ROW ANDnFOLLOWING(19075-5 §6.10.2); diğer her çerçeve reddedilir ve kabul edilen tek dışlamaEXCLUDE NO OTHERS'tır.- Regex: + * ? |
- Standart niceleyiciler ve seçenek (alternation).
- Regex: ( ) gruplama
- Parantezli alt örüntüler.
- Regex: {n} {n,} {,m} {n,m}
- Sınırlı tekrar sayıları.
- Gönülsüz *? +? ?? {n}? {n,}? {,m}? {n,m}?
- Standardın tanımladığı yedi gönülsüz (non-greedy) varyantın tamamı (absorption optimizasyonundan hariç tutulmuştur).
- DEFINE yan tümcesi
- Her örüntü değişkenini belirleyen Boole koşulları.
- Evrensel satır örüntüsü değişkeni
DEFINEiçinde nitelendirilmemiş sütun referansları (ör. yalınPrice) geçerli satıra çözümlenir, 19075-5 §4.10/§4.16'ya göre.- PREV, NEXT (ofset ile)
- Geçerli satırdan n satır önceye/sonraya erişir (varsayılan 1); içteki argüman gezilen satırda değerlendirilir.
- FIRST, LAST (ofset ile)
- Eşleşmeye göreli bir satıra erişir;
FIRST(expr, n), eşleşmenin başlangıcından n sonraki satırı;LAST(expr, n)ise en son eşleşme satırından n önceki satırı hedefler. - Bileşik gezinme (dört biçim)
- Bir iç FIRST/LAST üzerine katmanlanmış dış PREV/NEXT adımı:
PREV(FIRST(expr)),NEXT(FIRST(expr)),PREV(LAST(expr)),NEXT(LAST(expr))— hem iç hem dış adım kendi ofsetini kabul eder. - Gezinme adları
DEFINEiçinde nitelendirilmemiş çağrı olarak yazılanPREV,NEXT,FIRSTveLASTher zaman gezinme anlamına gelir; aynı adlı bir kullanıcı işlevi orada şemayla nitelendirilmelidir.- Gezinme argümanları
PREV,NEXT,FIRSTveLASTiçin içteki argüman en az bir sütun referansı içermeli ve ofset bir çalışma zamanı sabiti olmalıdır.- INITIAL
- Örüntü eşleşmeleri geçerli satırdan başlamak zorundadır (varsayılan).
- AFTER MATCH SKIP PAST LAST ROW
- Varsayılan atlama modu; bağlam emilimine uygundur.
- AFTER MATCH SKIP TO NEXT ROW
- Örtüşen eşleşmelere izin verir; emilimi devre dışı bırakır.
1.3 Gerçeklenmemiş
Gerçeklenmemiş kalan özellikler üç gevşek gruba ayrılır. Birincisi — açık ara en büyüğü — MEASURES etrafında kümelenen yapılar ailesidir: MEASURES yan tümcesinin kendisi, SUBSET, CLASSIFIER(), B.price gibi örüntüyle nitelenmiş sütun referansları ve LAST(B.price) ya da PREV(B.price) gibi örüntüyle nitelenmiş gezinme.
Bunlar bağımsız boşluklar olmaktan çok, tek bir eksik parçanın farklı görünümleridir: yürütücünün eşleşme başına bir tarihçe — eşleşmedeki her satır için, o satırın hangi örüntü değişkenine eşlendiğini gösteren bir kayıt — tutması gerekirdi ve bu yapıların hiçbirinin bu olmadan anlamlı bir tanımı yoktur. CLASSIFIER() bu kayıttan değişken adını okur; B.price, kayıt girdisi B diyen satırların price sütununu okur; LAST(B.price) aynı satır kümesini gezerek sonuncusunu seçer; SUBSET U = (A, B) her iki bucket üzerinde toplulaştırma yapan sanal bir değişken tanımlar; MEASURES ise tam da bu toplulaştırmayı kullanarak AVG(U.Price) gibi ifadeleri değerlendirir.
Mevcut yürütücü, DEFINE yüklemlerini satır satır değerlendirir ama ortaya çıkan değişken atamalarını hiçbir yere kaydetmez — sonradan sorgulanacak hiçbir şey yoktur. Bu nedenle tarihçe altyapısının inşası tüm grup için ön koşuldur; kayıtlar var olduğunda ayrı özellikler küçük projeksiyonlar olarak ortaya çıkar.
İkinci gruplama alternatif atlama hedefleriyle ilgilidir: AFTER MATCH SKIP TO FIRST değişken ve AFTER MATCH SKIP TO [LAST] değişken (yalın SKIP TO değişken, SKIP TO LAST değişken anlamına gelir). Bunlar da eşleşme tarihçesine bağlıdır; çünkü yürütücünün en son eşleşme içinde belirli bir değişkene eşlenmiş satırı işaret edebilmesi gerekir.
Geriye kalan maddeler heterojen bir kuyruktur: SEEK anahtar sözcüğü (INITIAL'in alternatifi), boş örüntü (), dışlama biçimi {- … -}, sıralamadan bağımsız PERMUTE operatörü ve DEFINE içindeki toplama işlevleri ile alt sorgular; bunların ikisi de şu anda reddedilir (değişkenle nitelenmiş bir toplam da eşleşme tarihçesine ihtiyaç duyardı).
- MEASURES
- Eşleşme başına adlandırılmış çıktı ifadeleri, örn.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; R020'de bir pencere işlevi gibiOVERaracılığıyla ortaya çıkar. FINAL / RUNNING anahtar sözcüklerini kabul eder (19075-5 §5.4); R020'de bu ikisi aynı değere indirgenir, çünkü ölçümler her zaman eşleşmenin son satırında değerlendirilir (19075-5 §6.9 (3)). - SUBSET
- Örüntü değişkenlerinin adlandırılmış birleşimleri, örn.
SUBSET U = (A, B, C). Bir örüntü değişkeninin referans gösterilebildiği her yerde kullanılabilir —MEASURES,DEFINEiçindeki örüntüyle nitelenmiş referanslar,CLASSIFIER(U)— bunların hepsi eşleşme tarihçesini gerektirir. - CLASSIFIER()
- Belirli bir satırın hangi örüntü değişkeni olarak eşleştirildiğini döndürür. Hem DEFINE hem MEASURES için tanımlıdır (19075-5 §5.9); herhangi bir satırdaki yanıt, o satır için eşleşme tarihçesinde kayıtlı değişken adıdır.
- Örüntüyle nitelenmiş sütun referansı
DEFINEveyaMEASURESiçinde çıplakB.price— adlandırılmış değişken olarak eşleştirilen satırın o sütununun değeri.- Örüntüyle nitelenmiş gezinme
- Gezinmeyi adlandırılmış değişken olarak eşleştirilen satırlarla sınırlar, örn.
LAST(B.price),FIRST(B.price),PREV(B.price),NEXT(B.price). - SEEK
- Eşleşme, geçerli satırdan tam pencere çerçevesinin sonuna kadar herhangi bir satırda başlayabilir (INITIAL'in tersine).
- AFTER MATCH SKIP TO FIRST değişken
- Adlandırılmış değişken olarak eşleştirilen ilk satıra atlar.
- AFTER MATCH SKIP TO [LAST] değişken
- Adlandırılmış değişken olarak eşleştirilen son satıra atlar.
- Regex: {- -}
- Dışlama — eşleşen satırları
ALL ROWS PER MATCHçıktısından çıkarır. Bu seçenek pencerelere uygulanmaz (19075-5 §6.3.3 (4)), dolayısıyla bir pencerede sözdizimine izin verilir (§6.13) ama etki edeceği bir çıktı yoktur. - Regex: ()
- Boş örüntü — boş diziyle eşleşir.
- PERMUTE(...)
- Listelenen değişkenler arasında sıralamadan bağımsız eşleşme. Anahtar sözcük tanınır ve reddedilir ("PERMUTE is not supported");
permutebir örüntü değişkeni adı olarak kullanılabilir olmaya devam eder. - DEFINE içinde toplama işlevleri
SUM,AVG,COUNTgibi toplamlaraDEFINEyüklemlerinde izin verilmez. Standart bunlara kısmi eşleşme üzerinden çalışan toplamlar olarak izin verir;AVG(B.Price)gibi değişkenle nitelenmiş bir toplam,MEASURES/CLASSIFIER()'ın gerektirdiği aynı eşleşme başına tarihçeye bağlıdır; nitelenmemiş bir toplam ise eşleşmenin o ana kadarki tüm satırları üzerinde çalışır.- DEFINE içinde alt sorgular
DEFINEiçindeki her alt sorgu reddedilir. Standart, satır örüntü tanıma yapmayan ve hiçbir satır örüntü değişkenine başvurmayan bir alt sorguya izin verir; yama şimdilik gereğinden fazlasını reddeder.
Burada belirtilmeye değer dört nokta daha vardır; çünkü bunlar eksiklik sanılmaya açıktır.
İlki, ^ ve $ örüntü çıpalarının WINDOW yan tümcesinde RPR ile birlikte standardın kendisi tarafından izin verilmemesidir (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; temel tanım 19075-5 §4.14.1'dedir); yokluğu bir boşluk değil, uyumdur.
İkincisi, MATCH_NUMBER() de R020'den standart tarafından dışlanmıştır (19075-5 §6.3.3 (6) ve 19075-5 §6.9 (1)) — yalnızca R010 yüzeyinin parçasıdır ve buradaki yokluğu da eksik bir özellik değil, yine uyumdur.
Üçüncüsü, standardın R020'ye dayattığı yapısal yasaklar kümesidir (19075-5 §6.17): satır örüntü tanıma, başka bir satır örüntü tanımanın içine yerleştirilemez; MEASURES ve DEFINE dış referans içeremez; MEASURES veya DEFINE içindeki alt sorgular, satır örüntü değişkenlerine referans veremez (yama daha ileri gider ve yukarıda listelendiği gibi DEFINE içindeki tüm alt sorguları reddeder); ve RPR özyinelemeli bir sorgunun içinde kullanılamaz. Yama dış referans kuralını ("cannot use outer query column in DEFINE clause") ve özyineleme kuralını uygular; ikincisini bir WITH RECURSIVE yan tümcesinin her öğesi için. Ayrıca DEFINE içinde volatile işlevleri ve satırın tamamına yapılan (whole-row) referansları da reddeder.
Dördüncüsü, MATCH_RECOGNIZE'ın kendisi — aynı mekanizmanın tablo yan tümcesi yüzeyi olan R010 özelliği — bu yamanın kapsamı dışındadır. PostgreSQL'in eninde sonunda R010'u ekleyip eklemeyeceği gelecekteki bir seri için soru olacaktır, bunun ölçütü değil.
§2. Örnekler — Gerçekte Nasıl Çalışır
Bu bölümdeki örnekler artımlı olarak ilerler. Satır örüntü eşleşmesinin metin örüntü eşleşmesinden gerçekten neden farklı olduğunun kavramsal nedeniyle başlıyor, ardından DEFINE koşullarını ilginç kılan dört gezinme işlevini tanıtıyor ve son olarak beş uygulamalı örneği adım adım inceliyoruz: tek bir eşleşme (NFA hareketi), seçenek, kolay durumda bağlam emilimi ve emilimin devre dışı bırakıldığı iki durum.
Gezinmeyi ucuz kılan iç mekanizma — 1 yuvalı tuple takası — yürütücünün tasarımına aittir ve burada değil, sonraki bölümde ele alınmıştır.
2.1 Satır örüntülerinin metin örüntülerinden farkı
Bir metin düzenli ifadesi karakter akışıyla eşleşir ve her konumda dikkate alınacak tam olarak bir simge vardır. Çalışma zamanı sorusu — "geçerli simge 'A''ya eşit mi?" — tek bir evet/hayır yanıtına sahiptir. Geri izlemeli otomatlar bunu kullanır: karakter başına en fazla bir dal hayatta kalır ve belirsizliğin maliyeti girdiyi yeniden okuyarak ödenir.
Bir satır örüntüsü temel bir biçimde farklıdır. Satır tek bir simge değildir; bir Boole yüklemleri kümesine, yani DEFINE koşullarına karşı değerlendirilen sütunlardan oluşan bir tuple'dır. Aynı satırda iki yüklem aynı anda doğru olabilir ve standartta bu yüklemlerin karşılıklı olarak dışlayıcı olması gerektiğini söyleyen hiçbir şey yoktur. Şu örneği düşünün:
DEFINE A AS price > 100, B AS volume > 1000, C AS price > 200
price = 150, volume = 2000 olan bir satır hem A'yı hem B'yi karşılar ama C'yi karşılamaz. Örüntü eşleştirici bunu tek bir duruma indirgeyemez — iki örüntü değişkeni canlıdır ve bunlardan herhangi birini adlandıran herhangi bir örüntü öğesi ilerleyebilir. Bu nedenle NFA, bölüm satırı başına bir değil birden fazla eşzamanlı durum taşımak zorundadır.
Bu tek gözlem, mimarinin geri kalanını yönlendirir. Yürütme durumu bir bağlamlar listesidir, her bağlam bir durumlar listesidir ve her satırda çalışma zamanı her duruma şunu sorar: "burada doğru olan değişkenler verildiğinde, nereye gidebilirim?" Ortaya çıkan dallanmalar, çalışma zamanının birkaç katmanlı budamaya — bağlam içinde durum tekilleştirme, bağlamlar arası emilim ve §3.6'da incelenen diğer kurallar — neden ihtiyaç duyduğunun nedenidir; bunlar olmadan canlı durum ve bağlam sayısı bölümle birlikte büyür ve örüntü eşleştirme süper-doğrusal hale gelir.
2.2 Gezinme işlevleri
Yalnızca geçerli satıra başvuran DEFINE koşulları sınırlıdır; ilginç olan neredeyse her örüntü, geçerli satırı komşularıyla veya eşleşmenin daha erken kabul edilmiş satırlarıyla karşılaştırmayı gerektirir. Standart bunun için dört gezinme işlevi sağlar ve yama bunların hepsini gerçekler.
- PREV(expr [, n])
- Geçerli satırdan n satır önceki satır (varsayılan n = 1). "Bugün vs. dün" karşılaştırmaları için kullanılır.
- NEXT(expr [, n])
- Geçerli satırdan n satır sonraki satır (varsayılan n = 1). İleriye dönük bakış; pencere monoton olduğundan pencere biçiminde nadirdir.
- FIRST(expr [, n])
- Mevcut eşleşmenin ilk satırından n satır sonraki satır (varsayılan n = 0, ilk satırın kendisi). "Bu eşleşmeyi başlatan satırla karşılaştır."
- LAST(expr [, n])
- Son eşleşmiş satırdan n satır önceki satır (varsayılan n = 0).
DEFINEiçinde son eşleşmiş satır geçerli satırdır, dolayısıylaLAST(price)geçerli satırı okur.
Dört ilkel birleşebilir: PREV ve NEXT, bir FIRST veya LAST çağrısını sarmalayarak anlamı "eşleşmeye göreli bir satıra git, ardından ondan sabit bir mesafe adımla" olan dört bileşik biçim verir. Bu, bir DEFINE ifadesinin, örneğin, eşleşme başlamadan hemen önceki satırı okumasına olanak tanır.
- PREV(FIRST(expr [, n]) [, m])
FIRST(expr, n)'nin okuduğu satırdan m satır geriye adımla (varsayılanlar n = 0, m = 1). "Bu eşleşme başlamadan hemen önceki değer neydi?"- NEXT(FIRST(expr [, n]) [, m])
FIRST(expr, n)'nin okuduğu satırdan m satır ileriye adımla. Geçerli satıra bağlı kalmaksızın eşleşmenin daha derinine ulaşır.- PREV(LAST(expr [, n]) [, m])
LAST(expr, n)'nin okuduğu satırdan m satır geriye adımla. "En son eşleşmiş satırın biraz öncesindeki bir satırla karşılaştır."- NEXT(LAST(expr [, n]) [, m])
LAST(expr, n)'nin okuduğu satırdan m satır ileriye adımla.
Burada iki pratik nokta belirtmeye değer. İlki, gezinme bileşik olabilir: PREV(FIRST(price)), eşleşme başlamadan hemen önceki satırı okur ve yama bunu destekler. İkincisi, gezinmenin yürütücü optimizasyonları üzerinde sonuçları vardır. Yalın PREV ve NEXT geçerli satıra göredir ve her zaman güvenlidir; FIRST ve LAST'ın ofsetli varyantları, tek başına ya da bileşik bir PREV/NEXT içinde, eşleşme sınırlarına göredir ve bu, bağlam emilimi ile etkileşir: planlayıcı bu durumda emilimi tüm örüntü için devre dışı bırakır. Bu etkileşimin arkasındaki mekanizma §2.6'nın konusudur.
2.3 Uygulamalı örnek 1 — NFA hareketi
SKIP PAST LAST ROW tarafından atılır.SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (START UP+ DOWN+) DEFINE UP AS price > PREV(price), DOWN AS price < PREV(price) );
Örüntü dört öğeye düzleştirilir:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
100, 110, 120, 115, 108, 130 fiyat serisi için:
| Satır | Fiyat | Doğru değişkenler | Eylem |
|---|---|---|---|
| 0 | 100 | START | Yeni bağlam. START eşleşir ve hemen çıkar (max=1); durum UP+'a ilerler. |
| 1 | 110 | START, UP | UP eşleşir. İlerleme dallanır: bir durum UP'ta döner, diğeri DOWN+'a çıkar. |
| 2 | 120 | START, UP | UP, döngüdeki durumda eşleşir ve yine dallanır. 1. satırdan gelen DOWN durumu ölür (120 ≮ 110). |
| 3 | 115 | START, DOWN | Döngüdeki durumda UP başarısız olur ve ölür. 2. satırdan gelen DOWN durumu eşleşir. İlerleme dallanır: DOWN'ta döngü ve #FIN'e çıkış — 0–3 satırları üzerinde bir eşleşme adayı kaydedilir. |
| 4 | 108 | START, DOWN | DOWN döngüdeki durumda eşleşir ve yine dallanır; 0–4 satırları üzerindeki yeni FIN adayı daha kısa olanın yerini alır. |
| 5 | 130 | START, UP | Döngüdeki DOWN durumu başarısız olur (130 ≮ 108). Bu bağlamda canlı durum kalmadığından, kaydedilen aday (0–4 satırları) eşleşme olarak kesinleşir. Sonraki deneme 5. satırda başlar; START eşleşir, ancak bölüm herhangi bir UP'tan önce sona erer. |
Anahtar nokta: 3. satırda, satır hem START (her zaman doğru) hem DOWN'u karşılar; ama START yalnızca 3. satırda başlayan bir bağlam için önemlidir; bu bağlamda döngüdeki UP durumu ölür ve yalnızca DOWN+'ta bekleyen durum ilerler. §2.1'in çok-durumlu doğası, her UP eşleşmesinde dallanma olarak görünür (durum UP+'ta kalabilir veya DOWN+'a doğru ilerleyebilir). Açgözlü tercih "çıkmadan önce tekrar döng"dür; dolayısıyla yeterli veri altında döngü dalları eşleşmeyi daha da uzatırdı; burada döngüdeki DOWN 5. satırda ölür (130 ≮ 108) ve son FIN adayı (0–4 satırları) — DOWN 4. satırda çıktığında üretilen ve 3. satır adayının yerini alan — eşleşme olarak kesinleşir.
Sorgunun sonucu doğrudan bu izlemeden çıkar. RPR anlamları altında, first_value(price) ve last_value(price) pencere işlevleri yalnızca eşleşmeyi başlatan satırda değerlendirilir — eşleşmedeki diğer her satır bu pencere işlevleri için NULL üretir, çünkü onun indirgenmiş çerçevesi boştur. Bu nedenle verilerimiz için çıktı, posterin sağ üst panelinde gösterdiği tabloya benzer:
| Satır | Fiyat | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
0. satır eşleşmenin başlangıcıdır, bu nedenle çerçevesi 0–4 satırlarını kapsar ve pencere işlevleri V şeklinin açılış fiyatını ($100) ve dip fiyatını ($108) raporlar. 1–4 satırları eşleşmenin içindedir ama başlangıcı değildir, bu nedenle NULL alırlar. 5. satır (fiyat $130) herhangi bir eşleşmenin dışındadır ve aynı şekilde NULL alır.
2.4 Uygulamalı örnek 2 — Seçenek ve sözcüksel sıra
(A | B) biçimi eşleştiriciye bir seçim verir: herhangi bir satırda iki seçenek bağımsız olarak test edilir ve herhangi bir sayıda seçenek eşleşebilir. §2.1'in çok-durumlu doğası tam burada tek bir bağlamın içinde görünür hale gelir — bağlamlar arasında değil (bu emilimdir), yürütücünün örüntü sırasıyla, önce daha erken dal olmak üzere keşfettiği paralel dallar boyunca.
PATTERN ((UP | HIGH) DONE) DEFINE UP AS price > PREV(price), HIGH AS price > 100, DONE AS volume > 1000
Fiyatın hem yükseldiği hem de 100 doları aştığı bir satır düşünün — hem UP hem HIGH doğrudur. Her seçenek kendi durumunu üretir: biri UP dalında yürür, biri HIGH dalında yürür. Ardından ikisi de DONE'a ilerler ve orada buluşurlar.
| Satır | Doğru değişkenler | Canlı durumlar |
|---|---|---|
| R | UP, HIGH | A durumu (UP dalı) ve B durumu (HIGH dalı) aynı sayılarla DONE'a ilerler; B, A'nın bir kopyasıdır ve atılır |
| R+1 | DONE | A durumu DONE ile eşleşir ve #FIN'e ulaşır |
Standardın terimleriyle her iki dal aynı satırlar üzerinde aynı uzunlukta bir eşleşme üretir ve iki aday yol verir — biri UP, DONE, diğeri HIGH, DONE etiketli. Standart bunu sözcüksel sıra ile çözer: (UP | HIGH) içinde yazılan seçenekler arasında, eşleşme uzunluğundan bağımsız olarak önce yazılan kazanır. UP, HIGH'tan önce göründüğü için hayatta kalan yol UP, DONE'dir. Yürütücü bunu FIN'de değil, R satırında uygular: UP dalı durumunu önce ekler, böylece nfa_append_state_unique() onu tutar ve özdeş HIGH dalı durumunu düşürür.
Sözcüksel sıra, CLASSIFIER() sonunda gerçeklendiğinde onu iyi tanımlı kılan şeydir — her iki yüklem de doğru olduğunda bile çalışma zamanının kullanıcıya "bu satır HIGH değil, UP olarak eşleşti" diyebilmesini sağlar. Sözcüksel sıra, seçenek için birincil kuraldır: sözcüksel olarak daha erken bir dal, sözcüksel olarak daha geç bir dal daha uzun bir eşleşme üretecek olsa bile ona karşı kazanır; ve sözcüksel olarak daha geç (muhtemelen daha kısa) bir dal, sözcüksel olarak daha erken her dal FIN'e ulaşmadan önce ölürse yine de kazanabilir. Açgözlü uzunluk tek bir niceleyici içinde kararlaştırılır — aynı seçenek dalının iki tamamlamasında, açgözlü niceleyici daha fazla yinelemeyi tercih eder.
2.5 Uygulamalı örnek 3 — Bağlam emilimi (aynı kader)
Emilimi sergileyen en basit örüntü, DEFINE A AS TRUE ile PATTERN (A+)'dır. Her satır A ile eşleşir ve standart, eşleştiricinin her satırı olası bir eşleşme başlangıcı olarak değerlendirmesini gerektirir. Naif olarak, bu, N satırlı bir bölüm için N bağlam demektir. Beş satırlı bir bölüm alalım (herhangi bir veri — yüklem sabit doğrudur):
| Satır | Naif bağlamlar | Emilimle |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 emildi |
| 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 | beş bağlam | C1[A:5] |
Canlı bağlamlar O(n)'den O(1)'e düşer; dolayısıyla bölüm boyunca toplam O(n²)'den O(n)'e iner. Atmayı haklı çıkaran emilim kuralı, niceleyici sınırsız olduğunda basittir:
Posterin sol alt paneli ("① Bağlam Emilimi") tam olarak bu kuralın beş satır üzerinde görselleştirilmiş halidir.
Kuralda ince ama önemli bir nokta gizlidir: atma güvenlidir, çünkü A AS TRUE yüklemi, hangi bağlam soruyor olursa olsun her satırda aynı değere değerlendirilir. Yalnızca geçerli satıra veya ondan sabit bir ofsete başvuran her yüklem için aynı şey geçerlidir — PREV dahil. Sonraki örnek, PREV tabanlı bir yüklem kullanarak somut bir fiyat haftasına geçer ve §2.6 tam olarak aynı haftayı tekrar kullanarak güvenli ve güvensiz emilim arasındaki simetriyi belirgin hale getirecektir:
PATTERN (RISE+) DEFINE RISE AS price > PREV(price)
Pazartesi'den Cuma'ya $100, $108, $112, $116, $110 işlem haftasını alın — dört yükselişi ani bir düşüş izliyor. C1'in Salı günü başladığını varsayın (RISE'ın eşleştiği ilk gün: $108 > $100) ve yürütücü, Çarşamba günü başlayan C2'yi de spekülatif olarak izlesin. Her satırın RISE koşulu, satırın fiyatını hemen önceki ile karşılaştırır — bağlam düzeyinde değil, bölüm düzeyinde bir gerçektir — bu nedenle iki bağlam, paylaştıkları her satırda aynı Boole değerini hesaplamaya zorlanır:
| Gün | Fiyat | C1 — Salı başlangıç price > PREV(price) | C2 — Çar başlangıç price > PREV(price) |
|---|---|---|---|
| Pzt | $100 | — | — |
| Sal | $108 | $108 > $100 ✓ (yeni başladı) | — |
| Çar | $112 | $112 > $108 ✓ | $112 > $108 ✓ (yeni başladı) |
| Per | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| Cum | $110 | $110 > $116 ✗ — kesinleş | $110 > $116 ✗ — kesinleş |
Yüklem, her bağlamın kendi sınırlarına bağlı olmaya başladığı anda hikâye kırılır — ve §2.6 tam olarak bununla ilgilidir.
2.6 Uygulamalı örnek 4 — Emilim ne zaman güvensiz hale gelir
DEFINE FIRST'e başvurduğunda neyin değiştiğini göstermek — emilim kuralı artık geçerli değildir ve planlayıcı örüntü için emilimi devre dışı bırakır.
Bir analistin, bir hisse senedinin koşunun başladığı günden itibaren on dolar içinde kaldığı ardışık işlem günlerini bulmak istediğini varsayın — bir tür konsolidasyon penceresi. Örüntü ve DEFINE şöyledir:
PATTERN (STABLE+) DEFINE STABLE AS price < FIRST(price) + 10
Koşul artık geçerli satırın fiyatını mevcut koşunun başlangıcındaki fiyatla karşılaştırır. Farklı günlerde başlayan iki koşunun farklı FIRST(price) değerleri vardır, dolayısıyla aynı örüntü öğesinde ve aynı sayıdaki iki durum artık değiştirilebilir değildir: gelecekleri, emilimin atmak üzere olduğu sınıra bağlıdır.
§2.5'tekiyle tam olarak aynı işlem haftasını alın — Pazartesi'den Cuma'ya $100, $108, $112, $116, $110. Çalışma zamanı yine aynı anda iki aday koşuyu canlı tutar: C1 Pazartesi başladı, C2 Salı başladı (STABLE+ altında her satır potansiyel bir koşu başlangıcıdır).
| Gün | Fiyat | C1 — Pzt başlangıç FIRST = $100 price < $100 + 10 | C2 — Sal başlangıç FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| Pzt | $100 | $100 < $110 ✓ | — |
| Sal | $108 | $108 < $110 ✓ | $108 < $118 ✓ (yeni başladı) |
| Çar | $112 | $112 < $110 ✗ — Pzt–Sal kesinleştir | $112 < $118 ✓ |
| Per | $116 | — | $116 < $118 ✓ |
| Cum | $110 | — | $110 < $118 ✓ (hâlâ çalışıyor) |
Emilim altında C2, Salı günü C1'e birleştirilirdi — birleştirilen bağlam yalnızca C1'in tavanını ($110) tutar, dolayısıyla C2'nin farklı görünümü (tavan $118, Cuma'ya kadar dört günlük koşu) C1'in geleceği tarafından kapsanmaz. Bu özel haftada çıktı tesadüfen değişmez: C1 Pzt–Sal'ı kaydeder, C2 o eşleşmenin içinde başlamıştır ve SKIP PAST LAST ROW tarafından atılır, sonraki deneme ise Çarşamba günü kendi tavanıyla ($122) başlar ve Çar–Cum ile eşleşir. Genel olarak ise daha erken bir bağlamın DEFINE sonucu artık daha sonrakininkini kapsamaz, dolayısıyla emilimin dayandığı sayı karşılaştırması geçersizdir. Bir DEFINE yüklemi eşleşme başlangıcı bağımlılığı taşıdığında, planlayıcı bu nedenle emilimi önleyici olarak devre dışı bırakır.
(Önde giden bağlamın eşleşmesi başarılı olduğunda, kabul edilen aralığının içinde başlayan bağlamlar — varsayılan AFTER MATCH SKIP PAST LAST ROW altında — basitçe atılır; yalnızca önde giden eşleşme başarısız olursa çalışma zamanının geri dönebileceği bir yer olması için canlı tutulurlar.)
Aşağıdaki tablo, posterin sağ alt panelini ("② Gezinme") bileşik biçimlerle genişletir ve hangi gezinme biçimlerinin eşleşme başlangıcı bağımlılığı yarattığını özetler:
| Gezinme | Eşleşme başlangıcı bağ. | Emilebilir mi? |
|---|---|---|
| PREV, NEXT | yok | evet |
| LAST (ofsetsiz) | yok | evet |
| LAST ofset ile | sınır kontrolü | hayır |
| FIRST (herhangi) | doğrudan | hayır |
| Bileşik (iç FIRST) | doğrudan | hayır |
| Bileşik (iç LAST, ofsetsiz) | yok | evet |
| Bileşik (iç LAST ofset ile) | sınır kontrolü | hayır |
§2.5 ve §2.6'daki iki örnek tek bir kurala indirgenir. Emilimi güvenli kılan şey aynı kaderdir: aynı örüntü öğesindeki her bağlam, gelecekteki her yükleme aynı yanıtı hesaplayacaksa, yalnızca en eskisinin tutulması gerekir. Farklı kaderler emilimi güvensiz kılar: yüklemler bağlama özel duruma göre dallandığı anda — ki bu tam olarak FIRST ve ofsetli LAST'ın yaptığı şeydir — her canlı bağlam, başka hiçbir bağlamın kapsayacağı garanti edilmeyen bir geleceği temsil eder; dolayısıyla birini atmanın güvenli olduğu artık gösterilemez.
Planlayıcı bu ayrımı derleme zamanında saptar ve emilimi tüm örüntü için açar ya da kapatır; kapalı olduğunda çalışma zamanı çoklu bağlam maliyetini öder. Posterin ③ panelindeki kıyaslama FIRST kullanmaz, dolayısıyla emilim açık kalır; PostgreSQL'in hem başarı hem başarısızlık durumlarında doğrusal kalmasının nedeni budur.
Posterdeki kıyaslama sayıları, aynı algoritmanın ölçekte oynamasıdır. Başarı örüntüsü (A+ B+ C+ D)'de, bir eşleşme onaylandıktan sonra hem PostgreSQL hem Trino kabaca O(n) ölçeklenir ve PostgreSQL kabaca 16× ile 33× arası önde gider (Trino rakamları JVM başlatmayı zaten hariç tutar).
Başarısızlık örüntüsü (A+ B+ C+ E)'de, emilimi yok gibi görünen Trino her potansiyel eşleşme başlangıcını kovalar ve O(n²)'den bile hızlı kötüleşir (5× satır için yaklaşık 56× süre); 100.000 satırda beş saatten fazla sürer, oysa PostgreSQL hâlâ 92 ms'de bitirir; yaklaşık 217.000× hızlanma.
Bu fark mühendislik cilası değildir — tam olarak §2.5 ve §2.6'daki aynı-kader / farklı-kader ayrımının, bölümdeki her potansiyel eşleşme başlangıcının her satırına uygulanmasıdır.
2.7 Uygulamalı örnek 5 — SKIP emilimi ne zaman devre dışı bırakır
Önceki örnek emilimi veri tarafından kırdı: DEFINE'daki FIRST, her bağlamın yüklemleri farklı değerlendirmesine neden oldu. Emilim çıktı tarafından da kırılabilir ve bunu AFTER MATCH SKIP yan tümcesi denetler.
DEFINE A AS TRUE ile PATTERN (A+) örüntüsünü, hepsi A ile eşleşen beş satır üzerinde düşünün. Varsayılan AFTER MATCH SKIP PAST LAST ROW altında, eşleştirici en erken satırdan başlayan en uzun eşleşmeyi bulur ve ardından üstüne atlar; bu eşleşmenin içinde başlayan herhangi bir bağlam gereksiz olarak örtük şekilde atılır — tam olarak emilimin ele almak için tasarlandığı durum. Çıktı tek bir eşleşmedir, 0–4 satırları; ve çalışma zamanının yalnızca tek canlı bir bağlama ihtiyacı vardır.
Atlama modunu AFTER MATCH SKIP TO NEXT ROW'a değiştirin ve sözleşme değişir:
PATTERN (A+) DEFINE A AS TRUE AFTER MATCH SKIP TO NEXT ROW
Şimdi her potansiyel başlangıç konumu, eşleşmeler örtüştüğünde bile ayrı raporlanmalıdır. Aynı beş satır için çalışma zamanının beş eşleşme yayması gerekir: 0–4, 1–4, 2–4, 3–4 ve 4–4 satırları. Bunlardan hiçbiri "daha erken başlayan daha uzun bir tanesi" ile değiştirilemez, çünkü standart kullanıcının hepsini istediğini söyler.
| Satır | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | eşleşme başlar; 0–4 satırları tek eşleşme olacak | eşleşme 0. satırda başlar |
| 1 | (eşleşme 0'ın içinde) | eşleşme 1. satırda başlar — canlı tutulmalı |
| 2 | (eşleşme 0'ın içinde) | eşleşme 2. satırda başlar — canlı tutulmalı |
| 3 | (eşleşme 0'ın içinde) | eşleşme 3. satırda başlar — canlı tutulmalı |
| 4 | eşleşme 0 kesinleşir (0–4 satırları) | beş eşleşme kesinleşir: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW altında, geç başlayan her bağlam kendi çıktı satırıdır. Aynı örüntü öğesindeki iki bağlam artık gereksiz değildir — her ikisi de gerekli çıktılardır ve birini atmak, kullanıcının istediği bir eşleşmeyi sessizce düşürür.
Yüklem'in değişmediğine dikkat edin. A AS TRUE, hangi bağlamın sorduğundan bağımsız olarak her satırda aynı şekilde değerlendirilir, dolayısıyla §2.5 aynı-kader koşulu hâlâ karşılanır. Değişen şey çıktı gerekliliğidir: özdeş geleceklere sahip bağlamlar bile birlikte var olmalıdır, çünkü sonucun farklı satırlarına karşılık gelirler. Bu nedenle planlayıcı, DEFINE yan tümcesinden bağımsız olarak AFTER MATCH SKIP TO NEXT ROW yürürlükteyken bağlam emilimini devre dışı bırakır.
§2.6 ve §2.7'yi yan yana koymak, bir sorgunun anlamlarının emilimi dışladığı iki yolu verir:
DEFINE içinde FIRST veya ofsetli LAST tarafından tetiklenir.AFTER MATCH SKIP TO NEXT ROW tarafından tetiklenir.
Her iki koşul da tüm örüntü için emilimi devre dışı bırakmaya yeter; UNBOUNDED FOLLOWING'de bitmeyen bir çerçeve de öyle. Hiçbiri yürürlükte değilken — varsayılan AFTER MATCH SKIP PAST LAST ROW, sınırsız bir çerçeve sonu ve yalnızca PREV, NEXT veya çıplak LAST kullanan DEFINE koşulları — emilim etkinleştirilir, ancak yalnızca örüntünün emilebilir bölgesindeki durumlar için: A+ veya A* gibi önde gelen açgözlü sınırsız bir değişken, (A B)+ gibi sınırsız açgözlü niceleyicili sabit uzunluklu bir grup, (A+ B)+ veya (A+ B){2} gibi gövdesi bunlardan biriyle başlayan açgözlü bir grup ya da bunlardan kurulmuş seçenek dalları; gönülsüz bir grup tüm alt ağacını uygunsuz kılar. Bunun geçerli olduğu yerde, §2.5'teki A+ için olduğu gibi, çalışma zamanı tek bir bağlama çöker ve doğrusal kalır; §2.3'teki START UP+ DOWN+ ise hiç emilebilir bölge almaz.
§3. Tasarım — Ayrıştırıcıdan Yürütücüye
Satır Örüntü Tanıma, iyi tanımlanmış ara biçimler üzerinden iş aktaran üç aşama olarak gerçeklenir. Ayrıştırıcı, SQL metnini bir örüntü ağacı ile bir DEFINE yüklemleri listesine çevirir; planlayıcı ağacı, örüntü öğelerinin düz bir dizisine derler ve hangilerinin bağlam emilimine katılabileceğine karar verir; yürütücü diziyi, üç aşamalı bir döngüde bölüm satırları üzerinde satır satır çalıştırır. Her aşamanın kendi veri biçimi vardır ve tasarım yaratıcılığının çoğu sınırlardadır: önbelleğe sığan düz bir NFA, başvuru başına bir tane materyalleştirmek yerine tek bir tuple yuvasını yeniden kullanan bir gezinme modeli ve O(n²) işi O(n)'e indiren bir emilim kuralı.
SQL metin
│
│ ayrıştırıcı aşaması
▼ çerçeveyi doğrula
örüntü ağacını kur
DEFINE'ı tip kontrolü
örüntü ağacı + DEFINE listesi
│
│ planlayıcı aşaması
▼ ağacı optimize et
düz NFA dizisine derle
emilebilirliğe karar ver
düz NFA + emilim bayrakları
│
│ yürütücü aşaması
▼ satır başına motor:
Eşleştir → Em → İlerle
eşleşme sonucu:
başlangıç satırı, uzunluk, başarı/başarısızlık
Aşağıdaki bölümler bu boru hattını takip eder. §3.1 ayrıştırıcıyı ve örüntü ağacının biçimini kapsar; §3.2 ağacı düz NFA'ya dönüştüren derlemeyi kapsar; §3.3 DEFINE yüklemlerinin komşu satırlara bakmak için kullandığı gezinme modelini kapsar; §3.4 eşleşme sınırı işlemini — bir eşleşmenin nerede başlayıp nerede biteceğini sabitleyen SKIP, INITIAL ve sınırlı çerçeve kurallarını — kapsar; §3.5 üç aşamalı satır başına motordur; §3.6 durum uzayını sınırlı tutan tüm budama mekanizmalarını derler; §3.7 ise gerçeklemenin EXPLAIN çıktısında ortaya çıkardıklarını inceler.
3.1 Ayrıştırıcı — örüntü ağacının inşası
Ayrıştırıcı, örüntü tanımayı bir pencere belirtimi içindeki PATTERN yan tümcesinin varlığıyla tanır. İlk işi çerçeve doğrulamasıdır; çünkü RPR sıradan pencere sorgularının dayatmadığı kısıtlamalar getirir: çerçeve modu ROWS olmalıdır (RANGE veya GROUPS değil), başlangıç sınırı CURRENT ROW olmalıdır, bitiş sınırı UNBOUNDED FOLLOWING veya pozitif bir ofset FOLLOWING olmalıdır (dolayısıyla varsayılan bir çerçeve de reddedilir) ve EXCLUDE NO OTHERS dışındaki EXCLUDE seçeneklerine izin verilmez. Bunlar optimizasyon değil, uyum kontrolleridir — RPR'nin çerçeve kavramı eşleşme aralığıdır ve standart, bunu eşleşmiş satırlardan başka bir şeyle doldurmayı düşünmez.
Çerçeve doğrulamayı geçtikten sonra, ayrıştırıcı PATTERN yan tümcesini dört tür düğümden oluşan bir ağaca çevirir — bir değişken referansı, bir dizi (birleştirme), bir seçenek ve bir grup (parantezli alt örüntü). Her düğüm, niceleyiciyi üç sayı olarak taşır — alt sınır, üst sınır (sonsuz olabilir) ve gönülsüz eşleşme bayrağı:
| Kaynak | Ağaç kodlaması |
|---|---|
| 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) |
Daha sonra her DEFINE yüklemi bölümün sütunlarına karşı tip kontrolüne tabi tutulur ve bir Boole ifadesine zorlanır. Bunun ardından iki pratik şey gerçekleşir. İlk olarak, ayrıştırma analizi DEFINE için sorgunun hedef listesine hiçbir şey eklemez; bunun yerine planlayıcı, HAVING için yaptığı gibi, bir DEFINE yükleminin başvurduğu her sütunu gerekli olarak işaretler ve çevredeki sorgu bunları seçmese bile bu sütunları yürütücü aşamasına yayar — bu olmadan çalışma zamanının değerlendirebileceği hiçbir şey olmazdı. İkinci olarak, PATTERN'de görünen ama DEFINE'da hiç görünmeyen değişkenler örtük olarak doğrudur: her satırla eşleşirler.
3.2 Derleme — AST'tan düz NFA'ya
Planlayıcı, ayrıştırıcının ağacını yürütücünün çalıştıracağı veri yapısına dönüştürür: indeksle adreslenen, örüntü öğelerinden oluşan düz bir dizi. Derleme altı adımlı bir boru hattı olarak ilerler:
compile(astTree):
1. AST'ı optimize et
2. boyutu ve derinliği ölç
3. öğe dizisini tahsis et
4. AST'tan doldur
(next/jump işaretçilerini ata)
5. sonlandır — FIN nöbetçisini kur
6. emilime uygun öğeleri işaretle
Düz biçim basit bir nedenle seçilmiştir: yürütücünün örüntüyü bölüm başına birçok kez dolaşması gerekir ve bitişik, indekslenebilir bir dizi, dolaşılacak en ucuz veri yapısıdır. İlginç olanlar 1. ve 6. adımlardır — 1. adım dizinin ne kadar büyük olacağını belirlediği için, 6. adım ise §2.5'teki emilim optimizasyonunun hiç devreye girip girmeyeceğine karar verdiği için.
AST optimizasyonu
Optimizasyon iki kez kazanç sağlar: bir kez düz dizinin statik öğe sayısında, bir kez de çalışma zamanında işlenen her satırda. Her dönüşüm, çalışma zamanının numaralandırması gereken durum uzayını azaltır. Optimize edici dokuz yeniden yazma kuralını tek bir aşağıdan yukarıya geçişte uygular (bir dizi içinde grup birleştirme bir kez daha çalışır, çünkü önceki birleştirmeler iki özdeş grubu yan yana getirebilir):
- SEQ düzleştirme
SEQ(A, SEQ(B, C))→SEQ(A, B, C)- Ardışık değişken birleştirme
-
A A→A{2}
A{2,3} A{1,2}→A{3,5} - Ardışık grup birleştirme
(A B)+ (A B)+→(A B){2,∞}- Ardışık ALT birleştirme
(A | B) (A | B) (A | B)→(A | B){3}- Önek/sonek birleştirme
A B (A B)+→(A B){2,∞}- ALT düzleştirme & tekilleştirme
-
(A | (B | C))→(A | B | C)
(A | B | A)→(A | B) - Niceleyici çarpımı
-
(A+)+→A+
(A{2,3}){5}→A{10,15} - Tek çocuk soyma
-
SEQ(A)→A
(A){1,1}→A - Gönülsüzlük normalleştirme
A{2}?→A{2}(min = max olan her yerde gönülsüzlük temizlenir)
Niceleyici çarpımı yalnızca ulaşılabilir sayılar tek bir bitişik aralık oluşturduğunda ve tercih edilen eşleşme kaymadığında çöker: kesin bir dış ((A{2,3}){5} → A{10,15}), min değeri 0 olan bir çocuk ya da çocuk min değeri en fazla 1 olan veya çocuk max değeri sınırsız olan, birbirine değen çocuk aralıkları ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}); min değeri 0 olan bir dış ayrıca en fazla 1 olan bir çocuk min değeri gerektirir ((A{2,})* olduğu gibi kalır, çünkü A* tek bir satırı kabul ederdi). Kendi niceleyicisi kesin olmayan bir grup çocuğunun önce sabit uzunluklu bir gövdesi olmalıdır; bu yüzden ((A | B B){1,2}){2} kesin bir dış altında bile olduğu gibi kalır. Diğer kombinasyonlar, düz biçimin gözden kaçıracağı boşluklar getirebilir — örn. (A{2}){2,3} yalnızca {4, 6}'yı kabul eder, ama naif bir A{4,6} 5'i de kabul ederdi — ya da tercih edilen eşleşmeyi kaydırabilir ((A{2,3}){1,2} üç satırı tercih ederken A{2,6} dört satır alır); bu yüzden optimize edici bunları olduğu gibi bırakır. Koşula bağlı tek yeniden yazma bu değildir: grup birleştirme ve sonek birleştirme sabit sayıda satır tüketen bir gövde gerektirir, önek birleştirme min değeri 0, max değeri sonlu ve içeriği nullable olan bir grubu reddeder, gönülsüz düğümler ne birleştirilir ne çarpılır ((A+?)+ olduğu gibi kalır) ve yeni sınırı taşacak bir yeniden yazma reddedilir.
Öğe biçimi
Düz dizinin her öğesi örüntüde tek bir konumu temsil eder. Altı mantıksal tür vardır: bir değişken referansı (satır tüketen tek tür); grup başlangıcı ve grup sonu işaretleri (parantezli bir alt örüntüyü açıp kapatırlar); seçenek işareti (bir dallar listesinin başını çeker); her dalı sonlandıran bir dal ayırıcı; ve örüntünün sonunda bir bitiş işareti.
Her öğe ayrıca bir derinlik (grup yuvalama düzeyi), niceleyici (bir min ve max yineleme sayısı, sonsuz olabilir) ve iki geçiş işaretçisi taşır — next, "bu öğeyi tükettikten sonra nereye gidileceği" ve jump, "nereye atlanacağı" (seçenek işareti ve dal ayırıcılar tarafından dalları zincirlemek için, grup başlangıcı tarafından kendi grup sonunu adlandırmak için — niceleyicisi sıfıra izin veren bir grup o sonun next'i üzerinden atlanır — ve grup sonu tarafından gövdeye geri dönmek için kullanılır).
PATTERN ((A B)+) için derlenen dizi şöyle görünür:
PATTERN ((A B)+) şuna derlenir:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(grubu açar; jump kendi
END'ini adlandırır)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(grubu kapatır; jump geri döner)
[4] FIN örüntü tamamlandı
Örüntü next aracılığıyla soldan sağa okunur, doğrusal olmayan kenarları jump ele alır. idx 3'te END'in jump'ı idx 1'e geri işaret eder; sınırsız dış niceleyici böyle döngüye girer; idx 0'da BEGIN'in jump'ı idx 3'teki END'ini adlandırır ve grup isteğe bağlı olsaydı atlama, END'e varmadan o END'in next'i üzerinden idx 4'e çıkardı. Çalışma zamanı asla çalışma zamanında bir grafik kurmak zorunda kalmaz — diziyi dolaşırken yalnızca bu iki işaretçiyi takip eder.
Öğe başına nitelikler
Biçimin ötesinde, her öğe çalışma zamanının o konumdaki davranışını yönlendiren beş mantıksal nitelik taşır:
- Reluctant
- Niceleyici genişlemesinin sırasını tersine çevirir. Açgözlü niceleyiciler "çıkış"tan önce "tekrar döng"ü dener; gönülsüz niceleyiciler önce "çıkış"ı dener.
A+?için değişken tarafından taşınır;((…)+?)için grubun BEGIN ve END'i tarafından taşınır. - Boş-döngülenebilir
- Gövdesi nullable olan grup sonlarına atanır (
(A? B?)+,(A | B*)+;(A?)*önceA*'a çarpılır ve grup sonu bırakmaz). Çalışma zamanına, min altında normal geri döngünün yanına hızlı ileri sarma çıkışı eklemesini söyler; böylece döngü koruması, boş yinelemeler üretebilen gruplarda meşru eşleşmeleri öldürmez. - Boş-tercihli
(A?? B??){2}'deki gibi gövdesi boş eşleşmeyi tercih eden grup sonlarına atanır. Min altında, grubun kendi açgözlülüğünün hiçbir şey söylemediği yerde, hızlı ileri sarma çıkışını geri döngünün önüne sıralar.- Emilebilir-bölgenin-içinde
- Bir emilime uygun bölgenin içinde kalan her öğeyi işaretler — çalışma zamanı tarafından geçerli durumun hâlâ güvenli bölgede olup olmadığını izlemek için kullanılır.
- Emilim-karşılaştırma-noktası
- Emilim karşılaştırmalarının çalışması gereken belirli öğeyi işaretler. Basit bir
A+için değişkene düşer;(A B)+gibi sınırsız bir grup için yalnızca grup sonuna düşer.
"Bölge içinde" ile "karşılaştırma noktası" arasındaki ayrım önemlidir, çünkü emilim yalnızca yinelemelerin kapandığı noktalarda anlamlıdır. (A B)+'nın gövdesinin içinde, çalışma zamanı yineleme ortasındadır ve sayı henüz o tur için son değerine ulaşmamıştır; burada karşılaştırma, karşılaştırılamaz değerleri karşılaştırmak demek olurdu. Çalışma zamanı karar verebilmeden önce durumun grup sonuna ulaşması gerekir. Bu nedenle ilk nitelik "hâlâ emilebilir bölgedesin" der; ikincisi "karşılaştırma noktasına ulaştın — şimdi kontrol et" der.
Emilebilirlik analizi
Derlemenin 6. adımı, §2.5'in "aynı kader" kuralına derleme zamanı tanığını veren şeydir. Karar katmanlıdır:
isAbsorbable(query):
if SKIP modu != SKIP PAST LAST ROW
→ return false
if çerçeve sonu != UNBOUNDED FOLLOWING
→ return false
if herhangi bir DEFINE match_start'a bağımlıysa
→ return false
düz diziyi 0. öğeden
itibaren dolaş ve yapısal bir
duruma uyan öğeleri işaretle
İlk üç kontrol sorgu düzeyindedir: tam olarak §2.7 (çıktı tarafı: SKIP modu), sınırlı çerçeve (sınır monotonluğu kırar) ve §2.6 (veri tarafı: DEFINE'da FIRST veya ofsetli LAST) koşullarına karşılık gelirler. Bunlardan herhangi biri başarısız olduğunda analiz hiçbir bayrak ayarlamaz ve emilim sorgu çapında devre dışı bırakılır. Hepsi geçtiğinde, yürüyüş dört yapısal biçimi kabul eder:
- Durum 1 — Basit sınırsız değişken
-
Her yineleme tam olarak bir satırdır. Daha eski bir bağlamın sayısı paylaşılan her konumda her zaman ≥ daha yenisinin sayısıdır.
A+,A*,A{2,∞} - Durum 2 — Sabit uzunluklu grup, sınırsız dış
-
Her çocuğun
(A B)+,(A B{2})+,((A (B C){2}){2})+min == maxdeğeri vardır, dolayısıyla gövde anlamsal olarak açılmış{1,1}biçimine eşdeğerdir —(A B{2})+,(A B B)+gibi davranır. Her yineleme sabit sayıda satır tüketir; sayı baskınlığı hâlâ geçerlidir. - Durum 3 — Gövdesi sınırsız bir değişkenle başlayan grup
-
Önde gelen sınırsız değişkenin kendisi emilebilirdir (Durum 1) ve daha eski bağlamları korur. Durum A'yı geçer geçmez emilim durur — gövdenin geri kalanında monotonluk garantisi yoktur, bu yüzden A her iki bayrağı alır, çevreleyen BEGIN bölge içi bayrağını alır, B ve END ise hiçbirini almaz.
(A+ B)+,(A+ B){2} - Durum 4 — Seçenek
-
Ayırıcı zinciri üzerinden ulaşılan her dal, yukarıdaki durumlarla kendi başına değerlendirilir; herhangi bir dal uygun olduğunda seçenek işareti bölge içi bayrağını alır.
A+ | B+,A+ | C D
Bu dört biçimin kapsamadığı yapısal durumlar da en az o kadar öğreticidir. A B+ mevcut kuralla emilemez, çünkü önde gelen A, sınırsız kısım başlamadan önce bir satır tüketir, dolayısıyla bir satır arayla başlayan bağlamlar sınırsız gövde içinde farklı konumlardadır. A+? gibi gönülsüz niceleyiciler yapı gereği hariçtir: emilim kuralı, daha uzun eşleşmelerin daha kısaları kapsadığı açgözlü anlamları varsayar ve gönülsüz eşleşme bu yönü tersine çevirir.
Sonuç, örüntü başına değil öğe başına bir karardır. Tek bir sorgu planı, (A+ B+ C) veya (A+ B+)+ gibi örüntülerin önde gelen A+'sı için emilimi etkin tutabilir — ikincisi, önde gelen öğeye uygulanan Durum 3'tür — ve sonrası için her şey için devre dışı bırakılabilir; çalışma zamanı, emilim geçişini her düşündüğünde geçerli durumun öğesindeki karşılaştırma-noktası niteliğine bakar. Bir durum emilebilir olmayan bir bölgeye girdiğinde, o durum için emilim kalıcı olarak kapanır — §2.5 ve §2.6'nın algoritmik düzeyde doğru olmasını gerektirdiği şey tam olarak budur.
3.3 Gezinme — 1 yuvalı tuple takası
DEFINE ifadeleri, bir satıra karşı değerlendirilen sıradan SQL ifadeleridir, ancak PREV, NEXT, FIRST veya LAST içerebilirler — farklı satırlara işaret eden başvurular. Satırların kendileri zaten pencerenin tuplestore'unda tamponlanmıştır; yürütücünün hâlâ yönetmesi gereken şey, SQL ifade mekanizmasının okuduğu tuple yuvasıdır; çünkü ifadenin içindeki sütun başvuruları plan zamanında bir yuvaya bağlanır. Gerçekleme her gezinme çağrısı için tek bir gezinme yuvasını yeniden kullanır: yuva, iç ifade değerlendirilmeden önce takılır ve sonra geri yüklenir; böylece SQL ifade mekanizmasının geri kalanı hiçbir zaman farkı bilmez.
Yürütücünün gördüğü model küçüktür: DEFINE ifadesinin değerlendirildiği satırı tutan bir geçerli satır yuvası ve çalışma zamanının geçici olarak farklı bir satıra yönlendirebileceği bir gezinme yuvası vardır. Çalışma zamanı, herhangi bir gezinme çağrısının çevresinde gezinme yuvasını ayarlar, iç ifadeyi sanki geçerli satırı okuyormuş gibi değerlendirir, sonra orijinal satırı geri yükler. Sözde kod:
eval_navigation(call):
targetPos = compute_target_position(call)
if targetPos geçerli aralığının dışındaysa:
return NULL
current_row_slot'u kaydet
if targetPos != currentPos:
targetPos'taki satırı
nav_slot'a getir
dış yuvayı nav_slot'a yönlendir
result = eval_inner_expression()
current_row_slot'u geri yükle
by-ref sonucu nav_slot'tan kopyala
return result
Hile, kaydedilip geri yüklenecek tam olarak bir yuva olmasıdır. İç ifade — aritmetik, işlev çağrıları veya diğer sütun referansları dahil her ne ise — geçerli satır için kullanacağı aynı değerlendirme yolunu kullanarak takas edilen yuvaya karşı çalışır. Alternatif değerlendirici yok ve başvuru başına yuva yok; hedef geçerli satır olduğunda getirme ve takas tamamen atlanır. Getirme, hedef satırı gezinme yuvasına kopyalar (yuva onu zaten tutmuyorsa) ve geri yükleme adımı, sonraki getirmenin onu serbest bırakamaması için başvuruyla geçirilen (pass-by-reference) bir sonucu tuple başına belleğe kopyalar.
Bileşik gezinme, takasın hâlâ bir kez gerçekleşmesi için ayrıştırma zamanında düzleştirilir. PREV(FIRST(price)) iki adımlı bir gezinme olarak tanınır — "ilk eşleşmiş satıra git, ardından bir satır önceye adımla" — ve bileşik türde tek bir gezinme çağrısı olarak saklanır. Çalışma zamanı hedef konumu iki aşamada hesaplar ama son satırı getirmek için yalnızca tek bir yuva takası gerçekleştirir:
compute_target_position(call):
# geçerli satıra göreli
PREV(n):
return currentPos − n
NEXT(n):
return currentPos + n
# eşleşmeye göreli
FIRST(n):
return matchStart + n
LAST(n):
return currentPos − n
# bileşik: eşleşmeye göreli, sonra adımla
PREV(FIRST(n), m):
return (matchStart + n) − m
NEXT(FIRST(n), m):
return (matchStart + n) + m
PREV(LAST(n), m):
return (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − n) + m
uygun aralığa karşı doğrula
(FIRST/LAST iç için eşleşme aralığı,
dış adım için bölüm aralığı)
Aynı DEFINE'daki birkaç gezinme çağrısı aynı satırı hedeflediğinde — price > PREV(price) AND volume > PREV(volume) gibi her iki çağrının önceki satıra çözüldüğü yaygın ifadeler gibi — bir konum önbelleği tuplestore getirmesini kısa devre yapar. Önbellek yalnızca "son getirilen konumu" saklar ve takasın kendisi tek bir işlem olarak kalır.
Gezinme çağrılarının sınıflandırılması, planlayıcının emilim kararına katkısıdır. Planlayıcı her DEFINE ifadesini dolaşır ve her değişkeni iki kovadan birine ayırır; tüm bağlamların aynı satırda aynı Boole değerini hesaplayıp hesaplamayacağına ya da her bağlamın kendininkini hesaplayıp hesaplamayacağına dayanır. Kova çalışma zamanında iki şeyi belirler: değişkenin ne sıklıkla değerlendirildiği (bir kez paylaşılmış veya etkilenen bağlam başına bir kez — §3.5 1. Aşama) ve bağlam emiliminin hiç mümkün olup olmadığı (§2.5 vs §2.6): eşleşme başlangıcına bağımlı tek bir değişken, onu tüm örüntü için devre dışı bırakır.
- Gezinme yok
- Yalnızca
PREV/NEXT - Ofsetsiz
LAST - İç
LASTile bileşik (ofsetsiz)
- Ofsetli
LAST FIRST(herhangi biçim)- İç
FIRSTile bileşik - İç
LASTile bileşik (ofsetli)
Sınıflandırma plan zamanında gerçekleştirilir ve her DEFINE değişkeninin yanında saklanır, dolayısıyla çalışma zamanı karar vermek için zaman harcamaz — bir satırı işlerken her değişken için kovayı basitçe okur.
Tutma bütçesi
Gezinme, pencere işlevi mekanizmasının aksi takdirde akıtıp geçtiği satırlara erişir. Bu satırları erişilebilir tutmak için yürütücü, son satırların kayan bir penceresini tutan bir tuplestore üzerine inşa edilmiştir; soru, o pencerenin ne kadar geniş olması gerektiğidir. Yürütücü bunu iki tamamlayıcı ofsetten hesaplar ve her ofseti tarama başına bir kez çözümler (sabit olanları ayrıca yürütücü başlatılırken de, böylece düz EXPLAIN bunları gösterebilir):
- Geriye bakma bütçesi
- Herhangi bir DEFINE çağrısının geçerli satırdan ne kadar geriye uzanabileceği.
- Başlangıçtan ileriye bakma bütçesi
- En eski canlı bağlamın eşleşme başlangıcından en küçük ileri uzanım (negatifse geriye) — herhangi bir DEFINE çağrısının ihtiyaç duyabileceği en erken satır.
Çalışma zamanında tuplestore'un kırpma işareti, iki konumdan hangisi daha erkense ona ayarlanır — geçerli satır eksi geriye bakma bütçesi ve en eski canlı bağlamın eşleşme başlangıcı artı ileriye bakma bütçesi. Bu işaretten önceki hiçbir şey, herhangi bir canlı bağlamdaki herhangi bir gezinme çağrısı tarafından erişilemez ve tuplestore bunu düşürmekte serbesttir. EXPLAIN'in raporladığı Nav Mark satırları (§3.7) — Lookback ve Lookahead — ölçülen tepe değerleri değil, bu iki bütçedir. Her biri yalnızca onu besleyen bir gezinme olduğunda yazdırılır ve ANALYZE olmadan da gösterilir; değeri yalnızca çalışma zamanında bilinen bir ofset (örneğin bir generic-plan parametresi) düz EXPLAIN altında runtime, EXPLAIN ANALYZE altında ise çözümlenmiş değerini yazdırır; retain all (Lookback) veya infinite (Lookahead) taşan bir ofseti belirtir.
3.4 Eşleşme sınırları — SKIP, INITIAL ve sınırlı çerçeve
Bir eşleşme sonucu iki değer olarak kaydedilir: eşleşmenin başladığı satır ve uzunluğu. Negatif bir başlangıç, konumun henüz değerlendirilmediği anlamına gelir; başlangıç ayarlandığında, yürütücüye yönelik sonraki sorgular — "bu satır bir eşleşmenin içinde mi?" — çifte bakarak O(1) ile yanıtlanabilir. Uzunluk sonucu kodlar: eşleşmeyen bir satır için -1, boş bir eşleşme için 0 ve gerçek bir eşleşme için satır sayısı. Sıfır uzunluk bir hata değil, gerçek bir sonuçtur: hiçbir satır tüketmeden eşleşen bir örüntüyü temsil eder ve yürütücünün bunu hem eşleşmeyen bir satırdan hem de "bu konumda henüz eşleşme denenmedi"den ayırması gerekir.
AFTER MATCH SKIP yan tümcesi, sonraki eşleşme denemesinin nereden başlayacağına karar verir. AFTER MATCH SKIP PAST LAST ROW eşleşme sonundan sonraki satıra geçer, çoğu sorgunun istediği örtüşmeyen çıktıyı üretir ve emilim optimizasyonunu etkinleştirir.
AFTER MATCH SKIP TO NEXT ROW yalnızca eşleşme başlangıcından sonraki satıra geçer, örtüşen eşleşmelere izin verir; bu nedenle bu mod yürürlükteyken planlayıcı o pencerenin örüntüsü için emilimi devre dışı bırakır.
Standardın tanımladığı diğer iki atlama hedefi — AFTER MATCH SKIP TO FIRST değişken ve AFTER MATCH SKIP TO LAST değişken — bu yamanın tutmadığı eşleşme başına tarihçeye bağlıdır. Bunlar dilbilgisinde hiç bulunmaz, bu nedenle ikisinden biri verilirse ayrıştırıcı genel bir sözdizimi hatası verir.
Aynı şey, spesifikasyonun INITIAL'a alternatifi olan SEEK için de geçerlidir. SEEK altında, R satırından başlayan bir eşleşme denemesi, yalnızca R'de değil, R'den çerçevenin sonuna kadar herhangi bir satırda başarılı olabilir. Yama yalnızca INITIAL'ı gerçekler: her potansiyel eşleşme belirli bir satıra çapalanır. SEEK istenirse ayrıştırıcı bir hata verir. Sınırlı çerçeveler kendi muamelesini alır — kullanıcı UNBOUNDED FOLLOWING yerine ROWS BETWEEN CURRENT ROW AND N FOLLOWING yazdığında, yürütücü eşleşmesi sınıra ulaşmış herhangi bir bağlamı bir uyumsuzluk zorlayarak kısa devre yapar ve emilim devre dışı bırakılır, çünkü sınır, emilimin dayandığı monotonluk varsayımını kırar.
3.5 Üç aşamalı satır başına motor
Yürütücünün satır başına sürücüsü, çevredeki pencere işlevi mekanizması tarafından, belirli bir satırın eşleşmiş bir çerçeveye ait olup olmadığını bilmesi gerektiğinde çağrılır. Sürücü, geçerli başlangıç konumu için bağlamı bulur veya oluşturur, ardından NFA'yı satır satır ileriye sürer — her satır için değişken başına bir eşleşme dizisini "değerlendirilmemiş" durumuna sıfırlayarak — ta ki o bağlamda canlı durum kalmayana ya da bölüm bitene kadar. DEFINE yüklemleri tembel olarak değerlendirilir: bir değişken, bir durum onu ilk kez tükettiğinde değerlendirilir; dolayısıyla bu satırda hiçbir canlı durumun sınamadığı bir değişken hiç değerlendirilmez. İleri adımın kendisi sabit sırayla üç aşamadır — Eşleştir, Em, İlerle — aynı dış döngüde sarılmıştır:
processRow(currentPos):
# 1. Aşama — EŞLEŞTİR (yakınsama)
for each context:
if bağlam çerçeve sonuna ulaştıysa:
uyumsuzluğu zorla (erken kesinleştir)
continue
if matchStartRow paylaşılan
değerlendirme konumundan farklıysa:
eşleşme başlangıcına bağımlı
DEFINE değişkenlerini değerlendirilmemiş
durumuna sıfırla (§3.3)
match(context, varMatched)
# 2. Aşama — EM
if örüntü emilebilirse:
her bağlamın bayraklarını yenile
absorb_contexts()
# 3. Aşama — İLERLE (ıraksama)
for each context:
advance(context, currentPos)
if bir eşleşme kaydettiyse ve
SKIP PAST LAST ROW ise:
eşleşmenin içinde başlayan
sonraki bağlamları buda
Sıralama bir biçim seçimi değildir. Eşleştir önce çalışmalıdır, çünkü emilim eşleşme sonrası sayıları karşılaştırır; Em'i Eşleştir'den önce çalıştırmak, ölmek üzere olan durumları karşılaştırırdı. İlerle en son çalışmalıdır, çünkü yeni durumlar yaratan tek aşamadır — hayatta kalan her durumu, her dal sonraki satırı bekleyen bir değişkene veya FIN nöbetçisine ulaşana kadar epsilon geçişleri yoluyla genişletir. Em'i İlerle'den sonra çalıştırmak, ıraksamış ardılları karşılaştırmak demek olurdu ve durumların en temiz şekilde karşılaştırılabileceği noktayı kaçırırdı.
1. Aşama — Eşleştir
Eşleştir bir "yakınsama" aşamasıdır: durumlar ya artırılmış sayı ile hayatta kalır ya da ölür. İnce bir nokta şudur: emilebilir bir bölgede oturan değişkenler için Eşleştir, Em'in temiz karşılaştırma yapabilmesi için küçük bir miktar ileri ilerleme de gerçekleştirir. Kapsama koşulu yalnızca emilebilir karşılaştırma noktasında — sınırsız grubun END'inde — ateşlenir, dolayısıyla yineleme ortası değişkenleri (örneğin (A B)+ içindeki B) yeni eşleştirmiş durumların Eşleştir sırasında o karşılaştırma noktasına kadar yürütülmesi gerekir; aksi takdirde Em karşılaştırılacak uygun bir şey bulamaz ve optimizasyon hiçbir zaman devreye girmez.
match(context, varMatched):
for each state in context:
elem = pattern[state.elemIdx]
assert elem bir değişkendir
# advance yalnızca değişkenlerde bekletir
if varMatched[elem.varId]
değerlendirilmemişse:
DEFINE'ını şimdi değerlendir
if not varMatched[elem.varId]:
drop state # ölü dal
continue
state.counts[elem.depth] += 1
# Sonraki aşamanın yineleme
# ortası yerine karşılaştırma
# noktası öğesinde karşılaştırma
# yapabilmesi için satır içi ileri ilerleme.
if elem bölge içindeyse ama
karşılaştırma noktası değilse,
ve max sayısına ulaştıysa,
ve elem.next bir grup sonu ise:
END zincirini yürü:
dış grup sayısını artır
state.elemIdx'ı END'e ilerlet
hâlâ bölge içinde, çıkmak
zorunda ve next END iken devam et
(karşılaştırma noktasında veya
hâlâ döngülenebilir bir öğede durur)
END zinciri yürüyüşü, iç içe sabit uzunluklu grupları emilebilir kılan şeydir. ((A B){2})+'da, B max'a ulaştığında (B, {1,1}'dir), iç grubun sayısı artmalıdır; o sayı da max'a ulaşırsa — iç {2}'yi kapatarak — dış grubun sayısı da artmalıdır ve böyle devam eder; ta ki durum en dıştaki emilim noktasına — sınırsız dış grubun (+) END'ine — düşene kadar. Bu işi Eşleştir'de yapmak, Em'in yineleme sonrası sayılarını zaten konsolide etmiş bağlamlara karşı karşılaştırma yapmasını sağlar.
2. Aşama — Em
Em geçişi bağlamları en yenisinden (kuyruktan) en eskisine (başa) doğru yürür. Tamamen emilebilir olan, devam eden her bağlam için, kendisini kapsayan daha eski, devam eden bir bağlam için geriye doğru tarar ve bulursa daha yenisini serbest bırakır. Bağlamlar oluşturma sırasıyla tutulduğundan ve her satır en fazla bir bağlam oluşturduğundan, "daha yeni" ve "daha eski" gerçekten "daha sonra başlamış" ve "daha önce başlamış" anlamına gelir.
absorb_contexts():
for ctx kuyruktan geriye:
if ctx bitti
veya emilebilir olmayan herhangi bir durumu varsa
veya kaydedilmiş bir eşleşme tutuyorsa:
skip
for older ctx.prev'den geriye:
if older bitti
veya emilebilir durumu yoksa:
skip
if covered(older, ctx):
free(ctx)
emilim uzunluğunu kaydet
break
covered(older, newer):
for each state in newer:
elem = pattern[state.elemIdx]
if elem karşılaştırma noktası değilse:
return false
if older'da şu özelliklere sahip durum yoksa:
aynı elemIdx
ve isAbsorbable
ve older.counts[depth]
>= newer.counts[depth]:
return false
return true
Bundan iki mikro karar çıkar. İlki, kapsama kontrolünün, yeni bağlamdaki herhangi bir durum karşılaştırma noktası dışında bir yerdeyse hemen reddetmesidir — yargı dışı noktalarda karşılaştırma anlamlı bir karşılaştırma olmazdı.
İkincisi, her bağlamdaki asimetrik bayrak çiftidir: has-absorbable-state, "bu bağlam daha yeni bir bağlamı emebilir mi?" sorusuna yanıt verir ve monotondur (yalnızca durumlar öldükçe true→false gidebilir); oysa all-states-absorbable, "bu bağlam emilebilir mi?" sorusuna yanıt verir ve dinamiktir (emilebilir olmayan bir durum kaldırıldığında true'ya geri döner), ta ki bağlam bir eşleşme kaydedene kadar; bu onu false'a sabitler — emmek, hiçbir emen bağlamın yeniden üretemeyeceği bir eşleşmeyi serbest bırakırdı. Her iki bayrak da kapsama taraması başlamadan bile önce sabit zamanda kontrol edilir, dolayısıyla emilim tam maliyetini yalnızca emilme şansı gerçekten olan bağlamlarda öder.
3. Aşama — İlerle
İlerle "ıraksama" aşamasıdır: hayatta kalan her durum, her dal ya sonraki satırı bekleyen bir değişkene ya da FIN nöbetçisine ulaşana kadar epsilon geçişleri yoluyla genişletilir. Genişletme derinliğine önceliklidir ve kardeş dalların yürütüldüğü sıra, standardın tercih kuralının gerçekten yürürlüğe girmesini sağlayan şeydir — sözcüksel olarak ilk dal her zaman önce eklenir ve durum eklemedeki tekilleştirme adımı, eşdeğer sonraki eklemeleri sessizce atar.
advance(context, currentPos):
tüm mevcut durumları çıkar;
ctx.states'i sıfırdan yeniden inşa et
her durum için sözlük sırasında:
ziyaret bit haritasını temizle
advance_state(state) # DFS
# Tercih: bir DFS FIN'e ulaştığında,
# kalan durumlar daha az tercih edilir
# ve atılabilir.
if FIN'e ulaşıldı ve durumlar kaldıysa:
kalanları serbest bırak
break
advance_state(state):
state.elemIdx üzerinden yürü,
şunlardan özyinele:
ALT dalları (sırayla, FIN
kaydedilince durarak),
BEGIN (gruba gir; ayrıca min = 0 ise
isteğe bağlı atlama yolu),
END (geri döng / çıkış / hızlı ileri sarma —
aşağıya bakın),
FIN (matchEndRow'u kaydet,
matchedState'i sakla ve bağlamı
işaretle ki bu adayın aralığındaki
sonraki bağlamlar budansın —
aşağıya bakın),
karşılaşılan her değişkende durarak:
durumu ctx.states'a ekle
(elemIdx + counts ile tekilleştir)
FIN'e ulaşan bir durumu kaydetmek yalnızca aday eşleşmeyi yer imlemekten fazlasını yapar. AFTER MATCH SKIP PAST LAST ROW altında, raporlanabilir sonraki eşleşme kesinlikle mevcuttan ilerde başlamalıdır — bu yüzden İlerle, bir aday kaydeden bağlamla işini bitirdiğinde, başlangıç satırı adayın aralığına düşen sonraki her bağlam aynı satırda budanır; FIN'e ulaşan bağlam açgözlü geri dönüş yoluyla daha uzun bir eşleşme aramaya devam ediyor olsa bile.
Bu budama güvenlidir, çünkü o arama nasıl biterse bitsin (daha uzun bir eşleşme adayın yerini alır veya aday kalır), budanan tüm bağlamlar, raporlanabilir sonraki eşleşmenin atlamak zorunda olduğu bir aralığın içinde başlamıştır ve bu nedenle kendi başlarına asla çıktı üretemezler.
Bu, bağlamlar arası FIN-zamanı budama adımıdır. Bağlamın içinde FIN, sözcüksel olarak aşağı işi de keser: İlerle kuyruktaki kalan durumları düşürür (bu bölümde daha önce açıklandı) ve tek bir DFS içinde daha az tercih edilen her yol — sonraki ALT dalları, BEGIN'in atlama ve girme yollarından diğeri, gönülsüz bir değişkenin girme yolu, END'in döngü ve çıkış yollarından diğeri — bir eşleşme kaydedildiğinde durur; böylece tek bir ilerleme en fazla bir eşleşme kaydeder.
En zor öğe başına mantık END işleyicisindedir. Bir grubun yineleme sayısı alt sınırın altındayken, çalışma zamanı geriye dönmek zorundadır; üst sınırda veya üzerindeyken, çıkmak zorundadır; arada, her iki seçenek de geçerlidir ve önce hangisinin denenmesine niceleyicinin açgözlülüğü karar verir:
advance_end(state, elem):
count = state.counts[elem.depth]
if count < elem.min:
gövdeye geri döng
if elem boş-döngülenebilir ise:
# nullable gövde, §3.2'ye bakın
ayrıca grubu sayım karşılanmış
olarak terk eden bir hızlı ileri
sarma durumu klonla
(gövde boşu tercih ediyorsa
önce hızlı ileri sarma; ilk
yol FIN'e ulaştıysa ikinci
yol düşürülür)
elif count >= elem.max:
bu derinlikteki sayıları sıfırla
next üzerinden çık
(END→END: dış END'in
sayısını artır)
else:
# min <= count < max: dallan
bir çıkış durumu kur
(bu derinlikteki sayılar sıfırlanır)
if greedy:
önce döng
if döngü FIN'e ulaştıysa:
çıkışı at
# daha uzunu tercih et
aksi takdirde ikinci olarak çık
else (reluctant):
önce çık
if çıkış FIN'e ulaştıysa:
döngüyü at
# daha kısayı tercih et
aksi takdirde ikinci olarak döng
Bir bağlama eklenen her durum, konumunu ve sayılarını mevcut durum listesiyle karşılaştıran bir tekilleştirme kontrolünden geçer. İlerle, dalları DFS sırasıyla işlediği için, herhangi bir seçeneğin ilk dalından gelen durum önce düşer — ve aynı konumu ve sayıları üreten herhangi bir sonraki dal eklemede reddedilir. Bu tam olarak §2.4'ün sözcüksel sıra kuralının istediği şeydir, ayrı bir geçiş olmadan çalışma zamanının dibinde gerçeklenir.
Boş-döngülenebilir gruplar
Çalışma zamanının etkisizleştirmesi gereken ince bir durum nullable grup'tur — gövdesinin her çocuğu kendi başına isteğe bağlı olduğundan gövdesi sıfır satırla eşleşebilen bir grup. (A? B?)+ ve (A | B*)+ gibi örüntüler bu özelliğe sahiptir: veriye bağlı olarak, gövde hiç satır tüketmeden bir yinelemeyi tamamlayabilir. ((A?)* gibi tek bir isteğe bağlı çocuk derleme zamanında A*'a yeniden yazılır ve geride grup bırakmaz.) Bu prensipte iyidir, ama NFA'nın epsilon genişletmesi için gerçek bir tehlike yaratır. Gövde boş bir eşleşme üretirse, END öğesi gövdeye geri döner (jump'ı grubun ilk çocuğudur), gövde yine boş bir eşleşme üretir, yine END'e ulaşır ve böyle devam eder. Onu durduracak bir şey olmadan İlerle'nin DFS'i asla sonlanmazdı.
Koruma derleme zamanında kararlaştırılır ve çalışma zamanında uygulanır. Planlayıcı, gövdesi nullable olan bir grup gördüğünde, o grubun END öğesini boş-döngülenebilir olarak etiketler. Çalışma zamanı, her durumun DFS genişletmesinden önce temizlenen bir ziyaret bit haritası tutar ve bu haritada yalnızca bu etiketli END'ler işaretlenir — başka hiçbir şey döngü oluşturamaz, çünkü diğer her geri döngü bir satır tüketmiştir. İşaretli bir END'e ulaşmak, gövdenin az önce boş bir yineleme türettiği anlamına gelir ve durum atılmaz: alt sınırda veya üzerinde grubu orada terk eder (boş bir yineleme niceleyiciyi durdurur), altında ise durum normal geri döngüye düşer; böylece her boş varış sayıyı min'e ulaşana kadar yine artırır. Hiçbir değişkenin satır akışında hiçbir yerde eşleşmediği (A? B?){2,3}'ü ele alın:
yin 1: A? B? sıfır satırla eşleşir
→ END, sayı = 1 (min altı)
END zaten işaretli (gruba
girişte), ama min altında:
→ A?'ya geri döng
yin 2: A? B? sıfır satırla eşleşir
→ END, sayı = 2 (min karşılanır)
END zaten işaretli, min'de:
→ grubu terk et
sıfır uzunluklu eşleşmeyle çık
Alt sınırın altında boş-döngü etiketi ayrıca END işleyicisine, normal geri döngü yolunun yanı sıra ek bir hızlı ileri sarma durumu klonlamasını söyler:
advance_end (sayı min altında):
geri döngü yolu:
gövdeye geri döng
(sonraki yinelemede gerçek,
boş olmayan bir eşleşme için
kapıyı açık tutar)
if elem boş-döngülenebilir ise:
hızlı ileri sarma yolu:
bu derinliğin sayısını sıfırla
grubu next üzerinden terk et,
kalan gerekli yinelemeleri
boş eşleşmeler olarak ele alarak
İki yol tamamlayıcı roller oynar. Geri döngü, gövdenin daha sonra üreteceği gerçek eşleşmeleri olduğu durumu yakalayan şeydir — örneğin, (A? B?){2,3}'ün ardından A'nın yalnızca sonraki satırlarda eşleştiği veride, geri döngü ikinci ve üçüncü yinelemelerin boş olmayan eşleşmeler bulmasına olanak tanır. Hızlı ileri sarma grubu hemen terk eder, "gerekli yinelemelerin geri kalanı boştur" der ve eşleşmenin sıfır uzunluklu bir gövde ile başarılı olmasını sağlar. Sırayı grubun kendi açgözlülüğü değil gövde belirler: hızlı ileri sarma tam olarak gövde boş eşleşmeyi tercih ettiğinde önce gelir ((A?? B??) gibi gönülsüz bir gövde) ve ilk yol FIN'e ulaşırsa ikincisi düşürülür; böylece daha az tercih edilen bir yol tercih edilen eşleşmenin yerini alamaz. Eklemedeki tekilleştirme kontrolü, her iki yolun payından fazla durum üretmesini önler.
Döngü korumasının ötesinde, bir başlangıç hilesi bağlamın en başında sıfır satırlı sonuçları belirsizlikten kurtarır. Her potansiyel başlangıç satırındaki bağlam oluşturma adımı, gerçek başlangıçtan bir satır önceki bir konumu kullanarak, herhangi bir satır tüketilmeden önce epsilon geçişleri yoluyla bir başlangıç ilerlemesi çalıştırır. Yalnızca epsilon geçişleri yoluyla — bir satır tüketmeden — FIN nöbetçisine ulaşan herhangi bir yol bu nedenle başlangıç konumundan daha küçük bir bitiş konumu üretir; bu negatif aralıklı koordinat, FIN'e gerçekten ulaşılıp ulaşılmadığıyla birleştiğinde, ayrı bir bayrak gerektirmeden boş bir eşleşme (uzunluk-0 eşleşme kabul edildi) ile eşleşmeyen bir başlangıç arasındaki farkı kodlar.
3.6 Durum uzayı nasıl sınırlı kalır
Çalışma zamanını sınırlı tutmak tek bir optimizasyonun sonucu değildir. Her biri satır başına döngünün farklı bir noktasında durum uzayı büyümesinin farklı bir nedenini yakalayan, katmanlı bir budama kuralları kümesinin kümülatif etkisidir. Bazıları derleme zamanında kararlaştırılır ve çalışma zamanında yalnızca başvurulur; bazıları dinamik olarak ateşlenir. Bazıları tek tek durumları öldürür; bazıları tüm bağlamları öldürür. Yukarıdaki bölümler bunların her birini bağlamında tanıttı; aşağıdaki tablo bunları tek bir sayfaya koyar.
- Başarısız yüklem Eşleştir
- DEFINE'ı geçerli satırda yanlış değerlendirilen değişken durumları — ölü dallar.
- Satır içi END zinciri ilerlemesi Eşleştir
- Max sayısına ulaşmış ve aksi takdirde durumu yineleme ortasında bırakacak değişkenler; emilim doğru noktada karşılaştırma yapabilsin diye sabit uzunluklu grup sonları boyunca ilerletilir.
- Bağlam emilimi Em
- Her durumu bir karşılaştırma noktasında oturan ve daha eski bir bağlamın aynı öğedeki, büyük veya eşit sayılı emilebilir bir durumuyla kapsanan daha yeni bağlamlar — kavramsal kural için §2.5'e, derleme zamanı uygunluğu için §3.2'ye, çift başına kontrol için §3.5'e bakın.
- Durum tekilleştirme İlerle
- Aynı konumda aynı sayılarla biten farklı DFS dalları aracılığıyla ulaşılan durumlar — yalnızca ilki (sözcüksel olarak en erken) hayatta kalır; sonraki eşdeğerler sessizce atılır; bu aynı zamanda tercihin nasıl uygulandığıdır (§2.4).
- FIN erken sonlandırma (bağlam içinde) İlerle
- Bir dal FIN'e ulaştığında DFS kuyruğunda hâlâ bekleyen durumlar — sözcüksel sıraya göre, kalan tüm durumlar daha az tercih edilir ve hemen atılabilir.
- Aday eşleşme budama (bağlamlar arasında) İlerle
- Başlangıç satırı aday eşleşmenin aralığına düşen diğer bağlamlar — FIN'e ulaşan bağlam daha uzun bir eşleşme aramaya devam edebilir (açgözlü geri dönüş), ancak
AFTER MATCH SKIP PAST LAST ROWaltında, adayın aralığındaki herhangi bir bağlam, o aramanın nasıl bittiğinden bağımsız olarak artık raporlanabilir bir çıktı üretemez ve İlerle, adayı kaydeden bağlamla işini bitirir bitirmez budanır. - Döngü koruması İlerle
- Aynı DFS içinde zaten işaretlenmiş (BEGIN üzerinden girişte veya daha önceki bir varışta işaretlenen) nullable bir grubun END'ine ulaşan epsilon genişletmeleri — aksi takdirde sonsuza kadar döngü oluştururdu; durum alt sınırda veya üzerinde grubu orada terk eder, altında ise döngüye devam eder.
- Boş-döngü hızlı ileri sarma İlerle
- Nullable bir grubun alt sınırının altında, kalan gerekli yinelemeler boş ilan edilerek grubu terk eden ek bir yol; geri döngüye göre sırası gövdenin tercihiyle belirlenir.
- Sınırlı çerçeve kesimi Eşleştir
- Eşleşmesi kullanıcının belirttiği çerçeve üst sınırına ulaşan bağlamlar — onu aşmamaları için uyumsuzluğa zorlanır (§3.4).
Girişleri aşama rozetlerine göre okumak bir bağlamın yaşam süresini izler: budama, üç ana aşama (Eşleştir, Em, İlerle) boyunca her satırda ateşlenir. Açıklamaları okumak ise kuralları hedefledikleri şeye göre gruplar: ölü dallar, gereksiz bağlamlar, eşdeğer durumlar, sonsuz döngüler ve kullanıcı tarafından dayatılan sınırların ötesine genişleme.
Hiçbir tek kural tek başına yeterli olmazdı. Boş-döngü hızlı ileri sarma tek başına sonsuz epsilon döngülerini durdurmazdı; emilim tek başına DEFINE eşleşme başlangıcına başvurduğunda aşırı konsolide ederdi; tekilleştirme tek başına gereksiz bağlamları değil, yalnızca gereksiz durumları kaldırırdı. Çalışma zamanı önemli olan durumlarda doğrusal kalır — 100.000 satırda PATTERN (A+ B+ C+ D), posterin ③ paneli kıyaslaması — yalnızca her katman, üstündeki katmanların kaçırdığını yakaladığı için. Kaynak kod, katmanların yakalamadığı durumları belgeler: tekilleştirme yalnızca min üzerindeki sayılarda farklılaşan durumları ayrı tutar, bu yüzden C'nin hiç doğru olmadığı (A{2,} B)+ C tepe noktada Θ(n²) durum tutar ve Θ(n³) durum oluşturur (320 satır üzerinde 37 s); tamamen nullable seçeneklerden oluşan bir dizi ise yol yol numaralandırılır, bu yüzden (A?|B?){30} yarım saatten uzun sürer.
3.7 EXPLAIN çıktısı
RPR'lı bir sorguda EXPLAIN ANALYZE, sıradan pencere işlevleri için bulunmayan NFA düzeyinde istatistikleri ortaya çıkarır. Metin biçiminde bunlar pencere operatörünün yanında, Pattern: satırından, varsa Nav Mark satırlarından (düz EXPLAIN de bunları gösterir) ve Storage: satırından sonra yayılır:
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(her biri yalnızca DEFINE onu besleyen
gezinme kullandığında)
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)
(ikinci NFA satırı yalnızca sayılardan
biri sıfır değilse; sıfır bir sayı
(len ...) olmadan yazdırılır)
Metin dışı biçimler her sayıyı kendi özelliği olarak yayar. Peak ve total, çalışma zamanının doğrudan ölçümüdür: aynı anda kaç durumun canlı olduğunu, sorgunun yaşam süresi boyunca kaçının oluşturulduğunu ve tekilleştirme tarafından kaçının birleştirildiğini gösterir; pruned, tek bir satırdan sonra başarısız olan bağlamları sayar. Eşleşme uzunluğu histogramları dört sonucu ayırır — başarılı eşleşmeler, birden fazla satırdan sonra başarısız olan eşleşme denemeleri (mismatched), emilen bağlamlar ve kaydedilmiş bir eşleşmenin içinde başladıkları için AFTER MATCH SKIP PAST LAST ROW tarafından serbest bırakılan bağlamlar (skipped) — ve bunları min/max/avg ile raporlamak performans patolojilerini bir bakışta görünür kılar: sağlıklı bir çalışma, bağlamların çoğunu eşleşmiş veya emilmiş olarak gösterir; uyumsuz uzunluklar küçüktür.
İki Nav Mark sayacı, §3.3'ün DEFINE'dan türettiği tuplestore tutma bütçesini raporlar. Lookback, geçerli satırdan PREV, herhangi bir ofsetli (varsayılan 0 dahil) LAST ve iç LAST'lı bileşik biçimlerdeki en derin geriye uzanmadır; Lookahead, en eski canlı bağlamın eşleşme başlangıcından ölçülen, FIRST ve iç FIRST'li bileşik biçimler tarafından katkılanan en küçük ileri uzanmadır (eşleşme başlangıcından önceye baktığında negatif).
Her sayaç, ofset sabit olduğunda sabit bir tamsayı olarak; ofset yalnızca tarama başına bilinen sabit olmayan bir ifade olduğunda "runtime" olarak; ve — yalnızca Lookback için — ofset taştığında "retain all" olarak yazdırılır; taşan bir Lookahead "infinite" yazdırır. Her satır yalnızca DEFINE içindeki bir gezinme onu beslediğinde yayılır ve her ikisi de düz EXPLAIN altında da görünür: sabit ofsetler yürütücü başlatılırken belirlenir, değeri yalnızca çalışma zamanında bilinen bir ofset (örneğin bir generic-plan parametresi) ise orada "runtime", EXPLAIN ANALYZE altında ise çözümlenmiş tamsayısını yazdırır.
Bu sayaçlar birlikte, arka uca gdb iliştirmeden RPR performansını ayıklamayı mümkün kılar.
Sayaçların ötesinde, EXPLAIN derlenmiş öğe dizisinden kurulan bir Pattern: satırı yazdırır; dolayısıyla örüntüyü derleme zamanı yeniden yazmalarından sonraki haliyle gösterir (PATTERN (A A), a{2} olarak açıklanır) ve # (karşılaştırma noktası) ile ~ (emilebilir bölge) emilim işaretlerini taşır; DEFINE ve AFTER MATCH SKIP seçeneği gösterilmez. Yan tümceleri gönülsüz niceleyiciler, grup tekrarı ve atlama seçeneği dahil yazıldığı gibi yeniden üretmek pg_get_viewdef()'in işidir; bu işlev, pg_dump ve pg_upgrade'in RPR nesnelerini anlamsal kayma olmadan koruyabilmesi için bu gidiş-dönüşü kararlı kılmak için belli bir çaba harcar — rpr_explain altındaki regresyon paketi bunu durum durum doğrular (bkz. §4).
§4. Testler — Kapsam Haritası
Yama, §3'te açıklanan her katmanı birlikte sınayan beş regresyon paketiyle birlikte gelir — kabaca 22.000 satır SQL, her paket farklı bir kaygıya odaklıdır. Bölüm bilinçlidir: ayrıştırıcı kaygılarını, çalışma zamanı doğruluğunu, planlayıcı etkileşimlerini ve çıktı biçimlendirmesini ayrı dosyalarda tutmak, başarısızlıkları konumlandırmayı kolaylaştırır ve bir katmandaki ilgisiz bir değişikliğin başka bir katmandaki testleri yanlışlıkla geçersiz kılmasını önler. Beş paket şunlardır:
- rpr
- WINDOW yan tümcesi entegrasyonu — sentetik hisse senedi verisinde gerçekçi pencere senaryoları (V şekli, W şekli, ardışık yükselişler, tersine çevirmeler), ayrıca gezinme anlamları ve DEFINE kısıtlama hataları.
- rpr_base
- Ayrıştırıcı katmanı — anahtar sözcük kabulü, sözdizimi biçimleri, niceleyiciler, gezinme ayrıştırma, hata mesajları ve pg_dump/pg_upgrade gidiş-dönüş kararlılığı; ayrıca bir planlayıcı katmanı — örüntü optimizasyonu, emilim bayrakları, optimizasyon geri dönüşü, planlayıcı entegrasyonu.
- rpr_nfa
- NFA çalışma zamanı — üç aşamalı döngü, her emilebilir biçimde emilim ve bağlam yaşam döngüsü uç durumları.
- rpr_explain
- Çıktı biçimlendirmesi — NFA istatistikleri, örüntü deparse, tanımlayıcı tırnaklama, yeniden yükleme boyunca biçim kararlılığı.
- rpr_integration
- Planlayıcı etkileşimleri — ilgisiz pencere optimizasyonlarının RPR anlamlarını bozmasını önleyen korumalar.
4.1 rpr — uçtan uca senaryolar
Senaryo paketi, test setinin halka açık yüzüdür: yaklaşık 1.600 satırlık sentetik bir hisse fiyatı veri kümesi kullanır ve buna karşı gerçekçi sorgular çalıştırır — V şekli toparlanma, W şekli (çift dip), ardışık yükselişler ve düşüşler, tersine çevirme örüntüleri, çoklu sembol bölümleri. Girdi ve çıktıları kullanıcının gerçekten yazabileceği sorgular gibi okunan tek testler bu senaryolardır; dosyanın geri kalanı, diğer paketler gibi, indirgemecidir — PREV/NEXT iç içe geçirme ve sabit olmayan ofset hataları, DEFINE referans kuralları ve gezinme ofseti anlamları.
Bu sorgular her katmanı (ayrıştırıcı, planlayıcı, yürütücü, EXPLAIN) birleştirdiğinden, rpr'daki tek bir başarısızlık size hatanın nerede olduğunu nadiren söyler. Takip eden dört paket biseksiyondur: rpr'da bir başarısızlık artı geçen bir rpr_base ayrıştırıcıyı eler; artı geçen bir rpr_nfa bunu senaryoya özgü veri biçimlerine daraltır; artı geçen bir rpr_integration planlayıcı müdahalesini eler; herhangi bir deparse kayması rpr_explain'de ortaya çıkar.
4.2 rpr_base — ayrıştırıcı yüzeyi
Temel paket en büyüğüdür ve bir nedenle en büyüğüdür: §1.2'deki her yasal sözdizimi parçasının gerçekten ayrıştığını, §1.3'teki her yasadışı parçanın faydalı bir hatayla reddedildiğini ve kabul edilen her biçimin bir serileştirme gidiş-dönüşünden sağ çıktığını kanıtlamaktan sorumludur. Çoğu, uzun gerçekçi sorgular yerine küçük odaklı parçalar olarak biçimlendirilmiştir — sözdizimsel özellik başına bir tane — çünkü amaç senaryo gerçekçiliği değil kapsamadır. İkinci bir bölüm olan planlayıcı katmanı, örüntü optimizasyonunu, emilim bayrağı gösterimini ve analizini, optimizasyon geri dönüşünü ve planlayıcı entegrasyonunu (alt sorgular, birleştirmeler, küme işlemleri, sıralama ve gruplama) kapsar.
Serileştirme testleri özel ilgiyi hak eder. RPR nesneleri (görünümler, somutlaştırılmış görünümler, pg_dump çıktısı), bir niceleyicideki gönülsüz bayrak veya bileşik bir gezinme ifadesinin tam biçimi gibi incelikler dahil, anlamsal kayma olmadan katalog gösteriminden gidiş-dönüş yapmalıdır. Çevredeki regresyon altyapısının onları alıp pg_dump ve pg_upgrade'ı bunlara karşı çalıştırabilmesi için, küçük bir serileştirmeye özgü nesne kümesi (rpr_serial_v* görünümleri ve onların destek tabloları) çalışma sonunda bilinçli olarak yerinde bırakılır. Test iskelesinin geri kalanı her zamanki gibi düşürülür. Deparse ve yeniden ayrıştırma boyunca kaybolan bir gönülsüz bayrak gibi kusurlar yalnızca gidiş-dönüş uçtan uca çalıştırıldığında ortaya çıkar.
4.3 rpr_nfa — çalışma zamanı motoru
Bu, §3.5 ve §3.6'da açıklanan her mekanizmayı sınayan pakettir. Testleri tutarlı bir desen izler: her satırda hangi DEFINE değişkenlerinin eşleştiğini bildiren bir değişken adları dizisi taşıyan satır içi VALUES satırları, belirli bir çalışma zamanı davranışını araştıran bir örüntüyle eşleştirilir. Dizi deyimi, çalışma zamanı testini DEFINE değerlendirme mekanizmasından ayırır — test edilen şey "DEFINE ifade değerlendiricisi bu Boole değerlerini doğru hesaplıyor mu?" değil, "bu değişkenler burada eşleştiğine göre, NFA döngüsü beklenen eşleşme aralığını üretiyor mu?" sorusudur. DEFINE değerlendiricisi başka yerde test edilir (ayrıştırma için rpr_base, uçtan uca davranış için rpr).
Tipik bir test düzeneği şöyle görünür — her girdinin o satırda hangi DEFINE değişkenlerinin ateşlendiğini söylediği değişken adı dizilerinden bir sütun ve DEFINE yan tümceleri o adları doğrudan test eden bir örüntü:
SELECT id, flags, first_value(id) OVER w AS ms, last_value(id) OVER w AS me FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A','B']), (3, ARRAY['A','B']), (4, ARRAY['B']), (5, ARRAY['_']), (6, ARRAY['A'])) AS t(id, flags) WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING INITIAL PATTERN (A+ B+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));
Dizi sütununu aşağı doğru okumak, test senaryosunu doğrudan okumaktır. 2. ve 3. satırlar her iki adı da taşır — A ve B her ikisi de orada ateşlenir, dolayısıyla NFA'nın A bacağından B bacağına nereden geçileceği konusunda gerçek bir seçimi vardır. Beklenen eşleşme (1–3 satırlarında A'yı 4. satırda B'nin izlemesi, standardın açgözlü tercih kuralı altında) yalnızca o bayraklarla sabittir, burada sonucu olan hiçbir ifade değerlendirmesi yoktur — = ANY, dizi sütununu DEFINE'a açan basit katmandır, testin sınadığı şey değil. Aynı senaryoyu sayısal bir yüklemle (price > PREV(price) vb.) yazmak NFA testini yüklem değerlendiricisinin davranışıyla iç içe geçirirdi; dizi deyimi ikisini temiz bir şekilde ayrı tutar ve buradaki bir başarısızlık doğrudan NFA döngüsüne işaret eder.
Emilim kapsamı özellikle kapsamlıdır, çünkü emilim, devreye girmemesi gereken yerde devreye girerse sessizce yanlış yanıtlar üretme olasılığı en yüksek olan optimizasyondur. Testler §3.2'nin durum analizinden her biçimi kapsar:
- basit sınırsız değişken (
A+) — kanonik N-1 çökmesi; - sabit uzunluklu gruplar (
(A B)+,(A B{2})+, üç düzey iç içe((A (B C){2}){2})+); - sabit son ekli önde gelen sınırsız değişken (
A+ B) — yalnızca önde gelenA+emilim bayrakları taşır, son ek taşımaz; - bir seçenek içinde dal başına emilim (
B+ C | B+ D); - birden çok sınırsız değişken (
A+ B+) — yalnızca önde geleni emilebilir; - gönülsüz niceleyiciler (
A+?) — emilimden hariç tutulduğu doğrulandı; - önde gelmeyen sınırsız (
A B+) — hariç tutulduğu doğrulandı.
Emilimin ötesinde, paket bağlam yaşam döngüsünü kapsar: AFTER MATCH SKIP TO NEXT ROW altında örtüşen bağlamlar, akış ortasında başarısız bağlam temizliği, eksik bağlamların bölüm sonu kesinleştirilmesi ve baş bağlamda zaten bir aday eşleşme kaydedildikten sonra karşılaşılan bağlamlar. Bunların her biri §3.6'daki belirli bir budama kuralına eşlenir ve testler kural yanlış ateşlerse (ya gereksiz bağlamları canlı bırakarak ya da çıktı üretmesi gereken bir bağlamı öldürerek) yüksek sesle başarısız olacak şekilde yazılmıştır.
4.4 rpr_explain — çıktı kararlılığı
EXPLAIN çıktısı, kullanıcıya yönelik sözleşmenin parçasıdır — üçüncü taraf araçlar (izleme panoları, log toplayıcıları) bunu ayrıştırır ve kozmetik gibi görünen değişiklikler bunları bozabilir. rpr_explain paketi üç şeyi doğrular:
- NFA sayaçları doğru yerde görünür — WindowAgg başına istatistikler (peak/total/merged states, peak/total/pruned contexts, matched/mismatched/absorbed/skipped için uzunluk histogramları)
EXPLAIN ANALYZEaltında metin, JSON ve XML biçimlerinde belgelenmiş etiketlerle görünür; Nav Mark Lookback ve Lookahead ise tam olarak DEFINE içindeki gezinme onları beslediğinde görünür. - Örüntüler doğru deparse edilir — her niceleyici biçimi, gönülsüz varyantlar ve sınırlı biçimler dahil; her seçenek; her grup; her
AFTER MATCH SKIPbiçimi;INITIAL; ofsetli gezinme çağrıları; bileşik gezinme. Deparse edilmiş metin, ayrıştırıcıdan değişmeden gidiş-dönüş yapmalıdır. - Tanımlayıcı tırnaklama doğrudur — örüntü değişkenleri ve DEFINE ifadeleri sıradan SQL tanımlayıcılarıyla aynı tırnaklama kurallarıyla yayılır, dolayısıyla olağandışı değişken adları
pg_dumpçıktısını bozmaz.
rpr_base gibi, bu paket de nesnelerini çalışma sonunda bilinçli olarak yerinde bırakır; böylece pg_dump ve pg_upgrade kapsamı, açıklama tarafındaki yapıtlara da uzanır.
4.5 rpr_integration — planlayıcı etkileşimleri
PostgreSQL'in planlayıcısı pencere sorguları üzerinde çalışan birçok optimizasyona sahiptir — çerçeve kanonikleştirme, run-condition pushdown, özdeş pencere tekilleştirme, kullanılmayan çıktı projeksiyonu, hareketli toplam ters geçişleri — ve bunların her biri RPR akılda tutulmadan tasarlanmıştır. Bir pencerenin PATTERN yan tümcesi olduğunda çoğunun uygulanması güvensizdir: çerçeve eşleşme sözleşmesinin parçasıdır, eşleşmiş çıktı artık herhangi bariz bir biçimde monoton değildir ve aynı belirtime ama farklı DEFINE'lara sahip iki pencere gerçekten farklı sonuçlar üretir. Entegrasyon paketi, bu optimizasyonların her birinin RPR pencerelerine nasıl davrandığını doğrular — çoğu devre dışı bırakılmalı veya atlanmalıdır:
- Çerçeve kanonikleştirme
- Planlayıcı normalde
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING'irow_number,rankventilegibi çerçeveden bağımsız pencere işlevleri içinROWS UNBOUNDED PRECEDING'e yeniden yazar. RPR'nin çerçevesi bir toplama penceresi değil, eşleşme aralığıdır ve aynen kalmalıdır. - Run-condition pushdown
- Bir pencere işlevinin çıktısı üzerindeki monoton bir
WHEREfiltresi normalde pencere operatörüne durdurma koşulu olarak itilebilir. RPR için bu örüntü eşleştirmesini erkenden sonlandırır, muhtemelen genişleme ortasında eşleşmeleri keser. - Pencere tekilleştirme (RPR vs RPR olmayan)
- Aynı
ORDER BYve çerçeveye sahip iki pencere normalde tek olarak birleştirilir. Bir RPR penceresi ve bir RPR olmayan pencere asla durum paylaşamaz, çünkü RPR tarafı eşleşme sonuçları taşır. - Pencere tekilleştirme (farklı DEFINE veya SKIP)
- Aynı
PATTERN'a ama farklıDEFINEyan tümcelerine veya farklı birAFTER MATCH SKIP'e sahip iki RPR penceresi farklı eşleşmeler üretir ve yapısal biçimleri özdeş olsa bile farklı kalmalıdır. - Kullanılmayan çıktı projeksiyonu
- Bu optimizasyonun uygulanmasına izin verilir: çevredeki sorgu pencerenin çıktısını hiç okumadığında, pencere işlevi NULL olur ve WindowAgg'ı düşürülür; satır sayısı değişmez. Testler, WindowAgg kaldığında DEFINE'ın okuduğu sütunların ona hâlâ ulaştığını ve değeri okunduğunda pencerenin korunduğunu denetler.
- Hareketli toplam ters geçişleri
- Bir ters geçiş işlevine sahip pencere toplamları normalde çerçeve hareket ettikçe artımlı olarak değerlendirilebilir. RPR'nin indirgenmiş çerçevesi bir kayan pencere değildir; ters geçiş yolu yanlış sonuçlar üretirdi.
Ek durumlar, maliyet tahmininin DEFINE'ı hesaba kattığını, bir RPR penceresi tutan alt sorgunun düzleştirilmediğini, DEFINE ifadelerinin üstteki bir WindowAgg'a sızmadığını ve LIMIT'in WindowAgg'ın üstünde kaldığını denetler; ikinci bir grup RPR'ı CTE'ler, birleştirmeler, küme işlemleri, hazırlanmış ifadeler, bölümlenmiş tablolar ve benzeri yapılarla birlikte çalıştırır. Korunan durumların çoğu aynı biçimi izler: optimizasyonu tetikleyen bir taban çizgisi (genellikle EXPLAIN'de denetlenen RPR olmayan bir sorgu), ardından optimizasyonun uygulanmadığı, yapısal olarak benzer biçimde bir RPR sorgusu — DEFINE/SKIP tekilleştirme durumunda taban çizgisi iki özdeş RPR penceresidir ve ters geçiş durumu atlamayı EXPLAIN yerine günlük tutan bir toplamla denetler. İki yarısı birlikte planlayıcıdaki korumanın gerçek doğrulama olmadan her sorguyu onaylamak yerine gerçek iş yaptığını kanıtlar.
Bu paket §3.4'ün kısa olmasının da nedenidir. "Eşleşme sınırları" mekanizmaları — indirgenmiş çerçeve, SKIP, INITIAL, sınırlı çerçeve kesimi — operasyonel olarak başka yerde test edilir; rpr_integration'ın doğruladığı şey, başka hiçbir optimize edici aşamanın bunlara giderken müdahale etmediğidir. Geçen bir rpr_integration, paketlerin geri kalanının girdilerinin yürütücüye dokunulmadan ulaştığına güvenmesini sağlayan şeydir.