ORDER BY (SELECT NULL)

My least favorite tempdb spills are the ones that happen with a large percentage of the memory grant remaining unused. For example, recently I saw tempdb spills with a memory grant of 35 GB but SQL Server reported that only 10 GB of memory was used. Usually this problem can be traced back to suboptimal memory fractions somewhere in a query plan. I suspect that it can also happen with certain types of queries that load data into columnstore tables but haven’t verified that. In the test environment the issue was caused by memory fractions, but these memory fractions were attached to batch mode operators. The rules for batch mode memory fractions certainly appear to be different than those for rowstore memory fractions. I believe that I was able to work out a few of the details for a few simple cases. In some scenarios, plans with multiple batch mode hash joins can ask for significantly more memory than needed. Reducing the memory grant via Resource Governor or a query hint to something more reasonable can lead to unnecessary (and often frustrating) tempdb spills.

What is a Memory Fraction?

There’s very little information out there about memory fractions. I would define them as information in the query plan that can give you clues about each operator’s share of the total query memory grant. This is naturally more complicated for query plans that insert into tables with columnstore indexes but that won’t be covered here. Most references will tell you not to worry about memory fractions or that they aren’t useful most of the time. Out of thousands of queries that I’ve tuned I can only think of a few for which memory fractions were relevant. Sometimes queries spill to tempdb even though SQL Server reports that a lot of query memory was unused. In these situations I generally hope for a poor cardinality estimate which leads to a memory fraction which is too low for the spilling operator. If fixing the cardinality estimate doesn’t prevent the spill then things can get a lot more complicated, assuming that you don’t just give up.

Types of Query Plans

The demos for this blog post all use tables with identical structures and data. The tables are heaps so the plans will only feature hash joins. The most important plan characteristic is how many of the hash tables need to be kept in memory concurrently while the query processor executes the query. This is where memory fractions come in. The query optimizer tries to reuse parts of memory grants as it can. For example, if the hash build for the first join isn’t needed when the third join executes then it’s possible to use the memory grant from the first hash table for the third hash table. Some of the examples below will make this more clear.

The first type of plan has hash joins which can all run concurrently. Memory for the hash tables cannot be reused between operators.

For that query, the MF_DEMO_1 table is the probe side for all of the joins. SQL Server builds all of the hash joins and then rows flow from the probe side through the plan (as long as there aren’t tempdb spills). I will refer to this type of plan as a “concurrent join plan” which is a term that I just made up.

The second type of plan has hash joins which cannot all run concurrently. Pairs of hash tables are active at the same time, but memory grants can be reused between operators.

For that query, the MF_DEMO_1 table is the build side for all of the joins. Each hash table blocks the next one from starting. This means that at most two hash tables need to be kept in memory at the same time. Query memory cannot be reused for joins 1 and 2 but join 3 can reuse memory from join 1 and join 4 can reuse memory from join 2. I will refer to this type of plan as a “nonconcurrent join plan” which is another term that I just made up.

If the above wasn’t clear I recommend running through the demos with live query statistics enabled. It can be very useful to understand how rows flow through a plan. As far as I know, all queries of this type can be implemented with the nonconcurrent pattern but not all queries can be implemented with the concurrent pattern .

Create the Tables

The table definitions for our demos are pretty boring. I’m using a VARCHAR(100) as the join column to blow up memory grants and requirements a bit. All of the tables are heaps and have about 6.5 million rows in them. TARGET_TABLE is used as a dumping ground for the inserts and #ADD_BATCH_MODE is used to switch the hash joins to batch mode as desired. All testing was done on SQL Server 2016 SP1 CU7.

DROP TABLE IF EXISTS MF_DEMO_1;
CREATE TABLE MF_DEMO_1 (
       ID VARCHAR(100)
);

INSERT INTO MF_DEMO_1 WITH (TABLOCK)
SELECT 999999999999999 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE STATISTICS S1 ON MF_DEMO_1 (ID) WITH FULLSCAN;

DROP TABLE IF EXISTS MF_DEMO_2;
CREATE TABLE MF_DEMO_2 (
       ID VARCHAR(100)
);

INSERT INTO MF_DEMO_2 WITH (TABLOCK)
SELECT 999999999999999 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE STATISTICS S2 ON MF_DEMO_2 (ID) WITH FULLSCAN;

DROP TABLE IF EXISTS MF_DEMO_3;
CREATE TABLE MF_DEMO_3 (
       ID VARCHAR(100)
); 

INSERT INTO MF_DEMO_3 WITH (TABLOCK)
SELECT 999999999999999 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE STATISTICS S3 ON MF_DEMO_3 (ID) WITH FULLSCAN;

DROP TABLE IF EXISTS MF_DEMO_4;
CREATE TABLE MF_DEMO_4 (
       ID VARCHAR(100)
); 

INSERT INTO MF_DEMO_4 WITH (TABLOCK)
SELECT 999999999999999 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE STATISTICS S4 ON MF_DEMO_4 (ID) WITH FULLSCAN;

DROP TABLE IF EXISTS MF_DEMO_5;
CREATE TABLE MF_DEMO_5 (
	ID VARCHAR(100)
); 

INSERT INTO MF_DEMO_5 WITH (TABLOCK)
SELECT 999999999999999 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE STATISTICS S5 ON MF_DEMO_5 (ID) WITH FULLSCAN;

CREATE TABLE #ADD_BATCH_MODE (I INT, INDEX CCI CLUSTERED COLUMNSTORE);

DROP TABLE IF EXISTS TARGET_TABLE;

CREATE TABLE TARGET_TABLE (ID VARCHAR(100));

Row Mode Memory Fractions For Concurrent Join Plans

The following query results in a concurrent join plan with row mode hash joins:

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_3 t3
RIGHT OUTER JOIN MF_DEMO_2 t2
RIGHT OUTER JOIN MF_DEMO_1 t1
ON t1.ID = t2.ID
ON t1.ID = t3.ID
OPTION (FORCE ORDER, MAXDOP 1);

The desired memory grant is 2860640 KB. The memory fractions for both join operators have an input of 0.5 and an output of 0.5. This is exactly as expected. The hash tables can both start at the same time and cannot reuse memory, so each operator gets 50% of the query memory grant for the plan. Adding a third join to the plan increases the query memory grant to 4290960 KB.

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_4 t4
RIGHT OUTER JOIN MF_DEMO_3 t3
RIGHT OUTER JOIN MF_DEMO_2 t2
RIGHT OUTER JOIN MF_DEMO_1 t1
ON t1.ID = t2.ID
ON t1.ID = t3.ID
ON t1.ID = t4.ID
OPTION (FORCE ORDER, MAXDOP 1);

Again, this seems very reasonable. SQL Server now tries to builds three hash tables in memory at the same time. The memory fractions for each operator have fallen to 0.3333333. Each operator gets a third of the query memory grant.

Row Mode Memory Fractions For Nonconcurrent Join Plans

The following query results in a nonconcurrent join plan with row mode hash joins:

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_1 t1
INNER JOIN MF_DEMO_2 t2 ON t1.ID = t2.ID
INNER JOIN MF_DEMO_3 t3 ON t2.ID = t3.ID
INNER JOIN MF_DEMO_4 t4 ON t3.ID = t4.ID
OPTION (MAXDOP 1, FORCE ORDER);

The query plan was uploaded here. I recommend downloading the all of the plans referenced in this blost post if you’re interested in them so you can see all of the details.

Here are the memory fractions for the rightmost join (node 3):

Memory Fractions Input: 1, Memory Fractions Output: 0.476174

here are the memory fractions for the middle join (node 2):

Memory Fractions Input: 0.523826, Memory Fractions Output: 0.5

and here are the memory fractions for the leftmost join (node 1):

Memory Fractions Input: 0.5, Memory Fractions Output: 1

What do all of those numbers mean? The rightmost join builds its hash table first and starts with all query memory available to it. However, the output fraction is 0.476174. That means that the hash table can only use up to 47.6% of the query memory granted to the plan. The middle join is able to use up to 50% (the minimum of the input and output fractions for the node) of the memory granted to the plan. Note that 0.476174 + 0.523826 = 1.0. The last join to start executing is also able to use up to 50% of the granted memory. That join is the last operator that uses memory in the plan so the output fraction is 1.0. Memory grant reuse allows the plan to use up to 147.6% of the memory grant over the lifetime of the query execution. Without memory grant reuse each operator wouldn’t be able to use as much memory.

Removing one of the joins results in the desired query memory grant dropping from 3146704 KB to 3003672 KB. This is a significantly less drop than the other query. The smaller decrease is expected because the third join that we added can reuse the memory grant from the first. As more joins are added to a nonconcurrent plan the desired memory grant grows at a much slower rate than the memory grant for the concurrent join plan.

Batch Mode Memory Fractions For Concurrent Join Plans

The query plan for the next query is somewhat dependent on hardware. On my machine I had to let it run in parallel to get batch mode hash joins:

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_5 t5
RIGHT OUTER JOIN MF_DEMO_4 t4
RIGHT OUTER JOIN MF_DEMO_3 t3
RIGHT OUTER JOIN MF_DEMO_2 t2
RIGHT OUTER JOIN MF_DEMO_1 t1
LEFT OUTER JOIN #ADD_BATCH_MODE ON 1 = 0
ON t1.ID = t2.ID
ON t1.ID = t3.ID
ON t1.ID = t4.ID
ON t1.ID = t5.ID
OPTION (FORCE ORDER, MAXDOP 4);

The estimated plan is here. It’s easy to tell if the query is using batch mode joins because the joins are run in parallel but there are no repartition stream operators.

SQL Server is not able to reuse memory grants for this query. SQL Server tries to build all of the hash tables in memory before probe side is processed. However, the memory fractions are different from before: 0.25, 0.5, 0.75, and 1.0. These memory fractions do not make sense if interpreted in the same way as before. How can the final hash join in the plan have an input memory fraction of 1.0?

It’s unclear what the memory fractions are supposed to mean here, but there is one observable difference compared to the row mode plan. In the row mode equivalent plan SQL Server divides the memory evenly between operators. For our very simple test plan this means that all of the hash joins will spill to tempdb or none of them will spill. Reducing a MAX_GRANT_PERCENT hint from the right value by 1% results in two spills:

Both operators spilled because memory was divided evenly and there wasn’t enough memory to hold both hash tables in memory. However, with batch mode hash joins we can get plans like the following:

How is it possible that one join spills but the other doesn’t? It is only possible if memory isn’t divided evenly. It appears that memory is used as needed in some situations. Unfortunately, the actual plan for batch mode operators doesn’t give us a lot of spill information like it does for row mode. There’s a debug channel extended event query_execution_batch_hash_join_spilled that can give us some clues. 657920 KB of memory was granted for a two batch mode hash join query. For the operator that spilled, only 44852457 bytes were written to memory on the build side. That’s about 43800 KB, which is significantly less than half of available query memory.

We can’t conclude that exactly 44852457 bytes of memory were granted to the operator. However, it should be somewhat close. In conclusion, for these types of queries it isn’t clear what the memory grant fractions are supposed to mean. SQL Server is able to exceed them in some cases. It’s possible to see 0 bytes of memory used for the build side in the extended event. I believe that this is the bad type of memory reuse as opposed to the good kind.

Batch Mode Memory Fractions For Nonconcurrent Join Plans

The following query results in a nonconcurrent batch mode hash join plan on my machine:

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_1 t1
LEFT OUTER JOIN #ADD_BATCH_MODE On 1 = 0
WHERE EXISTS (
	SELECT 1
	FROM MF_DEMO_2 t2 WHERE t1.ID = t2.ID
) AND EXISTS (
	SELECT 1
	FROM MF_DEMO_3 t3 WHERE t1.ID = t3.ID
) AND EXISTS (
	SELECT 1
	FROM MF_DEMO_4 t4 WHERE t1.ID = t4.ID
) AND EXISTS (
	SELECT 1
	FROM MF_DEMO_5 t5 WHERE t1.ID = t5.ID
) OPTION (MAXDOP 4, FORCE ORDER);

As far as I know there’s nothing special about the semijoins. I used them to keep the estimated row size as consistent as possible. The behavior detailed below can be observed with normal joins as well.

Here is the estimated query plan. The same memory fraction pattern of 0.25, 0.50, 0.75, and 1.00 can be found in this query. Based on the query’s structure, memory grant reuse should be allowed between operators. Alarmingly, this query has the same desired memory grant as one with four concurrent joins. The desired memory grant changes significantly as tables are added or removed. This is a big change in behavior compared to row mode batch joins.

As far as I can tell, memory grant reuse can happen in plans like this with batch mode hash joins. Removing or adding joins results in very small adjustments in maximum memory used during query execution. Still, it seems as if the query optimizer is assuming that memory cannot be reused. With this query pattern, the first operator to run does not have access more memory implied by the memory fraction. In fact, it has access to less memory implied by the memory fraction.

Running the query without any memory grant hints results in no tempdb spills and a maximum memory use of 647168 KB. Restricting the memory grant to 2 GB results in a tempdb spill for the rightmost operator. This is unexpected. 500000 KB of memory should be more than enough memory to avoid a spill. As before, the only way I could find to investigate this further was to use the query_execution_batch_hash_join_spilled extended event and to force tempdb spills using the MAX_GRANT_PERCENT query hint.

A good amount of testing suggested that the available memory per operator is the input memory fraction for that operator divided by the sum of all output memory fractions. The rightmost operator only gets 0.25 / (0.25 + 0.5 + 0.75 + 1.0) = 10% of the memory granted to the query, the next operator gets 20%, the next operator gets 30%, and the final operator gets 40%. The situation gets worse as more joins are added to the query. Keep in mind that we aren’t doing anything tricky with cardinality estimates or data types which would result in skewed estimates. The query optimizer seems to recognize that each join will require the same amount of memory for each hash join, but it doesn’t make the same minimum amount available for each operator. That’s what is so puzzling.

The preceding paragraph seems to contradict the idea that memory grant reuse is possible for these plan shapes. Perhaps for these simple plans memory grant reuse is possible but it cannot go above 100% like we saw in the row mode plan. This could still be helpful in that the query could steal less memory from the buffer pool, but it’s certainly not as helpful in avoiding spills as the behavior we get with the row mode plan. Under the assumption the total memory grants seem a bit more reasonable, although it’s hard not to object as to how SQL Server is distributing the memory to each operator.

We can avoid the spill by giving SQL Server the memory that it required, but this is undesirable if multiple concurrent queries are running. I’ve often observed higher than expected memory grants for queries with batch mode hash joins. An assumption that query memory reuse will not be available for batch mode hash joins can explain part of what I’ve observed. If memory grants are left unchecked, applications may see decreased possible concurrency due to RESOURCE_SEMAPHORE waits. Lowering memory grants through any available method can result in unnecessary (based on total memory granted) tempdb spills. It’s easy to get stuck between a rock and a hard place.

Batch Mode Workarounds

There is some hope for nonconcurrent batch mode hash join plans. SQL Server 2017 introduces adaptive memory feedback for these operators. I imagine that functionality is a poor fit for ETL queries which may process dramatically different amounts of data each day, so I can’t view it as a complete solution. It certainly doesn’t help us on SQL Server 2016. Are there workarounds to prevent spills without requiring excessive memory grants? Yes, but they are very ugly and I can only imagine using them when truly needed during something like an ETL process.

Consider the following query:

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_1 t1
LEFT OUTER JOIN MF_DEMO_2 t2 ON t2.ID = t1.ID
LEFT OUTER JOIN MF_DEMO_3 t3 ON t3.ID = t2.ID
LEFT OUTER JOIN MF_DEMO_4 t4 ON t4.ID = t3.ID
LEFT OUTER JOIN MF_DEMO_4 t5 ON t5.ID = t4.ID
LEFT OUTER JOIN #ADD_BATCH_MODE ON 1 = 0
OPTION (FORCE ORDER, MAXDOP 4, MAX_GRANT_PERCENT = 60);

On my machine, the memory hint results in a memory grant of 2193072 KB. The rightmost join spills even when only a maximum of 1232896 KB of memory is used during query execution:

One way to avoid the spill is to shift the memory fractions in our favor. Ideally SQL Server would think that the rightmost join would need much more memory for its hash table than the other joins. If we can add an always NULL column with a large data type that is only needed for the first hash table, that might do the trick. The query syntax below isn’t guaranteed to get the plan that we want but it seems to work in this case:

ALTER TABLE MF_DEMO_1 ADD DUMMY_COLUMN_V4000 VARCHAR(4000) NULL;
ALTER TABLE MF_DEMO_2 ADD DUMMY_COLUMN_V10 VARCHAR(10) NULL;

INSERT INTO TARGET_TABLE WITH (TABLOCK)
SELECT t1.ID
FROM MF_DEMO_1 t1
LEFT OUTER JOIN MF_DEMO_2 t2 ON t2.ID = t1.ID
LEFT OUTER JOIN MF_DEMO_3 t3 ON t3.ID = t2.ID
LEFT OUTER JOIN MF_DEMO_4 t4 ON t4.ID = t3.ID
LEFT OUTER JOIN MF_DEMO_4 t5 ON t5.ID = t4.ID
LEFT OUTER JOIN #ADD_BATCH_MODE ON 1 = 0
WHERE (t1.DUMMY_COLUMN_V4000 IS NULL OR t2.DUMMY_COLUMN_V10 IS NULL)
OPTION (FORCE ORDER, MAXDOP 4, MAX_GRANT_PERCENT = 32);

An actual plan was uploaded here. The query no longer spills even though the memory grant was cut to 1225960 KB. The memory fractions are now 0.82053, 0.878593, 0.936655, and 1. The change was caused by the increase in estimated row size for the rightmost join: 2029 bytes. That row size is reduced to 45 bytes after the filter is applied, which won’t filter out any rows because both columns are always NULL. The FORCE ORDER hint is essential to get this plan shape. It’s very unnatural otherwise.

If the same rules are followed as before, the rightmost join should get 22.5% of the available query memory grant now. This is enough to avoid the spill to tempdb.

Final Thoughts

I understand that the formulas for memory fractions need to account for an arbitrary combination of row mode and batch mode operators in a query plan. However, it is disappointing that the available information for memory fractions for batch mode operators is so confusing, some queries with batch mode hash joins ask for way more memory than they need, and some queries needlessly spill to tempdb without using close to their full memory grant. Batch mode adaptive memory grant feedback can offer some relief in SQL Server 2017, but why not expect good plans the first time as long as we’re giving the query optimizer good information? Thanks for reading!

Trace flags are often-hidden configuration switches within SQL Server that can be used to change advanced configuration options, enable or disable fixes, or provide additional diagnostic information. Microsoft recently (on the time scale of the product) published a list of supported trace flags.  The community has found other, undocumented trace flags through various means. The best repository that I’m aware of is maintained by Konstantin Ktaranov here and published here. This blog post contains a stored procedure that can find trace flags. The code contained in this blog post is extremely dangerous and should never be run in production. Be prepared to say goodbye to any server that you run it on.

Hunting Technique

Microsoft gives us a few clues about the range of valid trace flags. All of the documented trace flags (other than the one to make trace flags globally scoped, -1) are positive integers less than 11025. Looking through the list, we can see that similar trace flags are often grouped together. However, the most important hint is that DBCC TRACEON and DBCC TRACEOFF threw an error for any trace flag that’s above some hardcoded maximum. In SQL Server 2017 CU2 the largest allowed value is 11498. What if we had a stored procedure which could take a query to run, turn on one trace flag at a time from 1 to 11498, save off the XML from the estimated plan, turn off the trace flag, go to the next one, and compare all of the generated XML? That would give us a way to check for changes to the XML for everything in the known range of possible trace flags.

The technique described above will not work for trace flags that can only be activated at server startup. You’ll need something like Brent’s method here for that. It also won’t work well for trace flags which need other trace flags to be enabled at the same time. Some trace flags have an effect which cannot be observed through an estimated plan, such as some server settings and aggregate pushdown for CCIs. Still, with the right test query and a little patience you can get some interesting results.

Prepare for the Hunt

The stored procedure requires a few tables to exist and be populated. There is a set of three tables that exclude trace flags in different ways:

CREATE TABLE dbo.STACK_DUMP_TFS (TF INT, PRIMARY KEY (TF));

CREATE TABLE dbo.TFS_TO_EXCLUDE (TF INT, PRIMARY KEY (TF));

CREATE TABLE dbo.KNOWN_TFS (TF INT, PRIMARY KEY (TF));

The first table, STACK_DUMP_TFS, contains trace flags that cause stack dumps which you never want to enable. I found two such trace flags during my testing, but there could be others depending on server configuration and the query that you’re testing. The TFS_TO_EXCLUDE table contains trace flags that you don’t want to enable for one reason or another. Maybe you want to enable a trace flag throughout the lifetime of a test or you’ve found a previously unknown trace flag and you don’t want to continue to show up your test results. The KNOWN_TFS table contains all trace flags found in Konstantin’s trace flag guide. Of course, you can populate the tables with whatever you want, but I put code to populate the tables with the dataset that I use on pastebin.

Finally, the stored procedure logs what it finds to the following table:

CREATE TABLE dbo.LOG_TF_XML_COMPARE (
	TEST_NAME VARCHAR(100) NOT NULL,
	TF_SCOPE VARCHAR(10) NOT NULL,
	TF_NUMBER INTEGER NOT NULL,
	TF_IS_KNOWN INT,
	LOG_TIME DATETIME,
	QUERY_PLAN_XML XML,
	QUERY_ERROR_TEXT NVARCHAR(4000),
	PRIMARY KEY (TEST_NAME, TF_SCOPE, TF_NUMBER)
);

The structure of the table will make more sense after I go through an example later on in this post.

Set Your Bait

The stored procedure has a few parameters to define the search:

@test_name VARCHAR(100),
@query_text NVARCHAR(3900),
@tf_scope VARCHAR(10) = 'GLOBAL',
@first_TF_to_search INT = 1,
@last_TF_to_search INT = 11498,
@skip_known_TFs INT = 1

The @test_name parameter controls what is logged to the TEST_NAME column of LOG_TF_XML_COMPARE. The stored procedure deletes all existing data from the table with a matching @test_name and @tf_scope.

The @query_text parameter contains the query for which an estimated plan to be generated. Currently, the procedure only supports single statement queries, so you can’t define a variable or create a table in the query text and do something else after.

The @tf_scope parameter controls if the trace flags are enabled at the session, global, or query level with QUERYTRACEON. Allowed inputs are 'GLOBAL', 'SESSION', and 'QUERY'. The query level can only be used if @query_text contains a '{{QUERYTRACEON}}' or '{{QUERYHINT}}' placeholder. '{{QUERYTRACEON}}' should be used as a substitute for QUERYTRACEON in the query and '{{QUERYHINT}}' should be used to create the OPTION part of a query, so you’d only use '{{QUERYTRACEON}}' if you need to specify other hints at the query level.

@first_TF_to_search is the first trace flag to search with a default value of 1. Trace flags are always searched in ascending order.

@last_TF_to_search is the last trace flag to search with a default value of 11498. I haven’t done any testing on lower versions of SQL Server, so it’s possible that you’ll see errors when trying trace flags with a higher value on some product versions.

If @skip_known_TFs is set to 0 then trace flags in the KNOWN_TFS table will be skipped during the stored procedure run. Trace flags in the STACK_DUMP_TFS and TFS_TO_EXCLUDE tables are always skipped.

Begin the Hunt

The procedure enables a trace flag, generates a cached plan, does some cleanup on the plan, and saves it into the logging table if it’s different from the plan without any trace flags. The full code of the procedure is below:

-- THIS CODE DOES BAD THINGS!!!!
CREATE OR ALTER PROCEDURE [dbo].[FIND_TRACE_FLAGS] (
@test_name VARCHAR(100),
@query_text NVARCHAR(3900),
@tf_scope VARCHAR(10) = 'GLOBAL',
@first_TF_to_search INT = 1,
@last_TF_to_search INT = 11498,
@skip_known_TFs INT = 1
)
AS
BEGIN
DECLARE
	@plan_handle VARBINARY(64),
	@plan_xml XML,
	@query_error nvarchar(4000),
	@TF INT,
	@trace_sql VARCHAR(1000),
	@standard_plan_xml_as_string NVARCHAR(MAX),
	@TF_is_known INT,
	@query_text_to_run_w_placeholders NVARCHAR(4000),
	@query_text_to_run NVARCHAR(4000)

;
SET NOCOUNT ON;

IF @tf_scope NOT IN ('GLOBAL', 'SESSION', 'QUERY')
BEGIN
	THROW 50001, 'Fix @tf_scope', 1;
	RETURN;
END;

IF @tf_scope = 'QUERY' AND @query_text NOT LIKE '%{{QUERYTRACEON}}%' AND @query_text NOT LIKE '%{{QUERYHINT}}%'
BEGIN
	THROW 50001, '@query_text needs {{QUERYTRACEON}} or {{QUERYHINT}} placeholder', 1;
	RETURN;
END;

IF @first_TF_to_search NOT BETWEEN 1 AND 11498 -- max that doesn't error out in DBCC traceon is 11498
BEGIN
	THROW 50001, 'Fix @first_TF_to_search', 1;
	RETURN;
END;

IF @last_TF_to_search NOT BETWEEN 1 AND 11498 -- max that doesn't error out in DBCC traceon is 11498
BEGIN
	THROW 50001, 'Fix @@last_TF_to_search', 1;
	RETURN;
END;

IF @tf_scope = 'QUERY' AND @query_text NOT LIKE '%{{QUERYTRACEON}}%' AND @query_text NOT LIKE '%{{QUERYHINT}}%'
BEGIN
	THROW 50001, '@query_text needs {{QUERYTRACEON}} or {{QUERYHINT}} placeholder', 1;
END;

DBCC TRACEON(8757) with NO_INFOMSGS; -- disable trivial plans

DELETE FROM dbo.LOG_TF_XML_COMPARE WITH (TABLOCK)
WHERE TEST_NAME = @test_name AND TF_SCOPE = @tf_scope
OPTION (RECOMPILE);

DBCC FREEPROCCACHE with NO_INFOMSGS;

SET @query_text_to_run_w_placeholders = N'SET NOEXEC ON; /* FIND_ME */' + @query_text;

IF @tf_scope <> 'QUERY'
BEGIN
	SET @query_text_to_run = @query_text_to_run_w_placeholders
END
ELSE
BEGIN
	SET @query_text_to_run = REPLACE(REPLACE(@query_text_to_run_w_placeholders, N'{{QUERYTRACEON}}', N''), N'{{QUERYHINT}}', N'');
END;

BEGIN TRY
	EXEC (@query_text_to_run);
END TRY
BEGIN CATCH
	SET @query_error = ERROR_MESSAGE();
END CATCH;

IF @query_error IS NOT NULL
BEGIN
	THROW 50001, @query_error, 1;
	RETURN;
END;

SELECT /* HIDE_ME */ @plan_handle = ecp.plan_handle
, @plan_xml = eqp.query_plan
FROM sys.dm_exec_cached_plans ecp
CROSS APPLY sys.dm_exec_sql_text(ecp.plan_handle) est
CROSS APPLY sys.dm_exec_query_plan (ecp.plan_handle) eqp
WHERE est.text LIKE '%/* FIND_ME */%'
AND est.text NOT LIKE '%/* HIDE_ME */%';

DBCC FREEPROCCACHE (@plan_handle) WITH NO_INFOMSGS;

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple[1]
');

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@StatementCompId
');			

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileTime
');

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileCPU
');

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileMemory
');

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/TraceFlags
');

SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/OptimizerHardwareDependentProperties/@MaxCompileMemory
');

IF @tf_scope = 'QUERY' 	-- only wipe out text and other stuff when QUERYTRACEON is used
BEGIN
	SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
	delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@StatementText
	');

	SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
	delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@QueryHash
	');

	SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
	delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@QueryPlanHash
	');
END;

INSERT INTO dbo.LOG_TF_XML_COMPARE VALUES (@test_name, @tf_scope, 0, 0, GETDATE(), @plan_xml, @query_error);

SET @standard_plan_xml_as_string = CAST(@plan_xml AS NVARCHAR(MAX));

SET @TF = @first_TF_to_search;
WHILE @TF <= @last_TF_to_search
BEGIN
	SET @query_error = NULL;
	SET @plan_handle = NULL;
	SET @plan_xml = NULL;
	SET @TF_is_known = 0;

	IF @TF = 8757 OR EXISTS (SELECT 1 FROM dbo.STACK_DUMP_TFS WHERE TF = @TF) OR EXISTS (SELECT 1 FROM dbo.TFS_TO_EXCLUDE WHERE TF = @TF)
	BEGIN
		SET @TF = @TF + 1;
		CONTINUE;
	END;

	IF EXISTS (SELECT 1 FROM dbo.KNOWN_TFS WHERE TF = @TF)
	BEGIN
		SET @TF_is_known = 1;
	END;

	IF @TF_is_known = 1 AND @skip_known_TFs = 1
	BEGIN
		SET @TF = @TF + 1;
		CONTINUE;
	END;

	-- set trace flag at right level
	IF @tf_scope = 'GLOBAL'
	BEGIN
		SET @trace_sql = 'DBCC TRACEON(' + CAST(@TF AS VARCHAR(5)) + ', -1) with NO_INFOMSGS';
		EXEC (@trace_sql);
	END
	ELSE IF @tf_scope = 'SESSION'
	BEGIN
		SET @trace_sql = 'DBCC TRACEON(' + CAST(@TF AS VARCHAR(5)) + ') with NO_INFOMSGS';
		EXEC (@trace_sql);
	END
	ELSE
	BEGIN
		SET @query_text_to_run = REPLACE(REPLACE(@query_text_to_run_w_placeholders, N'{{QUERYTRACEON}}', N', QUERYTRACEON ' + CAST(@TF AS NVARCHAR(5)))
				, N'{{QUERYHINT}}', N'OPTION(QUERYTRACEON ' + CAST(@TF AS NVARCHAR(5)) + N')' );
	END;

	BEGIN TRY
		EXEC (@query_text_to_run);
	END TRY
	BEGIN CATCH
		SET @query_error = ERROR_MESSAGE();
	END CATCH;

	IF @query_error IS NULL
	BEGIN
		SELECT /* HIDE_ME */ @plan_handle = ecp.plan_handle, @plan_xml = eqp.query_plan
		FROM sys.dm_exec_cached_plans ecp
		CROSS APPLY sys.dm_exec_sql_text(ecp.plan_handle) est
		CROSS APPLY sys.dm_exec_query_plan (ecp.plan_handle) eqp
		WHERE est.text LIKE '%/* FIND_ME */%'
		AND est.text NOT LIKE '%/* HIDE_ME */%';

		IF @plan_handle IS NOT NULL
		BEGIN
			DBCC FREEPROCCACHE (@plan_handle) WITH NO_INFOMSGS;

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple[1]
			');

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@StatementCompId
			');			

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileTime
			');

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileCPU
			');

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/@CompileMemory
			');

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/TraceFlags
			');

			SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
			delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/QueryPlan/OptimizerHardwareDependentProperties/@MaxCompileMemory
			');

			IF @tf_scope = 'QUERY' 	-- only wipe out text and other stuff when QUERYTRACEON is used
			BEGIN
				SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
				delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@StatementText
				');

				SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
				delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@QueryHash
				');

				SET @plan_xml.modify('declare default element namespace "http://schemas.microsoft.com/sqlserver/2004/07/showplan";
				delete /ShowPlanXML/BatchSequence/Batch/Statements/StmtSimple/@QueryPlanHash
				');
			END;

		END;
	END;

	IF @standard_plan_xml_as_string <> CAST(@plan_xml AS NVARCHAR(MAX))
	BEGIN
		INSERT INTO dbo.LOG_TF_XML_COMPARE VALUES (@test_name, @tf_scope, @TF, @TF_is_known, GETDATE(), @plan_xml, @query_error);
	END;

	-- set trace flag at right level
	IF @tf_scope = 'GLOBAL'
	BEGIN
		SET @trace_sql = 'DBCC TRACEOFF(' + CAST(@TF AS VARCHAR(5)) + ', -1) with NO_INFOMSGS';
		EXEC (@trace_sql);
	END
	ELSE IF @tf_scope = 'SESSION'
	BEGIN
		SET @trace_sql = 'DBCC TRACEOFF(' + CAST(@TF AS VARCHAR(5)) + ') with NO_INFOMSGS';
		EXEC (@trace_sql);
	END;

	SET @TF = @TF + 1;
END;

SELECT *
FROM LOG_TF_XML_COMPARE
WHERE TEST_NAME = @test_name AND TF_SCOPE = @tf_scope
ORDER BY TEST_NAME
, TF_SCOPE
, TF_NUMBER;

DBCC TRACEOFF(8757) with NO_INFOMSGS; -- enable trivial plans

END;

There are some limitations. The current version can only handle single statement queries up to 4000 characters. The trace flag to disable trivial plans is automatically set during the run to avoid some trace flags that are missed otherwise. The run time is based on the complexity of the query plan. The XML parsing isn’t very efficient but I can run one test on average every two minutes.

Running this procedure will clean the plan cache, clear any trace flags already set, and possibly do other bad things including, but not limited to, causing stack dumps or data integrity issues.

The First Kill

Looking for trace flags related to adaptive joins is a good way to test the procedure. Dima already posted about a few undocumented trace flags here so it should be easy to verify the results. I used the same table that I created as part of this blog post. Here’s the code that I ran for the test:

EXEC [dbo].[FIND_TRACE_FLAGS]
'DEMO_FOR_BLOG',
N'SELECT *
FROM dbo.MY_FIRST_CCI o
INNER JOIN dbo.SEEK_ME i ON o.JOIN_ID = i.JOIN_ID';

After 101 seconds here are the results:

I can click on the plans and diff them to get clues as to what the listed trace flags do.

Final Thoughts

Remember, this code is extremely dangerous and should never be run in production or even in an important test environment. Feel free to use it to hunt for trace flags if you wish. My only request is that you share anything that you find with the community in some form. Thanks for reading!

Below is a list of trace flags which, as far as I can tell, have never been publicly documented. I did not fully investigate many of them and many of the descriptions are just guesses. I make no guarantees and none of these should be used in production. All tests were performed on SQL Server 2017 CU2 with trace flags enabled at the global level. Special thanks to Dmitry Pilugin for offering a few corrections.

Trace Flag List

166 – Unclear. Observable effect was to change the identifier for act1008 to act1009 in a query plan.

304 – Changed the reported CachedPlanSize.

861 – According to the error log this disables buffer pool extension.

862 – According to the error log this enables buffer pool extension. This TF probably doesn’t do anything anymore.

2368 – For one query, this resulted in a parallel plan significantly more expensive than the naturally occurring serial plan. Could be related to trace flag 3651.

2374 – Removes QueryHash and QueryPlanHash information from estimated query plans.

2387 – There was a small change in CPU and IO costs for some operators. Full effect unknown.

2399 – Small changes in operator costs were observed for some queries. These were typically less than 0.01 units.

2418 – According to Dima, this trace flag disables serial Batch mode processing.

3651 – Can cause stack dumps. For one query, this resulted in a parallel plan significantly more expensive than the naturally occurring serial plan.

7356 – Added a probe residual to an adaptive join. Full effect unknown.

7398 – Changed a nested loop join to have ordered prefetch.

8665 – According to Dima, this trace flag disables local/global aggregation.

8678 – For one query this changed a bushy plan to a left deep one. There was no change in cost. Full effect unknown.

8688 – According to Dima, this trace flag disables parallel scans.

8741 – Resulted in a different join order for some queries with a higher estimated cost. Perhaps this disables Transitive Predicates? Full effect unknown.

8742 – Resulted in a different join order for some queries. Full effect unknown.

8750 – According to Dima, this trace flag skips search 0 optimization phase and moves to search 1.

8799 – According to Dima, this trace flag forces unordered scans.

9114 – Implemented a (SELECT 1) = 1 predicate as a join instead of optimizing it away.

9164 – According to Dima, this trace flag disables hash joins.

9165 – Removed an index recommendation from a plan.

9182 – Resulted in a very strange cost change to a clustered index delete.

9183 – Same observed effect as trace flag 9182.

9236 – Resulted in a different join order for some queries. Full effect unknown.

9251 – Change in cardinality estimates for some queries. It might only work with the legacy CE. Full effect unknown.

9260 – Adds an explicit sort before creation of an index spool. Almost doesn’t change the total estimated cost. Might be identical plans with just more detail shown at that step.

9284 – Changed the order of a scalar operator comparison in a single join for certain queries. Full effect unknown.

9287 – Appears to disable partial aggreation.

9341 – Resulted in a rather odd plan for a COUNT(DISTINCT) query against a CCI.

9346 – Appears to disable batch mode window aggregates.

9384 – Very slightly changed the memory grant of a query with a batch mode window aggregate.

9390 – Resulted in plan changes including parallelism for queries that shouldn’t have been eligible for parallelism based on CTFP. Full effect unknown.

9412 – Removes the new OptimizerStatsUsage information from estimated query plans.

9447 – Forces query plans to use the new referential integrity operator when validating UPDATE and DELETE queries against foreign key parent tables.

9473 – Change in cardinality estimates for some queries. Full effect unknown.

9474 – Change in cardinality estimates for some joins in certain queries. Full effect unknown.

9477 – Slight change in ratio of EstimateRebinds and EstimateRewinds was observed. Full effect unknown.

9478 – Change in cardinality estimates for some joins in certain queries. Full effect unknown.

9480 – Reduced the selectivity of a bitmap filter from 0.001 to 0.000001. Full effect unknown.

9484 – Slight change in estimated number of rewinds. Full effect unknown.

9490 – Change in cardinality estimate. Full effect unknown.

10809 – According to Dima, this trace flag force stream Aggregates for scalar aggregation in batch mode.

11001 – Results in a different join order for some queries. Full effect unknown.

11029 – Prevents new information about row goals from getting logged to the plan cache. Example of what you get without it in 2017 CU2:

<RelOp EstimateRows="2540" EstimateRowsWithoutRowGoal="2540">

Final Thoughts

Perhaps one day I will come back to some of these to investigate them further. Going through this exercise gave me a new appreciation for those among us who can state the behavior of undocumented trace flags with confidence. Thanks for reading!

SQL Server 2016 introduced a new query plan operator that mostly flew under the radar: foreign key references check. It doesn’t even show up in the list of operators:

I’m not a foreign key guy, but a new operator is interesting enough for me to poke around. It’s described as the referential integrity operator in most of the docs so I’ll also describe it that way here for the rest of the post.

What Problem Does This Operator Solve?

Let’s start with a simple parent table and a simple child table that has two columns which both reference the parent table:

DROP TABLE IF EXISTS dbo.FK_PARENT_TABLE;
CREATE TABLE dbo.FK_PARENT_TABLE (
    FKey BIGINT NOT NULL,
    PRIMARY KEY (FKey)
); 

INSERT INTO FK_PARENT_TABLE VALUES (1);

DROP TABLE IF EXISTS dbo.CHILD_TABLE_BIG;
CREATE TABLE dbo.CHILD_TABLE_BIG (
	SurrogateKey BIGINT NOT NULL,
	FKey1 BIGINT NOT NULL,
	CONSTRAINT FK_CHILD_TABLE_BIG_1 FOREIGN KEY (FKey1)
		REFERENCES FK_PARENT_TABLE (FKey),
	FKey2 BIGINT NOT NULL,
	CONSTRAINT FK_CHILD_TABLE_BIG_2 FOREIGN KEY (FKey2)
		REFERENCES FK_PARENT_TABLE (FKey),
);

What happens if we need to delete a row from the parent table? SQL Server has to check that none of the children table values match the value we want to delete. The check can be seen in the execution plan for the delete query:

In this example, we have two unindexed columns in the child table. The query optimizer does a table scan for each referencing row. CHILD_TABLE_BIG is currently empty so this isn’t a problem.

What would happen if a parent table was referenced by hundreds of child tables, such as for a date dimension table? Deleting or updating a row in the parent table would create a query plan with at least one join per incoming foreign key reference. Creating a query plan for that statement is equivalent to creating a query plan for a query containing hundreds or even thousands of joins. That query plan could take a long time to compile or could even time out. For example, I created a simple query with 2500 joins and it still hadn’t finished compiling after 15 minutes. That’s why I assume a table is limited to 253 incoming foreign key references in SQL Server 2014.

That restriction won’t be hit often but could be pretty inconvenient to work around. The referential integrity operator introduced with compatibility level 130 raises the limit from 253 to 10000. All of the joins are collapsed into a single operator which can reduce compile time and avoid errors. From a blog post by Gjorgji Gjeorgjievski:

SQL Server 2016 introduces a new Referential Integrity Operator (under compatibility level 130) that increases the limit on the number of other tables with foreign key references to a primary or unique key of a given table (incoming references), from 253 to 10,000. The new query execution operator does the referential integrity checks in place, by comparing the modified row to the rows in the referencing tables, to verify that the modification will not break the referential integrity. This results in much lower compilation times for such plans and comparable execution times.

Many of SQL Server’s query plan operators are designed to be small in scope and reusable for lots of different purposes. For example, when STRING_AGG() was released in SQL Server 2017 it wasn’t necessary for Microsoft to create a new query plan operator. That function was implemented with a combination of existing operators. It’s unfortunate that the referential integrity operator is an “all-in-one” operator. Perhaps this was the only practical way to increase the number of incoming references.

Running Out Of Stack Space

First I’ll create tables similar to before, but CHILD_TABLE_BIG will have 253 references to FK_PARENT_TABLE. The code to create those tables is too tedious and long for this blog post, and that’s saying something. After creating the tables, the next step is to set the compatibility level to 120:

ALTER DATABASE tempdb SET COMPATIBILITY_LEVEL = 120;

Now I try to create one more incoming reference:

CREATE TABLE dbo.JUST_ONE_MORE_FK (
	SurrogateKey BIGINT NOT NULL,
	FKey254 BIGINT NOT NULL,
		CONSTRAINT FK_254 FOREIGN KEY (FKey1)
		REFERENCES FK_PARENT_TABLE (FKey)
);

It worked. So did generating a plan to delete a row from the parent table, which is a bit surprising. On SQL Server 2016 or later with compatibility level 120, it’s possible to create a query plan for a delete or update against a table with more than 253 incoming references. It’s certainly possible to get into trouble with too many incoming references. For example, I get the following error when attempting to delete from a parent table with about 2000 incoming references:

Msg 8621, Level 17, State 1, Line 2015
The query processor ran out of stack space during query optimization. Please simplify the query.

Referential Integrity Operator to the Rescue

Now I’ll reset the compatibility level to 140 and reset all of the tables. Now there are only 253 incoming references to the parent table.

ALTER DATABASE tempdb SET COMPATIBILITY_LEVEL = 140;

DELETE FROM dbo.FK_PARENT_TABLE
WHERE FKey = 1;

The query plan is a long one:

Looks like we don’t get the new operator by default with just 253 incoming references. Let’s add one more reference:

DROP TABLE IF EXISTS dbo.JUST_ONE_MORE_FK;

CREATE TABLE dbo.JUST_ONE_MORE_FK (
	SurrogateKey BIGINT NOT NULL,
	FKey254 BIGINT NOT NULL,
		CONSTRAINT FK_254 FOREIGN KEY (FKey254)
		REFERENCES FK_PARENT_TABLE (FKey)
);

Here it is:

This operator is made available through the RefIntegrityMaintainer optimizer rule. If I disable that optimizer rule with 254 incoming references I get the usual error:

Msg 8622, Level 16, State 1, Line 278
Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.

It is possible to force a plan without the new operator (more on that later). It just isn’t as easy as disabling the new optimizer rule.

Is it possible to get this operator with 253 or fewer incoming references? Yes:

The foreign key references check operator is used here with just one incoming reference. This was done via a USE HINT query hint:

DELETE FROM dbo.FK_PARENT_TABLE
WHERE FKey = 1
OPTION (USE PLAN N'<?xml version="1.0" encoding="utf-16"?>
<ShowPlanXML xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" Version="1.6" Build="14.0.3008.27" xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan">
  <BatchSequence>
    <Batch>
      <Statements>
        <StmtSimple>
          <StatementSetOptions />
          <QueryPlan >
            <MemoryGrantInfo SerialRequiredMemory="0" SerialDesiredMemory="0" />
            <OptimizerHardwareDependentProperties EstimatedAvailableMemoryGrant="0" EstimatedPagesCached="0" EstimatedAvailableDegreeOfParallelism="0" MaxCompileMemory="0" />
            <RelOp AvgRowSize="0" EstimateCPU="0" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="0" LogicalOp="Foreign Key References Check" NodeId="0" Parallel="false" PhysicalOp="Foreign Key References Check" EstimatedTotalSubtreeCost="0">
              <OutputList />
              <ForeignKeyReferencesCheck>
                <RelOp AvgRowSize="0" EstimateCPU="0" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="0" LogicalOp="Delete" NodeId="1" Parallel="false" PhysicalOp="Clustered Index Delete" EstimatedTotalSubtreeCost="0">
                  <OutputList>
                    <ColumnReference Database="" Schema="" Table="" Column="" />
                  </OutputList>
                  <SimpleUpdate DMLRequestSort="false">
                    <Object Database="[D1]" Schema="[dbo]" Table="[FK_PARENT_TABLE]" Index="[PK__FK_PAREN__A19DDDFB5081F0A5]" IndexKind="Clustered" Storage="RowStore" />
                    <SeekPredicateNew>
                      <SeekKeys>
                        <Prefix ScanType="EQ">
                          <RangeColumns>
                            <ColumnReference Database="" Schema="" Table="" Column="" />
                          </RangeColumns>
                          <RangeExpressions>
                            <ScalarOperator ScalarString="">
                              <Const ConstValue="" />
                            </ScalarOperator>
                          </RangeExpressions>
                        </Prefix>
                      </SeekKeys>
                    </SeekPredicateNew>
                  </SimpleUpdate>
                </RelOp>
                <ForeignKeyReferenceCheck>
                  <IndexScan Ordered="false">
                    <Object Database="" Schema="" Table="" IndexKind="Heap" Storage="RowStore" />
                  </IndexScan>
                </ForeignKeyReferenceCheck>
              </ForeignKeyReferencesCheck>
            </RelOp>
            <ParameterList>
              <ColumnReference Column="@1" ParameterDataType="tinyint" ParameterCompiledValue="(1)" />
            </ParameterList>
          </QueryPlan>
        </StmtSimple>
      </Statements>
    </Batch>
  </BatchSequence>
</ShowPlanXML>'
);

I suspect that this plan shape can also be achieved through the query store or a plan guide but did not test that.

Striking Gold With Extended Events

I got stuck on something during my investigation so I begrudgingly went into the extended events area of SSMS. The only relevant event that I found was reason_many_foreign_keys_operator_not_used, but oh what an event it was!

Is trace flag 9448 a previously unknown (to the community) trace flag? Sure looks like it:

Not a very useful one, but I can cross “discover a trace flag” off my bucket list. I searched around a bit in sys.dm_xe_map_values but couldn’t find any other freebies.

Some of the other reasons are helpful as well (I had mistakenly thought that an alternate plan couldn’t be forced before seeing that). I have no idea what some of them mean (MERGE_OPERATION), but this blog post isn’t going to dig into all of the reasons why you might not get the operator. I’m mainly looking to understand the basics of when it can show up, what it does, and when it can go wrong.

Operator Mechanics

The estimated plan details for the operator and the XML give you some level of information, but it isn’t too clear what’s going on under the hood. Below is a theory that I formed through some testing:

For plan creation, loop through each incoming foreign key in object_id order. Look for a suitable index on that column. A suitable index is a non-filtered one with all of the foreign key columns existing as a left subset of the index key columns. If there are multiple suitable indexes, pick the one with the highest index_id.

The possible access paths I was able to get were nonclustered index seek, clustered index scan, and table scan. For query execution, process each row one at a time in the operator. Check all foreign keys in object_id order using the access method that was determined earlier. Something like the equivalent query is run for each row getting deleted or updated and for each incoming foreign key reference:

SELECT TOP 1 1
FROM CHILD_TABLE WITH (INDEX (?))
WHERE ID = ?
OPTION (MAXDOP 1);

If any query returns a row, immediately quit and throw an error. I’m not claiming that SQL Server actually runs a separate query for each check that it needs to do. In fact, I suspect that it takes some kind of shortcut using the storage engine. That could be why the referential integrity operator currently doesn’t support incoming foreign key references from columnstore indexes.

The important takeaways here are that this operator truly operates rows by row and isn’t very flexible when it comes to index selection. It’s easy to imagine a scenario in which thousands of even millions of table scans would be performed by this operator, so indexing key columns on the child tables are important for performance of this operator.

XML Structure

There’s some information in the show plan for this operator but I had trouble decoding it. There’s a partial matching indexes count field and I couldn’t figure out how to get that to be anything but zero. Filtering indexes, covering indexes, and indexes with the first column of a two column foreign key all didn’t work.

The other annoying thing is that all table accesses are described as IndexScan, even when the equivalent of an index seek will be used:

A seek won’t have a predicate specified. You can also tell apart scans and seeks by paying attention to the amount of detail in the XML.  Here’s what an index seek looks like:

<?xml version="1.0" encoding="UTF-8"?>
<ForeignKeyReferenceCheck>
   <IndexScan Ordered="false">
      <Object Database="[D1]" Schema="[dbo]" Table="[CHILD_TABLE_DIFFERENT_INDEXES]" Index="[IX_FKey2_INDEXED]" IndexKind="NonClustered" Storage="RowStore" />
   </IndexScan>
</ForeignKeyReferenceCheck>

Here’s what a clustered index scan looks like:

<?xml version="1.0" encoding="UTF-8"?>
<ForeignKeyReferenceCheck>
   <IndexScan Ordered="false">
      <Object Database="[D1]" Schema="[dbo]" Table="[CHILD_TABLE_DIFFERENT_INDEXES]" Index="[PK__CHILD_TA__A8D35536FD3AA097]" IndexKind="Clustered" Storage="RowStore" />
      <Predicate>
         <ScalarOperator ScalarString="[D1].[dbo].[CHILD_TABLE_DIFFERENT_INDEXES].[FKey1_NO_INDEX]=[D1].[dbo].[FK_PARENT_TABLE].[FKey]">
            <Compare CompareOp="EQ">
               <ScalarOperator>
                  <Identifier>
                     <ColumnReference Database="[D1]" Schema="[dbo]" Table="[CHILD_TABLE_DIFFERENT_INDEXES]" Column="FKey1_NO_INDEX" />
                  </Identifier>
               </ScalarOperator>
               <ScalarOperator>
                  <Identifier>
                     <ColumnReference Database="[D1]" Schema="[dbo]" Table="[FK_PARENT_TABLE]" Column="FKey" />
                  </Identifier>
               </ScalarOperator>
            </Compare>
         </ScalarOperator>
      </Predicate>
   </IndexScan>
</ForeignKeyReferenceCheck>

The operator details do tell you how many unmatched foreign keys that you have which is nice. But it might not be easy to immediately identify the problem column.

Compile Time and Best Case Performance

For the next set of tests I created a single parent table along with child tables of 100 columns each. The child tables had 1000 rows along with a foreign key and an index on each column. I forced the new operator to appear with fewer than 254 incoming references via a USE HINT query plan and I prevented the new operator from appearing with TF 9448 with more than 253 incoming references. For each test I deleted half of the parent table, 500 rows.

Here’s the code that never produces a plan with the referential integrity operator:

BEGIN TRANSACTION;
SET STATISTICS TIME ON;

DELETE FROM FK_PARENT_TABLE
WHERE Fkey BETWEEN 501 AND 1000
OPTION (RECOMPILE, QUERYTRACEON 9448);

SET STATISTICS TIME OFF;
ROLLBACK;

BEGIN TRANSACTION;
SET STATISTICS TIME ON;

DELETE FROM FK_PARENT_TABLE
WHERE Fkey BETWEEN 501 AND 1000
OPTION (RECOMPILE, QUERYTRACEON 9448, LOOP JOIN);

SET STATISTICS TIME OFF;
ROLLBACK;

Here’s part of the code to get the new operator:

BEGIN TRANSACTION;

DELETE FROM FK_PARENT_TABLE
WHERE Fkey BETWEEN 501 AND 1000
OPTION (RECOMPILE,
USE PLAN N'<?xml version="1.0" encoding="utf-16"?>
...
</ShowPlanXML>'
);

ROLLBACK;

Here is a chart of my results:

Here are some graphs, because good blog posts have graphs:

The referential integrity operator wins pretty handily here, although I wonder what all of the fuss around the former 253 incoming limit was about. I’m also impressed that the new operator performs so much better even when comparing to forced nested loop joins. The number of logical reads reported through SET STATISTICS IO is very similar but not identical.

Worst Case Performance

The big disadvantage of the operator (other than us not knowing what’s going on) is that table access and plan options are very limited. In addition, there seem to be no query rules or query hints which will affect the performance of the operator. I’m not saying that deleting rows from a parent table with unindexed children tables is a good practice, but you have more options in that situation without the new operator.

For this next test, I created a 100 column child table without 100 foreign keys but no indexes. The child table has 1045000 rows because I accidentally inserted too many rows into it.

Deleting 10 rows from the parent table with the new operator results in 50000 = 10 * 100 table scans, although the reporting isn’t quite correct:

Table ‘CHILD_TABLE_1’. Scan count 100, logical reads 117040000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 161204 ms, elapsed time = 163982 ms.

The table has 117040 data pages so the scan count should have been reported as 1000.

Deleting 500 rows from the parent table without the new operator results in a table scan on the inner side of a nested loop:

The cost of the scan is discounted due to the row goal. It is amusing to consider that the query optimizer assumes that a matching row will quickly be found when such a row would violate the assert for the foreign keys. Disabling the row goal gives me 100 index eager spools, which is good only for causing nightmares:

Forcing a MERGE JOIN results in parallel zones in the foreign key checking section which is interesting to see:

This query finishes faster than the query with the referential integrity operator:

Table ‘CHILD_TABLE_1’. Scan count 500, logical reads 11704000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table ‘FK_PARENT_TABLE’. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 165521 ms, elapsed time = 89318 ms.

I expect the elapsed time to be better on a machine with better hardware than mine. If I delete negative foreign keys then I get even better performance:

SQL Server Execution Times:
CPU time = 56515 ms, elapsed time = 57350 ms.

The easiest way to get a large performance difference is by creating a wide table with just one foreign key column. The referential integrity can only do scans but traditional plans have more options. Code below:

DROP TABLE IF EXISTS CHILD_TABLE_THREE_COL;
DROP TABLE IF EXISTS dbo.FK_PARENT_TABLE

CREATE TABLE FK_PARENT_TABLE (
    FKey BIGINT NOT NULL
    PRIMARY KEY (FKey)
); 

INSERT INTO FK_PARENT_TABLE
SELECT TOP (2000) -1 + ROW_NUMBER()
	OVER (ORDER BY (SELECT NULL))
FROM master..spt_values;

CREATE TABLE dbo.CHILD_TABLE_THREE_COL (
	FKey1 BIGINT NOT NULL,
		FOREIGN KEY (FKey1)
		REFERENCES FK_PARENT_TABLE (FKey),
	OtherKey BIGINT NOT NULL,
	FILLER VARCHAR(3500)
);

INSERT INTO CHILD_TABLE_THREE_COL WITH (TABLOCK)
SELECT TOP (1000 * 1000) RN / 1000
, 1
, REPLICATE('Z', 3500)
FROM
(
	SELECT ROW_NUMBER()
		OVER (ORDER BY (SELECT NULL)) RN
	FROM master..spt_values t1
	CROSS JOIN master..spt_values t2
) t;

CREATE INDEX COVERING ON CHILD_TABLE_THREE_COL (OtherKey, FKey1);

For this delete:

DELETE FROM FK_PARENT_TABLE
WHERE Fkey BETWEEN 1010 AND 1110;

Here are the stats for the refential integrity operator:

Table ‘CHILD_TABLE_THREE_COL’. Scan count 1, logical reads 50500101, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table ‘FK_PARENT_TABLE’. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 31062 ms, elapsed time = 31100 ms.

Here are the stats for a standard plan with an index spool:

Table ‘Worktable’. Scan count 101, logical reads 2955922, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table ‘CHILD_TABLE_THREE_COL’. Scan count 1, logical reads 500001, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table ‘FK_PARENT_TABLE’. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 2219 ms, elapsed time = 2223 ms.

The index spool is so effective here because the temporary object doesn’t include the FILLER column. Oddly, I wasn’t able to get the query optimizer to use a covering index, so this example will have to do.

MS Response

I contacted Microsoft to express my concerns about performance. They responded with the following:

Disabling the Operator

If the new operator is causing you some kind of problem you do have a few options. You can use undocumented trace flag 9448 to disable the feature, although I can’t recommend that for production. Columnstore indexes still aren’t supported with the operator in SQL Server 2017, so you could create an empty columnstore table with foreign keys to any relevant parent tables. You can also run your delete or update query from a database with a compatibility level of 120. It isn’t necessary for the database to contain the parent table or even any user tables.

The only performance problem that I ran into involved missing indexes, so adding those or temporarily disabling foreign keys as needed is probably the most production-friendly way of doing it.

Final Thoughts

Microsoft is doing some pretty sneaky things with the referential integrity operator. I object to the concept from an operator design standpoint but it seems to significantly reduce compile times and to provide surprisingly good performance in most cases. Thanks for reading!