Home > SQL > Recursive Common Table Expressions

Recursive Common Table Expressions

November 5th 2009 | Kevin Jones

Recursive Common Table Expressions

Recently we had the need to do a recursive query in SQL. We were using SQL 2005 and up, which supports a feature called Common Table Expressions, or CTEs. They aren’t new, yet so many blog posts present the same example over and over again. Common Table Expressions are extremely helpful when you have a hierarchy of data. In our example below we have a table called OrganizationUnits that contains a representation of the Organizational Units in an Active Directory domain. The basic schema looks like this:

OrganizationUnitId    INT IDENTITY
OrganizaitonUnitName    NVARCHAR(255)
ParentOrganizationUnitId    INT
DomainId    INT

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

The ParentOrganizationUnitId column foreign keys to the OrganizationUnits table (itself). Our goal was, given an organization unit ID, get me all of its children, and its children’s children, etc. In SQL 2000 this used to be painful as it required a cursor. Let’s start with baby steps. The first thing we can do is remove the recursive part and just get the immediate children. That’s a simple select statement. Here is some sample data:

 

 

OrganizationUnitId

OrganizationUnitName

ParentOrganizationUnitId

DomainId

1

USA

NULL

1

2

California

1

1

3

Virginia

1

1

4

Los Angeles

2

1

5

Falls Church

3

1

6

Richmond

3

1

 

This is fairly typical of a table when dealing with these kinds of structures. So, if we wanted to get all of the children of Organization Unit 1, it would return all records. If we wanted to get all of the children of 3, it should return Falls Church and Richmond.

Let’s start with getting USA and all of its immediate children. That would look something like this:

SELECT    *
FROM        OrganizationUnits
WHERE        OrganizationUnitId = 1
OR
ParentOrganizationUnitId = 1

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

That wasn’t very difficult, right? However, it didn’t give us all of the children for Virginia or California. So let’s create a common table expression out of this table, as the “anchor”. We’ll name our common table expression “ou_cte”.

WITH ou_cte AS
(
    SELECT    *
    FROM        OrganizationUnits
    WHERE        OrganizationUnitId = 1
            OR
            ParentOrganizationUnitId = 1
)
SELECT * FROM ou_cte

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

This is the basic syntax for a common table expression. Think of it as declaring an alias for a select statement so far. To make this really powerful though, that select statement inside of the common table expression can join on itself! This will be the recursive part of the Common Table Expression. The beginning and the end of each statement is denoted with a UNION ALL. We’ll start by removing the second part of the WHERE clause in the query since our recursive join will handle it.

WITH ou_cte AS
(
    SELECT    *
    FROM        OrganizationUnits
    WHERE        OrganizationUnitId = 1
)
SELECT * FROM ou_cte

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

Now we will add the union to create the recursive join.

WITH ou_cte AS
(
    SELECT    *
    FROM        OrganizationUnits
    WHERE        OrganizationUnitId = 1
    UNION ALL
    SELECT    ou.*
    FROM        OrganizationUnits ou
            JOIN ou_cte
            ON ou_cte.OrganizationUnitId = ou.ParentOrganizationUnitId
)
SELECT * FROM ou_cte

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

This will return all of the rows. If we changed that WHERE clause to 2, it would return California and Los Angeles.

Neat, right? You can do some powerful things on recursive joining. Like building a folder path. Imagine the folder path is required to have a column called “FullDisplayName” that returns a slash delimited path, like USA\Virginia\Falls Church. That is very easy to do. We’ll start by declaring FullDisplayName as OrganizationUnitName, then loop through each record, appending the name again.

WITH ou_cte AS
(
    SELECT    *, [OrganizationUnitName] AS [FullDisplayName]
    FROM        OrganizationUnits
    WHERE        OrganizationUnitId = 2
    UNION ALL
    SELECT    ou.*,
CAST(ou_cte.OrganizationUnitName + '\' +
ou.[OrganizationUnitName] AS VARCHAR(255)) AS
[FullDisplayName]
    FROM        OrganizationUnits ou
            JOIN ou_cte
            ON ou_cte.OrganizationUnitId = ou.ParentOrganizationUnitId
)
SELECT * FROM ou_cte

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, “Courier New”, courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

This will yield a computed path that meets our requirements.

2

California

1

1

California

4

Los Angeles

2

1

California\Los Angeles

 

This allows us to build some very powerful queries that remove a lot of in-code logic and make reporting much more simple.

Note the cast in the above operation. If I didn’t do this, it would give me an error saying I was trying to union results that weren’t of the same type. This is because I am concatenating strings – and that results in a char type who’s length is exactly the size of the concatenation, such as CHAR(22) for California\Los Angeles. It must be cast back to the exact same type and the same length for this to work.

These are some basic examples of what can be a very powerful query.

Kevin Jones is a Team Lead at Thycotic Software, an agile software services and product development company based in Washington DC. Secret Server is our flagship password management software product.

  1. November 6, 2009 at 2:25 am

    Good one…
    I had touched the topic – you may want to check the solution.

    http://dgoyani.blogspot.com/2005/09/effective-way-to-expand-data-tree-in.html

  2. IanicBass
    November 11, 2009 at 2:25 pm

    You can do this also in a more simplier way…

    select * from OrganizationUnits where OrganizationUnitId = 1
    union all
    select s1.*
    from OrganizationUnits s1
    inner join OrganizationUnits s2 on s1.ParentOrganizationUnitId = s2.OrganizationUnitId

  3. November 11, 2009 at 2:42 pm

    @IanicBass – The problem with that is it isn’t recursive. If you don’t know the depth of the parent child relationship then you would have to keep adding joins for each potential child of each item. This will work regardless of how deep the “nesting” of the children go.

  4. IanicBass
    November 13, 2009 at 7:24 pm

    Kevin, could you please give me an example data where I would not know how deep would the nesting of the children go? I’ve tested this using the query I did with nesting child relationship and it seems to work just fine.

    Thank you.

  5. November 16, 2009 at 7:24 pm

    @IanicBass – Consider the following sample data with the same schema as in my post:

    1 | World | NULL | 1
    2 | USA | 1 | 1
    3 | China | 1 | 1
    4 | Fujian | 3 | 1
    5 | Longyan | 4 | 1
    6 | Virgina | 2 | 1
    7 | Falls Church | 6 | 1
    8 | California | 2 | 1
    9 | Los Angeles | 8 | 1

    And lets say we wanted to get all children for “World”. That should return everything, right?

    Mine as expected returns all rows if I specify 1 as who I want to get the children for. Yours also returns all because it unions all. If I wanted to get JUST the children for China, and ran yours like this:

    select * from OrganizationUnits where OrganizationUnitId = 3
    union all
    select s1.*
    from OrganizationUnits s1
    inner join OrganizationUnits s2 on s1.ParentOrganizationUnitId = s2.OrganizationUnitId

    It would still return everything, including USA which is not a child of China. However using a CTE will properly return

    3 | China | 1 | 1
    4 | Fujian | 3 | 1
    5 | Longyan | 4 | 1

  6. IanicBass
    November 16, 2009 at 7:42 pm

    Kevin,

    Yes, you are correct. In the sample above, CTE would be the best approach.

    But just an FYI, we can also just add a where clause in my query and have the same result as yours…

    select * from OrganizationUnits where OrganizationUnitId = 3
    union all
    select s1.*
    from OrganizationUnits s1
    inner join OrganizationUnits s2 on s1.ParentOrganizationUnitId = s2.OrganizationUnitId
    WHERE
    s2.OrganizationUnitId = 3 OR s2.ParentOrganizationUnitId = 3

    Thanks.

  7. chris
    November 20, 2011 at 6:40 pm

    something’s up w/ your inline css– its made your article almost allot more difficult to read (using Google Chrome)

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: