Recursive CTE for hierarchical data in SQL - Deep Dive

Overview - Recursive CTE for hierarchical data

What is it?

A Recursive Common Table Expression (CTE) is a special SQL query that calls itself to process hierarchical or tree-like data. It helps you find all levels of related data, like employees and their managers, or categories and subcategories. This lets you explore data that is connected in parent-child relationships easily. Recursive CTEs run repeatedly until they reach the bottom of the hierarchy.

Why it matters

Without recursive CTEs, querying hierarchical data would be very complex and inefficient, often requiring many separate queries or complicated loops outside the database. This would slow down applications and make data harder to understand. Recursive CTEs solve this by letting the database handle the hierarchy naturally and quickly, improving performance and simplifying code.

Where it fits

Before learning recursive CTEs, you should understand basic SQL queries, joins, and simple CTEs (non-recursive). After mastering recursive CTEs, you can explore advanced hierarchical queries, graph databases, and recursive algorithms in programming.

Mental Model

Core Idea

A recursive CTE repeatedly queries data, starting from a base case and then joining results back to itself to walk through all levels of a hierarchy.

Think of it like...

Imagine a family tree where you start with one person and then look for their children, then their grandchildren, and so on, step by step, until you reach the youngest generation.

┌───────────────┐
│ Base Query    │  -- Finds the root or starting nodes
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Recursive Part│  -- Finds children of nodes found so far
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Repeat Until  │  -- Stops when no new children found
│ no new rows   │
└───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Hierarchical Data

Concept: Hierarchical data is data organized in parent-child relationships, like a company org chart or folder structure.

Think of a company where each employee has a manager. The manager is the parent, and the employee is the child. This creates a tree where you can start from the CEO (top parent) and find all employees below them.

Result

You see how data can be connected in layers or levels, not just flat rows.

Understanding the shape of hierarchical data is key to knowing why special queries like recursive CTEs are needed.

2

Foundation

Basics of Common Table Expressions (CTEs)

Concept: CTEs are temporary named result sets you can reference within a query to organize complex SQL.

A simple CTE looks like this: WITH cte_name AS ( SELECT * FROM table WHERE condition ) SELECT * FROM cte_name; It helps break down queries into readable parts.

Result

You can write clearer queries by naming intermediate results.

Knowing CTEs prepares you to understand recursive CTEs, which build on this idea by calling themselves.

3

Intermediate

Structure of a Recursive CTE

🤔Before reading on: do you think a recursive CTE runs its query once or multiple times? Commit to your answer.

Concept: A recursive CTE has two parts: an anchor member (base case) and a recursive member that references the CTE itself.

Syntax example: WITH RECURSIVE cte_name AS ( -- Anchor member: starting point SELECT id, parent_id, name FROM table WHERE parent_id IS NULL UNION ALL -- Recursive member: find children SELECT t.id, t.parent_id, t.name FROM table t JOIN cte_name c ON t.parent_id = c.id ) SELECT * FROM cte_name; The anchor runs first, then the recursive part runs repeatedly, adding more rows each time.

Result

The query returns all rows connected in the hierarchy starting from the root.

Understanding the two-part structure is essential to writing and debugging recursive queries.

4

Intermediate

Using Recursive CTEs to Traverse Trees

🤔Before reading on: do you think recursive CTEs can find all descendants or only direct children? Commit to your answer.

Concept: Recursive CTEs can find all descendants by repeatedly joining child rows to their parents until no more children exist.

Example: Find all employees under a manager: WITH RECURSIVE subordinates AS ( SELECT id, name FROM employees WHERE id = 1 -- manager UNION ALL SELECT e.id, e.name FROM employees e JOIN subordinates s ON e.manager_id = s.id ) SELECT * FROM subordinates; This returns the manager and all employees below them at any level.

Result

You get a full list of all related rows in the hierarchy, not just immediate children.

Knowing recursive CTEs explore all levels helps you solve complex hierarchical queries efficiently.

5

Intermediate

Controlling Recursion Depth and Cycles

🤔Before reading on: do you think recursive CTEs automatically stop if there is a cycle? Commit to your answer.

Concept: Recursive CTEs can include conditions to limit depth and prevent infinite loops caused by cycles in data.

Add a level counter: WITH RECURSIVE cte AS ( SELECT id, parent_id, 1 AS level FROM table WHERE parent_id IS NULL UNION ALL SELECT t.id, t.parent_id, c.level + 1 FROM table t JOIN cte c ON t.parent_id = c.id WHERE c.level < 10 -- limit depth ) SELECT * FROM cte; To avoid cycles, track visited nodes or use database-specific cycle detection features.

Result

The query stops after a set depth or when no new rows are found, preventing infinite loops.

Understanding recursion limits is critical to writing safe queries on real-world data that may have errors.

6

Advanced

Performance Considerations and Indexing

🤔Before reading on: do you think recursive CTEs are always fast regardless of data size? Commit to your answer.

Concept: Recursive CTEs can be slow on large datasets without proper indexing and query design.

Indexes on the parent_id column speed up joins in recursion. Also, filtering early in the anchor or recursive parts reduces rows processed. Some databases optimize recursive CTEs better than others.

Result

Well-indexed recursive queries run faster and use fewer resources.

Knowing how to optimize recursive queries prevents performance bottlenecks in production.

7

Expert

Advanced Uses and Surprises in Recursive CTEs

🤔Before reading on: do you think recursive CTEs can be used for graph traversal beyond trees? Commit to your answer.

Concept: Recursive CTEs can traverse graphs with cycles, find shortest paths, and solve complex problems beyond simple hierarchies, but require careful cycle handling.

Example: Finding shortest path using recursive CTE with cycle detection: WITH RECURSIVE paths AS ( SELECT start_node, end_node, ARRAY[start_node] AS path FROM edges WHERE start_node = 'A' UNION ALL SELECT p.start_node, e.end_node, path || e.end_node FROM paths p JOIN edges e ON p.end_node = e.start_node WHERE NOT e.end_node = ANY(path) -- avoid cycles ) SELECT * FROM paths WHERE end_node = 'Z' ORDER BY array_length(path, 1) LIMIT 1; This finds shortest path from A to Z avoiding loops.

Result

Recursive CTEs can solve complex graph problems, not just simple trees.

Understanding recursive CTEs as graph traversal tools opens advanced data analysis possibilities.

Under the Hood

Recursive CTEs work by first executing the anchor query to get the base rows. Then, the recursive query runs repeatedly, each time joining new rows to the previous result set. This loop continues until no new rows are added. Internally, the database manages a temporary working table that grows with each iteration. The recursion is controlled by the UNION ALL operator and stops when the recursive part returns zero rows.

Why designed this way?

Recursive CTEs were designed to express hierarchical queries declaratively within SQL, avoiding procedural loops outside the database. This design leverages set-based operations and allows databases to optimize recursion internally. Alternatives like procedural code or multiple queries were less efficient and harder to maintain. The recursive CTE syntax balances power and readability.

┌───────────────┐
│ Anchor Query  │
│ (Base rows)   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Recursive     │
│ Query         │
│ (Joins to     │
│ previous rows)│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Accumulate    │
│ Results       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Stop when no  │
│ new rows      │
│ added        │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do recursive CTEs automatically detect and stop cycles in data? Commit yes or no.

Common Belief: Recursive CTEs automatically prevent infinite loops caused by cycles in hierarchical data.

Reality: Recursive CTEs do not automatically detect cycles; if the data has loops, the query can run infinitely or until the database stops it.

Why it matters: Without cycle detection, recursive queries can hang or crash the database, causing downtime or data loss.

Quick: Do recursive CTEs always return results in hierarchical order? Commit yes or no.

Common Belief: Recursive CTEs return rows in the order of the hierarchy levels by default.

Reality: Recursive CTEs return rows in the order they are found, which may not be sorted by hierarchy level unless explicitly ordered.

Why it matters: Assuming order can lead to incorrect reports or UI displays if sorting is not applied.

Quick: Can recursive CTEs only be used for trees, not graphs? Commit yes or no.

Common Belief: Recursive CTEs are only useful for strict tree hierarchies without cycles.

Reality: Recursive CTEs can traverse graphs with cycles if cycle detection logic is added.

Why it matters: Limiting recursive CTEs to trees restricts their powerful applications in network analysis and graph problems.

Quick: Do recursive CTEs always perform well on large datasets? Commit yes or no.

Common Belief: Recursive CTEs are efficient and fast regardless of data size.

Reality: Recursive CTEs can be slow and resource-intensive on large or deep hierarchies without proper indexing and query tuning.

Why it matters: Ignoring performance can cause slow applications and high database load.

Expert Zone

1

Recursive CTEs can be combined with window functions to calculate running totals or ranks within hierarchical levels.

2

Some databases optimize recursive CTEs differently; understanding your DBMS's execution plan can reveal hidden performance traps.

3

Recursive CTEs can be used to simulate procedural loops inside SQL, enabling complex iterative algorithms without external code.

When NOT to use

Avoid recursive CTEs when dealing with extremely large graphs or hierarchies where specialized graph databases or procedural code with caching perform better. Also, if your data has many cycles and complex relationships, graph query languages like Cypher or Gremlin may be more suitable.

Production Patterns

In production, recursive CTEs are used for organizational charts, bill of materials, folder structures, and permission hierarchies. They are often combined with caching layers or materialized views to improve performance. Recursive CTEs also appear in data migration scripts and reporting tools that need full hierarchy expansion.

Connections

Graph Theory

Recursive CTEs implement graph traversal algorithms like depth-first or breadth-first search within SQL.

Understanding graph theory helps optimize recursive queries and apply them beyond simple hierarchies to complex networks.

Functional Programming Recursion

Recursive CTEs mirror the concept of recursion in programming, where a function calls itself to solve smaller parts of a problem.

Knowing recursion in programming clarifies how recursive CTEs build results step-by-step by self-reference.

Organizational Behavior

Hierarchical data in databases often models real-world organizational structures and reporting lines.

Understanding how organizations are structured helps design better hierarchical queries and interpret their results meaningfully.

Common Pitfalls

#1 Infinite recursion due to cycles in data.

Wrong approach:

WITH RECURSIVE cte AS (
SELECT id, parent_id FROM table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id FROM table t
JOIN cte c ON t.parent_id = c.id
)
SELECT * FROM cte;

Correct approach:

WITH RECURSIVE cte AS (
SELECT id, parent_id, ARRAY[id] AS path FROM table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id, path || t.id FROM table t
JOIN cte c ON t.parent_id = c.id
WHERE NOT t.id = ANY(path)
)
SELECT * FROM cte;

Root cause:

Not tracking visited nodes allows the query to revisit the same rows endlessly.

#2 Assuming recursive CTE results are ordered by hierarchy level without ORDER BY.

Wrong approach:

WITH RECURSIVE cte AS (
SELECT id, parent_id FROM table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id FROM table t
JOIN cte c ON t.parent_id = c.id
)
SELECT * FROM cte;

Correct approach:

WITH RECURSIVE cte AS (
SELECT id, parent_id, 1 AS level FROM table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id, c.level + 1 FROM table t
JOIN cte c ON t.parent_id = c.id
)
SELECT * FROM cte ORDER BY level;

Root cause:

SQL does not guarantee order without explicit ORDER BY.

#3 Using recursive CTE on very large data without indexes.

Wrong approach:

WITH RECURSIVE cte AS (
SELECT id, parent_id FROM large_table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id FROM large_table t
JOIN cte c ON t.parent_id = c.id
)
SELECT * FROM cte;

Correct approach:

CREATE INDEX idx_parent_id ON large_table(parent_id);

WITH RECURSIVE cte AS (
SELECT id, parent_id FROM large_table WHERE parent_id IS NULL
UNION ALL
SELECT t.id, t.parent_id FROM large_table t
JOIN cte c ON t.parent_id = c.id
)
SELECT * FROM cte;

Root cause:

Missing indexes cause slow join operations in recursion.

Key Takeaways

Recursive CTEs let you query hierarchical data by repeatedly joining rows to their parents or children until the full tree is explored.

They consist of an anchor part that starts the recursion and a recursive part that references the CTE itself to find related rows.

Without cycle detection, recursive CTEs can run infinitely if the data contains loops, so always guard against cycles.

Performance depends heavily on indexing and query design; recursive CTEs are powerful but can be slow on large or deep hierarchies.

Beyond trees, recursive CTEs can traverse graphs and solve complex problems when combined with cycle detection and path tracking.

Practice

1. What is the main purpose of a RECURSIVE CTE in SQL when working with hierarchical data?

easy

A. To speed up simple SELECT queries without joins

B. To repeatedly query connected rows to explore hierarchical relationships

C. To create temporary tables for storing unrelated data

D. To update multiple tables at once

Solution

1. Step 1: Understand the role of recursive CTEs

   Recursive CTEs allow querying hierarchical or connected data by repeatedly joining rows to find related entries.

2. Step 2: Compare options with this purpose

   Only To repeatedly query connected rows to explore hierarchical relationships describes this repeated querying of connected rows to explore hierarchies.

3. Final Answer:

   To repeatedly query connected rows to explore hierarchical relationships -> Option B

4. Quick Check:

   Recursive CTE = repeated connected row queries [OK]

Hint: Recursive CTEs repeatedly join related rows to explore hierarchies [OK]

Common Mistakes:

• Confusing recursive CTEs with simple temporary tables
• Thinking recursive CTEs speed up unrelated queries
• Assuming recursive CTEs update data

2. Which of the following is the correct syntax to start a recursive CTE named OrgChart in SQL?

easy

A. DECLARE RECURSIVE OrgChart BEGIN ... END

B. CREATE RECURSIVE TABLE OrgChart AS ( ... )

C. SELECT RECURSIVE OrgChart FROM ...

D. WITH RECURSIVE OrgChart AS ( ... )

Solution

1. Step 1: Recall recursive CTE syntax

   The correct way to start a recursive CTE is using WITH RECURSIVE Name AS ( ... ).

2. Step 2: Check each option

   WITH RECURSIVE OrgChart AS ( ... ) matches the correct syntax. Options A, B, and C use invalid or unrelated SQL commands.

3. Final Answer:

   WITH RECURSIVE OrgChart AS ( ... ) -> Option D

4. Quick Check:

   Recursive CTE starts with WITH RECURSIVE [OK]

Hint: Recursive CTE always starts with WITH RECURSIVE [OK]

Common Mistakes:

• Using CREATE instead of WITH for CTEs
• Trying to SELECT RECURSIVE directly
• Using DECLARE which is for procedural code

3. Given the table Employees(id, name, manager_id) where manager_id references id, what will the following query return?

WITH RECURSIVE Subordinates AS (
  SELECT id, name, manager_id FROM Employees WHERE id = 2
  UNION ALL
  SELECT e.id, e.name, e.manager_id FROM Employees e
  JOIN Subordinates s ON e.manager_id = s.id
)
SELECT * FROM Subordinates;

medium

A. All employees who report directly or indirectly to employee with id 2

B. Only the employee with id 2

C. All employees who have no manager

D. All employees in the company

Solution

1. Step 1: Analyze the base query

   The base query selects the employee with id = 2.

2. Step 2: Analyze the recursive part

   The recursive part joins employees whose manager_id matches any id found so far, thus finding all subordinates under employee 2.

3. Final Answer:

   All employees who report directly or indirectly to employee with id 2 -> Option A

4. Quick Check:

   Recursive join finds all subordinates [OK]

Hint: Recursive CTE with join on manager_id finds all subordinates [OK]

Common Mistakes:

• Thinking it returns only the base employee
• Assuming it returns employees without managers
• Believing it returns all employees regardless

4. Identify the error in this recursive CTE that tries to list all descendants of a node in a tree:

WITH RECURSIVE Descendants AS (
  SELECT id, parent_id FROM Tree WHERE id = 1
  UNION ALL
  SELECT t.id, t.parent_id FROM Tree t
  JOIN Descendants d ON t.id = d.parent_id
)
SELECT * FROM Descendants;

medium

A. The JOIN condition should be ON t.parent_id = d.id, not t.id = d.parent_id

B. The base query should select from Descendants, not Tree

C. Recursive CTEs cannot use JOINs

D. The recursive part should use UNION, not UNION ALL

Solution

1. Step 1: Understand the tree relationship

   Each node's parent_id points to its parent. To find descendants, join where child's parent_id equals parent's id.

2. Step 2: Check the JOIN condition

   The query incorrectly joins on t.id = d.parent_id. It should be t.parent_id = d.id to find children of current nodes.

3. Final Answer:

   The JOIN condition should be ON t.parent_id = d.id, not t.id = d.parent_id -> Option A

4. Quick Check:

   Join child parent_id to parent id [OK]

Hint: Join child's parent_id to parent's id to find descendants [OK]

Common Mistakes:

• Reversing join condition columns
• Using base query from recursive CTE itself
• Thinking recursive CTEs can't use JOIN
• Confusing UNION and UNION ALL usage

5. You have a parts list table Parts(id, name, parent_part_id) representing assemblies and subassemblies. Write a recursive CTE query to find the full hierarchy of parts under part with id = 10, including the root part itself, and show the level (depth) of each part in the hierarchy starting at 0 for the root. Which query is correct?

hard

A. WITH RECURSIVE PartHierarchy AS (
SELECT id, name, parent_part_id FROM Parts WHERE parent_part_id IS NULL
UNION ALL
SELECT p.id, p.name, p.parent_part_id FROM Parts p
JOIN PartHierarchy ph ON p.id = ph.parent_part_id
)
SELECT * FROM PartHierarchy WHERE id = 10;

B. WITH RECURSIVE PartHierarchy AS (
SELECT id, name, parent_part_id, 1 AS level FROM Parts WHERE id = 10
UNION ALL
SELECT p.id, p.name, p.parent_part_id, ph.level - 1 FROM Parts p
JOIN PartHierarchy ph ON p.id = ph.parent_part_id
)
SELECT * FROM PartHierarchy;

C. WITH RECURSIVE PartHierarchy AS (
SELECT id, name, parent_part_id, 0 AS level FROM Parts WHERE id = 10
UNION ALL
SELECT p.id, p.name, p.parent_part_id, ph.level + 1 FROM Parts p
JOIN PartHierarchy ph ON p.parent_part_id = ph.id
)
SELECT * FROM PartHierarchy;

D. WITH RECURSIVE PartHierarchy AS (
SELECT id, name, parent_part_id, 0 AS level FROM Parts WHERE id = 10
UNION ALL
SELECT p.id, p.name, p.parent_part_id, ph.level + 1 FROM Parts p
JOIN PartHierarchy ph ON p.id = ph.parent_part_id
)
SELECT * FROM PartHierarchy;

Solution

1. Step 1: Identify the base case and level

   The base query selects the root part with id=10 and sets level to 0.

2. Step 2: Check the recursive join and level increment

   The recursive part joins parts where parent_part_id matches current part's id, and increments level by 1 to track depth.

3. Step 3: Verify options

   WITH RECURSIVE PartHierarchy AS ( SELECT id, name, parent_part_id, 0 AS level FROM Parts WHERE id = 10 UNION ALL SELECT p.id, p.name, p.parent_part_id, ph.level + 1 FROM Parts p JOIN PartHierarchy ph ON p.parent_part_id = ph.id ) SELECT * FROM PartHierarchy; correctly implements this logic. WITH RECURSIVE PartHierarchy AS ( SELECT id, name, parent_part_id, 1 AS level FROM Parts WHERE id = 10 UNION ALL SELECT p.id, p.name, p.parent_part_id, ph.level - 1 FROM Parts p JOIN PartHierarchy ph ON p.id = ph.parent_part_id ) SELECT * FROM PartHierarchy; has wrong join direction and decrements level. WITH RECURSIVE PartHierarchy AS ( SELECT id, name, parent_part_id FROM Parts WHERE parent_part_id IS NULL UNION ALL SELECT p.id, p.name, p.parent_part_id FROM Parts p JOIN PartHierarchy ph ON p.id = ph.parent_part_id ) SELECT * FROM PartHierarchy WHERE id = 10; starts from root parts but filters later, missing the correct root. WITH RECURSIVE PartHierarchy AS ( SELECT id, name, parent_part_id, 0 AS level FROM Parts WHERE id = 10 UNION ALL SELECT p.id, p.name, p.parent_part_id, ph.level + 1 FROM Parts p JOIN PartHierarchy ph ON p.id = ph.parent_part_id ) SELECT * FROM PartHierarchy; has wrong join direction.

4. Final Answer:

   The query with base WHERE id=10, level 0, JOIN p.parent_part_id=ph.id, level+1 -> Option C

5. Quick Check:

   Join on child.parent_part_id = parent.id, level + 1 [OK]

Hint: Join child.parent_part_id = parent.id and increment level [OK]

Common Mistakes:

• Reversing join condition (parent to child)
• Starting level at 1 or decrementing level
• Filtering after recursion instead of base case
• Using wrong root selection