Skip to content

CORE-199 scan bound contract

This page states what the native PostgreSQL subtree reads and subtree forget guarantee, and the conditions an operator must keep for the physical part of that guarantee to hold. The owner accepted it as option A on 2026-10-14 (Plane CORE-199). It is a contract, not a deployment record.

Scope

The bounded selectors are the three statements that enumerate one owner range of a v1 scope:

  • query_subtree's owner-path read (canonical_node_paths);
  • query_subtree's candidate read (the candidate_rows CTE);
  • subtree forget's per-table read (memory_nodes, memory_edges, memory_workset_progress).

v0 scopes and other backends are outside this contract.

What holds unconditionally

  • D1, rows. Each selector returns at most 1,025 rows of its range and refuses at 1,025 with MemoryContractError. Dead index entries it walks past are not rows and are not counted here; D4 covers them. It never truncates: nothing is returned or deleted. Expired Working rows count toward the budget.
  • D2, time. Each read, all phases together, is bounded by 1 s with server-side cancellation (statement_timeout) and refuses at the limit.
  • D3, plan shape. In custom and generic plans alike, each selector is one ordered Index (Only) Scan of its C range index with the owner range in the Index Cond: no sequential scan, bitmap scan or sort under the LIMIT.
  • D6, forget lock. Subtree forget holds EXCLUSIVE on memory_nodes, memory_edges and memory_workset_progress for at most its 1 s deadline. A commit still unacknowledged at the deadline gets 0.25 s more, then the connection is terminated and the outcome reported as indeterminate. Native writers of every tenant wait on that lock for that time.

What holds only under the preconditions

D4, buffers. Each selector statement visits at most 2 x (1,024 + 1) + 64 = 2,114 shared buffers (hit plus read) while both of these hold on the scanned owner range:

  • P1. At most one index entry per live row points at a row version the read cannot use: a deleted or updated version that VACUUM has not yet removed, or one that an older snapshot keeps it from removing.
  • P2. Since the index was built or last reindexed, at most two row versions per live row were deleted. VACUUM removes their index entries but not the leaf pages they thinned out, so only REINDEX is certain to reset this count.

D5, outside them. No physical bound is claimed. D1, D2 and D3 still hold, so the result is a refusal at the time limit, never a truncated result. Measured: one more churned version per live row than P2 allows already exceeds 2,114, and ten retained versions per live row read 11,388 buffers for a 1,024-row answer.

Snapshot age is not the variable. A snapshot opened after the deletes costs nothing; one opened before them costs one heap page per version it retains, however young it is.

Keeping the preconditions

These are operator practices. They make P1 and P2 likely; they do not prove them.

  • Bound how long a snapshot can live in every role that reaches the database: idle_in_transaction_session_timeout and a server-side statement_timeout. Abandoned prepared transactions (pg_prepared_xacts) and standbys with hot_standby_feedback also hold the horizon back.
  • Keep autovacuum enabled and aggressive enough on the memory_* tables for their write rate.
  • Reindex the C range indexes (REINDEX INDEX CONCURRENTLY) after bulk deletes or rewrites of an owner range: idx_nodes_scope_path_c, idx_edges_scope_path_c and the memory_workset_progress primary key. Where the chunked content erase script ran, also its keyset indexes idx_nodes_erase_keyset_c and idx_edges_erase_keyset_c. A completed chunked forget is itself such a bulk delete: until VACUUM and the reindex run, reads over that range may sit outside P1 and P2.

Evidence

  • tests/memory/integration/test_core199_d4_buffer_contract_live.py: every selector in both plan modes, P1 and P2 each at its limit and together, one owner per live row and one heap page per version (the worst case); plus the D5 cell one step past P2.
  • tests/memory/integration/test_core199_postgres_mvcc_scan_live.py: the retained-version and churn measurements outside the preconditions.
  • tests/memory/integration/test_core199_selector_index_plans_live.py: D3.