From c889b1631198f11779a6691af1368739274b27bf Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 28 Oct 2026 20:34:51 +0530 Subject: [PATCH] perf(engine): cache narrow entity probes in recursive joins (#672) --- CHANGELOG.md | 4 + CLAUDE.md | 2 +- docs/BENCHMARKS.md | 41 ++++ docs/TEST_COVERAGE.md | 7 +- docs/benchmarks/672-recursive-probes.jsonl | 17 ++ src/query/engine/join.rs | 114 ++++++++- src/query/engine/tests.rs | 273 +++++++++++++++++++++ 7 files changed, 448 insertions(+), 10 deletions(-) create mode 100644 docs/benchmarks/672-recursive-probes.jsonl diff --git a/CHANGELOG.md b/CHANGELOG.md index 79b41a2465..1bc980f61b 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -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. diff --git a/CLAUDE.md b/CLAUDE.md index 4fc73b8e4d..497b5d074c 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -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. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index f5462a0d24..b65da4cae9 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -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, diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 1f275798d5..711a569d95 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -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). @@ -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. diff --git a/docs/benchmarks/672-recursive-probes.jsonl b/docs/benchmarks/672-recursive-probes.jsonl new file mode 100644 index 0000000000..4ad79edc93 --- /dev/null +++ b/docs/benchmarks/672-recursive-probes.jsonl @@ -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} diff --git a/src/query/engine/join.rs b/src/query/engine/join.rs index 6ff6401cb1..6eabe79553 100644 --- a/src/query/engine/join.rs +++ b/src/query/engine/join.rs @@ -20,6 +20,11 @@ use std::sync::Arc; type Row = Vec; +/// 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, inner: Scan, @@ -55,6 +60,17 @@ struct Probe { probing: bool, matches: Vec, next: usize, + cached: Option, + /// At most 64 entries, so lookup and LRU eviction stay bounded. + cache: Vec, + tick: u64, +} + +struct CachedProbe { + entity: u64, + rows: Vec, + used: u64, + bytes: usize, } /// `HashJoin`: the table of the build side, the rows of the streamed side's @@ -208,7 +224,7 @@ impl Join { row: &[Cell], k: usize, ctx: &mut Ctx<'_>, - ) -> Result)>> { + ) -> Result)>> { let Some(key) = self.keys.get(k) else { return Ok(None); }; @@ -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, + 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::() + + p.matches.iter().map(|row| row_bytes(row)).sum::() + + (p.matches.capacity() - p.matches.len()) * size_of::(); + // 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, @@ -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), @@ -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, } diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 4b707db6fd..6c429eeb0b 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -953,6 +953,279 @@ fn planner_chooses_the_join() { ); } +/// #672: repeated bound entities reuse a small inner scan in a rule query. +#[test] +fn entity_probe_reuses_repeated_entities() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + let outer: String = (0..100).map(|i| format!("[:x{i} :outer :hub]")).collect(); + db.execute(&format!( + "(transact [{outer} [:hub :edge :a] [:hub :edge :b] [:hub :edge :c] [:hub :edge :d]])" + )) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x ?z :where (source ?x ?mid) [?mid :edge ?z]])") + .unwrap(); + let meter = cursor.stream_mut().unwrap().meter().clone(); + let batch = cursor.next_batch(400).unwrap().expect("all rows"); + let mut got = batch.rows().to_vec(); + let mut expected: Vec> = (0..100) + .flat_map(|i| { + [":a", ":b", ":c", ":d"].into_iter().map(move |z| { + vec![ + crate::Value::Ref(uuid_of(&format!(":x{i}"))), + crate::Value::Keyword(z.into()), + ] + }) + }) + .collect(); + let cmp = |a: &Vec, b: &Vec| { + a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal) + }; + got.sort_by(cmp); + expected.sort_by(cmp); + assert!( + got == expected, + "every outer entity has all four edges once" + ); + let counters = cursor.counters(); + assert!(counters.iter().any(|c| c.op == "IndexNestedLoopJoin")); + let read: u64 = counters + .iter() + .filter(|c| c.op == "Scan") + .map(|c| c.rows_in) + .sum(); + assert!(read < 130, "the inner entity is read once per join"); + assert!(cursor.next_batch(1).unwrap().is_none(), "no extra rows"); + cursor.close(); + assert_eq!(meter.used(), 0, "cached rows are released on close"); +} + +#[test] +fn entity_probe_cache_evicts_without_losing_rows() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + let facts: String = (0..70) + .map(|i| { + format!( + "[:a{i} :outer :hub{i}] [:b{i} :outer :hub{i}] [:hub{i} :edge :one] [:hub{i} :edge :two]" + ) + }) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x ?z :where (source ?x ?mid) [?mid :edge ?z]])") + .unwrap(); + let mut got = Vec::new(); + while let Some(batch) = cursor.next_batch(100).unwrap() { + got.extend(batch.rows().iter().cloned()); + } + let mut expected: Vec> = (0..70) + .flat_map(|i| { + [format!(":a{i}"), format!(":b{i}")] + .into_iter() + .flat_map(move |e| { + [":one", ":two"].into_iter().map(move |z| { + vec![ + crate::Value::Ref(uuid_of(&e)), + crate::Value::Keyword(z.into()), + ] + }) + }) + }) + .collect(); + let cmp = |a: &Vec, b: &Vec| { + a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal) + }; + got.sort_by(cmp); + expected.sort_by(cmp); + assert!(got == expected, "eviction preserves every answer once"); +} + +#[test] +fn cached_entity_probe_checks_other_shared_values() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact [[:a :outer :hub] [:a :wanted :one] \ + [:b :outer :hub] [:b :wanted :two] \ + [:hub :edge :one] [:hub :edge :two]])", + ) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x ?z :where (source ?x ?mid) [?x :wanted ?z] [?mid :edge ?z]])") + .unwrap(); + let mut got = Vec::new(); + while let Some(batch) = cursor.next_batch(10).unwrap() { + got.extend(batch.rows().iter().cloned()); + } + let mut expected = vec![ + vec![ + crate::Value::Ref(uuid_of(":a")), + crate::Value::Keyword(":one".into()), + ], + vec![ + crate::Value::Ref(uuid_of(":b")), + crate::Value::Keyword(":two".into()), + ], + ]; + let cmp = |a: &Vec, b: &Vec| { + a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal) + }; + got.sort_by(cmp); + expected.sort_by(cmp); + assert!(got == expected, "each outer value matches its own edge"); +} + +#[test] +fn cached_entity_probe_normalizes_keyword_and_ref() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + let hub = uuid_of(":hub"); + db.execute(&format!( + "(transact [[:a :outer :hub] [:b :outer #uuid \"{hub}\"] [:hub :edge :z]])" + )) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x :where (source ?x ?mid) [?mid :edge :z]])") + .unwrap(); + let batch = cursor.next_batch(2).unwrap().expect("two rows"); + assert_eq!(batch.len(), 2, "keyword and ref both name the hub"); + let read: u64 = cursor + .counters() + .iter() + .filter(|c| c.op == "Scan") + .map(|c| c.rows_in) + .sum(); + assert!(read <= 3, "the normalized entity uses one inner scan"); +} + +#[test] +fn cached_entity_probe_reads_recursive_inner_relation() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact [[:a :outer :hub] [:b :outer :hub] \ + [:hub :edge :one] [:one :edge :two] [:two :edge :three]])", + ) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :edge ?y]])").unwrap(); + db.execute("(rule [(reach ?x ?z) [?x :edge ?y] (reach ?y ?z)])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x ?z :where (source ?x ?mid) (reach ?mid ?z)])") + .unwrap(); + let mut got = Vec::new(); + while let Some(batch) = cursor.next_batch(10).unwrap() { + got.extend(batch.rows().iter().cloned()); + } + let mut expected: Vec> = [":a", ":b"] + .into_iter() + .flat_map(|e| { + [":one", ":two", ":three"].into_iter().map(move |z| { + vec![ + crate::Value::Ref(uuid_of(e)), + crate::Value::Keyword(z.into()), + ] + }) + }) + .collect(); + let cmp = |a: &Vec, b: &Vec| { + a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal) + }; + got.sort_by(cmp); + expected.sort_by(cmp); + assert_eq!(got.len(), 6, "all three recursive levels are present twice"); + assert!(got == expected, "the later recursive rounds stay visible"); +} + +#[test] +fn rule_entity_probe_streams_high_degree_entities() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let db = Minigraf::in_memory().unwrap(); + let edges: String = (0..130).map(|i| format!("[:hub :edge :z{i}]")).collect(); + db.execute(&format!( + "(transact [[:a :outer :hub] [:b :outer :hub] {edges}])" + )) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?x ?z :where (source ?x ?mid) [?mid :edge ?z]])") + .unwrap(); + let mut got = Vec::new(); + while let Some(batch) = cursor.next_batch(100).unwrap() { + got.extend(batch.rows().iter().cloned()); + } + let mut expected: Vec> = [":a", ":b"] + .into_iter() + .flat_map(|e| { + (0..130).map(move |i| { + vec![ + crate::Value::Ref(uuid_of(e)), + crate::Value::Keyword(format!(":z{i}")), + ] + }) + }) + .collect(); + let cmp = |a: &Vec, b: &Vec| { + a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal) + }; + got.sort_by(cmp); + expected.sort_by(cmp); + assert!(got == expected, "uncached streaming preserves every row"); +} + +#[test] +fn optional_probe_cache_respects_query_memory_limit() { + let _off = crate::query::datalog::optimizer::set_reorder(false); + let setup = |limit| { + let db = crate::OpenOptions::new() + .query_memory_limit(limit) + .open_memory() + .unwrap(); + let edges: String = (0..100).map(|i| format!("[:hub :edge {i}]")).collect(); + db.execute(&format!( + "(transact [[:a :outer :hub] [:b :outer :hub] {edges}])" + )) + .unwrap(); + db.execute("(rule [(source ?x ?mid) [?x :outer ?mid]])") + .unwrap(); + db + }; + let query = "(query [:find ?x :where (source ?x ?mid) [?mid :edge ?z]])"; + let db = setup(usize::MAX); + let mut cursor = db.query(query).unwrap(); + let base = cursor.stream_mut().unwrap().meter().used(); + drop(cursor); + + let db = setup(base + 2_000); + let mut cursor = db.query(query).unwrap(); + let first = cursor.next_batch(1).unwrap().expect("first row"); + assert_eq!(first.len(), 1); + let join = cursor + .counters() + .into_iter() + .find(|c| c.op == "IndexNestedLoopJoin") + .expect("entity join"); + assert_eq!(join.bytes_held, 0, "optional cache was refused"); + let mut count = 1; + while let Some(batch) = cursor.next_batch(100).unwrap() { + count += batch.len(); + } + assert_eq!(count, 200, "all rows stream after cache refusal"); +} + #[test] fn planner_binds_checks_or_replaces_an_expression_output() { use super::plan::{Out, Step, plan};