Search depth/breadth first

1. Minor deviation: contents of <sequence column>

The search clause of with recursive creates a column that allows sorting the result in depth-first or breadth-first order.

The search clause follows immediately after a recursive with element—even before a cycle clause. The primary order is specified by the depth first or breadth first keywords. The following, mandatory by clause takes a list of expression to define the per-level order. Finally, the set clause expects the name of the newly created column, the so-called sequence column.

WITH RECURSIVE
     categories (category_id, parent, name)
  AS ( SELECT *
         FROM product_categories
        WHERE parent IS NULL
    UNION ALL
       SELECT pc.*
         FROM categories AS parent
         JOIN product_categories pc
           ON pc.parent = parent.category_id
     )
SEARCH DEPTH FIRST BY name SET seq_col
SELECT category_id, name
  FROM categories
 ORDER BY seq_col

Note that the search clause does not define the order in which rows are returned by the recursive query.0 Instead it provides a column that can be used in an order by clause.

The example above traverses a hierarchy, such as the one shown below, from the root node to the leaf nodes. The order by clause in the last line uses seq_col generated by the search clause to actually establish the specified order. Note that seq_col is really just a column name. You can also put it into the select clause to see what it contains—or just select *. Consequently, the order by clause can also use other sort criteria and asc/desc and nulls first/last modifiers.

In either case, depth-first or breadth-first, the rows of the initial leg of the recursive query get the lowest value in the sequence column. That means, ascending ordering—as used in the example above—returns them first. Specifically, that is the root node: All Goodies.

The next item is, also in either case, the first child of the second level. Note that this is Brands, not Types, due to the by name clause that defines the per-level order.

The order or the remaining nodes differs between depth-first and breadth-first. Depth-first provides the deeper nodes first. That are, Modern SQL and Use The Index, Luke, in this order. Only then the sibling Types follows along with its children.

Breadth-first, on the other hand, first returns the Types node before any node of the third level. Then all nodes of the third level follow in the order specified in the by clause. Specifically: Books, Modern SQL, Mugs & co, Stickers, Use The Index, Luke. Note that siblings are not kept together. The children of Brands and Types are just intermixed due to the ordering by name.

Notable Extensions

Standard SQL does not support the asc/desc or nulls first/last modifiers in the by clause of search.1

SEARCH DEPTH FIRST BY name DESC SET seq_col

That means it is not possible to just reverse the per-level order in standard SQL. As this is a pretty reasonable requirement, some systems do support it nonetheless.

Contents of the Sequence Column

The SQL standard defines the search clause as a syntactic transformation that puts a row-value (breadth-first) or an array of row-values (depth-first) into the sequence column. Sorting based on these row-values yields the specified order.2 A consequence of this is that the just mentioned modifiers are not supported as they cannot be put into a row-value.3 From that perspective it seems to be no coincidence that systems that supports these modifies do not populate the sequence column in the way the standard describes it, but with a simple ordinal number.

Related

• cycle: Preventing Infinite Loops in Recursive SQL Queries

  If both are present, search and cycle, search must be first.

• Tutorial: With — Organize Complex Queries

Normative References

The search clause is defined in ISO/IEC 9075-2:2023 §7.18 as part of optional feature T131, “Recursive query”.