Why is this non-correlated query so slow?

Question

I have this query...

SELECT Distinct([TargetAttributeID]) FROM
    (SELECT distinct att1.intAttributeID as [TargetAttributeID]
        FROM AST_tblAttributes att1
        INNER JOIN
        AST_lnkProfileDemandAttributes pda
        ON pda.intAttributeID=att1.intAttributeID AND pda.intProfileID = @intProfileID

    union all

    SELECT distinct ca2.intAttributeID as [TargetAttributeID] FROM
        AST_lnkCapturePolicyAttributes ca2
        INNER JOIN
        AST_lnkEmployeeCapture ec2 ON ec2.intAdminCaptureID = ca2.intAdminCaptureID AND ec2.intTeamID = 57
        WHERE ec2.dteCreatedDate >= @cutoffdate) x

Execution Plan for the above query

The two inner distincts are looking at 32 and 10,000 rows respectively. This query returns 5 rows and executes in under 1 second.

If I then use the result of this query as the subject of an IN like so...

SELECT attx.intAttributeID,attx.txtAttributeName,attx.txtAttributeLabel,attx.txtType,attx.txtEntity FROM
    AST_tblAttributes attx WHERE attx.intAttributeID 
    IN
    (SELECT Distinct([TargetAttributeID]) FROM
    (SELECT Distinct att1.intAttributeID as [TargetAttributeID]
        FROM AST_tblAttributes att1
        INNER JOIN
        AST_lnkProfileDemandAttributes pda
        ON pda.intAttributeID=att1.intAttributeID AND pda.intProfileID = @intProfileID
    union all
    SELECT  Distinct ca2.intAttributeID as [TargetAttributeID] FROM
        AST_lnkCapturePolicyAttributes ca2
        INNER JOIN
        AST_lnkEmployeeCapture ec2 ON ec2.intAdminCaptureID = ca2.intAdminCaptureID AND ec2.intTeamID = 57
        WHERE ec2.dteCreatedDate >= @cutoffdate) x)

Execution Plan for the above query

Then it takes over 3 minutes! If I just take the result of the query and perform the IN "manually" then again it comes back extremely quickly.

However if I remove the two inner DISTINCTS....

SELECT attx.intAttributeID,attx.txtAttributeName,attx.txtAttributeLabel,attx.txtType,attx.txtEntity FROM
    AST_tblAttributes attx WHERE attx.intAttributeID 
    IN
    (SELECT Distinct([TargetAttributeID]) FROM
    (SELECT att1.intAttributeID as [TargetAttributeID]
        FROM AST_tblAttributes att1
        INNER JOIN
        AST_lnkProfileDemandAttributes pda
        ON pda.intAttributeID=att1.intAttributeID AND pda.intProfileID = @intProfileID
    union all
    SELECT ca2.intAttributeID as [TargetAttributeID] FROM
        AST_lnkCapturePolicyAttributes ca2
        INNER JOIN
        AST_lnkEmployeeCapture ec2 ON ec2.intAdminCaptureID = ca2.intAdminCaptureID AND ec2.intTeamID = 57
        WHERE ec2.dteCreatedDate >= @cutoffdate) x)

Execution Plan for the above query

..then it comes back in under a second.

What is SQL Server thinking? Can it not figure out that it can perform the two sub-queries and use the result as the subject of the IN. It seems as slow as a correlated sub-query, but it isn't correlated!!!

In Show Estimate Execution plan there are three Clustered Index Scans each with a cost of 100%! (Execution Plan is here)

Can anyone tell me why the inner DISTINCTS make this query so much slower (but only when used as the subject of an IN...) ?

UPDATE

Sorry it's taken me a while to get these execution plans up...

Query 1

Query 2 (The slow one)

Query 3 - No Inner Distincts

If you post the XML plans (for download) you will get much better responses — buckley, Jun 06 '12 at 10:58
@buckley Thanks, updated. [Here's the link](http://pastebin.com/CLdQGGsq) — El Ronnoco, Jun 06 '12 at 11:10
So, remove the `DISTINCT` when using this with an `IN` subquery. Problem solved :) — ypercubeᵀᴹ, Jun 11 '12 at 09:46
How do you even end up writing this - why are you doing the distinct work 3 times over yourself, when just switching to `union` (from `union all` would perform that operation automatically)? — Damien_The_Unbeliever, Jun 11 '12 at 09:47
You can remove them in the first query as well - just change `UNION ALL` into `UNION` — ypercubeᵀᴹ, Jun 11 '12 at 09:48
@ypercube Yes, I know how to *solve* the problem - I want to know what SQLServer is doing to make it so slow. If the first query executes in under 1 second - why is it so slow when that query is used as an `IN(...)`? — El Ronnoco, Jun 11 '12 at 10:08
@Damien_The_Unbeliever I wrote this in parts and then threw it together and was just perplexed as to why it was so slow. This question isn't about how to make this query faster. I've done that. It't about how SQLServer is executing it and why it is doing it so slowly. — El Ronnoco, Jun 11 '12 at 10:10
Is there a **performance** difference between the 2 versions (with and without `DISTINCT`) in the first query, without using `IN`? — ypercubeᵀᴹ, Jun 11 '12 at 10:12
@ypercube The `IN(...)` clause returns the same set of IDs in both versions. `txtAttributeName`, `txtAttributeLabel` and `txtType` are all nullable. — El Ronnoco, Jun 11 '12 at 10:16
I meant if there is performance difference when not using `IN`. Your first query with and without `DISTINCT` - without any `IN`. — ypercubeᵀᴹ, Jun 11 '12 at 10:17
I think this belongs better to [dba.stackexchange.com](http://dba.stackexchange.com), you'll probably get better answers there. You can flag it for migration. — ypercubeᵀᴹ, Jun 11 '12 at 10:21
(the nullability question was about the `TargetAttributeID` columns.) — ypercubeᵀᴹ, Jun 11 '12 at 10:23
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/12381/discussion-between-el-ronnoco-and-ypercube) — El Ronnoco, Jun 11 '12 at 10:23
Actual execution plans rather than estimated plans would be better and for both the queries (2nd and 3rd) — Martin Smith, Jun 11 '12 at 13:13
Don't understand why you would put a bounty on the question then fail to provide the requested information, so you are just left with speculation rather than a definitive answer. — Martin Smith, Jun 18 '12 at 09:02
@MartinSmith - apologies, I have been busy at work - Updated with actual plans on my post... — El Ronnoco, Jun 18 '12 at 11:04
@ElRonnoco - The plan for the slow one is still the actual, not the estimated. It doesn't have the actual number of rows in it so we can see if there are any big discrepancies as alluded to by Thomas Kejser — Martin Smith, Jun 18 '12 at 17:44

Peter Radocchia · Accepted Answer · 2012-06-14T02:59:48.697

Honestly I think it comes down to the fact that, in terms of relational operators, you have a gratuitously baroque query there, and SQL Server stops searching for alternate execution plans within the time it allows itself to find one.

After the parse and bind phase of plan compilation, SQL Server will apply logical transforms to the resulting tree, estimate the cost of each, and choose the one with the lowest cost. It doesn't exhaust all possible transformations, just as many as it can compute within a given window. So presumably, it has burned through that window before it arrives at a good plan, and it's the addition of the outer semi-self-join on AST_tblAttributes that pushed it over the edge.

How is it gratuitously baroque? Well, first off, there's this (simplified for noise reduction):

select distinct intAttributeID from (
   select distinct intAttributeID from AST_tblAttributes ....
   union all
   select distinct intAttributeID from AST_tblAttributes ....
   )

Concatenating two sets, and projecting the unique elements? Turns out there's operator for that, it's called UNION. So given enough time during plan compilation and enough logical transformations, SQL Server will realize what you really mean is:

select intAttributeID from AST_tblAttributes ....
union
select intAttributeID from AST_tblAttributes ....

But wait, you put this in a correlated subquery. Well, a correlated subquery is a semi-join, and the right relation does not require logical dedupping in a semi-join. So SQL Server may logically rewrite the query as this:

select * from AST_tblAttributes
where intAttributeID in (
  select intAttributeID from AST_tblAttributes ....
  union all
  select intAttributeID from AST_tblAttributes ....
  )

And then go about physical plan selection. But to get there, it has to see though the cruft first, and that may fall outside the optimization window.

EDIT:

Really, the way to explore this for yourself, and corroborate the speculation above, is to put both versions of the query in the same window and compare estimated execution plans side-by-side (Ctrl-L in SSMS). Leave one as is, edit the other, and see what changes.

You will see that some alternate forms are recognized as logically equivalent and generate to the same good plan, and others generate less optimal plans, as you bork the optimizer.**

Then, you can use SET STATISTICS IO ON and SET STATISTICS TIME ON to observe the actual amount of work SQL Server performs to execute the queries:

SET STATISTICS IO ON
SET STATISTICS TIME ON

SELECT ....
SELECT ....

SET STATISTICS IO OFF
SET STATISTICS TIME OFF

The output will appear in the messages pane.

** Or not--if they all generate the same plan, but actual execution time still varies like you say, something else may be going on--it's not unheard of. Try comparing actual execution plans and go from there.

+1 Is this a correlated subquery though? It's not my understanding of what a correlated subquery is. For that I would alias the outer AST_tblAttributes and then refer to columns from that outer table within the inner table - however I do not do this... — El Ronnoco, Jun 13 '12 at 11:16
You are correct, this syntax does not use explicit correlation. However, `this.intAttributeID IN (...)` makes it a semi-join, and is equivalent to the explicitly correlated form `EXISTS (.... WHERE this.intAttributeID = that.intAttributeID)`. — Peter Radocchia, Jun 13 '12 at 15:12

score 2 · Answer 2 · answered Jun 14 '12 at 23:24

El Ronnoco

First of all a possible explanation:

You say that: "This query returns 5 rows and executes in under 1 second.". But how many rows does it ESTIMATE are returned? If the estimate is very much off, using the query as part of the IN part could cause you to scan the entire: AST_tblAttributes in the outer part, instead of index seeking it (which could explain the big difference)

If you shared the query plans for the different variants (as a file, please), I think I should be able to get you an idea of what is going on under the hood here. It would also allow us to validate the explanation.

Russell Fox · Answer 3 · 2012-06-12T16:14:46.063

1

Edit: each DISTINCT keyword adds a new Sort node to your query plan. Basically, by having those other DISTINCTs in there, you're forcing SQL to re-sort the entire table again and again to make sure that it isn't returning duplicates. Each such operation can quadruple the cost of the query. Here's a good review of the effects that the DISTINCT operator can have, intended an unintended. I've been bitten by this, myself.

Are you using SQL 2008? If so, you can try this, putting the DISTINCT work into a CTE and then joining to your main table. I've found CTEs to be pretty fast:

WITH DistinctAttribID
AS
(
SELECT Distinct([TargetAttributeID]) 
FROM (
    SELECT distinct att1.intAttributeID as [TargetAttributeID] 
        FROM AST_tblAttributes att1 
        INNER JOIN 
        AST_lnkProfileDemandAttributes pda 
        ON pda.intAttributeID=att1.intAttributeID AND pda.intProfileID = @intProfileID 

    UNION ALL 

    SELECT distinct ca2.intAttributeID as [TargetAttributeID] FROM 
        AST_lnkCapturePolicyAttributes ca2 
        INNER JOIN 
        AST_lnkEmployeeCapture ec2 ON ec2.intAdminCaptureID = ca2.intAdminCaptureID AND ec2.intTeamID = 57 
        WHERE ec2.dteCreatedDate >= @cutoffdate
) x

SELECT attx.intAttributeID,
    attx.txtAttributeName,
    attx.txtAttributeLabel,
    attx.txtType,
    attx.txtEntity 
FROM AST_tblAttributes attx 
JOIN DistinctAttribID attrib
    ON attx.intAttributeID = attrib.TargetAttributeID

edited Jun 12 '12 at 16:14

answered Jun 12 '12 at 00:28

Russell Fox

5,273
1
24
28

Thanks for your answer Russell. I am using 2008 yes. Unfortunately your query doesn't execute. However I don't believe you have understood my question - I know how to make the query quicker. As others have said above I can remove all DISTINCTS from the query. What I want to know is why SQLServer doesn't optimise as effectively as it could. – El Ronnoco Jun 12 '12 at 09:22
Oh, right, answering the question (need coffee). Answer edited, if that helps. – Russell Fox Jun 12 '12 at 16:15
@RussellFox, each DISTINCT keyword *may* add a new sort node, it depends on a) where the `DISTINCT` occurs and b) whether SQL can detect a column that will necessarily be distinct. – Peter Radocchia Jun 12 '12 at 22:09
But what I don't understand is that the first query (at the top of my question) executes in under 1 second (and that has 3 DISTINCTS in it). It returns 5 IDs - If I just say eg `IN (23,145,167,180,190)` then the full query executes very quickly. However if I use the first query as the subject of the `IN(..)` then it takes 3 mins - even though they are doing exactly the same thing... – El Ronnoco Jun 13 '12 at 10:21
I suspect the outer query is having to check for distinctness in the inner queries for every attx.intAttributeID, so that sort is getting called for every row in the outer query. Just a guess, though. – Russell Fox Jun 13 '12 at 16:55

Why is this non-correlated query so slow?

3 Answers3