Databases Reference
In-Depth Information
Tables
Left-deep trees
Bushy trees
10
3,628,800
17,643,225,600
11
39,916,800
670,442,572,800
12
479,001,600
28,158,588,057,600
Table 1-2:
Possible join orders for left-deep and bushy trees.
The number of left-deep trees is calculated as
n!
, or
n factorial
, where
n
is the number
of tables in the relation. A factorial is the product of all positive integers less than or
equal to
n
; so, for example, for a five-table join, the number of possible join orders is
5! = 5 x 4 x 3 x 2 x 1 = 120
.
The number of possible join orders for a bushy tree is more complicated, and can be
calculated as
(2n-2)!/(n-1)!
.
The important point to remember here is that the number of possible join orders grows
very quickly as the number of tables increase, as highlighted by Table 1-2. For example,
in theory, if we had a six-table join, a query optimizer would potentially need to evaluate
30,240 possible join orders.
Of course, we should also bear in mind that this is just the number of permutations for
the join order. On top of this, the Query Optimizer also has to evaluate a number of
possible physical join operators, data access methods (e.g. Table Scan, Index Scan or
Index Seek), as well as optimize other parts of the query, such as aggregations, subqueries
and so on.
So how does the Query Optimizer analyze all these possible plan combinations? The
answer is: it doesn't. Performing an exhaustive evaluation of all possible combinations,
for a complex query, would take too long to be useful, so the Query Optimizer must find
a balance between the optimization time and the quality of the resulting plan. Rather
than exhaustively evaluate every single combination, the Query Optimizer tries to
