Skip to content

statement-store: evaluate index-backed subscription replay instead of full admission-log scan #12745

Description

@DenzelPenzel

Context

Follow-up to #12697 (see review discussion and the approval comment).

#12697 replays dynamically attached subscription filters from a persisted admission cursor: replay_batch iterates the ADMISSION_SEQ column from the cursor up to the registration watermark, point-reads and decodes every admitted statement, and matches it against the filter. The existing on-disk indexes (INDEX_BY_TOPIC, INDEX_BY_DEC_KEY) are not used on this path.

Problem

Replay cost is proportional to store size, not filter selectivity. From the benchmarks in the PR thread (store at max capacity, 4,194,304 statements / ~1.66 GiB of bodies, ~525k distinct topics):

Scenario Time to ReplayDone
Narrow filter, 8 matches out of 4.2M 2.5–2.9 s
Any (full-store delivery, 4.19M statements in 415 chunks) 2.7–2.9 s

A filter matching 8 statements pays the same full-scan cost (~0.7 µs per scanned statement: point-get + decode + match) as delivering the entire store. The scan is bounded-memory and doesn't block submit, but for selective filters nearly all of that work is wasted.

Proposal

Evaluate whether selective filters can replay through INDEX_BY_TOPIC / INDEX_BY_DEC_KEY instead of scanning the full admission log, making replay cost O(matches) rather than O(store size).

Open questions to resolve:

  1. Ordering and cursor semantics. Index enumeration yields hashes in no particular order, while ADMISSION_SEQ provides a stable, totally ordered, resumable cursor. Options: sort candidate hashes by admission_seq (cheap for narrow filters, unbounded for broad ones), or relax the replay ordering guarantee for the index path.
  2. Exactly-once replay/live handoff. The watermark split (replay < watermark <= live) must be preserved regardless of which path enumerates candidates.
  3. Path selection heuristic. Any and broad topic prefixes still require the scan path; an index path only pays off for selective filters. Needs a selectivity estimate (or a cheap index-cardinality probe) to choose between paths. Multi-topic filters additionally require index intersection.
  4. Is it worth it at all? In Statement store index optimization, stage 2a #12304 a disk-index-based snapshot scan measured ~2.0 s at the same capacity (Statement store index optimization, stage 2a #12304 (comment)), so the index path is not automatically cheaper — the decision should be made on benchmark numbers, e.g. by extending benches/add_filter.rs across a selectivity sweep.

Metadata

Metadata

Assignees

Labels

I5-enhancementAn additional feature request.T0-nodeThis PR/Issue is related to the topic “node”.

Type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions