Recursive CTE for graph traversal in PostgreSQL

Introduction

Recursive CTEs help you explore connected data step-by-step, like finding all friends of a friend in a network.

Finding all connected nodes in a network, like friends in a social media graph.

Tracing paths in a family tree to find ancestors or descendants.

Exploring dependencies between tasks or projects.

Finding all reachable locations from a starting point on a map.

Analyzing organizational charts to find all subordinates under a manager.

Syntax

PostgreSQL

WITH RECURSIVE cte_name(column_list) AS (
    -- Anchor member: starting point of recursion
    SELECT initial_columns
    FROM table_name
    WHERE condition
  
    UNION ALL
  
    -- Recursive member: references cte_name to find connected rows
    SELECT next_columns
    FROM table_name
    JOIN cte_name ON join_condition
    WHERE recursive_condition
)
SELECT * FROM cte_name;

The anchor member is the base query that starts the recursion.

The recursive member references the CTE itself to find connected rows.

Examples

Finds all friends and friends of friends starting from user 1, avoiding cycles back to user 1.

PostgreSQL

WITH RECURSIVE friends_cte(friend_id) AS (
  SELECT friend_id FROM friendships WHERE user_id = 1
  UNION ALL
  SELECT f.friend_id FROM friendships f
  JOIN friends_cte fc ON f.user_id = fc.friend_id
  WHERE f.friend_id != 1
)
SELECT * FROM friends_cte;

Finds all ancestors of person with id 5 by recursively joining on parent_id.

PostgreSQL

WITH RECURSIVE ancestors_cte(id, parent_id) AS (
  SELECT id, parent_id FROM family WHERE id = 5
  UNION ALL
  SELECT f.id, f.parent_id FROM family f
  JOIN ancestors_cte a ON f.parent_id = a.id
)
SELECT * FROM ancestors_cte;

Sample Program

This query finds all nodes you can reach starting from node 1 by following edges step-by-step.

PostgreSQL

CREATE TABLE edges (
  from_node INT,
  to_node INT
);

INSERT INTO edges VALUES
  (1, 2),
  (1, 3),
  (2, 4),
  (3, 5),
  (5, 6);

-- Find all nodes reachable from node 1
WITH RECURSIVE reachable_nodes(node) AS (
  -- Start from node 1
  SELECT 1 AS node
  UNION
  -- Find nodes connected to already found nodes
  SELECT e.to_node FROM edges e
  JOIN reachable_nodes r ON e.from_node = r.node
)
SELECT DISTINCT node FROM reachable_nodes ORDER BY node;

Important Notes

Time complexity depends on the number of edges and nodes; it can be expensive for large graphs.

Space complexity grows with the number of reachable nodes stored during recursion.

Common mistake: forgetting to include a stopping condition or DISTINCT, which can cause infinite loops or duplicates.

Use recursive CTEs when you need to explore hierarchical or connected data stepwise; for simple joins, recursion is not needed.

Summary

Recursive CTEs let you explore connected data step-by-step.

They have an anchor part and a recursive part that references itself.

Useful for graphs, trees, and hierarchical data traversal.