Indexed Nested-Loop Join in Software

Paint Code 128 Code Set C in Software Indexed Nested-Loop Join

In a nested-loop join (Figure 134), if an index is available on the inner loop s join attribute, index lookups can replace le scans For each tuple tr in the outer relation r, the index is used to look up tuples in s that will satisfy the join condition with tuple tr This join method is called an indexed nested-loop join; it can be used with existing indices, as well as with temporary indices created for the sole purpose of evaluating the join Looking up tuples in s that will satisfy the join conditions with a given tuple tr is essentially a selection on s For example, consider depositor 1 customer Suppose that we have a depositor tuple with customer-name John Then, the relevant tuples in s are those that satisfy the selection customer-name = John The cost of an indexed nested-loop join can be computed as follows For each tuple in the outer relation r, a lookup is performed on the index for s, and the relevant tuples are retrieved In the worst case, there is space in the buffer for only one page of r and one page of the index Then, br disk accesses are needed to read relation r, where br denotes the number of blocks containing records of r For each tuple in r, we perform an index lookup on s Then, the cost of the join can be computed as br + nr c, where nr is the number of records in relation r, and c is the cost of a single selection on s using the join condition We have seen in Section 133 how to estimate the cost of a single selection algorithm (possibly using indices); that estimate gives us the value of c The cost formula indicates that, if indices are available on both relations r and s, it is generally most ef cient to use the one with fewer tuples as the outer relation For example, consider an indexed nested-loop join of depositor 1 customer, with depositor as the outer relation Suppose also that customer has a primary B+ -tree index on the join attribute customer-name, which contains 20 entries on an average in each index node Since customer has 10,000 tuples, the height of the tree is 4, and one more access is needed to nd the actual data Since ndepositor is 5000, the total cost is 100 + 5000 5 = 25, 100 disk accesses This cost is lower than the 40, 100 accesses needed for a block nested-loop join

The merge join algorithm (also called the sort merge join algorithm) can be used to compute natural joins and equi-joins Let r(R) and s(S) be the relations whose natural join is to be computed, and let R S denote their common attributes Suppose

The McGraw Hill Companies, 2001

pr := address of rst tuple of r; ps := address of rst tuple of s; while (ps = null and pr = null) do begin ts := tuple to which ps points; Ss := {ts }; set ps to point to next tuple of s; done := false; while (not done and ps = null) do begin ts := tuple to which ps points; if (ts [JoinAttrs] = ts [JoinAttrs]) then begin Ss := Ss {ts }; set ps to point to next tuple of s; end else done := true; end tr := tuple to which pr points; while (pr = null and tr [JoinAttrs] < ts [JoinAttrs]) do begin set pr to point to next tuple of r; tr := tuple to which pr points; end while (pr = null and tr [JoinAttrs] = ts [JoinAttrs]) do begin for each ts in Ss do begin add ts 1 tr to result ; end set pr to point to next tuple of r; tr := tuple to which pr points; end end Figure 136 Merge join

that both relations are sorted on the attributes R S Then, their join can be computed by a process much like the merge stage in the merge sort algorithm Figure 136 shows the merge join algorithm In the algorithm, JoinAttrs refers to the attributes in R S, and tr 1 ts , where tr and ts are tuples that have the same values for JoinAttrs, denotes the concatenation of the attributes of the tuples, followed by projecting out repeated attributes The merge join algorithm associates one pointer with each relation These pointers point initially to the rst tuple of the respective relations As the algorithm proceeds, the pointers move through the relation A group of tuples of one relation with the same value on the join attributes is read into Ss