Topic 13 notes — graph engines

Baseline (provided lane, Apple M3 Pro, measured 2026-07-28)

cargo run --release --bin hop_bench — preferential-attachment graph, 1 M nodes / 16.0 M directed edges, two-hop COUNT(DISTINCT) from 10 000 random sources and from the 100 highest-degree nodes. Max degree 6565, p50 degree 11.

Same query, same graph, same code path: 101× slower depending on where you start. That ratio is the single most important fact about graph workloads and it has no analogue in the topics before this one. A B-tree point lookup costs what it costs; a two-hop traversal costs whatever the degree distribution under your start node says it costs, and on a scale-free graph that is a power law with no useful average. The p50 node has 11 neighbours; the top node has 6565.

Note the checksum column is a sum over the source set, and the two sets are different sizes — 10 000 random sources against 100 supernodes. Normalise before comparing anything: random reaches 1022 distinct nodes per query, a supernode reaches 78 907 — 77× more. (An earlier version of this file read the raw sums as “the slow case reaches fewer nodes”; it does not, and that mistake is worth keeping in mind every time a benchmark prints a total.)

So the 101× decomposes: 77× more nodes reached, and 1.31× worse cost per node reached (4.81 ns against 6.28 ns). The second factor is the one worth chasing, and this lane cannot attribute it — it counts distinct nodes, not edges traversed, so re-walked overlap and the cache cost of a 79 000-node frontier look identical from here. Exercise 6 in the README adds the edge counter that separates them.

Checksums must match across all three implementations per source set — that is the correctness gate before any timing comparison means anything.

Predictions (fill BEFORE implementing csr.rs / matrix.rs)

Baseline (provided, measured): adj_list 4914 ns/query random, 495378 ns/query supernodes (101× tail); graph 1M nodes / 16M directed edges, max degree 6565, p50 degree 11.

Implementation log

• csr.rs: counting-sort build + slice two_hop; all 5 tests green
• matrix.rs: spmv_masked + two-SpMV two_hop; all 4 tests green
• hop_bench full table recorded above (checksums match: random=10220457, supernodes=7890665)
• external: same 2-hop count on FalkorDB (MATCH (a)-[*1..2]->(b) WHERE id(a)=<src> RETURN count(DISTINCT b)) — ns/query here:
• optional: neo4j same query — ns/query:

Surprises / dead ends:

Questions from the reading guides

GraphBLAS + Delta_Matrix (reading-graphblas-internals.md)

1. Why delta_minus instead of deleting from M (CSR delete cost):
2. dot3 vs saxpy at frontier 10 vs 10⁶:
3. When BITMAP fits a label matrix:
4. Why (M ∪ DP) ∖ DM reads beat flush-per-write:
5. Delta_Matrix → LSM vocabulary map:

neo4j record store (reading-neo4j-record-store.md)

1. 1000-edge Expand: chain (~110 ns/edge) vs CSR stream — ×:
2. Why 15 B nodes / 34 B rels — field inventory:
3. Delete cost: chain vs CSR vs Delta_Matrix:
4. Property chains vs M12 columns for WHERE n.age > 65:
5. Index-free adjacency: what survives DRAM, what died:

memgraph storage (reading-memgraph-storage.md)

1. Why edges in both endpoints’ vectors; FalkorDB’s transposed trio:
2. small_vector inline + power-law degrees:
3. Per-object vs per-row delta chains under supernode edge inserts:
4. memgraph vector vs kuzu CSR slice — 16 B triples vs 8 B ids:
5. PageRank on pointer soup vs matrix — where the bus time goes:

kuzu (reading-kuzu.md)

1. Node-group-bounded rebuilds — which insert pattern still hurts:
2. Why Intersect needs sorted adjacency:
3. Triangle intermediates: binary join vs AGM at m=16M:
4. Factorized count(*) 2-hop as a matrix expression:
5. Best topic-12 encoding for CSR target columns:

WCOJ (reading-wcoj.md)

1. Star-graph R⋈S intermediates vs triangle output:
2. AGM bound for the 4-cycle:
3. Galloping and power-law skew:
4. Why C<A>=A² never materializes A² (dot3):
5. M10 trigger for intersect vs binary join (pattern cyclicity):

LDBC SNB (reading-ldbc-snb.md)

1. Why timed dependency-tracked inserts:
2. IC5-ish pattern: anchor + expand count + worst representation:
3. Which architecture flatters itself on uniform-degree graphs:
4. Where multi-hop cardinality estimation dies:
5. SF that fits this Mac per representation (bytes/edge each):

Cross-topic threads

• Pointer chase vs stream = topic 0’s cache ladder deciding graph architecture: neo4j chains pay ~110 ns/edge, CSR pays bandwidth.
• Delta overlay everywhere (Delta_Matrix, kuzu transient groups, GraphBLAS pending tuples) = topic 4’s LSM applied to adjacency.
• Masks = predicate pushdown (topic 10) into the kernel; SpMV frontier = topic 11’s batch, spelled algebraically.
• memgraph = topic 8’s N2O deltas + topic 9’s skip list, at vertex granularity; bit-smuggling ledger: deleted-flag in delta pointer low bits (PointerPack), neo4j’s 35-bit pointers in the inUse byte.
• Supernodes = the graph-shaped tail: same lesson as Zipfian keys (topic 2) and JOB correlations (topic 10) — uniform data lies.

M13 log (naive adjacency core — the baseline M20 must beat)

• node/edge store over adjacency lists + label bitmaps
• scan-anchor-then-expand for (a:L)-[:R]->(b)
• Expand fills M11 batches; bench engine-vs-raw (interpretation overhead = the M11 payoff measurement)
• update-pain notes for the M20 delta overlay design

Done when

• csr + matrix tests green; hop_bench table filled with matching checksums; FalkorDB external comparison recorded.
• Reading-guide questions answered.
• M13 update-pain notes written.