### Ant Build Targets Quick Reference for SimpleDB

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This reference provides a summary of common Ant commands and their descriptions relevant to the SimpleDB project. It covers targets for building, packaging, and running various types of tests.

```APIDOC
ant:
  Description: Build the default target (for simpledb, this is dist).
ant -projecthelp:
  Description: List all the targets in build.xml with descriptions.
ant dist:
  Description: Compile the code in src and package it in dist/simpledb.jar.
ant test:
  Description: Compile and run all the unit tests.
ant runtest -Dtest=testname:
  Description: Run the unit test named testname.
ant systemtest:
  Description: Compile and run all the system tests.
ant runsystest -Dtest=testname:
  Description: Compile and run the system test named testname.
```

--------------------------------

### Create Submission Zip File for Gradescope

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This command demonstrates how to package your assignment files into a `.zip` archive for submission to Gradescope. It recursively includes the `src/` directory, which contains your source code, and the `lab1-writeup.txt` file, which should contain your assignment write-up.

```bash
$ zip -r submission.zip src/ lab1-writeup.txt
```

--------------------------------

### Generate IDE Project Files with Ant

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

To prepare the codebase for use with IDEs like Eclipse or IntelliJ, run this Ant command. It generates the necessary project files, streamlining the import process into your chosen IDE.

```Ant
ant eclipse
```

--------------------------------

### Compile and Run SimpleDB Test Program

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

These shell commands demonstrate how to compile the `test.java` program using `ant` and then execute the compiled Java application. The `java -classpath` command ensures that the `simpledb.jar` library is included in the classpath for the program to run correctly.

```CLI
ant
java -classpath dist/simpledb.jar simpledb.test
```

--------------------------------

### SimpleDB Catalog File Definition Example

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

An example `catalog.txt` file defining the schema for a SimpleDB table named 'data'. It specifies two integer fields, 'f1' and 'f2', mapping to the converted data.

```Text
data (f1 int, f2 int)
```

--------------------------------

### Example SimpleDB Raw Data File

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

A sample `data.txt` file containing comma-separated integer values. Each line represents a record, and the values are fields, ready for conversion into a SimpleDB table.

```Text
1,10
2,20
3,30
4,40
5,50
5,50
```

--------------------------------

### View SimpleDB Table Contents

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This command prints the contents of a SimpleDB table (.dat file) to the console. The table must have been previously created using the 'convert' command. It requires the table filename and the number of columns.

```Shell
$ java -jar dist/simpledb.jar print file.dat N
```

--------------------------------

### Run SimpleDB Unit Tests with Ant

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This snippet provides commands to execute unit tests for the SimpleDB project using Ant. It includes options to run all unit tests or target a specific test class, which is useful for focused development and debugging.

```Bash
$ cd [project-directory]
$ # run all unit tests
$ ant test
$ # run a specific unit test
$ ant runtest -Dtest=TupleTest
```

--------------------------------

### Run SimpleDB End-to-End System Tests with Ant

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This snippet demonstrates how to run the comprehensive end-to-end system tests for SimpleDB using Ant. It includes commands to execute all system tests or target a specific test, which is crucial for verifying the overall correctness of the project and is used for grading.

```Bash
$ ant systemtest
$ # To run a specific system test:
$ ant runsystest -Dtest=testname
```

--------------------------------

### Push Git Changes After Initial Setup

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

After the initial push with upstream tracking configured, this command allows users to push their local changes to the personal 'origin' remote without needing to specify the remote name or branch. It's the standard command for subsequent pushes.

```bash
$ git push
```

--------------------------------

### Implement HeapFile Methods for Disk I/O and Tuple Iteration

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This exercise requires implementing methods within `src/java/simpledb/storage/HeapFile.java`. Key tasks include reading pages directly from disk using random access (without `BufferPool` calls for disk reads), and creating an iterator that traverses all tuples across pages, utilizing `BufferPool.getPage()` for page access to support future concurrency control.

```APIDOC
Class: simpledb.storage.HeapFile

Methods to Implement:
  readPage(pid: PageId) -> Page
    Description: Reads a specific page from disk.
    Requirements:
      - Calculate correct offset in the file.
      - Use random access to read and write pages at arbitrary offsets.
      - DO NOT call BufferPool methods when reading a page from disk.

  iterator() -> DbFileIterator
    Description: Returns an iterator that iterates through all tuples in the HeapFile.
    Requirements:
      - Access pages using BufferPool.getPage() method.
      - DO NOT load the entire table into memory on open().
```

--------------------------------

### Implement Catalog Management Methods (Java)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Implement the skeleton methods in the `Catalog` class to manage database tables and their schemas. This involves supporting the addition of new tables and retrieving table information, ensuring the code passes `CatalogTest` unit tests.

```APIDOC
Class: simpledb.common.Catalog
  Purpose: Manages metadata about tables in the database, including their schemas and file locations.
  Methods to implement:
    - addTable(file: DbFile, name: String, pkeyField: String)
    - getTableId(name: String) -> int
    - getTupleDesc(tableid: int) -> TupleDesc
    - getDbFile(tableid: int) -> DbFile
    - getPrimaryKey(tableid: int) -> String
    - tableIterator() -> Iterator<CatalogItem>
    - clear()
```

--------------------------------

### Execute Simple Selection Query in SimpleDB (Java)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This Java code implements a basic `SELECT * FROM some_data_file` query in SimpleDB. It sets up a 3-column integer table schema, creates a `HeapFile` from `some_data_file.dat`, registers it with the catalog, and then uses a `SeqScan` to iterate through and print all tuples from the table.

```Java
package simpledb;
import java.io.*;

public class test {

    public static void main(String[] argv) {

        // construct a 3-column table schema
        Type types[] = new Type[]{ Type.INT_TYPE, Type.INT_TYPE, Type.INT_TYPE };
        String names[] = new String[]{ "field0", "field1", "field2" };
        TupleDesc descriptor = new TupleDesc(types, names);

        // create the table, associate it with some_data_file.dat
        // and tell the catalog about the schema of this table.
        HeapFile table1 = new HeapFile(new File("some_data_file.dat"), descriptor);
        Database.getCatalog().addTable(table1, "test");

        // construct the query: we use a simple SeqScan, which spoonfeeds
        // tuples via its iterator.
        TransactionId tid = new TransactionId();
        SeqScan f = new SeqScan(tid, table1.getId());

        try {
            // and run it
            f.open();
            while (f.hasNext()) {
                Tuple tup = f.next();
                System.out.println(tup);
            }
            f.close();
            Database.getBufferPool().transactionComplete(tid);
        } catch (Exception e) {
            System.out.println ("Exception : " + e);
        }
    }

}
```

--------------------------------

### Implement BufferPool getPage Method (Java)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Implement the `getPage()` method within the `BufferPool` class. This method is responsible for retrieving pages from the buffer pool, potentially throwing a `DbException` if the pool is full and no eviction policy is implemented yet. It should utilize `DbFile.readPage` for disk access. The constructor and a testing-specific `flushAllPages` method also need implementation.

```APIDOC
Class: simpledb.storage.BufferPool
  Purpose: Caches database pages in memory, managing their lifecycle and access.
  Methods to implement:
    - Constructor: BufferPool(numPages: int)
    - getPage(pid: PageId, perm: Permissions) -> Page
    - flushAllPages() (for testing purposes)
```

--------------------------------

### Java Method Stub for Tuple Deletion

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Shows a Java method stub for 'deleteTuple' within a class, demonstrating a common pattern where methods are provided but marked as not necessary for the current lab, indicating future implementation.

```Java
public boolean deleteTuple(Tuple t)throws DbException{
        // some code goes here
        // not necessary for lab1
        return false;
        }
```

--------------------------------

### SimpleDB Parser Initialization Output

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

The console output observed after successfully starting the SimpleDB query parser. It confirms the addition of the 'data' table with its schema and presents the interactive prompt.

```Console
Added table : data with schema INT(f1), INT(f2), 
SimpleDB> 
```

--------------------------------

### Java Class Declaration for DbIterator

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Illustrates a Java class declaration for 'Insert' implementing 'DbIterator', indicating that this specific class is not required for Lab 1 implementation.

```Java
// Not necessary for lab1.
public class Insert implements DbIterator {
```

--------------------------------

### Convert Text File to SimpleDB Binary Format

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This command converts a plain text data file into a binary format (`.dat`) that SimpleDB can query. The argument '3' specifies that the input file has three columns, which is crucial for correct parsing by SimpleDB.

```CLI
java -jar dist/simpledb.jar convert some_data_file.txt 3
```

--------------------------------

### Update Local Repository with Git Pull

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This command fetches and merges changes from the `upstream` remote's `master` branch into the current local branch. It's the simplest way to get newly released lab content or solutions, ensuring the local repository is synchronized with the central source.

```bash
$ git pull upstream master
```

--------------------------------

### Implement TupleDesc and Tuple Core Methods (Java)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Implement the fundamental skeleton methods within the `TupleDesc` and `Tuple` classes. This involves defining how tuples are structured and how individual fields are handled, ensuring the code passes `TupleTest` and `TupleDescTest` unit tests.

```APIDOC
Class: simpledb.storage.TupleDesc
  Purpose: Describes the schema of a tuple, including field types and names.
  Methods to implement:
    - Constructor: TupleDesc(types: Type[], fieldNames: String[])
    - getFieldType(i: int) -> Type
    - getFieldName(i: int) -> String
    - numFields() -> int
    - iterator() -> Iterator<TDItem>
    - equals(o: Object) -> boolean
    - hashCode() -> int
    - toString() -> String

Class: simpledb.storage.Tuple
  Purpose: Represents a single row or record in a table.
  Methods to implement:
    - Constructor: Tuple(td: TupleDesc)
    - getTupleDesc() -> TupleDesc
    - setTupleDesc(td: TupleDesc)
    - getField(i: int) -> Field
    - setField(i: int, f: Field)
    - getRecordId() -> RecordId
    - setRecordId(rid: RecordId)
    - modifyRecordId(rid: RecordId)
    - iterator() -> Iterator<Field>
```

--------------------------------

### Calculate HeapPage Header Bytes

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Formula to determine the number of bytes required for the header of a HeapPage. The header contains a bitmap indicating the status of tuple slots and its size depends on the total number of tuples that can fit on a page.

```APIDOC
headerBytes = ceiling(tupsPerPage/8)
```

--------------------------------

### Calculate Tuples Per Page in HeapFile

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

Formula to determine the maximum number of tuples that can fit into a single HeapFile page, based on page size and tuple size, accounting for header bits. This calculation is crucial for understanding page capacity and layout.

```APIDOC
_tuples per page_ = floor((_page size_ * 8) / (_tuple size_ * 8 + 1))
```

--------------------------------

### Implement SeqScan Operator for Sequential Table Scanning

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This exercise focuses on implementing the `SeqScan` operator in `src/java/simpledb/execution/SeqScan.java`. The operator must sequentially scan all tuples from the table identified by `tableid` provided in its constructor, accessing tuples via the `DbFile.iterator()` method.

```APIDOC
Class: simpledb.execution.SeqScan implements DbIterator

Methods to Implement:
  SeqScan(tid: TransactionId, tableid: int)
    Description: Constructor for the sequential scan operator.
    Parameters:
      - tid: The transaction ID.
      - tableid: The ID of the table to scan.

  getNext() -> Tuple
    Description: Retrieves the next tuple from the scan.
    Requirements:
      - Sequentially scan all tuples from the pages of the table specified by `tableid`.
      - Access tuples through the `DbFile.iterator()` method.
```

--------------------------------

### Convert Text File to SimpleDB HeapFile Format

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab1.md

This command converts a plain text file into SimpleDB's HeapFile format (.dat). The input text file must be a comma-separated values (CSV) file where each value is a non-negative integer and each line represents a row. The command requires the input filename and the number of columns.

```Shell
$ java -jar dist/simpledb.jar convert file.txt N
```

```Text
int1,int2,...,intN
int1,int2,...,intN
int1,int2,...,intN
int1,int2,...,intN
```

--------------------------------

### Implement SimpleDB Relational Operators: Filter and Join

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This section guides the implementation of the `Filter` and `Join` relational algebra operators in SimpleDB. The `Filter` operator selects tuples based on a `Predicate`, while the `Join` operator combines tuples from two children using a `JoinPredicate`. A simple nested loops join is sufficient for the `Join` operator. Implement the skeleton methods in the specified Java files.

```APIDOC
Filter Class:
  Purpose: Filters tuples based on a predicate.
  Constructor:
    Filter(predicate: Predicate, child: OpIterator)
      predicate: The predicate to apply for filtering.
      child: The OpIterator providing input tuples.

Join Class:
  Purpose: Joins tuples from two children based on a join predicate.
  Constructor:
    Join(joinPredicate: JoinPredicate, child1: OpIterator, child2: OpIterator)
      joinPredicate: The predicate to apply for joining.
      child1: The first OpIterator providing input tuples.
      child2: The second OpIterator providing input tuples.

Predicate Class:
  Purpose: Defines a condition for filtering tuples.
  Methods:
    eval(tuple: Tuple): boolean
      tuple: The tuple to evaluate.
      Returns: true if the tuple satisfies the predicate, false otherwise.

JoinPredicate Class:
  Purpose: Defines a condition for joining tuples.
  Methods:
    eval(tuple1: Tuple, tuple2: Tuple): boolean
      tuple1: The first tuple to evaluate.
      tuple2: The second tuple to evaluate.
      Returns: true if the tuples satisfy the join predicate, false otherwise.
```

--------------------------------

### Verify Git Remote Configurations

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This command displays the current remote repositories configured for the local Git repository. It's used to verify the fetch and push URLs for each remote, helping to confirm that remotes like 'origin' and 'upstream' are correctly set up.

```bash
$ git remote -v
```

--------------------------------

### Packaging Project Files for Gradescope Submission

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab5.md

This command demonstrates how to create a `.zip` archive containing the source code directory (`src/`) and the lab write-up file (`lab5-writeup.txt`) for submission to Gradescope. The `-r` flag ensures that directories are included recursively, and the output is a single `submission.zip` file.

```bash
$ zip -r submission.zip src/ lab5-writeup.txt
```

--------------------------------

### Perform Initial Git Push to Personal Origin

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This command performs the first push of the local 'master' branch to the newly configured personal 'origin' remote. The '-u' flag sets up the upstream tracking, so subsequent pushes can be done without specifying the remote and branch.

```bash
$ git push -u origin master
```

--------------------------------

### Clone Lab Repository and Pull Updates

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This snippet shows how to initially clone the MIT DB Class lab repository from GitHub. It also includes the command to pull the latest updates or patches released by the instructors, ensuring the local repository is up-to-date with course materials.

```bash
$ git clone https://github.com/MIT-DB-Class/simple-db-hw-2021.git
$ git pull
```

--------------------------------

### Initialize Lab 5 Branch and Pull Updates

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab5.md

Instructions to set up the lab4 branch and pull the latest files from the master GitHub repository for Lab 5. This ensures all necessary source and test files are available, building upon the previous lab's work.

```Shell
$ cd simple-db-hw
$ git pull upstream master
```

--------------------------------

### Add Personal Git Repository as Origin Remote

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This snippet demonstrates how to add a new remote named 'origin' that points to the user's personal GitHub repository. This allows users to push their changes and maintain version control in their private space. It also includes an alternative command to fix potential errors if 'origin' already exists.

```bash
$ git remote add origin https://github.com/[your-repo]
# If 'remote origin already exists' error occurs, use:
$ git remote set-url origin https://github.com/[your-repo]
```

--------------------------------

### Package SimpleDB Assignment for Gradescope Submission

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

This bash command creates a '.zip' file containing the 'src/' directory and 'lab3-writeup.txt' for submission to Gradescope. It is the recommended method for submitting assignments on Linux/MacOS.

```bash
$ zip -r submission.zip src/ lab3-writeup.txt
```

--------------------------------

### Run LogTest System Test and Expected Output

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This snippet shows how to execute the `LogTest` system test using Ant and the expected output. It demonstrates that after initial modifications, some sub-tests (like `TestAbort`) are expected to fail, indicating further implementation is required.

```Bash
% ant runsystest -Dtest=LogTest
    ...
    [junit] Running simpledb.systemtest.LogTest
    [junit] Testsuite: simpledb.systemtest.LogTest
    [junit] Tests run: 10, Failures: 0, Errors: 7, Time elapsed: 0.42 sec
    [junit] Tests run: 10, Failures: 0, Errors: 7, Time elapsed: 0.42 sec
    [junit] 
    [junit] Testcase: PatchTest took 0.057 sec
    [junit] Testcase: TestFlushAll took 0.022 sec
    [junit] Testcase: TestCommitCrash took 0.018 sec
    [junit] Testcase: TestAbort took 0.03 sec
    [junit]     Caused an ERROR
    [junit] LogTest: tuple present but shouldn't be
    ...
```

--------------------------------

### Creating Submission Zip File for Gradescope

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab4.md

This command demonstrates how to create a `.zip` file containing the source code directory (`src/`) and the lab write-up (`lab4-writeup.txt`) for submission to Gradescope. It uses the `zip` utility with the `-r` option for recursive archiving, typically run on Linux/MacOS systems.

```bash
$ zip -r submission.zip src/ lab4-writeup.txt
```

--------------------------------

### Synchronize Local Master Branch with Remote Origin using Git Push

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This command uploads all local commits from the `master` branch to the `origin` remote repository, typically GitHub. It's essential for saving local work and making it accessible remotely, ensuring that the remote repository reflects the latest local changes.

```bash
$ git push origin master
```

--------------------------------

### Create Submission Zip Archive

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This command creates a zip archive named `submission.zip` containing the `src/` directory and the `lab6-writeup.txt` file. This archive format is required for submitting programming assignments to Gradescope.

```bash
zip -r submission.zip src/ lab6-writeup.txt
```

--------------------------------

### Clean and Build Simple DB Project with Ant

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This command sequence performs a clean build of the simple-db-hw project using Apache Ant. It first cleans previous build artifacts and then recompiles the entire project, ensuring all changes are incorporated.

```Bash
ant clean; ant
```

--------------------------------

### Implement BufferPool Page Eviction Policy in SimpleDB Java

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This exercise focuses on implementing a page eviction policy for the `BufferPool` to enforce the `numPages` limit. When the buffer pool exceeds its capacity, one page should be evicted before the next is loaded. The `flushPage()` method should write dirty pages to disk and mark them clean, while `evictPage()` should remove pages and flush dirty ones. `discardPage()` is also required for future labs.

```Java
src/java/simpledb/storage/BufferPool.java
src/java/simpledb/storage/HeapFile.java (for writePage if not implemented)
```

--------------------------------

### Exercise 4: Implement Join Ordering in Java

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Implement the `orderJoins` method in `JoinOptimizer.java`. This method should determine and return a new `List` of `LogicalJoinNode` objects specifying the optimal join order for the query's `joins` member. The returned list represents a left-deep plan, where adjacent joins must share at least one field. It utilizes `TableStats` for table statistics and `filterSelectivities` for predicate selectivities, and can output an explanation if the `explain` flag is true.

```APIDOC
orderJoins(
  stats: Map<String, TableStats>,
  filterSelectivities: Map<String, Double>,
  explain: boolean
): List<LogicalJoinNode>
```

--------------------------------

### Fetch and Merge Upstream Changes Explicitly with Git

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

These two commands provide a more controlled way to update a local repository. `git fetch upstream` downloads all new branches and commits from the `upstream` remote without modifying the local working directory, while `git merge upstream/master` then integrates those fetched changes into the current branch. This allows for inspection before merging.

```bash
$ git fetch upstream
$ git merge upstream/master
```

--------------------------------

### SimpleDB Query Optimizer Implementation Requirements

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Detailed requirements for implementing the core components of the SimpleDB query optimizer, including methods within TableStats for selectivity and cost estimation, and methods within JoinOptimizer for join cost, selectivity, and optimal ordering.

```APIDOC
TableStats Class:
  - Purpose: Estimate selectivities of filters and cost of scans.
  - Implementation Details:
    - Use histograms (skeleton provided for IntHistogram class) or other forms of statistics.

JoinOptimizer Class:
  - Purpose: Estimate cost and selectivities of joins, and order joins optimally.
  - Methods to Implement:
    - Methods for estimating cost of joins.
    - Methods for estimating selectivities of joins.
    - orderJoins method:
      - Purpose: Produce an optimal ordering for a series of joins.
      - Algorithm: Likely using the Selinger algorithm.
      - Dependencies: Statistics computed in TableStats and other JoinOptimizer methods.
```

--------------------------------

### Invoke SimpleDB Query Parser with Catalog

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

Command to launch the interactive SimpleDB query parser, loading the table definitions from `catalog.txt`. This prepares the database for SQL query execution.

```Java
java -jar dist/simpledb.jar parser catalog.txt
```

--------------------------------

### Add Log Write and Force to BufferPool.flushPage()

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This Java code snippet is inserted into `BufferPool.flushPage()` to ensure that an update record, including before and after images, is written to the log file before the page is flushed to disk. It also forces the log to disk to guarantee durability.

```Java
// append an update record to the log, with 
// a before-image and after-image.
TransactionId dirtier = p.isDirty();
if (dirtier != null){
  Database.getLogFile().logWrite(dirtier, p.getBeforeImage(), p);
  Database.getLogFile().force();
}
```

--------------------------------

### Java Helper Method: computeCostAndCardOfSubplan

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

This private helper method computes the best way to join a specific `joinToRemove` node to the remaining `joinSet`. It returns a `CostCard` object containing the cost, cardinality, and best join ordering, or `null` if no valid plan can be found or if the cost exceeds `bestCostSoFar`. It leverages a `PlanCache` for efficient lookup of sub-plans.

```APIDOC
computeCostAndCardOfSubplan(
  stats: Map<String, TableStats>,
  filterSelectivities: Map<String, Double>,
  joinToRemove: LogicalJoinNode,
  joinSet: Set<LogicalJoinNode>,
  bestCostSoFar: double,
  pc: PlanCache
): CostCard (or null)
```

--------------------------------

### Rename Default Git Remote to Upstream

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/README.md

This command renames the default 'origin' remote, which points to the course repository, to 'upstream'. This is a crucial step to differentiate the course repository from the user's personal repository, preventing accidental pushes to the course's official remote.

```bash
$ git remote rename origin upstream
```

--------------------------------

### Run SimpleDB Parser with Catalog

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Command to invoke the SimpleDB parser with a specified catalog file. The parser will compute statistics over all tables and convert queries into a logical plan before calling the optimizer.

```Shell
java -jar dist/simpledb.jar parser catalog.txt
```

--------------------------------

### Update SimpleDB Project with Git

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Instructions to update the SimpleDB project directory by pulling the latest changes from the upstream master GitHub repository, ensuring all new lab files are included.

```Shell
cd simple-db-hw
git pull upstream master
```

--------------------------------

### Create Lab Submission Zip Archive (Bash)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

A bash command to create a `.zip` file for lab submission. It recursively includes the `src/` directory and the `lab2-writeup.txt` file, ensuring all necessary components are packaged.

```Bash
$ zip -r submission.zip src/ lab2-writeup.txt
```

--------------------------------

### Implement SimpleDB BufferPool Tuple Insertion, Deletion, and Eviction

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

Implement the methods in `BufferPool` responsible for tuple insertion, deletion, and page eviction. This involves managing the in-memory representation of disk pages and their modifications. At this stage, transactions do not need to be considered.

```APIDOC
BufferPool Class:
  Purpose: Manages disk pages in memory, handling reads, writes, and eviction.
  Methods to Implement:
    insertTuple(transactionId: TransactionId, tableId: int, tuple: Tuple): void
      transactionId: The ID of the transaction performing the insertion.
      tableId: The ID of the table to insert into.
      tuple: The tuple to insert.
      Description: Inserts a tuple into the specified table, potentially modifying a page and marking it dirty.

    deleteTuple(transactionId: TransactionId, tuple: Tuple): void
      transactionId: The ID of the transaction performing the deletion.
      tuple: The tuple to delete.
      Description: Deletes a tuple from its page, marking the page dirty.

    evictPage(): void
      Description: Implements a page eviction policy (e.g., LRU) to free up buffer pool space by writing dirty pages to disk and discarding clean pages.
```

--------------------------------

### Java Helper Method: printJoins

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

A utility method provided to display a graphical representation of a join plan. This is typically used for debugging or informational purposes when an 'explain' flag is enabled in the optimizer.

```APIDOC
printJoins(
  js: List<LogicalJoinNode>,
  pc: PlanCache,
  stats: Map<String, TableStats>,
  selectivities: Map<String, Double>
): void
```

--------------------------------

### LogFile.recover() Method Implementation Requirements

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This section outlines the functional requirements for implementing the `LogFile.recover()` method, which is responsible for database recovery after a crash. It details a three-step process involving reading checkpoints, re-doing updates, and un-doing loser transactions.

```APIDOC
LogFile.recover() Method:
  Purpose: Recovers the database state after a crash.
  Execution Steps:
    1. Read the last checkpoint, if any.
    2. Scan forward from the checkpoint (or start of log file if no checkpoint) to:
       - Build the set of loser transactions.
       - Re-do updates during this pass (safe to start re-do at checkpoint as logCheckpoint() flushes dirty buffers).
    3. Un-do the updates of loser transactions.
  Context: Called before any new transactions start after a database reboot.
```

--------------------------------

### Update SimpleDB Project with Lab 2 Files using Git

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

To acquire the new source and test files for Lab 2, navigate to your project directory and execute these Git commands. This process pulls the latest changes from the upstream master GitHub repository, ensuring your local SimpleDB project is up-to-date with the lab's requirements.

```Shell
$ cd simple-db-hw
$ git pull upstream master
```

--------------------------------

### Implementing Tuple Insertion in SimpleDB HeapFile and HeapPage

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This section describes the implementation of the `insertTuple` method in `HeapFile.java` and `HeapPage.java`. It requires finding an empty slot in an existing page or creating a new page if no slots are available, and updating the tuple's `RecordID`.

```APIDOC
HeapFile Class:
  insertTuple(tuple: Tuple): void
    description: Adds a new tuple to the heap file, finding an empty slot or creating a new page.
    parameters:
      tuple: The tuple to be inserted.

HeapPage Class:
  insertTuple(tuple: Tuple): void
    description: Modifies the header bitmap to mark a slot as used.
    dependencies: Relies on getNumEmptySlots() and isSlotUsed().
    utility: markSlotUsed() can be used to modify slot status.

Files to implement:
  src/java/simpledb/storage/HeapPage.java
  src/java/simpledb/storage/HeapFile.java
```

--------------------------------

### Update Page Before-Image in BufferPool.transactionComplete()

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This Java code snippet is added to `BufferPool.transactionComplete()` after a page has been flushed. It updates the page's before-image to its current committed state, which is crucial for correct rollback behavior of subsequent transactions.

```Java
// use current page contents as the before-image
// for the next transaction that modifies this page.
p.setBeforeImage();
```

--------------------------------

### Update Simple DB Project with Git Pull

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

This command sequence navigates into the simple-db-hw project directory and pulls the latest changes from the upstream master branch, ensuring the project is up-to-date with the required files for the assignment.

```Bash
$ cd simple-db-hw
$ git pull upstream master
```

--------------------------------

### Update Project Dependencies for IDEs using Ant

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

For users working with Eclipse or IntelliJ, running the 'ant eclipse' command is the easiest way to update project dependencies. This command configures the project to include new library JARs, after which you should reopen your project in the respective IDE for changes to take effect.

```Shell
ant eclipse
```

--------------------------------

### Convert Raw Data to SimpleDB Table Format

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

Command-line execution using `simpledb.jar` to convert `data.txt` into a SimpleDB-compatible `.dat` file. Parameters specify two integer fields per record.

```Java
java -jar dist/simpledb.jar convert data.txt 2 "int,int"
```

--------------------------------

### Heuristics for Join Cardinality Estimation

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

This section provides simplified guidelines for estimating join cardinality, particularly for equality and range joins. It suggests specific heuristics for cases where one attribute is a primary key, when no primary key exists, and for range scans, acknowledging that these are simplified approaches for practical implementation.

```APIDOC
Join Cardinality Estimation Heuristics:
  Equality Joins (Primary Key):
    When one attribute is a primary key, the number of tuples produced by the join cannot be larger than the cardinality of the non-primary key attribute.
  Equality Joins (No Primary Key):
    It is difficult to accurately predict output size; it could range from zero to the product of cardinalities. A simple heuristic is to assume the size of the larger of the two tables.
  Range Scans:
    It is similarly hard to provide accurate size estimates. Assume a fixed fraction (e.g., 30%) of the cross-product is emitted. The cost of a range join should generally be larger than a non-primary key equality join of two tables of the same size.
```

--------------------------------

### Overall Plan Cost Calculation

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Formula for calculating the total cost of a left-deep join plan, considering I/O costs for table scans and CPU costs for joins. It also defines a scaling factor to make I/O and CPU costs comparable.

```Conceptual
scancost(t1) + scancost(t2) + joincost(t1 join t2) +
scancost(t3) + joincost((t1 join t2) join t3) +
...

cost(predicate application) = 1
cost(pageScan) = SCALING_FACTOR x cost(predicate application)
```

--------------------------------

### Implement TableStats Class for Comprehensive Table Statistics

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Implement the TableStats class, which computes the number of tuples and pages in a table and estimates predicate selectivity over its fields. This class is instantiated per table by the query parser and is crucial for the query optimizer. Specific methods to implement include the constructor, estimateSelectivity, and estimateScanCost.

```APIDOC
Class: TableStats
  Purpose: Computes table-level statistics (tuple/page counts) and estimates predicate selectivity.
  Methods to implement:
    - Constructor: TableStats(DbFile file, int avgPageSize)
      Purpose: Scans the table to build necessary statistics (e.g., histograms).
      Parameters:
        file: The database file to scan.
        avgPageSize: The average size of a page in bytes.
    - estimateSelectivity(int field, Predicate.Op op, Field constant): double
      Purpose: Estimates the selectivity of a predicate on a specific field.
      Parameters:
        field: The index of the field.
        op: The predicate operator (e.g., EQUALS, GREATER_THAN).
        constant: The constant value to compare against.
      Returns: The estimated selectivity (a double between 0.0 and 1.0).
    - estimateScanCost(): double
      Purpose: Estimates the cost of sequentially scanning the file.
      Returns: The estimated cost.
```

--------------------------------

### Implement SimpleDB Insert and Delete Operators in Java

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This exercise requires implementing the `Insert` and `Delete` operators, which modify disk pages by adding or removing tuples. These operators should utilize `BufferPool.insertTuple()` and `BufferPool.deleteTuple()` respectively, and return the count of affected tuples as a single-field integer tuple. Unit tests for `Insert` and system tests for both are provided.

```Java
src/java/simpledb/execution/Insert.java
src/java/simpledb/execution/Delete.java
```

--------------------------------

### Implement IntHistogram Class for Integer Selectivity Estimation

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Implement the IntHistogram class to record table statistics for integer attributes. This class should support a bucket-based histogram approach to estimate selectivity for various predicates. The implementation should be robust enough to pass the provided IntHistogramTest unit tests.

```APIDOC
Class: IntHistogram
  Purpose: Records table statistics for integer attributes using a histogram.
  Key functionalities (implied by description):
    - Constructor: Initializes the histogram with a specified number of buckets and min/max values.
    - addValue(int value): Adds a value to the histogram, updating bucket counts.
    - estimateSelectivity(Predicate.Op op, int constant): Estimates the selectivity of a predicate (e.g., equality, range) using the histogram data.
```

--------------------------------

### LogFile.rollback() Method Specification

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab6.md

Specification for the `rollback()` method within `LogFile.java`, detailing its purpose to undo changes made by an aborting transaction. It requires reading log records, extracting before-images, writing them to the table file, and invalidating corresponding buffer pool pages.

```APIDOC
Class: LogFile
Method: rollback()
  Description: Undoes any changes made by an aborting transaction.
  Parameters: None (implicitly operates on the current transaction context)
  Behavior:
    - Reads the log file to find all update records associated with the aborting transaction.
    - Extracts the before-image from each relevant update record.
    - Writes the extracted before-image back to the corresponding table file.
    - Discards any page from the buffer pool whose before-image was written back to the table file.
  Hints:
    - Use 'raf.seek()' to navigate the log file.
    - Use 'raf.readInt()' and similar methods to parse log records.
    - Use 'readPageData()' to read before- and after-images.
    - Utilize 'tidToFirstLogRecord' map to find the starting log offset for a transaction.
```

--------------------------------

### BufferPool.transactionComplete() Method API

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab4.md

API documentation for the `transactionComplete` method in the `BufferPool` class, detailing its two overloaded versions, parameters, and behavior during commit and abort operations, including flushing dirty pages, reverting changes, and releasing locks.

```APIDOC
BufferPool:
  transactionComplete(tid: TransactionId, commit: boolean): void
    tid: The TransactionId object associated with the query.
    commit: A boolean flag indicating whether to commit (true) or abort (false) the transaction.
    Description:
      When 'commit' is true, flushes dirty pages associated with the transaction to disk and releases transaction state and locks.
      When 'commit' is false, reverts any changes made by the transaction by restoring pages to their on-disk state and releases transaction state and locks.
  transactionComplete(tid: TransactionId): void
    tid: The TransactionId object associated with the query.
    Description:
      Always commits the transaction by calling transactionComplete(tid, true).
      Releases transaction state and locks.
```

--------------------------------

### Selinger Join Ordering Algorithm Pseudocode

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

Pseudocode outlining the Selinger join ordering algorithm, which iterates through subsets of join nodes to find the optimal join plan based on cost. It uses a dynamic programming approach to build up optimal plans for increasingly larger subsets of joins.

```Pseudocode
1. j = set of join nodes
2. for (i in 1...|j|):
3.     for s in {all length i subsets of j}
4.       bestPlan = {}
5.       for s' in {all length d-1 subsets of s}
6.            subplan = optjoin(s')
7.            plan = best way to join (s-s') to subplan
8.            if (cost(plan) < cost(bestPlan))
9.               bestPlan = plan
10.      optjoin(s) = bestPlan
11. return optjoin(j)
```

--------------------------------

### Implementing Tuple Operations in SimpleDB BufferPool

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This section outlines the implementation of `insertTuple` and `deleteTuple` methods in `BufferPool.java`. These methods act as an indirection layer, calling the appropriate methods in the `HeapFile` belonging to the table being modified, ensuring proper transaction support.

```APIDOC
BufferPool Class:
  insertTuple(): void
    description: Calls the appropriate insertTuple method in the HeapFile belonging to the table being modified.
  deleteTuple(): void
    description: Calls the appropriate deleteTuple method in the HeapFile belonging to the table being modified.

Files to implement:
  src/simpledb/BufferPool.java
```

--------------------------------

### Estimate Join Cost in Java's JoinOptimizer

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab3.md

This method estimates the cost of a given join operation, assuming a Nested Loop (NL) join. It takes into account the cardinalities and scan costs of both the left and right inputs to apply the specified cost formula, contributing to overall query plan optimization.

```APIDOC
JoinOptimizer.java:
  estimateJoinCost(LogicalJoinNode j, int card1, int card2, double cost1, double cost2)
    j: The LogicalJoinNode representing the join operation.
    card1: Cardinality of the left input.
    card2: Cardinality of the right input.
    cost1: Cost to scan the left input.
    cost2: Cost to access the right input.
    Returns: The estimated cost of the join.
```

--------------------------------

### Implement SimpleDB Insert and Delete Operators

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

Implement the `Insert` and `Delete` operators. Both implement `OpIterator`, accepting a stream of tuples to insert or delete and outputting a single tuple with an integer field indicating the number of tuples affected. These operators must call the appropriate methods in `BufferPool` to modify the pages on disk.

```APIDOC
Insert Class:
  Purpose: An OpIterator that inserts tuples into a table.
  Constructor:
    Insert(transactionId: TransactionId, tableId: int, child: OpIterator)
      transactionId: The ID of the transaction performing the insertion.
      tableId: The ID of the table to insert into.
      child: The OpIterator providing tuples to insert.
  Methods:
    next(): Tuple
      Returns: A single tuple with an integer field indicating the number of inserted tuples.
    hasNext(): boolean
    open(): void
    close(): void
    rewind(): void

Delete Class:
  Purpose: An OpIterator that deletes tuples from a table.
  Constructor:
    Delete(transactionId: TransactionId, child: OpIterator)
      transactionId: The ID of the transaction performing the deletion.
      child: The OpIterator providing tuples to delete.
  Methods:
    next(): Tuple
      Returns: A single tuple with an integer field indicating the number of deleted tuples.
    hasNext(): boolean
    open(): void
    close(): void
    rewind(): void
```

--------------------------------

### Implementing Tuple Deletion in SimpleDB HeapFile and HeapPage

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab2.md

This section focuses on implementing the `deleteTuple` method within `HeapFile.java` and `HeapPage.java`. It involves locating the page containing the tuple using its `RecordID` and modifying the page headers to mark the slot as unused.

```APIDOC
HeapFile Class:
  deleteTuple(tuple: Tuple): void
    description: Removes a tuple from the heap file by locating its page and modifying headers.
    parameters:
      tuple: The tuple to be deleted, containing its RecordID.

HeapPage Class:
  deleteTuple(tuple: Tuple): void
    description: Modifies the header bitmap to mark a slot as unused.
    dependencies: Relies on getNumEmptySlots() and isSlotUsed().
    utility: markSlotUsed() can be used to modify slot status.

Files to implement:
  src/java/simpledb/storage/HeapPage.java
  src/java/simpledb/storage/HeapFile.java
```

--------------------------------

### B+Tree Deletion and Redistribution API Specifications

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab5.md

Specifications for implementing core B+Tree deletion mechanisms, including functions for redistributing tuples/entries between pages and merging pages to maintain tree balance and optimize space. These operations are crucial for efficient B+Tree management.

```APIDOC
Class: BTreeFile
  Methods for Page Redistribution (Exercise 3):
    stealFromLeafPage():
      Purpose: Redistributes tuples from a sibling to a less than half full leaf page.
      Notes: Updates the corresponding key field in the parent.
    stealFromLeftInternalPage():
      Purpose: Redistributes entries from a left sibling to a less than half full internal page.
      Notes: Updates the corresponding key field in the parent and parent pointers of moved children (reuse updateParentPointers()).
    stealFromRightInternalPage():
      Purpose: Redistributes entries from a right sibling to a less than half full internal page.
      Notes: Updates the corresponding key field in the parent and parent pointers of moved children (reuse updateParentPointers()).

  Methods for Page Merging (Exercise 4):
    mergeLeafPages():
      Purpose: Merges a less than half full leaf page with a sibling.
      Notes: Inverse of splitLeafPage(). Utilizes deleteParentEntry() for recursive cases. Call setEmptyPage() on deleted pages.
    mergeInternalPages():
      Purpose: Merges a less than half full internal page with a sibling.
      Notes: Inverse of splitInternalPage(). Utilizes deleteParentEntry() for recursive cases. Call setEmptyPage() on deleted pages.

  Utility Methods (referenced):
    updateParentPointers():
      Purpose: Updates parent pointers of children pages after redistribution.
    deleteParentEntry():
      Purpose: Handles recursive deletion of entries from parent nodes during merges.
    getPage():
      Purpose: Encapsulates fetching pages and keeping the list of dirty pages up to date.
    setEmptyPage():
      Purpose: Marks a page as available for reuse after deletion/merging.
```

--------------------------------

### B+Tree Reverse Scan API Specification (Extra Credit)

Source: https://github.com/mit-db-class/simple-db-hw-2021/blob/master/lab5.md

Specification for implementing a new class, BTreeReverseScan, to enable scanning the BTreeFile in reverse order, optionally with an IndexPredicate. This requires implementing a reverse iterator and a specialized findLeafPage method.

```APIDOC
Class: BTreeReverseScan
  Purpose: Scans the BTreeFile in reverse order.
  Optional Parameter: IndexPredicate (for filtered reverse scans).
  Implementation Requirements:
    Implement a reverse iterator within BTreeFile.
    Implement a separate version of BTreeFile.findLeafPage() for reverse scanning.
  Dependencies/Helpers:
    BTreeLeafPage (provided reverse iterators available)
    BTreeInternalPage (provided reverse iterators available)
  Testing:
    Refer to BTreeScanTest.java for ideas on writing tests.
```