We have a query on a SQL Server 2016 SP2 CU12 Enterprise where the Query Optimizer estimates that only 1 row would come out of the *Nested Loops Join* operator, in reality 108501 rows came back. This caused that the `Sort` operator spilled to TempDB.
The estimates on the inner (index seek) and outer input (index seek) of the Nested Loops Join are correct.
I added trace flags 2363 (Selectivity Computation) and 3604 (redirect the output to the messages window) and here I found that there was a badly-formed histogram:
> Plan for computation:
> CSelCalcExpressionComparedToExpression( QCOL: [Object1].Column1 x_cmpEq QCOL: [Object3].Column18 )
> Loaded histogram for column QCOL: [Object1].Column1 from stats with id 1 *** WARNING: badly-formed histogram ***
> Loaded histogram for column QCOL: [Object3].Column18 from stats with id 9
> Selectivity: 1.07973e-009
> Stats collection generated:
> CStCollJoin(ID=4, CARD=1 x_jtLeftSemi)
> CStCollBaseTable(ID=1, CARD=5.01133e+007 TBL: Schema1.Table2 AS TBL: AA)
> CStCollFilter(ID=3, CARD=108210)
> CStCollBaseTable(ID=2, CARD=2.00511e+006 TBL: Schema1.Table1 AS TBL: A)
> End selectivity computation
Above is only a part of the output, the full text can be found [here]
When I updated the badly-formed histogram with fullscan the estimates are correct (without fullscan this issue is not resolved).
But as soon as one record is inserted in the table, the histogram is badly-formed again.
The query plan (with badly-formed histogram) can be found [here] and [here] you can find the query plan after update statistics.
No query optimizer fixes are enabled.
When I enable the original cardinality estimator for this query, using trace flag 9481, I'm getting the same query plan as after update statistics.
What can cause the badly-formed histogram?
Is there a way to solve this issue?
I tried the `PERSIST_SAMPLE_PERCENT` option but it didn't make a difference, the histogram gets also badly-formed.
> What can cause the badly-formed histogram?
This is a bug of course. It occurs when SQL Server scales the inexact histogram and encounters a unique column with apparently more than one value per key. This was [partially addressed] for SQL Server 2016, but it seems to me the full fix is only present on SQL Server 2017 (I tested on CU21).
> Is there a way to solve this issue?
Use `FULLSCAN` statistics, the original CE, upgrade to SQL Server 2017, or wait for the full fix to be back-ported.
Using my standard Numbers table creation script:
DROP TABLE IF EXISTS dbo.Numbers;
-- Itzik Ben-Gan's row generator
L0 AS (SELECT 1 AS c UNION ALL SELECT 1),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS n FROM L5)
-- Destination column type integer NOT NULL
ISNULL(CONVERT(integer, N.n), 0) AS n
FROM Nums AS N
WHERE N.n >= 1
AND N.n <= 10 * 1000 * 1000
OPTION (MAXDOP 1);
ALTER TABLE dbo.Numbers
ADD CONSTRAINT PK_Numbers_n
PRIMARY KEY CLUSTERED (n)
WITH (SORT_IN_TEMPDB = ON, MAXDOP = 1, FILLFACTOR = 100);
Update the statistics to be sampled:
UPDATE STATISTICS dbo.Numbers;
Trivial query (request an estimated plan only):
FROM dbo.Numbers AS N1
FROM dbo.Numbers AS N2
WHERE N2.n = N1.n
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363);
The trace output includes:
Begin selectivity computation
CStCollBaseTable(ID=1, CARD=1e+007 TBL: dbo.Numbers AS TBL: N1)
CStCollBaseTable(ID=2, CARD=1e+007 TBL: dbo.Numbers AS TBL: N2)
ScaOp_Identifier QCOL: [N2].n
ScaOp_Identifier QCOL: [N1].n
Plan for computation:
CSelCalcExpressionComparedToExpression( QCOL: [N1].n x_cmpEq QCOL: [N2].n )
Loaded histogram for column QCOL: [N1].n from stats with id 1
*** WARNING: badly-formed histogram ***
Validated on Microsoft SQL Server 2016 (SP2-CU14).
The statistics histogram obtained via:
has entries like:
on SQL Server 2017 the histogram is:
Note the `EQ_ROWS` steps are pre-scaled rather than relying on the CE to do it.