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.

Enums

BitmapLiteral

One signed dimension-key literal in a bitmap term.

BitmapScanError

Terminal signal raised by a bitmap evaluator on the bucket channel’s Err. It must be an error rather than a silent end-of-stream: the driver reads a clean end as “scanned the whole range” and advances the resume cursor to the terminus, so a budget or cancel stop has to short-circuit the try_stream! pipeline to truncate the scan at the current floor. The variant is chosen at the source, so each List handler maps it to a wire outcome with one exhaustive match.

ScanDirection

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.

Functions

buckets_with_watermarks

Convenience adapter: wrap a single raw BucketStream into a WatermarkedBucketStream with one Watermark(post_bucket) after each bucket plus one final at the range terminus on EOF.

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

BitmapScanResult

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