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.
I offer SQL training, tuning and consulting. Buying my book “SQL Performance Explained” (from €9.95) also supports my work on this website.
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
.
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.
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.
cycle
: Preventing Infinite Loops in Recursive SQL Queries
If both are present, search
and cycle
, search
must be first.
Tutorial: With
— Organize Complex Queries
The search
clause is defined in ISO/IEC 9075-2:2023 §7.18 as part of optional feature T131, “Recursive query”.
You can’t catch up on 20 years of SQL evolution in one day. Subscribe the newsletter via E-Mail, Twitter or RSS to gradually catch up and to keep modern-sql.com on your radar.
The essence of SQL tuning in 200 pages
Buy now!
(paperback and/or PDF)
Paperback also available at Amazon.com.
Markus offers SQL training and consulting for developers working at companies of all sizes.
Learn more »
Nor does it control the algorithm. SQL remains a declarative language.
ISO/IEC 9075-2:2023 §7.18: Not covered in the BNF. Not to be confused with the modifiers in the order by
clause that uses the sequence column.
Although I fail to find the place in the standard where the less-than comparison of arrays is defined—in particular for different-length arrays. The search
clause depends on the shorter-is-less semantic like is there for character strings with a no-pad collation (ISO/IEC 9075-2:2023 §8.2 GR 3b).
On the other hand, providing a composite value with all details allows picking the individual parts out of it to put them into the order by
clause individually—each with the desired modifiers.