Projection

A projection node can represent various computations on its input. It will always have exactly one child node. In the BusTub shell, inspect the query plans for the following queries:

EXPLAIN SELECT 1 + 2;
EXPLAIN SELECT colA FROM __mock_table_1;
EXPLAIN SELECT colA + colB AS a, 1 + 2 AS b FROM __mock_table_1;

A projection plan node consists of one or more expressions representing a computation:

• ColumnValueExpression: directly places a column of the child executor to the output. The syntax #0.0 means the first column in the first child. You will see something like #0.0 = #1.0 in a plan for joins.
• ConstantExpression: represents a constant value (e.g., 1).
• ArithmeticExpression: a tree representing an arithmetic computation. For example, 1 + 2 would be represented by an ArithmeticExpression with two ConstantExpression (1 and 2) as children.

Filter

A filter plan node is used to filter the output of a child given a predicate. For example:

EXPLAIN SELECT * FROM __mock_table_1 WHERE colA > 1;

A filter node has exactly one child and contains a predicate.

Values

A values plan node is used to directly produce values:

EXPLAIN values (1, 2, 'a'), (3, 4, 'b');
CREATE TABLE table1(v1 INT, v2 INT, v3 VARCHAR(128));
EXPLAIN INSERT INTO table1 VALUES (1, 2, 'a'), (3, 4, 'b');

Values plan nodes are useful when inserting user-supplied values into a table.

SeqScan

The SeqScanPlanNode can be planned with a SELECT * FROM table statement.

bustub> CREATE TABLE t1(v1 INT, v2 VARCHAR(100));
Table created with id = 15
bustub> EXPLAIN (o,s) SELECT * FROM t1;
=== OPTIMIZER ===
SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

The SeqScanExecutor iterates over a table and returns its tuples one at a time.

Hint: Make sure that you understand the difference between the pre-increment and post-increment operators when using the TableIterator object. (Check here for a quick refresher.)

Hint: Do not emit tuples that are deleted in the TableHeap. Check the is_deleted_ field of the corresponding TupleMeta for each tuple.

Hint: The output of sequential scan is a copy of each matched tuple and its original record identifier (RID).

Note: BusTub does not support DROP TABLE or DROP INDEX. You can reset your database by restarting the shell.

Insert

The InsertPlanNode can be planned with an INSERT statement. Note that you will need to use a single quote to specify a VARCHAR value.

bustub> EXPLAIN (o,s) INSERT INTO t1 VALUES (1, 'a'), (2, 'b');
=== OPTIMIZER ===
Insert { table_oid=15 } | (__bustub_internal.insert_rows:INTEGER)
  Values { rows=2 } | (__values#0.0:INTEGER, __values#0.1:VARCHAR)

The InsertExecutor inserts tuples into a table and updates any affected indexes. It has exactly one child producing values to be inserted into the table. The planner will ensure that the values have the same schema as the table. The executor will produce a single tuple of integer type as the output, indicating how many rows have been inserted into the table. Remember to update indexes when inserting into the table, if there are indexes associated with it.

Hint: See the System Catalog section below for information about the system catalog. To initialize this executor, you will need to look up information about the table being inserted into.

Hint: See the Index Updates section below for further details about updating a table's indexes.

Hint: You will need to use the TableHeap class to perform table modifications.

Update

The UpdatePlanNode can be planned with an UPDATE statement. It has exactly one child with the records to be updated in the table.

bustub> explain (o,s) update test_1 set colB = 15445;
=== OPTIMIZER ===
Update { table_oid=20, target_exprs=[#0.0, 15445, #0.2, #0.3] } | (__bustub_internal.update_rows:INTEGER)
  SeqScan { table=test_1 } | (test_1.colA:INTEGER, test_1.colB:INTEGER, test_1.colC:INTEGER, test_1.colD:INTEGER)

The UpdateExecutor modifies existing tuples in a specified table. The executor will produce a single tuple of integer type as the output, indicating how many rows have been updated. Remember to update any indexes affected by the updates.

Hint: To implement an update, first delete the affected tuple and then insert a new tuple.

Delete

The DeletePlanNode can be planned with a DELETE statement. It has exactly one child with the records to be deleted from the table. Your delete executor should produce an integer output that represents the number of rows that it deleted from the table. It will also need to update any affected indexes.

bustub> EXPLAIN (o,s) DELETE FROM t1;
=== OPTIMIZER ===
Delete { table_oid=15 } | (__bustub_internal.delete_rows:INTEGER)
  Filter { predicate=true } | (t1.v1:INTEGER, t1.v2:VARCHAR)
    SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

bustub> EXPLAIN (o,s) DELETE FROM t1 where v1 = 1;
=== OPTIMIZER ===
Delete { table_oid=15 } | (__bustub_internal.delete_rows:INTEGER)
  Filter { predicate=#0.0=1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)
    SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

You may assume that the DeleteExecutor is always at the root of the query plan in which it appears. The DeleteExecutor should not modify its result set.

Hint: To delete a tuple, you need to get a RID from the child executor and update the is_deleted_ field of the corresponding TupleMeta for that tuple.

IndexScan

The IndexScanExecutor does point lookup and ordered scan using the b-plus tree index to retrieve tuples in the table. The executor should be able to support several point lookups on the same index.

You will need to implement the index scan by supporting the following two types of queries:

1. Point Lookup: SELECT FROM <table> WHERE <index column> = <val>. You will implement the optimizer rule to transform a SeqScan into an IndexScan in the next section.
2. Ordered Scan: SELECT FROM <table> ORDER BY <index column>. The optimizer rule to generate an IndexScan for queries with ORDER BY on an index column has been implemented for you. Your task is to handle ASC (or default) ordering only in IndexScan.

bustub> CREATE TABLE t1(v1 int, v2 int);
Table created with id = 22

bustub> CREATE INDEX t1v1 ON t1(v1);
Index created with id = 0

bustub> EXPLAIN (o,s) SELECT * FROM t1 WHERE v1 = 1;
=== OPTIMIZER ===
IndexScan { index_oid=0, filter=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER)

bustub> EXPLAIN (o,s) SELECT * FROM t1 ORDER BY v1;
=== OPTIMIZER ===
IndexScan { index_oid=0 } | (t1.v1:INTEGER, t1.v2:INTEGER)

The type of the index object in the plan will always be BPlusTreeIndexForTwoIntegerColumn in this project. You can safely cast the object to this type and store it in the executor wherever needed:

tree_ = dynamic_cast<BPlusTreeIndexForTwoIntegerColumn *>(index_info_->index_.get())

You can then do point lookup or ordered scan with the b-plus tree index and emit the satisfying tuple. In this semester, you only need to support the index on a single, unique integer column. Our test cases will not contain duplicate keys. Hence, this executor returns one tuple per point lookup if it exists.

You will need to finish the optimizer rule in the next section to transform a SeqScan into an IndexScan. It may make more sense to implement the optimizer rule before implementing IndexScan to understand the kind of queries IndexScanExecutor will need to support.

Hint: We will never insert duplicate rows into tables with indexes.

Hint: As above, do not emit tuples that are deleted.

Hint: Please use ScanKey for the point lookup, and use Index Iterator for the ordered scan.

Optimizing SeqScan to IndexScan

As we learned in lecture, when we are querying on the indexed column, using an IndexScan will significantly boost the lookup performance. To this end, we need to push down the filter into the scanner so that we know the key to lookup in the index. Then we can directly retrieve the value over the index, instead of doing a full table scan.

You would need to modify the optimizer to transform a SeqScanPlanNode into a IndexScanPlanNode when it is possible.

Consider the following example:

bustub> EXPLAIN (o) SELECT * FROM t1 WHERE v1 = 1;

Without applying the MergeFilterScan and the SeqScan as IndexScan optimizer rule, the plan may look like the following:

 Filter { predicate=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)
   SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)                              

After applying the MergeFilterScan and SeqScan as IndexScan optimizer rule, we can just do a quick index lookup instead of iterating the entire table. The resulting plan will look like the following:

 IndexScan { index_oid=0, filter=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)

Here's the brief steps to implement this optimizer rule:

1. Enable Predicate pushdown to SeqScan: We can implement a predicate filter in SeqScanExecutor so that later the index scan node will have the predicate. We've already enabled MergeFilterScan optimizer rule src/optimizer/merge_filter_scan.cpp in the starter optimizer rules for you.

2. Use Index: You can check the filtering columns from the predicate. If there happens to exist an index on this column, create an IndexScanPlanNode. Note that to get full score, you will need to support this optimizer rule in a few different situations: (1) when there's one equality test on the indexed column in predicate (i.e., WHERE v1 = 1) (2) when the indexed column ordering is flipped (i.e., WHERE 1 = v1) (3) when there are several point lookups on the same index (i.e., WHERE v1 = 1 or v1 = 4). Note that queries of the form SELECT * FROM t1 WHERE v1 = 1 AND v2 = 2 should still use a seq scan, thus you do not need to split the predicates.

Please check Optimizer Rule Implementation Guide section for details on implementing an optimizer rule.

Now that you have implemented all storage related executors. In the following tasks, you can create tables and insert some values by yourself to test your own executor implementation! At this point, you should also have passed SQLLogicTests #1 to #6.

Hint: You may find the utility BPlusTreeIndex::ScanKey function helpful.

Hint: Think about how to handle queries of the form WHERE v1 = 1 OR v1 = 1. It may help to view AggregateKey in /src/include/execution/plans/aggregation_plan.h.

Hint: Please only optimize SeqScan to IndexScan in the 2 scenarios mentioned above (i.e. point lookup and ordered scan).

Aggregation

The AggregationPlanNode is used to support queries like the following:

EXPLAIN SELECT colA, MIN(colB) FROM __mock_table_1 GROUP BY colA;
EXPLAIN SELECT COUNT(colA), min(colB) FROM __mock_table_1;
EXPLAIN SELECT colA, MIN(colB) FROM __mock_table_1 GROUP BY colA HAVING MAX(colB) > 10;
EXPLAIN SELECT DISTINCT colA, colB FROM __mock_table_1;

The aggregation executor computes an aggregation function for each group of input. It has exactly one child. The output schema consists of the group-by columns followed by the aggregation columns.

As discussed in class, a common strategy for implementing aggregation is to use a hash table, with the group-by columns as the key. In this project, you may assume that the aggregation hash table fits in memory. This means that you do not need to implement a multi-stage, partition-based strategy, and the hash table does not need to be backed by buffer pool pages.

We provide a SimpleAggregationHashTable data structure that exposes an in-memory hash table (std::unordered_map) but with an interface designed for computing aggregations. This class also exposes an SimpleAggregationHashTable::Iterator type that can be used to iterate through the hash table. You will need to complete the CombineAggregateValues function for this class.

The aggregation executor itself will not need to handle the HAVING predicate. The planner will plan aggregations with a HAVING clause as an AggregationPlanNode followed by a FilterPlanNode.

Hint: In the context of a query plan, aggregations are pipeline breakers. This may influence the way that you use the AggregationExecutor::Init() and AggregationExecutor::Next() functions in your implementation. Carefully decide whether the build phase of the aggregation should be performed in AggregationExecutor::Init() or AggregationExecutor::Next().

Hint: You must handle NULL values in the input of the aggregation functions (i.e., a tuple may have a NULL value for the attribute used in the aggregation function). See test cases for expected behavior. Group-by columns will never be NULL.

Hint: When performing aggregation on an empty table, CountStarAggregate should return zero and all other aggregate types should return integer_null. This is why GenerateInitialAggregateValue initializes most aggregate values as NULL.

NestedLoopJoin

The DBMS will use NestedLoopJoinPlanNode for all join operations, by default. Consider the following example queries:

EXPLAIN SELECT * FROM __mock_table_1, __mock_table_3 WHERE colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 INNER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 LEFT OUTER JOIN __mock_table_3 ON colA = colE;

You will need to implement an inner join and left join for the NestedLoopJoinExecutor using the simple nested loop join algorithm from class. The output schema of this operator is all columns from the left table followed by all columns from the right table. For each tuple in the outer table, consider each tuple in the inner table and emit an output tuple if the join predicate is satisfied.

Hint: You should use the predicate in the NestedLoopJoinPlanNode. See AbstractExpression::EvaluateJoin, which handles the left tuple and right tuple and their respective schemas. Note that this returns a Value, which could be false, true, or NULL. See FilterExecutor for how to apply predicates on tuples.

HashJoin

The DBMS can use HashJoinPlanNode if a query contains a join with a conjunction of several equi-conditions between two columns (equi-conditions are seperated by AND). Consider the following example queries:

EXPLAIN SELECT * FROM __mock_table_1, __mock_table_3 WHERE colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 INNER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 LEFT OUTER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colA = t2.colA AND t1.colB = t2.colC;
EXPLAIN SELECT * FROM test_1 t1 INNER JOIN test_2 t2 on t1.colA = t2.colA AND t2.colC = t1.colB;
EXPLAIN SELECT * FROM test_1 t1 LEFT OUTER JOIN test_2 t2 on t2.colA = t1.colA AND t2.colC = t1.colB;

You will need to implement the inner join and left join for HashJoinExecutor using the hash join algorithm from class. The output schema of this operator is all columns from the left table followed by all columns from the right table. As with aggregation, you may assume that the hash table used by the join fits entirely in memory.

Your implementation should correctly handle the case where multiple tuples have hash collisions (on either side of the join). You will want to make use of the join key accessors functions GetLeftJoinKey() and GetRightJoinKey() in the HashJoinPlanNode to construct the join keys for the left and right sides of the join, respectively.

Hint: You will need a way to hash a tuple with multiple attributes in order to construct a unique key. As a starting point, take a look at how the SimpleAggregationHashTable in the AggregationExecutor implements this functionality.

Hint: As with aggregation, the build side of a hash join is a pipeline breaker. You should again consider whether the build phase of the hash join should be performed in HashJoinExecutor::Init() or HashJoinExecutor::Next().

Optimizing NestedLoopJoin to HashJoin

Hash joins usually yield better performance than nested loop joins. You should modify the optimizer to transform a NestedLoopJoinPlanNode into a HashJoinPlanNode when it is possible to use a hash join. Specifically, the hash join algorithm can be used when a join predicate is a conjunction of several equi-conditions between two columns. For this project, you should be able to handle a varying number of equi-conditions connected by AND.

Consider the following example:

bustub> EXPLAIN (o) SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colA = t2.colA AND t1.colB = t2.colC;

Without applying the NLJAsHashJoin optimizer rule, the plan may look like:

 NestedLoopJoin { type=Inner, predicate=((#0.0=#1.0)and(#0.1=#1.2)) } 
   SeqScan { table=test_1 }                                           
   SeqScan { table=test_2 }

After applying the NLJAsHashJoin optimizer rule, the left and right join key expressions will be extracted from the single join predicate in the NestedLoopJoinPlanNode. The resulting plan will look like:

 HashJoin { type=Inner, left_key=[#0.0, #0.1], right_key=[#0.0, #0.2] } 
   SeqScan { table=test_1 }                                             
   SeqScan { table=test_2 } 

Please check the Optimizer Rule Implementation Guide section for details on implementing an optimizer rule. At this point, you should pass SQLLogicTests - #14 to #15.

Hint: Make sure to check which table the column belongs to for each side of the equi-condition. It is possible that the column from outer table is on the right side of the equi-condition. You may find ColumnValueExpression::GetTupleIdx helpful.

Hint: The order to apply optimizer rules matters. For example, you want to optimize NestedLoopJoin into HashJoin after filters and NestedLoopJoin have merged.

Hint When dealing with multiple equi-conditions, try to extract out the keys recursively, instead of matching the joining condition with multiple layers of if clauses.

External Merge Sort

Except in the case that the ORDER BY attributes matches the keys of an index, BusTub will use a SortPlanNode for all ORDER BY operators.

EXPLAIN SELECT * FROM __mock_table_1 ORDER BY colA ASC, colB DESC;

This plan node does not change schema (i.e., the output schema is the same as the input schema). You can extract sort keys from order_bys. If the query does not include a sort direction in the ORDER BY clause (i.e., ASC, DESC), then the sort mode will be default (which is ASC).

One important assumption about the external merge sort is that the entries in a table will NOT be able to fit in memory. Therefore, you need to follow what you learned in the lecture: store the intermediate sorting results in temporary pages and do merge sort recursively based on the sorted results of the previous round.

As you may be aware of, a specific page format will be needed for the intermediate sorting results. In this project, you will be the one who designs the page format. Take a look at external_merge_sort_executor.h and you will find SortPage, which is dedicated for storing the intermediate sorting results but contains minimal pre-defined members/methods. You should design the page layout and implement the read/write methods for the page.

You will then implement the merge sort algorithm. It is not hard to do an in-memory merge sort. But when it involves the disk, you should carefully think of how you manipulate the sorted tuples via the page interfaces and the buffer pool. It is worth noting that the page that's no longer in use (i.e. from the previous round of merge sort) should be deleted, or you will have a bunch of "zombie" pages that will never be referred to but still exist in the buffer pool.

To simplify your implementation of SortPage, we will only test on sorting fixed-length tuples in this semester. That is to say, we will not sort tuples containing VARCHAR attributes. Also, we will only test on two-way external merge sort this semester even though ExternalMergeSortExecutor is templated. Therefore, feel free to implement a two-way merge sort algorithm instead of a k-way one.

However, it's important that your are doing the merge sort externally (not storing all data purely in memory). You are allowed to use std::sort to sort tuples fitting within one sort page, but NOT on all tuples. Also, your SortPage layout should be compact, i.e. as little fragmentation as possible. You should also make sure that the pages are actually deleted after the merge sort is done.

Hint: For comparison of tuples based on the sort key, we provide a helper class TupleComparator in execution_common.h. We also provide a helper function GenerateSortKey, which you may find helpful when sorting the tuples.

Hint: To better understand what to do and where to start for SortPage, you can take a look at the layout of the index pages you worked on in project 2 (e.g. a char array can be used as the start of page data). You may find Schema::GetInlinedStorageSize helpful given the assumption that we only test on fixed-length data. Also, it would be helpful to think of how your executor will call the read/write methods.

Hint: You don't really need to manually manipulate the "write-to-disk" part when doing the external merge sort. The buffer pool manager will handle this for you. Remember what you implemented in P1: the page guard will automatically pin and unpin a page, as well as setting the evictability. Just make proper use of the page guard and you will not be worrying too much for page manipulation in this project.

Limit

The LimitPlanNode specifies the number of tuples that query will generate. Consider the following example:

EXPLAIN SELECT * FROM __mock_table_1 LIMIT 10;

The LimitExecutor constrains the number of output tuples from its child executor. If the number of tuples produced by its child executor is less than the limit specified in the plan node, this executor has no effect and yields all of the tuples that it receives.

This plan node does not change schema (i.e., the output schema is the same as the input schema). You do not need to support offsets.

Query 1: Too Many Joins!

Consider the following sample database:

CREATE TABLE t4(x int, y int);
CREATE TABLE t5(x int, y int);
CREATE TABLE t6(x int, y int);

The user is not from CMU and they are writing terrible SQL. They forgot how write queries with joins so they puts all predicates in the WHERE clause.

SELECT * FROM t4, t5, t6
  WHERE (t4.x = t5.x) AND (t5.y = t6.y) AND (t4.y >= 1000000)
    AND (t4.y < 1500000) AND (t6.x >= 100000) AND (t6.x < 150000);

Recommended Optimizations: Decompose the filter condition to extract hash join keys, and push down the remaining filter conditions to be below the hash join.

Query 2: The Mad Data Scientist

There is a data scientist invested all their money in NFTs. After realizing their terrible mistake, they go crazy and starts writing some weird SQL queries. Consider the following example:

SELECT v, d1, d2 FROM (
  SELECT v,
         MAX(v1) AS d1, MIN(v1), MAX(v2), MIN(v2),
         MAX(v1) + MIN(v1), MAX(v2) + MIN(v2),
         MAX(v1) + MAX(v1) + MAX(v2) AS d2
    FROM t7 LEFT JOIN (SELECT v4 FROM t8 WHERE 1 == 2) ON v < v4
    GROUP BY v
)

(This is not the same as the actual leaderboard query; refer to the test file.)

Recommended Optimizations:

• Column pruning – you only need to compute v, d1, d2 from the left table in aggregation. We've provided a skeleton file column_pruning.cpp.
• Common expression elimination, transform always false filter to dummy scan (values plan node of zero rows)
• Some more if you could think of :)

Hint: You do not need to implement a complete rule for optimizing these queries. (1) a complete predicate pushdown requires you to handle all plan nodes – limit, order by, etc. But to optimize for Q2, you only need to implement push down predicates over hash join / nested loop joins. (2) a complete join reordering requires you to handle predicates correctly (and maybe absorb filters in-between back to the join predicate), and you do not need to do that. Just make your optimizer work with those queries is enough.

Query 3: All that work, for nothing?

After all the hard work with Q1 and Q2, here's something short and sweet. Imagine you have the following 2 tables representing everyone alive in the 1950s, and everyone born in the 1600s. Someone with no concept of human lifespan (or a firm belief in vampires) tries to construct a query that outputs the intersection of the 2 tables. You know the result will be empty, but your join executors won't, what can you do to help speed up the process?

SELECT * FROM alive_in_1950s a INNER JOIN born_in_1600s b ON a.birthday = b.birthday

(This is not the same as the actual leaderboard query; refer to the test file.)

Recommended Optimizations: Bloom filter for the hash table used during the build phase of the hash join.