From f7e2a1de1cc0348dd24deb33215df4d9e9254d15 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 18:50:13 +0530 Subject: [PATCH 1/3] test(query): pseudo-attribute join rule test is native plan order only (#545) Under the wasm feature the planner keeps source order, so [?b :db/valid-at ?t] runs first and binds ?b as a ref; the test's premise (the planner runs it last) holds only natively. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- tests/join_rules_test.rs | 3 +++ 1 file changed, 3 insertions(+) diff --git a/tests/join_rules_test.rs b/tests/join_rules_test.rs index fa05a86248..fc67274df9 100644 --- a/tests/join_rules_test.rs +++ b/tests/join_rules_test.rs @@ -161,6 +161,9 @@ fn keyword_or_ref_with_a_repeated_pattern() { ); } +// Under `wasm` the planner keeps source order, so the pseudo-attribute +// pattern runs first and binds `?b` itself, as the entity's ref. +#[cfg(not(feature = "wasm"))] #[test] fn pseudo_attribute_pattern_never_replaces_a_value() { let db = friends_db(); From 0c550a8438f42978d54d8b885ebc4de255b07cf9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 18:50:13 +0530 Subject: [PATCH 2/3] feat(query): joins on the streaming engine (#545) Planner v2 runs queries of several patterns with stored attributes and expression clauses: the first pattern is a Scan, each later one an IndexNestedLoopJoin when its entity is a bound variable (one EAVT range per outer row, committed and pending) or a HashJoin otherwise, built on the side with the smaller estimate. Cells join by JoinKey: floats by IEEE ==, a keyword with a ref to the entity it names (IdSpace::keyword_eid), long strings as one form (pending strings the value pages hold become Long). A join keeps the outer cell unless the executor's Binders say the pattern gives the value (first binding in :where text order). Pseudo-attribute patterns stay with single-pattern queries. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/query/datalog/executor.rs | 8 +- src/query/engine/cell.rs | 61 +++++- src/query/engine/filter.rs | 3 + src/query/engine/ids.rs | 45 ++++ src/query/engine/join.rs | 389 ++++++++++++++++++++++++++++++++++ src/query/engine/mod.rs | 6 +- src/query/engine/plan.rs | 280 +++++++++++++++++++----- src/query/engine/scan.rs | 103 ++++++--- src/query/engine/tests.rs | 183 +++++++++++++++- 9 files changed, 991 insertions(+), 87 deletions(-) create mode 100644 src/query/engine/join.rs diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index c9bc3fb4f2..ff79c5e9c7 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1494,7 +1494,7 @@ type Binding = std::collections::HashMap; /// returned as they were bound. An expression binding overwrites the value /// where the planner places it, and later patterns keep it. A /// pseudo-attribute pattern never replaces a value. -struct Binders { +pub(crate) struct Binders { /// Each top-level pattern (rule calls as patterns) and its position in /// `:where`; taken as the planner hands them out. text: Vec<(Pattern, usize)>, @@ -1504,7 +1504,7 @@ struct Binders { } impl Binders { - fn new(where_clauses: &[WhereClause], rule_patterns: Vec<(Pattern, usize)>) -> Self { + pub(crate) fn new(where_clauses: &[WhereClause], rule_patterns: Vec<(Pattern, usize)>) -> Self { let mut text: Vec<(Pattern, usize)> = where_clauses .iter() .enumerate() @@ -1522,7 +1522,7 @@ impl Binders { /// Record the pattern `p`, run next, and return the variables whose /// value it replaces. - fn pattern(&mut self, p: &Pattern) -> Vec { + pub(crate) fn pattern(&mut self, p: &Pattern) -> Vec { let at = match self.text.iter().position(|(q, _)| q == p) { Some(i) => self.text.swap_remove(i).1, None => usize::MAX, @@ -1558,7 +1558,7 @@ impl Binders { } /// Record an expression binding `var`. - fn expression(&mut self, var: &str) { + pub(crate) fn expression(&mut self, var: &str) { self.by_var.insert(var.to_string(), None); } } diff --git a/src/query/engine/cell.rs b/src/query/engine/cell.rs index 1b136efd6b..670d04cecd 100644 --- a/src/query/engine/cell.rs +++ b/src/query/engine/cell.rs @@ -1,9 +1,10 @@ //! Cells: the values operators exchange (#473 spec §5.2). +use super::Ctx; use super::ids::IdSpace; use crate::graph::types::Value; use crate::storage::KeySource; -use crate::storage::keys::{KeyValue, ValueRef}; +use crate::storage::keys::{KeyValue, SHORT_STRING_MAX, ValueRef}; use anyhow::Result; use std::sync::Arc; @@ -47,7 +48,9 @@ impl Cell { } } - /// The cell of a value, with ids from `ids`. + /// The cell of a value, with ids from `ids`. A string over 64 bytes + /// that the committed value pages hold is `Long`, as a committed key + /// holds it, so that equal strings are equal cells (#545). pub(crate) fn of_value( ids: &mut IdSpace, keys: Option<&dyn KeySource>, @@ -58,9 +61,63 @@ impl Cell { Value::Boolean(b) => Cell::Val(Scalar::Bool(*b)), Value::Integer(n) => Cell::Val(Scalar::Int(*n)), Value::Float(f) => Cell::Val(Scalar::Float(*f)), + Value::String(s) if s.len() > SHORT_STRING_MAX => { + match keys.map(|k| k.long_value_ref(s)).transpose()?.flatten() { + Some(vref) => Cell::Val(Scalar::Long(vref)), + None => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), + } + } Value::String(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), Value::Keyword(k) => Cell::Iid(ids.iid(keys, k)?), Value::Ref(u) => Cell::Eid(ids.eid(keys, u)?), }) } } + +/// A cell as a join compares it (#473 spec §5.4): equal keys are +/// join-equal cells. +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub(crate) enum JoinKey { + Eid(u64), + Iid(u64), + Null, + Bool(bool), + Int(i64), + /// A float's bits, `-0.0` as `0.0`; never NaN. + Float(u64), + Str(Arc), + Long(ValueRef), +} + +impl JoinKey { + /// The key of `cell`, or `None` for a NaN, which equals nothing. With + /// `normalise`, a keyword is the entity it names, so that it equals a + /// ref to that entity; without, it equals the same keyword only. + pub(crate) fn of(cell: &Cell, normalise: bool, ctx: &mut Ctx<'_>) -> Result> { + Ok(Some(match cell { + Cell::Eid(e) => JoinKey::Eid(*e), + Cell::Iid(i) if normalise => JoinKey::Eid(ctx.ids.keyword_eid(ctx.keys, *i)?), + Cell::Iid(i) => JoinKey::Iid(*i), + Cell::Val(Scalar::Null) => JoinKey::Null, + Cell::Val(Scalar::Bool(b)) => JoinKey::Bool(*b), + Cell::Val(Scalar::Int(n)) => JoinKey::Int(*n), + Cell::Val(Scalar::Float(f)) if f.is_nan() => return Ok(None), + Cell::Val(Scalar::Float(f)) => JoinKey::Float(if *f == 0.0 { 0 } else { f.to_bits() }), + Cell::Val(Scalar::Str(s)) => JoinKey::Str(s.clone()), + Cell::Val(Scalar::Long(vref)) => JoinKey::Long(*vref), + })) + } +} + +/// Whether `a` and `b` are join-equal (#473 spec §5.4). +pub(crate) fn join_eq(a: &Cell, b: &Cell, normalise: bool, ctx: &mut Ctx<'_>) -> Result { + Ok( + match ( + JoinKey::of(a, normalise, ctx)?, + JoinKey::of(b, normalise, ctx)?, + ) { + (Some(a), Some(b)) => a == b, + _ => false, + }, + ) +} diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index fba53be89f..ff8b62005b 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -27,6 +27,7 @@ impl Apply { Step::Pseudo { .. } => "Pseudo", Step::Filter(..) => "Filter", Step::Bind(..) => "Bind", + Step::Join(_) => "Join", }; Apply { child, @@ -105,6 +106,8 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { batch.retain(&keep); batch.set_col(*slot, out); } + // Joins are operators of their own (`join::Join`). + Step::Join(_) => {} } Ok(batch) } diff --git a/src/query/engine/ids.rs b/src/query/engine/ids.rs index 95874ea993..b08dc463d4 100644 --- a/src/query/engine/ids.rs +++ b/src/query/engine/ids.rs @@ -12,6 +12,8 @@ use crate::error::{ErrorCode, err_coded}; use crate::graph::types::EntityId; +use crate::query::datalog::matcher::edn_to_entity_id; +use crate::query::datalog::types::EdnValue; use crate::storage::KeySource; use anyhow::Result; use std::collections::HashMap; @@ -35,6 +37,8 @@ struct Maps { uuid_by_eid: HashMap, iid_by_name: HashMap, u64>, name_by_iid: HashMap>, + /// The entity each keyword names, as an entity id. + eid_by_keyword: HashMap, } impl IdSpace { @@ -134,6 +138,30 @@ impl IdSpace { Ok(u) } + /// The id of the entity the keyword with id `iid` names + /// (`edn_to_entity_id`): a keyword and a ref to that entity are equal in + /// a join (#545). + pub(crate) fn keyword_eid(&mut self, keys: Option<&dyn KeySource>, iid: u64) -> Result { + for maps in [&self.provisional, &self.dict] { + if let Some(&e) = maps.eid_by_keyword.get(&iid) { + return Ok(e); + } + } + let name = self.name(keys, iid)?; + let uuid = edn_to_entity_id(&EdnValue::Keyword(name.to_string())) + .map_err(|e| err_coded!(ErrorCode::Int049, format!("query engine: {e}")))?; + let e = self.eid(keys, &uuid)?; + // Kept as long as the shorter-lived of the two ids. + let provisional = iid >= self.dict_iids && e >= self.dict_eids; + self.maps(provisional).eid_by_keyword.insert(iid, e); + Ok(e) + } + + /// `eid` as a DICT id, or `None` for a provisional one. + pub(crate) fn dict_eid(&self, eid: u64) -> Option { + (eid < self.dict_eids).then_some(eid) + } + /// The ident with id `iid`. pub(crate) fn name(&mut self, keys: Option<&dyn KeySource>, iid: u64) -> Result> { let maps = self.maps(iid >= self.dict_iids); @@ -172,4 +200,21 @@ mod tests { assert_eq!(&*ids.name(None, ia).unwrap(), ":a"); assert!(ids.uuid(None, 99).is_err(), "unknown id"); } + + /// A keyword's entity id is the id of the UUID it names, whether that + /// UUID was met first as an entity or not. + #[test] + fn keyword_eid_is_the_named_entitys_id() { + let mut ids = IdSpace::new(None); + let named = uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, b":alice"); + let e = ids.eid(None, &named).unwrap(); + let k = ids.iid(None, ":alice").unwrap(); + assert_eq!(ids.keyword_eid(None, k).unwrap(), e); + ids.end_pull(); + assert_eq!(ids.keyword_eid(None, k).unwrap(), e); + let u = uuid::Uuid::from_u128(7); + let k = ids.iid(None, &format!(":{u}")).unwrap(); + let e = ids.keyword_eid(None, k).unwrap(); + assert!(ids.uuid(None, e).unwrap() == u, "UUID keyword"); + } } diff --git a/src/query/engine/join.rs b/src/query/engine/join.rs new file mode 100644 index 0000000000..ee23d4cf5d --- /dev/null +++ b/src/query/engine/join.rs @@ -0,0 +1,389 @@ +//! `IndexNestedLoopJoin` and `HashJoin` (#473 spec §6.2): the rows so far +//! (the outer side) joined with one more pattern (the inner side). +//! +//! The inner pattern is a [`Scan`] over slots of its own. Two cells join +//! when their [`JoinKey`]s are equal (spec §5.4): floats by IEEE `==`, a +//! keyword with a ref to the entity it names. A joined row keeps the outer +//! cell of each shared variable, except where the plan says the pattern +//! gives its value (`JoinSpec::replace`). + +use super::batch::Batch; +use super::cell::{Cell, JoinKey, join_eq}; +use super::plan::{JoinKind, JoinSpec, Key}; +use super::scan::Scan; +use super::{BATCH_ROWS, Counters, Ctx, Operator}; +use anyhow::Result; +use std::collections::HashMap; + +type Row = Vec; + +pub(crate) struct Join { + outer: Box, + inner: Scan, + kind: JoinKind, + keys: Vec, + new: Vec, + replace: Vec<(usize, usize)>, + outer_width: usize, + state: State, + /// `rows_in` counts the outer rows received. + counters: Counters, +} + +enum State { + Start, + Probe(Probe), + Hash(Hash), + Done, +} + +/// `IndexNestedLoopJoin`: the rows of the current outer batch, the one +/// probed, whether its inner scan is open, and the inner rows read but not +/// yet joined. +#[derive(Default)] +struct Probe { + rows: Vec, + at: usize, + probing: bool, + matches: Vec, + next: usize, +} + +/// `HashJoin`: the table of the build side, the rows of the streamed side's +/// current batch, the one matched, and the next row of its bucket. +struct Hash { + table: Table, + rows: Vec, + at: usize, + bucket: Option, + next: usize, +} + +/// The build side of a `HashJoin`: its rows grouped by key. +#[derive(Default)] +struct Table { + by_key: HashMap, usize>, + buckets: Vec>, +} + +/// Which side a row comes from. +#[derive(Clone, Copy)] +enum Side { + Outer, + Inner, +} + +impl Join { + pub(crate) fn new(outer: Box, spec: JoinSpec) -> Self { + let op = match spec.kind { + JoinKind::Probe(_) => "IndexNestedLoopJoin", + JoinKind::Hash { .. } => "HashJoin", + }; + Join { + outer, + inner: Scan::new(spec.inner), + kind: spec.kind, + keys: spec.keys, + new: spec.new, + replace: spec.replace, + outer_width: spec.outer_width, + state: State::Start, + counters: Counters::new(op), + } + } + + /// The key of `row`, from `side`, or `None` when a cell equals nothing. + fn key(&self, row: &[Cell], side: Side, ctx: &mut Ctx<'_>) -> Result>> { + let mut key = Vec::with_capacity(self.keys.len()); + for k in &self.keys { + let slot = match side { + Side::Outer => k.outer, + Side::Inner => k.inner, + }; + let Some(cell) = row.get(slot) else { + return Ok(None); + }; + match JoinKey::of(cell, k.normalise, ctx)? { + Some(j) => key.push(j), + None => return Ok(None), + } + } + Ok(Some(key)) + } + + /// Append the join of `outer` and `inner` to `out`. + fn emit(&self, outer: &[Cell], inner: &[Cell], out: &mut Batch) { + let cells = outer + .iter() + .take(self.outer_width) + .enumerate() + .map(|(slot, cell)| { + self.replace + .iter() + .find(|(_, o)| *o == slot) + .and_then(|(i, _)| inner.get(*i)) + .unwrap_or(cell) + }) + .chain(self.new.iter().filter_map(|i| inner.get(*i))); + for (col, cell) in out.cols.iter_mut().zip(cells) { + col.push(cell.clone()); + } + out.len += 1; + } + + /// The next rows of `side`, or `None` once it has ended. + fn pull(&mut self, side: Side, ctx: &mut Ctx<'_>) -> Result>> { + let batch = match side { + Side::Outer => self.outer.next_batch(ctx)?, + Side::Inner => self.inner.next_batch(ctx)?, + }; + Ok(batch.map(|b| { + if let Side::Outer = side { + self.counters.rows_in += b.len as u64; + } + rows(&b) + })) + } + + /// Read all of `side` into a table. + fn build(&mut self, side: Side, ctx: &mut Ctx<'_>) -> Result { + let mut table = Table::default(); + while let Some(rows) = self.pull(side, ctx)? { + for row in rows { + let Some(key) = self.key(&row, side, ctx)? else { + continue; + }; + let next = table.buckets.len(); + let b = *table.by_key.entry(key).or_insert(next); + if b == next { + table.buckets.push(Vec::new()); + } + if let Some(bucket) = table.buckets.get_mut(b) { + bucket.push(row); + } + } + } + Ok(table) + } + + /// The entity of an outer row to probe: its UUID and DICT id, or `None` + /// when the cell is no entity (a scalar never equals one). + fn probe_of( + &self, + row: &[Cell], + k: usize, + ctx: &mut Ctx<'_>, + ) -> Result)>> { + let Some(key) = self.keys.get(k) else { + return Ok(None); + }; + let Some(cell) = row.get(key.outer) else { + return Ok(None); + }; + let Some(JoinKey::Eid(e)) = JoinKey::of(cell, true, ctx)? else { + return Ok(None); + }; + let uuid = ctx.ids.uuid(ctx.keys, e)?; + Ok(Some((uuid, ctx.ids.dict_eid(e)))) + } + + /// Whether `outer` and `inner` agree on every key but the probed one. + fn agree( + &self, + outer: &[Cell], + inner: &[Cell], + probed: usize, + ctx: &mut Ctx<'_>, + ) -> Result { + for (n, k) in self.keys.iter().enumerate() { + if n == probed { + continue; + } + let (Some(o), Some(i)) = (outer.get(k.outer), inner.get(k.inner)) else { + return Ok(false); + }; + if !join_eq(o, i, k.normalise, ctx)? { + return Ok(false); + } + } + Ok(true) + } + + /// Join outer rows into `out` until it is full; `false` once the outer + /// side has ended. + fn next_probe( + &mut self, + p: &mut Probe, + probed: usize, + out: &mut Batch, + ctx: &mut Ctx<'_>, + ) -> Result { + while out.len < BATCH_ROWS { + if let Some(o) = p.rows.get(p.at) { + if let Some(m) = p.matches.get(p.next) { + p.next += 1; + if self.agree(o, m, probed, ctx)? { + self.emit(o, m, out); + } + } else if p.probing { + match self.inner.next_batch(ctx)? { + Some(b) => p.matches = rows(&b), + None => { + p.matches.clear(); + p.probing = false; + p.at += 1; + } + } + p.next = 0; + } else { + match self.probe_of(o, probed, ctx)? { + Some((uuid, eid)) => { + self.inner.probe(uuid, eid); + p.probing = true; + } + None => p.at += 1, + } + } + continue; + } + match self.pull(Side::Outer, ctx)? { + Some(r) => { + p.rows = r; + p.at = 0; + } + None => return Ok(false), + } + } + Ok(true) + } + + /// Join streamed rows into `out` until it is full; `false` once the + /// streamed side has ended. + fn next_hash( + &mut self, + h: &mut Hash, + build_inner: bool, + out: &mut Batch, + ctx: &mut Ctx<'_>, + ) -> Result { + let streamed = if build_inner { + Side::Outer + } else { + Side::Inner + }; + while out.len < BATCH_ROWS { + if let Some(s) = h.rows.get(h.at) { + let matched = h + .bucket + .and_then(|b| h.table.buckets.get(b)) + .and_then(|r| r.get(h.next)); + if let Some(m) = matched { + h.next += 1; + if build_inner { + self.emit(s, m, out); + } else { + self.emit(m, s, out); + } + } else if h.bucket.is_some() { + h.bucket = None; + h.at += 1; + } else { + let key = self.key(s, streamed, ctx)?; + match key.and_then(|k| h.table.by_key.get(&k).copied()) { + Some(b) => { + h.bucket = Some(b); + h.next = 0; + } + None => h.at += 1, + } + } + continue; + } + match self.pull(streamed, ctx)? { + Some(r) => { + h.rows = r; + h.at = 0; + } + None => return Ok(false), + } + } + Ok(true) + } +} + +impl Operator for Join { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { + let mut out = Batch::new(self.outer_width + self.new.len()); + if let State::Start = self.state { + self.state = match self.kind { + JoinKind::Probe(_) => State::Probe(Probe::default()), + JoinKind::Hash { build_inner } => { + let built = if build_inner { + Side::Inner + } else { + Side::Outer + }; + let table = self.build(built, ctx)?; + if table.buckets.is_empty() { + State::Done + } else { + State::Hash(Hash { + table, + rows: Vec::new(), + at: 0, + bucket: None, + next: 0, + }) + } + } + }; + } + // Taken out while it runs; an error leaves the join done. + let more = match (std::mem::replace(&mut self.state, State::Done), self.kind) { + (State::Probe(mut p), JoinKind::Probe(k)) => { + let more = self.next_probe(&mut p, k, &mut out, ctx)?; + self.state = State::Probe(p); + more + } + (State::Hash(mut h), JoinKind::Hash { build_inner }) => { + let more = self.next_hash(&mut h, build_inner, &mut out, ctx)?; + self.state = State::Hash(h); + more + } + _ => false, + }; + if !more { + self.close(); + } + if out.len == 0 { + return Ok(None); + } + self.counters.out(&out); + Ok(Some(out)) + } + + fn close(&mut self) { + self.state = State::Done; + self.outer.close(); + self.inner.close(); + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + self.inner.counters(out); + self.outer.counters(out); + } +} + +/// The rows of `batch`. +fn rows(batch: &Batch) -> Vec { + (0..batch.len) + .map(|i| { + batch + .cols + .iter() + .filter_map(|c| c.get(i).cloned()) + .collect() + }) + .collect() +} diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index e3684641ec..de61da4bb4 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -10,6 +10,7 @@ mod batch; mod cell; mod filter; mod ids; +mod join; #[cfg(any(test, feature = "test-oracle"))] pub(crate) mod oracle; mod plan; @@ -131,7 +132,10 @@ pub(crate) fn open( } = plan; let mut root: Box = Box::new(scan::Scan::new(scan)); for step in steps { - root = Box::new(filter::Apply::new(root, step)); + root = match step { + plan::Step::Join(spec) => Box::new(join::Join::new(root, spec)), + step => Box::new(filter::Apply::new(root, step)), + }; } Some(Stream { snapshot, diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 5d52974863..4fce570511 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -1,20 +1,26 @@ -//! Planner v1 (#473 spec §6.3): which queries the engine runs, and their +//! Planner v2 (#473 spec §6.3): which queries the engine runs, and their //! operator trees. //! -//! #544 runs a query whose `:where` is one pattern with a stored attribute, -//! followed by pseudo-attribute patterns on the same entity and expression -//! clauses, and whose `:find` holds plain variables. Every other query runs -//! on the existing executor (spec §9). +//! The engine runs a query whose `:where` holds patterns with a stored +//! attribute and expression clauses, and whose `:find` holds plain +//! variables (#545); or one such pattern, pseudo-attribute patterns on its +//! entity and expression clauses (#544). Every other query runs on the +//! existing executor (spec §9). //! //! Clauses run in the order `optimizer::plan` gives the executor, so an //! expression sees the same variables, and a binding expression overwrites a -//! variable at the same point, as it does there. +//! variable at the same point, as it does there. The first pattern is a +//! `Scan`; each later one a join: an `IndexNestedLoopJoin` when its entity is +//! a variable already bound, a `HashJoin` otherwise (decision 3 of the #545 +//! plan). use crate::graph::types::{EntityId, Value}; +use crate::query::datalog::executor::Binders; use crate::query::datalog::matcher::edn_to_entity_id; use crate::query::datalog::optimizer; use crate::query::datalog::types::{ - AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, PseudoAttr, ValidAt, WhereClause, + AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, PseudoAttr, ValidAt, + WhereClause, }; use std::collections::HashMap; @@ -111,6 +117,49 @@ pub(crate) enum Step { /// `[(f …) ?out]`: binds (or overwrites) the slot; drops the rows where /// the expression fails. Bind(Expr, Vars, usize), + /// A later pattern, joined with the rows so far. + Join(JoinSpec), +} + +/// A join of the rows so far (the outer side) with one pattern (spec §6.2). +#[derive(Debug, Clone)] +pub(crate) struct JoinSpec { + /// The pattern, over slots of its own: its variables in order of first + /// occurrence. A variable repeated inside it compares exactly, as in one + /// pattern alone. + pub(crate) inner: ScanSpec, + pub(crate) kind: JoinKind, + /// The variables both sides bind. + pub(crate) keys: Vec, + /// The inner slots of the variables the outer side lacks, in the order + /// they are added after the outer slots. + pub(crate) new: Vec, + /// `(inner, outer)`: outer slots whose cell the inner one replaces, for a + /// variable whose first binding in the query text is this pattern + /// (decision 2 of the #545 plan). + pub(crate) replace: Vec<(usize, usize)>, + /// Number of slots of an outer row. + pub(crate) outer_width: usize, +} + +/// One variable both sides of a join bind. +#[derive(Debug, Clone, Copy)] +pub(crate) struct Key { + pub(crate) inner: usize, + pub(crate) outer: usize, + /// Whether a keyword equals a ref to the entity it names here: everywhere + /// but between two attribute positions. + pub(crate) normalise: bool, +} + +#[derive(Debug, Clone, Copy)] +pub(crate) enum JoinKind { + /// `IndexNestedLoopJoin`: the inner pattern's entity is `keys[k]`; one + /// entity range per outer row. + Probe(usize), + /// `HashJoin`: a table of the side with the smaller estimate, probed by + /// the other. + Hash { build_inner: bool }, } /// The variables an expression reads that are bound when it runs, by slot. @@ -125,17 +174,26 @@ pub(crate) struct Plan { pub(crate) vars: Vec, } +/// Positions a slot's cells come from. +const ATTRIBUTE: u8 = 1; +const OTHER: u8 = 2; + /// Variable slots, in the order clauses bind them. #[derive(Default)] struct Slots { by_var: HashMap, - len: usize, + /// For each slot: the positions its cells may come from. + kinds: Vec, } impl Slots { - fn add(&mut self) -> usize { - self.len += 1; - self.len - 1 + fn add(&mut self, kind: u8) -> usize { + self.kinds.push(kind); + self.kinds.len() - 1 + } + + fn len(&self) -> usize { + self.kinds.len() } } @@ -160,6 +218,20 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { { return None; } + // Pseudo-attribute patterns read the fact of the one real pattern; across + // joins they wait for #545's last part. + let real = query + .where_clauses + .iter() + .filter(|c| matches!(c, WhereClause::Pattern(p) if matches!(p.attribute, AttributeSpec::Real(_)))) + .count(); + let pseudo = query.where_clauses.iter().any( + |c| matches!(c, WhereClause::Pattern(p) if matches!(p.attribute, AttributeSpec::Pseudo(_))), + ); + if real > 1 && pseudo { + return None; + } + let mut binders = Binders::new(&query.where_clauses, Vec::new()); let (planned, _) = optimizer::plan(query.where_clauses.clone()); let mut planned = planned.into_iter().map(|(c, _)| c); let Some(WhereClause::Pattern(p)) = planned.next() else { @@ -168,18 +240,13 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { let AttributeSpec::Real(attribute) = &p.attribute else { return None; }; + binders.pattern(&p); let rest: Vec = planned.collect(); let mut slots = Slots::default(); - let e = term(&p.entity, &mut slots, |c| match c { - EdnValue::Keyword(_) | EdnValue::Uuid(_) => edn_to_entity_id(c).ok(), - _ => None, - })?; - let a = term(attribute, &mut slots, |c| match c { - EdnValue::Keyword(k) => Some(k.clone()), - _ => None, - })?; - let v = term(&p.value, &mut slots, value_const)?; + let e = term(&p.entity, &mut slots, OTHER, entity_const)?; + let a = term(attribute, &mut slots, ATTRIBUTE, attribute_const)?; + let v = term(&p.value, &mut slots, OTHER, value_const)?; // A pseudo-attribute pattern reads the metadata of the fact the scan // matched only when its entity is the scan's entity term; any other @@ -189,15 +256,15 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { let WhereClause::Pattern(q) = c else { continue; }; - let m = match &q.attribute { - AttributeSpec::Pseudo(pa) => meta_of(pa)?, - AttributeSpec::Real(_) => return None, + let AttributeSpec::Pseudo(pa) = &q.attribute else { + continue; }; + let m = meta_of(pa)?; if !same_entity(&p.entity, &q.entity) { return None; } if !meta.iter().any(|(mm, _)| *mm == m) { - meta.push((m, slots.add())); + meta.push((m, slots.add(OTHER))); } } // An expression that rebinds the entity variable would send a later @@ -210,34 +277,59 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { { return None; } - let width = slots.len; + let scan = ScanSpec { + e, + a, + v, + meta: meta.clone(), + as_of, + valid, + width: slots.len(), + }; + let mut outer_patterns = vec![WhereClause::Pattern(p.clone())]; let mut steps = Vec::with_capacity(rest.len()); for c in rest { steps.push(match c { - WhereClause::Pattern(q) => { - let AttributeSpec::Pseudo(pa) = &q.attribute else { - return None; - }; - let m = meta_of(pa)?; - let col = meta.iter().find(|(mm, _)| *mm == m)?.1; - let value = term(&q.value, &mut slots, |c| { - Some(match c { - EdnValue::Integer(n) => Some(*n), - _ => None, - }) - })?; - Step::Pseudo { col, value } - } + WhereClause::Pattern(q) => match &q.attribute { + AttributeSpec::Pseudo(pa) => { + binders.pattern(&q); + let m = meta_of(pa)?; + let col = meta.iter().find(|(mm, _)| *mm == m)?.1; + let value = term(&q.value, &mut slots, OTHER, |c| { + Some(match c { + EdnValue::Integer(n) => Some(*n), + _ => None, + }) + })?; + Step::Pseudo { col, value } + } + AttributeSpec::Real(attribute) => { + let rebind = binders.pattern(&q); + let mut join = join(&q, attribute, &mut slots, &rebind, as_of, valid)?; + if let JoinKind::Hash { build_inner } = &mut join.kind { + *build_inner = optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) + <= optimizer::branch_cost(&outer_patterns); + } + outer_patterns.push(WhereClause::Pattern(q)); + Step::Join(join) + } + }, WhereClause::Expr { expr, binding } => { let vars = expr_vars(&expr, &slots); match binding { None => Step::Filter(expr, vars), Some(out) => { + binders.expression(&out); let slot = match slots.by_var.get(&out) { - Some(&s) => s, + Some(&s) => { + if let Some(k) = slots.kinds.get_mut(s) { + *k |= OTHER; + } + s + } None => { - let s = slots.add(); + let s = slots.add(OTHER); slots.by_var.insert(out, s); s } @@ -259,21 +351,112 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { find.push(*slots.by_var.get(var)?); } Some(Plan { - scan: ScanSpec { + scan, + steps, + find, + vars: query.find.iter().map(FindSpec::display_name).collect(), + }) +} + +/// The join of the rows so far, whose variables are `slots`, with the +/// pattern `q`; adds the slots of its new variables. `rebind` names the +/// variables whose value `q` gives (decision 2 of the #545 plan). +fn join( + q: &Pattern, + attribute: &EdnValue, + slots: &mut Slots, + rebind: &[String], + as_of: Option, + valid: Valid, +) -> Option { + let outer_width = slots.len(); + let mut local = Slots::default(); + let e = term(&q.entity, &mut local, OTHER, entity_const)?; + let a = term(attribute, &mut local, ATTRIBUTE, attribute_const)?; + let v = term(&q.value, &mut local, OTHER, value_const)?; + + let mut keys = Vec::new(); + let mut new = Vec::new(); + let mut replace = Vec::new(); + let mut probe = None; + // Each variable at its first position in the pattern. + for (position, (edn, kind)) in [ + (&q.entity, OTHER), + (attribute, ATTRIBUTE), + (&q.value, OTHER), + ] + .into_iter() + .enumerate() + { + let EdnValue::Symbol(var) = edn else { + continue; + }; + let Some(&inner) = local.by_var.get(var) else { + continue; + }; + if keys.iter().any(|k: &Key| k.inner == inner) || new.contains(&inner) { + continue; + } + match slots.by_var.get(var) { + Some(&outer) => { + let held = slots.kinds.get(outer).copied().unwrap_or(OTHER); + if position == 0 { + probe = Some(keys.len()); + } + keys.push(Key { + inner, + outer, + normalise: !(kind == ATTRIBUTE && held == ATTRIBUTE), + }); + if rebind.contains(var) { + replace.push((inner, outer)); + if let Some(k) = slots.kinds.get_mut(outer) { + *k |= kind; + } + } + } + None => { + new.push(inner); + let s = slots.add(kind); + slots.by_var.insert(var.clone(), s); + } + } + } + Some(JoinSpec { + inner: ScanSpec { e, a, v, - meta, + meta: Vec::new(), as_of, valid, - width, + width: local.len(), }, - steps, - find, - vars: query.find.iter().map(FindSpec::display_name).collect(), + kind: match probe { + Some(k) => JoinKind::Probe(k), + None => JoinKind::Hash { build_inner: true }, + }, + keys, + new, + replace, + outer_width, }) } +fn entity_const(c: &EdnValue) -> Option { + match c { + EdnValue::Keyword(_) | EdnValue::Uuid(_) => edn_to_entity_id(c).ok(), + _ => None, + } +} + +fn attribute_const(c: &EdnValue) -> Option { + match c { + EdnValue::Keyword(k) => Some(k.clone()), + _ => None, + } +} + fn value_const(c: &EdnValue) -> Option { Some(match c { EdnValue::String(s) => ValueConst::Exact(Value::String(s.clone())), @@ -346,6 +529,7 @@ fn expr_vars(expr: &Expr, slots: &Slots) -> Vars { fn term( edn: &EdnValue, slots: &mut Slots, + kind: u8, konst: impl Fn(&EdnValue) -> Option, ) -> Option> { match edn { @@ -353,7 +537,7 @@ fn term( EdnValue::Symbol(s) if s.starts_with('?') => Some(match slots.by_var.get(s) { Some(&slot) => Term::Eq(slot), None => { - let slot = slots.add(); + let slot = slots.add(kind); slots.by_var.insert(s.clone(), slot); Term::Bind(slot) } diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index 17d3266631..e7ae266c8d 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -19,6 +19,12 @@ use std::collections::{HashMap, HashSet}; pub(crate) struct Scan { spec: ScanSpec, + /// The entity of the current probe of a join's inner scan, by UUID and + /// DICT id (`None` for an entity only pending facts hold). + probe: Option<(EntityId, Option)>, + /// The DICT ids of the attribute and value constants, resolved once for + /// every probe; `Some(None)` when no committed key can match them. + consts: Option>, state: State, keys_buf: Vec, facts_buf: Vec, @@ -45,7 +51,15 @@ struct Committed { shadow: HashSet>, } +/// The attribute and value constants of a scan, against the DICT. +#[derive(Clone)] +struct Consts { + a: Option, + test: Option, +} + /// A value constant over committed key values, with ids resolved. +#[derive(Clone)] enum KeyTest { Exact(KeyValue), /// A keyword constant: the keyword's ident id, the named entity's id. @@ -81,12 +95,21 @@ impl Scan { pub(crate) fn new(spec: ScanSpec) -> Self { Scan { spec, + probe: None, + consts: None, state: State::Start, keys_buf: Vec::new(), facts_buf: Vec::new(), counters: Counters::new("Scan"), } } + + /// Start again, over the facts of the entity `uuid` (DICT id `eid`) + /// only: one probe of an `IndexNestedLoopJoin`. + pub(crate) fn probe(&mut self, uuid: EntityId, eid: Option) { + self.probe = Some((uuid, eid)); + self.state = State::Start; + } } impl Operator for Scan { @@ -94,7 +117,14 @@ impl Operator for Scan { loop { let mut batch = Batch::new(self.spec.width); match &mut self.state { - State::Start => self.state = open(&self.spec, ctx)?, + State::Start => { + if self.consts.is_none() + && let Some(keys) = ctx.keys + { + self.consts = Some(consts(&self.spec, keys)?); + } + self.state = open(&self.spec, self.probe.as_ref(), self.consts.as_ref(), ctx)?; + } State::Committed(c) => { let Some(keys) = ctx.keys else { self.state = State::Pending(None); @@ -154,7 +184,7 @@ impl Operator for Scan { State::Pending(resume) => { self.facts_buf.clear(); let more = ctx.snapshot.pending_live( - range(&self.spec), + range(&self.spec, self.probe.as_ref()), self.spec.as_of, resume, BATCH_ROWS, @@ -221,34 +251,48 @@ fn set(row: &mut [Option], slot: usize, n: i64) { } } -/// Resolve the committed ranges of `spec` and the pending triples that -/// shadow them. -fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { - let Some(keys) = ctx.keys else { - return Ok(State::Pending(None)); - }; - let pending = State::Pending(None); - let e = match &spec.e { - Term::Const(u) => match keys.eid_of(u)? { - Some(e) => Some(e), - None => return Ok(pending), - }, - _ => None, - }; +/// The DICT ids of the constants of `spec`, or `None` when no committed key +/// can match them. +fn consts(spec: &ScanSpec, keys: &dyn KeySource) -> Result> { let a = match &spec.a { Term::Const(name) => match keys.iid_of(name)? { Some(a) => Some(a), - None => return Ok(pending), + None => return Ok(None), }, _ => None, }; let test = match &spec.v { Term::Const(c) => match key_test(keys, c)? { Some(t) => Some(t), - None => return Ok(pending), + None => return Ok(None), }, _ => None, }; + Ok(Some(Consts { a, test })) +} + +/// Resolve the committed ranges of `spec` (of the entity `probe`, when +/// given) and the pending triples that shadow them. +fn open( + spec: &ScanSpec, + probe: Option<&(EntityId, Option)>, + consts: Option<&Option>, + ctx: &mut Ctx<'_>, +) -> Result { + let pending = State::Pending(None); + let (Some(keys), Some(Some(Consts { a, test }))) = (ctx.keys, consts) else { + return Ok(pending); + }; + let (a, test) = (*a, test.clone()); + let e = match (probe, &spec.e) { + (Some((_, Some(e))), _) => Some(*e), + (Some((_, None)), _) => return Ok(pending), + (None, Term::Const(u)) => match keys.eid_of(u)? { + Some(e) => Some(e), + None => return Ok(pending), + }, + (None, _) => None, + }; let (ranges, test) = match (e, a, test) { (Some(e), Some(a), Some(KeyTest::Exact(v))) => ( vec![(Index::Eavt, keys::entity_attribute_value_prefix(e, a, &v))], @@ -261,7 +305,10 @@ fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { (None, None, t) => (vec![(Index::Eavt, Vec::new())], t), }; let mut shadow = HashSet::new(); - for f in ctx.snapshot.pending_records(range(spec), spec.as_of)? { + for f in ctx + .snapshot + .pending_records(range(spec, probe), spec.as_of)? + { if let Some(t) = committed_triple(keys, &f)? { shadow.insert(t); } @@ -316,13 +363,17 @@ fn key_test(keys: &dyn KeySource, c: &ValueConst) -> Result> { }) } -/// The pending range of `spec`. -fn range(spec: &ScanSpec) -> Range<'_> { - match (&spec.e, &spec.a) { - (Term::Const(e), Term::Const(a)) => Range::EntityAttribute(e, a), - (Term::Const(e), _) => Range::Entity(e), - (_, Term::Const(a)) => Range::Attribute(a), - _ => Range::All, +/// The pending range of `spec` (of the entity `probe`, when given). +fn range<'a>(spec: &'a ScanSpec, probe: Option<&'a (EntityId, Option)>) -> Range<'a> { + let e = match (probe, &spec.e) { + (Some((u, _)), _) | (None, Term::Const(u)) => Some(u), + _ => None, + }; + match (e, &spec.a) { + (Some(e), Term::Const(a)) => Range::EntityAttribute(e, a), + (Some(e), _) => Range::Entity(e), + (None, Term::Const(a)) => Range::Attribute(a), + (None, _) => Range::All, } } diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 650203c2d2..82b4ea0673 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -15,7 +15,7 @@ fn runs() -> usize { /// Rows of `query`, which must run on the engine. fn rows(db: &Minigraf, query: &str) -> usize { let before = runs(); - let QueryResult::QueryResults { results, .. } = db.execute(query).unwrap() else { + let QueryResult::QueryResults { results, .. } = db.execute(query).expect(query) else { panic!("expected query results"); }; assert_eq!(runs(), before + 1, "query ran on the engine"); @@ -33,7 +33,8 @@ fn uuid_of(entity: &str) -> uuid::Uuid { /// One batch of history, numbered `round`: assertions, retractions, /// re-assertions in new windows, refs, keywords (one naming an entity by its -/// UUID), floats, long strings. +/// UUID, one naming an attribute), floats, long strings, attributes that +/// name entities. fn write_round(db: &Minigraf, round: u32) { let scores = ["0.30000000000000004", "1.5", "-0.0", "0.0", "2.5"]; for p in 0..6u32 { @@ -44,7 +45,7 @@ fn write_round(db: &Minigraf, round: u32) { [:p{p} :person/friend :p{f}] [:p{p} :person/name \"n{p}\"] \ [:p{p} :person/bio \"{bio}\"] [:p{p} :person/ok {ok}] [:p{p} :person/self :p{p}] \ [:p{p} :person/boss #uuid \"{boss}\"] [:p{p} :person/alias :{alias}] \ - [:p{p} :person/score {score}]])", + [:p{p} :person/score {score}] [:p{p} :person/attr :person/age] [:p{p} :p{f} {p}]])", age = 20 + round % 4, bio = long(p % 2), ok = (round + p) % 2 == 0, @@ -204,6 +205,14 @@ fn queries(tx: u64) -> Vec { )); } } + for clauses in joins() { + let find = vars_of(clauses); + for temporal in temporals(tx) { + out.push(format!( + "(query [:find {find} {temporal} :where {clauses}])" + )); + } + } for (find, clauses) in pseudo { for temporal in &pseudo_temporals { out.push(format!( @@ -214,6 +223,65 @@ fn queries(tx: u64) -> Vec { out } +/// Join shapes (#545): on the entity, value and attribute positions, cross +/// products, keywords and refs of one entity in both text orders, floats, +/// long strings, three patterns, expressions between joins. +fn joins() -> Vec<&'static str> { + vec![ + // IndexNestedLoopJoin: the entity is bound. + "[?e :person/name ?n] [?e :person/age ?a]", + "[?e :person/age ?a] [?e ?b ?v]", + "[?e :person/name ?n] [?e :person/name ?n]", + // ... by a keyword value naming it, or a ref. + "[?e :person/friend ?f] [?f :person/name ?n]", + "[?f :person/name ?n] [?e :person/friend ?f]", + "[?e :person/boss ?f] [?f :person/name ?n]", + "[?e :person/alias ?x] [?x :person/age ?a]", + "[?e :person/friend ?f] [?f :person/friend ?g] [?g :person/name ?n]", + "[?e :person/self ?x] [?x :person/self ?x]", + "[?e :person/friend ?f] [?f :person/self ?e]", + "[?e :person/age ?a] [?e :person/score 0.0]", + // HashJoin on the value position: keywords and refs, both orders. + "[?e :person/boss ?b] [?f :person/friend ?b]", + "[?f :person/friend ?b] [?e :person/boss ?b]", + "[?e :person/alias ?b] [?f :person/boss ?b]", + "[?e :person/friend ?b] [?b :person/self ?b]", + "[?a :person/age ?v] [?b :person/age ?v]", + "[?a :person/score ?s] [?b :person/score ?s]", + "[?a :person/bio ?s] [?b :person/bio ?s]", + "[?a :person/status ?s] [:p1 :person/status ?s]", + "[:p0 :person/friend ?f] [?e :person/friend ?f]", + // ... on the attribute position, from attributes or entities. + "[?e ?a 21] [:p1 ?a ?w]", + "[?e :person/boss ?x] [?y ?x ?v]", + "[?e :person/friend ?x] [?y ?x ?v]", + "[?e :person/attr ?x] [?y ?x ?v]", + // Cross products. + "[?e :person/ok true] [?f :person/status :s1]", + "[:p1 :person/age ?a] [:p2 :person/age ?b]", + "[?e :person/null ?x] [?f :person/null ?y]", + // Expressions between joins. + "[?e :person/age ?a] [?f :person/age ?b] [(< ?a ?b)]", + "[?e :person/age ?a] [(+ ?a 1) ?b] [?f :person/age ?b]", + "[?e :person/friend ?s] [(= ?s :p1)] [?f :person/boss ?s]", + "[?e :person/name ?s] [(= ?s \"n2\")] [?f :person/name ?s]", + "[?e :person/score ?s] [(- 0.0 ?s) ?t] [?f :person/score ?t]", + "[?e :person/boss ?b] [(+ 18 3) ?b] [?f :person/age ?b]", + "[?e :person/age ?a] [(+ ?a 1) ?a] [?f :person/age ?a]", + ] +} + +/// The variables of `clauses`, in order. +fn vars_of(clauses: &str) -> String { + let mut vars: Vec<&str> = Vec::new(); + for t in clauses.split(|c: char| c.is_whitespace() || "[]()".contains(c)) { + if t.starts_with('?') && !t.starts_with("?_") && !vars.contains(&t) { + vars.push(t); + } + } + vars.join(" ") +} + fn temporals(tx: u64) -> [String; 6] { [ String::new(), @@ -295,8 +363,7 @@ fn engine_reads_many_batches() { assert_eq!(rows(&db, "(query [:find ?e :where [?e :big/n 2999]])"), 1); } -/// The executor still runs what the engine does not: two patterns, -/// aggregates, `:as-of` a timestamp, `:db/valid-at`, pseudo-attributes of +/// The executor still runs what the engine does not: aggregates, `:as-of` a timestamp, `:db/valid-at`, pseudo-attributes of /// another entity, a pseudo-attribute pattern planned first, an expression /// rebinding the entity before a pseudo-attribute pattern. #[test] @@ -304,7 +371,6 @@ fn other_queries_stay_on_the_executor() { let db = Minigraf::in_memory().unwrap(); write_round(&db, 0); for q in [ - "(query [:find ?e ?n :where [?e :person/name ?n] [?e :person/age ?a]])", "(query [:find (count ?e) :where [?e :person/name ?n]])", "(query [:find ?e :as-of \"2099-01-01T00:00:00Z\" :where [?e :person/name ?n]])", "(query [:find ?e ?t :where [?e :person/name ?n] [?e :db/valid-at ?t]])", @@ -316,6 +382,9 @@ fn other_queries_stay_on_the_executor() { :where [_ :person/name ?e] [_ :db/tx-count ?t]])", "(query [:find ?n ?t :valid-at :any-valid-time \ :where [?e :person/name ?n] [(+ 1 2) ?e] [?e :db/tx-count ?t]])", + // Pseudo-attributes across joins wait for #545's last part. + "(query [:find ?e ?t :valid-at :any-valid-time \ + :where [?e :person/name ?n] [?e :person/age ?a] [?e :db/tx-count ?t]])", ] { let before = runs(); db.execute(q).unwrap(); @@ -558,3 +627,105 @@ fn dict_cache_is_dropped_after_each_pull() { } assert_eq!(rows, 3002); } + +/// The planner's join choice (decision 3 of the #545 plan): an +/// `IndexNestedLoopJoin` when the entity is bound, a `HashJoin` otherwise, +/// built on the side with the smaller estimate. +#[test] +fn planner_chooses_the_join() { + use super::plan::{JoinKind, Step, plan}; + use crate::query::datalog::parser::parse_datalog_command; + use crate::query::datalog::types::DatalogCommand; + let kinds = |q: &str| -> Vec { + let Ok(DatalogCommand::Query(query)) = parse_datalog_command(q) else { + panic!("expected a query"); + }; + let plan = plan(&query).expect("an engine plan"); + plan.steps + .iter() + .filter_map(|s| match s { + Step::Join(j) => Some(match j.kind { + JoinKind::Probe(_) => "probe".to_string(), + JoinKind::Hash { build_inner } => format!("hash inner={build_inner}"), + }), + _ => None, + }) + .collect() + }; + assert_eq!( + kinds("(query [:find ?e :where [?e :a ?x] [?e :b ?y]])"), + ["probe"] + ); + assert_eq!( + kinds("(query [:find ?e :where [?e :a ?x] [?f :b ?x]])"), + ["hash inner=true"] + ); + assert_eq!( + kinds("(query [:find ?e :where [?e :a 1] [?f :b ?y] [?f :c ?e]])"), + ["hash inner=false", "probe"] + ); + assert_eq!( + kinds("(query [:find ?e :where [?e :a ?x] [?f ?x ?y]])"), + ["hash inner=false"] + ); +} + +/// Joins whose answers span many batches: one probe with more than a batch +/// of matches, a cross product, a table built on the outer side, over +/// committed and pending facts. +#[test] +fn engine_joins_read_many_batches() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("joins.graph")).unwrap(); + let facts: String = (0..2000) + .map(|i| { + format!( + "[:e{i} :big/n {i}] [:e{i} :big/tag :t{}] [:hub :big/has :e{i}]", + i % 7 + ) + }) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + let more: String = (2000..2600) + .map(|i| format!("[:e{i} :big/n {i}] [:hub :big/has :e{i}]")) + .collect(); + db.execute(&format!("(transact [{more}])")).unwrap(); + db.execute("(retract [[:e5 :big/n 5] [:e2001 :big/n 2001]])") + .unwrap(); + assert_eq!( + rows( + &db, + "(query [:find ?e ?n ?t :where [?e :big/n ?n] [?e :big/tag ?t]])" + ), + 1999 + ); + assert_eq!( + rows( + &db, + "(query [:find ?x ?n :where [:hub :big/has ?x] [?x :big/n ?n]])" + ), + 2598 + ); + assert_eq!( + rows( + &db, + "(query [:find ?h ?x :where [?h :big/has ?x] [?x :big/tag :t3]])" + ), + 286 + ); + assert_eq!( + rows( + &db, + "(query [:find ?a ?b :where [?a :big/tag :t1] [?b :big/tag :t2] [(< 0 1)]])" + ), + 286 * 286 + ); + assert_eq!( + rows( + &db, + "(query [:find ?a ?b :where [?a :big/tag ?t] [?b :big/tag ?t]])" + ), + 5 * 286 * 286 + 2 * 285 * 285 + ); +} From b254694c71bdf38670a50d93d884abfdda6a4baf Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 19:37:57 +0530 Subject: [PATCH 3/3] docs: joins on the streaming engine, measurements, test counts (#545) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 1 + CLAUDE.md | 4 ++-- README.md | 2 +- ROADMAP.md | 2 +- docs/BENCHMARKS.md | 18 +++++++++++++++++- docs/TEST_COVERAGE.md | 6 +++--- 6 files changed, 25 insertions(+), 8 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 17d24c591c..c6d5f5450e 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -59,6 +59,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query, and reads inside a `WriteTransaction`, run on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature). - **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545). - **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change. +- **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. Pseudo-attribute patterns in a query of several patterns, `:db/valid-at`, `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`). - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. diff --git a/CLAUDE.md b/CLAUDE.md index 13e060bc3a..97c1e556dc 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -139,7 +139,7 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, then per-fact pseudo-attribute patterns on its entity and expression clauses in `optimizer::plan` order, plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs), `filter.rs` (`Filter`/`Bind` and pseudo-attribute columns over batches), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns with stored attributes and expression clauses in `optimizer::plan` order, or one pattern with per-fact pseudo-attribute patterns on its entity; plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute columns over batches), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1500 tests** (1490 passing, 10 ignored; unit + integration + doc). +**1503 tests** (1493 passing, 10 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 35c603a7ec..b40c686843 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1500 tests +cargo test # run 1503 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index a3b8863be2..ebaee99292 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -93,7 +93,7 @@ Scope — format and storage integrity: Scope — query API: -- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544); joins, negation, aggregates, rules and transaction reads move to it in #545–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). +- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544; joins of patterns and expressions, #545); pseudo-attributes across joins, negation, aggregates, rules and transaction reads move to it in #545–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index fb21656560..ec64008590 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -98,7 +98,23 @@ Single-pattern queries run on the streaming engine since #544 (with expressions | `attribute_scan` peak RSS, `v3` → PR 3 | 11 → 6 MiB | 58 → 7 MiB | 458 → 7 MiB | | point, `:as-of`, `:valid-at`, hot entity | unchanged (16–26 µs; hot 0.3 ms) | unchanged | unchanged | -`attribute_value` reads only the AVET range of its value since #544 PR 1 (#518): 22–24 µs at every scale here, where the table above, before #544, has 24.5 ms, 288 ms and 3.16 s. An attribute scan drained with `next_batch(1000)` now holds one batch: peak RSS no longer grows with the number of rows (1.67M rows at 10M facts in 7 MiB, against a 4 MiB baseline). Before PR 3 the cursor held the whole answer, and in PR 3's first commit the query's id cache still held every entity it returned (189 MiB at 10M). Joins, aggregates and rules still run on the executor and are unchanged (#545–#548). +`attribute_value` reads only the AVET range of its value since #544 PR 1 (#518): 22–24 µs at every scale here, where the table above, before #544, has 24.5 ms, 288 ms and 3.16 s. An attribute scan drained with `next_batch(1000)` now holds one batch: peak RSS no longer grows with the number of rows (1.67M rows at 10M facts in 7 MiB, against a 4 MiB baseline). Before PR 3 the cursor held the whole answer, and in PR 3's first commit the query's id cache still held every entity it returned (189 MiB at 10M). Aggregates and rules still run on the executor and are unchanged (#546–#548). Joins: see below. + +### Joins on the streaming engine (#545) + +Queries of several patterns run on the engine since #545 PR 2: an `IndexNestedLoopJoin` when the next pattern's entity is bound, a `HashJoin` otherwise. A/B on the same idle server, unpinned, `v3` before PR 2 (eab15bb) and PR 2 run one after the other, two rounds each; p50 of the two rounds, peak RSS per shape. + +| Shape | 100K | 1M | +|---|---:|---:| +| `join_2` p50, `v3` → PR 2 | 58.2 ms → 51 µs | 796 ms → 50 µs | +| `join_2` peak RSS | 38 → 4 MiB | 322 → 4 MiB | +| `join_3_selective` p50 | 125 ms → 10.6 ms | 1.67 s → 148 ms | +| `join_3_selective` peak RSS | 40–41 → 7 MiB | 392–462 → 14 MiB | +| `join_3_scan` p50 | 165 ms → 41.1 ms | 2.64 s → 1.12 s | +| `join_3_scan` peak RSS | 48–67 → 14 MiB | 468–480 → 42 MiB | +| point, `:as-of`, `:valid-at`, hot entity, attribute scan | unchanged | unchanged | + +`join_2` probes one entity's range for its one outer row. `join_3_selective` joins on the value position, so it is a `HashJoin` that reads every `:manager` fact into its table: a value probe would need AVET over pending facts, which the pending store does not have (decision 3 of the #545 plan). `join_3_scan` scans the AVET range of `:group 7`, joins `:follows` on its value with a `HashJoin` built on those rows (it streams every `:follows` fact), then probes `:name` per row. 10M runs with #545's last PR. ### Python FFI round trip diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index ba2d2e5728..d0ffd18624 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-14 with `cargo test --quiet` -**Result**: 1,490 passing tests and 10 ignored tests (1,500 total) +**Result**: 1,493 passing tests and 10 ignored tests (1,503 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `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 damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). 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). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `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 (#445). Merged from the v2.x line: `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). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, 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 writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). @@ -14,8 +14,8 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). Query and prepared-query cursors keep their answer and their pages across writes, checkpoints and index rebuilds, and the file stops growing once they close (`tests/cursor_test.rs`); a snapshot leaves out facts appended after it on every scan (`graph::storage`); a crash at every write point of a save with a pinned generation loses no fact and no page, and the reopened database reuses the quarantined ids (`storage::persistent_facts`); the browser withholds free pages a pinned generation may read and releases them once out of force (`storage::pins::split_released`, and a `#[wasm_bindgen_test]` with an open `BrowserDb` cursor). -- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). Lazy cursors (`cursor::tests`, #544 PR 3): one pull reads one internal batch of the scan (operator counters), rows left in a batch need no pull, a closed stream reads nothing more, a filter's counters chain, and a cursor's answer is unchanged by writes and by checkpoints that free the leaves it has yet to read (file-backed) or by later writes (in memory); a read error after some rows are gathered comes on the next call, then the cursor ends (`query::engine::tests`). DICT lookups are cached for one pull only, and provisional ids keep their values across pulls (`query::engine::ids`). -- **Join rules** (`tests/join_rules_test.rs`, 10 tests; #545): a join on a float value pairs `0.0` with `-0.0`, through the hash key and as a shared variable, and a float constant still matches within epsilon; a variable bound to a keyword by one pattern and to the ref of the same entity by another returns the kind from the first pattern in `:where` text order, when the planner runs the patterns in another order, through the attribute position, before and after a rule call, and with a repeated pattern; an expression binding is kept by a later join, and a pseudo-attribute pattern never replaces a value. A unit test checks that `-0.0` and `0.0` hash alike. +- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, expression filters and bindings (including rebinding and failing expressions), pseudo-attribute columns, keyword/UUID/float constants against keywords, refs and UUID-named keywords, and checks which queries stay on the executor and that INT-026 and QRY-007 come first. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). Lazy cursors (`cursor::tests`, #544 PR 3): one pull reads one internal batch of the scan (operator counters), rows left in a batch need no pull, a closed stream reads nothing more, a filter's counters chain, and a cursor's answer is unchanged by writes and by checkpoints that free the leaves it has yet to read (file-backed) or by later writes (in memory); a read error after some rows are gathered comes on the next call, then the cursor ends (`query::engine::tests`). DICT lookups are cached for one pull only, and provisional ids keep their values across pulls (`query::engine::ids`). Joins (#545 PR 2): the oracle matrix adds two- and three-pattern joins on the entity (`IndexNestedLoopJoin`), value and attribute positions (`HashJoin`), cross products, keywords and refs of one entity in both text orders, UUID-named keywords, attributes that name entities, floats `0.0`/`-0.0`, long strings committed and pending, and expressions between joins, at every temporal; joins whose answers span many batches (one probe with more than a batch of matches, cross products, tables built on either side); the planner's join choice; a keyword's entity id (`query::engine::ids`). +- **Join rules** (`tests/join_rules_test.rs`, 10 tests; #545): a join on a float value pairs `0.0` with `-0.0`, through the hash key and as a shared variable, and a float constant still matches within epsilon; a variable bound to a keyword by one pattern and to the ref of the same entity by another returns the kind from the first pattern in `:where` text order, when the planner runs the patterns in another order, through the attribute position, before and after a rule call, and with a repeated pattern; an expression binding is kept by a later join, and a pseudo-attribute pattern never replaces a value (native plan order only: under `wasm` the pattern runs first and binds the variable). Under the `test-oracle` feature the joins among them also run on the streaming engine. A unit test checks that `-0.0` and `0.0` hash alike. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples.