Repository navigation
perf(post-1.0): hash-join negation inner loop #202
Description
Roadmap source
ROADMAP.md: Post-1.0 Performance Backlog.
Problem
not / not-join evaluation re-scans all candidate facts once per outer binding, producing O(outer * inner) behavior. Roadmap benchmark observations: not_scale/10k around 13s and not_join_scale/10k around 23s.
Proposed fix
Pre-compute the exclusion set from the not body once, then probe per outer binding using a hash lookup.
Acceptance criteria
- Reduce negation inner-loop behavior from O(N^2) to O(N) for the benchmarked shape.
- Add or update benchmarks for
not_scaleandnot_join_scale. - Preserve existing negation semantics and safety checks.
Activity
feat: selective B+Tree lookup in filter_facts_for_query (#208) (#246)
perf: pre-compute not/not-join exclusion sets — O(N²) → O(N) (#202)
fix: address code review issues in #202 exclusion set implementation
fix: not-join underspecified binding now falls back to evaluate_not_j…
fix: type aliases to satisfy clippy::type_complexity (#202)
Merge pull request #247 from project-minigraf/feature/issues-202-203-…
docs: add Wave 1 performance design spec (#208, #202, #203, #204)
docs: add Wave 1 implementation plans for #208 and #202/#203/#204
docs: sync all docs for Wave 1 performance completion