Consider the relation enrolled(student, course) in which (student, course) is…
2006
Consider the relation enrolled(student, course) in which (student, course) is the primary key, and the relation paid(student, amount), where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to "list all courses taken by students who have paid more than x".
A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10 micro-seconds. Which of the following statements is correct?
- A.
Plan 1 and Plan 2 will not output identical row sets for all databases.
- B.
A course may be listed more than once in the output of Plan 1 for some databases
- C.
For x = 5000, Plan 1 executes faster than Plan 2 for all databases.
- D.
For x = 9000, Plan I executes slower than Plan 2 for all databases.
Attempted by 243 students.
Show answer & explanation
Correct answer: C
Key insight: compare how many index probes each plan performs and how the selection on amount affects that count.
Plan 1 (left): sequentially scan paid and apply amount > x to find qualifying students; for each qualifying student do an indexed lookup into enrolled to retrieve that student's courses; finally project course.
Plan 2 (right): perform the join in a way that causes work proportional to the number of enrolled rows (student-course pairs) and then apply amount > x after the join; effectively this leads to probing/processing per enrolled tuple rather than per qualifying student.
Notation: let S be the number of students and E be the number of enrolled rows (total student-course pairs). By definition E >= S (each student has at least one enrolled row if enrolled).
Apply these facts to x = 5000:
Given the amount distribution (6000, 7000, 8000, 9000, 10000 each 20%), every paid value is greater than 5000, so all S students qualify.
Plan 1 does one scan of paid + approximately S indexed probes into enrolled (one probe per qualifying student).
Plan 2 ends up doing work proportional to E (it must examine/join each enrolled row and then apply the amount filter), so it performs about E probes/operations.
Since E >= S, Plan 1 performs no more index probes than Plan 2 and typically performs fewer, so Plan 1 executes faster (or equal in the degenerate case when E = S).
Conclusion: For x = 5000 Plan 1 executes faster than Plan 2 for all databases (option stating this claim is correct).
Notes and caveats:
Whether duplicate course names appear in the final output depends on whether the query requests DISTINCT courses. Duplicate appearance is governed by projection semantics, not by choosing Plan 1 vs Plan 2.
For other values of x (e.g., x = 9000) the relative cost depends on selectivity and on E versus S (courses per student). You cannot claim a universal ordering without those counts.