Nested Loop has very low estimates due to skewed data
Question
On SQL Server 2016 SP2 we have a query that has a very low estimate on the nested loop operator. Due to the low estimate this query also spills to tempdb.
If I'm correct SQL Server 2014+ uses Coarse Histogram Estimation to calculate the estimated number of rows on a join.
But when I execute the query, SQL Server uses the density vector to calculate the number of estimated rows.
Is SQL Server only using the Coarse Histogram Estimation if there is no where
clause?
Normally I would use filtered statistics to improve estimations when I have a table with skewed data. But in this case that doesn't seem to work.
Is there a way to improve the estimations on the nested loop?
Using following code you can reproduce the data:
create table MyTable
(
id int identity,
field varchar(50),
constraint pk_id primary key clustered (id)
)
go
create table SkewedTable
(
id int identity,
startdate datetime,
myTableId int,
remark varchar(50),
constraint pk_id primary key clustered (id)
)
set nocount on
insert into MyTable select top 1000 [name] from master..spt_values
go
insert into SkewedTable select GETDATE(),FLOOR(RAND()*(1000))+1,REPLICATE(N'A',FLOOR(RAND()*(40))+1)
go 1000
insert into SkewedTable select GETDATE(),FLOOR(RAND()*(1000))+1,REPLICATE(N'A',FLOOR(RAND()*(40))+1)
go
CREATE NONCLUSTERED INDEX [ix_field] ON [dbo].[MyTable]([field] ASC)
go
CREATE NONCLUSTERED INDEX [ix_mytableid] ON [dbo].[SkewedTable]([myTableId] ASC)
go
--95=varchar in sys.messages
set nocount off
;with cte as
(
select GETDATE() as startdate ,95 as myTableId, REPLICATE(N'B',FLOOR(RAND()*(40))+1) as remark
union all
select * from cte
)
insert into skewedtable select top 40000 * from cte
option(maxrecursion 0)
go
update statistics mytable with fullscan
go
update statistics skewedtable with fullscan
go
Solution
Normally I would use filtered statistics to improve estimations when I have a table with skewed data. But in this case that doesn't seem to work.
You should find the following filtered statistic helpful:
CREATE STATISTICS [stats id (field=varchar)]
ON dbo.MyTable (id)
WHERE field = 'varchar'
WITH FULLSCAN;
This gives the optimizer information about the distribution of id
values that match field = 'varchar'
, giving a much better selectivity estimate for the join:
The execution plan above shows exactly correct estimates with the filtered statistic, leading the optimizer to choose a hash join (for cost reasons).
This distribution information is much more important than the exact method used by the estimator to match the join histograms (fine or coarse alignment), or even the general assumptions (e.g. simple join, base containment).
If you can't do that, your options are broadly as outlined in answer to your previous question Sort spills to tempdb due to varchar(max). My preference would probably be an intermediate temporary table.
OTHER TIPS
Completely agree with the filtered index, this answer is added to expand on the other option that @PaulWhite mentioned, to use an intermediate temp table and consequentially get rid of the SORT
operator
You could add an index or change the existing index:
CREATE INDEX IX_SkewedTable_MytableId_startdate
ON SkewedTable(myTableId,startdate)
INCLUDE(remark);
Insert the values in an intermediate temp table
CREATE TABLE #temp2(param int);
INSERT INTO #temp2(param)
SELECT t.id
FROM mytable t
WHERE t.field = 'varchar';
Add an index on the temp table
CREATE INDEX IX_ID on #temp2(param);
And then use a CTE to remove the sort operator from the query plan
;WITH CTE AS
(
select TOP(999999999999)
s.myTableId,s.id,s.remark from
SkewedTable s
order by startdate
)
SELECT s.id , s.remark
from CTE s
INNER JOIN #temp2
on s.myTableId = #temp2.param
OPTION(RECOMPILE)
As mentioned by @Forrest to push the sort lower Here
Result:
Which removes the sort operator.