MiniDB

MiniDB 是一个使用 C++20 实现的 PostgreSQL 风格关系型数据库内核，包含 MVCC 快照隔离、WAL 崩溃恢复、B+Tree 索引、代价优化器、分区 Buffer Pool、低内存降级执行路径，以及带准入控制的 TCP Server。

前言

• 本数据库大部分代码由AI编写，笔者只做了一些设计和细节上的调整
• 项目主要目的是基于教学目的，实现了大部分数据库的基础特性
• 项目地址

功能概览

SQL 支持

数据类型

支持以下字段类型和别名：

• BOOL / BOOLEAN
• INT / INTEGER
• BIGINT
• FLOAT / REAL
• DOUBLE / DECIMAL / NUMERIC
• VARCHAR(n)
• TEXT
• NULL

支持常见约束：

PRIMARY KEY
UNIQUE
NOT NULL
DEFAULT

存储引擎

• 8KB 页面，包含 slot array / line pointer 布局。
• Heap File 存储表数据，页级空闲空间跟踪。
• Buffer Pool 支持可配置大小、LRU、顺序扫描防污染，以及按 page id 分区的 page table / LRU 锁。
• B+Tree 索引支持单列索引、复合索引、唯一索引、等值查询、范围查询和 Index-Only Scan。
• Primary Key 和 Unique 字段会自动创建唯一索引。
• Double-write buffer 防止 torn page。
• Page checksum 用于检测静默损坏。
• FD cache 用于限制打开文件描述符数量。

MVCC 与事务

• 快照隔离，每个事务看到一致快照。
• Tuple 包含 xmin / xmax 和版本链指针。
• 支持 HOT update，减少索引维护开销。
• 支持 undo record，事务回滚不依赖 REDO。
• GC 基于活跃事务水位线回收旧版本。
• UPDATE/COMMIT 路径会主动剪枝对所有活跃事务不可见的版本链。

WAL 与恢复

• WAL-first：数据页刷盘前必须先写 WAL。
• WAL record 支持 Begin、Commit、Abort、Insert、Delete、Update、IndexInsert、IndexDelete、PageAlloc、Checkpoint。
• WAL 写入支持 8KB page buffer，攒页后批量写入/fsync。
• 支持 group commit，可配置批量提交延迟。
• 支持 checkpoint，按时间和 WAL 大小触发。
• 崩溃恢复会从 checkpoint 后重放 WAL。
• 索引恢复支持 lazy rebuild 或启动时重建。

查询执行器

MiniDB 使用 Volcano iterator 模型，主要执行器包括：

• SeqScan：顺序扫描、MVCC 可见性、版本链遍历、late materialization。
• IndexScan：B+Tree 等值和范围扫描。
• IndexOnlyScan：投影只需要索引 key 时避免回表。
• Filter：编译后的常见谓词快路径，失败时回退通用表达式求值。
• Project：列投影和表达式计算。
• NestedLoopJoin：小表或非等值连接。
• HashJoin：等值连接，小侧 build，低内存时 Grace Hash Join 分区 spill。
• IndexLookupJoin：外侧较小且内侧 join key 有索引时使用索引查找连接。
• Sort：内存排序、External Sort、Top-N heap。
• Aggregate：普通聚合、Hash Aggregate、spill 路径、COUNT(*) JOIN 快路径。
• Distinct：去重和 spill。
• Limit：LIMIT/OFFSET。
• Union：UNION 和 UNION ALL。
• SubqueryIn：IN (SELECT ...) / NOT IN。
• Insert / Update / Delete：维护 MVCC、索引和 WAL。

优化器

优化器采用规则 + 代价模型组合：

• 基于表行数、NDV、列统计估算选择率。
• 支持 ANALYZE table; 显式刷新统计信息。
• 自动选择 SeqScan、IndexScan、IndexOnlyScan。
• 支持等值和范围索引路径选择。
• 支持谓词下推：单表 WHERE 条件可下推到 JOIN 两侧。
• 支持投影下推：JOIN / COUNT 场景只读取必要列。
• 支持 COUNT(*) join-count 快路径，避免构造完整 join tuple。
• 支持 HashJoin 小侧 build 选择。
• 支持 IndexLookupJoin 选择。
• 支持索引有序输出消除多余 ORDER BY Sort。
• 支持 Top-N heap，ORDER BY ... LIMIT N 不需要全量排序。
• 内存不足时 HashJoin 使用 Grace hash partition，不退化为全量 nested-loop spill。