How SQL Server Solves the Halloween Problem

It’s that time of year again when ghouls and spooks surface and database bloggers write about an issue that shares its name with Halloween. Around mid to late October, you often come across database blogs about a phenomenon that dates all the way back to the mid-1970s: the Halloween Problem. This is my take on the topic.

The What?

The Halloween Problem gets its name from the day it was discovered – 31st October (some reports differ between 1975 and 1976). On this day, Donald Chamberlin, Patricia Selinger, and Morton M. Astrahan were working on the System R database project in an IBM lab and wrote a SQL query which updated a database, giving each staff member who earned less than $25,000 a 10% pay rise. The query completed, but every staff member then had a salary of at least $25,000 – this was not the expected output of the query.

They had inadvertently found a flaw in how the update was being executed – some affected records were updated more than once, until they no longer matched the filter criteria.

To demonstrate how this happens, let’s assume we have 4 employees in an Employees table and the table has an index on salary. The data in the index would look like the table below (names generated by Anthropic Claude, model: Sonnet 5.5):

First Name	Last Name	Salary
Jane	Doe	20,000
John	Smith	21,000
Bob	Jones	23,000
Aisha	Khan	27,000

If we were to run the following SQL query to update the table, the database engine would read through the rows one by one and add 10% to the value:

UPDATE	Employees
SET		Salary = Salary * 1.1
WHERE	Salary < 25000;

As the index is sorted by salary, that ordering should be maintained as records are updated.

The Halloween Problem in Action

The first record to be updated is Jane Doe, whose salary is 20,000. The arrow marks the next row the scan will update:

Row to update this iteration	First Name	Last Name	Salary
➜	Jane	Doe	20,000
	John	Smith	21,000
	Bob	Jones	23,000
	Aisha	Khan	27,000

Jane is updated to 22,000 so that record moves along in the index to maintain the order (the bold text marks the row just updated):

Row to update this iteration	First Name	Last Name	Salary
➜	John	Smith	21,000
	Jane	Doe	22,000
	Bob	Jones	23,000
	Aisha	Khan	27,000

John is updated to 23,100. His row moves below Bob. Jane is now the next row in the scan, even though she has already been updated:

Row to update this iteration	First Name	Last Name	Salary
➜	Jane	Doe	22,000
	Bob	Jones	23,000
	John	Smith	23,100
	Aisha	Khan	27,000

Jane is updated a second time, from 22,000 to 24,200:

Row to update this iteration	First Name	Last Name	Salary
➜	Bob	Jones	23,000
	John	Smith	23,100
	Jane	Doe	24,200
	Aisha	Khan	27,000

Bob is updated to 25,300, which is no longer below 25,000:

Row to update this iteration	First Name	Last Name	Salary
➜	John	Smith	23,100
	Jane	Doe	24,200
	Bob	Jones	25,300
	Aisha	Khan	27,000

John is updated a second time, from 23,100 to 25,410:

Row to update this iteration	First Name	Last Name	Salary
➜	Jane	Doe	24,200
	Bob	Jones	25,300
	John	Smith	25,410
	Aisha	Khan	27,000

Jane is updated a third time, from 24,200 to 26,620. The scan then finds no rows under 25,000, so it stops.

First Name	Last Name	Salary
Bob	Jones	25,300
John	Smith	25,410
Jane	Doe	26,620
Aisha	Khan	27,000

The table below shows the end result – each person who started with a salary below 25,000 is now over 25,000, some receiving a much greater increase than we expected. Let’s hope Jane is going to give generously to the trick-or-treaters at her door.

Employee	Start	Expected (one 10% raise)	Actual	Times updated
Jane Doe	20,000	22,000	26,620	3
John Smith	21,000	23,100	25,410	2
Bob Jones	23,000	25,300	25,300	1
Aisha Khan	27,000	27,000	27,000	0

How SQL Server Prevents This Behaviour

Clearly, the above is not the desired behaviour and something must be done to prevent it. Let’s see what SQL Server does to prevent this from happening.

We’ll work through a similar example in the Stack Overflow database, provided under cc-by-sa 4.0 licence from the Stack Exchange Data Dump. The database is in compatibility level 160 on a SQL Server 2022 instance installed on a VM with 8 cores and 46GB RAM. I will use the 2013 version of the database for this example.

The following query increases the reputation of those users who already have a reputation over 1,000,000 by 10%

UPDATE	dbo.Users
SET		Reputation = Reputation * 1.1
WHERE	Reputation > 1000000;

To support this query, we may create the index below so SQL Server can seek directly to those users with a reputation over 1,000,000. The index allows SQL Server to seek directly to those users that need to be updated, but it also means the query reads and modifies the keys of the same index, which is what creates the Halloween Problem.

The WHERE clause is highly selective as there is only one user in this version of the database that has a reputation in that range, so this index should mean we can jump straight to that user and update their record:

CREATE INDEX IX_Reputation ON dbo.Users
(
	Reputation
);

As we’re going to run a few tests here, I’ll just grab the estimated execution plan as it illustrates SQL Server’s strategy without actually changing the data – this way each test is being run against the same data.

The estimated plan for the update query above is:

We can see a Table Spool operator and that is what prevents the Halloween Problem from occurring.

As we are retrieving the data we want to update using an index on the column we are modifying, that index must then be updated. SQL Server needs to separate the read dataset from the update dataset.

An Eager Table Spool reads all the rows of its child operator (the Index Seek in our case) before the next operator can start processing, as such, the Eager Table Spool operator is known as a blocking operator in an execution plan. What happens in this execution plan is that the records to be updated (one user with a reputation over 1,000,000 in this example) are read from the index and written to the Spool operator (this is written to tempdb) The dataset in the Eager Table Spool is then worked on (the Compute Scalars are there to support the 10% calculation) and then the output is pushed into the Clustered Index Update. The key is that the spool is a separate object from the index itself and therefore is unaffected by the index update.

The Clustered Index Update operator actually updates both the clustered index and the non-clustered index on Reputation:

A spool isn’t the only operator that provides Halloween Protection in SQL Server, other blocking operators such as a sort can give the same effect.

Let’s change the criteria of the WHERE clause so that every user with a reputation above 1 gets a 10% uplift. I’m forcing the optimizer to use the same index as it did before – rarely is this a good idea in reality, but I am doing it here to keep the demonstration on topic. Note the form of the update has changed slightly as there is now a FROM clause – this is to allow me to provide the index hint:

UPDATE	dbo.Users
SET		Reputation = Reputation * 1.1
FROM	dbo.Users WITH (INDEX = IX_Reputation)
WHERE	Reputation > 1;

The plan is below:

SQL Server still seeks the index (because of our index hint) but rather than perform a spool, it sorts the data that comes out of the Index Seek. It sorts by the Id column (which is the column the table is clustered on) so that it can update the clustered index. Like the spool, the sort creates a copy of the data and it is that which is used to drive the update, rather than the index which was read at the beginning of the plan. While the spool copies the data to tempdb, the sort is done in memory, though it can spill to tempdb if not enough memory is granted. In both cases, reading the secondary dataset, rather than the original index, is what provides the Halloween Protection.

As an aside, without forcing the index above, SQL Server chose a different plan:

UPDATE	dbo.Users
SET		Reputation = Reputation * 1.1
FROM	dbo.Users
WHERE	Reputation > 1;

The plan is below:

SQL Server chose to scan the entire clustered index. We can see the root operator in the plan for this query and the plan for our hint query that it has costed the clustered index plan slightly cheaper and as the optimizer is cost-based, SQL Server picks that plan.

Conclusion

This post was my take on how SQL Server protects against the Halloween Problem – a platform agnostic issue that could happen when using an index to retrieve records from a database where those are the same records being updated by the query. The post is a short overview of the problem, with some simple examples. For a more detailed overview, I would recommend Paul White’s excellent four-part article on the topic in the references below.