Databases Reference
In-Depth Information
As a result of the
commutative
and
associative
properties of joins, even simple queries
offer many different possible join orders, and this number increases exponentially with
the number of tables that need to be joined. The task of the Query Optimizer is to find
the optimal sequence of joins between the tables used in the query. To clarify this
challenge, let's first clarify the terminology.
The commutative property of a join between tables A and B states that:
A
JOIN
B is equivalent to B
JOIN
A.
This defines which table will be accessed first. In a Nested Loops Join, for example, the
first accessed table is called the outer table and the second one the inner table. In a Hash
Join, the first accessed table is the build input and the second one the probe input. As we
will see in the next chapter, correctly defining which table will be the inner and outer
table in a Nested Loops Join, or the build input or probe input in a Hash Join is important
to get right, as it has significant performance and cost implications, and it is a choice
made by the Query Optimizer.
The associative property of a join between tables A, B, and C states that:
(A
JOIN
B)
JOIN
C is equivalent to A
JOIN
(B
JOIN
C).
This defines the order in which the tables are joined. For example, (A
JOIN
B)
JOIN
C
specifies that table A must be joined to table B first, and then the result must be joined to
table C. A
JOIN
(B
JOIN
C) means that table B must be joined to table C first and then the
result must be joined to table A. Each possible permutation may have different cost and
performance results depending, for example, on the size of their temporary results.
Costing of the join algorithms will also be explained in the next chapter.
By way of an example, Listing 1-7 shows a query, taken from Books Online, which joins
together three tables in the
AdventureWorks
database. Click
Include Actual Execution
Plan
and execute the query.
