Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 25

S but additionally returns
all rows in R that do not match any row in S (these additional tuples have
NULL values in columns in S ). Symmetric outerjoins preserve both the input
relations. Unlike regular joins, a sequence of outerjoins and joins does not
freely commute. However, the following algebraic equivalence allows pulling
outerjoins above a block of joins:

S (denoted R → S ) is similar to the join R

R ( S → T ) ≡ ( R S ) → T

After outerjoins have been delayed in this manner, joins may be freely re-
ordered. As with other transformations, there is no guarantee as to which
alternative is better in all cases, and thus the use of this identity needs to be
cost based.

2.1.2 Access Path Selection
Earlier query optimizers chose at most one index for accessing tuples of a
table in a given query (see, for instance, the examples in Chapter 1). For
queries with complex single-table predicates, more advanced strategies can
manipulate multiple indexes simultaneously to eciently obtain the qualifying
tuples. Consider as an example a SQL query that returns all engineers who earn
less than $50,000:

SELECT *
FROM Emp
WHERE Title = 'Engineer' AND Salary < 50000
and suppose that we have single-column indexes E 1

= Emp ( Title ) and E 2 =

. Traditionally, the alternative plans that the optimizer would
consider for the query would be either (1) a table or clustered index scan
filtering each tuple by both predicates, or (2) an index seek using either E 1or
E 2, followed by lookups to the primary index to obtain the remaining columns,
followed by a filter on the predicate that was not evaluated by the index. By
using both indexes simultaneously, we can sometimes obtain better execution
plans. In this case, we could perform what is called an index intersection as
follows:

Emp ( Salary )

1. Use index E 1 to obtain all RIDs of tuples satisfying Title =
'Engineer' (each index contains, in addition to the index columns,
the RID of each tuple).
2. Similarly, use index E 2 to obtain all RIDs of tuples that satisfy Salary
< 50000 .
3. Intersect both lists of RIDs (this procedure is similar to a join).
4. Fetch the resulting records (which satisfy both predicates).

This alternative can greatly reduce execution times because (1) the individ-
ual indexes E 1 and E 2 are in general smaller than the clustered index, (2) the