{"id":912,"date":"2016-08-14T14:00:50","date_gmt":"2016-08-14T14:00:50","guid":{"rendered":"http:\/\/nenadnoveljic.com\/blog\/?p=912"},"modified":"2016-08-14T14:00:50","modified_gmt":"2016-08-14T14:00:50","slug":"anti-semi-join-null-cost-calculation","status":"publish","type":"post","link":"https:\/\/nenadnoveljic.com\/blog\/anti-semi-join-null-cost-calculation\/","title":{"rendered":"Anomaly in Cost Calculation of Anti Semi Join With Nullable Columns"},"content":{"rendered":"

Introduction<\/h1>\n

While analyzing a long running query on a SQL Server database I discovered a boundary condition which revealed a flaw in the cost calculation of Anti Semi Join<\/a>.\u00a0Consequently,\u00a0the wrong cost led\u00a0to a bad execution plan that caused the query to run “forever”. In this blog post I’ll provide a test case, an analysis and a possible workaround.<\/p>\n

I’ll also\u00a0show how the max server memory and\u00a0NOT NULL\u00a0constraint can influence the execution plan selection.<\/p>\n

Setting the Scene<\/h1>\n

The test case is a simplified version of the mentioned real world scenario:<\/p>\n

create table t1 (a integer)\r\n\r\ncreate table t2 (\r\n  a integer not null ,\r\n  CONSTRAINT [t2_pk] PRIMARY KEY NONCLUSTERED ( [a] ASC )\r\n)\r\n\r\nupdate statistics t1<\/span> with rowcount=206057632,pagecount=4121154<\/span>\r\n\r\nupdate statistics t2<\/span> with rowcount=2,pagecount=1<\/span><\/code><\/pre>\n
I tweaked the statistics to make the optimizer think that the table t1 is very large and t2 extremely small containing just two records.
\nFurthermore, the maximum SQL Server memory is set to 20000 MB (or less).\u00a0Maybe it is not\u00a0obvious at the moment, but later\u00a0it will turn out that the max memory limit has a significant impact on the selection of the execution plan.<\/p>\n
SELECT name, value\r\nFROM sys.configurations\r\nWHERE name like 'max server memory%'\r\nORDER BY name \r\n\r\nmax server memory (MB)\t20000<\/code><\/pre>\n
Anti Semi Join<\/h1>\n
The following query selects all the records from t1 without corresponding values in t2:<\/p>\n
SET SHOWPLAN_text on\r\n\r\nselect count(a) from t1 \r\n  where a not in \r\n    (select a from t2) option (maxdop 1)\r\n\r\n|--Compute Scalar(DEFINE:([Expr1006]=CONVERT_IMPLICIT(int,[Expr1009],0)))\r\n    |--Stream Aggregate(DEFINE:([Expr1009]=COUNT([t1].[a])))\r\n        |--Nested Loops(Left Anti Semi Join, WHERE:([t1].[a] IS NULL OR [t1].[a]=[t2].[a]))<\/span>\r\n                |--Table Scan(OBJECT:([t1]))\r\n                |--Table Scan(OBJECT:([t2]))<\/code><\/pre>\n
The Anti Semi Join returns the inverted result of the highlighted predicate of the Nested Loop. Since it contains an OR operation, neither Merge nor Hash Match, which would be a better option in this case, could be considered as alternatives.
\nAs for the next step, let’s see what happens to the execution plan if we “make” the table t2 much larger, again, by manipulating its statistics:<\/p>\n
SET SHOWPLAN_text off\r\n\r\nupdate statistics t2<\/span> with rowcount=1320764,pagecount=146753<\/span>\r\n\r\n|--Compute Scalar(DEFINE:([Expr1006]=CONVERT_IMPLICIT(int,[Expr1009],0)))\t26060.84\r\n     |--Stream Aggregate(DEFINE:([Expr1009]=COUNT([t1].[a])))\t26060.84\r\n          |--Hash Match(Right Anti Semi Join, HASH:([t2].[a])=([t1].[a])<\/span>, RESIDUAL:([t1].[a]=[t2].[a]))\t26060.83\r\n               |--Index Scan(OBJECT:([t2].[t2_pk]))\t1.456122\r\n               |--Nested Loops(Left Anti Semi Join, WHERE:([t1].[a] IS NULL))<\/span>\t24828.88\r\n                    |--Table Scan(OBJECT:([t1]))\t3279.373\r\n                    |--Row Count Spool\t20626.37\r\n<\/span>                         |--Top(TOP EXPRESSION:((1)))\t0.0032832\r\n                              |--Index Scan(OBJECT:([t2].[t2_pk]))\t0.0032831\r\n\r\n<\/code><\/pre>\n
I cut out all of non-relevant information from the SHOWPLAN_ALL output above leaving only the total cost of the subtree at the end of each line.<\/p>\n
For the high number of records in the inner table t2 the optimizer has decided to replace the Nested Loop with a more efficient Hash Match which led to a more complex plan; namely, because of the OR operator, the IS NULL condition must be checked in a separate branch now, i.e. Nested Loop Anti Semi Join.<\/p>\n
Max Server Memory Impact<\/h1>\n
As we keep increasing memory nothing really happens – both the plan and the calculated cost remain the same. However, this is only true until a certain threshold is reached.<\/p>\n
Interestingly, setting the max server memory to 30000 MB will cause a change in the execution plan:<\/p>\n
USE master\r\nEXEC sp_configure 'max server memory (MB)', 30000\r\nRECONFIGURE WITH OVERRIDE\r\nGO \r\nConfiguration option 'max server memory (MB)' changed from 20000 to 30000<\/span>. Run the RECONFIGURE statement to install.\r\n\r\n|--Compute Scalar(DEFINE:([Expr1006]=CONVERT_IMPLICIT(int,[Expr1009],0)))\t21857.26\r\n     |--Stream Aggregate(DEFINE:([Expr1009]=COUNT([t1].[a])))\t21857.26\r\n          |--Hash Match(Right Anti Semi Join, HASH:([t2].[a])=([t1].[a]), RESIDUAL:([t1].[a]=[t2].[a]))\t21857.25\r\n               |--Index Scan(OBJECT:([t2].[t2_pk]))\t1.456122\r\n               |--Nested Loops(Left Anti Semi Join, WHERE:([t1].[a] IS NULL))\t20625.31\r\n                    |--Table Scan(OBJECT:([t1]))\t3279.373\r\n                    |--Top(TOP EXPRESSION:((1)))\t16422.8\r\n                         |--Table Scan(OBJECT:([t2]))\t16402.19<\/span><\/code><\/pre>\n
The Row Count Spool has been replaced by a Table Scan, because the cost of the Table Scan amounts to 16402.19 and is therefore considered by the optimizer to be more efficient than the Row Count Spool which has the cost 20626.37. By changing the maximum server memory and observing the estimated cost, it can be easily verified that the cost is not a function of the memory size for both Row Count Spool and Table Scan.<\/p>\n
But then again, if the cost calculation doesn’t depend on the memory limit, why was the optimizer ignoring the plan with the Table Scan inspite of its lower cost until the memory was increased? I couldn’t find any hints that would explain the observed behavior.\u00a0Possibly, the optimizer speculates that with less memory it would be more probable that some pages of the t2 table get evicted from the cache during the Nested Loop operation so it wouldn’t consider the Table Scan unless there is sufficient memory around to keep the whole t2 cached during the execution.<\/p>\n
However, in reality, the query runs with the plan with the Row Count Spool far more faster than with the plan with the Table Scan. The elapsed times are the half of a minute and “forever”, respectively.<\/p>\n
Table Scan Cost<\/h1>\n
So why has the optimizer massively underestimated the amount of work associated with the Table Scan?<\/p>\n
To answer this question, I’ll change the size of the t2 table and observe the estimated cost. In general, the total operation cost of the Table Scan within the Nested Loop is the product of the number of records in the outer source and the CPU cost for a single Table Scan plus some additional base cost. Curiously, in this particular case the cost is not a function of the rowcount of the inner table:<\/p>\n
\r\nupdate statistics t2 with rowcount=1000,pagecount=100\r\n<\/span>|--Table Scan(OBJECT:([t2]))\t16402.19<\/span>\t\r\n\r\nupdate statistics t2 with rowcount=1000000,pagecount=100000<\/span>\r\n|--Table Scan(OBJECT:([t2]))\t16402.19\t\r\n<\/span><\/code><\/pre>\n
Even after changing the size of the table by orders of magnitude, the cost hasn’t even slightly changed! As a consequence, the cost of the Table Scan of large tables will be massively underestimated misleading the optimizer to arrive at a very bad plan.<\/p>\n
To NULL or NOT to NULL – That is the Question<\/h1>\n
Hence, we ended up with a paradox – in order to improve page life expectancy and overall performance we increased the server memory, but because of the flaw in the cost calculation one query started to run significantly slower after the memory adjustment. I started to look for possible workarounds. An easy way out would have been to rewrite the query to use alternative join methods for returning the same result set, but I strived for a solution which would fix all of the queries following the same pattern without touching the code.<\/p>\n
Provided\u00a0we think of the definition of the problem once again, we will quickly come to conclusion that the whole complexity has arisen due to the fact that the optimizer has to create a new branch in the execution plan just to handle the NULL values of the table t1. If t1.a\u00a0was\u00a0mandatory, we could declare the column as NOT NULL giving the optimizer a cue not to bother dealing with the NULL records, which in turn would significantly reduce the realm of execution plan candidates to choose from, thus making the scenario of hitting an optimizer bug under some boundary conditions less probable.<\/p>\n
Although the column was never NULL on my live system, it was not declared as such. Actually, in the whole schema the application vendor avoided using NOT NULL for no obvious reason.<\/p>\n
Therefore, it came as no surprise to me that altering the column t1.a to NOT NULL resulted in a much more efficient and less volatile execution plan:<\/p>\n
alter table t1 alter column a integer not null\r\n\r\n|--Compute Scalar(DEFINE:([Expr1006]=CONVERT_IMPLICIT(int,[Expr1009],0)))\t4517.912\r\n     |--Stream Aggregate(DEFINE:([Expr1009]=Count(*)))\t4517.912\r\n          |--Hash Match(Right Anti Semi Join, HASH:([t2].[a])=([t1].[a]))\t4394.278\r\n<\/span>               |--Index Scan(OBJECT:([t2].[t2_pk]))\t1.456122\r\n               |--Table Scan(OBJECT:([t1]))\t3279.373<\/code><\/pre>\n
This plan has a much lower cost than the one which was devised when NOT NULL was not specified (4517.912 and 21857.26, respectively).<\/p>\n
In conclusion, not only does the declaration of the column as NOT NULL (if appropriate for a given case) ensure data integrity, but also it provides the optimizer with invaluable information leading to far better and more stable execution plans.<\/p>\n
Versions Affected<\/h1>\n
The problem is reproducible in the SQL Server versions 2008R2 and 2014. In contrast, it seems to be fixed in the versions 2012 and 2016.<\/p>\n
Summary<\/h1>\n
Due to a software bug the optimizer can devise a bad plan under following conditions:<\/p>\n
At this point, we’ll also\u00a0make a mental note of the Row Count Spool operation and its cost. Row Count Spool scans its input, counts the number of rows for a given key, and caches the result making it generally a more efficient operation for checking the existence of a row than Table Scan (see\u00a0the blog post<\/a> by Fabiano Amorim for understanding the Row Count Spool operation in more detail).<\/p>\n