The Halloween Problem – Part 4

The Halloween Problem can have a number of important effects on execution plans. In this final part of the series, we look at the tricks the optimizer can employ to avoid the Halloween Problem when compiling plans for queries that add, change or delete data.

Background

Over the years, a number of approaches have been tried to avoid the Halloween Problem.

One early technique was to simply avoid building any execution plans that involved reading from and writing to keys of the same index. This was not very successful from a performance point of view, not least because it often meant scanning the base table instead of using a selective nonclustered index to locate the rows to change.

A second approach was to completely separate the reading and writing phases of an update query, by first locating all rows that qualify for the change, storing them somewhere, and only then starting to perform the changes. In SQL Server, this full phase separation is achieved by placing the now-familiar Eager Table Spool on the input side of the update operator:

The spool reads all rows from its input and stores them in a hidden tempdb work table. The pages of this work table may remain in memory, or they might require physical disk space if the set of rows is large, or if the server is under memory pressure.

Full phase separation can be less than ideal because we generally want to run as much of the plan as possible as a pipeline, where each row is fully processed before moving on to the next. Pipelining has many advantages including avoiding the need for temporary storage, and only touching each row once.

The SQL Server Optimizer

SQL Server goes much further than the two techniques described so far, though it does of course include both as options. The SQL Server query optimizer detects queries that require Halloween Protection, determines how much protection is required, and uses cost-based analysis to find the cheapest method of providing that protection.

The easiest way to understand this aspect of the Halloween Problem is to look at some examples. In the following sections, the task is to add a range of numbers to an existing table – but only numbers that do not already exist:

CREATE TABLE dbo.Test
(
    pk      integer NOT NULL,

    CONSTRAINT PK_Test
        PRIMARY KEY CLUSTERED (pk)
);

5 rows

The first example processes a range of numbers from 1 to 5 inclusive:

INSERT dbo.Test (pk)
SELECT Num.n 
FROM dbo.Numbers AS Num
WHERE
    Num.n BETWEEN 1 AND 5
    AND NOT EXISTS 
    (
        SELECT NULL
        FROM dbo.Test AS t 
        WHERE t.pk = Num.n
    );

Since this query reads from and writes to the keys of the same index on the Test table, the execution plan requires Halloween Protection. In this case, the optimizer uses full phase separation using an Eager Table Spool:

50 rows

With five rows now in the Test table, we run the same query again, changing the WHERE clause to process the numbers from 1 to 50 inclusive:

This plan provides correct protection against the Halloween Problem, but it does not feature an Eager Table Spool.

The optimizer recognizes that the Hash Match Join operator is blocking on its build input; all rows are read into a hash table before the operator starts the matching process using rows from the probe input. As a consequence, this plan naturally provides phase separation (for the Test table only) without the need for a spool.

The optimizer chose a Hash Match Join plan over the Nested Loops Join seen in the 5-row plan for cost-based reasons. The 50-row hash match plan has a total estimated cost of 0.0347345 units. We can force the nested loops plan used previously with a hint to see why the optimizer did not choose that option:

This plan has an estimated cost of 0.0379063 units including the spool, a bit more than the hash match plan.

500 Rows

With 50 rows now in the Test table, we further increase the range of numbers to 500:

This time, the optimizer chooses a Merge Join. Again, there is no Eager Table Spool. The Sort operator provides the necessary phase separation in this plan. It fully consumes its input before returning the first row (the sort cannot know which row sorts first until all rows have been seen).

The optimizer decided that sorting 50 rows from the Test table would be cheaper than eager-spooling 450 rows just before the update operator.

The Sort plus Merge Join plan has an estimated cost of 0.0362708 units. The Hash Match and Nested Loops plan alternatives come out at 0.0385677 units and 0.112433 units respectively.

Something odd about the Sort

If you have been running these examples for yourself, you might have noticed something odd about that last example, particularly if you looked at the Plan Explorer tool tips for the Test table Seek and the Sort:

The Seek produces an ordered stream of pk values, so what is the point of sorting on the same column immediately afterward?

To answer that (very reasonable) question, we start by looking at just the SELECT portion of the INSERT query:

SELECT Num.n 
FROM dbo.Numbers AS Num
WHERE
    Num.n BETWEEN 1 AND 500
    AND NOT EXISTS 
    (
        SELECT 1
        FROM dbo.Test AS t 
        WHERE t.pk = Num.n
    )
ORDER BY
    Num.n;

This query produces the execution plan below (with or without the ORDER BY I added to address certain technical objections you might have):

Notice the lack of a Sort operator.

So why did the INSERT plan include a Sort? It was to avoid the Halloween Problem. The optimizer considered that performing a redundant sort (with its built-in phase separation) was the cheapest way to execute the query and guarantee correct results. Clever.

Halloween Protection Levels and Properties

The SQL Server optimizer has specific features that allow it to reason about the level of Halloween Protection (HP) required at each point in the query plan, and the detailed effect each operator has. These extra features are incorporated into the same property framework the optimizer uses to keep track of hundreds of other important bits of information during its search activities.

Each operator has a required HP property and a delivered HP property. The required property indicates the level of HP needed at that point in the tree for correct results. The delivered property reflects the HP provided by the current operator and the cumulative HP effects provided by its subtree.

The optimizer contains logic to determine how each physical operator (for example, a Compute Scalar) affects the HP level. By exploring a wide range of plan alternatives and rejecting plans where the delivered HP is less than the required HP at the update operator, the optimizer has a flexible way to find correct, efficient plans that do not always require an Eager Table Spool.

Plan changes for Halloween Protection

We saw the optimizer add a redundant sort for Halloween Protection in the previous Merge Join example. How can we be sure this is more efficient than a simple Eager Table Spool? And how can we know which features of an update plan are only there for Halloween Protection?

Both questions can be answered (in a test environment, naturally) using undocumented trace flag 8692, which forces the optimizer to use an Eager Table Spool for Halloween Protection.

Recall that the Merge Join plan with the redundant sort had an estimated cost of 0.0362708 magic optimizer units. We can compare that to the Eager Table Spool alternative by recompiling the query with trace flag 8692 enabled:

INSERT dbo.Test (pk)
SELECT Num.n 
FROM dbo.Numbers AS Num
WHERE
    Num.n BETWEEN 1 AND 500
    AND NOT EXISTS 
    (
        SELECT 1
        FROM dbo.Test AS t 
        WHERE t.pk = Num.n
    )
OPTION (QUERYTRACEON 8692);

The Eager Spool plan has an estimated cost of 0.0378719 units (up from 0.0362708 with the redundant sort).

The cost differences shown here are not very significant due to the trivial nature of the task and the small size of the rows. Real-world update queries with complex trees and larger row counts often produce plans that are much more efficient thanks to the SQL Server optimizer’s ability to think deeply about Halloween Protection.

Other non-spool options

Positioning a blocking operator optimally within a plan is not the only strategy open to the optimizer to minimize the cost of providing protection against the Halloween Problem. It can also reason about the range of values being processed, as the following example demonstrates:

CREATE TABLE #Test
(
    pk          integer IDENTITY PRIMARY KEY,
    some_value  integer
);

CREATE INDEX i ON #Test (some_value);

-- Pretend the table has lots of data in it
UPDATE STATISTICS #Test
WITH ROWCOUNT = 123456, PAGECOUNT = 1234;

UPDATE #Test
SET some_value = 10
WHERE some_value = 5;

The execution plan shows no need for Halloween Protection, despite the fact we are reading from and updating the keys of a common index:

The optimizer can see that changing some_value from 5 to 10 could never cause an updated row to be seen a second time by the Index Seek (which is only looking for rows where some_value is 5). This reasoning is only possible where literal values are used in the query, or where the query specifies OPTION (RECOMPILE), allowing the optimizer to use the literal values of the parameters for a one-off execution plan.

Even with literal values in the query, the optimizer may be prevented from applying this logic if the database option FORCED PARAMETERIZATION is ON. In that case, the literal values in the query are replaced by parameters, and the optimizer can no longer be sure that Halloween Protection is not required (or will not be required when the plan is reused with different parameter values):

In case you are wondering what happens if FORCED PARAMETERIZATION is enabled and the query specifies OPTION (RECOMPILE), the answer is that the optimizer compiles a plan for the runtime values, and so can apply the optimization. As always with OPTION (RECOMPILE), the specific-value query plan is not cached for reuse.

Top

This last example shows how the Top operator can remove the need for Halloween Protection:

UPDATE TOP (1) t
SET some_value += 1
FROM #Test AS t
WHERE some_value <= 10;

No protection is required because we are only updating one row. The updated value cannot be encountered by the Index Seek, because the processing pipeline stops as soon as the first row is updated.

Again, this optimization can only be applied if a constant literal value is used in the TOP, or if a variable returning the value ‘1’ is extracted using OPTION (RECOMPILE).

If we change the TOP (1) in the query to a TOP (2), the optimizer chooses a Clustered Index Scan instead of the Index Seek:

We are not updating the keys of the clustered index, so this plan does not require Halloween Protection. Forcing the use of the nonclustered index with a hint in the TOP (2) query makes the cost of the protection apparent:

The optimizer estimated the Clustered Index Scan would be cheaper than this plan (with its extra Halloween Protection).

Odds and Ends

There are a couple of other points I want to make about Halloween Protection that have not found a natural place in the series before now. The first is the question of Halloween Protection when a row-versioning isolation level is in use.

Row Versioning

SQL Server provides two isolation levels, READ COMMITTED SNAPSHOT and SNAPSHOT ISOLATION that use a version store (always in tempdb before SQL Server 2019) to provide a statement- or transaction-level consistent view of the database.

SQL Server could avoid Halloween Protection completely under these isolation levels, since the version store can provide data unaffected by any changes the currently executing statement might have made so far.

This idea is currently not implemented in a released version of SQL Server, though Microsoft has filed a patent describing how this would work, so perhaps a future version will incorporate this technology.

Heaps and Forwarded Records

If you are familiar with the internals of heap structures, you might be wondering if a particular Halloween Problem might occur when forwarded records are generated in a heap table.

In case this is new to you, a heap record will be forwarded if an existing row is updated such that it no longer fits on the original data page. The engine leaves behind a forwarding stub, and moves the expanded record to another page.

A problem could occur if a plan containing a heap scan updates a record such that it is forwarded. The heap scan might encounter the row again when the scan position reaches the page with the forwarded record.

In SQL Server, this issue is avoided because the Storage Engine guarantees to always follow forwarding pointers immediately. If the scan encounters a record that has been forwarded, it ignores it. With this safeguard in place, the query optimizer does not have to worry about this scenario.

SCHEMABINDING and T-SQL Scalar Functions

There are very few occasions when using a T-SQL scalar function is a good idea (prior to SQL Server 2019 where some functions can be inlined), but if you must use one you should be aware of an important effect it can have regarding Halloween Protection:

Unless a scalar function is declared with the SCHEMABINDING option, SQL Server assumes the function accesses tables.

To illustrate, consider the simple T-SQL scalar function below:

CREATE FUNCTION dbo.ReturnInput
(
    @value integer
)
RETURNS integer
AS
BEGIN
 RETURN @value;
END;

This function does not access any tables; in fact it does nothing except return the parameter value passed to it. Now look at the following INSERT statement:

DECLARE @T AS TABLE (ProductID integer PRIMARY KEY);

INSERT @T (ProductID)
SELECT p.ProductID
FROM AdventureWorks2012.Production.Product AS p;

The execution plan is exactly as we would expect, with no Halloween Protection needed:

Adding our do-nothing function has a dramatic effect, however:

DECLARE @T AS TABLE (ProductID integer PRIMARY KEY);

INSERT @T (ProductID)
SELECT dbo.ReturnInput(p.ProductID)
FROM AdventureWorks2012.Production.Product AS p;

The execution plan now includes an Eager Table Spool for Halloween Protection. SQL Server assumes the function accesses data, which might include reading from the Product table again.

As you may recall, an INSERT plan that contains a reference to the target table on the reading side of the plan requires full Halloween Protection, and as far as the optimizer knows, that might be the case here.

Adding the SCHEMABINDING option to the function definition means SQL Server examines the body of the function to determine which tables it accesses. It finds no such access, and so does not add any Halloween Protection:

ALTER FUNCTION dbo.ReturnInput
(
    @value integer
)
RETURNS integer
WITH SCHEMABINDING
AS
BEGIN
 RETURN @value;
END;
GO
DECLARE @T AS TABLE (ProductID int PRIMARY KEY);

INSERT @T (ProductID)
SELECT p.ProductID
FROM AdventureWorks2012.Production.Product AS p;

This issue with T-SQL scalar functions affects all update queries – INSERT, UPDATE, DELETE, and MERGE.

Knowing when you are hitting this problem is made more difficult because unnecessary Halloween Protection will not always show up as an extra Eager Table Spool, and scalar function calls may be hidden in views or computed column definitions, for example.

[ Part 1 | Part 2 | Part 3 | Part 4 ]