Dependency Tree Analysis for PostgreSQL Extension Upgrades #

Automating PostgreSQL extension upgrades in production requires deterministic dependency resolution, explicit failure boundaries, and CI/CD-native validation gates. When an extension declares requires in its .control file or relies on shared libraries, implicit upgrade paths break during minor version bumps and platform migrations — a single out-of-order ALTER EXTENSION UPDATE can leave the catalog in a half-migrated state that blocks the entire fleet. Dependency tree analysis is the practice of parsing those declarations, building a directed acyclic graph (DAG), and resolving a provably safe apply order before any DDL touches the database. This page is for DBAs and database SREs who need that resolution to run unattended inside a pipeline rather than as a hopeful manual sequence.

This work sits inside the broader PostgreSQL Extension Architecture & Lifecycle Fundamentals, which governs how control files, shared library loading, and catalog registration behave; understanding those mechanics is a prerequisite for scripting the resolver below.

Resolution Pipeline at a Glance #

Dependency resolution runs as a deterministic, fail-fast pipeline stage before any DDL executes. Every branch that detects a cycle, a missing prerequisite, or a runtime incompatibility exits non-zero and stops the deploy.

Prerequisites #

Before running the resolver, confirm the environment meets these assumptions. The analyzer is deliberately conservative: it fails closed when any prerequisite is unverifiable.

• PostgreSQL version: 12 or newer on every node. pg_available_extension_versions (the source of the requires array) has existed since 9.6, but the regnamespace cast used for schema reporting requires 9.5+, and the transactional semantics assumed by the rollback path are only reliable from 12 onward.
• Python packages: Python 3.8+ with psycopg2-binary (pip install psycopg2-binary). The resolver uses only the standard library plus psycopg2; no ORM or migration framework is required. If your automation stack is asynchronous, the same graph logic ports cleanly to asyncpg — the trade-offs are covered in the driver comparison under ALTER EXTENSION Automation.
• Required privileges: A read-only role is sufficient for static analysis and dry-run. Executing the upgrade sequence requires a role that owns the extensions or holds the privileges each CREATE/ALTER EXTENSION demands — often SUPERUSER for extensions that install C functions. Scope those grants tightly, as described in Security Boundaries & Permissions.
• Catalog state: The staging replica must be catalog-identical to production. Drift between pg_available_extensions on the two nodes is the single most common cause of a resolution that passes staging and fails production; keep the mapping authoritative with Extension Registry Mapping.

Core Concept: Building and Sorting the DAG #

The heart of dependency tree analysis is modeling extensions as nodes and requires declarations as directed edges, then producing a linear apply order that never installs a dependent before its dependency. Two distinct catalog surfaces feed this graph, and conflating them is a classic mistake — the separation between what is available to install and what is currently installed is detailed in Understanding pg_available_extensions vs Installed Extensions.

Prerequisite edges do not live in the free-text comment column. They live in pg_available_extension_versions.requires, a name[] array keyed by extension name and version. Reading requires for the wrong version silently drops transitive edges, so the resolver always joins on default_version.

Why a topological sort, and why Kahn’s algorithm #

A valid apply order is exactly a topological ordering of the DAG. Kahn’s algorithm is preferred over depth-first ordering here for two operational reasons:

1. Cycle detection is free. Kahn’s algorithm repeatedly removes nodes of in-degree zero. If the graph still contains nodes when the queue empties, those nodes form a cycle — the algorithm reports the failure as a byproduct of the sort rather than requiring a separate pass. A cycle in an extension graph (A requires B, B requires A) is unresolvable and must halt the deploy.
2. The order is deterministic and auditable. By seeding the queue in a stable order, the same graph always yields the same apply sequence, which is what lets you diff a dry-run plan across runs and gate on it in review.

The edges point from dependency to dependent (dep -> ext), so a dependency with in-degree zero is applied first, and its dependents become eligible only once it has been emitted.

Step-by-Step Implementation #

The following procedure turns the concepts above into a runnable, dry-run-capable analyzer suitable for CI/CD integration. Each step is complete and copy-pasteable.

Step 1 — Inspect the raw dependency declarations #

Before writing any Python, confirm what the catalog actually reports for your targets. Run this directly against the staging replica:

-- Prerequisite edges for every available extension at its default version.
SELECT e.name,
       e.default_version,
       v.requires AS requires_array
FROM pg_available_extensions e
JOIN pg_available_extension_versions v
  ON v.name = e.name
 AND v.version = e.default_version
WHERE v.requires IS NOT NULL
ORDER BY e.name;

A non-empty requires_array (for example {postgis} on postgis_topology) is a directed edge the resolver must honor. If this query returns rows you did not expect, stop and reconcile the catalog before automating anything.

Step 2 — Capture current installed state #

The installed set determines whether each node needs CREATE EXTENSION or ALTER EXTENSION UPDATE, and it is the baseline you roll back to:

SELECT extname,
       extversion,
       extnamespace::regnamespace::text AS schema
FROM pg_extension
ORDER BY extname;

Step 3 — Run the resolution engine #

This analyzer queries the system catalog, resolves transitive dependencies with Kahn’s algorithm, detects missing or circular references, and exits with explicit status codes for pipeline orchestration.

#!/usr/bin/env python3
"""
PostgreSQL Extension Dependency Tree Analyzer
Designed for CI/CD pre-flight validation and idempotent dry-run execution.
Requires: psycopg2-binary (pip install psycopg2-binary)
"""

import argparse
import sys
import json
from collections import defaultdict, deque
from typing import Dict, List, Set, Tuple, Optional

try:
    import psycopg2
    import psycopg2.extras
    from psycopg2 import sql
except ImportError:
    print("ERROR: psycopg2 is required. Install via: pip install psycopg2-binary", file=sys.stderr)
    sys.exit(2)

def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(description="Resolve PostgreSQL extension dependency trees")
    parser.add_argument("--db-uri", required=True, help="PostgreSQL connection URI (postgresql://...)")
    parser.add_argument("--target-extensions", nargs="+", required=True, help="Extensions to analyze/upgrade")
    parser.add_argument("--dry-run", action="store_true", help="Validate DAG without executing DDL")
    parser.add_argument("--strict-mode", action="store_true", help="Fail on missing optional dependencies")
    return parser.parse_args()

def fetch_catalog_data(conn) -> Tuple[Dict[str, dict], Dict[str, dict]]:
    """
    Returns:
      available: {ext_name: {"default_version": str, "requires": List[str]}}
      installed: {ext_name: {"version": str, "schema": str}}
    """
    with conn.cursor(cursor_factory=psycopg2.extras.RealDictCursor) as cur:
        # Prerequisite extensions live in pg_available_extension_versions.requires
        # (a name[] array), NOT in the free-text `comment` column.
        cur.execute("""
            SELECT e.name, e.default_version, v.requires
            FROM pg_available_extensions e
            JOIN pg_available_extension_versions v
              ON v.name = e.name AND v.version = e.default_version;
        """)
        available = {
            row["name"]: {
                "default_version": row["default_version"],
                "requires": list(row["requires"]) if row["requires"] else []
            }
            for row in cur.fetchall()
        }

        cur.execute("SELECT extname, extversion, extnamespace::regnamespace::text AS schema FROM pg_extension;")
        installed = {
            row["extname"]: {"version": row["extversion"], "schema": row["schema"]}
            for row in cur.fetchall()
        }
    return available, installed

def build_dependency_graph(
    targets: List[str],
    available: Dict[str, dict],
    installed: Dict[str, dict],
    strict: bool
) -> Tuple[Dict[str, List[str]], List[str]]:
    """Constructs a DAG of required extensions and returns missing dependencies."""
    graph = defaultdict(list)
    missing = []
    visited = set()
    queue = deque(targets)

    while queue:
        ext = queue.popleft()
        if ext in visited:
            continue
        visited.add(ext)

        if ext not in available:
            missing.append(ext)
            continue

        graph.setdefault(ext, [])  # register node so standalone targets aren't dropped
        deps = available[ext]["requires"]
        for dep in deps:
            graph[dep].append(ext)
            if dep not in visited:
                queue.append(dep)

    if strict and missing:
        print(f"STRICT MODE FAILURE: Missing dependencies: {', '.join(missing)}", file=sys.stderr)
        sys.exit(1)

    return graph, missing

def topological_sort(graph: Dict[str, List[str]], targets: Set[str]) -> List[str]:
    """Kahn's algorithm for deterministic dependency resolution."""
    in_degree = defaultdict(int)
    for node, neighbors in graph.items():
        if node not in in_degree:
            in_degree[node] = 0
        for neighbor in neighbors:
            in_degree[neighbor] += 1

    queue = deque([n for n in in_degree if in_degree[n] == 0])
    sorted_order = []

    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(sorted_order) != len(in_degree):
        print("ERROR: Circular dependency detected in extension graph.", file=sys.stderr)
        sys.exit(1)

    return [n for n in sorted_order if n in targets or n in graph]

def execute_upgrade_sequence(conn, order: List[str], available: Dict, installed: Dict, dry_run: bool) -> int:
    """Applies CREATE or ALTER EXTENSION UPDATE in dependency-safe order."""
    executed = []
    for ext in order:
        if ext not in available:
            continue

        target_ver = available[ext]["default_version"]
        is_installed = ext in installed
        current_ver = installed[ext]["version"] if is_installed else None

        if is_installed and current_ver == target_ver:
            continue  # Idempotency guarantee: skip if already at target

        if dry_run:
            action = "CREATE EXTENSION" if not is_installed else "ALTER EXTENSION UPDATE"
            print(f"[DRY-RUN] {action} {ext} TO {target_ver}")
        else:
            with conn.cursor() as cur:
                if not is_installed:
                    cur.execute(sql.SQL(
                        "CREATE EXTENSION IF NOT EXISTS {} VERSION {}"
                    ).format(sql.Identifier(ext), sql.Literal(target_ver)))
                else:
                    cur.execute(sql.SQL(
                        "ALTER EXTENSION {} UPDATE TO {}"
                    ).format(sql.Identifier(ext), sql.Literal(target_ver)))
            conn.commit()
            print(f"[EXECUTED] {ext} -> {target_ver}")
        executed.append(ext)

    return 0

def main() -> int:
    args = parse_args()

    try:
        conn = psycopg2.connect(args.db_uri)
        conn.autocommit = False
    except Exception as e:
        print(f"CONNECTION ERROR: {e}", file=sys.stderr)
        return 2

    try:
        available, installed = fetch_catalog_data(conn)
        graph, missing = build_dependency_graph(args.target_extensions, available, installed, args.strict_mode)

        if missing and not args.strict_mode:
            print(f"WARNING: Optional dependencies missing: {', '.join(missing)}")

        # Filter graph to only include targets and their required ancestors
        target_set = set(args.target_extensions)
        resolution_order = topological_sort(graph, target_set)

        print(json.dumps({"status": "resolved", "order": resolution_order, "missing": missing}, indent=2))

        return execute_upgrade_sequence(conn, resolution_order, available, installed, args.dry_run)
    except Exception as e:
        print(f"RESOLUTION ERROR: {e}", file=sys.stderr)
        return 1
    finally:
        conn.close()

if __name__ == "__main__":
    sys.exit(main())

Step 4 — Wire it into the pipeline #

Invoke the analyzer as an isolated stage. Use read-only credentials for the dry-run gate and a privileged connection only for the guarded apply step:

# Gate: resolve and validate with no side effects (read-only role).
python3 resolve_extensions.py \
  --db-uri "postgresql://ci_readonly@staging:5432/appdb" \
  --target-extensions postgis postgis_topology pg_partman \
  --dry-run --strict-mode

# Apply: only reached if the gate above exited 0 (privileged role).
python3 resolve_extensions.py \
  --db-uri "postgresql://deployer@prod:5432/appdb" \
  --target-extensions postgis postgis_topology pg_partman

Dry-Run & Validation Gate #

The --dry-run flag is the safety interlock: it performs the full static analysis, builds the DAG, runs the topological sort, and prints the exact DDL it would execute — without opening a single write transaction. A clean dry-run emits a machine-readable plan your pipeline can archive as a deploy artifact:

{
  "status": "resolved",
  "order": [
    "postgis",
    "postgis_topology",
    "pg_partman"
  ],
  "missing": []
}

Gate the downstream apply step on three conditions before promoting to production:

• Exit code is 0. 1 signals dependency resolution failure (a cycle or, under --strict-mode, a missing required package). 2 denotes a connection or execution error. Only 0 may proceed.
• missing is empty. A non-empty array under a non-strict run is a warning that becomes a hard failure the moment the missing package is actually required by a target.
• The order diff is expected. Store the previous run’s order and fail review if the apply sequence changed unexpectedly — a reordered plan usually means the catalog or a requires declaration drifted. This mirrors the compatibility checks in Extension Upgrade Planning & Compatibility Validation, and for multi-extension fleets it should be reconciled against the Compatibility Matrix Synchronization source of truth.

Failure Modes & Error Taxonomy #

Dependency resolution fails in a small, well-defined set of ways. Each has a distinctive catalog state, log signature, or SQLSTATE, and each maps to a specific recovery action.

When errors cluster during a batch upgrade, route them into a structured classifier rather than eyeballing logs — the taxonomy in Error Categorization Frameworks turns these SQLSTATEs into automated triage signals.

Rollback & Recovery Path #

ALTER EXTENSION UPDATE is not universally transaction-safe. Most catalog-only updates commit and roll back cleanly inside a transaction block, but updates that register background workers, allocate shared memory, or touch shared_preload_libraries take effect at a level that a plain ROLLBACK cannot undo. Design the recovery path around that distinction.

For a transactional update that fails mid-flight, the resolver’s per-extension conn.commit() boundary means only the failed statement is uncommitted — abort and the node is untouched:

-- Fails cleanly for catalog-only updates: the transaction never commits.
BEGIN;
ALTER EXTENSION pg_partman UPDATE TO '5.1.0';
-- verify here; on any doubt:
ROLLBACK;

For a non-transactional update, ROLLBACK is not enough. The deterministic recovery sequence is:

1. Halt dependent workloads so no session writes against the half-migrated extension.
2. Downgrade explicitly with the extension’s shipped downgrade script — ALTER EXTENSION X UPDATE TO '<prior_version>' — if one exists for that hop.
3. Re-register the prior shared library version at the OS layer and restart the node so shared_preload_libraries loads the correct binary.
4. Restore from a verified pre-upgrade snapshot when no downgrade path exists. Take that snapshot as part of the deploy and drive the restore through Snapshot & Point-in-Time Recovery; the automated recovery routing lives under Fallback Routing Strategies.

Because some of these steps require a restart, always capture the pre-upgrade extension version set (Step 2 above) as an artifact — it is the target state your rollback restores to, and pairing it with Version Control & Branching makes every rollback a reproducible, reviewable change.

Performance & Scale Considerations #

Dependency resolution itself is cheap — Kahn’s algorithm is linear in nodes plus edges, and real extension graphs rarely exceed a few dozen nodes. The cost lives entirely in the DDL it schedules.

• Lock contention: CREATE EXTENSION and ALTER EXTENSION UPDATE acquire locks on the objects they modify. For extensions that alter widely-used types or operators, that can block DML briefly. Sequence updates during a low-traffic window and keep each transaction short so lock hold time is bounded.
• Downtime estimates: Catalog-only updates are typically sub-second. Updates that rebuild indexes, rewrite tables, or require a restart to reload shared_preload_libraries are the ones to budget for — measure them on the staging replica and publish the number, then tune the window per Threshold Tuning for Downtime Windows.
• Fleet parallelism: Across a fleet, resolve and dry-run every node in parallel, but apply in a controlled rollout. The resolver is idempotent — it skips any extension already at default_version — so re-running across a partially-upgraded fleet is safe and converges each node toward the target without redoing completed work.
• Staging fidelity: The biggest scale risk is not throughput but topology drift; validate against a replica that mirrors production, as described in Test Environment Routing.

FAQ #

Related Pages #

• Up: PostgreSQL Extension Architecture & Lifecycle Fundamentals
• Understanding pg_available_extensions vs Installed Extensions
• Extension Registry Mapping
• Security Boundaries & Permissions
• Fallback Routing Strategies
• Version Control & Branching