什么是查询处理
下图是查询处理的基本步骤
首先我们输入一串 sql语句，这就是 query 查询，然后会交给 parser 解析器进行内部的处理，比如将 sql语句 转换成 关系代数 等，同一个操作可以有不同的 关系代数表达式，我们最好是选择 执行代价 最小的那一种，这就是 optimizer 优化器的作用了，它会生成 execution plan 查询计划，然后把它交给 evaluation engine 执行引擎执行，最后生成 查询结果 并返回
所以基本步骤就是：
- 查询解析
sql ---> 关系代数表达式 - 查询优化
关系代数表达式 ---> 查询计划 - 查询执行
查询计划 ---> 结果
查询解析 --- parser
假设我们有一个语句 Dog does math.
词法分析
就是把输入的语句拆分成一个一个的 token 单词序列
那们我们会把上述的语句拆分成单词序列，如下：
Dog does math .
语法分析
分析我们获得的token序列是否符合定义的语法
在上述的语句中，就是英语中很简单的 主谓宾 的语法
Dog是 主语，它的后面 预期 是 谓语，does 正好是一个 谓语，符合条件，它的后面 预期 是 宾语，math 正好是一个 宾语，符合条件，这个句子已经差不多完整了，最后是 预期 是结尾标志.，正好符合，所以这个句子是符合语法的
语法分析，就是确保输入是符合我们的 预期 的
语义分析
语义分析，就是要结合语境了，也就是上下文，确保这个句子的意思是正确的
我们这句 Dog does math. 符合语法，但他的意思是 小狗在做数学题，那这个意思就不正确了，正常来说应该是 人类在做数学题，所以这个句子就 语义错误 了
总结
在实际的实现中，词法分析主要是区分 关键字，标识符，常量等等单词，然后语法分析是将这些token组合成树的形式，生成 抽象语法树AST，语义分析，则是结合上下文，判断表名、列名、变量是否正确定义、是否存在等等，生成的是 查询树
查询分流 --- traffic cop
查询分流 就是 区分 简单和复杂的查询指令，后续做相应的处理，比如将复杂的命令传递给 重写器
对简单命令执行最少的优化，把更多的时间投入到复杂的命令上，从而减少处理时间
查询重写 --- rewriter
查询重写：利用已有语句特征和关系代数运算来生成 更高效 的 等价 语句
2个基本原则：
- 等价性：原语句和重写后的语句，输出结果相同
- 高效性：重写后的语句，比原语句在执行时间和资源使用上更高效
查询优化 --- optimizer
一个给定的SQL查询（以及一个查询树）实际上可以以多种不同的方式执行，每种方式都会产生 相同的结果集
优化器 的任务是创建最佳执行计划
查询执行 --- executor
执行器：对优化器输出的计划进行 递归 处理以提取所需的行的集合。是一种 需求驱动的流水线执行机制，每次调用一个计划节点时，它都必须再传送一行，或者报告已完成传送所有行
假设有一个查询，它执行以下操作：
- 从一个表中扫描所有记录
- 过滤掉不符合条件的记录
- 对结果进行排序
- 将最终结果返回给用户
在传统的非流水线执行中，数据库可能会 一次性将所有记录读取到内存，然后进行处理，这会消耗大量资源和时间。而流水线执行机制则不同，它会 逐步处理每一行数据：
- 表 扫描节点 读取 一行 数据
- 这行数据 传递 给 过滤节点，检查是否符合条件
- 符合条件的数据传递给 排序节点，排序后传给下一节点
每当一个节点处理完一行数据，它会将该行传递给下一个节点，或者报告数据处理完毕，说明没有更多行可以处理。这就像是流水线一样，每个节点只负责自己的那部分工作，做完了就交给下游，这样层层筛选，就能得到最后的结果了
查询成本度量
查询成本通常通过回答查询的总耗时来衡量，受到磁盘访问、CPU 和网络通信等因素的影响
成本可以通过响应时间或资源消耗来评估
磁盘访问的成本
寻道时间（简单来说就是 定位），读写块的数量
可以通过使用 缓冲区 减少 磁盘IO，可用于缓冲区的内存容量需要考虑其他 并发查询 和 操作系统进程，仅在 执行期间 才能确定，通常要用 最坏情况 评估
Slection Operation
文件扫描
A1 (linear search)：线性搜索，逐个扫描 每个文件块并检查所有记录，看它们是否满足选择条件
成本估算：
- br（块传输）：关系r中记录的文件块数量
- 1次寻道：定位到 文件起始位置后 向文件的后续块 顺序扫描，无需额外的寻道（假设文件存储是连续的）
如果选择条件是 基于键属性
- 可以在找到满足条件的记录时停止：当选择条件是基于某个键属性（例如主键）时，一旦找到符合条件的记录，就可以停止扫描，不必继续遍历后面的记录
在这种情况下，假设记录是随机分布的，平均情况下大约需要扫描一半的块，因此成本变为：(br / 2)（块传输） + 1次寻道
索引扫描
索引扫描 是指通过数据库的索引来检索数据的过程
在进行选择操作时，选择条件必须匹配索引的 搜索键。换句话说，查询的条件必须 依赖于某个字段
-
A2 (primary index, equality on key):
-
定义：
基于 主键索引 进行查询的。当查询条件是 主键等值查询 时，索引会直接定位到目标记录 (简单来说就是只要1条记录)
-
成本:
hi+1: 索引查询 hi 次，最后 1 次就是定位到最终结果(Tt + Ts): 数据块的传输时间和寻道时间
-
-
A3 (primary index, equality on nonkey):
-
定义:
基于 主键索引 进行查询的情况，但查询条件使用的是 非主键字段（即非主键上的等值查询）。这种情况下，尽管使用主索引，但 返回的匹配记录通常不止一个，而是多个
-
成本:
b: 表示包含匹配记录的块的数量（匹配记录可能多个，那么块也可能多个）
其实和
A2的成本计算差不多，会比它多Tt*(b - 1)，如果b为1，那就是和A2一样了。这里Ts只需要额外一次是因为我们是 主键索引，记录通常会按照 主键索引 排序，所以只需要1次额外定位，顺序扫描即可
-
-
A4 (secondary index, equality on nonkey):
-
定义:
基于 辅助索引 进行查询的情况，查询条件使用的是 非主键字段（即非主键上的等值查询）
- 查询的非主键字段 是候选键：这种情况下，辅助索引直接能够 定位到唯一的记录
- 查询的非主键字段 不是候选键：这种情况下，多个记录可能匹配 这个条件，查询可能需要访问 多个数据块
-
成本:
- 查询的非主键字段 是候选键 （唯一值匹配）：与
A2成本一致
-
查询的非主键字段 不是候选键 （多值匹配）：
n表示的是匹配的记录数，可能分布在不同的块中
这里使用的是 辅助索引，所以记录通常在物理存储上是不连续的，匹配的记录会更加分散
- 查询的非主键字段 是候选键 （唯一值匹配）：与
-
Sorting
外部排序 -- External Sort-Merge
-
Created Sorted Runs
-
初始状态：假设当前有一个未排序的大型数据集。我们将其 分成多个小块，每个小块能够装入内存进行排序
步骤： -
读取数据：从 磁盘 读取M个数据块到 内存 中。这里的 M是内存可以容纳的数据块数
-
内存排序：对内存中的数据块进行排序。这个步骤会使用诸如快速排序等常见的内存排序算法，因为这些数据块在内存中，大小足以适应内存排序
-
写入已排序数据：将已排序的数据 写回磁盘，并 标记 为一个“运行”（run）。每次生成的已排序数据集称为一个“已排序运行”，它们依次标号为 Ri（i 是运行的编号），直到所有数据都被处理完成
-
重复，直到所有数据都被分成多个已排序的“运行”块。假设最终有N个这样的运行，N即为运行的数量
-
-
Merge the Runs
-
N路归并（N-way merge):
- 系统有N个内存块用于存储每个输入运行的当前记录（即每个已排序块的缓冲区）。另外，还有1个内存块用于存储输出结果的缓冲区
- 对于每个输入的运行（数据块），读取其第一个块（即数据的前几个记录）到相应的缓冲区页面中
-
重复步骤：
-
从所有N个输入缓冲区中，选择 最小 的记录（按排序顺序），即当前各个缓冲区中最小的那个记录
-
将选中的最小记录 写入到输出缓冲区。如果输出缓冲区已满，将缓冲区中的内容写回到磁盘中
-
将选中的记录从其原始输入缓冲区中 删除
-
如果某个输入缓冲区中的数据已经被完全消耗（即空了），则从该运行中 读取下一个 数据块（如果有）并将其加载到缓冲区
-
-
结束条件：
直到所有的输入缓冲区都没有数据为止。此时，所有的记录都已经被合并到输出缓冲区，并最终写回磁盘。
-