Why relational graph queries need N self-joins

Note: Company names, engineers, incidents, numbers, and scaling scenarios in this article are hypothetical — even when they resemble real ones. See the full disclaimer.

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.

Common confusions

• "WITH RECURSIVE makes Postgres as fast as Neo4j on graph queries." It does not. The recursive CTE collapses the syntactic explosion — one CTE body instead of N self-joins — but the executor still iterates depth by depth, materialising a working table on each round and joining it against edges with a B-tree probe per row. There is no streaming, no shared traversal state, no path operator. On the ShopCircle 3-hop benchmark above, the recursive CTE clocks ~30 s; Neo4j clocks ~200 ms on the same hardware. Same logic, two orders of magnitude.

• "Adding more indexes will fix the multi-hop slowness." It will not, past the second one. The PK on (src_id, dst_id, type) and a secondary on dst_id are sufficient; every hop already gets an index probe. The bottleneck is not "we are seq-scanning" — it is "each probe costs ~100 µs of B-tree descent and there are thousands of them." A native engine`s pointer-chase costs ~1 µs because the storage is the index. You cannot index your way out of the storage layout, only sideways.

• "DISTINCT is just a cosmetic de-duplication step." It is not — it is a materialise-and-sort over every candidate path. With fan-out 12 and three hops, that is 1,728 rows; with five hops, ~250,000 rows per seed. The sort-and-unique node sits above every join, so the planner cannot stop expanding when it has enough output — it must finish every path before de-duplicating. This is why a native engines LIMIT 50` on a Cypher pattern can short-circuit at hop two while Postgres has to expand the full lattice.

• "Apache AGE turns Postgres into Neo4j." AGE compiles Cypher into a Postgres plan tree, but the underlying storage is still relational tables — there are no real adjacency lists, no pointer chases. AGE adds graph-aware plan operators on top of B-tree storage, which closes a meaningful chunk of the gap (10–15× over vanilla CTEs in the ShopCircle measurement) but cannot match the storage-level advantage of an engine where the adjacency is the index. AGE is "Cypher syntax for the Postgres optimiser," not "Neo4j inside Postgres."

• "Recursive CTEs handle cycles automatically." They do not. Postgres uses UNION ALL (not UNION) inside recursion, so the same node can re-enter the working set every iteration through every path that reaches it. On a graph with cycles — and every social or commerce graph has cycles — a naive recursive CTE without an explicit visited-set check (e.g., path array plus NOT (e.dst_id = ANY(x.path))) runs until temp space fills and the connection is killed. The depth cap is a band-aid, not a fix.

• "Sharding the edges table across machines fixes the latency at scale." Sharding fixes write throughput, not multi-hop read latency. Each hop now needs a cross-shard lookup — the network round-trip is ~500 µs vs ~100 µs single-machine — so a 3-hop query that took 30 s on one box takes 60+ s across four shards. Native graph engines that scale (TigerGraph, Neo4j Fabric) co-locate adjacent vertices on the same machine using graph-partitioning algorithms (METIS, label-propagation), which Postgres sharding by src_id hash does not even attempt.

Going deeper

If you needed only the headline — N hops in SQL means N self-joins, recursive CTEs reduce syntax not cost, native engines win past 2 hops — you have it. The rest of this section connects the argument to systems an Indian engineer is actually likely to ship.

Why Postgres` planner under-budgets self-joins

The Postgres planner uses most-common-value (MCV) statistics and a column-independence assumption to estimate join cardinality. For a query SELECT … FROM edges e1 JOIN edges e2 ON e1.dst_id = e2.src_id, it computes selectivity(e1.src_id) × selectivity(e2.dst_id) × |edges|² / |edges|, which on a skewed-degree graph dramatically underestimates the result size. A Bollywood-actor node with 5M followers contributes 5M × avg-degree to the join, but the planner sees only the average degree in its statistics.

The practical consequence: the planner under-budgets, picks hash join (cheap when small, catastrophic when large), builds a hash table in work_mem, spills to disk when it overflows, and the query falls off a cliff. The fix engineers reach for is SET enable_hashjoin = off or a pg_hint_plan annotation to force nested-loop. It works, but it is a manual override that needs to be re-tuned every time the graph topology shifts. Native engines avoid the problem entirely because they keep per-vertex degree as a first-class statistic and the planner consults it during traversal expansion.

How WITH RECURSIVE is actually executed

The Postgres executor implements recursive CTEs via a WorkTableScan node and a temporary working table held in temp_buffers. On each iteration:

1. The recursive arm reads the current working table.
2. It runs its body (a self-join with edges) over those rows.
3. The output rows are appended to the intermediate result (visible to the outer SELECT).
4. The output rows also replace the working table for the next iteration.

The working table lives in shared temp buffers (default 8 MB) and spills to a temp file when it overflows. Because the recursive reference is opaque to the planner, it cannot push predicates from the outer query down into the body; the WHERE depth = 3 filter at the end runs after all 22,000+ rows have been generated and stored. Why even a LIMIT 50 outside the CTE does not short-circuit it: Postgres applies LIMIT at the top of the plan tree, after the CTE has fully materialised. There is no operator that can tell the recursive expansion to stop early when the limit is met. (source: Postgres mailing list discussion on CTE optimisation barriers).

The 2017 fence-removal change for non-recursive CTEs (MATERIALIZED / NOT MATERIALIZED keywords in PG12+) does not apply to recursive CTEs — they remain an optimisation fence by design.

Apache AGE: Cypher inside Postgres

Apache AGE ("A Graph Extension") is the most production-ready option for teams who want Cypher without leaving Postgres. AGE represents nodes and edges as rows in special property tables (_ag_label_vertex, _ag_label_edge), and rewrites Cypher queries into a SQL plan that calls AGE-provided graph operators rather than naive joins.

A Cypher query like MATCH (a)-[:KNOWS*1..3]->(b) compiles to a plan tree where the variable-length path becomes a single cypher_path_expand operator that walks adjacency rows in a streaming fashion, with predicate push-down for label and property filters. The result on the ShopCircle 3-hop carousel: ~3 s median latency vs ~30 s for the recursive CTE — a 10× win, attributable mostly to predicate push-down and avoiding the working-table materialisation. Still 15× slower than Neo4j because the storage is still relational pages, not adjacency lists.

The team at the Bengaluru fintech PaisaBridge`s graph fraud-detection group has written publicly about choosing AGE over a separate Neo4j cluster for their 50M-account fraud graph: the operational simplicity of one Postgres footprint outweighed the 5× latency loss for their 1-2 hop dominant workload.

pg_graph and graph-aware physical operators

A more aggressive line of work — pursued in research at Vistron Research`s SQL-on-Graphs programme and various commercial Postgres extensions — adds a real graph traversal physical operator to the Postgres planner. This operator takes a starting set of vertex IDs, an edge predicate, a depth bound, and produces output paths in a streaming fashion, never materialising intermediate results.

In benchmarks reported in the SQL-on-Graphs paper, this operator closes the gap to within 3-4× of native engines on 3-hop queries and within 2× on 2-hop. The cost: it is a non-standard extension, not portable across Postgres versions, and the Postgres core team has resisted upstreaming graph operators on the grounds that "it should be possible to express graph queries in SQL" — which is true, but as this chapter has shown, expressibility is not the same as performant execution.

When to operate two databases

The pragmatic Indian-engineering question is: when does the operational pain of running two databases (Postgres for tabular truth, Neo4j or TigerGraph for traversals, plus a CDC pipeline keeping them in sync) become worth the latency win?

A back-of-the-envelope rule from teams like BharatBazaars recommendations engineering (~1B users-product graph), BhojanBoxs social-discovery layer, and DigiPaisa`s fraud team (~500M-account graph): operate two databases when at least 5% of your read traffic is 3+ hop traversals and that 5% has a tight latency SLA (under 500 ms at p99). Below 5%, the engineering cost of CDC, schema-drift management, and dual-database operational overhead exceeds the savings. Above 5%, the latency improvement on the hot path makes the two-database architecture pay for itself within a quarter.

The CDC pipeline itself is non-trivial: typical implementations use Debezium to read the Postgres WAL, transform rows into graph events (node-create, edge-create, property-update), and apply them to Neo4j via a Kafka topic. Lag of 200-500 ms is normal in production; a few thousand events/sec is comfortable, tens of thousands/sec needs a partitioned consumer group. The team needs to decide explicitly whether the graph is eventually consistent with Postgres (almost always yes — strong consistency across two engines requires distributed transactions, which is not worth the complexity).

Going deeper still: what graph engines themselves cannot do

The flip side of "Postgres is bad at graphs" is "graph engines are bad at tabular work." A native graph engine like Neo4j stores nodes and properties in two separate variable-length files, which makes a query like SELECT count(*) FROM users WHERE city = 'mumbai' AND created_at > '2026-01-01' punishingly slow — there is no columnar scan, no MCV statistics, no hash aggregate. Many production graph teams maintain a small number of materialised property views in a relational engine alongside the graph, keeping each engine on the workload it was designed for.

The next chapter (Neo4j internals and page-cache tuning) goes inside the native engine to show exactly how the adjacency-list storage layout enables the pointer-chase per hop, what the page cache contains, and how to tune it for graph workloads where working sets are scattered rather than localised.

Where this leads next

• Native adjacency storage and index-free adjacency — chapter 161: the storage layout that makes pointer-chasing per hop possible.
• Cypher and Gremlin: declarative graph query languages — chapter 160: the path-expression syntax that compiles to adjacency walks rather than joins.
• Neo4j internals and page-cache tuning — chapter 163: how the buffer pool serves graph traversals when working sets are scattered.
• Query rewrite and the volcano iterator model — the underlying execution model that makes the join-by-join SQL plan tree both elegant and fundamentally non-graph-shaped.
• Hash join: build and probe phases — why the planner sometimes picks hash for self-joins and where it goes wrong.

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, Vistron 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.