# v0.89.0 — Incremental Window Functions

> **Status:** Implemented. `ROW_NUMBER` runtime admission was rejected by the measured performance gate.
> **Scope:** Large
> **User promise:** *"One PostgreSQL instance can handle a lot."*
> **Blocked by:** [v0.88.0](v0.88.0.md)
> **Split from:** the original v0.84.0 "Fast Incremental Engine".

## Theme

Establish a correct, bounded, crash-safe framework for incremental window
maintenance, then admit only the function and frame combinations that show a
measured benefit over partition recomputation.

This is a release on its own, not a bullet point. Every entry in the table below
is a distinct algorithm with its own auxiliary state, its own persistence and
crash-recovery story, its own migration path for existing stream tables, and its
own DIFFERENTIAL-versus-FULL proof obligation. Bundling it with the vectorized
aggregate path and a delta-query cost model — as the original v0.84.0 did —
produced a release that could not be scoped, reviewed or gated.

The state framework is mandatory. Algorithm breadth is not a v1.0 blocker. Any
shape that does not pass the admission gate keeps the existing, correct
partition-recomputation path with a visible reason code.

## Release result

v0.89.0 ships the typed semantic plan, private LOGGED state machinery,
validation, the bounded-state guard, the versioned cost selector, and
diagnostics. The release evaluated one built-in `ROW_NUMBER` candidate over a
direct keyed scan. The query used exact same-name projections and included the
complete non-null identity in `ORDER BY`.

The candidate filtered changed output rows but still recomputed the affected
partition. It was slower than partition recomputation in all six measured
cells. The recompute-to-state ratio ranged from 0.0446 to 0.4030, so the 20
percent performance gate rejected it.

No window family is runtime-enabled. Every candidate in LT-7c, LT-7d, and
LT-7e uses partition recomputation with an explicit reason. The release
publishes the negative measurements and makes no incremental speedup claim.

## Non-Goals

- No new window functions beyond those PostgreSQL already supports.
- No change to the window semantics users see. Only the maintenance strategy
  changes.
- No removal of the partition-recomputation path — it remains the fallback.
- No requirement that every candidate family become incremental before v1.0.

## Items

### LT-7a: Incremental state model and persistence

Before any individual algorithm, define once:

- where per-partition auxiliary state lives (a side table keyed by stream table
  and partition key, not user-visible columns)
- how it is initialised on first refresh and rebuilt on reinitialisation
- how it survives crash, restore and `ALTER`, and how a mismatch is detected
- how it is bounded, so a query with millions of partitions cannot grow state
  without a ceiling and an alert (bound sourced from
  `pg_trickle.memory_budget_mb`, v0.87.0)

New metadata in `pgt_stream_tables`: `window_strategy JSONB` recording, per
window function, the chosen strategy and its auxiliary state location.

### LT-7b: Algorithm admission gate

A function and frame combination becomes incremental only when it passes all
of these checks:

1. PostgreSQL semantics match exactly, including peers, NULL ordering,
   collations, and frames.
2. DIFFERENTIAL converges with FULL after INSERT, UPDATE, and DELETE histories.
3. The auxiliary state survives restart, backup, restore, rebuild, and upgrade.
4. State growth is bounded under the documented policy.
5. Output amplification and the recomputation crossover are measured.
6. A representative end-to-end workload shows a material speedup without
   exceeding its regression budget.

Failure of any check selects partition recomputation. The support matrix and
diagnostics report the reason.

### LT-7c: Rank-family candidates

| Function | Current strategy | Admission target |
|----------|------------------|------------------|
| `ROW_NUMBER()` | Recompute partition; measured state candidate rejected | Update ordered per-partition state only after a later implementation passes the performance gate |
| `RANK()` / `DENSE_RANK()` | Recompute partition | Update peer-aware rank state when cheaper than recomputation |

Both must handle the case where one inserted row shifts every subsequent row's
output — the delta is not proportional to the input change, and the release must
document where the crossover to partition recomputation lies rather than
pretending it does not exist.

### LT-7d: Offset and boundary candidates

| Function | Current strategy | Admission target |
|----------|------------------|------------------|
| `LAG(col, N)` / `LEAD(col, N)` | Recompute partition | Maintain enough ordered state for bounded offsets |
| `FIRST_VALUE()` / `LAST_VALUE()` | Recompute partition | Maintain exact frame-boundary state |
| `NTH_VALUE()` | Recompute partition | Maintain indexed ordered state for the admitted frame |

These are semantic and performance goals, not commitments to a ring buffer or
another specific data structure. The implementation must handle insertion and
deletion at arbitrary positions before an offset strategy is admitted.

### LT-7e: Aggregate-over-window candidates

| Function | Current strategy | Admission target |
|----------|------------------|------------------|
| `SUM() OVER (...)` | Recompute partition | Maintain bounded algebraic state for admitted frames |
| `COUNT() OVER (...)` | Recompute partition | Maintain bounded algebraic state for admitted frames |

Non-invertible aggregates over windows (`MIN`/`MAX` with deletions) stay on the
recomputation path unless a proof is available, consistent with the fail-closed
rule established in [v0.83.0](v0.83.0.md).

### LT-7f: Fallback, reason codes and the support matrix

Frames that are not covered — `ROWS BETWEEN` / `RANGE BETWEEN` variants outside
the algorithms above, `EXCLUDE` clauses, `GROUPS` mode — fall back to partition
recomputation with a reason code visible in refresh history and `explain()`, and
are listed explicitly in `docs/DVM_SUPPORT_MATRIX.md`. A window function whose
incremental algorithm is unavailable must never silently produce a different
answer from PostgreSQL.

## Exit criteria

- [x] Auxiliary state is bounded and LOGGED, survives SIGKILL recovery, and is
      excluded from logical dumps while durable strategy metadata is retained;
      logical restore remains fail-closed rather than trusting stale OIDs
- [x] Every candidate in LT-7c/d/e either passes the admission gate or has an
      explicit reason for staying on recomputation
- [ ] Property tests compare DIFFERENTIAL with FULL after every INSERT, UPDATE
      and DELETE for each admitted window shape, including peers, NULL ordering,
      collations, and frame boundaries. The rejected candidate has mutation-by-
      mutation convergence coverage, but no window shape is admitted.
- [ ] Measured speed-up published per function family, including the crossover
      point and output amplification where recomputation is still faster
- [x] The v0.89 performance admission gate ran for the narrow `ROW_NUMBER`
      candidate and rejected it in all six cells. The negative medians, ranges,
      WAL, and output-row results are published.
- [x] Unsupported frames fall back with a reason code and appear in
      `docs/DVM_SUPPORT_MATRIX.md`
- [x] Existing window stream tables upgrade without user action, or are flagged
      for reinitialisation with an actionable message. The v0.88-to-v0.89 E2E
      suite preserves the target, lazily records the disabled plan, repairs the
      frontier and CDC metadata, and proves the next differential interval.
