QueryPlan
class 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:QueryOperator
objects 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#execute
method. 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).EXPLAIN
command which outputs the query plan for a given query. Let's test out our current query optimizer! Navigate to CommandLineInterface.java
and 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:exit
to terminate the CLI. In the next few tasks, we'll implement an optimizer that will drastically improve the cost of our queries!query/QueryPlan.java
in this part.QueryPlan#minCostSingleAccess
helper method, which takes a table and returns the optimal QueryOperator
for scanning the table.SequentialScanOperator
) and an index scan (IndexScanOperator
), which requires an index and filtering predicate on a column.QueryPlan#addEligibleSelections
).SelectOperator
s.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#minCostJoins
helper method.QueryPlan#join
method to identify potential joins.TestOptimizationJoins#testMinCostJoins
t1
, t2
, and t3
have 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.QueryPlan
class).QueryPlan
are kept in the variable tableNames
.database.query.*
.CommandLineInterface.java
and run the code to start our CLI. Let's try running the following two queries again:database.query.TestNestedLoopJoin
database.query.TestGraceHashJoin
database.query.TestSortOperator
database.query.TestSingleAccess
database.query.TestOptimizationJoins
database.query.TestBasicQuery