Database Inside 是一个新开的小系列，旨在为初学者建立一个对数据库的的基本观感，或者说直觉。本系列定位，求短不求全、用意不用力。前因后果、内涵外延，点到即止。文末会给些许参考，若不尽兴，可自行探求。
SQL 的三维侧写
SQL 起源于上世纪七十年代的 IBM R 系统，是一个针对关系型数据库的声明式查询语言。一句话引出三个点：
1. 关系型（relational）：基于关系代数理论的一种数据建模方式，其他的建模方式如文档数据库、图数据库等。以 SQL 表的方式来理解，可以将任何数据集抽象为一张二维表，每行一个元组（tuple），每个元组有多个属性列；将对数据集的查询抽象为一组运算符的组合，也即二维表的一组变换。常见的运算符：
关系表的变换
- 选择 (σ)：针对单张二维表，选择其中一些行；对应 SQL 中 where 子句
- 投影 (π)：针对单张二维表，选择其中某几列；对应 SQL 中 select xx 子句
- 自然连接 (⋈)：针对两张二维表，按某一列上等值进行合并；对应 SQL 中 join 子句
2. 声明式（declarative）：与命令式（imperative）相对，可类比编程中的接口。侧重于描述而非实现。举个例子感受一下：
- 声明式：“找出教三今天的空闲教室”
- 命令式：“1. 找出教三所有教室 2. 对于每间教室查询课表看其是否空闲 3. 如果空闲则加入结果集”
3. 查询语言（Query）：顾名思义，这是一门专门用来做诸如“找教室”一类的对满足条件的数据进行查询的语言。虽然他是图灵完备的，但一般不用于像通用编程语言 C++ 等来编写复杂软件。
SQL 执行过程
CMU 15445 课程图
SQL 也是一门语言，因此其执行过程和编译器前端类似，参考上图（来自 cmu 15-445）可粗分为数个步骤：
- 解析（Parsing）：将适合人阅读的 SQL 语句进行分词（token），并进行基本语法检查。然后基于关系代数，构建成抽象语法树（AST，Abstract Syntax Tree）。其中叶子节点为表，中间节点为运算符。
- 校验（Validating）：检查所插入数据格式是否满足之前所定义的模式。举个例子，学生表定义了学号、姓名、课程三列，则插入的数据每一行不能多于三个属性。
- 计划（Planning）：使用模式信息，将语法树中元素（各种有意义的名称）转成内部表示（各种 无意义且不重复 id），生成逻辑计划。
- 优化（Optimization）：逻辑计划由多个数据变换操作构成，我们可以基于关系代数中算子的一些性质（比如交换性、结合性），调整变换顺序和组合，使得查询所耗费资源（包括计算、存储和网络带宽等）最小，最后生成物理执行计划，常包括基于规则和基于代价的两种方式。
- 执行（Execution）：将优化过后的执行计划（一般仍是树形）进行执行。包括从外存捞数据到内存和在内存中对数据做各种变换。不管数据在外存表现为什么形式，捞到内存后可以理解为一张前面提到的二维表，然后按树结构施加各种算子，进行计算。
有时候校验阶段也被归入解析范畴，有时候执行阶段中的表达式求值会单拎出来说，但总的职责就这几个，排列顺序基本确定，只是划分可能有出入。
之后对于每个阶段，会分别出一篇小文。
参考
- https://15445.courses.cs.cmu.edu/fall2022/notes/02-modernsql.pdf
- https://15445.courses.cs.cmu.edu/fall2022/notes/14-optimization.pdf
- Database System Concepts, Chapter 15 Query Processing and Chapter 16 Query Optimization
