Sql-server – Slow query – big difference between estimated and actual rows

cardinality-estimatesoptimizationsql serversql server 2014

At my work, we have a problem with a search query.

If I don't include the lookup into Table_39 (see below query), it takes 0 seconds to execute the query.
If I include the lookup (..AND (Not Exists(Select 1 From Table_39 ll ..), it takes 4 minutes and 57 seconds.

From the execution plan I can see that there is a huge discrepancy between number of expected rows and actual rows, especially in the index for Table_39 (62.6 estimated vs. 10,956,165), so I tried running UPDATE STATISTICS WITH FULLSCAN, but it didn't make any difference.

I would appreciate any input I can get on how to improve the performance of the query that includes the lookup!

Query:

select [Table_2].Gid
  into #Table_1
  from [Table_2]
where [Table_2].Gid_Line in ('{31445a8f-900b-4d64-b72f-4e2ac10fd6a7}')
union
select '{31445a8f-900b-4d64-b72f-4e2ac10fd6a7}' as Gid

create unique nonclustered index temp_Table1 on #Table_1 (Gid)
go

select top 500 Table_9.Id
 , Table_9.Gid
 , Table_9.name
 , Table_9.TimeEnter
 , Table_9.Prio
 , Table_9.Direction
 , Table_9.status
 , Table_9.CreaterId
 , Table_9.Subject
 , Table_9.BodyType
 , Table_9.Attach
 , Table_9.FromAddr
 , Table_9.ToAddr
 , Table_9.Gid_LineSet
 , Table_9.xml
from Table_9
where Table_9.Gid_LineSet in (
    select Gid
      from #Table_1
      ) 
  and not exists (
   select 1
   from Table_39 ll
   where ll.Id_Obj_To      = Table_9.Id 
    and ll.Id_ObjType_To   = 5 
    and ll.Id_ObjType_From = 3 
    and ll.Id_Obj_From in (
        9602, 10661, 10857, 10858, 10859, 68823
      , 68824, 68825, 68826, 68827, 68828, 68829
      , 68830, 68831, 68832, 68833, 68834, 372513
      )
    )
order by Table_9.Id desc

drop table #Table_1

Execution plan for slow query (with lookup): https://www.dropbox.com/s/rc1i6vvdwwc5hzh/long%20query_Cleaned.sqlplan?dl=0

Execution plan for fast query (no lookup):
https://www.dropbox.com/s/bjafn5tiy3uepul/short%20query_Cleaned.sqlplan?dl=0

Best Answer

Row goal

The issue with the estimates is most likely due to the row goal introduced by the TOP (500). See:

How (and why) does TOP impact an execution plan?

If you find the estimates are much better without the TOP, or by adding OPTION (QUERYTRACEON 4138) to the query, that would confirm the hypothesis.

Trace flag 4138 is documented in KB 2667211:

A query may take a long time to run if the query optimizer uses the Top operator in SQL Server 2008 R2 or in SQL Server 2012.

You should also enable optimizer fixes with trace flag 4199.

Indexing

Consider creating an index on table 39, keyed on:

Id_Obj_To, Id_ObjType_To, Id_ObjType_From, Id_Obj_From

Ensure Id_Obj_From has a suitable data type (not e.g. a max type).

Predicte ordering

The optimizer does not reorder NOT EXISTS clauses well in your version of SQL Server. If you expect the NOT EXISTS clause to be more selective than the Gid_LineSet predicate, reorder those two clauses in the WHERE part of the query.

Related Solutions

Sql-server – Differences between estimated and actual execution plans

The estimated execution plan is generated based solely on the statistics that SQL Server has - without actually executing the query. The query optimizer is just asked what it would most likely do with this query, based on all the information it has on the query and the data distributions etc.

This works OK, the query doesn't need to run (which could take a long time), but if the statistics are out of date, the plan might be severely skewed.

The actual execution plan is just that - the actual execution plan that was used when actually running the query. This will show you things that might hint at "out-of-date" statistics etc. But to get this, you must run the query - which can take a long time.

Sql-server – Estimated vs Actual rows differences (actual much smaller than estimated) – sort

There is no statistics generated on XML columns. The estimates is guessed based on the expressions used when querying the XML.

Using this table:

create table T(XMLCol xml not null)
insert into T values('<root><item value = "1" /></root>')

And this rather simple XML query:

select X.N.value('@value', 'int')
from T
  cross apply T.XMLCol.nodes('root/item') as X(N)

Will give you one row returned but the estimated rows returned is 200. It will be 200 regardless of what XML or how much XML you stuff into the XML column for that one row.

This is the query plan with the estimated row count displayed.

enter image description here

A way to improve, or at least change, the estimates is to give the query optimizer some more information about the XML. In this case, because I know that root really is a root node in the XML, I can rewrite the query like this.

select X2.N.value('@value', 'int')
from T
  cross apply T.XMLCol.nodes('root[1]') as X1(N)
  cross apply X1.N.nodes('item') X2(N)

That will give me an estimate of 5 rows returned.

enter image description here

The rewrite of the query will probably not speed up the shredding of the XML but if the estimates are better, chances are that the query optimizer can make smarter decisions for the rest of the query.

I have not found any documentation on what the rules are for the estimates other than a presentation by Michael Rys where he says:

Base cardinality estimate is always 10’000 rows!
Some adjustment based on pushed path filters