如何用5000行JS撸一个关系型数据库

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

 

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

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

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

 

体验页面

 如何用5000行JS撸一个关系型数据库

 

前言


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

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

如果要搞一个"年度最无用项目"的颁奖,估计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 硬实现的字符串识别程序:

if (c == ‘\‘‘) {
    while (pos < len) {
        c = source.charAt(pos++);
        if (c == ‘\\‘) {
            c = source.charAt(pos++);
            if (c == ‘n‘) {
                buf.append(‘\n‘);
            } else if (c == ‘r‘) {
                buf.append(‘\r‘);
            } else if (c == ‘t‘) {
                buf.append(‘\t‘);
            } else {
                buf.append(c);
            }
        } else if (c == ‘\‘‘) {
            return addToken(buf.toString(), SqlConstants.STRING, line);
        } else {
            buf.append(c);
        }
    }
}

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

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

 

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

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

 

如何用5000行JS撸一个关系型数据库

 

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

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

如何用5000行JS撸一个关系型数据库

需要特别解释两点:

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

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

      灰色表示回到初始状态;

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

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

 

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

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

const TK_START = 0;  //起始
const TK_ERROR = 1;  //错误

const TK_IDENTITY = 7;  //标识符(下划线当作字母处理)
const TK_INT = 8;  //整数(不支持科学计数法)
const TK_FLOAT = 9;  //浮点数(不支持科学计数法)

const TK_GT = 10; //操作符:大于 >
const TK_LT = 11; //操作符:小于 <
const TK_GE = 12; //操作符:大于等于 >=
const TK_LE = 13; //操作符:小于等于 <=
const TK_EQ = 14; //操作符:等于 =
const TK_NE = 15; //操作符:不等于 <>
const TK_ADD = 16; //操作符:加 +
const TK_SUB = 17; //操作符:减 -
const TK_MUL = 18; //操作符:乘 *
const TK_DIV = 19; //操作符:除 /
const TK_MOD = 20; //操作符:模(取余) %
const TK_MOVE_LEFT = 21; //操作符:左移 <<
const TK_MOVE_RIGHT = 22; //操作符:右移 >>

const TK_DOT = 23; //分隔符:点 .
const TK_OPEN_PAREN = 24; //分隔符:左圆括号 (
const TK_CLOSE_PAREN = 25; //分隔符:右圆括号 )
const TK_COMMA = 26; //分隔符:逗号 ,

const TK_HOLD = 27; //占位符 ?
const TK_COMMENT = 28; //注释 /**/
const TK_STRING = 29; //字符串  ‘abc‘

const TK_SELECT = 50; //关键字:select
const TK_FROM = 51; //关键字:from
const TK_WHERE = 52; //关键字:where
const TK_AS = 53; //关键字:as
const TK_DISTINCT = 54; //关键字:distinct
const TK_LEFT = 55; //关键字:left
const TK_JOIN = 56; //关键字:join
const TK_ON = 57; //关键字:on
const TK_CASE = 58; //关键字:case
const TK_WHEN = 59; //关键字:when
const TK_THEN = 60; //关键字:then
const TK_ELSE = 61; //关键字:else
const TK_END = 62; //关键字:end
const TK_IS = 63; //关键字:is
const TK_NOT = 64; //关键字:not
const TK_NULL = 65; //关键字:null
const TK_TRUE = 66; //关键字:true
const TK_FALSE = 67; //关键字:false
const TK_AND = 68; //关键字:and
const TK_OR = 69; //关键字:or
const TK_BETWEEN = 70; //关键字:between
const TK_IN = 71; //关键字:in
const TK_LIKE = 72; //关键字:like
const TK_GROUP = 73; //关键字:group
const TK_BY = 74; //关键字:by
const TK_HAVING = 75; //关键字:having
const TK_ORDER = 76; //关键字:order
const TK_ASC = 77; //关键字:asc
const TK_DESC = 78; //关键字:desc
const TK_LIMIT = 79; //关键字:limit
const TK_INSERT = 80; //关键字:insert
const TK_INTO = 81;//关键字:into
const TK_VALUES = 82;//关键字:values
const TK_UPDATE = 83;//关键字:update
const TK_SET = 84;//关键字:set
const TK_DELETE = 85;//关键字:delete
const TK_CREATE = 86;//关键字:create
const TK_TABLE = 87;//关键字:table

/**
 * 词法状态流转图。
 * 详见:lex_state_flow.xlsx 文件。
 */
const STATE_FLOW_TABLE = [
    [0, 0, 8, 7, 1, 4, 1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, 1],
    [0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-2, -2, -2, -2, -2, -2, -2, -2, -2, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2],
    [-2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -28, -2, -2, -2, -2, -2, -2, -2, -2, -2],
    [-5, -1, -5, -5, -5, -29, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
    [-5, -1, -5, -5, -5, -29, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
    [-5, -1, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
    [0, 0, -7, -7, 23, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
    [0, 0, -8, -1, -9, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
    [0, 0, -9, -1, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -22, -1, -12, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -15, -21, -13, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -1, -1, -1, -1, -1, -1, 24, 25, 26, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -2, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 1, 7, -1, -1, -1, -1, -1, 18, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, 18, -1, -1, -1, -1, -1, 24, 25, -1, 27, -1],
    [0, 0, 1, 7, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, -1, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, -1, -1, -1, -1, -1, -1, 24, -1, -1, 27, -1],
    [0, 0, 1, -1, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, -1, 25, 26, -1, -1],
    [0, 0, 8, 7, -1, 4, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
    [0, 0, 1, 7, -1, -1, -1, 16, -1, -1, 19, -1, 10, 11, 14, -1, 25, 26, -1, -1]
];

/**
 * SQL词法分析类。
 */
class SqlLexer {

    /**
     * 扫描指定的SQL语句,返回所有单词。
     * 用一个元组来表示单词的三个字段:类型(状态)、内容、行号(从1开始)。
     * @param sql 要扫描的SQL语句。
     */
    public scan(sql: string): Array<[number, string, number]> {
        let tokens = new Array<[number, string, number]>();
        let pos = 0;
        let len = sql.length;
        let buf = ‘‘;
        let c = ‘‘;
        let j = 0;
        let state = TK_START;
        let beginLine = 1;
        let totalLine = 1;

        while (pos < len) {
            c = sql[pos++];
            if (c == ‘ ‘ || c == ‘\t‘ || c == ‘\r‘) {
                j = 0;
            } else if (c == ‘\n‘) {
                j = 1;
            } else if (c >= ‘0‘ && c <= ‘9‘) {
                j = 2;
            } else if ((c >= ‘a‘ && c <= ‘z‘) || (c >= ‘A‘ && c <= ‘Z‘) || c == ‘_‘) {
                j = 3;
            } else if (c == ‘.‘) {
                j = 4;
            } else if (c == ‘\‘‘) {
                j = 5;
            } else if (c == ‘\\‘) {
                j = 6;
            } else if (c == ‘+‘) {
                j = 7;
            } else if (c == ‘-‘) {
                j = 8;
            } else if (c == ‘*‘) {
                j = 9;
            } else if (c == ‘/‘) {
                j = 10;
            } else if (c == ‘%‘) {
                j = 11;
            } else if (c == ‘>‘) {
                j = 12;
            } else if (c == ‘<‘) {
                j = 13;
            } else if (c == ‘=‘) {
                j = 14;
            } else if (c == ‘(‘) {
                j = 15;
            } else if (c == ‘)‘) {
                j = 16;
            } else if (c == ‘,‘) {
                j = 17;
            } else if (c == ‘?‘) {
                j = 18;
            } else {
                j = 19;
            }

            //如果新状态的值小于0,表示带着当前缓存区的内容,直接转换到新的状态;
            //如果新状态的值大于等于0,则用当前缓冲区的内容构造一个旧状态的单词,然后从当前字符开始进入新的状态。
            let nextState = STATE_FLOW_TABLE[state][j];
            if (nextState < 0) {
                buf += c;
            } else {
                let token = this.newToken(state, buf, beginLine);
                if (token) {
                    tokens.push(token);
                    beginLine = totalLine;
                }
                buf = j > 1 ? c : ‘‘;
                if (c == ‘\n‘) {
                    beginLine++;
                }
            }
            state = Math.abs(nextState);

            //处理最后一个单词
            if (pos >= len) {
                let token = this.newToken(state, buf, beginLine);
                if (token) {
                    tokens.push(token);
                    beginLine = totalLine;
                }
            } else if (c == ‘\n‘) {
                totalLine++;
            }
        }

        return tokens;
    }

    private newToken(state: number, value: string, line: number): [number, string, number] {
        if (value.length <= 0) {
            return null;
        }
        if (state == TK_IDENTITY) {
            value = value.toLowerCase();
            switch (value) {
                case ‘select‘:
                    state = TK_SELECT;
                    break;
                case ‘from‘:
                    state = TK_FROM;
                    break;
                case ‘where‘:
                    state = TK_WHERE;
                    break;
                case ‘as‘:
                    state = TK_AS;
                    break;
                case ‘distinct‘:
                    state = TK_DISTINCT;
                    break;
                case ‘left‘:
                    state = TK_LEFT;
                    break;
                case ‘join‘:
                    state = TK_JOIN;
                    break;
                case ‘on‘:
                    state = TK_ON;
                    break;
                case ‘case‘:
                    state = TK_CASE;
                    break;
                case ‘when‘:
                    state = TK_WHEN;
                    break;
                case ‘then‘:
                    state = TK_THEN;
                    break;
                case ‘else‘:
                    state = TK_ELSE;
                    break;
                case ‘end‘:
                    state = TK_END;
                    break;
                case ‘is‘:
                    state = TK_IS;
                    break;
                case ‘not‘:
                    state = TK_NOT;
                    break;
                case ‘null‘:
                    state = TK_NULL;
                    break;
                case ‘true‘:
                    state = TK_TRUE;
                    break;
                case ‘false‘:
                    state = TK_FALSE;
                    break;
                case ‘and‘:
                    state = TK_AND;
                    break;
                case ‘or‘:
                    state = TK_OR;
                    break;
                case ‘between‘:
                    state = TK_BETWEEN;
                    break;
                case ‘in‘:
                    state = TK_IN;
                    break;
                case ‘like‘:
                    state = TK_LIKE;
                    break;
                case ‘group‘:
                    state = TK_GROUP;
                    break;
                case ‘by‘:
                    state = TK_BY;
                    break;
                case ‘having‘:
                    state = TK_HAVING;
                    break;
                case ‘order‘:
                    state = TK_ORDER;
                    break;
                case ‘asc‘:
                    state = TK_ASC;
                    break;
                case ‘desc‘:
                    state = TK_DESC;
                    break;
                case ‘limit‘:
                    state = TK_LIMIT;
                    break;
                case ‘insert‘:
                    state = TK_INSERT;
                    break;
                case ‘into‘:
                    state = TK_INTO;
                    break;
                case ‘values‘:
                    state = TK_VALUES;
                    break;
                case ‘update‘:
                    state = TK_UPDATE;
                    break;
                case ‘set‘:
                    state = TK_SET;
                    break;
                case ‘delete‘:
                    state = TK_DELETE;
                    break;
                case ‘create‘:
                    state = TK_CREATE;
                    break;
                case ‘table‘:
                    state = TK_TABLE;
                    break;
                default:
                    break;
            }
        } else if (state > TK_ERROR && state < TK_IDENTITY) {//无效字符
            state = TK_ERROR;
        }
        return [state, value, line];
    }

}

 

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

原则上来讲,每个关键字都是一个单独的状态。但是,如果都列入状态表格,这个表格就超级复杂了。比如,为了识别一个关键字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 文件包含了所有词法扫描的测试用例。截取一段代码如下:

Assert.runCase(‘scan identity‘, function () {
     let lexer = new SqlLexer();
     let tokens = lexer.scan(‘id  _name‘);
     Assert.isEqual(tokens.length, 2);
     Assert.isEqual(tokens[0], [TK_IDENTITY, ‘id‘, 1]);
     Assert.isEqual(tokens[1], [TK_IDENTITY, ‘_name‘, 1]);
});

 

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

 

第二章 语法解析 

 

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

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

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

会被解析成如下树结构:

如何用5000行JS撸一个关系型数据库

 

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

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

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

/**
 * SQL语法节点基类。
 */
class SqlNode {

    /**
     * 构造函数。
     * @param parent 父节点。
     * @param value 节点值
     * @param line 所在行号(从1开始)。
     */
    protected constructor(parent: SqlNode, value: string, line: number) {
        this.parent = parent;
        if (parent) {
            parent.nodes.push(this);
        }
        this.value = value;
        this.line = line;
        this.nodes = [];
    }

    public value: string;
    public line: number;
    public parent: SqlNode;
    public nodes: Array<SqlNode>;

    /**
     * 类型推导。
     * @param ctx 上下文。
     */
    public typeDeriva(ctx: SqlContext): SqlColumnType {
        return SqlColumnType.varchar;
    }

    /**
     * 计算节点的值。
     * @param ctx 上下文。
     */
    public compute(ctx: SqlContext): any {
        return null;
    }

}

 

详细介绍一下:

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       -> ‘select‘ [‘distinct‘] fields [from] [where] [groupby] [having] [orderby] [limit]
fields       -> field [‘,‘ field]*
insert       -> ‘insert‘ ‘into‘ identity ‘values‘ ‘(‘ identity [‘,‘ identity] * ‘)‘ ‘values‘ params
update       -> ‘update‘ identity ‘set‘ identity ‘=‘ exp_or [‘,‘ identity ‘=‘ exp_or]* [ where ]
delete       -> ‘delete‘ ‘from‘ identity [ where ]
create_table -> ‘create‘ ‘table‘ identity ‘(‘ field_declare [‘,‘ field_declare] ‘)‘
field_declare-> identity (‘varchar‘ | ‘number‘)
from         -> ‘from‘ table
field        -> exp_or [[‘as‘] identity]
table        -> identity [‘as‘ identity]
join         -> [‘left‘] ‘join‘ table ‘on‘ exp_or
where        -> ‘where‘ exp_or
groupby      -> ‘group‘ ‘by‘ exp_or [‘,‘ exp_or]*
having       -> ‘having ‘ [exp_or]
orderby      -> ‘order‘ ‘by‘ order [‘,‘ order]*
order        -> exp_or [‘asc‘ | ‘desc‘]
limit        -> ‘limit‘ exp_or [‘,‘ exp_or]
params       -> ‘(‘ exp_or [‘,‘ exp_or]+ ‘)‘
exp_or       -> exp_or ‘or‘ exp_and | exp_and
exp_and      -> exp_and ‘and‘ exp_eq | exp_eq
exp_eq       -> exp_eq (‘=‘ | ‘<>‘ | ‘in‘ | ‘not‘ ‘in‘ | ‘is‘ | ‘is‘ ‘not‘ | ‘between‘ | ‘like‘ | ‘not‘ ‘like‘) exp_rel | exp_rel
exp_rel      -> exp_add (‘<‘ | ‘<=‘ | ‘>‘ | ‘>=‘) exp_add | exp_add
exp_add      -> exp_add (‘+‘ | ‘-‘) exp_mult | exp_mult
exp_mul      -> exp_mul (‘*‘ | ‘/‘ | ‘%‘) exp_unary | exp_unary
exp_unary    -> (‘+‘ | ‘-‘ | ‘not‘) exp_unary | factor
exp_ref      -> identity ‘.‘ (identity | ‘*‘)
exp_func     -> identity ‘(‘ exp_or [‘,‘ exp_or]* | empty)  ‘)‘
exp_case     -> ‘case‘ [exp_or] [‘when‘ exp_or ‘then‘ exp_or]+ [‘else‘ exp_or] ‘end‘
exp_hold     -> ‘?‘
factor       -> identity | string | number | bool | star | exp_hold | exp_ref | exp_func | exp_case | ‘(‘ exp_or ‘)‘
identity     -> (‘_‘ | a-z | A-Z)[‘_‘ | a-z | A-Z | 0-9]*
star         -> ‘*‘
string       -> ‘‘‘ (*)* ‘‘‘
number       -> [0-9]+ [‘.‘ [0-9]+]
bool         -> ‘true‘ | ‘false‘
null         -> ‘null‘

 

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

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

 

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

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

    public parseExpRefNode(parent: SqlNode): SqlExpRefNode {
        let beginToken = this.peekAndCheck();
        if (!beginToken) {
            return null;
        }

        let beginIndex = this.pos;
        let node1 = this.parseIdentityNode(null);
        if (!node1) {
            this.moveTo(beginIndex);
            return null;
        }

        let dotToken = this.peek();
        if (!dotToken || dotToken[0] != TK_DOT) {
            this.moveTo(beginIndex);
            return null;
        }

        let endToken = this.moveNext();
        if (!endToken) {
            this.errors.push(new SqlError(‘语法错误:‘ + beginToken[1] + ‘后缺少引用项的名称。‘, beginToken[2]));
            return null;
        }

        if (endToken[0] == TK_MUL || endToken[0] == TK_IDENTITY) {
            this.moveNext();
            return new SqlExpRefNode(parent, beginToken[1] + dotToken[1] + endToken[1], beginToken[2]);
        }

        this.errors.push(new SqlError(‘语法错误:‘ + beginToken[1] + ‘后的引用项无效。‘, beginToken[2]));
        return null;
    }

 

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

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

 

parseExpOrNode类:

public parseExpOrNode(parent: SqlNode): SqlExpOrNode {
    let beginToken = this.peekAndCheck();
    if (!beginToken) {
        return null;
    }

    let node1 = this.parseExpAndNode(parent);
    if (this.errors.length > 0) {
        return null;
    }
    if (node1 == null) {
        if (this.errors.length == 0) {
            this.errors.push(new SqlError(‘词法错误:解析逻辑或表达式失败。‘, beginToken[2]));
        }
        return null;
    }
    let nodeList = [node1];

    let opToken = this.peek();
    while (opToken && opToken[0] == TK_OR) {
        let node = new SqlExpOrNode(parent, opToken[1], opToken[2]);
        nodeList.push(node);

        let node2Token = this.moveNext();
        if (!node2Token) {
            this.errors.push(new SqlError(‘词法错误:符号‘ + opToken[1] + "后面缺少表达式。", opToken[2]));
            return null;
        }
        let node2 = this.parseExpAndNode(parent);
        if (this.errors.length > 0) {
            return null;
        }
        if (!node2) {
            if (this.errors.length == 0) {
                this.errors.push(new SqlError(‘词法错误:解析符号‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
            }
            return null;
        }
        nodeList.push(node2);

        opToken = this.peek();
    }

    if (nodeList.length % 2 == 0) {
        this.errors.push(new SqlError(‘词法错误:逻辑或表达式数量错误。‘, opToken[2]));
        return null;
    }

    //把列表转换为二叉树
    let rootNode = null;
    for (let i in nodeList) {
        let node = nodeList[i];
        if (!rootNode) {
            rootNode = node;
        } else if (node instanceof SqlExpOrNode) {
            this.setNodeParent(rootNode, node);
            rootNode = node;
        } else {
            this.setNodeParent(node, rootNode);
        }
    }

    if (parent && rootNode) {
        this.setNodeParent(rootNode, parent);
    }

    return rootNode;
}

 

 parseExpAndNode类:

public parseExpAndNode = function (parent): SqlExpAndNode {
        let beginToken = this.peekAndCheck();
        if (!beginToken) {
            return null;
        }

        let node1 = this.parseExpEqNode(parent);
        if (this.errors.length > 0) {
            return null;
        }
        if (!node1) {
            this.errors.push(new SqlError(‘词法错误:解析逻辑与表达式失败。‘, beginToken[2]));
            return null;
        }

        let nodeList = [node1];

        let opToken = this.peek();
        while (opToken && opToken[0] == TK_AND) {
            let node = new SqlExpAndNode(parent, opToken[1], opToken[2]);
            nodeList.push(node);

            let node2Token = this.moveNext();
            if (!node2Token) {
                this.errors.push(new SqlError(‘词法错误:符号‘ + opToken[1] + "后面缺少表达式。", opToken[2]));
                return null;
            }
            let node2 = this.parseExpEqNode(parent);
            if (this.errors.length > 0) {
                return null;
            }
            if (!node2) {
                this.errors.push(new SqlError(‘词法错误:解析符号‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
                return null;
            }
            nodeList.push(node2);

            opToken = this.peek();
        }

        if (nodeList.length % 2 == 0) {
            this.errors.push(new SqlError(‘词法错误:逻辑与表达式数量错误。‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
            return null;
        }

        //把列表转换为二叉树
        let rootNode = null;
        for (let i in nodeList) {
            let node = nodeList[i];
            if (!rootNode) {
                rootNode = node;
            } else if (node instanceof SqlExpAndNode) {
                this.setNodeParent(rootNode, node);
                rootNode = node;
            } else {
                this.setNodeParent(node, rootNode);
            }
        }

        if (parent && rootNode) {
            this.setNodeParent(rootNode, parent);
        }

        return rootNode;
    }

 

看着有点晕?没关系,我画一张图,演示一下表达式 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

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

如何用5000行JS撸一个关系型数据库

 

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

 

第三章 计算语法树

 

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

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

 

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

public compute(ctx: SqlContext): any {
    return this.value.indexOf(‘.‘) >= 0 ? parseFloat(this.value) : parseInt(this.value);
}

 

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

public compute(ctx: SqlContext): any {
    if (!this.value) {
        return ‘‘;
    }
    //处理字符串转义
    let s = ‘‘;
    for (let i = 1; i < this.value.length - 1; i++) {
        let c = this.value[i];
        if (c == ‘\\‘) {//escape
            c = this.value[++i];
            if (c == ‘r‘) {
                c = ‘\r‘;
            } else if (c == ‘n‘) {
                c = ‘\n‘;
            } else if (c == ‘t‘) {
                c = ‘\t‘;
            }
            s += c;
        } else {
            s += c;
        }
    }
    return s;
}

 

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

public compute(ctx: SqlContext): any {
    let left = this.nodes[0].compute(ctx);
    if (left instanceof SqlError) {
        return left;
    }
    let right = this.nodes[1].compute(ctx);
    if (right instanceof SqlError) {
        return right;
    }
    if (this.value == ‘>‘) {
        return left > right;
    } else if (this.value == ‘>=‘) {
        return left >= right;
    } else if (this.value == ‘<‘) {
        return left < right;
    } else if (this.value == ‘<=‘) {
        return left <= right;
    }
    return false;
}

 

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

    public compute(ctx: SqlContext): any {
        let left = this.nodes[0].compute(ctx);
        if (left instanceof SqlError) {
            return left;
        }
        let right = this.nodes[1].compute(ctx);
        if (right instanceof SqlError) {
            return right;
        }
        if (typeof left == ‘number‘ && typeof right == ‘number‘) {
            if (this.value == ‘+‘) {
                return left + right;
            } else if (this.value == ‘-‘) {
                return left - right;
            }
        }
        return null;
    }

 

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)。这里我没有做任何优化,直接生成一个笛卡尔积,所以,测试的数据量千万不要太大,否则,运行的速度够你酸爽的~~~

//主表
let fromTableName = this.getFromTableNode().nodes[0].value;
let fromTableAlias = this.getFromTableNode().value;
if (fromTableAlias) {
    ctx.tableAliasMap[fromTableAlias] = fromTableName;
    ctx.tableAliasMap[fromTableName] = fromTableAlias;
}
let fromTable: SqlDataTable = ctx.database.tables[fromTableName];
if (!fromTable) {
    return new SqlError(‘不存在指定的主表:‘ + fromTableName, this.getFromTableNode().line);
}

let tableList = new Array<SqlDataTable>();
tableList.push(fromTable);

//构造宽表的结构
let fullTable = new SqlDataTable(‘__full__‘);
for (let j = 0; j < fromTable.columnNames.length; j++) {
    let col = fromTable.getColumnByIndex(j);
    fullTable.addColumn((fromTableAlias ? fromTableAlias : fromTableName) + ‘.‘ + col.name, col.type);
}
let joinNodes = this.getJoinNodes();
for (let k = 0; k < joinNodes.length; k++) {
    let joinNode = joinNodes[k];
    let joinTableNode = joinNode.nodes[0];
    let joinTableName = joinTableNode.nodes[0].value;
    let joinTableAlias = joinTableNode.value;
    if (joinTableAlias && joinTableAlias == fromTableName) {
        return new SqlError(‘联结表别名与主表名冲突。‘, joinTableNode.line);
    }
    if (joinTableAlias && joinTableAlias == fromTableAlias) {
        return new SqlError(‘联结表别名与主表别名冲突。‘, joinTableNode.line);
    }
    if (!joinTableAlias && joinTableName == fromTableName) {
        return new SqlError(‘联结表名与主表名冲突,必须指定别名。‘, joinTableNode.line);
    }
    if (!joinTableAlias && joinTableName == fromTableAlias) {
        return new SqlError(‘联结表名与主表别名冲突,必须指定别名。‘, joinTableNode.line);
    }

    if (joinTableAlias) {
        ctx.tableAliasMap[joinTableAlias] = joinTableName;
        ctx.tableAliasMap[joinTableName] = joinTableAlias;
    }
    let joinTable: SqlDataTable = ctx.database.tables[joinTableName];
    if (!joinTable) {
        return new SqlError(‘不存在指定的联结表:‘ + joinTableName, joinTableNode.line);
    }
    for (let j = 0; j < joinTable.columnNames.length; j++) {
        let col = joinTable.getColumnByIndex(j);
        fullTable.addColumn((joinTableAlias ? joinTableAlias : joinTableName) + ‘.‘ + col.name, col.type);
    }
    tableList.push(joinTable);
}

//构造宽表的数据
let fullTableRowCount = tableList[0].rows.length;
for (let i = 1; i < tableList.length; i++) {
    fullTableRowCount *= tableList[i].rows.length;
}
for (let i = 0; i < fullTableRowCount; i++) {
    fullTable.addDataRow(fullTable.newRow());
}
if (fullTableRowCount > 0) {
    let joinTableRowCount = fullTableRowCount;
    let colStart = 0;
    for (let i = 0; i < tableList.length; i++) {
        let table = tableList[i];
        joinTableRowCount /= table.rows.length;
        let rowIndex = 0;
        while (rowIndex < fullTableRowCount) {
            for (let j = 0; j < table.rows.length; j++) {
                for (let k = 0; k < joinTableRowCount; k++) {
                    for (let m = 0; m < table.columnNames.length; m++) {
                        fullTable.setValueByIndex(rowIndex, colStart + m, table.rows[j].values[m]);
                    }
                    if (i == 0) {//from table
                        fullTable.rows[rowIndex].id = table.rows[j].id;
                    }
                    rowIndex++;
                }
            }
        }
        colStart += table.columnNames.length;
    }
}
ctx.dataTable = fullTable;

 

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

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

//join筛选
if (joinNodes.length > 0) {
    let filteredRowIndexSet = [];
    for (let i = fullTable.rows.length - 1; i >= 0; i--) {
        ctx.rowIndex = i;
        let joinFaildCount = 0;
        for (let k = 0; k < joinNodes.length; k++) {
            let joinNode = joinNodes[k];
            let joinTableNode = joinNode.nodes[0];
            let joinOnNode = joinNode.nodes[1];
            let v = joinOnNode.compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
            if (v != true) {
                if (joinNode.value == ‘join‘) {
                    joinFaildCount = joinNodes.length + 1;//must be deleted
                } else {//left join
                    joinFaildCount++;
                }

                //没join上的字段设置为null值
                for (let j = 0; j < fullTable.columnNames.length; j++) {
                    let colTableName = fullTable.columnNames[j].split(‘.‘)[0];
                    if (colTableName == joinTableNode.value || colTableName == joinTableNode.nodes[0].value) {
                        fullTable.setValueByIndex(i, j, null);
                    }
                }
            }
        }
        let rid = fullTable.rows[i].id;
        if (typeof filteredRowIndexSet[rid] == ‘undefined‘) {
            filteredRowIndexSet[rid] = {rowIndex: i, failures: joinFaildCount, repeatJoinRows: []};
        } else if (joinFaildCount < filteredRowIndexSet[rid].failures) {
            filteredRowIndexSet[rid].rowIndex = i;
            filteredRowIndexSet[rid].failures = joinFaildCount;
        } else if (joinFaildCount == 0) {
            if (filteredRowIndexSet[rid].failures == 0) {
                filteredRowIndexSet[rid].repeatJoinRows.push(fullTable.rows[i]);
            } else {
                filteredRowIndexSet[rid].rowIndex = i;
                filteredRowIndexSet[rid].failures = joinFaildCount;
            }
        }
    }

    //删除未join上的行
    for (let i = fullTable.rows.length - 1; i >= 0; i--) {
        let r = filteredRowIndexSet[fullTable.rows[i].id];
        if (r.failures > joinNodes.length) {
            fullTable.deleteRow(i);
            continue;
        }
        if (r.rowIndex == i) {
            continue;
        }
        let needDelete = true;
        for (let k = 0; k < r.repeatJoinRows.length; k++) {
            if (r.repeatJoinRows[k] == fullTable.rows[i]) {
                needDelete = false;
                break;
            }
        }
        if (needDelete) {
            fullTable.deleteRow(i);
        }
    }
}

 

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

//where筛选
let whereExpNode = this.getWhereExpNode();
if (whereExpNode) {
    for (let i = fullTable.rows.length - 1; i >= 0; i--) {
        ctx.rowIndex = i;
        if (whereExpNode) {
            let v = whereExpNode.compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
            if (v != true) {
                fullTable.deleteRow(i);
            }
        }
    }
}

 

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节点中,所以,必须在这一步中集中处理一下。

//分组
let groupByNode = this.getGroupByNode();
let havingNode = this.getHavingNode();
let orderByNode = this.getOrderByNode();

//找出用到的所有聚合表达式
let funcNodeList: SqlExpFuncNode[] = [];
for (let j = 0; j < fieldNodes.length; j++) {
    this.loadAggregateFunctions(fieldNodes[j], funcNodeList);
}
if (havingNode) {
    this.loadAggregateFunctions(havingNode, funcNodeList);
}
if (orderByNode) {
    this.loadAggregateFunctions(orderByNode, funcNodeList);
}
let funcNodeCount = 0;
for (let m in funcNodeList) {
    funcNodeCount++;
}

if (groupByNode || funcNodeCount > 0) {
    //构造分组中间表
    let t = new SqlDataTable(‘__group__‘);
    if (groupByNode) {
        for (let k = 0; k < groupByNode.nodes.length; k++) {
            let gNode = groupByNode.nodes[k];
            let col = t.addColumn(gNode.toSql(), gNode.typeDeriva(ctx));
            if (col) {
                col.node = gNode;
            }
        }
    }
    for (let i in funcNodeList) {
        let fNode = funcNodeList[i];
        let col = t.addColumn(fNode.toSql(), fNode.typeDeriva(ctx));
        if (col) {
            col.node = fNode;
        }
    }
    ctx.groupByMidTable = t;

    //计算分组中间表的数据
    for (let i = 0; i < fullTable.rows.length; i++) {
        ctx.rowIndex = i;
        for (let j = 0; j < t.columnNames.length; j++) {
            let col = t.getColumnByIndex(j);
            let expNode = col.node;
            let v = expNode.compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
        }
    }
    ctx.isGroupByMidTableFinished = true;
    ctx.dataTable = ctx.groupByMidTable;

    //计算结果表的数据
    for (let i = 0; i < ctx.dataTable.rows.length; i++) {
        ctx.rowIndex = i;
        if (havingNode) {
            let hv = havingNode.compute(ctx);
            if (hv instanceof SqlError) {
                return hv;
            }
            if (hv != true) {
                continue;
            }
        }
        let rowValues = [];
        for (let j = 0; j < fieldExpNodes.length; j++) {
            let fNode = fieldExpNodes[j];
            let fCol = ctx.dataTable.getColumnByName(fNode.toSql());
            if (fCol) {
                let fVal = ctx.dataTable.rows[i].values[fCol.index];
                if (fVal instanceof SqlGroupByValue) {
                    fVal = fVal.value;
                }
                rowValues.push(fVal);
            } else {
                let v = fNode.compute(ctx);
                if (v instanceof SqlError) {
                    return v;
                }
                rowValues.push(v);
            }
        }
        resultTable.addRow(rowValues);
    }
}

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

public compute(ctx: SqlContext): any {
    let fnName = this.value;
    let isDistinct = this.nodes.length > 1 && this.nodes[0] instanceof SqlModifiersNode && this.nodes[0].nodes[0].value == ‘distinct‘;
    let paramNodes = isDistinct ? this.nodes[1].nodes : (this.nodes.length > 0 ? this.nodes[0].nodes : []);

    //
    // 执行非聚合函数
    //
    if (!this.isAggregate()) {
        let fn = ctx.standardFunctions[‘_‘ + fnName];
        if (!fn) {
            return new SqlError(‘不存在指定的函数:‘ + fnName, this.line);
        }

        //计算实参的值
        let fnArgs = [];
        for (let i = 0; i < paramNodes.length; i++) {
            let v = paramNodes[i].compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
            fnArgs.push(v);
        }
        return fn(fnArgs);
    }

    //
    // 执行聚合函数
    //

    //检查分组中间表
    let t: SqlDataTable = ctx.groupByMidTable;
    if (!t) {
        return new SqlError(‘分组中间表未初始化。‘, this.line);
    }
    let k = this.toSql();
    let col = t.getColumnByName(k);
    if (!col) {
        return new SqlError(‘分组中间表中不存在指定的聚合列:‘ + k, this.line);
    }

    //检查分组中间表是否已完成,如果已完成,则可以直接取值
    if (ctx.isGroupByMidTableFinished) {
        let gv: SqlGroupByValue = t.getValueByIndex(ctx.rowIndex, col.index);
        return gv ? gv.value : null;
    }

    //分组中间表还没有完成,需要继续计算
    let fnArgs = [];
    for (let i = 0; i < paramNodes.length; i++) {
        let pNode = paramNodes[i];
        let v = null;
        if (pNode instanceof SqlStarNode) {
            v = 1;// TODO: 这里应该改为判断该行所有列是否都不为null
        } else {
            v = pNode.compute(ctx);
        }
        if (v instanceof SqlError) {
            return v;
        }
        fnArgs.push(v);
    }
    if (fnArgs.length != 1) {
        return new SqlError(‘函数‘ + fnName + ‘的参数个数错误。‘, this.line);
    }
    let v = fnArgs[0];
    if (v == null) {
        return null;
    }

    //分组的中间数据行
    let groupByNode = ctx.selectNode.getGroupByNode();
    let groupByExpNodes = groupByNode ? groupByNode.nodes : [];
    let groupByValues = [];
    for (let i = 0; i < groupByExpNodes.length; i++) {
        let bv = groupByExpNodes[i].compute(ctx);
        if (bv instanceof SqlError) {
            return bv;
        }
        groupByValues.push(bv);
    }
    let r = t.addDataRow(new SqlDataRow(groupByValues, false));

    //分组计算
    let gv: SqlGroupByValue = r.values[col.index];
    if (!gv) {
        gv = new SqlGroupByValue();
        r.values[col.index] = gv;
    }
    if (fnName == ‘count‘) {
        if (isDistinct) {
            v = v + ‘‘;
            if (!gv.distinctValues[v]) {
                gv.distinctValues[v] = 1;
                gv.value = gv.value == null ? 1 : gv.value + 1;
            }
        } else {
            gv.value = gv.value == null ? 1 : gv.value + 1;
        }
    } else if (fnName == ‘sum‘) {
        gv.value = gv.value == null ? v : v + gv.value;
    } else if (fnName == ‘max‘) {
        if (gv.value == null || v > gv.value) {
            gv.value = v;
        }
    } else if (fnName == ‘min‘) {
        if (gv.value == null || v < gv.value) {
            gv.value = v;
        }
    } else if (fnName == ‘avg‘) {
        gv.sum += v;
        gv.count++;
        gv.value = gv.sum / gv.count;
    }
    return null;
}

 

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

//计算结果表的数据
for (let i = 0; i < ctx.dataTable.rows.length; i++) {
    ctx.rowIndex = i;
    let rowValues = [];
    for (let j = 0; j < fieldExpNodes.length; j++) {
        let v = fieldExpNodes[j].compute(ctx);
        if (v instanceof SqlError) {
            return v;
        }
        rowValues.push(v);
    }
    resultTable.addRow(rowValues);
}

 

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

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

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

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

//排序
if (orderByNode && orderByNode.nodes.length > 0) {
    //计算每一行的排序值
    let rows = resultTable.rows;
    for (let i = 0; i < rows.length; i++) {
        ctx.rowIndex = i;
        let row = rows[i];
        for (let m = 0; m < orderByNode.nodes.length; m++) {
            let oVal = orderByNode.nodes[m].nodes[0].compute(ctx);
            if (oVal instanceof SqlError) {
                return oVal;
            }
            row.orderByValues.push(oVal);
        }
    }

    //计算每个排序项的方向
    let directions: boolean[] = [];
    for (let k = 0; k < orderByNode.nodes.length; k++) {
        directions.push(orderByNode.nodes[k].value == ‘desc‘);
    }

    //对数据行进行排序
    rows.sort(function (a: SqlDataRow, b: SqlDataRow) {
        let m = 0;
        while (m < directions.length) {
            if (a.orderByValues[m] == b.orderByValues[m]) {
                m++;
            } else {
                if (directions[m]) {//desc
                    return a.orderByValues[m] < b.orderByValues[m] ? 1 : -1;
                } else {
                    return a.orderByValues[m] > b.orderByValues[m] ? 1 : -1;
                }
            }
        }
        return 0;
    });
}

 

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

let limitNode = this.getLimitNode();
if (limitNode) {
    let limitNums = [];
    for (let i = 0; i < limitNode.nodes.length; i++) {
        let v = limitNode.nodes[i].compute(ctx);
        if (v instanceof SqlError) {
            return v;
        }
        if (typeof v != ‘number‘) {
            return new SqlError(‘无效的limit值:‘ + v, limitNode.line);
        }
        limitNums.push(v);
    }
    if (limitNums.length == 1) {
        let end = limitNums[0];
        if (resultTable.rows.length > end) {
            resultTable.rows.splice(end, resultTable.rows.length - end);
        }
    } else if (limitNums.length == 2) {
        let begin = limitNums[0];
        let end = limitNums[0] + limitNums[1] - 1;
        resultTable.rows.splice(end + 1, resultTable.rows.length - end - 1);
        resultTable.rows.splice(0, begin);
    }
}

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

 

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

 

第五章 其它语句

 

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

public compute(ctx: SqlContext): any {
    let tableName = this.nodes[0].nodes[0].value;
    let table: SqlDataTable = ctx.database.tables[tableName];
    if (!table) {
        return new SqlError(‘不存在指定的表:‘ + tableName, this.line);
    }

    ctx.dataTable = table;

    let deletedCount = 0;
    if (this.nodes.length >= 2) {
        for (let i = table.rows.length - 1; i >= 0; i--) {
            ctx.rowIndex = i;
            ctx.holdIndex = -1;
            let v = this.nodes[1].compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
            if (v) {
                table.deleteRow(i);
                deletedCount++;
            }
        }
    } else {
        deletedCount = table.rows.length;
        table.rows = [];
    }

    return deletedCount;
}

 

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

public compute(ctx: SqlContext): any {
    let tableName = this.nodes[0].nodes[0].value;
    let table: SqlDataTable = ctx.database.tables[tableName];
    if (!table) {
        return new SqlError(‘不存在指定的表:‘ + tableName, this.line);
    }

    ctx.dataTable = table;

    let updateCols = [];
    let updateValueNodes = [];
    for (let j in this.nodes[1].nodes) {
        let setNode = this.nodes[1].nodes[j];
        let colName = setNode.nodes[0].value;
        let col = table.getColumnByName(colName);
        if (!col) {
            return new SqlError(‘不存在指定的列:‘ + colName, setNode.nodes[0].line);
        }
        updateCols.push(col);
        updateValueNodes.push(setNode.nodes[1]);
    }

    let updateRowIndexList = [];
    if (this.nodes.length == 2) {
        for (let i = 0; i < table.rows.length; i++) {
            updateRowIndexList.push(i);
        }
    } else if (this.nodes.length == 3) {
        for (let i = 0; i < table.rows.length; i++) {
            ctx.rowIndex = i;
            ctx.holdIndex = -1;
            let whereValue = this.nodes[2].compute(ctx);
            if (whereValue instanceof SqlError) {
                return whereValue;
            }
            if (whereValue) {
                updateRowIndexList.push(i);
            }
        }
    }

    for (let i in updateRowIndexList) {
        ctx.rowIndex = updateRowIndexList[i];
        ctx.holdIndex = -1;
        for (let j in updateCols) {
            let col = updateCols[j];
            let v = updateValueNodes[j].compute(ctx);
            if (v instanceof SqlError) {
                return v;
            }
            table.setValueByIndex(ctx.rowIndex, col.index, v);
        }
    }

    return updateRowIndexList.length;
}

 

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

public compute(ctx: SqlContext): any {
    let tableName = this.nodes[0].value;
    let table = ctx.database.tables[tableName];
    if (!table) {
        return new SqlError(‘不存在指定的表:‘ + tableName, this.line);
    }

    let fieldsNodes = this.nodes[1].nodes;
    let valuesNodes = this.nodes[2].nodes;

    let row = table.newRow();
    ctx.holdIndex = -1;
    for (let j = 0; j < fieldsNodes.length; j++) {
        let colName = fieldsNodes[j].value;
        let colIndex = table.getColumnByName(colName).index;
        let valueNode = valuesNodes[j];
        let v = valueNode.compute(ctx);
        if (v instanceof SqlError) {
            return v;
        }
        row.values[colIndex] = v;
    }
    table.addDataRow(row);

    return 1;
}

 

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

public compute(ctx: SqlContext): any {
    let table = new SqlDataTable(this.nodes[0].value);
    let paramsNode = this.nodes[1];
    let columnNames = [];
    for (let i = 0; i < paramsNode.nodes.length; i++) {
        let fieldDeclareNode = paramsNode.nodes[i];
        let colName = fieldDeclareNode.value;
        let colType = fieldDeclareNode.nodes[0].value;
        if (columnNames.indexOf(colName) >= 0) {
            return new SqlError(‘列名重复:‘ + colName, fieldDeclareNode.line);
        }
        table.addColumn(colName, colType);
        columnNames.push(fieldDeclareNode);
    }
    return ctx.database.addTable(table);
}

 

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

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

 

第六章 程序展示

通过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

执行结果:

如何用5000行JS撸一个关系型数据库

 

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

 

如何用5000行JS撸一个关系型数据库

上一篇:django怎么实现从数据库获取图片在前端显示


下一篇:MySQL管理-DDL语句(11)