# v0.89.0 — Incremental Window Functions

> **Status:** Planned
> **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.

## 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 | Update ordered per-partition state when cheaper than recomputation |
| `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

- [ ] Auxiliary state model shipped, bounded, crash-tested and covered by the
      backup/restore suite
- [ ] 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
- [ ] Measured speed-up published per function family, including the crossover
      point and output amplification where recomputation is still faster
- [ ] Unsupported frames fall back with a reason code and appear in
      `docs/DVM_SUPPORT_MATRIX.md`
- [ ] Existing window stream tables upgrade without user action, or are flagged
      for reinitialisation with an actionable message