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

START

20 KT 500 KT 1 KT

FF = 0.1%

FF = 1%

IEUR...

ITEMT...

MS/HJ

TEMP

NL

ITEM

INVOICE

500 KT

20,000,000 rows

100,000 rows

ITEMNO...

TR = 1K
(1 + 1K +1 + 1)

INVOICE_ITEM

50,000,000 rows

Figure 8.20 Predicting table access order in a nested-loop and merge scan/hash join.

Step 2: Join the Work File with INVOICE (MS/HJ)

Workfile TR = 1 TS = 500,000

Index (IEUR,...) TR = 1 TS = 0.001 × 20,000,000 = 20,000

LRT = 2 × 10 ms + 520 , 000 × 0 . 01 ms = 5s
With merge scan, 520,000 rows must be sorted and merged:
2 × 520 , 000 × 0 . 01 ms = 10 s

Hash join is probably faster because the smaller row set, 20,000, should fit
in memory.

Local Response Time The total response time, with these indexes, is 30 s
using merge scan or between 20 and 30 s with hash join—impressive compared
to nested loop (12 min).

WHY JOINS OFTEN PERFORM POORLY

Fuzzy Indexing

One of the oldest indexing recommendations is to “index join columns.” Actually
this is an expanded version of the basic recommendation “ create an index for
the primary key and an index starting with each foreign key .” Indexing the join
predicate columns makes the nested loop a feasible alternative, but thin join