Row Pattern Recognition Глубокое погружение
Сопровождаемый обзор ISO/IEC 19075-5 · SQL R020 в PostgreSQL — что реализовано, что ещё не описано и как это работает на практике.
Краткий обзор стандарта, разбор примеров, изучение архитектуры и работа с действующим NFA-симулятором на собственных шаблонах.
Обсуждение: тред pgsql-hackers · последний патч (v55) · commitfest #4460.
Предварительный перевод ИИ — возможны ошибки.
§1. Стандарт, подмножество и открытые вопросы
1.1 Область стандарта
Row Pattern Recognition был введён в SQL стандартом ISO/IEC 9075-2:2016 и описан в сопутствующем документе ISO/IEC 19075-5:2021 (Часть 5, «Row Pattern Recognition»).
Стандарт определяет две формы доступа к одному и тому же базовому механизму. Возможность R010 размещает предложение MATCH_RECOGNIZE в списке FROM для построения производной таблицы; возможность R020 встраивает ту же логику шаблонов в спецификацию WINDOW для получения вывода оконной функции. Обе формы имеют значительную общую часть синтаксиса и семантики (19075-5 отмечает несколько отличий, специфичных для R020, в §6.3.3), но представляют собой функционально различные точки входа — база данных может реализовать одну из них или обе.
Серия патчей, обсуждаемая здесь, реализует подмножество только R020; форма с табличным предложением намеренно оставлена вне области.
Поверхность R020 невелика, но выразительна. Запрос привязывает шаблон к окну добавлением предложений внутри спецификации окна, рамка которой — ROWS BETWEEN CURRENT ROW AND …: PATTERN описывает регулярное выражение над именованными переменными шаблона, DEFINE задаёт логический предикат, идентифицирующий каждую переменную, а необязательное AFTER MATCH SKIP (по умолчанию PAST LAST ROW) определяет расположение последующих совпадений внутри секции.
Необязательные MEASURES, SUBSET, INITIAL/SEEK и вспомогательная функция CLASSIFIER() завершают набор. (Стандартная функция MATCH_NUMBER() относится только к поверхности R010 — 19075-5 §6.3.3 (6) явно исключает её из R020.)
Патч покрывает достаточный объём этого словаря, чтобы нетривиальные запросы работали, но не охватывает ряд конструкций, реализация которых зависит от инфраструктуры, ещё не построенной.
Оставшаяся часть раздела разделяет словарь стандарта на то, что патч уже поддерживает, и на то, что намеренно оставлено на будущее. Списки ниже отражают текущее состояние серии патчей.
1.2 Реализованные возможности
Реализованный словарь достаточен для выражения канонических шаблонов V-образной, W-образной формы и разворота, которые изначально мотивируют распознавание шаблонов строк. Он также охватывает все стандартные кванторы — включая все семь нежадных вариантов *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — и четыре примитива навигации, необходимых условиям DEFINE для сравнения соседних строк.
- Предложение PATTERN
- Определяет шаблон строк внутри спецификации окна; до 240 различных переменных шаблона.
- Рамка окна
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGилиROWS BETWEEN CURRENT ROW ANDnFOLLOWINGпри n ≥ 1 (19075-5 §6.10.2); любая другая рамка отвергается, аEXCLUDE NO OTHERS— единственное допустимое исключение.- Regex: + * ? |
- Стандартные кванторы и альтернация.
- Regex: ( ) группировка
- Подшаблоны в круглых скобках.
- Regex: {n} {n,} {,m} {n,m}
- Ограниченные счётчики повторов.
- Нежадные *? +? ?? {n}? {n,}? {,m}? {n,m}?
- Все семь нежадных вариантов, определяемых стандартом (исключены из оптимизации абсорбции).
- Предложение DEFINE
- Логические условия, идентифицирующие каждую переменную шаблона.
- Универсальная переменная строкового шаблона
- Неквалифицированные ссылки на столбцы в
DEFINE(например, голоеPrice) разрешаются в текущую строку, согласно 19075-5 §4.10/§4.16. - PREV, NEXT (со смещением)
- Достижение строки на n позиций до/после текущей (по умолчанию 1); внутренний аргумент вычисляется на достигнутой строке.
- FIRST, LAST (со смещением)
- Достижение строки относительно совпадения;
FIRST(expr, n)указывает на строку через n позиций после начала совпадения,LAST(expr, n)— на строку за n позиций до последней строки совпадения. - Составная навигация (четыре формы)
- Внешний шаг PREV/NEXT поверх внутреннего FIRST/LAST:
PREV(FIRST(expr)),NEXT(FIRST(expr)),PREV(LAST(expr)),NEXT(LAST(expr))— как внутренний, так и внешний шаг принимают собственное смещение. - Имена навигации
PREV,NEXT,FIRSTиLAST, записанные как неквалифицированные вызовы внутриDEFINE, всегда означают навигацию; одноимённая пользовательская функция там должна быть квалифицирована схемой.- Аргументы навигации
- Для
PREV,NEXT,FIRSTиLASTвнутренний аргумент должен содержать хотя бы одну ссылку на столбец, а смещение должно быть константой времени выполнения. - INITIAL
- Совпадения шаблона должны начинаться с текущей строки (по умолчанию).
- AFTER MATCH SKIP PAST LAST ROW
- Режим пропуска по умолчанию; допускает абсорбцию контекста.
- AFTER MATCH SKIP TO NEXT ROW
- Разрешает перекрывающиеся совпадения; отключает абсорбцию.
1.3 Не реализовано
Нереализованные возможности делятся на три условные группы. Первая — и значительно крупнейшая — это семейство конструкций, сосредоточенных вокруг MEASURES: само предложение MEASURES, SUBSET, CLASSIFIER(), ссылки на столбцы с квалификатором шаблона, такие как B.price, и навигация с квалификатором шаблона, такая как LAST(B.price) или PREV(B.price).
Это не отдельные пробелы, а скорее разные представления одной отсутствующей детали: executor должен сохранять историю каждого совпадения — запись для каждой строки совпадения, какой переменной шаблона она была сопоставлена — и ни одна из этих конструкций не имеет осмысленного определения без неё. CLASSIFIER() читает имя переменной из этой записи; B.price читает столбец price из строк, чья запись указывает B; LAST(B.price) проходит то же множество строк и выбирает последнюю; SUBSET U = (A, B) определяет виртуальную переменную, агрегирующую оба набора; а MEASURES вычисляет выражения вроде AVG(U.Price) именно с использованием такой агрегации.
Текущий executor вычисляет предикаты DEFINE строка за строкой, но нигде не записывает получившиеся назначения переменных — запрашивать впоследствии нечего. Построение инфраструктуры истории является предпосылкой для всей группы; отдельные возможности возникают как небольшие проекции, как только записи существуют.
Вторая группа касается альтернативных целей пропуска: AFTER MATCH SKIP TO FIRST var и AFTER MATCH SKIP TO [LAST] var (простое SKIP TO var означает SKIP TO LAST var). Они также зависят от истории совпадений, так как executor должен иметь возможность указать на строку, сопоставленную данной переменной внутри самого недавнего совпадения.
Оставшиеся пункты составляют разнородный хвост: ключевое слово SEEK (альтернатива INITIAL), пустой шаблон (), форма исключения {- … -}, нечувствительный к порядку оператор PERMUTE, а также агрегатные функции и подзапросы в DEFINE, сейчас отвергаемые (агрегату с квалификатором переменной тоже понадобилась бы история совпадений).
- MEASURES
- Именованные выражения вывода для каждого совпадения, например
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; в R020 представлены черезOVERкак оконная функция. Принимает ключевые слова FINAL / RUNNING (19075-5 §5.4), которые в R020 сводятся к одному значению, поскольку measures всегда вычисляются на последней строке совпадения (19075-5 §6.9 (3)). - SUBSET
- Именованные объединения переменных шаблона, например
SUBSET U = (A, B, C). Применимо везде, где может использоваться переменная шаблона —MEASURES, ссылки с квалификатором шаблона вDEFINE,CLASSIFIER(U)— всему этому необходима история совпадений. - CLASSIFIER()
- Возвращает, какой переменной шаблона сопоставлена данная строка. Определена и для DEFINE, и для MEASURES (19075-5 §5.9); ответ для любой строки — имя переменной, записанное в истории совпадений для этой строки.
- Ссылка на столбец с квалификатором шаблона
- Простое
B.priceвDEFINEилиMEASURES— значение столбца из строки, сопоставленной как именованная переменная. - Навигация с квалификатором шаблона
- Ограничивает навигацию строками, сопоставленными как именованная переменная, например
LAST(B.price),FIRST(B.price),PREV(B.price),NEXT(B.price). - SEEK
- Совпадение может начинаться на любой строке от текущей до конца полной рамки окна (в отличие от INITIAL).
- AFTER MATCH SKIP TO FIRST var
- Переход к первой строке, сопоставленной как именованная переменная.
- AFTER MATCH SKIP TO [LAST] var
- Переход к последней строке, сопоставленной как именованная переменная.
- Regex: {- -}
- Исключение — удаляет совпавшие строки из вывода
ALL ROWS PER MATCH. Этот параметр неприменим к окнам (19075-5 §6.3.3 (4)), поэтому в окне синтаксис допускается (§6.13), но нет вывода, на который он мог бы подействовать. - Regex: ()
- Пустой шаблон — соответствует пустой последовательности.
- PERMUTE(...)
- Сопоставление, нечувствительное к порядку, по перечисленным переменным. Ключевое слово распознаётся и отвергается ("PERMUTE is not supported");
permuteостаётся допустимым именем переменной шаблона. - Агрегатные функции в DEFINE
- Агрегаты, такие как
SUM,AVG,COUNT, не допускаются в предикатахDEFINE. Стандарт допускает их как накапливающиеся агрегаты по частичному совпадению; агрегат с квалификатором переменной, такой какAVG(B.Price), зависит от той же истории совпадений, которая нужнаMEASURES/CLASSIFIER(), тогда как неквалифицированный охватывает все строки совпадения на данный момент. - Подзапросы в DEFINE
- Любой подзапрос в
DEFINEотвергается. Стандарт допускает подзапрос, который не выполняет распознавание шаблонов строк и не ссылается ни на одну переменную шаблона строк; патч пока отвергает больше, чем требуется.
Здесь стоит отметить ещё четыре пункта, поскольку их легко принять за упущения.
Первый: якоря шаблона ^ и $ не разрешены с RPR в предложении WINDOW самим стандартом (19075-5 §6.13: «якоря (^ и $) не разрешены при сопоставлении шаблонов строк в окнах»; с базовым определением в 19075-5 §4.14.1); их отсутствие — соответствие стандарту, а не пробел.
Второй: MATCH_NUMBER() также исключён из R020 стандартом (19075-5 §6.3.3 (6) и 19075-5 §6.9 (1)) — она относится только к поверхности R010, и её отсутствие здесь снова является соответствием стандарту, а не недостающей возможностью.
Третий — набор структурных запретов, которые стандарт налагает на R020 (19075-5 §6.17): распознавание шаблонов строк не может быть вложено в другое распознавание шаблонов строк; MEASURES и DEFINE не могут содержать внешних ссылок; подзапросы внутри MEASURES или DEFINE не могут ссылаться на переменные шаблона строк (патч идёт дальше и отвергает все подзапросы в DEFINE, как указано выше); RPR не может использоваться внутри рекурсивного запроса. Патч обеспечивает правило о внешних ссылках ("cannot use outer query column in DEFINE clause") и правило о рекурсии, последнее — для каждого элемента предложения WITH RECURSIVE. Он также отвергает изменчивые (volatile) функции и ссылки на всю строку в DEFINE.
Четвёртый: сам MATCH_RECOGNIZE — возможность R010, табличная форма того же механизма — вне области данного патча. Появится ли в PostgreSQL в конечном итоге R010 — вопрос для будущей серии, а не критерий оценки текущей.
§2. Примеры — как это работает на практике
Примеры в этом разделе выстраиваются последовательно. Сначала рассматривается концептуальная причина того, чем сопоставление шаблонов строк действительно отличается от сопоставления текстовых шаблонов, затем представляются четыре функции навигации, делающие условия DEFINE содержательными, и наконец разбираются пять примеров: одно совпадение (движение NFA), альтернация, абсорбция контекста в простом случае и два случая, когда абсорбция отключена.
Внутренний механизм, делающий навигацию дешёвой — обмен кортежами в одной ячейке — относится к дизайну executor и рассматривается в следующем разделе, а не здесь.
2.1 Почему шаблоны строк отличаются от текстовых шаблонов
Регулярное выражение для текста сопоставляет поток символов, и в каждой позиции имеется ровно один символ для рассмотрения. Вопрос времени выполнения — «равен ли текущий символ 'A'?» — имеет единственный ответ да/нет. Автоматы с возвратом используют это: в худшем случае одна ветвь выживает на символ, а стоимость неоднозначности оплачивается перечитыванием входа.
Шаблон строк отличается принципиально. Строка — не один символ; это кортеж столбцов, проверяемых относительно множества логических предикатов — условий DEFINE. Два предиката могут быть истинными для одной строки одновременно, и стандарт не утверждает, что они должны быть взаимоисключающими. Например:
DEFINE A AS price > 100, B AS volume > 1000, C AS price > 200
Строка с price = 150, volume = 2000 удовлетворяет одновременно A и B, но не C. Сопоставитель шаблонов не может свернуть это в одно состояние — две переменные шаблона активны, и любой элемент шаблона, упоминающий любую из них, может продвинуться. Поэтому NFA должен нести несколько одновременных состояний на строку секции, а не одно.
Это единственное наблюдение определяет остальную архитектуру. Состояние выполнения — это список контекстов, каждый контекст — список состояний, и на каждой строке runtime спрашивает каждое состояние: «учитывая переменные, истинные здесь, куда я могу перейти?» Возникающие развилки и являются причиной, по которой runtime нуждается в нескольких уровнях отсечения — дедупликации состояний внутри контекста, абсорбции между контекстами и других правилах, обозреваемых в §3.6, — без которых число активных состояний и контекстов растёт вместе с секцией, и сопоставление шаблонов становится сверхлинейным.
2.2 Функции навигации
Условия DEFINE, ссылающиеся только на текущую строку, ограничены; почти любому интересному шаблону нужно сравнивать текущую строку с соседними или со строками, уже принятыми ранее в совпадении. Стандарт предоставляет для этого четыре функции навигации, и патч реализует все.
- PREV(expr [, n])
- Строка на n позиций до текущей (по умолчанию n = 1). Используется для сравнений «сегодня vs вчера».
- NEXT(expr [, n])
- Строка на n позиций после текущей (по умолчанию n = 1). Просмотр вперёд; редок в оконной форме, поскольку окно монотонно.
- FIRST(expr [, n])
- Строка на n позиций после первой строки текущего совпадения (по умолчанию n = 0, сама первая строка). «Сравнение со строкой, начавшей это совпадение».
- LAST(expr [, n])
- Строка на n позиций до последней совпавшей строки (по умолчанию n = 0). Внутри
DEFINEпоследняя совпавшая строка — текущая, поэтомуLAST(price)читает текущую строку.
Четыре примитива комбинируются: PREV и NEXT могут оборачивать вызов FIRST или LAST, давая четыре составные формы, семантика которых: «перейти к строке относительно совпадения, затем сделать фиксированный шаг от неё». Именно это позволяет выражению DEFINE читать, например, строку, непосредственно предшествующую началу совпадения.
- PREV(FIRST(expr [, n]) [, m])
- Шаг на m позиций назад от строки, которую читает
FIRST(expr, n)(по умолчанию n = 0, m = 1). «Каким было значение непосредственно перед началом этого совпадения?» - NEXT(FIRST(expr [, n]) [, m])
- Шаг на m позиций вперёд от строки, которую читает
FIRST(expr, n). Заглядывает дальше в совпадение, не завися от текущей строки. - PREV(LAST(expr [, n]) [, m])
- Шаг на m позиций назад от строки, которую читает
LAST(expr, n). «Сравнение со строкой незадолго до последней совпавшей строки». - NEXT(LAST(expr [, n]) [, m])
- Шаг на m позиций вперёд от строки, которую читает
LAST(expr, n).
Здесь стоит отметить два практических момента. Во-первых, навигация может комбинироваться: PREV(FIRST(price)) читает строку непосредственно перед началом совпадения, и патч это поддерживает. Во-вторых, навигация имеет последствия для оптимизаций executor. Простые PREV и NEXT относительны текущей строке и всегда безопасны; FIRST и варианты LAST со смещением, сами по себе или внутри составного PREV/NEXT, относительны границам совпадения, что взаимодействует с абсорбцией контекста: тогда планировщик отключает абсорбцию для всего шаблона. Механизм этого взаимодействия — тема §2.6.
2.3 Разбираемый пример 1 — движение NFA
SKIP PAST LAST ROW, как только его совпадение записано.SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (START UP+ DOWN+) DEFINE UP AS price > PREV(price), DOWN AS price < PREV(price) );
Шаблон разворачивается в четыре элемента:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
Для ряда цен 100, 110, 120, 115, 108, 130:
| Строка | Цена | Истинные перем. | Действие |
|---|---|---|---|
| 0 | 100 | START | Новый контекст. START совпадает и немедленно выходит (max=1); состояние продвигается к UP+. |
| 1 | 110 | START, UP | UP совпадает. Продвижение разветвляется: одно состояние зацикливается на UP, другое выходит к DOWN+. |
| 2 | 120 | START, UP | UP совпадает в зацикленном состоянии и разветвляется снова. Состояние DOWN из строки 1 погибает (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP не выполняется в зацикленном состоянии и погибает. Состояние DOWN из строки 2 совпадает. Продвижение разветвляется: цикл на DOWN и выход к #FIN — записывается кандидат совпадения по строкам 0–3. |
| 4 | 108 | START, DOWN | DOWN совпадает в зацикленном состоянии и разветвляется снова; новый кандидат FIN по строкам 0–4 заменяет более короткий. |
| 5 | 130 | START, UP | Зацикленное состояние DOWN не выполняется (130 ≮ 108). Поскольку в этом контексте не осталось живых состояний, записанный кандидат (строки 0–4) финализируется как совпадение. Следующая попытка начинается на строке 5; START совпадает, но секция заканчивается до какого-либо UP. |
Ключевой момент: на строке 3 строка удовлетворяет одновременно START (всегда истинно) и DOWN, но START важен только для контекста, начинающегося на строке 3; в этом контексте зацикленное состояние UP погибает, и продвигается только состояние, ожидающее на DOWN+. Многосостоянная природа §2.1 проявляется как разветвление при каждом совпадении UP (состояние может остаться на UP+ или продвинуться к DOWN+). Жадное предпочтение — «зациклиться снова перед выходом», поэтому при достаточных данных зацикленные ветви продлили бы совпадение дальше; здесь зацикленное DOWN погибает на строке 5 (130 ≮ 108), а последний кандидат FIN (строки 0–4) — порождённый при выходе DOWN на строке 4 и заменивший кандидата строки 3 — финализируется как совпадение.
Результат запроса напрямую следует из этой трассировки. По семантике RPR оконные функции first_value(price) и last_value(price) вычисляются только на строке, начавшей совпадение — все прочие строки совпадения дают NULL для этих оконных функций, так как их сжатая рамка пуста. Поэтому вывод для наших данных выглядит как таблица, показанная на постере в верхней правой панели:
| Строка | Цена | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
Строка 0 является началом совпадения, поэтому её рамка охватывает строки 0–4, и оконные функции возвращают начальную цену V-образного шаблона ($100) и нижнюю ($108). Строки 1–4 находятся внутри совпадения, но не являются его началом, поэтому получают NULL. Строка 5 (цена $130) находится вне любого совпадения и аналогично получает NULL.
2.4 Разбираемый пример 2 — Альтернация и лексикографический порядок
Форма (A | B) даёт сопоставителю выбор: на любой строке две альтернативы проверяются независимо, и сколько угодно из них может совпасть. Здесь многосостоянная природа §2.1 становится видимой внутри одного контекста — не между контекстами (это абсорбция), а вдоль параллельных ветвей, которые executor исследует в порядке шаблона, начиная с более ранней ветви.
PATTERN ((UP | HIGH) DONE) DEFINE UP AS price > PREV(price), HIGH AS price > 100, DONE AS volume > 1000
Представим строку, где цена и выросла, и превысила $100 — одновременно истинны UP и HIGH. Каждая альтернатива порождает собственное состояние: одно идёт по ветви UP, другое — по ветви HIGH. Затем оба продвигаются к DONE, где они встречаются.
| Строка | Истинные перем. | Живые состояния |
|---|---|---|
| R | UP, HIGH | Состояние A (ветвь UP) и Состояние B (ветвь HIGH) оба продвигаются к DONE с одинаковыми счётчиками; B — дубликат A и отбрасывается |
| R+1 | DONE | Состояние A совпадает с DONE и достигает #FIN |
В терминах стандарта обе ветви дают совпадение одинаковой длины по одним и тем же строкам, что даёт два кандидатных пути — один помеченный UP, DONE, другой — HIGH, DONE. Стандарт разрешает это по лексикографическому порядку: среди альтернатив, записанных в (UP | HIGH), побеждает та, что записана первой, независимо от длины совпадения. Поскольку UP идёт раньше HIGH, выживший путь — UP, DONE. Executor обеспечивает это на строке R, а не на FIN: он добавляет состояние ветви UP первым, поэтому nfa_append_state_unique() сохраняет его и отбрасывает идентичное состояние ветви HIGH.
Лексикографический порядок и делает CLASSIFIER() однозначно определённым, когда он будет реализован — он позволяет runtime сообщить пользователю «эта строка совпала как UP, а не HIGH» даже когда оба предиката были истинны. Лексикографический порядок — основное правило для альтернации: лексикографически более ранняя ветвь побеждает более позднюю, даже если более поздняя дала бы более длинное совпадение, а более поздняя (возможно, более короткая) ветвь всё же может победить, если каждая более ранняя погибнет, не достигнув FIN. Жадная длина решается внутри одного квантора — при двух завершениях одной ветви альтернации жадный квантор предпочитает большее число итераций.
2.5 Разбираемый пример 3 — Абсорбция контекста (одна судьба)
Простейший шаблон, демонстрирующий абсорбцию, — PATTERN (A+) с DEFINE A AS TRUE. Каждая строка совпадает с A, и стандарт требует, чтобы сопоставитель рассматривал каждую строку как возможное начало совпадения. Наивно это означает N контекстов для секции из N строк. Рассмотрим секцию из пяти строк (любые данные — предикат всегда истинен):
| Строка | Наивные контексты | С абсорбцией |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 поглощён |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | пять контекстов | C1[A:5] |
Число живых контекстов падает с O(n) до O(1), поэтому суммарная работа по секции снижается с O(n²) до O(n). Правило абсорбции, обосновывающее отбрасывание, прямолинейно, когда квантор неограничен:
Левая нижняя панель постера («① Context Absorption») — именно это правило, визуализированное на пяти строках.
В правиле скрывается тонкий, но важный момент: отбрасывание безопасно, потому что предикат A AS TRUE вычисляется в одно и то же значение на каждой строке независимо от того, какой контекст спрашивает. То же верно для любого предиката, ссылающегося только на текущую строку или фиксированное смещение от неё — включая PREV. Следующий пример переходит к конкретной неделе цен, используя предикат на основе PREV, а §2.6 повторно использует именно эту неделю, чтобы сделать симметрию между безопасной и небезопасной абсорбцией очевидной:
PATTERN (RISE+) DEFINE RISE AS price > PREV(price)
Возьмём торговую неделю $100, $108, $112, $116, $110 с понедельника по пятницу — четыре подъёма и затем резкий спад. Предположим, C1 начинается во вторник (первый день, когда RISE совпадает: $108 > $100), а executor также спекулятивно отслеживает C2, начатый в среду. Условие RISE на каждой строке сравнивает цену строки с её непосредственным предшественником — факт уровня секции, а не контекста — поэтому оба контекста вынуждены вычислять одно и то же логическое значение на каждой общей строке:
| День | Цена | C1 — старт во вт price > PREV(price) | C2 — старт в ср price > PREV(price) |
|---|---|---|---|
| Пн | $100 | — | — |
| Вт | $108 | $108 > $100 ✓ (только начат) | — |
| Ср | $112 | $112 > $108 ✓ | $112 > $108 ✓ (только начат) |
| Чт | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| Пт | $110 | $110 > $116 ✗ — финализация | $110 > $116 ✗ — финализация |
История рушится в тот момент, когда предикат начинает зависеть от собственных границ каждого контекста — и об этом §2.6.
2.6 Разбираемый пример 4 — Когда абсорбция становится небезопасной
DEFINE ссылается на FIRST — правило абсорбции перестаёт действовать, и планировщик отключает абсорбцию для шаблона.
Предположим, аналитик хочет найти последовательные торговые дни, когда акция оставалась в пределах десяти долларов от дня, с которого начался прогон — своего рода окно консолидации. Шаблон и DEFINE выглядят так:
PATTERN (STABLE+) DEFINE STABLE AS price < FIRST(price) + 10
Условие теперь сравнивает цену текущей строки с ценой в начале текущего прогона. Два прогона, начавшихся в разные дни, имеют разные значения FIRST(price), поэтому два состояния на одном и том же элементе шаблона с одинаковым счётчиком больше не взаимозаменяемы: их будущее зависит от границы, которую абсорбция собиралась отбросить.
Возьмём ту же торговую неделю, что и в §2.5 — $100, $108, $112, $116, $110 с понедельника по пятницу. Runtime снова удерживает два кандидатных прогона одновременно: C1 начат в понедельник, C2 — во вторник (каждая строка является потенциальным началом прогона при STABLE+).
| День | Цена | C1 — старт в пн FIRST = $100 price < $100 + 10 | C2 — старт во вт FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| Пн | $100 | $100 < $110 ✓ | — |
| Вт | $108 | $108 < $110 ✓ | $108 < $118 ✓ (только начат) |
| Ср | $112 | $112 < $110 ✗ — финализация Пн–Вт | $112 < $118 ✓ |
| Чт | $116 | — | $116 < $118 ✓ |
| Пт | $110 | — | $110 < $118 ✓ (продолжается) |
При абсорбции C2 был бы слит с C1 во вторник — слитый контекст хранит только потолок C1 ($110), поэтому различающее представление C2 (потолок $118, четырёхдневный прогон до пятницы) не покрывается будущим C1. На этой конкретной неделе вывод случайно не меняется: C1 записывает Пн–Вт, C2 начался внутри этого совпадения и отбрасывается SKIP PAST LAST ROW, а следующая попытка начинается в среду с собственным потолком ($122) и совпадает по Ср–Пт. В общем же случае результат DEFINE более раннего контекста больше не включает в себя результат более позднего, поэтому сравнение счётчиков, на котором основана абсорбция, становится неверным. Когда предикат DEFINE несёт зависимость от начала совпадения, планировщик поэтому превентивно отключает абсорбцию.
(Когда совпадение ведущего контекста всё же успешно, контексты, начавшиеся внутри его принятого диапазона — при стандартном AFTER MATCH SKIP PAST LAST ROW, — просто отбрасываются; они удерживаются только для того, чтобы runtime имел возможность отката при отказе ведущего совпадения.)
Таблица ниже расширяет правую нижнюю панель постера («② Navigation») составными формами и обобщает, какие формы навигации создают зависимость от начала совпадения:
| Навигация | Завис. от старта | Абсорбируется? |
|---|---|---|
| PREV, NEXT | нет | да |
| LAST (без смещения) | нет | да |
| LAST со смещением | проверка границы | нет |
| FIRST (любой) | прямая | нет |
| Составная (внутренний FIRST) | прямая | нет |
| Составная (внутренний LAST, без смещения) | нет | да |
| Составная (внутренний LAST со смещением) | проверка границы | нет |
Два примера из §2.5 и §2.6 сводятся к одному правилу. Одна судьба делает абсорбцию безопасной: если каждый контекст на одном и том же элементе шаблона вычислит одинаковый ответ на любой будущий предикат, нужно сохранить только старейший. Разные судьбы делают абсорбцию небезопасной: как только предикаты ветвятся на приватном состоянии контекста — что именно делают FIRST и LAST со смещением — каждый живой контекст представляет будущее, покрытие которого никаким другим контекстом не гарантировано, поэтому безопасность отбрасывания любого из них уже нельзя доказать.
Планировщик распознаёт это различие во время компиляции и включает или выключает абсорбцию для всего шаблона; когда она выключена, runtime платит многоконтекстную стоимость. Бенчмарк постера в панели ③ не использует FIRST, поэтому абсорбция остаётся включённой — именно поэтому PostgreSQL остаётся линейным как при успехе, так и при отказе.
Числа бенчмарка на постере — тот же алгоритм в масштабе. На шаблоне успеха (A+ B+ C+ D) и PostgreSQL, и Trino масштабируются примерно O(n) после подтверждения совпадения, и PostgreSQL опережает примерно в 16× до 33× (показатели Trino уже исключают запуск JVM).
На шаблоне отказа (A+ B+ C+ E) Trino, у которого, по-видимому, нет абсорбции, преследует каждое потенциальное начало совпадения и деградирует даже быстрее, чем O(n²) (примерно в 56× больше времени при 5× строк); при 100 000 строк это занимает более пяти часов, тогда как PostgreSQL завершает за 92 мс, ускорение около 217 000×.
Этот разрыв — не инженерная полировка, а именно то самое различие «одна судьба / разные судьбы» из §2.5 и §2.6, применённое к каждой строке каждого потенциального начала совпадения в секции.
2.7 Разбираемый пример 5 — Когда SKIP отключает абсорбцию
Предыдущий пример нарушал абсорбцию со стороны данных: FIRST в DEFINE заставлял каждый контекст вычислять предикаты по-разному. Абсорбция также может нарушаться со стороны вывода, и предложение AFTER MATCH SKIP управляет этим.
Рассмотрим шаблон PATTERN (A+) с DEFINE A AS TRUE по пяти строкам, все из которых совпадают с A. При стандартном AFTER MATCH SKIP PAST LAST ROW сопоставитель находит самое длинное совпадение, начинающееся с самой ранней строки, и затем перескакивает за него; любой контекст, начавшийся внутри этого совпадения, неявно отбрасывается как избыточный — именно та ситуация, для которой предназначена абсорбция. Вывод — одно совпадение, строки 0–4, и runtime нужен только один живой контекст.
Переключите режим пропуска на AFTER MATCH SKIP TO NEXT ROW — и контракт меняется:
PATTERN (A+) DEFINE A AS TRUE AFTER MATCH SKIP TO NEXT ROW
Теперь каждая потенциальная стартовая позиция должна сообщаться отдельно, даже при перекрытии совпадений. Для тех же пяти строк runtime обязан выдать пять совпадений: строки 0–4, 1–4, 2–4, 3–4 и 4–4. Ни одно из них нельзя заменить «более длинным, начинающимся раньше», потому что стандарт утверждает, что пользователь хочет получить их все.
| Строка | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | совпадение начинается; строки 0–4 будут единственным совпадением | совпадение начинается на строке 0 |
| 1 | (внутри совпадения 0) | совпадение начинается на строке 1 — должно оставаться живым |
| 2 | (внутри совпадения 0) | совпадение начинается на строке 2 — должно оставаться живым |
| 3 | (внутри совпадения 0) | совпадение начинается на строке 3 — должно оставаться живым |
| 4 | совпадение 0 финализируется (строки 0–4) | финализируются пять совпадений: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW каждый поздно стартующий контекст — отдельная строка вывода. Два контекста на одном элементе шаблона больше не избыточны — они оба являются требуемыми выводами, и отбрасывание одного незаметно потеряло бы совпадение, запрошенное пользователем.
Заметим, что предикат не изменился. A AS TRUE вычисляется одинаково на каждой строке независимо от того, какой контекст спрашивает, поэтому условие одной судьбы из §2.5 по-прежнему выполняется. Меняется требование к выводу: даже контексты с идентичным будущим должны сосуществовать, потому что соответствуют разным строкам результата. Поэтому планировщик отключает абсорбцию контекстов всегда, когда действует AFTER MATCH SKIP TO NEXT ROW, независимо от предложения DEFINE.
Сопоставление §2.6 и §2.7 даёт два способа, которыми семантика запроса исключает абсорбцию:
FIRST или LAST со смещением в DEFINE.AFTER MATCH SKIP TO NEXT ROW.
Любого из этих условий достаточно, чтобы отключить абсорбцию для всего шаблона; то же делает и рамка, которая не заканчивается на UNBOUNDED FOLLOWING. Когда не действует ни одно — стандартный AFTER MATCH SKIP PAST LAST ROW, неограниченный конец рамки и условия DEFINE, использующие только PREV, NEXT или простой LAST, — абсорбция включена, но только для состояний в абсорбируемой области шаблона: ведущая жадная неограниченная переменная, такая как A+ или A*, группа фиксированной длины с неограниченным жадным квантором, такая как (A B)+, жадная группа, тело которой начинается с одного из них, такая как (A+ B)+ или (A+ B){2}, или ветви альтернации, построенные из них; нежадная группа дисквалифицирует всё своё поддерево. Где это выполняется, как для A+ в §2.5, runtime сворачивается до одного контекста и остаётся линейным; START UP+ DOWN+ из §2.3 не получает абсорбируемой области вовсе.
§3. Дизайн — от Parser к Executor
Row Pattern Recognition реализован как три стадии, передающие работу через чётко определённые промежуточные формы. Parser превращает текст SQL в дерево шаблона и список предикатов DEFINE; planner компилирует дерево в плоский массив элементов шаблона и решает, какие из них могут участвовать в абсорбции контекста; executor прогоняет массив по секции построчно в трёхфазном цикле. Каждая стадия имеет собственную форму данных, и большая часть инженерной находчивости — на границах: плоский NFA, помещающийся в кэш, модель навигации, переиспользующая одну ячейку кортежа вместо материализации по одной на ссылку, и правило абсорбции, превращающее O(n²) работы в O(n).
SQL text
│
│ parser stage
▼ validate frame
build pattern tree
type-check DEFINE
pattern tree + DEFINE list
│
│ planner stage
▼ optimize the tree
compile to flat NFA array
decide absorbability
flat NFA + absorption flags
│
│ executor stage
▼ per-row engine:
Match → Absorb → Advance
match result:
start row, length, success/fail
Разделы ниже проходят по этому конвейеру. §3.1 описывает parser и форму дерева шаблона; §3.2 — компиляцию, превращающую дерево в плоский NFA; §3.3 — модель навигации, которой пользуются предикаты DEFINE для обращения к соседним строкам; §3.4 — обработку границ совпадения — правила SKIP, INITIAL и ограниченной рамки, фиксирующие, где совпадение начинается и заканчивается; §3.5 — трёхфазный построчный движок; §3.6 собирает все механизмы отсечения, удерживающие пространство состояний ограниченным; а §3.7 обозревает, что реализация выводит в EXPLAIN.
3.1 Parser — построение дерева шаблона
Parser распознаёт распознавание шаблонов по наличию предложения PATTERN внутри спецификации окна. Его первая задача — валидация рамки, поскольку RPR налагает ограничения, которых нет у обычных оконных запросов: режим рамки должен быть ROWS (а не RANGE или GROUPS), начальная граница должна быть CURRENT ROW, конечная граница должна быть UNBOUNDED FOLLOWING или положительным смещением FOLLOWING (поэтому рамка по умолчанию тоже отвергается), а опции EXCLUDE, кроме EXCLUDE NO OTHERS, запрещены. Это проверки соответствия, а не оптимизации — понятие рамки в RPR — это диапазон совпадения, и стандарт не предполагает заполнения его чем-либо, кроме совпавших строк.
Когда рамка прошла валидацию, parser превращает предложение PATTERN в дерево, построенное из четырёх видов узлов — ссылки на переменную, последовательности (конкатенации), альтернации и группы (подшаблона в скобках). Каждый узел несёт квантор в виде трёх чисел — нижней границы, верхней границы (возможно, бесконечной) и флага нежадного сопоставления:
| Исходный код | Кодировка дерева |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
Каждый предикат DEFINE затем проверяется по типам по столбцам секции и приводится к логическому выражению. Из этого следуют две практически важные вещи. Во-первых, анализ разбора ничего не добавляет в целевой список запроса ради DEFINE; вместо этого planner помечает каждый столбец, на который ссылается предикат DEFINE, как необходимый, как он делает это для HAVING, и протаскивает эти столбцы до стадии executor, даже если окружающий запрос их не выбирает — без этого runtime не имел бы основы для вычислений. Во-вторых, переменные, появляющиеся в PATTERN, но никогда в DEFINE, неявно истинны: они совпадают с каждой строкой.
3.2 Компиляция — от AST к плоскому NFA
Planner превращает дерево parser в структуру данных, которую будет выполнять executor: плоский массив элементов шаблона, адресуемый по индексу. Компиляция идёт по шестишаговому конвейеру:
compile(astTree):
1. оптимизировать AST
2. измерить размер и глубину
3. выделить массив элементов
4. заполнить из AST
(назначить указатели next/jump)
5. финализировать — установить sentinel FIN
6. отметить элементы, пригодные для поглощения
Плоская форма выбрана по простой причине: executor должен обходить шаблон много раз на секцию, а сплошной массив с индексным доступом — самая дешёвая структура данных для обхода. Интересны шаги 1 и 6 — шаг 1 потому, что определяет размер массива, а шаг 6 потому, что решает, включится ли вообще оптимизация абсорбции из §2.5.
Оптимизация AST
Оптимизация окупается дважды: один раз — в статическом числе элементов плоского массива и второй — на каждой обрабатываемой во время выполнения строке. Каждое преобразование уменьшает пространство состояний, которое runtime должен перечислять. Оптимизатор применяет девять правил перезаписи за один восходящий проход (внутри последовательности слияние групп выполняется ещё раз, поскольку более ранние слияния могут свести вместе две одинаковые группы):
- Сплющивание SEQ
SEQ(A, SEQ(B, C))→SEQ(A, B, C)- Слияние соседних переменных
-
A A→A{2}
A{2,3} A{1,2}→A{3,5} - Слияние соседних групп
(A B)+ (A B)+→(A B){2,∞}- Слияние соседних ALT
(A | B) (A | B) (A | B)→(A | B){3}- Слияние префикса/суффикса
A B (A B)+→(A B){2,∞}- Сплющивание и дедуп ALT
-
(A | (B | C))→(A | B | C)
(A | B | A)→(A | B) - Перемножение кванторов
-
(A+)+→A+
(A{2,3}){5}→A{10,15} - Развёртывание единственного потомка
-
SEQ(A)→A
(A){1,1}→A - Нормализация нежадности
A{2}?→A{2}(нежадность снимается везде, где min = max)
Перемножение кванторов сворачивает только тогда, когда достижимые счётчики образуют один непрерывный интервал, а предпочтительное совпадение не смещается: точный внешний квантор ((A{2,3}){5} → A{10,15}), потомок с min 0 или интервалы потомка, которые соприкасаются, при min потомка не более 1 или неограниченном max потомка ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), причём внешний квантор с min 0 также требует min потомка не более 1 ((A{2,})* остаётся, поскольку A* принял бы одну строку). Потомок-группа, собственный квантор которой не точный, должна сначала иметь тело фиксированной длины, поэтому ((A | B B){1,2}){2} остаётся нетронутым даже при точном внешнем кванторе. Иные комбинации могут внести пробелы, которые плоская форма не отразит — например, (A{2}){2,3} принимает только {4, 6}, а наивный A{4,6} принял бы и 5, — или сместить предпочтительное совпадение ((A{2,3}){1,2} предпочитает три строки, тогда как A{2,6} берёт четыре), поэтому оптимизатор оставляет их нетронутыми. Это не единственная перезапись с условием: слияние групп и слияние суффикса требуют тела, потребляющего фиксированное число строк, слияние префикса отказывается от группы с min 0, конечным max и обнуляемым содержимым, нежадные узлы не сливаются и не перемножаются ((A+?)+ остаётся), а перезапись, новая граница которой переполнилась бы, отклоняется.
Форма элемента
Каждый элемент плоского массива представляет одну позицию в шаблоне. Существует шесть логических видов: ссылка на переменную (единственный вид, потребляющий строку); маркеры начала группы и конца группы, открывающие и закрывающие подшаблон в скобках; маркер альтернации, возглавляющий список ветвей; разделитель ветвей, завершающий каждую ветвь; и маркер завершения в конце шаблона.
Каждый элемент также несёт глубину (уровень вложенности групп), квантор (минимальное и максимальное число повторений, возможно бесконечное) и два указателя перехода — next, «куда идти после потребления этого элемента», и jump, «куда перепрыгнуть» (используется маркером альтернации и разделителями ветвей для соединения ветвей, началом группы — чтобы назвать собственный конец группы (группа, квантор которой допускает ноль, пропускается через next этого конца), — и концом группы для возврата к телу).
Для PATTERN ((A B)+) скомпилированный массив выглядит так:
PATTERN ((A B)+) compiles to:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(открывает группу; jump указывает
на её собственный END)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(закрывает группу; jump зацикливается)
[4] FIN шаблон завершён
Шаблон читается слева направо через next, а jump обрабатывает нелинейные рёбра. На индексе 3 jump у END указывает обратно на индекс 1 — так зацикливается неограниченный внешний квантор; на индексе 0 jump у BEGIN указывает на его END на индексе 3, и если бы группа была необязательной, пропуск вышел бы через next этого END к индексу 4, не заходя в сам END. Runtime не строит граф во время выполнения — он просто следует этим двум указателям, обходя массив.
Атрибуты элементов
Помимо формы, каждый элемент несёт пять логических атрибутов, направляющих поведение runtime в этой позиции:
- Reluctant
- Меняет порядок раскрытия квантора. Жадные кванторы пробуют «зациклиться снова» прежде «выйти»; нежадные сначала пробуют «выйти». Несётся переменной для
A+?; несётся BEGIN и END группы для((…)+?). - Empty-loopable
- Устанавливается на концах групп, тело которых обнуляемо (
(A? B?)+,(A | B*)+;(A?)*сначала перемножается вA*и не оставляет конца группы). Указывает runtime добавить быстрый выход рядом с обычным возвратом ниже min, чтобы защита от циклов не убивала легитимные совпадения в группах, способных давать пустые итерации. - Empty-preferred
- Устанавливается на концах групп, тело которых предпочитает пустое совпадение, как в
(A?? B??){2}. Ставит быстрый выход впереди возврата ниже min, где собственная жадность группы ничего не определяет. - In-absorbable-region
- Помечает каждый элемент, лежащий внутри области, пригодной к абсорбции — используется runtime для отслеживания, находится ли текущее состояние ещё в безопасной зоне.
- Absorption-comparison-point
- Помечает конкретный элемент, где должны выполняться сравнения абсорбции. Для простого
A+он попадает на переменную; для неограниченной группы вроде(A B)+— только на конец группы.
Разделение между «в области» и «точкой сравнения» важно, поскольку абсорбция имеет смысл только в точках закрытия итераций. Внутри тела (A B)+ runtime находится в середине итерации, и счётчик ещё не достиг финального значения для этого раунда; сравнение здесь означало бы сравнение несравнимых величин. Состояние должно достичь конца группы, прежде чем runtime сможет решить. Поэтому первый атрибут говорит «вы всё ещё в области абсорбции»; второй — «вы достигли точки сравнения — проверяйте сейчас».
Анализ абсорбируемости
Шаг 6 компиляции даёт правилу «одной судьбы» из §2.5 свидетельство времени компиляции. Решение многоуровневое:
isAbsorbable(query):
если режим SKIP != SKIP PAST LAST ROW
→ return false
если конец frame != UNBOUNDED FOLLOWING
→ return false
если хоть один DEFINE зависит от match_start
→ return false
пройти плоский массив от
элемента 0 и пометить элементы,
удовлетворяющие структурному случаю
Первые три проверки уровня запроса: они в точности соответствуют условиям §2.7 (сторона вывода: режим SKIP), ограниченной рамке (граница нарушает монотонность) и §2.6 (сторона данных: FIRST или LAST со смещением в DEFINE). При сбое любой из них анализ не ставит ни одного флага, и абсорбция отключается на уровне всего запроса. Когда все они проходят, обход допускает четыре структурные формы:
- Случай 1 — Простая неограниченная переменная
-
Каждая итерация — ровно одна строка. Счётчик более раннего контекста всегда ≥ счётчика более позднего на каждой общей позиции.
A+,A*,A{2,∞} - Случай 2 — Группа фиксированной длины, неограниченная внешне
-
У каждого потомка
(A B)+,(A B{2})+,((A (B C){2}){2})+min == max, поэтому тело семантически эквивалентно своей развёрнутой форме{1,1}—(A B{2})+ведёт себя как(A B B)+. Каждая итерация потребляет фиксированное число строк; доминирование счётчика по-прежнему выполняется. - Случай 3 — Группа, тело которой начинается с неограниченной переменной
-
Ведущая неограниченная переменная сама абсорбируема (Случай 1) и защищает более ранние контексты. Абсорбция прекращается, как только состояние проходит мимо A — у остальной части тела нет гарантии монотонности, поэтому A получает оба флага, охватывающий BEGIN — флаг области, а B и END — ни одного.
(A+ B)+,(A+ B){2} - Случай 4 — Альтернация
-
Каждая ветвь, достигаемая через цепочку разделителей, оценивается сама по себе по случаям выше; маркер альтернации получает флаг области, если подходит хотя бы одна ветвь.
A+ | B+,A+ | C D
Структурные случаи, не охваченные этими четырьмя формами, не менее поучительны. A B+ не может быть абсорбирован текущим правилом, потому что ведущий A потребляет строку до начала неограниченной части, и контексты, начавшиеся с интервалом в одну строку, находятся на разных позициях внутри неограниченного тела. Нежадные кванторы вроде A+? исключены по построению: правило абсорбции предполагает жадную семантику, в которой более длинные совпадения поглощают более короткие, а нежадное сопоставление обращает это направление.
Результат — поэлементное, а не пошаблонное решение. Один план запроса может иметь абсорбцию, включённую для ведущего A+ в шаблонах вроде (A+ B+ C) или (A+ B+)+ — последний — лишь Случай 3, применённый к его ведущему элементу — и отключённую для всего остального; runtime просто сверяется с атрибутом точки сравнения на элементе текущего состояния каждый раз, рассматривая проход абсорбции. Как только состояние переходит в неабсорбируемую область, абсорбция для этого состояния отключается окончательно — именно то, что §2.5 и §2.6 требуют на алгоритмическом уровне.
3.3 Навигация — обмен кортежами в одной ячейке
Выражения DEFINE — обычные выражения SQL, вычисляемые относительно строки, но они могут включать PREV, NEXT, FIRST или LAST — ссылки, указывающие на другие строки. Сами строки уже буферизованы в tuplestore окна; что executor ещё должен обслуживать — это ячейку кортежа, из которой читает машина выражений SQL, поскольку ссылки на столбцы внутри выражения привязываются к ячейке при планировании. Реализация переиспользует одну навигационную ячейку для каждого вызова навигации: ячейка подменяется перед вычислением внутреннего выражения и восстанавливается после, так что остальная часть машины выражений SQL не замечает разницы.
Модель, видимая executor, мала: есть ячейка текущей строки, содержащая строку, относительно которой вычисляется выражение DEFINE, и навигационная ячейка, которую runtime может временно перенаправить на другую строку. Вокруг любого вызова навигации runtime настраивает навигационную ячейку, вычисляет внутреннее выражение, как если бы оно читало текущую строку, затем восстанавливает исходную строку. Псевдокод:
eval_navigation(call):
targetPos = compute_target_position(call)
если targetPos вне допустимого диапазона:
return NULL
сохранить current_row_slot
если targetPos != currentPos:
загрузить строку из targetPos
в nav_slot
направить внешнюю ячейку на nav_slot
result = eval_inner_expression()
восстановить current_row_slot
скопировать by-ref результат из nav_slot
return result
Хитрость в том, что сохранять и восстанавливать нужно ровно одну ячейку. Внутреннее выражение — каким бы оно ни было, включая арифметику, вызовы функций или другие ссылки на столбцы — выполняется относительно подменённой ячейки тем же путём вычисления, что и для текущей строки. Нет альтернативного вычислителя и нет ячейки на каждую ссылку; когда цель — текущая строка, выборка и подмена пропускаются вовсе. Выборка копирует целевую строку в навигационную ячейку (если ячейка ещё не содержит её), а шаг восстановления копирует результат, передаваемый по ссылке, в память на кортеж, чтобы следующая выборка не могла его освободить.
Составная навигация сплющивается при разборе так, чтобы обмен по-прежнему происходил один раз. PREV(FIRST(price)) распознаётся как двухшаговая навигация — «перейти к первой совпавшей строке, затем шагнуть на одну строку раньше» — и хранится как единственный вызов навигации составного вида. Runtime вычисляет целевую позицию в два этапа, но выполняет только один обмен ячейкой для извлечения финальной строки:
compute_target_position(call):
# относительно текущей строки
PREV(n):
return currentPos − n
NEXT(n):
return currentPos + n
# относительно совпадения
FIRST(n):
return matchStart + n
LAST(n):
return currentPos − n
# составное: match-rel, затем шаг
PREV(FIRST(n), m):
return (matchStart + n) − m
NEXT(FIRST(n), m):
return (matchStart + n) + m
PREV(LAST(n), m):
return (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − n) + m
проверить на соответствующем диапазоне
(диапазон совпадения для внутренних FIRST/LAST,
диапазон секции для внешнего шага)
Кэш позиций позволяет обойти выборку из tuplestore, когда несколько навигационных вызовов в одном DEFINE нацелены на одну и ту же строку — обычное явление в выражениях вида price > PREV(price) AND volume > PREV(volume), где оба вызова приводят к предыдущей строке. Кэш хранит только «последнюю извлечённую позицию», а сам обмен остаётся одной операцией.
Классификация навигационных вызовов — вклад planner в решение об абсорбции. Planner обходит каждое выражение DEFINE и сортирует каждую переменную в одну из двух корзин, исходя из того, будут ли все контексты вычислять одно и то же логическое значение на одной строке или каждый контекст — своё собственное. Корзина определяет во время выполнения две вещи: как часто вычисляется переменная (один раз совместно или по разу на каждый затронутый контекст — §3.5 Фаза 1) и возможна ли абсорбция контекста вообще (§2.5 vs §2.6): одна переменная, зависящая от начала совпадения, отключает её для всего шаблона.
- Без навигации
- Только
PREV/NEXT LASTбез смещения- Составная с внутренним
LAST(без смещения)
LASTсо смещениемFIRST(любая форма)- Составная с внутренним
FIRST - Составная с внутренним
LAST(со смещением)
Классификация выполняется во время планирования и хранится рядом с каждой переменной DEFINE, поэтому runtime не тратит времени на принятие решения — он просто читает корзину каждой переменной при обработке строки.
Бюджет хранения
Навигация дотягивается до строк, мимо которых машина оконных функций уже прошла. Чтобы эти строки оставались доступны, executor построен поверх tuplestore, удерживающего скользящее окно недавних строк; вопрос в том, насколько широким должно быть это окно. Executor вычисляет это, исходя из двух дополняющих смещений, разрешая каждое смещение один раз за сканирование (константные — также при инициализации executor, чтобы их мог показать простой EXPLAIN):
- Бюджет lookback
- Насколько далеко назад от текущей строки может дотянуться любой вызов DEFINE.
- Бюджет lookahead-from-start
- Минимальный охват вперёд (назад при отрицательном значении) от начала совпадения старейшего живого контекста — самая ранняя строка, которая может понадобиться любому вызову DEFINE.
Во время выполнения метка отсечения tuplestore устанавливается в более раннюю из двух позиций — текущая строка минус бюджет lookback и начало совпадения старейшего живого контекста плюс бюджет lookahead. Всё, что перед этой меткой, не может быть достигнуто никаким навигационным вызовом ни в одном живом контексте, и tuplestore волен это отбросить. Строки Nav Mark, выводимые EXPLAIN (§3.7) — Lookback и Lookahead — это сами два бюджета, а не измеренные пики. Каждая печатается только тогда, когда её питает какая-либо навигация, и показывается даже без ANALYZE; смещение, значение которого известно только во время выполнения (например, параметр generic-плана), печатается как runtime при простом EXPLAIN и как разрешённое значение при EXPLAIN ANALYZE, а retain all (Lookback) или infinite (Lookahead) обозначает смещение, вызвавшее переполнение.
3.4 Границы совпадения — SKIP, INITIAL и ограниченная рамка
Результат совпадения записывается как два значения: строка, на которой совпадение начинается, и его длина. Отрицательное начало означает, что позиция ещё не вычислялась; как только начало установлено, последующие запросы к executor — «находится ли эта строка внутри совпадения?» — могут отвечать за O(1) проверкой пары. Длина кодирует исход: -1 для несовпавшей строки, 0 для пустого совпадения и число строк для реального совпадения. Длина ноль — это реальный исход, а не ошибка: она представляет шаблон, совпавший без потребления строк, что executor должен отличать как от несовпавшей строки, так и от «по этой позиции попыток совпадения ещё не было».
Предложение AFTER MATCH SKIP определяет, где начинается следующая попытка совпадения. AFTER MATCH SKIP PAST LAST ROW переходит к строке после конца совпадения, давая неперекрывающийся вывод, который нужен большинству запросов, и включая оптимизацию абсорбции.
AFTER MATCH SKIP TO NEXT ROW переходит только к строке после начала совпадения, разрешая перекрывающиеся совпадения; поэтому planner отключает абсорбцию для шаблона этого окна при этом режиме.
Две другие цели пропуска, определяемые стандартом, — AFTER MATCH SKIP TO FIRST var и AFTER MATCH SKIP TO LAST var — зависят от истории совпадения, которую этот патч не сохраняет. Они вообще отсутствуют в грамматике, поэтому parser выдаёт обобщённую синтаксическую ошибку при их использовании.
То же справедливо для SEEK, альтернативы спецификации к INITIAL. При SEEK попытка совпадения, начинающаяся со строки R, может удасться на любой строке от R до конца рамки, а не только на R. Патч реализует только INITIAL: каждое потенциальное совпадение привязано к конкретной строке. Parser возбуждает ошибку при запросе SEEK. Ограниченные рамки обрабатываются особо — когда пользователь пишет ROWS BETWEEN CURRENT ROW AND N FOLLOWING вместо UNBOUNDED FOLLOWING, executor сокращает любой контекст, чьё совпадение достигло границы, форсируя несовпадение, и абсорбция отключается, так как граница нарушает предположение монотонности, на котором абсорбция базируется.
3.5 Трёхфазный построчный движок
Построчный драйвер executor вызывается окружающей машиной оконных функций всякий раз, когда ей нужно узнать, относится ли данная строка к совпавшей рамке. Драйвер находит или создаёт контекст для текущей стартовой позиции, затем продвигает NFA вперёд строка за строкой — сбрасывая для каждой строки массив совпадений по переменным в «не вычислено», — пока у этого контекста не останется живых состояний или не закончится секция. Предикаты DEFINE вычисляются лениво: переменная вычисляется в первый раз, когда какое-либо состояние её потребляет, поэтому переменная, которую ни одно живое состояние не проверяет на этой строке, никогда не вычисляется. Сам шаг вперёд — три фазы в фиксированном порядке — Match, Absorb, Advance — обёрнутые в общий внешний цикл:
processRow(currentPos):
# Фаза 1 — MATCH (конвергенция)
для каждого контекста:
если контекст достиг конца своего frame:
форсировать mismatch (досрочное завершение)
continue
если matchStartRow отличается от
общей позиции вычисления:
сбросить DEFINE-переменные, зависящие
от начала совпадения, в «не вычислено» (§3.3)
match(context, varMatched)
# Фаза 2 — ABSORB
если шаблон absorbable:
обновить флаги каждого контекста
absorb_contexts()
# Фаза 3 — ADVANCE (дивергенция)
для каждого контекста:
advance(context, currentPos)
если он записал совпадение и
SKIP PAST LAST ROW:
срезать последующие контексты,
начавшиеся внутри совпадения
Порядок — не стилистический выбор. Match должен идти первым, поскольку абсорбция сравнивает постматч-счётчики; запуск Absorb до Match означал бы сравнение состояний, которые вот-вот погибнут. Advance должен идти последним, потому что это единственная фаза, создающая новые состояния — она раскрывает каждое выжившее состояние через эпсилон-переходы, пока каждое не достигнет переменной, ожидающей следующую строку. Запуск Absorb после Advance означал бы сравнение разошедшихся преемников, упуская момент, в котором состояния наиболее чисто сравнимы.
Фаза 1 — Match
Match — фаза «схождения»: состояния либо выживают с инкрементированным счётчиком, либо погибают. Тонкость в том, что для переменных, находящихся в области абсорбции, Match также выполняет небольшой объём продвижения вперёд, чтобы Absorb мог сравнивать чисто. Условие покрытия срабатывает только в точке сравнения абсорбции — END неограниченной группы — поэтому состояния, только что совпавшие с переменными в середине итерации (вроде B внутри (A B)+), необходимо «довести» до этой точки сравнения уже в Match; иначе Absorb не найдёт ничего пригодного для сравнения, и оптимизация не сработает.
match(context, varMatched):
для каждого состояния в context:
elem = pattern[state.elemIdx]
assert elem — переменная
# advance паркует только переменные
если varMatched[elem.varId]
не вычислено:
вычислить его DEFINE сейчас
если не varMatched[elem.varId]:
отбросить state # мёртвая ветвь
continue
state.counts[elem.depth] += 1
# Inline-продвижение вперёд, чтобы
# следующая фаза могла сравнивать
# на элементе точки сравнения,
# а не в середине итерации.
если elem in-region, но не
точка сравнения,
и достиг своего max-счёта,
и elem.next — group end:
пройти цепочку END:
инкрементировать счёт внешней группы
продвинуть state.elemIdx до END
продолжать пока in-region,
must-exit, и next — END
(останавливается в точке сравнения
или на ещё loop-овом элементе)
Прохождение цепочки END и делает вложенные группы фиксированной длины абсорбируемыми. В ((A B){2})+, когда B достигает максимума (B — {1,1}), счётчик внутренней группы должен инкрементироваться; если он также достигает максимума — закрывая внутренний {2} — должен инкрементироваться и счётчик внешней группы, и так далее, пока состояние не попадёт на наружную точку абсорбции — END неограниченной внешней группы (+). Выполнение этой работы в Match позволяет Absorb сравнивать с контекстами, уже консолидировавшими постытерационные счётчики.
Фаза 2 — Absorb
Проход поглощения обходит контексты от самого нового (хвост) к самому старому (голова). Для каждого незавершённого полностью абсорбируемого контекста он ищет назад более старый незавершённый контекст, который его покрывает, и освобождает более новый при нахождении. Поскольку контексты хранятся в порядке создания и каждая строка создаёт не более одного контекста, «новее» и «старше» действительно означают «начат позже» и «начат раньше».
absorb_contexts():
для ctx с хвоста назад:
если ctx завершён
или имеет неабсорбируемое состояние
или хранит записанное совпадение:
пропустить
для older с ctx.prev назад:
если older завершён
или нет абсорбируемого состояния:
пропустить
если covered(older, ctx):
free(ctx)
записать длину поглощения
break
covered(older, newer):
для каждого состояния в newer:
elem = pattern[state.elemIdx]
если elem не точка сравнения:
return false
если в older нет состояния с:
тем же elemIdx
и isAbsorbable
и older.counts[depth]
>= newer.counts[depth]:
return false
return true
Из этого следуют два микрорешения. Первое: проверка покрытия отклоняет немедленно, если любое состояние более нового контекста находится в позиции, отличной от точки сравнения — сравнение в неоценочных точках не было бы осмысленным сравнением.
Второе — асимметричная пара флагов на каждом контексте: has-absorbable-state отвечает «может ли этот контекст поглотить более новый?» и является монотонным (может только переходить true→false по мере гибели состояний), тогда как all-states-absorbable отвечает «может ли этот контекст быть поглощён?» и является динамическим (возвращается в true при удалении неабсорбируемого состояния), пока контекст не запишет совпадение, что закрепляет его в false — поглощение освободило бы совпадение, которое ни один поглощающий контекст не может воспроизвести. Оба флага проверяются за константное время ещё до начала сканирования покрытия, поэтому абсорбция несёт полную стоимость только на контекстах, имеющих реальный шанс быть поглощёнными.
Фаза 3 — Advance
Advance — фаза «расхождения»: каждое выжившее состояние раскрывается через эпсилон-переходы, пока каждая ветвь не достигнет либо переменной, ожидающей следующую строку, либо страницы FIN. Раскрытие — в глубину, и порядок обхода соседних ветвей — то, что заставляет правило предпочтения стандарта реально работать: лексикографически первая ветвь всегда добавляется первой, а шаг дедупликации при вставке состояния молча отбрасывает эквивалентные более поздние добавления.
advance(context, currentPos):
извлечь все текущие состояния;
перестроить ctx.states с нуля
для каждого состояния в лексическом порядке:
очистить bitmap посещённых
advance_state(state) # DFS
# Преферменция: как только DFS
# достигает FIN, оставшиеся состояния
# менее предпочтительны и могут быть
# отброшены.
если FIN достигнут и состояния остались:
освободить остальные
break
advance_state(state):
идти по state.elemIdx,
рекурсивно проходить через:
ветви ALT (по порядку, останавливаясь,
как только записан FIN),
BEGIN (войти в группу; плюс опциональный
путь пропуска если min = 0),
END (loop back / exit / fast-forward —
см. ниже),
FIN (записать matchEndRow,
сохранить matchedState и пометить
контекст, чтобы последующие контексты
внутри диапазона кандидата были
срезаны — см. ниже),
останавливаясь на каждой встреченной переменной:
добавить состояние в ctx.states
(дедуплицируя по elemIdx + counts)
Запись состояния, достигшего FIN, делает больше, чем просто отмечает кандидатное совпадение. При AFTER MATCH SKIP PAST LAST ROW следующее сообщаемое совпадение должно начинаться строго после текущего — поэтому как только Advance закончит с контекстом, записавшим кандидата, каждый последующий контекст, чья стартовая строка попадает внутрь диапазона кандидата, отсекается на той же строке, даже если контекст, достигший FIN, может продолжать поиск более длинного совпадения через жадный откат.
Отсечение безопасно, потому что независимо от того, как завершится этот поиск (более длинное совпадение заменит кандидата или кандидат останется), все отсечённые контексты начались внутри диапазона, который следующее сообщаемое совпадение должно пропустить, и поэтому никогда не смогли бы дать собственного вывода.
Это межконтекстный шаг отсечения времени FIN. Внутри контекста FIN также обрезает лексикографически уступающую работу: Advance отбрасывает оставшиеся состояния в очереди (описано ранее в этом разделе), а в пределах одного DFS каждый менее предпочтительный путь — более поздние ветви ALT, второй из путей пропуска и входа у BEGIN, путь входа нежадной переменной, второй из путей цикла и выхода у END — останавливается, как только записано совпадение, поэтому один advance записывает не более одного совпадения.
Самая хитрая поэлементная логика — в обработчике END. Когда счётчик итераций группы ниже нижней границы, runtime должен зациклиться обратно; когда он на верхней границе или выше, должен выйти; между ними оба варианта валидны, и жадность квантора решает, что пробовать первым:
advance_end(state, elem):
count = state.counts[elem.depth]
если count < elem.min:
зациклиться обратно в тело
если elem — empty-loopable:
# обнуляемое тело, см. §3.2
также клонировать fast-forward-
состояние, выходящее из группы
с удовлетворённым count
(fast-forward первым, если тело
предпочитает пустое; второй путь
отбрасывается, если первый
достиг FIN)
иначе если count >= elem.max:
сбросить counts на этой глубине
выйти через next
(END→END: инкрементировать count
внешнего END)
иначе:
# min <= count < max: ветвление
построить состояние выхода
(counts на этой глубине сброшены)
если greedy:
сначала loop
если loop достиг FIN:
отбросить exit
# предпочтение длиннее
иначе exit вторым
иначе (reluctant):
сначала exit
если exit достиг FIN:
отбросить loop
# предпочтение короче
иначе loop вторым
Каждое состояние, добавляемое в контекст, проходит проверку дедупликации, сравнивающую его позицию и счётчики с существующим списком состояний. Поскольку Advance обрабатывает ветви в порядке DFS, состояние из первой ветви любой альтернации попадает первым — и любая более поздняя ветвь с такой же позицией и счётчиками отклоняется при вставке. Это именно то, что требует правило лексикографического порядка из §2.4, реализованное на нижнем уровне runtime без отдельного прохода.
Empty-loopable группы
Тонкий случай, который runtime должен обезвредить, — обнуляемая группа: группа, чьё тело может совпасть с нулём строк, потому что каждый потомок тела сам необязателен. Шаблоны вроде (A? B?)+ и (A | B*)+ обладают этим свойством: в зависимости от данных тело может завершить итерацию, не потребив ни одной строки. (Единственный необязательный потомок, как в (A?)*, переписывается в A* во время компиляции и не оставляет группы.) В принципе это нормально, но создаёт реальную опасность для эпсилон-раскрытия NFA. Если тело даёт пустое совпадение, элемент END возвращается в тело (его jump — первый потомок группы), тело снова даёт пустое совпадение, снова достигает END, и так далее. Без чего-либо, останавливающего это, DFS Advance никогда бы не завершилась.
Защита решается во время компиляции и исполняется во время выполнения. Когда planner видит группу с обнуляемым телом, он помечает её элемент END как empty-loopable. Runtime держит bitmap посещённых, очищаемый перед DFS-раскрытием каждого состояния, в котором отмечаются только эти помеченные END — больше ничто не может зациклиться, потому что любой другой возврат уже потребил строку. Достижение отмеченного END означает, что тело только что дало пустую итерацию, и состояние не отбрасывается: на нижней границе или выше оно выходит из группы здесь (пустая итерация останавливает квантор), а ниже неё состояние проходит к обычному возврату, так что каждое пустое прибытие всё же увеличивает счётчик, пока он не достигнет min. Возьмём (A? B?){2,3}, где ни одна переменная нигде не совпадает в потоке строк:
iter 1: A? B? совпадают с нулём строк
→ END, count = 1 (ниже min)
END уже отмечен (при входе
в группу), но ниже min:
→ зациклиться обратно в A?
iter 2: A? B? совпадают с нулём строк
→ END, count = 2 (достигает min)
END уже отмечен, на min:
→ выйти из группы
выйти с совпадением нулевой длины
Ниже нижней границы тег пустого цикла также указывает обработчику END клонировать дополнительное fast-forward-состояние рядом с обычным путём возврата:
advance_end (count ниже min):
путь возврата:
зациклиться обратно в тело
(оставляет дверь открытой для
реального, непустого совпадения
в следующей итерации)
если elem — empty-loopable:
fast-forward-путь:
сбросить count этой глубины
выйти из группы через next,
трактуя оставшиеся требуемые
итерации как пустые совпадения
Два пути играют дополняющие роли. Возврат ловит случай, когда тело ещё имеет реальные совпадения позже — например, в (A? B?){2,3}, за которым следуют данные, где A совпадает только на более поздних строках, возврат позволяет второй и третьей итерациям найти непустые совпадения. Fast-forward сразу выходит из группы, заявляя «оставшиеся требуемые итерации пусты», и позволяет совпадению удасться с телом нулевой длины. Порядок определяет тело, а не собственная жадность группы: fast-forward идёт первым ровно тогда, когда тело предпочитает пустое совпадение (нежадное тело, такое как (A?? B??)), и если первый путь достигает FIN, второй отбрасывается, поэтому менее предпочтительный путь не может заменить предпочтительное совпадение. Проверка дедупликации при вставке не позволяет ни одному из путей породить больше состояний, чем положено.
Помимо защиты от циклов, ещё один стартовый приём устраняет неоднозначность исходов нулевой длины в самом начале контекста. Шаг создания контекста на каждой потенциальной стартовой строке выполняет начальный advance через эпсилон-переходы до потребления любой строки, используя позицию на одну строку раньше фактического старта. Любой путь, достигший страница FIN только через эпсилон-переходы — без потребления строки — поэтому даёт конечную позицию меньше стартовой; эта координата с отрицательным диапазоном в сочетании с тем, был ли реально достигнут FIN, кодирует разницу между пустым совпадением (принятое совпадение длины 0) и несовпавшим стартом без необходимости отдельного флага.
3.6 Как пространство состояний остаётся ограниченным
То, что runtime остаётся ограниченным, — не результат одной оптимизации. Это совокупный эффект слоёного набора правил отсечения, каждое из которых ловит свою причину роста пространства состояний в своей точке построчного цикла. Некоторые решаются во время компиляции и лишь сверяются во время выполнения; другие срабатывают динамически. Некоторые убивают отдельные состояния; другие — целые контексты. Разделы выше представили каждое из них в контексте; таблица ниже сводит их на одну страницу.
- Невыполненный предикат Match
- Состояния переменных, чей DEFINE на текущей строке оказался ложным — мёртвые ветви.
- Встроенное продвижение по END-цепочке Match
- Переменные, достигшие максимума счётчика, которые иначе оставили бы состояние в середине итерации; продвигаются через концы групп фиксированной длины, чтобы абсорбция могла сравнивать в правильной точке.
- Абсорбция контекста Absorb
- Более новые контексты, чьё каждое состояние стоит в точке сравнения и покрыто абсорбируемым состоянием более старого контекста на том же элементе с большим или равным счётчиком — см. §2.5 для концептуального правила, §3.2 для допустимости при компиляции, §3.5 для проверки по парам.
- Дедупликация состояний Advance
- Состояния, достигнутые разными ветвями DFS и оказавшиеся в той же позиции с теми же счётчиками — выживает только первое (лексикографически самое раннее); более поздние эквиваленты молча отбрасываются, что также реализует предпочтение (§2.4).
- Раннее завершение по FIN (в пределах контекста) Advance
- Состояния, ещё ожидающие в очереди DFS, когда одна ветвь достигает FIN — по лексикографическому порядку все оставшиеся менее предпочтительны и могут быть немедленно отброшены.
- Отсечение кандидатных совпадений (между контекстами) Advance
- Другие контексты, чья стартовая строка попадает в диапазон кандидатного совпадения — контекст, достигший FIN, может продолжать поиск более длинного совпадения (жадный откат), но при
AFTER MATCH SKIP PAST LAST ROWлюбой контекст внутри диапазона кандидата уже не сможет дать сообщаемый вывод независимо от того, как закончится поиск, и отсекается, как только Advance закончит с контекстом, записавшим кандидата. - Защита от циклов Advance
- Эпсилон-раскрытия, достигающие END обнуляемой группы, уже отмеченного в рамках того же DFS (отмеченного при входе через BEGIN или при более раннем прибытии) — иначе зацикливались бы навечно; на нижней границе или выше состояние выходит из группы здесь, а ниже неё продолжает цикл.
- Empty-loop fast-forward Advance
- Ниже нижней границы обнуляемой группы — дополнительный путь, выходящий из группы с оставшимися требуемыми итерациями, объявленными пустыми, и упорядоченный относительно возврата по предпочтению тела.
- Отсечение по ограниченной рамке Match
- Контексты, чьё совпадение достигло заданной пользователем верхней границы рамки — принудительно несовпадают, чтобы не выходить за неё (§3.4).
Чтение записей по их фазовой метке прослеживает жизненный цикл контекста: отсечение срабатывает на каждой строке через три основные фазы (Match, Absorb, Advance). Чтение описаний, наоборот, группирует правила по их целям: мёртвые ветви, избыточные контексты, эквивалентные состояния, бесконечные циклы и расширение за пользовательские границы.
Ни одного правила в одиночку не было бы достаточно. Fast-forward пустого цикла сам по себе не остановил бы бесконечные эпсилон-циклы; одна абсорбция переконсолидировала бы при ссылке DEFINE на начало совпадения; одна дедупликация не убрала бы избыточные контексты, только избыточные состояния. Runtime остаётся линейным в значимых случаях — PATTERN (A+ B+ C+ D) на 100 000 строк, бенчмарк панели ③ постера — только потому, что каждый слой ловит то, что упускают слои над ним. Исходный код документирует случаи, которые слои не ловят: дедупликация сохраняет состояния, различающиеся только счётчиками выше min, поэтому (A{2,} B)+ C, где C никогда не истинно, удерживает Θ(n²) состояний на пике и создаёт их Θ(n³) (37 с на 320 строках), а цепочка полностью обнуляемых альтернаций перечисляется путь за путём, поэтому (A?|B?){30} выполняется более получаса.
3.7 Вывод EXPLAIN
EXPLAIN ANALYZE на запросе с RPR показывает статистику уровня NFA, которой нет у обычных оконных функций. В текстовом формате она выводится рядом с оконным оператором, после строки Pattern:, строк Nav Mark, если они есть (их показывает и простой EXPLAIN), и строки Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(каждая — только когда DEFINE использует
навигацию, которая её питает)
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)
(вторая строка NFA — только когда хотя бы
один счётчик ненулевой; нулевой счётчик
печатается без своего (len ...))
Нетекстовые форматы выдают каждый счётчик как отдельное свойство. Peak и total — прямые приборы runtime: сколько состояний когда-либо были живы одновременно, сколько было создано за время жизни запроса и сколько было слито дедупликацией; pruned считает контексты, провалившиеся после одной строки. Гистограммы длин совпадений разделяют четыре исхода — успешные совпадения, попытки, провалившиеся после более чем одной строки (mismatched), поглощённые контексты и контексты, освобождённые AFTER MATCH SKIP PAST LAST ROW, потому что они начались внутри записанного совпадения (skipped), — и выдача их с min/max/avg делает патологии производительности видимыми с первого взгляда: здоровый прогон показывает большинство контекстов либо как совпавшие, либо как поглощённые, с малыми длинами несовпадений.
Два счётчика Nav Mark сообщают бюджет хранения tuplestore, который §3.3 выводит из DEFINE. Lookback — самый глубокий охват назад от текущей строки через PREV, LAST с любым смещением (включая 0 по умолчанию) и составные формы с внутренним LAST; Lookahead — минимальный охват вперёд (отрицательный, когда он смотрит раньше начала совпадения), отсчитываемый от начала совпадения старейшего живого контекста, вносимый FIRST и составными формами с внутренним FIRST.
Каждый счётчик печатается как фиксированное целое, когда смещение константное, «runtime», когда смещение — неконстантное выражение, значение которого определяется только при каждом сканировании, и — только для Lookback — «retain all», когда смещение переполняется; переполнившийся Lookahead печатается как «infinite». Каждая строка выводится только когда её питает какая-либо навигация в DEFINE, и обе появляются и при простом EXPLAIN: константные смещения устанавливаются при инициализации executor, а смещение, известное только во время выполнения (например, параметр generic-плана), печатается там как «runtime» и как разрешённое целое при EXPLAIN ANALYZE.
Вместе эти счётчики позволяют отлаживать производительность RPR без подключения gdb к backend.
Помимо счётчиков, EXPLAIN печатает строку Pattern:, построенную из скомпилированного массива элементов, поэтому она показывает шаблон после перезаписей времени компиляции (PATTERN (A A) объясняется как a{2}) и несёт маркеры абсорбции # (точка сравнения) и ~ (область абсорбции); DEFINE и опция AFTER MATCH SKIP не показываются. Воспроизведение предложений в исходном виде, включая нежадные кванторы, повторение групп и опцию пропуска, — задача pg_get_viewdef(), который прилагает усилия для стабильности этого циклического преобразования, чтобы pg_dump и pg_upgrade могли сохранять объекты RPR без семантического дрейфа — регрессионный набор rpr_explain проверяет это случай за случаем (см. §4).
§4. Тесты — карта покрытия
Патч сопровождается пятью регрессионными наборами, которые вместе покрывают каждый слой, описанный в §3 — около 22 000 строк SQL, каждый набор сосредоточен на отдельной задаче. Разделение намеренное: хранение задач parser, корректности runtime, взаимодействий с planner и форматирования вывода в отдельных файлах облегчает локализацию ошибок и предотвращает случайную инвалидизацию тестов одного слоя несвязанным изменением в другом. Пять наборов:
- rpr
- Интеграция с предложением WINDOW — реалистичные оконные сценарии на синтетических данных по акциям (V-форма, W-форма, последовательные подъёмы, развороты), а также семантика навигации и ошибки ограничений DEFINE.
- rpr_base
- Слой parser — приём ключевых слов, синтаксические формы, кванторы, разбор навигации, сообщения об ошибках и стабильность циклического преобразования pg_dump/pg_upgrade; а также слой planner — оптимизация шаблонов, флаги абсорбции, откат оптимизации, интеграция с planner.
- rpr_nfa
- Runtime NFA — трёхфазный цикл, абсорбция во всех абсорбируемых формах и краевые случаи жизненного цикла контекстов.
- rpr_explain
- Форматирование вывода — статистика NFA, деппарс шаблона, экранирование идентификаторов, стабильность формата при перезагрузке.
- rpr_integration
- Взаимодействия с planner — защиты, не позволяющие посторонним оконным оптимизациям повреждать семантику RPR.
4.1 rpr — сквозные сценарии
Набор сценариев — публичное лицо тестового комплекта: используется синтетический набор данных по ценам акций из примерно 1600 строк, и запускаются реалистичные запросы — восстановление V-формы, W-форма (двойное дно), последовательные подъёмы и спады, шаблоны разворота, многосимвольные секции. Эти сценарии — единственные тесты, чьи входы и выходы читаются как запросы, которые пользователь действительно мог бы написать; остальная часть файла, как и другие наборы, редуктивна — ошибки вложенности PREV/NEXT и неконстантных смещений, правила ссылок в DEFINE и семантика смещений навигации.
Поскольку эти запросы соединяют каждый слой (parser, planner, executor, EXPLAIN), одиночный сбой в rpr редко указывает, где находится ошибка. Четыре последующих набора — бисекция: сбой в rpr плюс прошедший rpr_base исключает parser; плюс прошедший rpr_nfa сужает до специфики формы данных сценария; плюс прошедший rpr_integration исключает помехи planner; а любой дрейф деппарса проявляется в rpr_explain.
4.2 rpr_base — поверхность parser
Базовый набор самый крупный, и крупный по причине: он отвечает за доказательство того, что каждая легальная часть синтаксиса из §1.2 действительно разбирается, каждая нелегальная из §1.3 отклоняется с полезной ошибкой, а каждая принятая форма переживает сериализационное циклическое преобразование. Основная его масса — небольшие сфокусированные сниппеты, по одному на синтаксическую возможность, а не длинные реалистичные запросы, поскольку цель — покрытие, а не реалистичность сценариев. Вторая часть, слой planner, охватывает оптимизацию шаблонов, отображение и анализ флагов абсорбции, откат оптимизации и интеграцию с planner (подзапросы, соединения, операции над множествами, сортировку и группировку).
Тесты сериализации заслуживают особого внимания. Объекты RPR (представления, материализованные представления, вывод pg_dump) должны проходить циклическое преобразование через каталожное представление без семантического дрейфа, включая такие тонкости, как нежадный флаг на кванторе или точная форма выражения составной навигации. Небольшой набор сериализационно-специфичных объектов (представления rpr_serial_v* и их подстилающие таблицы) намеренно оставляется на месте в конце прогона, чтобы окружающая регрессионная инфраструктура могла их подхватить и прогнать против них pg_dump и pg_upgrade. Остальные тестовые «леса» сбрасываются как обычно. Дефекты вроде потери нежадного флага между деппарсом и повторным разбором проявляются только при сквозной проверке циклического преобразования.
4.3 rpr_nfa — движок выполнения
Это набор, тестирующий каждый механизм, описанный в §3.5 и §3.6. Его тесты следуют согласованному шаблону: встроенные строки VALUES, несущие массив имён переменных, который объявляет, какие переменные DEFINE совпадают на каждой строке, в паре с шаблоном, проверяющим конкретное поведение runtime. Идиома массивов разъединяет тест runtime и машину вычисления DEFINE — проверяется «при условии, что эти переменные совпадают здесь, даёт ли цикл NFA ожидаемый диапазон совпадения?», а не «правильно ли вычислитель выражений DEFINE считает эти булевы значения?». Вычислитель DEFINE тестируется в других местах (rpr_base для разбора, rpr для сквозного поведения).
Типичный тестовый стенд выглядит так — столбец массивов имён переменных, где каждая запись говорит, какие переменные DEFINE срабатывают на этой строке, и шаблон, чьи предложения DEFINE проверяют эти имена напрямую:
SELECT id, flags, first_value(id) OVER w AS ms, last_value(id) OVER w AS me FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A','B']), (3, ARRAY['A','B']), (4, ARRAY['B']), (5, ARRAY['_']), (6, ARRAY['A'])) AS t(id, flags) WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING INITIAL PATTERN (A+ B+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));
Чтение столбца массивов вниз — это прямое чтение тестового сценария. Строки 2 и 3 несут оба имени — A и B срабатывают там обе, так что у NFA есть реальный выбор, где переключиться с A-плеча на B-плечо. Ожидаемое совпадение (A на строках 1–3 с последующим B на строке 4 при жадном предпочтении стандарта) определяется одними этими флагами, без какой-либо значимой здесь оценки выражений — = ANY — лишь тривиальный слой, выставляющий столбец массива для DEFINE, не то, что тест проверяет. Запись того же сценария с числовым предикатом (price > PREV(price) и подобное) переплела бы тест NFA с поведением вычислителя предикатов; идиома массивов держит их чисто раздельно, и сбой здесь указывает прямо на цикл NFA.
Покрытие абсорбции особенно тщательное, поскольку абсорбция — оптимизация, которая с наибольшей вероятностью молча даст неверные ответы, если включится, когда не должна. Тесты охватывают все формы из анализа случаев §3.2:
- простая неограниченная переменная (
A+) — каноничное свёртывание N в 1; - группы фиксированной длины (
(A B)+,(A B{2})+, трёхуровневая вложенная((A (B C){2}){2})+); - ведущая неограниченная переменная с фиксированным суффиксом (
A+ B) — только ведущаяA+несёт флаги абсорбции, суффикс — нет; - поветвенная абсорбция внутри альтернации (
B+ C | B+ D); - несколько неограниченных переменных (
A+ B+) — абсорбируема только ведущая; - нежадные кванторы (
A+?) — проверены как исключённые из абсорбции; - не ведущая неограниченная (
A B+) — проверена как исключённая.
Помимо абсорбции, набор охватывает жизненный цикл контекстов: перекрывающиеся контексты при AFTER MATCH SKIP TO NEXT ROW, очистку проваленных контекстов в середине потока, финализацию незавершённых контекстов в конце секции и контексты, встретившиеся после того как кандидатное совпадение уже записано в головном контексте. Каждый случай отображается на конкретное правило отсечения из §3.6, и тесты написаны так, чтобы громко падать при сбое правила (либо оставляя избыточные контексты живыми, либо убивая контекст, который должен был дать вывод).
4.4 rpr_explain — стабильность вывода
Вывод EXPLAIN — часть пользовательского контракта; сторонние инструменты (мониторинговые дашборды, парсеры журналов) разбирают его, и изменения, кажущиеся косметическими, могут их сломать. Набор rpr_explain проверяет три вещи:
- Счётчики NFA появляются в правильном месте — статистика на каждый WindowAgg (peak/total/merged states, peak/total/pruned contexts, гистограммы длин для matched/mismatched/absorbed/skipped) появляется в
EXPLAIN ANALYZEв текстовом формате, JSON и XML с документированными метками, а Nav Mark Lookback и Lookahead появляются ровно тогда, когда их питает навигация в DEFINE. - Шаблоны корректно деппарсятся — каждая форма квантора, включая нежадные варианты и ограниченные формы; каждая альтернация; каждая группа; каждая форма
AFTER MATCH SKIP;INITIAL; навигационные вызовы со смещениями; составная навигация. Деппарсенный текст должен пройти циклическое преобразование обратно через parser неизменённым. - Экранирование идентификаторов корректно — переменные шаблона и выражения DEFINE выводятся по тем же правилам экранирования, что и обычные идентификаторы SQL, чтобы необычные имена переменных не ломали вывод
pg_dump.
Как и rpr_base, этот набор намеренно оставляет свои объекты на месте по окончании прогона, чтобы покрытие pg_dump и pg_upgrade распространялось и на артефакты со стороны explain.
4.5 rpr_integration — взаимодействия с planner
Planner PostgreSQL имеет множество оптимизаций, работающих с оконными запросами — канонизация рамки, проталкивание run-condition, дедупликация идентичных окон, проекция неиспользуемого вывода, инверсные переходы скользящих агрегатов — и каждая из них спроектирована без учёта RPR. Большинство небезопасны для применения, когда у окна есть предложение PATTERN: рамка — часть контракта совпадения, выход совпадений уже не монотонен в каком-либо очевидном смысле, и два окна с одинаковой спецификацией, но разными DEFINE, дают действительно разные результаты. Интеграционный набор проверяет, как каждая из этих оптимизаций обращается с окнами RPR — большинство должны быть отключены или обходиться:
- Канонизация рамки
- Planner обычно переписывает
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGвROWS UNBOUNDED PRECEDINGдля оконных функций, не зависящих от рамки, таких какrow_number,rankиntile. Рамка RPR — диапазон совпадения, а не агрегационное окно, и должна оставаться дословно. - Проталкивание run-condition
- Монотонный фильтр
WHEREна выходе оконной функции обычно может быть протолкнут в оконный оператор как условие остановки. Для RPR это преждевременно прервало бы сопоставление шаблона, возможно отрезая совпадения в середине расширения. - Дедупликация окон (RPR vs не-RPR)
- Два окна с идентичными
ORDER BYи рамкой обычно сливаются в одно. Окно RPR и не-RPR никогда не могут разделять состояние, потому что сторона RPR несёт результаты совпадений. - Дедупликация окон (разные DEFINE или SKIP)
- Два окна RPR с одинаковым
PATTERN, но разными предложениямиDEFINEили разнымAFTER MATCH SKIP, дают разные совпадения и должны оставаться различными, даже если их структурная форма идентична. - Проекция неиспользуемого вывода
- Эта оптимизация применяться может: когда окружающий запрос никогда не читает вывод окна, оконная функция становится NULL и её WindowAgg удаляется, а число строк не меняется. Тесты проверяют, что столбцы, которые читает DEFINE, по-прежнему доходят до WindowAgg, когда он остаётся, и что окно сохраняется, когда его значение читается.
- Инверсные переходы скользящих агрегатов
- Оконные агрегаты с инверсной переходной функцией обычно могут вычисляться инкрементно по мере движения рамки. Сжатая рамка RPR — не скользящее окно; путь инверсного перехода дал бы неверные результаты.
Дополнительные случаи проверяют, что оценка стоимости учитывает DEFINE, что подзапрос с окном RPR не уплощается, что выражения DEFINE не просачиваются в вышестоящий WindowAgg и что LIMIT остаётся над WindowAgg; вторая группа запускает RPR вместе с CTE, соединениями, операциями над множествами, подготовленными операторами, секционированными таблицами и подобными конструкциями. Большинство защищаемых случаев имеют одну форму: базис, запускающий оптимизацию (обычно не-RPR запрос, проверяемый в EXPLAIN), затем запрос RPR структурно похожей формы, где оптимизация не применяется — для случая дедупликации DEFINE/SKIP базисом служат два одинаковых окна RPR, а случай инверсного перехода проверяет обход с помощью журналирующего агрегата, а не EXPLAIN. Обе половины вместе доказывают, что защита в planner делает реальную работу, а не одобряет каждый запрос без реальной проверки.
Этот набор — также причина того, что §3.4 короток. Механизмы «границ совпадения» — сжатая рамка, SKIP, INITIAL, отсечение по ограниченной рамке — операционно тестируются в других местах; что rpr_integration проверяет — это что никакая другая стадия оптимизатора не вмешивается в них на пути. Прошедший rpr_integration — то, что позволяет остальным наборам доверять, что их входы достигают executor нетронутыми.