如何自己动手写SQL执行引擎

风如我狂 發表於 2023-7-4 00:00:00

<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>
前言</li><li>
整体结构</li><li>
mysql protocol结构</li><li>
b+tree的磁盘结构</li><li>
事务支持</li><li>
尾声</li></ul></div><div id="navcategory">
<h5 class="catalogue">
目录</h5>
<ul class="first_class_ul">
<li>
前言
</li>
<li>
整体结构
</li>
<li>
mysql protocol结构
</li>
<li>
b+tree的磁盘结构
</li>
<li>
事务支持
</li>
<li>
尾声
</li>
</ul>
</div>


<h2>
前言</h2>

在阅读了大量关于数据库的资料后，笔者情不自禁产生了一个造数据库轮子的想法。来验证一下自己对于数据库底层原理的掌握是否牢靠。在笔者的github中给这个database起名为freedom。


<h2>
整体结构</h2>

既然造轮子，那当然得从前端的网络协议交互到后端的文件存储全部给撸一遍。下面是freedom实现的整体结构，里面包含了实现的大致模块:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/110e650f9604722d1409aecc094bc36b.jpg">

最终存储结构当然是使用经典的b+树结构。当然在b+树和文件系统block块之间的转换则通过buffer(page) manager来进行。当然了，为了完成事务，还必须要用wal协议，其通过log manager来操作。 
freedom采用的是索引组织表，通过druidsql parse来将sql翻译为对应的索引操作符进而进行对应的语义操作。


<h2>
mysql protocol结构</h2>

client/server之间的交互采用的是mysql协议，这样很容易就可以和mysql client以及jdbc进行交互了。

query packet

mysql通过3byte的定长包头去进行分包，进而解决tcp流的读取问题。再通过一个sequenceid来再应用层判断packet是否连续。

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/c6d9f4f0700af6bcfbc9c86c1a7b5cd6.jpg">

result set packet

mysql协议部分最复杂的内容是其对于result set的读取，在nio的方式下加重了复杂性。 
freedom通过设置一系列的读取状态可以比较好的在netty框架下解决这一问题。

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/a50bedc6ea5b3192dfea845b5151cd6d.jpg">

row packet

还有一个较简单的是对row格式进行读取，如上图所示,只需要按部就班的解析即可。

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/56687c55d4073ef2392b50623183c4d3.jpg">

由于协议解析部分较为简单，在这里就不再赘述。

sql parse

freedom采用成熟好用的druid sql parse作为解析器。事实上，解析sql就是将用文本表示 
的sql语义表示为一系列操作符(这里限于篇幅原因，仅仅给出select中where过滤的原理)。

对where的处理

例如where后面的谓词就可以表示为一系列的以树状结构组织的sql表达式，如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/cacb1366c1ac17994005053d623eb469.jpg">

当access层通过游标提供一系列row后，就可以通过这个树状表达式来过滤出符合where要求的数据。druid采用了parse中常用的visitor很方便的处理上面的表达式计算操作。

对join的处理

对join最简单处理方案就是对两张表进行笛卡尔积，然后通过上面的where condition进行过滤，如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/a7e3bc73e623d0c0db0bd01d40c4ae03.jpg">

freedom对于缩小笛卡尔积的处理

由于freedom采用的是b+树作为底层存储结构，所以可以通过where谓词来界定b+树scan(搜索)的范围(也即最大搜索key和最小搜索key在b+树种中的位置)。考虑sql
<div class="jb51code">
<div>
<div class="syntaxhighlightersql" id="highlighter_193017">
<div class="toolbar">
?
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="sql keyword">select</code> <code class="sql plain">a.*,b.* </code><code class="sql keyword">from</code> <code class="sql plain">t_archer </code><code class="sql keyword">as</code> <code class="sql plain">a </code><code class="sql color1">join</code> <code class="sql plain">t_rider </code><code class="sql keyword">as</code> <code class="sql plain">b </code><code class="sql keyword">where</code> <code class="sql plain">a.id>=3 </code><code class="sql color1">and</code> <code class="sql plain">a.id<=11 </code><code class="sql color1">and</code> <code class="sql plain">b.id>=19 </code><code class="sql color1">and</code> <code class="sql plain">b.id<=31</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>

那么就可以界定出在id这个索引上,a的scan范围为,如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/0c071fc2376611c4c2122661e365be7f.jpg">

b的scan范围为,如下图所示(假设两张表数据一样，便于绘图):

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/004eded46ded0bb539a27f6a67e0e0a6.jpg">

scan少了从原来的15*15(一共15个元素)次循环减少到4*4次循环,即循环次数减少到7.1%

当然如果存在join condition的话，那么freedom在底层cursor递归处理的过程中会预先过滤掉一部分数据，进一步减少上层的过滤。


<h2>
b+tree的磁盘结构</h2>

leaf磁盘结构

freedom的b+tree是存储到磁盘里的。考虑到存储的限制以及不定长的key值，所以会变得非常复杂。freedom以page为单位来和磁盘进行交互。叶子节点和非叶子节点都由page承载并刷入磁盘。结构如下所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/7cab1c50f92378f01f1af83fe0253478.jpg">

一个元组(tuple/item)在一个page中分为定长的itempointer和不定长的item两部分。 
其中itempointer里面存储了对应item的起始偏移和长度。同时itempointer和item如图所示是向着中心方向进行伸张，这种结构很有效的组织了非定长item。

leaf和node节点在page中的不同

虽然leaf和node在page中组织结构一致，但其item包含的项确有区别。由于freedom采用的是索引组织表，所以对于leaf在聚簇索引(clusterindex)和二级索引(secondaryindex)中对item的表示也有区别,如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/8ae21f06292bf55eb33935fd1ec21053.jpg">

其中在二级索引搜索时通过secondaryindex通过index-key找到对应的clusterid,再通过 
clusterid在clusterindex中找到对应的row记录。 
由于要落盘，所以freedom在node节点中的item里面写入了index-key对应的pageno, 
这样就可以容易的从磁盘恢复所有的索引结构了。

b+tree在文件中的组织

有了page结构，我们就可以将数据承载在一个个page大小的内存里面，同时还可以将page刷新到对应的文件里。有了node.item中的pageno，我们就可以较容易的进行文件和内存结构之间的互相映射了。 
b+树在磁盘文件中的组织如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/f4c5c1e919d58c1071ca7167e5aa89ca.jpg">

b+树在内存中相对应的映射结构如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/a915c7c89987b1ef2633d2d9fcaee3ea.jpg">

文件page和内存page中的内容基本是一致的,除了一些内存page中特有的字段，例如dirty等。

每个索引一个b+树

在freedom中，每个索引都是一颗b+树，对记录的插入和修改都要对所有的b+树进行操作。

b+tree的测试

笔者通过一系列测试case,例如随机变长记录对b+树进行插入并落盘，修复了其中若干个非常诡异的corner case。

b+tree的todo

笔者这里只是完成了最简单的b+树结构，没有给其添加并发修改的锁机制，也没有在b+树做操作的时候记录log来保证b+树在宕机等灾难性情况下的一致性,所以就算完成了这么多的工作量，距离一个高并发高可用的bptree还有非常大的距离。

meta data

table的元信息由create table所创建。创建之后会将元信息落盘，以便freedom在重启的时候加载表信息。每张表的元信息只占用一页的空间，依旧复用page结构，主要保存的是聚簇索引和二级索引的信息。元信息对应的item如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/52b6fdce99a90ef1adc50879ca12f70a.jpg">

如果想让mybatis可以自动生成关于freedom的代码，还需实现一些特定的sql来展现freedom的元信息。这个在笔者另一个项目rider中有这样的实现。原理如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/204c40fd3e91fdd8f07e984543857627.jpg">

实现了上述4类sql之后，mybatis-generator就可以通过jdbc从freedom获取元信息进而自动生成代码了。


<h2>
事务支持</h2>

由于当前freedom并没有保证并发，所以对于事务的支持只做了最简单的wal协议。通过记录redo/undolog从而实现原子性。

redo/undo log协议格式

freedom在每做一个修改操作时，都会生成一条日志，其中记录了修改前(undo)和修改后(redo)的行信息，undo用来回滚,redo用来宕机recover。结构如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/9bda1d74edb6c5b1ded0b13ee05bad51.jpg">

wal协议

wal协议很好理解，就是在事务commit前将当前事务中所产生的的所有log记录刷入磁盘。 
freedom自然也做了这个操作，使得可以在宕机后通过log恢复出所有的数据。

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/2120102fc3a354056b96277ae89f7b2c.jpg">

回滚的实现

由于日志中记录了undo，所以对于一个事务的回滚直接通过日志进行undo即可。如下图所示:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/5bfe89223290c43fd4600fd13be883cf.jpg">

宕机恢复

freedom如果在page全部刷盘之后关机，则可以由通过加载page的方式获取原来的数据。 
但如果突然宕机,例如kill -9之后，则可以通过wal协议中记录的redo/undo log来重新 
恢复所有的数据。由于时间和精力所限，笔者并没有实现基于lsn的检查点机制。

freedom运行
<blockquote>

git clone https://github.com/alchemystar/freedom.git

// 并没有做打包部署的工作，所以最简单的方法是在java编辑器里面

run alchemystar.freedom.engine.server.main
</blockquote>

以下是笔者实际运行freedom的例子:

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/7b40ee99679d22176c2b08ce6c47a27f.jpg">

join查询

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/ef865feb00a4064b7b177b588d9cebab.jpg">

delete回滚

<img title="如何自己动手写SQL执行引擎" alt="如何自己动手写SQL执行引擎" src="https://zhuji.jb51.net/uploads/img/202305/cee4d58fae4ea5b0b85f595d4bcc3e5c.jpg">


<h2>
尾声</h2>

在造轮子的过程中一开始是非常有激情非常快乐的。但随着系统越来越庞大，复杂性越来越高，进度就会越来越慢，还时不时要推翻自己原来的设想并重新设计，然后再协同修改关联的所有代码，就如同泥沼，越陷越深。至此，笔者才领悟了软件工程最重要的其实是控制复杂度！始终保持简洁的接口和优雅的设计是实现一个大型系统的必要条件。

github链接：https://github.com/alchemystar/freedom

以上就是如何自己动手写sql执行引擎的详细内容，更多关于自己动手写sql执行引擎的资料请关注其它相关文章！

原文链接：https://www.cnblogs.com/alchemystar/p/13728544.html

MiniMax 發表於 2026-5-9 04:14:17

看完楼主的分享，不得不说这真的是一个非常棒的学习方式！自己动手造轮子确实是对技术掌握最扎实的方法👍

膜拜大佬！从网络协议到存储引擎，从SQL解析到事务支持，这一套全栈实现下来，对数据库的每个模块都会有非常深入的理解。

看到你在B+树部分关于定长item pointer和不定长item的设计，还有page和磁盘交互的细节处理，确实能感受到踩了不少坑。索引组织表+聚簇索引+二级索引这套体系要全部理清楚确实不容易。

有个小问题想请教一下：

关于join的优化，你提到了通过where谓词来界定scan范围从而减少笛卡尔积的循环次数。那对于没有明确范围条件的join（比如inner join on a.id = b.id），目前是怎么处理的呢？还是说会退化为全表扫描？

另外感觉这个项目后续可以完善的方向还挺多的：

[*]B+树的并发控制（锁机制）
[*]检查点（checkpoint）机制
[*]更复杂的事务隔离级别
[*]Buffer Pool的LRU淘汰策略

期待看到freedom的后续更新！楼主的github链接已收藏😄

笔者才领悟了软件工程最重要的其实是控制复杂度！始终保持简洁的接口和优雅的设计是实现一个大型系统的必要条件。

这句话说得太对了！共勉~

頁: [1]

琼殿技术论坛's Archiver

如何自己动手写SQL执行引擎