手写数据库内核，见证行列混存的最佳实践

开源无限 2023-11-18

简介

在当今信息化时代，数据已经成为企业和个人最为宝贵的资产之一。为了有效地管理和利用这些数据，数据库技术应运而生，并得到了广泛的应用。目前市场上已经有很多成熟的数据库产品，如 MySQL、Oracle、PostgreSQL 等，它们提供了丰富的功能和性能，满足了不同场景的需求。然而，这些数据库产品的庞大和复杂也让很多人感到困惑和不解，不知道数据库内部的运作机制和原理。

为了解决这个问题，我们开发了 toadb 数据库。toadb 的目标是以最基础的骨架来搭建一个数据库，让人们能够更清晰地了解数据库的本质和运作原理。通过 toadb，我们可以深入了解数据库的内部结构、存储引擎、查询执行等方面的知识，从而为更好地理解和使用其他数据库产品打下坚实的基础。

toadb 是一个轻量级的、开源的关系型数据库，它提供了基本的 SQL 支持和数据存储管理功能。相比于其他成熟的数据库产品，toadb 更加简单和易于理解，适合初学者和数据库内核开发人员使用。通过学习和使用 toadb，我们可以更好地理解数据库的基本原理，掌握数据库的核心技术，为以后的数据库设计和优化工作打下坚实的基础。

使用 toadb，你可以轻松地搭建一个简单的数据库系统，进行数据的存储和查询。toadb 提供了 SQL 语法支持框架，可以满足大部分场景的需求。此外，toadb 还支持行列混合式存储模型，相较于传统的行式存储更适合数据爆炸今天。通过使用 toadb，你可以更深入地了解数据库的内部运作机制和原理，提高自己的技术水平。

toadb 的发展是开源的，我们欢迎任何人对 toadb 进行改进和优化。我们相信，通过社区的力量，toadb 会不断发展和完善，成为一款优秀的数据库产品。我们也希望通过 toadb 的开发和使用，推动数据库技术的普及和发展，为更多的人和企业带来便利和价值。

toadb 是从零开始开发的数据库，本教程适合学习了 C 语言，数据库理论后的学生，也适合工作多年的老同志，不论是学习，兴趣，还是找练手项目，有自己拿得出手的一件作品，也为自己的人生简历增添了份量。

中文教程

开发教程地址^[1] 介绍数据库整体架构，SQL 执行流程，重点对于存储架构，SQL 解析，SQL 执行进行了重点分析；根据代码的更新进度，详细介绍各模块流程，开发流程。

开源代码

代码开源地址^[2]

更新详情

最近更新日期 2023/11/15

更新概要

主要更新了解析树，增加了查询树和执行计划树的生成，这有利于带条件 SQL 和复杂 SQL 处理，同时节点化各个关系代数运算后，有利于执行计划优化的实现。与此同时，更新了执行器，可以通过输入的计划树来执行，不再像以前通过 SQL 解析结果。

更新内容

下面将分别描述更新的内容：

•解析树

在词法分析、语法分析的过程中，会生成解析树，将用不同节点来表示各子句及存储它们传递的信息，这样有助于后续步骤的开展。在开发解析树时，尽可能与存储模型，数据库类型无关，希望做成一个通用的 SQL 解析器，它的输入就是 SQL 字符，输出就是解析树，不像现在每种类型的数据都有一个解析器。真正与数据库，存储模型相关的，是在下一步骤，也就是查询树。

•查询树

查询树，也叫做逻辑执行计划，它的主要是把 SQL 用关系代数进行表达，不同关系代数用不同节点表示，树的层次来表示节点之间的关系。当然在转换的过程中，会对 SQL 中的数据进行检查，比如表是否存在，表的元数据是否一致等；同时还会对一些 SQL 子句进行展开和替换，比如对sellect *
, 将它的结果目标列替换为所有的属性列，这就是常说的重写的过程。当然，在真实数据库中，重写阶段还会对视图，规则等进行处理。

•计划树

计划树，也叫执行计划，或者叫做物理执行计划树，它是一个树状结构，每个节点的类型对应着真正要执行的动作。当然未来会在生成计划树之前，可以再增加一个优化器，对各种可能的 SQL 子句进行重新整理，提升子句，逻辑检查等，这将大大提升执行的效率。

•执行器

之前只对简单的 SQL 执行全表查询，更新后通过输入的物理执行计划，只需要递归的遍历执行计划的节点，按对应节点的类型执行相应动作即可，然后返回 target 对应的元组，更新后执行器更加通用，更加灵活。未来增加索引，优化节点执行动作，增加节点执行接口，这些将变成局部修改。

•内存管理

之前对于动态内存申请并没有进行释放管理，本次增加了一个简单的内存管理，实现一种内存上下文的机制，在上下文使用完成后，会统一释放之前上下文中申请的内存。在程序退出时，会释放所有申请的内存。同时，为了方便调式，对于动态申请的内存，标定了内存的起始和结尾，这样可以方便探测到内存越界的情况。这是一个公共组件，目前只是简单实现，后期与数据库的缓存管理一起进行模块级实现。

举例说明

下面举几个例子说明一下变化情况。

•insert 语句

比如insert into tablename(...) values(...),(...);
,这条插入语句。

之前是通过遍历 values 子句，循环执行执行表的动作。

更新之后，values 子句转换为一个虚似的表，在执行计划中，会有一个表扫描的节点，将返回的元组，再执行一个 ModifyTable 动作。这样就是一个通用的操作，未来很方便的支持insert into ... select ...
这种形式，或者更复杂的形式。

•select 语句如上所述，之前只有一个表的全表扫描。现在对于表扫描，实现一种迭代器的扫描方式，每次可以返回下一个扫描到的元组。对于多表和带条件表达式时，增加控制节点，比如两个表的连接，会增加嵌套循环节点，先从外表中拿到一个元组，再从内表中依次扫描元组，如果两表都有元组，则输出结果，当内表遍历完时，从外表再扫描下一个元组，再从头遍历内表。

目前只有顺序扫描和嵌套循环两种实现路径。

支持情况

目前 toadb 支持的 SQL 语法有：

•DDL

create table tableName(columnName type,...);
drop table tableName;
创建表和删除表的 SQL 支持；

•DML

insert into tablename(...) values(...),(...);
向表中插入数据，可以是一个 values，也可以带多组值；

•DQL

select columName,.. from tableName,.. where qual and qual or qual;
可以查询单个或多个表，带有条件(目前需要带一个条件)，目前对条件并没有处理，只是简单的返回全表。当查询为多表时，会以积的形式返回结果，也就是两边非空的所有列。