Skip to content

perf(engine): avoid pending maps for selective ancestor joins (#723) - #785

Merged
adityamukho merged 5 commits into
v3from
perf/723-memory-joins
Oct 29, 2026
Merged

adityamukho merged 5 commits into
v3from
perf/723-memory-joins

Conversation

@adityamukho

@adityamukho adityamukho commented Oct 29, 2026 •

Copy link
Copy Markdown
Collaborator

An in-memory ancestor query currently builds a value map of every pending edge when a recursive delta runs first. Eligible three-pattern delta runs now retain an alternative that starts from a small derived relation and probes edges by entity. Both orders use the same semi-naive ranges, and the alternative is refused if it could change the rule value head’s keyword/ref representation.

For #723, the existing recursion/ancestors/w10_d4 benchmark improves from 15.05 ms to 0.297 ms; a second pair gives 14.49 ms to 0.286 ms (about 50×). The depth-100 chain and fanout controls show no significant change; the depth-10 chain regresses by about 4%. Full measurements and raw Criterion output are in docs/BENCHMARKS.md and docs/benchmarks/723-recursive-joins.txt.

The runtime choice is limited to an empty committed dictionary, at most 128 source relation rows with no stored records, and an uncached pending value map whose capped record count favors entity probes. Populated committed generations retain AVET probes. There is no new storage index, dependency, API, or file format.

Validation on the bench machine:

  • The 128 KiB ancestor regression fails on the baseline with QRY-012 and passes with the change, including staged edge replacement and meter release.
  • A separate regression caught keyword/ref value-head changes and passes with the final eligibility guard.
  • Full default (1,982 passing) and test-hooks (2,015 passing) suites passed before the final guard and fourth test. The final full test-hooks run excluding the unchanged fault matrix passes 2,000 tests / 18 ignored; those 16 fault tests passed in both earlier full runs. The final default non-fault unit suite (1,140 passing) and plan-independence matrix (16 passing) also pass.
  • Strict all-features clippy and formatting pass. The docs site builds all 13 versions / 368 pages; docs PR: docs: explain selective in-memory ancestor joins (#723) minigraf-docs#84.

The maintainer approved raising the v3 binary-size cap from 1,230 to 1,234 KiB. With the same toolchain and lockfile, the release binary grows from 1,258,712 to 1,261,432 bytes (+2,720), below the new 1,263,616-byte cap. The workflow, PHILOSOPHY.md and benchmark report record the increase and rationale.

@codecov

codecov Bot commented Oct 29, 2026 •

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 86.16071% with 31 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/query/engine/recursive.rs 86.66% 8 Missing and 8 partials ⚠️
src/query/engine/plan.rs 73.68% 4 Missing and 11 partials ⚠️

📢 Thoughts on this report? Let us know!

@adityamukho
adityamukho marked this pull request as ready for review October 29, 2026 03:39
@adityamukho
adityamukho merged commit 5f80732 into v3 Oct 29, 2026
27 of 28 checks passed
@adityamukho
adityamukho deleted the perf/723-memory-joins branch October 29, 2026 03:40
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