### Solution to Exercises in Query Processing Notes

Consider the following modification to our running example:
```   Student(ID, Name, Major)  // ID is key
Course(Num, Dept, Units)  // Num is key
Took(ID, Num, Quarter)    // (ID,Num) is key
```
Query 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.
Note: join associativity matters

Question: How many possible physical query plans are there for this query?

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
```

Question: What if the system also supports NLJ with inner index (NLIJ)?
(Note: By convention, the right operand of NLJ and NLIJ is the inner.)

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
```

Question: Go back to the original problem (no NLIJ) but assume that Sort-Merge Join is symmetric. Now how many plans?

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

```