8000 perf: phase 7.4 — eliminate filter_facts_for_query index rebuild (~62-65% speedup) by adityamukho · Pull Request #26 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]

Skip to content

perf: phase 7.4 — eliminate filter_facts_for_query index rebuild (~62-65% speedup) - #26

Merged
adityamukho merged 15 commits into
mainfrom
feature/phase-7-4-query-optimizer
Mar 27, 2026
Merged

adityamukho merged 15 commits into
mainfrom
feature/phase-7-4-query-optimizer

Conversation

@adityamukho
Copy link
Copy Markdown
Collaborator

Summary

  • Eliminates O(N) four-BTreeMap index rebuild from filter_facts_for_query on every query call. The function now returns Arc<[Fact]> instead of a throwaway FactStorage, avoiding the rebuild of EAVT/AEVT/AVET/VAET indexes that PatternMatcher never used.
  • execute_query (non-rules path): zero FactStorage construction — pure Arc<[Fact]> flow from filter through to all pattern match, or-clause, and not-join operations.
  • ~62–65% speedup on non-rules queries at 10K facts (query/point_entity/10k: 22ms → 8.6ms; aggregation/count_scale/10k: 28ms → 9.7ms). Negation improved ~12%; disjunction unchanged (dominated by known O(N²) inner loop, post-1.0 backlog).

Changes

  • PatternMatcher: new MatcherStorage enum (Owned(FactStorage) / Slice(Arc<[Fact]>)), from_slice constructor, get_facts() helper. Existing new(FactStorage) unchanged.
  • filter_facts_for_query: return type Result<FactStorage> → Result<Arc<[Fact]>>. Index rebuild removed.
  • apply_or_clauses, evaluate_not_join, not_body_matches, evaluate_branch: signatures changed from &FactStorage to Arc<[Fact]>.
  • execute_query_with_rules: still converts Arc<[Fact]> → FactStorage for StratifiedEvaluator (deferred; post-profiling TODO).
  • Evaluator mixed-rules loop: accumulated_facts: Arc<[Fact]> computed once per rule iteration, reused for 4 call sites (was 4 separate get_asserted_facts() calls).
  • 6 new tests (4 in matcher.rs, 2 in executor.rs). 568 tests passing.
  • Version bumped to v0.13.1.

Test Plan

  • cargo test — 568 tests pass, 0 failures
  • cargo clippy — clean
  • cargo fmt --check — clean
  • Profiling gate confirmed: flamegraph showed Indexes::insert/BTreeMap as dominant cost (~25% query, ~23% negation) before changes
  • Benchmark regression check: non-rules query groups show expected improvement; no regressions

🤖 Generated with Claude Code

adityamukho and others added 15 commits March 27, 2026 08:26
- Add docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md
  covering profiling gate and filter_facts_for_query snapshot fix
- Narrow phase 7.4 ROADMAP scope to profiling + snapshot fix only
- Move optimizer extensions, rule eval optimization, and predicate
  push-down to post-1.0 backlog in ROADMAP.md

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
- Replace pprof/criterion with cargo flamegraph (Criterion version conflict)
- Enumerate both matcher.rs get_asserted_facts() call sites (lines 27 and 222)
- Clarify shared functions (apply_or_clauses, evaluate_not_join) across
  executor.rs and evaluator.rs with per-file call-site tables
- Separate execute_query (line 263) and execute_query_with_rules (line 477)
  not-filter rows in evaluate_not_join table
- Clarify §2.5 insertion point for accumulated_facts Arc computation
- Move evaluate_not_join propagation note (line 921) to §2.4 where
  evaluate_branch is covered
- Add per-join allocation note and out-of-scope entry

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
- Reframe gate as a proceed condition (not just a stop condition)
- Add explicit Step 2 conditional header
- Architecture Overview now states conditionality upfront

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
8-task TDD implementation plan for filter_facts_for_query Arc<[Fact]>
return type change. Gated behind flamegraph profiling confirmation.
Unit tests written in red state (Task 3) before implementation (Task 5).
Adds strip = "none" and debug = true to the bench profile so that
cargo flamegraph --bench produces readable stack frames instead of
opaque binary blobs. Profiling confirmed filter_facts_for_query
index rebuild (Indexes::insert / BTreeMap) is dominant cost at 10K
facts (~25% query, ~23% negation).

Phase 7.4 profiling gate: PASSES.
Adds MatcherStorage enum with Owned(FactStorage) and Slice(Arc<[Fact]>)
variants. from_slice constructor used by the executor snapshot path.
Existing new(FactStorage) constructor and all evaluator call sites
unchanged.

Part of phase 7.4 snapshot fix.
Two unit tests for filter_facts_for_query in executor.rs #[cfg(test)]:
net-asserted view (retracted facts excluded) and valid-time filtering.
Tests currently fail to compile; Task 5 changes the return type to
Arc<[Fact]> to make them pass.

Phase 7.4.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
…Fact]>

All call sites convert FactStorage → Arc at call time via get_asserted_facts().
No semantic change. Prepares for filter_facts_for_query returning Arc directly.

Part of phase 7.4 snapshot fix.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
filter_facts_for_query now returns Arc<[Fact]> instead of FactStorage,
eliminating the O(N) BTreeMap rebuild (4 indexes x N facts) on every
non-rules query call. execute_query constructs no FactStorage at all.
execute_query_with_rules still converts Arc -> FactStorage for
StratifiedEvaluator (deferred to post-profiling decision).

Also fixes the test_filter_facts_for_query_valid_time_filter test: the
"open-ended" fact now uses explicit valid_from=0 so it is visible at the
test's query timestamps (1500, 3000) rather than at tx_id_now() which is
epoch-ms and far larger.

Phase 7.4.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
…tion

Replaces four separate accumulated.clone() + get_asserted_facts() calls
with a single Arc<[Fact]> computed once and reused for PatternMatcher,
apply_or_clauses, not-body matching, and evaluate_not_join.

Part of phase 7.4 snapshot fix.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
filter_facts_for_query returns Arc<[Fact]>; execute_query path constructs
no FactStorage. PatternMatcher::from_slice added. 568 tests passing.
~62-65% speedup on non-rules queries at 10K facts.

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
- Update query latency point_entity/10K: 15.6 ms → 8.6 ms (-61.5% vs pre-fix baseline of 22 ms)
- Update aggregation count_scale/10K: 23.4 ms → 9.7 ms (-64.7%)
- Update negation not_scale/10K: 13.4 s → 7.0 s (-12.1% vs pre-fix baseline)
- Update disjunction or_scale/10K: 73.7 s → 68.9 s (within noise, p=0.36)
- Add Phase 7.3 → Phase 7.4 summary section with before/after table
- Update Known Limitations: index rebuild eliminated for non-rules path
- Fix Criterion version: 0.5 → 0.8
- Update header note to reference v0.13.1

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
…hase references

- Add named post-1.0 backlog entry for B+Tree Selective Lookup (range-scan
  predicate push-down): the get_all_facts() full scan is O(N) regardless of
  query predicates; fix is to use get_facts_by_entity/get_facts_by_attribute
  for bound patterns to achieve O(log N) selective fetch
- Update BENCHMARKS.md query latency and known limitations sections to
  reference "post-1.0 backlog" instead of vague "future phase"

Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
@adityamukho
adityamukho merged commit b635c7f into main Mar 27, 2026
13 checks passed
@adityamukho
adityamukho deleted the feature/phase-7-4-query-optimizer branch March 27, 2026 08:39
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant

0