From 710fb56db74940eccb2fcd4cd7050a0802dc7bfd Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 11 Oct 2026 11:04:27 +0530 Subject: [PATCH] fix(query): count only derived facts against max_results (#528) Backport of the v3 fix (#534) to v2.x. RecursiveEvaluator seeded seen_facts with every base fact and compared its size with max_results, so on a database with max_results (default 1,000,000) live facts every rule query failed with INT-020 at its first derived fact, whatever the size of its answer. The limit now counts only the facts the rules derive. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/ERROR_REFERENCE.md | 3 ++- docs/TEST_COVERAGE.md | 4 ++-- src/db.rs | 8 +++++--- src/query/datalog/evaluator.rs | 10 ++++++---- tests/recursive_rules_test.rs | 35 ++++++++++++++++++++++++++++++++++ 8 files changed, 53 insertions(+), 12 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 4938b401a..8194d88db 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -11,6 +11,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **A file shorter than one page is refused at open with `STG-045` unless it is a torn first write (#506).** Open treated any file under 4 KiB as a new database and wrote a new header over it, so a database cut below one page by an interrupted copy, or an unrelated file at the path, was silently replaced. Such a file now opens as a new database only when its bytes are zeros or a prefix of the header a new database writes (what a crash during creation can leave); anything else is `STG-045` and the file is not modified. A zero-length file is still a new database. New code `STG-045`, numbered as in v3.0.0, which also fixes this. - **A commit made after a torn WAL entry is no longer lost on recovery (#513).** Recovery replays the WAL up to its first partial or damaged entry, but the writer appended after the end of the file. After a crash during an append, the next session's commits went in after the partial entry, so a second crash before any checkpoint lost them, although each had been fsynced and reported as committed. A failed append (short write, full disk, I/O error) did the same to the next commit through that handle. Opening a database for writing now cuts the WAL back to the end of its last valid entry, and syncs it, before anything is appended. After a failed append, every later write through that handle fails with the new `WAL-007` until the database is reopened or a `checkpoint()` succeeds. The transaction whose append failed is not applied; after a reopen it is there in full or not at all. Affected every release since v0.5.0. Also fixed in v3.0.0. +- **Rule queries no longer fail with `INT-020` on databases with 1,000,000 or more live facts (#528).** The recursive evaluator counted the database's own facts against `max_results`, so once a database held that many live facts, every rule query failed at its first derived fact, whatever the size of its answer. `max_results` now counts only the facts the rules derive, so raising it with `OpenOptions::max_results` or `:max-results` is no longer needed. Affected every release since v0.18.0. Also fixed in v3.0.0. ### Tests diff --git a/CLAUDE.md b/CLAUDE.md index 22d8885b1..63d02547b 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1237 tests** (1228 passing, 9 ignored; unit + integration + doc). +**1238 tests** (1229 passing, 9 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. diff --git a/README.md b/README.md index 352ad4bd1..5a5222f6d 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1237 tests +cargo test # run 1238 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index c94de6a9e..aaa774af9 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -2540,7 +2540,8 @@ similar). The `{}` carries the specific underlying message. **Cause**: The recursive rule evaluator (semi-naive evaluation) exceeded its maximum iteration count, maximum derived facts per iteration, or maximum -query result count — guards against infinite recursion/cycles or +number of facts derived in total (`max_results`; the database's own facts do +not count) — guards against infinite recursion/cycles or runaway-generating rules. **Resolution**: diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index fb0d91981..399602210 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-10 with `cargo test` -**Result**: 1,228 passing tests and 9 ignored tests (1,237 total), including the golden-file corpus (#391) +**Result**: 1,229 passing tests and 9 ignored tests (1,238 total), including the golden-file corpus (#391) Since v2.0.4, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). @@ -16,7 +16,7 @@ Since v2.0.4, torn-WAL-tail tests (#513) check that opening a WAL writer cuts of Not counted above: the `BrowserDb` tests run only on wasm32 with `wasm-bindgen-test` in a browser. Two of them check that the IndexedDB flush returns every page a write dirtied, and that a dirty page that cannot be read is an error rather than left out. -The v2.0.4 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). For v2.0.3, storage unit tests and two `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). A WAL test reopens a database next to a WAL whose entries are all checkpointed, writes again, and checks that `:as-of` history is unchanged before and after another reopen; a unit test checks that restoring the transaction counter never lowers it (#447). Since v2.0.3, `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). +The v2.0.4 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). For v2.0.3, storage unit tests and two `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). A WAL test reopens a database next to a WAL whose entries are all checkpointed, writes again, and checks that `:as-of` history is unchanged before and after another reopen; a unit test checks that restoring the transaction counter never lowers it (#447). Since v2.0.3, `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). A recursive-rules test runs rule queries on a database with more live facts than `max_results` and checks that they answer, and that the limit still stops a rule that derives more facts than it allows (#528). ### Covered Areas diff --git a/src/db.rs b/src/db.rs index d0128a085..541dd8ba5 100644 --- a/src/db.rs +++ b/src/db.rs @@ -128,7 +128,8 @@ pub struct OpenOptions { /// Maximum facts that can be derived per recursive rule iteration. /// Defaults to 1_000_000. Use to prevent runaway recursive rules. pub max_derived_facts: usize, - /// Maximum total query results. Defaults to 1_000_000. + /// Maximum facts a rule query may derive. Defaults to 1_000_000. + /// The database's own facts do not count against it. pub max_results: usize, /// Open even when the filesystem cannot lock files at all. /// @@ -199,9 +200,10 @@ impl OpenOptions { self } - /// Set the maximum total query results. + /// Set the maximum number of facts a rule query may derive. /// - /// Defaults to 1_000_000. Use lower values to limit result set size. + /// Defaults to 1_000_000. The database's own facts do not count against it, + /// and queries without rules are not limited by it. pub fn max_results(mut self, n: usize) -> Self { self.max_results = n; self diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 7e58d225c..3dfd10ade 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -68,7 +68,7 @@ pub struct RecursiveEvaluator { max_iterations: usize, /// Maximum facts that can be derived per iteration max_derived_facts: usize, - /// Maximum total query results + /// Maximum facts the rules may derive in one evaluation; base facts do not count max_results: usize, } @@ -81,7 +81,7 @@ impl RecursiveEvaluator { /// * `functions` - Function registry for UDF predicates/aggregates /// * `max_iterations` - Safety limit (e.g., 1000) /// * `max_derived_facts` - Maximum facts per iteration - /// * `max_results` - Maximum total results + /// * `max_results` - Maximum facts the rules may derive (base facts do not count) pub fn new( storage: FactStorage, rules: Arc>, @@ -133,6 +133,8 @@ impl RecursiveEvaluator { (f.entity, f.attribute.clone(), encoded) }) .collect(); + // `max_results` limits the facts the rules derive, not the database (#528). + let base_count = seen_facts.len(); let mut iteration = 0; @@ -170,8 +172,8 @@ impl RecursiveEvaluator { let encoded = encode_value(&fact.value); let key = (fact.entity, fact.attribute.clone(), encoded); if !seen_facts.contains(&key) { - // Check total result limit - if seen_facts.len() >= self.max_results { + // Check total derived-fact limit + if seen_facts.len() - base_count >= self.max_results { return Err(err_coded!( ErrorCode::Int020, format!("Max query results ({}) exceeded.", self.max_results) diff --git a/tests/recursive_rules_test.rs b/tests/recursive_rules_test.rs index 7428e48f5..967b36243 100644 --- a/tests/recursive_rules_test.rs +++ b/tests/recursive_rules_test.rs @@ -468,3 +468,38 @@ fn test_convergence_simple_graph() { _ => panic!("Expected QueryResults"), } } + +/// #528: `max_results` limits what the rules derive, not the size of the database. +/// A rule query must answer on a database with more live facts than `max_results`. +#[test] +fn test_max_results_counts_derived_facts_not_base_facts() { + let db = minigraf::OpenOptions::new() + .max_results(10) + .open_memory() + .unwrap(); + // A chain a -> b -> c -> d, plus 50 unrelated facts: 53 live facts in all. + exec( + &db, + "(transact [[:a :manager :b] [:b :manager :c] [:c :manager :d]])", + ); + let filler: String = (0..50).map(|i| format!("[:p{i} :age {i}] ")).collect(); + exec(&db, &format!("(transact [{filler}])")); + exec(&db, "(rule [(boss ?x ?y) [?x :manager ?y]])"); + exec(&db, "(rule [(boss ?x ?y) [?x :manager ?m] (boss ?m ?y)])"); + + // Bound first argument (magic-sets path): b, c, d. + match exec(&db, "(query [:find ?y :where (boss :a ?y)])") { + QueryResult::QueryResults { results, .. } => assert_eq!(results.len(), 3), + _ => panic!("Expected QueryResults"), + } + // All free: 6 pairs. + match exec(&db, "(query [:find ?x ?y :where (boss ?x ?y)])") { + QueryResult::QueryResults { results, .. } => assert_eq!(results.len(), 6), + _ => panic!("Expected QueryResults"), + } + // The limit still stops a rule that derives more than it allows. + let err = db + .execute("(query [:find ?x ?y :where (boss ?x ?y) :max-results 5])") + .unwrap_err(); + assert_eq!(err.code(), "INT-020"); +}