GATE CS 2006 Q69 — Tuple Calculus and SQL

The two query plans represented in the diagram are:

• Plan 1 (Selection before Join): $\pi_{\text{course}} \left( \text{enrolled} \bowtie \sigma_{\text{amount} > x}(\text{paid}) \right)$
• Plan 2 (Join before Selection): $\pi_{\text{course}} \left( \sigma_{\text{amount} > x}(\text{enrolled} \bowtie \text{paid}) \right)$

Let $N_{\text{paid}}$ be the number of tuples in the paid relation, and $N_{\text{enrolled}}$ be the number of tuples in the enrolled relation. Since a student can enroll in multiple courses, we have $N_{\text{enrolled}} \ge N_{\text{paid}}$.

For $x = 5000$, all payments ($6000, 7000, 8000, 9000, 10000$) satisfy the condition $\text{amount} > 5000$, meaning $100\%$ of the students are selected.

• Plan 1 performs the selection on the paid relation first, requiring $N_{\text{paid}}$ comparisons. It then joins the filtered tuples with enrolled.
• Plan 2 joins the relations first, producing an intermediate relation of size $N_{\text{enrolled}}$, and then performs $N_{\text{enrolled}}$ comparisons.

Since $N_{\text{enrolled}} \ge N_{\text{paid}}$, Plan 1 requires fewer CPU comparisons ($10\,\mu\text{s}$ per check) and avoids processing a larger intermediate relation. Thus, Plan 1 executes faster than Plan 2 for all databases when $x = 5000$.