Split, Sort, Collapse: how SQL Server survives an overlapping unique update

One table, one single column, 10,000 contiguous values from 1 to 10,000. We shift everyone up by 1:

UPDATE u SET val = val + 1;

Each new value lands on a value that already exists: 1 wants to become 2, but a 2 is already there; 2 wants to become 3, but a 3 is already there… Every target overlaps a neighboring value. Yet a unique index allows no duplicate, at any instant.
How can this update succeed?

Two tables, one single difference

-- Unique column
CREATE TABLE u (val INT NOT NULL);
CREATE UNIQUE INDEX ux_u ON u(val);
INSERT INTO u (val)
  SELECT TOP (10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
  FROM sys.all_objects a CROSS JOIN sys.all_objects b;

-- Same column, without uniqueness
CREATE TABLE n (val INT NOT NULL);
INSERT INTO n (val) SELECT val FROM u;

The same UPDATE ... SET val = val + 1 on each. Yet the two execution plans differ completely: on n, a direct update, a single modification operator. On u, three unexpected operators appear: Split, Sort, Collapse. That is the entire gap between “any column” and “a unique column”.

Why the naive method doesn’t work

Let’s process u row by row, in ascending order. First row: 1 → 2. But 2 still exists. Two rows carry the value 2: uniqueness is violated immediately. Processing in descending order would get by (10000 → 10001 first, then 9999 → 10000…), but SQL Server can’t bet on the order in which the rows to process are acquired. It needs a method that works regardless of order, and that never lets the same value coexist twice.

Split, sort, collapse

This is the engine’s answer, in three steps. Let’s take five rows with the values 3,4,5,6,7 and follow each step closely.

1. Split (the update becomes delete + insert)

Modifying the key of a unique index directly is risky: the target value may overlap a value that is present. Split works around the problem by decomposing each update into a deletion of the old value followed by an insertion of the new one. Our 5 rows become 10 operations:

DELETE 3     (old value of row #0)
INSERT 4     (new value of row #0)
DELETE 4     (row #1)
INSERT 5
DELETE 5     (row #2)
INSERT 6
DELETE 6     (row #3)
INSERT 7
DELETE 7     (row #4)
INSERT 8

A delete can never fail on uniqueness; an insert fails only if the final value is truly a duplicate. We’ve separated the two risks.

2. Sort (sort to free a value before reoccupying it)

The 10 operations are sorted by the index key. Decisive rule: for equal values, the delete comes before the insert.

DELETE 3
DELETE 4     -- 4 is freed...
INSERT 4     -- ...before being reoccupied
DELETE 5
INSERT 5
DELETE 6
INSERT 6
DELETE 7
INSERT 7
INSERT 8

This is where the overlap is defused. For each value, the old occupant leaves before the new one arrives. At no point do two rows share the same key.

3. Collapse (reduce the intermediate operations)

After sorting, each DELETE k / INSERT k pair for the same value sits adjacent. Collapse fuses each pair into a single in-place update of the existing index entry, rather than deleting and re-inserting it. The two unpaired ends survive as a real delete and a real insert.

DELETE 3          (low end, no partner)
MODIFY 4
MODIFY 5
MODIFY 6
MODIFY 7
INSERT 8          (high end, no partner)

Does the engine really execute it this way? The transaction log settles it.

SELECT Operation, Context, COUNT(*) AS n
FROM sys.fn_dblog(NULL, NULL)
WHERE AllocUnitName LIKE '%ux_u%'
GROUP BY Operation, Context
ORDER BY n DESC;

Result:

Operation            Context               n
LOP_MODIFY_ROW       LCX_INDEX_LEAF        4
LOP_DELETE_ROWS      LCX_MARK_AS_GHOST     1
LOP_SET_BITS         LCX_PFS               1
LOP_INSERT_ROWS      LCX_INDEX_LEAF        1

This result is particularly revealing.

If the five updates had truly been executed as five DELETEs followed by five INSERTs, we would have expected five deletions and five insertions in the log.

Yet what we ultimately observe is:

4x MODIFY_ROW
1x DELETE_ROWS
1x INSERT_ROWS

Collapse is therefore not only a theoretical concept visible in the execution plan. The observations from fn_dblog() show that it translates concretely into a massive reduction of physical operations. The intermediate values are merged into simple index row modifications, while only the two ends of the shift survive as a genuine deletion (3) and a genuine insertion (8).

4. Visualization of the complete SPLIT-SORT-COLLAPSE process

The preceding observations now make it possible to connect the theory to what is actually executed. The following visualization traces the complete sequence of the Split, Sort and Collapse phases, along with the progressive reduction of operations down to the final result observed in the transaction log:

What it costs

The Split / Sort / Collapse mechanism lets SQL Server guarantee uniqueness throughout the entire UPDATE, but this safety comes at a significant cost. To measure this impact, we ran exactly the same update on the two 10,000-row tables created earlier, with STATISTICS IO ON enabled. The results are unambiguous. On table u, SQL Server performed 40,036 logical reads, consumed 266 ms of CPU and 360 ms of elapsed time. On table n, the same operation required only 34 logical reads, 15 ms of CPU and 71 ms of elapsed time.

It’s worth noting that this extra cost corresponds mainly to the logical processing imposed by the uniqueness guarantee. Indeed, our analysis with fn_dblog() shows that the engine does not naively delete and then reinsert each row. After Collapse, the intermediate operations are largely merged into simple MODIFY_ROW operations, which limits the physical work actually performed on the index pages. The price to pay is therefore not so much a full rebuild of the index as a substantial amount of preparatory organization that lets SQL Server guarantee that at no instant do two rows simultaneously hold the same unique key.

A side note about the Halloween Problem

This need to read everything before writing anything has a name. In the mid-1970s, Don Chamberlin, Pat Selinger and Morton Astrahan wrote a query meant to give a 10% raise to every employee earning under $25,000. It ran without error but left everyone at exactly $25,000: the engine scanned the salary index upward, and each raised row crossed the threshold, moved back ahead of the scan, and got raised again. They found it on Halloween, and the name stuck after the day, not the nature of the bug (link).

Their fix was to make sure the optimizer never reads an update through an index built on the very column being updated. Split/Sort/Collapse is a descendant of that idea: when an UPDATE reads and writes the same index, reading and writing must be separated. That’s the Sort’s job. It is a blocking operator: it must consume its entire input before emitting a single row and that property forms the barrier. In doing so it materializes the whole set of rows to modify (in memory via a memory grant or spilling to tempdb if the volume exceeds it). Once that snapshot is frozen, each source row is read exactly once, and no write can ever catch up to it.

Conclusion

Updating a unique key that overlaps itself seems, at first glance, impossible without temporarily violating uniqueness. Yet, thanks to the Split / Sort / Collapse mechanism, SQL Server manages to turn a potentially conflicting operation into a sequence of actions that guarantees no duplicate ever appears at any instant. The execution plan analysis explains the logic the engine uses, while the study of the transaction log shows how this logic materializes concretely. The observations made with fn_dblog() reveal that the intermediate operations are largely reduced to MODIFY_ROW operations. In the end, the real complexity does not lie in the physical modifications themselves, but in the preparatory work needed to preserve uniqueness. That is precisely what explains the overhead observed compared to a classic update: SQL Server pays the price of safety and consistency, but then heavily optimizes the actual execution thanks to Collapse.

This post was inspired by Franck Pachot‘s look at the same problem on Oracle, where he follows the ROWIDs through the index at the physical level. A good companion to this post, to read by the fireplace (or the air-con) !