Table Join on Hash Match vs Nested Loop
-
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
-
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 recoverabilityWe walk in the dark places no others will enter
We stand on the bridge and no one may pass -
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]
-
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 AdventureWorksGO
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 recoverabilityWe walk in the dark places no others will enter
We stand on the bridge and no one may pass -
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]
-
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 recoverabilityWe walk in the dark places no others will enter
We stand on the bridge and no one may pass -
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]
-
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 recoverabilityWe walk in the dark places no others will enter
We stand on the bridge and no one may pass -
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) A socialist is someone who will give you the shirt off *someone else's* back.
Viewing 9 posts - 1 through 8 (of 8 total)
You must be logged in to reply to this topic. Login to reply