Row Pattern Recognition Глубокое погружение

§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 для получения вывода оконной функции. Обе формы делят большую часть синтаксиса и всю семантику, но представляют собой функционально различные точки входа — база данных может реализовать одну из них или обе.

Серия патчей, обсуждаемая здесь, реализует подмножество только R020; форма с табличным предложением намеренно оставлена вне области.

Поверхность R020 невелика, но выразительна. Запрос привязывает шаблон к окну добавлением трёх предложений внутри спецификации окна: PATTERN описывает регулярное выражение над именованными переменными шаблона, DEFINE задаёт логический предикат, идентифицирующий каждую переменную, а AFTER MATCH SKIP определяет расположение последующих совпадений внутри секции.

Необязательные 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

Определяет шаблон строк внутри спецификации окна.

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)) — как внутренний, так и внешний шаг принимают собственное смещение.

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 метка, AFTER MATCH SKIP TO FIRST var и AFTER MATCH SKIP TO LAST var. Они также зависят от истории совпадений, так как executor должен иметь возможность указать на конкретную помеченную строку внутри самого недавнего совпадения.

Оставшиеся пункты составляют разнородный хвост: ключевое слово SEEK (альтернатива INITIAL), пустой шаблон (), форма исключения {- … -} и нечувствительный к порядку оператор PERMUTE.

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 метка

Переход к помеченной строке.

AFTER MATCH SKIP TO FIRST var

Переход к первой строке, сопоставленной как именованная переменная.

AFTER MATCH SKIP TO LAST var

Переход к последней строке, сопоставленной как именованная переменная.

Regex: {- -}

Исключение — удаляет совпавшие строки из вывода для совпадения.

Regex: ()

Пустой шаблон — соответствует пустой последовательности.

PERMUTE(...)

Сопоставление, нечувствительное к порядку, по перечисленным переменным.

Агрегатные функции в DEFINE

Агрегаты, такие как SUM, AVG, COUNT, не допускаются в предикатах DEFINE. Стандарт допускает их как накапливающиеся агрегаты по частичному совпадению (построчное вычисление по строкам, уже сопоставленным переменной), что зависит от той же истории совпадений, которая нужна MEASURES/CLASSIFIER().

Здесь стоит отметить ещё четыре пункта, поскольку их легко принять за упущения.

Первый: якоря шаблона ^ и $ не разрешены с 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 не могут ссылаться на переменные шаблона строк; RPR не может использоваться внутри рекурсивного запроса.

Четвёртый: сам MATCH_RECOGNIZE — возможность R010, табличная форма того же механизма — вне области данного патча. Появится ли в PostgreSQL в конечном итоге R010 — вопрос для будущей серии, а не критерий оценки текущей.

Источник. Списки реализованных и нереализованных возможностей в этом разделе отражают текущее состояние серии патчей — в частности, v47 (2026-05-02).

§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 позиций после текущей. Просмотр вперёд; редок в оконной форме, поскольку окно монотонно.

FIRST(expr [, n])

Строка с номером n в текущем совпадении, считая от начала. «Сравнение со строкой, начавшей это совпадение».

LAST(expr [, n])

Строка с номером n, считая от самой последней совпавшей. «Сравнение с самой недавней совпавшей строкой».

Четыре примитива комбинируются: PREV и NEXT могут оборачивать вызов FIRST или LAST, давая четыре составные формы, семантика которых: «перейти к строке относительно совпадения, затем сделать фиксированный шаг от неё». Именно это позволяет выражению DEFINE читать, например, строку, непосредственно предшествующую началу совпадения.

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

Шаг на m позиций назад от n-й строки совпадения (по умолчанию m = 1). «Каким было значение непосредственно перед началом этого совпадения?»

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

Шаг на m позиций вперёд от n-й строки совпадения. Заглядывает дальше в совпадение, не завися от текущей строки.

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

Шаг на m позиций назад от n-й самой недавней совпавшей строки. «Сравнение со строкой незадолго до последнего совпадения».

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

Шаг на m позиций вперёд от n-й самой недавней совпавшей строки.

Здесь стоит отметить два практических момента. Во-первых, навигация может комбинироваться: PREV(FIRST(price)) читает строку непосредственно перед началом совпадения, и патч это поддерживает. Во-вторых, навигация имеет последствия для оптимизаций executor. PREV и NEXT относительны текущей строке и всегда безопасны; FIRST и варианты LAST со смещением относительны границам совпадения, что взаимодействует с абсорбцией контекста и заставляет планировщик удерживать живыми контексты, которые иначе были бы отброшены. Механизм этого взаимодействия — тема §2.6.

2.3 Разбираемый пример 1 — движение NFA

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

Шаблон разворачивается в четыре элемента:

[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:

Ключевой момент: на строке 3 строка удовлетворяет одновременно START (всегда истинно) и DOWN, но единственное состояние, выжившее на строке 2, находится на ветви выхода к DOWN, поэтому выполняется только переход UP → DOWN. Многосостоянная природа §2.1 проявляется как разветвление при каждом совпадении UP (состояние может остаться на UP+ или продвинуться к DOWN+). Жадное предпочтение — «зациклиться снова перед выходом», поэтому при достаточных данных зацикленные ветви продлили бы совпадение дальше; здесь зацикленное DOWN погибает на строке 5 (130 ≮ 108), а более ранний кандидат FIN (строки 0–4) — порождённый при выходе DOWN на строке 4 — финализируется как совпадение.

Результат запроса напрямую следует из этой трассировки. По семантике RPR оконные функции first_value(price) и last_value(price) вычисляются только на строке, начавшей совпадение — все прочие строки совпадения дают NULL для этих оконных функций, так как их сжатая рамка пуста. Поэтому вывод для наших данных выглядит как таблица, показанная на постере в верхней правой панели:

Строка 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 их не разрешит.

Обе ветви дают совпадение одинаковой длины по одним и тем же строкам, оставляя сопоставителю два кандидатных пути — один помеченный UP, DONE, другой — HIGH, DONE. Стандарт разрешает это по лексикографическому порядку: среди альтернатив, записанных в (UP | HIGH), побеждает та, что записана первой, независимо от длины совпадения. Поскольку UP идёт раньше HIGH, выживший путь — UP, DONE.

Лексикографический порядок и делает CLASSIFIER() однозначно определённым, когда он будет реализован — он позволяет runtime сообщить пользователю «эта строка совпала как UP, а не HIGH» даже когда оба предиката были истинны. Лексикографический порядок — основное правило для альтернации: лексикографически более ранняя ветвь побеждает более позднюю, даже если более поздняя дала бы более длинное совпадение, а более поздняя (возможно, более короткая) ветвь всё же может победить, если каждая более ранняя погибнет, не достигнув FIN. Жадная длина решается внутри одного квантора — при двух завершениях одной ветви альтернации жадный квантор предпочитает большее число итераций.

2.5 Разбираемый пример 3 — Абсорбция контекста (одна судьба)

Простейший шаблон, демонстрирующий абсорбцию, — PATTERN (A+) с DEFINE A AS TRUE. Каждая строка совпадает с A, и стандарт требует, чтобы сопоставитель рассматривал каждую строку как возможное начало совпадения. Наивно это означает N контекстов для секции из N строк. Рассмотрим секцию из пяти строк (любые данные — предикат всегда истинен):

Память растёт с O(n) до O(1). Правило абсорбции, обосновывающее отбрасывание, прямолинейно, когда квантор неограничен:

Левая нижняя панель постера («① 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 на каждой строке сравнивает цену строки с её непосредственным предшественником — факт уровня секции, а не контекста — поэтому оба контекста вынуждены вычислять одно и то же логическое значение на каждой общей строке:

История рушится в тот момент, когда предикат начинает зависеть от собственных границ каждого контекста — и об этом §2.6.

2.6 Разбираемый пример 4 — Когда абсорбция становится небезопасной

Предположим, аналитик хочет найти последовательные торговые дни, когда акция оставалась в пределах десяти долларов от дня, с которого начался прогон — своего рода окно консолидации. Шаблон и DEFINE выглядят так:

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

Условие теперь сравнивает цену текущей строки с ценой в начале текущего прогона. Два прогона, начавшихся в разные дни, имеют разные значения FIRST(price), поэтому два состояния на одном и том же элементе шаблона с одинаковым счётчиком больше не взаимозаменяемы: их будущее зависит от границы, которую абсорбция собиралась отбросить.

Возьмём ту же торговую неделю, что и в §2.5 — $100, $108, $112, $116, $110 с понедельника по пятницу. Runtime снова удерживает два кандидатных прогона одновременно: C1 начат в понедельник, C2 — во вторник (каждая строка является потенциальным началом прогона при STABLE+).

При абсорбции C2 был бы слит с C1 во вторник — слитый контекст хранит только один потолок, поэтому различающее представление C2 (потолок $118, четырёхдневный прогон, заканчивающийся только в субботу) уже невозможно восстановить из внутреннего состояния. C2 обязан остаться живым, поскольку является независимым кандидатом совпадения, который runtime может ещё понадобиться: как только совпадение C1 заканчивается в среду, следующая попытка должна продолжиться с ещё живого C2, а не начинаться заново. Когда предикат DEFINE несёт зависимость от начала совпадения, планировщик поэтому превентивно отключает абсорбцию.

(Когда совпадение ведущего контекста всё же успешно, контексты, начавшиеся внутри его принятого диапазона — при стандартном AFTER MATCH SKIP PAST LAST ROW, — просто отбрасываются; они удерживаются только для того, чтобы runtime имел возможность отката при отказе ведущего совпадения.)

Таблица зависимостей в правой нижней панели постера («② Navigation») обобщает, какие формы навигации создают зависимость от начала совпадения:

Два примера из §2.5 и §2.6 сводятся к одному правилу. Одна судьба делает абсорбцию безопасной: если каждый контекст на одном и том же элементе шаблона вычислит одинаковый ответ на любой будущий предикат, нужно сохранить только старейший. Разные судьбы делают абсорбцию небезопасной: как только предикаты ветвятся на приватном состоянии контекста — что именно делают FIRST и LAST со смещением — каждый живой контекст представляет будущее, которое никакой другой контекст не сможет восстановить, и отбрасывание любого из них рискует выдать неверный ответ.

Планировщик распознаёт это различие во время компиляции и решает поконтекстно, применима ли абсорбция. Именно поэтому бенчмарк постера в панели ③ остаётся линейным как при успехе, так и при отказе: когда абсорбция безопасна, runtime сворачивает контексты, а когда нет — планировщик принимает многоконтекстную стоимость, чтобы не рисковать неверным ответом.

Числа бенчмарка на постере — тот же алгоритм в масштабе. На шаблоне успеха (A+ B+ C+ D) и PostgreSQL, и Trino масштабируются O(n) после подтверждения совпадения, а отрыв PostgreSQL — примерно 16× до 33× — преимущественно объясняется разницей JVM.

На шаблоне отказа (A+ B+ C+ E) Trino не имеет абсорбции и деградирует до O(n²), преследуя каждое потенциальное начало совпадения; при 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. Ни одно из них нельзя заменить «более длинным, начинающимся раньше», потому что стандарт утверждает, что пользователь хочет получить их все.

Заметим, что предикат не изменился. A AS TRUE вычисляется одинаково на каждой строке независимо от того, какой контекст спрашивает, поэтому условие одной судьбы из §2.5 по-прежнему выполняется. Меняется требование к выводу: даже контексты с идентичным будущим должны сосуществовать, потому что соответствуют разным строкам результата. Поэтому планировщик отключает абсорбцию контекстов всегда, когда действует AFTER MATCH SKIP TO NEXT ROW, независимо от предложения DEFINE.

Сопоставление §2.6 и §2.7 даёт полную картину того, когда абсорбция терпит неудачу:

Любого из этих условий достаточно, чтобы отключить абсорбцию для затронутых контекстов. Когда не действует ни одно — стандартный AFTER MATCH SKIP PAST LAST ROW с условиями DEFINE, использующими только PREV, NEXT или простой LAST — runtime сворачивается до одного контекста на позицию шаблона и остаётся линейным до конца.

§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, а опции EXCLUDE запрещены. Это проверки соответствия, а не оптимизации — понятие рамки в RPR — это диапазон совпадения, и стандарт не предполагает заполнения его чем-либо, кроме совпавших строк.

Когда рамка прошла валидацию, parser превращает предложение PATTERN в дерево, построенное из четырёх видов узлов — ссылки на переменную, последовательности (конкатенации), альтернации и группы (подшаблона в скобках). Каждый узел несёт квантор в виде трёх чисел — нижней границы, верхней границы (возможно, бесконечной) и флага нежадного сопоставления:

Каждый предикат DEFINE затем проверяется по типам по столбцам секции и приводится к логическому выражению. Здесь происходят две практически важные вещи. Во-первых, каждый столбец, на который ссылается предикат DEFINE, регистрируется как часть требований к выводу запроса, поэтому planner протаскивает эти столбцы до стадии 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 должен перечислять. Оптимизатор применяет восемь правил перезаписи последовательно, пока AST не перестаёт меняться:

Сплющивание 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+)+ → A+), внешний точный ((A{2,3}){5} → A{10,15}) или потомок тривиальный {1,1} ((A){2,5} → A{2,5}). Иные комбинации могут внести пробелы, которые плоская форма не отразит — например, (A{2}){2,3} принимает только {4, 6}, а наивный A{4,6} принял бы и 5, — поэтому оптимизатор оставляет их нетронутыми.

Форма элемента

Каждый элемент плоского массива представляет одну позицию в шаблоне. Существует пять логических видов: ссылка на переменную (единственный вид, потребляющий строку); маркеры начала группы и конца группы, открывающие и закрывающие подшаблон в скобках; маркер альтернации, возглавляющий список ветвей; и маркер завершения в конце шаблона.

Каждый элемент также несёт глубину (уровень вложенности групп), квантор (минимальное и максимальное число повторений, возможно бесконечное) и два указателя перехода — next, «куда идти после потребления этого элемента», и jump, «куда перепрыгнуть» (используется альтернацией для соединения ветвей, началом группы для обхода тела, когда квантор допускает ноль, и концом группы для возврата к телу).

Для PATTERN ((A B)+) скомпилированный массив выглядит так:

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (открывает группу; jump перескакивает
     к FIN, когда min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (закрывает группу; jump зацикливается)

[4] FIN    шаблон завершён

Шаблон читается слева направо через next, а jump обрабатывает нелинейные рёбра. На индексе 3 jump у END указывает обратно на индекс 1 — так зацикливается неограниченный внешний квантор; на индексе 0 jump у BEGIN перепрыгнул бы через END к индексу 4, если группа была бы необязательной. Runtime не строит граф во время выполнения — он просто следует этим двум указателям, обходя массив.

Атрибуты элементов

Помимо формы, каждый элемент несёт четыре логических атрибута, направляющих поведение runtime в этой позиции:

Reluctant

Меняет порядок раскрытия квантора. Жадные кванторы пробуют «зациклиться снова» прежде «выйти»; нежадные сначала пробуют «выйти». Несётся переменной для A+?; несётся BEGIN и END группы для ((…)+?).

Empty-loopable

Устанавливается на концах групп, тело которых обнуляемо ((A?)*, (A? B?)+, (A | B*)). Указывает runtime добавить быстрый выход рядом с обычным возвратом, чтобы защита от циклов не убивала легитимные совпадения в группах, способных давать пустые итерации.

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
  пройти AST и пометить
  элементы, удовлетворяющие
  структурному случаю

Первые три проверки уровня запроса: они в точности соответствуют условиям §2.7 (сторона вывода: режим SKIP), ограниченной рамке (граница нарушает монотонность) и §2.6 (сторона данных: FIRST или LAST со смещением в DEFINE). При сбое любой из них анализ не ставит ни одного флага, и абсорбция отключается на уровне всего запроса. Когда все они проходят, обход AST допускает три структурные формы:

Случай 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 — Группа, тело которой начинается с неограниченной переменной

(A+ B)+

Ведущая неограниченная переменная сама абсорбируема (Случай 1) и защищает более ранние контексты. Абсорбция прекращается, как только состояние проходит мимо A — у остальной части тела нет гарантии монотонности, поэтому флаги ставятся только на A.

Структурные случаи, не охваченные этими тремя формами, не менее поучительны. A B+ не может быть абсорбирован текущим правилом, потому что ведущий A потребляет строку до начала неограниченной части, и контексты, начавшиеся с интервалом в одну строку, находятся на разных позициях внутри неограниченного тела. (Расширение «PREFIX absorption», обрабатывающее префиксы фиксированной длины через теневой путь, спроектировано и запланировано в отдельный патч.) Нежадные кванторы вроде 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
    в current_row_slot
  result = eval_inner_expression()
  восстановить current_row_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 lastMatchedRow − n

  # составное: match-rel, затем шаг
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  проверить на соответствующем диапазоне
  (диапазон совпадения для внутренних FIRST/LAST,
   диапазон секции для внешнего шага)

Кэш позиций позволяет обойти выборку из tuplestore, когда несколько навигационных вызовов в одном DEFINE нацелены на одну и ту же строку — обычное явление в выражениях вида price > PREV(price) AND volume > PREV(volume), где оба вызова приводят к предыдущей строке. Кэш хранит только «последнюю извлечённую позицию», а сам обмен остаётся одной операцией.

Классификация навигационных вызовов — вклад planner в решение об абсорбции. Planner обходит каждое выражение DEFINE и сортирует каждую переменную в одну из двух корзин, исходя из того, будут ли все контексты вычислять одно и то же логическое значение на одной строке или каждый контекст — своё собственное. Корзина определяет во время выполнения две вещи: как часто вычисляется переменная (один раз совместно или по разу на каждый затронутый контекст — §3.5 Фаза 1) и пригодно ли окружающее состояние к абсорбции контекста (§2.5 vs §2.6).

Классификация выполняется во время планирования и хранится рядом с каждой переменной DEFINE, поэтому runtime не тратит времени на принятие решения — он просто читает корзину каждой переменной при обработке строки.

Бюджет хранения

Навигация дотягивается до строк, мимо которых машина оконных функций уже прошла. Чтобы эти строки оставались доступны, executor построен поверх tuplestore, удерживающего скользящее окно недавних строк; вопрос в том, насколько широким должно быть это окно. Патч решает это во время компиляции, исходя из двух дополняющих смещений:

Бюджет lookback

Насколько далеко назад от текущей строки может дотянуться любой вызов DEFINE.

Источники: PREV, LAST со смещением, PREV(LAST(...)), NEXT(LAST(...))

Бюджет lookahead-from-start

Насколько далеко вперёд (или назад при отрицательном значении) от начала совпадения старейшего живого контекста может дотянуться любой вызов DEFINE.

Источники: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Во время выполнения метка отсечения tuplestore устанавливается в более раннюю из двух позиций — текущая строка минус бюджет lookback и начало совпадения старейшего живого контекста плюс бюджет lookahead. Всё, что перед этой меткой, не может быть достигнуто никаким навигационным вызовом ни в одном живом контексте, и tuplestore волен это отбросить. Два счётчика Nav Mark, выводимые EXPLAIN (§3.7) — Lookback и Lookahead — являются измеренными пиками двух бюджетов, наибольшей глубиной, на которую executor дотягивался в каждом направлении за всё время запроса.

3.4 Границы совпадения — SKIP, INITIAL и ограниченная рамка

Успешное совпадение записывается как небольшой набор значений: флаг валидности, флаг успеха/неудачи, строка, на которой совпадение начинается, и число потреблённых им строк. При установленном флаге валидности последующие запросы к executor — «находится ли эта строка внутри совпадения?» — могут отвечать за O(1) проверкой набора. Длина ноль — это реальный исход, а не ошибка: она представляет шаблон, совпавший без потребления строк, что 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 вызывается окружающей машиной оконных функций всякий раз, когда ей нужно узнать, относится ли данная строка к совпавшей рамке. Драйвер находит или создаёт контекст для текущей стартовой позиции, один раз вычисляет каждый предикат DEFINE относительно текущей строки, формируя массив логических значений на переменную, затем продвигает NFA на одну строку вперёд. Сам шаг вперёд — три фазы в фиксированном порядке — 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)

Порядок — не стилистический выбор. 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]
      если elem не переменная:
          continue   # advance с этим разбирается

      если не 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 при удалении неабсорбируемого состояния). Оба флага проверяются за константное время ещё до начала сканирования покрытия, поэтому абсорбция несёт полную стоимость только на контекстах, имеющих реальный шанс быть поглощёнными.

Фаза 3 — Advance

Advance — фаза «расхождения»: каждое выжившее состояние раскрывается через эпсилон-переходы, пока каждая ветвь не достигнет либо переменной, ожидающей следующую строку, либо страницы FIN. Раскрытие — в глубину, и порядок обхода соседних ветвей — то, что заставляет правило предпочтения стандарта реально работать: лексикографически первая ветвь всегда добавляется первой, а шаг дедупликации при вставке состояния молча отбрасывает эквивалентные более поздние добавления.

advance(context, currentPos):
  извлечь все текущие состояния;
  перестроить ctx.states с нуля
  для каждого состояния в лексическом порядке:
      очистить bitmap посещённых элементов
      advance_state(state)   # DFS

      # Преферменция: как только DFS
      # достигает FIN, оставшиеся состояния
      # менее предпочтительны и могут быть
      # отброшены.
      если FIN достигнут и состояния остались:
          освободить остальные
          break

advance_state(state):
  идти по state.elemIdx,
  рекурсивно проходить через:
    ветви ALT (по порядку),
    BEGIN (войти в группу; плюс опциональный
           путь пропуска если min = 0),
    END (loop back / exit / fast-forward —
         см. ниже),
    FIN (записать matchEndRow,
         сохранить matchedState и срезать
         последующие контексты внутри
         диапазона кандидата — см. ниже),
  останавливаясь на каждой встреченной переменной:
      добавить состояние в ctx.states
      (дедуплицируя по elemIdx + counts)

Запись состояния, достигшего FIN, делает больше, чем просто отмечает кандидатное совпадение. При AFTER MATCH SKIP PAST LAST ROW следующее сообщаемое совпадение должно начинаться строго после текущего — поэтому в момент записи кандидата каждый последующий контекст, чья стартовая строка попадает внутрь диапазона кандидата, сразу отсекается, даже если контекст, достигший FIN, может продолжать поиск более длинного совпадения через жадный откат.

Отсечение безопасно, потому что независимо от того, как завершится этот поиск (более длинное совпадение заменит кандидата или кандидат останется), все отсечённые контексты начались внутри диапазона, который следующее сообщаемое совпадение должно пропустить, и поэтому никогда не смогли бы дать собственного вывода.

Это один из двух шагов отсечения времени FIN — другой, описанный ранее в этом разделе как часть Advance, отбрасывает лексикографически уступающие состояния внутри того же контекста.

Самая хитрая поэлементная логика — в обработчике END. Когда счётчик итераций группы ниже нижней границы, runtime должен зациклиться обратно; когда он на верхней границе или выше, должен выйти; между ними оба варианта валидны, и жадность квантора решает, что пробовать первым:

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

  если count < elem.min:
      зациклиться обратно в тело
      если elem — empty-loopable:
          # обнуляемое тело, см. §3.2
          также клонировать fast-forward-
          состояние, выходящее из группы
          с удовлетворённым count
          (спасает легитимные совпадения,
           которые иначе убил бы
           cycle guard)

  иначе если count >= elem.max:
      сбросить counts на этой глубине
      выйти через next
      (END→END: инкрементировать count
       внешнего END)

  иначе:
      # min <= count < max: ветвление
      построить состояние выхода
      (counts на этой глубине сброшены)
      если greedy:
          сначала loop, затем exit
          # предпочтение длиннее
      иначе (reluctant):
          сначала exit
          если exit достиг FIN:
              отбросить loop
              # предпочтение короче
          иначе loop вторым

Каждое состояние, добавляемое в контекст, проходит проверку дедупликации, сравнивающую его позицию и счётчики с существующим списком состояний. Поскольку Advance обрабатывает ветви в порядке DFS, состояние из первой ветви любой альтернации попадает первым — и любая более поздняя ветвь с такой же позицией и счётчиками отклоняется при вставке. Это именно то, что требует правило лексикографического порядка из §2.4, реализованное на нижнем уровне runtime без отдельного прохода.

Empty-loopable группы

Тонкий случай, который runtime должен обезвредить, — обнуляемая группа: группа, чьё тело может совпасть с нулём строк, потому что каждый потомок тела сам необязателен. Шаблоны вроде (A?)*, (A? B?)+ и (A | B*) обладают этим свойством: в зависимости от данных тело может завершить итерацию, не потребив ни одной строки. В принципе это нормально, но создаёт реальную опасность для эпсилон-раскрытия NFA. Если тело даёт пустое совпадение, элемент END возвращается к BEGIN, тело снова даёт пустое совпадение, BEGIN ведёт к END, и так далее. Без чего-либо, останавливающего это, DFS Advance никогда бы не завершилась.

Runtime останавливает это битмапом посещённых элементов (один бит на элемент шаблона), очищаемым перед DFS-раскрытием каждого состояния: как только любой элемент посещён второй раз в рамках одного раскрытия, этот путь оставляется. Защита от циклов безусловна и дёшева, но имеет побочный эффект — она также может оставить пути, которые должны достичь нижней границы через легитимные пустые итерации. Возьмём (A?){2,3} без единого совпадения A в потоке строк:

желаемое поведение:
  iter 1: A? совпадает с нулём строк
          → END, count = 1 (ниже min)
  iter 2: A? совпадает с нулём строк
          → END, count = 2 (достигает min)
  выйти с совпадением нулевой длины

что делает cycle guard сам по себе:
  iter 1: A? пропущен → END, count = 1
          → зациклиться обратно к BEGIN
  iter 2: BEGIN уже посещён
          → DFS прерывается
  count никогда не достигает min
  → совпадение проваливается (неверно)

Решение принимается во время компиляции и исполняется во время выполнения. Когда planner видит группу с обнуляемым телом, он помечает её элемент END как empty-loopable. Во время выполнения, когда обработчик END собирается зациклиться обратно, потому что счётчик итераций ещё ниже нижней границы, тег пустого цикла указывает ему клонировать дополнительное fast-forward-состояние рядом с обычным путём возврата:

advance_end (count ниже min):

  основной путь:
    зациклиться обратно в тело
    (оставляет дверь открытой для
     реального, непустого совпадения
     в следующей итерации)

  если elem — empty-loopable:
    fast-forward-путь:
      сбросить count этой глубины
      выйти из группы через next,
      трактуя оставшиеся требуемые
      итерации как пустые совпадения

Два пути играют дополняющие роли. Основной возврат ловит случай, когда тело ещё имеет реальные совпадения позже — например, в (A?){2,3}, за которым следуют данные, где A совпадает только на более поздних строках, возврат позволяет второй и третьей итерациям найти непустые совпадения. Fast-forward ловит случай, когда тело никогда ничего не производит: он обходит защиту от циклов, выходя из группы целиком, заявляя «оставшиеся требуемые итерации пусты», и позволяет совпадению удасться с телом нулевой длины. Оба состояния добавляются в контекст; то, которое успешно расширится, и побеждает, а проверка дедупликации при вставке не позволяет ни одному из путей породить больше состояний, чем положено.

Помимо защиты от циклов, ещё один стартовый приём устраняет неоднозначность исходов нулевой длины в самом начале контекста. Шаг создания контекста на каждой потенциальной стартовой строке выполняет начальный 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 — по лексикографическому порядку все оставшиеся менее предпочтительны и могут быть немедленно отброшены.

Отсечение кандидатных совпадений (между контекстами) On FIN

Другие контексты, чья стартовая строка попадает в диапазон кандидатного совпадения — контекст, достигший FIN, может продолжать поиск более длинного совпадения (жадный откат), но при AFTER MATCH SKIP PAST LAST ROW любой контекст внутри диапазона кандидата уже не сможет дать сообщаемый вывод независимо от того, как закончится поиск, и сразу отсекается.

Защита от циклов Advance

Эпсилон-раскрытия, повторно посещающие тот же элемент шаблона в рамках одного DFS — иначе зацикливались бы навечно в обнуляемых группах.

Empty-loop fast-forward Advance

Легитимные совпадения с пустыми итерациями, которые защита от циклов убила бы в обнуляемых группах — обходит цикл, выходя из группы с оставшимися требуемыми итерациями, объявленными пустыми.

Отсечение по ограниченной рамке Match

Контексты, чьё совпадение достигло заданной пользователем верхней границы рамки — принудительно несовпадают, чтобы не выходить за неё (§3.4).

Чтение записей по их фазовой метке прослеживает жизненный цикл контекста: отсечение срабатывает на каждой строке через три основные фазы (Match, Absorb, Advance) и снова при завершении совпадения (On FIN). Чтение описаний, наоборот, группирует правила по их целям: мёртвые ветви, избыточные контексты, эквивалентные состояния, бесконечные циклы и расширение за пользовательские границы.

Ни одного правила в одиночку не было бы достаточно. Защита от циклов сама по себе убила бы легитимные совпадения в обнуляемых группах; fast-forward пустого цикла сам по себе не остановил бы бесконечные эпсилон-циклы; одна абсорбция переконсолидировала бы при ссылке DEFINE на начало совпадения; одна дедупликация не убрала бы избыточные контексты, только избыточные состояния. Runtime остаётся линейным в значимых случаях — PATTERN (A+ B+ C+ D) на 100 000 строк, бенчмарк панели ③ постера — только потому, что каждый слой ловит то, что упускают слои над ним.

3.7 Вывод EXPLAIN

EXPLAIN ANALYZE на запросе с RPR показывает статистику уровня NFA, которой нет у обычных оконных функций. Рядом с оконным оператором выводятся три группы счётчиков:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (only when the query uses FIRST,
   PREV(FIRST(...)), or NEXT(FIRST(...)))

Peak и total — прямые приборы runtime: сколько состояний когда-либо были живы одновременно, сколько было создано за время жизни запроса и сколько было слито дедупликацией. Гистограммы длин совпадений разделяют четыре исхода — успешные совпадения, неудачные попытки, поглощённые контексты и контексты, отсечённые (пропущенные) без оценки — и выдача их с min/max/avg делает патологии производительности видимыми с первого взгляда: здоровый прогон показывает большинство контекстов либо как совпавшие, либо как поглощённые, с малыми длинами несовпадений.

Два счётчика Nav Mark сообщают бюджет хранения tuplestore, который §3.3 выводит во время компиляции. Lookback — самый глубокий охват назад через PREV, LAST со смещением и составные формы с внутренним LAST; Lookahead — самый глубокий охват вперёд (или назад при отрицательном значении) от начала совпадения старейшего живого контекста, вносимый FIRST и составными формами с внутренним FIRST.

Каждый счётчик печатается как фиксированное целое, когда смещение константное, «runtime», когда смещение — неконстантное выражение, вычисляемое при каждом вызове, и «retain all», когда runtime требуется неограниченный бюджет. Lookahead выводится только когда запрос реально использует навигацию относительно начала совпадения.

Вместе эти счётчики позволяют отлаживать производительность RPR без подключения gdb к backend.

Помимо счётчиков, EXPLAIN также точно воспроизводит исходные предложения PATTERN и DEFINE, включая нежадные кванторы, повторение групп и опцию AFTER MATCH SKIP. Реализация прилагает усилия для стабильности этого циклического преобразования, чтобы pg_dump и pg_upgrade могли сохранять объекты RPR без семантического дрейфа — регрессионный набор rpr_explain проверяет это случай за случаем (см. §4).

§4. Тесты — карта покрытия

Патч сопровождается пятью регрессионными наборами, которые вместе покрывают каждый слой, описанный в §3 — около 13 000 строк SQL, каждый набор сосредоточен на отдельной задаче. Разделение намеренное: хранение задач parser, корректности runtime, взаимодействий с planner и форматирования вывода в отдельных файлах облегчает локализацию ошибок и предотвращает случайную инвалидизацию тестов одного слоя несвязанным изменением в другом. Пять наборов:

rpr

Сквозная семантика запросов — реалистичные оконные сценарии на синтетических данных по акциям (V-форма, W-форма, последовательные подъёмы, развороты).

rpr_base

Слой parser — приём ключевых слов, синтаксические формы, кванторы, разбор навигации, сообщения об ошибках и стабильность циклического преобразования pg_dump/pg_upgrade.

rpr_nfa

Runtime NFA — трёхфазный цикл, абсорбция во всех абсорбируемых формах и краевые случаи жизненного цикла контекстов.

rpr_explain

Форматирование вывода — статистика NFA, деппарс шаблона, экранирование идентификаторов, стабильность формата при перезагрузке.

rpr_integration

Взаимодействия с planner — защиты, не позволяющие посторонним оконным оптимизациям повреждать семантику RPR.

4.1 rpr — сквозные сценарии

Набор сценариев — публичное лицо тестового комплекта: используется синтетический набор данных по ценам акций из примерно 1600 строк, и запускаются реалистичные запросы — восстановление V-формы, W-форма (двойное дно), последовательные подъёмы и спады, шаблоны разворота, многосимвольные секции. Это единственный набор, где входы и выходы читаются как запросы, которые пользователь действительно мог бы написать; остальные намеренно редуктивны и сосредоточены на одном слое за раз.

Поскольку эти запросы соединяют каждый слой (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 отклоняется с полезной ошибкой, а каждая принятая форма переживает сериализационное циклическое преобразование. Основная его масса — небольшие сфокусированные сниппеты, по одному на синтаксическую возможность, а не длинные реалистичные запросы, поскольку цель — покрытие, а не реалистичность сценариев.

Тесты сериализации заслуживают особого внимания. Объекты RPR (представления, материализованные представления, вывод pg_dump) должны проходить циклическое преобразование через каталожное представление без семантического дрейфа, включая такие тонкости, как нежадный флаг на кванторе или точная форма выражения составной навигации. Небольшой набор сериализационно-специфичных объектов (представления rpr_serial_v* и их подстилающие таблицы) намеренно оставляется на месте в конце прогона, чтобы окружающая регрессионная инфраструктура могла их подхватить и прогнать против них pg_dump и pg_upgrade. Остальные тестовые «леса» сбрасываются как обычно. Ошибки, ловящиеся таким способом (например, потеря нежадного флага между деппарсом и повторным разбором), проявляются только при сквозной проверке циклического преобразования.

4.3 rpr_nfa — движок выполнения

Это набор, тестирующий каждый механизм, описанный в §3.5 и §3.6. Его тесты следуют согласованному шаблону: входная таблица, чьи строки — явные булевы массивы, объявляющие, какие переменные 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 — часть пользовательского контракта; сторонние инструменты (автодополнение psql, мониторинговые дашборды, парсеры журналов) разбирают его, и изменения, кажущиеся косметическими, могут их сломать. Набор rpr_explain проверяет три вещи:

• Счётчики NFA появляются в правильном месте — статистика на каждый WindowAgg (peak/total/merged states, peak/total/pruned contexts, гистограммы длин для matched/mismatched/absorbed/skipped, Nav Mark Lookback и — при использовании навигации относительно начала совпадения — Nav Mark Lookahead) — всё это появляется в EXPLAIN ANALYZE с документированными метками.
• Шаблоны корректно деппарсятся — каждая форма квантора, включая нежадные варианты и ограниченные формы; каждая альтернация; каждая группа; каждая форма 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 для монотонных агрегатов. Рамка RPR — диапазон совпадения, а не агрегационное окно, и должна оставаться дословно.

Проталкивание run-condition

Монотонный фильтр WHERE на выходе оконной функции обычно может быть протолкнут в оконный оператор как условие остановки. Для RPR это преждевременно прервало бы сопоставление шаблона, возможно отрезая совпадения в середине расширения.

Дедупликация окон (RPR vs не-RPR)

Два окна с идентичными ORDER BY и рамкой обычно сливаются в одно. Окно RPR и не-RPR никогда не могут разделять состояние, потому что сторона RPR несёт результаты совпадений.

Дедупликация окон (разные DEFINE)

Два окна RPR с одинаковым PATTERN, но разными DEFINE, дают разные совпадения и должны оставаться различными, даже если их структурная форма идентична.

Проекция неиспользуемого вывода

Даже если окружающий запрос никогда не читает построчный вывод окна, окно RPR нельзя удалить: побочные эффекты сопоставителя (какие строки внутри какого совпадения) питают вычисления сжатой рамки в других местах плана.

Инверсные переходы скользящих агрегатов

Оконные агрегаты с инверсной переходной функцией обычно могут вычисляться инкрементно по мере движения рамки. Сжатая рамка RPR — не скользящее окно; путь инверсного перехода дал бы неверные результаты.

Шаблон этих тестов один и тот же: каждый предоставляет не-RPR базис, запускающий оптимизацию (и проверяет, что EXPLAIN показывает её применение), затем выполняет запрос RPR структурно похожей формы и проверяет, что оптимизация не применяется. Обе половины вместе доказывают, что защита в planner делает реальную работу, а не одобряет каждый запрос без реальной проверки.

Этот набор — также причина того, что §3.4 короток. Механизмы «границ совпадения» — сжатая рамка, SKIP, INITIAL, отсечение по ограниченной рамке — операционно тестируются в других местах; что rpr_integration проверяет — это что никакая другая стадия оптимизатора не вмешивается в них на пути. Прошедший rpr_integration — то, что позволяет остальным наборам доверять, что их входы достигают executor нетронутыми.