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
5 changes: 4 additions & 1 deletion .github/workflows/binary-size.yml
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,10 @@ jobs:
name: Check release binary size
runs-on: ubuntu-latest
env:
SIZE_LIMIT_BYTES: 1228800 # 1200 KiB — raised from 1 MiB for #277's structured error codes; see PHILOSOPHY.md §4
# 1230 KiB: 1200 KiB (raised from 1 MiB for #277's structured error codes) plus a
# temporary 30 KiB while the streaming engine and the executor both ship (#473).
# Back to 1200 KiB when #551 removes the executor's query path. See PHILOSOPHY.md §4.
SIZE_LIMIT_BYTES: 1259520
steps:
- name: Checkout code
uses: actions/checkout@v4
Expand Down
3 changes: 2 additions & 1 deletion CHANGELOG.md

Large diffs are not rendered by default.

4 changes: 2 additions & 2 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -140,7 +140,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: patterns, expression clauses, `not`/`not-join` and `or`/`or-join` without rule invocations, in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; 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 steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `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`/`rewind`/`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, expression clauses, `not`/`not-join` and `or`/`or-join` without rule invocations, in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, or aggregates with `:with`; windows stay on the executor), `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 steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `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`/`rewind`/`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)

Expand Down Expand Up @@ -205,7 +205,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1616 tests** (1606 passing, 10 ignored; unit + integration + doc).
**1620 tests** (1610 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.
Expand Down
4 changes: 3 additions & 1 deletion PHILOSOPHY.md
Original file line number Diff line number Diff line change
Expand Up @@ -113,7 +113,9 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s
#277's structured error codes — 130 documented codes across 6 categories
cannot fit in 1MB even with opt-level="z", LTO, codegen-units=1, and
strip=symbols all already applied; see CI's `binary-size.yml` for the
enforced limit)
enforced limit). On the v3 branch the gate allows a temporary 30 KiB more
(1,230 KiB) while the streaming engine and the old executor both ship
(#473); it returns to 1,200 KiB when #551 removes the executor's query path
- No runtime dependencies (no JVM, no Python, no Node.js)

**Anti-pattern**: Requiring external services, libraries, or runtimes to function.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

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

Expand Down
14 changes: 14 additions & 0 deletions docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -130,6 +130,20 @@ At 10M facts with PR 3 (same server, two rounds; the PR 2 code is unchanged for

The pseudo-attribute pattern reads the `:db/tx-count` column that the `:name` probe fills for its one row.

### Aggregates on the streaming engine (#547 PR 2)

`count` is `[:find (count ?v) :where [?e ?a ?v]]` (every fact, 1 row); `count_grouped` is `[:find ?g (count ?e) :where [?e :group ?g]]` (100 rows). Before PR 2 every aggregate query ran on the executor, which holds every binding before grouping. A/B on the same idle server, `v3` (234cc3e, with the `count` shape added) then PR 2; p50 and peak RSS.

| Shape | 100K | 1M | 10M |
|---|---:|---:|---:|
| `count` p50, `v3` → PR 2 | 207 → 44 ms | 3.01 s → 457 ms | 29.6 s → 4.46 s |
| `count` peak RSS | 97 → 7 MiB | 728 → 7 MiB | 6,619 → 7 MiB |
| `count_grouped` p50 | 31.4 → 5.9 ms | 397 → 61 ms | 4.51 s → 614 ms |
| `count_grouped` peak RSS | 14 → 5 MiB | 97 → 7 MiB | 901 → 7 MiB |
| every other shape | unchanged | unchanged | unchanged |

An ungrouped aggregate holds one set of accumulators, and `count` reads no value, so memory is flat across scales; a grouped one holds one entry per group.

### Python FFI round trip

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

Large diffs are not rendered by default.

5 changes: 5 additions & 0 deletions examples/perf_envelope.rs
Original file line number Diff line number Diff line change
Expand Up @@ -553,6 +553,11 @@ fn shapes(e: usize, tx_half: u64, hot_tx_half: u64) -> Vec<Shape> {
),
rows: 1,
},
Shape {
name: "count",
query: "[:find (count ?v) :where [?e ?a ?v]]".into(),
rows: 1,
},
Shape {
name: "count_grouped",
query: "[:find ?g (count ?e) :where [?e :group ?g]]".into(),
Expand Down
29 changes: 28 additions & 1 deletion src/query/datalog/aggregate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -9,7 +9,7 @@ use crate::graph::types::Value;
use anyhow::Result;
use std::any::Any;
use std::cmp::Ordering;
use std::collections::BTreeSet;
use std::collections::{BTreeMap, BTreeSet};

/// The class of a value in [`value_order`]: numbers, strings, booleans,
/// refs, keywords, `nil`.
Expand Down Expand Up @@ -505,6 +505,33 @@ impl Agg {
}
}

/// The groups of an aggregate query, by their grouping values as `Value`'s
/// `Ord` compares them: the values each group returns, and one accumulator
/// per aggregate, in `:find` order.
pub(crate) type Groups = BTreeMap<Vec<Value>, (Vec<Value>, Vec<Agg>)>;

/// Finish `groups` in key order (spec §3.3): each group's values and its
/// aggregates' results. A group whose aggregate gives `INT-042` is dropped;
/// any other error, the first in `:find` order of the first group, fails.
/// `funcs` names each aggregate, for the messages.
pub(crate) fn finish_groups(
groups: Groups,
funcs: &[&str],
) -> Result<Vec<(Vec<Value>, Vec<Value>)>> {
let mut out = Vec::with_capacity(groups.len());
'group: for (shown, accs) in groups.into_values() {
let mut results = Vec::with_capacity(accs.len());
for (acc, func) in accs.into_iter().zip(funcs) {
match acc.finish(func)? {
Some(v) => results.push(v),
None => continue 'group,
}
}
out.push((shown, results));
}
Ok(out)
}

/// A window function's running value over a sorted partition (spec §4.2).
pub(crate) enum Running {
Count(i64),
Expand Down
46 changes: 27 additions & 19 deletions src/query/datalog/executor.rs
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
use super::aggregate::{Agg, Running, named_vars, value_order};
use super::aggregate::{Agg, Groups, Running, finish_groups, named_vars, value_order};
use super::evaluator::{StratifiedEvaluator, evaluate_not_join};
use super::functions::FunctionRegistry;
use super::matcher::{PatternMatcher, edn_to_entity_id, edn_to_value};
Expand Down Expand Up @@ -1673,22 +1673,34 @@ fn compute_aggregation(
})
.collect();

// Groups in key order, as `Value`'s `Ord` compares keys.
use std::collections::BTreeMap;
let mut groups: BTreeMap<Vec<Value>, Vec<Agg>> = BTreeMap::new();
// Groups in key order, as `Value`'s `Ord` compares keys. Each holds the
// values it returns: of the key values `Ord` finds equal (`-0.0` and
// `0.0`, NaNs), the least by `value_order`, whatever the input order.
let mut groups = Groups::new();
for b in bindings {
let key: Vec<Value> = group_var_names
.iter()
.map(|v| b.get(*v).cloned().unwrap_or(Value::Null))
.collect();
let accs = match groups.entry(key) {
let (shown, accs) = match groups.entry(key) {
std::collections::btree_map::Entry::Occupied(e) => e.into_mut(),
std::collections::btree_map::Entry::Vacant(e) => e.insert(
aggs.iter()
.map(|(_, func, _)| Agg::new(func, registry))
.collect::<Result<Vec<_>>>()?,
),
std::collections::btree_map::Entry::Vacant(e) => {
let shown = e.key().clone();
e.insert((
shown,
aggs.iter()
.map(|(_, func, _)| Agg::new(func, registry))
.collect::<Result<Vec<_>>>()?,
))
}
};
for (s, v) in shown.iter_mut().zip(&group_var_names) {
if let Some(v) = b.get(*v)
&& value_order(v, s).is_lt()
{
*s = v.clone();
}
}
for (acc, (_, _, var)) in accs.iter_mut().zip(&aggs) {
if let Some(v) = b.get(*var) {
acc.step(v);
Expand All @@ -1706,19 +1718,15 @@ fn compute_aggregation(
})
.collect();

let funcs: Vec<&str> = aggs.iter().map(|(_, func, _)| *func).collect();
let mut results: Vec<Binding> = Vec::new();
'group: for (key, accs) in groups {
for (shown, values) in finish_groups(groups, &funcs)? {
let mut binding = Binding::new();
for (v, val) in plain.iter().zip(key) {
for (v, val) in plain.iter().zip(shown) {
binding.insert((*v).to_string(), val);
}
for (acc, (i, func, _)) in accs.into_iter().zip(&aggs) {
match acc.finish(func)? {
Some(v) => {
binding.insert(format!("__agg_{}", i), v);
}
None => continue 'group,
}
for (v, (i, _, _)) in values.into_iter().zip(&aggs) {
binding.insert(format!("__agg_{}", i), v);
}
results.push(binding);
}
Expand Down
Loading
Loading