EXPLAIN EXTENDED

How to create fast database queries

Adjacency list vs. nested sets: SQL Server

with 5 comments

Continuing the series:

What is better to store hierarchical data: nested sets model or adjacency list (parent-child) model?

For detailed explanations of the terms, see the first article in the series:

Now, let's see what's better for SQL Server.

We will create a single table that holds both adjacency list data and nested sets data, with 8 levels of nesting, 5 children of each parent node and 2,441,405 records:

Table creation details

We will test the performance of 3 most common operations:

  • Find all descendants of a given node
  • Find all ancestors of a given node
  • Find all descendants of a given node up to a certain depth

All descendants

We will select all descendants of a given node (which is close to the root node and has lots of descendants).

Since there are more than 100,000 descendants, we will select the aggregated length of the stuffing columns rather than a huge resultset of values. All rows are required to be visited anyway, so this is quite good performance test.

Nested sets

SELECT  SUM(LEN(hc.stuffing))
FROM    [20090925_nested].t_hierarchy hp
JOIN    [20090925_nested].t_hierarchy hc
ON      hc.lft BETWEEN hp.lft AND hp.rgt
WHERE   hp.id = 42

View query details

Nested sets model is good for this query, since it required only a single range scan on lft to get all descendants.

This query completes in 81 ms.

Adjacency list

WITH    q AS
(
SELECT  id, stuffing
FROM    [20090925_nested].t_hierarchy h
WHERE   id = 42
UNION ALL
SELECT  hc.id, hc.stuffing
FROM    q
JOIN    [20090925_nested].t_hierarchy hc
ON      hc.parent = q.id
)
SELECT  SUM(LEN(stuffing))
FROM    q

View query details

This query makes several range scans (one per node) using recursion.

These ranges finally sum up to the same set of values (of course), however, the parents of descendants are not contiguous and no single range can select them all. That's why this query is less efficient than nested sets and runs for 531 ms, or about 6 times as long.

All ancestors

Nested sets

SELECT  hp.id, hp.parent, hp.lft, hp.rgt, hp.data
FROM    [20090925_nested].t_hierarchy hc
JOIN    [20090925_nested].t_hierarchy hp
ON      hc.lft BETWEEN hp.lft AND hp.rgt
WHERE   hc.id = 1000000
ORDER BY
hp.lft

View query details

This is extremely inefficient: 16 seconds.

Unlike PostgreSQL, SQL Server is not capable of building in-memory bitmaps from the index results. It just has to seek the index and join. And the join condition used here is not an equality, thus making all join methods except NESTED LOOPS impossible to use.

All this results in a very poor performance which is far beyond that of even a marginally usable query.

Adjacency list

WITH    q AS
(
SELECT  h.*, 1 AS level
FROM    [20090925_nested].t_hierarchy h
WHERE   id = 1000000
UNION ALL
SELECT  hp.*, level + 1
FROM    q
JOIN    [20090925_nested].t_hierarchy hp
ON      hp.id = q.parent
)
SELECT  id, parent, lft, rgt, data
FROM    q
ORDER BY
level DESC

View query details

Now, this query is a boon for adjacency list model. There are 9 ancestors that can be retrieved in 9 clustered index seeks and these 9 values then need to be sorted. SQL Server eats such queries for breakfast.

This query completes in 1 ms which is the range of time measurement error in SQL Server statistics.

In other words, this query is very very fast.

Descendants up to a given level

Since the performance on this task may depend on the number of the descendants, we will run 2 queries for each model.

This first query selects descendants of a node that is close to the root (node 42), the second one selects those of node 31,415 which is further from the root.

Nested sets

SELECT  hc.id, hc.parent, hc.lft, hc.rgt, hc.data
FROM    [20090925_nested].t_hierarchy hp
JOIN    [20090925_nested].t_hierarchy hc
ON      hc.lft BETWEEN hp.lft AND hp.rgt
WHERE   hp.id = ?
AND
(
SELECT  COUNT(*)
FROM    [20090925_nested].t_hierarchy hn
WHERE   hc.lft BETWEEN hn.lft AND hn.rgt
AND hn.lft BETWEEN hp.lft AND hp.rgt
) <= 3

View results for node 42

View results for node 31,415

These queries complete in 108 seconds and 38 seconds, respectively. Both these queries use nested loops with a full table scan which doesn't add to performance. This makes the queries unusable.

Adjacency list

WITH    q AS
(
SELECT  id, parent, lft, rgt, data, 1 AS level,
CAST(LEFT(CAST(id AS VARCHAR) + REPLICATE('0', 10), 10) AS VARCHAR) AS bc
FROM    [20090925_nested].t_hierarchy hc
WHERE   id = ?
UNION ALL
SELECT  hc.id, hc.parent, hc.lft, hc.rgt, hc.data, level + 1,
CAST(bc + '.' + LEFT(CAST(hc.id AS VARCHAR) + REPLICATE('0', 10), 10) AS VARCHAR)
FROM    q
JOIN    [20090925_nested].t_hierarchy hc
ON      hc.parent = q.id
WHERE   level < 3
        )
SELECT  id, parent, lft, rgt, data
FROM    q
ORDER BY
        bc

The field bc defines breadcrumbs which can be used to return the nodes in tree order.

In PostgreSQL 8.4, we used an array for that.

SQL Server lacks array type, that's why we need to use a hack: converting the id's into zero-padded strings of fixed length (10 characters) and concatenating them.

Here are the query results:

View results for node 42

View results for node 31,415

Both queries use the same efficient plans (which basically include 31 index seeks and ordering of the values fetched) and complete in 2 ms, which may be considered instant.

Summary

We made an SQL Server table combining two popular models for hierarchical data: adjacency list and nested sets and tested three most used queries against these data:

  1. Find all descendants of a given node
  2. Find all ancestors of a given node
  3. Find all descendants of a given node up to a certain depth

As in the similar test for PostgreSQL 8.4 (conducted in the previous article), nested sets model has shown a little performance benefit for the first query (finding all descendants).

However, SQL Server, unlike PostgreSQL, is not able to build in-memory bitmaps which makes nested loops (required for the queries 2 and 3 against the nested sets model) very inefficient.

This makes the nested sets model very slow for queries 2 and 3 in SQL Server. More or less significant number of records in the table makes these queries too slow to be of practical use.

Adjacency list, on the contrary, shows decent performance for the query 1 and amazing performance for the queries 2 and 3.

This fact, along with the simplicity of adjacency list implementation and management, make adjacency list a preferred way to store hierarchical data in SQL Server versions that support recursive CTEs, that is versions from 2005 onwards.

Written by Quassnoi

September 25th, 2009 at 11:00 pm

Posted in SQL Server

5 Responses to 'Adjacency list vs. nested sets: SQL Server'

Subscribe to comments with RSS

  1. Hi Quassnoi,

    Excellent article, I appreciate the depth to which you’ve investigated these structures. I’ve learned a great deal from reading this and other articles on your site. Most impressive!

    I would like to understand further about your nested loop setup. I’ve made a few adjustments which result in much better performance (I’m speaking in relative terms as our equipment I’m sure is different), and would like your thoughts about what I’ve done.

    First, in the environment I’m in (non-dag bills of materials (BOMs)), the most common use cases differ from what you have described. I would agree that “all descendants” is one case, and that “all ancestors” is another, but I would remove “descendants to a particular level” completely from the list (not just move it down in priority), and replace it with “immediate descendants”. Here is why. With a BOM, if the current row is called an “assembly”, then descendants can either be another “assembly” or a “component”. I will define an assembly as that which is made up of a collection of components. This fits well into the model of the tree structure, where components are leaf nodes and assemblies are non-leaf nodes. If we want to see a BOM for a given assembly, then we want “immediate descendants”, as it allows us to collect all the parts (assemblies or components) that we need to make the current assembly. If we wanted to see _everything_ that went into the highest level assembly, then we want “all descendants”. If we drill to a fixed layer, we get neither of these desired results, instead, its a useless mix.

    Perhaps in some environments that have completely balanced hierarchies, the specific level is desired, but in this one its not. In fact, if the hierarchies were completely balanced, then would you need something so flexible as the nested loop or the adjacency list anyway?

    Another note about this first point, when you have the environment where you don’t need the “particular level” query at all, the need for recursion goes away and allows MySQL and other non-recursive engines to play in the game again.

    Next, if we stick with your nested loop query for “all ancestors”, the addition of an index on both lft and rgt columns improved my performance by ~15x. Something like this:

    CREATE NONCLUSTERED INDEX IX_hierarchy_lft_rgt ON [20090925_nested].t_hierarchy (lft,rgt)

    Finally, the nested loop query for “all ancestors” should be simpler than what you have designed because there really is no need to join anything here (AFAIK). It should be just two comparisons in the WHERE clause:

    DECLARE @clft INT; DECLARE @crgt INT;

    SELECT @clft=lft, @crgt=rgt
    FROM [20090925_nested].t_hierarchy
    WHERE id=1000000;

    SELECT id, parent, lft, rgt, data
    FROM [20090925_nested].t_hierarchy
    WHERE lft=@crgt
    ORDER BY lft;

    Admittedly, this takes two separate queries, but all included, the performance increases another ~3x for a total of ~45x. In fact, even without the index this new query structure performs at the same level. Also, when I made these changes, my nested loop “all ancestors” query outperformed the adjacency list query, even if only by 20%.

    Again, I appreciate you laying the groundwork and putting forth the effort required to document all this. You have motivated me to learn a great deal about these structures. I use the nested loop a lot in MySQL so I look forward to reading whatever comments you have about my suggestions.

    ps1. All my experiments and numbers came from using SQL Server to stay in the same realm as this article, even though my typical platform is MySQL.

    ps2. When I ran your setup query, I only got 480k rows instead of the 2.4M you got. I suspect there is a < / <= difference somewhere, but I didn't debug it.

    Mike Tallroth

    27 Oct 12 at 06:23

  2. Sorry, I must not have formatted my code properly, its supposed to have two comparisons in the final select statement. I’ll try again,

    DECLARE @clft INT; DECLARE @crgt INT;

    SELECT @clft=lft, @crgt=rgt
    FROM [20090925_nested].t_hierarchy
    WHERE id=1000000;

    SELECT id, parent, lft, rgt, data
    FROM [20090925_nested].t_hierarchy
    WHERE lft <= @clft AND rgt >= @crgt
    ORDER BY lft;

    Mike Tallroth

    27 Oct 12 at 06:31

  3. @Mike: thanks for your input.

    Could you please post the queries and response times when you are comparing performances? I. e. “I’ve run this query, it completed in X seconds, then I’ve run that query, it completed in Y seconds”.

    Also please run these two commands:


    SET STATISTICS TIME ON
    SET STATISTICS IO ON

    prior to running the queries. This will make SQL Server output IO stats (which are crucial for understanding the query performance).

    Thanks!

    P.S. Just a side note: the model is called “nested sets”. “Nested loops” is a join algorithm used by the optimizer.

    Quassnoi

    28 Oct 12 at 00:24

  4. @Quassnoi: Will do, and thanks for the feedback already.

    I was looking at Client Statistics, not the Server Stats reporting that you showed me here. I’ve re-run and have posted the results below. I thought I was on to something because the client stats made it appear as though my method was faster than it really is. Also, I found a sequence to clear cache, etc which helps to stabilize the results.

    The results in a nutshell;
    1) I didn’t get the AdjList algo down under 1ms per your numbers, but it is still the fastest as you suggest (were you clearing cache each time to get your numbers?),
    2) your Nested Set algo seems to be improved by using the multi-column index I suggested earlier,
    3) my Nested Set algo is unaffected by the extra index,
    4) my Nested Set algo is the slowest of the three options once the new index is applied to your NS algo.

    Here are the details. First, I’ll iterate and label the queries, then I’ll show the sequence I used and the execution times that resulted.

    [Create Table and Single Indexes] resulted in 480k rows.
    ———————————————————————
    No changes from your queries.

    [Clear Cache]
    probably contains some redundancy, or unnecessary bits in my case,
    but I had a hard time finding good references on this topic.
    ———————————————————————
    CHECKPOINT;
    GO
    DBCC DROPCLEANBUFFERS;
    GO
    DBCC FREESYSTEMCACHE(‘ALL’);
    GO
    DBCC FREESESSIONCACHE;
    GO
    DBCC FREEPROCCACHE;
    GO

    [Create Multi Index] Created 1 multi column index.
    ———————————————————————
    CREATE NONCLUSTERED INDEX IX_hierarchy_lft_rgt ON [20090925_nested].t_hierarchy (lft,rgt) include (id,stuffing);

    [AA ExpExt NS] All ancestors from Explain Extended, Nested Set model.
    Modified only to accomodate smaller number of rows in table.
    ———————————————————————
    SELECT hp.id, hp.parent, hp.lft, hp.rgt, hp.data
    FROM [20090925_nested].t_hierarchy hc
    JOIN [20090925_nested].t_hierarchy hp
    ON hc.lft BETWEEN hp.lft AND hp.rgt
    WHERE hc.id = 450000
    ORDER BY hp.lft

    [AA Simple NS] All ancestors with simple, Nested Set model.
    ———————————————————————
    DECLARE @clft INT; DECLARE @crgt INT;
    select @clft=lft, @crgt=rgt from [20090925_nested].t_hierarchy where id=450000;
    select id, parent, lft, rgt, data from [20090925_nested].t_hierarchy where lft <=@clft and rgt >=@crgt order by lft;

    [AA ExpExt AdjList] All ancestors with Explain Extended, Adjacency List model.
    Modified only to accomodate smaller number of rows in table.
    ———————————————————————
    WITH q AS
    (
    SELECT h.*, 1 AS level
    FROM [20090925_nested].t_hierarchy h
    WHERE id = 450000
    UNION ALL
    SELECT hp.*, level + 1
    FROM q
    JOIN [20090925_nested].t_hierarchy hp
    ON hp.id = q.parent
    )
    SELECT id, parent, lft, rgt, data
    FROM q
    ORDER BY level DESC

    Sequence with times : Execution Elapsed Time
    ————————————————–
    [Create Table and Single Indexes]
    [Clear Cache]
    [AA ExpExt AdjList] : 11m
    [Clear Cache]
    [AA ExpExt NS] : 1722m
    [Clear Cache]
    [AA Simple NS] : 621m (2m + 619m)

    [Create Multi Index]
    [Clear Cache]
    [AA ExpExt AdjList] : 12m
    [Clear Cache]
    [AA ExpExt NS] : 306m
    [Clear Cache]
    [AA Simple NS] : 607m (2m + 605m)

    So clearly not what I had originally thought, but still good as an exercise to show that Nested Sets can still play in the game. IMHO they are a more simplistic way of thinking about the problem, and the queries are “more straightforward”. But one cannot discount the performance difference, which would only compound as we increase the number of layers in the hierarchy.

    If you could comment a little more on how your setup achieved the 0-1ms response time on the AdjList query, I would appreciate that.

    thanks for your feedback and your great work on Explain Extended,
    Mike

    Mike Tallroth

    4 Nov 12 at 21:57

  5. Hi Quassnoi,

    thank you for the great explanation. I’ve tested it and found one issue concerning the wrong indexes which gave me a tremendous bost because of avoiding expensive key lookups.

    CREATE INDEX IX_hierarchy_parent ON [20090925_nested].t_hierarchy (parent) INCLUDE (stuffing);
    CREATE INDEX IX_hierarchy_lft ON [20090925_nested].t_hierarchy (lft) INCLUDE (stuffing);
    CREATE INDEX IX_hierarchy_rgt ON [20090925_nested].t_hierarchy (rgt) INCLUDE (stuffing);

    When I run both examples with id = 42 together the costs are separated by

    97% for the “nested set”
    03% for the adjacency list

    I was really impressed of the difference because I expected a really bad performance when using CTE ;)

    @Mike,
    you don’t have to put Id to the index because it is the PK and – because not explicit disabled – the clustered key. Keep in mind that the cl is ALWAYS part of any NC-index!

    Uwe Ricken

    10 Mar 13 at 13:47

Leave a Reply