Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Consider the following simple query (only 3 tables involved)

    SELECT

        l.sku_id AS ProductId,
        l.is_primary AS IsPrimary,
        v1.category_name AS Category1,
        v2.category_name AS Category2,
        v3.category_name AS Category3,
        v4.category_name AS Category4,
        v5.category_name AS Category5

    FROM category c4
    JOIN category_voc v4 ON v4.category_id = c4.category_id and v4.language_code = 'en'

    JOIN category c3 ON c3.category_id = c4.parent_category_id
    JOIN category_voc v3 ON v3.category_id = c3.category_id and v3.language_code = 'en'

    JOIN category c2 ON c2.category_id = c3.category_id
    JOIN category_voc v2 ON v2.category_id = c2.category_id and v2.language_code = 'en'

    JOIN category c1 ON c1.category_id = c2.parent_category_id
    JOIN category_voc v1 ON v1.category_id = c1.category_id and v1.language_code = 'en'

    LEFT OUTER JOIN category c5 ON c5.parent_category_id = c4.category_id
    LEFT OUTER JOIN category_voc v5 ON v5.category_id = c5.category_id and v5.language_code = @lang

    JOIN category_link l on l.sku_id IN (SELECT value FROM #Ids) AND
    (
        l.category_id = c4.category_id OR
        l.category_id = c5.category_id
    )

    WHERE c4.[level] = 4 AND c4.version_id = 5

This is a pretty simple query, the only confusing part is the last category join, it's this way because category level 5 might or might not exist. At the end of the query I am looking for category info per product ID (SKU ID), and the that's where the very large table category_link comes in. Finally, the table #Ids is just a temp table containing 10'000 Ids.

When executed, I get the following actual execution plan:

Actual Execution Plan

As you can see, almost 90% of the time is spent in the Nested Loops (Inner Join). Here's extra information on those Nested Loops:

Nested Loops (Inner Join)

Note that the table names don't match exactly because I edited the query table names for readability, but it's pretty easy to match (ads_alt_category = category). Is there any way to optimize this query? Also note that in production, the temp table #Ids doesn't exist, it's a Table Valued Parameter of the same 10'000 Ids passed on to the Stored Procedure.

Additional info:

  • category indices on category_id and parent_category_id
  • category_voc index on category_id, language_code
  • category_link index on sku_id, category_id

Edit (solved)

As pointed out by the accepted answer, the problem was the OR clause in the category_link JOIN. However, the code suggested in the accepted answer is very slow, slower even than the original code. A much faster and also much cleaner solution is simply to replace the current JOIN condition with the following:

JOIN category_link l on l.sku_id IN (SELECT value FROM @p1) AND l.category_id = COALESCE(c5.category_id, c4.category_id)

This minute tweak is the fastest solution, tested against the double join from the accepted answer and also tested against the CROSS APPLY as suggested by valverij.

share|improve this question

migrated from stackoverflow.com Apr 17 '13 at 21:54

This question came from our site for professional and enthusiast programmers.

    
We'll need to see the rest of the query plan. –  RBarryYoung Apr 17 '13 at 18:25
    
Just a remark: with that many dependent joins cardinality estimation errors become likely. Most often, query performance is derailed by cardinality underestimation. –  usr Apr 17 '13 at 18:46
    
Does the execution plan make suggestions for indexes? Also, don't forget that you can set primary keys and indexes on your temporary tables (more info here) –  valverij Apr 17 '13 at 19:55
    
@rbarry If after trying current solutions I get nothing, I'll improve on the question –  Luis Ferrao Apr 17 '13 at 20:28
    
@usr Thanks for the remark but I must say I have no idea what to do with it, all I can say is that it takes much longer than expected to get the first result –  Luis Ferrao Apr 17 '13 at 20:29

3 Answers 3

up vote 4 down vote accepted

The problem appears to be in this part of the code:

JOIN category_link l on l.sku_id IN (SELECT value FROM #Ids) AND
(
    l.category_id = c4.category_id OR
    l.category_id = c5.category_id
)

or in join conditions is always suspicious. One suggestion is to split this into two joins:

JOIN category_link l1 on l1.sku_id in (SELECT value FROM #Ids) and l1.category_id = cr.category_id
left outer join
category_link l1 on l2.sku_id in (SELECT value FROM #Ids) and l2.category_id = cr.category_id

You then have to modify the rest of the query to handle this . . . coalesce(l1.sku_id, l2.sku_id) for instance in the select clause.

share|improve this answer
    
With the amount of filtering being done on that particular join, I'd also test changing the JOIN to a CROSS APPLY with the IN switching over to an EXISTS in the APPLY's WHERE clause. –  valverij Apr 17 '13 at 19:52
    
Thanks Gordon, I will test this first thing in the morning. @Valverij, I am not familiar with cross apply, could you describe your solution more, maybe in a proper Answer, so I can vote if it turns out to be the fastest scenario? –  Luis Ferrao Apr 17 '13 at 20:23
    
I am accepting this answer because it was the first answer that pointed me to the problem. The suggested solution however is extremely slow, slower even than the original code. However, knowing that the OR clause was the issue, simply replacing it by ON l.category_id = ISNULL(c5.category_id, c4.category_id did the trick. –  Luis Ferrao Apr 18 '13 at 9:34
    
@LuisFerrao . . . Thank you for the additional information. It is useful to know that the coalesce() pushes the optimizer in the right direction. –  Gordon Linoff Apr 18 '13 at 13:28

As another user mentioned, this join is likely the cause:

JOIN category_link l on l.sku_id IN (SELECT value FROM #Ids) AND
(
    l.category_id = c4.category_id OR
    l.category_id = c5.category_id
)

Besides splitting these out into multiple joins, you can also try a CROSS APPLY

CROSS APPLY (
    SELECT [some column(s)]
    FROM category_link x
    WHERE EXISTS(SELECT value FROM #Ids WHERE value = x.sku_id)
    AND (x.category_id = c4.category_id OR x.category_id = c5.category_id)        
) l

From the MSDN link above:

The table-valued function acts as the right input and the outer table expression acts as the left input. The right input is evaluated for each row from the left input and the rows produced are combined for the final output.

Basically, APPLY is like a subquery that filters out records on the right first, and then applies them to the rest of your query.

This article does a very good job of explaining what it is and when to use it: http://explainextended.com/2009/07/16/inner-join-vs-cross-apply/

It's important to note, however, that the CROSS APPLY does not always perform faster than an INNER JOIN. In many situations, it will probably be about the same. In rare cases, though, I've actually seen it slower (again, this all depends on your table structure and the query itself).

As a general rule of thumb, if I find myself joining to a table with way too many conditional statements, then I tend to lean toward APPLY

Also a fun note: OUTER APPLY will act like a LEFT JOIN

Also, please take note of my choice to use EXISTS rather than IN. When doing IN on a subquery, remember that it will return the entire result set, even after it has found your value. With EXISTS, though, it will stop the subquery the instant it finds a match.

share|improve this answer
    
I tested this solution thoroughly. As you wrote it, it's pretty slow, but you forgot to apply the advice you started your message with. Replacing AND x.cat = c4.cat OR x.cat = c5.cat by x.cat = ISNULL(c5.cat, c4.cat) and getting rid of the IN clause made this the second fastest solution, and worthy of an upvote, because it's pretty informative. –  Luis Ferrao Apr 18 '13 at 9:38
    
Thanks. The IN line actually wasn't supposed to be there (couldn't decide on using IN or sticking with the OR), I'll remove it. –  valverij Apr 18 '13 at 12:14

I'll follow up on a remark I made:

Just a remark: with that many dependent joins cardinality estimation errors become likely. Most often, query performance is derailed by cardinality underestimation.

How big are the intermediate result sets? Can you store the result set as it was generated by the query plan up to the problematic join into a temp table? If this is possible then you can probably get rid of the cardinality misestimation that way at the expense of an otherwise needless temp table population. The temp table will receive statistics which will help guide the query optimizer to a saner choice for the final join.

This would be at least a half-elegant solution.

You can probably also fix this by applying join hints (like INNER MERGE JOIN) but this gets nasty soon and has maintenance problems due to brittleness.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.