Graph vs Relational: When a Graph Database Beats SQL Recursive Joins

graph vs relational is the architecture decision that quietly determines whether a relationship-heavy feature ships in three days or becomes a six-month performance war — and it is the single modeling choice senior engineers get wrong most often because "everything is a table" is a comfortable default that works right up until the query needs to walk five hops through a densely connected graph. Every relationship in your domain — a manager who manages managers, a part that contains sub-assemblies that contain parts, an account that transfers money to accounts that transfer it back, a user who follows users who follow users — has to be traversed, and the cost of that traversal is not a property of your data alone but of the engine you chose to store it in. The engineering trade-off does not live in "should we model relationships" — every non-trivial domain has them — but in how deep and how variable the traversals are, and what each hop costs the storage engine you picked.

This guide is the walkthrough you wished existed the first time an interviewer asked "when would you reach for a graph database instead of Postgres?", or "why does this recursive cte fall off a cliff at six levels deep?", or "explain index-free adjacency and why it changes the complexity of a friends-of-friends query." It works through why the "just add another JOIN" reflex eventually breaks, the relational toolkit for relationships (adjacency lists, junction tables, self-joins, and recursive joins via WITH RECURSIVE) and exactly where it hits a wall, the native graph model (nodes, relationships, and constant-cost traversal), a head-to-head of the same friends-of-friends, bill-of-materials, and fraud-ring query written in both SQL and Cypher, and a decision framework for when relational wins, when a graph database wins, and when the honest answer is a hybrid. Each section pairs a teaching block with a worked interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the graph practice library →, rehearse on the joins practice library →, and pressure-test query plans with the optimization practice library →.

---

On this page

• Why "just add another JOIN" eventually breaks
• The relational way — recursive CTEs, self-joins, junction tables
• The graph way — traversals and constant-cost hops
• Head-to-head — the same query in SQL vs Cypher
• Decision framework — when relational wins, when graph wins
• Cheat sheet — graph vs relational recipes
• Frequently asked questions
• Practice on PipeCode

---

1. Why "just add another JOIN" eventually breaks

The deep-traversal problem — every hop is another join, and every join is another index lookup

The one-sentence invariant: the relational model stores relationships implicitly as matching key values across tables, so every step through a relationship costs a fresh index lookup at query time, and a query that walks N steps through the data pays N index lookups per starting row — which is fine when N is one or two and fixed, and pathological when N is large, variable, or unbounded. A graph vs relational decision is really a decision about the shape of your traversals: shallow and fixed-depth workloads stay comfortably relational, while deep, variable-depth, or pathfinding workloads eventually punish the join-per-hop cost model badly enough that a native graph engine's constant-cost traversal wins by orders of magnitude.

Why one more join is never free.

• Relationships are recomputed, not stored. In a relational database, orders.customer_id = customers.id is a value match the planner discovers at query time. There is no stored pointer from an order to its customer; the engine probes an index on customers.id for every order row it processes. Each hop is an index probe — typically O(log N) into a B-tree of N rows.
• Depth multiplies the cost. A one-hop query (order → customer) is one probe. A three-hop query (order → customer → region → sales_rep) is three probes chained. When each hop fans out (one customer has many orders), the intermediate result set grows and the probe count grows with it.
• Fixed vs variable depth is the fault line. A query whose depth is known at write time (always exactly 2 hops) can be written as a fixed chain of joins and optimized well. A query whose depth is unknown — "find everyone reachable from me" — must be expressed as a recursive cte, and the optimizer loses most of its leverage because it cannot see how many iterations the recursion will run.

The four axes that decide graph vs relational.

• Traversal depth. How many relationship steps does the hot query walk? One or two: relational is fine. Five, ten, or unbounded: the join-per-hop cost compounds and a graph engine's O(1)-per-hop traversal pulls ahead.
• Relationship density. How many edges per node? Sparse graphs (a few relationships each) keep intermediate results small. Dense graphs (thousands of edges per node — social follows, "customers who bought this") make each recursive step explode combinatorially. This is the join explosion interviewers probe for.
• Query shape — fixed vs variable. Is the depth a compile-time constant or a runtime property of the data? Variable-length and shortest-path queries are where relational SQL is least expressive and graph query languages are most natural.
• Read/write balance. Native graph engines optimize traversal reads by paying a small write-time cost to maintain adjacency pointers. If your workload is write-heavy and traversal-light, that trade may not pay off; if it is traversal-heavy, it pays off enormously.

What interviewers listen for.

• Do you say "each join hop is an index lookup" rather than "joins are slow"? — the precise version is the senior signal.
• Do you name index-free adjacency as the reason a graph hop is O(1) while a SQL hop is O(log N)? — required answer.
• Do you distinguish fixed-depth (a chain of joins) from variable-depth (a recursive CTE or a graph traversal)? — senior signal.
• Do you refuse to say "graph databases are just better" and instead frame it as "it depends on traversal depth, density, and query shape"? — required answer.

Worked example — counting the index lookups per hop

Detailed explanation. The clearest way to internalize why depth breaks relational traversal is to count the index probes a query issues as depth grows. Take a social graph where each person KNOWS on average d other people (the average degree), and count how the work grows as you walk from one to six hops.

• The model. people(id) plus a friendships(a_id, b_id) junction table, indexed on (a_id).
• The query family. "Everyone within k hops of person 1."
• The cost per hop. Each frontier row triggers an index range scan on friendships(a_id) returning ~d neighbours.

Question. For average degree d = 30, estimate the frontier size and total index probes at each depth from 1 to 6, ignoring overlap.

Input.

Symbol	Meaning	Value
d	average out-degree (friends per person)	30
k	traversal depth (hops)	1..6
frontier(k)	rows at depth k	d^k
probes(k)	index probes to expand depth k	frontier(k-1)

Code.

# Estimate frontier size and cumulative index probes by depth.
# Each frontier row costs one index range scan on friendships(a_id).
d = 30
frontier = 1          # start: just person 1
total_probes = 0
print(f"{'depth':>5} {'frontier':>12} {'cumulative_probes':>18}")
for k in range(1, 7):
    probes_this_hop = frontier      # expand every current-frontier row
    total_probes += probes_this_hop
    frontier = frontier * d         # each row fans out to ~d neighbours
    print(f"{k:>5} {frontier:>12,} {total_probes:>18,}")

Step-by-step explanation.

1. Depth 1 expands the single starting row, issuing 1 index probe and producing ~30 neighbours. Cheap — this is the case relational databases handle beautifully.
2. Depth 2 expands those 30 rows, issuing 30 probes and producing ~900 rows. Still fine; a friends-of-friends query at depth 2 runs happily in Postgres.
3. Depth 3 expands 900 rows (900 probes → ~27,000 rows). Depth 4 expands 27,000 (→ ~810,000). The frontier is now growing by a factor of d every hop — this is exponential in depth.
4. By depth 6 the (overlap-free) frontier is 30^6 ≈ 729 million and cumulative probes are in the tens of millions. Real graphs overlap heavily so the distinct set saturates, but the work the engine does still follows this expansion until dedup kicks in — and the recursive CTE must materialize and dedup every intermediate row.
5. The takeaway is not "joins are bad" — it is that the cost is O(d^k) index probes for a depth-k traversal on a degree-d graph. Relational excels while k is 1–2; the wall is a function of depth and density, exactly the axes the interview probes.

Output.

Depth k	Frontier (d^k)	Cumulative index probes
1	30	1
2	900	31
3	27,000	931
4	810,000	27,931
5	24,300,000	837,931
6	729,000,000	25,137,931

Rule of thumb. Estimate d^k before you choose a store. If your hot query's depth k times the log of d keeps the probe count in the thousands, relational is fine. If d^k runs into the millions, you are shopping for a graph engine or a precomputed projection.

Worked example — fixed depth vs unbounded depth

Detailed explanation. The other axis that breaks relational is not fan-out but whether you know the depth in advance. A fixed-depth query compiles to a fixed chain of joins the optimizer can plan; an unbounded-depth query forces a recursive CTE whose iteration count the optimizer cannot predict. Contrast the two on an org chart.

• Fixed depth. "My manager's manager" — always exactly two hops. Two self-joins; the planner sees the whole shape.
• Unbounded depth. "Everyone in my reporting chain up to the CEO" — depth depends on where you sit in the tree. Must be recursive.
• Why it matters. The optimizer can reorder and cost a fixed join chain; it treats a recursive term as an opaque loop and cannot push most predicates through it.

Question. Write the fixed-depth (two-hop) query and the unbounded-depth query against the same employees(id, manager_id) table and name what the planner can and cannot optimize in each.

Input.

Query	Depth	Expressible as
manager's manager	exactly 2	two self-joins
full reporting chain	1..N (unbounded)	recursive CTE

Code.

-- Fixed depth (exactly 2 hops): a plain chain of self-joins.
-- The planner sees three table references and can cost/reorder them.
SELECT e.name        AS employee,
       m1.name       AS manager,
       m2.name       AS skip_manager
FROM   employees e
JOIN   employees m1 ON e.manager_id  = m1.id
JOIN   employees m2 ON m1.manager_id = m2.id
WHERE  e.id = 42;

-- Unbounded depth: recursion. The planner cannot know the iteration count.
WITH RECURSIVE chain AS (
    SELECT id, manager_id, name, 1 AS level
    FROM   employees
    WHERE  id = 42                        -- anchor: the starting employee
    UNION ALL
    SELECT e.id, e.manager_id, e.name, c.level + 1
    FROM   employees e
    JOIN   chain c ON c.manager_id = e.id -- climb one level per iteration
)
SELECT level, name FROM chain ORDER BY level;

Step-by-step explanation.

1. In the fixed-depth query the optimizer sees exactly three references to employees and one filtering predicate (e.id = 42). It can start from that highly selective row, probe the PK index twice, and finish in three index lookups total. This is relational at its best.
2. The unbounded query uses WITH RECURSIVE: an anchor term selects the starting row, and a recursive term joins the working table (chain) back to employees to climb one level per iteration until no new rows are produced.
3. The planner treats the recursive term as a black-box loop. It cannot know whether the chain is 2 levels deep or 20, so it cannot cost the query the way it costs the fixed chain. Each iteration is a fresh index probe on employees.id for every row in the current working set.
4. For a shallow tree this is still fast — a five-level org chain is five iterations. The danger is a deep or wide recursion (a bill-of-materials, a permission-inheritance graph) where the working set grows each iteration.
5. The lesson: relational handles fixed, shallow traversal with elegance and unbounded traversal with a recursive CTE that works but loses optimizer leverage. Graph engines express both the same way — a traversal — and keep each hop constant-cost.

Output.

Aspect	Fixed 2-hop joins	Recursive CTE
Depth known at plan time	yes	no
Optimizer can reorder/cost	yes	recursion is opaque
Index probes	3 (bounded)	one per row per iteration
Cost predictability	high	depends on tree shape
Right tool when	shallow, fixed	shallow tree OK; deep/dense = graph territory

Rule of thumb. If the depth is a compile-time constant and small, write joins and move on. The moment the depth becomes a runtime property of the data — "up to the root", "all reachable", "shortest path" — you are in recursive-CTE-or-graph territory, and density decides which.

Worked example — the join-explosion trap on many-to-many

Detailed explanation. The third way "just add another JOIN" breaks is many-to-many fan-out. When you join two large tables through a junction table, the intermediate row count can multiply far past either input, and each additional many-to-many hop multiplies again. Walk through a two-hop friends-of-friends against a junction table to see the blow-up.

• The schema. friendships(a_id, b_id) — one row per directed friendship.
• The two-hop join. Join friendships to itself: my friends, then their friends.
• The blow-up. If I have d friends and each has d friends, the raw (pre-dedup) intermediate set is d^2 rows — before you even filter or deduplicate.

Question. Write the two-hop friends-of-friends as a self-join and quantify the intermediate row count for d = 300 (a well-connected user).

Input.

Component	Value
junction table	friendships(a_id, b_id)
starting user	a_id = 1
average degree d	300
raw 2-hop rows	d^2 = 90,000 (before DISTINCT)

Code.

-- Friends-of-friends by self-joining the junction table.
-- f1 = my friendships; f2 = my friends' friendships.
SELECT DISTINCT f2.b_id AS friend_of_friend
FROM   friendships f1
JOIN   friendships f2 ON f2.a_id = f1.b_id   -- hop 2: expand each friend
WHERE  f1.a_id = 1                           -- hop 1: my direct friends
  AND  f2.b_id <> 1                          -- exclude myself
  AND  f2.b_id NOT IN (                      -- exclude people I already know
        SELECT b_id FROM friendships WHERE a_id = 1
       );

Row-count intuition (d = 300):
  hop 1  (f1 WHERE a_id = 1)         -> ~300 rows      (my friends)
  hop 2  (join f2 on f2.a_id=f1.b_id)-> ~300 * 300     = ~90,000 rows
  after DISTINCT + NOT IN filter     -> maybe ~40,000 distinct people
The engine materializes and dedups ~90,000 rows to return ~40,000.

Step-by-step explanation.

1. f1 WHERE a_id = 1 selects my ~300 direct friendships via an index range scan — cheap.
2. The self-join f2.a_id = f1.b_id expands each of those 300 friends into their ~300 friendships. The optimizer probes friendships(a_id) 300 times, producing ~90,000 raw rows. This is the join explosion: the intermediate set is d^2, quadratic in degree.
3. DISTINCT forces the engine to sort or hash all ~90,000 rows to collapse duplicates (two of my friends both know the same person). The dedup cost scales with the raw count, not the distinct count.
4. The NOT IN subquery removes people I already know — another scan. Every filter you add runs against the already-exploded set.
5. At depth 2 this is tolerable. But note the pattern: each additional hop multiplies by d again. A depth-3 friends-of-friends-of-friends is d^3 ≈ 27 million raw rows for a well-connected user. That is the wall — and it arrives sooner the denser the graph.

Output.

Stage	Rows processed (d=300)	Operation
hop 1 (direct friends)	~300	index range scan
hop 2 (self-join)	~90,000	300 index probes, fan-out
DISTINCT	~90,000 → ~40,000	sort/hash dedup
NOT IN filter	~40,000	anti-join scan
depth-3 (hypothetical)	~27,000,000 raw	intractable inline

Rule of thumb. Multiply the degrees along the path before you write the query. If the product stays in the thousands, a junction-table self-join is fine. If it runs to millions, either precompute the result, cap the depth, or move the traversal to a graph engine where the frontier is walked as pointers, not materialized as a join product.

System-design interview question on choosing graph vs relational

A senior interviewer often opens with: "We have a social product on Postgres. 'People you may know' — friends-of-friends ranked by mutual-connection count — is timing out for our most-connected users. Walk me through why the SQL is slow, what the graph vs relational trade-off actually is here, and how you'd decide whether to move this to a graph database or fix it in Postgres."

Solution Using a depth-and-density analysis with a precompute-or-graph decision

# A back-of-envelope model the interviewer wants you to reason through out loud.
# It quantifies the two-hop friends-of-friends cost as a function of degree,
# then picks a strategy per user segment.

def fof_cost(degree: int) -> dict:
    """Estimate raw intermediate rows and dedup work for 2-hop FoF."""
    hop1 = degree                       # my direct friends
    hop2_raw = degree * degree          # each friend's friends (pre-dedup)
    return {
        "degree": degree,
        "hop1_rows": hop1,
        "hop2_raw_rows": hop2_raw,      # what the engine must materialize
        "strategy": (
            "inline SQL"        if hop2_raw <   50_000 else
            "precompute nightly" if hop2_raw < 5_000_000 else
            "graph engine"                                  # deep/dense/real-time
        ),
    }

for deg in (20, 150, 300, 1500):
    print(fof_cost(deg))

Step-by-step trace.

User segment	Degree	2-hop raw rows (d^2)	Chosen strategy
Casual user	20	400	inline SQL — trivially fast
Typical user	150	22,500	inline SQL — still fine
Power user	300	90,000	precompute nightly into a table
Influencer	1,500	2,250,000	graph engine or capped precompute

Walking the trace out loud: the slowness is not "Postgres is bad at joins" — it is that the two-hop self-join materializes d^2 rows, and for influencer-degree users d^2 reaches millions. Casual and typical users are fine inline. Power users are best served by a nightly precompute that stores people_you_may_know(user_id, candidate_id, mutuals) so the read is a single indexed scan. Only the true influencer tail — deep, dense, and expected in real time — justifies a native graph engine or an incrementally maintained projection.

Output:

Decision axis	Signal	Verdict
Depth	fixed at 2 hops	favors relational or precompute
Density	up to 1,500 edges/node	tail explodes d^2
Freshness need	"people you may know" tolerates staleness	precompute is legitimate
Real-time deep traversal	only for the influencer tail	graph engine earns its place
Blast radius	one feature, not the whole app	do not migrate the whole DB

Why this works — concept by concept:

• Depth-times-density estimate — the whole decision reduces to estimating d^k before choosing a store. A two-hop query is d^2; that number, per user segment, tells you inline-vs-precompute-vs-graph without benchmarking blindly.
• Segment-specific strategy — the answer is not one store for everyone. Casual users run inline, power users get a precompute, only the influencer tail justifies a graph engine. Senior candidates segment; junior candidates pick one hammer.
• Precompute as the middle path — "people you may know" tolerates staleness, so a nightly job that materializes the result turns an O(d^2) read into an O(1) indexed lookup. Recognizing that freshness slack exists is the move that avoids an unnecessary migration.
• Bounded blast radius — moving one feature to a graph projection is cheap; migrating the whole product to a graph database is not. Scoping the change to the hot traversal is the senior instinct.
• Cost — inline SQL is O(d^2) per query (fatal for the tail); the precompute is O(1) read + one batch O(N·d^2) job amortized nightly; a graph engine is O(result_size) per query at the price of a second store to operate. Match the cost model to the segment.

Graph
Topic — graph
Graph traversal and connectivity problems

Practice →

Joins Topic — joins SQL join and self-join problems

Practice →

---

2. The relational way — recursive CTEs, self-joins, junction tables

recursive joins, adjacency lists, and junction tables — the full relational toolkit for relationships, and exactly where each hits a wall

The mental model in one line: the relational answer to relationships is to store them as rows — a self-referencing foreign key for hierarchies (the adjacency list), a junction table for many-to-many, fixed self-joins for known-depth traversal, and WITH RECURSIVE for unbounded-depth traversal — and this toolkit is genuinely excellent up to the point where traversal depth or relationship density makes the per-hop index-lookup cost dominate the query. Every senior engineer should be fluent in all four; the skill the interview probes is knowing precisely where each one stops being the right tool.

The adjacency list — hierarchies via a self-referencing key.

• What it is. A single self-referencing foreign key: employees(id, manager_id) where manager_id points at another employees.id. One row per node; the edge lives in the row.
• What it is great at. Cheap writes (moving a subtree is one UPDATE), the natural shape for org charts, category trees, comment threads, and file systems.
• Where it strains. Reading a whole subtree of unknown depth needs recursion; deep trees mean many recursive iterations. Alternatives like nested-set or closure-table models trade write cost for read cost.

The junction table — many-to-many as its own relation.

• What it is. A dedicated table whose rows are the relationships: friendships(a_id, b_id), enrollments(student_id, course_id), role_permissions(role_id, perm_id).
• What it is great at. Clean modeling of many-to-many, per-edge attributes (a since date, a weight), and single-hop lookups ("all courses for this student") that are one indexed scan.
• Where it strains. Multi-hop traversal self-joins the junction table, and each hop multiplies the intermediate row count by the degree — the join explosion from section 1.

Fixed self-joins vs recursive CTEs — the depth fault line.

• Fixed depth. Known, small depth → a chain of self-joins the optimizer plans well. "Manager's manager" is two joins; "mutual friends" is a bounded join.
• Variable depth. Unknown depth → WITH RECURSIVE: an anchor term plus a recursive term unioned with UNION ALL, iterating until no new rows appear.
• The catch with recursion. Cycles (A manages B who manages A, or a friendship loop) make naive recursion loop forever. You must guard against revisiting nodes.

The three walls senior engineers name.

• Per-hop index lookup. Every join hop is an O(log N) B-tree probe. Depth k on degree d is roughly O(d^k · log N) work. This is the structural cost graph engines avoid.
• Cycle handling. Recursive CTEs need an explicit visited-path guard (a Postgres CYCLE clause or a manual path array with NOT ... = ANY(path)), or they never terminate on cyclic data.
• Optimizer opacity. The planner cannot estimate recursion depth, so it cannot cost or reorder the recursive term the way it does a fixed join. You lose predictability exactly when the query is hardest.

Worked example — full subtree with a recursive CTE

Detailed explanation. The canonical relational traversal: read an entire org subtree of unknown depth from an adjacency list. Build the recursive CTE, track depth, and produce an indented path — the query every relational engineer should be able to write from memory.

• Schema. employees(id, name, manager_id), manager_id self-references id.
• Goal. Everyone reporting (directly or transitively) under employee 1, with their depth and a path string.
• Mechanism. Anchor = the root; recursive term = join children to the working set one level at a time.

Question. Write a recursive CTE that returns every descendant of employee 1 with depth and a 1 > 4 > 9 style path.

Input.

id	name	manager_id
1	Ada (root)	NULL
2	Bo	1
3	Cy	1
4	Di	2
5	Ez	4

Code.

WITH RECURSIVE subtree AS (
    -- Anchor: the root of the subtree we want.
    SELECT id, name, manager_id,
           1                       AS depth,
           id::text                AS path
    FROM   employees
    WHERE  id = 1
    UNION ALL
    -- Recursive term: attach each direct report of a row already in `subtree`.
    SELECT e.id, e.name, e.manager_id,
           s.depth + 1,
           s.path || ' > ' || e.id::text
    FROM   employees e
    JOIN   subtree s ON e.manager_id = s.id
)
SELECT depth, name, path
FROM   subtree
ORDER  BY path;

Step-by-step explanation.

1. The anchor term selects the root (id = 1), seeding the working table with one row at depth = 1 and path = '1'.
2. The recursive term joins employees e to the current working table subtree s on e.manager_id = s.id — i.e. "find the children of everyone I found last round." Each matched child gets depth + 1 and its parent's path with its own id appended.
3. Postgres runs the recursive term repeatedly: round 1 finds Bo and Cy (children of Ada), round 2 finds Di (child of Bo), round 3 finds Ez (child of Di), round 4 finds nothing and recursion stops.
4. UNION ALL accumulates every round's rows into the final subtree result. The path column threads the ancestry so ORDER BY path yields a depth-first, human-readable ordering.
5. Each recursive round issues one index probe on employees(manager_id) per working-set row. On this five-node tree that is trivial; on a million-node, ten-level tree the round count and per-round fan-out are exactly the cost you must estimate before shipping.

Output.

depth	name	path
1	Ada (root)	1
2	Bo	1 > 2
3	Di	1 > 2 > 4
4	Ez	1 > 2 > 4 > 5
2	Cy	1 > 3

Rule of thumb. For any adjacency-list tree, WITH RECURSIVE + a path column is the reference read pattern. Index the self-referencing key (manager_id) or every recursive round degrades to a sequential scan.

Worked example — cycle-safe recursion with a visited-path guard

Detailed explanation. Recursion over cyclic data (friendship graphs, transfer graphs, dependency graphs with accidental loops) will spin forever unless you guard against revisiting a node. Postgres offers two ways: a manual path array with a membership check, or the SQL-standard CYCLE clause. Build both.

• The hazard. friendships(a_id, b_id) where 1→2, 2→3, 3→1. Naive recursion loops 1→2→3→1→2→...
• Manual guard. Carry an array of visited nodes; only expand to nodes not already in it.
• CYCLE clause. Postgres 14+ can auto-detect cycles and mark them.

Question. Traverse everyone reachable from account 1 in a transfer graph that contains a cycle, without looping forever.

Input.

a_id	b_id	(edge)
1	2	1→2
2	3	2→3
3	1	3→1 (cycle)
3	4	3→4

Code.

-- Approach A: manual visited-path array (portable, explicit).
WITH RECURSIVE reach AS (
    SELECT a_id, b_id,
           ARRAY[a_id, b_id] AS path
    FROM   transfers
    WHERE  a_id = 1
    UNION ALL
    SELECT t.a_id, t.b_id,
           r.path || t.b_id
    FROM   transfers t
    JOIN   reach r ON t.a_id = r.b_id
    WHERE  NOT t.b_id = ANY(r.path)      -- do not revisit a node already on the path
)
SELECT DISTINCT b_id AS reachable FROM reach ORDER BY reachable;

-- Approach B: SQL-standard CYCLE clause (Postgres 14+).
WITH RECURSIVE reach AS (
    SELECT a_id, b_id FROM transfers WHERE a_id = 1
    UNION ALL
    SELECT t.a_id, t.b_id
    FROM   transfers t
    JOIN   reach r ON t.a_id = r.b_id
)
CYCLE b_id SET is_cycle USING cyc_path      -- auto-detect revisits on b_id
SELECT DISTINCT b_id FROM reach WHERE NOT is_cycle ORDER BY b_id;

Step-by-step explanation.

1. In Approach A the path array records every node visited on the current branch. The recursive term only expands to t.b_id when NOT t.b_id = ANY(r.path) — so when the traversal reaches the 3→1 edge, node 1 is already on the path and the branch stops. Termination is guaranteed because the path can hold each node at most once.
2. Approach B uses the CYCLE clause: CYCLE b_id SET is_cycle USING cyc_path tells Postgres to track the b_id column, set is_cycle = true on the row that closes a loop, and stash the traversal path in cyc_path. Filtering WHERE NOT is_cycle drops the looping rows.
3. Both approaches carry per-row bookkeeping (an array of visited nodes). On dense graphs this bookkeeping grows with path length and is itself a cost — every recursive row now stores a growing array, inflating memory.
4. Approach A is portable to any database with recursive CTEs; Approach B is cleaner but requires Postgres 14+. Interviewers accept either but expect you to know a cycle guard is mandatory — omitting it is the classic recursive-CTE bug.
5. This bookkeeping is exactly what native graph engines do internally as part of traversal, without you hand-rolling arrays — one reason cyclic pathfinding feels more natural in a graph query language.

Output.

reachable (from account 1)	via
2	1→2
3	1→2→3
4	1→2→3→4
(1 not re-listed)	cycle 3→1 pruned by guard

Rule of thumb. Never write a recursive CTE over data that could contain a cycle without a visited-node guard — either a path array with NOT ... = ANY(path) or the CYCLE clause. An unguarded recursion on cyclic data is an infinite loop waiting for production data to trigger it.

Worked example — the closure table, trading write cost for read speed

Detailed explanation. When an adjacency-list tree is read far more than it is written, you can precompute every ancestor-descendant pair into a closure table, turning an O(depth) recursive read into an O(1) indexed lookup. This is the relational world's answer to "make deep traversal fast" — and its cost is write amplification.

• The idea. tree_paths(ancestor, descendant, depth) holds one row for every pair connected by a path, including self-pairs at depth 0.
• The win. "All descendants of X" is SELECT descendant FROM tree_paths WHERE ancestor = X — one index scan, no recursion.
• The cost. Inserting a node writes one row per ancestor; moving a subtree rewrites many rows.

Question. Design the closure table and show the query that replaces the recursive subtree read.

Input.

Operation	Adjacency list	Closure table
read subtree	recursive CTE, O(depth)	one indexed scan, O(1)
insert leaf	one row	one row per ancestor
move subtree	one UPDATE	rewrite descendant paths

Code.

-- Closure table: one row per (ancestor, descendant) reachable pair.
CREATE TABLE tree_paths (
    ancestor    BIGINT NOT NULL,
    descendant  BIGINT NOT NULL,
    depth       INT    NOT NULL,          -- 0 = self, 1 = direct child, ...
    PRIMARY KEY (ancestor, descendant)
);
CREATE INDEX idx_tp_descendant ON tree_paths (descendant);

-- Insert a new node `child` under an existing `parent`:
--   copy every path that ends at parent, extend it by one to reach child,
--   then add the self-path (child, child, 0).
INSERT INTO tree_paths (ancestor, descendant, depth)
SELECT ancestor, :child, depth + 1
FROM   tree_paths
WHERE  descendant = :parent
UNION ALL
SELECT :child, :child, 0;

-- Read the whole subtree of X with NO recursion:
SELECT descendant, depth
FROM   tree_paths
WHERE  ancestor = :x
ORDER  BY depth;

Step-by-step explanation.

1. tree_paths materializes transitivity: if the tree is A→B→C, the table holds (A,A,0),(A,B,1),(A,C,2),(B,B,0),(B,C,1),(C,C,0). Every reachable pair is a stored row.
2. Inserting child under parent copies all paths ending at parent and extends each by one hop to reach child, then adds (child, child, 0). A node at depth k writes k+1 rows — this is the write amplification.
3. Reading a subtree becomes WHERE ancestor = :x — a single index range scan returning every descendant with its depth. No recursion, no per-hop probes, constant plan cost regardless of tree depth. This is the read win.
4. The trade is explicit: you paid write cost and storage (roughly O(nodes · average_depth) rows) to buy O(1) reads. It pays off when reads massively outnumber writes and the tree is not reshaped constantly.
5. Note what you have built: a precomputed reachability projection — the same idea a graph engine gives you natively, hand-materialized in a table. Recognizing that a closure table is a poor-man's graph index is a senior insight.

Output.

ancestor = 1	descendant	depth
self	1	0
child	2	1
grandchild	4	2
great-grandchild	5	3

Rule of thumb. For read-heavy, write-light hierarchies, a closure table converts deep recursive reads into flat index scans. For write-heavy trees, the row-per-ancestor write amplification is often worse than just paying for the recursion — measure the read/write ratio before choosing.

SQL interview question on relational traversal limits

A senior interviewer might ask: "You have a parts bill-of-materials in Postgres: assemblies(parent_sku, child_sku, qty). Product wants a 'total quantity of each raw component to build 100 bikes' report, exploding an assembly tree up to 12 levels deep with shared sub-assemblies. Write the recursive CTE, handle the quantity multiplication, and tell me where this design starts to hurt."

Solution Using a quantity-accumulating recursive CTE with a depth guard

-- Explode the BOM for BIKE-01, multiplying quantities down each path,
-- then sum per leaf component. Guard depth to fail loudly on bad data.
WITH RECURSIVE explosion AS (
    -- Anchor: the top assembly, 100 units required.
    SELECT parent_sku,
           child_sku,
           qty,
           qty * 100          AS extended_qty,   -- 100 bikes
           1                  AS depth,
           ARRAY[parent_sku]  AS path
    FROM   assemblies
    WHERE  parent_sku = 'BIKE-01'
    UNION ALL
    -- Recursive term: descend into each child that is itself an assembly,
    -- multiplying the running quantity.
    SELECT a.parent_sku,
           a.child_sku,
           a.qty,
           e.extended_qty * a.qty,
           e.depth + 1,
           e.path || a.parent_sku
    FROM   assemblies a
    JOIN   explosion e ON a.parent_sku = e.child_sku
    WHERE  e.depth < 12                            -- hard depth guard
      AND  NOT a.parent_sku = ANY(e.path)          -- cycle guard
)
SELECT child_sku                AS component,
       SUM(extended_qty)        AS total_required
FROM   explosion
-- Keep only leaves: components that are never a parent (raw parts).
WHERE  child_sku NOT IN (SELECT DISTINCT parent_sku FROM assemblies)
GROUP  BY child_sku
ORDER  BY total_required DESC;

Step-by-step trace.

Level	Row expanded	Running multiply	extended_qty
1	BIKE-01 → WHEEL (qty 2)	2 × 100	200
2	WHEEL → SPOKE (qty 32)	200 × 32	6,400
2	WHEEL → TIRE (qty 1)	200 × 1	200
1	BIKE-01 → FRAME (qty 1)	1 × 100	100
2	FRAME → BOLT (qty 8)	100 × 8	800

Walking it out loud: the anchor pulls BIKE-01's direct children and multiplies each qty by the 100 units required. The recursive term descends into any child that is itself a parent in assemblies (i.e. a sub-assembly), multiplying the running extended_qty by the child's qty at each level. The depth guard (< 12) and cycle guard (NOT ... = ANY(path)) keep a malformed BOM from looping. The final GROUP BY sums per leaf component, and the NOT IN (parents) filter keeps only raw parts. Shared sub-assemblies (a bolt used in both the wheel and the frame) are summed correctly because every path contributes its own row.

Output:

component	total_required
SPOKE	6,400
BOLT	800
TIRE	200
...	...

Why this works — concept by concept:

• Quantity accumulation in the recursive term — multiplying e.extended_qty * a.qty at each descent turns the tree walk into a correct quantity explosion. The running product is the load-bearing trick that distinguishes a BOM explosion from a plain reachability query.
• Depth guard — e.depth < 12 bounds the recursion so a data error (a sub-assembly that lists itself) fails predictably instead of running the server out of memory. Bounding unbounded recursion is a production reflex.
• Cycle guard via path array — NOT a.parent_sku = ANY(e.path) prevents a cyclic BOM from looping forever, the same guard from the cycle-safe example applied to a real workload.
• Leaf filter — child_sku NOT IN (SELECT parent_sku ...) isolates raw components from intermediate assemblies so the report sums only purchasable parts.
• Cost — the recursion visits every path in the assembly DAG; with shared sub-assemblies the number of paths can be far larger than the number of nodes, so cost is O(paths) not O(nodes). This is exactly where a graph engine — which walks nodes with pointer hops and can deduplicate visited nodes cheaply — starts to pull ahead as the DAG grows deeper and more shared.

SQL
Topic — joins
Recursive CTE and hierarchy problems

Practice →

Optimization Topic — optimization Query-plan and index-tuning problems

Practice →

---

3. The graph way — traversals and constant-cost hops

index-free adjacency — why a native graph database makes each hop a pointer dereference instead of an index lookup

The mental model in one line: a native graph database stores nodes and relationships as first-class records with direct physical pointers between adjacent elements, so traversing a relationship is a pointer dereference whose cost does not depend on the total size of the graph — this property, called index-free adjacency, turns a depth-k traversal from the relational O(d^k · log N) into O(size of the frontier actually touched), which is why deep, variable-length, and pathfinding queries that punish recursive SQL run comfortably on a graph engine. The graph query language (Cypher in Neo4j, Gremlin, or SQL/PGQ in newer standards) expresses traversal as a first-class pattern rather than a chain of joins.

The property model — nodes, relationships, properties.

• Nodes. Entities with labels and properties: (:Person {id: 1, name: 'Ada'}). The equivalent of a row, but with a direct handle other records can point to.
• Relationships. First-class, typed, directed edges with their own properties: (a)-[:KNOWS {since: 2019}]->(b). Unlike a junction-table row, a relationship stores physical pointers to both endpoint nodes.
• Traversal. Following a relationship is dereferencing a stored pointer — no lookup into a global index keyed by the neighbour's id.

Index-free adjacency, precisely.

• What "index-free" means. After you find the starting node (that first lookup does use an index), every subsequent hop reads pointers stored on the node and its relationships. The engine never re-consults a global B-tree to find neighbours.
• The complexity consequence. A relational hop is O(log N) (probe a B-tree of N rows). A graph hop is O(1) amortized — it reads the adjacent record directly. Over k hops touching a frontier of size F, the traversal is O(F), independent of the total node count N.
• The write-time price. Maintaining adjacency pointers is a small extra cost on insert/delete. Graph engines pay it once at write time to make every future traversal cheap.

What Cypher expresses that SQL cannot, naturally.

• Variable-length paths. (a)-[:KNOWS*1..3]->(b) matches any path of 1 to 3 KNOWS hops in a single clause. In SQL this is a recursive CTE with a depth guard.
• Shortest path. shortestPath((a)-[:KNOWS*]-(b)) is a built-in; in SQL you must hand-roll a breadth-first recursion and stop at the first hit.
• Pattern matching. (a)-[:TRANSFER]->(b)-[:TRANSFER]->(a) matches a two-node cycle declaratively; the engine's traversal explores only reachable neighbours, never a full join product.

Where graph genuinely wins.

• Deep and variable traversal. Reachability, ancestry, dependency closures — anything where depth is a property of the data.
• Pathfinding. Shortest path, all paths, weighted paths (Dijkstra/A* variants ship as library procedures).
• Dense pattern matching. Fraud rings, recommendation co-occurrence, "common connections" — patterns that would be a many-way self-join with catastrophic fan-out in SQL.

Worked example — friends-of-friends as a native traversal

Detailed explanation. The same friends-of-friends query that exploded into a d^2 self-join in section 1 is a two-hop pattern in Cypher. Write it, and see how the engine walks only the reachable frontier instead of materializing a join product.

• Model. (:Person)-[:KNOWS]->(:Person).
• Goal. People two hops from Ada, excluding Ada and her direct friends, ranked by number of mutual connections.
• Mechanism. Match a two-hop pattern; the engine dereferences pointers, never probing a global index after the anchor.

Question. Write the Cypher for ranked friends-of-friends and explain what the engine does per hop.

Input.

Cypher element	Role
(me:Person {id: 1})	anchor — one index lookup
-[:KNOWS]->(f)	hop 1 — pointer dereference
-[:KNOWS]->(fof)	hop 2 — pointer dereference
count(DISTINCT f)	mutual-connection ranking

Code.

// Ranked friends-of-friends for Ada (id 1).
MATCH (me:Person {id: 1})-[:KNOWS]->(f:Person)-[:KNOWS]->(fof:Person)
WHERE fof <> me
  AND NOT (me)-[:KNOWS]->(fof)          // exclude people Ada already knows
RETURN fof.name           AS candidate,
       count(DISTINCT f)  AS mutual_connections
ORDER  BY mutual_connections DESC
LIMIT  20;

Step-by-step explanation.

1. (me:Person {id: 1}) is the single indexed lookup — the engine finds Ada's node once via an index on Person.id. This is the only index access in the whole traversal.
2. -[:KNOWS]->(f) dereferences the pointers stored on Ada's node to reach her direct friends. No index probe: the neighbours are physically linked. This is index-free adjacency in action.
3. -[:KNOWS]->(fof) repeats the pointer-follow from each friend to their friends. The engine walks only real edges, so it touches exactly the reachable frontier — not a d^2 cartesian materialization.
4. WHERE fof <> me AND NOT (me)-[:KNOWS]->(fof) prunes Ada herself and existing friends. The NOT (me)-[:KNOWS]->(fof) is a direct adjacency check — again a pointer test, not a subquery scan.
5. count(DISTINCT f) ranks each candidate by how many of Ada's friends connect to them — the "mutual connections" signal — computed as the traversal aggregates. The cost is proportional to the frontier touched, O(F), not O(d^2) materialized rows.

Output.

candidate	mutual_connections
Faye	7
Guo	5
Hana	4
...	...

Rule of thumb. In a graph engine, friends-of-friends is a two-hop MATCH whose cost tracks the frontier actually reachable. The denser and deeper the query, the larger the gap versus the relational d^k self-join — density is precisely where the graph model earns its keep.

Worked example — variable-length paths and bill-of-materials

Detailed explanation. The BOM explosion that needed a guarded recursive CTE in section 2 is a variable-length path with a reduce over the relationship list in Cypher. Write it and see how quantity multiplication and depth-flexibility collapse into one clause.

• Model. (:Part)-[:CONTAINS {qty: n}]->(:Part).
• Goal. Total quantity of each leaf component to build 100 of BIKE-01.
• Mechanism. [:CONTAINS*1..] matches any-depth paths; reduce multiplies quantities along each path.

Question. Write the Cypher BOM explosion with quantity multiplication.

Input.

Cypher element	Role
[:CONTAINS*1..]	variable-length: any depth
reduce(...)	multiply qty along the path
NOT (leaf)-[:CONTAINS]->()	leaf = a part with no children
sum(...)	total per component

Code.

// Explode BIKE-01, multiplying quantities down each path, sum per leaf.
MATCH path = (top:Part {sku: 'BIKE-01'})-[rels:CONTAINS*1..]->(leaf:Part)
WHERE NOT (leaf)-[:CONTAINS]->()        // leaf = raw component (no children)
WITH leaf,
     reduce(q = 100, r IN rels | q * r.qty) AS extended_qty  // 100 bikes
RETURN leaf.sku          AS component,
       sum(extended_qty) AS total_required
ORDER  BY total_required DESC;

Step-by-step explanation.

1. [:CONTAINS*1..] is the variable-length operator: it matches paths of one or more CONTAINS hops in a single pattern. The depth guard and recursion boilerplate of the SQL version vanish — depth-flexibility is native.
2. path = (...) binds the whole path so its relationship list rels is available to reduce. Each element r carries its own qty property.
3. reduce(q = 100, r IN rels | q * r.qty) folds the multiplication down the path: start at 100 (bikes required), multiply by each hop's qty. This is the direct analogue of the SQL running product, expressed as a fold.
4. WHERE NOT (leaf)-[:CONTAINS]->() keeps only leaves — parts that contain nothing — the same "raw component" filter as the SQL NOT IN (parents), but as an adjacency test.
5. The engine walks the assembly DAG following pointers, so shared sub-assemblies are traversed per path and summed by sum(extended_qty). Neo4j caps runaway variable-length expansion, but for well-formed DAGs the traversal touches each edge as it explores reachable paths — no join product.

Output.

component	total_required
SPOKE	6,400
BOLT	800
TIRE	200
...	...

Rule of thumb. Any "explode a tree/DAG of unknown depth" query is a one-line variable-length path in Cypher versus a guarded recursive CTE in SQL. When depth is genuinely variable, the graph query language is not just faster — it is dramatically more readable, which matters for maintenance.

Worked example — shortest path and degrees of separation

Detailed explanation. "Fewest introductions between two people" — shortest path in a social graph — is a built-in graph primitive and a hand-rolled breadth-first recursion in SQL. Write the Cypher and note what the engine does that a recursive CTE cannot easily.

• Model. (:Person)-[:KNOWS]-(:Person) (undirected traversal).
• Goal. The shortest chain of acquaintances from Ada (1) to Zed (99).
• Mechanism. shortestPath explores breadth-first and stops at the first connection found.

Question. Write the Cypher for the shortest acquaintance chain and its length.

Input.

Cypher element	Role
shortestPath((a)-[:KNOWS*..6]-(b))	built-in BFS, capped at 6
length(p)	degrees of separation
nodes(p)	the people on the chain

Code.

// Shortest acquaintance chain from Ada (1) to Zed (99), at most 6 hops.
MATCH (a:Person {id: 1}), (b:Person {id: 99})
MATCH p = shortestPath((a)-[:KNOWS*..6]-(b))
RETURN length(p)                    AS degrees_of_separation,
       [n IN nodes(p) | n.name]     AS chain;

Step-by-step explanation.

1. The two anchor MATCHes find Ada and Zed via the Person.id index — the two index lookups that bookend the traversal.
2. shortestPath((a)-[:KNOWS*..6]-(b)) runs a bidirectional breadth-first search over KNOWS edges, capped at 6 hops. The undirected -[:KNOWS*..6]- (no arrow) lets it traverse the relationship in either direction.
3. The engine stops the moment it finds a shortest path — it does not enumerate all paths. This early termination is the key efficiency: a naive SQL recursion would expand the full frontier at each level and then compute the minimum, whereas shortestPath prunes as soon as the two search frontiers meet.
4. length(p) returns the hop count (degrees of separation) and [n IN nodes(p) | n.name] projects the names along the chain — a list comprehension over the path's nodes.
5. Reproducing this in SQL means a breadth-first recursive CTE that tracks depth, dedups visited nodes, and manually stops at the first depth where the target appears — dozens of lines versus one built-in. Pathfinding is the clearest "graph wins" category.

Output.

degrees_of_separation	chain
3	["Ada", "Faye", "Guo", "Zed"]

Rule of thumb. Shortest-path, all-paths, and weighted-path queries are built-in graph procedures and hand-rolled recursions in SQL. If pathfinding is a core feature — routing, social distance, dependency-impact analysis — that alone can justify a graph engine.

Graph interview question on modeling a workload for traversal

A senior interviewer might ask: "We are building an access-control system: users belong to groups, groups nest inside groups, and permissions attach at any level. The hot query is 'does user U have permission P?' which means walking up an arbitrarily deep group-membership graph. Model this as a graph, write the Cypher, and explain why index-free adjacency makes the authorization check fast."

Solution Using a nested-group graph with a variable-length authorization traversal

// Model:
//   (:User)-[:MEMBER_OF]->(:Group)
//   (:Group)-[:MEMBER_OF]->(:Group)          // groups nest arbitrarily deep
//   (:Group)-[:GRANTS]->(:Permission)
//   (:User)-[:GRANTS]->(:Permission)         // direct grants too

// Authorization check: does user 1 have permission 'billing:write'?
MATCH (u:User {id: 1}), (p:Permission {name: 'billing:write'})
RETURN EXISTS {
    MATCH (u)-[:MEMBER_OF*0..]->(:Group)-[:GRANTS]->(p)   // via any group depth
} OR EXISTS {
    MATCH (u)-[:GRANTS]->(p)                              // or a direct grant
} AS has_permission;

// List *why* (the granting path) for an audit view:
MATCH path = (u:User {id: 1})-[:MEMBER_OF*0..]->(g:Group)-[:GRANTS]->(p:Permission {name: 'billing:write'})
RETURN [n IN nodes(path) | coalesce(n.name, n.id)] AS grant_path
LIMIT 5;

Step-by-step trace.

Step	Traversal	Cost model
find user 1	Person.id index	one index lookup
-[:MEMBER_OF*0..]->	walk group nesting via pointers	O(groups reachable), index-free
-[:GRANTS]->(p)	check permission edge	pointer test
EXISTS { ... }	stop at first satisfying path	early termination
direct-grant branch	(u)-[:GRANTS]->(p)	one hop

Walking the trace: the check finds user 1 once by index, then follows MEMBER_OF pointers up the group hierarchy — *0.. means "zero or more hops", so a direct group grant and a five-levels-nested grant are the same clause. At each group it tests for a GRANTS edge to the target permission. EXISTS { ... } short-circuits at the first satisfying path, so a user who inherits the permission from their immediate group pays almost nothing; only a denied check walks the full reachable group set. The audit query reuses the same pattern but returns the granting path for a "why does this user have access?" view.

Output:

has_permission	grant_path (audit)
true	["user:1", "eng-team", "all-staff", "billing:write"]

Why this works — concept by concept:

• Nested groups as MEMBER_OF edges — modeling group nesting as relationships makes "arbitrary depth" a *0.. traversal instead of a recursive CTE. Depth-flexibility is the whole authorization requirement, and the graph expresses it in one operator.
• index-free adjacency — after the single lookup for user 1, every MEMBER_OF and GRANTS step is a pointer dereference. The check cost depends on the groups reachable from this user, not on the total number of users, groups, or permissions in the system — so it stays fast as the org grows.
• EXISTS early termination — an authorization check needs a yes/no, so EXISTS stops at the first granting path. Most checks succeed shallowly and return almost immediately.
• One pattern for check and audit — the same MEMBER_OF*0.. > GRANTS pattern answers both "may they?" and "why may they?", which a bespoke SQL permission-resolution routine rarely does cleanly.
• Cost — O(groups reachable from the user) per check, independent of global cardinality, versus a relational recursive CTE that is O(depth · membership fan-out · log N) per check. For a deep, densely-nested org, the graph traversal is the difference between a sub-millisecond and a multi-hundred-millisecond authorization check on the hot path.

Graph
Topic — graph
Variable-length path and pathfinding problems

Practice →

Design Topic — design Design problems on graph-modeled systems

Practice →

---

4. Head-to-head — the same query in SQL vs Cypher

cypher vs sql on three canonical workloads — friends-of-friends, bill-of-materials, and fraud rings, with the complexity that decides each

The mental model in one line: put the same query side by side in recursive SQL and in Cypher across three depth-increasing workloads — a fixed two-hop friends-of-friends, a variable-depth bill-of-materials, and a cyclic fraud-ring detection — and the pattern is consistent: SQL and graph are comparable at shallow fixed depth, and the graph pulls away as depth grows, becomes variable, or turns cyclic, because relational cost is O(d^k · log N) in joins while graph cost is O(frontier touched) in pointer hops. This section is the direct cypher vs sql comparison interviewers love, with the complexity analysis that justifies each verdict.

How to read a head-to-head fairly.

• Same data, same result. Both queries must return the identical set; a comparison that quietly changes the result is worthless.
• Compare the cost model, not one benchmark. A single benchmark on one dataset misleads. The durable comparison is the complexity as a function of depth and density — that predicts behaviour across datasets.
• Account for the second store. The graph win is a query-time win; it costs you an extra system to operate and keep in sync. A fair head-to-head names that operational tax.

The three workloads, by increasing difficulty for SQL.

• Friends-of-friends (fixed depth 2). The easiest for SQL — a bounded self-join. Graph is cleaner but the gap is small at depth 2.
• Bill-of-materials (variable depth). Depth is a property of the data. SQL needs a guarded recursive CTE; graph needs a variable-length path. The gap widens.
• Fraud ring (cyclic, variable depth). Cycles plus variable depth. SQL needs cycle-guarded recursion that materializes paths; graph matches a cycle pattern declaratively. The gap is largest.

The complexity that decides it.

• Relational per hop. Each join hop is an O(log N) index probe; a depth-k traversal over degree d is O(d^k · log N) work, plus dedup on the materialized intermediate set.
• Graph per hop. Each hop is O(1) pointer dereference; a depth-k traversal is O(F) where F is the frontier actually reached, independent of N.
• Where they cross. At k = 1..2 and modest d, the two are comparable and the simpler-to-operate single store (relational) usually wins. As k grows or the graph turns cyclic/dense, the d^k · log N term dominates and graph wins decisively.

Worked example — friends-of-friends, side by side

Detailed explanation. Depth 2, fixed. This is SQL's best case for a traversal, so it is the fair place to start: the graph is more readable but the performance gap is modest. Put both queries next to each other.

• Result contract. People exactly two hops away, excluding self and direct friends.
• SQL. Self-join the junction table once.
• Cypher. A two-hop MATCH.

Question. Write both, and state the complexity of each at depth 2.

Input.

Side	Structure	Depth
SQL	self-join friendships	fixed 2
Cypher	(me)-[:KNOWS]->()-[:KNOWS]->(fof)	fixed 2

Code.

-- SQL: fixed two-hop self-join.
SELECT DISTINCT f2.b_id AS fof
FROM   friendships f1
JOIN   friendships f2 ON f2.a_id = f1.b_id
WHERE  f1.a_id = 1
  AND  f2.b_id <> 1
  AND  NOT EXISTS (SELECT 1 FROM friendships x
                   WHERE x.a_id = 1 AND x.b_id = f2.b_id);

// Cypher: the same result as a two-hop pattern.
MATCH (me:Person {id: 1})-[:KNOWS]->(:Person)-[:KNOWS]->(fof:Person)
WHERE fof <> me AND NOT (me)-[:KNOWS]->(fof)
RETURN DISTINCT fof.name AS fof;

Step-by-step explanation.

1. The SQL self-join is a bounded two-table join — the optimizer plans it well, using the index on friendships(a_id) for both hops. At degree d, it materializes ~d^2 intermediate rows and dedups them.
2. The Cypher walks two pointer hops from the anchor and aggregates the reachable set. It touches the same logical frontier but never builds a d^2 row product it must then dedup.
3. At depth 2 with typical degree (tens to low hundreds), both run in milliseconds. d^2 for d = 100 is 10,000 rows — nothing for Postgres. This is why "just use Postgres" is correct for shallow social queries.
4. The readability difference is real even here: the Cypher pattern looks like the question ("me, my friend, their friend"), while the SQL requires reading alias plumbing. For a fixed depth-2 query that is a maintenance nicety, not a performance argument.
5. The verdict at depth 2: comparable performance, graph slightly more readable, relational wins on "one fewer system to operate." The gap only opens up as depth grows — which the next two examples show.

Output.

Metric	SQL (self-join)	Cypher (2-hop)
Complexity	O(d^2 · log N) + dedup	O(frontier) ≈ O(d^2) touched
Depth-2 latency	milliseconds	milliseconds
Readability	alias-heavy	pattern mirrors the question
Operational cost	single store	second store to sync
Verdict at depth 2	relational usually wins	negligible speed edge

Rule of thumb. At fixed depth 1–2, keep it relational unless you already run a graph engine for other reasons. The self-join's d^2 is cheap at low depth, and one store beats two. Do not migrate for a two-hop query.

Worked example — bill-of-materials, side by side

Detailed explanation. Now depth becomes variable. The SQL side needs the guarded recursive CTE from section 2; the graph side needs the variable-length path from section 3. Put them next to each other to see the expressiveness gap widen.

• Result contract. Total quantity per leaf component to build 100 units, over an unknown-depth DAG with shared sub-assemblies.
• SQL. Guarded, quantity-accumulating recursive CTE.
• Cypher. Variable-length path with reduce.

Question. Compare the two implementations and their complexity on a depth-k DAG.

Input.

Side	Depth handling	Quantity math
SQL	WITH RECURSIVE + depth guard	running product column
Cypher	[:CONTAINS*1..]	reduce fold

Code.

-- SQL: (condensed from section 2) guarded recursive explosion.
WITH RECURSIVE explosion AS (
    SELECT parent_sku, child_sku, qty, qty*100 AS ext, 1 AS depth,
           ARRAY[parent_sku] AS path
    FROM assemblies WHERE parent_sku = 'BIKE-01'
    UNION ALL
    SELECT a.parent_sku, a.child_sku, a.qty, e.ext*a.qty, e.depth+1,
           e.path || a.parent_sku
    FROM assemblies a JOIN explosion e ON a.parent_sku = e.child_sku
    WHERE e.depth < 12 AND NOT a.parent_sku = ANY(e.path)
)
SELECT child_sku, SUM(ext) AS total
FROM explosion
WHERE child_sku NOT IN (SELECT parent_sku FROM assemblies)
GROUP BY child_sku;

// Cypher: the same explosion in four lines.
MATCH path = (top:Part {sku:'BIKE-01'})-[rels:CONTAINS*1..]->(leaf:Part)
WHERE NOT (leaf)-[:CONTAINS]->()
WITH leaf, reduce(q = 100, r IN rels | q * r.qty) AS ext
RETURN leaf.sku, sum(ext) AS total ORDER BY total DESC;

Step-by-step explanation.

1. The SQL recursive CTE must spell out the anchor, the recursive term, the depth guard, the cycle guard, the running-product column, and the leaf filter — six moving parts. Each is a place to introduce a bug (forgetting the cycle guard is the classic one).
2. The Cypher expresses the same logic in four lines: variable-length pattern, leaf filter, reduce for the quantity fold, aggregate. Depth-flexibility and cycle handling are the engine's job, not yours.
3. On cost: both walk the assembly DAG's paths. With shared sub-assemblies the path count exceeds the node count, so both are O(paths). But the SQL side additionally materializes and dedups intermediate rows and re-probes an index each hop (· log N), while the graph follows pointers (· 1).
4. As the DAG deepens (12 levels is common in manufacturing) and sub-assembly sharing increases, the relational log N per hop and the intermediate materialization compound. The graph's constant-hop cost keeps the traversal proportional to paths touched.
5. Verdict: at variable depth the graph wins on both readability and, as depth/sharing grow, performance. This is the first workload where a migration argument becomes defensible — if BOM explosion is a hot, deep, real-time query.

Output.

Metric	SQL recursive CTE	Cypher variable-length
Lines of query	~14, six moving parts	~4
Cycle handling	manual guard required	engine-handled
Complexity	O(paths · log N) + dedup	O(paths) pointer hops
Depth flexibility	guard + UNION ALL	*1.. operator
Verdict	fine to ~few levels	wins as depth/sharing grow

Rule of thumb. When traversal depth is a property of the data and the query is hot, the graph's variable-length path beats the recursive CTE on maintainability first and performance second. Deep, shared DAGs (BOM, dependency graphs, permission inheritance) are the sweet spot.

Worked example — fraud-ring detection, side by side

Detailed explanation. The hardest case for SQL: find cycles — accounts that transfer money in a loop back to themselves within 3–6 hops. Cyclic and variable depth. The SQL side needs cycle-guarded recursion that materializes candidate paths; the graph side matches a cycle pattern.

• Result contract. Rings of 3–6 accounts where money flows A → B → C → ... → A.
• SQL. Recursive CTE tracking the path, detecting the return-to-start.
• Cypher. A cyclic variable-length pattern that starts and ends at the same node.

Question. Compare cycle detection in both and their complexity.

Input.

Side	Cycle mechanism	Depth
SQL	path array, detect start reappearing	3..6
Cypher	(a)-[:TRANSFER*3..6]->(a)	3..6

Code.

-- SQL: cycle detection via a path array that must return to the start.
WITH RECURSIVE walk AS (
    SELECT a_id AS start_id, b_id AS cur, 1 AS hops,
           ARRAY[a_id, b_id] AS path
    FROM   transfers
    UNION ALL
    SELECT w.start_id, t.b_id, w.hops + 1, w.path || t.b_id
    FROM   transfers t
    JOIN   walk w ON t.a_id = w.cur
    WHERE  w.hops < 6
      AND  (t.b_id = w.start_id OR NOT t.b_id = ANY(w.path))  -- allow closing the loop
)
SELECT DISTINCT path AS ring
FROM   walk
WHERE  cur = start_id            -- returned to the origin
  AND  hops BETWEEN 3 AND 6;

// Cypher: a ring is a path that starts and ends at the same account.
MATCH ring = (a:Account)-[:TRANSFER*3..6]->(a)
RETURN [n IN nodes(ring) | n.id] AS accounts
LIMIT 20;

Step-by-step explanation.

1. The SQL recursion starts a walk from every edge (no anchor filter — we are searching the whole graph for rings), carries a start_id and a path array, and extends until it either returns to start_id (a ring) or hits the depth cap. This walks an enormous candidate space.
2. The cycle condition is subtle: t.b_id = w.start_id OR NOT t.b_id = ANY(w.path) allows the loop to close on the start while still forbidding other revisits. Getting this predicate exactly right is where most SQL cycle-detection attempts break.
3. The final filter cur = start_id AND hops BETWEEN 3 AND 6 keeps only genuine rings. The intermediate set — every partial walk from every account — is huge; this is O(d^6) candidate paths in the worst case, materialized.
4. The Cypher (a:Account)-[:TRANSFER*3..6]->(a) says exactly what a ring is: a 3-to-6 hop path returning to the same node. The engine explores reachable neighbours with pointer hops and binds the same a at both ends — no whole-graph candidate materialization.
5. Verdict: fraud-ring detection is the clearest graph win. The SQL is long, error-prone, and materializes a d^k candidate space; the Cypher is one line and walks only real edges. Cyclic pattern-matching at variable depth is the category graph databases were built for.

Output.

Metric	SQL recursive cycle search	Cypher cycle pattern
Query length	~14 lines, subtle predicate	1 line
Candidate space	O(d^6) partial walks materialized	frontier reachable via pointers
Correctness risk	high (close-loop predicate)	low (pattern is the spec)
Complexity	O(d^k · log N) + dedup	O(frontier)
Verdict	painful	graph wins decisively

Rule of thumb. Cyclic, variable-depth pattern matching — fraud rings, circular dependencies, money-laundering loops — is the workload where graph databases beat recursive SQL by the widest margin. If cycle detection is a core feature, that is a strong standalone reason to reach for a graph engine.

SQL-vs-Cypher interview question on justifying a store choice

A senior interviewer might ask: "Product wants three features on our transaction data: a two-hop 'who did my counterparties also pay' view, an unbounded 'trace the full downstream flow of these funds' view, and a real-time 'flag transfers that complete a 3–6 account loop' alert. We are on Postgres today. For each feature, tell me whether you'd keep it in SQL or move it to a graph engine, and defend it with complexity."

Solution Using a per-feature depth analysis mapping each to SQL or graph

# Map each feature to a store based on depth, cyclicity, and freshness.
features = [
    # name,                       depth,        cyclic, realtime
    ("counterparty 2-hop view",   "fixed-2",    False,  False),
    ("downstream funds trace",    "unbounded",  False,  True),
    ("3-6 account loop alert",    "3..6",       True,   True),
]

def decide(depth, cyclic, realtime):
    if depth == "fixed-2" and not cyclic:
        return "SQL — bounded self-join, O(d^2), keep in Postgres"
    if cyclic:
        return "GRAPH — cyclic pattern match, worst case for recursive SQL"
    if depth == "unbounded" and realtime:
        return "GRAPH — variable-length traversal, O(frontier) not O(d^k·logN)"
    return "SQL — recursive CTE is adequate"

for name, depth, cyclic, realtime in features:
    print(f"{name:30} -> {decide(depth, cyclic, realtime)}")

Step-by-step trace.

Feature	Depth	Cyclic?	Real-time?	Verdict
Counterparty 2-hop view	fixed 2	no	no	SQL self-join
Downstream funds trace	unbounded	no	yes	Graph traversal
3–6 account loop alert	3..6	yes	yes	Graph cycle pattern

Walking it out loud: feature one is a fixed two-hop self-join — O(d^2), cheap, stays in Postgres; migrating it would add a second store for no gain. Feature two traces funds to arbitrary depth in real time — a recursive CTE works but its O(d^k · log N) cost and materialization make it fragile as flows deepen, so a graph traversal's O(frontier) is the safer real-time choice. Feature three is cyclic and real-time — the exact worst case for recursive SQL and the exact best case for a graph engine's cycle pattern. The senior answer is not "move everything" — it is a per-feature verdict grounded in depth, cyclicity, and freshness.

Output:

Feature	Store	Primary reason
Counterparty 2-hop	Postgres (SQL)	shallow fixed depth, one store wins
Funds trace	Graph	unbounded depth, real-time, O(frontier)
Loop alert	Graph	cyclic pattern, worst case for SQL

Why this works — concept by concept:

• Per-feature verdict — the interview reward is refusing a blanket answer. Each feature is scored on depth, cyclicity, and freshness, and only the two that genuinely need a graph get one. Segmenting beats dogma.
• Fixed depth stays relational — the two-hop view is O(d^2) and cheap; keeping it in Postgres avoids a needless second store and its sync burden. Recognizing when not to use the shiny tool is the senior signal.
• Unbounded + real-time goes graph — the funds trace's depth is a data property, and real-time removes the precompute escape hatch, so the graph's constant-hop traversal is the robust choice.
• Cyclic goes graph — loop detection is where recursive SQL is longest, most error-prone, and most expensive; the graph's cycle pattern is one line and walks only real edges.
• Cost — SQL feature is O(d^2) (fine); graph features are O(frontier) per query versus a recursive O(d^k · log N) that materializes a d^k candidate space. The cost model, not a vibe, drives each verdict — and it names the operational price of the second store instead of hiding it.

Graph
Topic — graph
Cycle-detection and pattern-matching problems

Practice →

Joins Topic — joins Multi-hop join and recursive-query problems

Practice →

---

5. Decision framework — when relational wins, when graph wins

The graph vs relational decision, reduced to depth, density, query shape, and a hybrid escape hatch

The mental model in one line: the graph vs relational choice is not a religion but a four-question decision — how deep are the hot traversals, how dense are the relationships, is the depth fixed or variable, and is the workload traversal-heavy or write/aggregate-heavy — and for a large fraction of real systems the honest answer is a hybrid: keep the relational database as the source of truth for tabular data and transactions, and project the relationship-heavy slice into a graph engine (or a Postgres graph extension) for the traversals that punish recursive SQL. The senior move is to name the threshold and the hybrid, not to pick a side.

When relational wins — keep it in the table.

• Shallow, fixed-depth joins. One or two hops of known depth. The optimizer plans them; the d^k term is tiny.
• Aggregation and reporting. GROUP BY, window functions, roll-ups over columns. Graph engines are not built for wide tabular aggregation; relational is.
• Transactional single-store integrity. When the data is fundamentally tabular and you need ACID across many tables in one system, a second store is pure overhead.
• Modest relationship density. Sparse graphs keep even multi-hop queries cheap; the d^k explosion never fires.

When graph wins — reach for the traversal engine.

• Deep or variable-depth traversal. Reachability, ancestry, dependency closures, "everything connected to X." Depth as a data property.
• Pathfinding. Shortest path, all paths, weighted routes — built-in graph primitives, hand-rolled recursions in SQL.
• Dense many-to-many pattern matching. Fraud rings, recommendations, common-connections — where SQL fan-out is catastrophic and the graph walks pointers.
• Real-time deep queries. When you cannot precompute because freshness matters and depth is variable.

The hybrid patterns — the answer for most real systems.

• Source-of-truth + graph projection. Postgres holds the canonical data; a CDC or ETL job projects the relationship slice into Neo4j (or similar) for traversals. Writes go to Postgres; deep reads go to the graph.
• Graph extension inside Postgres. Apache AGE adds openCypher to Postgres; pgRouting adds graph algorithms for geospatial routing; ltree handles materialized-path hierarchies. You get graph queries without a second system — at the cost of the engine still being relational underneath (no true index-free adjacency).
• Query virtualization. Tools like PuppyGraph expose relational tables as a graph for Cypher/Gremlin queries without copying data — a middle path when you want graph query ergonomics over an existing warehouse.

The interview signals that mark a senior answer.

• Name index-free adjacency as the reason graph hops are constant-cost. Required.
• Name a concrete depth threshold ("past ~3–4 variable hops on a dense graph") rather than "when it gets slow." Senior.
• Name the hybrid — source-of-truth plus projection, or AGE/pgRouting — instead of framing it as all-or-nothing. Senior.
• Name the operational cost of a second store (sync, consistency, ops burden) so the graph choice is honest. Senior.

Worked example — scoring a workload on the four axes

Detailed explanation. Turn the decision into a reproducible scoring rubric: rate each hot query on depth, density, variability, and freshness, and let the scores point at relational, graph, or hybrid. Walk three real workloads through it.

• The rubric. Score depth (hops), density (edges/node), variability (fixed/variable), freshness (batch/real-time).
• The mapping. Low on all → relational. High depth+density+variability → graph. Mixed → hybrid.

Question. Score an org-chart read, a recommendation "also bought" query, and a fraud-ring alert, and assign each a store.

Input.

Workload	Depth	Density	Variable?	Real-time?
Org-chart subtree	up to ~8	low (1 manager)	variable	batch OK
"Also bought" recs	2–3	high	fixed-ish	near real-time
Fraud-ring alert	3–6	high	variable + cyclic	real-time

Code.

def score_workload(depth, density, variable, cyclic, realtime):
    """Return a store recommendation from four-axis scores."""
    graph_pressure = 0
    graph_pressure += 2 if depth >= 4 else 0
    graph_pressure += 2 if density == "high" else 0
    graph_pressure += 1 if variable else 0
    graph_pressure += 2 if cyclic else 0
    graph_pressure += 1 if realtime else 0
    if graph_pressure >= 5:
        return "GRAPH (or graph projection)"
    if graph_pressure >= 3:
        return "HYBRID — relational truth + graph projection"
    return "RELATIONAL"

print(score_workload(8, "low",  True,  False, False))  # org chart
print(score_workload(3, "high", False, False, True))   # also-bought
print(score_workload(6, "high", True,  True,  True))    # fraud ring

Step-by-step explanation.

1. The org-chart read is deep (up to 8) but sparse (each node has one manager) and batch-tolerant. Its graph-pressure score is moderate: depth pushes toward graph, but low density and no cyclicity/real-time pull it back. It lands on relational (a recursive CTE) or a closure table — no graph engine needed.
2. "Also bought" is shallow (2–3 hops) but dense and near-real-time. Density and freshness raise the score into hybrid territory: a graph projection of the co-purchase relationships serves the recommendations while Postgres stays the order source of truth.
3. The fraud-ring alert scores high on every axis that matters — depth, density, variability, cyclicity, real-time — landing squarely on graph. This is the workload that alone justifies operating a graph engine.
4. The rubric's value is forcing an explicit score instead of a gut call. Two engineers who disagree can compare axis scores rather than argue vibes.
5. Note that two of three workloads did not land on "pure graph" — they landed on relational and hybrid. That distribution is realistic: most systems have one or two traversal-heavy features amid a majority of tabular work.

Output.

Workload	Graph-pressure	Store
Org-chart subtree	moderate	Relational (recursive CTE / closure table)
"Also bought" recs	3+	Hybrid — graph projection
Fraud-ring alert	5+	Graph

Rule of thumb. Score every candidate query on depth, density, variability, and freshness before choosing a store. Most workloads land on relational or hybrid; reserve a dedicated graph engine for the queries that score high on multiple axes at once.

Worked example — a hybrid Postgres-plus-graph projection

Detailed explanation. The most common senior answer is a hybrid: Postgres stays the transactional source of truth, and the relationship slice is projected into a graph store for deep reads. Show the sync pattern and the read routing.

• Write path. Application writes to Postgres as normal; transactions and tabular reads unchanged.
• Projection. A CDC stream (or batch ETL) turns relevant inserts/updates into graph nodes and relationships.
• Read routing. Tabular/aggregate reads hit Postgres; deep-traversal reads hit the graph.

Question. Sketch the projection job and the read-routing logic for a social product.

Input.

Concern	Mechanism
source of truth	Postgres users, friendships
projection	CDC → graph upserts
deep reads	friends-of-friends, shortest path → graph
tabular reads	profile, counts, feed → Postgres

Code.

# Projection worker: turn Postgres CDC events into graph upserts.
# (Debezium-style change events; graph driver calls are illustrative.)
def project_event(event, graph):
    table = event["table"]
    op    = event["op"]        # 'c' create, 'u' update, 'd' delete
    row   = event["after"] or event["before"]

    if table == "users":
        graph.run(
            "MERGE (p:Person {id: $id}) SET p.name = $name",
            id=row["id"], name=row.get("name"),
        )
    elif table == "friendships":
        if op == "d":
            graph.run(
                "MATCH (a:Person {id:$a})-[r:KNOWS]->(b:Person {id:$b}) DELETE r",
                a=row["a_id"], b=row["b_id"],
            )
        else:
            graph.run(
                "MATCH (a:Person {id:$a}), (b:Person {id:$b}) "
                "MERGE (a)-[:KNOWS]->(b)",
                a=row["a_id"], b=row["b_id"],
            )

# Read router: send each query to the store that serves it cheapest.
def route_read(query_kind):
    deep = {"friends_of_friends", "shortest_path", "mutual_connections", "reach"}
    return "graph" if query_kind in deep else "postgres"

Step-by-step explanation.

1. Every write still lands in Postgres first — the source of truth, with ACID transactions and all the tabular reads (profiles, feeds, counts) unchanged. Nothing about the write path or the majority of reads moves.
2. A CDC stream (Debezium tailing the WAL, or a periodic ETL) converts relevant changes into graph upserts: a new user becomes a MERGE (p:Person ...), a new friendship becomes a MERGE (a)-[:KNOWS]->(b), a deleted friendship deletes the relationship. MERGE makes the projection idempotent so replays are safe.
3. The read router sends deep-traversal queries — friends-of-friends, shortest path, reachability — to the graph, and everything else to Postgres. Each query runs on the store that serves it cheapest.
4. The consistency model is eventual: the graph lags Postgres by the CDC latency (usually sub-second). For "people you may know" this staleness is invisible; for a query that must be transactionally consistent with a write, route it to Postgres.
5. This hybrid captures most of the graph's traversal win while keeping Postgres's transactional and tabular strengths — at the cost of running a projection pipeline and accepting eventual consistency on the graph side. Naming that cost is what makes the answer senior.

Output.

Query	Routed to	Why
Load profile + friend count	Postgres	tabular, transactional
News feed with aggregates	Postgres	GROUP BY / windows
Friends-of-friends	Graph	deep traversal
Shortest connection path	Graph	pathfinding primitive
Post a new friendship	Postgres (then projected)	source of truth

Rule of thumb. The default senior architecture for a relationship-heavy product is not "graph database" — it is "Postgres source of truth plus a graph projection for the traversal-hot queries." You keep ACID and tabular power, add constant-cost traversal where it matters, and pay only the projection-pipeline and eventual-consistency tax.

Worked example — graph queries inside Postgres with AGE

Detailed explanation. Sometimes you want graph query ergonomics without operating a second database. Apache AGE adds openCypher to Postgres, letting you write graph patterns against data in the same instance. Show what you gain and what you do not.

• What AGE gives you. Cypher syntax (MATCH, variable-length paths) inside Postgres, in the same transaction as your relational tables.
• What it does not give you. True index-free adjacency — AGE stores graph data in Postgres tables, so traversal is still index-backed underneath. You get expressiveness, not the constant-hop physics of a native engine.

Question. Write a variable-length traversal in AGE Cypher and state the honest performance caveat.

Input.

Aspect	Native graph (Neo4j)	Apache AGE (in Postgres)
query language	Cypher	openCypher
storage	native, pointer-linked	Postgres tables
adjacency	index-free (O(1) hop)	index-backed (O(log N) hop)
second system	yes	no

Code.

-- Apache AGE: openCypher embedded in Postgres via the cypher() function.
LOAD 'age';
SET search_path = ag_catalog, "$user", public;

-- Variable-length reachability from person 1, up to 4 hops.
SELECT * FROM cypher('social', $$
    MATCH (me:Person {id: 1})-[:KNOWS*1..4]->(reached:Person)
    RETURN DISTINCT reached.id AS id, reached.name AS name
$$) AS (id agtype, name agtype);

Step-by-step explanation.

1. LOAD 'age' and the cypher('social', $$ ... $$) wrapper let you write openCypher against a graph named social living inside Postgres. The pattern [:KNOWS*1..4] is the same variable-length operator as native Cypher.
2. You keep a single database: the graph and your relational tables share one instance, one backup, one transaction boundary. For teams that cannot justify operating Neo4j, this is a real win.
3. The honest caveat: AGE stores nodes and edges in Postgres tables, so a KNOWS hop is ultimately an index lookup into an edge table — O(log N), not the O(1) pointer dereference of a native engine. You get Cypher's expressiveness but not its adjacency physics.
4. That means AGE shines for readability and moderate-depth traversals where the query is easier to write in Cypher than in a recursive CTE, but it does not deliver the order-of-magnitude deep-traversal speedups a native graph engine does on dense graphs.
5. The decision: AGE (or pgRouting, or ltree for pure hierarchies) when you want graph ergonomics in one system and your depths are moderate; a native engine when deep/dense traversal performance is the actual requirement.

Output.

Choice	Get	Give up
Native graph engine	O(1) hops, pathfinding libs	a second system to operate
Apache AGE	Cypher in one Postgres	index-free adjacency (still O(log N) hops)
Recursive CTE	zero new tooling	expressiveness + deep-traversal speed

Rule of thumb. Apache AGE and friends give you graph query syntax without a second database, but not native adjacency physics. Reach for them when readability and moderate depth are the goal; reach for a native engine only when deep, dense traversal performance is the binding constraint.

System-design interview question on a final store recommendation

A senior interviewer might close with: "Given everything — a product with a transactional core, heavy reporting, a moderately deep org hierarchy, and one genuinely deep-and-cyclic fraud-detection feature — give me your final data-store recommendation and defend where each workload lives. I want to hear you avoid both 'just use Postgres for everything' and 'rewrite it all on a graph database'."

Solution Using a hybrid architecture with per-workload placement

# Final placement: each workload lands where its cost model is cheapest.
placement = {
    "transactions (orders, payments)": "Postgres — ACID, single-store integrity",
    "reporting / dashboards":          "Postgres (or warehouse) — aggregation, GROUP BY",
    "org-chart subtree reads":         "Postgres — recursive CTE or closure table (sparse, batch OK)",
    "fraud-ring detection (3-6 cyclic)":"Graph engine — projected from Postgres via CDC",
}
for workload, store in placement.items():
    print(f"- {workload:34} -> {store}")

Step-by-step trace.

Workload	Depth/shape	Store	Reason
Transactions	tabular, ACID	Postgres	integrity, one store
Reporting	aggregate	Postgres/warehouse	GROUP BY, windows
Org-chart reads	deep but sparse, batch	Postgres	recursive CTE / closure table
Fraud rings	deep, dense, cyclic, real-time	Graph (projected)	worst case for SQL

Walking the final recommendation: the transactional core and reporting stay in Postgres — that is what relational systems are best at, and moving them buys nothing. The org hierarchy, though deep, is sparse and batch-tolerant, so a recursive CTE (or a closure table if reads dominate) keeps it relational. Only the fraud-detection feature — deep, dense, cyclic, and real-time — earns a graph engine, and even then the graph is a projection of the Postgres source of truth via CDC, not a replacement for it. This is the answer that threads between the two failure modes: it neither forces a d^6 cycle search into Postgres nor rewrites a healthy transactional system on a graph database.

Output:

Failure mode avoided	How
"Postgres for everything"	fraud rings moved to a graph engine
"Rewrite on a graph DB"	transactions/reporting/org-chart stay relational
Unbounded blast radius	graph is a projection, not the source of truth
Silent staleness bugs	transactional reads stay on Postgres

Why this works — concept by concept:

• Per-workload placement — the architecture is decided query by query, not database by database. Each workload lands on the store whose cost model fits it, which is the entire lesson of graph vs relational compressed into one design.
• Sparse-but-deep stays relational — the org chart is deep yet sparse, so its recursive CTE never triggers the d^k explosion; depth alone does not justify a graph engine without density.
• Cyclic-and-dense goes graph — the fraud feature is the one workload that scores high on every axis, so it alone justifies the second store and its operational cost.
• Projection, not replacement — the graph is fed from Postgres by CDC, so the relational database remains the source of truth and the blast radius of adopting graph is bounded to one feature.
• Cost — Postgres workloads keep their existing cost profile; the graph feature adds O(frontier) traversal at the price of a projection pipeline and eventual consistency on the graph side. The total cost is one extra pipeline and one extra store scoped to a single feature — the cheapest way to buy constant-cost traversal exactly where the workload demands it, and nowhere it does not.

Design
Topic — design
Store-selection and data-modeling problems

Practice →

Optimization
Topic — optimization
Traversal-cost and query-tuning problems

Practice →

---

Cheat sheet — graph vs relational recipes

• Which model when. Relational wins on shallow fixed-depth joins, aggregation/reporting, transactional single-store integrity, and sparse graphs. A graph database wins on deep or variable-depth traversal, pathfinding (shortest/all/weighted paths), dense many-to-many pattern matching (fraud rings, recommendations), and cyclic queries. Score every hot query on depth, density, variability, and freshness before deciding — most workloads land on relational or hybrid, not pure graph.
• The core physics. A relational join hop is an O(log N) B-tree index probe; a depth-k traversal on average degree d is O(d^k · log N) plus dedup on the materialized intermediate set. A native graph hop is an O(1) pointer dereference (index-free adjacency); a depth-k traversal is O(frontier touched), independent of total node count N. Depth and density are the axes that flip the winner.
• Adjacency-list read template. WITH RECURSIVE t AS (SELECT id, parent_id, 1 AS depth, id::text AS path FROM nodes WHERE id = :root UNION ALL SELECT n.id, n.parent_id, t.depth+1, t.path||' > '||n.id::text FROM nodes n JOIN t ON n.parent_id = t.id) SELECT * FROM t ORDER BY path;. Index the self-referencing key or every recursive round degrades to a seq scan.
• Cycle guard (mandatory on cyclic data). Either carry a path array — ... ARRAY[a_id] AS path ... WHERE NOT n.child = ANY(t.path) — or use the SQL-standard CYCLE b_id SET is_cycle USING cyc_path (Postgres 14+). An unguarded recursive CTE over data that could contain a cycle is an infinite loop waiting for production data.
• BOM / quantity explosion. Accumulate a running product in the recursive term (e.ext * a.qty), add a hard depth guard (e.depth < 12) and a cycle guard, then GROUP BY leaf and filter child NOT IN (SELECT parent ...). In Cypher: MATCH p = (top)-[rels:CONTAINS*1..]->(leaf) WHERE NOT (leaf)-[:CONTAINS]->() WITH leaf, reduce(q=units, r IN rels | q*r.qty) AS ext RETURN leaf.sku, sum(ext);.
• Closure table (read-heavy hierarchies). tree_paths(ancestor, descendant, depth PRIMARY KEY(ancestor,descendant)) materializes every reachable pair; subtree read is one index scan WHERE ancestor = :x. Insert writes one row per ancestor (write amplification O(depth)). Use when reads dominate writes; skip when the tree is reshaped constantly.
• Cypher variable-length + shortest path. (a)-[:KNOWS*1..3]->(b) matches any 1–3 hop path in one clause; shortestPath((a)-[:KNOWS*..6]-(b)) runs a capped bidirectional BFS with early termination; (a)-[:TRANSFER*3..6]->(a) matches a cycle declaratively. These are one-liners that map to multi-line guarded recursive CTEs in SQL.
• friends-of-friends cost. SQL self-join materializes ~d^2 rows then dedups — fine to ~mid hundreds of degree, painful in the influencer tail. Graph two-hop MATCH touches only the reachable frontier. For "people you may know" (staleness-tolerant), a nightly precompute into pymk(user_id, candidate_id, mutuals) turns the read into O(1).
• Decision matrix. Depth 1–2 fixed → relational. Variable depth, sparse, batch → relational recursive CTE. Variable depth, dense, real-time → graph. Cyclic pattern matching → graph (widest win). Aggregation/reporting → relational always. Mixed workload → hybrid.
• Hybrid patterns. (1) Postgres source of truth + graph projection via CDC — writes/tabular reads to Postgres, deep reads to the graph, eventual consistency on the graph side. (2) Apache AGE / pgRouting / ltree — graph query ergonomics inside Postgres, but still O(log N) hops (no native adjacency). (3) Query virtualization (e.g. PuppyGraph) — Cypher/Gremlin over existing relational tables without copying.
• Postgres graph toolbox. WITH RECURSIVE for traversal; CYCLE clause for loop safety; ltree for materialized-path hierarchies; pgRouting for weighted/geospatial pathfinding; Apache AGE for openCypher. Reach for these before adopting a second database when depths are moderate.
• Interview signal checklist. Say "each join hop is an index lookup" (not "joins are slow"); name index-free adjacency for O(1) graph hops; name a concrete depth threshold (~3–4 variable hops on a dense graph); name the hybrid (source-of-truth + projection); name the operational cost of a second store. Hitting all five marks the senior answer.
• Migration cost reality. Adding a graph projection to an existing Postgres app: ~1–2 sprints (CDC/ETL projection + read routing). Rewriting a transactional system onto a graph database: months, and usually the wrong call. Prefer scoping graph to the one or two traversal-hot features; keep the tabular majority relational.

Frequently asked questions

What is the core difference between graph and relational databases?

A relational database stores relationships implicitly — as matching key values that the query planner discovers at run time by probing an index (orders.customer_id = customers.id), so every relationship step costs an O(log N) index lookup. A graph database stores relationships explicitly — as first-class, typed, directed records with physical pointers between adjacent nodes — so traversing a relationship is an O(1) pointer dereference whose cost does not depend on the total size of the graph. That single property, index-free adjacency, is why the graph vs relational question is really a question about traversals: relational is excellent at tabular data, aggregation, and shallow fixed joins, while graph is built for deep, variable-length, and cyclic traversal. The data can be identical; the cost of walking it is what differs.

When does a graph database actually beat SQL recursive joins?

A graph database beats SQL recursive joins when the hot traversal is deep, dense, variable in depth, or cyclic — and especially when several of those hold at once. A recursive CTE costs roughly O(d^k · log N) for depth k on average degree d, materializing and deduplicating a growing intermediate set at each level; a graph traversal costs O(frontier touched) because each hop follows a stored pointer. At fixed depth 1–2 with modest density the two are comparable and one store (relational) usually wins on operational simplicity. The gap opens as depth grows past ~3–4 variable hops on a dense graph, and it is widest for cyclic pattern matching (fraud rings, circular dependencies) where the SQL is long, error-prone, and materializes a d^k candidate space while the Cypher is a one-line pattern.

What is index-free adjacency?

index-free adjacency is the storage property of native graph engines where each node holds direct physical references to its relationship records and adjacent nodes, so following an edge is a pointer dereference rather than a lookup into a global index. The first node in a query is still found via an index, but every hop after that reads neighbours directly — no B-tree probe keyed on the neighbour's id. The complexity consequence is decisive: a relational hop is O(log N) (probe an index of N rows) while a graph hop is O(1) amortized, so a depth-k traversal drops from O(d^k · log N) to O(frontier touched), independent of the total node count. The trade is a small write-time cost to maintain the adjacency pointers, paid once so every future traversal is cheap — which is why graph engines win on read-heavy traversal workloads.

Can Postgres do graph queries without a separate graph database?

Yes, with real caveats. Postgres has WITH RECURSIVE for arbitrary-depth traversal (with a CYCLE clause for loop safety), ltree for materialized-path hierarchies, pgRouting for weighted and geospatial pathfinding, and Apache AGE for openCypher (MATCH, variable-length paths) embedded in the same instance. These cover a large fraction of graph workloads without operating a second database — a genuine win for teams that cannot justify Neo4j. The caveat is that all of them store graph data in relational structures underneath, so a hop is still an O(log N) index lookup, not the O(1) pointer dereference of index-free adjacency. You get graph query expressiveness but not native adjacency physics, which is fine for moderate depths and readability but does not deliver the order-of-magnitude deep-traversal speedups a native engine gives on dense graphs.

Recursive CTE vs graph traversal — which is faster?

It depends entirely on depth and density, which is the honest interview answer. A recursive cte and a graph traversal return the same reachability result, but their cost curves differ: the CTE is O(d^k · log N) and materializes/deduplicates intermediate rows at each level, while the traversal is O(frontier) with constant-cost hops. At shallow depth (1–3) on a sparse graph they are close, and the recursive CTE often wins on total system simplicity because there is no second store to sync. As depth grows, density rises, or the query becomes cyclic, the CTE's d^k term and per-hop index probes compound while the traversal stays proportional to the frontier actually reached — so the graph pulls ahead, sometimes by orders of magnitude. Benchmark on your depth and density rather than trusting a blanket claim; the crossover point is workload-specific.

Is a graph database always the right choice for many-to-many relationships?

No — many-to-many alone does not justify a graph database. A junction table (enrollments(student_id, course_id), friendships(a_id, b_id)) models many-to-many cleanly, supports per-edge attributes, and serves single-hop lookups ("all courses for this student") as one fast indexed scan. The junction table only strains on multi-hop traversal, where self-joining it multiplies the intermediate row count by the degree at each hop (join explosion), and on aggregation-over-relationships at scale. So the deciding factor is not the cardinality of the relationship but the depth of the traversal over it: shallow many-to-many stays comfortably relational; deep or dense multi-hop many-to-many (recommendations, social reach, fraud rings) is where a graph engine — or a graph projection of just that slice — earns its place. Reach for graph when the traversal is deep, not merely because a relationship is many-to-many.

Practice on PipeCode

• Drill the graph practice library → for the traversal, reachability, shortest-path, and cycle-detection problems that separate a fluent graph vs relational answer from a hand-wavy one.
• Rehearse on the joins practice library → for the self-join, junction-table, and recursive cte patterns that are the backbone of relational traversal.
• Pressure-test query plans with the optimization practice library → for the index-lookup-per-hop and join explosion cost analysis interviewers probe.
• Layer in the design practice library → for the store-selection and hybrid-architecture questions where naming the depth threshold and the projection pattern marks the senior answer.
• Stack the prerequisites against PipeCode's broader 450+ data-engineering catalogue to anchor the four-axis decision framework against real graded inputs.

Lock in graph-vs-relational muscle memory

Docs explain the models. PipeCode drills explain the decision — when a recursive CTE is the right call, when the join-per-hop cost explodes, when index-free adjacency makes a graph traversal win, when a hybrid projection beats a full migration. Pipecode.ai is Leetcode for Data Engineering — pattern-first practice tuned for the production trade-offs senior engineers actually face when choosing between a table and a graph.

Practice graph problems →
Practice join problems →