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

STAR T

20 T

Roughly 2 touches
per result row

20 T

U CCTRY,

CNO,
CNAME,
CTYPE

U

CCTRY,
IEUR DESC ,
INO,
CNO

P,C F,C

P

CNO CNO

INO

CUST INVOICE (+CCTRY)

1,000,000 rows 20,000,000 rows

Figure 8.11 Program B + with ideal indexes satisfying the basic join question.

Perhaps it would be a good idea to apply the BJQ early, when a join has been
written or generated, and to implement the necessary denormalization, together
with the triggers required to maintain the redundant table data (column CCTRY
in table INVOICE).
Now our transaction is fast with any input because there are never more than
20 random touches to index (CCTRY, CNO, CNAME, CTYPE).

Index CCTRY, IEUR DESC, INO, CNO TR = 1 TS = 19

Index CCTRY, CNO, CNAME, CTYPE TR = 20

Fetch 20 × 0.1 ms

LRT TR = 21 TS = 19
21 × 10 ms 19 × 0.01 ms
=210ms+0.2ms+2ms=0.2s
Adding column CCTRY to the invoice table and the index may require 1 . 5 ×
40 , 000 , 000 × 3 bytes = 180 MB of disk space. If a customer moves to another
country, probably a rare occurrence, one table row and one index row must
be updated. For the average customer with 20 invoices, this means 20 random
touches to the table and 40 random touches to the index, 60 × 10 ms = 0.6 s.
Please note that a further, more comprehensive, discussion on table design
aspects of joins, will be found in the Table Design Considerations section at the
end of this chapter.

Conclusion: Nested-Loop Join

A summary of the local response times for the various indexes and programs
used in the case study so far is shown in Table 8.1.