Archive

Posts Tagged ‘OrganizationUnits CTE’

Recursive Common Table Expressions

November 5, 2009 7 comments

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.