Design question: Single-pass convergence vs eventual convergence?

[asonawalla]

I ran into a behavior that got me curious about the project's design intent.

When adding a new column with a COMMENT ON COLUMN, it takes two plan/apply cycles to converge - the first plan/apply creates the column, the second adds the comment. The comment doesn't appear in the first plan even though it's in the schema file.

This made me wonder: is pgschema designed to be single-pass (like Terraform) or eventual-convergence? Looking at the code, there's clearly effort toward correct ordering - topological sorting for tables/views/types, deferred foreign keys, pre-dropping dependent materialized views. So single-pass seems like the intent, but I couldn't find it stated anywhere.

If single-pass is the goal, the current approach handles it through a mix of hardcoded phase ordering, topological sort within phases, and individual special cases as they're discovered. A dependency graph approach (each operation declares what must exist first) could handle this uniformly and guarantee single-pass by construction - but that's a bigger architectural shift.

Would be very happy to brainstorm some approaches here. I'll submit a patch to fix the column comment case using the current patterns shortly.

[asonawalla]

Another similar ordering problem fixed here: #243

[tianzhou]

Claude code analysis

Multi-Pass Scenarios: Why Single-Pass is Impossible

This document analyzes the multi-pass scenarios in pgschema's diff and plan modules that cannot be converted to single-pass implementations.

1. Pre-Drop Materialized Views (3 phases)

Location: internal/diff/diff.go:1290-1395

The Problem

Phase 1: DROP MATERIALIZED VIEW mv1; -- depends on table t1
Phase 2: ALTER TABLE t1 DROP COLUMN x; -- now safe to modify
Phase 3: CREATE MATERIALIZED VIEW mv1 ... -- recreate with new definition

Why Single-Pass is Impossible

PostgreSQL enforces a hard dependency lock between materialized views and their base tables. When you try to run:

ALTER TABLE t1 DROP COLUMN x;
-- ERROR: cannot drop column x of table t1 because materialized view mv1 depends on it

This is not a pgschema limitation - it's a PostgreSQL enforcement. The database kernel checks pg_depend and blocks the operation.

What Would Break

• Any ALTER TABLE that changes columns used by a materialized view
• Any DROP TABLE with dependent materialized views (without CASCADE)

Theoretical Alternative

Use CASCADE everywhere, but this is dangerous and loses user data.

---

2. Topological Sort with Cycle Breaking (2+ iterations)

Location: internal/diff/topological.go:11-127, 131-222, 244-373

The Problem

Table A has FK → Table B
Table B has FK → Table A

Kahn's algorithm builds a queue of nodes with zero in-degree. When circular dependencies exist:

1. Queue becomes empty (no zero in-degree nodes)
2. But unprocessed nodes remain
3. Must artificially break cycle by setting one node's in-degree to 0
4. Continue processing

Why Single-Pass is Impossible

The definition of "cycle detection" requires knowing the global state of the graph. You cannot know if you're in a cycle until you've tried to process all reachable nodes from the initial zero-degree set.

Initial state:
A (in-degree: 1) ← B references A
B (in-degree: 1) ← A references B

Queue: [] (empty!)
Unprocessed: [A, B]

Single-pass cannot determine: "Are A and B unreachable, or are they in a cycle?"

What Would Break

Any schema with circular FK references (common in self-referential tables like employee.manager_id → employee.id, or mutual references like order ↔ payment).

Alternative Considered

DFS-based topological sort (Tarjan's algorithm) is technically single-traversal, but:

1. Still requires backtracking for cycle detection (not truly "single-pass" in the streaming sense)
2. Cycle handling is more complex
3. Output ordering is less deterministic
4. The current Kahn's implementation is already O(V+E) - no asymptotic improvement

---

3. Deferred Foreign Key Constraints (2 phases)

Location: internal/diff/table.go:391-499, internal/diff/diff.go:1435-1450

The Problem

CREATE TABLE orders (
id INT PRIMARY KEY,
customer_id INT REFERENCES customers(id) -- customers doesn't exist yet!
);
CREATE TABLE customers (
id INT PRIMARY KEY
);

Why Single-Pass is Impossible

PostgreSQL's REFERENCES clause requires the target table to exist at parse time:

CREATE TABLE orders (customer_id INT REFERENCES customers(id));
-- ERROR: relation "customers" does not exist

The Solution (already implemented)

-- Phase 1: Create all tables WITHOUT FK constraints
CREATE TABLE orders (id INT PRIMARY KEY, customer_id INT);
CREATE TABLE customers (id INT PRIMARY KEY);

-- Phase 2: Add FK constraints via ALTER TABLE
ALTER TABLE orders ADD CONSTRAINT fk_customer
FOREIGN KEY (customer_id) REFERENCES customers(id);

What Would Break

Any schema where table A references table B, and B is created after A in topological order.

Theoretical Alternative

PostgreSQL could support "forward declarations" like some languages, but it doesn't. This is a language/database limitation.

---

4. Function-Table Bidirectional Dependencies (3 phases)

Location: internal/diff/diff.go:1407-1456

The Problem

-- Function references table
CREATE FUNCTION get_user_count() RETURNS INT AS $$
SELECT count(*) FROM users; -- needs 'users' table
$$ LANGUAGE SQL;

-- Table references function
CREATE TABLE audit_log (
id INT,
user_count INT DEFAULT get_user_count() -- needs function
);

Why Single-Pass is Impossible

This is a true circular dependency at the SQL execution level:

• Function body references users table → table must exist first
• Table column default references get_user_count() → function must exist first

The Solution (already implemented)

-- Phase 1: Create tables WITHOUT function dependencies
CREATE TABLE users (...);

-- Phase 2: Create functions (can now reference tables)
CREATE FUNCTION get_user_count() ...;

-- Phase 3: Create tables WITH function dependencies
CREATE TABLE audit_log (... DEFAULT get_user_count());

What Would Break

Any schema where:

• Functions use tables in their body (common)
• Tables use functions in CHECK constraints or DEFAULTs (common)

Theoretical Alternative

PostgreSQL could support lazy binding of function references, but it validates at creation time.

---

5. Online Index Replacement (4 steps)

Location: internal/plan/rewrite.go:114-190

The Problem

-- User wants to change index definition
-- Old: CREATE INDEX idx ON t(a);
-- New: CREATE INDEX idx ON t(a, b);

Why Single-Pass is Impossible

CREATE INDEX CONCURRENTLY has PostgreSQL-enforced constraints:

1. Cannot run in a transaction:
   BEGIN;
   CREATE INDEX CONCURRENTLY idx ON t(a);
   -- ERROR: CREATE INDEX CONCURRENTLY cannot run inside a transaction block
2. Is asynchronous - PostgreSQL builds the index in the background while allowing concurrent writes. You must wait for completion before the index is usable.
3. Cannot replace an existing index atomically - there's no CREATE OR REPLACE INDEX.

The Solution (already implemented)

-- Step 1: Create new index with temp name (non-transactional)
CREATE INDEX CONCURRENTLY idx_pgschema_new ON t(a, b);

-- Step 2: Wait for build to complete
SELECT pg_sleep(0.1) WHERE NOT pg_index_is_valid(...);

-- Step 3: Drop old index (now safe)
DROP INDEX idx;

-- Step 4: Rename new to original name
ALTER INDEX idx_pgschema_new RENAME TO idx;

What Would Break

Users would get table locks during index creation (defeating the purpose of online migrations).

Theoretical Alternative

PostgreSQL could support CREATE INDEX CONCURRENTLY ... REPLACE, but it doesn't exist.

---

6. SET NOT NULL Online (4 steps)

Location: internal/plan/rewrite.go:268-318

The Problem

ALTER TABLE t ALTER COLUMN x SET NOT NULL;
-- This acquires ACCESS EXCLUSIVE lock and scans entire table

Why Single-Pass is Impossible

Direct SET NOT NULL has these PostgreSQL behaviors:

1. Acquires ACCESS EXCLUSIVE lock (blocks all reads/writes)
2. Scans entire table to verify no NULLs exist
3. Holds lock for duration of scan

For large tables, this can block the application for minutes/hours.

The Solution (already implemented)

-- Step 1: Add CHECK constraint (instant, no scan)
ALTER TABLE t ADD CONSTRAINT x_not_null CHECK (x IS NOT NULL) NOT VALID;

-- Step 2: Validate constraint (scans table, but allows concurrent reads)
ALTER TABLE t VALIDATE CONSTRAINT x_not_null;

-- Step 3: Set NOT NULL (instant, PostgreSQL trusts the validated constraint)
ALTER TABLE t ALTER COLUMN x SET NOT NULL;

-- Step 4: Drop redundant CHECK
ALTER TABLE t DROP CONSTRAINT x_not_null;

What Would Break

Production systems would experience downtime during column modifications.

Theoretical Alternative

This IS technically single-statement possible (ALTER ... SET NOT NULL), but the 4-step approach is a deliberate design choice for online safety. The "limitation" is self-imposed for operational reasons.

---

Summary

┌─────────────────────────────┬─────────────────────────────────┬───────────────────────┐
│          Scenario           │           Root Cause            │  Type of Limitation   │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ Pre-Drop Materialized Views │ pg_depend enforcement           │ PostgreSQL kernel     │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ Topological Sort Cycles     │ Graph algorithm requirement     │ Mathematical          │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ Deferred FK Constraints     │ Parse-time reference validation │ PostgreSQL parser     │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ Function-Table Dependencies │ Creation-time binding           │ PostgreSQL executor   │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ Online Index Replacement    │ CONCURRENTLY semantics          │ PostgreSQL DDL design │
├─────────────────────────────┼─────────────────────────────────┼───────────────────────┤
│ SET NOT NULL Online         │ Lock acquisition behavior       │ Deliberate design     │
└─────────────────────────────┴─────────────────────────────────┴───────────────────────┘

Key Insight

Five of these six limitations are PostgreSQL-imposed - no code changes in pgschema can work around them. The sixth (SET NOT NULL) is a deliberate trade-off choosing availability over simplicity.

[tianzhou]

@asonawalla we strive single-pass. Only use multi-pass if we have to or it improves readability.

[asonawalla]

@tianzhou gotcha, but just to be clear, when I say single pass, I mean one round of pgschema apply, not necessarily one statement. i.e. the user should not have to plan/apply more than once to get the DB to the desired state. The number of statements a single apply cycle executes shouldn't matter from a UX perspective, but having to plan/apply until "no changes detected" can make automation tricky.

So the main question is: if we run plan after apply and see changes, it means there is a bug, correct? As of right now we've fixed all the ones I've seen so far, but just want to make sure this is the right way to think about the UX.

[tianzhou]

So the main question is: if we run plan after apply and see changes, it means there is a bug, correct? As of right now we've fixed all the ones I've seen so far, but just want to make sure this is the right way to think about the UX.

@asonawalla yes, it would be a bug

[asonawalla]

Sounds good. I do suspect there's some benefit to modeling dependencies explicitly in a DAG structure in the long term, but of course that's an implementation detail. We've addressed all the ordering issues I've seen so far, so feel free to close this issue out.

Thanks again!