Exam Prep 6
Iterators and Joins
Announcements
Project 3 pt. 2 is due Thurs 10/15 at 11:59PM.
Vitamin 7 is due Mon 10/19 at 11:59PM.
Iterators and Joins
Joins
Single Nested Loop Join (SNLJ)
Page Nested Loop Join (PNLJ)
Block Nested Loop Join (BNLJ)
Joins
Notation
Joins
Notation
Joins
Notation
Joins
Notation
+ cost to sort S using external sorting
+ [R] + [S]
Joins
Notation
Normally:
Joins
Notation
Sort-merge optimization:
Note that in this example, previously we needed only 3 input buffers, but the optimized version needed 6 input buffers!
You can also do a partial version where you finish sorting one table normally, then do the join with the runs of the unmerged table and the one run of the merged table. The partial version saves either 2 * [R] or 2 * [S], depending on which table you wait to merge.
Joins
Notation
Worksheet
Joins 1
Question 1a
What is the I/O cost of a simple nested loop join for Students ⋈ AssignmentSubmissions? How about for AssignmentSubmissions ⋈ Students?
Notation
Question 1a
What is the I/O cost of a simple nested loop join for Students ⋈ AssignmentSubmissions? How about for AssignmentSubmissions ⋈ Students?
Answer: 160,020 I/Os.
The formula for a simple nested loop join is [S] +|S|·[A].
Plugging in the numbers gives us 20 + (20·200)·40 = 160,020 I/Os
Answer: 200,040 I/Os.
The formula for a simple nested loop join is [A] +|A|·[S].
Plugging in the numbers gives us 40 + (40·250)·20 = 200,040 I/Os
Notation
Question 1b
What is the I/O cost of a block nested loop join for Students ⋈ AssignmentSubmissions? Assume our buffer size is B= 12 pages.
Notation
Question 1b
What is the I/O cost of a block nested loop join for Students ⋈ AssignmentSubmissions? Assume our buffer size is B= 12 pages.
Answer: 100 I/Os.
First, we can calculate our block size: B−2 = 10.
Since Students is our left table, we calculate the number of blocks of Students :[S]/(B−2) = 20/10 = 2.
Thus the final cost is [S] plus 2 passes through all of [A], or 20 + 2·40 = 100 I/Os.
Notation
Question 1c
What is the I/O cost of a block nested loop join for AssignmentSubmissions ⋈ Students? Assume our buffer size is B= 12 pages.
Notation
Question 1c
What is the I/O cost of a block nested loop join for AssignmentSubmissions ⋈ Students? Assume our buffer size is B= 12 pages.
Answer: 120 I/Os.
As before, we can calculate our block size: B−2 = 10.
Since AssignmentSubmissions is our left table, we calculate the number of blocks: [A]/(B−2) = 40/10 = 4.
Thus the final cost is [A] plus 4 passes through all of [S], or 40 + 4·20 = 120 I/Os.
Notation
Question 1d
What is the I/O cost of an Index-Nested Loop Join for Students ⋈ AssignmentSubmissions? Assume we have a clustered alternative 2 index on AssignmentSubmissions.studentid, in the form of a height 2 B+ tree. Assume that index node and leaf pages are not cached; all hits are on the sameleaf page; and all hits are also on the same data page.
Notation
Question 1d
What is the I/O cost of an Index-Nested Loop Join for Students ⋈ AssignmentSubmissions? Assume we have a clustered alternative 2 index on AssignmentSubmissions.studentid, in the form of a height 2 B+ tree. Assume that index node and leaf pages are not cached; all hits are on the sameleaf page; and all hits are also on the same data page.
Answer: 16,020 I/Os.
The formula is [S] +|S|·(cost of index lookup).
The cost of index lookup is 3 I/Os to access the leaf, and 1 I/O to access the data page for all matching records.
So the total cost is 20 + 4000·4 = 16,020 I/Os.
Notation
Question 1e
Now assume we have an unclustered alternative 2 index on AssignmentSubmissions.studentid, in the form of a height 2 B+ tree. Assume that index node pages and leaf pages are never cached, and we only need to read the relevant leaf page once for each record of Students, and all hits are on the same leaf page. What is the I/O cost of an Index-Nested Loop Join for Students ⋈ AssignmentSubmissions?
Notation
Question 1e
Now assume we have an unclustered alternative 2 index on AssignmentSubmissions.studentid, in the form of a height 2 B+ tree. Assume that index node pages and leaf pages are never cached, and we only need to read the relevant leaf page once for each record of Students, and all hits are on the same leaf page. What is the I/O cost of an Index-Nested Loop Join for Students ⋈ AssignmentSubmissions?
Answer:22,020 I/Os.
The formula is [S] +|S|·(cost of index lookup). This time though, the cost of index lookup is 3 I/Os to access the leaf, and 1 I/O to access the data page for each matching record.
How many records match per key? We actually haven’t told you! But, we do know that we will eventually have to access each record exactly once (since each AssignmentSubmission is foreign-keyed on a studentid) - so there will be |A|= 10,000 data page lookups, one for each row. So the total cost is 20 + 4000·3 + 10000 = 22,020 I/Os.
Notation
Question 1f
What is the cost of an unoptimized sort-merge join for Students ⋈ AssignmentSubmissions? Assume we have B = 12 buffer pages.
Notation
Question 1f
What is the cost of an unoptimized sort-merge join for Students ⋈ AssignmentSubmissions? Assume we have B = 12 buffer pages.
Answer:300 I/Os.
The formula is〈cost of sorting S〉+〈cost of sorting A〉+ [S] + [A].
For sorting S: The first pass will make two runs, which is mergeable in one merge pass; thus, we need two passes; For sorting A: The first pass will make four runs, which is mergeable in one merge pass; thus, we need two passes.
Thus the total cost is (2·2[S]) + (2·2[A]) + [S] + [A] = 5([S] + [A]) = 5·60 = 300 I/Os.
Notation
Question 1g
What is the cost of an optimized sort-merge join for Students ⋈ AssignmentSubmissions? Assume we have B = 12 buffer pages.
Notation
Question 1g
What is the cost of an optimized sort-merge join for Students ⋈ AssignmentSubmissions? Assume we have B = 12 buffer pages.
Answer: 180 I/Os.
The difference from the above question is that we will skip the last write in the external sorting phase, and the initial read in the sort-merge phase. For this to be possible, all the runs of S and A in the last phase of external sorting should be able to fit into memory together.
From the previous question, we know there are 2 + 4 = 6 runs, which fits just fine in our buffer of 12 pages. Thus the total cost is 300−2[S]−2[A] = 300−120 = 180 I/Os.
Notation
Question 1h
In the previous question, we had a buffer of B= 12 pages. If we shrank B enough, the answer we got might change. How small can the buffer B be without changing the I/O cost answer we got?
Question 1h
In the previous question, we had a buffer of B= 12 pages. If we shrank B enough, the answer we got might change. How small can the buffer B be without changing the I/O cost answer we got?
Answer: 9 buffer pages.
The restriction for optimized sort-merge join is that the number of final runs of S and A can both fit in memory simultaneously. (i.e., the number of runs of S + the number of runs of A≤B - 1). We had 2 + 4 runs last time, which fit comfortably in 12−1 buffer pages (recall that one page is reserved for output).
What about B= 9? Now we have 3 runs for S and 5 runs forA, which just exactly fits in 9−1 buffer pages.Since 9 buffer pages fits perfectly, any smaller would force more merge passes and thus more I/Os.
Question 1i
What is the I/O cost of Grace Hash Join on these tables? Assume we have a buffer of B = 6 pages
Question 1i
What is the I/O cost of Grace Hash Join on these tables? Assume we have a buffer of B = 6 pages
Answer: 180 I/Os
For Grace Hash Join, we have to walk through what the partition sizes are like for each phase, one phase at a time. In the partitioning phase, we will proceed as in external hashing. We will load in 1 page a time and hash it into B−1 = 5 partitions. This means the 20 pages of S get split into 4 pages per partition, and the 40 pages of A get split into 8 pages per partition.
Do we need to recursively partition? No! Remember that the stopping condition is that any table’s partition fits in B−2 = 4 buffer pages; the partitions of S satisfy this.In the hash joining phase, the I/O cost is simply the total number of pages across all partitions - we read all of these in exactly once. Thus the final I/O cost is 20 + 20 for partitioning S, 40 + 40 for partitioning A, and 20 + 40 for the hash join, for a total cost of 180 I/Os.
Question 1j.a
Our program memory is extremely limited (not buffer memory)! As a result, we only have enough memory to store 1 hash function. What join algorithms work here provided it fits our system constraints)? Why?
Question 1j.a
Our program memory is extremely limited (not buffer memory)! As a result, we only have enough memory to store 1 hash function. What join algorithms work here provided it fits our system constraints)? Why?
Anything that's not GHJ or Hash Join. Hash Join requires one of the relations to fit in memory (B-2 pages). For GHJ, since we have only 1 hash function, we can not recursively partition. Remember for recursive partitioning, a new, independent hash function must be used in order to effectively re-partition the data.
Question 1j.b
Now, we have very little buffer memory (only 3 pages). What join algorithms work here? How are the different join algorithms affected by the given constraint? Why?
Question 1j.b
Now, we have very little buffer memory (only 3 pages). What join algorithms work here? How are the different join algorithms affected by the given constraint? Why?
BNLJ, PNLJ, and SNLJ would work. Given the limited buffer memory, BNLJ will reduce to PNLJ, since the size of the blocks will be limited to 1 page. In other words, the BNLJ and PNLJ will have the same IO cost. Note that the limited buffer memory does not impact SNLJ, since SNLJ simply takes each record in the first relation and searches for all matches in the second relation.
Naive Hash Join will not work, since neither of the relations can directly fit in B-2 pages. To fit in B-2 pages means that we can create a hash table for that relation.
GHJ would work with this constraint. We can repeatedly hash the two relations into B-1 buffers to create partitions that are ≤ B − 2 pages big, which eventually allows us to fit the relations into memory and perform a Naive Hash Join. Due to the limited buffer memory, GHJ will require a significant number of partitioning passes, which in turn results in an increase in the overall IO cost.
SMJ would work with this constraint. Due to the limited buffer memory, SMJ would require a significant number of passes to sort a relation. This in turn will result in an increase in the overall IO cost.
Question 1j.c
Now, assume that Students is only 1 page. What is the best join algorithm IO wise?
Question 1j.c
Now, assume that Students is only 1 page. What is the best join algorithm IO wise?
All join algorithms would work in this case, since our requirements are looser than than when Students had 600 pages. PNLJ/BNLJ/HJ/GHJ is the best IO wise.
SNLJ: [R] + p_r[R][S] = 1 + 60(1 * 600) = 36001 IOs �PNLJ: [R] + [R][S] = 1 + (1 * 600) = 601 IOs�BNLJ: [R] + ceil([R]/(B-2))[S] = 1 + 1 * 600 = 601 IOs�HJ/GHJ: [R] + [S] = 1 + 600 = 601 IOs�SMJ: Since our tables are not yet sorted, we'd incur some overhead to sort them, which would take a significant number of IOs.
Question 1j.d
Now, assume that all student_ids in both tables are exactly the same (i.e. assume the primary key constraint does not hold). What join algorithms work here? How are the different join algorithms affected by the given constraint? Why?
Question 1j.d
Now, assume that all student_ids in both tables are exactly the same (i.e. assume the primary key constraint does not hold). What join algorithms work here? How are the different join algorithms affected by the given constraint? Why?
GHJ and Hash Join would not work in this case. Since all student_ids are exactly the same, GHJ and Hash Join will be subject to extreme data skew (data hashing to the same bucket).
The nested loop joins (BNLJ, PNLJ, SNLJ) and SMJ will work in this case, however, it is worth considering what these joins will yield. Assuming that the joins are performed by matching student_ids, the nested loop joins (BNLJ, PNLJ, SNLJ) and SMJ will match every row from the left relation to all rows in the right relation.
More Joins
Question 2a
What is the I/O cost of a block nested loop join for joining Teams on Players on Teams.team
id = Players.team id? Assume our buffer size is B = 10 pages.
Notation
Question 2a
What is the I/O cost of a block nested loop join for joining Teams on Players on Teams.team
id = Players.team id? Assume our buffer size is B = 10 pages.
Answer: 1,230 I/Os.
The formula for a block nested loop join is [T] + ceil([T]/(B − 2)) · [P].
Plugging in the numbers gives us 30 + 4 · 300 = 1, 230 I/Os.
Notation
Question 2b
Assume we have an unclustered index of height 1 on Teams.team id. What is the I/O cost of an index nested loop join on Teams.team id = Players.team id using this index? You can assume that every player only plays on one team each year.
Notation
Question 2b
Assume we have an unclustered index of height 1 on Teams.team id. What is the I/O cost of an index nested loop join on Teams.team id = Players.team id using this index? You can assume that every player only plays on one team each year.
Answer: 45,300 I/Os.
If we are using an index on Teams.team id, this means that Teams should be the inner relation, because for each record in Players, we will search our index for the corresponding record in the Teams table. Thus the formula for the index nested loop join is [P] + |P|· cost to find matching records. Each search will cost 3 I/Os (2 to read the root + leaf, and 1 additional I/O to read a data page).
Plugging in the numbers gives us 300 + (300 · 50) · 3 = 45,300 I/Os.
Notation
Question 2c
Now, assume we have a clustered index of height 2 on Players.player id and an clustered index of height 3 on Players.team id. If each team has 25 players each year, what is the lowest I/O cost of the join on Teams.team id = Players.team id using one of these indexes?
Notation
Question 2c
Now, assume we have a clustered index of height 2 on Players.player id and an clustered index of height 3 on Players.team id. If each team has 25 players each year, what is the lowest I/O cost of the join on Teams.team id = Players.team id using one of these indexes?
Answer: 6,030 I/Os.
Although the index on Players.player id has a lower height, it is not useful for this join since the player id column is not part of the join. We must use the clustered index of height 3 on Players.team id. Since we are using an index on Players.team id, the Players table should be the inner relation. The formula will be [T] + |T|· cost to find matching records. Each search will cost 5 I/Os (4 to read down to the leaf level, and 1 additional I/O to read a data page since it is clustered).
Plugging in the numbers gives us 30 + (30 · 40) · 5 = 6,030 I/Os.
Notation
Question 2d
Assume the index on Players.team id is actually unclustered. What is cost of the join on on Teams.team id = Players.team id using this index?
Notation
Question 2d
Assume the index on Players.team id is actually unclustered. What is cost of the join on on Teams.team id = Players.team id using this index?
Answer: 34,830 I/Os.
The equation will still be [T] + |T|· cost to find matching records; the only difference from the previous question is that the cost of searching matching records will be different, since it is unclustered.
Each search will cost 29 I/Os (4 to read down to the leaf level, and 25 additional I/Os to read data pages) since we must assume that the 25 player records for each team are on separate data pages.
Plugging in the numbers gives us 30 + (30 · 40) · 29 = 34, 830 I/Os.
Notation
Question 2e
Consider a universe where there are no limits on team size and players get to time travel to play for whatever team they want, and 75% of players choose to travel to 2020 to play for the best baseball team, the San Diego Padres. In other words, imagine that 75% of the records in the Players table have the same team_id. What are the effects on the performance of the different join algorithms?
Question 2e
Consider a universe where there are no limits on team size and players get to time travel to play for whatever team they want, and 75% of players choose to travel to 2020 to play for the best baseball team, the San Diego Padres. In other words, imagine that 75% of the records in the Players table have the same team_id. What are the effects on the performance of the different join algorithms?
Simple, page, and block nested loop join would have the same performance as the original scenario.
Index nested loop joins could potentially be improved if we had enough buffer pages to keep the leaf node corresponding to the repeated team_id in memory.
Question 2e
Consider a universe where there are no limits on team size and players get to time travel to play for whatever team they want, and 75% of players choose to travel to 2020 to play for the best baseball team, the San Diego Padres. In other words, imagine that 75% of the records in the Players table have the same team_id. What are the effects on the performance of the different join algorithms?
For sort merge join, many duplicate values generally tend to increase the number of I/Os, since iterators need to be reset. In this scenario, using the Players table as the outer relation during the merge phase could alleviate these concerns, since there are no duplicate team_id values in the Teams table.
Question 2e
Consider a universe where there are no limits on team size and players get to time travel to play for whatever team they want, and 75% of players choose to travel to 2020 to play for the best baseball team, the San Diego Padres. In other words, imagine that 75% of the records in the Players table have the same team_id. What are the effects on the performance of the different join algorithms?
Grace hash join requires us to partition our data until at least one of our tables has chunks that are small enough to fit into memory. Since the Teams table does not have duplicate team_id values, there should not be significant differences in the number of I/Os compared to the original scenario.
Attendance Link