Metadata-Version: 2.4
Name: minisql-engine
Version: 0.4.0
Summary: A miniature SQL database engine built from scratch in Python
Author-email: Kathan Patel <kathanpatel403@gmail.com>
License-Expression: MIT
License-File: LICENSE
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Topic :: Database
Classifier: Topic :: Education
Requires-Python: >=3.10
Provides-Extra: dev
Requires-Dist: hypothesis; extra == 'dev'
Requires-Dist: pytest; extra == 'dev'
Requires-Dist: pytest-cov; extra == 'dev'
Requires-Dist: ruff; extra == 'dev'
Description-Content-Type: text/markdown

# MiniSQL

A miniature relational database engine built entirely from scratch in Python — lexer, parser, query planner with cost-based index selection, B-Tree indexes, write-ahead logging, ACID transactions with per-table locking, and a TCP client/server. Designed as a learning-focused reimplementation of core database internals, not a toy wrapper around SQLite.

## Features

- **DDL** — `CREATE TABLE` with column types, `PRIMARY KEY`, `NOT NULL`, `UNIQUE`, `FOREIGN KEY`
- **DML** — `INSERT` (multi-row), `SELECT`, `UPDATE`, `DELETE` (all with `WHERE`)
- **Joins** — `INNER`, `LEFT`, `RIGHT` joins with `ON` conditions
- **Aggregation** — `GROUP BY` / `HAVING` with `COUNT`, `SUM`, `AVG`, `MIN`, `MAX`
- **Ordering & Limits** — multi-column `ORDER BY` (ASC/DESC, NULL ordering), `LIMIT`
- **Null handling** — `IS NULL` / `IS NOT NULL` with three-valued logic
- **B-Tree indexes** — automatic index-aware query planning (SeqScan vs IndexScan)
- **Cost-based planner** — `EXPLAIN` shows estimated costs; planner auto-selects index for equality and range predicates
- **ACID transactions** — `BEGIN` / `COMMIT` / `ROLLBACK` with snapshot-based rollback
- **Write-Ahead Logging** — WAL ensures committed transactions survive crashes; uncommitted changes are discarded on recovery
- **Concurrency** — per-table read/write locking, exclusive write locks, concurrent readers, deadlock prevention via sorted table acquisition order, configurable timeout
- **Client/Server** — TCP socket server (one thread per client), JSON-lines protocol, per-connection sessions
- **Persistence** — JSON-based table and catalog storage, WAL checkpoint on clean shutdown
- **CLI** — `minisql` command with `repl`, `server`, `client`, `exec`, and `benchmark` subcommands

## Architecture

```
 SQL string
     │
     ▼
  ┌────────┐     ┌────────┐     ┌─────────┐     ┌──────────┐     ┌──────────┐
  │ Lexer  │────▶│ Parser │────▶│ Planner │────▶│ Executor │────▶│ Storage  │
  └────────┘     └────────┘     └─────────┘     └──────────┘     └──────────┘
   tokens          AST       execution plan    runs plan +       rows + B-Tree
                                  │           acquires locks      indexes
                                  │               │
                                  ▼               ▼
                           cost model        ┌────────┐
                           (index vs seq)     │  WAL   │──▶ crash recovery
                                              └────────┘
```

Each layer has a single responsibility and can be understood in isolation. The lexer produces tokens with position info; the parser produces a typed AST; the planner selects between SeqScan and IndexScan using a cost model; the executor runs the plan and coordinates with the lock manager; the WAL records mutations for durability.

## Install

```bash
git clone https://github.com/youruser/mini-sql-database.git
cd mini-sql-database
pip install -e ".[dev]"
```

## Quick Start

**REPL** — interactive SQL shell:

```bash
minisql repl
```

**Execute a single statement**:

```bash
minisql exec "CREATE TABLE users (id INT PRIMARY KEY, name TEXT, age INT);"
minisql exec "INSERT INTO users VALUES (1, 'Alice', 30);"
minisql exec "SELECT * FROM users WHERE age > 25;"
```

**Client/Server** — start a server, connect from another terminal:

```bash
# Terminal 1
minisql server --port 9000

# Terminal 2
minisql client --port 9000
```

**Run the benchmark suite**:

```bash
minisql benchmark --rows 5000
```

## SQL Syntax Reference

### DDL

```sql
CREATE TABLE employees (
    id    INT PRIMARY KEY,
    name  TEXT NOT NULL,
    email TEXT UNIQUE,
    dept  TEXT REFERENCES departments(name)
);
```

### DML

```sql
INSERT INTO employees VALUES (1, 'Alice', 'alice@example.com', 'Engineering');
INSERT INTO employees VALUES (2, 'Bob', 'bob@example.com', 'Sales'),
                              (3, 'Carol', 'carol@example.com', 'Engineering');

SELECT name, email FROM employees WHERE dept = 'Engineering';
SELECT * FROM employees ORDER BY name ASC LIMIT 10;
UPDATE employees SET dept = 'Support' WHERE id = 2;
DELETE FROM employees WHERE id = 3;
```

### Joins

```sql
SELECT e.name, d.location
FROM employees e
INNER JOIN departments d ON e.dept = d.name;

SELECT e.name, p.title
FROM employees e
LEFT JOIN projects p ON e.id = p.emp_id;
```

### Aggregation

```sql
SELECT dept, COUNT(*) AS cnt, AVG(age) AS avg_age
FROM employees
GROUP BY dept
HAVING COUNT(*) > 2;
```

### Transactions

```sql
BEGIN;
INSERT INTO employees VALUES (4, 'Dave', 'dave@example.com', 'Sales');
-- visible in this session only
ROLLBACK;
-- Dave is gone

BEGIN;
INSERT INTO employees VALUES (5, 'Eve', 'eve@example.com', 'Support');
COMMIT;
-- Eve is persisted
```

### Query Plans

```sql
EXPLAIN SELECT * FROM employees WHERE id = 1;
-- Uses IndexScan on idx_employees_id (cost 1.2) instead of SeqScan (cost 48.5)
```

## Benchmark Results

Benchmarks run on a single thread with 5,000 rows (in-memory, Python 3.10):

| Test | Time (s) |
|---|---|
| INSERT (bulk) | 2.24 |
| Full scan | 0.002 |
| Index equality lookup | 0.0001 |
| Index range scan | 0.002 |
| Seq scan (age > 50) | 0.013 |
| GROUP BY + COUNT | 0.006 |
| ORDER BY + LIMIT 100 | 0.023 |
| INNER JOIN (2,500 matched) | 36.97 |

Key observations:
- Index lookups are orders of magnitude faster than sequential scans for point queries.
- The JOIN dominates runtime because the nested-loop implementation re-scans the inner table for every outer row — a hash join or sort-merge join would be a meaningful improvement.
- INSERT performance is limited by per-row constraint checking and index maintenance.

Run your own: `minisql benchmark --rows 10000`

## Design Decisions & Tradeoffs

**Table-level locking instead of row-level locking.**
Row-level locking is more并发, but adds significant complexity (lock inheritance on split, gap locks, lock tables). Table-level locking is the right first implementation — it's simpler, correct, and lets the architecture support row-level locking as a drop-in replacement later.

**Simplified cost model with fixed selectivity heuristics.**
Real optimizers use table/column histograms to estimate selectivity. This planner uses fixed assumptions (equality selects ~10% of rows, range selects ~30%, filter predicates select ~50%). This is a known simplification — the planner will occasionally choose SeqScan when IndexScan would be faster for skewed data. The architecture supports swapping in real histograms later.

**B-Tree over hash index.**
Hash indexes only support equality. B-Trees support equality, range, prefix, and ORDER BY optimization — strictly more useful for a general-purpose engine. The B-Tree implementation supports order-3 trees with leaf-level linked lists for range scans.

**Nested-loop joins only.**
Hash joins and sort-merge joins would be faster for large tables, but nested-loop joins are correct for all join types (including LEFT/RIGHT) and trivially extensible. The executor interface supports swapping in better join algorithms without changing the planner.

**JSON-based persistence instead of a custom page format.**
A real database uses fixed-size pages, buffer pools, and direct I/O. JSON persistence trades performance for simplicity and debuggability — you can open `table.json` in any editor and understand exactly what's stored. The WAL provides crash-safety guarantees regardless of the storage format.

**WAL records operations, not page diffs.**
Recording higher-level operations (INSERT row X, DELETE row Y) rather than raw page bytes means recovery re-executes operations rather than replaying page writes. This is simpler but slower for large transactions — acceptable for a learning engine.

**Deadlock prevention via sorted acquisition order.**
Rather than deadlock detection (wait-for graphs, timeout-based abort/retry), the lock manager always acquires table locks in sorted name order. This makes deadlocks structurally impossible at the cost of occasional unnecessary waiting — the correct tradeoff for a single-server engine.

## Future Work

- **MVCC** — multi-version concurrency control to replace table-level locking with snapshot isolation
- **Row-level locking** — finer-grained locking for high-concurrency workloads
- **Hash joins and sort-merge joins** — reduce join cost from O(n*m) to O(n+m)
- **Cost histograms** — real selectivity estimation for the query planner
- **Subqueries and UNION** — extend the parser/grammar
- **Web admin UI** — browser-based query box and table browser
- **PyPI publication** — `pip install minisql` for anyone

## Testing

```bash
# Run all tests
python -m pytest tests/ -v

# Run with coverage
python -m pytest tests/ --cov=minisql --cov-report=term-missing

# Run fuzz tests (requires hypothesis)
python -m pytest tests/test_fuzz_parser.py -v
```

## Project Structure

```
mini-sql-database/
├── src/minisql/
│   ├── cli.py              # CLI entry point (repl, server, client, exec, benchmark)
│   ├── engine.py            # Top-level engine: tokenize → parse → plan → execute
│   ├── lexer.py             # Tokenizer with position tracking
│   ├── parser.py            # Recursive descent parser → AST
│   ├── tokens.py            # Token and TokenType definitions
│   ├── keywords.py          # SQL keyword/operator lookup tables
│   ├── ast_nodes.py         # AST node dataclasses
│   ├── catalog.py           # Table/column/index metadata
│   ├── storage.py           # In-memory table with B-Tree indexes
│   ├── index.py             # B-Tree index implementation
│   ├── planner.py           # Cost-based query planner
│   ├── plan_nodes.py        # Execution plan node dataclasses
│   ├── executor.py          # Plan executor with lock coordination
│   ├── wal.py               # Write-Ahead Log for crash recovery
│   ├── transaction.py       # Transaction and TransactionManager
│   ├── locking.py           # LockManager (per-table R/W locks)
│   ├── server.py            # TCP socket server
│   ├── client.py            # TCP client
│   ├── repl.py              # Interactive REPL
│   ├── benchmarks.py        # Benchmark suite
│   ├── exceptions.py        # Exception hierarchy
│   └── types.py             # Type coercion and validation
├── tests/
│   ├── test_btree.py
│   ├── test_catalog.py
│   ├── test_engine.py
│   ├── test_executor.py
│   ├── test_lexer.py
│   ├── test_parser.py
│   ├── test_planner.py
│   ├── test_types.py
│   ├── test_wal.py
│   ├── test_transactions.py
│   ├── test_concurrency.py
│   ├── test_explain.py
│   ├── test_error_messages.py
│   ├── test_fuzz_parser.py
│   └── test_cli.py
├── pyproject.toml
├── ARCHITECTURE.md
└── .github/workflows/ci.yml
```

## License

MIT
