Back to articles list November 26, 2016 - 7 minutes read Do it in SQL: Recursive SQL Tree Traversal Michał Kołodziejski Senior Software Engineer, Team Leader Tags: sql In the previous article, I described how to use Common Table Expressions to find the shortest path in a directed graph. That example could be hard to follow, I admit. Let’s do something much more common, something that is implemented on almost every website – a menu. Instead of writing the code, we’ll take advantage of the SQL tree structure writing just one query. We’ll use CTEs for PostgreSQL and the hierarchical query clause for Oracle. If you want to learn to write CTEs on your own, I recommend our interactive course Recursive Queries. So, let’s see what a simple menu looks like: What have we got here? There is a main menu and a drop-down menu which appears after we click the button from the main menu. Of course, there could be more submenus attached to another button on the main menu. What’s more, there could also be a sub-submenu, which would appear after clicking on one of the buttons of a submenu. In general, there could be an unlimited number of menu levels. The data arrangement of such a menu is a SQL tree structure: As you can see, it’s a typical SQL tree structure. There are menu nodes which are attached to parent nodes. The only node without a parent is the root node. This is how we store such a SQL tree structure in the database: In the SQL tree structure, every node has its own, unique id. It has a reference to the parent node. For every node in a submenu we need its sequence number for ordering purposes. The name column is just a label which will be shown on the website. The url_path column may require a little more explanation. Every node stores a part of the full URL path of the resource. Its entire path is a concatenation of the url_path of all nodes from the root to that node. For example, for the following data: > select * from menu_node; id | parent_node_id | seq | name | url_path ----+----------------+-----+--------------------+----------- 1 | | 1 | root | 2 | 1 | 1 | Diagram | diagram 3 | 1 | 2 | My models | my_models 4 | 1 | 3 | Share requests | share 5 | 1 | 4 | My account | account 6 | 1 | 5 | Invite people | invite 7 | 1 | 6 | Help | help 8 | 7 | 1 | Documentation | doc 9 | 7 | 2 | FAQ | faq 10 | 7 | 3 | Ask a question | ask 11 | 7 | 4 | Request a feature | feature 12 | 7 | 5 | Report a problem | problem 13 | 7 | 6 | Keyboard shortcuts | shortcuts 14 | 8 | 1 | Section 1 | section1 15 | 8 | 2 | Section 2 | section2 16 | 8 | 3 | Section 3 | section3 (16 rows) the entire path of the node “Section 1” is: /help/doc/section1. Having such a structure, we want to render the menu on the page. If we didn’t use a SQL query to get hierarchical tree levels, we would have to either run multiple queries (for every node to get its children) or retrieve all the data and build the structure in the code. I’m not saying it’s a bad approach, but it can be done in an easier and smarter way. PostgreSQL – recursive WITH clause In order to render such a menu, we need to know the full URL path of each button, information about the level of the node (to appropriately style it in CSS) and where to attach it (it’s parent’s ID of course). So let’s start to build our select query with CTE: WITH RECURSIVE menu_tree (id, name, url, level, parent_node_id, seq) AS ( At first, we need to get the root node: SELECT id, name, '' || url_path, 0, parent_node_id, 1 FROM menu_node WHERE parent_node_id is NULL Then, we recursively go deeper with our SQL query, concatenating the path and incrementing the level: UNION ALL SELECT mn.id, mn.name, mt.url || '/' || mn.url_path, mt.level + 1, mt.id, mn.seq FROM menu_node mn, menu_tree mt WHERE mn.parent_node_id = mt.id And in the end, we need to get all rows except for the root node (we don’t need it anymore) in the proper order. First, they should be ordered by level, then “grouped” by parent, and finally following seq order. So the query will look like this: SELECT * FROM menu_tree WHERE level > 0 ORDER BY level, parent_node_id, seq; The final query: WITH RECURSIVE menu_tree (id, name, url, level, parent_node_id, seq) AS ( SELECT id, name, '' || url_path, 0, parent_node_id, 1 FROM menu_node WHERE parent_node_id is NULL UNION ALL SELECT mn.id, mn.name, mt.url || '/' || mn.url_path, mt.level + 1, mt.id, mn.seq FROM menu_node mn, menu_tree mt WHERE mn.parent_node_id = mt.id ) SELECT * FROM menu_tree WHERE level > 0 ORDER BY level, parent_node_id, seq; Looks pretty easy, doesn’t it? As a result we get the data: id | name | url | level | parent_node_id | seq ----+--------------------+--------------------+-------+----------------+----- 2 | Diagram | /diagram | 1 | 1 | 1 3 | My models | /my_models | 1 | 1 | 2 4 | Share requests | /share | 1 | 1 | 3 5 | My account | /account | 1 | 1 | 4 6 | Invite people | /invite | 1 | 1 | 5 7 | Help | /help | 1 | 1 | 6 8 | Documentation | /help/doc | 2 | 7 | 1 9 | FAQ | /help/faq | 2 | 7 | 2 10 | Ask a question | /help/ask | 2 | 7 | 3 11 | Request a feature | /help/feature | 2 | 7 | 4 12 | Report a problem | /help/problem | 2 | 7 | 5 13 | Keyboard shortcuts | /help/shortcuts | 2 | 7 | 6 14 | Section 1 | /help/doc/section1 | 3 | 8 | 1 15 | Section 2 | /help/doc/section2 | 3 | 8 | 2 16 | Section 3 | /help/doc/section3 | 3 | 8 | 3 (15 rows) With this single query you can get all the data you need to render a simple multi-level menu. Thanks to the SQL tree structure, your data is represented in a clear and easily-digestible way. To practice writing hierarchical queries like this one, I recommend our interactive course Recursive Queries. Oracle – hierarchical queries In Oracle you can use either the hierarchical query clause (also known as “CONNECT BY query”) or recursive subquery factoring (introduced in version 11g release 2). The structure of the second one is almost the same as in the query for PostgreSQL. The only differences are: lack of RECURSIVE keyword “level” is a reserved word, so we must change it The rest remains unchanged and the query works well. With regards to the hierarchical query clause, its syntax is totally different. The query looks like this: SELECT id, name, SYS_CONNECT_BY_PATH(url_path, '/') AS url, LEVEL, parent_node_id, seq FROM menu_node START WITH id IN (SELECT id FROM menu_node WHERE parent_node_id IS NULL) CONNECT BY PRIOR id = parent_node_id; One thing worth noting is that this query will go truly recursively, that is – in a depth-first order. The “recursive” WITH clause in PostgreSQL and (by default) in Oracle traverse the structure in a breadth-first order. As you can see, understanding the concept of the SQL tree structure may save some of our precious time (and a few lines of code). It’s your choice if you use recursive traversal queries or not, but it’s definitely worth while to know the alternative. To learn how to write recursive queries in SQL, I recommend our interactive course Recursive Queries. It contains 114 hands-on coding exercises that let you practice Common Table Expressions and recursive queries like the ones shown in this article. Tags: sql You may also like Simplify SQL Code: Recursive Queries in DBMS Are you repeating the same query in every report? Are they getting too complicated? Use recursive queries to simplify SQL code! Read more How to Organize SQL Queries with CTEs Common table expressions (CTEs) allow you to structure and organize your SQL queries. It is a necessity when you begin to move deeper into SQL. Read more How to Draw a Christmas Tree in SQL Learn how to use SQL to manipulate all kinds of data, from huge analytical queries to brief single-purpose statements. Read more Get to Know the Power of SQL Recursive Queries Recursive Queries: skewness and kurtosis. Most commonly, the SQL queries we run on a database are quite simple. Read more Long SQL Query vs. Recursive SQL Query Explore recursive CTE hierarchy in SQL server and find out how to tune your SQL query performance. Read more How Recursive Common Table Expressions Work Recursive Common Table Expressions are immensely useful when you're querying hierarchical data. Let's explore what makes them work. Read more How CTEs Work We explain what Common Table Expressions or CTEs are, how they compare to subqueries, and how to use them in your SQL instructions. Read more Subscribe to our newsletter Join our weekly newsletter to be notified about the latest posts.