42

I am starting to learn execution plans and am confused about how exactly a hash match works and why it would be used in a simple join:

select Posts.Title, Users.DisplayName
From Posts JOIN Users on
Posts.OwnerUserId = Users.Id
OPTION (MAXDOP 1)

enter image description here

As I understand it the results of the Top index scan become the hash able and each row in the bottom Index clustered scan is looked up. I understand how hash tables work to at least some degree, but I am confused about which values exactly get hashed in an example like this.

What would make sense me is the the common field between them, the id, is hashed -- but if this is the case, why hash a number?

Kyle Brandt
  • 2,345
  • 8
  • 29
  • 37

3 Answers3

32

As SQLRockstar's answer quotes

best for large, unsorted inputs.

Now,

  • from the Users.DisplayName index scan (assumed nonclustered) you get Users.Id (assuming clustered) = unsorted
  • You are also scanning Posts for OwnerUserId = unsorted

This is 2 unordered inputs.

I'd consider an index on the Posts table on OwnerUserId, including Title. This will add some order on one side of the input to the JOIN + it will be covering index

CREATE INDEX IX_OwnerUserId ON Posts (OwnerUserId) INCLUDE (Title)

You may then find that the Users.DisplayName index won't be used and it will scan the PK instead.

gbn
  • 69,809
  • 8
  • 163
  • 243
  • 1
    Ah okay I see now, I was thinking of the Users.DisplayName has being ordered by the PK which just isn't the case. Now the use of Hash makes a lot more sense to me. Thanks! – Kyle Brandt Mar 24 '11 at 13:01
  • 1
    You could also try the OPTION (FAST n) hint, where n is the rough number of rows you expect. What this will do is bias the optimizer towards nested loops rather than hash joins when n is low. The reason is that hash joins are fast for large joins but have a high startup cost. Nested loops are expensive per-row, but can get started very cheaply. So it's a matter of fine tuning based on your actual data and access pattern. – Gaius Mar 28 '11 at 11:42
  • 1
    @Gaius: Personally I'd rather have indexes than hints. A hint is only good for the query when you add it. A.k.a. the hint becomes a liability over time. Indexes tend to be useful a lot longer. – gbn Mar 28 '11 at 11:50
  • 1
    it's not an either-or proposition :-) – Gaius Mar 28 '11 at 11:51
14

From http://sqlinthewild.co.za/index.php/2007/12/30/execution-plan-operations-joins/

"The hash join is one of the more expensive join operations, as it requires the creation of a hash table to do the join. That said, it’s the join that’s best for large, unsorted inputs. It is the most memory-intensive of any of the joins

The hash join first reads one of the inputs and hashes the join column and puts the resulting hash and the column values into a hash table built up in memory. Then it reads all the rows in the second input, hashes those and checks the rows in the resulting hash bucket for the joining rows."

which links to this post:

Link

HTH

Glorfindel
  • 2,201
  • 5
  • 17
  • 26
SQLRockstar
  • 6,359
  • 26
  • 48
  • So if it is just the id fields, I guess I don't understand the advantage of hashing an id field? – Kyle Brandt Mar 23 '11 at 22:19
  • +1 for the link to Craig Freedman's blog, there are more join articles available: http://blogs.msdn.com/b/craigfr/archive/tags/joins/ – Jeff Mar 24 '11 at 01:55
9

The advantage of hashing a numeric field is that you're taking a bigger value and breaking it down into smaller pieces so that it can fit into a hash table.

Here's how Grant Fritchey describes it:

"A hash table, on the other hand, is a data structure that divides all of the elements into equal-sized categories, or buckets, to allow quick access to the elements. The hashing function determines which bucket an element goes into. For example, you can take a row from a table, hash it into a hash value, then store the hash value into a hash table."

You can also get a free copy of his ebook "Dissecting SQL Server Execution Plans" from a link from the following article:

Source: http://www.simple-talk.com/sql/performance/graphical-execution-plans-for-simple-sql-queries/

Jeff
  • 1,035
  • 7
  • 12