Why relational graph queries need N self-joins

The previous chapter made the case for index-free adjacency at the storage layer: pointer-chasing instead of index-probing, ~1 µs per hop instead of ~100 µs. This chapter is about the query layer — what happens when you try to express a multi-hop traversal in SQL, why the syntax explodes, why the optimiser cannot rescue you, and what the SQL standard`s answer (recursive CTEs) does and does not solve.

The thesis is simple. SQL has exactly one primitive for "combine information from two rows": the JOIN. Joining the edges table to itself once gives two-hop reachability. Twice gives three-hop. N-hop reachability needs N self-joins. Around N=3 the query becomes a chore to write; around N=4 the optimiser starts producing defensible-looking plans that execute poorly; around N=5 you have given up and gone looking for a different database.

The schema and the one-hop query

The starting schema is the standard property-graph-on-Postgres layout:

CREATE TABLE nodes (id BIGINT PRIMARY KEY, label TEXT NOT NULL, properties JSONB);
CREATE TABLE edges (
  src_id BIGINT NOT NULL REFERENCES nodes(id),
  dst_id BIGINT NOT NULL REFERENCES nodes(id),
  type   TEXT   NOT NULL,
  properties JSONB,
  PRIMARY KEY (src_id, dst_id, type)
);
CREATE INDEX edges_dst_idx ON edges (dst_id);   -- for reverse traversal

A one-hop query — "who does Riya know?" — is a single index lookup:

SELECT e.dst_id FROM edges e WHERE e.src_id = 'riya' AND e.type = 'KNOWS';

Postgres descends the primary-key B-tree on (src_id, dst_id, type), finds the leaf page for ('riya', *, *), scans matching tuples, returns the destinations. Cost: ~100 µs warm. Why this is the floor: the only way to find Riyas edges is to look them up by source ID. The index makes that O(log N), but the lookup itself is unavoidable because edges live on different pages from nodes — there is no shortcut from Riyas row to her edges.

Two hops: the first self-join

Two hops — "who do Riya`s friends know?", the people-you-may-know primitive — is a self-join:

SELECT DISTINCT e2.dst_id
FROM   edges e1 JOIN edges e2 ON e1.dst_id = e2.src_id
WHERE  e1.src_id = 'riya' AND e1.type = 'KNOWS' AND e2.type = 'KNOWS';

The JOIN clause e1.dst_id = e2.src_id is the trick: every row of e1 is an outgoing edge from Riya; every row of e2 whose source matches e1.dst_id is an outgoing edge from one of Riyas friends. DISTINCTremoves duplicates when two friends know the same person. <span class="why">Why DISTINCT is mandatory: in a graph, a node reachable in two hops via three different paths shows up three times in the join output. Without de-duplication the result set bloats bydegree²`, and downstream consumers reason about path-multiplicities they never asked for.

Postgres treats this as a join of two relations, not graph traversal. A typical plan: scan the PK index on edges for e1.src_id = 'riya' (~12 rows for Riyas friends), then for each of those 12 rows probe the same PK index for e2.src_id = e1.dst_id(nested-loop with index on inner), filter bytype, sort and de-duplicate. Cost: 12 × 100 µs` plus a sort over ~144 rows ≈ 2 ms. Manageable. Why nested-loop with index-on-inner is the right call here: the outer relation (12 rows) is tiny and the inner has a usable index on the join key; hash-join would build a useless hash table over the entire edges table.

Three hops: the second self-join, and the syntax starts to bite

Three hops — "who do Riyas friends friends know?" — needs a third self-join:

SELECT DISTINCT e3.dst_id
FROM   edges e1
JOIN   edges e2 ON e1.dst_id = e2.src_id
JOIN   edges e3 ON e2.dst_id = e3.src_id
WHERE  e1.src_id = 'riya'
  AND  e1.type = 'KNOWS' AND e2.type = 'KNOWS' AND e3.type = 'KNOWS'
  AND  e3.dst_id <> 'riya';

Three aliases, joined head-to-tail, each with its own type filter. A four-hop query adds e4; a five-hop adds e5; you end up with a railway-timetable query. Why the type filter repeats on every alias: SQL has no "all edges in this path are of type KNOWS" operator — each predicate binds to one table reference. A heterogeneous path (KNOWS then BOUGHT then VIEWED) needs different filters on different aliases, and Cyphers compact [*1..3]` quantifier has no SQL equivalent.

The cost: each join is a sort+scan or hash+probe

Each JOIN in the SQL becomes one physical join operator. Postgres picks per-join from three algorithms based on cardinality estimates. Nested loop with index probe (the 2-hop plan above): outer relation small, index on inner — cost outer_rows × inner_lookup_cost, ~1.2 ms for Riyas 12 friends. Beautiful when the outer is selective and an index exists. **Hash join**: build a hash table over one input, probe with the other — cost build_rows × hash_cost + probe_rows × probe_cost. Catastrophic when applied to a self-join on the entire edges table because billions of rows hash in memory or spill to disk. <span class="why">Why the planner sometimes picks hash and gets it wrong: cardinality estimation on self-joins is notoriously poor. Postgres assumes column independence and uses MCV statistics collected for single-column predicates. The estimate "rows where e1.dst_id = e2.src_id`" multiplies per-column selectivities, which underestimates join cardinality on skewed-degree graphs. The planner under-budgets, picks hash, spills, and latency collapses. Sort-merge join: sort both inputs on the join key, merge in one pass. Rarely the right plan on graphs — there is almost always a usable index, so nested-loop wins.

The deeper problem is not which join is picked but that the optimiser reasons about each join independently. A native graph engine knows that the joins form a path: it walks node by node, never materialising intermediate results, and short-circuits as soon as enough output rows exist. SQL has no path operator. Each join produces a complete intermediate relation that flows up the plan tree, even when the next join only needs a streaming subset.

WITH RECURSIVE: SQL`s answer to unbounded depth

The N-self-join pattern is fine when N is fixed and small. It fails the moment the query is "find all reachable nodes" (N is unbounded) or "find the shortest path" (N is variable). The SQL standard added recursive common table expressions in SQL:1999 precisely for this:

WITH RECURSIVE friends(person, depth) AS (
    -- anchor: start at Riya, depth 0
    SELECT 'riya'::TEXT, 0
    UNION ALL
    -- recursive step: follow one more KNOWS edge from the working set
    SELECT e.dst_id, f.depth + 1
    FROM   friends f
    JOIN   edges   e ON f.person = e.src_id
    WHERE  e.type = 'KNOWS'
      AND  f.depth < 4
)
SELECT DISTINCT person FROM friends WHERE depth > 0;

The semantics are textbook fixed-point iteration. The anchor query produces an initial working set (just Riya at depth 0). The recursive query is applied to the working set repeatedly: each iteration takes the rows added in the previous step, joins them with edges, and produces the next layer. Iteration stops when the recursive step produces no new rows — or, more commonly, when an explicit termination predicate (depth < 4) cuts it off. Why the depth cap is essential in practice: in a graph with cycles (and every social graph has cycles), the naive recursive CTE never terminates. Postgres uses UNION ALL (not UNION) inside the recursion, which means duplicates are kept; the same node can re-enter the working set multiple times, each time spawning more recursive expansions. Without a depth cap or an explicit WHERE NOT EXISTS (SELECT 1 FROM friends ff WHERE ff.person = e.dst_id) deduplication clause, the query runs until the working table fills temp space and the server kills it.

The WITH RECURSIVE form is a real improvement: the syntax stays compact regardless of N, path length becomes a runtime parameter (depth < N) instead of a query rewrite, cycles can be handled cleanly, and the planner has one recursive operator to optimise rather than N+1 join nodes.

But the cost story has not fundamentally changed. The executor materialises a working table on each iteration, joins it with edges, appends to the intermediate output, swaps in the new rows as the next working set, and repeats. Each iteration is essentially one self-join, executed serially. The optimiser cannot push predicates into the recursion and cannot reorder iterations. WITH RECURSIVE matches the cost of N stacked self-joins to within a constant factor — better than writing them out, but not by much. Why the optimiser cannot push predicates into the recursion: the planner needs a stable cost estimate for the recursive body, but the body`s input depends on its previous output — a function of itself. Postgres treats the recursive reference as an opaque "scan working table" operator with conservative cardinality estimates. Pushing a predicate down would require fixed-point analysis the planner does not attempt.

Why native engines win on multi-hop

The native graph answer to the same query — MATCH (riya)-[:KNOWS*1..4]->(other) in Cypher — runs end-to-end in milliseconds, for three reinforcing reasons. Pointer chase per hop: each hop is one pointer dereference, not a B-tree probe — ~1 µs vs ~100 µs, compounded (previous chapter). Optimiser knows graph topology: [Neo4js planner](https://neo4j.com/docs/cypher-manual/current/planning-and-tuning/) maintains per-label degree statistics (average and max) and decides whether to expand from Riya outward, from other backward, or bidirectionally — choices SQLs join planner has no analogue for. Why supernode awareness matters: a query that traverses through a Bollywood-actor node with five million followers behaves catastrophically if the planner does not know to handle it specially. Native engines prune or warn at parse time; Postgres just produces a plan that estimates 12 friends, sees 5,000,000, and OOMs. Indexes are integral: in Neo4j the adjacency is the index — no separate structure to maintain, no plan-time choice about whether to use it. The storage layout is the index.

When SQL is good enough — and when it isn`t

Postgres remains the right tool for one- and two-hop queries ("show this user`s direct friends", "friends-of-friends with mutual count"): single self-join, single-millisecond latency on 100M-edge graphs, no operational overhead. It is also the right tool for aggregations over node attributes ("users in Mumbai joined last month") — a row-store seq-scan with hash aggregate, the bread-and-butter of relational engines, which native graph engines do poorly because nodes and properties live in two separate variable-length files. And it is the right tool for hybrid analytical-transactional workloads where 90 % of the queries are CRUD-plus-aggregations and only 10 % are traversal — the operational tax of running a second database is rarely worth recovering 20× on a sliver of the workload.

The decision flips when the requirements include three-or-more-hop traversal at interactive latency (live fraud detection, real-time recommendations), graph algorithms (Dijkstra, Louvain community detection, PageRank — expressible in recursive CTEs but an order of magnitude slower than native implementations in Neo4j Graph Data Science or [TigerGraphs GSQL library](https://docs.tigergraph.com/graph-ml/current/intro/)), or **declarative pattern matching with type and property constraints** (Cyphers (person)-[:WROTE]->(book)<-[:REVIEWED]-(critic {country: 'IN'}) becomes a sprawling unreadable WHERE-clause in SQL).

The Postgres ecosystem`s answer

The choice is not binary. Apache AGE (A Graph Extension) embeds Cypher inside Postgres: nodes and edges still live in Postgres tables, but the engine compiles Cypher into a plan with graph-aware operators on top of relational storage — closer to Neo4j on multi-hop, with one operational footprint. pg_graph-style extensions (covering several research and commercial designs) add a graph-traversal physical operator to the Postgres planner that streams paths without materialising intermediates the way recursive CTEs do. ArangoDB ships a hybrid document-graph engine where AQL supports both FOR doc IN collection and FOR v, e, p IN 1..3 OUTBOUND startNode GRAPH 'social', with the optimiser picking per-query execution. The interesting decision in 2026 is which point on the relational-to-native spectrum your workload sits on.

WITH RECURSIVE expand AS (
    SELECT %s::BIGINT AS node_id, 0 AS depth, ARRAY[%s::BIGINT] AS path
    UNION ALL
    SELECT e.dst_id, x.depth + 1, x.path || e.dst_id
    FROM   expand x JOIN edges e ON e.src_id = x.node_id
    WHERE  x.depth < 3
      AND  ((x.depth < 2 AND e.type = 'KNOWS')
       OR   (x.depth = 2 AND e.type = 'BOUGHT'))
      AND  NOT (e.dst_id = ANY(x.path))
)
SELECT DISTINCT node_id AS product_id FROM expand
WHERE  depth = 3 AND node_id NOT IN (SELECT product_id FROM purchases WHERE user_id = %s)
LIMIT 50;

MATCH (me:User {id: $userId})-[:KNOWS*1..2]->(friend:User)-[:BOUGHT]->(product:Product)
WHERE NOT (me)-[:BOUGHT]->(product)
RETURN DISTINCT product LIMIT 50

The takeaway

Relational databases express graph queries fine on shallow traversal (one or two hops). The architecture stops scaling at three-plus hops because SQLs only join-across-rows primitive is the JOIN, and an N-hop traversal needs N self-joins. The syntax balloons; the optimiser cannot reason about path shape; each join is a sort-or-hash that materialises an intermediate result with multiplicative row counts; and WITH RECURSIVE`, while collapsing the syntax, does not collapse the cost.

Native engines win on multi-hop because their storage layout is the index — pointer-chase replaces B-tree probe per hop, the planner understands graph topology, and the query language has first-class path operators. The 30-second-vs-200-millisecond gap on the ShopCircle workload is the sharp edge of that argument: same data, same logical query, two orders of magnitude latency difference. The right answer in production is rarely "all of one or all of the other": Postgres remains the system of record for tabular truth and shallow queries; a native graph engine alongside it serves the path-heavy ones; CDC keeps them in sync. The middle ground — Apache AGE, pg_graph extensions, ArangoDB — narrows the gap when operating two databases is unaffordable. The next chapter (Neo4j internals and page-cache tuning) goes inside the native engine to see how the storage and buffer pool deliver that 100× per-hop speedup in practice.

References

1. PostgreSQL Documentation, Recursive Queries — postgresql.org/docs/current/queries-with.html. The canonical reference on WITH RECURSIVE semantics and execution.
2. Sun et al., SQL/PG: SQL Server Graph Extensions and the SQL on Graphs Programme, Microsoft Research — microsoft.com/en-us/research/publication/sql-on-graphs/. The research programme that introduced graph operators into a row-store optimiser.
3. Robinson, Webber, Eifrem, Graph Databases (2nd ed., OReilly, 2015), Chapter 4 — [graphdatabases.com](https://graphdatabases.com/). The canonical exposition of why relational queries struggle with multi-hop, by Neo4js founders.
4. Neo4j blog, Graph databases vs. relational databases: a benchmark — neo4j.com/blog/relational-database-vs-graph-database/. End-to-end timing comparisons across hop counts.
5. Apache AGE Project, Quick Start and Cypher Reference — age.apache.org/age-manual/master/intro/overview.html. How Cypher embeds inside Postgres without leaving the relational engine.
6. ArangoDB Documentation, Graphs in AQL — arangodb.com/docs/stable/aql/graphs.html. Hybrid document-graph query execution.