Repository navigation
perf: short-circuit or/or-join branch evaluation using cost model #250
Description
Summary
Once optimizer::clause_cost() is available (landed in #205), use it to short-circuit or/or-join branch evaluation in apply_or_clauses.
Motivation
Currently apply_or_clauses evaluates all branches unconditionally and unions the results. For disjunctions with one highly selective branch, this wastes work on branches that contribute little or nothing to the final result.
The fast path (no Not/NotJoin in branches) evaluates each branch from an empty seed and hash-joins the union back onto incoming bindings. If the cheapest branch already produces bindings that cover all incoming bindings, subsequent branches add nothing and can be skipped.
Prerequisite
- perf(post-1.0): cost-based optimizer extensions for new clause types #205 —
optimizer::clause_cost()must land first (provides the static cardinality estimates needed to order branches)
Proposed approach
- Sort branches by
clause_cost()ascending before evaluation (cheapest first). The branch ordering inplan_or_branches()/clause_cost()from perf(post-1.0): cost-based optimizer extensions for new clause types #205 provides this directly. - In the fast-path loop, track which incoming binding keys are already covered after each branch is joined. Once coverage is complete, break early.
- In the seeded slow-path (branches with Not/NotJoin), sort branches cheapest-first so that branches most likely to match run first — less useful for short-circuit but reduces average work per outer binding.
Acceptance criteria
-
apply_or_clausessorts branches byclause_cost()before evaluation - Fast path: early exit when all incoming bindings are covered
- No change to query results — all existing tests pass
- Benchmark showing improvement on queries with one selective and one expensive Or branch
Activity
feat: cost-based not/or ordering (#205) (#251)
perf: push down not/not-join clauses and short-circuit or/or-join bra…
fix(or): an or branch meets a keyword value as the entity it names (#637