SQL search depth/breadth first

Compute an Extra Column to Order the Result of Recursive Queries

Apache DerbyBigQueryDb2 (LUW)H2MariaDBMySQLOracle DBPostgreSQLSQL ServerSQLite20072009201120132015201720192021⊘ 3.5.7 - 3.43.0⊘ 2008R2 - 2022✓ 14 - 16⊘ 8.3 - 13✓ 11gR2 - 21ca⊘ 11gR1⊘ 5.0 - 8.0.34⊘ 5.1 - 10.11⊘ 1.4.191 - 2.2.220⊘ 9.7 - 11.5.8⊘ 2.0⊘ -
  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.

     categories (category_id, parent, name)
         FROM product_categories
        WHERE parent IS NULL
       SELECT pc.*
         FROM categories AS parent
         JOIN product_categories pc
           ON pc.parent = parent.category_id
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.

All GoodiesTypesBrandsBooksMugs & coStickersModern SQLUse The Index, Luke

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.

Support My Work

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.

Notable Extensions

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


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.

Oracle DBPostgreSQLsearch … by … asc/descsearch … by … nulls first/last

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.

Oracle DBPostgreSQLstandard-conformingordinal numbering

Normative References

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.

About the Author

Photo of Markus Winand

Markus Winand provides insights into SQL and shows how different systems support it at modern-sql.com. Previously he made use-the-index-luke.com, which is still actively maintained. Markus can be hired as trainer, speaker and consultant via winand.at.

Buy the Book

Cover of “SQL Performance Explained”: Squirrel running on grass

The essence of SQL tuning in 200 pages

Buy now!
(paperback and/or PDF)

Paperback also available at Amazon.com.

Hire Markus

Markus offers SQL training and consulting for developers working at companies of all sizes.
Learn more »


  1. Nor does it control the algorithm. SQL remains a declarative language.

  2. 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.

  3. 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).

  4. 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.

Connect with Markus Winand

Markus Winand on LinkedInMarkus Winand on XINGMarkus Winand on Twitter
“modern SQL” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Legal | Contact | NO WARRANTY | Trademarks | Privacy and GDPR | CC-BY-NC-ND 3.0 license