Databases Reference
In-Depth Information
hinted query to be more expensive. Specifically, the relative cost of the first query is 38%,
compared to 62% for the
FORCE
ORDER
query.
Estimated subtree costs
You can get the same result by hovering over the
SELECT
icon of each plan and examining the
Estimated Subtree Cost
which, in this case, is the entire tree or query. The first query will show
a cost of 3.2405 and the second one will show 5.3462. Therefore the relative cost of the second query
is 5.3462/(3.2405 + 5.3462)*100 = 62%.
As noted earlier, the number of possible join orders in a query increases exponentially
with the number of tables. In fact, with just a handful of tables, the number of possible
join orders could be numbered in the thousands or even millions, although the exact
number of possible join orders depends on the overall shape of the query tree. Obviously,
it is impossible for the Query Optimizer to look at all those combinations: it would take
far too long. Instead, it uses heuristics, such as considering the shape of the query tree, to
help it narrow down the search space.
As mentioned before, queries are represented as trees in the query processor, and the
shape of the query tree, as dictated by the nature of the join ordering, is so important in
query optimization that some of these trees have names, such as left-deep, right-deep and
bushy trees.
Figure 1-10 shows left-deep and bushy trees for a join of four tables. For example, the
left-deep tree could be:
JOIN( JOIN( JOIN(A, B), C), D)
And the bushy tree could be:
JOIN(JOIN(A, B), JOIN(C, D))
Left-deep trees are also called linear trees or linear processing trees, and you can see
how their shapes lead to that description. Bushy trees, on the other hand, can take any
arbitrary shape, and so the set of bushy trees actually includes the sets of both left-deep
and right-deep trees.
