Query runs indefinitely - what is the root cause ? (not asking how to fix)

Question

I have a simple query with a grouping, which worked fine, until I added one more join:

select 
   [ca].Value,
   [c].cID, 
   [c].Name

from ReportingDB..Table1 [t1]

join MainDB..Companies [c] on
    [t1].CompanyID = [c].cID
    and [c].cID not in (1)

join MainDB..CompanyAttributes [ca] on -- this is the join that causes trouble
    [t1].CompanyID = caCID
    and caAttr = 26

group by [ca].Value, [c].cID, [c].Name

Info:

Companies table is a "lookup" table and has 2254 rows, cID is PK
CompanyAttributes has many to one relationship to Companies and has 4055 rows
Table1 has many to one relationship to Companies table and has 3,485,150 rows and

Estimated execution plan does not look unusual.

• When I try to run the query, it does not finish and after 1 hour I stop it, so can't see what is going on with the Actual execution plan
• Live Query Statistics made my SSMS hang
• If remove "group by" clause, it starts fetching rows without any problem pretty fast. Or when last join is removed, it also works fine - with grouping
• Server is not busy, has enough resources, and I don't see noticeable CPU rise when launch the query
• looking at sys.dm_exec_requests, wait_type is NULL, cpu_time and logical_reads continue to grow, for the session running the query

What is the ROOT cause of original query running over 1 h without finishing?

---

I resolved the performance bottleneck itself (see my answer), but don't understand WHAT exactly causes original query to run 1 hour and not finish on a decent server, queried tables are not huge. Would expect original query to finish in less than 1 minute.

Answer 1

The main problem with the estimated execution plan shown is the Top operator above the Clustered Index Scan of Table1. The scan has a residual predicate:

[ReportingDB].[dbo].[Table1].[CompanyID]=[MainDB].[dbo].[CompanyAttributes].[cacID]

The optimizer tries to estimate how many rows it will need to read from the scan before one passes that test. The logic it uses is generic and not particularly sound in my opinion. In particular, if there is no match, the scan will run to completion, checking all 3,514,200 rows.

More to the point, this scan will repeat for every row returned by the scan of Company Attributes, multiplied by the number of rows returned by the seek on Companies. This is just how nested loops joins work.

The optimizer is super-optimistic about finding matches on each scan of Table1. This results in this plan shape having the lowest estimated cost of the alternatives considered. The root cause of that is the row goal introduced by the Top operator.

If you are curious about where the Top came from (it is not in your query text), please take a look at my closely-related article Row Goals, Part 4: The Anti Join Anti Pattern.

In short: the optimizer introduced a local (partial) aggregate as part of its plan search. That aggregate turned out to be logically redundant, and was replaced with the equivalent Top. An unfortunate side-effect of the Top is to introduce a row goal, significantly reducing the estimated cost of the scan.

A Top above a Scan with a residual predicate (especially where the scan is repeated) is very much an anti-pattern to watch out for.

Answer 2

I believe what you're running into is similar to what I've recently experienced a few times as mentioned in my DBA.StackExchange question. I'm by no means an expert on what's happening but will try to summarize my understanding.

When you join two tables together, the SQL Engine utilizes statistics on your data (based on the fields in your predicates) to determine the most efficient operation to use when actually joining the data together. A lot of this depends on the cardinalities of those predicates, in other words how much data is expected to be returned by them.

There are three main operations (types of joins internally) that the SQL Engine can choose to use, depending on how many rows it expects your join will return: Nested Loop Join, Merge Join, and Hash Join. There is also an internal metric, commonly referred to as "the tipping point" which is a cutoff that the SQL Engine uses (based on the cardinalities) to determine when to use one of the previously mentioned join operations to serve your query.

Nested Loop Joins are typically most efficient when joining two small datasets together as opposed to Hash Joins being more efficient for joining large datasets together. (There's also some other other characteristics for when one is more performant than the other as well, such as if the data is already sorted on the join predicate.) From a procedural programming languages perspective, think of Nested Loops as an outer loop that's processing another inner loop inside of it and comparing each value of the inner loop to the current value of the outer loop, whereas Hash Joins do what the name implies and hashes the data of the predicates to do a hash lookup when joining.

The issue you may be encountering (if similar to the one in my linked question above) is that for some reason the SQL Engine doesn't think your data crosses the tipping point threshold that warrants it to upgrade from a Nested Loop Join operation to a Merge or Hash Join operation. I based my guess on forcing a Hash Join by using the join hint on the fact that your Table1 has almost ~3.5 million rows, and your estimated execution plan is showing a Nested Loops operation when ultimately joining it to CompanyAttributes.

I presume when you do one of the few things you've mentioned that help improve performance, if you analyze the actual execution plan, you'll likely noticed that specific Nested Loops operation is now replaced with either a Merge or Hash Join.

Erik's mention of a "row goal" issue led me to find a couple of relevant resources you might find interesting as well:

1. Row Goals Gone Rogue - Bart Duncan - This discusses a little bit on reasons why a Nested Loop Join may be favoured (to meet a row goal) over a Hash Join.

2. Setting And Identifying Row Goals In Execution Plans - Paul White - Goes more in depth on row goals, what can trigger them, and further discusses causes for Nested Loops to be favoured over Hash Joins.

I'll try to elaborate and improve this answer further when I get more time, but I'd like to finally mention that join hints are generally not an ideal solution and should really only be used when left with no other option to get across the finish line with performance tuning. But they are certainly helpful in trying to debug the cause of a performance issue, such as the one you're currently experiencing.

Answer 3

Discovered three ways to fix this performance bottleneck, and query completes within 1 sec after:

1. simply replace [c].cID by [t1].CompanyID in the select clause, no need to create indexes

OR

2. add nonclustered index on [t1].CompanyID on Table1 - as Erik suggested. And no need to replace columns in the select clause

OR

3. Changing your join to CompanyAttributes to inner hash join MainDB..CompanyAttributes [ca] (thanks J.D.)

What I DON'T understand is why original query (and when there is no NC index) does not finish.
Ok, I would expect it do clustered index scan, and complete within minute or less, Table1 is not super big (3.5 M rows).

But it runs 1 hour and no complete. So, I will accept other answer if anyone can explain root cause of original query running over 1h and not finishing