Background
This project builds on top of the code and functionality that you should be familiar with from Project 1. In this project, you will be implementing several of the join algorithms covered in class as well as a costbased query optimizer. We have released the staff solutions for Project 1 to a private repository link can be found on Piazza, and you are free to integrate those into your codebase. Though if you feel confident about your own solutions to Project 1, you may stick with those as well. Regardless, a correct working implementation of Project 1 is necessary in order to complete this project.
This project uses the same functionoriented query interface we implemented in Project 1, but with a few differences. The original implementation was inefficient because at every stage of the query processing pipeline, we would fully materialize every record in memory. This means the query operators execute in sequential batches, and furthermore queries will fail if data does not fit in memory. To address this, we have implemented an Iterator interface directly into each query operator, and you’ll be adding some more iterators for the join operators in this project!
Additionally, the original query plan would always execute a naive plan without any optimizations built in. We’ve included a separate execution method that will leverage a query optimizer that you will be filling in to generate better plans according to the System R costbased approach we’ve covered in class.
Getting Started
As usual, you can get the assignment from the Github course repository assuming you’ve set things up as we asked you to in homework 0 by running gitpullcoursemaster. This will get you all of the starter code we’ve provided, this project spec, and all of the tests that we’ve written for you.
We’ve also generated all of the API documentation of the code as webpages viewable here
Setup
All of the Java, Maven, and IntelliJ setup from Project 1 is still applicable for this project. Assuming that you were able to complete Project 1, you should not need to do any additional setup for this project. Refer to the Project 1 spec for setup details.
Starter Code
Package Overview
There’s a bunch of code that we’ve provided for you, both from Project 1 and some new additions in this project. We strongly suggest that you spend some time looking through it before starting to write your own code. The Project 1 spec contains descriptions for each package of the codebase, but the relevant parts for this project are all in the query package. Briefly, it consists of a QueryPlan class that holds the query optimizer, and several classes that all inherit from QueryOperator with each class representing a different operator in the plan tree.
All of the starter code descriptions from Project 1 are still valid. We have modified some classes and added additional functionality, but for the most part the code is the same except where we have specifically noted differences here in this document.
Query Generation
The QueryPlan interface allows you to generate SQLlike queries without having to parse actual SQL queries. We use the same interface from Project 1 to create queries, but whereas before you would call the naive QueryPlan#execute method to execute your query, now there exists a QueryPlan#executeOptimal which will generate an optimal plan, and then execute your query.
If you would like to run queries on the database, you can create a new QueryPlan by calling Transaction#query and passing the name of the base table for the query. You can then call the QueryPlan#where, QueryPlan#join, etc. methods in order to generate as simple or as complex a query as you would like. Finally, call QueryPlan#executeOptimal to run the query optimizer and execute the query and get a response of the form Iterator[Record]. You can also use the Transaction#queryAs methods to alias tables.
As a quick example, a simple query might look something like this.
You can also examine the query plan tree generated by the query optimizer by printing the final operator of the query plan:
You can find more examples in the OptimalQueryPlanTest and OptimalQueryPlanJoinsTest files.
Your Assignment
Alright, now we can write some code! NOTE: Throughout this project, you’re more than welcome to add any and all helper methods you’d like to write. However, it is very important that you do not change any of the interfaces that we’ve given you.
It’s also a good idea to always check the course repo for updates on the project.
Part 1: Join Algorithms
The first part of the project involves completing the implementations of PNLJOperator, BNLJOperator, and GraceHashOperator, which correspond to page nested loop join, block nested loop join, and grace hash join, respectively. Simple nested loop join has already been implemented for you in SNLJOperator. It is recommended that you look through the code for SNLJOperator, and use this as an example of how to implement a join algorithm before starting the others.
As a brief overview of how the join algorithms in this project work, each join operator first reads in the records from the left input operator and the right input operator and stores those records in a left and right temporary table. The JoinOperator abstract class, which all the join algorithms extend, provides several methods for accessing record or page iterators from the left and right temporary tables along with other useful information. The SNLJIterator inside SNLJOperator reads records from the left and right operators in a nested loop fashion and joins the appropriate records.
Page nested loop join
For the first part of this project you’ll need to implement the PNLJIterator inside PNLJOperator. Similar to the SNLJIterator, this iterator should join records from the left and right source operators using a nested loop method. As discussed in class, the difference in this join algorithm compared to simple nested loop join is that you iterate over the right table once for every page in the left table instead of every record in the left table. Don’t forget that the first page of a page iterator may be a header page!
We strongly recommend you write helper methods that retrieve the next left record and the next right record when you need to get them. The class has a lot of member variables already given, which serve as a guide for what you might need. You may also add any other member variables as you see fit. The order in which records are yielded is part of the tests, so make sure you are following the algorithms from lecture correctly.
It would also be helpful to familiarize yourself with the implementation of SNLJIterator and TableIterator before starting to write any code for this section.
Block nested loop join
Once you have implemented page nested loop join, you should be able to extend this logic to implement block nested loop join. You’ll need to implement the BNLJIterator inside BNLJOperator specifically. The algorithm should iterate over the right table once for every block of B2 pages in the left table instead of every page in the left table. B represents the total number of memory pages available to the query, and is accessible from the numBuffers field.
Grace hash join
For the last chunk of this section you’ll need to implement grace hash join in the GraceHashIterator inside GraceHashOperator. For grace hash join, you can make the simplifying assumption that we don’t need to do recursive partitioning i.e. you will only partition the inputs once and not multiple times. On the first phase of the algorithm, each record is hashed into its corresponding partition by being added to a temporary table that represents that partition. For an example of this, you can look inside the GroupByOperator class. On the second phase, you can build an inmemory hash table using Java’s builtin HashMap class.
Testing
Once you’ve implemented all of these methods, you should be passing all of the tests in JoinOperatorTest. We strongly recommend you start writing tests once you’ve wrapped your head around the code to try to catch some of the edge cases that you might have missed. It’s generally a good idea to write your own tests as you go along due to the fact that the given tests don’t cover all edge cases.
Part 2: Query Optimization
The second part of the project is focused on the query optimizer. We have provided some structure to help you get started. The QueryPlan#executeOptimal method runs the query optimizer and has been implemented already. This method calls other methods which you’ll need to implement in order to make sure the optimizer works correctly.
As an overview of what this method does, it first searches for the lowest cost ways to access each single table in the query. Then using the dynamic programming search algorithm covered in lecture, it will try to compute a join between a set of tables and a new table if there exists a join condition between them. The lowest cost join of all the tables is found, and then a group by and select operator is applied on top if those are specified in the query. The method returns an iterator over the final operator created. For an example of the naive query plan generation, look at the code inside QueryPlan#execute(). Note that the query optimizer code will look quite different from the naive code, but the naive code still serves as a good example of how to compose a query plan tree.
Cost estimation
The first part of building the query optimizer is ensuring that each query operator has the appropriate IO cost estimates. In order to estimate IO costs for each query operator, you will need the table statistics for any input operators. This information is accessible from the QueryOperator#getStats method. The TableStats object returned represents estimated statistics of the operator’s output, including information such as number of tuples and number of pages in the output among others. These statistics are generated whenever a QueryOperator is constructed.
All of the logic for estimating statistics has been fully implemented except for the calculation of the reduction factor of a WHERE predicate. You must implement the IntHistogram#computeReductionFactor method which will return a reduction factor based on the type of predicate given. The reduction factor calculations should be the same as those that were taught in class.
Each type of QueryOperator has a different estimateIOCost method which handles IO cost estimation. You will be implementing this method in a few of the operators. This method should estimate the IO cost of executing a query plan rooted at that query operator. It is executed whenever a QueryOperator is constructed, and afterwards the cost of an operator can be accessed from the QueryOperator#getIOCost method.
Several operators already have their estimateIOCost methods implemented. In this project, you are only responsible for implementing this method in IndexScanOperator, SNLJOperator, PNLJOperator, BNLJOperator, and GraceHashOperator. For the index scan cost, assume an unclustered index is used. The methods in Transaction and TableStats#getReductionFactor will be useful for implementing the index scan cost. For the grace hash join cost, assume there is only one pass of partitioning.
After implementing all the methods up to this point, you should now have everything you need to start building the search algorithm.
Single table access selection Pass 1
The first part of the search algorithm involves finding the lowest cost plans for accessing each single table in the query. You will be implementing this functionality in QueryPlan#minCostSingleAccess. This method takes in a single table name and should first calculate the estimated IO cost of performing a sequential scan. Then if there are any eligible indices that can be used to scan the table, it should calculate the estimated IO cost of performing such an index scan. The QueryPlan#getEligibleIndexColumns method can be used to determine whether there are any existing indices that can be used for this query. Out of all of these operators, keep track of the lowest cost operator.
Then as part of a heuristicbased optimization we covered in class, you should push down any selections that correspond to the table. You should be implementing the push down select functionality in QueryPlan#pushDownWheres which will be called by the QueryPlan#minCostSingleAccess method.
The end result of this method should be a query operator that starts with either a SequentialScanOperator or IndexScanOperator followed by zero or more WhereOperator’s.
After implementing all the methods up to this point, you should be passing all of the OptimalQueryPlan tests that do not involve any joins.
Join selection Pass
The next part of the search algorithm involves finding the lowest cost join between each set of tables in the previous pass and a separate single table. You will be implementing this functionality in QueryPlan#minCostJoins. Remember to only consider leftdeep plans and to avoid creating any Cartesian products. Use the list of explicit join conditions added through the QueryPlan#join method to identify potential joins. Once you’ve identified a potential join between a left set of tables and a right table, you should be considering each type of join implementation in QueryPlan#minCostJoinType which will be called by the QueryPlan#minCostJoins method.
The end result of this method should be a mapping from a set of tables to a join query operator that corresponds to the lowest cost join estimated.
Testing
If you’ve completed all the sections up to this point, you should now be passing all of the tests that we’ve given you. Again, we strongly encourage you to write tests as you go to try to catch any relevant bugs in your implementation.
Part 3: Testing
We can’t emphasize enough how important it is to test your code! Like we said earlier, writing valid tests that test actual code i.e., don’t write assertEquals(true,true);, or we’ll be mad at you is worth 10% of your project grade. CS 186 is a design course, and validating the reasonability and the functionality of the code you’ve designed and implemented is very important. We suggest you try to find the trickiest edge cases you can and expose them with your tests.
Testing that your code does exactly what you expect in the simplest case is good for sanity’s sake, but it’s often not going to be where the bugs are.
To encourage you to try to find interesting edge cases, we’re going to give you some extra credit. If you find edge cases that most other students didn’t find, you can get up to 5 points of extra credit. Keep in mind that if some other people find the same edge cases as you, that doesn’t mean you won’t get extra credit so don’t treat this as a competition!
Part 4: Feedback
We’ve been working really hard to give you guys the best experience possible with these new projects. We’d love to improve on them and make sure we’re giving reasonable assignments that are helping you learn. In that vein, please fill out this Google Form to help us understand how we’re doing!