Graph Traversal vs Joins Lab (Interactive)
Breadth-first search a real seeded friendship graph and race it against N SQL self-joins. Run an actual BFS up to six hops over a growing graph while the SQL equivalent re-estimates its adjacency-table joins hop by hop — compare latency and work actually touched.
Index-Free Adjacency vs Recursive SQL Joins
A real BFS runs on a sampled social graph of degree-averaged users; the JOIN engine pays per hop against the whole table.
Double the network to a billion nodes and the SQL plan gets slower at every hop; the graph engine never notices — that is the traversal guarantee of index-free adjacency, and why fraud rings (A→B→C→A cycles) and “People you may know” live in Neo4j, not in JOINs.
How It Works Under the Hood
A relational adjacency list stores every relationship in one edge table; a k-hop query pays k self-joins, and the join machinery probes indexes over hundreds of millions of rows unrelated to the neighborhood you visit. A property graph stores adjacency as direct pointers — index-free adjacency — so each hop touches only the frontier's real edges and cost scales with degree^hops over the local subgraph, independent of total graph size. This lab runs genuine BFS on a seeded graph against the SQL cost curve to show where they diverge.
Core Architectural Principles
- Index-free adjacency: every relationship is a direct pointer, so a hop costs O(frontier degree) regardless of database size.
- SQL k-hop reachability needs k self-joins over the adjacency table, with intermediate row counts exploding multiplicatively.
- Traversal work scales with degree^hops — breadth (friend count) hurts more than depth (hop count).
For fraud rings, recommendations, or social feeds, name the query shape — multi-hop traversal — and pick a graph engine with index-free adjacency as the reason, quantifying work proportional to the visited subgraph. Contrast it with N self-joins over a billion-row adjacency table, and note that bounding hop depth keeps degree^hops tractable.
Graph engines win multi-hop traversal by storing relationships physically, but give up relational generality, analytics breadth, and mature operational tooling.