Skip to content

docs(storage): the count's cap costs a decode per key past it, not per repeated key #1081

Closed

Description

@chappie-daemon

The count's decision record states its cost wrongly, in four places, and the code comments copy it. The code is correct; the prose is not, and it is wrong in the direction a reader would trust.

What it says

docs/rewrite/decisions/0011-lmdb-backend.md:206-208:

The price of the cap is a body decode per repeated key past it; an index order that visits each row once is what would remove that too.

And again at :201-203, :257-259, :359-361, in crates/nostream-storage/src/lmdb/events.rs:840-843, :659-660, :3119-3120, and in the shortcut: marker at events.rs:840.

What the code does

counted_earlier (events.rs:918-920) reads the body for every key past the cap unless the range is the family's first exact criterion — a later criterion's key decodes even when the row has only one key in the walk, and a #g prefix's key decodes to ask whether a smaller matching value already answered. It is not confined to repeated keys.

Measured by the round-15 review on one 20,000-row corpus, release build:

shape capped uncapped ratio
{"#t":["a","b"]}, 2 keys a row 63,278 µs 12,003 µs 5.3×
{"#t":["zz","a"]}, 1 key a row, zero repeats 55,706 µs 9,851 µs 5.7×

Decodes past the cap: 5,000 at 10k rows, 15,000 at 20k, at ~3.1 µs and 18 allocations each. The ["zz","a"] shape has no repeated key at all, which is the clean refutation of "per repeated key".

The second false claim is at :200: "Below the cap the walk reads no body" — contradicted by :251-253 and events.rs:1482-1485; a second tag family decodes below the cap.

What is right, and should not be changed

  • The set is bounded: 5,000 ids, HashSet capacity 7,168, 270,352 B, constant at 5k / 10k / 20k rows, against 1,081,360 B at 20k unbounded.
  • The count is exact at every corpus size and on every shape the round-15 reviews could build (five committed shapes plus five more, three inversions), so the fallback must stay.
  • The cap is free below 5,000 rows: nine counters identical across 96 comparisons.

The fix

Two sentences, in the record and its copies:

  • Replace "The price of the cap is a body decode per repeated key past it" with: "Past the cap every key the set does not answer reads the row's body — a later criterion's key to ask whether an earlier criterion matched the row, a #g prefix's key to ask whether a smaller value did — not only a repeated one. The walk costs 5.3× to 5.7× its uncapped time at 20,000 rows for that reason."
  • Qualify :200 so it does not claim the walk is decode-free below the cap: it is decode-free for a single-tag-family filter, and a second family decodes there too (:251-253).

Then the same wording at every copy listed above, which is a comment edit and no behaviour change.

Source: factory job 024-lmdb-store, round 15 — round-15/review-code.md Finding 1, round-15/review-architecture.md Findings 1-2, round-15/review-performance.md Finding 1. Merged as-is at the operator's direction.

Activity

  1. added a commit that references this issue on Nov 16, 2026
    cc4685e
  2. chappie-daemon commented on Nov 16, 2026

    @chappie-daemon
    CollaboratorAuthor

    Fixed by #1137, merged at cc4685e.

    Every copy the issue listed is corrected, and the sweep for "repeated key" across 0011-lmdb-backend.md and lmdb/events.rs at the merge finds none left. The boundary the new wording names is the code's own early return in counted_earlier — if earlier.is_empty() && prefix.is_none() { return Ok(false) } — so "every key the set does not answer, outside the family's first exact criterion" is exact rather than approximate.

    The claim is also now pinned by a test rather than only by prose: a_count_past_its_id_cap_totals_what_the_unbounded_walk_totals asserts, on its {"#t":["zz","a"]} case, that the capped and uncapped totals agree, that the capped walk decoded a body, and that the uncapped walk decoded none — the zero-repeat shape the issue was filed about, as an assertion. It passes at the merged head.

    One caveat worth recording: the 5.3× / 5.7× ratios are the round-15 table in this issue, measured on one 20,000-row corpus in a release build, and there is no committed benchmark that reproduces them. They are reported as measured, which is what the record should say, but a reader should not take them as a constant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

No labels
No labels

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions