Recursive CTEs

## What is a Recursive CTE?

A Common Table Expression (CTE) is a named query introduced using WITH. A recursive CTE is a CTE that refers to its own name so that it can process data level by level.

Imagine an organization:

- An employee reports to a manager.
- That manager reports to another manager.
- The chain continues until the top-level manager is reached.

A normal query can find an employee's immediate manager. A recursive CTE can follow the reporting relationship to find managers at multiple levels.

Other practical uses include:

- Finding every descendant of a category.
- Traversing folder and directory structures.
- Exploring parent-child relationships.
- Generating a sequence of numbers.
- Exploring graph-like relationships, with appropriate cycle handling.

## The three main parts

A recursive CTE commonly contains:

1. **Anchor query:** Produces the initial row or rows. It does not refer to the recursive CTE itself.
2. **Recursive member:** Refers to the CTE and finds the next set of related rows.
3. **Termination condition:** Determines when no more rows are produced, or otherwise limits traversal.

The recursive member is evaluated repeatedly using rows from the previous iteration. The process ends when an iteration produces no additional rows, assuming the query does not continue generating rows indefinitely.

## Example structure

WITH RECURSIVE hierarchy AS (
-- Anchor query
SELECT ...

UNION ALL

-- Recursive member
SELECT ...
FROM hierarchy
JOIN ...
)
SELECT *
FROM hierarchy;

The keyword RECURSIVE is required by PostgreSQL for this pattern.

Important: Recursive does not mean that SQL calls a function in the same way a programming language might. The database evaluates the anchor and recursive member according to its recursive-query rules.

## A complete working example

The following PostgreSQL example generates numbers from 1 through 5. It is a simple way to understand how a recursive CTE grows one row at a time.

### Step 1: Write the anchor query

SELECT 1 AS n;

This produces the starting row:

n
-
1

### Step 2: Define the recursive member

SELECT n + 1
FROM numbers
WHERE n < 5;

The recursive member reads the previous result and adds one. The condition n < 5 prevents it from generating values greater than 5.

### Step 3: Combine both parts

Use WITH RECURSIVE to name the CTE and UNION ALL to combine the anchor and recursive member.

## Follow the iterations

For the number-generation example, the database conceptually proceeds as follows:

| Iteration | Input to recursive member | New rows |
|---|---|---|
| Anchor | None | 1 |
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 4 |
| 4 | 4 | 5 |
| 5 | 5 | No rows |

The final result contains the anchor row and the rows generated by successful recursive iterations.

PostgreSQL's recursive-query evaluation uses a working set of rows for each iteration. The recursive member processes the current working set to produce the next one.

This distinction matters: the recursive member does not simply execute once against every row already accumulated in the final output. Its iterative behavior follows the recursive CTE evaluation rules.

## Why UNION ALL?

UNION ALL preserves all rows generated by the anchor and recursive member.

UNION removes duplicate rows, which can add deduplication work. Although UNION may help some recursive queries stop producing repeated identical rows, it is not a universal solution to cycles. If each repeated visit has a different depth or path, the complete rows may never be duplicates.

Choose UNION ALL when the query design ensures the correct rows are generated and cycles are controlled where necessary.

## Find everyone reporting under a manager

Suppose a company stores employees in a table named employees. Each employee has an employee_id and may have a manager_id. The manager_id references another employee's employee_id. A NULL manager_id identifies a top-level employee.

### Example table

CREATE TABLE employees (
employee_id INTEGER PRIMARY KEY,
employee_name TEXT NOT NULL,
manager_id INTEGER REFERENCES employees(employee_id)
);

INSERT INTO employees
(employee_id, employee_name, manager_id)
VALUES
(1, 'Asha', NULL),
(2, 'Ravi', 1),
(3, 'Meera', 1),
(4, 'Arjun', 2),
(5, 'Neha', 2),
(6, 'Kabir', 3);

The hierarchy is:

Asha
├── Ravi
│ ├── Arjun
│ └── Neha
└── Meera
└── Kabir

The following query starts with Asha and recursively finds every employee whose manager is already in the hierarchy.

The depth column records how far each employee is from the starting manager. Asha is at depth 0, direct reports are at depth 1, and their reports are at depth 2.

The query also builds a path of employee IDs and avoids following a path that revisits an employee already on that path. This provides cycle protection for the traversal.

## Why termination matters

A recursive query needs a reliable way to stop.

Consider this incorrect pattern:

WITH RECURSIVE numbers(n) AS (
SELECT 1
UNION ALL
SELECT n + 1
FROM numbers
)
SELECT n
FROM numbers;

The recursive member always creates another number. There is no stopping condition, so the query can continue generating rows until a resource limit, cancellation, or another database safeguard intervenes.

Do not run an unbounded recursive query against a production system.

## Use a depth limit

A depth column can limit how far a hierarchy is traversed:

WHERE tree.depth < 10

If the anchor has depth 0, this condition permits recursive rows at depths 1 through 10. Rows at depth 10 do not generate depth 11.

A depth limit is a useful safety measure, but it does not prove that the data is cycle-free. It may also omit valid descendants deeper than the chosen limit.

## Use a natural stopping condition

In number generation, the condition n < 5 stops the sequence at 5.

In a hierarchy, the recursive member naturally stops when no related child rows exist.

For example, an employee with no direct reports produces no new employee rows in the next iteration.

A robust design combines a meaningful relationship condition with a depth limit or cycle protection when appropriate.

## PostgreSQL safeguards

PostgreSQL also supports statement timeouts and query cancellation. These are useful operational safeguards, but they should not replace correct recursive-query logic.

## What is a cycle?

A cycle exists when following relationships eventually returns to a node already visited on the same path.

For example:

Employee 2 reports to Employee 3.
Employee 3 reports to Employee 2.

A recursive traversal can loop through these relationships repeatedly unless it detects the cycle or reaches another termination condition.

A foreign key ensures that a referenced manager exists, but it does not guarantee that the management hierarchy is acyclic.

## Detect a repeated node

In the employee example, path stores the IDs visited along the current path:

ARRAY[employee_id]

The recursive member appends the next ID:

t.path || e.employee_id

Before adding a child, it checks:

NOT (e.employee_id = ANY(t.path))

If the child ID is already in the current path, the query does not follow that edge.

This is path-based cycle detection. It is especially useful when the query must retain a path through a hierarchy.

## Important distinction

Preventing repeated nodes on a single path is not the same as globally deduplicating every node in a graph.

A graph can have multiple legitimate paths to the same node. Whether to return that node once or once per path depends on the question being answered.

For PostgreSQL versions that support the SQL-standard CYCLE clause, recursive CTEs can also use CYCLE to track visited values and mark cycles. Check the database version and syntax documentation before relying on that feature.

## Traverse a category tree

Online stores often organize products into nested categories:

Electronics
├── Computers
│ └── Laptops
└── Phones

A categories table can store each category's parent category:

CREATE TABLE categories (
category_id INTEGER PRIMARY KEY,
category_name TEXT NOT NULL,
parent_id INTEGER REFERENCES categories(category_id)
);

The anchor starts with the selected root category. The recursive member finds its children, then the children of those children.

This pattern can retrieve every descendant beneath a category. It can also return the depth and path needed to display a tree or build a breadcrumb.

As with employee hierarchies, a self-referencing foreign key does not prevent cycles. Apply cycle detection if malformed relationships are possible.

## Index the relationship column

When traversing a hierarchy, the recursive member repeatedly looks for rows whose parent or manager matches the current node.

For a categories table, this index can help:

CREATE INDEX idx_categories_parent_id
ON categories(parent_id);

For employees, consider:

CREATE INDEX idx_employees_manager_id
ON employees(manager_id);

A primary key already indexes the node identifier in PostgreSQL. Indexing the parent relationship can help find children efficiently, but actual benefit depends on table size, selectivity, and the query plan.

## Keep the recursive row narrow

Carry only the columns required for traversal and the final result. Large text values or unnecessary columns can increase the amount of data processed at each iteration.

## Filter at the correct stage

A filter in the anchor determines which starting nodes are included.

A filter in the recursive member determines which new rows may be followed. Filtering out a parent can prevent the traversal from reaching its descendants.

A filter applied only in the outer SELECT may hide rows from the final output without preventing the recursive query from exploring them.

## Use EXPLAIN

Use EXPLAIN to inspect the planned operations:

EXPLAIN
WITH RECURSIVE ...

Use EXPLAIN ANALYZE only when you intend to execute the query and understand its operational impact. On production data, inspect the query carefully before running an expensive recursive query with ANALYZE.

## Understand the data model

A simple parent_id column naturally represents a tree or forest when each node has at most one parent and the data is acyclic.

Graphs with multiple parent relationships require an edge table or another suitable model. In that case, cycle detection and duplicate handling need special attention.

Recursive CTEs are not automatically faster than every alternative. Measure with realistic data and validate the query plan before deployment.

## Mistake 1: Forgetting the stopping condition

Incorrect:

WITH RECURSIVE numbers(n) AS (
SELECT 1
UNION ALL
SELECT n + 1
FROM numbers
)
SELECT n FROM numbers;

Why it is wrong: The recursive member never stops generating new numbers.

Better:

WITH RECURSIVE numbers(n) AS (
SELECT 1
UNION ALL
SELECT n + 1
FROM numbers
WHERE n < 5
)
SELECT n FROM numbers;

## Mistake 2: Joining the wrong columns

Incorrect:

JOIN employees AS e
ON e.employee_id = tree.employee_id

This matches the same employee identifier and does not find the employee's direct reports.

Better:

JOIN employees AS e
ON e.manager_id = tree.employee_id

The child employee's manager_id must match the current employee's employee_id.

## Mistake 3: Assuming a foreign key prevents cycles

A self-referencing foreign key prevents references to nonexistent employees. It does not prevent two employees from referring to each other.

Use cycle-aware traversal and validate hierarchy updates when acyclic data is required.

## Mistake 4: Assuming UNION always solves recursion

UNION removes duplicate complete rows. If a row contains a changing depth or path, a repeated node may still produce a different row on every iteration.

Use explicit cycle detection when node revisits must be prevented.

## Mistake 5: Using an arbitrary depth limit without explaining it

A depth limit is a safety boundary, not proof that the hierarchy is complete.

Choose the limit based on valid business requirements and decide how deeper rows should be handled.

## Mistake 6: Assuming result order is guaranteed

Recursive evaluation order is not a presentation guarantee. Add an explicit ORDER BY to control the final result.

Complete these exercises using PostgreSQL.

### Exercise 1: Number sequence

Write a recursive CTE that returns the numbers 1 through 10.

Requirements:
- Start at 1.
- Add 1 during each recursive iteration.
- Stop at 10.

### Exercise 2: Direct and indirect reports

Using the employees table from this lesson, return all employees who report directly or indirectly to employee 2.

Requirements:
- Start with employee 2.
- Include employee 2 in the result.
- Include a depth column.
- Avoid revisiting employees along the same path.

### Exercise 3: Category descendants

Using the categories table, return every descendant of category 1.

Requirements:
- Include category names and depth.
- Sort the result in a hierarchy-friendly order.
- Consider how to prevent cycles.

### Exercise 4: Maximum depth

Modify a hierarchy query to return no descendants beyond depth 3.

Explain whether the root should have depth 0 or depth 1, and make your condition consistent with that choice.

### Exercise 5: Diagnose a cycle

Suppose employee 7 manages employee 8 and employee 8 manages employee 7.

Explain why a foreign key does not make this relationship safe for recursive traversal. Add cycle protection to the query.

### Exercise 6: Performance

Identify the relationship column used by your recursive join. Propose an index and explain how EXPLAIN can help evaluate whether it is useful.

Do not assume an index is beneficial without considering the query plan and data size.

### Question 1

Which part of a recursive CTE provides the initial rows?

A. Recursive member
B. Anchor query
C. ORDER BY
D. Outer SELECT

**Answer:** B. The anchor query provides the initial rows.

### Question 2

What does UNION ALL do in a recursive CTE?

A. Automatically prevents all cycles
B. Combines rows without removing duplicates
C. Sorts rows by hierarchy depth
D. Creates an index

**Answer:** B. UNION ALL preserves duplicates rather than performing duplicate elimination.

### Question 3

In an employee hierarchy, which join finds direct reports of the current employee?

A. e.employee_id = tree.employee_id
B. e.manager_id = tree.employee_id
C. e.manager_id = NULL
D. e.employee_name = tree.manager_id

**Answer:** B. The child's manager_id matches the current employee's employee_id.

### Question 4

Why is a depth limit useful?

A. It guarantees that every row is unique
B. It prevents traversal beyond a specified level
C. It automatically indexes the hierarchy
D. It removes all NULL values

**Answer:** B. A depth limit restricts how far the query can traverse.

### Question 5

Why does UNION not always prevent cycles?

A. UNION cannot be used in a CTE
B. UNION sorts only text values
C. A revisited node can produce a different complete row when depth or path changes
D. UNION always returns NULL

**Answer:** C. Duplicate elimination applies to complete rows, not just a selected node identifier.

### Question 6

Does a self-referencing foreign key guarantee an acyclic hierarchy?

A. Yes, always
B. No, it validates references but does not generally prohibit cycles
C. Only if the table has a text primary key
D. Only when UNION is used

**Answer:** B. Cycle prevention requires additional logic or data-model constraints.

### Question 7

What is the purpose of ORDER BY in the final SELECT?

A. It terminates recursion
B. It determines the anchor rows
C. It specifies the presentation order of the result
D. It prevents invalid foreign keys

**Answer:** C. Explicit ordering controls the returned result order.

### 1. What is a recursive CTE?

A recursive CTE is a named query that refers to itself to process related data iteratively. It is commonly used for hierarchical relationships such as employee reporting structures and nested categories.

### 2. What are the anchor query and recursive member?

The anchor query supplies the starting rows. The recursive member uses rows from the current recursive working set to produce the next level.

### 3. Why is WITH RECURSIVE used?

In PostgreSQL, WITH RECURSIVE declares a CTE that can refer to itself. Ordinary WITH CTEs are not recursive.

### 4. What happens when the recursive member returns no rows?

The recursion finishes because there are no more rows to add through subsequent iterations.

### 5. Why is UNION ALL commonly used?

It combines the anchor and recursive results without duplicate elimination, avoiding the extra duplicate-removal work associated with UNION. It requires the query design to handle duplicates and cycles appropriately.

### 6. How can you prevent infinite recursion?

Use a meaningful stopping condition, track depth when appropriate, and detect cycles when relationships may revisit previously visited nodes. Operational limits and query cancellation provide additional safeguards.

### 7. Does a foreign key prevent cycles in a hierarchy?

No. A foreign key ensures that referenced rows exist, but it does not generally prohibit circular relationships between existing rows.

### 8. What is the difference between depth limiting and cycle detection?

A depth limit stops traversal beyond a chosen level. Cycle detection prevents revisiting a node along a path. They solve different problems and may be used together.

### 9. Can recursive CTEs be used for graphs?

Yes, but graph traversal needs deliberate handling of cycles, duplicate paths, and whether a node should appear once or once per path.

### 10. How do you improve recursive-query performance?

Index relationship columns where useful, carry only necessary columns, restrict traversal appropriately, inspect the plan with EXPLAIN, and test against representative data.

### 11. Does a recursive CTE guarantee a particular row order?

No. Specify ORDER BY in the final query to define result ordering.

### 12. What is a common use case for recursive CTEs in backend development?

A backend can use a recursive CTE to retrieve a category subtree, an employee's reporting chain, or nested folder contents in a single database query, subject to the application's authorization and data-model requirements.

You have learned how recursive CTEs traverse hierarchical relationships in PostgreSQL.

Remember these principles:

- WITH RECURSIVE declares a recursive CTE.
- The anchor query produces the starting rows.
- The recursive member produces the next level.
- UNION ALL combines rows without duplicate elimination.
- A meaningful termination condition is essential.
- Depth limits restrict traversal depth but do not independently prove that data is cycle-free.
- Path-based cycle detection helps prevent revisiting nodes along a traversal path.
- Parent-child joins must match the correct relationship columns.
- Indexes, explicit ordering, EXPLAIN, and realistic testing support reliable production queries.

Before moving on, make sure you can write a recursive number sequence, traverse an employee hierarchy, explain a cycle, and distinguish a depth limit from cycle detection.