FlexQL - A Flexible SQL-like Database Driver

A client-server SQL database engine built from scratch in C++17 with zero external dependencies. FlexQL implements a focused subset of SQL over a custom storage engine featuring slotted-page heaps, B+ tree indexing, a CLOCK-based buffer pool, and write-ahead logging for crash recovery.

Design Document: See [Design_Document.pdf] for a detailed writeup of every design decision.

Prerequisites

• C++17 compiler (GCC 11+ or Clang 14+)
• CMake 3.16+
• POSIX system (macOS or Linux)

Build

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel

Produces two binaries:

Binary	Description
build/flexql_server	Database server
build/flexql_client	Interactive REPL client

Quick Start

# Terminal 1: Start the server (fresh database)
./build/flexql_server 9000 --fresh

# Terminal 1: Start the server (recover existing data)
./build/flexql_server 9000

# Terminal 2: Connect the client
./build/flexql_client 127.0.0.1 9000

Example Session

$ ./build/flexql_client 127.0.0.1 9000
Connected to FlexQL server

flexql> CREATE TABLE employees (id INT PRIMARY KEY, name VARCHAR(100), salary DECIMAL);
OK

flexql> INSERT INTO employees VALUES (1, 'Alice', 80000);
OK

flexql> INSERT INTO employees VALUES (2, 'Bob', 95000);
OK

flexql> SELECT * FROM employees;
id = 1
name = Alice
salary = 80000

id = 2
name = Bob
salary = 95000

flexql> SELECT name FROM employees WHERE id = 1;
name = Alice

flexql> CREATE TABLE departments (did INT PRIMARY KEY, emp_id INT, dept VARCHAR(50));
OK

flexql> INSERT INTO departments VALUES (101, 1, 'Engineering');
OK

flexql> SELECT * FROM employees INNER JOIN departments ON employees.id = departments.emp_id;
employees.id = 1
employees.name = Alice
employees.salary = 80000
departments.did = 101
departments.emp_id = 1
departments.dept = Engineering

flexql> .exit
Connection closed

Supported SQL

Command	Example
CREATE TABLE	CREATE TABLE t (id INT PRIMARY KEY, name VARCHAR(100) NOT NULL, score DECIMAL);
INSERT (single row)	INSERT INTO t VALUES (1, 'Alice', 3.9);
INSERT (multi-row)	INSERT INTO t VALUES (1, 'Alice', 3.9), (2, 'Bob', 4.0);
SELECT *	SELECT * FROM t;
SELECT columns	SELECT name, score FROM t;
WHERE	SELECT * FROM t WHERE id = 1;
INNER JOIN	SELECT * FROM a INNER JOIN b ON a.id = b.aid;
ORDER BY	SELECT * FROM t ORDER BY score DESC;
DELETE (truncate)	DELETE FROM t;

Supported types: INT / INTEGER, VARCHAR(n), DECIMAL, DATETIME

Comparison operators in WHERE: =, >, <, >=, <=

Restriction: WHERE supports one condition only (no AND / OR chaining).

Architecture Overview

                  +-------------------+
                  |   TCP Clients     |
                  +--------+----------+
                           |
                  +--------v----------+
                  |   Wire Protocol   |  Semicolon-delimited SQL, HEADER/ROW responses
                  +--------+----------+
                           |
                  +--------v----------+
                  | Parser (Tokenizer |  Hand-written recursive descent
                  |   + AST Builder)  |
                  +--------+----------+
                           |
                  +--------v----------+
                  |     Executor      |  Index lookup, table scan, nested-loop join
                  +--------+----------+
                           |
            +--------------+--------------+
            |                             |
   +--------v----------+      +-----------v--------+
   |    Table Heap      |      |     B+ Tree        |
   | (Slotted Pages,    |      | (INT PK index,     |
   |  Linked List)      |      |  crab locking)     |
   +--------+-----------+      +-----------+--------+
            |                             |
            +--------------+--------------+
                           |
                  +--------v----------+
                  |   Buffer Pool     |  131K frames (512 MB), CLOCK eviction
                  +--------+----------+
                           |
              +------------+------------+
              |                         |
     +--------v----------+   +----------v--------+
     |   Disk Manager    |   |   WAL Manager     |
     | (pread/pwrite,    |   | (REDO-only, page  |
     |  4KB pages)       |   |  after-images)    |
     +-------------------+   +-------------------+

Storage: Row-major slotted-page heap

• 4 KB fixed-size pages with a 16-byte header
• Slot directory grows downward from the header, tuple data grows upward from the page end
• Each tuple carries an 8-byte expiration timestamp as its first field
• Pages are linked together per table to form a singly-linked list

Indexing: B+ tree on primary key

• Integer keys mapped to RecordID (page_id, slot_id)
• ~339 entries per leaf node, ~509 entries per internal node
• A tree with 10 million keys is only 3 levels deep
• Crab locking (latch coupling) during inserts for concurrency

Caching: CLOCK replacement (buffer pool)

• 131,072-frame buffer pool (512 MB default)
• Write-back dirty page policy, eviction writes skip WAL for efficiency
• Second-chance (CLOCK) eviction algorithm
• Tracks cache hits, misses, evictions, and dirty flushes

Write-Ahead Logging

• REDO-only physical WAL with full page after-images (4,108 bytes per record)
• XOR-based checksums for corruption detection
• Batched fsync (every 2,048 records) for throughput
• Crash recovery replays valid records on startup, then checkpoints

Concurrency

• Thread-per-connection server model
• shared_mutex on pages, catalog, and table heap for reader/writer access
• B+ tree crab locking with early ancestor release
• Double-checked locking on table heap inserts (shared lock fast path)

Wire Protocol

• TCP socket with TCP_NODELAY and 256 KB buffers
• Semicolon-delimited SQL statements
• Response format: HEADER/ROW lines (tab-separated), OK, END markers

C/C++ Client API

The client library exposes a C API (flexql.h) modeled after SQLite's callback interface:

#include "flexql.h"

FlexQL *db;
int rc = flexql_open("127.0.0.1", 9000, &db);

char *errmsg = NULL;
rc = flexql_exec(db, "SELECT * FROM t;", callback, user_data, &errmsg);
if (rc != FLEXQL_OK) {
    printf("Error: %s\n", errmsg);
    flexql_free(errmsg);
}

flexql_close(db);

API Reference

Function	Description
flexql_open(host, port, &db)	Connect to server, return opaque handle
flexql_exec(db, sql, callback, arg, &errmsg)	Execute SQL, invoke callback per result row
flexql_close(db)	Close connection and free resources
flexql_free(ptr)	Free API-allocated memory (error messages)

Callback signature: int callback(void* data, int columnCount, char** values, char** columnNames)

• Return 0 to continue, 1 to abort.

Benchmarking

# 1. Start the server
./build/flexql_server 9000 --fresh

# 2. Build and run the benchmark (links against FlexQL's C API)
./build/flexql_ta_benchmark

The benchmark inserts 10 million rows and measures insert throughput and SELECT query latency.

Data Files

FlexQL stores all persistent state in three flat files:

File	Contents
flexql.db	Main data file containing 4 KB pages
flexql.db.wal	Write-ahead log for crash recovery
flexql.db.catalog	Text-based catalog metadata (tables, schemas, page pointers)

Use --fresh when starting the server to wipe all data and start clean.

Project Structure

FlexQL/
  include/
    flexql.h              C client API header
    database.hpp          Top-level database orchestration
    common/               Constants, RecordID
    storage/              Page, SlottedPage, Tuple, TableHeap, DiskManager, WAL
    cache/                BufferPoolManager, ClockReplacer
    index/                B+ tree pages and operations
    catalog/              Catalog, Schema, Column
    parser/               Token, AST, Tokenizer, Parser
    query/                Executor
    network/              TCP protocol helpers
    server/               SQL normalizer
  src/
    server/server.cpp     Main server entry point
    client/main.cpp       Interactive REPL
    flexql_api.cpp        C API implementation
    storage/              Storage layer implementations
    cache/                Buffer pool and CLOCK implementations
    index/                B+ tree operations
    parser/               Tokenizer and parser
    query/                Query executor
  benchmark_flexql.cpp    Benchmark and unit test suite
  CMakeLists.txt          Build configuration
  report.tex              Design document (LaTeX)