Spec: Roaring Bitmap Predicate Acceleration (PR-022b)¶

File: .ai/specs/core-engine/2026-07-02-bitmap-predicate-index.md Status: Draft — design settled now; activation and tuning await PR-029 benchmark evidence (deliberately sequenced post-baseline per ratified F10) Owners: Storage lane Related: PR-022b; F10 amended resolution; query-language spec (predicates), global-temporal-scan spec (validation doctrine), F4 (derived-data doctrine)

1. Overview¶

Defines the bitmap accelerator: dense row-id allocation, posting-list maintenance, planner integration, and the temporal post-validation rule that keeps bitmaps a pure candidate-generation optimization — never a correctness path.

2. Problem Statement¶

Deep $and/$or trees over low-selectivity predicates make the scan executor read many rows to keep few. Set intersection is the right primitive — but bitmaps answer "which rows match P," not "which rows matched P at time T," and a naive bitmap index silently breaks temporal queries (the F10 correction). The design must make temporal wrongness inexpressible.

3. Proposed Solution¶

Per (tenant, label): a monotonic u32 row-id allocator over node logicalIds (persisted watermark + id↔logicalId mapping rows). Per (tenant, label, property, value-bucket): a roaring posting list in a bitmap_index CF, maintained in the same WriteBatch as node writes — a version write sets the bit for its (property, bucket) memberships; bits are never cleared (a set bit means "some version ever matched," the temporally-safe superset). Query path: planner resolves eligible predicates to posting lists, intersects/unions via croaring, maps surviving ids → logicalIds → standard bitemporal selection + end-boundary validation per candidate — identical validation to the scan path, so the bitmap path can only ever return a subset-of-equal results, never extras. Value-buckets: equality buckets for Str/Bool/Int exact values (hashed, capped cardinality per property with overflow-to-scan fallback), range buckets (16 quantile bands, maintained lazily) for Int/Float/Datetime range predicates — bands widen candidates, validation tightens.

4. Architecture¶

write path → bitmap maintenance hook (same batch) · query planner → cost rule: use bitmaps iff (all top-level conjuncts indexed) ∧ (estimated candidates < scan_rows × 0.3, from PR-029-informed telemetry) → candidates → validate → pipeline continues unchanged.

5. Data Models¶

bitmap_index keys: [scope][labelHash 8][kind 1: alloc|map|posting][…]; posting value = serialized roaring bitmap (chunked at 4MB). Allocator watermark and id-map rows under kind bytes. All derived: telha index rebuild-bitmaps regenerates everything from version CFs (F4 doctrine).

6. API Contracts¶

None public — planner-internal. Trace output gains path: bitmap|scan and candidate/validated counts so operators see the accelerator working (or not).

7. UI/UX¶

None beyond trace visibility and the rebuild subcommand.

8. Configuration¶

bitmap.enabled (default off until activation criteria met), bitmap.max_values_per_property (10k, overflow → property unindexed), bitmap.candidate_ratio (0.3), bitmap.range_bands (16).

9. Alternatives Considered¶

Temporal bitmaps (bit per version, or per-time-slice bitmap sets — rejected: cardinality explosion; the ever-matched superset + validation achieves correctness at a fraction of the state). Clearing bits on version closure (rejected: reintroduces the exact backward-history deletion bug class of F3; bits only accrete). Inline in PR-022 (rejected per amended F10: the scan baseline must exist and be benchmarked first). External search engine (Tantivy et al — rejected: dependency weight and a second consistency domain for what intersection + validation solves in-store).

10. Implementation Approach¶

PR-022b commits as planned: this spec → allocator + CF → maintenance hooks → planner cost rule + croaring intersections → consistency checker + rebuild → differential gate: bitmap path vs scan path byte-identical on randomized temporal datasets (non-negotiable) → bench extension proving wins on deep-predicate suites without regressing point/traversal gates.

11. Migration Path¶

Enabling on an existing dataset = run rebuild (backfills postings from version CFs), then flip bitmap.enabled. Disabling is instant (planner ignores; state harmless). Nothing else in the system knows bitmaps exist.

12. Success Metrics¶

Differential test green (the gate). Deep-AND/OR suite: ≥3× p50 improvement at the activation selectivity profile (threshold refined from PR-029 data — recorded here on amendment). Zero regression on point/traversal benchmarks. Rebuild-equivalence green.

13. Open Questions¶

OQ-1: Edge-property predicates — extend bitmaps to edges v1 or nodes-only? Stance: nodes-only until node-side wins are proven; edge predicates are rarer in the fixture corpus.

14. Changelog¶

2026-07-03 — v0.2: implementation notes recorded at PR-022b landing. (1) Roaring library: pure-Rust roaring crate instead of croaring-rs — identical portable serialization format, no C toolchain dependency; swap is contained to one codec module if profiling ever argues for croaring. (2) Range buckets v1 ship as 16 static order-preserving bands over the f64 order-space (all numeric types route through f64, whose rounding is monotone, preserving the candidate-superset property) rather than lazy quantiles — quantile refinement remains planned with PR-029 telemetry, same as the activation thresholds. (3) Planner cost rule v1 estimates scan size via the label's row-id watermark. (4) $ne is explicitly non-indexable (complement over accreting bitmaps is unsound), as are $exists and dotted paths. Differential gate green on randomized temporal datasets incl. corrections and tombstones.
2026-07-02 — v0.1: design draft; activation criteria and tuning thresholds await PR-029 benchmark data (amendment expected).