Search code examples
postgresqlquery-optimizationcommon-table-expressionrecursive-query

EXISTS condition in RECURSIVE CTE


I'm trying to use "EXISTS condition in RECURSIVE CTE" to stop recursion, but I get SQL Error [42P19]. PostgreSQL version 13.2. Is there a way to bypass this limitation?

The Sql-query below creates a table with node-parent relationships. I need to build a relative path from any base node to any nested node. Example. Given the input arguments base_id(1) and rel_id(4), the result should be "1/2/4".

If you remove part EXISTS from the query, the result will be correct, BUT if there are 100+ records in depth, this will seriously affect performance.


DROP TABLE IF EXISTS nodes;

CREATE TABLE nodes (
    id INT4
    , parent_id INT4
);

INSERT INTO nodes (
    id, parent_id
) VALUES (
    1, NULL
), (
    2, 1
), (
    3, 1
), (
    4, 2
), (
    5, 4
);

-- get rel path by base id 1 to rel id 4
WITH RECURSIVE r AS (
    SELECT n.id, n.parent_id, CAST(n.id AS VARCHAR) rel_path
    FROM nodes n
    WHERE n.id = 1 -- base
    UNION ALL 
    SELECT n.id, n.parent_id, CONCAT(rel_path, ' / ', n.id) rel_path
    FROM r
    JOIN nodes n ON n.parent_id = r.id
    WHERE NOT EXISTS (
        SELECT *
        FROM r r_sub
        WHERE r_sub.id = 4 -- rel
    )
)
SELECT *
FROM r
WHERE id = 4; -- rel

sandbox rel https://extendsclass.com/postgresql/1a1bc61


Solution

  • You already have r in your query, filter can be simplified to !=. It will not stop alternative paths but you can additionally filter in the outmost select.

    WITH RECURSIVE r AS (
        SELECT n.id, n.parent_id, n.id::text rel_path -- here you need to initiate rel_path
        FROM nodes n
        WHERE n.id = 1 -- base
        UNION ALL 
        SELECT n.id, n.parent_id, CONCAT(rel_path, ' / ', n.id) rel_path
        FROM r
        JOIN nodes n ON n.parent_id = r.id
        WHERE r.id != 4
    )
    SELECT rel_path
    FROM r
    where r.id = 4
    

    Result: 1 / 2 / 4