Change query to improve operator estimates

Question

I have a query which runs in an acceptable amount of time but I want to squeeze the most performance possible from it.

The operation I'm trying to improve is the "Index Seek" at the right of the plan, from Node 17.

I've added appropriate indexes but the estimates that I get for that operation are half of what they are supposed to be.

I've looked for changing my indexes and adding a temporary table and re-writing the query, but I couldn't simplify it more than this in order to get the right estimates.

Does anyone have any suggestions on what else I can try?

The full plan and its details can be found here.

The non-anonymized plan can be found here.

Update:

I have a feeling the initial version of the question raised a lot of confusion, so I'm going to add the original code with some explanations.

create procedure [dbo].[someProcedure] @asType int, @customAttrValIds idlist readonly
as
begin
    set nocount on;

    declare @dist_ca_id int;

    select *
    into #temp
    from @customAttrValIds
        where id is not null;

    select @dist_ca_id = count(distinct CustomAttrID) 
    from CustomAttributeValues c
        inner join #temp a on c.Id = a.id;

    select a.Id
        , a.AssortmentId 
    from Assortments a
        inner join AssortmentCustomAttributeValues acav
            on a.Id = acav.Assortment_Id
        inner join CustomAttributeValues cav 
            on cav.Id = acav.CustomAttributeValue_Id
    where a.AssortmentType = @asType
        and acav.CustomAttributeValue_Id in (select id from #temp)
    group by a.AssortmentId
        , a.Id
    having count(distinct cav.CustomAttrID) = @dist_ca_id
    option(recompile);

end

Answers:

1. Why the odd initial naming in the pasteThePlan link?

   Answer: Because I used anonymize plan from SQL Sentry Plan Explorer.

2. Why OPTION RECOMPILE?

   Answer: Because I can afford recompiles in order to avoid parameter sniffing (the data is / could be skewed). I have tested and I am happy with the plan that the Optimizer generates while using OPTION RECOMPILE.

3. WITH SCHEMABINDING?

   Answer: I'd really want to avoid that and would use it only when I have a indexed view. Anyway, this is a system function (COUNT() ) so no use for SCHEMABINDING here.

Answers to more possible questions:

1. Why do I use INSERT INTO #temp FROM @customAttrributeValues?

   Answer: Because I noticed and now know that when using variables plugged into a query, any estimates that come out of working with a variable is always 1. And I tested putting the data into a temp table and the Estimated is then equal with Actual Rows.

2. Why did I use and acav.CustomAttributeValue_Id in (select id from #temp)?

   Answer: I could have replaced it with a JOIN on #temp, but developers were very confused and proffered the IN option. I don't really think there would be a difference even by replacing and either way, there is no problem with this.

Answer 1

The plan was compiled on a SQL Server 2008 R2 RTM instance (build 10.50.1600). You should install Service Pack 3 (build 10.50.6000), followed by the latest patches to bring it up to the (current) lastest build 10.50.6542. This is important for a number of reasons, including security, bug fixes, and new features.

The Parameter Embedding Optimization

Relevant to the present question, SQL Server 2008 R2 RTM did not support the Parameter Embedding Optimization (PEO) for OPTION (RECOMPILE). Right now, you are paying the cost of recompiles without realizing one of the main benefits.

When PEO is available, SQL Server can use the literal values stored in local variables and parameters directly in the query plan. This can lead to dramatic simplifications and performance increases. There is more information about that in my article, Parameter Sniffing, Embedding, and the RECOMPILE Options.

Hash, Sort and Exchange Spills

These are only displayed in execution plans when the query was compiled on SQL Server 2012 or later. In earlier versions, we had to monitor for spills while the query was executing using Profiler or Extended Events. Spills always result in physical I/O to (and from) the persistent storage backing tempdb, which can have important performance consequences, especially if the spill is large, or the I/O path is under pressure.

In your execution plan, there are two Hash Match (Aggregate) operators. The memory reserved for the hash table is based on the estimate for output rows (in other words, it is proportional to the number of groups found at runtime). The memory granted is fixed just before execution begins, and cannot grow during execution, regardless of how much free memory the instance has. In the supplied plan, both Hash Match (Aggregate) operators produce more rows than the optimizer expected, and so may be experiencing a spill to tempdb at runtime.

There is also a Hash Match (Inner Join) operator in the plan. The memory reserved for the hash table is based on the estimate for probe side input rows. The probe input estimates 847,399 rows, but 1,223,636 are encountered at run time. This excess may also be causing a hash spill.

Redundant Aggregate

The Hash Match (Aggregate) at node 8 performs a grouping operation on (Assortment_Id, CustomAttrID), but the input rows are equal to the output rows:

This suggests the column combination is a key (so the grouping is semantically unnecessary). The cost of performing the redundant aggregate is increased by the need to pass the 1.4 million rows twice across hash partitioning exchanges (the Parallelism operators on either side).

Given that the columns involved come from different tables, it is more difficult than usual to communicate this uniqueness information to the optimizer, so it can avoid the redundant grouping operation and unnecessary exchanges.

Inefficient thread distribution

As noted in Joe Obbish's answer, the exchange at node 14 uses hash partitioning to distribute rows among threads. Unfortunately, the small number of rows and available schedulers means all three rows end up on a single thread. The apparently-parallel plan runs serially (with parallel overhead) as far as the exchange at node 9.

You can address this (to obtain round-robin or broadcast partitioning) by eliminating the Distinct Sort at node 13. The easiest way to do that is to create a clustered primary key on the #temp table, and perform the distinct operation when loading the table:

CREATE TABLE #Temp
(
    id integer NOT NULL PRIMARY KEY CLUSTERED
);

INSERT #Temp
(
    id
)
SELECT DISTINCT
    CAV.id
FROM @customAttrValIds AS CAV
WHERE
    CAV.id IS NOT NULL;

Temporary table statistics caching

Despite the use of OPTION (RECOMPILE), SQL Server can still cache the temporary table object and its associated statistics between procedure calls. This is generally a welcome performance optimization, but if the temporary table is populated with a similar amount of data on adjacent procedure calls, the recompiled plan may be based on incorrect statistics (cached from a previous execution). This is detailed in my articles, Temporary Tables in Stored Procedures and Temporary Table Caching Explained.

To avoid this, use OPTION (RECOMPILE) together with an explicit UPDATE STATISTICS #TempTable after the temporary table is populated, and before it is referenced in a query.

Query rewrite

This part assumes the changes to the creation of the #Temp table have been made already.

Given the costs of possible hash spills and the redundant aggregate (and surrounding exchanges), it may pay to materialize the set at node 10:

CREATE TABLE #Temp2
(
    CustomAttrID integer NOT NULL,
    Assortment_Id integer NOT NULL,
);

INSERT #Temp2
(
    Assortment_Id,
    CustomAttrID
)
SELECT
    ACAV.Assortment_Id,
    CAV.CustomAttrID
FROM #temp AS T
JOIN dbo.CustomAttributeValues AS CAV
    ON CAV.Id = T.id
JOIN dbo.AssortmentCustomAttributeValues AS ACAV
    ON T.id = ACAV.CustomAttributeValue_Id;

ALTER TABLE #Temp2
ADD CONSTRAINT PK_#Temp2_Assortment_Id_CustomAttrID
PRIMARY KEY CLUSTERED (Assortment_Id, CustomAttrID);

The PRIMARY KEY is added in a separate step to ensure the index build has accurate cardinality information, and to avoid the temporary table statistics caching issue.

This materialization is quite likely to occur in memory (avoiding tempdb I/O) if the instance has enough memory available. This is even more likely once you upgrade to SQL Server 2012 (SP1 CU10/SP2 CU1 or later), which has improved Eager Write behaviour.

This action gives the optimizer accurate cardinality information on the intermediate set, allows it to create statistics, and allows us to declare (Assortment_Id, CustomAttrID) as a key.

The plan for the population of #Temp2 should look like this (note the clustered index scan of #Temp, no Distinct Sort, and the exchange now uses round-robin row partitioning):

With that set available, the final query becomes:

SELECT
    A.Id,
    A.AssortmentId
FROM
(
    SELECT
        T.Assortment_Id
    FROM #Temp2 AS T
    GROUP BY
        T.Assortment_Id
    HAVING
        COUNT_BIG(DISTINCT T.CustomAttrID) = @dist_ca_id
) AS DT
JOIN dbo.Assortments AS A
    ON A.Id = DT.Assortment_Id
WHERE
    A.AssortmentType = @asType
OPTION (RECOMPILE);

We could manually rewrite the COUNT_BIG(DISTINCT... as a simple COUNT_BIG(*), but with the new key information, the optimizer does that for us:

The final plan may use a loop/hash/merge join depending on statistical information about the data that I do not have access to. One other small note: I assumed that an index like CREATE [UNIQUE?] NONCLUSTERED INDEX IX_ ON dbo.Assortments (AssortmentType, Id, AssortmentId); exists.

Anyway, the important thing about the final plans is that the estimates should be much better, and the complex sequence of grouping operations has been reduced to a single Stream Aggregate (which does not require memory and therefore cannot spill to disk).

It is hard to say that performance will actually be better in this case with the extra temporary table, but the estimates and plan choices will be much more resilient to changes in data volume and distribution over time. That may be more valuable over the long term than a small performance increase today. In any case, you now have much more information on which to base your final decision.

Answer 2

The cardinality estimates on your query are actually very good. It's rare to get the number of estimated rows to match the number of actual rows exactly, especially when you have this many joins. Join cardinality estimates are tricky for the optimizer to get right. One important thing to note is that the number of estimated rows for the inner part of the nested loop is per execution of that loop. So when SQL Server says that 463869 rows will be fetched with the index seek the real estimate in this case is number of executions (2) * 463869 = 927738 which isn't that far off from the actual number of rows, 1391608. Surprisingly, the number of estimated rows is near perfect immediately after the nested loop join at node ID 10.

Poor cardinality estimates are mostly a problem when the query optimizer picks the wrong plan or doesn't grant enough memory to the plan. I don't see any spills to tempdb for this plan, so memory looks okay. For the nested loop join that you call out you have a small outer table and an indexed inner table. What's wrong with that? To be precise, what would you expect the query optimizer to do differently here?

In terms of improving performance, the thing that stands out to me is that SQL Server is using a hashing algorithm to distribute parallel rows which results on all of them being on the same thread:

As a result, one thread does all of the work with the index seek:

That means that your query effectively does not run in parallel until the repartition streams operator at node id 9. What you probably want is round robin partitioning so that each row ends up on its own thread. That will allow two threads to do the index seek for node id 17. Adding a superfluous TOP operator may get you round robin partitioning. I can add detail here if you like.

If you really want to focus on cardinality estimates you could put the rows after the first join into a temp table. If you gather statistics on the temp table that gives the optimizer more information about the outer table for the nested loop join that you called out. It could also result in round robin partitioning.

If you aren't using trace flags 4199 or 2301 you could consider them. Trace flag 4199 offers a wide variety of optimizer fixes, but they can degrade some workloads. Trace flag 2301 changes some of the join cardinality assumptions of the query optimizer and makes it work harder. In both cases test carefully before enabling them.

Answer 3

I believe getting a better estimate on that join will not change the plan, unless 1.4 mill is a sufficient portion of the table to make the optimiser choose an index (not cluster) scan with hash or merge join. I suspect that would not be the case here, nor actually helpful, but you can test the effects by replacing inner join against CustomAttributeValues with inner hash join and inner merge join.

I've also looked more broadly at the code and can't see any way to improve it -- I'd be interested to be proven wrong of course. And if you feel like posting the full logic of what you're trying to accomplish I'd be interested in another look.

Answer 4

You are not going to improve from a [non-clustered] Index Seek. The only thing better than a non-clustered index seek is a Clustered Index Seek.

Also, I've been a SQL DBA for the last ten years, and a SQL developer for five years before that, and in my experience it is extremely rare to find an improvement to a SQL Query by studying the execution plan that you couldn't find by other means. The main reason to generate the execution plan is because it will often suggest missing indexes to you that you can add to improve performance.

The main performance gains will be in adjusting the SQL Query itself, if there are any inefficiencies there. For example, a couple months ago I got a SQL function to run 160 times faster by rewriting a SELECT UNION SELECT style pivot table to use the standard SQL PIVOT operator.

insert into Variable1 values (?), (?), (?)


select *
    into Object1
    from Variable2
        where Column1 is not null;



select Variable3 = Function1(distinct Column2) 
    from Object2 Object3
        inner join Object1 Object4 on Object3.Column1 = Object4.Column1;



select Object4.Column1
        , Object4.Column3 
    from Object5 Object4
        inner join Object6 Object7
            on Object4.Column1 = Object7.Column4
        inner join Object2 Object8 
            on Object8.Column1 = Object7.Column5
    where Object4.Column6 = Variable4
        and Object7.Column5 in (select Column1 from Object1)
    group by Object4.Column3
        , Object4.Column1
    having Function1(distinct Object8.Column2) = Variable3
    option(recompile);

So let's see, SELECT * INTO is generally less efficient than a standard INSERT Object1 (column list) SELECT column list. So I would rewrite that. Next, if Function1 was defined without a WITH SCHEMABINDING, adding a WITH SCHEMABINDING clause should allow it to run faster.

You've chosen a lot of aliases that don't make sense, like aliasing Object2 as Object3. You should choose better aliases that don't obfuscate the code. You have "Object7.Column5 in (select Column1 from Object1)".

IN clauses of this nature are always more efficient written as EXISTS (SELECT 1 FROM Object1 o1 WHERE o1.Column1 = Object7.Column5). Perhaps I should have written that the other way. EXISTS will always be at least as good as IN. It's not always better, but usually is.

Also, I doubt that option(recompile) is improving the query performance here. I would test removing it.