nordisk/knut

knut-rel2graph-bench — rel2graph benchmark + correctness harness (2026-07-30)

A scalable benchmark + correctness harness for bifröst's rel2graph engine. It generates deterministic synthetic relational databases, runs the real bifröst mapping fabric over them through its public API only, and asserts the resulting property graph is CORRECT while measuring how construction time scales. Additive: a new workspace crate that USES rel2graph; it does not touch the inference/codegen.

0. What it exercises

bifröst is the rel2graph engine (see .nornir/rel2graph-codegen-design.md). A reviewed [MappingSpec] is lowered by the Transform fabric into a [GraphMutation] (VertexSets + EdgeSets) — and, canonically, into a [GraphPlan] projected to (a) a PySpark job and (b) a thund Pipeline. This harness drives both seams with no live DB:

• correctness is asserted at the GraphMutation level (VertexSet / EdgeSet);
• shape agreement is asserted at the GraphPlan / to_thund_pipeline level;
• any live FalkorDB load is out of scope here (gated #[ignore] elsewhere in knut).

1. Correctness rules (the criteria — with sources)

Relational→property-graph direct mapping is a studied transform. The rules the harness enforces follow the R2PG-DM direct mapping and the recent complete direct-mapping treatment:

1. Table → node label; row → node; PK → node identity. Each entity relation becomes a vertex label keyed on its primary key.
2. Non-key, non-FK columns → node properties (scalar type-mapped).
3. FK → directed edge, "many"→"one". A foreign key becomes a relationship from the referencing (child) row to the referenced (parent) row.
4. M:N junction (join) table → EDGE, not a vertex. A relation whose key is a pair of FKs and which carries only relationship attributes is collapsed to an edge; it must not yield a spurious intermediate node label. (The known exception — a junction that is itself referenced by a third entity stays a node — does not occur in this schema.)
5. Composite primary key. A key of n>1 columns identifies the element; for a junction the pair (fk1, fk2) is the edge's composite identity.
6. Self-referential FK → self-loop relationship (hierarchies/trees); a NULL self-FK is the tree root — a null FK is "no edge" (standard SQL semantics), not a dangling edge.
7. No dangling endpoints. Every non-null edge endpoint must resolve to an existing node of the endpoint's label.

Sources:

• P. Stoica et al., On Directly Mapping Relational Databases to Property Graphs (R2PG-DM), CEUR-WS Vol-2369 — https://ceur-ws.org/Vol-2369/short06.pdf (direct mapping; composite key as col1::col2; FK-defined edge types).
• From relational model to property graph: mapping data, schema, constraints and queries, Progress in Artificial Intelligence (2025) — https://link.springer.com/article/10.1007/s13748-025-00373-0 (complete direct mapping of data + schema + constraints).
• Ontopic, Mapping many-to-many relationship tables to object properties — https://ontopic.ai/en/tech-notes/mapping-many-to-many-relationships/ (junction FKs → subject/object of the relationship; the "referenced junction stays a node" exception).
• Microsoft, Map many-to-many relationships + Wikipedia, Many-to-many (data model) — the composite-PK junction-table pattern being collapsed.

2. The test schema (12 tables)

Northwind/ERP-shaped. Parents precede children so the generator can pick FK targets from known id ranges. Defined once in src/schema.rs — the single source of truth the mapping, the generator, and the expectations all read.

Feature coverage: 10 entity labels, 2 junction tables (11, 12, no vertex), 2 composite keys (the junctions), 1 self-referential FK (7). 11 distinct relationship types in total.

3. Scalable generator (src/generate.rs)

• Parametrised by scale (1 / 10 / 100 …) and a seed. Node tables grow linearly (base_rows * scale); junctions grow with their parents (each order fans out to 1..=5 distinct products; each product to 1..=3 distinct suppliers, giving composite-unique pairs).
• Deterministic: a dependency-free SplitMix64 PRNG (src/prng.rs), one stable sub-stream per table. Same (scale, seed) ⇒ byte-identical data. No rand, no wall clock.
• Referential integrity by construction: serial PKs 1..=count; every FK is a uniform pick from the parent's known range ⇒ zero dangling by design (the bencher proves it, and a negative test proves the check is not vacuous).

4. Correctness bencher (tests/correctness.rs)

Property-style assertions, run at scale 1 and scale 10 (+ a scaling test), each judged against an INDEPENDENT oracle computed from the generated relational data (distinct PKs, FK cardinalities):

• node count per label == distinct PKs of that table (== linear-scaled row count);

• edge count per relationship == that FK's non-null cardinality;

• labels are exactly the 10 entities — no OrderItem/ProductSupplier vertex;

• each junction projects its edge(s), non-empty;

• dangling == 0 (every non-null endpoint resolves);

• self-ref: REPORTS_TO == employees with a non-null manager, < employees (roots are not edges), null roots counted as "no edge" not "dangling";

• composite junctions: one resolved edge per generated (fk1, fk2) row;

• shape agreement: GraphPlan::from_mapping ⇒ 10 node plans (none from a junction table) + 11 edge plans; to_thund_pipeline ⇒ 10 node__* + 11 edge__* datasets, no junction node dataset;

• PROJECTION PARITY (down to keys) — twelve_table_projections_agree_down_to_keys: the ONE 12-table GraphPlan fans out to the PySpark job and the thund Pipeline; both are parsed INDEPENDENTLY (the generated Python's selectExpr

  • _write_edges on one side, the knut.edge.* props on the other) and asserted equal as the 7-tuple (from, rel, to, from_col, to_col, from_key, to_key) — edge direction, the two read columns, and the two merge keys. This pins the composite-key junctions (CONTAINS, SUPPLIED_BY) and the self-ref REPORTS_TO to map identically, and guards that no edge reads the same column for both endpoints (a self-loop). It is the scaled-up sibling of thund's 2-table two_projections_agree, extended to endpoint keys.

• not vacuous: a deliberately corrupted FK is detected as dangling.

4.1 Bug the self-ref case surfaced — read column vs merge key (FIXED)

The bench's Employee-[:REPORTS_TO]->Employee (read from manager_id, MERGE on employee_id) exposed a real codegen bug: EdgePlan carried a single to_key = id_column ?? column used for BOTH the selectExpr read AND the MERGE property, so the projections emitted employee_id AS dst — reading each employee's own id and collapsing the edge into a self-loop. Both projections shared the field, so they agreed with each other while both diverged from the data (the GraphMutation path, which reads .column, was always correct — which is why correctness_at_scale_* passed while the codegen shipped wrong). Fixed by splitting from_col/to_col (read columns) from from_key/to_key (merge keys) across codegen, to_thund_pipeline, and the native graph-sink. See .nornir/rel2graph-codegen-design.md §2.1.

5. Timing bencher (src/bin/timing.rs)

A seeded, monotonic-Instant timed loop (median of N iters, warmups) — no bench crate, no wall-clock randomness (only the DATA is seeded; elapsed time is measured). Scales 1x/10x/100x. Representative run (unloaded dev box, release):

 scale |   rel.rows |   nodes |   edges | from_mapping | to_thund | build_mut |  verify | elems/sec*
    1x |       2250 |    1106 |    2955 |        9.5us |   56.6us |    28.8us |   98.1us |  41,381,770
   10x |      22493 |   11060 |   29570 |       10.4us |   60.8us |    30.5us |  973.3us |  41,746,124
  100x |     224826 |  110600 |  295623 |       11.4us |   64.3us |    33.4us |  11.30ms |  35,937,092

(oden, release, 2026-07-30. from_mapping/to_thund are shape-only O(schema); build_mut is O(#steps) zero-copy Arc-clones; verify is the only pass that scales with data volume — the harness's full per-element endpoint resolution.)

Finding — construction is zero-copy. from_mapping and to_thund_pipeline are O(schema) (shape-only, scale-invariant). build_mutation is O(#pipeline steps), NOT O(rows): the fabric projects Arrow columns by Arc-clone into VertexSet/EdgeSet (five-zeros: zero-copy), so ~31–40us regardless of scale — the per-row cost lives at the sink/MERGE. The only stage that scales with data volume is the harness's own full endpoint-resolution verify pass (106us → 1.04ms → 14.94ms as elements go 4k → 41k → 406k), i.e. ~27–39M elements/s.

6. Cross-session git

• ISOLATED CLONE of knut; branch feat/rel2graph-benchers off origin/main (f7525b6, the thund-graph-sink merge whose API this harness uses).
• Additive only: one new workspace member (crates/knut-rel2graph-bench) + its registration in the root Cargo.toml members list. No edit to any rel2graph inference/codegen. Branch pushed only — never merged to main.