Badly-formed histogram causes bad estimates on Nested Loop

Question

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.

Answer 1

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.

Demo

Using my standard Numbers table creation script:

DROP TABLE IF EXISTS dbo.Numbers;
GO
-- Itzik Ben-Gan's row generator
WITH
  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)
SELECT
    -- Destination column type integer NOT NULL
    ISNULL(CONVERT(integer, N.n), 0) AS n
INTO dbo.Numbers
FROM Nums AS N
WHERE N.n >= 1
AND N.n <= 10 * 1000 * 1000
OPTION (MAXDOP 1);
GO
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):

SELECT * 
FROM dbo.Numbers AS N1
WHERE EXISTS
(
    SELECT * 
    FROM dbo.Numbers AS N2
    WHERE N2.n = N1.n
)
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363);

The trace output includes:

Begin selectivity computation

Input tree:

  LogOp_LeftSemiJoin
      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_Comp x_cmpEq
          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 ***

Selectivity: 1

Validated on Microsoft SQL Server 2016 (SP2-CU14).

The statistics histogram obtained via:

DBCC SHOW_STATISTICS 
    (Numbers, [PK_Numbers_n])
    WITH HISTOGRAM;

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.