Databases Reference
In-Depth Information
Indexed nested-loop join Case 1:
Scan foreign key table once and index to the
primary key table once.
The basic strategy is to do a full scan of the table containing the foreign keys, and
for each qualifying join attribute value, locate the corresponding unique row in the
primary key table via a unique index. There will be a scan of the foreign key table
and (
h
+ 1) block accesses to the primary key table via the unique index to each tar-
get row. Let the number of target rows, ntr = 100 qualifying rows for the foreign
key table (assignedTo) matching one row in the primary key table (project) in
Example Query 4.2. Assume height
h
= 2 for the B+tree index to table project.
join I/O time = scan the entire foreign key table (assignedTo) +
index to the primary key table (project) qualifying row
= (77 buffers + (h + 1) block (buffer) accesses)
×
5.8 ms
×
= (77 + 3)
5.8 ms
= .46 seconds.
Indexed nested-loop join Case 2:
Index to the primary key table, and then index
to the foreign key table.
Another indexed nested-loop join strategy is to use a B+tree or hash index to the
primary key table once for the qualifying primary key value, then use a B+tree com-
posite index to the foreign key table for the rows containing the qualifying foreign
key values that match the primary key value. For this case, assume the composite
index height,
h
= 3, one block required for the pointers to ntr = 100 target foreign
key rows as given in Case 1.
join I/O time = index to the primary key table +
index to the foreign key table
= ((h + 1) + [h + 1 + ntr])
×
5.8 ms
×
= (4 + 104)
5.8 ms
= .63 seconds.
Comparing the join times, we see that table scans have become very efficient, mak-
ing Case 1 the better strategy here.
4.4.4 Sort-merge Join
The sort-merge join strategy, unlike the nested-loop strategy, takes advantage of row
order in the same way that batch processing does. If the tables are both sorted on the
join columns, then only a single sequential scan of each table is required to complete the
join. If one or both tables are not sorted on the join column, then each unsorted table is
sorted before the merge is executed. Even with the overhead of a sort operation, this
