Corax Query Pipeline: v7.2 vs RavenDB-25281 Branch Comparison

CORAX_PIPELINE_COMPARISON.md

Corax Query Pipeline: v7.2 vs RavenDB-25281 Branch

Architectural Overview

v7.2: Optimizer Tree → Lazy Materialization

RQL AST
  │
  ▼
CoraxQueryBuilder.BuildQuery()
  │  ToCoraxQuery() walks AST recursively
  │  Produces optimizer nodes: CoraxBooleanItem, CoraxAndQueries, CoraxOrQueries, CoraxVectorItem
  │
  ▼
streamingOptimization (stack struct, ref-threaded through all methods)
  │  Detects: WHERE field == ORDER BY field → enables forward/backward iterators
  │  If streaming: SkipOrderByClause = true → SortingMatch omitted
  │
  ▼
MaterializeWhenNeeded()
  │  CoraxAndQueries.Materialize()  → MultiUnaryMatch scan OR chained And()
  │  CoraxOrQueries.Materialize()   → InQuery consolidation
  │  CoraxBooleanItem.Materialize() → TermQuery / BetweenQuery / RangeQuery
  │  CoraxVectorItem.Materialize()  → VectorSearch + AND with prior matches
  │
  ▼
DeduplicationMatch() ← if duplicates possible
OrderBy()            ← SortingMatch / SortingMultiMatch (if not skipped)

Key characteristics:

• Optimizer-first: Clauses exist as optimizer nodes BEFORE becoming IQueryMatch objects
• Deferred materialization: Clauses can be reordered, merged, or converted to scans before execution
• Streaming is baked in: MultiTermMatch has _doNotSortResultsDueToStreaming flag; BetweenQuery has streamingEnabled parameter
• Single query context: CoraxQueryBuilder.Parameters struct holds everything (searcher, allocator, fields, timings, etc.)

Branch: Plan → IL Compile → Bitmap Pipeline

RQL AST
  │
  ▼
QueryPlanBuilder.BuildAndCompile()
  │  ParseTemplate() → ClauseTemplate (immutable, cached)
  │  PopulateClauseValues() → PackedParam (typed packed 32-bit)
  │  EstimateCardinality() → sort clauses by selectivity
  │  EmitPlan() → PlanOp[] (linear sequence)
  │
  ▼
QueryILEmitter.EmitDelegate()
  │  Compiles PlanOp[] to DynamicMethod IL
  │  IL calls QueryPrimitives.Ctx* static methods
  │
  ▼
CompiledQueryMatch (cached per query text + operand order)
  │  Bitmaps[] pool (slot 0=main, 1=scratch, 2=save)
  │  ResolvedMatches[], PostingSources[], TermsProviders[]
  │
  ▼
Post-build optimizations (in CoraxIndexReadOperation):
  ├─ DirectScan: bypasses bitmap for range-ORDER BY patterns
  ├─ Compound field: single tree lookup for (f1,f2) patterns
  └─ Sort seek hint: skip irrelevant tree terms in SortingMatch
  │
  ▼
SortingMatch / SortingMultiMatch ← if ORDER BY present

Key characteristics:

• Plan-first: AST → flat PlanOp[] sequence → IL-compiled delegate
• Bitmap-centric: All AND/OR operations are bitmap set ops (RoaringBitmap)
• JIT-compiled execution: QueryLogic is compiled to IL once, reused across invocations
• Plan cache: Shared per index instance, two-generation eviction, SIMD key lookup

---

1. Sort Avoidance (Streaming / Index Walk)

No WHERE, only ORDER BY

Query: from Documents order by Name

v7.2	Branch
BetweenQuery(Name, min, max, streamingEnabled=true) → MultiTermMatch walks CompactTree in sort order. No bitmap. No SortingMatch. IncludeNullMatch + IncludeNonExistingMatch decorators handle edge entries.	ExistsQuery(Name, forward=asc) → SortedDrivingMatch walks field tree via ITermsProvider in sort order. Null/non-existing entries drained by built-in iterator handling. Wrapped as DirectScanSimpleMatch. No bitmap. No SortingMatch.

Query: from Documents order by Age

v7.2	Branch
Same pattern but with BetweenQuery(Age, long.MinValue, long.MaxValue, streamingEnabled=true). Forward/backward direction matches sort direction.	Same pattern with ExistsQuery(Age, forward). SortedDrivingMatch handles numeric field the same as string.

WHERE range on ORDER BY field

Query: from Documents where Age > 25 order by Age

v7.2	Branch
CoraxBooleanItem.Materialize() → GreatThanQuery(Age, 25, forward=true) with streaming enabled. No SortingMatch.	TryCreateSimpleFieldDirectScan → BetweenQuery(Age, 26, max, forward) → SortedDrivingMatch → DirectScanSimpleMatch. No bitmap. No SortingMatch.

Query: from Documents where Age between 30 and 50 order by Age desc

v7.2	Branch
BetweenQuery(Age, 30, 50, forward=false, streamingEnabled=true). Walks tree backwards. No SortingMatch.	TryCreateSimpleFieldDirectScan → BetweenQuery(Age, 30, 50, forward=false) → SortedDrivingMatch walks backwards. No SortingMatch.

Query: from Documents where Age > 25 and Name = 'Alice' order by Age

v7.2	Branch
Age range detected as streaming-capable. Streaming on Age produces sorted output. Name = 'Alice' is a residual filter. No SortingMatch.	TryCreateSimpleFieldDirectScan — Age range is driving clause (SortedDrivingMatch). Name = 'Alice' is residual predicate → DirectScanFilteredMatch with compiled IL delegate. No SortingMatch.

WHERE equals on ORDER BY field

Query: from Documents where Name = 'Alice' order by Name

v7.2	Branch
CoraxBooleanItem.TrySetAsStreamingField detects field match → materializes as BetweenQuery(Name, 'Alice', 'Alice', GTE, LTE, forward=asc). MultiTermMatch walks one term. No SortingMatch.	NOT DirectScan-eligible. Goes through bitmap pipeline: TermQuery(Name, 'Alice') → FillFromPostings fills bitmap → SortingMatch wraps. Sort is functionally a no-op: all entries matching 'Alice' have the same field value. SortedIndexReader seeks to the exact term position, decodes one posting list. The bitmap creation overhead is negligible (single term).

Why not a TermMatch directly? In v7.2, the optimizer did start with a TermQuery equivalent, but TrySetAsStreamingField converted it to a BetweenQuery with streaming so no SortingMatch wrapper was needed. In the branch, we COULD add DirectScan support for Equals (by using a single-term BetweenQuery as the driving clause), but it doesn't provide meaningful benefit:

• The bitmap for a single exact match is tiny (one term's posting list)
• The SortingMatch.SortUsingIndexFromBitmap walk is equally efficient (seeks to one term, decodes one posting list)
• The sort is a no-op — all entries share the same sort key

The SortingMatch wrapper IS created, adding minor overhead. The AttemptToSkipSorting mechanism could skip it, but SortingMatch hardcodes throw new NotSupportedException().

Multi-field ORDER BY

Query: from Documents order by State, Name

v7.2	Branch
Streaming on first field (State) was possible. The BetweenQuery(State, min, max, forward=sortDir, streamingEnabled=true) produces sorted output on primary field. SortingMultiMatch wraps for tie-breaking on remaining fields.	DirectScan requires orderByFields.Length == 1 → returns false. Falls through to AllEntriesMatch + SortingMultiMatch with full materialization + heap sort. This is a regression: v7.2 could stream on the primary field and only sort for ties. The branch materializes everything.

Options to fix:

Option A: Extend DirectScan for multi-field (low risk, high impact) Allow DirectScan when the first ORDER BY field has a driving clause (range or no-WHERE). Produce results pre-sorted by the primary field via SortedDrivingMatch. Wrap in SortingMultiMatch for remaining fields — the primary sort is free from the index walk, only tie-breaking sorts the remaining fields. Change: relax orderByFields.Length != 1 to orderByFields.Length == 0, and pass the remaining OrderMetadata to SortingMultiMatch after DirectScan.

Option B: Extend SortingMultiMatch to walk the primary field's index (medium risk, medium impact) Currently SortingMultiMatch always full-materializes. Add a SortUsingIndexFromBitmap-style path for the primary comparer: walk the first field's CompactTree, intersect batches with the bitmap, then only heap-sort within each batch for the remaining fields. This helps ALL multi-field sorts, not just DirectScan-eligible ones.

Option C: Special-case no-WHERE multi-field with DirectScan (low risk, narrow) When there's no WHERE clause, use SortedDrivingMatch for the primary field, heap-sort for remaining. Avoids full AllEntries materialization. Change: in TryCreateSimpleFieldDirectScan, allow multi-field when the no-WHERE case triggers.

Recommendation: Option A. Lowest risk, highest impact, directly addresses the v7.2 parity gap.

Null/non-existing handling

v7.2

Branch

IncludeNullMatch + IncludeNonExistingMatch decorator structs interleave null/non-existing posting lists at correct stream position. These were streaming-only — only used on the BetweenQuery produced for no-WHERE + ORDER BY.

Three coverage points: (1) DirectScan: SortedDrivingMatch has built-in iterator-based null/non-existing draining with nullFirst flag. (2) Bitmap + SortUsingIndexFromBitmap: SortedIndexReader has built-in null/non-existing posting list draining. (3) AllEntriesMatch (for multi-field or non-index-walk sorts): includes ALL entry IDs, including those with null/missing fields. The heap sort's comparers handle null positioning.

Do we need IncludeNullMatch/IncludeNonExistingMatch anywhere else? No. All three code paths cover null handling. The decorator pattern was tied to v7.2's streaming architecture where null entries had to be interleaved with tree-walk output. In the branch, null handling is integrated into the tree-walking primitives themselves (SortedDrivingMatch, SortedIndexReader).

---

2. AND/OR Boolean Optimization

Aspect	v7.2	Branch
AND reordering	CoraxAndQueries.Materialize() sorts clauses by PrioritizeSort(): Equals first, Between second, then by count descending	EmitPlan() sorts clauses by (IsNegated, Cardinality) — smallest (most selective) first
OR consolidation	CoraxOrQueries groups same-field Equals terms into InQuery (single multi-term lookup)	OR chain: FillFromPostings seeds bitmap[0], OrWithPostings ORs subsequent terms into bitmap[0]; limit check after each OR
AND-group within OR	Nested CoraxAndQueries within OR chain, materialized separately then OR-chained	Three-bitmap swap pattern: SwapBitmaps[0,2] (save), build AND in slot 0, OrBitmaps[0,2] (lazy OR), ClearBitmap[2]
NOT handling	AndNot(AllEntries, TermQuery) for standalone NotEquals	AndNotWithPostings bounded scan — ANDNOT the bitmap with the negated posting list

---

3. Scan Optimization

Query: from Documents where Age > 25 and Name = 'Alice' and City = 'NYC'

v7.2	Branch
MultiUnaryMatch: finds cheapest Equals clause (lowest term frequency) as anchor posting list. Walks that posting list, checks Age > 25 and City = 'NYC' per-entry inline.	Entry scan IL: CheckAndMaybeEntryScan fires when bitmap[0] is < 32K entries and 64× cheaper than posting-list decode. RunEntryScan() walks bitmap[0] entries, reads stored fields via EntryTermsReader, evaluates residual predicates via second IL delegate.

Query: from Documents order by Name

v7.2	Branch
Streaming BetweenQuery walks Name tree. No scan needed.	DirectScan: ExistsQuery → SortedDrivingMatch walks tree. No bitmap. No scan.

Query: from Documents where Name > 'M' order by Name

v7.2	Branch
Streaming BetweenQuery with range bounds. Tree walk starts at 'M'.	DirectScan: BetweenQuery(Name, 'M', max) → SortedDrivingMatch with range-bounded ITermsProvider. Tree walk starts at 'M'.

Query: from Documents where Name = 'Alice' and Age > 30

v7.2	Branch
Choose cheapest clause (likely Name = 'Alice') as anchor, Age > 30 as constraint. MultiUnaryMatch scan.	EmitPlan: FillFromPostings(TermQuery 'Alice') seeds bitmap[0]. If bitmap[0] is small (<32K), entry scan IL evaluates Age > 30 per-entry. If large, AndWithPostings(Age > 30) bounded scan.

AndWithPostings bounded scan: from Documents where Tags In ($largeList) and Status = 'Active'

• Status = 'Active' produces a 50K-entry bitmap
• Tags In list produces a 10M-entry posting list
• AndWithPostings uses bitmap's MinContainerKey/MaxContainerKey to Seek past entries below the bitmap and prune above the max. Only reads posting-list pages covering the 50K range — not all 10M.

AndWithPostingsLimited: from Documents where Tags In ($list) with include timings() and no ORDER BY

• When pageSize is set (e.g., take 20), after 20 matches, stops reading the posting list entirely
• For unsorted queries, any N results are sufficient

---

4. Sort Infrastructure

Aspect	v7.2	Branch
Single-field sort	SortingMatch<TInner> (full materialization + heap sort)	Same class, 3 strategies: (1) SortUsingIndexFromBitmap (index walk + bitmap intersect, no full materialization), (2) SortResultsFromBitmap (materialize + heap sort for non-index types), (3) Non-bitmap path (materialize + heap sort)
Multi-field sort	SortingMultiMatch<TInner> (full materialization + heap sort)	Same pattern — full materialization + heap sort with compound comparers
Random sort	SortHelper + random seed	ReservoirSampleFromBitmap (Floyd's algorithm, O(N) single pass)
Null ordering	nullFirst boolean	NullsSortMode enum — per-query nulls first/last via OrderMetadata.NullsSortMode?; per-field via NullIsSmallest(comparerId)

---

5. Caching

Aspect	v7.2	Branch
Query plan	N/A	PlanCache per index instance — caches ClauseTemplate (AST parse) + CompiledPlan (IL delegate). Two-generation eviction. SIMD key lookup
Result memoization	MemoizationMatch: caches shared sub-queries in growable buffer	Removed — bitmap pipeline avoids shared sub-queries through bitmap AND/OR operations

---

6. Execution Model

Aspect	v7.2	Branch
Dispatch	IQueryMatch tree — recursive Fill() / AndWith() calls	CompiledQueryMatch wraps IL delegate → IL calls QueryPrimitives.Ctx* → RoaringBitmap ops
Bitmap	GrowableBitArray (hash or bit-array)	RoaringBitmap (ref struct, container-based Array/Bitmap/Range, SIMD ops, storage recycling)
Tracing	QueryTimingsScope	Per-op Timings[] + ResultCounts[] in CompiledQueryMatch
EXPLAIN	Inspect() recursion per match	Pseudocode generated during EmitPlan, stored as ExplainSource on CompiledPlan

---

7. Vector / Spatial

Aspect	v7.2	Branch
Vector search	CoraxVectorItem in optimizer → VectorSearch() with filter bitmap	Separate from AND chain, post-filter phase. VectorSearchRetriever accepts RoaringBitmap directly
Spatial	SpatialMatch in optimizer tree	Post-filter phase via AttachPostFilterPhases()

---

Key Differences Summary

Architecture

	v7.2	Branch
Execution	Interpreted IQueryMatch tree	JIT-compiled IL delegate
Data structure	GrowableBitArray	RoaringBitmap (container-based ref struct)
Clause representation	CoraxBooleanItem structs (deferred materialization)	PlanOp[] (flat, pre-compiled) + PackedParam
Sort avoidance	Streaming baked into MultiTermMatch/BetweenQuery	DirectScan or SortingMatch.SortUsingIndexFromBitmap

What the Branch Gains

1. IL-compiled execution — plan ops compile to DynamicMethod IL calling QueryPrimitives directly
2. Plan caching — per-index, two-generation eviction, SIMD key lookup
3. Bounded range scans — AndWithPostings only reads pages overlapping the bitmap's container range
4. Limit-aware AND — stops accumulation early when enough results exist
5. Container-level set ops — SIMD-accelerated AndWith/OrWith/AndNotWith with storage recycling
6. Per-query nulls ordering — order by ... nulls first/last via NullsSortMode

What the Branch Loses

1. Memoization — removed (bitmap AND/OR replaces shared sub-queries)
2. MultiUnaryMatch scan — replaced by entry-scan IL (more general)
3. OR → InQuery consolidation — removed (bitmap OR handles this)
4. IncludeNullMatch / IncludeNonExistingMatch — null handling is now built into tree-walking primitives

Streaming Optimization — What Changed

v7.2 Streaming Pattern	Branch Equivalent
order by X (no WHERE)	DirectScan via ExistsQuery + SortedDrivingMatch → DirectScanSimpleMatch
where X > 5 order by X	DirectScan via BetweenQuery + SortedDrivingMatch → DirectScan
where X = 'val' order by X	Bitmap + SortingMatch (sort is a no-op; DirectScan not triggered)
order by X, Y (multi-field)	Gap: falls to full materialization + SortingMultiMatch. Option A (extend DirectScan for multi-field) is the recommended fix.