Is there a way to select Parent IDs in SQL without recursion or looping?

Question

I have a table with the following columns: group_id, parent_id, name

In this table parent_id is the group_id of another record. There is a 1 to N relationship of parents to children. This forms a hierarchy with only one top level group having NULL for a parent_id. There could be an arbitrary amount of depth, but in practice my hierarchy is never more than 20 levels deep.

I would like to retrieve every ancestor (a parent's parent and so on) of a group with a given group_id. I am concerned about the particular way this is returned.

I am using MS SQL 2005, but I am also interested in solutions using other RDBMSs.

I have found some similar questions, but they all seem to break down to recursion, looping or nested sets. I cannot use nested sets, because I cannot change the data structure. I would like to avoid recursion or looping where possible, or at least understand why it is not possible.

Here are some question I found while researching this:

How to select parent ids

Sql recursion without recursion

Answer 1

The operation is inherently looped. Because each node does not have any finite relation to their root, you must traverse in order to discover it.

If, for example, you knew that there was a maximum depth of N then you could create N LEFT OUTER JOINs in a single statement and display the last non-null parent ID returned this way.

The looping requirement is that you simply don't know what N is, and you cannot ask a declarative language like SQL to "figure it out"

Even if you can accomplish it with some built-in method, it will still be a loop or recursion, just obfuscated from you.

Answer 2

If you know exactly how deep your data structure goes, you can just write the code out by hand:

DECLARE
    @parentId1 int
   ,@parentId2 int
   ...
   ,@parentId19 int
   ,@parentId20 int

SELECT
    @parentId1 = parent_id
FROM
    myTable
WHERE
    group_id = <someid>

SELECT
    @parentId2 = parent_id
FROM
    myTable
WHERE
    group_id = @parentId1

And so on. However, this will give you a whole bunch of extra code and won't perform any better than a loop, and it's horribly brittle. Adding a new level to the tree requires you to amend your code, which should be an instant code smell.

Think about it in terms of any other language. You have to perform task X a total of N times, where N is variable. How are you going to go about writing this? You'd use a loop. Now suppose that your data structure is a tree (which is what you've got here). How would you write this? You'd probably use recursion, unless you flatten the recursion into a loop.

The only caveat specific to MSSQL is the fact that, by default, the recursion stack is limited to a depth of 16. You're much better off using loops than recursion in MSSQL.

I'd typically do something like this:

-- Temp table will hold the results starting from the ID of the source item
-- through all its ancestors in ascending order
DECLARE @table TABLE (
    sequence int IDENTITY(1, 1)
   ,group_id int
)

DECLARE @groupId int

SELECT @groupId = <someid>

-- Loop backwards through the group's hierarchy inserting all parent IDs
-- into the temporary table
WHILE @groupId IS NOT NULL
BEGIN
    INSERT INTO @table (
        group_id
    )

    VALUES (
        @groupId
    )

    -- Get the ID of the group's parent ready to loop again
    SELECT @groupId = parent_id
    FROM mutable
    WHERE group_id = @groupId
END

-- Print the results
SELECT group_id
FROM @table

There are probably better ways, but that'll give you all IDs in a form you can manipulate easily, plus they'll be in the correct order.

Answer 3

You can create a temporary table similar to yours and populate it like this:

INSERT INTO #T(group_id, parent_id) SELECT group_id, parent_id FROM Your_Table

Now perform the exact same SQL five times:

INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL

After this, your table now tracks ancestors rather than parents, up to 32 levels of distance. (2^5 = 32 and 32 > 20).

This is one efficient way to compute "transitive closure", although if you add looping instead of just repeating the same INSERT five times, you will not need your assumption about 20 levels any more. You should just stop when the INSERT inserts zero new rows. This kind of looping will help rather than hurt performance as well as the number of iterations will be very small.