Skip to content
hgryoo · Docs

PostgreSQL Dependency Tracking — pg_depend, CASCADE, and Deletion Ordering

Contents:

Theoretical Background

Section titled “Theoretical Background”

A relational database is not a flat bag of tables. It is a graph of schema objects — tables reference types, views reference tables, constraints reference columns, indexes reference operator classes, functions reference argument types, sequences are owned by columns, extensions own everything they ship. The moment you allow CREATE to build one object on top of another, you inherit an obligation: when the user asks to DROP something, the system must answer two questions correctly.

  1. Is this drop safe? If other objects still reference the target, removing it would leave dangling references in the catalog — a view whose base table is gone, a function whose argument type no longer exists. The engine must either refuse the drop (RESTRICT) or remove the dependents too (CASCADE).

  2. In what order may the objects be removed? Even once the full set of doomed objects is known, they cannot be deleted arbitrarily. A referencing object must die before — or at least not require — the object it references. This is a topological ordering problem over the dependency graph.

The classic textbook framing comes from the integrity-constraint and referential-integrity literature. Database System Concepts (Silberschatz, Korth, Sudarshan) introduces referential actions — ON DELETE CASCADE, ON DELETE RESTRICT, ON DELETE SET NULL — at the data level (foreign keys between rows). Schema-level dependency tracking is the same idea lifted one level up, from rows to catalog objects: the DDL engine needs its own CASCADE/RESTRICT semantics for the definitions, not just the data. The catalog itself is “just tables,” so the dependency information is naturally stored as a table — a self-describing relation whose rows are edges of the object graph.

The deletion-ordering half is graph theory. The dependency edges form a directed graph; “delete everything reachable from X” is a reachability/closure computation, and “delete in a safe order” is a topological sort of the induced subgraph. The subtlety is that the graph is not a clean DAG: PostgreSQL deliberately permits dependency cycles (a table and its rowtype reference each other; a composite type and its array type form a loop). A naïve topological sort would deadlock on a cycle. The engine therefore distinguishes edge kinds so that cycles can be broken at a designated “weak” edge — the internal dependency that says “these two objects are really one logical thing, drop them as a unit.” Database Internals (Petrov) discusses the catalog/data-dictionary as the metadata layer the rest of the engine consults; dependency tracking is the integrity discipline that keeps that metadata self-consistent across DDL.

A second axis is scope. Most dependencies are local to one database: a view in database app depends on a table in app. But some referenced objects are shared cluster-wide — roles, tablespaces — and live in shared catalogs with no per-database copy. A role owns objects in many databases at once. Tracking “can I drop this role?” therefore requires a separate, cluster-global dependency catalog that every backend, regardless of which database it is connected to, contributes to and consults. This is the pg_depend / pg_shdepend split.

Common DBMS Design

Section titled “Common DBMS Design”

Every SQL engine that supports DROP ... CASCADE solves the same core problems. The patterns below are the shared design space; PostgreSQL’s specific choices in the next section read as selections within it.

Dependency information as a system catalog

Section titled “Dependency information as a system catalog”

The natural home for “object A depends on object B” is a two-sided catalog table whose rows are graph edges: (depender_class, depender_oid, depender_subid) → (referenced_class, referenced_oid, referenced_subid). Because every schema object is addressable by (catalog OID, row OID, optional column number) — an object address — a single edge table can describe dependencies between objects of any type without one column per object kind. The catalog is indexed in both directions: a “depender” index answers “what does A depend on?” (needed when redefining or dropping A’s own links), and a “reference” index answers “what depends on B?” (needed to compute the CASCADE set).

Dependency kinds / strengths

Section titled “Dependency kinds / strengths”

A single edge type is not enough. Engines classify edges by strength:

  • A hard / normal edge means “B must outlive A; if you want to drop B you must explicitly cascade through A.” This is the RESTRICT-guarded edge.
  • A soft / automatic edge means “A only exists for B’s sake; silently drop A when B goes” — e.g. a column default, a serial sequence.
  • An internal / implementation edge means “A is part of B; you may not drop A directly at all — drop B and A goes with it.” This is the edge used to break dependency cycles and to forbid dropping, say, the index that implements a primary-key constraint.

Two-phase traversal: redirect upward, then collect downward

Section titled “Two-phase traversal: redirect upward, then collect downward”

The CASCADE engine cannot simply do a forward closure. If the user aims DROP at an internal sub-component (the auto-created index behind a constraint), the request must be redirected up to the owning object first, so that the whole unit is deleted together and in the right order. So a robust traversal has two phases per node: first scan the node’s own dependencies to detect an owner it must defer to (upward redirection / cycle handling), then scan the inverse edges to find everything that depends on the node and recurse into those (downward collection). The order in which a node is appended to the kill-list — after all its dependents — yields the topological deletion order for free.

RESTRICT vs. CASCADE gate

Section titled “RESTRICT vs. CASCADE gate”

Once the full doomed set is known, a reporting pass decides legality. Objects reached only through soft/internal/automatic edges may always be dropped (they were going to die anyway). Objects reached through a hard edge are the ones RESTRICT forbids: if any such object is in the set and the user did not say CASCADE, the whole DROP aborts with a “other objects depend on it” error that lists the blockers.

Local vs. shared (cluster-wide) dependencies

Section titled “Local vs. shared (cluster-wide) dependencies”

Objects referenced from many databases at once — roles, tablespaces — cannot be tracked in a per-database catalog, because a backend connected to database X cannot see catalog rows stored in database Y. The standard answer is a second, shared dependency catalog stamped with the database OID of each depender, so that DROP ROLE can scan one global table and report “role still owns objects in 3 other databases” without connecting to each.

PostgreSQL’s Approach

Section titled “PostgreSQL’s Approach”

PostgreSQL implements exactly this design with two catalogs and one recursive traversal engine. The local catalog is pg_depend; the cluster-shared catalog is pg_shdepend. The edge endpoints are ObjectAddress triples (classId, objectId, objectSubId) — classId is the OID of the catalog the object lives in (e.g. RelationRelationId for pg_class), objectId is the object’s own OID, and objectSubId is a column number (0 for a whole object).

The dependency kinds

Section titled “The dependency kinds”

The user-facing strengths are an enum of char codes stored in pg_depend.deptype:

// DependencyType — src/include/catalog/dependency.h
typedef enum DependencyType
{
  DEPENDENCY_NORMAL = 'n',          /* hard: RESTRICT-guarded */
  DEPENDENCY_AUTO = 'a',            /* soft: auto-drop with referenced */
  DEPENDENCY_INTERNAL = 'i',        /* A is part of B; drop B, not A */
  DEPENDENCY_PARTITION_PRI = 'P',   /* partition: primary owner */
  DEPENDENCY_PARTITION_SEC = 'S',   /* partition: secondary owner */
  DEPENDENCY_EXTENSION = 'e',       /* A is a member of extension B */
  DEPENDENCY_AUTO_EXTENSION = 'x',  /* auto, but also extension-owned */
} DependencyType;

The mental model:

  • normal (n) — a view’s dependency on the table it selects from, a table column’s dependency on its data type. Dropping the referenced object requires CASCADE.
  • auto (a) — a DEFAULT expression’s pg_attrdef row, owned by its column. When the column dies the default dies silently.
  • internal (i) — the index that implements a UNIQUE/PK constraint depends internally on the constraint. You cannot DROP INDEX it; you must DROP CONSTRAINT, and the traversal redirects a misdirected DROP INDEX up to the constraint.
  • extension (e) — every object a CREATE EXTENSION script builds gets an extension dependency on the pg_extension row, so DROP EXTENSION cascades to all of them. (Covered in depth in postgres-extensions.md.)
  • partition (P/S) — a partition child’s dependency on its parent and on the partitioned-table root; modelled as a pair so the engine can insist you drop a partition link, not orphan a partition.

pg_shdepend.deptype is a different enum — shared dependencies are about ownership and ACLs, not implementation structure:

// SharedDependencyType — src/include/catalog/dependency.h
typedef enum SharedDependencyType
{
  SHARED_DEPENDENCY_OWNER = 'o',       /* referenced role owns object */
  SHARED_DEPENDENCY_ACL = 'a',         /* role appears in object's ACL */
  SHARED_DEPENDENCY_INITACL = 'i',     /* role in pg_init_privs ACL */
  SHARED_DEPENDENCY_POLICY = 'r',      /* role referenced in RLS policy */
  SHARED_DEPENDENCY_TABLESPACE = 't',  /* object lives in tablespace */
  SHARED_DEPENDENCY_INVALID = 0,
} SharedDependencyType;

Recording an edge

Section titled “Recording an edge”

The primitive is recordDependencyOn — depender first, referenced second. It delegates to the batched recordMultipleDependencies, which contains two characteristic optimizations: it skips pinned objects entirely (system objects from bootstrap that can never be dropped, so recording edges to them would waste enormous space), and it multi-inserts in slot batches.

// recordMultipleDependencies — src/backend/catalog/pg_depend.c
for (i = 0; i < nreferenced; i++, referenced++)
{
  /* If the referenced object is pinned by the system, there's no real
   * need to record dependencies on it.  This saves lots of space... */
  if (isObjectPinned(referenced))
    continue;


  /* DROP routines should lock the object exclusively before they check
   * dependencies. */
  dependencyLockAndCheckObject(referenced->classId, referenced->objectId);
  /* ... fill a TupleTableSlot with the 7 pg_depend columns ... */
  slot[slot_stored_count]->tts_values[Anum_pg_depend_deptype - 1] =
    CharGetDatum((char) behavior);
  /* ... batched CatalogTuplesMultiInsertWithInfo when slots fill ... */
}

isObjectPinned is the space-saver: it just asks IsPinnedObject, which consults the hard-coded pin list built at initdb.

// isObjectPinned — src/backend/catalog/pg_depend.c
static bool
isObjectPinned(const ObjectAddress *object)
{
  return IsPinnedObject(object->classId, object->objectId);
}

Most callers do not enumerate edges by hand — they hand an expression tree (a view query, a CHECK constraint, a default) to recordDependencyOnExpr, which walks the node tree, collects every object the expression mentions, de-dups, and records them all at the requested strength:

// recordDependencyOnExpr — src/backend/catalog/dependency.c
context.addrs = new_object_addresses();
context.rtables = list_make1(rtable);
find_expr_references_walker(expr, &context);   /* collect refs */
eliminate_duplicate_dependencies(context.addrs);
recordMultipleDependencies(depender,
               context.addrs->refs, context.addrs->numrefs,
               behavior);

The DROP engine at a glance

Section titled “The DROP engine at a glance”

performDeletion is the single entry point for every dependency-aware DROP. It opens pg_depend once, locks the target, builds the doomed set with findDependentObjects, runs the RESTRICT/CASCADE gate in reportDependentObjects, then deletes the list in order.

flowchart TD
  A["performDeletion(object, behavior, flags)"] --> B["table_open(pg_depend)<br/>AcquireDeletionLock(target)"]
  B --> C["findDependentObjects()<br/>recursive: build targetObjects in safe deletion order"]
  C --> D["reportDependentObjects()<br/>RESTRICT gate + NOTICE 'drop cascades to ...'"]
  D --> E["deleteObjectsInList()<br/>iterate targetObjects front-to-back"]
  E --> F["deleteOneObject() per entry<br/>doDeletion + purge pg_depend + pg_shdepend rows"]
  F --> G["table_close(pg_depend)"]

The key invariant, stated in the header comment of findDependentObjects, is that an object’s dependencies are placed into targetObjects before the object itself — so iterating the finished array front-to-back is a valid deletion order. The recursion appends each node only after recursing into everything that depends on it.

Two-phase traversal and cycle breaking

Section titled “Two-phase traversal and cycle breaking”

findDependentObjects does the redirect-up / collect-down dance per node. Phase one scans the node’s own pg_depend rows (depender index) to find an internal/extension “owner” it must defer to. If found at the outermost level, the drop is illegal and is redirected; if found while recursing from the owner, it is allowed.

flowchart TD
  N["visit object"] --> S{"already on stack<br/>or in targetObjects?"}
  S -->|yes| R["merge flags, return<br/>(breaks cycles)"]
  S -->|no| P1["Phase 1: scan OWN deps<br/>(depender index)"]
  P1 --> I{"internal/extension<br/>owner found?"}
  I -->|"outer level"| ERR["redirect: recurse into owner<br/>or ERROR if not pending"]
  I -->|"recursing from owner"| OK["allowed, continue"]
  P1 --> P2["Phase 2: scan INVERSE deps<br/>(reference index)"]
  P2 --> SORT["collect dependents,<br/>qsort by OID desc"]
  SORT --> REC["recurse into each dependent"]
  REC --> ADD["append THIS object to targetObjects<br/>(after all dependents)"]

The cycle-breaking trick lives in the DEPENDENCY_INTERNAL case: when the traversal enters a dependency loop at an “owned” object, the internal edge forces it to switch to the “owning” object and start there, so the loop is always broken at the internal edge — never at an arbitrary point. The header comment is explicit: “the check for internal dependency below guarantees that we will not break a loop at an internal dependency.”

Source Walkthrough

Section titled “Source Walkthrough”

The code lives in three files: dependency.c (the traversal/deletion engine and the expression walker), pg_depend.c (CRUD on the local catalog plus special-purpose lookups), and pg_shdepend.c (the cluster-shared catalog). We walk them by call-flow.

Recording: pg_depend.c

Section titled “Recording: pg_depend.c”

recordDependencyOn is a one-edge wrapper over the batched recordMultipleDependencies. The batched form is the workhorse — it opens pg_depend with RowExclusiveLock, allocates up to MAX_CATALOG_MULTI_INSERT_BYTES / sizeof(FormData_pg_depend) tuple slots, and for each referenced object skips pins, locks-and-rechecks the referenced object, fills the seven columns, and multi-inserts in batches. The seven columns are the two ObjectAddress triples plus deptype:

// recordMultipleDependencies — src/backend/catalog/pg_depend.c
slot[n]->tts_values[Anum_pg_depend_refclassid - 1]  = ObjectIdGetDatum(referenced->classId);
slot[n]->tts_values[Anum_pg_depend_refobjid - 1]    = ObjectIdGetDatum(referenced->objectId);
slot[n]->tts_values[Anum_pg_depend_refobjsubid - 1] = Int32GetDatum(referenced->objectSubId);
slot[n]->tts_values[Anum_pg_depend_deptype - 1]     = CharGetDatum((char) behavior);
slot[n]->tts_values[Anum_pg_depend_classid - 1]     = ObjectIdGetDatum(depender->classId);
slot[n]->tts_values[Anum_pg_depend_objid - 1]       = ObjectIdGetDatum(depender->objectId);
slot[n]->tts_values[Anum_pg_depend_objsubid - 1]    = Int32GetDatum(depender->objectSubId);

dependencyLockAndCheckObject is the concurrency backstop. Before a row referencing object B is committed, B must not vanish under us. It takes AccessShareLock on B (which conflicts with DROP’s AccessExclusiveLock), then re-verifies B still exists — first via syscache, falling back to a SnapshotSelf scan so that objects created earlier in the same command are visible:

// dependencyLockAndCheckObject — src/backend/catalog/pg_depend.c
if (LockHeldByMe(&tag, AccessShareLock, true))
  return;
LockDatabaseObject(classId, objectId, 0, AccessShareLock);
cache = get_object_catcache_oid(classId);
if (cache != -1 && SearchSysCacheExists1(cache, ObjectIdGetDatum(objectId)))
  return;
/* else SnapshotSelf scan; ERROR "referenced %s was concurrently dropped" */

recordDependencyOnCurrentExtension is how the e edges get planted: if a CREATE EXTENSION is in progress (creating_extension), every extension-capable object created records a DEPENDENCY_EXTENSION edge to CurrentExtensionObject. The pg_depend.c mutators deleteDependencyRecordsFor, changeDependencyFor, and changeDependenciesOf support object redefinition (CREATE OR REPLACE) and rename/reassign by deleting or repointing edges via the depender or reference index.

Lookups: pg_depend.c special queries

Section titled “Lookups: pg_depend.c special queries”

A family of read-only helpers reuse the two indexes for specific questions. getOwnedSequences finds the sequences a column owns (serial/identity), getExtensionOfObject finds which extension owns an object by scanning for the e edge, and get_index_constraint finds the constraint an index internally implements:

// get_index_constraint — src/backend/catalog/pg_depend.c
/* scan pg_depend for the index as depender; the INTERNAL edge to a
 * pg_constraint row is the owning constraint */
if (deprec->refclassid == ConstraintRelationId &&
  deprec->refobjsubid == 0 &&
  deprec->deptype == DEPENDENCY_INTERNAL)
{
  constraintId = deprec->refobjid;
  break;
}

The traversal: findDependentObjects

Section titled “The traversal: findDependentObjects”

This recursive function is the heart of CASCADE. It takes the object to visit, objflags (why we are visiting it), the shared flags, the recursion stack, the accumulating targetObjects, an optional pendingObjects list (for multi-deletions), and the open pg_depend.

It guards recursion two ways before doing work — a stack check (already being visited at an outer level → merge flags and return, which is what breaks cycles) and a targetObjects check (already fully processed):

// findDependentObjects — src/backend/catalog/dependency.c
if (stack_address_present_add_flags(object, objflags, stack))
  return;
check_stack_depth();
if (object_address_present_add_flags(object, objflags, targetObjects))
  return;
if (IsPinnedObject(object->classId, object->objectId))
  ereport(ERROR, ... "cannot drop %s because it is required by the database system" ...);

Phase 1 — redirect up. It scans pg_depend with the depender index (rows where object is the depender) looking for the object’s owner. On an INTERNAL/EXTENSION edge there are three cases, encoded in one switch arm. At the outer level (stack == NULL) the drop is illegal — unless the owner is already in pendingObjects, in which case it bails and lets the pending entry handle it:

// findDependentObjects (Phase 1, INTERNAL case) — dependency.c
if (stack == NULL)
{
  if (pendingObjects &&
    object_address_present(&otherObject, pendingObjects))
  {
    systable_endscan(scan);
    ReleaseDeletionLock(object);
    return;
  }
  /* remember owner; complain after the loop (prefer EXTENSION) */
  if (!OidIsValid(owningObject.classId) ||
    foundDep->deptype == DEPENDENCY_EXTENSION)
    owningObject = otherObject;
  break;
}

When recursing from elsewhere, case 3 redirects the deletion to the owner — releasing the lock on the current object, locking the owner, rechecking the pg_depend tuple is still live, and recursing into the owner with DEPFLAG_REVERSE. This is exactly the cycle-break: the loop is always re-entered at the owning end.

// findDependentObjects (Phase 1, case 3) — dependency.c
ReleaseDeletionLock(object);
AcquireDeletionLock(&otherObject, 0);
if (!systable_recheck_tuple(scan, tup)) { /* owner gone: bail */ }
systable_endscan(scan);
findDependentObjects(&otherObject, DEPFLAG_REVERSE, flags,
           stack, targetObjects, pendingObjects, depRel);

Phase 2 — collect down. After the own-deps scan, it re-scans with the reference index (rows where object is the referenced side) to find direct dependents. Each is locked, rechecked for liveness, classified into a subflags bit, and buffered into dependentObjects. The buffer is then qsort-ed and recursed into — before the current object is appended:

// findDependentObjects (Phase 2) — dependency.c
switch (foundDep->deptype)
{
  case DEPENDENCY_NORMAL:          subflags = DEPFLAG_NORMAL;    break;
  case DEPENDENCY_AUTO:
  case DEPENDENCY_AUTO_EXTENSION:  subflags = DEPFLAG_AUTO;      break;
  case DEPENDENCY_INTERNAL:        subflags = DEPFLAG_INTERNAL;  break;
  case DEPENDENCY_PARTITION_PRI:
  case DEPENDENCY_PARTITION_SEC:   subflags = DEPFLAG_PARTITION; break;
  case DEPENDENCY_EXTENSION:       subflags = DEPFLAG_EXTENSION; break;
}
/* ... buffer dependentObjects[], then: */
if (numDependentObjects > 1)
  qsort(dependentObjects, numDependentObjects,
      sizeof(ObjectAddressAndFlags), object_address_comparator);
/* recurse into each, THEN append self */
add_exact_object_address_extra(object, &extra, targetObjects);

The qsort is not for correctness — any topological order is valid — but for deterministic output, so DROP ... CASCADE notices are stable across runs (important for regression tests). The comparator sorts by OID descending (newest first, usually the right deletion order), then catalog ID, then subId with 0 first:

// object_address_comparator — src/backend/catalog/dependency.c
if (obja->objectId > objb->objectId) return -1;   /* OID descending */
if (obja->objectId < objb->objectId) return 1;
if (obja->classId  < objb->classId)  return -1;
/* subId compared as unsigned so 0 (whole object) sorts first */

The gate: reportDependentObjects

Section titled “The gate: reportDependentObjects”

With targetObjects built, this pass decides legality and emits the “drop cascades to N other objects” message. It walks the list back to front (dependency order, more readable). An object reached via AUTO | INTERNAL | PARTITION | EXTENSION is always droppable; only an object reached purely via a NORMAL edge can trip RESTRICT:

// reportDependentObjects — src/backend/catalog/dependency.c
if (extra->flags & (DEPFLAG_AUTO | DEPFLAG_INTERNAL |
          DEPFLAG_PARTITION | DEPFLAG_EXTENSION))
  ereport(DEBUG2, (errmsg_internal("drop auto-cascades to %s", objDesc)));
else if (behavior == DROP_RESTRICT)
{
  appendStringInfo(&clientdetail, _("%s depends on %s"), objDesc, otherDesc);
  ok = false;
}
else
  appendStringInfo(&clientdetail, _("drop cascades to %s"), objDesc);

If ok is false, it raises ERRCODE_DEPENDENT_OBJECTS_STILL_EXIST (“cannot drop %s because other objects depend on it” + the Use DROP ... CASCADE hint). It also enforces partition integrity: an object flagged DEPFLAG_IS_PART but never reached via a partition edge means the user tried to orphan a partition, which is rejected.

The deletion: deleteOneObject and doDeletion

Section titled “The deletion: deleteOneObject and doDeletion”

deleteObjectsInList iterates targetObjects front-to-back (safe order) calling deleteOneObject on each. deleteOneObject fires the object-drop hook, performs the type-specific deletion via doDeletion, then purges every pg_depend row where this object is the depender, the matching pg_shdepend rows, and comments/seclabels/init-privs — finishing with a CommandCounterIncrement so the next step sees the change:

// deleteOneObject — src/backend/catalog/dependency.c
InvokeObjectDropHookArg(object->classId, object->objectId,
            object->objectSubId, flags);
doDeletion(object, flags);                       /* type-specific drop */
/* purge outgoing pg_depend rows (incoming ones are already gone) */
while (HeapTupleIsValid(tup = systable_getnext(scan)))
  CatalogTupleDelete(*depRel, &tup->t_self);
deleteSharedDependencyRecordsFor(object->classId, object->objectId,
                 object->objectSubId);
DeleteComments(...); DeleteSecurityLabel(object); DeleteInitPrivs(object);
CommandCounterIncrement();

doDeletion is a big switch on classId dispatching to the right catalog-specific routine — this is where dependency tracking hands off to the per-object DDL teardown (postgres-ddl-execution.md):

// doDeletion — src/backend/catalog/dependency.c
switch (object->classId)
{
  case RelationRelationId:      /* index_drop / heap_drop_with_catalog */
  case ProcedureRelationId:     RemoveFunctionById(object->objectId);   break;
  case TypeRelationId:          RemoveTypeById(object->objectId);       break;
  case ConstraintRelationId:    RemoveConstraintById(object->objectId); break;
  case TriggerRelationId:       RemoveTriggerById(object->objectId);    break;
  /* ... ~30 catalog classes ... */
}

The shared catalog: pg_shdepend.c

Section titled “The shared catalog: pg_shdepend.c”

pg_shdepend mirrors pg_depend but for cluster-shared referenced objects (roles, tablespaces) and carries an extra dbid column stamping which database the depender lives in. recordSharedDependencyOn is the primitive; recordDependencyOnOwner is the common wrapper that records a SHARED_DEPENDENCY_OWNER edge to a role:

// recordDependencyOnOwner — src/backend/catalog/pg_shdepend.c
referenced.classId = AuthIdRelationId;
referenced.objectId = owner;
recordSharedDependencyOn(&myself, &referenced, SHARED_DEPENDENCY_OWNER);

changeDependencyOnOwner (used by ALTER ... OWNER TO) drives shdepChangeDep, which finds the single existing owner/tablespace edge and updates it in place — or inserts/deletes depending on whether the new referenced object is pinned. checkSharedDependencies is the DROP ROLE / DROP TABLESPACE gate: it scans pg_shdepend by the reference index, buckets dependers into local/shared/remote, and builds the “role still owns objects in N other databases” detail message that lets the engine refuse the drop without connecting to those databases:

// checkSharedDependencies — src/backend/catalog/pg_shdepend.c
if (sdepForm->dbid == MyDatabaseId || sdepForm->dbid == InvalidOid)
  /* local or shared: add to objects[] for detailed report */;
else
  /* remote: tally per-database count in remDeps list */;

deleteSharedDependencyRecordsFor (called from deleteOneObject) and shdepDropDependency purge a dropped object’s shared edges.

Position hints (as of 2026-06-05, REL_18 273fe94)

Section titled “Position hints (as of 2026-06-05, REL_18 273fe94)”
SymbolFileLine
DependencyType enumsrc/include/catalog/dependency.h31
SharedDependencyType enumsrc/include/catalog/dependency.h78
PERFORM_DELETION_INTERNALsrc/include/catalog/dependency.h92
recordDependencyOnsrc/backend/catalog/pg_depend.c51
recordMultipleDependenciessrc/backend/catalog/pg_depend.c63
recordDependencyOnCurrentExtensionsrc/backend/catalog/pg_depend.c206
deleteDependencyRecordsForsrc/backend/catalog/pg_depend.c314
changeDependencyForsrc/backend/catalog/pg_depend.c470
isObjectPinnedsrc/backend/catalog/pg_depend.c729
dependencyLockAndCheckObjectsrc/backend/catalog/pg_depend.c752
getExtensionOfObjectsrc/backend/catalog/pg_depend.c865
getOwnedSequencessrc/backend/catalog/pg_depend.c1140
get_index_constraintsrc/backend/catalog/pg_depend.c1192
deleteObjectsInListsrc/backend/catalog/dependency.c185
performDeletionsrc/backend/catalog/dependency.c273
performMultipleDeletionssrc/backend/catalog/dependency.c332
findDependentObjectssrc/backend/catalog/dependency.c432
reportDependentObjectssrc/backend/catalog/dependency.c980
deleteOneObjectsrc/backend/catalog/dependency.c1246
doDeletionsrc/backend/catalog/dependency.c1352
AcquireDeletionLocksrc/backend/catalog/dependency.c1496
recordDependencyOnExprsrc/backend/catalog/dependency.c1553
eliminate_duplicate_dependenciessrc/backend/catalog/dependency.c2398
object_address_comparatorsrc/backend/catalog/dependency.c2458
recordSharedDependencyOnsrc/backend/catalog/pg_shdepend.c125
recordDependencyOnOwnersrc/backend/catalog/pg_shdepend.c168
shdepChangeDepsrc/backend/catalog/pg_shdepend.c206
changeDependencyOnOwnersrc/backend/catalog/pg_shdepend.c316
checkSharedDependenciessrc/backend/catalog/pg_shdepend.c676
deleteSharedDependencyRecordsForsrc/backend/catalog/pg_shdepend.c1047

Source verification (as of 2026-06-05)

Section titled “Source verification (as of 2026-06-05)”

All claims above were checked against the working tree at /data/hgryoo/references/postgres, branch REL_18_STABLE, commit 273fe94852b3a7e34fd171e8abdf1481beb302fa (PostgreSQL 18.x).

  • Catalog files exist and own the cited routines. dependency.c (2838 lines), pg_depend.c (1295), and pg_shdepend.c (1759) all carry the IDENTIFICATION banner naming src/backend/catalog/<file>. Every symbol in the position-hint table was located by grep -n at the line shown.

  • The two enums are verbatim. DependencyType ('n' 'a' 'i' 'P' 'S' 'e' 'x') and SharedDependencyType ('o' 'a' 'i' 'r' 't' 0) match src/include/catalog/dependency.h lines 31 and 78. The DEPFLAG_* bitmask (0x0001…0x0100) is defined at the top of dependency.c.

  • The deletion-order invariant is the code’s own contract. The findDependentObjects header comment states “An object’s dependencies will be placed into targetObjects before the object itself; this means that the finished list’s order represents a safe deletion order,” and the function appends add_exact_object_address_extra(object, ...) only after the recursion loop over dependents — confirmed structurally.

  • Cycle breaking via the internal edge is documented in the same function’s comment block (“the check for internal dependency below guarantees that we will not break a loop at an internal dependency”) and implemented in the DEPENDENCY_INTERNAL switch arm that recurses into owningObject with DEPFLAG_REVERSE.

  • The RESTRICT gate lives in reportDependentObjects: the DEPFLAG_AUTO | DEPFLAG_INTERNAL | DEPFLAG_PARTITION | DEPFLAG_EXTENSION test downgrades to DEBUG2, and only DROP_RESTRICT with a NORMAL-only path sets ok = false → ERRCODE_DEPENDENT_OBJECTS_STILL_EXIST.

  • Scope of this doc. Only dependency.c, pg_depend.c, and pg_shdepend.c were treated as authoritative. The per-object teardown routines reached through doDeletion (e.g. heap_drop_with_catalog, RemoveFunctionById) and the ObjectAddress resolution machinery in objectaddress.c are out of scope and deferred to postgres-ddl-execution.md and postgres-system-catalogs.md. No contrib/ code is referenced. Extension membership mechanics are summarized here but detailed in postgres-extensions.md.

Beyond PostgreSQL — Comparative Designs & Research Frontiers

Section titled “Beyond PostgreSQL — Comparative Designs & Research Frontiers”

PostgreSQL’s dependency tracking is one point in a broad design space. Comparing it against other engines and against the research literature sharpens what is essential versus what is a PostgreSQL-specific choice.

Catalog-as-table vs. hard-coded dependency rules

Section titled “Catalog-as-table vs. hard-coded dependency rules”

The defining PostgreSQL choice is to store dependencies as catalog data in pg_depend rather than to encode them in C as per-object-type rules. This is the same self-describing philosophy traced back to System R (Astrahan et al., 1976; captured in research/dbms-papers/systemr.md), whose SYSCATALOG/SYSCOLUMNS catalogs were themselves relations queried through the ordinary access path. The payoff is generality: a new object type (a publication, a statistics object, an access method) participates in CASCADE the moment its CREATE path calls recordDependencyOn — no change to the traversal engine. The cost is that findDependentObjects must run live catalog scans at DROP time, and the dependency graph is only as correct as the discipline of every CREATE path.

Many engines take the opposite tack. Several embedded and historical systems hard-code “dropping a table drops its indexes and triggers” in the DROP TABLE handler, with no general edge catalog. That is simpler and faster for the common case but does not generalize to arbitrary cross-object references (a function used in a CHECK constraint, a type used by a column in another schema), which is precisely the case pg_depend exists to handle.

Deletion ordering as topological sort

Section titled “Deletion ordering as topological sort”

The deletion-order problem is a topological sort of the induced subgraph, and PostgreSQL solves it implicitly: post-order append during DFS yields reverse-topological order, so front-to-back iteration deletes dependents before dependencies. The textbook treatment (e.g. Cormen et al.’s DFS-based topological sort) is the same algorithm; PostgreSQL adds two wrinkles the pure algorithm does not address:

  1. Cycles are legal and must be broken deterministically at the internal edge, not at an arbitrary back-edge. This is why findDependentObjects cannot be a textbook acyclic topo-sort — it needs the redirect-to-owner logic.

  2. Determinism for testability. The qsort by OID-descending in the dependent-collection phase is purely to make DROP CASCADE output reproducible. Most topological-sort formulations are indifferent to ties; a production catalog engine that ships a regression suite is not.

Strength-typed edges vs. uniform edges

Section titled “Strength-typed edges vs. uniform edges”

PostgreSQL’s four-plus dependency strengths (normal/auto/internal/ extension, plus partition pri/sec and auto-extension) are richer than the binary “RESTRICT vs CASCADE referential action” of the SQL standard’s data-level foreign keys. The closest standard analogue is the schema object behavior in SQL:2016’s DROP ... RESTRICT|CASCADE, but the standard does not specify an internal strength — the notion that two catalog objects are one logical unit and one may not be dropped without the other. That concept is what lets PostgreSQL forbid DROP INDEX on a constraint-backing index while still cascading correctly; it is an implementation necessity born of representing one logical object (a primary key) as several catalog rows (a pg_constraint plus a pg_class index plus pg_attribute columns).

Shared/global dependency tracking

Section titled “Shared/global dependency tracking”

The pg_shdepend split — a second, cluster-wide catalog stamped with dbid — is PostgreSQL’s answer to the fact that roles and tablespaces are visible from every database but their dependents are scattered across per-database catalogs. DROP ROLE would otherwise have to connect to every database to check for owned objects. Database Internals (Petrov) frames the data dictionary as a metadata layer the engine consults; the shared-catalog variant is what happens when that metadata layer must span the isolation boundary between databases in a multi-database cluster. Engines that use one database per server instance (or a global namespace) never face this and need only one dependency catalog.

Research frontiers

Section titled “Research frontiers”

  • Incremental / cached dependency closure. findDependentObjects recomputes the closure from scratch on every DROP. For schema-heavy workloads (thousands of partitions, generated tables), this is repeated graph traversal over the catalog. Research on incremental view maintenance and materialized graph reachability is directly relevant: a maintained transitive-closure index over pg_depend could make DROP CASCADE and RESTRICT checks sublinear, at the cost of maintaining the index on every CREATE/ALTER.

  • Online / concurrent schema change. The dependency engine takes AccessExclusiveLock on every doomed object (AcquireDeletionLock), which serializes DROP against all access. Systems pursuing non-blocking DDL (Google F1’s schema-change protocol; online schema-change tools) must reason about dependency edges under concurrent readers — a problem dependencyLockAndCheckObject’s “referenced object concurrently dropped” recheck only partially addresses.

  • Dependency-graph correctness as an invariant. Because the graph is only as correct as every CREATE path’s discipline, missing or stale pg_depend edges are a class of latent bug (a dropped object leaving a dangling reference). Formal-methods work on catalog-invariant checking — treating “every reference has a recording edge” as a checkable property — would let the engine verify the graph rather than trust it.

Sources

Section titled “Sources”

PostgreSQL source (REL_18_STABLE, commit 273fe94, PG 18.x), under /data/hgryoo/references/postgres:

  • src/backend/catalog/dependency.c — the traversal/deletion engine: performDeletion, performMultipleDeletions, findDependentObjects, reportDependentObjects, deleteOneObject, doDeletion, recordDependencyOnExpr, eliminate_duplicate_dependencies, object_address_comparator, AcquireDeletionLock.
  • src/backend/catalog/pg_depend.c — local-catalog CRUD and lookups: recordDependencyOn, recordMultipleDependencies, recordDependencyOnCurrentExtension, deleteDependencyRecordsFor, changeDependencyFor, dependencyLockAndCheckObject, isObjectPinned, getExtensionOfObject, getOwnedSequences, get_index_constraint.
  • src/backend/catalog/pg_shdepend.c — cluster-shared catalog: recordSharedDependencyOn, recordDependencyOnOwner, shdepChangeDep, changeDependencyOnOwner, checkSharedDependencies, deleteSharedDependencyRecordsFor.
  • src/include/catalog/dependency.h — DependencyType, SharedDependencyType, the PERFORM_DELETION_* flags.

Textbook / paper anchors (under knowledge/research/):

  • Database System Concepts (Silberschatz, Korth, Sudarshan) — research/dbms-general/database-system-concepts.md — referential integrity and CASCADE/RESTRICT referential actions.
  • Database Internals (Petrov) — research/dbms-general/database-internals.md — the data dictionary / catalog as the engine’s metadata layer.
  • System R (Astrahan et al., 1976) — research/dbms-papers/systemr.md — the catalog-as-relation design that PostgreSQL’s pg_depend inherits.

Cross-references (sibling docs in this folder):

  • postgres-system-catalogs.md — ObjectAddress, catalog OIDs, objectaddress.c resolution.
  • postgres-ddl-execution.md — the per-object teardown routines reached through doDeletion.
  • postgres-extensions.md — DEPENDENCY_EXTENSION membership mechanics and CREATE/DROP EXTENSION.