Spec 0015 — Hybrid Retrieval and Query Planning
Status: Draft (Phase 4 design).
Depends on: spec/0001, spec/0002, spec/0004, spec/0006, spec/0010, spec/0011, spec/0013.
Motivation: spec/0004–0013 give DreamDB the per-modality retrieval primitives — vector ANN (LSH/IVF/IMI/Vamana), vector compression (QINCo), scalar filters (B-tree / bitmap), federation, graph routing. Production search engines (Elastic, Vespa, Pinecone, Weaviate, Marqo) all converged on something DreamDB does not yet have: a hybrid retrieval contract that fuses lexical (BM25), dense (vector), scalar (structured), and (increasingly) multi-vector late-interaction (ColBERT) into a single ranked list per query — with a query planner that decides which indexes to consult, in what order, with what cost budget. Without this layer, DreamDB is "a strong collection of indexes" rather than "a search engine." This spec closes that gap.
1. Purpose
Real-world retrieval queries are not pure: "DreamDB protocol changes since 2026" needs an exact-phrase match on "DreamDB," a semantic match on "protocol changes," and a time filter on "since 2026." Today each goes through a different verb on a different index; the application is responsible for fusing the results. That's correct as a separation of concerns but inadequate as a default — applications routinely get the fusion wrong (incompatible score scales, double-counted duplicates, blown latency budgets).
By the end of this document the following are concrete:
- The TextIndex Object: a new ObjectKind that holds inverted-index posting lists for lexical retrieval. Algorithm registry adds
dreamdb.bm25,dreamdb.bm25-plus, and OPTIONALdreamdb.splade-cosinefor learned sparse retrieval. - The multi-vector retrieval contract: ColBERT-style late interaction over ordinary SpatialBucket and VectorStorage Objects, with a canonical composite-anchor identity and MaxSim aggregation.
- The HybridQuery verb: extends spec/0006 §4.3's
Queryto accept multi-modality sub-queries with fusion policy. - The Reciprocal Rank Fusion (RRF) default: scale-invariant score combination; the v0.X production default.
- The Query Planner: cost-model + execution strategy. Decides pre-filter-vs-post-filter for scalar+vector composition, chooses which TextIndex/SpatialIndex/GraphIndex to consult, batches I/O, applies early-termination.
- The pre-filter vs post-filter contract: when a query has a scalar predicate AND a vector predicate, which runs first is a major optimization. spec/0015 pins the planner's contract so two implementations make the same choice given the same statistics.
What stays defined elsewhere:
- Per-modality storage layouts — spec/0007, spec/0010, spec/0013.
- Manifest registry — spec/0002; federation and runtime Connector bindings — spec/0012. Credential formats are deployment-local (
0018§3). - The
Queryverb's general shape — spec/0006.
What this document does NOT define:
- Question answering / generation. Retrieval ends with a ranked list; the application's LLM / answer generator is downstream.
- Personalization / behavioral signals. Click-through reweighting is application-layer.
- Cross-Track joins. Joins are out of scope; the application materializes them.
- Approximate query languages (SQL-like, GraphQL-like). HybridQuery is structured-CBOR; pretty syntax is SDK ergonomics.
2. The retrieval surface
| Surface | What it answers | Existing index | New index (this spec) |
|---|---|---|---|
| Dense | Semantic similarity over embedding | SpatialIndex (0004) / GraphIndex (0013) | — |
| Dense compressed | Same, with PQ/QINCo codes | VectorCompressor (0010) | — |
| Scalar | label = "cat", time ∈ [a, b], score > 0.5 | ScalarIndex (0011) | — |
| Lexical | BM25 / token-match for proper nouns / codes | — | TextIndex (§3) |
| Multi-vector | ColBERT MaxSim over per-token vectors | SpatialIndex + SpatialBucket + VectorStorage | Composite-anchor contract (§4) |
| Hybrid (fusion) | Combine 2+ of the above | — | HybridQuery (§5) |
Every individual surface retains its own query entry. The new physical ObjectKind in this spec is TextIndex; multi-vector retrieval composes the existing vector Objects rather than introducing another stored index kind. The higher layer is the HybridQuery composition.
3. The TextIndex Object
A TextIndex Object holds an inverted index for a text-bearing modality.
3.1 Modality string
Text modalities follow the existing grammar:
The .bm25 / .bm25-plus / .splade=… suffix is OPTIONAL. Without it, text is stored as Constant or Time-bucketed Discrete Event items (per existing modality table); presence enables index publication.
3.2 Address path
(New per-Timeline slot, parallel to spatial-index/ and graph-index/.)
3.3 CBOR encoding
3.4 Algorithm-specific params
dreamdb.bm25 and dreamdb.bm25-plus
dreamdb.splade-cosine
SPLADE produces a sparse |V|-dim vector per doc; the index is effectively an inverted file keyed by vocab dimension. Same posting-list machinery as BM25, just different per-document weights.
3.5 Posting-list pages
Posting lists for high-volume tokens exceed inline budget. Following spec/0002's paged-index pattern:
Address: <timeline>/<modality>/text-index/posting/<page-hash>.
tf is term frequency in the doc; positions is OPTIONAL byte-packed list of in-doc token positions for phrase queries. For BM25 without phrase support, omit positions to halve posting-list size.
3.6 BM25 scoring
For a query Q and document d:
dreamdb.bm25-plus adds + delta to each per-term contribution (Yang & Lin 2011); recommended for long-doc collections.
Scoring is computed by the SDK after fetching the relevant posting-list pages. Implementations MUST use the same fp32 left-fold discipline as spec/0004 §5.4.1 to guarantee bit-identical scores across implementations (otherwise top-K rankings drift across SDKs for tied scores).
3.7 Registry reference
A TextIndex is an auxiliary Object bound to a source Track through the
registry. It is NOT a Track. (Resolves OQ-93; see 0002 §13.) It therefore
never appears in a Manifest's tracks[], has no Track kind, no Object kind and
no role, and is never decoded through the Track inline-index path.
This is the same shape SpatialIndex (0004 §3.3), ScalarIndex (0011 §3) and
VectorCompressor (0010 §4) already use. A Track is time-anchored data; an
index is an access structure over it. They have different lifecycles, and the
Manifest already versions the binding atomically, so promoting an index to a
Track buys nothing and would force a second set of semantics onto kind,
role, coverage, merge, layering, paging, GC and conformance.
The Manifest registry's per-modality entry for an indexed text modality:
Note what is absent: no kind, no object_kind. Earlier drafts of this
section showed "kind": "discrete" and "object_kind": "time-batch", which
contradicted 0002 §7.2.1 (whose kind enumeration is
continuous | event | constant, with no discrete) and presumed the index was
a Track. Both fields are removed.
Normative requirements:
- An Index Object MUST NOT appear in a Manifest's
tracks[]. - The registry key MUST identify the index uniquely per field, not merely
per algorithm. Two text fields in one Space indexed with the same algorithm
would otherwise collide on one registry key and the second binding would
silently displace the first. Carry the field in the modality tag —
.field=<name>, asscalar.*already does (0011§2). source_trackMUST record the address of the Track the index was built from, so staleness is detectable.- A Track and the indexes over it MUST be published in the same Manifest, so the binding is atomic. (A Manifest is a single content-addressed Object, so this costs nothing beyond not splitting the publish in two.)
- A reader that finds
source_trackabsent from the Manifest, or pointing at a Track other than the one it is about to query, MUST raise an error rather than serve results from a stale index.
Standard SpatialIndex / ScalarIndex / VectorCompressor lineage validation (per 0004 §3.3.1, 0010 §3.3) applies symmetrically. SDKs MUST validate algorithm match and tokenizer-vocab-hash match before scoring.
3.8 Garbage-collection reachability
A paged TextIndex (§3.5) stores its posting lists in separate Objects that
only the index root enumerates. A GC implementation MUST mark both the root and
every Object in its posting_pages list reachable. Marking only the root leaves
the pages sweepable, and the result is silent corruption: the root survives
pointing at Objects that no longer exist.
GraphIndex is not the same case, and an earlier revision of this section said
it was. A GraphIndexObject (0013 §3) carries no page list, and each
GraphPage carries the hash of its parent GraphIndex (0013 §4.2, header field
graph_index_hash) — so enumerating the pages from the index would make the
index's content address depend on hashes that already depend on it. The
enumeration therefore lives where it can: an ordinary Track Object whose inline
object index lists the GraphPages in page order. A GraphIndex is reachable
through the registry; its GraphPages are reachable through that Track, and
the Track stays in tracks[] for exactly that reason. Requirement 1 of §3.7 —
"an Index Object MUST NOT appear in tracks[]" — is about the index Object,
and is not violated by the page-list Track. Making GraphIndex genuinely
Track-free requires an acyclic redesign of the GraphIndex→GraphPage addressing
and is not specified here.
This is a real failure mode, not a theoretical one — it is what happens when an index is reachable only incidentally, via a Track entry, and that entry is removed by requirement 1 above. Extend the GC registry walk before writers stop emitting the legacy Track entry.
4. Multi-vector retrieval
A multi-vector field supports ColBERT-style retrieval: each logical document is represented by N vectors (typically per-token contextualized embeddings), and similarity to a query (also N vectors) is the MaxSim aggregation:
Late interaction beats single-vector retrieval substantially on long documents (Khattab & Zaharia 2020, BEIR benchmark) at the cost of N× storage.
4.1 Modality string
This spelling and parameter order are canonical. multivec is the marker and
maxtokens=M is the positive u32 token-slot count reserved for every
document. spec=S is REQUIRED for a field identified by 0024, MUST be its
canonical full spec_id, and is absent only for a legacy unidentified field.
dim, maxtokens, and an optional trailing version use the unique base-10
spelling with no leading zeroes. Aliases such as multi-vec,
max-tokens, multi_vec, reordered parameters, duplicate parameters, and
additional v1 parameters other than 0024's spec MUST be rejected. The hyphenated spellings in earlier
drafts never satisfied the modality grammar in 0002 §5 and were never emitted
by the shipped writer.
bucketed classifies the Track as ordinary SpatialBucket storage. The bound
SpatialIndex and VectorCompressor remain the ones in the modality registry;
there is no MultiVectorIndex Object or multi-vec-index address slot in v1.
4.2 Storage layout
The field holds one ordinary bucketed embedding Track and one SpatialIndex over
all token vectors in the corpus. No SpatialBucket header or record layout is
extended. Each token uses the existing record shape (time_anchor, vector bytes), and the record anchor is the following composite identity:
document_id is a non-negative logical id, not an arbitrary nanosecond timestamp;
v1 does not require consecutive ids.
Document ids within one write MUST be unique. 0 ≤ token_ordinal < M; a
document has at least one and at most M token vectors. Its complete reserved
window is [document_id * M, (document_id + 1) * M). The writer MUST reject a
document unless that exclusive end is representable and no record anchor can
reach i64::MAX; equivalently:
All multiplication and addition are checked. A reader MUST reject an anchor in
the unrepresentable tail rather than wrap, truncate through an i64 cast, or
assign it to an incomplete document window. These bounds make document-window
scans expressible through the v1 Dataset time-range API and give the quotient
and remainder one portable interpretation.
The logical parent field records derivation provenance. The composite
document_id is the identity returned to the caller; v1 does not persist a
separate parent-resolution Track.
Lookup proceeds as:
- Compute the N query-token vectors.
- For each, do a coarse ANN over the global token index → top-K_tok candidates.
- Decode each candidate's composite anchor and group by
document_id. - For each candidate document, fetch every surviving token in its reserved window and obtain the original f32 vectors from the entry-aligned exact VectorStorage sidecars.
- Re-rank by MaxSim; return top-K_doc.
Conforming new writers set the embedding field's Schema rerank declaration to
true and write an exact VectorStorage sidecar beside every bucket entry. Bucket
record i and sidecar record i are the same token, under the alignment and
integrity rules of 0010 §5.2. A missing, truncated, ambiguous, or divergent
sidecar is a hard error; MaxSim MUST NOT silently fall back to a decoded lossy
code. Each query and document token is L2-normalized before its inner product,
as required by the field's cosine algorithm; MaxSim uses the fp32 left-fold
discipline of 0004 §5.4.1.
4.3 Compatibility with the shipped representation
The implementations included in release tags python-v0.0.7 through
python-v0.0.10 already contained writers for the composite-anchor bucket
representation and the canonical multivec.maxtokens modality above.
This revision standardizes those bytes; it does not reinterpret or migrate
their bucket records and does not introduce the draft 240-byte alternative.
Those historical writers declared rerank=false and did not publish exact
sidecars. Their ordinary vector Track remains valid and readable, but it cannot
satisfy exact MaxSim. A current query_multi_vector implementation MUST refuse
such a field with a diagnostic requiring republish from source vectors. It MUST
NOT label a MaxSim over decoded lossy codes as exact. Re-ingestion with a
conforming writer preserves the same composite identity and adds the missing
sidecars; no in-place byte reinterpretation is permitted.
5. The HybridQuery verb
Extends spec/0006 §4.3 Query. A HybridQuery accepts a structured spec describing per-modality sub-queries and the fusion policy.
5.1 Query spec (CBOR)
5.1.1 TrackSelector sub-Object
A v0 query that targets a single Track passes only track_ref; the other two fields are absent or null. spec/0017 multi-version queries use logical_concept + version_preference (with track_ref = null), letting the planner enumerate matching versions from the Manifest registry rather than addressing a specific Track. The planner MUST accept both shapes — track_ref-only is the v0 fast path; logical_concept-only is the migration-aware path; both populated is malformed.
5.2 Fusion policies
Reciprocal Rank Fusion (RRF) — default
where k = 60 by convention; rank_i(d) is d's rank in sub-query i (∞ if absent). RRF is scale-invariant — sub-queries with different score ranges (BM25 ~[0, 40]; cosine ~[0, 1]) combine sensibly without normalization. Cormack et al. 2009 + a decade of TREC track results show RRF is hard to beat without tuning.
Linear
Normalization is per-sub-query min-max over the candidate pool. Linear lets operators encode known preferences ("dense matters 2× more than lexical") but requires per-collection tuning. NOT the default.
Max
Cheap fallback; effectively "best signal wins." Useful for "lexical OR semantic" queries.
Pareto
Return the union of each sub-query's top-K_local; client takes responsibility for re-ranking. Bypasses score-combination entirely. Use when the application has its own re-ranker (e.g., a cross-encoder).
5.3 Required sub-queries
A sub-query with required: true becomes a filter — candidates absent from its top-K_local are eliminated from the final pool. This is how spec/0015 encodes "must match the lexical phrase AND be semantically close" without nested boolean syntax.
5.4 Latency-vs-recall budget
budgets.max_latency_ms is a ceiling on the planner's deterministic projected
cost, not a wall-clock timeout. If the requested candidate depths exceed the
ceiling, the planner reduces k_local in ascending marginal-cost order (ties
by query-spec order), never below one for a non-empty sub-query. It then reduces
the remaining, costlier sub-queries in the same order. The result trace carries
the requested and executed depths, projected microseconds, and
degraded: true. If even the fixed cost plus one candidate from each non-empty
sub-query exceeds the ceiling, the query MUST fail before those sub-queries run;
silently ignoring the budget is forbidden.
6. The query planner
The planner translates a HybridQuery spec into an execution plan: an ordered list of index accesses with batched I/O and parallel-where-possible scheduling.
6.1 Pre-filter vs post-filter (the central decision)
When a query has a scalar filter (e.g., label = "cat") AND a vector sub-query, the planner chooses one of:
| Strategy | Steps | Best when |
|---|---|---|
| Pre-filter | 1. Scalar lookup → candidate doc-id set; 2. Vector search RESTRICTED to set | Scalar is highly selective (<1%) |
| Post-filter | 1. Vector ANN → top-K_oversampled; 2. Filter by scalar; 3. Re-rank | Scalar is mildly selective (>1%) |
| Joint (future) | A scalar-aware vector index (e.g., label_id participating in spec/0004 spatial-key derivation) gives O(1) intersect | Single field, very high selectivity. Deferred — spec/0004 v0 does not yet support hybrid spatial keys. |
The threshold-of-1% is a planner heuristic, not a contract. The contract is:
- The planner MUST estimate selectivity from the ScalarIndex Object (count
of matching doc-ids vs total). The Dataset SDK currently materializes the
matching anchor set and selects pre-filter at
count ≤ 1024; this absolute threshold is an implementation heuristic until a cheap total-count statistic is available. - The planner MUST be deterministic given the same implementation, cost model, statistics, and query. The threshold is not a wire-compatibility constant and different implementations need not choose the same strategy.
- A pre-filter MUST restrict BM25 accumulation before its top-K and vector candidates before pool selection/scoring. For reference-mode vector buckets, it MUST also run before Vector-Storage ranges are constructed. Applying set membership only to the returned top-K is post-filtering under another name.
6.2 Cost model
Each strategy is costed by:
α, β, γ are operator-tunable SDK configuration (bandwidth, CPU speed,
network latency), resolving OQ-63. An SDK MAY expose an equivalent collapsed
integer model — fixed cost plus marginal scalar-match, text-candidate, and
vector-candidate costs — provided every term and the result use integer
microseconds and saturating arithmetic. Defaults are SDK choices; the
decision function consuming a chosen model is deterministic per §6.1.
6.3 Plan stability (mandatory)
Per-query plans MUST be:
- Deterministic given the same implementation, cost model, Manifest, ScalarIndex statistics, and HybridQuery spec (§6.1). Different implementation heuristics need not choose identical plans.
- Returned in an observable execution trace: selected plan, scalar match count, requested/executed candidate depths, projected cost, and degradation flag. SDKs MAY also log that trace. Wall-clock actual cost is operational telemetry, not an input to or reproducibility claim about the plan.
6.4 Adaptive execution
Within a plan, the SDK MAY adapt:
- If pre-filter returns 0 candidates → return 0 candidates. Falling back to an unfiltered query violates the caller's predicate and can expose records the query explicitly excluded.
- If vector ANN returns 0 candidates above similarity floor → widen search-list / probe count once before giving up.
- If a transport stalls → apply the connector's bounded retry policy. Use another backend only when the runtime has explicitly bound a suitable mirror;
0012does not discover mirrors or grant implicit credentials (OQ-52).
Adaptive execution is implementation-defined for the retry tactics but mandatory for the escalation order: cheaper-first widens first. Same discipline as spec/0004 §6.5 recall-widening escalation.
7. Hybrid query latency at 1B-scale
Illustrative planner scenario, not measured performance or a literal wire tag:
a BM25 TextIndex plus an independently bound compressed embedding field over
1B documents. Tokenizer and compressor configuration belong to their bound
Objects; the former compress=qinco:M=8 example is not a valid modality spelling
(0010 §4), and QINCo remains deferred. Query: lexical terms plus a vector and
a time predicate. The numbers below are assumptions, not an implementation report.
Planner output (deterministic given stats):
Latency:
- Step 1: 1 GET of ScalarIndex root + tree walk → ~20 ms warm.
- Step 2: 2 GETs of posting-list pages → ~30 ms warm.
- Step 3: in-memory set intersection → <1 ms.
- Step 4: 16 GETs of Spatial Bucket Objects (QINCo-compressed; ~512 KB total) → ~30 ms warm.
- Step 5: fusion + final ranking → <1 ms.
- Total p50: ~80 ms warm. Single-backend; federation scatter-gather adds the spec/0012 §6 fan-out.
Cold-start adds ~100 ms (one Manifest fetch, one Track Object root fetch). Within the same budget as a single-modality query — fusion overhead is negligible.
8. Conformance categories (per spec/0009 §8.6.1)
| Category | Pass criterion | Coverage |
|---|---|---|
hybrid.rrf.scale-invariance.* | Same RRF score regardless of sub-query score scales | BM25+cosine; cosine+bm25-plus |
hybrid.planner.deterministic.* | Same Manifest + stats + query → same plan | Multi-implementation |
hybrid.prefilter.threshold.* | Selectivity <1% → pre-filter chosen; >1% → post-filter | Adversarial stats |
hybrid.required.elimination.* | required:true sub-query eliminates non-matching candidates | Boolean-AND semantics |
hybrid.bm25.fp32-determinism.* | BM25 scores bit-identical across implementations | Scalar reference vectors |
hybrid.colbert.maxsim.* | MaxSim aggregation matches reference (within fp32 left-fold discipline) | dim=128 reference corpus |
hybrid.splade.encoder-validation.* | TextIndex with SPLADE algorithm validates encoder_hash against registry | Encoder mismatch → critical error |
9. Composition with existing specs
| Existing primitive | Composition |
|---|---|
| spec/0004 (SpatialIndex) | Dense sub-query backend; HybridQuery dispatches to existing Query verb |
| spec/0010 (VectorCompressor) | All sub-queries inherit compression transparently |
| spec/0011 (ScalarIndex) | Scalar sub-query AND scalar filter share the same B-tree / bitmap indexes |
| spec/0012 (Federation) | HybridQuery scatter-gathers per-modality; merge is sub-query-aware |
| spec/0013 (Vamana) | Dense sub-query backend (interchangeable with SpatialIndex) |
| spec/0014 (chunked Items) | Sub-query results are Item IDs; stitching handled by per-Item read path |
The composition story is clean by design: HybridQuery is a plan over existing primitives, not a new physical layer.
10. Out of scope
- Cross-encoders / neural re-rankers. Late re-ranking with a transformer is application-layer; HybridQuery returns a ranked candidate set; the application's re-ranker downstream is its own concern.
- Personalization signals. User-specific weights, click-through reweighting — out.
- Query expansion (synonyms, hypernyms). Tokenizer-layer concern; the application can call its expander before submitting the HybridQuery.
- Native graph queries. "Find docs cited by X" requires graph traversal of citation links; out of v0.X spec.
11. Open questions
- OQ-62 (→ this spec): RESOLVED — positions OFF by default, opt-in. Phrase queries need positions; recall-only retrieval does not, and defaulting to positional roughly doubles index size. The recommendation was taken and shipped:
dreamdb-protocoltext_index.rsbuild()delegates tobuild_with(.., positions = false), so a caller who wants positional postings (andphrase_match) must ask for them explicitly. - OQ-63 (→ this spec): RESOLVED — operator-tunable with SDK defaults. The deterministic decision consumes the selected model; default coefficients are not wire-format or cross-implementation compatibility constants (§6.2).
- OQ-64 (→ this spec): SPLADE vs ColBERT as the v0.X learned-retrieval default. Both work; SPLADE composes more cleanly with existing inverted-index machinery. Lean SPLADE; ColBERT as opt-in.
- OQ-65 (→ spec/0009): Portable vectors for hybrid query semantics, eligibility ordering and fusion. Benchmark recall/latency on BEIR or MS-MARCO belongs to
0023and cannot substitute for those correctness cases; a benchmark target does not gate unrelated protocol releases. - OQ-66 (→ spec/0006): Add HybridQuery as a 10th verb or fold into
Query? Resolved: spec/0006 §2.2.1 folds HybridQuery into the existingQueryverb — the structuredquery_specpayload defined in §5.1 of this document is the new richer shape. The eight-verb taxonomy of spec/0006 §2 is unchanged.
Next: spec/0016 — streaming updates and real-time freshness (closes the continuous-ingest gap that hybrid retrieval surfaces — without sub-second freshness, "search what I just wrote" doesn't work).