Documentation
¶
Overview ¶
Package cyclicjoin holds the permanent benchmarks for the fused cyclic expand (rmp #2157, measured under #2159).
Both arms run in ONE process ¶
Every benchmark here measures the fused operator against the two-Expand plan INSIDE a single binary, toggled by EngineOptions.EnableCyclicIntersect, rather than by comparing two commits. That is deliberate and follows sprint 313's finding: `bench-history.sh` compares runs back-to-back by construction, and on this machine a byte-identical control produced 22 of 36 "significant" rows spanning −11%…+4%, inventing two phantom regressions. A same-process A/B is immune to that class of error because both arms see the same binary, the same fixture and the same thermal state, and `-count` interleaves them.
The consequence for the record: a same-process run must NOT take a numbered LEDGER row. Sprint 314's row is deliberately unnumbered for this reason — `bench-history.sh` uses the previous numbered file as its baseline, so a heterogeneous benchmark set in that chain leaves the next curated run with no common benchmark names and an empty comparison.
The queries must be UNLABELLED ¶
bench/expandinto's queries are labelled (`(a:P)-[:K]->…`) and would measure nothing here: a label predicate interposes a Selection between the hops, so ir.Expand.Child is not an *ir.Expand and the fusion correctly DECLINES. The fusing queries below are therefore type-only or untyped. LabelledTriangleQuery is kept precisely as the non-qualifying control that proves the predicate leaves declined shapes untouched.
What the claim is, and what it is NOT ¶
The sprint was opened on `Θ(m²) → Θ(m^1.5)`. SPIKE #2155 REFUTED that as a description of GoGraph's cost: the per-graph work terms are `Σ_v d_in(v)·d_out(v)` for the binary-join plan and `Σ_(a,b) min(d_out(b), d_in(a))` for the intersection, and those are EXACTLY EQUAL on any regular graph. Measured exponents in m were 1.000/1.000 on a uniform fixture and 1.112/1.008 on a power-law one. So these benchmarks do not try to demonstrate an asymptotic win. They measure what the SPIKE established is actually available — fewer materialised intermediates and a sequential merge in place of a per-candidate probe — and they report the fitted exponents so the record states the shape of the cost rather than a single ratio.
Index ¶
Constants ¶
const AcyclicQuery = `MATCH (a)-[:K]->(b)-[:K]->(c) RETURN count(*) AS n`
AcyclicQuery is the other non-qualifying control: nothing closes, so no hop ever carries IntoVar and the predicate cannot fire.
const ClosingQuery = `MATCH (a)-[:K]->(b)-[:K]->(a) RETURN count(*) AS n`
ClosingQuery is the 2-cycle — the motivating audit's own §2.3 shape. It fuses too, which was not anticipated when the operator was written.
const LabelledTriangleQuery = `MATCH (a:P)-[:K]->(b:P)-[:K]->(c:P)-[:K]->(a) RETURN count(*) AS n`
LabelledTriangleQuery is a NON-QUALIFYING control: the label predicates interpose a Selection between the hops, so the fusion declines and both arms must measure the same plan.
const SquareQuery = `MATCH (a)-[:K]->(b)-[:K]->(c)-[:K]->(d)-[:K]->(a) RETURN count(*) AS n`
SquareQuery closes a 4-cycle. Only its LAST hop closes, so the fusion is the same single 2-way intersection as the triangle's — measured to keep on record that a longer cycle adds open hops, not intersections.
const TriangleQuery = `MATCH (a)-[:K]->(b)-[:K]->(c)-[:K]->(a) RETURN count(*) AS n`
TriangleQuery is the headline fusing shape: a directed 3-cycle whose last two hops fuse. Type-only, so no Selection is interposed.
Variables ¶
This section is empty.
Functions ¶
func SeedPowerLaw ¶
SeedPowerLaw builds a Holme-Kim style graph — preferential attachment with triadic closure — which yields a heavy-tailed degree distribution AND real triangles. This is the realistic social shape, and the only regime in which the SPIKE measured any asymptotic separation at all (exponent 1.112 against 1.008).
The RNG is explicitly seeded so the fixture is deterministic and the numbers are reproducible; Date.now-style nondeterminism in a benchmark fixture would make every recorded figure unreproducible.
func SeedUniform ¶
SeedUniform builds a ring of n nodes where node k has out-edges to k+1 … k+degree plus a back-edge to k−1, so every node has the same in- and out-degree and triangles genuinely exist.
A uniform-degree fixture is the honest FLOOR for this operator, not a flattering case: the SPIKE proved the two plans' work terms are exactly equal here, so whatever this measures is the constant-factor and materialisation difference with no skew advantage whatsoever.
Types ¶
This section is empty.
Source Files