Summary of Join Properties

[アーティクル]
08/16/2006

The following table summarizes the characteristics of the three physical join operators which I described in my three prior posts.

	Nested Loops Join	Merge Join	Hash Join
Best for …	Relatively small inputs with an index on the inner table on the join key.	Medium to large inputs with indexes to provide order on the equijoin keys and/or where we require order after the join.	DW queries with medium to large inputs. Parallel execution that scales linearly.
Concurrency	Supports large numbers of concurrent users.	Many-to-one join with indexes to provide order supports large numbers of concurrent users.	Best for small numbers of concurrent users with high throughput requirements.
Stop and go	No	No	Yes (build input only)
Equijoin required	No	Yes (except for full outer join)	Yes
Outer and semi-joins	Left joins only (full outer joins via transformation)	All join types	All join types
Uses memory	No	No (may require sorts which use memory)	Yes
Uses tempdb	No	Yes (many-to-many join only)	Yes (if join runs out of memory and spills)
Requires order	No	Yes	No
Preserves order	Yes (outer input only)	Yes	No

Examples

For the remainder of this post, I’ll give some examples that show how subtle changes to a query can lead to different choices of join type.

Let’s begin with two tables with 1000 rows each:

create table T1 (a int, b int, x char(200))

create table T2 (a int, b int, x char(200))

set nocount on

declare @i int

set @i = 0

while @i < 1000

begin

insert T1 values (@i * 2, @i * 5, @i)

insert T2 values (@i * 3, @i * 7, @i)

set @i = @i + 1

end

Since we have no indexes, a simple join of these two tables results in a hash join:

select * from T1 join T2 on T1.a = T2.a

|--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
|--Table Scan(OBJECT:([T1]))
|--Table Scan(OBJECT:([T2]))

However, one thing that hash join is really bad at is returning the first few rows of a query quickly. Suppose that we want the first 10 rows only:

select top 10 * from T1 join T2 on T1.a = T2.a

Now we get a nested loops join. We don’t have an index, so this plan is going to scan all of T2 for each row of T1 until we find 10 rows that match. If finding 10 matches requires many scans of T2, this plan is going to get expensive quickly. Fortunately, if you run this query with statistics profile, you’ll see that we only scan T2 28 times.

Notes:

As you might expect, the top operator returns the first N rows and then terminates its input sub-tree. In this example, N is 10.
The table spool is an optimization. In this example, it does not do much. However, suppose that instead of “select *” we wrote “select T2.a”. T2 contains three columns including a char(200) column, but we only need the one integer column T2.a. Thus, we can store just T2.a in the spool. T2 can store only about 40 rows per page based on a row size of just over 200 bytes. Scanning all 1000 rows of T2 requires touching about 25 pages. The spool can store all 1000 rows with just column T2.a in only one or two pages.

Returning to the example, as I noted above, if we request too many rows, the nested loops join becomes very expensive. A merge join is a better choice:

select top 100 * from T1 join T2 on T1.a = T2.a

Similarly, if we need order anyhow, a merge join is also a good choice since we need to sort at least one table anyhow:

select top 10 * from T1 join T2 on T1.a = T2.a

order by T1.a

(The plan for this query is essentially the same as for the above top 100 query.)

Now let’s add a clustered index:

create unique clustered index T1a on T1(a)

Returning to the original join, we now get a many-to-one merge join:

select * from T1 join T2 on T1.a = T2.a

|--Merge Join(Inner Join, MERGE:([T1].[a])=([T2].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
|--Clustered Index Scan(OBJECT:([T1].[T1a]), ORDERED FORWARD)
|--Sort(ORDER BY:([T2].[a] ASC))
|--Table Scan(OBJECT:([T2]))

The optimizer has decided that since we already have one table in sorted order, we may as well sort the other table and use a merge join rather than using a hash join.

But, if we add a predicate to the scan of T1, we are back to a hash join:

select * from T1 join T2 on T1.a = T2.a

where T1.b < 100

|--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
|--Clustered Index Scan(OBJECT:([T1].[T1a]), WHERE:([T1].[b]<(100)))
|--Table Scan(OBJECT:([T2]))

The merge join plan needs to sort all 1000 rows of T1 while the hash join plan only needs to build a hash table on the 20 rows of T1 that match the predicate T1.b < 100. Thus, the hash join plan needs less memory and is less likely to spill.

But, if we also add a sort requirement to the query, we are back to the merge join again:

select * from T1 join T2 on T1.a = T2.a

where T1.b < 100

order by T1.a

|--Merge Join(Inner Join, MERGE:([T1].[a])=([T2].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
|--Clustered Index Scan(OBJECT:([T1].[T1a]), WHERE:([T1].[b]<(100)) ORDERED FORWARD)
|--Sort(ORDER BY:([T2].[a] ASC))
|--Table Scan(OBJECT:([T2]))

Recall that the merge join preserves order so we do not need to do a final sort to sastify the order by clause of the query. Hash join does not preserve order so we would need an extra sort. With the hash join, we would need two memory consuming operators. (Note that one memory consuming operator is not necessarily better than two. It really depends on how much memory the operators need.)

Next, let’s put the predicate on the scan of T2:

select * from T1 join T2 on T1.a = T2.a

where T2.b < 100

|--Nested Loops(Inner Join, OUTER REFERENCES:([T2].[a]))
|--Table Scan(OBJECT:([T2]), WHERE:([T2].[b]<(100)))
|--Clustered Index Seek(OBJECT:([T1].[T1a]), SEEK:([T1].[a]=[T2].[a]) ORDERED FORWARD)

By reducing the cardinality of T2 an index nested loops join is now the best choice.

Finally, let’s add a larger table T3 with 100,000 rows:

create table T3 (a int, b int, x char(200))

declare @i int

set @i = 0

while @i < 100000

begin

insert T3 values (@i * 5, @i * 11, @i)

set @i = @i + 1

end

Consider a simple join of T1 and T3:

select * from T1 join T3 on T1.a = T3.a

|--Hash Match(Inner Join, HASH:([T1].[a])=([T3].[a]), RESIDUAL:([T3].[a]=[T1].[a]))
|--Clustered Index Scan(OBJECT:([T1].[T1a]))
|--Table Scan(OBJECT:([T3]))

Even though we have an index on T1, we still choose a hash join. Recall that the join of T1 and T2 which were similarly sized used a merge join. To do a merge join, we need sorted order on both T1 and T3. The hash join needs enough memory to build a hash table on T1 or 1000 rows while a merge join would need enough memory to sort all of T3 or 100,000 rows. Thus, the hash join saves memory.

Hints

Although we recommend against using hints unless absolutely necessary, if you want to experiment a bit to see how different join orders and join types affect query plans and performance, you can use hints to force SQL Server to generate different plans. These hints are documented in Book Online. Be aware that it is not possible to force all plans and that using the wrong hints could cause SQL Server to fail to find a valid plan and generate this error:

Msg 8622, Level 16, State 1, Line 1
Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.

You can use query hints to tell SQL Server to use a particular join type or to force the join order. Query hints appear in the OPTION clause at the end of each statement. I’ve already used query hints in some of the examples in my prior posts. The relevant hints are LOOP JOIN, MERGE JOIN, HASH JOIN, and FORCE ORDER. The first three hints tell the optimizer to use only the specified join type. If you specify two join hints, the optimizer will use only those two join types; this provides a way to disable a particular join type. FORCE ORDER tells the optimizer to join the tables in the order that they appear in the FROM clause.

You can also use join hints in the FROM clause to force both join type and order. These hints are very powerful. You can specify the exact join type for each join. By using parenthesis you can force any join order including bushy trees. For (a purely hypothetical) example, here the hints to force a bushy tree with all three join types:

select *

from (T1 inner merge join T2 on T1.a = T2.a)

inner hash join

(T3 inner loop join T4 on T3.a = T4.a)

on T1.b = T3.b

Next …

In my next post, I’ll write about some more advanced join issues.

Comments

Anonymous
August 16, 2006
CraigFr has a great series of posts in his blog describing the difference between the various logical...
Anonymous
September 12, 2006
Every once in awhile, I get an opportunity to look around for new and interesting things to read.&nbsp;...
Anonymous
September 12, 2006
Every once in awhile, I get an opportunity to look around for new and interesting things to read.&nbsp;...
Anonymous
August 07, 2007
Since the beginning of learning SQL Server I'm pretty much confused with JOIN conditions that defines
Anonymous
January 02, 2009
HI craigfr,Can you talk about the inside of the Sort operator.
Anonymous
April 28, 2009
In this post, I want to take a look at how two seemingly unrelated features of SQL Server can interact
Anonymous
April 06, 2010
WOW... thanks MR.Craig. Your article on Join gave me clear idea about sql server join types and how it works.. Really appericiate your work. Thanks a lot Regards Kokila K

次の方法で共有

Summary of Join Properties

Comments

その他のリソース