Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 4 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -85,6 +85,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **Prepared queries in every binding** (#181). `prepare(text)` returns a prepared query with `execute(bindings)` (the JSON `execute` returns) and `query(bindings)` (the binding's cursor) in Python, Java, Android, Swift, Node.js and C, as `BrowserDb.prepare` does in the browser. Bindings map slot names (without the `$`) to plain host values (booleans, integers, floats, strings, null/`None`/`nil`, and a UUID type where the language has one, which binds an entity) or to a typed bind value for the other kinds (keyword, ref, entity, tx count, timestamp, any valid time). A prepared query sees the database as it is on each run. Where the binding has no `close` (Python, Java, Android, Swift, browser), a prepared query keeps its database open; in Node.js and C, closing the database releases its prepared queries, so the path can be reopened, and a prepared query used afterwards fails with `API-018`.
- **`BindValue::Entity` and `BindValue::Val(Value::Ref(..))` fit each other's slots** (#181). An entity slot (`[$e :attr ?v]`) takes `Val(Value::Ref(uuid))`, and a value, expression or rule-argument slot takes `Entity(uuid)` as the ref. Before, each was `INT-035` in the other's position, and a rule argument needed `Val(Value::Ref(..))`. A binding can now pass a host UUID without knowing where its slot is.

### Performance

- **Recursive rule joins reuse narrow entity probes** (#672). A rule query keeps up to 64 complete, at most 128-row entity probes in a metered LRU cache for each join. Repeated paths through the same middle nodes read their stored edges once per join instead of once per candidate. High-degree probes still stream, and ordinary joins keep their previous path. On the bench machine, `reach_5m` fell from 302.66 to 70.91–74.40 seconds in two change runs, with 165–172 versus 172 bytes of added RSS per derived fact. Query answers, file format and public API are unchanged.

### Fixed

- **Window partition scratch obeys `query_memory_limit`** (#765). Each window now charges its partition row indices while they coexist with input rows and earlier result columns, returns `QRY-012` if reserving them fails, and releases the charge after the window or on error. An in-place total sort removes the stable sort's uncharged merge buffer; partition and row order are unchanged.
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1989 tests** (1972 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
**1996 tests** (1979 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
41 changes: 41 additions & 0 deletions docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,47 @@

This document records reproducible local benchmark snapshots. Completed release-performance history belongs in the [CHANGELOG](../CHANGELOG.md); continuous CI history is available on [Bencher](https://bencher.dev/perf/minigraf/plots).

## Bounded recursive entity probes (#672, unreleased)

**Date**: 2026-10-28 · **Baseline**: `v3` at `d0ad89c1d` · **Machine**:
Intel Xeon E5-2696 v4, 88 logical CPUs, Rust 1.99.1. Baseline and change used
the same bench machine and fixture, with no other benchmark running. The
ignored 5M acceptance test ran once on the baseline and twice on the change
with `--profile bench`:

| Workload | Baseline | Change |
|---|---:|---:|
| `reach_5m`: 4,882,500 rows, 62 rounds | 302.66 s | 74.40 / 70.91 s (4.1–4.3× faster) |
| Added peak RSS per derived fact | 172 bytes | 172 / 165 bytes |

The 1M-fact [performance envelope](#performance-envelope-v300-394) used
`--profile envelope`. Four recursive pairs ran sequentially, alternating
baseline/change order. The table gives the mean of the four p50s; each
recursive process warmed three queries and timed five. The point shape has
three pairs. The [raw results](benchmarks/672-recursive-probes.jsonl) include
each process's peak RSS and row count.

| Shape | Baseline p50 | Change p50 | Difference |
|---|---:|---:|---:|
| `recursive`, 888,885 rows | 2,808.89 ms | 2,761.06 ms | -1.7% |
| `point_entity`, 1 row | 17.87 µs | 17.86 µs | within run-to-run noise |

The recursive shape's process peak RSS varied: the change was lower in the
first two pairs (360,080 → 358,948 KiB and 353,880 → 352,212 KiB) and higher
in the later two (338,916 → 351,808 KiB and 340,864 → 350,156 KiB). It does
not establish a memory improvement for this shape. The point query did not
use the new rule-query cache; its latency remains around 18 µs. The small
envelope latency delta is a direction check rather than a stable estimate of
speedup. The 5M test supplies the larger repeated-probe workload and its
query-specific added-RSS measurement.

To reproduce, build both revisions with `cargo build --profile envelope
--example perf_envelope`, build one 1M fixture with `perf_envelope __build`,
then run each executable with `__query fixture-1m.graph 11 8 60` for recursion
and `__query fixture-1m.graph 0 2 60` for the point lookup. The 5M command is
`cargo test --profile bench --test recursive_acceptance_test -- --ignored
--nocapture`. Builds and fixture creation are outside the timed phase.

## Partition-at-a-time windows (#641, slice 3, unreleased)

**Date**: 2026-10-28 · **Parent**: slice 2 at `e6670c82d` · **Change**: #641,
Expand Down
7 changes: 4 additions & 3 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -4,11 +4,11 @@

| | Default features | With `--features test-hooks` |
|---|---|---|
| **Passing** | 1,972 | 2,005 |
| **Passing** | 1,979 | 2,012 |
| **Ignored** | 17 | 18 |
| **Total** | 1,989 | 2,023 |
| **Total** | 1,996 | 2,030 |

**Verified**: 2026-10-28 on the designated bench machine: full default/test-hooks tests and the full branch-coverage suite pass, including golden files and migration/fault injection after sharing stable-sort code. Disabling internal reference-result cache eviction makes the targeted window regression fail. All unchanged coverage floors pass; measured overall coverage is 95.44% lines and 86.50% branches. Strict native/browser/WASI lint, WASI tests (1,182 passing, seven ignored), the WASI release build and Firefox tests (61 passing) also pass; the new committed-reader window fixture executes on both portable runners.
**Verified**: 2026-10-28 on the designated bench machine: full default/test-hooks tests and the full branch-coverage suite pass, including golden files and migration/fault injection after sharing stable-sort code. Disabling internal reference-result cache eviction makes the targeted window regression fail. All unchanged coverage floors pass; measured overall coverage is 95.44% lines and 86.50% branches. Strict native/browser/WASI lint, WASI tests (1,182 passing, seven ignored), the WASI release build and Firefox tests (61 passing) also pass; the new committed-reader window fixture executes on both portable runners. The #672 default and `test-hooks` suites passed separately on 2026-10-28 before rebasing onto #641.

#641 slice 1 adds 30 tests with default features and one more with `test-hooks`. Slice 2 adds 22 default-feature tests (21 active and one ignored committed-fixture memory diagnostic). Slice 3 adds 26 default-feature tests (25 active and one ignored committed-fixture memory diagnostic).

Expand Down Expand Up @@ -449,6 +449,7 @@ These tests compare the database against an independent answer rather than a sin
## Rules

- **Rule queries on the engine** (`tests/recursive_engine_test.rs`, 11 tests; #548)
- Seven engine unit tests for rule-query entity-probe reuse (#672) check one inner read for repeated entities, full answer bags through LRU eviction, other shared value bindings, keyword/ref normalization, a recursive inner relation across rounds, streaming above the 128-row cache bound, and successful streaming when the query memory limit refuses an optional cache entry. The nightly `reach_5m` acceptance test still checks 4,882,500 derived facts, RSS, and the default derived-fact limit.
- Linear and non-linear transitive closure, mutual recursion, and strata whose `not` and `or` rules recurse (#633's cases).
- Naive rules: a same-stratum read in an `or` branch, through a `:p` pattern, through `[?y ?a ?z]`.
- Derived facts visible to every pattern and to the magic-set predicate's attribute.
Expand Down
17 changes: 17 additions & 0 deletions docs/benchmarks/672-recursive-probes.jsonl
Original file line number Diff line number Diff line change
@@ -0,0 +1,17 @@
{"build":"baseline","commit":"d0ad89c1d","shape":"reach_5m","rows":4882500,"seconds":302.66,"added_rss_bytes_per_fact":172}
{"build":"change","round":1,"shape":"reach_5m","rows":4882500,"seconds":74.40,"added_rss_bytes_per_fact":172}
{"build":"change","round":2,"shape":"reach_5m","rows":4882500,"seconds":70.91,"added_rss_bytes_per_fact":165}
{"build":"baseline","round":1,"shape":"recursive","rows":888885,"p50_ms":2830.034095,"p99_ms":2861.556268,"peak_rss_kb":360080,"runs":5}
{"build":"change","round":1,"shape":"recursive","rows":888885,"p50_ms":2753.613952,"p99_ms":2793.423012,"peak_rss_kb":358948,"runs":5}
{"build":"change","round":2,"shape":"recursive","rows":888885,"p50_ms":2747.39619,"p99_ms":2794.835834,"peak_rss_kb":352212,"runs":5}
{"build":"baseline","round":2,"shape":"recursive","rows":888885,"p50_ms":2780.496812,"p99_ms":2798.735509,"peak_rss_kb":353880,"runs":5}
{"build":"baseline","round":3,"shape":"recursive","rows":888885,"p50_ms":2795.765073,"p99_ms":2822.804785,"peak_rss_kb":338916,"runs":5}
{"build":"change","round":3,"shape":"recursive","rows":888885,"p50_ms":2775.115592,"p99_ms":2786.297056,"peak_rss_kb":351808,"runs":5}
{"build":"change","round":4,"shape":"recursive","rows":888885,"p50_ms":2768.11864,"p99_ms":2790.291429,"peak_rss_kb":350156,"runs":5}
{"build":"baseline","round":4,"shape":"recursive","rows":888885,"p50_ms":2829.272449,"p99_ms":2875.240564,"peak_rss_kb":340864,"runs":5}
{"build":"baseline","round":1,"shape":"point_entity","rows":1,"p50_ms":0.018482,"p99_ms":0.035102,"peak_rss_kb":5276,"runs":200}
{"build":"change","round":1,"shape":"point_entity","rows":1,"p50_ms":0.017596,"p99_ms":0.02669,"peak_rss_kb":5288,"runs":200}
{"build":"change","round":2,"shape":"point_entity","rows":1,"p50_ms":0.01815,"p99_ms":0.041286,"peak_rss_kb":5088,"runs":200}
{"build":"baseline","round":2,"shape":"point_entity","rows":1,"p50_ms":0.017864,"p99_ms":0.046861,"peak_rss_kb":5284,"runs":200}
{"build":"baseline","round":3,"shape":"point_entity","rows":1,"p50_ms":0.017272,"p99_ms":0.033143,"peak_rss_kb":5288,"runs":200}
{"build":"change","round":3,"shape":"point_entity","rows":1,"p50_ms":0.017836,"p99_ms":0.031906,"peak_rss_kb":5292,"runs":200}
114 changes: 108 additions & 6 deletions src/query/engine/join.rs
Original file line number Diff line number Diff line change
Expand Up @@ -20,6 +20,11 @@ use std::sync::Arc;

type Row = Vec<Cell>;

/// A small bound on retained entity probes. A high-degree entity still uses
/// the streaming path; the cache is most useful for repeated narrow probes.
const CACHED_PROBES: usize = 64;
const CACHED_ROWS_PER_PROBE: usize = 128;

pub(crate) struct Join {
outer: Box<dyn Operator>,
inner: Scan,
Expand Down Expand Up @@ -55,6 +60,17 @@ struct Probe {
probing: bool,
matches: Vec<Row>,
next: usize,
cached: Option<usize>,
/// At most 64 entries, so lookup and LRU eviction stay bounded.
cache: Vec<CachedProbe>,
tick: u64,
}

struct CachedProbe {
entity: u64,
rows: Vec<Row>,
used: u64,
bytes: usize,
}

/// `HashJoin`: the table of the build side, the rows of the streamed side's
Expand Down Expand Up @@ -208,7 +224,7 @@ impl Join {
row: &[Cell],
k: usize,
ctx: &mut Ctx<'_>,
) -> Result<Option<(crate::graph::types::EntityId, Option<u64>)>> {
) -> Result<Option<(u64, crate::graph::types::EntityId, Option<u64>)>> {
let Some(key) = self.keys.get(k) else {
return Ok(None);
};
Expand All @@ -219,7 +235,87 @@ impl Join {
return Ok(None);
};
let uuid = ctx.ids.uuid(ctx.keys, e)?;
Ok(Some((uuid, ctx.ids.dict_eid(e))))
Ok(Some((e, uuid, ctx.ids.dict_eid(e))))
}

/// Start an entity probe, retaining its rows only when the scan is small.
/// Cached rows belong to this join instance, whose snapshot and derived
/// relation are fixed until it is rewound.
#[inline(never)]
fn start_entity_probe(
&mut self,
p: &mut Probe,
entity: u64,
uuid: crate::graph::types::EntityId,
eid: Option<u64>,
ctx: &mut Ctx<'_>,
) -> Result<()> {
p.next = 0;
p.matches.clear();
if ctx.derived.is_some() {
p.tick = p.tick.wrapping_add(1);
if let Some((at, entry)) = p
.cache
.iter_mut()
.enumerate()
.find(|(_, entry)| entry.entity == entity)
{
entry.used = p.tick;
p.cached = Some(at);
p.probing = false;
return Ok(());
}
}

self.inner.probe(uuid, eid);
p.probing = true;
// Reuse is for rule queries. Ordinary joins keep their original
// streaming probe path, including many-distinct-entity joins.
if ctx.derived.is_none() {
return Ok(());
}
while p.matches.len() <= CACHED_ROWS_PER_PROBE {
match self.inner.next_batch(ctx)? {
Some(batch) => {
p.matches.extend(rows(&batch));
if p.matches.len() > CACHED_ROWS_PER_PROBE {
return Ok(());
}
}
None => break,
}
}

// Vec's geometric growth uses at most four slots per live entry,
// including its four-slot minimum allocation.
let bytes = 4 * size_of::<CachedProbe>()
+ p.matches.iter().map(|row| row_bytes(row)).sum::<usize>()
+ (p.matches.capacity() - p.matches.len()) * size_of::<Row>();
// A cache is optional: a tight query memory limit still takes the
// streaming path. Scan is fused after Done, so it advances the outer
// row once the already-read matches drain.
if self.held.charge(bytes).is_err() {
return Ok(());
}
if p.cache.len() == CACHED_PROBES
&& let Some((oldest, _)) = p
.cache
.iter()
.enumerate()
.min_by_key(|(_, entry)| entry.used)
{
let entry = p.cache.swap_remove(oldest);
self.held.uncharge(entry.bytes);
}
p.cache.push(CachedProbe {
entity,
rows: std::mem::take(&mut p.matches),
used: p.tick,
bytes,
});
p.cached = Some(p.cache.len() - 1);
p.probing = false;
Ok(())
}

/// Whether `outer` and `inner` agree on every key but the probed one,
Expand Down Expand Up @@ -259,11 +355,18 @@ impl Join {
let skip = (!by_value).then_some(probed);
while out.len < BATCH_ROWS {
if let Some(o) = p.rows.get(p.at) {
if let Some(m) = p.matches.get(p.next) {
let matched = p
.cached
.and_then(|at| p.cache.get(at))
.and_then(|entry| entry.rows.get(p.next))
.or_else(|| p.matches.get(p.next));
if let Some(m) = matched {
p.next += 1;
if self.agree(o, m, skip, ctx)? {
self.emit(o, m, out);
}
} else if p.cached.take().is_some() {
p.at += 1;
} else if p.probing {
match self.inner.next_batch(ctx)? {
Some(b) => p.matches = rows(&b),
Expand All @@ -287,9 +390,8 @@ impl Join {
}
} else {
match self.probe_of(o, probed, ctx)? {
Some((uuid, eid)) => {
self.inner.probe(uuid, eid);
p.probing = true;
Some((entity, uuid, eid)) => {
self.start_entity_probe(p, entity, uuid, eid, ctx)?
}
None => p.at += 1,
}
Expand Down
Loading
Loading