Repository navigation
perf: hash-join cluster — O(N²) → O(N) for not/or/join (#202 #203 #204) - #247
Merged
Merged
Conversation
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
Replace the per-binding not-filter loop in execute_query with a pre-computed exclusion set approach: run each not/not-join body once against filtered_facts, build a HashSet of excluded join-key tuples, then probe O(1) per outer binding. Includes normalize_value() to reconcile Value::Keyword vs Value::Ref entity representations across body and outer bindings. Expr-only bodies fall through to the existing not_body_matches slow path unchanged. Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
- Move has_expr out of per-binding filter closure into pre-compute phase; store alongside exclusion set as (bool, HashSet) tuple for both not and not-join paths, eliminating redundant O(clauses) work per outer binding - Apply normalize_value consistently on the not (non-join) path when building and probing the exclusion set, matching the not-join path; prevents misses when entity values differ between Ref and Keyword variants - Derive key_vars as intersection of join_vars with vars present in ALL body binding rows (fold/all approach), not just the first sample row - Fix not fast path to fall back to not_body_matches when the outer binding is underspecified relative to the exclusion set key, instead of silently allowing the row through with continue - Replace unsafe [i] indexing with zip() iteration to satisfy clippy (reduces clippy errors from 3 to 0) Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
For Or/OrJoin branches that contain only patterns (no Not/NotJoin), evaluate each branch once from an empty seed to get the full candidate set, then hash-join the union back onto incoming bindings using shared user-visible variables. Branches with Not/NotJoin fall back to the classic seeded evaluation to preserve correctness (those clauses need bound outer-scope variables). Adds or_hash_join_tests covering the no-overlap, overlap deduplication, and or-join cases. Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
Replace the nested-loop in join_with_pattern with a hash-join when a shared join variable is detected in the entity or value position of the incoming pattern. Keyword/Ref values are normalized during build and probe so cross-type entity references (e.g., Value::Keyword stored as a fact value vs. Value::Ref produced in entity position) compare equal. The fallback to nested-loop is preserved for pseudo-attribute patterns and patterns with no shared variable. Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
adityamukho
force-pushed
the
feature/issues-202-203-204-hash-join
branch
from
May 15, 2026 09:18
e78c4dd to
92b2ce4
Compare
This was
linked to
issues
May 15, 2026
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
Three surgical O(N²) → O(N) fixes in the query engine:
executor.rs): Pre-compute not/not-join exclusion sets once before the outer binding loop. Each not-body is now evaluated once against filtered facts; the filter loop probes aHashSetin O(1) per binding. Expr-only bodies fall through to the existing slow path. Normalize keyword→Ref for cross-type entity reference equality.executor.rs): Replace seeded branch evaluation inapply_or_clauseswith empty-seed eval + hash-join back onto incoming bindings. Branches are evaluated once from[{}]; results are unioned across branches and hash-joined on shared user-visible variables. Includes defensive guard foror-joinvariables not bound in outer scope.matcher.rs): Replace nested-loop injoin_with_patternwith hash-join when a shared variable is detected. Entity position is checked first (dominant?e-join), value position as fallback.normalize_join_valuehandles keyword/Ref asymmetry. Pseudo-attribute patterns and unrelated patterns fall back to nested-loop.Test Plan
cargo test— all 577+ unit tests + all integration suites pass, zero failurescargo clippy— cleancargo fmt --check— cleannot_hash_join_tests(2),or_hash_join_tests(3),hash_join_tests(2)negation/not_scale,disjunction/or_scale,aggregation/with_grouped_sumall complete without panics{:?}debug format on Result/Fact/Value/EdnValue in any new test assert messagesCloses #202, #203, #204.
🤖 Generated with Claude Code