Skip to content

CONCEPT Cited by 1 source

Diff commutativity check

Definition

The diff commutativity check is the conflict-detection test at the heart of schema three-way merge: given two concurrent semantic schema diffs diff1 and diff2, the branches can be merged without conflict iff composing the diffs in both orders yields an identical, valid result.

Formally, treating each diff as a function from schema to schema, the branches commute iff:

  • diff1(diff2(main)) is valid.
  • diff2(diff1(main)) is valid.
  • diff1(diff2(main)) == diff2(diff1(main)).

All three must hold. Any failure → conflict.

Canonical verbatim framing (Noach, 2023 PlanetScale):

"Compute diff1 as diff(main, branch1). This is similar to main..branch1 in Git notation. We can consider diff1 as a function — i.e., diff1(main) => branch1. Likewise, compute diff2 as diff(main, branch2). Look at diff1(diff2(main)). If running diff1 over diff2(main) is invalid (examples to follow), there's a conflict. Likewise, attempt diff2(diff1(main)). If that's invalid, there's a conflict. If both are valid but diff1(diff2(main)) != diff2(diff1(main)), there is a conflict. If both are valid and diff1(diff2(main)) == diff2(diff1(main)), there is no conflict between the two branches." (Source: sources/2026-04-21-planetscale-database-branching-three-way-merge-for-schema-changes)

Why commutativity is the right test

Two branches can be merged iff applying them in any order produces the same final schema. This is exactly commutativity over diff composition. Three failure modes correspond to three conflict classes:

Mode 1: one composition is invalid

Example: both branches add a column with the same name and different types.

  • diff1: ALTER TABLE customer ADD COLUMN subscription_type enum('free', 'promotional', 'paid')
  • diff2: ALTER TABLE customer ADD COLUMN subscription_type int unsigned NOT NULL DEFAULT 0

diff1(diff2(main)) tries to add subscription_type when it already exists — MySQL rejects it. Conflict.

Mode 2: both valid, results differ

Example: both branches add different columns at the end of a table.

  • diff1: ALTER TABLE customer ADD COLUMN subscription_type enum(…)
  • diff2: ALTER TABLE customer ADD COLUMN joined_at timestamp …

Both compositions succeed. But the resulting column order differs between orderings, and column order matters in MySQL (positional SELECT * semantics). Conflict via column-order conflict.

Mode 3: both valid, results equal

  • diff1: ALTER TABLE customer ADD COLUMN name …
  • diff2: CREATE TABLE delivery …

Disjoint entities. Applying in any order yields the same final schema. No conflict.

Computation via in-memory simulation

The check does not execute DDL against a real database. schemadiff maintains an in-memory representation of the schema and applies each diff statement to it, verifying validity at every intermediate step. The comparison diff1(diff2(main)) == diff2(diff1(main)) is made on the two resulting in-memory schemas.

Policy-layer deviations from pure commutativity

PlanetScale's production implementation is not a pure commutativity check. Two documented exemptions:

  • Index ordering is ignored. Two branches adding different indexes in different orders produce schemas with different index positions (SHOW CREATE TABLE ordering differs) — but query semantics are identical. Policy: treat index order as irrelevant.
  • Identical overlap auto-adapts. If diff1 and diff2 share an identical sub-diff (e.g., both add the same name column), the first merge consumes it and the second branch's remaining diff is re-computed without the shared change. See concepts/diff-overlap-auto-adaptation.

Both deviations relax the commutativity check by treating some non-commuting cases as non-conflicting. Neither deviation tightens it by treating commuting cases as conflicting.

Relationship to Git

Git's three-way merge also performs a kind of commutativity check, but at the line level and with hunks rather than structured operations. The schema version benefits from operating on structured DDL:

  • Equivalence of DDL representation. Two identical ALTER TABLE statements compare equal regardless of formatting.
  • Validity check is type-aware. Column-type mismatches can be detected; textual merge would miss them.
  • Result-comparison is schema-equality. Two schemas are equal iff they have the same tables, columns, indexes, constraints, column ordering, etc. — a much richer comparison than line-by-line file equality.

Algorithmic complexity

The post does not disclose complexity bounds. In the naive implementation, the check is O(|diff1| + |diff2|) statement applications per direction, plus a full schema-equality comparison — roughly linear in the combined size of the two branches' changes against a baseline proportional to schema size.

For large deploy-requests touching many tables, the post observes "resources are not infinite, and only so many changes can run concurrently" — suggesting practical upper bounds exist but are not quantified in the public material.

Seen in

Last updated · 550 distilled / 1,221 read