Sample Solutions for Quiz 4, Question 5, Block Nested Loop (BNL) Join 3 MARKS
Marking Scheme:
Don’t double-deduct for propagated errors, unless it trivializes the solution. Look
at the context. Errors:
-1 for not taking the ceiling to compute the “block” for the outer table
-1 (once) for not taking the denominator to be B – 2 pages when
computing the “block” for the outer table
-1 for using the wrong B altogether
-1 (once) for using the wrong BNL formula, providing they correctly
computed the “block” of the outer table. By this, I mean instead of: M + ceiling(M / (B-2)) * N, they used something erroneous like:
B + ceiling(M / (B-2)) * N
-0.5 for a non-trivial arithmetic error (no more than two such penalties; ignore trivial errors where it doesn’t really make a big difference
If that -0.5 arithmetic error no longer causes the bigger table to be the winner, but they still provided the two calculations with each table as the outer table, then just use -0.5 for the deduction (and therefore they could get 2.5 out of 3). But, they should get no more than 2 out of 3 if they didn’t compute both tables.
Version 1: Sales has 600,000 records and 60 records/page. Customer has 510,000 records and 50 records/page. B = 30.
a) [0.5 marks] Sales pages = ceiling(600,000 rec / 60 rec/page) = 10,000 pages
b) [0.5 marks] Customer pages = ceiling(510,000 rec / 50 rec/page) = 10,200 pages
c) [1 mark] Computing BNL with Sales as the outer table
10,000 * ceiling(10,000 / (30-2)) * 10,200 page I/Os = 10,000 + 358 * 10,200 page I/Os
= 3,661,600 page I/Os
d) [1 mark] Computing BNL with Customer as the outer table
10,200 * ceiling (10,200 / (30 -2)) * 10,000 page I/Os
= 10,200 + 365 * 10,000 page I/Os
= 3,660,200 page I/Os ← The BEST CHOICE: use Customer as the outer table.
a) If they computed both (c) and (d), but didn’t point out that Customer is best as the outer table, then deduct -0.5 (but it’s OK if they said that the 3,660,200 page I/O calculation is best without actually naming Customer).
If they only computed one of the tables as the outer table, then it’s simply -1 for the missing BNL calculation.
1
Version 2: Sales has 300,000 records and 60 records/page. Customer has 255,000 records and 50 records/page. B = 16.
b) [0.5 marks] Sales pages = ceiling(300,000 rec / 60 rec/page) = 5,000 pages
c) [0.5 marks] Customer pages = ceiling(255,000 rec / 50 rec/page) = 5,100 pages
d) [1 mark] Computing BNL with Sales as the outer table
5,000 * ceiling(5,000 / (16-2)) * 5,100 page I/Os = 5,000 + 358 * 5,100 page I/Os
= 1,830,800 page I/Os
e) [1 mark] Computing BNL with Customer as the outer table 5,100 * ceiling (5,100 / (16-2)) * 5,000 page I/Os
= 5,100 + 365 * 5,000 page I/Os
= 1,830,100 page I/Os ← The BEST CHOICE: use Customer as the outer table.
f) If they computed both (c) and (d), but didn’t point out that Customer is best as the outer table, then deduct -0.5 (but it’s OK if they said that the 1,830,100 page I/O calculation is best without actually naming Customer).
If they only computed one of the tables as the outer table, then it’s simply -1 for the missing BNL calculation.
2