Recursion in SQL Server using Common Table Expressions (CTE)

How do you take a relational table and make it recursive? Today, we cover Common Table Expressions (CTE) in SQL Server.

No matter what application you write, at one time in your career, you will experience a need for a hierarchical structure in your tables.

While this particular way of storing data is easy, how do you retrieve records based on a certain node or point in the data hierarchy?

For example, let's look at Amazon's menu hierarchy.

When you click on their hamburger icon, you get their list of primary categories.

Click on "Movies, Music, and Games" to dig down even further to their secondary level.

You get the idea.

Their menu system can be multiple levels deep with even more sub-levels thrown in for good measure. ;-)

If you had this large of a category system for menus, how would you pull records starting at a certain point in the hierarchy?

Enter Common Table Expressions (CTE)

Introduced back in SQL Server 2008, Common Table Expressions are similar to temp tables except they clean up after themselves. ;-)

With CTEs, they can be recursive or non-recursive. I've used both when I needed something quick, but as you may have guessed, we'll be looking at the recursive approach in this post.

The table structure is similar to a post I wrote about building a generic menu system.

So let's build something like Amazon's menu.

Table Design (MenuSystem)

Table Records

I didn't want to spend eight hours grabbing all of Amazon's menu items, so I decided to create a quick table and populated just enough for a demonstration.

Common Table Expression Structure

CTEs should begin with a ";WITH" statement. The semi-colon is required to make sure no other commands bleed into this CTE.

The CTE is then given a name and wraps a statement with parentheses. After the second parentheses, we immediately follow that with another SQL statement like a SELECT to view our results.

For our recursive list, we need a starting point. The starting point for our records are the ParentIds containing null.

Our first SELECT statement will grab our initial records and follow that up with a UNION ALL to the CTE name. This is where it gets a little trippy.

;WITH cte_categories
AS
(
    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    WHERE ParentId IS NULL

    UNION ALL

    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    INNER JOIN cte_categories cat ON ms.ParentId = cat.MenuId
)

Notice how we are joining on the cte_categories inside the cte_categories.

As I mentioned before, it is absolutely necessary to have a single statement right after the ending parentheses or SQL Server will complain about it.

So our final Common Table Expression looks like this:

;WITH cte_categories
AS
(
    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    WHERE ParentId IS NULL

    UNION ALL

    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    INNER JOIN cte_categories cat ON ms.ParentId = cat.MenuId
)
SELECT
    MenuId
   ,Title
   ,ParentId
FROM cte_categories

And this result set returns back all of the records.

"But JD, why not just return all the records anyway and let C# handle it?"

Even though you could do a "SELECT * FROM MenuSystem", CTEs provide a better way to grab hierarchical data.

This is where the beauty of recursive common table expressions shines through.

Let's say our user selects the "Movies, Music, & Games" menu option from the Amazon menu and, on the next page, you want to display all of the menu items from MenuId 2 down. Your CTE would look like this:

;WITH cte_categories
AS
(
    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    WHERE ms.MenuId=2 -- Make your starting point a single menu item

    UNION ALL

    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    INNER JOIN cte_categories cat ON ms.ParentId = cat.MenuId
)
SELECT
    MenuId
   ,Title
   ,ParentId
FROM cte_categories

Your results look like this:

Whoa!

We don't need that many records. We only need to go down one level. Adjust the second SELECT statement in the UNION ALL with an additional filter.

;WITH cte_categories
AS
(
    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    WHERE ms.MenuId=2

    UNION ALL

    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    INNER JOIN cte_categories cat ON ms.ParentId = cat.MenuId AND ms.ParentId=2
)
SELECT
    MenuId
   ,Title
   ,ParentId
FROM cte_categories

That's better.

Going Up!

This is great if we are looking down the tree of items and want the entire tree, but what if we want to move up the tree? What if we are down in the weeds and located at the bottom of the tree?

Let's pick a deep category here as an example. How about Blues Music? What are the parents of this category?

We simply swap the aliases in the inner join and set the initial menuId as our starting point.

;WITH cte_categories
AS
(
    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    WHERE ms.MenuId=16 

    UNION ALL

    SELECT
        ms.MenuId
       ,ms.Title
       ,ms.ParentId
    FROM MenuSystem ms
    INNER JOIN cte_categories cat ON cat.ParentId = ms.MenuId
)
SELECT
    MenuId
   ,Title
   ,ParentId
FROM cte_categories

Now you have the exact path for breadcrumbs.

Movies, Music & Games » Digital Music » Blues

Forward or backwards, CTEs offer a quick and simple way to recurse through data.

Conclusion

Common Table Expressions provide the most bang-for-the-buck. Instead of pulling back all of the records and sorting it out using C#, pull back the records you need based on one point in the hierarchy.

This technique is particularly useful when you have:

• Menu systems with multiple levels (where am I on the site based on the current page?)
• Product Categories (what product page am I on and what sub-products are below it?)
• Organizational Charts (who reports to this person in the hierarchy?)

One of my favorite uses recently was to display a root level of product categories. When the user clicks on a folder image next to the category, a call was made with the category Id to retrieve the children underneath this category.

This is how dynamic treeviews are built. ;-)

Have you used CTEs before? How did you use them? Post your comments below and let's discuss!