Home, Optimizer, Benchmarks, Server Systems, Processors, Storage, TPC-H Studies

Bushy Join

A great session by Adam Machanic at SQL Saturday Boston the previous weekend on methods to influence the query optimizer while still letting it do its task. The gist of this is that while SQL Server has what are called Query Hints, there adverse adverse consequences. The Join Hints (Loop, Hash and Merge) "specify that the query optimizer enforce a join strategy between two tables," but also results in the query optimizer not bothering to investigate the different join orders, even though only the join type was specified. Hence the general advice is that one should not use the SQL Server Query/Join Hints unless one is prepared to completely override the query optimizer, which is essentially to say, one should almost never use join hints. Microsoft's advice is: "we recommend that hints, including , be used only as a last resort by experienced developers and database administrators." Adams' session investigated an alternative method of providing advice to the query optimizer without causing it to otherwise shutdown.

Now that we have said that the Loop, Hash and Merge Join Hints should almost never be used, and without recommending the use of hints, consider the question of how to use hints in the case of a last resort situation. Given the fact that the query optimizer disables join order optimization when hints are applied, the task is to reconstruct a good join order. It is explained elsewhere the general preference regarding join order. See either my articles on www.qdpma.com/ on the Query Optimizer (mostly I just examine the formulas, without bothering on the explanation), articles by Paul White, Benjamin Nevarez and others. Here will only examine the technique of join ordering.

In a two table join, there is only one shape, one table as the outer source in the upper right of the execution plan and the second table as the inner source in the lower left of the execution plan as in the diagram below.

Natural

We can reverse the order of the join, or change the type of join, but there is only one shape.

In a three table join, there are two possible shapes. One is linear, the first table is the outer source, joins to the second table as the inner source, and finally the output of this is the outer source for the final join with the third table as the inner source.

Linear

The second possible shape is that one table is the outer source in one join to another table. The output of this is now the inner source in the other join with the third table as the outer source.

Bush

From these two basic shapes, we can assemble almost any possible execution plan (sorry, but I do not have examples with the spool operation, if any one would like to comment on these).

Until a few years ago, I had always been under the impression that it was necessary to write out the full sub-query expression in order to force a bushy join, example below.

SELECT xx
FROM A
JOIN (
  SELECT xx
  FROM B
  JOIN C ON xx
) ON xx

The both join shape and order are forced with either a join hint or the OPTION (FORCE ORDER) clause. In a complex query with a long SELECT list, this style of expresssion quickly becomes cumbersome. Then one day, I needed to relax, so I read one of Itzik Ben-Gan's books and saw a style of SQL expression on joins that I had never seen before.

SELECT xx
FROM A
JOIN (
  B JOIN C ON xx
) ON xx

There is no SELECT in the sub-expression!

My heart skipped a beat.

What would be the execution plan join shape be if there were a join hint or force order hint on this expression?

Below is an SQL query example from Adam's session.

query

The execution plan for this query is below. Note that the join order is different than in the SQL.

Natural

If we forced a hash join, we would get the linear plan below.

Linear

Note that the join order is the same as in the SQL.

We could write the SQL in the form below.

query

But without a hint, the execution plan is the same as the original (natural) plan.

Now if we were to force the join order in the new SQL, as below

query

we do indeed get the bush shape with the join type.

Bush

We now have the basic techniques for writing SQL with the objective of forcing a particular join shape and order, to which we could apply join hints that also override much of the query optimizer.

Again, this is not an endorsement of using join hints. Do not use join hints without understanding that it has the effect of overriding the query optimizer on join ordering, and the implications. I do not accept any consequences on the use of join hints unless I was the consultant engaged. OK, so I just gave you a loaded gun while saying don't blame me for its improper use.

Appendix
Search Microsoft Technet for the terms Advanced Query Tuning Concepts, Understanding Nested Loops Joins, Understanding Merge Joins, and Understanding Hash Joins. I do recall that there was role reversal feature in hash joins.