Query Optimization, Individual Part

Note to self:Next time around, be explicit if you want them to annotate evaluation trees with algorithms. Most of them showed the join trees, etc., but didn't specify which algortihms were used. Also, you didn't indicate clearly if you want them to tell you WHY the queries are different for question 1 (if you want them to, some did and some didn't). On correct/equivalent: some students focused on things like "equivalent" only if sid is a key, etc. Clarify how you want them to answer this (likely assuming data is correct, keys are as specified in sql1, etc.) Finally, asking which query was likely to better just resulted ina whole lot of speculation by the students, and you got very different (even opposite) answers with fuzzy but rational sounding reasons. You should make them calculate cost in some page way first. When you asked them to speculate why these were different, that's what you got: a whole lot of speculation. Maybe that's what you want: but grading that (apart from all correct) was pretty hard. But still, they seem to have learned something from thinking hard about this, even if you can't grade it well. In drawing evaluation trees, they didn't well distinguish between left and right (left for outer), you should specify this better next time. Find a copy of an assignment you kept as a starting point to an answer key.

This assignment should be done individually. You may work with other people, get ideas, help each other debug, and so on; but the content that you submit should be your own.

Setup

This part of the assignment uses the same college enrollment data that you used for the last SQL assignment. If you do not still have the data set up from the last assignment, visit the previous SQL assignment web page to find instructions on connecting to lime and loading the data.

Learning about EXPLAIN

Read the documentation about EXPLAIN in the PostgreSQL manual. Look at the examples at the end to see specifically how to use it.

Questions

I've provided below some queries that were submitted by students for questions from the previous SQL assignment. For some of the questions from the previous assignment, I'm providing two or three alternative choices as solutions that yield the same answer when you run them. For each group of queries, answer the following questions:

Are the alternative queries all correct and/or equivalent? Are they guaranteed to give the same results (apart from order)? If the answer is that it depends on something, what does it depend on?
Use EXPLAIN to find the query plan for each query. Transcribe each plan into a relational algebra query evaluation tree, similar to that which your textbook does. Explain in words how these plans differ. This shouldn't be a long-winded explanation. Keep it short, but highlight what the key differences are between the plans. Explain which plan is likely to be better if the dataset were dramatically bigger. If that depends on what "bigger" means, explain what you're thinking.
Also explain (or speculate) why the plans are different for these queries. If the queries technically do something different, that could be one explanation. But if the queries are guaranteed to provide the same result, why might the optimizer come up with different plans?

The queries

The numbers on these queries are those from the previous assignment. Feel free to go back and look to remind yourself what each query was supposed to do.

Query 3

-- Version A --
SELECT E.cno, E.sectno, AVG(S.gpa)
FROM enroll E, student S
WHERE S.sid = E.sid AND E.dname = 'Computer Sciences'
GROUP BY E.cno, E.sectno;

-- Version B --
SELECT A.cno, A.sectno, AVG(A.gpa)
FROM   (SELECT E.sid, S.gpa, E.cno, E.sectno
        FROM enroll E, student S
        WHERE S.sid = E.sid AND E.dname = 'Computer Sciences') A
GROUP BY A.cno, A.sectno;

-- Version C --
SELECT section.cno AS Course, section.sectno AS Section, AVG(student.gpa) AS avgGPA
FROM section, enroll, student
WHERE enroll.cno=section.cno AND enroll.sid = student.sid AND 
      enroll.sectno = section.sectno AND section.dname='Computer Sciences'
GROUP BY section.cno, section.sectno;

Query 4

-- Version A --
SELECT temp.sectno, temp.cname
FROM   (SELECT E.cno, E.sectno, C.cname
        FROM enroll E, course C
        WHERE E.cno = C.cno AND E.dname = C.dname) temp
GROUP BY temp.cno, temp.sectno, temp.cname
HAVING COUNT(*) > 6;

-- Version B --
SELECT course.cname, thistable.sectno
FROM course, (SELECT enroll.cno, enroll.sectno, enroll.dname, COUNT (*) AS count
              FROM enroll
              GROUP BY enroll.cno, enroll.sectno, enroll.dname) AS thistable
WHERE course.cno=thistable.cno AND course.dname=thistable.dname
      AND thistable.count > 6;

Query 5

-- Version A --
SELECT S.sid,S.sname
FROM   student S, enroll E
WHERE  S.sid=E.sid
GROUP BY S.sid, S.sname
HAVING COUNT(*) >= ALL (SELECT COUNT(*)
                        FROM student S, enroll E
                        WHERE S.sid=E.sid
                        GROUP BY s.sid);

-- Version B --
SELECT  S.sid, S.sname
FROM    student S
WHERE   S.sid IN (SELECT   E.sid
                  FROM     enroll E
                  GROUP BY E.sid
                  HAVING   COUNT(*) = (SELECT  MAX(count)
                                       FROM    (SELECT   COUNT(*)
                                                FROM     enroll E
                                                GROUP BY E.sid) AS foo));

-- Version C --
SELECT temp.sid, S.sname
FROM (SELECT COUNT(*), E2.sid
      FROM enroll E2
      GROUP BY E2.sid) AS temp, student S
WHERE temp.count = (SELECT MAX(temp.count)
                    FROM (SELECT COUNT(*), E2.sid
                          FROM enroll E2
                          GROUP BY E2.sid) AS temp)
       AND temp.sid = S.sid;

Query 7

-- Version A --
SELECT  S.sname, M.dname
FROM    student S, major M
WHERE   S.sid = M.sid AND
        S.sid IN (SELECT  S.sid
                  FROM    student S, enroll E, course C
                  WHERE   S.sid = E.sid AND E.cno = C.cno AND E.dname = C.dname
                          AND SUBSTRING(C.cname from 1 for 16) = 'College Geometry');

-- Version B --
SELECT S.sname, M.dname
FROM   enroll E, course C, major M, student S
WHERE  C.cname LIKE 'College Geometry%' AND E.cno = C.cno
       AND M.sid = E.sid AND E.sid = S.sid;

-- Version C --
SELECT S.sname, M.dname
FROM   student S, major M
WHERE  S.sid = M.sid AND
       S.sid IN (SELECT E.sid
                 FROM enroll E
                 WHERE E.cno IN (SELECT C.cno
                                 FROM course C
                                 WHERE cname LIKE 'College Geometry%' ));

What to Turn In

Submit on paper the answers to the questions above for each set of queries.