Resolving Circular Extension Dependencies with Kahn’s Algorithm

How to detect a cycle in a PostgreSQL extension requires graph and produce a safe topological apply order with Kahn’s algorithm — so a batch upgrade never applies a dependent before the dependency it needs.

Up: Dependency Tree Analysis — this page is the concrete cycle-detection and ordering routine that analysis relies on, under the PostgreSQL Extension Architecture & Lifecycle Fundamentals area of the site.

Context & When This Applies

Extensions declare a requires list in their control file, forming a directed graph the server must satisfy before any member installs or updates. Most graphs are clean directed acyclic graphs (DAGs) — postgis_topology requires postgis, which requires nothing — and a topological sort yields the apply order. But partial upgrades, hand-edited control files, and third-party bundles occasionally introduce a cycle, where following requires edges leads back to the start. A cycle has no valid apply order at all, and detecting it before you issue a single ALTER EXTENSION is what separates a clean block from a half-applied cascade. This applies to PostgreSQL 12–17 anywhere you resolve a multi-extension upgrade in code rather than by hand.

Kahn’s algorithm is the right tool because it does both jobs in one pass: it emits a topological order when the graph is a DAG, and it proves a cycle exists when it cannot. That dual result is exactly what a promotion gate needs — an order to execute, or a definitive reason to stop, feeding the compatibility validation pipeline.

Kahn's algorithm: topological order or proof of a cycle Kahn's algorithm computes each node's indegree, then repeatedly removes any node with indegree zero, appending it to the output order and decrementing its neighbours' indegrees. If every node is removed, the output is a valid topological apply order. If nodes still remain when no zero-indegree node exists, those remaining nodes form a cycle and no apply order is possible, so the gate must block. On the left, a clean DAG of address_standardizer to postgis to postgis_topology resolves in order. On the right, a cycle between ext_a and ext_b never reaches indegree zero. DAG → topological order address_standardizer postgis postgis_topology order: standardizer → postgis → topology cycle → block ext_a ext_b neither ever reaches indegree 0

Concept: Indegree Zero Is the Only Safe Starting Point

Kahn’s algorithm rests on one invariant: a node with indegree zero — no unmet requires — is always safe to apply next, because nothing it depends on is still pending. The algorithm computes every node’s indegree, applies (and removes) a zero-indegree node, decrements the indegree of everything that required it, and repeats. Each removal can only create new zero-indegree nodes, never destroy the safety of the order already emitted. When the queue of zero-indegree nodes empties, one of two things is true: every node was emitted (a valid order exists) or some nodes remain (they mutually depend, i.e. a cycle).

That second outcome is the operationally valuable one. A naive recursive install that just follows requires edges will, on a cyclic graph, either infinite-loop or apply a member before its dependency — surfacing later as required extension "x" is not installed. Kahn’s algorithm converts that latent runtime failure into a pre-flight decision with a named culprit: the set of nodes still carrying a positive indegree is the cycle. Pair the ordering output with the version-constraint checks from extension registry mapping so the order you emit is not just dependency-safe but version-valid.

Runnable Implementation

The function below reads the requires graph, runs Kahn’s algorithm, and returns either an apply order or the exact cycle. It reads live requires from pg_available_extension_versions so the graph reflects what this node can actually satisfy.

#!/usr/bin/env python3
"""Topologically order an extension requires-graph, or report the cycle."""
from collections import deque


def kahn_order(requires: dict[str, list[str]]) -> dict:
    """requires maps an extension to the list it depends on (its requires)."""
    # Build indegree: an edge dep -> ext means ext depends on dep.
    nodes = set(requires) | {d for deps in requires.values() for d in deps}
    indegree = {n: 0 for n in nodes}
    adj: dict[str, list[str]] = {n: [] for n in nodes}
    for ext, deps in requires.items():
        for dep in deps:
            adj[dep].append(ext)     # dep must be applied before ext
            indegree[ext] += 1

    # Seed the queue with everything that has no unmet requirement.
    queue = deque(sorted(n for n in nodes if indegree[n] == 0))
    order: list[str] = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for nbr in sorted(adj[n]):
            indegree[nbr] -= 1
            if indegree[nbr] == 0:
                queue.append(nbr)

    if len(order) == len(nodes):
        return {"ok": True, "apply_order": order}
    # Whatever still has a positive indegree is part of a cycle.
    cycle = sorted(n for n in nodes if indegree[n] > 0)
    return {"ok": False, "cycle": cycle,
            "reason": "circular requires dependency; no apply order exists"}


if __name__ == "__main__":
    import json
    dag = {"postgis": ["address_standardizer"],
           "postgis_topology": ["postgis"]}
    print(json.dumps(kahn_order(dag), indent=2))
    bad = {"ext_a": ["ext_b"], "ext_b": ["ext_a"]}
    print(json.dumps(kahn_order(bad), indent=2))

Feed the apply_order into ALTER EXTENSION automation to run each hop in sequence, and route an ok: false result to a hard block — a cycle is never something to retry.

Expected Output & Verification

The DAG resolves; the cyclic graph is caught and named:

{"ok": true, "apply_order": ["address_standardizer", "postgis", "postgis_topology"]}
{"ok": false, "cycle": ["ext_a", "ext_b"], "reason": "circular requires dependency; no apply order exists"}

Verify the emitted order against the live catalog before executing — every dependency must precede its dependents in the list:

-- Ground-truth requires edges this node actually reports.
SELECT name, requires
FROM   pg_available_extension_versions
WHERE  requires IS NOT NULL
ORDER  BY name;

Cross-check that for each row, every entry in requires appears earlier in your apply_order. Record the resolved order alongside the promotion plan in version control and branching so the exact sequence that shipped is auditable.

Edge Cases & Gotchas

A self-loop is a degenerate cycle. A control file that lists itself in requires (through a bad edit) produces a one-node cycle Kahn’s algorithm catches — the node never reaches indegree zero. Treat it identically to a multi-node cycle: block and fix the control file.

A missing dependency is not a cycle — handle it separately. If requires names an extension absent from the node, that node still has a positive indegree at the end and can be misread as a cycle. Before running Kahn’s algorithm, assert every referenced dependency exists in pg_available_extension_versions; a genuinely missing one is a DEPENDENCY_BLOCK for the error categorization framework, not a cycle.

Ordering is not uniqueness. A DAG can have several valid topological orders. Sorting the zero-indegree queue (as above) makes the output deterministic, which matters so the same graph always produces the same reviewable plan — non-deterministic ordering makes diffs meaningless.

The graph must be built per node, not fleet-wide. Because requires is computed from on-disk control files, two nodes can present different graphs after a partial package rollout. Resolve the order on each node from its catalog, exactly as extension registry mapping reconciles, rather than assuming a single global graph.