Student(ID, Name, Major) // ID is key Course(Num, Dept, Units) // Num is key Took(ID, Num, Quarter) // (ID,Num) is keyQuery to find all students named "Mary" who took at least one 3-unit course in their own major in the fall quarter 2007:

Select * From Student, Course, Took Where Took.ID = Student.ID And Took.Num = Course.Num And Course.Dept = Student.Major And Student.Name = 'Mary' And Course.Units = 3 And Took.Quarter = 'Fall07'Suppose:

- The DBMS supports
*Nested-Loops Join*(NLJ),*Sort-Merge Join*, and*Hash Join*. For now assume that all 3 join methods are asymmetric, i.e., joins are noncommutative. - Each table can be accessed either with a
*Table Scan*or a*Condition-Based Index Scan*(assume all relevant attributes are indexed). - All single-table selections are pushed down, i.e., they are performed before joins.
- For now assume that the system will not perform NLJ using an index on the inner relation's join attribute.

*Solution*:

It helps to think of the problem algebraically. We are trying to generate physical plans for a logical expression of the form: SELECT1(R1) JOIN1 SELECT2(R2) JOIN2 SELECT3(R3) where: - R1, R2, and R3, are permutations of Student, Course, Taking - SELECT1, SELECT2, and SELECT3 are table access methods - JOIN1 and JOIN2 are join methods Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join method combinations = 3 * 3 = 9 Number of associativities = 2 TOTAL = 6 * 8 * 9 * 2 = 864

(

Case (a): System can exploit 2 indexes on a table

*Solution*:

First consider the original problem with 4 join methods: Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join method combinations = 4 * 4 = 16 Number of associativities = 2 TOTAL = 6 * 8 * 16 * 2 = 1536 However, plans of the following form are invalid, because NLIJ cannot be used with a composite inner: SELECT1(R1) NLIJ (SELECT2(R2) JOIN2 SELECT3(R3)) How many plans of this form did we include in the 1536 total? Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join methods = 4 TOTAL = 192 GRAND TOTAL = 1536 - 192 = 1344

Case (b): System can't exploit 2 indexes on a table

*Solution*:

(1) Plans that don't use NLIJ = 864 (original problem) (2) Plans that use NLIJ must be of one of the following four forms: (a) (SELECT1(R1) NLIJ TABLE-SCAN(R2)) JOIN2 SELECT3(R3) (b) (SELECT1(R1) JOIN1 SELECT2(R2)) NLIJ TABLE-SCAN(R3) (c) SELECT1(R1) JOIN1 (SELECT2(R2) NLIJ TABLE-SCAN(R3)) (d) (SELECT1(R1) NLIJ TABLE-SCAN(R2)) NLIJ TABLE-SCAN(R3) Right-associative plans can't use NLIJ for the first join. (a)-(c) all have: Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access method combinations = 2 * 2 = 4 Number of join methods = 3 TOTAL = 72 * 3 = 216 (d) has: Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access methods = 2 TOTAL = 12 GRAND TOTAL = 864 + 216 + 12 = 1092

*Solution*:

(1) Plans that don't use SMJ at all = original problem with 2 join methods: Number of relation orderings (permutations) = 3 * 2 * 1 = 6 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join method combinations = 2 * 2 = 4 Number of associativities = 2 TOTAL = 6 * 8 * 4 * 2 = 384 (2) Plans that use SMJ for innermost join only: (SELECT1(R1) SMJ SELECT2(R2)) JOIN2 SELECT3(R3) Number of relation orderings = 3 Commutativity of JOIN2 = 2 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join methods = 2 TOTAL = 3 * 2 * 8 * 2 = 96 (3) Plans that use SMJ for outermost join only: (SELECT1(R1) JOIN1 SELECT2(R2)) SMJ SELECT3(R3) Number of relation orderings = 6 Number of table access method combinations = 2 * 2 * 2 = 8 Number of join methods = 2 TOTAL = 6 * 8 * 2 = 96 (4) Plans that use two SMJs: (SELECT1(R1) SMJ SELECT2(R2)) SMJ SELECT3(R3) Number of relation orderings = 3 Number of table access method combinations = 2 * 2 * 2 = 8 TOTAL = 3 * 8 = 24 GRAND TOTAL = 384 + 96 + 96 + 24 = 600