Repository navigation
bench: add benchmarks for window functions, temporal metadata, UDFs, and post-7.4 perf fixes #81
Description
Background
The benchmark suite (benches/minigraf_bench.rs) and BENCHMARKS.md were last updated at Phase 7.4 / v0.13.1. Since then, Phases 7.5–7.7b have added several new query features and a series of O(n²)→O(n log n) performance fixes, none of which have corresponding benchmarks.
This issue tracks all missing benchmarks and the required BENCHMARKS.md update.
Missing benchmark groups
1. Window functions (Phase 7.7a)
Window functions (running_sum, running_count, running_avg, rank, row_number, etc.) run incrementally over an ordered result set using the AggState accumulator path. They are fundamentally different from batch aggregates (separate code path in the executor) and need their own benchmark group.
Add a bench_window function:
fn bench_window(c: &mut Criterion) {
// Setup: DB with N entities, each with a :val Integer attribute.
// Query: (query [:find ?e (running_sum ?v) :where [?e :val ?v]])
// Measure at 1K and 10K facts, sample_size(100).
let mut group = c.benchmark_group("window/running_sum");
for &n in &[1_000usize, 10_000] {
let label = helpers::label(n);
let db = helpers::preload_db(n); // helper that inserts N :val facts
group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, _| {
b.iter(|| {
db.execute("(query [:find ?e (running_sum ?v) :where [?e :val ?v]])")
.unwrap()
});
});
}
group.finish();
// Also benchmark rank / row_number to capture ordering overhead.
let mut group = c.benchmark_group("window/rank");
// similar structure
group.finish();
}Register it in criterion_group!(benches, ..., bench_window, ...).
2. Temporal metadata queries (Phase 7.6)
Phase 7.6 added pseudo-attributes ?tx-time, ?valid-from, ?valid-to (and ?tx-count, ?asserted) that can be bound in query :where clauses. These require extra projection work per result row and have not been measured.
Add a bench_temporal_metadata function:
fn bench_temporal_metadata(c: &mut Criterion) {
// Query: (query [:find ?e ?t :where [?e :val _ :tx-time ?t]])
// Measure at 1K and 10K facts.
let mut group = c.benchmark_group("temporal_metadata/tx_time");
for &n in &[1_000usize, 10_000] {
let db = helpers::preload_db(n);
group.bench_with_input(BenchmarkId::from_parameter(helpers::label(n)), &n, |b, _| {
b.iter(|| {
db.execute("(query [:find ?e ?t :where [?e :val ?v :tx-time ?t]])")
.unwrap()
});
});
}
group.finish();
// Also benchmark :valid-from / :valid-to projection.
}3. UDF aggregates and predicates (Phase 7.7b)
Minigraf::register_aggregate and Minigraf::register_predicate let callers plug in custom Rust functions. The overhead of the closure dispatch path vs. the built-in function-pointer path should be measured.
Add a bench_udf function:
fn bench_udf(c: &mut Criterion) {
// Register a UDF aggregate that sums integers (same semantics as built-in sum).
// Run at 1K and 10K, compare against built-in sum to isolate dispatch overhead.
let mut group = c.benchmark_group("udf/aggregate_sum_dispatch");
for &n in &[1_000usize, 10_000] {
let db = helpers::preload_db(n);
db.register_aggregate("udf_sum", /* ... closure ... */).unwrap();
group.bench_with_input(BenchmarkId::from_parameter(helpers::label(n)), &n, |b, _| {
b.iter(|| {
db.execute("(query [:find (udf_sum ?v) :where [?e :val ?v]])")
.unwrap()
});
});
}
group.finish();
// Also benchmark a UDF predicate filter.
}4. Post-7.4 performance fixes — re-run affected groups
Several O(n²) bugs were fixed after Phase 7.4. The existing benchmark numbers in BENCHMARKS.md predate these fixes and are now stale. Re-run these groups and update the table values:
| Fix | PR | Affected benchmark group |
|---|---|---|
count-distinct/sum-distinct O(n log n) |
#73 | aggregation/count_scale, new aggregation/count_distinct_scale |
| Aggregation grouping O(n log n) | #71 | aggregation/grouped_count_scale, aggregation/with_grouped_sum |
| Or/OrJoin deduplication O(n log n) | #68 | disjunction/or_scale, disjunction/or_join_scale |
contains_fact O(n) in semi-naive |
#72 | recursion/chain, recursion/fanout |
| Regex precompile at parse time | #67 | any query with matches? predicate — add a query/regex_filter sub-benchmark |
| Query optimizer index hints | #69 | query/point_entity, query/join_3pattern |
For count-distinct, also add a dedicated benchmark that exercises the distinct-dedup path with many duplicates:
// In bench_aggregation, add:
let mut group = c.benchmark_group("aggregation/count_distinct_scale");
// 1K and 10K facts, 50% duplicate values.BENCHMARKS.md update instructions
After running the new and updated benchmarks, update BENCHMARKS.md as follows:
-
Add new sections after the existing "Expression Clauses" section:
## Window Functions— table withrunning_sum,rank,row_numberat 1K / 10K, plus a brief O(N) scaling note.## Temporal Metadata— table withtx_time,valid_from,valid_atprojection at 1K / 10K.## UDF Dispatch Overhead— table comparing UDF aggregate vs. built-in aggregate at 1K / 10K.
-
Update stale numbers in:
## Aggregation— updatecount_scale,grouped_count_scale,with_grouped_sum10K numbers; addcount_distinct_scalerow.## Disjunction— updateor_scale,or_join_scale10K numbers.## Recursive Rules— updatechainandfanoutnumbers.## Query Latency— updatepoint_entity10K if optimizer hints produce a measurable change; addregex_filterrow if a new sub-benchmark is added.
-
Add a Phase 7.4 → current summary table (similar to the existing "Phase 7.3 → Phase 7.4 Summary" table) capturing the before/after for each perf fix. Example structure:
## Phase 7.4 → v0.17.0 Performance Summary | Fix | Metric | Before | After | Change | |---|---|---|---|---| | count-distinct O(n log n) | aggregation/count_distinct_scale 10K | ? ms | ? ms | ? | | aggregation grouping O(n log n) | aggregation/grouped_count_scale 10K | 51.550 ms | ? ms | ? | | Or dedup O(n log n) | disjunction/or_scale 10K | 68.929 s | ? s | ? | | contains_fact O(n) | recursion/chain depth_10 | 2.75 ms | ? ms | ? |
-
Update the version reference at the top of
BENCHMARKS.mdfromv0.13.1to the current version and update the "Core query benchmarks were updated in..." line.
How to run
# Run all benchmarks (slow — ~30 min total)
cargo bench
# Run only new groups
cargo bench -- "window"
cargo bench -- "temporal_metadata"
cargo bench -- "udf"
# Re-run specific stale groups
cargo bench -- "aggregation"
cargo bench -- "disjunction"
cargo bench -- "recursion"Criterion writes HTML reports to target/criterion/. Copy the median time from each report into the relevant BENCHMARKS.md table.
Helpers
The benches/helpers/mod.rs module contains preload_db(n) and related setup. Add any new fixture helpers there (e.g., a preload_db_with_duplicates(n, dup_fraction) for the count-distinct benchmark, or a preload_db_with_temporal(n) that inserts facts with explicit valid_from/valid_to for the temporal metadata benchmark).
Acceptance criteria
-
bench_windowfunction added and registered incriterion_group! -
bench_temporal_metadatafunction added and registered -
bench_udffunction added and registered -
count_distinct_scalesub-benchmark added tobench_aggregation -
regex_filtersub-benchmark added tobench_query(formatches?predicate) - All stale 10K numbers in
BENCHMARKS.mdupdated with post-fix measurements - New sections added to
BENCHMARKS.mdfor window, temporal metadata, UDF - Phase 7.4 → v0.17.0 summary table added to
BENCHMARKS.md -
BENCHMARKS.mdversion reference updated at top
Activity
bench: add benchmarks for window functions, temporal metadata, UDFs
bench: add benchmarks for window functions, temporal metadata, UDFs
docs: add new benchmark sections to BENCHMARKS.md (issue #81)
Merge pull request #90 from adityamukho/fix/issue-81-bench-new-features