Recursive Query Execution Patterns

You will design recursive queries that balance depth-first and breadth-first search requirements.

In this lesson, you will learn how to control the order in which PostgreSQL traverses hierarchical data by implementing depth-first and breadth-first search patterns within recursive Common Table Expressions (CTEs).

The Mechanics of Traversal

When you execute a recursive CTE, PostgreSQL processes the UNION ALL members iteratively. By default, it processes the result set in a way that feels "breadth-first" because it evaluates all nodes at the current level before moving to the next. However, as your data hierarchies grow—such as deep organizational charts or file systems—you often need to dictate the order of retrieval to optimize for specific output requirements or memory constraints.

Implementing Search Orders

To explicitly control the traversal, we use the SEARCH clause. This feature, introduced in modern PostgreSQL, allows the engine to keep track of the hierarchy without manual bookkeeping.

1. Breadth-First Search Use this when you want to see all "Level 1" items, then all "Level 2" items, and so on. This is ideal for tiered reporting.

WITH RECURSIVE org_chart(id, name, path) AS (
    SELECT id, name, ARRAY[id] FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, o.path || e.id 
    FROM employees e, org_chart o WHERE e.manager_id = o.id
)
SEARCH BREADTH FIRST BY id SET order_col
SELECT * FROM org_chart ORDER BY order_col;

2. Depth-First Search Use this when you want to explore one branch fully before moving to the next sibling. This is significantly more memory-efficient when you only need to process specific paths or perform deep-copy operations.

WITH RECURSIVE org_chart(id, name, path) AS (
    -- Anchor and Recursive members
    ...
)
SEARCH DEPTH FIRST BY id SET order_col
SELECT * FROM org_chart ORDER BY order_col;

Why it Matters

The SEARCH clause creates a virtual column (order_col) that the engine uses to sort the final result set. By choosing between DEPTH or BREADTH, you are telling the optimizer how to stage the memory buffers for the recursive working table. Depth-first traversal mimics a stack, often resulting in lower memory overhead for wide, deep trees, while breadth-first traversal mimics a queue, which is preferred when hierarchy level is the primary sorting criterion.

Key Takeaway: Use the SEARCH clause to explicitly define traversal order, allowing the query engine to optimize memory allocation based on whether you need a level-by-level view (Breadth-First) or a branch-by-branch view (Depth-First).