Recursive CTE for graph traversal in PostgreSQL - Step-by-Step Execution

Concept Flow - Recursive CTE for graph traversal

Start with base nodes

↓

Recursive step: find neighbors

↓

Add new nodes to result

↓

Check if new nodes found

↓

Repeat recursion

Start with initial nodes, then repeatedly find connected neighbors until no new nodes are found.

Execution Sample

PostgreSQL

WITH RECURSIVE traverse AS (
  SELECT source, target, 1 AS depth
  FROM edges
  WHERE source = 1
  UNION
  SELECT e.source, e.target, t.depth + 1
  FROM edges e
  JOIN traverse t ON e.source = t.target
  WHERE t.depth < 3
)
SELECT * FROM traverse;

This query finds nodes reachable from node 1 up to 3 steps away using a recursive CTE.

Execution Table

Step	Action	New Rows Added	Current Result Set (source->target, depth)	Termination Check
1	Initialize base case: select edges where source=1	Edges (1->2), (1->3)	(1->2, 1), (1->3, 1)	New rows found, continue
2	Recursive step: find edges where source matches previous target	Edges (2->4), (3->5)	(1->2, 1), (1->3, 1), (2->4, 2), (3->5, 2)	New rows found, continue
3	Recursive step: find edges where source matches previous target	Edges (4->6), (5->6)	(1->2, 1), (1->3, 1), (2->4, 2), (3->5, 2), (4->6, 3), (5->6, 3)	Depth limit reached (3), stop recursion
4	No further recursion	No new rows	(1->2, 1), (1->3, 1), (2->4, 2), (3->5, 2), (4->6, 3), (5->6, 3)	No new rows, recursion ends

💡 Recursion stops because depth limit 3 is reached and no new rows are found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
depth	N/A	1	2	3	3
result_set_count	0	2	4	6	6
new_rows_count	0	2	2	2	0

Key Moments - 3 Insights

Why does the recursion stop even though some nodes might still connect further?

Because the query limits recursion depth to 3 (see execution_table row 3), so it stops after reaching that depth.

How does the recursive part avoid infinite loops in cyclic graphs?

The recursion stops when no new rows are added (execution_table row 4), preventing infinite loops by not revisiting already found nodes.

Why do we join edges on e.source = t.target in the recursive step?

Because we want to find edges starting from nodes found in the previous step (t.target), extending the path forward.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, how many new rows are added?

A 2

B 3

C 4

D 1

💡 Hint

Check the 'New Rows Added' column for Step 2 in the execution_table.

At which step does the recursion stop due to reaching the depth limit?

A Step 1

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'Termination Check' column describing depth limit in execution_table.

If the depth limit was removed, what would happen to the 'new_rows_count' after Step 3?

A It would decrease to zero immediately

B It would stay zero

C It would increase if more edges exist

D It would cause an error

💡 Hint

Refer to variable_tracker for 'new_rows_count' and understand recursion behavior without depth limit.

Concept Snapshot

WITH RECURSIVE cte_name AS (
  -- Base case: select starting nodes
  SELECT ...
  UNION
  -- Recursive step: join cte with edges to find neighbors
  SELECT ... FROM edges JOIN cte_name ON ...
  WHERE depth < max_depth
)
SELECT * FROM cte_name;

Use recursive CTEs to traverse graphs step-by-step, stopping when no new nodes or depth limit reached.

Full Transcript

Recursive Common Table Expressions (CTEs) in PostgreSQL allow you to traverse graphs by starting from base nodes and repeatedly finding connected neighbors. The process begins by selecting initial edges from a starting node. Then, the recursive part joins the current results with the edges table to find new connected nodes, increasing the depth each time. This repeats until no new nodes are found or a depth limit is reached, preventing infinite loops. The execution table shows each step adding new rows representing edges found at increasing depths. Variables like depth and counts of new rows track progress. Key points include understanding why recursion stops (depth limit or no new rows) and how the join condition extends the traversal. This method is powerful for exploring hierarchical or network data in SQL.