Skip to main content

​
Dependency Resolution

Database schema objects have complex interdependencies. A foreign key depends on the referenced table existing. An index depends on its table. A view depends on the tables it queries. pgtofu uses topological sorting to determine the correct execution order.

​
The Dependency Graph

pgtofu builds a directed acyclic graph (DAG) of dependencies: 
                    ┌──────────────┐
                    │  Extensions  │
                    └──────┬───────┘
                           │
              ┌────────────┼────────────┐
              │            │            │
              ▼            ▼            ▼
        ┌──────────┐ ┌──────────┐ ┌──────────┐
        │  Types   │ │ Sequences│ │  Tables  │
        └────┬─────┘ └────┬─────┘ └────┬─────┘
             │            │            │
             └────────────┼────────────┘
                          │
              ┌───────────┼────────────┐
              │           │            │
              ▼           ▼            ▼
        ┌──────────┐ ┌───────────┐ ┌──────────┐
        │ Indexes  │ │Constraints│ │  Views   │
        └──────────┘ └───────────┘ └────┬─────┘
                                        │
                                        ▼
                                 ┌──────────────┐
                                 │  Functions   │
                                 └──────┬───────┘
                                        │
                                        ▼
                                 ┌──────────────┐
                                 │   Triggers   │
                                 └──────┬───────┘
                                        │
                                        ▼
                                 ┌──────────────┐
                                 │  TimescaleDB │
                                 │   Features   │
                                 └──────────────┘

​
Topological Sorting

pgtofu uses Kahn’s algorithm for topological sorting: 
1. Build adjacency list and in-degree count for all nodes
2. Initialize queue with nodes having in-degree 0
3. While queue is not empty:
   a. Dequeue node, add to result
   b. For each dependent of node:
      - Decrement in-degree
      - If in-degree becomes 0, enqueue
4. If result size ≠ total nodes, cycle detected

​
Example

Given these changes:
  • Add table users
  • Add column orders.user_id
  • Add foreign key fk_orders_user (references users)
  • Add index idx_orders_user_id
Dependency graph: 
users ──┬──► fk_orders_user
        │
orders.user_id ──┬──► fk_orders_user
                 └──► idx_orders_user_id
Sorted order:
  1. Add table users
  2. Add column orders.user_id
  3. Add foreign key fk_orders_user
  4. Add index idx_orders_user_id

​
Dependency Categories

​
Explicit Dependencies

Dependencies declared in the schema:
ObjectDepends On
Foreign KeyReferenced table and columns
IndexTable it indexes
TriggerTable and trigger function
ViewTables/views it queries
ConstraintTable it belongs to

​
Implicit Dependencies

Dependencies inferred from object types:
Object TypeMust Come After
TablesExtensions, Types, Sequences
ViewsTables, other Views
FunctionsTypes, Tables
TriggersFunctions, Tables
ConstraintsTables (and referenced tables for FKs)
IndexesTables
HypertablesTables
PoliciesHypertables

​
Type Dependencies

Custom types must be created before columns using them: 
-- Must be created first
CREATE TYPE order_status AS ENUM ('pending', 'shipped');

-- Can only be created after order_status exists
CREATE TABLE orders (
    status order_status NOT NULL
);

​
Creation vs. Deletion Order

​
Creation Order

Objects are created in dependency order (dependencies first): 
1. Extensions
2. Custom Types
3. Sequences
4. Tables (in FK dependency order)
5. Constraints
6. Indexes
7. Views
8. Functions
9. Triggers
10. TimescaleDB features

​
Deletion Order

Objects are deleted in reverse dependency order (dependents first): 
1. TimescaleDB features
2. Triggers
3. Functions
4. Views
5. Indexes
6. Constraints
7. Tables (in reverse FK order)
8. Sequences
9. Custom Types
10. Extensions

​
Handling Foreign Keys

Foreign keys create inter-table dependencies: 
-- These tables reference each other through FKs
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    manager_id INT REFERENCES users(id)  -- Self-reference
);

CREATE TABLE orders (
    id SERIAL PRIMARY KEY,
    user_id INT REFERENCES users(id)
);

CREATE TABLE order_items (
    id SERIAL PRIMARY KEY,
    order_id INT REFERENCES orders(id)
);
pgtofu determines the creation order:
  1. users (no external dependencies)
  2. orders (depends on users)
  3. order_items (depends on orders)

​
Circular Dependencies

Some schemas have circular foreign key references: 
CREATE TABLE departments (
    id SERIAL PRIMARY KEY,
    manager_id INT REFERENCES employees(id)
);

CREATE TABLE employees (
    id SERIAL PRIMARY KEY,
    department_id INT REFERENCES departments(id)
);

​
Detection

pgtofu detects cycles during topological sort. If the sorted result has fewer nodes than the graph, a cycle exists.

​
Resolution Strategies

  1. Deferrable Constraints (recommended):
CREATE TABLE departments (
    id SERIAL PRIMARY KEY,
    manager_id INT
);

CREATE TABLE employees (
    id SERIAL PRIMARY KEY,
    department_id INT REFERENCES departments(id)
);

-- Add deferred FK after both tables exist
ALTER TABLE departments
    ADD CONSTRAINT fk_dept_manager
    FOREIGN KEY (manager_id)
    REFERENCES employees(id)
    DEFERRABLE INITIALLY DEFERRED;
  1. Split Migrations:
  • Create tables without circular FKs
  • Add circular FKs in separate migration

​
View Dependencies

Views can depend on other views: 
CREATE VIEW active_users AS
SELECT * FROM users WHERE status = 'active';

CREATE VIEW active_user_orders AS
SELECT o.* FROM orders o
JOIN active_users u ON o.user_id = u.id;  -- Depends on active_users
pgtofu automatically:
  1. Creates active_users first
  2. Creates active_user_orders second
For drops:
  1. Drops active_user_orders first
  2. Drops active_users second

​
Function Dependencies

Functions may depend on types or other functions: 
-- Type must exist first
CREATE TYPE user_summary AS (id INT, name TEXT);

-- Function uses the type
CREATE FUNCTION get_user_summary(uid INT)
RETURNS user_summary AS $$
    SELECT id, name FROM users WHERE id = uid;
$$ LANGUAGE sql;

​
Graph Implementation

pgtofu uses a generic directed graph implementation: 
type DirectedGraph[T comparable] struct {
    nodes    map[T]bool       // All nodes
    edges    map[T]map[T]bool // node -> dependents
    inDegree map[T]int        // Incoming edge count
}

func (g *DirectedGraph[T]) TopologicalSort() ([]T, error) {
    // Kahn's algorithm
    queue := make([]T, 0)
    result := make([]T, 0)

    // Initialize with nodes having no dependencies
    for node := range g.nodes {
        if g.inDegree[node] == 0 {
            queue = append(queue, node)
        }
    }

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)

        for dependent := range g.edges[node] {
            g.inDegree[dependent]--
            if g.inDegree[dependent] == 0 {
                queue = append(queue, dependent)
            }
        }
    }

    if len(result) != len(g.nodes) {
        return nil, ErrCycleDetected
    }
    return result, nil
}

​
Debugging Dependencies

To understand why changes are ordered a certain way:
  1. Run pgtofu diff to see changes
  2. Check the depends_on field in each change
  3. Trace the dependency chain
Example output: 
{
  "type": "ADD_INDEX",
  "object_name": "idx_orders_user_id",
  "depends_on": ["public.orders", "public.orders.user_id"]
}

​
See Also