System Architecture and Query Processing

The database system processes SQL statements through a multi-stage pipeline. The query flow begins with the parser and binder, which transforms raw SQL text into an Abstract Syntax Tree (AST). This AST is then passed to the planner to generate a query plan, which is subsequently optimized. The final execution plan is a tree of nodes, where data flows from the leaves to the root.

You can inspect the transformation process using the EXPLAIN command. For instance, examining a simple selection query reveals the plan structure:

db-shell> EXPLAIN SELECT id, value FROM test_table;
=== OPTIMIZER ===
SeqScan { table=test_table } | (test_table.id:INTEGER, test_table.value:INTEGER)

The optimizer outputs a tree structure. For example, a query involving aggregation and filtering results in a tree where the root node depends on child nodes for data.

Execution Model

The system employs the Volcano iterator model for query execution. Each executor implements a Next() function. When invoked, the executor returns either a single tuple or a signal indicating that no more tuples are available. Executors form a tree structure; a parent executor calls Next() on its children to retrieve input tuples, processes them, and yields results to its own parent.

Task #1: Access Method Executors

Sequential Scan

The SeqScanExecutor iterates over a table and emits tuples one by one. It utilizes a TableIterator to traverse the table heap. Care must be taken with iterator incrementation; pre-increment operators should be used to avoid logic errors associated with post-increment behavior.

db-shell> CREATE TABLE items (key INTEGER, data VARCHAR(100));
db-shell> EXPLAIN (o, s) SELECT * FROM items;
=== OPTIMIZER ===
SeqScan { table=items } | (items.key:INTEGER, items.data:VARCHAR)

Insertion

The InsertExecutor adds tuples into a table. It consumes input from a single child executor (typically a ValuesExecutor) that provides the tuples to be inserted. The executor must modify both the table heap and all relevant indexes. The output schema for this executor consists of a single integer column representing the count of inserted rows.

Deletion

The DeleteExecutor removes tuples from a table. It fetches tuples from its child executor and marks the corresponding records as deleted in the table heap using MarkDelete(). Similar to insertion, all associated indexes must be updated to reflect the deletion. The executor outputs the number of rows deleted.

Index Scan

The IndexScanExecutor leverages an existing B+ Tree index to retrieve tuples. Instead of scanning the entire table, it iterates through the index structure to find matching Record IDs (RIDs) and then fetches the actual tuples from the table heap. This executor is automatically utilized when a query contains an ORDER BY clause matching the index key.

db-shell> CREATE INDEX idx_key ON items(key);
db-shell> EXPLAIN (o, s) SELECT * FROM items ORDER BY key;
=== OPTIMIZER ===
IndexScan { index_oid=0 } | (items.key:INTEGER, items.data:VARCHAR)

Task #2: Aggregation and Join Executors

Aggregation

The AggregationExecutor computes aggregate functions (e.g., MIN, MAX, COUNT, SUM) over groups of tuples. A hash table is used to store aggregation states. Since aggregation is a pipeline breaker, the executor typically builds the hash table during the initialization phase or the first call to Next().

The system provides a SimpleAggregationHashTable structure. Implementations must handle the combination of aggregate values, paying attention to the distinction between COUNT(column) and COUNT(*), as well as the correct handling of NULL values. On an empty table, COUNT(*) should return 0, while other aggregates typically return NULL.

Nested Loop Join

The NestedLoopJoinExecutor implements the standard nested loop join algorithm. For every tuple from the outer (left) table, it probes the inner (right) table. If the join predicate evaluates to true, the combined tuple is emitted. This executor must support both inner and left joins. The output schema concatenates columns from the left table followed by columns from the right table.

Nested Index Join

The NestedIndexJoinExecutor is an optimization applied when the inner side of a join has an index on the join key. For each tuple from the outer table, the executor extracts the join key, probes the index to find the matching RID, and retrieves the corresponding inner tuple. This avoids a full sequential scan of the inner table.

db-shell> EXPLAIN SELECT * FROM items LEFT JOIN other_items ON items.key = other_items.key;
=== OPTIMIZER ===
NestedIndexJoin { key_predicate=#0.0, index=idx_key }
  SeqScan { table=items }

Task #3: Sort, Limit, and Top-N Optimization

Sort and Limit

The SortExecutor collects all tuples from its child into memory and sorts them based on the specified ORDER BY keys. A custom comparator is required to handle ascending and descending sort orders. The LimitExecutor constrains the number of output tuples. If the child yields fewer tuples than the limit, all results are passed through.

Top-N Optimization

To optimize queries involving both ORDER BY and LIMIT, the optimizer should convert the plan to use a TopNExecutor. This executor utilizes a priority queue (heap) to maintain only the top N elements, avoiding the cost of sorting the entire dataset. The optimization rule, OptimizeSortLimitAsTopN, must be implemented to trigger this transformation.

db-shell> EXPLAIN SELECT * FROM items ORDER BY key DESC LIMIT 5;
=== OPTIMIZER ===
TopN { n=5, order_bys=[(Desc, #0.0)] }
  SeqScan { table=items }

System Catalog and Index Maintenance

Executors interact with the system catalog to retrieve metadata about tables and indexes. The Catalog class provides methods such as GetTable() and GetIndex(). When modifying data (Insert/Delete), the executor must iterate through all indexes defined on the target table and perform the corresponding index modifications.