# 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

Replace partition-based recomputation for window functions with genuinely
incremental algorithms.

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.

## Non-Goals

- No new window functions beyond those PostgreSQL already supports.
- No change to the window semantics users see; only to how they are maintained.
- No removal of the partition-recomputation path — it remains the fallback.

## 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: Rank-family algorithms

| Function | Current Strategy | New Strategy |
|----------|-----------------|--------------|
| `ROW_NUMBER()` | Recompute partition | Maintain sorted index; insert/delete at position |
| `RANK()` / `DENSE_RANK()` | Recompute partition | Track rank counts per distinct value; adjust on delta |

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-7c: Offset and boundary algorithms

| Function | Current Strategy | New Strategy |
|----------|-----------------|--------------|
| `LAG(col, N)` / `LEAD(col, N)` | Recompute partition | Ring buffer of N preceding/following values per partition |
| `FIRST_VALUE()` / `LAST_VALUE()` | Recompute partition | Track min/max by sort key |
| `NTH_VALUE()` | Recompute partition | Indexed array per partition |

### LT-7d: Aggregate-over-window algorithms

| Function | Current Strategy | New Strategy |
|----------|-----------------|--------------|
| `SUM() OVER (...)` | Recompute partition | Running sum with prefix-sum tree for range frames |
| `COUNT() OVER (...)` | Recompute partition | Running count (algebraic) |

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-7e: 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 function in LT-7b/c/d has an incremental algorithm, or an explicit
      documented reason it stays on recomputation
- [ ] Property tests compare DIFFERENTIAL with FULL after every INSERT, UPDATE
      and DELETE for each supported window shape
- [ ] Measured speed-up published per function family, including the crossover
      point 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