Caltech CS122 — NanoDB

A relational database engine in Java — an independent, from-skeleton implementation of CS122 Database System Implementation (Caltech, Winter 2018–2019), part of a csdiy.wiki full-catalog build.

Overview

NanoDB is a teaching DBMS from Caltech's CS122. Starting from the course's official Winter-2019 skeleton (Maven + ANTLR4, package edu.caltech.nanodb), this repository implements the storage layer, the SQL-to-plan translator with joins, table-statistics collection and cost-based plan costing, and non-correlated/correlated subquery support. Every feature is exercised by the course's own TestNG suite and by an end-to-end SQL demo.

The work spans these assignments from the official course site:

• Assignment 1 — Set-Up and Storage Layer: tuple deletion & update, buffer pinning.
• Assignment 2 — SQL Translation and Joins: a real query planner, nested-loop joins.
• Assignment 3 — Table Statistics and Plan Costing: ANALYZE, selectivity, costs.
• Assignment 5 — Advanced Subqueries: scalar / IN / EXISTS subqueries.

(Assignment 4 — the Selinger dynamic-programming join optimizer — and Assignment 6 — the B+Tree tuple-file module — are not present in this base skeleton; see Scope & partials.)

Results (measured on Windows, JDK 21, CPU-only)

The course's TestNG suite runs via mvn test (one forked JVM per class):

Test area	Class(es)	Result
Heap storage: insert/update/delete/format	TestHeapTableFormat	6 / 6
Simple selects & projection	TestSimpleSelects, TestSelectProject	2 / 2, 3 / 3
String matching (LIKE)	TestStringMatch	6 / 6
Aggregation (SUM/AVG/MIN/MAX/COUNT/STDDEV/VAR, DISTINCT)	TestAggregation	11 / 11
Grouping	TestGroupBy, TestGroupingAndAggregation	6 / 6, 6 / 6
HAVING	TestHaving	2 / 2
Built-in functions	TestSimpleFunctions	3 / 3
Subqueries: scalar / IN / EXISTS (incl. correlated)	TestScalarSubquery, TestInPredicates, TestExists	6 / 6, 3 / 3, 3 / 3
Key/constraint enforcement	TestPrimaryKeyOps, TestUniqueOps, TestNotNullOps, TestForeignKeyOps	all green
Parser, expressions, storage framework	30+ classes	all green
Whole suite		201 / 206 passing

The 5 remaining failures are base-skeleton / environment issues, not defects in the implemented assignments — details in Scope & partials and results/assignment-test-results.txt.

End-to-end demo (results/demo.sql → results/demo-output.txt)

A single script drives every assignment. Highlights of the real output:

-- A1: UPDATE (VARCHAR resize + set-to-NULL) and DELETE
+--------+-----------+-------+--------+
| emp_id | name      | dept  | salary |
+--------+-----------+-------+--------+
|      1 | Alexandra | Eng   | 120000 |   <- 'Alice' grown in place to 'Alexandra'
|      3 | Carol     | Sales | 105000 |
|      4 | Dan       | null  |  85000 |   <- dept set to NULL
|      5 | Eve       | Eng   | 130000 |   <- emp_id 2 deleted
+--------+-----------+-------+--------+

-- A2: GROUP BY dept with COUNT(*), AVG(salary), MAX(salary)
| Eng   | 2 | 125000.0 | 130000 |
| Sales | 1 | 105000.0 | 105000 |
| null  | 1 |  85000.0 |  85000 |

-- A2: LEFT OUTER JOIN keeps unmatched 'Dan' with a NULL location.

-- A3: ANALYZE + EXPLAIN produces real, statistics-driven plan costs
SimpleFilter[pred: employees.salary > 100000] cost=[tuples=4.0, tupSize=20.3, cpuCost=8.0, blockIOs=1, largeSeeks=0]
    FileScan[table: employees]                cost=[tuples=4.0, tupSize=20.3, cpuCost=4.0, blockIOs=1, largeSeeks=0]

-- A5: scalar subquery (salary > (SELECT AVG(salary) ...)) and IN-subquery both return {Alexandra, Eve}

Implemented assignments

• A1 — Storage layer
  • DataPage.deleteTuple — reclaim tuple space, mark the slot empty, trim trailing empty slots.
  • PageTuple.setNullColumnValue / setNonNullColumnValue — correct null-bitmap and value-offset management for fixed- and variable-size columns, tracking the tuple's moving pageOffset (NanoDB tuples grow downward from a fixed end-offset).
  • HeapTupleFile.addTuple — unpin skipped pages during the free-space scan.
• A2 — SQL translation & joins
  • SimplePlanner — joins (inner / left- / right-outer via nested loop), FROM subqueries, WHERE, GROUP BY + aggregation, HAVING, ORDER BY, and projection.
  • AggregateProcessor — extracts aggregate calls from SELECT/HAVING, rejects nesting.
  • NestedLoopJoinNode — full inner + left-outer join logic and cost estimation.
• A3 — Statistics & costing
  • HeapTupleFile.analyze — per-column (distinct/NULL/min/max) and table-level (tuples, avg size, data pages) stats, persisted to the header page.
  • SelectivityEstimator — AND/OR/NOT, equality & inequality (via distinct counts and min/max ratios), column-vs-column equality, with graceful fallback.
  • FileScanNode / SimpleFilterNode cost computation scaled by predicate selectivity.
• A5 — Advanced subqueries
  • SubqueryPlanner — plans scalar/IN/EXISTS subqueries in SELECT/WHERE/HAVING and wires the parent environment for correlated evaluation.
  • InSubqueryOperator — correct IN / NOT IN semantics.
• [~] A4 / A6 — not in this base skeleton (see Scope & partials).

Project structure

caltech-cs122-nanodb/
├── pom.xml                     # Maven build (ANTLR4 parser gen, JaCoCo, surefire/TestNG)
├── nanodb, nanodb.bat          # launch scripts
├── src/main/antlr4/…           # NanoSQL grammar
├── src/main/java/edu/caltech/nanodb/
│   ├── storage/…               # DataPage, PageTuple, HeapTupleFile (A1, A3 analyze)
│   ├── plannodes/…             # NestedLoopJoinNode, FileScanNode, SimpleFilterNode (A2, A3)
│   ├── queryeval/…             # SimplePlanner, AggregateProcessor, SubqueryPlanner,
│   │                           #   SelectivityEstimator (A2, A3, A5)
│   ├── queryast/…              # SelectClause / FromClause schema computation
│   └── expressions/…           # InSubqueryOperator, aggregate functions, DateTimeUtils
├── src/test/java/…             # the course's TestNG suite (unmodified)
├── testng-all.xml              # convenience suite listing the functional test classes
└── results/                    # demo.sql, demo-output.txt, test summaries

How to run

Requires JDK 11+ (verified on JDK 21), Apache Maven, and Python (for the ANTLR pre-generate step).

# Build and run the full test suite (one forked JVM per test class):
mvn test

# Run a single assignment's tests:
mvn test -Dtest=TestHeapTableFormat     # A1 storage
mvn test -Dtest=TestAggregation         # A2 aggregation
mvn test -Dtest=TestScalarSubquery      # A5 subqueries

# Package a runnable JAR and start the interactive shell:
mvn -DskipTests package
./nanodb            # (nanodb.bat on Windows) — then type SQL at the CMD> prompt

# Reproduce the end-to-end demo:
java -Dnanodb.baseDirectory=./datafiles \
     -cp "target/classes;target/lib/*" \
     edu.caltech.nanodb.client.ExclusiveClient < results/demo.sql

Verification

• Course tests: mvn test runs the course's own TestNG suite — 201/206 pass. Every assignment's functional tests are green (see the table above and results/assignment-test-results.txt).
• End-to-end: results/demo.sql produced results/demo-output.txt, exercising A1 update/delete, A2 joins & aggregation, A3 ANALYZE/EXPLAIN cost output, and A5 subqueries.
• Several bugs were found by the tests and fixed with root-cause reasoning (see the git history), most notably: the tuple pageOffset not being updated on in-place resize (corrupted VARCHARs), COUNT(DISTINCT x) silently dropping DISTINCT, integer-division in AVG/STDDEV, a derived-table result-schema that kept only its last column, and NOT IN never negating.

Scope & partials

• Assignment 4 (cost-based join optimizer) and Assignment 6 (B+Tree tuple files) are not part of this base skeleton — it ships neither the CostBasedJoinPlanner nor a storage/btreefile module, and its testng.xml references B+Tree tests that do not exist in the tree. TestIndexOps' one failure (indexColRefs must be specified) is a B+Tree index-creation test with no backing module here.
• TestNaturalUsingJoins (3 failures): (a) the WI-2019 test suite is internally inconsistent about identifier case — the parser tests assert lowercase identifiers, while these SQL tests assert uppercase, so a single parser cannot satisfy both; (b) chained 3+-table NATURAL joins hit a base AST/ProjectNode limitation when coalescing an unqualified common column that is ambiguous in the physical join schema. Two-table NATURAL/USING joins produce correct results (verified).
• TestBufferManager.testConcurrentSeparateFiles: a Windows-only file-lock flake in a concurrency test's temp-directory cleanup, unrelated to any assignment code.

Toolchain notes

The base targets Java 11; it compiles and runs on JDK 21 with two portability fixes made to run the course's own tests on this machine:

• JaCoCo 0.8.2 → 0.8.11 — 0.8.2's coverage agent crashes the forked test JVM on JDK 21.
• DateTimeUtils formatters pinned to Locale.ENGLISH — so MMM/AM-PM date-time formats parse under a non-English default locale.

Tech stack

Java 21 · Apache Maven 3.9 · ANTLR 4.7 (SQL grammar) · TestNG 6.14 · Log4j 2.

Key ideas / what I learned

• Slotted-page tuple storage: how in-place update of a variable-size column forces the whole tuple to slide, and why the tuple's start offset — not its end — is what moves.
• The demand-driven (Volcano) plan-node pipeline: prepare → initialize → getNextTuple → cleanUp, and implementing nested-loop inner/outer joins on top of it.
• Turning a parsed SELECT-FROM-WHERE-GROUP BY-HAVING-ORDER BY block into a plan, including extracting aggregates into a hashed group-aggregate node.
• Cost-based query costing: collecting table/column statistics and estimating predicate selectivity from distinct-value counts and min/max ranges.
• Evaluating subqueries as nested plans, and threading a parent Environment through the plan tree to support correlated evaluation.

Credits & license

Based on the assignments of CS122 Database System Implementation by Donnie Pinkston at the California Institute of Technology. This repository is an independent educational reimplementation; all course materials, the NanoDB skeleton, datasets, and specifications belong to their original authors. Original code in this repo is released under the MIT License.