2

A custom statistic exists for the CacheId column of a table. After an overnight statistics update:

Statistics for INDEX 'ST_TableName_CacheId'.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Name                            Updated                         Rows                            Rows Sampled                    Steps                           Density                         Average Key Length              String Index                    
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ST_TableName_CacheId Apr 26 2014  2:04AM             121482                          121482                          6                               0                               4                               NO                                                              121482                          

All Density                     Average Length                  Columns                         
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0.1666667                       4                               CacheId                         

Histogram Steps                 
RANGE_HI_KEY                    RANGE_ROWS                      EQ_ROWS                         DISTINCT_RANGE_ROWS             AVG_RANGE_ROWS                  
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
39968                           0                               20247                           0                               1                               
40058                           0                               20247                           0                               1                               
40062                           0                               20247                           0                               1                               
40066                           0                               20247                           0                               1                               
40069                           0                               20247                           0                               1                               
41033                           0                               20247                           0                               1                               

1) Performance of a join against an existing data set in this table where CacheId = 41033 perform well with good estimates (23622 vs actual of 20247).

2) Then an insert is performed with CacheId = 41273 of 20247 rows.

3) Then a join against this newly inserted data set shows a poor estimate of 1 row resulting in a bad plan.

4) A manual update of the statistics (which was originally with fullscan) shows a new histogram:

Statistics for INDEX 'ST_TableName_CacheId'.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Name                            Updated                         Rows                            Rows Sampled                    Steps                           Density                         Average Key Length              String Index                    
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ST_TableName_CacheId Apr 28 2014 10:41AM             141729                          141729                          7                               0                               4                               NO                                                              141729                          

All Density                     Average Length                  Columns                         
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0.1428571                       4                               CacheId                         

Histogram Steps                 
RANGE_HI_KEY                    RANGE_ROWS                      EQ_ROWS                         DISTINCT_RANGE_ROWS             AVG_RANGE_ROWS                  
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
39968                           0                               20247                           0                               1                               
40058                           0                               20247                           0                               1                               
40062                           0                               20247                           0                               1                               
40066                           0                               20247                           0                               1                               
40069                           0                               20247                           0                               1                               
41033                           0                               20247                           0                               1                               
41274                           0                               20247                           0                               1                               

5) Running the same join query again for the CacheId = 41274 shows perfect estimates (20247) and good performance.

Q1) Why mathematically is the original estimate so bad? I mean the CacheId's are sparse but not at a ratio of 20000:1.

Q2) As the number of cacheId's increases would you expect the estimates for newly inserted data improve naturally?

Q3) Are there any ways (gulp, tricks or otherwise) to improve the estimate (or make it less certain of 1 row) without having to update the statistics every time a new set of data is inserted (e.g. adding a fake data set at a much larger CacheId = 999999).

Here are the true number of rows for all CacheId's within the table:

CacheId Rows
39968   20247
40058   20247
40062   20247
40066   20247
40069   20247
41033   20247
41274   20247

[ I don't think QP's are needed to answer this question and its some work to clean them up. I can answer specific questions if needed! ]

  • Q1: because the cardinality estimator is far from perfect, and hasn't received a lot of love since before 2000. 2014 makes some great improvements, but I don't know if it will fix this. – Aaron Bertrand Apr 28 '14 at 18:45
  • Q2. No, I would not expect estimates to get better over time, in fact I would expect them to get worse, because as the table gets bigger, the threshold to kick in automatic statistics updates gets harder to hit. – Aaron Bertrand Apr 28 '14 at 18:46
  • You need to take a look at the histogram after you insert new rows but before you update the stats. Autostats update is triggered -- The table had more than 500 rows when the statistics were gathered, and the colmodctr of the leading column of the statistics object has changed by more than 500 + 20% of the number of rows in the table when the statistics were gathered. -- Statistics Used by the Query Optimizer in Microsoft SQL Server 2008. 20% + 500 in your case = 24,796.4! Not enough to trigger an autoupdate. – DenisT Apr 28 '14 at 18:47
  • @DenisT, at that time, as you calculate, the histogram had not updated automatically. So it sounds like a 2nd insert of that row count would easily trigger an auto update. So initially 1 of every 2 insert/queries would be good then Aaron Bertrand expects them to get worse over time (1/3, 1/4, etc...) unless something else kicks in. I have verified that this is the case for a few iterations. – crokusek Apr 28 '14 at 21:33
5

Q1) Why mathematically is the original estimate so bad? I mean the CacheId's are sparse but not at a ratio of 20000:1.

Here is the rule to trigger auto update the stats Statistical maintenance functionality (autostats) in SQL Server:

The above algorithm can be summarised in the form of a table:


Table Type | Empty Condition | Threshold When Empty |Threshold When Not Empty


Permanent | < 500 rows | # of Changes >= 500 | # of Changes >= 500 + (20% of Cardinality)

Even thought the KB point to 2000, it's still true up to 2012.

Run through this scenario and see for yourself.

STEP#1

SET STATISTICS IO OFF;
GO
SET NOCOUNT ON;
GO
-- make sure the Include Actual Execution Plan is off!!!
IF OBJECT_ID('IDs') IS NOT NULL
DROP TABLE dbo.IDs;

CREATE TABLE IDs
(
ID tinyint NOT NULL
)

INSERT INTO IDs
SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7;

IF OBJECT_ID('TestStats') IS NOT NULL
DROP TABLE dbo.TestStats;

CREATE TABLE dbo.TestStats
(
 ID tinyint NOT NULL,
 Col1 int NOT NULL,
 CONSTRAINT PK_TestStats PRIMARY KEY CLUSTERED (ID, col1)
);

DECLARE @id int = 1
DECLARE @i int = 1

WHILE @id <= 6
BEGIN
 SET @i = 1

WHILE @i <= 20247
BEGIN
    INSERT INTO dbo.TestStats VALUES(@id,@i);

    SET @i = @i + 1
END

SET @id = @id + 1
END

-- so far so good!
SELECT ID, COUNT(*) AS RowCnt FROM dbo.TestStats GROUP BY ID;

DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;

Now we have a table with IDs 1 through 6 and each ID has 20247 rows. Stats look good so far!

STEP#2

-- now insert another ID = 7 with 20247 rows
DECLARE @i int = 1;

WHILE @i <= 20247
BEGIN
  INSERT INTO dbo.TestStats VALUES(7,@i);

  SET @i = @i + 1
END

-- see the problem with the histogram?
SELECT ID, COUNT(*) FROM dbo.TestStats GROUP BY ID;

DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;

Look at the table and histogram! The actual table has ID = 7 with 20247 rows but the histogram has no idea that you've just inserted the new data because the auto update didn't trigger. According the the formula you need to insert (20247 * 6) * 0.2 + 500 = 24,796.4 rows to trigger an auto update for stats on this table.

Thus, if you look at the plans for these queries you see the wrong estimates:

-- CTRL + M to include the Actual Execution plan
-- now, IF we run these queries, the Optimizer has no info about ID = 7
-- and the Estimates 1 because it cannot say 0.
SELECT ts.*
FROM dbo.TestStats ts
INNER JOIN dbo.IDs ON IDs.ID = ts.ID
WHERE IDs.ID = 1;

SELECT ts.*
FROM dbo.TestStats ts
INNER JOIN dbo.IDs ON IDs.ID = ts.ID
WHERE IDs.ID = 7;

Query #1:

Query #1:

Query #2:

Query #2

The Optimize cannot say 0 rows, so it just shows you 1.

STEP#3

-- now we manually update the stats
UPDATE STATISTICS dbo.TestStats WITH FULLSCAN;

-- check the histogram
DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;

-- rerun the queries
SELECT ts.*
FROM dbo.TestStats ts
INNER JOIN dbo.IDs ON IDs.ID = ts.ID
WHERE IDs.ID = 1;

SELECT ts.*
FROM dbo.TestStats ts
INNER JOIN dbo.IDs ON IDs.ID = ts.ID
WHERE IDs.ID = 7;

Now the histogram show the missing ID 7 and the execution plans show the right estimates as well.

Query #1:

Query #1

Query #2:

Query #2

Q2) As the number of cacheId's increases would you expect the estimates for newly inserted data improve naturally?

Yes, as soon as you pass the threshold of 20% + 500 from the total rows. The auto update will trigger. You can run though this scenario by re-running STEP#1, but then modify STEP#2 by running these queries:

-- now insert another ID = 7 with 20247 rows
DECLARE @i int = 1;

WHILE @i <= 20247
BEGIN
   INSERT INTO dbo.TestStats VALUES(7,@i);

   SET @i = @i + 1
END

-- see the problem with the histogram?
SELECT ID, COUNT(*) FROM dbo.TestStats GROUP BY ID;

DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;
GO
-- try to insert ID = 8 to trigger the auto update for the stats
DECLARE @i int = 1;

WHILE @i <= 4548
BEGIN
  INSERT INTO dbo.TestStats VALUES(8,@i);

  SET @i = @i + 1
END

-- no update yet
SELECT ID, COUNT(*) FROM dbo.TestStats GROUP BY ID;

DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;

No update yet because the threshold is 24,796.4 - 20247 = 4549.4 but we inserted only 4548 rows for ID 8. Now insert this one row and double check the histogram:

-- this will trigger the update
INSERT INTO dbo.TestStats VALUES(8,4549);

-- double check
SELECT ID, COUNT(*) FROM dbo.TestStats GROUP BY ID;

DBCC SHOW_STATISTICS('TestStats',PK_TestStats) WITH HISTOGRAM;

Q3) Are there any ways (gulp, tricks or otherwise) to improve the estimate (or make it less certain of 1 row) without having to update the statistics every time a new set of data is inserted (e.g. adding a fake data set at a much larger CacheId = 999999).

Controlling Autostat (AUTO_UPDATE_STATISTICS) behavior in SQL Server

However, when a table becomes very large, the old threshold (a fixed rate – 20% of rows changed) may be too high and the Autostat process may not be triggered frequently enough. This could lead to potential performance problems. SQL Server 2008 R2 Service Pack 1 and later versions introduce trace flag 2371 that you can enable to change this default behavior. The higher the number of rows in a table, the lower the threshold will become to trigger an update of the statistics. For example, if the trace flag is activated, update statistics will be triggered on a table with 1 billion rows when 1 million changes occur. If the trace flag is not activated, then the same table with 1 billion records would need 200 million changes before an update statistics is triggered.

Hope this helped you to understand! Pretty good question!

  • Wow, I'm giving the answer to you for nice test case/effort. I understand the update thresholds, but that really isn't a valid excuse for such a poor estimate. On Q1) given that there is a threshold like that, and assuming that one is always inserting new data at the end, that means that very often the queries will not have histogram entries and 0/1 row is just seems like a terrible estimate given all the other data from the histogram. I wish someone could delve into the histogram interpolation (or lack of extrapolation) and assumptions to explain why that should be a "good" estimate. – crokusek Apr 28 '14 at 23:02
  • On Q2 you say yes. But I think you would agree that it is only true for just that one insert/query that triggers the statistics update, then the next insert/query will go bad again as the statistics become stale. – crokusek Apr 28 '14 at 23:04
  • It looks like Sql Server 2014 may address this issue as the "ascending key" problem – crokusek Apr 28 '14 at 23:52
  • @crokusek Ascending keys has had a trace flag solution since 2005 SP1. – Mark Storey-Smith Apr 28 '14 at 23:57
  • Thanks @MarkStorey-Smith. I verified that putting tracon(2989, 2390) works for the original case. I understand those would need to be set by an sysadmin account. Do tracon's stick between re-starts? – crokusek Apr 29 '14 at 0:57
1

One answer to Q3)

Q3) Are there any ways (gulp, tricks or otherwise) to improve the estimate (or make it less certain of 1 row) without having to update the statistics every time a new set of data is inserted (e.g. adding a fake data set at a much larger CacheId = 999999).

In the join, add some confusion using IsNull(), and at the end, add an "optimize for".

 select ... from ... join ...
   where CacheId = IsNull(@cacheId, 0)    
  option (recompile, optimize for (@cacheId = 41274))

Both seem to be needed. The Id 0 does not really exist. The ID value used within the "optimize for" does not appear to matter, and apparently does not even need to exist.

Side Note: I had also tried deleting the custom statistics, adding an fresh index on CacheId but its implicit statistics still eventually behaved the same as the explicit custom statistics as far as the update row count thresholds.

Edit 2014-04-29:

The estimates for "ascending keys" has likely been improved in SQL Server 2014's improved Cardinality Estimator

There is also a traceon() solution for Ascending keys since 2005 SP1 from Mark Storey-Smith comment.

Edit 2015-05-07:

Some cases were still estimating 1 row (sometimes). Using unknown appears to help and then the IsNull() can also be removed:

  select ... from ... join ...
   where CacheId = @cacheId
  option (recompile, optimize for (@cacheId = unknown))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.