Table Join on Hash Match vs Nested Loop

Question

Table Join on Hash Match vs Nested Loop

kwiggans

Ten Centuries

Points: 1196
More actions
January 23, 2009 at 2:16 pm

#204417

I have created the following script to simulate the issue I encountered while attempting to optimize a view that was causing deadlocks on our SQL server.
/***************************
Our production tables have many more columns, but the indexes on the columns shown match those in production. @tbl1 is unique for each QID just like our production environment. It has a one to many relationship to @tbl2 which keeps track of any changes made to the submission. Eventually for each QID, a specific version is used to process, which changes the Version field in @tbl2 to a NULL value.
***************************/
declare @tbl1 table (VersionUsed varchar(1) null, QID varchar(7) not null)
declare @tbl2 table (Version varchar(4), VerOriginal varchar(1), QID varchar(7), primary key(QID,VerOriginal))
insert @tbl1 values('C','0400000')
insert @tbl2 values('A','A','0400000')
insert @tbl2 values('B','B','0400000')
insert @tbl2 values(NULL,'C','0400000')
insert @tbl1 values('B','0500000')
insert @tbl2 values('A','A','0500000')
insert @tbl2 values(NULL,'B','0500000')
insert @tbl2 values('C','C','0500000')
insert @tbl2 values('D','D','0500000')
-- Original Method
select * from @tbl1 tbl1 join @tbl2 tbl2 on tbl1.VersionUsed+tbl1.QID = tbl2.VerOriginal+tbl2.QID
-- Revised Method
select * from @tbl1 tbl1 join @tbl2 tbl2 on tbl1.QID=tbl2.QID and tbl2.Version is null and tbl1.VersionUsed=(select VerOriginal from @tbl2 where QID=tbl1.QID and Version is null)
The code above mimics the two methods used to join the tables contained within the view.
In the example provided, both select statements run very quickly. Our database however contains hundreds of thousands of rows for both tables. Even selecting a very narrow parameter window using the view would cause a deadlock timeout. Surprisingly to me, in production, the revised method shown above ran quickly and smoothly.
I ran the estimated execution plan in SSMS and found that the original method of joining the tables utilized a Hash Match, while the revised method which seems to have a more complex plan used nested loops.
My question is why is there such a great performance difference between the two methods, and should I avoid using concatenated columns in my table JOIN statements in the future? What if the columns are properly indexed, would that make a difference, and how would you recommend indexing the columns?
Keith Wiggans

Viewing 9 posts - 1 through 8 (of 8 total)

You must be logged in to reply to this topic. Login to reply

Gail Shaw SSC Guru Points: 1004504 More actions · Answer 1

kwiggans (1/23/2009)
My question is why is there such a great performance difference between the two methods, and should I avoid using concatenated columns in my table JOIN statements in the future?

Second question first, yes, avoid such constructs

The reason is that concatenation like that is considered by the optimiser to be the same as a function applied to a column. It prevents index seeks. With a join like that, you're looking at index scans or table scans to satisfy it.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

Sankar Reddy SSCrazy Points: 2410 More actions · Answer 2

Gail is correct and just to complement what she said, avoid using correlated subqueries if you can solve the problem with a simpler join.

In Correlated subquery, inner query is executed once for each row from the outer table and this can be expensive on large datasets.

select * from @tbl1 tbl1 join @tbl2 tbl2

on tbl1.QID=tbl2.QID

and tbl1.VersionUsed=tbl2.VerOriginal

and tbl2.Version is null

With the sample dataset you gave us, this method has 5% cost where as Orig method has 19% and revised method has 8%. Test it out with your large dataset and you will know.

[font="Courier New"]Sankar Reddy | http://SankarReddy.com/[/url][/font]

Gail Shaw SSC Guru Points: 1004504 More actions · Answer 3

Sankar Reddy (1/24/2009)
Correlated subquery, inner query is executed once for each row from the outer table and this can be expensive on large datasets.

That's only true when the join to the outer query is an inequality or there's a TOP 1.. ORDER BY in the subquery. In the vast majority of cases, the optimiser will create a plan for the correlated subquery where the subquery runs only once.

See this example (Adventureworks). You'll note that the number of executes for the SalesOrderDetail table is 1. If what you said was true, it would be 194 (the number of rows in the outer query)

USE AdventureWorks

GO

SET STATISTICS IO ON

GO

SELECT productId, productnumber,

(SELECT SUM(LineTotal) SumTotal FROM Sales.SalesOrderDetail sd WHERE sd.productID = p.productid )

FROM Production.Product p

WHERE ProductNumber like 'bk%'

SELECT p.ProductID, ProductNumber, SumTotal

FROM Production.Product p

INNER JOIN (

SELECT productid, SUM(LineTotal) SumTotal

FROM Sales.SalesOrderDetail

GROUP BY ProductID

) SalesTotals on p.ProductID = SalesTotals.ProductID

WHERE ProductNumber like 'bk%'

The execution plans for the two are the same cost, they give the same execution times (1st - CPU time = 1000 ms, elapsed time = 1131 ms. 2nd CPU time = 1000 ms, elapsed time = 1150 ms.) and the IO statistics for the two are identical

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0
Table 'SalesOrderDetail'. Scan count 1, logical reads 20384, physical reads 0
Table 'Product'. Scan count 1, logical reads 2, physical reads 0

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

Sankar Reddy SSCrazy Points: 2410 More actions · Answer 4

Gail, Good to know. Then whats the reasoning behind the differences in logical reads for the 3 plans.

--Orig

(2 row(s) affected)

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table '#3FF073BA'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table '#3EFC4F81'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

--Revised

(2 row(s) affected)

Table '#3FF073BA'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Table '#3EFC4F81'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

--Simple join

(2 row(s) affected)

Table '#3FF073BA'. Scan count 0, logical reads 4, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table '#3EFC4F81'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

[font="Courier New"]Sankar Reddy | http://SankarReddy.com/[/url][/font]

Gail Shaw SSC Guru Points: 1004504 More actions · Answer 5

No idea. Post the full setup for your test (including table creation, population and the exact queries you used) and I'll check.

Just be careful with using table variables, because they don't have statistics, their performance can (and will) be way different from temp or permanent tables. Rather test with temp tables

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

Sankar Reddy SSCrazy Points: 2410 More actions · Answer 6

Gail,

After reading your reply I thought that it might be because of table variables as you said but interestingly, its the same using the permanent tables also.

>>Just be careful with using table variables

Here is the code snippet I am using.

create table tbl1 (VersionUsed varchar(1) null, QID varchar(7) not null)

create table tbl2 (Version varchar(4), VerOriginal varchar(1), QID varchar(7), primary key(QID,VerOriginal))

insert tbl1 values('C','0400000')

insert tbl2 values('A','A','0400000')

insert tbl2 values('B','B','0400000')

insert tbl2 values(NULL,'C','0400000')

insert tbl1 values('B','0500000')

insert tbl2 values('A','A','0500000')

insert tbl2 values(NULL,'B','0500000')

insert tbl2 values('C','C','0500000')

insert tbl2 values('D','D','0500000')

go

set statistics io on

-- Original Method

select * from tbl1 tbl1 join tbl2 tbl2 on tbl1.VersionUsed+tbl1.QID = tbl2.VerOriginal+tbl2.QID

-- Revised Method

select * from tbl1 tbl1 join tbl2 tbl2 on tbl1.QID=tbl2.QID and tbl2.Version is null and tbl1.VersionUsed=(select VerOriginal from tbl2 where QID=tbl1.QID and Version is null)

select * from tbl1 tbl1 join tbl2 tbl2

on tbl1.QID=tbl2.QID

and tbl1.VersionUsed=tbl2.VerOriginal

and tbl2.Version is null

If you look at the execution plan also, they are completely different.

[font="Courier New"]Sankar Reddy | http://SankarReddy.com/[/url][/font]

Gail Shaw SSC Guru Points: 1004504 More actions · Answer 7

The second has a very different exec plan for a simple reason. That subquery, as written, must return only one value. If it returns more, the query must fail (with a subquery returned more than one value error). That's why there's a stream aggregate and an assert sitting after the clustered index scan and before the nested loop join. Take those two out, and the plan looks more like the 3rd one

The table tbl2 is been read more than once because, in the query, it's referred to more than once. Once in the subquery, once in the outer query. That's two scans straight off. The other two are because both joins are nested loop, and the way a nested loop join works is by reading the inner input once for each row of the outer input. That's why they're very good for small resultsets, but very bad for large ones.

With the 3rd query, the table tbl2 is only referred to once, hence fewer scans. It's still the outer of a nested loop join, so 2 scans (at least that's what I see)

The one operator that will tell you that a subquery is been executed more than once is the table spool/eager spool or index spool/eager spool. Both of those are used to store and replay results, which is what will happen on the odd occurrences where a correlated subquery truly is run once per row of the outer.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

ScottPletcher SSC Guru Points: 101129 More actions · Answer 8

select * from @tbl1 tbl1 join @tbl2 tbl2 on tbl1.VersionUsed+tbl1.QID = tbl2.VerOriginal+tbl2.QID

I agree about avoiding the concatenation. And it's definitely not needed here anyway:

SELECT *

FROM @tbl1 tbl1

INNER JOIN @tbl2 tbl2 ON

--tbl2.Version IS NULL AND --if applicable

tbl1.VersionUsed = tbl2.VerOriginal AND

tbl1.QID = tbl2.QID

SQL DBA,SQL Server MVP(07, 08, 09) "It's a dog-eat-dog world, and I'm wearing Milk-Bone underwear." "Norm", on "Cheers". Also from "Cheers", from "Carla": "You need to know 3 things about Tortelli men: Tortelli men draw women like flies; Tortelli men treat women like flies; Tortelli men's brains are in their flies".