common/iteratordirectory contains an interface called a
BacktrackingIterator. Iterators that implement this will be able to mark a point during iteration, and reset back to that mark. For example, here we have a backtracking iterator that just returns 1, 2, and 3, but can backtrack:
ArrayBacktrackingIteratorimplements this interface. It takes in an array and returns a backtracking iterator over the values in that array.
querydirectory contains what are called query operators. A single query to the database may be expressed as a composition of these operators. All operators extend the
QueryOperatorclass and implement the
Iterable<Record>interface. The scan operators fetch data from a single table. The remaining operators take one or more input operators, transform or combine the input (e.g. projecting away columns, sorting, joining), and return a collection of records.
JoinOperator.javais the base class of all the join operators. Reading this file and understanding the methods given to you can save you a lot of time on Part 1. It provides methods you may need to deal with tables and the current transaction. You should not be dealing directly with
TransactionContextobjects while implementing join algorithms in Part 1 (aside from passing them into methods that require them). Subclasses of JoinOperator are all located in
IndexScanOperator.java- Takes a table name, column name, a PredicateOperator (>, <, <=, >=, =) and a value. The column specified must have an index built on it for this operator to work. If so, the index scan will use take advantage of the index to yield records with columns satisfying the given predicate and value (e.g.
salaries.yearid >= 2000) efficiently
SelectOperator.java- Corresponds to the σ operator of relational algebra. This operator takes a column name, a PredicateOperator (>, <, <=, >=, =, !=) and a value. It will only yields records from the source operator for which the predicate is satisfied, for example (
yearid >= 2000)
ProjectOperator.java- Corresponds to the π operator of relational algebra. This operator takes a list of column names and filters out any columns that weren't listed. Can also compute aggregates, but that is out of scope for this project
MaterializeOperator.java- Materializes the source operator into a temporary table immediately, and then acts as a sequential scan over the temporary table. Mainly used in testing to control when IOs take place
GroupByOperator.java- Out of scope for this project. This operator accepts a column name and yields the records of the source operator but with the records grouped by their value and each separated by a marker record. For example, if the source operator had singleton records
[0,1,2,1,2,0,1]the group by operator might yield
Mis a marker record.
addmethod that can be used to insert a record into the partition/run. These classes will automatically buffer insertions and reads so that at most one page is needed in memory at a time.
QueryPlanclass represents a query. Users of the database create queries using the public methods (such as
select(), etc.) and then call
executeto generate a query plan for the query and get back an iterator over the resulting data set (which is not fully materialized: the iterator generates each tuple as requested). The current implementation of
executeNaive, which joins tables in the order given; your task in Part 2 will be to generate better query plans.
someTable.col1 < 186. A select predicate has four values that you can access:
columnNamespecify which column the predicate applies to
operatorrepresents the type of operator being used (for example
valueis a DataBox containing a constant value that the column should be evaluated against (in the above example,
186would be the value).
leftTable.leftColumn = rightTable.rightColumn. All joins in RookieDB are equijoins. JoinPredicates have five values:
joinTable: the name of one of the table's being joined in. Only used for toString()
leftTable: the name of the table on the left side of the equality
leftColumn: the name of the column on the left side of the equality
rightTable: the name of the table on the right side of the equality
rightColumn: The name of the column on the right side of the equality
Database.javasection of the main overview and browse through examples in
src/test/java/edu/berkeley/cs186/database/TestDatabase.javato familiarize yourself with how queries are written in our database.
execute()has been called on a
QueryPlanobject, you can print the final query plan: