代码拉取完成，页面将自动刷新
[toc]
toad database system，“癞蛤蟆”数据库，正如其名，我们想吃天鹅肉，它是一款从零完全开始手写的数据库，同时在每做一步都会有教程和分析，期待更多人加入，一起同行。
地址：https://senllang.blog.csdn.net/category_12338586.html
介绍数据库整体架构，SQL执行流程，重点对于存储架构，SQL解析，SQL执行进行了重点分析； 根据代码的更新进度，详细介绍各模块流程，开发流程。
源码规模
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 47 3264 2534 12860
C/C++ Header 55 750 789 1838
yacc 1 93 33 828
Bourne Shell 6 144 128 475
Markdown 4 119 0 376
JSON 4 0 0 244
lex 3 30 43 243
make 4 63 84 127
-------------------------------------------------------------------------------
SUM: 124 4463 3611 16991
-------------------------------------------------------------------------------
benchmark 测试结果，采用TPC-B的测试模型。
初始化数据，scale=10, 最大的toad_accounts表有100万条数据，耗时如下：
insert into toad_accounts aid:1000000
load toad_accounts endTime: 2024-03-22 23:39:38
begin time:2024-03-22 08:26:39
end time :2024-03-22 23:39:38
---------------------------------------------------------
load data finish.
total elapse time: 15h12m59s
create table elapse time: 1s
total of load table data elapse time: 15h12m58s
total of load toad_branches data elapse time:
total of load toad_tellers data elapse time:
total of load toad_accounts data elapse time: 15h12m58s
real 912m58.523s
user 13m1.022s
sys 15m15.532s
运行测试程序，执行了600s,tps=0.27。
Test process elapse(s) 594 tps=.27
---------------------------------------------------------
test end.............
begin time: 2024-03-24 08:44:00
end time: 2024-03-24 08:54:02
Test process total runtimes(s) :10m2s
Test process total transactions :168
Test process average tps=.27
主要更新了解析树，增加了查询树和执行计划树的生成，这有利于带条件SQL和复杂SQL处理，同时节点化各个关系代数运算后，有利于执行计划优化的实现。与此同时，更新了执行器，可以通过输入的计划树来执行，不再像以前通过SQL解析结果。
下面将分别描述更新的内容：
在词法分析、语法分析的过程中，会生成解析树，将用不同节点来表示各子句及存储它们传递的信息，这样有助于后续步骤的开展。在开发解析树时，尽可能与存储模型，数据库类型无关，希望做成一个通用的SQL解析器，它的输入就是SQL字符，输出就是解析树，不像现在每种类型的数据都有一个解析器。真正与数据库，存储模型相关的，是在下一步骤，也就是查询树。
查询树，也叫做逻辑执行计划，它的主要是把SQL用关系代数进行表达，不同关系代数用不同节点表示，树的层次来表示节点之间的关系。当然在转换的过程中，会对SQL中的数据进行检查，比如表是否存在，表的元数据是否一致等；同时还会对一些SQL子句进行展开和替换，比如对
sellect *, 将它的结果目标列替换为所有的属性列，这就是常说的重写的过程。当然，在真实数据库中，重写阶段还会对视图，规则等进行处理。
计划树，也叫执行计划，或者叫做物理执行计划树，它是一个树状结构，每个节点的类型对应着真正要执行的动作。当然未来会在生成计划树之前，可以再增加一个优化器，对各种可能的SQL子句进行重新整理，提升子句，逻辑检查等，这将大大提升执行的效率。
之前只对简单的SQL执行全表查询，更新后通过输入的物理执行计划，只需要递归的遍历执行计划的节点，按对应节点的类型执行相应动作即可，然后返回target对应的元组，更新后执行器更加通用，更加灵活。 未来增加索引，优化节点执行动作，增加节点执行接口，这些将变成局部修改。
之前对于动态内存申请并没有进行释放管理，本次增加了一个简单的内存管理，实现一种内存上下文的机制，在上下文使用完成后，会统一释放之前上下文中申请的内存。在程序退出时，会释放所有申请的内存。同时，为了方便调式，对于动态申请的内存，标定了内存的起始和结尾，这样可以方便探测到内存越界的情况。 这是一个公共组件，目前只是简单实现，后期与数据库的缓存管理一起进行模块级实现。
下面举几个例子说明一下变化情况。
比如
insert into tablename(...) values(...),(...);,这条插入语句。
之前是通过遍历values子句，循环执行执行表的动作。
更新之后，values子句转换为一个虚似的表，在执行计划中，会有一个表扫描的节点，将返回的元组，再执行一个ModifyTable动作。这样就是一个通用的操作，未来很方便的支持
insert into ... select ...这种形式，或者更复杂的形式。
目前只有顺序扫描和嵌套循环两种实现路径。
目前toadb支持的SQL语法有：
create table tableName(columnName type,...);drop table tableName;创建表和删除表的SQL支持；
insert into tablename(...) values(...),(...);向表中插入数据，可以是一个values，也可以带多组值；
select columName,.. from tableName,.. where qual and qual or qual;可以查询单个或多个表，带有条件(目前需要带一个条件)，目前对条件并没有处理，只是简单的返回全表。当查询为多表时，会以积的形式返回结果，也就是两边非空的所有列。
- 原来传统的行存储模式，也叫NSM（N-Arr storage model），每一行的数据是连续存放在一起；
- 改变后的存储模式为行列混合存放模式 PAX(partition attributes across), 这结合了DSM(Decomposition storage model ) 和 NSM的优势；
- 创建表时，不仅创建表数据文件，还要创建分组管理文件，这两者是一一对应的
- 在插入数据时，按分组查找空闲空间，如果没有时，先新建分组，再插入数据；
- 查询时，按分组来扫描数据；当前只支持 select * 配匹；如果按列时，那么只从磁盘加载对应列的数据即可，这就是PAX模式的优势；
- 删除表时，当然也是需要成对删除表数据文件和分组文件
create table tablename(columnname type, ...);
drop table tablename;
insert into tablename(columnname,...) values(val...);
select columnname,... from tablename;
当前查找支持全部列表，不支持部分列名的过滤。
int/integer, 整型数字，如88，99等；
char, 单个字符，如'a','b'等，用‘’包括起来；
varchar, 字符串，也是用‘’包括；
bool，布尔值，用数字表示，0是false，非零为true，显示为F/T；
完成flex/bison语法解析的框架，能够解析几个关键词，字符串，数字。
分为两部分， 词法分析器scanner 语法分析器grammar
支持DDL: create table name (column type,..); drop table name;
支持DML: select */ column, ... from tablename; insert into tablename(column...) values(...);
在toadb/src 当前目录下执行
make parser 如果没有做修改的话，可以跳过这一步，因为库中已经包含编译后的文件
在toadb/src 目录下执行
make
在toadb/src 当前目录下执行
[senllang@hatch src]$ ./toadb-0-01 -D ./toadbtest
Welcome to Toad Database Manage System.
cwd :/mnt/sda1/data/gitdata/hatch/Coder/operator/toadb/src
datadir: [./toadbtest]
toadb>
-D 参数指定数据文件存放的目录，最后不需要加'/', 最好是绝对路径; 之后创建的表，对应的表文件就会存放在此目录下
toadb> create table student(sid integer, sname varchar, ssex char);
toadb> select sid,sname,ssex from student;
return 0 rows
toadb> insert into student(sid,sname,ssex) values(1,'lilei','M');
toadb> select sid,sname,ssex from student;
|sid-|sname|ssex|
| 1|lilei| M|
return 1 rows
toadb> insert into student(sid,sname,ssex) values(2,'hanmeimei','F');
toadb> insert into student(sid,sname,ssex) values(3,'richel','F');
注意： 目前数据中不能带有空格，这是在词法分析中的问题。 比如'han meimei'这样就会解析错误。
toadb> select sid,sname,ssex from student;
|sid-|sname----|ssex|
| 1| lilei| M|
| 2|hanmeimei| F|
| 3| richel| F|
return 3 rows
toadb> drop table student;
toadb> quit
最后输入quit 回车后，退出toadb client。
功能 事务机制，保证事务的原子性，一致性；
限制
功能 执行计划功能开发，在SQL解析后，重写查询树，生成执行计划树，执行器按照执行计划进行；
限制
功能： 完善SQL解析，支持select ... from ... where ... 简单语句；、
限制：
暂不支持 table.column带 .的格式；
功能：行列混合的存储模式
功能：支持创建表，删除表，插入数据，删除数据 数据库特性：客户端，词法/语法解析，SQL执行，数据字典，存储管理
词法分析器和语法分析器使用了著名的开源工具flex和bison组合，flex能够按照正则表达式规则解析出关键字，标识符，以及其它字符串；而bison则通过它的语法推导规则，将各个部分解析成一个个表达式，每个表达式形成逆波兰式的抽象语法树。
词法分析器是向前看一个字符，所以对于规则在文件中的前后顺序就有要求。比如标识符字串如果放在操作符规则之后，那么在匹配时就会先匹配到操作符的分号，此时就会执行操作符的规则，而把前面的字符串会丢掉，把两者换个顺序就会优先匹配标识符，当下一个字符为分号时，先执行标识符的动作，再取分号进行分析。
语法分析器在编写过程中遇到两个问题： （1）语法分析器规则里要使用当前表达式的值时，需要给表达式定义类型，默认是yylval为整型，如果是字符串时，就需通过%union定义，然后在token里绑定类型； （2）语法分析器第二部分规则定义部分，规则推导出的内容必须是词法分析器返回的内容，比如列名和类型中间是空格，但是空格在词法分析器中已经过滤掉了，就不能用空格来分隔了。
执行过程涉及到执行模块和存储模块，还有数据字典。目前对于数据字典，简单存储在表文件中。
在程序启动时指定，使用-D参数；
文件以块为单位存储，第一个块是存储元数据信息，也就是数据字典内容；
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
