CTE query that fails to find ancestors

Question

I have a table foo

with the content

So the records of the table foo can graphically be represented with this graph.

When I run a procedure that should return ancestors using @starting_id=9

(represented with a circle in the graph), I get this result

• 9

instead of

• 9
• 3 and
• 1

Why?

CREATE PROCEDURE [dbo].[GetParents]
    @starting_id int
AS
BEGIN
    WITH chainIDsUpwards AS
    (
        SELECT id, parent_id FROM foo WHERE id = @starting_id

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsUpwards p ON p.id = foo.parent_id
    )

    SELECT id FROM chainIDsUpwards
END

Fiddle at https://dbfiddle.uk/?rdbms=sqlserver_2019&fiddle=81be3d86dc7581eb60bc7af4c09077e4

Answer 1

I believe you made a mistake in your join predicate. Try:

WITH chainIDsUpwards AS
    (
        SELECT id, parent_id FROM foo WHERE id = @starting_id

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsUpwards p ON p.parent_id = foo.id
    )

    SELECT id FROM chainIDsUpwards

It is a common mistake, and I often do it myself. I find it easiest to get it right if I start with the CTE:

    SELECT foo.id, foo.parent_id 
    FROM chainIDsUpwards p
    JOIN foo p 

and then think of the CTE as a linked list where I need to find the next element:

        ON p.parent_id = foo.id

Answer 2

I already got advices from others. Let me know if this is correct unrolling.

DECLARE @starting_id int = 9
SELECT id, parent_id FROM foo WHERE id = @starting_id

UNION

SELECT foo.id, foo.parent_id FROM foo INNER JOIN
(
    SELECT id, parent_id FROM foo WHERE id = @starting_id
) p ON p.parent_id = foo.id

UNION

SELECT foo.id, foo.parent_id FROM foo INNER JOIN
(
    SELECT foo.id, foo.parent_id FROM foo INNER JOIN
    (
        SELECT id, parent_id FROM foo WHERE id = @starting_id
    ) p ON p.parent_id = foo.id
) p ON p.parent_id = foo.id

and now its apparent why parent_id and id should be interchanged.