The `CYCLE` clause and graphs: avoiding infinite loops

Recursive CTEs work perfectly on trees (hierarchies without cycles). But if your data is a graph (it can have cycles: A → B → A), a recursive CTE goes into an infinite loop until PostgreSQL kills it for OOM or timeout.

PostgreSQL 14+ introduced the CYCLE clause that detects cycles automatically and cuts them off. This capsule shows the problem, the solution, and the difference between DEPTH FIRST and BREADTH FIRST ordering (also PG 14+).

The problem with graphs

Simple schema: users and "follows" (a social network).

CREATE TABLE users (id SERIAL PRIMARY KEY, name VARCHAR(100));
CREATE TABLE follows (
    follower_id INTEGER REFERENCES users(id),
    followed_id INTEGER REFERENCES users(id),
    PRIMARY KEY (follower_id, followed_id)
);

INSERT INTO users (id, name) VALUES (1, 'Alice'), (2, 'Bob'), (3, 'Carol');

-- Alice → Bob, Bob → Carol, Carol → Alice (cycle!)
INSERT INTO follows VALUES (1, 2), (2, 3), (3, 1);

Now we try "all users reachable from Alice":

WITH RECURSIVE reachable AS (
    SELECT followed_id FROM follows WHERE follower_id = 1  -- Alice
    UNION ALL
    SELECT f.followed_id
    FROM follows f
    JOIN reachable r ON f.follower_id = r.followed_id
)
SELECT * FROM reachable;

Infinite loop:

• Iter 1: [2] (Bob)
• Iter 2: [3] (Carol)
• Iter 3: [1] (Alice — back to start)
• Iter 4: [2] (Bob again)
• ...

PostgreSQL eventually kills it for memory or timeout. Not what you want.

Pre-PG14 solution: manual tracking

Before PG 14, you had to keep an array of the visited paths:

WITH RECURSIVE reachable AS (
    SELECT followed_id, ARRAY[follower_id, followed_id] AS path
    FROM follows WHERE follower_id = 1
    UNION ALL
    SELECT f.followed_id, r.path || f.followed_id
    FROM follows f
    JOIN reachable r ON f.follower_id = r.followed_id
    WHERE NOT (f.followed_id = ANY(r.path))  -- skip if already visited
)
SELECT DISTINCT followed_id FROM reachable;

Works but verbose. Every query manual.

PG 14+: the CYCLE clause

WITH RECURSIVE reachable AS (
    SELECT follower_id, followed_id FROM follows WHERE follower_id = 1
    UNION ALL
    SELECT f.follower_id, f.followed_id
    FROM follows f JOIN reachable r ON f.follower_id = r.followed_id
)
CYCLE followed_id SET is_cycle USING path  -- detects cycles in the followed_id column
SELECT followed_id, is_cycle, path FROM reachable;

Syntax: CYCLE col_name SET cycle_col USING path_col

• col_name: the column to track to detect the cycle.
• SET cycle_col: name of the boolean column added to the output (true when it detects a cycle).
• USING path_col: name of the array column with the accumulated path.

Output:

 followed_id | is_cycle |    path
-------------+----------+------------
           2 | f        | {(1,2)}
           3 | f        | {(1,2),(2,3)}
           1 | t        | {(1,2),(2,3),(3,1)}  -- cycle detected

When PostgreSQL sees that followed_id=1 already appeared in path, it marks is_cycle=true and doesn't expand further from that row.

Filtering results without cycles

If you only want the nodes without a loop, filter:

WITH RECURSIVE reachable AS (
    SELECT follower_id, followed_id FROM follows WHERE follower_id = 1
    UNION ALL
    SELECT f.follower_id, f.followed_id
    FROM follows f JOIN reachable r ON f.follower_id = r.followed_id
)
CYCLE followed_id SET is_cycle USING path
SELECT DISTINCT followed_id FROM reachable WHERE NOT is_cycle;

Returns [2, 3] (Bob, Carol) without going back to Alice.

BREADTH FIRST vs DEPTH FIRST

PG 14+ also introduced control over the traversal order:

WITH RECURSIVE descendants AS (
    SELECT id, name, parent_id FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.name, c.parent_id
    FROM categories c JOIN descendants d ON c.parent_id = d.id
)
SEARCH BREADTH FIRST BY id SET ordering
SELECT * FROM descendants ORDER BY ordering;

SEARCH BREADTH FIRST BY id: level by level. Root → all children → all grandchildren → ...

SEARCH DEPTH FIRST BY id: down the leftmost branch first. Root → first child → first grandchild → ... → backtrack.

Visual example

Tree:

A
├── B
│   └── D
└── C
    └── E

BFS: A, B, C, D, E (level by level). DFS: A, B, D, C, E (down each branch).

For a "progressive tree expansion" UI, BFS typically. For "complete a path then the next sibling," DFS.

Combining CYCLE + SEARCH

WITH RECURSIVE x AS (
    ...
)
CYCLE col1 SET is_cycle USING path
SEARCH BREADTH FIRST BY col2 SET ordering
SELECT * FROM x ORDER BY ordering;

Both clauses are combinable. CYCLE for safety, SEARCH for a deterministic order.

Real case: friend recommendations

"Suggest friends of friends without going back to the user":

WITH RECURSIVE friends AS (
    -- My direct friends (depth 1)
    SELECT followed_id, 1 AS depth FROM follows WHERE follower_id = :my_id
    UNION ALL
    -- Friends of friends (depth 2+)
    SELECT f.followed_id, fr.depth + 1
    FROM follows f
    JOIN friends fr ON f.follower_id = fr.followed_id
    WHERE fr.depth < 3  -- limit depth
)
CYCLE followed_id SET is_cycle USING path
-- Friends of my friends, don't go back to me, up to 3 levels
SELECT DISTINCT u.id, u.name, MIN(f.depth) AS distance
FROM friends f
JOIN users u ON u.id = f.followed_id
WHERE NOT f.is_cycle
  AND u.id != :my_id  -- exclude myself
GROUP BY u.id, u.name
ORDER BY distance, u.name
LIMIT 20;

Returns users reachable via friends, with their distance (1=direct, 2=friend of friend, etc.). No loops.

Performance considerations

The CYCLE clause adds overhead (maintaining an array of paths). For small graphs (~1000 nodes), trivial. For huge graphs (millions of edges), consider:

• Limit depth: WHERE depth < N in the recursive case.
• Filter early: add conditions in the recursive case to prune branches.
• Migrate to a graph DB: if the graph is central to the app and it's huge, Neo4j or another graph DB.

A recursive CTE is excellent for small/medium graphs. For massive graphs, a different tool.

Common traps and mistakes

1. Assuming CYCLE is the default.

Without the CYCLE clause, a recursive CTE over a graph goes into an infinite loop. The default is the "no protection" behavior. You have to add it explicitly.

2. CYCLE in a non-recursive CTE.

CYCLE only applies to recursive CTEs. In a normal CTE it makes no sense.

3. Forgetting USING path_col.

CYCLE followed_id SET is_cycle  -- ❌ missing USING

USING path_col is mandatory. It specifies the name of the column that keeps the accumulated path.

4. Expecting BFS behavior without SEARCH.

Without SEARCH BREADTH FIRST, the iteration order isn't strict BFS. PostgreSQL may use another internal strategy. If you need a specific order, declare it.

5. Performance assumption: CYCLE is free.

Maintaining the path array has overhead. For small graphs, negligible. For millions of edges, measurable. Verify with EXPLAIN ANALYZE.

6. Confusing path with path_col.

CYCLE followed_id SET is_cycle USING path  -- 'path' is the name you choose

path is not a reserved word. It's a name you choose for the added column. It could be cycle_path, traversal_path, etc.

7. PG <14.

The CYCLE and SEARCH clauses are PG 14+. On PG 13 or earlier, fall back to manual tracking with an array.

Exercise: detect cycles

Setup:

CREATE TABLE nodes (id SERIAL PRIMARY KEY, name TEXT);
CREATE TABLE edges (
    from_id INTEGER REFERENCES nodes(id),
    to_id INTEGER REFERENCES nodes(id),
    PRIMARY KEY (from_id, to_id)
);

INSERT INTO nodes (id, name) VALUES (1, 'A'), (2, 'B'), (3, 'C'), (4, 'D'), (5, 'E');

-- Graph with a cycle: A → B → C → A, plus D → E independent
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (4, 5);

Step 1: try a traversal without CYCLE — observe (don't run in production!).

-- Only if you have nerves of steel
WITH RECURSIVE x AS (
    SELECT to_id FROM edges WHERE from_id = 1
    UNION ALL
    SELECT e.to_id FROM edges e JOIN x ON e.from_id = x.to_id
)
SELECT * FROM x;
-- Infinite loop — kill it manually

Step 2: with CYCLE.

WITH RECURSIVE x AS (
    SELECT from_id, to_id FROM edges WHERE from_id = 1
    UNION ALL
    SELECT e.from_id, e.to_id FROM edges e JOIN x ON e.from_id = x.to_id
)
CYCLE to_id SET is_cycle USING path
SELECT to_id, is_cycle, path FROM x;

What does it return?

Step 3: filter without cycles.

WITH RECURSIVE x AS (...)
CYCLE to_id SET is_cycle USING path
SELECT DISTINCT to_id FROM x WHERE NOT is_cycle;

List of reachable nodes without a loop.

Step 4: detect WHETHER there's a cycle in the graph (without enumerating everything).

-- Does the graph have any cycle?
WITH RECURSIVE x AS (
    SELECT from_id, to_id FROM edges
    UNION ALL
    SELECT e.from_id, e.to_id FROM edges e JOIN x ON e.from_id = x.to_id
)
CYCLE to_id SET is_cycle USING path
SELECT EXISTS (SELECT 1 FROM x WHERE is_cycle) AS has_cycle;

Step 5: experiment with BFS vs DFS.

WITH RECURSIVE x AS (...)
SEARCH BREADTH FIRST BY to_id SET ord
SELECT to_id, ord FROM x ORDER BY ord;

-- vs

WITH RECURSIVE x AS (...)
SEARCH DEPTH FIRST BY to_id SET ord
SELECT to_id, ord FROM x ORDER BY ord;

Any difference in order?

to_id | is_cycle | path
------+----------+--------
    2 | f        | {(1,2)}
    3 | f        | {(1,2),(2,3)}
    1 | t        | {(1,2),(2,3),(3,1)}

Summary and next step

What you learned:

• The CYCLE clause (PG 14+) detects loops automatically.
• Syntax: CYCLE col SET is_cycle_col USING path_col.
• is_cycle = true marks rows that close a cycle. Filter them out to avoid it.
• SEARCH BREADTH/DEPTH FIRST for a deterministic order.
• PG <14 fallback: manual tracking with an array of paths.
• Performance: small overhead on small graphs, measurable on massive graphs.

In the next capsule we compare the recursive CTE with the alternative: the closure table — pre-computing all the ancestor-descendant relationships. Trade-off: more maintenance, less compute per query. Useful for very stable hierarchies.

Resources

1. PostgreSQL Docs — Recursive Query Cycle Detection — reference.
2. PostgreSQL 14 Release Notes — Cycle detection — when it was added.
3. Crunchy Data — Cycle detection — analysis with cases.

Capsule 04 of 08 — Module 8 — Advanced PostgreSQL for Backend Guide