Part 2: Query Optimization
In this part, you will implement a piece of a relational query optimizer: Plan space search.
Overview: Plan Space Search
You will now search the plan space of some cost estimates. For our database, this is similar to
System R: the set of all left-deep trees, avoiding Cartesian products where possible. Unlike
System R, we do not consider interesting orders, and further, we completely disallow Cartesian
products in all queries. To search the plan space, we will utilize the dynamic programming
algorithm used in the Selinger optimizer.
Before you begin, you should have a good idea of how the QueryPlan class is used (see the
section) and how query operators fit together. For example, to implement a simple
query with a single selection predicate:
Sk
eleton Code
/**1
* SELECT * FROM myTableName WHERE stringAttr = ‘CS 186’2
*/3
QueryOperator source = SequentialScanOperator(transaction, myTableName);4
QueryOperator select = SelectOperator(source, ‘stringAttr’, PredicateOperator5
6
int estimatedIOCost = select.estimateIOCost(); // estimate I/O cost7
Iterator
A tree of 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
CS186 Projects
Cookies
This site uses cookies to deliver its service and to analyse traffic. By browsing this site, you accept
our cookie policy.
Reject all
https://cs186.gitbook.io/project/assignments/proj3/skeleton-code
https://cs186.gitbook.io/project/
https://policies.gitbook.com/privacy/cookies