Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««1234»»»

Hash Match Expand / Collapse
Author
Message
Posted Thursday, May 1, 2014 10:57 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 1:33 PM
Points: 8,571, Visits: 9,076
gbritton1 (5/1/2014)
Before I answered this question, I read

[url=http://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx][/url]

It reads, in part:

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.


then later:

The hash join first scans or computes the entire build input and then builds a hash table in memory.


I'm having trouble reconciling the official description with the "correct" answer.

Without looking anything up, I answered smallest (ie build) input first. When I saw the answer, I constructed a test (using SQL Server 2012) to see what happened. Given one table with 65537 rows and another with 393222 rows (the sizes of teh test tables I built - admittedly not very big, but big enough to refute a silly "correct" answer) I found that whether I wrote the join so that the small table was the first or second referenced in the select clause and whether the small table was teh first or second listed in teh from clause, the actual (not estimated but actual) execution plan took the smaller table as first (ie build) table.

So I don't just have trouble reconciling the official correct answer with the documentation, I have clear and solid experimantal evidence that the officially correct answer is just plain wrong.


Tom
Post #1566791
Posted Thursday, May 1, 2014 11:05 AM


Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Friday, July 18, 2014 11:41 AM
Points: 309, Visits: 279
TomThomson (5/1/2014)
gbritton1 (5/1/2014)
Before I answered this question, I read

[url=http://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx][/url]

It reads, in part:

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.


then later:

The hash join first scans or computes the entire build input and then builds a hash table in memory.


I'm having trouble reconciling the official description with the "correct" answer.

Without looking anything up, I answered smallest (ie build) input first. When I saw the answer, I constructed a test (using SQL Server 2012) to see what happened. Given one table with 65537 rows and another with 393222 rows (the sizes of teh test tables I built - admittedly not very big, but big enough to refute a silly "correct" answer) I found that whether I wrote the join so that the small table was the first or second referenced in the select clause and whether the small table was teh first or second listed in teh from clause, the actual (not estimated but actual) execution plan took the smaller table as first (ie build) table.

So I don't just have trouble reconciling the official correct answer with the documentation, I have clear and solid experimantal evidence that the officially correct answer is just plain wrong.


Tom - See my earlier post... there is no need for the answer to be wrong ( run test using HASH join hint) to match with your tests so far. When writing a hash join using the Hint you put the smaller to the right to make it the build table. Try you experiment with the Hash Join hint and see what happens.

Your experiment proves what the Query Optimizer does, but not how it is done.

Of course I would not know about any of this if I had not learned all of this by having to work with an Execution Plan that for some reason had chosen the Larger (2 million records) set as the Build list years ago.
Post #1566796
Posted Thursday, May 1, 2014 11:29 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 1:33 PM
Points: 8,571, Visits: 9,076
PHYData DBA (5/1/2014)
TomThomson (5/1/2014)
gbritton1 (5/1/2014)
Before I answered this question, I read

[url=http://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx][/url]

It reads, in part:

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.


then later:

The hash join first scans or computes the entire build input and then builds a hash table in memory.


I'm having trouble reconciling the official description with the "correct" answer.

Without looking anything up, I answered smallest (ie build) input first. When I saw the answer, I constructed a test (using SQL Server 2012) to see what happened. Given one table with 65537 rows and another with 393222 rows (the sizes of teh test tables I built - admittedly not very big, but big enough to refute a silly "correct" answer) I found that whether I wrote the join so that the small table was the first or second referenced in the select clause and whether the small table was teh first or second listed in teh from clause, the actual (not estimated but actual) execution plan took the smaller table as first (ie build) table.

So I don't just have trouble reconciling the official correct answer with the documentation, I have clear and solid experimantal evidence that the officially correct answer is just plain wrong.


Tom - See my earlier post... there is no need for the answer to be wrong ( run test using HASH join hint) to match with your tests so far. When writing a hash join using the Hint you put the smaller to the right to make it the build table. Try you experiment with the Hash Join hint and see what happens.

Your experiment proves what the Query Optimizer does, but not how it is done.

Of course I would not know about any of this if I had not learned all of this by having to work with an Execution Plan that for some reason had chosen the Larger (2 million records) set as the Build list years ago.

I suppose it depends on what the answer means by "first". If it means the "the table which ir processed first in order to build the the hash table against which rows from teh other table will be tested" then " that's first" is a pointless tautology. It's not at all clear to me that any sane person can take it as meaning that. If on the other hand it means that the table used as build table can be any of the tables involved, regardless of size, which is the only sensible interpretation of the words given that (a) "is the one that is used first used first?" is not a sensible question and (b) the statement "Size does not matter for this operator" in the explanation it seems clear both that the BOL documentation quoted by gbritton1 indicates that the "correct" answer is wrong fpr SQL 2008R2 (not a terribly interesting argument, given how often BOL gets it wrong, but in fact - see below - BOL didn't go wrong here) and that the experiment I undertook after seeing this crazy answer proved conclusively that the "correct" answer is wrong for SQL 2012. It may of course be different for SQL 2014, but there are several releases currently in full support and we can see that it is wrong for the majority of them (I ran the experiment for 2008 R2 as well before composing this reply, and this is not one of the places where BOL got it wrong).
So we have to work out what Jason (author of the referenced document) meant by "first(top)" and "second(bottom)". Jason doesn't usually get things wrong. I think he was referring to the layout of the operators in the query plan in the standard query plan display provided by SSMS - certainly that's what I thought he meant when I read it a month or two ago. There's no imaginable way that today's question could be interpreted so that "first" mant that, so I think that Steve has misunderstood what Jason was saying and produced a question and answer based on that misunderstanding.


Tom
Post #1566805
Posted Thursday, May 1, 2014 12:05 PM


Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Friday, July 18, 2014 11:41 AM
Points: 309, Visits: 279
TomThomson (5/1/2014)
PHYData DBA (5/1/2014)
TomThomson (5/1/2014)
gbritton1 (5/1/2014)
Before I answered this question, I read

[url=http://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx][/url]

It reads, in part:

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.


then later:

The hash join first scans or computes the entire build input and then builds a hash table in memory.


I'm having trouble reconciling the official description with the "correct" answer.

Without looking anything up, I answered smallest (ie build) input first. When I saw the answer, I constructed a test (using SQL Server 2012) to see what happened. Given one table with 65537 rows and another with 393222 rows (the sizes of teh test tables I built - admittedly not very big, but big enough to refute a silly "correct" answer) I found that whether I wrote the join so that the small table was the first or second referenced in the select clause and whether the small table was teh first or second listed in teh from clause, the actual (not estimated but actual) execution plan took the smaller table as first (ie build) table.

So I don't just have trouble reconciling the official correct answer with the documentation, I have clear and solid experimantal evidence that the officially correct answer is just plain wrong.


Tom - See my earlier post... there is no need for the answer to be wrong ( run test using HASH join hint) to match with your tests so far. When writing a hash join using the Hint you put the smaller to the right to make it the build table. Try you experiment with the Hash Join hint and see what happens.

Your experiment proves what the Query Optimizer does, but not how it is done.

Of course I would not know about any of this if I had not learned all of this by having to work with an Execution Plan that for some reason had chosen the Larger (2 million records) set as the Build list years ago.

I suppose it depends on what the answer means by "first". If it means the "the table which ir processed first in order to build the the hash table against which rows from teh other table will be tested" then " that's first" is a pointless tautology. It's not at all clear to me that any sane person can take it as meaning that. If on the other hand it means that the table used as build table can be any of the tables involved, regardless of size, which is the only sensible interpretation of the words given that (a) "is the one that is used first used first?" is not a sensible question and (b) the statement "Size does not matter for this operator" in the explanation it seems clear both that the BOL documentation quoted by gbritton1 indicates that the "correct" answer is wrong fpr SQL 2008R2 (not a terribly interesting argument, given how often BOL gets it wrong, but in fact - see below - BOL didn't go wrong here) and that the experiment I undertook after seeing this crazy answer proved conclusively that the "correct" answer is wrong for SQL 2012. It may of course be different for SQL 2014, but there are several releases currently in full support and we can see that it is wrong for the majority of them (I ran the experiment for 2008 R2 as well before composing this reply, and this is not one of the places where BOL got it wrong).
So we have to work out what Jason (author of the referenced document) meant by "first(top)" and "second(bottom)". Jason doesn't usually get things wrong. I think he was referring to the layout of the operators in the query plan in the standard query plan display provided by SSMS - certainly that's what I thought he meant when I read it a month or two ago. There's no imaginable way that today's question could be interpreted so that "first" mant that, so I think that Steve has misunderstood what Jason was saying and produced a question and answer based on that misunderstanding.


It seems you are once again ranting and/or trolling for something you are not going to find here.
Have fun with that.

I have read what you wrote, re-read my post, and read the BOL again.
Your post reads the least sane of all of them and is full of assumptions without reference, along with an experiment that only prove the Query Optimizer did it's job and changed how your select was executed.
Had you used the HASH Join hint you might have seen something different.

Maybe if I feel motivated I ask Kim or Paul at SQLskills.com how this is done.
Hrmmm.... reading your post above has actually unmotivated me to do any of this...
<un-subscribing now for same reason as a thousand others>
Post #1566815
Posted Thursday, May 1, 2014 12:44 PM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Today @ 3:02 PM
Points: 13,334, Visits: 10,201
Answered incorrectly because I found some blogs online which said something different than the official answer.
Mystery mystery...




How to post forum questions.
Need an answer? No, you need a question.
What’s the deal with Excel & SSIS?

Member of LinkedIn. My blog at LessThanDot.

MCSA SQL Server 2012 - MCSE Business Intelligence
Post #1566824
Posted Thursday, May 1, 2014 12:54 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 3:35 PM
Points: 5,930, Visits: 8,179
gbritton1 (5/1/2014)
Before I answered this question, I read

[url=http://technet.microsoft.com/en-us/library/ms189313(v=sql.105).aspx][/url]

It reads, in part:

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.


then later:

The hash join first scans or computes the entire build input and then builds a hash table in memory.


I'm having trouble reconciling the official description with the "correct" answer.


The only correct answer is "the first input" - allthough there is some room for confusion, based on the interpretation of "first".
Because of the usage of the term "hash match" (a plan operator, not a query construct) and "input" (not "table" or "data source", terms more associated with the query), I conclude that "first" relates to the order in which icons are rendered in the graphical execution plan (assuming that most languages write and read bottom to top), the order in which operators are speicified in both the (outdated) text representation and the XML representation of a plan, and the order in which inputs are consumed when the plan executes - those order all align,
Look at an execution plan - if you see a hash match operator performing a join, the top input (aka "build input") will be consumed first in order to build the hash table; the second input ("probe input") will then be consumed second.

The hash match algorithm for joins is most efficient when the build input is small and the probe input is large. The optimizer knows this - so if possible, the optimizer will rearrange the order of joins in order to get the smaller input at the top (and the optimizer can do that even in the case of outer or semi joins, because hash match supports all logical join types in both the right and the left variety).
So the top ("first") input does not always correspond to the first-mentioned data source. But there is no guarantee that the smaller input will always be processed first. The optimizer can make a mistake - maybe statistics were out of date or skewed, maybe one of the sources is already the effect of several joins and filtering, making the statistics necessarily lesser quality. Or maybe hints in the query have forced an order.

The TechNet documentation quoted above describes the ideal behaviour of optimizer + execution engine. It even explicitly says so: "the query optimizer assigns these roles so that the smaller of the two inputs is the build input".
The QotD focuses only on the execution engine, taking the compiled and optimized plan as a given. I was able to derive that from some wording of the question, but I do agree that this could have been clearer.


(And for the really nitpicky people - there is one edge case scenario where the second input will actually eventually be used to build the hash table, but I have never knowlingly witnessed it. When the first input is much larger than estimated, the query will have insufficient memory to store the hash table. In such a case, the execution engine will usually decide to spill a part of the hash table to tempdb - multiple times if needed. However, there is also an alternative mechanism called "role reversal" where at runtime the execution engine decides that probably the second input may actually be smaller - and at that time the already built part of the hash table will be spilled to tempdb and the operator will start building a new hash table based on the second input.
Again, really edge case, and I have never seen it happen. If anyone has a script that repros this behaviour, I'd love to see it!)



Hugo Kornelis, SQL Server MVP
Visit my SQL Server blog: http://sqlblog.com/blogs/hugo_kornelis
Post #1566829
Posted Thursday, May 1, 2014 1:05 PM
SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Thursday, June 26, 2014 9:20 AM
Points: 825, Visits: 721
Hugo Kornelis (5/1/2014)

The TechNet documentation quoted above describes the ideal behaviour of optimizer + execution engine. It even explicitly says so: "the query optimizer assigns these roles so that the smaller of the two inputs is the build input".
The QotD focuses only on the execution engine, taking the compiled and optimized plan as a given. I was able to derive that from some wording of the question, but I do agree that this could have been clearer.


Thanks for the clarification on this. At least now I have some reference for the different interpretations of the QOTD that we have seen in this thread.

Brian
Post #1566833
Posted Thursday, May 1, 2014 1:15 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 2:56 PM
Points: 1,603, Visits: 4,593
Given the options: first, larger, smaller, or second input, I still say that 'smaller input' is closest to the correct answer.

On his MSDN blog, Craig Freedman goes into some detail about the hash join, and he states that the choice of which input is used for building the hash table is cost based with a preferance for the smaller of the two tables. He was a member of the query execution team that developed the scan, seek, and join operators in SQL Server 2005, so he must know a good deal about the internals of how the algorithm works. It wouldn't be the first time that the official documentation for an application doesn't correspond exactly with the technical implementation, especially when it comes to something like this.

..Before a hash join begins execution, SQL Server tries to estimate how much memory it will need to build its hash table. We use the cardinality estimate for the size of the build input along with the expected average row size to estimate the memory requirement. To minimize the memory required by the hash join, we try to choose the smaller of the two tables as the build table..

http://blogs.msdn.com/b/craigfr/archive/2006/08/10/687630.aspx

I've experimented using the sample tables T1 (1,000 rows) and T2 (10,000 rows) provided in the blog post above, and regardless of the left or right position of each in the JOIN clause or ON expression, SQL Server choses the smaller T1 table for building the hash.
Post #1566837
Posted Thursday, May 1, 2014 3:56 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Tuesday, June 10, 2014 3:21 PM
Points: 102, Visits: 52
PHYData DBA (5/1/2014)
jackson.fabros (5/1/2014)
still unclear what the correct answer is. my textbook also mentions that "the hash table is built from the smaller input"

Is this exactly what your textbook says?
Let's hope not since the build input should be made from the smaller set and the probe input from the remainder in a HASH JOIN.
A "hash table" would be something else but not sure how it would have different inputs.

There are even HASH JOIN where the build and probe inputs are the same thing...


I may have misquoted that piece of text. actually dont have the book in front of me at the moment. I'm sure I was thinking of what you just said, "build input should be made from the smaller set"

thanks for confirming
Post #1566864
Posted Thursday, May 1, 2014 5:50 PM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Monday, June 9, 2014 11:35 PM
Points: 27, Visits: 86
From my course notes from SQLSkills IE1, module 10 Indexing strategies (Taught by Kimberly Tripp from sqlskills.com), Slide 37, Join Strategies :

"Hash join
Two-phsae operation (build, then probe): Build table(smaller set) and probe table (larger set) allowing SQL to join extremely large sets - in MEMORY (can spill"

I just can't make this reconcile with the official answer.

Simon.
Post #1566880
« Prev Topic | Next Topic »

Add to briefcase ««1234»»»

Permissions Expand / Collapse