Spec 0011 — Scalar Indexing (Native Structured-Metadata Filters)

Status: Normative (v0.2). dreamdb.bitmap-categorical preserves the v0.1 equality format. dreamdb.btree-int64, dreamdb.btree-float64, and dreamdb.btree-string are pinned and implemented across create/append/layer, query, compaction, merge, and GC. ScalarIndex and B-tree page bytes are vector-gated under dreamdb-conformance/vectors/0011/; the public Dataset query suite verifies that a narrow ordered predicate prunes immutable pages rather than scanning every distinct value. Depends on: spec/0001, spec/0002, spec/0004, spec/0007. Motivation: design/0001-dataset-platform.md — ML training pipelines need to filter samples by structured metadata (WHERE label='cat') alongside vector similarity and time range. DreamDB v0 has the latter two; scalar filtering is the missing piece. This spec defines the modality that closes the gap.

1. Purpose

The vector- and time-filter paths in v0 (spec/0004 + time-bucket addresses) both rely on a content-addressed index that lives alongside the bucket data: vector queries hit a SpatialIndex Object (LSH/IVF/IMI centroids); time queries descend the Track's paged time-bucket index.

For structured fields (label = 'cat', region IN ('us', 'eu'), confidence > 0.9, etc.) DreamDB uses ScalarIndex Objects and ScalarBucket Tracks. The original bitmap representation answers equality efficiently but implements ordered predicates by scanning every distinct-value entry. This revision pins the value-keyed tree used by new ordered fields so a selective range reads O(log N + matches) index entries rather than the whole distinct-value set.

2. Scope

In scope:

• A new family of algorithm IDs under dreamdb.btree-* and dreamdb.bitmap-*.
• A new InlineObjectIndex::ScalarBucket variant for Track Objects of scalar modalities.
• A value-keyed page tree whose leaves retain the established ScalarBucketEntry data references.
• Multi-version semantics: how the index handles overwrites in an append-only timeline.
• Sizing guidance (when to pick bitmap vs B-tree, how to scale across N).

Out of scope (deferred to future revisions):

• Full-text / token indexes. Covered by 0015's auxiliary TextIndex binding, not 0012 (federation). A lexical index is not itself a data Track.
• Compound indexes ((field_a, field_b) jointly indexed). Single-field for v0; compound is a future addition.
• User-defined comparators for string ordering. We use byte-lexical order; locale-aware collation is application-level.

3. Algorithm registry additions

Extends spec/0004 §3.4. New built-in algorithms:

Same identifier grammar and registry contract as spec/0004 §3.4. Per-modality registry entries point at the ScalarIndex Object's hash, mirroring the SpatialIndex Object pattern.

4. The ScalarIndex Object

Symmetric with spec/0004 §3's SpatialIndex Object. Carries algorithm parameters; content-addressed; immutable.

4.1 CBOR encoding

{
  "algorithm":  "<id>",          ;; one of the IDs in §3
  "field_name": "<text>",        ;; logical field name (Schema-level)
  "metric":     "<id>",          ;; "ordinal" for B-tree, "categorical" for bitmap
  "params":     <sub-object>,    ;; algorithm-specific (often empty)
}

field_name is not strictly needed for index lookup (the modality string carries the discriminator), but is useful for human readability and for cross-referencing the Dataset's Schema. Address: scalar-index/<multihash-of-canonical-CBOR-bytes>.

4.2 Params

dreamdb.btree-*

{
  "version": 1,
  "leaf_fanout":     <uint>,    ;; entries per leaf page (default 4096)
  "internal_fanout": <uint>,    ;; children per internal page (default 256)
}

The B-tree is realized as immutable Scalar B-tree pages at <timeline>/<modality>/index/<page-hash>. leaf_fanout and internal_fanout MUST each be at least 2. They are count caps; the 65,536-byte encoded-page cap in §4.3 is an additional first-to-fire bound.

dreamdb.bitmap-*

{
  "version": 1,
  "cardinality_limit": <uint>,  ;; max distinct values; default 65536
}

The v0.1 format retains ScalarBucketEntry values inline in the Track Object and stores a tagged RoaringTreemap anchor set in each addressed ScalarBucket payload (or packed range). Readers also accept the older canonical-CBOR anchor-array payload. This revision does not reinterpret either encoding.

4.3 Scalar B-tree page bytes

Every page is a canonical-CBOR CLOSED map with exactly four keys:

{
  "type":      "leaf" / "internal",
  "algorithm": "dreamdb.btree-int64" / "dreamdb.btree-float64" / "dreamdb.btree-string",
  "level":     <uint>,
  "entries":   <array>,
}

Pages MUST be non-empty and their complete canonical encoding MUST be at most 65,536 bytes. A leaf has level = 0; an internal page has level > 0. Every child of an internal page at level L MUST decode as a page at level L - 1 with the same algorithm.

A leaf row is the existing ScalarBucket tuple, unchanged:

[value_cbor_bstr, t_start, t_end, bucket_address]
[value_cbor_bstr, t_start, t_end, bucket_address, pack_offset, byte_size]

The 4- and 6-element forms retain spec/0002 §6.5.4 semantics. Rows sort by normalized key, then by the literal value bytes, t_start, t_end, address bytes, pack_offset, and byte_size. An internal row is:

[key_min_bstr, key_max_bstr, child_address]

Bounds are inclusive. Rows sort by (key_min, key_max, child_address-bytes). Numeric normalized keys are exactly 8 bytes. String normalized keys are at most 8,192 bytes; this guarantees that a conforming internal page can branch under the page-byte cap.

value_cbor_bstr contains one scalar value in RFC 8949 preferred serialization. It is an opaque byte string to the outer DreamDB Object encoder: a finite CBOR float is allowed inside this bstr even though spec/0002 §3.1.5 forbids a CBOR float as a field of the hash-bearing page map itself. Readers MUST reject malformed, trailing, or non-preferred inner encodings.

Normalized keys are byte-comparable:

• btree-int64: interpret the canonical-CBOR value as an i64, XOR its two's-complement u64 representation with 0x8000000000000000, encode big-endian. Timestamp uses the same rule.
• btree-float64: reject non-finite values; canonicalize both zero signs to +0; for a negative IEEE-754 bit pattern use bitwise NOT, otherwise XOR the sign bit; encode big-endian.
• btree-string: decode a CBOR text string and use its UTF-8 bytes unchanged. Ordering is byte-lexical, not locale collation.

The Track root summary and every page are content-addressed. Readers MUST verify the fetched page bytes against the address, algorithm, level, count caps, ordering, and local bounds before using it. A full traversal additionally MUST match the root summary's page_count and total_entries.

5. Track-side layout

A bitmap scalar Track retains InlineObjectIndex::ScalarBucket(_). An ordered Track is empty in that same inline form until its first value is written; after that its Object Index is the CLOSED map:

{
  "form":          "scalar-btree-v1",
  "root":          <page multihash bstr>,
  "page_count":    <uint>,
  "total_entries": <uint>,
  "tree_height":   <uint>,
}

All four counts MUST be non-zero. This form is distinct from the time-keyed form: "paged"; keys from the two forms MUST NOT be mixed. The root's level MUST equal tree_height - 1.

Leaf rows continue to contain the established entry shape:

pub enum InlineObjectIndex {
    Fragment(Vec<FragmentEntry>),
    SpatialBucket(Vec<SpatialBucketEntry>),
    TimeBatch(Vec<TimeBatchEntry>),
    ScalarBucket(Vec<ScalarBucketEntry>),  // NEW
}

pub struct ScalarBucketEntry {
    /// The field value (CBOR-encoded so heterogeneous concrete types
    /// share one entry shape).
    pub value: Vec<u8>, // canonical CBOR for the declared scalar type
    /// Inclusive time-anchor range covered by this bucket.
    pub t_start: u64,
    pub t_end: u64,
    /// The bucket's content hash.
    pub bucket_address: Multihash,
}

The addressed bucket bytes remain the existing tagged Roaring anchor set (with the legacy canonical-CBOR array accepted on read). Packed leaves retain their (pack_offset, byte_size) range. A B-tree changes only how readers locate matching ScalarBucket entries; it does not change bucket payload bytes.

6. Query semantics

The Dataset layer exposes the query primitive used by the planner:

pub async fn query_scalar(
    &self,
    field: &str,
    op: ScalarOp,
    value: &ScalarValue,
) -> Result<Vec<u64>, DatasetError>;

ScalarPredicate mirrors the Filter::Where/ScalarOp from dreamdb-dataset:

• Eq(v) / Neq(v) — single-value lookup (B-tree: point search; bitmap: load bitmap for value).
• Lt(v) / Lte(v) / Gt(v) / Gte(v) — B-tree range scan; bitmap: legacy distinct-value scan.
• In([v1, v2, ...]) — bitmap: union of per-value bitmaps; B-tree: O(k log N).

t_start/t_end is intersected with the returned anchors at the bucket-entry level (time bounds on each ScalarBucketEntry let us skip whole buckets that fall outside the window).

The Dataset-layer planner uses this to evaluate Filter::Where clauses, then intersects with the vector/time results. Or/Not compose these per-anchor (e.g. In is Or of Eq).

For a B-tree predicate, a reader normalizes the target once, follows only child ranges that can satisfy the predicate, filters matching leaf rows, then reads their anchor buckets. Neq may visit every leaf. Eq and one-sided ranges prune subtrees by their inclusive bounds. A bitmap ScalarIndex continues to use the v0.1 inline scan and byte-equality behavior; ordered comparison is not retrofitted onto it.

7. Multi-version and migration semantics

Existing dreamdb.bitmap-categorical ScalarIndex and inline Track objects remain byte-for-byte valid and MUST NOT be reinterpreted as B-trees. Readers select behavior from the bound ScalarIndex algorithm and Track form, and MUST reject a non-empty inline Track paired with a B-tree or a scalar B-tree paired with a bitmap index.

New Int, Timestamp, Float, and String Schema fields use the corresponding built-in B-tree. Bool and Categorical fields retain bitmap-categorical. Appending to an existing field preserves its bound algorithm. There is no implicit in-place migration, and this revision does not provide an in-place migration command. A future or dedicated rebuild that changes a legacy ordered field from bitmap to B-tree MUST publish a new ScalarIndex binding and its matching Track atomically. Until such a rebuild exists and is requested, legacy data remains readable through the scan path. Compaction and merge rebuild the selected representation but never change the algorithm on their own.

DreamDB Tracks are append-only. If an application models a scalar-field update, it writes the new value at a fresh time anchor; both anchors remain independently queryable in every Manifest whose active Track contains them. The scalar API has no implicit “latest value per logical sample” reduction and no include_overwritten mode.

Manifest history selects the active Track version as specified by spec/0008. Within that Track, Dataset::query_scalar and Dataset::query_scalar_in return the sorted, deduplicated union of matching anchors after removing the effective tombstone set defined by spec/0020. A B-tree rebuild, compaction, or merge MUST preserve that result.

8. Sizing guidance

ImageNet-100's label (100 distinct values) and split (2 values) both fit the bitmap path cleanly. A future "ResearchDataset" with 10K-class taxonomy would still fit (bitmap-categorical cardinality_limit = 65536 covers it). Anything denser uses B-tree.

The cardinality limit on dreamdb.bitmap-categorical is intentional: above ~64K distinct values, bitmaps stop being more efficient than B-tree leaves. The decoder rejects an index that exceeds the limit; the producer must re-train as B-tree.

9. Implementation status

Mirrors the IVF rollout shape from spec/0004 §5.6:

Steps 1-7 are implemented in the reference implementation. The first non-empty B-tree for a Track is built from all of its leaf entries. An append to an existing non-empty B-tree MUST instead path-copy the affected leaf and its ancestors; untouched page addresses remain in the new tree. Independently published layers, merge, and compaction use the full builder deliberately and are the rebalancing boundary.

For an incremental append, the writer normalizes and orders new rows by the complete leaf tuple in §4.3. At an internal page it selects the rightmost child whose key_min is not greater than the new key, or the first child when the key precedes the tree. The affected leaf is re-sorted by the complete leaf tuple. An overflowing leaf or internal page is divided, in canonical order, into the fewest maximal pages allowed by the declared fanout and page-byte cap. Child ties retain the §4.3 (key_min, key_max, child_address-bytes) order. A root split creates the minimum required parent levels. Incremental append does not merge underfull pages; full rebuild may rebalance them.

Every fetched path page MUST be verified against its address, algorithm, expected level, ordering, fanout, byte cap, and its parent's declared bounds before it contributes to a replacement. total_entries, page_count, and tree_height MUST describe the resulting tree. Only pages reachable from the final root are published; intermediate pages produced while applying a batch are not. New pages and the replacement Track Object are staged before the Ref moves, so a refusal or failed write leaves the prior Ref authoritative.

The reference Dataset API exposes an append report for ordered scalar fields. It distinguishes an initial Rebuild from Incremental path-copy and reports existing pages read, new reachable pages written, and existing pages reused. The legacy append methods retain their sample-count return type.

10. Open questions

• Sample-id model coupling. This spec assumes sample anchors are byte-comparable u64s — DreamDB's existing time-anchor semantics. If design/0001 ever introduces an explicit sample-id join Track (the deferred Phase 1 question), the bucket-record shape needs a per-record sample-id field. Resolution: defer until the join-Track decision is made; bitmaps internally already abstract over the "sample identifier" concept.
• Bitmap representation. The existing per-value, tagged RoaringTreemap anchor-bucket representation remains normative for v0.2; the legacy CBOR anchor array is read-only compatibility. A different future bitmap representation needs a new discriminated payload format and MUST NOT overload a magic address in the existing tuple.

11. Conformance

Adds a new test category to spec/0009 §5:

• 5.4. Scalar Index — ScalarIndex Object CBOR round-trip per algorithm and byte-pinned B-tree leaf/internal pages. Dataset behavioral tests cover bitmap equality and ordered page pruning.

Cross-implementation vectors live in dreamdb-conformance/vectors/0011/. Producers MUST byte-match the pinned ScalarIndex and page encodings before the implementation is certified.