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?
Answer: C. For x = 5000, Plan 1 executes faster than Plan 2 for all databases. — Concept: In a relational query plan, pushing a selection below an inner join is logically safe when the predicate uses only attributes of that input. Its…
- 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 337 students.
Show answer & explanation
Correct answer: C
Concept: In a relational query plan, pushing a selection below an inner join is logically safe when the predicate uses only attributes of that input. Its performance effect comes from selectivity: filtering the outer input earlier can reduce indexed nested-loop probes, while projection in relational algebra returns a set of values.
Application:
Let P be the number of tuples in paid. Plan 1 scans paid, tests amount > x, and uses only the qualifying paid tuples as the outer input of the indexed nested-loop join.
Plan 2 scans all P paid tuples, uses them as the outer input of the same indexed nested-loop join, and tests amount > x on the join output.
For x = 5000, all stated amounts—6000, 7000, 8000, 9000, and 10000—pass the predicate. Under the intended GATE cost model, Plan 1 performs the cheap test during the paid scan and avoids carrying the predicate through the joined tuples, whereas Plan 2 evaluates it after the join.
The join and early-selection rule therefore support the statement that, for x = 5000, Plan 1 executes faster than Plan 2 in the exam’s intended model.
Cross-check and contrast:
Both plans apply the same amount predicate to the same inner-join condition, so selection pushdown does not change the resulting course relation.
The final projection on course has set semantics in relational algebra, so repeated course values collapse in the projected relation.
For x = 9000, only the 10000 group qualifies. Early selection gives Plan 1 a smaller outer input, so a universal claim that Plan 1 is slower is unsupported.
Result: For x = 5000, Plan 1 executes faster than Plan 2 for all databases, under the cost model intended by the GATE 2006 question.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Ssc Je Imd Scientific Assistant Computer Science