CS计算机代考程序代写 database algorithm Part 2: Query Optimization

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 iter = select.iterator(); // iterator over the results8

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