Bitmap predicate index¶

Architecture

Deep $and/$or trees over low-selectivity predicates make the scan executor read many rows to keep few. This page documents the roaring-bitmap accelerator that narrows candidates before the scan-equivalent validation step runs, and the temporal discipline (F10) that keeps it a pure candidate-generation optimization, never a correctness path.

Overview & purpose¶

The spec's problem statement (§2) is precise about the risk class this subsystem exists to avoid: bitmaps answer "which rows match predicate P," not "which rows matched P at time T," and a naive bitmap index would silently break temporal queries. The design responds with one governing rule, F10: bits only ever accrete (a set bit means "some version of this row ever matched," a temporally-safe superset), and every bitmap-produced candidate is re-validated through the exact same bitemporal winner-rule and filter logic the scan path uses. A bitmap can therefore only narrow the set of rows the executor has to read; it can never change which rows are returned.

Three design decisions fall out of that governing rule:

• Bits are never cleared. Clearing a bit on version closure would reintroduce "the exact backward-history deletion bug class of F3" (spec §9, Alternatives Considered): a query pinned to an old tx_time could then miss a row a stale bitmap had already forgotten. Accretion-only avoids that class of bug entirely, at the cost of postings that only grow.
• Any non-indexable leaf anywhere falls the whole query back to scan. There is no partial/hybrid execution: bitmap_source returns None (not a partial bitmap result) the moment any predicate in the tree cannot be expressed as posting-list algebra, and the executor's execute() simply tries scan_and_filter next.
• Validation is identical code to the scan path, not a lighter-weight check. bitmap_source calls self.reads.get_as_of(...), the label check, and eval_filter(...) exactly as scan_and_filter does; the only thing the bitmap path changes is which logical ids get validated.

Design¶

Row-id allocation and posting maintenance¶

Per (tenant, label), a monotonic u32 row-id allocator assigns dense ids to node logical ids as they are first observed under that label. Per (tenant, label, property, value-bucket), a roaring bitmap posting list tracks which row ids have ever had a version matching that bucket. BitmapMaintenance builds the write ops for one version:

pub struct BitmapMaintenance {
    engine: Arc<dyn StorageEngine>,
    max_values_per_property: u32,
}

impl BitmapMaintenance {
    pub fn ops_for_version(
        &self,
        scope: &TenantScope,
        labels: &[String],
        logical_id: Uuid,
        properties: &BTreeMap<String, Value>,
    ) -> Result<Vec<WriteOp>, BitmapError>;
}

For each label on the version, it resolves (or allocates) the row id, then for each property computes the buckets that property's value contributes to (buckets_of, an equality bucket plus a range band) and sets the corresponding bits. NodeOps holds an Option<BitmapMaintenance> (None when bitmap.enabled is off) and folds bitmap_ops(...) into the same WriteOp batch as the node version write, the schema-inference puts, and the adjacency rows, so a single batch_write call commits all of it atomically. Edge properties are out of scope for v1: spec OQ-1 records the stance "nodes-only until node-side wins are proven."

Write-path allocation is idempotent¶

row_id_or_allocate checks the reverse map (logicalId -> rowId) first; on a hit it returns the existing row id with no new ops. A re-observation of an identical property value likewise produces no new posting op, because RoaringBitmap::insert returns false for an already-set bit and the maintenance code only emits a Put when insert returns true. This is covered directly by maintenance_allocates_and_sets_bits_then_checker_passes, which asserts a repeat call with identical data returns an empty op list.

Query-side: planner then cost rule then validation¶

flowchart LR
    F["Filter tree (validated Query AST)"] --> P["bitmap_planner::candidates"]
    P -->|"any leaf unindexable"| SCAN["scan_and_filter\n(baseline path)"]
    P -->|"RoaringBitmap"| COST{"watermark==0 OR\ncandidates >= watermark*ratio?"}
    COST -->|yes| SCAN
    COST -->|no| RESOLVE["logical_ids(candidates)\n(id_map point lookups)"]
    RESOLVE --> VALIDATE["get_as_of winner rule\n+ label check\n+ eval_filter"]
    VALIDATE --> WINNERS["sorted winners\n(valid desc, tx desc, id asc)"]

QueryExecutor::execute always tries bitmap_source first; a None result (disabled, no filter, unindexable leaf, or the cost rule rejecting it) falls through to scan_and_filter. Both paths converge on the same sort order and the same cursor format, so pagination and the "byte-identical to scan" differential gate (spec §10) hold regardless of which path served a page.

Data model¶

The 13th column family¶

bitmap_index is the 13th RocksDB column family (see Storage engine & key layout for the full CF table). It was added after the composite-key-layout spec's original "12 CFs" count and is fully keyed through the shared KeyCodec/TenantScope discipline, with a kind byte discriminating five row shapes:

common prefix: [ scope 32 ][ label_hash 8 ][ kind 1 ]

kind = 0x00 ALLOC          [ ...prefix... ]                              total: 41 bytes
kind = 0x01 ID_MAP         [ ...prefix... ][ row_id 4 ]                  total: 45 bytes
kind = 0x02 REV_MAP        [ ...prefix... ][ logical_id 16 ]             total: 57 bytes
kind = 0x03 POSTING        [ ...prefix... ][ property_hash 8 ][ bucket_hash 8 ]  total: 57 bytes
kind = 0x04 PROP_COUNTER   [ ...prefix... ][ property_hash 8 ]           total: 49 bytes

These lengths are read directly from core-engine/src/storage/keys.rs (key_len::BITMAP_ALLOC = 41, BITMAP_ID_MAP = 45, BITMAP_REV_MAP = 57, BITMAP_POSTING = 57, BITMAP_PROP_COUNTER = 49) and the bitmap_kind module's byte constants.

Row semantics¶

• alloc: the row-id watermark for one (tenant, label), a big-endian u32. The value stored is the next id to allocate; BitmapReader::watermark reads it directly as the planner's scan-size estimate.
• id_map: row_id -> logical_id (16-byte UUID value), keyed by the 4-byte big-endian row_id.
• rev_map: logical_id -> row_id (4-byte big-endian value), the inverse map; the write path's idempotency check reads this first.
• posting: a serialized RoaringBitmap of row ids for one (property_hash, bucket_hash) pair, where bucket_hash is either an equality bucket (eq_bucket) or a range-band bucket (band_bucket).
• prop_counter: a big-endian u32 distinct-value counter for one property, or the sentinel OVERFLOW_MARKER = u32::MAX once the property's distinct-eq-value count reaches max_values_per_property.

Value buckets¶

Two independent bucket families exist per property, and a value can contribute to both simultaneously:

fn buckets_of(value: &Value) -> impl Iterator<Item = u64> {
    eq_bucket(value).into_iter().chain(band_of(value).map(band_bucket))
}

Equality buckets (eq_bucket) canonicalize the value before hashing: Bool, Str, Int, Float, and Datetime each get a type-tagged byte prefix (b:, s:, i:, f:, d:) so distinct types never collide, and integral floats canonicalize onto the Int encoding (Value::Int(5) and Value::Float(5.0) hash to the same bucket), matching the executor's Int/Float coercion. Null, Bytes, Array, and Object are not eq-indexable (eq_bucket returns None); non-finite floats (NaN, infinities) are also excluded.

Range bands (band_of) apply only to Int, Float, and Datetime. Every numeric value routes through f64, whose bit pattern is transformed into an order-preserving u64 (sign-bit flip for positives, full bit flip for negatives, the standard total-order trick), and the top 4 bits of that transformed value select one of 16 static bands (RANGE_BANDS: u8 = 16):

pub fn band_of(value: &Value) -> Option<u8> {
    let f = match value {
        Value::Int(i) => *i as f64,
        Value::Float(f) if f.is_finite() => *f,
        Value::Datetime(us) => *us as f64,
        _ => return None,
    };
    let bits = f.to_bits();
    let ordered = if f.is_sign_negative() { !bits } else { bits ^ (1 << 63) };
    Some((ordered >> 60) as u8)
}

Because the transform is monotone, band membership is monotone too: a value greater than another never lands in a strictly lower band. This is what lets range queries union a contiguous slice of bands and still guarantee the result is a superset of the true match set.

Encoding¶

Postings are serialized with RoaringBitmap::serialize_into (the pure-Rust roaring crate's own portable format) and stored whole, as a single value per posting row. There is no chunking of large postings across multiple rows.

Algorithms & invariants¶

Write-path maintenance¶

sequenceDiagram
    autonumber
    participant N as NodeOps
    participant M as BitmapMaintenance
    participant E as StorageEngine

    N->>M: ops_for_version(scope, labels, logical_id, properties)
    loop each label
        M->>E: get rev_map(logical_id)
        alt row id already allocated
            E-->>M: row_id
        else first sighting
            M->>E: get alloc watermark
            M->>M: push Put(alloc, watermark+1)
            M->>M: push Put(id_map[watermark] = logical_id)
            M->>M: push Put(rev_map[logical_id] = watermark)
        end
        loop each property
            M->>E: get posting(eq_bucket)
            alt new distinct value and under cap
                M->>M: push Put(prop_counter, count+1)
                M->>M: push Put(posting, {row_id})
            else already counted
                M->>M: insert row_id into existing bitmap, push Put if changed
            else cap reached this write
                M->>M: push Put(prop_counter, OVERFLOW_MARKER)
            else already overflowed
                M->>M: no eq posting op (frozen)
            end
            M->>E: get posting(band_bucket), never capped
            M->>M: insert row_id, push Put if changed
        end
    end
    M-->>N: Vec<WriteOp>
    N->>E: batch_write (same batch as the version write)

Query-side planner: And/Or/In translation¶

bitmap_planner::candidates walks the validated Filter tree and translates it into roaring-bitmap set algebra, returning None the instant any leaf or sub-tree is not indexable:

Cost rule and the correctness backstop¶

let watermark = reader.watermark(scope, &plan.find_label)?;
if watermark == 0 || (candidates.len() as f64) >= f64::from(watermark) * self.candidate_ratio {
    return Ok(None); // fall back to scan
}

watermark is the label's allocated row-id count, used as the scan-size estimate (spec v0.2 changelog, item 3). If the bitmap-derived candidate set is not meaningfully narrower than the full label population (candidate_ratio, default 0.3), scanning is assumed cheaper and the bitmap result is discarded even though it was computed. watermark == 0 (label never allocated, i.e. never seen or bitmaps never populated for it) is treated the same way.

Every surviving candidate is then resolved and re-validated with exactly the scan path's logic:

for id in ids {
    let Some(node) = self.reads.get_as_of(scope, id, valid_t, tx_t)? else {
        continue; // not visible / tombstoned at the coordinate
    };
    if !node.labels.iter().any(|l| l == &plan.find_label) {
        stats.rows_filtered_out += 1;
        continue;
    }
    if !eval_filter(filter, &node, &mut stats.type_mismatches) {
        stats.rows_filtered_out += 1;
        continue;
    }
    winners.push(node);
}

get_as_of applies the same bitemporal winner rule described in The tritemporal model; eval_filter is the identical predicate evaluator the scan path calls. This is the backstop that makes the accretion-only posting design safe: bitmaps can only ever produce a superset of the correct row set, because every survivor is re-checked against ground truth before it becomes a result. Winners are then sorted valid desc, tx desc, id asc, matching the scan path's index byte order, so a page boundary or resumed cursor behaves identically regardless of which path produced it.

Overflow freezes equality postings, not range bands¶

if count == OVERFLOW_MARKER {
    // Property overflowed: eq postings frozen.
} else if count >= self.max_values_per_property {
    // this write pushes it over the cap: mark overflowed
} else {
    // under cap: count and index normally
}

Once a property's distinct-eq-value count reaches max_values_per_property (default 10_000), prop_counter is set to OVERFLOW_MARKER and no further equality postings are written for that property, ever (existing postings are left as-is, but no new distinct value gets its own bucket). property_overflowed lets both the write path and eq_leaf in the planner check this cheaply. Range bands are not subject to any cap: since there are only ever 16 bands per property regardless of cardinality, they keep accreting unconditionally. The test overflow_freezes_eq_postings_but_not_bands verifies this directly: with a cap of 2, five distinct integer writes overflow the eq postings, but the union of all 16 band postings for that property still contains all five row ids.

Rebuild and consistency check¶

rebuild(engine, scope, max_values_per_property) implements the F4 derived-data doctrine: it deletes every existing bitmap_index row for the tenant, then replays every node_versions row through BitmapMaintenance::ops_for_version, batching writes in chunks of 1,000. check(engine, scope) is the read-only consistency checker: for every stored node version it verifies the rev_map/id_map pair is a consistent bijection and that every property's expected bucket bits are set (skipping properties whose prop_counter has overflowed, since those are expected to be incomplete by design). Both are exercised end-to-end by checker_flags_missing_state_and_rebuild_heals_it: a node version written without going through BitmapMaintenance is correctly flagged as inconsistent, and rebuild heals it.

Trace visibility¶

ExecStats (core-engine/src/query/executor.rs) carries path: String ("bitmap" or "scan") and bitmap_candidates: u64 (0 on the scan path), persisted into the traces CF when plan.trace is set. Operators can therefore see, per query, whether the accelerator engaged and how many candidates it produced before validation trimmed them.

Cursor format is unchanged¶

Both paths sign an identical cursor: base64(msgpack{v, scope_hash, plan_hash, last_key} ‖ HMAC-SHA256 tag), built from the valid_time_index key bytes of the last accepted record via sign_cursor. There is no bitmap-specific cursor variant; a cursor produced on a bitmap-served page resumes correctly on a scan-served page and vice versa, because both paths sort winners into the same index byte order before pagination.

Configuration¶

All four keys live under BitmapConfig in core-engine/src/config.rs. The first three (enabled, max_values_per_property, candidate_ratio) are listed in ENV_KEYS and settable via TELHA_BITMAP__ENABLED, TELHA_BITMAP__MAX_VALUES_PER_PROPERTY, and TELHA_BITMAP__CANDIDATE_RATIO respectively; range_bands is deliberately excluded, matching the spec's characterization of it as fixed in v1, not tunable.

As-built notes¶

From the spec's v0.2 changelog (2026-07-03, "implementation notes recorded at PR-022b landing"), reconciled against the code:

• Pure-Rust roaring crate, not croaring. The spec's §4/§5 prose mentions croaring (a C-binding wrapper) as the intersection engine; the as-built code uses the pure-Rust roaring crate instead, per the v0.2 changelog's explicit swap: "identical portable serialization format, no C toolchain dependency; swap is contained to one codec module if profiling ever argues for croaring." core-engine/src/storage/bitmap.rs imports roaring::RoaringBitmap directly.
• No 4MB posting chunking exists. The spec's §5 Data Models line says "posting value = serialized roaring bitmap (chunked at 4MB)." The as-built encode_bitmap/decode_bitmap functions serialize and store a posting as a single whole value with no chunking logic anywhere in core-engine/src/storage/bitmap.rs or its key layout (there is no chunk-index component in the posting key shape). This is a spec-vs-code gap worth flagging for anyone relying on the spec text: very high cardinality postings are not chunked in v1.
• Range bands ship as 16 static order-preserving bands, not lazy quantiles, exactly as the v0.2 changelog records: "quantile refinement remains planned with PR-029 telemetry, same as the activation thresholds." RANGE_BANDS: u8 = 16 and the top-4-bits-of-ordered-f64 transform in band_of match the changelog's description precisely.
• The planner cost rule estimates scan size via the label's row-id watermark, per changelog item 3; confirmed in bitmap_source's direct use of reader.watermark(...) rather than any other cardinality estimate.
• $ne, $exists, and dotted paths are non-indexable, per changelog item 4; confirmed in bitmap_planner.rs's leaf() (PredOp::Ne(_) | PredOp::Exists(_) => Ok(None)) and path.contains('.') guard.
• OQ-1 (edge-property predicates) is unresolved as specified: the spec's stance is "nodes-only until node-side wins are proven," and the code matches, BitmapMaintenance::ops_for_version and the planner both operate purely on node labels and node properties; there is no edge-side posting maintenance anywhere in the codebase.
• The differential gate (spec §10, "bitmap path vs scan path byte-identical on randomized temporal datasets") and the ≥3x p50 improvement success metric (§12) are process/benchmark claims not independently re-verified for this page; the consistency-check and rebuild round-trip tests in bitmap.rs were inspected directly and pass, but the differential-fuzz harness and PR-029 benchmark suite live outside core-engine/src/storage/bitmap.rs and core-engine/src/query/ and were not re-run here.

Related¶

• Storage engine & key layout: the bitmap_index column family in the context of all 13 CFs, and the reserved-scope and prefix-bloom machinery it shares with every other CF.
• Schema inference: another derived index maintained in the same write batch as the triggering version write, with its own churn-avoidance discipline.
• Global temporal scan: the scan baseline the bitmap path must match byte-for-byte on results.
• Concepts › The tritemporal model: the winner rule every bitmap candidate is re-validated against.
• Developers › Query language: the Filter/PredOp AST the planner consumes.