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
19 changes: 19 additions & 0 deletions .github/workflows/smoke.yml
Original file line number Diff line number Diff line change
Expand Up @@ -47,3 +47,22 @@ jobs:
run: cargo test --profile bench --test recursive_acceptance_test -- --ignored --nocapture
env:
RUST_BACKTRACE: 1

# #549 / #575: 1M aggregate groups complete or stop with QRY-012 under a
# limit; a 13-pattern cartesian product streams in a few MiB. Without
# test-oracle: the executor would run out of memory on the product.
memory-limit-acceptance:
name: Query memory limit acceptance
runs-on: ubuntu-latest
timeout-minutes: 30

steps:
- uses: actions/checkout@v4

- name: Install Rust stable
uses: dtolnay/rust-toolchain@stable

- name: Run the acceptance tests
run: cargo test --profile bench --test memory_limit_acceptance_test -- --ignored --nocapture --test-threads=1
env:
RUST_BACKTRACE: 1
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -120,6 +120,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off.
- **Rule queries on the engine (#548).** `tests/recursive_engine_test.rs` (10 tests) runs rule queries in memory, on a file with pending facts and after a checkpoint, and under `test-oracle` against the executor: transitive closure (linear and non-linear), mutual recursion, strata whose `not` and `or` rules recurse, rules that read their stratum outside a top-level invocation, derived facts seen by every pattern, the identity of derived facts, `nil` metadata, heads, both `INT-020` limits, and rule queries with aggregates, `not-join`, `or` and windows. Every existing rule suite (`recursive_rules_test`, `negation_test`, `disjunction_test`, `magic_sets_test`, the model-based and property tests) now runs its rule queries on the engine with the oracle. Engine unit tests cover routing and derived rows read across batches.
- **Recursive rules at 5M derived facts (#473 acceptance, #548).** `tests/recursive_acceptance_test.rs` (ignored; the nightly smoke workflow runs it) derives 4,882,500 `reach` facts in 62 rounds over a layered graph of 155,000 edges and checks that every one is returned and that the query's peak RSS stays under 256 bytes per derived fact (169 measured); the default `max_derived_facts` then stops the same rule with `INT-020`. The #394 envelope has a `recursive` shape: the whole transitive closure of `:manager`, with no constant, so no magic sets.
- **Query memory at 1M groups and on the #575 product (#549).** `tests/memory_limit_acceptance_test.rs` (ignored; the nightly smoke workflow runs it without `test-oracle`) returns 1M aggregate groups, or `QRY-012` naming `Aggregate` under a 32 MiB limit, and streams the 1.6M rows of 13 patterns sharing no variable over the fuzz harness's 3 facts in under 64 MiB of peak RSS (the executor held more than 5.7 GB), or `QRY-012` naming `HashJoin` under a 64-byte limit. An ignored engine test prints the meter's peak against the peak RSS: 435 MiB against about 545 MiB for the groups (`docs/BENCHMARKS.md`). Measuring it found `Aggregate`'s sorted map of groups uncharged while its hash table was still held; the map is now charged and the table freed first, which lowered the real peak from 651 MiB.
- **Negation bodies in both forms (#546).** A second test-only switch (`minigraf::__subplans`, `test-oracle` feature) forces the engine's `not` / `not-join` bodies to run hashed or correlated. `tests/plan_independence_test.rs` runs every query with the body forms chosen, forced hashed and forced correlated, each with reordering on and off; its matrix gains negations over floats near zero, `0.0` and `-0.0`, keywords and refs of one entity, long strings, bodies reading an imported variable they do not bind, variable-free bodies and `:db/valid-at`. `tests/negation_equality_test.rs` checks the changed answers on every executor path, in memory and after a checkpoint. The property test's rerun also forces hashed bodies. Engine unit tests cover the form the planner picks, routing, multiplicity, failing expressions in bodies, and that a hashed body is read once and a correlated one probes once per row.
- **Disjunctions (#546).** `tests/or_equality_test.rs` checks the changed `or` / `or-join` answers through `execute` and a cursor, in memory and after a checkpoint. `tests/plan_independence_test.rs` gains disjunctions (keywords meeting refs, floats near zero, long strings as keys, branches naming different outer variables or no join variable, a branch with `not`, an `or` with nothing before it, a cross product, `:db/valid-at` in a branch), run with branches chosen, forced hashed and forced correlated. The property test generates `or` and `or-join` over bound variables, with a reference evaluator that deduplicates the rows they keep. Engine unit tests run every disjunction shape with each branch form forced against the executor, and cover routing, the form the planner picks, `Distinct`, and that a hashed branch is read once.
- **Aggregates and windows (#547).** `src/query/datalog/aggregate.rs` unit tests check every accumulator over every order of small inputs (exact float sums against hand-computed values, cancellation, subnormals, signed zeros, infinities and NaN, integer saturation, errors decided at the end) and that the value order is total. `tests/aggregate_window_rules_test.rs` checks the changed answers; `tests/plan_independence_test.rs` gains aggregate, window and mixed queries over ties, keywords and refs, and floats.
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -206,7 +206,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1720 tests** (1709 passing, 11 ignored; unit + integration + doc).
**1725 tests** (1711 passing, 14 ignored; unit + integration + doc).
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
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1720 tests
cargo test # run 1725 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
13 changes: 13 additions & 0 deletions docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -171,6 +171,19 @@ The executor copied the database into a `FactStorage` for every rule query; the

The acceptance test (`tests/recursive_acceptance_test.rs`, ignored; the nightly smoke workflow runs it) derives 4,882,500 `reach` facts over a layered graph of 155,000 edges (63 layers of 50 nodes, complete bipartite between neighbours) in 62 rounds: 226 s and 169 bytes of RSS per derived fact on a laptop. Each fact is derived through 50 middle nodes, so the rounds probe about 250M candidate rows; the time is in those entity probes and the identity set, not in memory.

### Query memory accounting (#549)

**Command**: `cargo test --profile bench --test memory_limit_acceptance_test -- --ignored --nocapture --test-threads=1` (the nightly smoke workflow runs it) and `cargo test --profile bench --lib meter_peak_against_rss -- --ignored --nocapture`, on a dedicated 88-vCPU Linux server, pinned to one NUMA node, three runs each.

| Shape | Rows | Time | Meter peak | Peak RSS added |
|---|---:|---:|---:|---:|
| 1M groups, `[:find ?g (count ?e) :where [?e :g ?g]]` | 1,000,000 | 3.5–3.6 s | 435 MiB | 542–549 MiB |
| #575 cartesian, 13 patterns sharing no variable over 3 facts | 1,594,323 | 2.6 s | 4 KiB | 9.6–9.7 MiB in a fresh process; under 50 KiB after another query |

The meter's estimate is within the spec's factor of two of the RSS a query adds (1.25× for the groups). The rest is allocator rounding, hash-table capacity beyond its entries, and the reader's pages, which no holder counts. The cartesian product held more than 5.7 GB on the executor (#575); on the engine every join builds on its 3-row inner pattern and the 1.6M rows stream through, so what a fresh process adds is the reader and the cursor, not the rows. With `query_memory_limit` at 32 MiB the groups query stops with `QRY-012` naming `Aggregate`, and at 64 bytes the product stops with `QRY-012` naming `HashJoin`.

Measuring this found that `Aggregate` built its sorted map of groups uncharged while its hash table was still alive: the meter read 282 MiB against 651 MiB of RSS. The map is now charged, and the table goes first, which also cut the real peak to the figure above.

### Python FFI round trip

**Command**: `python bench/envelope.py <fixture> --report envelope.json --scale <scale>` in [minigraf-python](https://github.com/project-minigraf/minigraf-python) (`v3`), on the same fixtures and report. The binding is built with `maturin develop --release` against this commit. It runs the same queries through `db.query(...)`, drains them with `next_batch(1000)`, and decodes each JSON batch with `json.loads`. Python 3.14.7.
Expand Down
8 changes: 5 additions & 3 deletions docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

6 changes: 6 additions & 0 deletions src/db.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1102,6 +1102,12 @@ impl Minigraf {
self.inner.fact_storage.current_tx_count()
}

/// One state of the store, for tests that open the engine directly.
#[cfg(test)]
pub(crate) fn snapshot(&self) -> Result<Snapshot> {
self.inner.fact_storage.snapshot()
}

/// End the handle as a killed process would: no close-time checkpoint and
/// no save on drop. Whatever reached the file stays; the lock is released.
#[cfg(all(test, not(target_arch = "wasm32")))]
Expand Down
34 changes: 31 additions & 3 deletions src/query/engine/aggregate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -74,6 +74,18 @@ impl Acc {
}

/// The accumulator as an [`Agg`], whose `finish` gives its result.
/// The bytes `step` charged for the members of a set that stays in the
/// `Agg`: `sum-distinct`'s. A `count-distinct` set ends as its count.
fn member_bytes(&self) -> usize {
match self {
Acc::Values(Agg::SumDistinct(set)) => set
.iter()
.map(|v| value_bytes(v) + HASH_ENTRY_OVERHEAD)
.sum(),
_ => 0,
}
}

fn into_agg(self) -> Agg {
match self {
Acc::Count(n) => Agg::Count(n),
Expand Down Expand Up @@ -206,18 +218,34 @@ impl Aggregate {
row.extend(vec![Cell::Val(Scalar::Int(0)); self.aggs.len()]);
return Ok(vec![row]);
}
// Sorted and finished as the executor's groups are.
// Sorted and finished as the executor's groups are. The sorted map
// holds each group's values twice and its accumulators, with their
// `sum-distinct` members, until every row is built, so it is charged
// as `finished` too.
self.table = HashMap::new();
let mut groups = Groups::new();
let mut sorted = 0;
for group in std::mem::take(&mut self.rows) {
let values = group
.cells
.iter()
.map(|c| value(c, ctx))
.collect::<Result<Vec<Value>>>()?;
let members: usize = group.accs.iter().map(Acc::member_bytes).sum();
let n = 2 * (size_of::<Vec<Value>>() + values.iter().map(value_bytes).sum::<usize>())
+ size_of::<Vec<Agg>>()
+ group.accs.len() * size_of::<Agg>()
+ members
+ HASH_ENTRY_OVERHEAD;
// The members move from `held` to `finished`, so they are not
// counted twice.
self.held.uncharge(members);
self.finished.charge(n)?;
sorted += n;
let accs = group.accs.into_iter().map(Acc::into_agg).collect();
groups.insert(values.clone(), (values, accs));
}
self.table.clear();
self.held.release();
let funcs: Vec<&str> = self.aggs.iter().map(|(f, _)| f.as_str()).collect();
let mut rows = Vec::new();
for (shown, results) in finish_groups(groups, &funcs)? {
Expand All @@ -232,7 +260,7 @@ impl Aggregate {
self.finished.reserve(rows.try_reserve(1), n, refused)?;
rows.push(row);
}
self.held.release();
self.finished.uncharge(sorted);
rows.reverse();
Ok(rows)
}
Expand Down
151 changes: 151 additions & 0 deletions src/query/engine/tests.rs
Original file line number Diff line number Diff line change
Expand Up @@ -2191,3 +2191,154 @@ fn planner_builds_a_keyless_join_on_the_smaller_product() {
"reorder off builds inner"
);
}

/// The two acceptance shapes of `tests/memory_limit_acceptance_test.rs`:
/// a checkpointed database at `path`, and the query.
fn acceptance_shape(name: &str, path: &std::path::Path) -> String {
let db = Minigraf::open(path).unwrap();
if name == "groups" {
for chunk in 0..10 {
let facts: String = (chunk * 100_000..(chunk + 1) * 100_000)
.map(|i| format!("[:e{i} :g {i}]"))
.collect();
db.execute(&format!("(transact [{facts}])")).unwrap();
db.checkpoint().unwrap();
}
"(query [:find ?g (count ?e) :where [?e :g ?g]])".to_string()
} else {
db.execute(r#"(transact [[:alice :name "Alice"] [:bob :name "Bob"] [:alice :age 30]])"#)
.unwrap();
db.checkpoint().unwrap();
let patterns: String = (0..13).map(|i| format!("[?e{i} ?a{i} ?v{i}]")).collect();
format!("(query [:find ?v0 :where {patterns}])")
}
}

/// A `kB` field of `/proc/self/status`; 0 where it does not exist.
fn proc_status_kb(field: &str) -> usize {
std::fs::read_to_string("/proc/self/status")
.ok()
.and_then(|s| {
s.lines()
.find_map(|l| l.strip_prefix(field)?.strip_prefix(':').map(str::to_owned))
})
.and_then(|v| v.trim().trim_end_matches("kB").trim().parse().ok())
.unwrap_or(0)
}

/// The meter's peak against the peak RSS the query adds, for both
/// acceptance shapes (#549 spec §3.2: the estimate is meant to be within a
/// factor of two). Opens the engine directly, without the executor oracle,
/// which would run out of memory on the cartesian shape. Prints only; run
/// alone, as the high-water mark is per process:
///
/// ```text
/// cargo test --profile bench --lib meter_peak_against_rss -- --ignored --nocapture
/// ```
#[test]
#[ignore]
fn meter_peak_against_rss() {
use crate::query::datalog::functions::FunctionRegistry;
use crate::query::datalog::parser::parse_datalog_command;
use crate::query::datalog::types::DatalogCommand;
for name in ["groups", "cartesian"] {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("shape.graph");
let query = acceptance_shape(name, &path);
let db = Minigraf::open(&path).unwrap();
let Ok(DatalogCommand::Query(query)) = parse_datalog_command(&query) else {
panic!("expected a query");
};
let plan = super::plan(&query).expect("an engine plan");
let functions =
std::sync::Arc::new(std::sync::RwLock::new(FunctionRegistry::with_builtins()));
let snapshot = db.snapshot().unwrap();
let reset = std::fs::write("/proc/self/clear_refs", "5").is_ok();
let before_kb = proc_status_kb("VmRSS");
let mut stream =
super::open(snapshot, plan, functions, usize::MAX).expect("the engine runs it");
let meter = stream.meter().clone();
let mut rows = 0;
while let Some(batch) = stream.next_rows().unwrap() {
rows += batch.len();
}
drop(stream);
let added_kb = proc_status_kb("VmHWM").saturating_sub(before_kb);
eprintln!(
"{name}: {rows} rows; meter peak {} KiB, peak RSS added {added_kb} KiB{}",
meter.peak() / 1024,
if reset {
""
} else {
" (high-water mark not reset)"
}
);
assert_eq!(meter.used(), 0, "released after the drain");
}
}

/// `Aggregate::finish` charges its sorted map of groups until every row is
/// built, and lets the hash table and group rows go first, so once rows are
/// returned only the ones not yet returned stay charged (#549).
#[test]
fn aggregate_finish_charges_its_sorted_groups() {
use super::meter::{HASH_ENTRY_OVERHEAD, row_bytes, value_bytes};
use crate::graph::types::Value;
use crate::query::datalog::aggregate::Agg;
use std::mem::size_of;
let n = 3000;
let meter = super::Meter::unlimited();
let mut aggregate = super::aggregate::Aggregate::new(
Box::new(Ints { n, at: 0 }),
vec![0],
vec![("count".to_string(), 0)],
false,
&meter,
);
let batch = pull_once(&mut aggregate, &meter).unwrap().expect("a batch");
let row = [
super::cell::Cell::Val(super::cell::Scalar::Int(0)),
super::cell::Cell::Val(super::cell::Scalar::Int(1)),
];
let n = usize::try_from(n).unwrap();
assert_eq!(
meter.used(),
(n - batch.len) * row_bytes(&row),
"only the rows not yet returned"
);
let sorted = 2 * (size_of::<Vec<Value>>() + value_bytes(&Value::Integer(0)))
+ size_of::<Vec<Agg>>()
+ size_of::<Agg>()
+ HASH_ENTRY_OVERHEAD;
assert!(
meter.peak() >= n * (sorted + row_bytes(&row)),
"the sorted groups and the finished rows at once"
);
}

/// A `sum-distinct` set's members stay charged once, in the sorted map,
/// until the rows are built (#549).
#[test]
fn aggregate_finish_keeps_sum_distinct_members_charged_once() {
use super::meter::row_bytes;
let n = 3000;
let meter = super::Meter::unlimited();
let mut aggregate = super::aggregate::Aggregate::new(
Box::new(Ints { n, at: 0 }),
vec![],
vec![("sum-distinct".to_string(), 0)],
false,
&meter,
);
pull_once(&mut aggregate, &meter).unwrap().expect("a batch");
assert_eq!(meter.used(), 0, "the one row returned, nothing held");
let members = usize::try_from(n).unwrap()
* (super::meter::value_bytes(&crate::graph::types::Value::Integer(0))
+ super::meter::HASH_ENTRY_OVERHEAD);
let row = [super::cell::Cell::Val(super::cell::Scalar::Int(0))];
assert!(meter.peak() >= members, "members charged");
assert!(
meter.peak() < 2 * members + row_bytes(&row),
"members not counted twice"
);
}
Loading
Loading