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
2 changes: 1 addition & 1 deletion .github/workflows/binary-size.yml
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,7 @@ jobs:
name: Check release binary size
runs-on: ubuntu-latest
env:
SIZE_LIMIT_BYTES: 1259520 # 1230 KiB — raised from 1 MiB for #277's structured error codes, from 1200 KiB for #306's :order-by/top-k; see PHILOSOPHY.md §4
SIZE_LIMIT_BYTES: 1263616 # 1234 KiB — #277 error codes, #306 top-k, #723 ancestor join planning; see PHILOSOPHY.md §4
steps:
- name: Checkout code
uses: actions/checkout@v4
Expand Down
2 changes: 2 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -9,6 +9,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Performance

- **Avoid whole-attribute reads for selective in-memory ancestors** (#723). Eligible three-pattern recursive delta runs can start from a small derived relation and probe stored facts by entity, preserving the same semi-naive ranges and answers. The choice is reconsidered each round using bounded pending-index counts. Populated committed generations retain AVET value probes; general value joins retain their existing behavior. No persistent index, dependency, API or format change. The approved v3 binary-size budget increases from 1,230 to 1,234 KiB for this change.

- **Skip sorting proven ordered input** (#641, first slice). Plain queries can omit `Sort` when a committed integer, float, or Boolean range already provides the complete ascending result order. Attribute scans use AVET; entity-and-attribute scans retain their selective EAVT range. `:offset` and `:limit` then stop reading early, so memory-limit (`QRY-012`) or I/O errors in unread later input may be avoided. The proof uses the query's pinned reader, including a large write transaction's working trees, and rejects pending or staged records in the source range, mixed kinds, unsupported comparators, tie suffixes, order-changing operators, user callbacks and `collect-set`. Unproven queries retain their original plan.

- **Release completed count groups** (#641, second slice). A plain query with exactly one proved scalar grouping key, no `:with` or windows, and only built-in `count`/`count-distinct` holds one active group plus bounded batches. Completed groups are released, and a limit can stop before later groups; one large distinct group still grows with its members. Integer, Boolean and committed-float keys qualify, including mixed integer/float grouping in `Value::Ord` order. A unique single-kind group key can also remove the final ascending Sort; mixed numeric keys retain numeric Sort. Fallible aggregates, callbacks and `collect-set` retain full-input validation and later errors. Small selective grouped queries pay proof startup cost, and a single growing group is slower (see `docs/BENCHMARKS.md`). No new aggregate syntax or function is added.
Expand Down
5 changes: 3 additions & 2 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -16,7 +16,7 @@ Minigraf follows the "SQLite for bi-temporal graph databases" philosophy:
- **Zero-configuration** - No setup, no config files, just works
- **Embedded-first** - Library not server, in-process execution
- **Single-file database** - One portable `.graph` file
- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,230 KiB enforced on v3 since #306; see PHILOSOPHY.md §4)
- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,234 KiB enforced on v3 since #723; see PHILOSOPHY.md §4)
- **Cross-platform** - Native, WASM, mobile, embedded
- **Reliability over features** - Do less, do it perfectly
- **Bi-temporal first-class** - Time travel is a core feature, not addon
Expand Down Expand Up @@ -218,7 +218,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**2000 tests** (1983 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
**2005 tests** (1988 passing, 17 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.

The #760 deterministic storage suite adds three native unit tests in a separate `--cfg minigraf_shuttle` build, outside the default count. Run only `graph::storage::deterministic::` with that cfg; ordinary unit tests do not enter its scheduler. `deterministic-schedules.yml` runs relevant v3 PRs on Linux/macOS/Windows plus Linux MSRV, and larger nightly/manual searches with replay artifacts. The identical main workflow activates the v3 schedule after both PRs merge. See `docs/testing/deterministic-schedules.md` for scope, controls and findings.
Expand All @@ -230,6 +230,7 @@ The #760 deterministic storage suite adds three native unit tests in a separate
**v2.0.5 released** (2026-10-11) — short-file open refused with STG-045 (#506), commit after a torn WAL entry no longer lost, WAL-007 (#513); backported rule-query `max_results` (#528), all-checkpointed WAL removal (#457) and `usize::MAX` close-time save (#476); weekly soak test (#392), real coverage gates (#396). **v2.0.4** (2026-10-08) — `BrowserDb` IndexedDB flush returns an error for an unreadable dirty page (#470); golden-file v7 corpus (#391) and SIGKILL committed-data crash test (#384). **v2.0.3** (2026-10-06) — data-integrity patch under the support policy: indexed queries with >65,535 uncheckpointed facts (#445), tx counter rewound on reopen next to an already-checkpointed WAL (#447). **v2.0.2** (2026-09-27) — last planned v2.x feature/fix release: query fixes (#297, #405, #407, #410), directory fsync (#389), point-query/attribute-scan/checkpoint perf mitigations (#323, #381, #315), CI policy checks (#395), support policy and tiers (#397, #399, #400). **v2.0.1** (2026-09-25) fixed index rebuild on open (#370). **v2.0.0** introduced kernel file locking (#317, #304), structured runtime error codes (#277), `OpenOptions` `#[non_exhaustive]`, and an MSRV of Rust 1.89. See `CHANGELOG.md` for the full rationale and release history.

Current plan (see `ROADMAP.md` and the milestones):
- **In-memory ancestors (#723)**: eligible positive three-pattern delta runs retain an entity-first alternative with the same `Old`/`Delta`/`Full` ranges and separately planned head slots. Each round can select it when the committed dictionary is empty, the source relation has at most 128 rows and no stored records, and a capped AEVT count favors entity probes over building an uncached pending value map. Populated committed generations keep AVET probes. No additional write-time index.
- **v2.x** (`main`, format v7) now gets only data-integrity and security fixes as patch releases (v2.0.3 is the first); v2.0.2 was the last planned v2.x release.
- **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, sliding row frames #183, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`.
- **Input order (#641)** targets v3.0.0 in three slices: committed scalar Sort omission, one-group count/count-distinct and partition-at-a-time windows are implemented in the dependent PRs for `v3`. The reviewed design, fallback scope and acceptance gates are in `docs/superpowers/specs/2026-10-28-641-input-order-design.md`.
Expand Down
5 changes: 4 additions & 1 deletion PHILOSOPHY.md
Original file line number Diff line number Diff line change
Expand Up @@ -115,7 +115,10 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s
strip=symbols all already applied; see CI's `binary-size.yml` for the
enforced limit). v3.0.0 raises the enforced limit to 1,230 KiB for
`:order-by`/`:offset` and the top-k `Sort` (#306), whose ~11 KiB did not
fit the 2 KiB left after the streaming engine (#473) and set values (#316)
fit the 2 KiB left after the streaming engine (#473) and set values (#316).
The approved #723 ancestor-join optimization raises it to 1,234 KiB:
the measured increase is 2,720 bytes, avoiding a whole-attribute value
map for selective in-memory recursion without adding a storage index
- No runtime dependencies (no JVM, no Python, no Node.js)

**Anti-pattern**: Requiring external services, libraries, or runtimes to function.
Expand Down
2 changes: 2 additions & 0 deletions README.md
Original file line number Diff line number Diff line change
Expand Up @@ -34,6 +34,8 @@ The unreleased v3.0.0 branch adds bounded sliding windows such as `(avg ?salary

On v3.0.0, an ascending value-only query such as `[:find ?v :where [?e :score ?v] :order-by [?v] :limit 10]` can read directly in index order and stop early when all committed `:score` history has one value kind (integer, float, or Boolean) and its source range has no pending writes. A query whose full order cannot be proved uses the existing sort (#641). Built-in `count` and `count-distinct` can also release completed groups when one committed integer/Boolean/float key is proved ordered (including mixed integer/float groups), with no `:with`, windows, callbacks or `collect-set`. Memory then follows the active group and batches; distinct members within one group still grow. Other aggregates keep full-input validation. When every built-in window uses the same proved nonconstant partition key, the engine can also finish and release one partition at a time. Its memory follows the largest partition plus bounded batches; one growing partition still grows. Unpartitioned windows, incompatible keys, aggregate queries, callbacks and `collect-set` keep full-input evaluation. A surrounding sort or distinct operation can still require more memory.

On the unreleased v3 branch, selective in-memory ancestor queries can use entity probes instead of reading the whole edge attribute (#723). This is a query-planning optimization; it adds no storage index or configuration.

**Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction.

## Why Datalog?
Expand Down
2 changes: 2 additions & 0 deletions ROADMAP.md
Original file line number Diff line number Diff line change
Expand Up @@ -94,6 +94,8 @@ Scope — format and storage integrity:

Scope — query API:

- Selective in-memory ancestor joins avoid building a whole-attribute value map (#723; implemented for eligible three-pattern recursive bodies). Populated committed generations keep AVET probes; general in-memory value joins remain unchanged.

- Optional `:distinct` result tuples, preserving bag output by default (#493; done on `v3`)
- `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0)
- Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182)
Expand Down
43 changes: 43 additions & 0 deletions docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,49 @@

This document records reproducible local benchmark snapshots. Completed release-performance history belongs in the [CHANGELOG](../CHANGELOG.md); continuous CI history is available on [Bencher](https://bencher.dev/perf/minigraf/plots).

## Selective in-memory ancestors (#723, unreleased)

**Date**: 2026-10-29 · **Baseline**: `v3` at `756ffea20`. Both revisions
used the same dependency lockfile and the existing `bench` profile. Prebuilt
Criterion executables ran sequentially on the idle bench machine, pinned
to the same NUMA node, with 10 samples, 3 seconds of warm-up and 5 seconds
of requested measurement time. Builds and tests finished before timing.
The estimates below are Criterion's fitted per-query times, not individual
query percentiles.

| Workload | Baseline | Change |
|---|---:|---:|
| `recursion/ancestors/w10_d4` | 15.049 ms | 0.297 ms |
| same ancestors, second pair | 14.487 ms | 0.286 ms |
| `recursion/chain/depth_10` | 0.522 ms | 0.542 ms |
| `recursion/chain/depth_100` | 21.515 ms | 21.651 ms |
| `recursion/fanout/w10_d3` | 19.663 ms | 19.817 ms |

The ancestor query is about 50 times faster in both pairs. Criterion found
no significant change for the depth-100 chain or fanout. The depth-10 chain
regressed by about 4% (Criterion's mean-change estimate); the added planning
and selection work is visible on this small query. General value joins
retain their existing behavior. Populated committed generations continue
to use AVET probes; this optimization targets eligible positive
three-pattern recursive bodies with small derived demand and preserves the
original value-head binding.

The regression test returns three ancestors in a 1,999-edge tree with a
128 KiB query budget, including a staged edge replacement. The baseline
fails with `QRY-012` while building the pending value map. No persistent
value index or write-time cost is added.

Release size with the same toolchain and lockfile: baseline 1,258,712 bytes,
change 1,261,432 bytes (+2,720). The maintainer approved raising the v3 gate
from 1,230 to 1,234 KiB (1,263,616 bytes), leaving 2,184 bytes of headroom.
The budget and its rationale are recorded in PHILOSOPHY.md §4.

Reproduce with `cargo bench --bench minigraf_bench -- '^recursion/'` on each
revision. For an isolated timed phase, build with `--no-run` first and invoke
the resulting benchmark executable with `'^recursion/' --bench` under the
same CPU/memory affinity. The [raw Criterion output](benchmarks/723-recursive-joins.txt)
contains both ancestor pairs and the control shapes.

## Bounded recursive entity probes (#672, unreleased)

**Date**: 2026-10-28 · **Baseline**: `v3` at `d0ad89c1d` · **Machine**:
Expand Down
Loading
Loading