CS3223: Database Systems Implementation

Project Assignment 3: Sorting

In this assignment, you will extend SimpleDB to support the order by clause and the sorting operator. Fortunately, you do not need to implement the code for sort operator. The code for sorting can be found in SimpleDB’s materialize subdirectory. You should study the following programs in this subdirectory:

· SortPlan.java

· SortScan.java

· RecordComparator.java

· TempTable.java

You will also need to make changes to the parser.

1. Work with the current sort operator

· Examine the program BasicQueryPlanner.java in the subdirectory plan.

· Import SimpleDB.materialize.*.

· Look at the routine createPlan(). Add another plan node after the ProjectPlan node in Step 4 (this SortPlan node would be the top-most node in the query tree):

p = new SortPlan(tx, p, data.fields())

· Create/run a test program that prints out a table (e.g., run PlanTest1.java in SimpleDB/plan or any of the files you have created in studentdb database). You should find that the records are ordered in ascending order.

2. Implement the order by clause

While the code in (1) can sort a file, there are three limitations. First, it essentially sorts based on all the attributes of the records. But, we usually want to sort on a subset of attributes. Second, the default ordering is the ascending (non-decreasing) order. Again, we may want to sort in a descending (non-increasing) order. Third, because of the above, we are also unable to sort a subset of attributes in a mix of orders, i.e., we may want to sort on age in ascending order while salary in descending order.

This part of the assignment will add the order by clause. The SQL subset now should allow the order by clause to be specified together with a comma-separated list of attribute and ordering pairs. For example, SimpleDB should be able to handle queries like

select SId, Sname, GradYear from student order by GradYear asc, Sname desc

Note that the ascending order is usually set as the default, so there is no need to specify asc if an attribute is to be ordered in ascending order.

· Look at the parser code (simpledb/parse). Modify the SimpleDB lexical analyzer (Lexer.java) and query parser (Parser.java) to implement these syntax changes. See QueryData.java also.

· Examine the query planner code (simpledb/plan). Modify the SimpleDB query planner (BasicQueryPlanner.java*) to generate an appropriate sort operation for queries containing an order by clause. Note that the SortPlan node added in (1) should have been optional (i.e., if there is no order by clause, then the SortPlan node should not be added. You may need to also examine/revise SortPlan.java, SortScan.java and RecordComparator.java.

* Note that this description assumes that you are using the (QueryPlanner, UpdatePlanner) pair. If you are using the (HeuristicQueryPlanner, IndexUpdatePlanner) pair, then you should be modifying HeuristicQueryPlanner.java in simpledb/opt (rather than BasicQueryPlanner.java).

3. Run some test programs

· Run your test programs in the student database. [Note that you may need to rename your database (or delete the old one before you rerun).]

4. Submit a report

Submit a report that describes the changes made to support the order by clause/sorting of fields. It is sufficient to create a table as follows:

File to change	Changes
simpledb/parse/Lexer.java	Added keywords “order” and “by” to keywords (in routine initKeywords())
Simpledb/parse/Parser.java	….
….	….