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
102 changes: 96 additions & 6 deletions src/db.rs
Original file line number Diff line number Diff line change
Expand Up @@ -17,6 +17,8 @@ use crate::graph::types::{Fact, VALID_TIME_FOREVER};
const VALID_FROM_USE_TX_TIME: i64 = i64::MIN;
use crate::graph::FactStorage;
use crate::graph::types::Value;
use crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS;
use crate::query::datalog::evaluator::DEFAULT_MAX_RESULTS;
use crate::query::datalog::executor::DatalogExecutor;
use crate::query::datalog::executor::QueryResult;
use crate::query::datalog::functions::{
Expand Down Expand Up @@ -63,13 +65,20 @@ pub struct OpenOptions {
pub wal_checkpoint_threshold: usize,
/// Number of pages to hold in the LRU page cache. Default: 256 (= 1MB at 4KB pages).
pub page_cache_size: usize,
/// Maximum facts that can be derived per recursive rule iteration.
/// Defaults to 100_000. Use to prevent runaway recursive rules.
pub max_derived_facts: usize,
/// Maximum total query results. Defaults to 1_000_000.
pub max_results: usize,
}

impl Default for OpenOptions {
fn default() -> Self {
OpenOptions {
wal_checkpoint_threshold: 1000,
page_cache_size: 256,
max_derived_facts: DEFAULT_MAX_DERIVED_FACTS,
max_results: DEFAULT_MAX_RESULTS,
}
}
}
Expand All @@ -88,6 +97,23 @@ impl OpenOptions {
self
}

/// Set the maximum facts that can be derived per recursive rule iteration.
///
/// Defaults to 100_000. Use lower values to prevent runaway recursive rules
/// from consuming excessive memory.
pub fn max_derived_facts(mut self, n: usize) -> Self {
self.max_derived_facts = n;
self
}

/// Set the maximum total query results.
///
/// Defaults to 1_000_000. Use lower values to limit result set size.
pub fn max_results(mut self, n: usize) -> Self {
self.max_results = n;
self
}

/// Set the path for a file-backed database.
pub fn path(self, path: impl AsRef<Path>) -> OpenOptionsWithPath {
OpenOptionsWithPath {
Expand All @@ -98,10 +124,9 @@ impl OpenOptions {

/// Open an in-memory (non-persistent) database.
///
/// Note: any builder options set before calling this method are ignored for
/// in-memory databases, which have no WAL or persistent file.
/// Uses the options set on the builder. WAL-related options are ignored.
pub fn open_memory(self) -> Result<Minigraf> {
Minigraf::in_memory()
Minigraf::in_memory_with_options(self)
}
}

Expand Down Expand Up @@ -297,8 +322,15 @@ impl Minigraf {

/// Create an in-memory database (no WAL, no persistence). Suitable for tests and REPL.
pub fn in_memory() -> Result<Self> {
Self::in_memory_with_options(OpenOptions::default())
}

/// Create an in-memory database with custom options.
///
/// Note: WAL-related options are ignored for in-memory databases.
pub fn in_memory_with_options(opts: OpenOptions) -> Result<Self> {
let backend = MemoryBackend::new();
let pfs = PersistentFactStorage::new(backend, 8)?;
let pfs = PersistentFactStorage::new(backend, opts.page_cache_size)?;
let fact_storage = pfs.storage().clone();

// For in-memory databases we don't need the PFS beyond initialisation;
Expand All @@ -311,7 +343,7 @@ impl Minigraf {
rules: Arc::new(RwLock::new(RuleRegistry::new())),
functions: Arc::new(RwLock::new(FunctionRegistry::with_builtins())),
write_lock: Mutex::new(WriteContext::Memory),
options: OpenOptions::default(),
options: opts,
}),
})
}
Expand Down Expand Up @@ -456,11 +488,15 @@ impl Minigraf {
}
} else {
// Read-only: no lock needed
let executor = DatalogExecutor::new_with_rules_and_functions(
let mut executor = DatalogExecutor::new_with_rules_and_functions(
self.inner.fact_storage.clone(),
self.inner.rules.clone(),
self.inner.functions.clone(),
);
executor.set_limits(
self.inner.options.max_derived_facts,
self.inner.options.max_results,
);
executor.execute(cmd)
}
}
Expand Down Expand Up @@ -1177,6 +1213,8 @@ mod tests {
let opts = OpenOptions {
wal_checkpoint_threshold: 5,
page_cache_size: 256,
max_derived_facts: 100_000,
max_results: 1_000_000,
};
let db = Minigraf::open_with_options(&path, opts).unwrap();
assert_eq!(db.inner.options.wal_checkpoint_threshold, 5);
Expand Down Expand Up @@ -1351,4 +1389,56 @@ mod tests {
"materialize_retraction with pseudo-attr must fail"
);
}

// ── query complexity limits ───────────────────────────────────────────────────

#[test]
fn test_max_derived_facts_limit_enforced() {
// Recursive rule will derive many facts
// Low limit should trigger error
let low_opts = OpenOptions::default()
.max_derived_facts(5)
.max_results(1_000_000);
let db_low = Minigraf::in_memory_with_options(low_opts).unwrap();

// Add base edges in a chain
db_low.execute("(transact [[:a :edge :b] [:b :edge :c] [:c :edge :d] [:d :edge :e] [:e :edge :f]])").unwrap();

// Register recursive rule
db_low
.execute(r#"(rule [(reachable ?x ?y) [?x :edge ?y]])"#)
.unwrap();
db_low
.execute(r#"(rule [(reachable ?x ?y) [?x :edge ?z] (reachable ?z ?y)])"#)
.unwrap();

let result = db_low.execute("(query [:find ?to :where (reachable :a ?to)])");
assert!(
result.is_err(),
"Query should fail with max_derived_facts limit"
);
let err_msg = result.unwrap_err().to_string();
assert!(
err_msg.contains("derived") || err_msg.contains("limit"),
"Error should mention derived facts limit, got: {}",
err_msg
);

// Same query with higher limit should succeed
let high_opts = OpenOptions::default()
.max_derived_facts(100_000)
.max_results(1_000_000);
let db_high = Minigraf::in_memory_with_options(high_opts).unwrap();

db_high.execute("(transact [[:a :edge :b] [:b :edge :c] [:c :edge :d] [:d :edge :e] [:e :edge :f]])").unwrap();
db_high
.execute(r#"(rule [(reachable ?x ?y) [?x :edge ?y]])"#)
.unwrap();
db_high
.execute(r#"(rule [(reachable ?x ?y) [?x :edge ?z] (reachable ?z ?y)])"#)
.unwrap();

let result = db_high.execute("(query [:find ?to :where (reachable :a ?to)])");
assert!(result.is_ok(), "Query should succeed with higher limit");
}
}
41 changes: 36 additions & 5 deletions src/query/datalog/executor.rs
Original file line number Diff line number Diff line change
@@ -1,6 +1,4 @@
use super::evaluator::{
DEFAULT_MAX_DERIVED_FACTS, DEFAULT_MAX_RESULTS, StratifiedEvaluator, evaluate_not_join,
};
use super::evaluator::{StratifiedEvaluator, evaluate_not_join};
use super::functions::{AggImpl, FunctionRegistry, apply_builtin_aggregate, value_lt};
use super::matcher::{PatternMatcher, edn_to_entity_id, edn_to_value};
use super::optimizer;
Expand Down Expand Up @@ -57,6 +55,8 @@ pub struct DatalogExecutor {
// RwLock pre-wired for 7.7b register_aggregate API.
functions: Arc<RwLock<FunctionRegistry>>,
indexes: Arc<crate::storage::index::Indexes>,
max_derived_facts: usize,
max_results: usize,
}

impl DatalogExecutor {
Expand All @@ -67,6 +67,8 @@ impl DatalogExecutor {
rules: Arc::new(RwLock::new(RuleRegistry::new())),
functions: Arc::new(RwLock::new(FunctionRegistry::with_builtins())),
indexes: Arc::new(indexes),
max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS,
max_results: crate::query::datalog::evaluator::DEFAULT_MAX_RESULTS,
}
}

Expand All @@ -84,6 +86,8 @@ impl DatalogExecutor {
rules,
functions,
indexes: Arc::new(indexes),
max_derived_facts: crate::query::datalog::evaluator::DEFAULT_MAX_DERIVED_FACTS,
max_results: crate::query::datalog::evaluator::DEFAULT_MAX_RESULTS,
}
}

Expand All @@ -98,6 +102,33 @@ impl DatalogExecutor {
)
}

/// Create a `DatalogExecutor` with custom complexity limits.
///
/// Used by `Minigraf` when `OpenOptions` specifies non-default limits.
pub fn new_with_limits(
storage: FactStorage,
rules: Arc<RwLock<RuleRegistry>>,
functions: Arc<RwLock<FunctionRegistry>>,
max_derived_facts: usize,
max_results: usize,
) -> Self {
let indexes = storage.pending_indexes_snapshot();
DatalogExecutor {
storage,
rules,
functions,
indexes: Arc::new(indexes),
max_derived_facts,
max_results,
}
}

/// Set complexity limits on an existing executor.
pub fn set_limits(&mut self, max_derived_facts: usize, max_results: usize) {
self.max_derived_facts = max_derived_facts;
self.max_results = max_results;
}

/// Execute a Datalog command
pub fn execute(&self, command: DatalogCommand) -> Result<QueryResult> {
match command {
Expand Down Expand Up @@ -404,8 +435,8 @@ impl DatalogExecutor {
self.rules.clone(),
self.functions.clone(),
1000, // max iterations
DEFAULT_MAX_DERIVED_FACTS,
DEFAULT_MAX_RESULTS,
self.max_derived_facts,
self.max_results,
);

let derived_storage = evaluator.evaluate(&predicates)?;
Expand Down
Loading