SQL Tuning [Electronic resources] نسخه متنی

6.3 Simple Examples

Nothing illustrates the method better than examples, so I demonstrate
the method using the query diagrams built in Chapter 5, beginning with the simplest case, the two-way
join, shown again in Figure 6-1.

Figure 6-1. A simple two-way join

Applying Step 1 of the method, first ask which node offers the best
(lowest) effective filter ratio. The answer is E,
since E's filter ratio of 0.1 is
less than D's ratio of 0.5.
Driving from that node, apply Step 2 and find that the best (and
only) downstream node is node D, so go to
D next. You find no other tables, so that
completes the join order. Following the rules for a robust execution
plan, you would reach E with an index on its
filter, on Exempt_Flag. Then, you would follow
nested loops to the matching departments through the primary-key
index on Department_ID for
Departments. By brute force, in Chapter 5, I already showed the comforting result that
this plan is in fact the best, at least in terms of minimizing the
number of rows touched.

The rules for robust plans and optimum robust plans take no account of what indexes you already have. Remember that this chapter addresses the question of which plan you want, and that question should not be confined by currently lacking indexes. I later address the question of settling for less than optimal plans when indexes are missing, but you must first find ideal plans before you can evaluate when to make compromises.

6.3.1 Join Order for an Eight-Way Join

So far, so good, but two-way joins are too easy to need an elaborate
new method, so let's continue with the next example,
the eight-way join. Eight tables can, in theory, be joined in
8-factorial join orders (40,320 possibilities), enough to call for a
systematic method. Figure 6-2 repeats the earlier
problem from Chapter 5.

Figure 6-2. A typical eight-way join

Following the heuristics outlined earlier, you can determine the
optimal join order for the query diagrammed in Figure 6-2 as follows:

Find the table with the lowest filter ratio. In this case,
it's C, with a ratio of 0.0002,
so C becomes the driving table.

From C, it is not possible to drive down to any
table through a primary-key index. You must therefore move upward in
the diagram.

The only way up from C is to O,
so O becomes the second table to be joined.

After reaching O, you find that you can now drive
downward to OT. Always drive downward when
possible, and go up only when you've exhausted all
downward paths. OT becomes the third table to be
joined.

There's nothing below OT, so
return to O and move upward to
OD, which becomes the fourth table to be joined.

The rest of the joins are downward and are all unfiltered, so join to
S, P, and
ODT in any order.

Join to A at any point after it becomes eligible,
after the join to S places it within reach.

I will show that, when you consider join ratios, you will always place downward inner joins before outer joins. This is because such inner joins have at least the potential to discard rows, even in cases like this, when statistics indicate the join will have no effect on the running rowcount.

Therefore, you find the optimum join order to be
C; O; OT;
OD; S, P,
and ODT in any order; and A at
any point after S. This dictates 12 equally good
join orders out of the original 40,320 possibilities. An exhaustive
search of all possible join orders confirms that these 12 are equally
good and are better than all other possible join orders, to minimize
rows visited in robust execution plans.

This query diagram might strike you as too simple to represent a
realistic problem, but I have found this is not at all the case. Most
queries with even many joins have just one or two filters, and one of
the filter ratios is usually obviously far better than any other.

For the most part, simply driving to that best filter first,
following downward joins before upward joins, and perhaps picking up
one or two minor filters along the way, preferably sooner rather than
later, is all it takes to find an excellent execution plan. That plan
is almost certainly the best or so close to the best that the
difference does not matter. This is where the simplified query
diagrams come in. The fully simplified query diagram, shown in Figure 6-3, with the best filter indicated by the capital
F and the other filter by lowercase
f, leads to the same result with only qualitative
filter information.

Figure 6-3. Fully simplified query diagram for the same eight-way join

I will return to this example later and show that you can slightly
improve on this result by relaxing the requirement for a fully robust
execution plan and using a hash join, but for now, I focus on
teaching complete mastery of the skill of optimizing for the best
robust plan. I already showed the 12 best join orders, and I need one
of these for further illustration to complete the solution of the
problem. I choose (C, O, OT, OD, ODT, P,
S, A) as the join order to illustrate.

6.3.2 Completing the Solution for an Eight-Way Join

The rest of the solution is to apply the robust-plan rules to get the
desired join order in a robust plan. A robust plan calls for nested
loops through indexes, beginning with the filter index on the driving
table and followed by indexes on the join keys. Here is the best plan
in detail (refer back to Chapter 5 for the
original query and filter conditions):

Drive
to Customers on an index on (Last_Name,
First_Name), with a query somehow modified to make that
index accessible and fully useful.

Join, with nested loops, to Orders on an index on
the foreign key Customer_ID.

Join, with nested loops, to Code_Translations
(OT) on its primary-key index (Code_Type,
Code).

Join, with nested loops, to Order_Details on an
index on the foreign key Order_ID.

Join, with nested loops, to Code_Translations
(ODT) on its primary-key index
(Code_Type, Code).

Outer join, with nested loops, to Products on its
primary-key index Product_ID.

Outer join, with nested loops, to Shipments on its
primary-key index Shipment_ID.

Outer join, with nested loops, to Addresses on its
primary-key index Address_ID.

Sort the final result as necessary.

Any execution plan that failed to follow this join order, failed to
use nested loops, or failed to use precisely the indexes shown would
not be the optimal robust plan chosen here. Getting the driving table
and index right is the key problem 90% of the time, and this example
is no exception. The first obstacle to getting the right plan is to
somehow gain access to the correct driving filter index for Step 1.
In Oracle, you might use a functional index on the uppercase values
of the Last_Name and First_Name
columns, to avoid the dilemma of driving to an index with a complex
expression. In other databases, you might recognize that the name
values are, or should be, always stored in uppercase, or you might
denormalize with new, indexed columns that repeat the names in
uppercase, or you might change the application to require a
case-sensitive search. There are several ways around this specific
problem, but you would need to choose the right driving table to even
discover the need.

Once you make it possible to get the driving table right, are your
problems over? Almost certainly, you have indexes on the necessary
primary keys, but good database design does not (and should not)
guarantee that every foreign key has an index, so the next likely
issue is to make sure you have foreign-key indexes
Orders(Customer_ID) and
Order_Details(Order_ID). These enable the
necessary nested-loops joins upward for a robust plan starting with
Customers.

Another potential problem is that optimizers might choose a join
method other than nested loops to one or more of the tables, and you
might need hints or other techniques to avoid the use of methods
other than nested loops. If they take this course, they will likely
also choose a different access method for the tables being joined
without nested loops, reaching all the rows that can join at once.

However, I will show that sort-merge or hash joins to a small table like Code_Translations would be fine here, even slightly faster, and nearly as robust, since tables like this are unlikely to grow very large.

In this simple case, with just the filters shown, join order is
likely the least of the problems, as long as you get the driving
table right and have the necessary foreign-key indexes.

6.3.3 A Complex 17-Way Join

Figure 6-4 shows a deliberately complex example to
fully illustrate the method. I have left off the join ratios, making
Figure 6-4 a partially simplified query diagram,
since the join ratios do not affect the rules you have learned so
far. I will step through the solution to this problem in careful
detail, but you might want to try it yourself first, to see which
parts of the method you already fully understand.

Figure 6-4. A complex 17-way join

For Step 1, you quickly find that B4 has the best
filter ratio, at 0.001, so choose that as the driving table.
It's best to reach such a selective filter through
an index; so, in real life, if this were an important enough query,
you might create a new index to use in driving to
B4. For now though, we'll just
worry about the join order. Step 2 dictates that you next examine the
downward-joined nodes C4 and
C5, with a preference to join to better-filtered
nodes first. C5 has a filter ratio of 0.2, while
C4 has a filter ratio of 0.5, so you join to
C5 next. At this point, the beginning join order
is (B4, C5), and the cloud around the
so-far-joined tables looks like Figure 6-5.

Figure 6-5. So-far-joined cloud, with two tables joined

If C5 had one or more nodes connected below, you
would now have to compare them to C4, but since it
does not, Step 2 offers only the single choice of
C4. When you widen the cloud boundaries to include
C4, you find no further nodes below the cloud, so
you move on to Step 3, find the single node A2
joining the cloud from above, and add it to the building join order,
which is now (B4, C5, C4, A2). The cloud around
the so-far-joined tables now looks like Figure 6-6.

Figure 6-6. So-far-joined cloud, after four tables joined

Note that I left in the original two-node cloud in gray. In practice,
you need not erase the earlier clouds; just redraw new clouds around
them. Returning to Step 2, find downstream of the current
joined-tables cloud a single node, B3, so put it
next in the join order without regard to any filter ratio it might
have. Extend the cloud boundaries to include B3,
so you now find nodes C2 and C3
applicable under Step 2, and choose C2 next in the
join order, because its filter ratio of 0.5 is better than the
implied filter ratio of 1.0 on unfiltered C3. The
join order so far is now (B4, C5, C4, A2,
B3, C2). Extend the cloud further around
C2. This brings no new downstream nodes into play,
so Step 2 now offers only C3 as an alternative.
The join order so far is now (B4, C5, C4, A2, B3, C2,
C3), and Figure 6-7 shows the current
join cloud.

Figure 6-7. So-far-joined cloud, with seven tables joined

Step 2 now offers two new nodes below the current join cloud,
D1 and D2, with
D1 offering the better filter ratio. Since neither
of these has nodes joined below, join to them in filter-ratio order
and proceed to Step 3, with the join order so far now
(B4, C5, C4, A2, B3, C2, C3, D1,
D2). This completes the entire branch from
A2 down, leaving only the upward link to
M (the main table being queried) to reach the rest
of the join tree, so Step 3 takes you next to M.
Since you have reached the main table at the root of the join tree,
Step 3 does not apply for the rest of the problem. Apply Step 2 until
you have reached the rest of the tables. Immediately downstream of
M (and of the whole join cloud so far), you find
A1 and A3, with only
A1 having a filter, so you join to
A1 next. Now, the join order so far is
(B4, C5, C4, A2, B3, C2, C3, D1, D2, M,
A1), and Figure 6-8 shows the current
join cloud.

Figure 6-8. So-far-joined cloud, with 11 tables joined

Find immediately downstream of the join cloud nodes
B1, B2, and
A3, but none of these have filters, so look for
two-away filters that offer the best filter ratios two steps away.
You find such filters on C1 and
B5, but C1 has the best, so add
B1 and C1 to the running join
order. Now, the join order so far is (B4, C5, C4, A2, B3,
C2, C3, D1, D2, M, A1, B1, C1). You
still find no better prospect than the remaining two-away filter on
B5, so join next to A3 and
B5, in that order. Now, the only two nodes
remaining, B2 and C6, are both
eligible to join next, being both directly attached to the join
cloud. Choose C6 first, because it has a filter
ratio of 0.9, which is better than the implied filter ratio of 1.0
for the unfiltered join to B2. This completes the
join order:(B4, C5, C4, A2, B3, C2, C3, D1, D2, M, A1, B1,
C1, A3, B5, C6, B2).

Apart from the join order, the rules specify that the database should
reach table B4 on the index for its filter
condition and the database should reach all the other tables in
nested loops to the indexes on their join keys. These indexed join
keys would be primary keys for downward joins to
C5, C4, B3,
C2, C3, D1,
D2, A1, B1,
C1, A3, B5,
C6, and B2, and foreign keys
for A2 (pointing to B4) and
M (pointing to A2). Taken
together, this fully specifies a single optimum robust plan out of
the 17-factorial (355,687,428,096,000) possible join orders and all
possible join methods and indexes. However, this example is
artificial in two respects:

Real queries rarely have so many filtered nodes, so it is unlikely
that a join of so many tables would have a single optimum join order.
More commonly, there will be a whole range of equally good join
orders, as I showed in the previous example.

The later part of the join order matters little to the runtime, as
long as you get the early join order right and reach all the later
tables through their join keys. In this example, once the database
reached node M, and perhaps A1,
with the correct path, the path to the rest of the tables would
affect the query runtime only slightly. In most queries, even fewer
tables really matter to the join order, and often you will do fine
with just the correct driving table and nested loops to the other
tables following join keys in any order that the join tree permits.

If you need to change a query anyway and have the chance to get the whole join order right, you might as well. However, if you already have a plan that is correct in the early join order, the improvement might not be worth the trouble of changing the query just to change the end of the join order.