Physical Database Design

62 CHAPTER 4 Selecting Indexes

4.4 Join Index Selection

Up to this point, index selection has assumed simple queries based only on selection cri-

teria, e.g.

SELECT lastName

FROM employee

WHERE empNo = 45678;

However, most queries involve at least one or more joins, and in-dexes are com-

monly used to speed up the join operations. This sec-tion discusses the index selec-

tion tradeoffs involved in join opera-tions using our simple mathematical model in

Appendix A.

The basic join implementations we will consider are:

• Nested-loop join

– Block nested-loop join

– Indexed nested-loop join

• Sort-merge join

• Hash join

All these basic join implementations are supported by DB2, SQL Server, and Oracle, as

well as many other systems.

Our analysis is based on ...