CORE-199 eligible-candidate index rollout

Native PostgreSQL candidate selection (select_candidates, which serves GraphBackedHms.retrieve) reads at most 4,097 rows and refuses above 4,096. Without the optional index idx_nodes_candidate_eligible_c, those rows are every row in the caller's owner paths, whether or not the read could return them. With a valid index of exactly the shipped shape, plus its wide-row companion idx_nodes_candidate_wide, they are only the eligible rows. An empty-cue read can also return its exact ranked page above 4,096 eligible rows. Application startup never creates either index. This page is the operator procedure. It is not a deployment record.

Artifact: scripts/migrations/core199_candidate_eligible_index.sql, which follows the pattern of scripts/migrations/core199_pending_index.sql.

What the index holds

• Predicate: no truthy __symfonic_pending__ or __symfonic_retracted__ marker, and procedural rows only when approved and active.
• Keys: tenant_id and scope_path under "C", layer, an audience (empty for rows every session reads, the SHA-256 of the row's own session_id string for working and session episodic rows, NULL for an unreadable session), the profile-slot flag, the importance rank descending, and id under "C".
• The audience is a fixed 32-byte digest, so a session_id of any length fits a btree tuple; the raw id is never a key. The digest only narrows a seek. Each seek also compares the exact session_id before its LIMIT, so a digest collision can neither return nor count another session's row.
• Size: the key holds tenant_id, scope_path, layer and id whole, and none of them is length-bounded on write. The predicate therefore also requires their bytes to total at most 2,560 (KEY_BYTES). The tuple adds at most 106 bytes to them by derivation (62 measured on PostgreSQL 16), under the 2,704-byte btree limit of 8 KiB pages.

What the companion index holds

• Predicate: the same eligibility, and key bytes over 2,560: exactly the eligible rows the first index leaves out, so each eligible row is in one of the two.
• Keys: a SHA-256 of tenant, scope path and layer (separated by a NUL byte, which text cannot contain) and the same audience, 32 bytes or less each, so any row the table accepts fits.
• Reads seek it once per (path, layer, audience). The digest only narrows the seek: the exact tenant, path, layer, session, eligibility and TTL checks run inside it, before its limit, so a collision neither returns nor counts a foreign row. It has no rank order, so the seek reads every wide row of its combination, up to the budget plus one, and each counts.

Every fragment is generated from src/symfonic/memory/backends/postgres_candidate_predicates.py, the same module that builds the ranked statement. The read recognises the index only when PostgreSQL's own rendering of its definition hashes to ELIGIBLE_INDEX_SHA256, and the companion only when its rendering hashes to WIDE_INDEX_SHA256; it uses neither unless both match. If a later release changes an eligibility fragment or KEY_BYTES, an index built by this script stops matching. Reads then return to the visible-row budget until the new script is run; they never trust the old index.

Mixed fleet

The index is additive. Binaries that predate it do not reference it, and PostgreSQL maintains both on their writes as well. A row too wide for the eligible key goes to the companion, whose key is fixed-width, so the pair adds no write-time size limit on any column and no existing row blocks a build. A binary that knows the index uses it only when it is valid and has the pinned shape, and otherwise keeps the visible-row budget. Neither rollout order changes a result or opens a scan; only the budget's counting differs. An index built by an earlier revision of this script (the raw-session key, or the digest key without the size predicate) does not match the pinned shape: reads ignore it, the script refuses it, and the operator drops it as under Failure and rollback before rerunning.

Pre-validation

1. Confirm the target schema, PostgreSQL 16 (the pinned rendering), 8 KiB pages (SHOW block_size is 8192; the key bound is derived for them), and that the role owns memory_nodes and holds CREATE on the schema and TEMP on the database. On any other major version or page size the script refuses before the build and creates nothing.
2. Look for existing indexes with either name: SELECT indexrelid::regclass, indisvalid, pg_get_indexdef(indexrelid) FROM pg_index WHERE indexrelid IN (to_regclass('<schema>.idx_nodes_candidate_eligible_c'), to_regclass('<schema>.idx_nodes_candidate_wide')); If one exists and is invalid or has a different shape, stop. The script refuses it too and never drops it. Optionally count the rows the companion will hold: SELECT count(*) FROM <schema>.memory_nodes WHERE octet_length(tenant_id)+octet_length(COALESCE(scope_path,''))+octet_length(layer)+octet_length(id) > 2560; Each such row is read and counted by every recall of its owner path, layer and audience, so many of them at one path move those reads toward the budget refusal.
3. Look for long transactions. CREATE INDEX CONCURRENTLY waits for every snapshot older than the build.
4. Check that there is disk headroom. On a disposable PostgreSQL 16 the index took about 157 bytes per indexed row (71 MB beside a 107 MB heap of 453,000 short rows) and built in 1.1 s without CONCURRENTLY. Its size grows with path length and with the number of eligible rows. The companion holds only wide rows: about 104 bytes each when every row has its own owner, and about 9 when 20,000 rows share 20 owners and deduplicate (disposable PostgreSQL 16, 2,600-byte ids). Every insert and update of memory_nodes also maintains both.

Run

psql "$POSTGRES_DSN" -X -v scope_schema=public -f scripts/migrations/core199_candidate_eligible_index.sql

Do not pass -1 or wrap the script in a transaction: CONCURRENTLY refuses to run inside one. ON_ERROR_STOP is set. The script verifies both indexes before and after the builds. Running it again is a no-op that keeps the same indexes.

Post-validation

• The script exits 0.
• A native recall that exceeds the budget now refuses with more than 4096 eligible rows rather than more than 4096 visible rows.
• After ANALYZE memory_nodes, an auto_explain plan of a candidate read shows only Index Scan using idx_nodes_candidate_eligible_c on memory_nodes, with the scope path, layer and audience in the index condition and no rows removed by filter, and Index Scan using idx_nodes_candidate_wide with the owner digest and audience in the index condition. The read disables sequential and bitmap scans for itself only. That steers the planner; it does not forbid other plans.

Failure and rollback

• If a build is interrupted, PostgreSQL can leave an invalid index under its name. If a build completes but the final verifier rejects its shape, a valid index remains that every write maintains and no read uses. In both cases reads keep the visible-row budget and the script refuses to continue (operator recovery required, naming the index); it never drops an index itself. Investigate, run the DROP INDEX CONCURRENTLY it names, and re-run the script. If only one of the two was built, reads keep the visible-row budget until a rerun builds the other.
• To roll back, run DROP INDEX CONCURRENTLY on <schema>.idx_nodes_candidate_eligible_c and <schema>.idx_nodes_candidate_wide. Dropping either one already returns reads to the visible-row budget. No row data changes during rollout or rollback.

Limits

• A cue-bearing read over 4,096 eligible rows still refuses. Token hits do not order with any index here; postings (E1) and truncated pages (T) are separate decisions.
• An empty-cue read uses up to limit + 1 rows per seek, one seek per (path, layer, audience, profile), and every row it reads counts. When (limit + 1) times the populated seeks exceeds 4,096 (for example about 41 populated seeks at limit 100) it refuses even though an exact top-k exists. It never truncates; the certified tests cover limit up to 16.
• Wide rows (key bytes over 2,560) have no rank order in their index, so every read of their owner path, layer and audience reads all of them, up to 4,097, with or without a cue, and each counts. They are always ranked exactly; enough of them at one path makes those reads refuse, never truncate. Normal rows keep the ordered, bounded seek.
• Scopes deeper than 23 levels keep the counting budget for empty cues as well, because the ancestor decay is no longer an exact power of two there.
• TTL-expired working rows and dead index entries are read and skipped without counting. The 1 s native read deadline bounds that residual; no live test yet loads a mass of expired rows at the caller's own path.
• A session with standard_conforming_strings=off sees both definitions rendered differently, so its reads do not recognise the indexes and keep the visible-row budget. Results stay exact.
• Certification is PostgreSQL 16 with 8 KiB pages only. The script refuses any other major or page size, and each native read checks both before it trusts the pair, so a pair carried to another major by pg_upgrade stays valid but unused: reads keep the visible-row budget.
• Public admission and defaults are unchanged.