Declarative Query Processing in Relational Database Systems - Automated Physical Database Design and Tuning - page 16

involve its included columns, but we can obtain these columns with-
out requiring a lookup over the clustered index or heap. We separate
key and included columns in an index using a | sign. As an example,
Emp(Salary | EId, DId) refers to an index on table Emp with key col-
umn Salary and included columns EId and DId .

1.3.1.1 Index-Based Query Processing

To better understand how indexes can be used in the context of query pro-
cessing, consider again the SQL query whose execution plan we showed in
Figure 1.3, and suppose that we create the following database indexes:

E1 = Emp ( EId , Salary )
E2 = Emp ( Title )
D1 = Dept ( DId | Budget , City )
Figure 1.5 shows an execution plan for the query in the previous section that
exploits such indexes. Index E2 is first used to seek employees who are engi-
neers. For that purpose, the corresponding B + -tree is traversed, and all such
employees are passed upward in the execution plan. However, the tuples in
E2 contain only the Title column (and the corresponding RID of the original
tuple), so an additional lookup to the base table is performed (using an Index
Join alternative). The result of this lookup contains all relevant columns for
every employee that is an engineer. Next, a second Index Join operator is
used to obtain the department of each employee. For each employee, we seek
index D1 to locate the corresponding department. The second Index Seek op-
erator using index D1 evaluates a residual predicate discarding all employees
in departments with high budgets, which considerably reduces the number of
employees. Then, a third Index Join operator finds the manager of each em-
ployee using index Index Seeks over D1 and discards employees who earn less
than their managers. The result of this third join is the set of all employees in
low-budget departments who earn more than their managers. From this point
on, the plan behaves exactly like the alternative one in Figure 1.3.
As we have shown, indexes can be used to obtain new execution plans to
evaluate queries. In addition to Scan operators to obtain base table tuples,
we can leverage different index strategies to obtain the same result. Although
the examples in this section are simple, there are alternatives that intersect
or combine intermediate results produced by multiple indexes on the same
table (see Section 2.1.2 for an example). Index-based plans may significantly
improve query performance (e.g., the index-based plan in Figure 1.5 executed
three times faster than the alternative plan in Figure 1.3 for the same query
on a synthetic database). Of course, this is not always the case. As an ex-
ample, if there are many engineers in table Emp , the alternative in Figure 1.5
would quickly become more expensive than that in Figure 1.3 due to a large
number of table lookups in the first Index Join operator. Indexes also need