Repository navigation
perf: push down not/not-join clauses and short-circuit or/or-join branches - #344
Merged
Merged
Conversation
…nches #248: optimizer::plan() now places Not/NotJoin at the earliest position where their required variables are bound by preceding patterns, instead of always deferring them to a post-filter after every pattern (and after Or/OrJoin). A clause that can only be satisfied via an Or/OrJoin binding is still deferred, since plan() has no visibility into those clauses. This shrinks the executor's two large not-filter blocks into small per-clause helper calls reused for both the inline and deferred paths. #250: apply_or_clauses now short-circuits once evaluated branches already cover every incoming binding. Always safe for or-join (branches are projected to already-bound outer keys before merging, so a skipped branch could only re-derive an existing row). For plain or, only safe when no evaluated branch has introduced a variable beyond the incoming scope, since a later branch legitimately could bind a new variable differently for an already-covered key otherwise. Benchmarks: negation/not_pushdown_selectivity shows up to ~55% faster at high exclusion rates; disjunction/or_short_circuit and disjunction/or_join_short_circuit show ~11% and ~27% improvement on fully-redundant branches. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU
Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
…sh-down Two nits from ultrareview on PR #344: - Not/NotJoin clauses landing at the same insertion point came out in reverse cost order, since each result.insert(pos, ..) shifts an already-inserted clause one slot later. Sorting descending by cost before inserting corrects this (the insertion reversal then produces the intended ascending/cheapest-first order). - The Not arm's required-variable computation didn't exempt `?_`-prefixed wildcard vars, unlike the NotJoin arm and the parser's own outer_vars_from_clause. A `(not [?e :attr ?_x])` body was deferred to the post-filter as if ?_x needed to be bound by an outer clause, even though the wildcard convention means it never does. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
optimizer::plan()now placesNot/NotJoinclauses at the earliest position where their required variables are bound by preceding patterns, instead of always deferring them to a post-filter after every pattern (and afterOr/OrJoin). A clause that can only be satisfied via anOr/OrJoinbinding is still deferred, sinceplan()has no visibility into those clauses — this preserves correctness for that case exactly as before.apply_or_clausesnow short-circuits branch evaluation once the branches evaluated so far already cover every incoming binding. Always safe foror-join(branches are projected onto already-bound outer keys before merging, so a skipped branch could only re-derive an existing row). For plainor, only safe when no evaluated branch has introduced a variable beyond the incoming scope — otherwise a later branch could legitimately bind a new variable differently for an already-covered key, so that case still evaluates every branch.executor.rsinto small, reusable per-clause helper functions used for both the inline (pushed-down) and deferred (post-filter) application paths.Test plan
cargo test— full suite green (688 unit tests + all integration suites)cargo clippy --all-features -- -D warnings— cleancargo fmt --check— cleanoptimizer.rscovering not/not-join push-down positioning and deferral (unbound vars, wildcard?_join vars, zero-required-vars placement)tests/disjunction_test.rscovering or/or-join short-circuit correctness, including a call-counting UDF predicate proving the expensive branch is actually skipped (not just that results happen to be correct), a test proving skip relies on genuinebranch_cost-based reordering rather than declaration order, and a correctness guard proving plainornever skips branches that introduce new variablesnegation/not_pushdown_selectivityshows up to ~55% faster at high exclusion rates;disjunction/or_short_circuitanddisjunction/or_join_short_circuitshow ~11% and ~27% improvement on fully-redundant branchesCo-Authored-By: Claude Sonnet 5 noreply@anthropic.com
https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU