chidb

chidb is a didactic relational database management system (RDBMS) designed for teaching how a RDBMS is built internally, from the data organization in files all the way up to the SQL parser and query optimizer. The design of chidb is based on SQLite, with several simplifying assumptions that make it possible to develop a complete chidb implementation over the course of a quarter or semester. One of the key similarities is that chidb uses a single file to store all its information (database metadata, tables, and indexes). In fact, the chidb file format is a subset of SQLite, meaning that well-formed chidb files will also be well-formed SQLite files (the opposite, though, is not necessarily true).

• Introduction
• The chidb File Format
  • File format overview
  • Datatypes
  • File header
  • Table pages
  • Table cells
  • Database records
  • Indexes
  • The schema table
• The chidb Architecture
  • chidb API
  • Database Machine
• Installing, Building, and Running chidb
  • Software Requirements
  • Building
  • Running
• Assignment I: B-Trees
  • Before you get started
  • Step 1: Opening a chidb file
  • Step 2: Loading a B-Tree node from the file
  • Step 3: Creating and writing a B-Tree node to disk
  • Step 4: Manipulating B-Tree cells
  • Step 5: Finding a value in a B-Tree
  • Step 6: Insertion into a leaf without splitting
  • Step 7: Insertion with splitting
  • Step 8: Supporting index B-Trees
• Assignment II: Database Machine
  • DBM code
  • Testing your DBM
  • Step 1: Implement the Register Manipulation Instructions
  • Step 2: Implement the Control Flow Instructions
  • Step 3: Implement Cursors and Cursor Instructions for Table B-Trees
  • Step 4: SELECT queries
  • Step 5: INSERT statements
  • Step 6: CREATE TABLE statements
  • Step 7: Index operations
• Assignment III: Code Generation
  • Code Generator code
  • Testing your Code Generator
  • Step 1: Schema Loading
  • Step 2: Simple SELECT Code Generation
  • Step 3: INSERT Code Generation
  • Step 4: CREATE TABLE Code Generation
  • Step 5: NATURAL JOIN Code Generation
• Assignment IV: Query Optimization
  • Pushing Sigmas
  • Supporting Indexes
• Testing your Implementation
  • Automated tests
  • Running tests selectively
  • Sample “string” B-Tree files
  • Sample chidb files
  • The DBM File Format
• The chidb Shell
  • Running SQL queries
  • Running DBM programs
  • The EXPLAIN command
  • Other commands
  • Running non-interactively