Sequoia：从页开始写起的数据库

为什么做

数据库的每一层在教科书里都有讲，但教科书很少讲清楚一层是怎么交给下一层的。 Sequoia 把整条链路放进一个小代码库：SQL 文本从顶上进去，4 KB 的页从底下出来， 每一层只依赖它下面的层。没有任何依赖，所以没有东西藏在某个 crate 后面。

里面有什么

• 语言。 手写的词法分析器和递归下降解析器。支持连接（内连接、左连接、交叉连接）、 GROUP BY/HAVING、DISTINCT、ORDER BY、LIMIT，以及可关联、可嵌套的子查询， NULL 遵循 SQL 的三值逻辑。
• 计划。 WHERE 和 ON 按 AND 拆开，下推到能用上它们的扫描，由它们选择索引。 每个连接依次优先选择索引连接、哈希连接、嵌套循环连接。EXPLAIN 会打印出整棵树。
• 执行。 火山模型：每一步都是一个从下一步拉取行的迭代器，所以 LIMIT 拿够了行就会停止扫描。排序超出内存预算时溢出为外部归并排序，带 LIMIT 时则改用 top-N 堆。
• 三种存储引擎。 默认的分槽页堆表；LSM 树，带跳表 MemTable、布隆过滤器， 以及分层或通用合并；PAX 列存，每个数据块自行挑选编码（游程、位压缩、差分、字典、位图）， 并在压缩状态下直接过滤。
• 索引。 B+ 树，支持分裂、合并和有序链接的叶子，建在堆表或 LSM 表的单列上。
• 持久性。 使用 ARC 置换的缓冲池（也支持 LRU-K 和 CLOCK）， 以及由带校验和的页帧组成的预写日志。每条语句都是原子的，事务支持保存点， 恢复时恰好保留到最后一个有效提交为止的页帧。

怎么验证

崩溃测试在会于任意一次写入时中断的模拟文件上运行每一种语句， 再检查每张表和每个索引对这条语句要么完整呈现、要么完全没有。 差分测试随机生成表结构、行、查询和事务，同时在 Sequoia 和 SQLite 上运行， 两者一旦不一致就失败，并把这个用例打印成可以在 shell 里重放的脚本。

状态

小而易读，不追求快。只有一个连接，所以没有并发控制； 不支持 RIGHT 和 FULL 连接，也不支持多列索引。