Module bitmap_query 

DNF bitmap index queries over ordered bucket streams.

Callers build a BitmapQuery as an OR of terms. Each term is an AND of signed dimension-key literals. Evaluation yields matching bitmap members as they are produced. Back-pressure from downstream consumers, e.g. a .take(page_size), propagates back to the backend-provided bucket streams and avoids materializing matches we won’t use.

Queries are intentionally restricted to anchored DNF: every term must contain at least one positive literal. Positive literals give the evaluator concrete bitmap streams to scan and intersect; negative literals only shrink those candidate streams. Negative-only terms such as NOT sender = A are supported by anchoring them upstream on a universe include — a stored existence marker in event-space (EventExtant), a scan-time-synthesized dense leaf in tx-space (TxUniverse, see dense_universe_buckets) — so the evaluator itself stays a set of ordered stream merge-joins with no complement-specific code path. The full-range scan such a term implies is inherent to negation and is bounded by the per-request bucket budget.

Backends provide one ordered (bucket_id, RoaringBitmap) stream or iterator per dimension key. The merge-join machinery here is storage-agnostic: BigTable, RocksDB, or any other backend can reuse it as long as its bucket source is sparse, ordered by the requested scan direction, and stores bitmap positions relative to that bucket.

Structs

BitmapKey

Validated [dimension_tag][dimension_value] lookup key.

BitmapQuery

A DNF query over bitmap dimension scans.

BitmapScanMetrics

Per-request bucket-scan accounting, delivered via the on_metrics callback passed to eval_bitmap_query_stream. Fires once when the eval pipeline is dropped (natural end, error, or consumer cancel). The sole exception is the budget-misconfig early-out, which errors before any scan is set up and emits nothing.

BitmapTerm

One conjunction in a DNF bitmap query.

DenseUniverseBuckets

Synthesized dense-universe bucket iterator.

SkipPolicy

Physical gap-crossing policy. Logical frontier jumps are unconditional; this only bounds how many charged dead rows a lagging leaf drains from its open scan per lag episode before seeking past the gap.

Enums

BitmapLiteral

One signed dimension-key literal in a bitmap term.

LeafStop

Terminal raised by a single leaf/backend bucket stream. Positionless by construction — one leaf cannot know the merged multi-term floor. Leaf stops never reach a List driver: the DNF evaluators consume them and re-raise a ScanStop carrying the merged frontier.

ScanDirection

ScanStop

Terminal signal of a merged bitmap eval stream, raised on the error channel so the try_stream! pipeline short-circuits (a clean end-of-stream means “scanned the whole range”). The List handlers map each variant to a wire outcome with one exhaustive match.

Watermarked

Item or progress watermark flowing through a bitmap eval pipeline. Watermark(p) means every Item with position strictly before p in scan direction has been emitted upstream. Downstream stages must preserve watermark/item ordering — that’s what makes the watermark a safe resume cursor on timeout.

Traits

BitmapBucketIteratorSource

Storage backend that can scan one bitmap dimension key synchronously.

BitmapBucketSource

Storage backend that can scan one bitmap dimension key over a member range.

SeekableBucketIterator

Synchronous bucket iterator that can reposition within its scan bounds.

Functions

dense_universe_buckets

Synthesized bucket sequence for the dense tx-seq universe: one full bitmap per bucket touched by range, in scan-direction order. Backends return this for the query-only IndexDimension::TxUniverse key instead of reading storage — the tx-seq namespace is dense, so the universe is computable.

eval_bitmap_query_bucket_iter

Evaluate a DNF BitmapQuery as an ordered iterator of marked bucket bitmaps. Output emits Watermarked::Item((bucket_id, bitmap)) interleaved with Watermarked::Watermark(p) derived from the slowest leaf’s progress.

eval_bitmap_query_stream

Evaluate a DNF BitmapQuery against a backend-provided bitmap source.

flatten_watermarked_buckets

Flatten marked bucket bitmaps into absolute member ids with edge-bucket trimming against range. Watermarks pass through unchanged.

Type Aliases

BucketItem

A stream of (bucket_id, RoaringBitmap) in the requested bucket order. Bitmap positions are relative to the bucket (u32 offsets [0, BUCKET_SIZE))

BucketStream

WatermarkedBucketStream