common/iterator
directory 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:ArrayBacktrackingIterator
implements this interface. It takes in an array and returns a backtracking iterator over the values in that array.query
directory 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 QueryOperator
class 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.java
is 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 Table
objects nor TransactionContext
objects while implementing join algorithms in Part 1 (aside from passing them into methods that require them). Subclasses of JoinOperator are all located in query/join
.SequentialScanOperator.java
- Takes a table name provides an iterator over all the records of that tableIndexScanOperator.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
) efficientlySelectOperator.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 projectSortOperator.java
- Yields records from the source operator in sorted order. You'll be implementing this in Part 1MaterializeOperator.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 placeGroupByOperator.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 [0,0,M,1,1,1,M,2,2]
where M
is a marker record.add
method 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.QueryPlan
class represents a query. Users of the database create queries using the public methods (such as join()
, select()
, etc.) and then call execute
to 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 execute
simply calls 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:tableName
and columnName
specify which column the predicate applies tooperator
represents the type of operator being used (for example <
, <=
, >
, etc...)value
is a DataBox containing a constant value that the column should be evaluated against (in the above example, 186
would 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 equalityleftColumn
: the name of the column on the left side of the equalityrightTable
: the name of the table on the right side of the equalityrightColumn
: The name of the column on the right side of the equalityDatabase.java
section of the main overview and browse through examples in src/test/java/edu/berkeley/cs186/database/TestDatabase.java
to familiarize yourself with how queries are written in our database.execute()
has been called on a QueryPlan
object, you can print the final query plan: