Going Beyond Three-Way Merge

DoltHub.com is the Version-Controlled Database company. We started with Dolt, a MySQL compatible database. Then we expanded to DoltgreSQL, a PostgreSQL compatible offering. In 2026, we added Doltlite and Dumbo to the mix as well. All of these databases enable users to branch and merge their data, just like they would with source code.

At the basis of all of these products is the three-way merge. The three-way merge is the bread and butter of merge algorithms. It enables two entities to go and edit their source, or data, then join their changes together in a predictable way.

Git’s DAG can lead to some scenarios where there are multiple bases for the three-way merge to start from. The Dolt family of databases has been using the three-way approach since day one, and occasionally users notice what happens when a merge has multiple bases to choose from.

Just reading that may make you scratch your head. What is a “base”, and how can you know what multiple bases are if you don’t know what one is? We’re here to help.

Today we are going to go deep on how Git merges in these more complex situations. It’s worth stating up front that Dolt did not actually behave this way until very recently. We’ll discuss more at the end of this post. Rest assured, Dolt behaves identically to Git in its latest release. Let’s jump in!

Review: Common Three-Way Merging#

To establish a baseline, let’s look at what is hopefully something familiar.

A typical merge starts with taking the two commits which you want to merge, and walking their commit history back to a point in the past where their histories join up. We call this common point the base.

In the example above, when you attempt to merge the feature branch into the main branch, there is an operation called merge-base (docs: git, dolt) which is executed to walk their histories back to their common ancestor. In the diagram above, the 4b2 commit is the only correct answer, and it is the base for the merge.

The intermediary commits, 7d0, 5e8, and 8f6, are not directly used as part of the merge. They drop in significance when evaluating what changed in feature relative to base and what changed in main relative to base, so we simplify for the purposes of the three-way merge, and consider the simpler question, like this.

The example diagram above lets you set the value of a given piece of data, and then you can see if the two sides will merge without error or if a conflict will be generated.

It’s important to recognize that every merge has a granularity: the size of the unit it compares. The three-way merge rule is applied to each unit independently, and conflicts are only possible when both branches change the same unit.

For example, in Git, different files never conflict. If one branch changes foo.txt while the other changes bar.txt, merging them is a non-event. Within a single file, Git works roughly line by line, so edits to separate parts of a file merge cleanly too.

Dolt uses rows in a table as the first granularity. Two different changes which affect two different rows will never conflict. Dolt goes finer than rows: it merges cell by cell in a given row. If one branch changes a customer’s email and the other changes the same customer’s city in the same row of a given table, Dolt takes both changes. A conflict only happens when both branches change the same cell to different values.

The Criss-Cross Merge Conundrum#

The critical requirement in the simple case mentioned above is that it must be simple to determine, unambiguously, what the merge base is for the merge. Unfortunately, this is not always the case.

The classic example is what is called a “criss-cross merge”, and it looks like this.

In this situation, commits 6c2 and 7f0 are both merges of 3a8 and 9b5. It’s easy to imagine how this would happen. Two people are working independently, and they see changes in flight from a peer which are useful to them. They both invoke a merge of the other person’s changes into theirs.

It’s possible that there were no conflicts in the two changes, and they merged cleanly. Equally possible is that there were conflicts, and each person was forced to resolve the conflicts manually. If each person resolved the conflicts identically, it’s all fine. The problem arises when conflicts in those merges are resolved differently.

This is pretty subtle, and also critically important. The important takeaway is that using either of the merge bases highlighted above as the only merge base can produce incorrect results. In the default example, 9b5 happens to get it right, but only because neither resolution matched its value.

I suggest you try some different values in the example above, and select different merge bases to demonstrate how picking the merge base used to perform a three-way merge will alter what is considered a conflict and what is merged “silently”, which you should read as data being quietly altered incorrectly.

To reiterate: neither merge base can be trusted to produce the correct result. When it’s wrong, that means data loss. This is where virtual merge bases come into play!

Virtual Merge Base#

Based on the example above, we can’t choose either of the two merge bases. What Git actually does is create what’s called a “Virtual Merge Base.” This is a temporary commit whose contents will be used as the base for the merge.

The idea behind it is simple. A merge base is supposed to be the state that both sides started from. Both e17 and d4e contain all of 3a8 and all of 9b5, so the honest starting point is the two of them combined. No commit in the history holds exactly that, so we build one.

Building the virtual merge base takes three steps:

1. Merge the merge bases. 3a8 and 9b5 are merged with each other, using the same three-way merge as any other merge. Like any three-way merge, it needs a base of its own: the merge base of 3a8 and 9b5, which is 0d1.
2. Keep everything that merges cleanly. Every cell that 3a8 and 9b5 don’t disagree on gets its merged value, exactly as in a normal merge. This is where the virtual base picks up the changes that both sides of the final merge already share.
3. Mark the cells that conflict. 3a8 set val to 'dog' and 9b5 set it to 'fish', so this inner merge conflicts. Nobody is around to resolve it, and it shouldn’t be resolved anyway: that disagreement is exactly what 6c2 and 7f0 already resolved, each in their own way. Git writes the conflict markers right into the file content of the virtual base. A cell in Dolt can’t hold conflict markers, so Dolt keeps the value from before the disagreement ('cat', from 0d1) as a placeholder and records that the cell is conflicted.

The result never appears on any branch. Git creates it as a temporary commit that nothing points to. Dolt does the same: a dangling commit whose parents are 3a8 and 9b5. Any conflicts from the final merge refer back to it, and Dolt can rebuild it from 3a8 and 9b5 if garbage collection removes it.

Then the real merge happens: an ordinary three-way merge of e17 and d4e, with the virtual merge base as the base. Every cell that wasn’t conflicted works just like any other merge. For a conflicted cell, neither side can ever match the virtual base (in Git, nobody’s file contains those exact conflict markers; in Dolt, the cell is flagged), so both sides count as changed. If 6c2 and 7f0 resolved the conflict the same way, both sides hold the same value and the merge is clean. If they resolved it differently, the merge reports a conflict, and a person decides. Nobody’s resolution is silently thrown away.

The diagram below adds the virtual merge base to the criss-cross from the previous section. The table compares two versions of the virtual base, with and without the flag. Without it, a resolution that happens to equal the placeholder 'cat' looks like “no change”, and the other resolution wins silently.

You may be asking why not simply use the value from 0d1, and instead we “flag” it as conflicting while preserving the original value. The trouble is that 'cat' is a perfectly ordinary value, and someone resolving the conflict might choose it. That is exactly what happens in the default setting of the diagram above: 6c2 resolved the conflict back to 'cat'. Against an unflagged 'cat', the three-way rule concludes that e17 “didn’t change anything”, so 7f0’s 'fish' wins without anyone being asked. The two people who resolved the conflict disagreed, and the merge silently picked one of them.

Git doesn’t have this problem, because the conflict markers it leaves in the virtual base are text nobody would ever commit, so no real resolution can match them. The flag is Dolt’s equivalent: it guarantees that a flagged cell counts as changed on both sides, whatever value the placeholder holds. The placeholder itself is still useful, because every cell needs some value, and it’s what Dolt shows as the base when it reports the conflict. 'cat' is the most honest choice: it’s where the value stood before the merge bases disagreed.

More than Two Merge Bases#

The virtual merge base works in the example above where there are two merge bases to choose from. We can extend this approach to support any number of merge bases.

There are situations where there will be many merge bases. They show up whenever several branches that never merge into each other are all merged into both sides of a merge.

Every additional shared branch that gets merged the same way adds another merge base. In the example below, main and feature both merge two shared branches, schema and lookups, so a merge of main and feature has three merge bases: the fork point plus the tip of each shared branch.

These situations can become complex fast. Ultimately there can be any number of merge bases, and so a solution is required to deterministically create a virtual merge base in these situations.

Git does this in the following way. It walks the DAG and collects all merge bases as a set. Then it orders those commits by their date (this is arbitrary, but deterministic). Finally, if you have N merge bases, they will be merged recursively to create your virtual base:

  V = merge(N, merge(N-1, merge(N-2, ... , merge(1,0))))

For the example above, the three merge bases will be joined like so:

Reading it from left to right: the merge bases are lined up oldest first. The two oldest, 2b7 and 5c3, are merged into a first virtual commit. That result is merged with the next merge base, 6e9, to produce the virtual base, and with more merge bases this continues one at a time. Each of these merges is an ordinary three-way merge, so each one needs a base of its own. Here both happen to have the same one, 1a0, but when that base is ambiguous too, Git builds it the same way, one level down. That is where the recursion comes from. Finally, c5f and e90 are merged with a plain three-way merge, using the virtual base as the base.

Confession#

As I stated above, Dolt until release v2.6.0 has not behaved in the same way as Git. Since our first release years ago, the dolt_merge_base() operation has returned just one merge base, even if there was more than one. This meant that in a criss-cross merge situation, Dolt could produce incorrect results. We suspect this is very rare in practice. Criss-cross merges, and really anything that results in multiple merge bases, are unusual. But with the rise of agents, maybe it’s going to happen more frequently. We did have a customer issue which prompted us to fix this, after all.

This gap has been remedied now. The dolt_merge_bases() table function has been added to mirror the behavior of git merge-base --all, and that allows for finding multiple merge base candidates.

Finally, the dolt_merge() function, and its related friends have all been updated to use the multi-merge-base approach. This ensures that Dolt handles multiple merge bases the same way Git’s default merge strategy does.

If you’d like to talk more about version control, and how your data needs it, come hop on our Discord where me and the dev team hang out every day!