QueryPlanclass is used (see the Skeleton Code section) and how query operators fit together. For example, to implement a simple query with a single selection predicate:
QueryOperatorobjects is formed when we have multiple tables joined together. The current implementation of
QueryPlan#execute, which is called by the user to run the query, is to join all tables in the order given by the user: if the user says
SELECT * FROM t1 JOIN t2 ON .. JOIN t3 ON .., then it scans
t1, then joins
t2, then joins
t3. This will perform poorly in many cases, so your task is to implement the dynamic programming algorithm to join the tables together in a better order.
QueryPlan#executemethod. To do so, you will also have to implement two helper methods:
QueryPlan#minCostSingleAccess(pass 1 of the dynamic programming algorithm) and
QueryPlan#minCostJoins(pass i > 1).
EXPLAINcommand which outputs the query plan for a given query. Let's test out our current query optimizer! Navigate to
CommandLineInterface.javaand run the code to start our CLI. This should open a new panel in IntelliJ at the bottom. Click on this panel. We've provided 3 demo tables (Students, Courses, Enrollments). Let's try running the following query:
exitto terminate the CLI. In the next few tasks, we'll implement an optimizer that will drastically improve the cost of our queries!
query/QueryPlan.javain this part.
QueryPlan#minCostSingleAccesshelper method, which takes a table and returns the optimal
QueryOperatorfor scanning the table.
SequentialScanOperator) and an index scan (
IndexScanOperator), which requires an index and filtering predicate on a column.
QueryPlan#minCostSingleAccess, you should be passing all of the tests in
TestSingleAccess. These tests do not involve any joins.
QueryOperator. You will need to implement the logic for pass i (i > 1) of the search algorithm in the
QueryPlan#joinmethod to identify potential joins.
t3have been joined together. Therefore, a database that supports all of SQL would have to push down predicates after each pass of the search algorithm.
QueryPlan#execute, which should utilize the two helper methods you have implemented to find the best query plan.
QueryPlanare kept in the variable
CommandLineInterface.javaand run the code to start our CLI. Let's try running the following two queries again: