Skip to content

perf(engine): cache narrow entity probes in recursive joins (#672) - #782

Merged
adityamukho merged 1 commit into
v3from
perf/672-recursive-dedup
Oct 29, 2026
Merged

adityamukho merged 1 commit into
v3from
perf/672-recursive-dedup

Conversation

@adityamukho

@adityamukho adityamukho commented Oct 28, 2026 •

Copy link
Copy Markdown
Collaborator

Summary

  • Reuse completed, narrow entity probes in recursive rule joins with a per-join 64-entry LRU. Each entry holds at most 128 rows; high-degree probes and ordinary joins retain the streaming path.
  • Add seven engine regressions for repeated entities, eviction, shared bindings, keyword/ref identity, recursive inner relations, high-degree streaming, and optional-cache refusal at the query memory limit.
  • Record the 5M acceptance and 1M envelope measurements, plus the updated test counts.

Fixes #672.

Type of change

  • Performance improvement (non-breaking)

Validation

On the benchmark machine, the 4,882,500-row reach_5m query fell from 302.66 s to 70.91–74.40 s; added peak RSS was 165–172 versus 172 bytes per derived fact. Across four paired 1M envelope rounds, recursive p50 fell from 2,808.89 to 2,761.06 ms (1.7%); point lookups remained around 18 µs. Envelope process peak RSS varied between pairs; the raw runs and commands are in docs/BENCHMARKS.md.

On current v3, the bench-machine engine suite passed (73 tests, 2 ignored), and the 5M acceptance passed with 4,882,500 rows in 69.87 s and 172 added RSS bytes per fact. The release binary is 1,258,712 bytes, 808 bytes under the gate. All PR checks are green, including test-hooks, coverage, MSRV, native/browser/WASI clippy, Linux/macOS/Windows builds and tests, browser/WASI tests, docs, and the size gate. Claude reviewed the spec, plan, and code, including the rebased engine. Its questions about recursive rounds, meter release on rewind, and provisional entity IDs were checked against the current implementation.

Checklist

  • cargo test passes on the rebased branch (test-hooks CI and focused bench-machine suite)
  • cargo clippy -- -D warnings is clean on the rebased branch
  • cargo fmt --check passes
  • New code has tests, including the memory-limit fallback
  • No unwrap() / expect() in new library paths
  • CHANGELOG.md updated under Unreleased
  • The change aligns with PHILOSOPHY.md: an embedded, bounded, metered performance improvement with no file-format or public API change

Notes for reviewer

The cache is optional under a tight query memory limit; a refused entry continues through the existing streaming path. The benchmark baseline (d0ad89c1d) predates the three #641 slices now on v3; the rebased branch passed the 5M acceptance and size gate separately.

@codecov

codecov Bot commented Oct 28, 2026

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 97.18310% with 2 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/query/engine/join.rs 97.18% 0 Missing and 2 partials ⚠️

📢 Thoughts on this report? Let us know!

@adityamukho
adityamukho merged commit 756ffea into v3 Oct 29, 2026
19 checks passed
@adityamukho
adityamukho deleted the perf/672-recursive-dedup branch October 29, 2026 00:08
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