Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -78,6 +78,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Fixed

- **Window partition scratch obeys `query_memory_limit`** (#765). Each window now charges its partition row indices while they coexist with input rows and earlier result columns, returns `QRY-012` if reserving them fails, and releases the charge after the window or on error. An in-place total sort removes the stable sort's uncharged merge buffer; partition and row order are unchanged.
- **An expression's `=` and `!=` equate a keyword with a ref to the entity it names** (#744). Patterns, joins, `not` bodies and `or` branches treat the keyword `:bob` as equal to a ref to the entity `:bob` names, but `[(= ?g :bob)]` compared the two values as they are, so with `?g` bound to that ref it kept no row and `[(!= ?g :bob)]` kept the row: the same question answered differently by how the query was written, with no error. `=` and `!=` now compare as joins do, in queries, rule bodies, `not` clauses and binding expressions, against a keyword constant, a keyword value or a bound `Val(Ref)`. A keyword still equals only the same keyword, and `<`, `>`, `<=` and `>=` on a keyword or a ref are still a type mismatch (no row).
- **`checkpoint`, `verify` and `rebuild_indexes` inside a `WriteTransaction` return `INT-001` instead of deadlocking** (#734). Called on a thread that holds a `WriteTransaction`, they waited on the write lock that the transaction already held, so the thread hung. They now return `INT-001`, as `execute`, `query`, `fact_log` and `begin_write` already did, and the transaction stays usable. `prepare` and `PreparedQuery::execute`/`query` make the same check; they could not deadlock, but they ran inside the transaction where `execute`/`query` refused. `checkpoint` deadlocked in every release since `WriteTransaction` was added; the fix for it and for the prepared calls ships in v2.x too.
- **A float constant in a pattern matches equal floats only** (#706). A float written in a pattern's value position, or bound to a `$slot` of a prepared query, matched every stored float within an absolute `f64::EPSILON` (about `2.2e-16`), so `[?e :m/x 0.0]` returned an entity whose `:m/x` is `1e-17`, while `[?e :m/x ?v] [(= ?v 0.0)]` did not. Above 1.0 the epsilon is smaller than the gap between adjacent floats, so only floats smaller than about `2.2e-16` in magnitude were affected: every one of them matched `0.0`, and `1e-20` matched `5e-20`. Float constants now compare by IEEE `==`, as joins, predicates and the indexes do: `0.0` matches `-0.0` and nothing else changes. The fix covers patterns in queries, rule bodies and `not` / `or` bodies, on the executor and the streaming engine. Nothing stored was wrong. The same fix ships in v2.0.10.
Expand Down
4 changes: 2 additions & 2 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -138,7 +138,7 @@ cargo run < demos/demo_negation.txt
- `parser/verifier.rs`: test-only (not wasm32) bounded-exhaustive check of the parser against `tests/grammar/grammar.pest` (#643): every 1–3 character string (`parse_edn`) and every balanced token filler up to `MINIGRAF_GRAMMAR_BOUND` (default 3) in 16 command templates (`parse_datalog_command`); pest rejects ⇒ parser rejects, pest accepts ⇒ parser accepts or raises a `SEMANTIC` code; today's drift is `KNOWN_DRIFT`, one entry per cause, removed by its fix (empty: #649, #650, #651 fixed)
- `executor.rs`: `DatalogExecutor` — `transact`/`retract`/`rule` commands, and every query on the engine (`open_query`, `open_rule_query`; planner errors after the pseudo-attribute check, then every predicate the query and its rules name, `QRY-007`); its own query path is gone (#551)
- `matcher.rs`: `edn_to_value`, `edn_to_entity_id`
- `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: partitions, sort, peers) (#547)
- `aggregate.rs`: `Agg` (one aggregate of one group) and `Running` (a window's running value), used by the engine; exact sums (`i128` integers saturated once, fixed-point floats rounded once), `value_order` (one total order of values for window sorts, peers, `rank`, `min`/`max` and `:order-by`), `row_order` (#306), `named_vars` (a window's tie-break variables), `windows` (each window's value per row: charged partition indices, in-place total sort, peers) (#547, #765)
- `functions.rs`: `FunctionRegistry` (built-ins and UDFs; `Clone` shares the closures), `Functions` — the registry a database shares, `RwLock<Arc<FunctionRegistry>>`: a query takes a `snapshot()` when it opens and holds no lock while a UDF runs, so UDFs may call back into the database; registration copies, inserts and swaps (#180). `UdfError`: a `try_register_*` closure's failure, `QRY-014`; `eval_expr`'s `EvalError` is `NoValue` (row dropped) or `Udf` (query fails)
- `evaluator.rs`: `rule_invocation_to_pattern`, the rule limits and their errors
- `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628)
Expand Down Expand Up @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1880 tests** (1866 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
**1887 tests** (1873 passing, 14 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
17 changes: 17 additions & 0 deletions benches/minigraf_bench.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1345,6 +1345,23 @@ fn bench_window(c: &mut Criterion) {
group.finish();
}

// Each distinct :val is its own partition (#765): measures partition
// membership construction and sorting without aggregate work.
{
let mut group = c.benchmark_group("window/many_partitions");
group.sample_size(10);
for &(label, n) in SCALES {
group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| {
let db = helpers::populate_in_memory(n);
b.iter(|| {
db.execute("(query [:find ?e (row-number :over (:partition-by ?v :order-by ?v)) :where [?e :val ?v]])")
.unwrap()
});
});
}
group.finish();
}

// row_number: row number function — similar overhead to rank.
{
let mut group = c.benchmark_group("window/row_number");
Expand Down
5 changes: 3 additions & 2 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -4,9 +4,9 @@

| | Default features | With `--features test-hooks` |
|---|---|---|
| **Passing** | 1,860 | 1,891 |
| **Passing** | 1,873 | 1,904 |
| **Ignored** | 14 | 15 |
| **Total** | 1,874 | 1,906 |
| **Total** | 1,887 | 1,919 |

**Verified**: 2026-10-26 with `cargo test --quiet` (and `--features test-hooks`).

Expand Down Expand Up @@ -389,6 +389,7 @@ These tests compare the database against an independent answer rather than a sin
- `QRY-012` names the holder over the limit (each operator, `IdSpace`, `Recursive`, `Distinct` and `Relations`), and its allocator form through the `try_reserve` test hook;
- a cursor returns rows, then `QRY-012`, then nothing; `rewind` and `close` release;
- the planner builds a keyless join on the side with the smaller product estimate (#575's shape, a selective outer side, a tie, reordering off).
- Five engine unit tests (#765) cover the exact limit while partition indices overlap input and prior window results, allocator refusal and charge release on errors, empty input, and unchanged row-number, rank, lag and lead over tied rows and interleaved float partitions.
- `meter.rs` (4 unit tests) checks charge, release, drop, peak and the allocator form.
- `Aggregate` charges its sorted map of groups until every row is built, and lets its hash table and group rows go first, with `sum-distinct` members charged once (`aggregate_finish_charges_its_sorted_groups`, `aggregate_finish_keeps_sum_distinct_members_charged_once`).
- **Join rules** (`tests/join_rules_test.rs`, 15 tests; #545, #744)
Expand Down
132 changes: 98 additions & 34 deletions src/query/datalog/aggregate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -667,6 +667,8 @@ pub(crate) struct WindowColumn {
/// engine's meter type.
pub(crate) trait WindowColumnMeter {
fn charge(&mut self, bytes: usize) -> Result<()>;
fn uncharge(&mut self, bytes: usize);
/// On refusal, release `charged` and return `QRY-012`.
fn reserve(
&mut self,
result: std::result::Result<(), TryReserveError>,
Expand All @@ -677,6 +679,36 @@ pub(crate) trait WindowColumnMeter {
fn charge_payload(&mut self, value: &Value) -> Result<usize>;
}

/// The row-index allocation held while a window is sorted and evaluated.
/// The vector is declared after this guard, so it is dropped before its
/// charge is released on every return path.
struct WindowScratch<'a, M: WindowColumnMeter> {
meter: &'a mut M,
bytes: usize,
}

impl<'a, M: WindowColumnMeter> WindowScratch<'a, M> {
fn new(meter: &'a mut M, bytes: usize) -> Result<Self> {
meter.charge(bytes)?;
Ok(Self { meter, bytes })
}

fn reserve(&mut self, result: std::result::Result<(), TryReserveError>) -> Result<()> {
let result = self.meter.reserve(result, self.bytes, self.bytes);
if result.is_err() {
// WindowColumnMeter::reserve has already undone this charge.
self.bytes = 0;
}
result
}
}

impl<M: WindowColumnMeter> Drop for WindowScratch<'_, M> {
fn drop(&mut self) {
self.meter.uncharge(self.bytes);
}
}

/// The value of each window of `find` for each row (spec §4), one list per
/// window in `:find` order, by row position. `rows` holds each row's
/// values of the [`named_vars`] of `find`, which hold every variable a
Expand Down Expand Up @@ -710,58 +742,89 @@ pub(crate) fn windows(
};
let var = ws.var.as_deref().and_then(col);
let order = col(&ws.order_by);
let mut partitions: BTreeMap<&Value, Vec<usize>> = BTreeMap::new();
for r in 0..rows.len() {
let part = ws.partition_by.as_deref().and_then(col);
partitions.entry(read(r, part)).or_default().push(r);
let part = ws.partition_by.as_deref().and_then(col);
let index_bytes = rows
.len()
.checked_mul(size_of::<usize>())
.ok_or_else(|| err_coded!(ErrorCode::Qry012, "Window row-index size overflow"))?;
let mut scratch = WindowScratch::new(meter, index_bytes)?;
let mut keyed = Vec::new();
scratch.reserve(keyed.try_reserve_exact(rows.len()))?;
keyed.extend(0..rows.len());
let row_cmp = |a: usize, b: usize| {
let by_key = match ws.order {
Order::Asc => value_order(read(a, order), read(b, order)),
Order::Desc => value_order(read(b, order), read(a, order)),
};
by_key
.then_with(|| {
rows.get(a)
.into_iter()
.flatten()
.zip(rows.get(b).into_iter().flatten())
.map(|(x, y)| value_order(x, y))
.find(|o| o.is_ne())
.unwrap_or(Ordering::Equal)
})
.then(a.cmp(&b))
};
if let Some(partition_col) = part {
keyed.sort_unstable_by(|&a, &b| {
read(a, Some(partition_col))
.cmp(read(b, Some(partition_col)))
.then_with(|| row_cmp(a, b))
});
} else {
keyed.sort_unstable_by(|&a, &b| row_cmp(a, b));
}

// Charge slots before allocating, then payloads as each slot is
// filled. The outer vector's entry stays charged until it is dropped.
let slots = rows.len().saturating_mul(size_of::<Value>());
let entry = size_of::<WindowColumn>();
let charged = slots.saturating_add(entry);
meter.charge(charged)?;
meter.reserve(out.try_reserve(1), charged, entry)?;
scratch.meter.charge(charged)?;
scratch.meter.reserve(out.try_reserve(1), charged, entry)?;
let mut values = Vec::new();
meter.reserve(values.try_reserve_exact(rows.len()), charged, slots)?;
scratch
.meter
.reserve(values.try_reserve_exact(rows.len()), charged, slots)?;
values.resize(rows.len(), Value::Null);
let mut bytes = slots;
for mut keyed in partitions.into_values() {
keyed.sort_by(|&a, &b| {
let by_key = match ws.order {
Order::Asc => value_order(read(a, order), read(b, order)),
Order::Desc => value_order(read(b, order), read(a, order)),
};
by_key
.then_with(|| {
rows.get(a)
.into_iter()
.flatten()
.zip(rows.get(b).into_iter().flatten())
.map(|(x, y)| value_order(x, y))
.find(|o| o.is_ne())
.unwrap_or(Ordering::Equal)
let mut offset = 0;
while let Some(&first) = keyed.get(offset) {
let end = part.map_or(keyed.len(), |partition_col| {
keyed
.iter()
.skip(offset + 1)
.position(|&r| {
read(r, Some(partition_col))
.cmp(read(first, Some(partition_col)))
.is_ne()
})
.then(a.cmp(&b))
.map_or(keyed.len(), |n| offset + 1 + n)
});
let partition = keyed
.get(offset..end)
.ok_or_else(|| err_coded!(ErrorCode::Int032, "window partition bounds invalid"))?;

// Row offsets use the physical row order, not aggregate peer groups.
if matches!(ws.func, WindowFunc::Lag | WindowFunc::Lead) {
for (pos, &row) in keyed.iter().enumerate() {
for (pos, &row) in partition.iter().enumerate() {
let adjacent = if matches!(ws.func, WindowFunc::Lag) {
pos.checked_sub(1)
} else {
pos.checked_add(1)
};
let neighbor = adjacent.and_then(|p| keyed.get(p));
let neighbor = adjacent.and_then(|p| partition.get(p));
let source = neighbor.map_or(&NULL, |&r| read(r, var));
let payload = meter.charge_payload(source)?;
let payload = scratch.meter.charge_payload(source)?;
bytes = bytes.saturating_add(payload);
if let Some(v) = values.get_mut(row) {
*v = source.clone();
}
}
offset = end;
continue;
}

Expand All @@ -770,19 +833,19 @@ pub(crate) fn windows(
_ => Some(Running::new(ws, registry)?),
};
let mut start = 0;
while let Some(&first) = keyed.get(start) {
let end = keyed
while let Some(&first) = partition.get(start) {
let peer_end = partition
.iter()
.skip(start + 1)
.position(|&r| value_order(read(r, order), read(first, order)).is_ne())
.map_or(keyed.len(), |n| start + 1 + n);
let peers = keyed.get(start..end).unwrap_or(&[]);
.map_or(partition.len(), |n| start + 1 + n);
let peers = partition.get(start..peer_end).unwrap_or(&[]);
if let Some(acc) = running.as_mut() {
for &r in peers {
acc.step(read(r, var))?;
}
}
for (pos, &r) in (start..end).zip(peers) {
for (pos, &r) in (start..peer_end).zip(peers) {
let (value, payload) = match (&running, &ws.func) {
(Some(acc @ (Running::Min(_) | Running::Max(_))), _) => {
let best = match acc {
Expand All @@ -791,12 +854,12 @@ pub(crate) fn windows(
}
_ => unreachable!(),
};
let payload = meter.charge_payload(best)?;
let payload = scratch.meter.charge_payload(best)?;
(acc.value()?, payload)
}
(Some(acc), _) => {
let value = acc.value()?;
let payload = meter.charge_payload(&value)?;
let payload = scratch.meter.charge_payload(&value)?;
(value, payload)
}
(None, WindowFunc::RowNumber) => (position(pos)?, 0),
Expand All @@ -807,8 +870,9 @@ pub(crate) fn windows(
*v = value;
}
}
start = end;
start = peer_end;
}
offset = end;
}
out.push(WindowColumn { values, bytes });
}
Expand Down
Loading
Loading