How can row estimates be improved in order to reduce chances of spills to tempdb

Question

I notice that when there are spill to tempdb events (causing slow queries) that often the row estimates are way off for a particular join. I've seen spill events occur with merge and hash joins and they often increase the runtime 3x to 10x. This question concerns how to improve row estimates under the assumption that it will reduce chances of spill events.

Actual Number of rows 40k.

For this query, the plan shows bad row estimate (11.3 rows):

select Value
  from Oav.ValueArray
 where ObjectId = (select convert(bigint, Value) NodeId
                     from Oav.ValueArray
                    where PropertyId = 3331  
                      and ObjectId = 3540233
                      and Sequence = 2)
   and PropertyId = 2840
option (recompile);

For this query, the plan shows good row estimate (56k rows):

declare @a bigint = (select convert(bigint, Value) NodeId
                       from Oav.ValueArray
                      where PropertyId = 3331
                        and ObjectId = 3540233
                        and Sequence = 2);

select Value
  from Oav.ValueArray
 where ObjectId = @a               
   and PropertyId = 2840
option (recompile);

Can statistics or hints be added to improve the row estimates for the first case? I tried adding statistics with particular filter values (property = 2840) but either could not get the combination correct or perhaps it is being ignored because the ObjectId is unknown at compile time and it might be choosing an average over all ObjectIds.

Is there any mode where it would do the probe query first and then use that to determine the row estimates or must it fly blindly?

This particular property has many values (40k) on a few objects and zero on the vast majority. I would be happy with a hint where the max expected number of rows for a given join could be specified. This is a generally haunting problem because some parameters may be determined dynamically as part of the join or would be better placed within a view (no support for variables).

Are there any parameters that can be adjusted to minimize chance of spills to tempdb (e.g. min memory per query)? Robust plan had no effect on the estimate.

Edit 2013.11.06: Response to comments and additional information:

Here are the query plan images. The warnings are about the cardinality/seek predicate with the convert():

Per @Aaron Bertrand's comment, I tried replacing the convert() as a test:

create table Oav.SeekObject (
       LookupId bigint not null primary key,
       ObjectId bigint not null
);

insert into Oav.SeekObject (
   LookupId, ObjectId
) VALUES (
   1, 3540233
) 

select Value
  from Oav.ValueArray
 where ObjectId = (select ObjectId 
                     from Oav.SeekObject 
                    where LookupId = 1)
   and PropertyId = 2840
option (recompile);

As a odd but successful point of interest, also allowed it to short circuit the lookup:

select Value
  from Oav.ValueArray
 where ObjectId = (select ObjectId 
                     from Oav.ValueArray
                    where PropertyId = 2840
                      and ObjectId = 3540233
                      and Sequence = 2)
   and PropertyId = 2840
option (recompile);

Both of these list a proper key lookup but only the first ones lists an "Output" of ObjectId. I guess that indicates the second is indeed short circuiting?

Can someone verify whether single-row probes are ever performed to help with row estimates? Its seems wrong to limit optimization to only histogram estimates when a single-row PK lookup can greatly improve the accuracy of the lookup into the histogram (especially if there is spill potential or history). When there are 10 of these sub-joins in a real query, ideally they would be happening in parallel.

A side note, since sql_variant stores its base type (SQL_VARIANT_PROPERTY = BaseType) within the field itself, I would expect a convert() to be nearly costless so long as it is "directly" convertible (e.g. not string to decimal but rather int to int or maybe int to bigint). Since that is not known at compile time but may be known by the user, perhaps an "AssumeType(type, ...)" function for sql_variants would allow them to be treated more transparently.

Answer 1

I won't comment about spills, tempdb or hints because the query seems pretty simple to need that much consideration. I think SQL-Server's optimizer will do its job quite good, if there are indexes suited for the query.

And your splitting into two queries is good as it shows what indexes will be useful. The first part:

(select convert(bigint, Value) NodeId
 from Oav.ValueArray
 where PropertyId = 3331  
   and ObjectId = 3540233
   and Sequence = 2)

needs an index on (PropertyId, ObjectId, Sequence) including the Value. I'd make it UNIQUE to be safe. The query would throw error anyway during runtime if more than one rows were returned, so it's good to ensure in advance that this won't happen, with the unique index:

CREATE UNIQUE INDEX
    PropertyId_ObjectId_Sequence_UQ
  ON Oav.ValueArray
    (PropertyId, ObjectId, Sequence) INCLUDE (Value) ;

The second part of the query:

select Value
  from Oav.ValueArray
 where ObjectId = @a               
   and PropertyId = 2840

needs an index on (PropertyId, ObjectId) including the Value:

CREATE INDEX
    PropertyId_ObjectId_IX
  ON Oav.ValueArray
    (PropertyId, ObjectId) INCLUDE (Value) ;

If efficiency is not improved or these indexes were not used or there are still differences in row estimates appearing, then there would be need to look further into this query.

In that case, the conversions (needed from the EAV design and the storing of different datatypes in the same columns) are a probable cause and your solution of splitting (as @AAron Bertrand and @Paul White comment) the query into two parts seems natural and the way to go. A redesign so to have different datatypes in their respective columns might be another.

Answer 2

As a partial answer to the explicit question on improving statistics...

Note that the row estimates even for the broken up separately case are still off by 10X (4k vs expected 40k).

The statistics histogram was likely spread too thin for that property because it is a long (vertical), 3.5M rows table and that particular property is extremely sparse.

Create an additional statistics (somewhat redundant with the IX statistics) for the sparse property:

create statistics [STAT_ValueArray_ObjPropValue_WhereProp2840] ON [Oav].[ValueArray](ObjectId, PropertyId, Value)
where PropertyId = 2840

The original's:

With convert() removed (proper):

With convert() removed (short-ciruit):

Still off by ~2X likely because >99.9% of the objects do not have Property 2840 defined on them at all. In fact just for this test case the property exists just on on 1 of 200k distinct Objects of the 3.5M row table. Its amazing it got that close really. Adjusting the filter to be fewer ObjectIds,

create statistics [STAT_ValueArray_ObjPropValue_WhereProp2840] ON [Oav].[ValueArray](ObjectId, PropertyId, Value)
where PropertyId = 2840 and ObjectId >= 3540000 and ObjectId < 3541000

create statistics [STAT_ValueArray_ObjPropValue_WhereProp2840] ON [Oav].[ValueArray](ObjectId, PropertyId, Value)
where PropertyId = 2840 and ObjectId = 3540233;

Hmm, no change... Backed that out added "with full scan" to end of statistics (might be why the previous two didn't work) and yes:

create statistics [STAT_ValueArray_ObjPropValue_WhereProp2840] ON [Oav].[ValueArray](ObjectId, PropertyId, Value)
where PropertyId = 2840 with full scan;

Yay. So in a highly vertical table with a broadly covering IX, adding additional filtered statistics appears to be a great improvement (notably for sparse but highly variant key combinations).