Indexing for Table Joins - Relational Database Index Design and the Optimizers - page 168

The MS/HJ with ideal indexes is quite clearly the most promising access
path, without having to resort to one screen per transaction or using the BJQ. It
has succeeded for two reasons:
1. It has removed the potentially huge problem we encountered in the nested-
loop discussion—the random touches to an inner table, or its index.
2. The incredibly fast sequential access now available with current hardware.
Regardless of the tremendous improvement, the resulting elapsed time of nearly
2 s is perhaps still a little high for an on-line query. If this response time is
unacceptable, a nested-loop join satisfying the BJQ would be necessary.
NESTED-LOOP JOINS VERSUS MS/HJ
AND IDEAL INDEXES
Nested-Loop Joins Versus MS/HJ
Traditionally, nested loop joins (NLJ) have been the preferred join technique,
assuming appropriate indexes have been created and the result table is not
exceptionally large. These “appropriate indexes” refer, of course, to the relevant
semifat, fat, or even ideal indexes with which we are hopefully now perfectly
familiar. Unfortunately, as we have seen in this chapter, even these well-designed
indexes may not be able to provide good performance; large numbers of random
touches to the inner table (or index) may constitute a huge problem. To overcome
this in the past, we have had to resort to limiting the size of the result set, or
applying the basic join question (BJQ) such that all local predicates refer to one
table, neither solution perhaps being desirable.
Over the last few years, as we have observed in this topic on several occa-
sions, hardware has favored the sequential touch. The performance of random
touches has improved too (e.g., faster disks and more memory), but not to the
same extent. The result of this is clearly visible by comparing the 0.01 ms TS
with the 10 ms TR in the QUBE. We can access 1000 rows sequentially in the
time it takes to access one row randomly (ignoring the additional CPU cost and
other issues, such as comebacks, that will be discussed in Chapter 15).
One of the by-products of this transition is that optimizers are now more
likely to choose scans rather than random touches. We have already seen that
even with filter factors as low as 0.1%, a table scan may well be used in pref-
erence to a nonfat, nonclustered index scan. For the same reason, they are now
also more likely to choose MS/HJ than they have in the past. These issues are
particularly important ones to be appreciated by those who have worked with
relational databases for a considerable period of time, but who have not really
considered the implications of these changes. One perhaps should not be too
hasty, for example, in attempting to persuade the optimizer to revert to an index
scan or a NLJ.
It is, of course, the role of the optimizer to determine how to access a table
or index, and which join technique to choose, but these issues affect the index