GATE CSE 2006 | Question: 69

Question

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µs.$ 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

Comments

fun fact : Don't get tensed by seeing question,read it completely

---

early SELECT  reduces operations :)

---

@js__ True, but NOT working on this particular question. 

Somebody please clear my doubt!! 👇 @GO Classes @Deepak Poonia

For $x = 5000$, all amounts ($6000, 7000, 8000, 9000, 10000$) are strictly greater than $5000$ (100% of tuples qualify). In that case, both plans perform the exact same number of index probes on enrolled, meaning Plan 1 is not strictly faster for all databases, making C incorrect.

Answer 1

If we carefully look at both the query plans, we can easily identify which plan runs faster.

Let's first understand how we can efficiently run nested loop join.

Algorithm is :

Two relations R and S are joined as follows:

  For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>

According to https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx article from microsoft

This algorithm runs fast if the number of tuples in outer loop are less.

Since, in plan1 we are reducing the number of tuples by placing where condition for selecting rows of plan relation, the join algorithm of plan1 is guaranteed to run faster than that of plan2 and hence Plan1 will execute faster than plan2.

So, answer is C.

Comments

@Pranavpurkar How can you say that the Project keyword is the Project keyword of Relational Algebra and not the normal SELECT Command of SQL?

---

@Abhrajyoti00

Bcz it is specified clearly,

SELECT ON and PROJECT ON.

 

---

@Pranavpurkar Brilliant Observation!

Answer 2

Answer should be (C)

In all cases plan $1$ is faster than plan $2$ cause in plan $1$ we are reducing the load by doing select amount $>x$ and then the loop

But, in case of plan 2 its in the nested loop so it need to check every time and will take more time to execute .

Comments

How could the value of x affect execution speed? I think it should be independent of x, whatever be the value of x, Plan 1 will execute faster than Plan 2.

---

There is a difference between joining after comparing and comparing after joining

Let's say ENROLLED table has 100 tipples and PAID table has 100 elements

After joining Operation let us say we get 100*100 tupples

If we compare and join then it takes 100*10 microseconds for comparing + cost for joining

If we join and compare then it takes cost of joining + 100*100*10 microseconds (because joining gives you 100*100 and comparing all these takes lot of time)

Correct me if I am wrong

So option C is correct because it is comparing and then joining

---

udaysai194

Let's say ENROLLED table has 100 tipples and PAID table has 100 elements
 

how can there be 100 elements in paid table if only 20% of the students paid the amount? 

Answer 3

Both B and C should be true.

Obviously applying select operation before the join operation is better than plan2 bcoz it helps in optimising the entire Join-Selection process.

A is false.

B is true.

suppose two students paid more than x opting for same course so both will be selected as per select operation in plan1 and then we will apply Join between result of select and enrolled printing same course twice.

C is true. 

Effect of select operation becomes more evident when x is any value >=6000(min. amount) bcoz then select will remove these tuples at very first place instead of removing them after join.
But even if x=5000 then select operation though becomes useless bcoz all amounts are greater than or equal to 6000.But still Plan1 is faster than Plan2 bcoz it has to apply select(scanning the tuples) on less number of tuples as compared to Plan2 which will apply select after JOIN leading to scanning of more tuples(although none would be eliminated).

D is false
D would have been true ---> "For x = 9000, Plan I executes faster than Plan 2 for all databases"

Comments

Consider the database in which every student enrolls for a single course only.

In such case : no. of entries in Enrolled table = no. of entries in Paid table

For this database, count of scan & select will be the same in both plans for x=5000, making both plan execution equivalent in speed.

---

What if Each Tuple Corresponds to Enrolled get join with exactly one tuple of Paid.Then in this case , The time taken by select is also same.

---

B is not true as question says "Project on Course" and it will have no duplicate tuples.

Project operation is "select distinct"

Answer 4

Option A is totally false, as both queries output same results.

 

Option B seems right, but projection never allows duplicates(in relational algebra). So, option B is obviously false(The only confusion is if we treat the question as part of SQL, then projection is same as select and it produces duplicates.

 

Option C also seems right.

If we have x=5000, all tuples are already OK. We don't need to filter anything, but still, SQL don't know this. So, the procedure will be same as for other conditions.

For eg suppose enrolled relation contains 1000 tuples and paid relation contains 500 tuples. Then distinct number of students must be atleast 500(because paid relation contains all distinct student and there might be some students in enrolled who haven't paid the fees yet).

Then In Query Ist, we need 500 comparison operations to select tuples where amount > x, and suppose the tuples where x > amount comes out to be 200. Then we get 200 * 1000 = 200,000 entries in output table from which we have to select only the tuples where enrolled.student = paid.student. So total amount of work = 200,000 + 500 = 200,500.

Now, if we go with Query IInd, we first need to do cross product = 500 * 1000 = 500,000, then filter comparison conditions on all 500,000 tuples. So total work done = 500,000 * 2 = 1,000,000

Clearly, we can see option C comes out to be right.

 

This example also counters the Option D, and hence option D is false.

Comments

It is given in the question that “ amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students.”  So totally 100%, ie all of the students have paid the fees. Isn’t it?

---

the tuples where x > amount comes out to be 200

 

 i think it will be  x < amount.

pls check!!

Answer 5

since, both plans need to load both the tables viz.courses and enrolled in the main memory. So disk access time is same for both plans.
Plan 2 does more number of comparisons compared to plan 1 because:

1) filtering of rows is done before join thus less comparison done because of less no of tuples.
1) Join operation will require more comparisons as the second table will have more rows in plan 2 compared to plan 1.

Answer 6

I think answer is B.

Comments

wrong because project is given in question!