Calculate the cost functions for different options of executing the JOIN operation OP7 discussed in section 19.3.2.

Question

What will be an ideal response?

Answer 1

The operation is
OP7: DEPARTMENT |x| MGRSSN=SSN EMPLOYEE.
As in section 18.2.3 we assume the secondary index on MGRSSN of DEPARTMENT, with
selection cardinality s=1 and level x=1; also the join selectivity of OP7 is js = 1/125 =
1/|DEPARTMENT|, because MGRSSN acts as a key of the DEPARTMENT table. (Note:
There is exactly one manager per department.)
Finally, we assume the same blocking factor as the OP6 join of these two tables:
bfr = 4 records/block, as the results involve the same number of attributes. Thus the
applicable methods are J1 and J2 with either table as the outer loop; the quantities
parallel those of OP6:
J1 with EMPLOYEE as outer loop:
CJ1 = 2000 + (2000*13) + (((1/125)*10000*125)/4) = 30,500
J1 with DEPARTMENT as outer loop:
CJ1' = 13 + (13*2000) + (((1/125)*10000*125)/4) = 28,513
J2 with EMPLOYEE as outer loop, and MGRSSN as secondary key for S:
[EMPLOYEE as outer loop and primary index on SSN gives the same result.]
CJ2a = b R + (|R|*(x S + s)) + ((js*|R|*|S|)/bfr
= 2000 + (2000*(1+1)) + (((1/125)*10000*125)/4)
= 24,500
J2 with DEPARTMENT as outer loop:
CJ2c = b S + (|S|*(x R + 1)) + ((js*|R|*|S|)/bfr
= 13 + (125*2) + (((1/125)*10000*125)/4)
= 13 + 250 + 2500 = 2,763 [ ! ]
Obviously this optimization was worthwhile, to get the latter minimum.