Detecting cycles in recursive CTEs for graph data

Carry the visited path in an array column and add child.id != all_(path) to the recursive term, plus a depth ceiling as a backstop — a recursive CTE over data containing a cycle produces rows until a statement timeout or the disk stops it. This guide belongs to common table expressions, CTEs and recursive queries.

Quick Answer

A recursive CTE has no built-in termination condition: it stops when the recursive term produces no new rows. A cycle guarantees that never happens.

Before — a traversal that hangs on cyclic data:

from sqlalchemy import literal, select
from sqlalchemy.orm import aliased

from tasks.models import Task

base = (
    select(Task.id, Task.depends_on_id, literal(0).label("depth"))
    .where(Task.id == root_id)
    .cte("chain", recursive=True)
)
child = aliased(Task)
chain = base.union_all(
    select(child.id, child.depends_on_id, base.c.depth + 1)
    .join(base, child.depends_on_id == base.c.id)
)
# With A → B → C → A in the data, this produces rows forever.
# canceling statement due to statement timeout — after filling temporary space.

After — each row carries the path that reached it:

from sqlalchemy import Integer, all_, cast, func, literal, select
from sqlalchemy.dialects.postgresql import ARRAY, array
from sqlalchemy.orm import aliased

from tasks.models import Task

MAX_DEPTH = 50


def dependency_chain(root_id: int):
    base = (
        select(
            Task.id,
            Task.depends_on_id,
            literal(0).label("depth"),
            cast(array([Task.id]), ARRAY(Integer)).label("path"),
        )
        .where(Task.id == root_id)
        .cte("chain", recursive=True)
    )
    child = aliased(Task)
    return base.union_all(
        select(
            child.id,
            child.depends_on_id,
            base.c.depth + 1,
            func.array_append(base.c.path, child.id),
        )
        .join(base, child.depends_on_id == base.c.id)
        .where(
            child.id != all_(base.c.path),      # the cycle guard
            base.c.depth < MAX_DEPTH,           # the backstop
        )
    )

child.id != all_(base.c.path) renders child.id <> ALL (chain.path), which is true only when the node has not been visited on this branch. The depth ceiling is deliberately redundant: it bounds the query even if the guard is ever wrong.

Execution Context & Async Workflow Integration

A recursive CTE evaluates in rounds. The base term produces the first working set; the recursive term runs against that set to produce the next; the process repeats until a round produces no rows. Everything produced is unioned into the result.

Nothing in that algorithm prevents revisiting a node. With A → B → C → A, round one yields B, round two C, round three A, round four B again — and the working set never empties. PostgreSQL happily produces rows until it exhausts temporary space or hits statement_timeout, and the symptom is a query that "hangs" while consuming CPU and disk.

The fix is to make the recursion remember where it has been. An array column, appended to in each round, gives every row the path that reached it, and <> ALL(path) is the test that refuses to re-enter. Two details make it correct. The path must be per branch, not global — which an array carried in the row gives you for free, while a shared visited set would not. And the comparison has to be <> ALL, not NOT IN against a subquery: the array is a value in the row, not a table.

Two other bounds are worth having regardless.

A depth ceiling costs one comparison and turns a pathological graph into a truncated result rather than a hang. Choose it well above the deepest legitimate path — a dependency graph fifty levels deep is already unusual — and log when it is reached, because hitting it means either very deep data or a guard that is not working.

A server-side statement_timeout is the backstop that protects the database from any query, recursive or not, and is worth setting for the whole request path: connect_args={"server_settings": {"statement_timeout": "5000"}}.

On PostgreSQL 14 and later there is a built-in alternative. The CYCLE clause does what the array does, with less SQL, and marks the row where the cycle closed. SQLAlchemy does not build it, so it is reached through a text fragment:

from sqlalchemy import text

cycle_sql = text("""
    WITH RECURSIVE chain AS (
        SELECT id, depends_on_id FROM tasks WHERE id = :root
      UNION ALL
        SELECT t.id, t.depends_on_id
        FROM tasks t JOIN chain c ON t.depends_on_id = c.id
    ) CYCLE id SET is_cycle USING path
    SELECT id, is_cycle, path FROM chain
""")

Under async none of this changes: the statement is built synchronously and awaited once. What does matter under async is that a hanging recursive query holds a pooled connection for as long as it runs, so an unbounded traversal in a request handler is also a pool-exhaustion risk — the failure described in debugging QueuePool limit reached timeouts.

Resolving Warnings, Errors & Common Mistakes

The duplicate-nodes row is not a bug in the guard — it is the difference between a tree and a graph. In a graph, two paths can legitimately reach the same node, and the path guard only prevents revisiting within one path. When the question is "which nodes are reachable", collapse them and keep the shortest route:

from sqlalchemy import select

chain = dependency_chain(root_id)

reachable = (
    select(chain.c.id, chain.c.depth, chain.c.path)
    .distinct(chain.c.id)
    .order_by(chain.c.id, chain.c.depth)
)

DISTINCT ON with that ordering keeps one row per node, the one found at the smallest depth — a shortest-path result, computed in the database.

The <> versus NOT IN distinction is worth being precise about, because the wrong form fails in a way that looks like it works. base.c.path.contains([child.id]) would test array containment and is also correct on PostgreSQL; child.id.not_in(base.c.path) is not, because not_in expects a set of values or a subquery, not an array column. When in doubt, compile the statement and read the SQL, as in reading EXPLAIN output for a SQLAlchemy query.

Advanced: Reporting the Cycle, Not Just Surviving It

Avoiding a cycle keeps a feature working; finding one is what lets it be fixed. The same query shape does both — the difference is whether the closing edge is discarded or returned.

from sqlalchemy import Integer, all_, cast, func, literal, select
from sqlalchemy.dialects.postgresql import ARRAY, array
from sqlalchemy.orm import aliased

from tasks.models import Task

MAX_DEPTH = 50


def cycles_from(root_id: int):
    """Return the paths that close a cycle, starting from one node."""
    base = (
        select(
            Task.id.label("node"),
            cast(array([Task.id]), ARRAY(Integer)).label("path"),
            literal(False).label("is_cycle"),
        )
        .where(Task.id == root_id)
        .cte("walk", recursive=True)
    )
    child = aliased(Task)
    walk = base.union_all(
        select(
            child.id,
            func.array_append(base.c.path, child.id),
            child.id == all_(base.c.path),        # True when this edge closes a cycle
        )
        .join(base, child.depends_on_id == base.c.node)
        .where(
            func.array_length(base.c.path, 1) < MAX_DEPTH,
            # Stop expanding once a cycle is found, but keep that row.
            base.c.is_cycle.is_(False),
        )
    )
    return select(walk.c.path).where(walk.c.is_cycle.is_(True))

The recursive term no longer filters out the repeating edge; it marks it, and stops expanding past it. The rows that come back are the paths describing each cycle, which is what an error message should contain: task 14 → 27 → 91 → 14 tells a user what to change, while "a cycle was detected" does not.

For validating a whole graph rather than one root, start from every node and let DISTINCT collapse the duplicates — or better, start from nodes that have an incoming edge, since a cycle always includes one:

from sqlalchemy import select

from tasks.models import Task

roots = select(Task.id).where(Task.depends_on_id.is_not(None))

Running that check on a schedule is the third layer of defence, and it matters because data does not only arrive through the write path: bulk imports, manual fixes and restored backups all bypass application validation. A nightly job that reports cycles turns "a page hangs occasionally" into a ticket with the offending path in it.

The write-path check is the first layer, and it is the same traversal asked in reverse: before adding an edge from source to target, verify that source is not reachable from target. For a hierarchy, that is the ancestor check described in modeling self-referential relationships for trees; for a general graph it is this query with the edge's endpoints swapped.

Bounding Cost as Well as Termination

A guard that guarantees termination does not guarantee the query is cheap. A dense graph can produce an enormous number of distinct paths even with no cycles at all — the count grows with the product of out-degrees — so a traversal that terminates can still read millions of rows.

Four techniques keep the cost bounded.

Limit the depth to what the feature needs. A UI that shows three levels of dependencies does not need a full traversal. WHERE depth < 3 in the recursive term stops the work rather than filtering it afterwards, which is the difference between reading a handful of rows and reading the whole component.

Prune on the way down, not on the way up. Any filter that can be applied to the recursive term — only active tasks, only edges of a given type, only the current tenant — reduces every subsequent round. Filtering the final select instead means the rows were produced first:

walk = base.union_all(
    select(child.id, func.array_append(base.c.path, child.id))
    .join(base, child.depends_on_id == base.c.node)
    .where(
        child.id != all_(base.c.path),
        child.status != "archived",          # prunes the frontier, not the result
        child.tenant_id == tenant_id,
    )
)

Index the edge column. Each round joins the frontier to the edge table, so depends_on_id needs an index or every round is a sequential scan. On a self-referential hierarchy this is the same index the children lookup needs anyway.

Materialise for repeated reads. When the same traversal is requested constantly and the graph changes rarely, compute it once — into a closure table, a cached JSON document, or a materialised view refreshed on a schedule — and read that instead. The trade-off is the same one described for stored counter columns: write-time work in exchange for read-time certainty.

Finally, make the cost observable. A recursive query's row count is data-dependent in a way most queries are not, so log the number of rows and the maximum depth reached when it exceeds a threshold. That log line is what tells you a graph is growing pathological before a request times out — and it is much cheaper than discovering it from the pool metrics described in instrumenting and observing async queries.

Frequently Asked Questions

Related

• Common Table Expressions, CTEs and Recursive Queries — The parent guide: CTEs for decomposition and recursion.
• Implementing recursive CTEs for hierarchical data — The traversal this guide makes safe.
• Modeling self-referential relationships for trees — Preventing cycles when the parent is assigned.
• Querying Postgres array columns with any and contains — The array operators the path guard uses.