1

In docs, and pretty much everywhere else on the net, to guard against loops in recursive CTEs people use cycle column. The problem with this solution (as opposed to doing the ANY(path) check in join condition directly) is that the loop is detected in the iteration after which it's first encountered.

Is there any reason to favor the first approach as opposed to the second? Is it because you explicitly want that duplicate child row, for some reason, or is there some hidden side effect of the second approach I'm not seeing?

CREATE TEMPORARY TABLE folders (id INT, parent INT) ON COMMIT DROP;
INSERT INTO folders
    (id, parent)
VALUES
    (1, 1);
  1. cycle guard as a column in parent

    WITH RECURSIVE tree (id, path, cycle) AS (
        SELECT
            id,
            ARRAY[id],
            FALSE
        FROM folders
        WHERE id = 1
    
        UNION ALL
    
        SELECT
            c.id,
            tree.path || c.id,
            c.id = ANY(tree.path)
        FROM folders c
        INNER JOIN tree
            ON tree.id = c.parent
        WHERE
            NOT cycle
    )
    SELECT * FROM tree
    

    results in duplicate row (unless we explicitly deduplicate):

    1    "{1}"    false
    1    "{1,1}"  true
    
  2. or as part of the join condition directly

    WITH RECURSIVE tree (id, path) AS (
        SELECT
            id,
            ARRAY[id]
        FROM folders
        WHERE id = 1
    
        UNION ALL
    
        SELECT
            c.id,
            tree.path || c.id
        FROM folders c
        INNER JOIN tree
            ON 
                tree.id = c.parent AND
                NOT c.id = ANY(tree.path)
    )
    SELECT * FROM tree
    

    which does not result in duplicate rows (+ one less iteration):

    1    "{1}"
    

Edit: one possible benefit of solution (1) I'm seeing is when you need to know that there was a loop in the query.

  • So if you need that duplicate row in the result, use a cycle column. In all other cases don't, it's a bit cheaper. – Erwin Brandstetter Dec 30 '18 at 22:54
  • I'm wondering why postgresql docs do it that way, pretty much canonizing it for everyone else to copy. – dwelle Dec 31 '18 at 12:10
  • Probably easier to understand, and the difference in performance is small. – Erwin Brandstetter Dec 31 '18 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.