Database branching: three-way merge for schema changes

You may be familiar with Git's three-way merge as a way to resolve source code changes made by developers on their independent branches. PlanetScale offers three-way merge for your schema branches, making schema change collaboration simpler and safer. It's similar in concept, but completely different in implementation. In the remainder of this post, we illustrate the technical implementation and the nuances of diffing schemas vs. diffing code.

What does it mean to merge schema changes in the first place?

PlanetScale offers a model of schema branching and deploy requests. In short, a developer may branch the main database, creating a copy of the schema in a dev environment, where they are free to make any changes without affecting production. Multiple developers can do the same, concurrently. At some point, the developer wants to apply their schema changes to production. They create a deploy request on PlanetScale, similar to a pull request on GitHub.

The deploy request is where the developer and their team review the changes. The deploy request page presents a semantic diff of the changes made — e.g., an ALTER TABLE foo ..., a CREATE TABLE bar (...), etc. PlanetScale uses Vitess's schemadiff library to generate the semantic diff between the main (production) branch and the developer's branch. If approved, the changes are enqueued in the deploy queue, to be eventually deployed in a non-blocking fashion.

The case for three-way merge arises when multiple developers do the same, concurrently. Say Dev 1 created a branch a couple of days ago. During this time, Dev 2 created and deployed their own branch, merging it into main, the production branch. Dev 1's branch and changes now may or may not be compatible with main. Not only do they not reflect or contain the new schema in main, but they may also outright conflict with the newly made changes!

As long as Dev 1 still works on their branch, that's fine. But at some time, they will want to deploy their changes. It's time to put their changes in the deployment queue. But, are the changes at all valid? This is where three-way merge is invoked. It is essentially a mechanism that determines whether branches slated to be merged conflict with one another, overlap one another, or are completely unrelated and have no impact on one another.

Setting the database branching terminology

In Git, we use terminology such as merge-base, topic-head, etc. But we now illustrate a solution tailored to schema changes, and we may as well use different terminology. Let's use main for production: this is what everyone branches from and eventually deploys to. And let's use branch1 and branch2 as branch names created by Dev 1 and Dev 2, respectively.

It's worth pointing out that nothing tracks the changes on a development branch while it's open. Dev 1 may CREATE, ALTER and, DROP all they want. PlanetScale follows up on any changes they make, but, simplified for the purposes of this post, it's only when the developer creates a deployment request that PlanetScale examines their schema to compute the diff in their branch. The diff is one or more SQL statements (we ignore the case where the schema is unchanged here) that would get main to look like branch1. For example, consider these schemas in main and in branch1:

-- main:
CREATE TABLE `customer` (
	`id` int,
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);

The git diff of the two would be:

 CREATE TABLE `customer` (
        `id` int,
+       `name` varchar(255) NOT NULL DEFAULT '',
        PRIMARY KEY (`id`)
 );

But that's not something a database can work with. Instead, the deploy request generates this semantic SQL diff:

ALTER TABLE `customer` ADD COLUMN `name` varchar(255) NOT NULL DEFAULT ''

This semantic diff is generated for any deploy request.

Schema three-way merge

Assume main is the base branch, and branch1 and branch2 are both enqueued to deploy.

Three-way merge compares the two branches and uses main (hence, three branch comparison) like so:

1. 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.
2. Likewise, compute diff2 as diff(main, branch2).
3. Look at diff1(diff2(main)). If running diff1 over diff2(main) is invalid (examples to follow), there's a conflict.
4. Likewise, attempt diff2(diff1(main)). If that's invalid, there's a conflict.
5. If both are valid but diff1(diff2(main)) != diff2(diff1(main)), there is a conflict.
6. If both are valid and diff1(diff2(main)) == diff2(diff1(main)), there is no conflict between the two branches.

The algorithm is, in fact, more elaborate. But let's first walk through a few examples to understand how the diffs and three-way-merge work, and what SQL nuances we might hit.

Example: no conflict

Consider this simplified schema for the three branches:

-- main:
CREATE TABLE `customer` (
	`id` int,
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);


-- branch2:
CREATE TABLE `customer` (
	`id` int,
	PRIMARY KEY (`id`)
);
CREATE TABLE `delivery` (
	`id` int,
	`customer_id` int,
	PRIMARY KEY (`id`)
);

The diffs are:

-- diff1:
ALTER TABLE `customer` ADD COLUMN `name` varchar(255) NOT NULL DEFAULT ''


-- diff2:
CREATE TABLE `delivery` (
	`id` int,
	`customer_id` int,
	PRIMARY KEY (`id`)
)

Clearly, the two branches do not conflict with one another. One adds a column to customer, and the other creates delivery table. Applying the two diffs in either order ends up with the same end result:

CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);
CREATE TABLE `delivery` (
	`id` int,
	`customer_id` int,
	PRIMARY KEY (`id`)
);

Example: clear conflict

In the next example, both branches introduce a new column under the same name but with a different type:

-- main:
CREATE TABLE `customer` (
	`id` int,
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`subscription_type` enum('free', 'promotional', 'paid'),
	PRIMARY KEY (`id`)
);


-- branch2:
CREATE TABLE `customer` (
	`id` int,
	`subscription_type` int unsigned NOT NULL DEFAULT 0,
	PRIMARY KEY (`id`)
);

The diffs are:

-- 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

Clearly, applying both diffs on top of each other is destined to fail. You cannot add two columns under the same name.

Example: subtle conflict

How about adding two completely different columns?

CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`subscription_type` enum('free', 'promotional', 'paid'),
	PRIMARY KEY (`id`)
);


-- branch2:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	PRIMARY KEY (`id`)
);

The diffs are:

-- diff1:
ALTER TABLE `customer` ADD COLUMN `subscription_type` enum('free', 'promotional', 'paid')


-- diff2:
ALTER TABLE `customer` ADD COLUMN `joined_at` timestamp NOT NULL DEFAULT current_timestamp()

It's possible to apply both diffs, in any order. However, the resulting schema looks different depending on the order. It may look either:

-- diff1(diff2(main)):
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	`subscription_type` enum('free', 'promotional', 'paid'),
	PRIMARY KEY (`id`)
);


-- diff2(diff1(main)):
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`subscription_type` enum('free', 'promotional', 'paid'),
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	PRIMARY KEY (`id`)
);

The order of columns in a table matters. Queries that run a SELECT * FROM customer and use positional arguments will get different columns at positions 3 and 4. The two branches conflict with each other. This is similar to a Git merge conflict where two branches append different rows to the end of a file.

We could avoid the conflict if one of the branches positioned the new column anywhere but last. For example:

CREATE TABLE `customer` (
	`id` int,
	`subscription_type` enum('free', 'promotional', 'paid'),
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);

The above would lead to a non-conflicting diff:

-- diff1:
ALTER TABLE `customer` ADD COLUMN `subscription_type` enum('free', 'promotional', 'paid') AFTER `id`

Nuance: no conflict

The same cannot be said for index changes. We now add a column and a matching index in one migration, and another index in the second migration:

-- main:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`),
	KEY `name_idx` (`name`(16))
);


-- branch2:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	PRIMARY KEY (`id`),
	KEY `joined_idx` (`joined_at`)
);

The diffs are:

-- diff1:
ALTER TABLE `customer` ADD KEY `name_idx` (`name`(16))


-- diff2:
ALTER TABLE `customer` ADD COLUMN `joined_at` timestamp NOT NULL DEFAULT current_timestamp(), ADD KEY `joined_idx` (`joined_at`)

Strictly speaking, the table structure looks different based on the order we apply the diffs. It can be either of:

-- diff1(diff2(main)):
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	PRIMARY KEY (`id`),
	KEY `joined_idx` (`joined_at`),
	KEY `name_idx` (`name`(16))
);


-- diff2(diff1(main)):
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	`joined_at` timestamp NOT NULL DEFAULT current_timestamp(),
	PRIMARY KEY (`id`),
	KEY `name_idx` (`name`(16)),
	KEY `joined_idx` (`joined_at`)
);

However, for practical purposes, the order of indexes is inconsequential. All queries against the table will both behave in the exact same way, as well as perform in the same way, irrespective of the ordering of the keys. The only change is the output of SHOW CREATE TABLE as well as INFORMATION_SCHEMA introspection.

PlanetScale disregards index ordering.

Overlapping changes

The algorithm is more elaborate than described thus far. To reduce developer friction as much as possible, it also considers identical, partial overlap between diffs. For example:

-- main:
CREATE TABLE `customer` (
	`id` int,
	PRIMARY KEY (`id`)
);


-- branch1:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);
CREATE TABLE `tbl1` (
	`id` int,
	PRIMARY KEY (`id`)
);


-- branch2:
CREATE TABLE `customer` (
	`id` int,
	`name` varchar(255) NOT NULL DEFAULT '',
	PRIMARY KEY (`id`)
);
CREATE TABLE `tbl2` (
	`id` int,
	PRIMARY KEY (`id`)
);

Both branches create the same name column on customer, and then each branch proceeds to make other unrelated changes. Thanks to schemadiff, each of the changes (ALTER, CREATE, ...) is fully formalized and we can analyze the changes one by one.

Is there a conflict with the new name column? Given that both branches completely agree on that particular change, PlanetScale's three-way merge considers this as an overlap and allows it. Should branch1 merge first, branch2's diff auto-adapts and is left to the creation of tbl2 only.

Further reducing friction

Schema changes may take time to run, during which more developers will want to deploy their own changes. There is a deployment queue, first come first served, that only allows a single deploy request at a time to run.

When a developer submits their deploy request, their change is validated against all queued changes. This avoids the situation where the developer waits for hours in queue, only to learn the one deployment before theirs caused a conflict. PlanetScale shoots an early warning so that developers can better use their time in queue.

Conclusion

Schema changes and source code changes share enough similarities that we can offer developers schema lifecycle workflows they are familiar with from their source code workflows. With some adaptations to the obvious differences and challenges a schema change deployment poses, we are able to utilize familiar and trusted logic to manage developer collaboration around schema branching.