首先声明，我不是标题党，我真的是用5000行左右的JS实现了一个轻量级的关系型数据库JSDB，核心是一个SQL编译器，支持增删改查。

 

源代码放到github上了：https://github.com/lavezhang/jsdb

如果你需要修改程序引入新的特性，请严格遵守GPL协议。

如果转发此文，请注明来源。

 

体验页面

 

 

前言

工作太忙，好久没写这种长文章了，难得今年国庆超长，又不便外出，这才有时间“不务正业”。

为什么要用一周的时间写这么个玩意儿？看起来也没什么用处，毕竟，没有哪个系统需要在浏览器中跑一个关系型数据库。

如果要搞一个"年度最无用项目"的颁奖，估计JSDB榜上有名。

 

我一直有一个梦想，要研发一款咱们中国人自己的列式存储分布式数据库！（此处应有掌声^_^）

古人讲，不积跬步无以至千里，JSDB就算探索数据库自研的一个开端吧。

为什么用TypeScript？因为coding效率非常高，跟Python差不多，而且有浏览器就能运行，非常方便，很适合做技术预研，正式开发时再改为C或Rust。

如文章开头所言，JSDB的核心是一个SQL编译器，准确地说，是解释器。学习过《编译原理》的同学，对这个不会陌生。

解释器也是属于编译器的范畴，所以，后面仍然会沿用“SQL编译器”的说法。

概述

按照执行顺序，JSDB的代码由四个部分构成：

1、词法分析，得到 token 列表。参见GitHub源代码，SqlLexer.ts 文件，基于状态机实现，详见 lex_state_flow.xlsx 文件。

2、语法语义分析，得到抽象语法数。参见 SqlParser.ts 文件，自上而下解析，这是行数最多的一个文件。

3、对抽象语法树的执行。参见SqlDatabase.ts文件，以及ast目录下的几十个语法节点的compute(ctx)方法。

4、单元测试和应用范例。test目录和test.html文件里运行着所有的单元测试，index.html文件就是文章开头的体验页面，语法高亮功能基于第三方组件codemirror实现，在 static/codemirror 目录里。

JSDB确实是一个关系型数据库，参照SQL92标准实现，但它并不完整，只实现了最核心的一小部分功能，可以满足日常基本需求。主要特性有：

01、create table 语句

02、insert 语句

03、update 语句

04、delete 语句

05、select 语句，含：distinct / from / join / left join / where / group by / having / order by / limit

06、算数运算符：+、-、*、/、%

07、关系运算符：>、>=、<、<=、=、<>

08、条件运算符：and、or、not

09、其它操作符：like、not like、is null、is not null、between

10、动态占位符：?

11、标准函数，目前只实现了：ifnull、len、substr、substring、instr、concat。
如果需要增加新的标准函数，可以在SqlContext类的构造函数中实现，所有的标准函数都注册到SqlContext.standardFunctions字段中。

尚未实现的重要特性有：

1、with / sub query / exists / alter / truncate 等

2、数据存储。一直在内存中运行，大家可以修改程序，写入浏览器localStorage中。

3、事务。这个需要事务日志来实现，以后再搞，不过在内存中模拟一个，问题也不大。

4、并发锁。JS是单线程，没有真正的并发，有了一个不用实现它的好理由。

5、其它功能。详见大学时的《数据库原理》。

 

如果大家多多点赞，我就把它实现得更加完整。^_^

 

本文针对编译器和数据库的入门读者，写了很多小白的内容，高手请飘过。

 

第一章 词法分析

 

关于词法分析，程序本身并不难。无论何种编程语言，它的词法分析模块一般都不超过300行，有些甚至只有几十行。

很多人喜欢用 lex/yacc/antr 之类的工具来自动生成，我不喜欢，我就是喜欢手撸的感觉。

 

词法分析就是要识别源代码中的一个个token，一般包括：关键字、标识符、字符串、数值、布尔值、空值、运算符、操作符、分隔符。

例如，一条SQL语句：

select name, (total_score / 4) as avg_score from student where id = '010123'

涉及如下token：

关键字：select、as、from、where

标识符：name、total_score、avg_score、student、id

字符串：'010123'

数值：4

运算符：/、=

分隔符：,  ( )

 

如何识别这些token呢？两种办法：硬实现、状态机。

 

硬实现，就是用一大坨的 if/else 识别每一个字符。

举例来说，如果当前字符是一个单引号，程序就认为是一个字符串的开始，于是用一个while循环来判断，直到遇到另一个单引号，表示字符串的结束。

硬实现的最大问题在于，条件分支太多，很容易遗漏或判断错误。

比如，字符串中是要处理转义符的，遇到换行符则要记录错误。

再比如，'>=' 和 '> =' 是不一样的，前者表示大于等于号，后者表示两个运算符：大于号和等于号，因为中间有个空格，而硬写的程序往往会忽略掉这些空白符，什么时候空白符该忽略，什么时候不该忽略，必须把规则一条条列出来，针对处理。

类似的情况还非常多，所以，硬写出来的词法分析程序，无一例外，都是非常复杂的。

给大家看一段用 java 硬实现的字符串识别程序：

 View Code

 

上述java程序是我很久之前写的，整个词法程序漏洞百出。

即使是硬实现，也要提前梳理各种转换关系，既然这样，为什么不用状态机呢？

 

状态机是老一辈计算机科学家发明的理论，基于状态机和BNF产生式，词法分析程序完全可以被形式化了。

一个字符串识别的状态机范例如下：

 

 

一个字符串就涉及4个状态，完整的SQL词法涉及几十个状态，如果都用状态流转图画出来，实在太复杂，所以，一般都改用等价的表格来表示。

我在github上放了一个叫 lex_state_flow.xlsx 的Excel文件，截图如下：

需要特别解释两点：

1、状态2到状态6的名字用紫色标记，因为这几个状态是中间状态，最终不能独立存在。

2、状态转换的单元格有三种颜色：灰色、白色、红色。

      灰色表示回到初始状态；

      白色表示正数状态，转换状态时，前面的缓存内容作为一个token，当前新字符进入新的状态；比如，当前状态是 TK_IDENTITY，这时输入一个字符 '>'，则缓冲区的内容得到一个标识符token，新输入的 '>' 字符进入 TK_GT 状态。

      红色表示负数状态，转换状态时，前面的内容加上当前字符一起进入新的状态。比如，当前状态是 TK_GT，这时输入一个字符 ‘=’，则缓冲区的内容 '>' 加上新输入的 '='，得到 '>=' ，进入新的状态 TK_GE，表示大于等于。

 

词法分析的核心，正是这个状态表格。要完成这样一张表格，看着容易，实际并不容易，我也是花了一天时间。因为一旦遗漏了某个状态或输入字符，整个表格都要改一遍，撸得手都起茧子了。

完成状态表格后，基于此实现的词法扫描程序，就可以非常简单了。文件名为 SqlLexer.ts，代码如下：

 

 View Code

 

细心的同学可能会发现，代码里的关键字状态，并没有出现在状态表格中。

原则上来讲，每个关键字都是一个单独的状态。但是，如果都列入状态表格，这个表格就超级复杂了。比如，为了识别一个关键字select，要依次检查连续字符 ‘s’  'e'  'l'  'e'  'c'  't' ，即使到了最后一个字符 't' ，也不意味着结束，后面跟上一个数字 '1'，立马就不是关键字了，而是一个普通的标识符 select1。而JSDEB一共支持38个关键字，都要并入表格，简直难以想象。所以，通常的做法是，先统一作为标识符来识别，完成一个token时，再进一步判断是否为某个关键字，而在状态表格中就不画了。

 

一个token用一个三元组来表达，在TypeScript中是Tuple类型，实际就是JavaScript中的数组。这里有三个值，分别是number、string、number类型。

第0个值，number类型，表示token的类型，对应于状态表格中的状态id；

第1个值，string类型，表示token的内容，对于字符串 'abc' 来说，存的不是 abc，而是 'abc'，也就是说，原原本本保存，后面在执行的时候才会翻译为 abc；

第2个值，number类型，表示token所在的行号，提示词法错误的时候，可以明确告知在哪一行。

有的同学可能会问，为什么不用一个class来表示。其实也可以用class表示，但是，扫描一段源代码，得到的token非常多，如果用class表示，会浪费更多的资源，不如用数组，返璞归真，简单实用。

 

用一组单元测试来验证程序是否正确。

代码中的Assert类是一个简单的断言类，用于单元测试中的条件检查。

/test/SqlLexerTest.ts 文件包含了所有词法扫描的测试用例。截取一段代码如下：

 View Code

 

到这里词法分析就结束了，得到一个token列表，接下来，会对这个token列表进行扫描，也就是语法解析。

 

第二章 语法解析 

 

语法解析也叫语法分析，读入token列表，输出抽象语法树。

在编译器设计中，以抽象语法树的形式构造一条SQL语句。例如SQL：

SELECT id, t.stf_name AS name FROM student t WHERE id = 123

会被解析成如下树结构：

 

自上而下，递归解析，识别出每一个节点。

每种语法节点都是一个单独的class，比如，SqlSelectNode、SqlFromNode、SqlWhereNode、SqlIdentityNode、StringNumberNode，等等。

数量有点多，一共39个。这39个类都是继承自语法节点基类SqlNode。

 View Code

 

详细介绍一下：

value字段，用于保存节点的值。SqlStringNode存的是类似 'abc'这样的值，SqlNumber存的是类似 123 这样的值，SqlSelectNode存的是 select。

line字段，用于保存节点所在的行号。这个行号是从前一阶段的词法分析中得到的，就是token三元组的最后一个值。

nodes字段，用于保存子节点。例如，SqlExpAddNode的value是 + 或 - ，它的nodes是两个表达式节点，表示这个表达式的结果相加或相减。

compute方法，用于计算表达式的值。例如，id = 3，如果运行时id的值为3，则运行时返回True，否则返回False。再例如，a * 3，如果运行时a的值为10，则运行时返回30。

typeDeriva方法，用于类型推导。如果数据库列id是number类型，那么 id + 100 的结果也应该是numer类型；如果 id列是varchar类型，那么 id + 100也是varchar类型。这就是类型推导。

类型推导非常重要，主要用于类型安全检查。比如，count(*)的结果一定是numer类型，如果写出 substr(count(*),1) 这样的表达式，就应该给出语法错误。此外，类型推导还可以用于提前确定查询结果集中每一列的类型，构造好结果集，以容纳接下来返回的数据。比如，对于C#或Java，查询数据库后得到DataTable或RecordSet，可以获取到每一列的类型信息，这些类型信息在正式查询数据库之前通过语法分析就已经得到了。

推导出的类型，理论上来说，应该跟compute方法返回的值，保持一致。

 

实现各个语法节点子类的时候，重点是重写compute和typeDeriva这两个方法。

 

接下来讲如何构造这些语法节点。

 

有的节点具有明确的特征，比如 select节点，以关键字SELECT开头，只要扫描这个关键字，就可以认为是一条SELECT语句，然后按照SELECT语句的规则继续往下扫描。

有的节点则不那么容易判断，具有二义性。

比如 减号 -，如果是 a - b，则表示相减；如果是a = -b，则表示负号。

再比如关键字 AND，如果是 a AND b，则表示条件与；如果是 a BETWEEN b AND c，则表示一个数值范围或字符串范围。

这种情况下，需要通过上下文分析、优先级判断、消除文法左递归的办法，来消除二义性。

 

JSDB实现的只是SQL92的子集，SELECT语法如下：

由于简化了SELECT语法，所以相对来说还算简单。唯一有难度的地方，在于表达式的解析，采用的方法是抄自“龙书”《编译原理》。

自上而下，根据优先级，依次解析 exp_or、exp_and、exp_eq、exp_rel、exp_add、exp_mult、exp_unary、factor。

 

先看一个简单点的方法，parseExpRefNode，用于解析类似 t.id 这样的字段引用表达式。

先尝试解析第一个标识符，然后是一个分隔符点，最后是结尾的标识符。如果解析失败，则添加一个SqlError。

 View Code

 

接下来看parseExpOrNode、parseExpAndNode两个方法，分别用于解析条件OR和AND的节点。由于函数是一层层调用进去的，所以，实际上的构造节点顺序是反过来的，从factor开始，然后才依次是 unary、mult、add、rel、req、and、or 。

先是从左到右挨个解析，放到一个列表中，然后把列表中的元素转换为一棵二叉树，函数返回的是这棵二叉树的根节点。

 

parseExpOrNode类：

 View Code

 

 parseExpAndNode类：

 View Code

 

看着有点晕？没关系，我画一张图，演示一下表达式 a OR b AND c OR d OR e 是如何转换为二叉树的。

测试代码：

Assert.runCase('parse exp', function () {
    let parser = new SqlParser("a OR b AND c OR d OR e");
    let node = parser.parseExpOrNode(null);
    console.log(node.toString());
});

输出如下二叉树结构：

|--SqlExpOrNode@1：or
    |--SqlExpOrNode@1：or
        |--SqlExpOrNode@1：or
            |--SqlIdentityNode@1：a
            |--SqlExpAndNode@1：and
                |--SqlIdentityNode@1：b
                |--SqlIdentityNode@1：c
        |--SqlIdentityNode@1：d
    |--SqlIdentityNode@1：e

构造该二叉树的步骤如下图所示：

 

构造完抽象语法树后，不用生成机器码，直接在语法树上计算。

 

第三章 计算语法树

 

前面提到过，语法树节点基类SqlNode里有一个compute方法，用于计算节点的值，子类会重写该方法，实现具体的计算逻辑。

语法节点太多了，咱们只讲几个关键节点的计算逻辑：

 

SqlNumberNode类，根据value字段的值是否有小数点，相应返回parseInt(this.value)或parseFloat(this,value)。

 View Code

 

SqlStringNode类，根据value字段的值返回字符串，去掉首尾的单引号，如果有转义符，要进行转义。

 View Code

 

SqlExpRelNode类，计算左右两个子节点的值，比较其大小，返回True或False。

 View Code

 

SqlExpAddNode类，计算左右两个子节点的值，根据value字段的值是 '+' 还是 '-'，相应执行相加或相减。

 View Code

 

SqlExpMulNode类，计算左右两个子节点的值，根据value字段的值是 '*' 、'/' 还是 '%'，相应执行相乘、相除、取余。

SqlExpAndNode类，计算左右两个子节点的值，如果都为True，才返回True，否则返回False。

SqlExpOrNode类，计算左右两个子节点的值，如果都为False，才返回False，否则返回True。

SqlExpUnaryNode类，一元操作符，只有一个节点，计算其值。根据操作符的值是'+'、'-'、'not'，执行相应的取正、取负、取反逻辑。

SqlExpFuncNode类，执行函数。首先从SqlContext.standardFunctions字段取一下，如果取到了，说明是标准函数，直接执行，否则再看是不是聚合函数。聚合函数的执行比较复杂，咱们单独讲。

SqlInsertNode类，执行插入逻辑，返回受影响行数。

SqlUpdateNode类，执行更新逻辑，返回受影响行数。

SqlDeleteNode类，执行删除逻辑，返回受影响行数。

SqlSelectNode类，执行查询逻辑，返回一个二维表SqlDataTable实例。这个最复杂，咱们接下来重点讲。

其它语法节点的执行逻辑，请参见源代码。

 

接下来，重点讲一下SqlSelectNode类和SqlExpFuncNode类的实现逻辑，也就是SELECT语句到底是怎么实现数据查询的，这货老复杂了，烧了不少脑细胞，大伙一定要给个赞。

 

第四章 SELECT语句

 

一条SELECT语句的执行，可以分为如下几个步骤：

1、根据 from 节点，以及可能存在的 join 节点，合并出一张宽表（fullTable）。这里我没有做任何优化，直接生成一个笛卡尔积，所以，测试的数据量千万不要太大，否则，运行的速度够你酸爽的~~~

 View Code

 

2、如果有 join节点，执行联结规则。JSDB只支持 join 和 left join 这两种最常用的联结方式，其它联结方式暂不支持。执行on条件节点，如果返回False，表示没有join上，这时再判断是join还是left join，如果是join，就直接删除；如果是left join，就填上null值。

不太好理解的是repeatJoinRows这个字段，这是为了处理重复join的问题。比如，from表有一条记录，外键ID对应一个 join表中的两条记录，也就是说，join表存在id重复的情况。针对这种情况，需要把重复join的数据也保留下来。

 View Code

 

3、如果有 where 节点，执行筛选规则。就是执行SqlWhereNode节点，不符合条件的记录，直接删除。

 View Code

 

4、如果有 group by 节点，则执行分组规则。这个最复杂，分为以下几个步骤：

    4.1 首先要提取出 fields、having、orderby 这三个节点中的聚合表达式。

    4.2 根据 group by的节点，以及上一步得到的聚合表达式列表，构造一张分组计算中间表，写入上下文中，后面聚合函数计算时会用到。

    4.3 遍历宽表fullTable，计算分组中间表的值，得到分组中间表groupByMidTable。这段代码不好理解，实际逻辑是在SqlExpFuncNode类中。为了遍历一次就能算出所有聚合表达式的值，我封装了一个SqlGroupByValue类，该类用于记录一个聚合表达式的当前最新的count行数、sum汇总、distinctValues去重值列表，以及当前最新值，这个当前最新值可以是行数、汇总，也可以是最大值、最小值、平均值，取决于具体的聚合函数。所以，一定要注意，普通SqlDataTable的单元值是string或number，但是分组中间表的单元值是SqlGroupByValue。

    4.4 基于分组中间表groupByMidTable，根据fields节点进行计算，得到结果表resultTable。为什么要再算一遍？因为，对于 count(*) * 10 这样的表达式，在4.3小节中实际只计算了count(*)，乘以10的步骤是在这里计算的。另外，并不是所有聚合表达式都是要返回的，有些聚合表达式是在having或order节点中出现的，并不在fields节点中，所以，必须在这一步中集中处理一下。

 View Code

 

涉及的函数表达式，尤其是聚合函数表达式，计算代码如下：

 View Code

 

5、如果没有 group by 节点，直接在where筛选后的fullTable上根据fields节点进行计算，得到结果表resultTable。这个就简单很多了。

 View Code

 

6、如果有 order by 节点，则对结果表resultTable进行排序。由于排序规则可能包含多个条件，这里要分为三个步骤来计算：

    6.1 遍历resultTable表，每一行数据都得到一个orderByValues数组，包含了排序要用的值。如果是多个排序条件，数组就包含多个值。

    6.2 计算每个排序条件的方向，默认是asc。

    6.3 根据排序表达式的值，以及排序方向，对数据行进行排序。这里调用的是Array类的sort方法，传入一个function，实现自定义排序。

 View Code

 

7、如果有 limit 节点，则返回指定范围的数据，也就是分页时要用的东西。如果是limit n，则返回前面n行数据；如果是limit m, n，则从第m行开始，返回n行数据的。

 View Code

 

到这里就得到最终的结果表了。

 

相对于SELECT语句，其它语句就简单多了。

 

第五章 其它语句

 

DELETE语句的执行分为两步：执行where筛选，然后根据row.id进行删除。

 View Code

 

UPDATE语句也分为两步：执行where筛选，然后set规则更新指定列的数据。

 View Code

 

INSERT语句也分为两步：根据表构造创建一个空行，然后更新指定列的数据。

 View Code

 

CREATE TABLE语句，在 SqlDatabase 中创建一个新的 SqlDataTable 实例。

 View Code

 

至此，几个主要的语句都介绍了。

最后，我们写几个测试范例，展示一下运行结果，这几个测试范例，在文章开头的“体验页面”上都有展示。

 

第六章 程序展示

通过JS创建三张表：t_gender（性别字典表）、t_dept（部门字典表）、t_staff（员工表）。

var database = new SqlDatabase();
database.execute("create table t_gender(id number, name varchar(100))");
database.execute("create table t_dept(dept_id number, dept_name varchar)");
database.execute("create table t_staff(id varchar, name varchar, gender number, dept_id number)");

database.execute("insert into t_gender(id, name)values(1, 'Male')");
database.execute("insert into t_gender(id, name)values(2, 'Female')");

database.execute("insert into t_dept(dept_id, dept_name)values(101, 'Tech')");
database.execute("insert into t_dept(dept_id, dept_name)values(102, 'Finance')");

database.execute("insert into t_staff(id, name, gender, dept_id)values('016001', 'Jack', 1, 102)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016002', 'Bruce', 1, null)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016003', 'Alan', null, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016004', 'Hellen', 2, 103)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016005', 'Linda', 2, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016006', 'Royal', 3, 104)");

 

然后准备几条范例sql，方便大家执行查询，也可以自己写一个新的sql。

SELECT
    s.id,
    s.name,
    ifnull(s.gender, '--') AS gender_id, /*处理空值*/
    (CASE g.name WHEN 'Male' THEN '男' WHEN 'Female' THEN '女' ELSE '未知' END) AS gender_name,
    s.dept_id,
    d.dept_name
FROM t_staff s
LEFT JOIN t_gender g ON g.id=s.gender
LEFT JOIN t_dept d ON d.dept_id=s.dept_id
WHERE d.dept_name IS NOT NULL
LIMIT 3

 

执行结果：

 

文章到这里就结束了，欢迎大家指正，多给Star，多给赞 ^_^