Skip to content

A reduced mysql compiler. 西电编译原理大作业

Notifications You must be signed in to change notification settings

Iamnotphage/myDBMS

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

43 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

myDBMS

  /$$$$$$  /$$   /$$ /$$$$$$$$ /$$   /$$      
 /$$__  $$| $$  | $$| $$_____/| $$$ | $$      
| $$  \__/| $$  | $$| $$      | $$$$| $$      
| $$      | $$$$$$$$| $$$$$   | $$ $$ $$      
| $$      | $$__  $$| $$__/   | $$  $$$$      
| $$    $$| $$  | $$| $$      | $$\  $$$      
|  $$$$$$/| $$  | $$| $$$$$$$$| $$ \  $$      
 \______/ |__/  |__/|________/|__/  \__/ 

设计并实现一个DBMS原型系统,可以接受基本的SQL语句,对其进行词法分析、语法分析,然后解释执行SQL语句,完成对数据库文件的相应操作,实现DBMS的基本功能。

ps: 以下教科书特指西电出版社的《编译原理》

效果演示

demo

环境说明

  • windows11
  • GCC/G++ 8.1.0
  • Lex(Flex) 2.5.4a
  • YACC(Bison) 2.4.1
  • CLion 2023
  • VSCode 插件Yash可以高亮Lex和YACC语法

lex和yacc在UNIX中是标配,所以windows用户需要自己去下载,而linux或者macos用户会方便一些。

下面贴出GNU官方的下载地址。

Flex Download

Bison Download

安装之后需要配置环境变量,将bin目录添加到系统环境变量就行了。

配置好环境变量后,cmd终端能够找到bison.exeflex.exe,所以能够执行命令,查看一下版本号看看配置是否正确。

前置知识

  1. CMake相关的前置知识: Quick CMake Tutorial
  2. 正则表达式: flex官方说明 或教科书
  3. Lex程序基本结构: 简单程序演示 或教科书2.5章
  4. YACC程序基本结构: YACC官方文档

Lex源程序说明

Lex用来生成词法分析器(词法分析器生成器),能识别正规式,并执行给定的动作。输出的文件是.yy.c后缀。

Lex源程序结构

Lex源程序的结构被%%符号分为三/四部分(查看教科书2.5章):

%{
Declarations
%}
Definitions
%%
Rules
%%
User subroutines
  1. Declarations段包含一些C的头文件,宏定义,函数声明,全局变量声明
  2. Definitions段包含一些 正则表达式 的名字 (比如digit [0-9],digit是名字)
  3. Rules段定义{patterns} {actions}每一个模式串(正则表达式)对应一个动作(C代码片段)
  4. User subroutines段可以定义函数

比如上述文件名为lex.l

通过命令flex lex.l生成lex.yy.c文件,再gcc编译生成.exe文件,就能对输入记号流进行词法分析。

全局变量/函数

分析源码,需要注意Lex程序中常用的几个全局变量和函数

全局变量/函数 说明
char *yytext 输入序列(字符串)
int yyleng 输入序列的长度
int yylex() 词法分析驱动器的入口,扫描输入序列后,匹配到正则表达式(最长的那一条),执行对应的C代码,返回代码段返回的值(代码段没写返回值yylex()默认返回0),也就是每个token的标号。
int yywrap() 词法分析器分析结束时,自动调用yywrap()。如果其返回值为1,则结束分析过程;如果返回值为0,则继续扫描下一个输入。

例子

例子(或参考编译原理2.5章节):

识别输入序列,输出记号类型:

%{
    #define ID 0
    #define NUMBER 1
%}

char [a-zA-Z]
digit [0-9]
digits {digit}+
optional_fraction ("."{digits})?
optional_exponent (E[+-]?{digits})?

%%
{char}({char}|{digit})* {printf("identified a ID %s: length: %d\n", yytext, yyleng);
                         return ID;}

{digits}{optional_fraction}{optional_exponent} {printf("identified a NUMBER %s: length: %d\n", yytext, yyleng);
                                                return NUMBER;}

%%
int main(void){
    printf("Done, token type: %d\n", yylex());
}

int yywrap(){
    return 1;
}

文件名为mylexer.l,运行步骤(Windows):

  1. lex源程序编译: flex .\mylexer.l
  2. 对生成的C源文件lex.yy.c编译: gcc lex.yy.c
  3. 运行编译完的可执行文件a.exe: .\a.exe

程序可以识别两类记号,一种是标识符,一种是数字.

若识别到正则表达式对应的字符串,执行对应的C代码.

main()函数将自动调用生成的yylex()函数。

yylex()执行完之后询问yywrap(),是否需要再扫描后续输入。

YACC源程序说明

Yet Another Compiler Compiler.

语法分析器生成器。识别手工设计的产生式(Productions)执行对应的语义动作。文件后缀.y,输出文件后缀.tab.c

YACC源程序结构

YACC源程序的结构也是类似的三/四段(查看教科书3.5章)

%{
Declarations
%}
Definitions
%%
Productions
%%
User subroutines

这里DeclarationsUser subroutines和lex源程序是一样的作用。

特别说明的是Definitions段和Productions段。

前者比lex源码多了一些YACC转有的变量,后者是定义语法产生式(一说文法,都是grammar),并且与手写的符号不太一样。

关于Definitions段

改变yylval的默认类型

查看下面的表格,yylval默认类型其实是int,但是在yacc源文件中可以这样定义他的union从而实现自定义。

%union {
    int intval;
    char *chval;
}

yacc允许yylex()通过yylval传递值:

yacc定义了yylval的union,它将会把yylval的定义写到y.tab.h中,所以当.l文件中引用了.tab.h头文件之后,能够给yylval赋值。(详情查看后续lex和yacc联合使用)

非终结符

%type<chval> tableName // 这里chval是上述联合体中定义的char *chval

在后续语法定义中tableName将作为非终结符,这意味着他可以进一步推导。

终结符

token定义

%token NUMBER

结合性和优先级

%left '+' '-'
%left '*' '/'

变量left代表左结合,同一行的符号优先级相同。下面行的优先级比上面行的高。

关于Productions段

除了一般的文法,还要注意YACC默认把第一条产生式当作开始的产生式。

这一点非常重要!

下面举例说明:

// Productions段
createStatement:
    CREATE TABLE tableName ';'
    ;

queryStatement:
    SELECT columnName FROM tableName ';'
    ;
    
//如果后面还有文法产生式,也将因为无法从S推导,而无法识别

如果先读取到了SELECT语句,将无法识别,因为一切语法分析要从第一条产生式开始。

所以在上述例子中,最好是这样定义Productions段:

// Productions段
statements:
    createStatement
    | queryStatement
    ;

createStatement:
    CREATE TABLE tableName ';'
    ;

queryStatement:
    SELECT columnName FROM tableName ';'
    ;

这样第一条产生式就可以有多种选择。

全局变量/函数

全局变量/函数 说明
YYSTYPE yylval YYSTYPE类型(其实就是int),默认是int,可以通过union自定义。存储当前词法单元的属性值
char *yytext 同lex中的yytext,指向当前匹配的输入字符串
int yyleng 同lex中的yyleng,表示当前匹配的输入字符串的长度
int yylex() 同lex中的yylex(),词法分析器函数
int yyparse() 语法分析器函数,解析输入内容,并根据语法规则执行对应代码。返回值有三种:YYACCEPT(0)、YYABORT(1)、YYNOMEM(2)分别代表接受、语法错误、内存不足的情况。
void yyerror() 错误处理,用户自定义
int yywrap() 同lex中的yywrap(),返回1表示输入结束,0表示还有输入

特别地,在产生式中,对应的动作(也就是对应的C代码段,原文actions)可以使用$符号指代产生式的左部或者右部的某个符号。

$1、$2 和 $$ 的使用
$n:用于访问产生式右侧第 n 个符号的值。$1 表示第一个符号的值,$2 表示第二个符号的值,依此类推。
$$:用于表示产生式左侧非终结符的值。

......前文省略
%%

expr : expr '+' expr { printf("Result: %d\n", $1.intval + $3.intval); }
     | expr '-' expr { printf("Result: %d\n", $1.intval - $3.intval); }
     | expr '*' expr { printf("Result: %d\n", $1.intval * $3.intval); }
     | expr '/' expr { printf("Result: %d\n", $1.intval / $3.intval); }
     | NUMBER        { $$ = $1.intval; }
     ;

%%
......后文省略

例子

这里是单个YACC程序,没有配合lex。用户手动输入代替lex词法分析之后产生的token stream.

所以手动定义了yylex(),后续lex和YACC配合时,yylex()由lex自动生成。

%{
    #include<ctype.h>
    #include<stdio.h>
    int yylex();
    void yyerror(const char*);
%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%% // 这里是产生式 expr是非终结符,NUMBER是终结符
expr : expr '+' expr    {printf("Identified [add].\n");}
     | expr '-' expr    {printf("Identified [sub].\n");}
     | expr '*' expr    {printf("Identified [multiply].\n");}
     | expr '/' expr    {printf("Identified [divide].\n");}
     | '(' expr ')'     {printf("Identified [round bracket].\n");}
     | NUMBER           {printf("Identified [NUMBER].\n");}
     ;
%%

int main(void){
    return yyparse();
}

int yylex(void){
    int c;
    while((c = getchar()) == ' ');
    if(isdigit(c)){
        ungetc(c, stdin);
        scanf("%d", &yylval);
        return NUMBER;
    }
    if(c == '\n')return 0;
    return c;
}

void yyerror(const char *s){
    printf("%s", s);
}

文件名为myparser.y,运行步骤(Windows):

  1. 编译.y程序: bison .\myparser.y
  2. 编译生成的C程序: gcc .\myparser.tab.c
  3. 执行生成的可执行文件: .\a.exe

输入字符串(其实是token stream),可以识别表达式。

这里是main()函数调用yyparse()函数

而yyparse()将调用yylex()函数 (这里因为只由一个YACC程序组成,所以yylex()函数是用户自定义的) 获取输入的token,并语法分析

匹配到产生式就执行对应的代码段。

Lex和YACC联合编程

没啥区别,主要在于yylval和yylex()这些变量/函数的链接。

yylval在Lex程序中的赋值

yylval是在YACC程序中定义的,而yylex()是在Lex程序中自动生成的(也就是{patterns} {actions}里面的actions)

当前目录下的test文件夹中测试了两个文件test.ltest.y

要保证Lex程序中能给yylval赋值,从而让YACC程序进一步操作,就要在Lex程序中添加YACC程序的头文件(因为yylval是在YACC程序中定义的

所以编译YACC程序就要顺便生成YACC的头文件,以便Lex程序包含,从而使用yylval变量。

yylex()在YACC程序中被调用

前文提到过,yylex()是在Lex程序中根据模式串自动生成的函数。

YACC程序中,yyparse()将自动调用yylex()程序(这也是为什么YACC单独运行时,需要用户自定义yylex()函数)

所以YACC源程序中要声明yylex()函数。

例子

其次,上述Lex单独运行和YACC单独运行时,都自定义了main函数。

下面的例子是main函数定义在test.y中,当然也可以在其他文件中定义main(),然后调用yyparse()

test.ltest.y(自己写的一个测试样例,内容很简单,只需要理解如何编译他们)

// in test.l
%{
#include "test.tab.h"
%}

NUM [1-9]+[0-9]*|0

%%

{NUM}		                return NUM;
[ \t]+                     /* ignore whitespace */;
.

%%


int yywrap(){
return 1;
}

看一下test.y:

%{
    #include <stdio.h>
    #include <string.h>
    int yylex(void);
    void yyerror(char *);
%}

%token NUM

%%
expr:
    NUM {printf("This is a number.\n")};
    ;
%%
void yyerror(char *str){
    fprintf(stderr,"error:%s\n",str);
}

int main() // 后续这里可以注释掉,别的地方调用yyparse()
{
    yyparse();
}

大体上是识别数字。

首先要编译test.ltest.y文件,下面用Flex和Bison演示。

flex test.l
bison -d test.y

不同的点在于bison命令行参数的-d,这里会生成test.tab.ctest.tab.h文件,从而让lex程序包含yylval。

接下来两个文件编译

gcc -o test test.tab.c lex.yy.c

这样就能够生成test.exe文件了,执行是没问题的。(上述是纯C文件的编译)

模块化

问题在于,我并不想在test.tab.c中就直接进入入口main(),我可能需要给项目分模块,词法分析、语法分析只是其中一块而已。

这时候就需要将test.y中的main()删除了,毕竟程序的入口main()我们需要放在别的地方。

这样会有两个新问题:

  1. 那在别的文件中,怎么调用词法分析、语法分析这一块内容呢?
  2. 上述的测试都是在标准输入/输出中进行的,如果我有一个shell,这个shell从标准输入中读取字符串,再交给编译器这个模块来解析,岂不是lex和YACC要传入字符串了(而不是从标准输入中读取)?

其实都是很好解决的问题:

Flex官方文档给出了如下说明:

Three routines are available for setting up input buffers for scanning in-memory strings instead of files.

其中一个就是yy_scan_string(const char *str),这意味着,可以将指定的字符串作为Lex的输入流,然后yylex()函数将从这个输入流中进行词法分析,再将分析结果传给yyparse().

所以,test.ltest.y这一个模块,可以被外部调用,只需要利用好yy_scan_string()yyparse()(因为yyparse()内部会调用yylex())即可。

下面是一个例子main.cpp:

//很重要
int yyparse(void); // 从别的文件找这些函数
void yy_scan_string(const char* str);


int main() {
    std::string inputLine;

    // 从标准输入读取一行
    std::getline(std::cin, inputLine);

    // 将输入字符串传递给词法分析器
    yy_scan_string(inputLine.c_str()); // c风格的string,其实就是char*

    // 调用语法分析器
    yyparse();

    return 0;
}

注意!CPP和C混合编程,C和C++编译器会有不太一样的表现,这里是关于名字改编的问题,上述代码在test文件夹下,用下面的编译命令能够正常运行

flex test.l
bison -d test.y
g++ -o lex.yy.c test.tab.c main.cpp

在CPP文件中,如果要用到yyparse()yy_scan_string()这些来自C文件的函数,就要加上extern "C"的关键字。

//很重要
extern "C"{
    int yyparse(void); // 从别的文件找这些函数
    void yy_scan_string(const char* str);
}

自己注意就行,总之能够调用这两个函数就可以了。

如果要在parser.y中用到cpp的某些特性,比如类或者某些集合,那么你就需要保证你用lexyacc编译的文件是.cpp/.hpp的,从而尽量避免C和CPP混合编程带来的undefine reference的链接问题。

要么纯C要么纯CPP,C和CPP混合的话,还是挺麻烦的,除非你能做到完美分离前后端。

如果你要纯CPP的话,flex源文件可以在开头加上%option outfile = "lex.yy.cpp",这样flex lex.l编译出来的文件就是lex.yy.cpp(可改名)

使用yyparse()yy_scan_string()的话,就不用加上extern "C"的关键字了。

数据库设计

myDBMS Architecture

概览如下图:

arch

ShellCompiler部分属于Front-End部分。

Engine以及后续的部分属于Back-End部分。

这一点参考的官方Architecture of SQLite

编译器设计

Tokenizer

lex程序比较简单,没什么特别需要注意的地方,本人遇到的两个bug需要注意。

一个是关于NUMBER的正则表达式,之前使用的是:

[-+]?[1-9][0-9]*,其实这个表达式不包含0,一定要注意多测试前端的问题。

后续修复这样:

[-+]?[0-9]+

另一个是关于STRING的正则表达式,很容易想到:

'.*'

也就是两个单引号包含一个任意字符闭包。

看起来没什么问题,但是实际上如果出现多个字符:

SELECT * FROM table WHERE name = 'test' AND money = 'infinity';

将会出现难以调试的bug。有可能会把test' AND money = 'infinity作为两个单引号的内容,导致bug。

建议改成:

"'"[^']*"'"

Parser

在YACC程序,语法分析主要写一些文法产生式,还有对应的规则。

我设计语句如下:

开始语句为startStatement,其语法树如下:

startStatement

分为六大部分,systemControl,createStatement,queryStatement,insertStatement,updateStatement,deleteStatement

systemControl

主要是对数据库和表进行创建、删除、使用、列举:

/* System-Control Statements */
systemControl:
	CREATE DATABASE databaseName ';'	
	| SHOW DATABASES ';'				
	| USE databaseName ';'				
	| DROP DATABASE databaseName ';'	
	| SHOW TABLES ';'					
	| DROP TABLE tableName ';'			
	;

databaseName:
	ID									
	;

tableName:
	ID
	;

createStatement

主要是在已经选中的数据库中创建表:

// Create Statement.
createStatement:
	CREATE TABLE tableName '('columnsDefinition')' ';'
	;

columnsDefinition:
	columnName columnType
	| columnName columnType ',' columnsDefinition
	;

columnName:
	ID
	;

columnType:
	INT
	| CHAR '(' NUMBER ')'
	;

queryStatement

主要是在已经选中的数据库中进行查询:

// Query Statement.
queryStatement:
	SELECT columnNames FROM tableNames ';'
	| SELECT columnNames FROM tableNames WHERE conditions ';'
	;

columnNames:
	'*'
	| columnName
	| columnName ',' columnNames
	;

tableNames:
	tableName
	| tableName ',' tableNames
	;

// Top-level conditions rules
conditions:
    condition
    | '(' conditions ')'
    | conditions AND conditions
    | conditions OR conditions
    ;

// Single condition rule
condition:
    columnName operator rightOperand
    ;

// Operator definitions
operator:
    '<'
    | '>'
    | '='
    | '!' '='
    | '<' '>'
    ;

// Right operand can be a number or a string
rightOperand:
    NUMBER
    | STRING
    ;

需要特别注意的是conditions的语法树,后续对应的规则比较复杂。

insertStatement

主要是在已经选中的数据库中进行插入:

// Insert statement.
insertStatement:
	INSERT INTO tableName '(' columnNames ')' VALUES '(' values ')' ';'
	| INSERT INTO tableName VALUES '(' values ')' ';'
	;

values:
	value
	| value ',' values
	;

value:
	NUMBER
	| STRING
	;

updateStatement

主要是在已经选中的数据库中进行更新:

// Update statement.
updateStatement:
	UPDATE tableName SET assignments WHERE conditions ';'
	;

assignments:
	assignment
	| assignment ',' assignments
	;

assignment:
	columnName '=' value
	;

deleteStatement

主要是在已经选中的数据库中进行删除:

// Delete statement.
deleteStatement:
	DELETE FROM tableName ';'
	| DELETE FROM tableName WHERE conditions ';'
	;

后端接口设计

前端是lex和yacc共同分析输入语句,识别到对应的文法后,执行对应的代码。

这里设计Database.h暴露给前端一些接口用于内核执行数据库语句。

在语法分析的同时,将一些链表结构或者树结构创建,所以需要声明一些结点,方便后端执行。

#define STATE_SYS 0
#define STATE_DB 1 // 选中数据库的状态才能增删改查

struct columnNode{
    std::string columnName;
    int charLength;
    struct columnNode* next = nullptr;
};

// for SELECT node;
struct tableNode{
    std::string tableName;
    struct tableNode* next = nullptr;
};

struct conditionNode{
    std::string columnName;
    // 如果op是AND或者OR,说明是一个中间结点,有左右子树,cloumnName和value为空。
    // 如果这个结点是叶子节点,则代表这是一个表达式结点,columnName op value;
    enum op{
        AND, OR, GREATER, LESS, EQUAL, NOT_EQUAL
    }op;
    enum rightOperandType{
        INT, STRING
    }rightOperandType;
    int intval;
    std::string chval;

    struct conditionNode* left = nullptr;
    struct conditionNode* right = nullptr;
};

// SELECT [columnNames] FROM [tables] WHERE [conditions];
struct selectNode{
    struct columnNode* columnNames = nullptr;
    struct tableNode* tables = nullptr;
    struct conditionNode* conditions = nullptr;
};

// for INSERT node;
struct valueNode{
    enum type{
        INT, STRING
    }type;
    int intval;
    std::string chval;
    struct valueNode* next = nullptr;
};

// INSERT INTO [table] ([columnNames]) VALUES ([values]);
// INSERT INTO [table] VALUES ([values]);
struct insertNode{
    std::string tableName;
    struct columnNode* columnNames = nullptr;
    struct valueNode* values = nullptr;
};

// for UPDATE node;
struct assignmentNode{
    std::string columnName;
    enum type{
        INT, STRING
    }type;
    int intval;
    std::string chval;
    struct assignmentNode* next = nullptr;
};

// UPDATE [tableName] SET [assignments] WHERE [conditions];
struct updateNode{
    std::string tableName;
    struct assignmentNode* assignments = nullptr;
    struct conditionNode* conditions = nullptr;
};

// DELETE FROM [tableName];
// DELETE FROM [tableName] WHERE [conditions];
struct deleteNode{
    std::string tableName;
    struct conditionNode* conditions = nullptr;
};

// API in Databases.h
class Database {
public:
    void showDatabases();
    void useDatabase(const std::string& databaseName);
    void dropDatabase(const std::string& databaseName);
    void createDatabase(const std::string& databaseName);
    void showTables();
    void dropTable(const std::string& tableName);
    void createTable(const std::string& tableName, struct columnNode* columnHead);
    void select(struct selectNode* node);
    void insert(struct insertNode* node);
    void update(struct updateNode* node);
    void deleteFrom(struct deleteNode* node);
    
private:
    int currentState; // 当前系统状态
    const std::string dataPath = "../data";
    std::string currentDatabase; // 当前选中的数据库
    std::unordered_map<std::string, std::string> tableFiles;
    Pager* currentPage; // 当前页 (这里可以改为存放页的某类容器,可以实现LRU)
}

其他结点结构都很简单,都是拉链结构。

唯独conditionNode要特别注意,遍历这个结点相当于LDR遍历二叉树(前序遍历)

比如... WHERE id = 3 AND name = 'chen',传递给后端的树结构如下:

conditionNodeExample

即,op的枚举类型是ANDOR,则说明这个结点是一个连接的结点,或者说是一个父亲结点。

只有叶子结点是有columnNameintvalchval的。

这样就能清晰表示条件。

存储结构设计

总体结构如下:

memoryArch

采取分页的思想,一个文件为一张表,一张表内有若干页,一页内有若干行。

对于每一个页:

  • 首先要有一个File Header,除了表明页的信息外,还有两个指针,分别指向上一页和下一页。
  • 再来一个Page Header,存储一些该页的状态信息。
  • 再设计一个Infimum + Supermum,用来记录当前页最小和最大的记录。
  • 接下来设计一个Page Directory,对下文的User Records做一个简单索引。
  • 最后才是User Records用来存储每一行的数据,数据之间物理上按先后顺序存储,逻辑上按主键顺序形成单链表。

主要在Pager.h中实现页机制(读入内存的页):

const unsigned int PAGE_SIZE = 4096;
const unsigned int FILE_HEADER_SIZE = sizeof(int) * 3;
const unsigned int PAGE_HEADER_SIZE = sizeof(int) * 2;
const unsigned int RECORDS_SIZE = PAGE_SIZE - FILE_HEADER_SIZE - PAGE_HEADER_SIZE;
const unsigned int ROW_PER_PAGE = 8 + RECORDS_SIZE / 64; // 8 + 63 = 71; 大概63行数据,8行头信息
const int DEFAULT_INFIMUM = 99999;
const int DEFAULT_SUPERMUM = -1;

struct FileHeader {
    int pageNumber; // 当前页的页号
    std::unordered_map<std::string, int> columnOffset; // 在Records中列名对应的偏移(第几个逗号)
    int prevPage; // 上一页偏移 (-PAGE_SIZE)
    int nextPage; // 下一页偏移 (+PAGE_SIZE)
};

struct PageHeader {
    int recordsCount; // 当前页记录的数目
    int pageState; // 页的状态
};

struct Record {
    int id; // 主键
    std::string data; // 数据(逗号分隔)
    int nextOffset; // 下一条数据的偏移量
};

class Pager {
public:
    std::string path; // 当前页所属表名(即文件名)
    FileHeader fileHeader;
    PageHeader pageHeader;
    int Infimum; // 当前页最小记录
    int Supermum; // 当前页最大记录
    bool isDirty;
    std::vector<int> pageDirectory; // 页目录存储记录的偏移量
    std::vector<Record> records; // 当前页的记录
    
    Pager(const std::string& filePath); // 初始化时从外存读页
    
    Pager* readPage(int ID); // 将页从外存读入内存,这里还没实现BTree,先根据path读文件,遍历页来找目标id所在的页
    void writePage(); // 页的状态设为DIRTY,并在内存中更新页
    bool isFull();
};

简单的脏页机制

在频繁IO的程序中,程序的瓶颈往往是IO速率。

所以这里简单实现一个脏页机制,只有切换数据库等操作再将脏页写回外存,从而保证数据一致性。

这样在频繁对一张表进行操作时,不需要大量IO(比如频繁插入或更新数据后又读数据,在内存的页暂时不写回外存,这样提升效率)

IODemo

Pager.h中有一项bool isDirty,只有进行插入删除更新的操作后,该页标记为DIRTY

同时,在Database.h中有一个当前页Pager* currentPage指向读入内存的当前页,在选中数据库后的操作都是在内存页完成,直到类似切换数据库的指令调用,再写入外存。同时更新currentPage的指向。

批处理测试

这里采用重定向符号来对程序大量输入测试语句。用的bat(批处理程序)

cls
cd .\cmake-build-release\
cls
.\myDBMS.exe < ..\commands.txt

其中,commands.txt中的测试数据为:

show databases;
CREATE DATABASE tmp;
SHOW DATABASES;
create database del;
SHOW DATABASES;
DROP DATABASE del;
SHOW DATABASES;
use demo;
show tables;
create table tmp(id INT, testname CHAR(25), sex INT);
show tables;
drop table tmp;
show tables;
select * from course;
insert into course(cname, cid) values('TETSCOURSE', 13);
select * from course;
select * from student;
insert into student values('TEST',20,2);
insert into student values('TEST2',999,2);
insert into student values('TEST3',999,2);
insert into student values('TEST4',999,2);
insert into student values('TEST5',999,2);
insert into student values('TEST6',999,2);
select * from student;
insert into student(sname,sage) values('TEST7',555);
insert into student(sname,sage) values('TEST8',666);
select * from student;
select sname from student;
select ssex from student;
select sname,sage from student;
select sname,sage from student where sage > 20;
select sname,sage from student where sage < 20;
select sname,sage from student where sage = 20;
select sname,sage from student where sage <> 20;
select sname,sage from student where sage != 20;
select sname,sage from student where (((sage = 20)));
select sname,sage from student where sage > 18 and sage < 35;
select sname,sage from student where (sage > 18) and (sage < 35);
select sname,sage from student where sage < 18 or sage > 35;
select sname,sage from student where (sage < 18) or (sage > 35);
select sname,sage from student where sname = 'chen' and sage = 20;
select * from student;
delete from student where sage > 100;
select * from student;
delete from student where sname = 'TEST' and sage = 20 and ssex = 2;
select * from student;
select * from student where sname = 'chen';
update student set sage = 21 where sname = 'chen';
select * from student where sname = 'chen';
select * from student where sname = 'clay';
update student set sage = 999 where sname = 'clay';
select * from student where sname = 'clay';
exit

About

A reduced mysql compiler. 西电编译原理大作业

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published