数据库的语句编译主要步骤：
- 词法分析/语法分析：建立查询的分析树；
- 查询计划重写：分析树被转化为初始查询计划（查询的代数表达式），然后将查询计划转化为一个预期执行时间较小的等价计划；
- 物理计划生成与执行：将逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序，逻辑计划被转化为物理查询计划；然后将这些计划应用到数据库的数据上，得到并返回结果；
本文先将简单介绍物理查询计划的执行（最后一阶段），后续将介绍编译的各个阶段。
物理计划操作符
表扫描策略：读一个关系R的所有元组或满足谓词的元组，扫描的基本方法：
- 表-扫描：扫描整表；
- 索引-扫描：根据索引进行扫描；
- 顺序-扫描：内存排序，多路归并排序；
基本操作 这里将基本操作分成如下三类：
- 一次单个元组，一元操作：不需要一次性装入整个关系，甚至不需要关系的大部分，例如：选择，投影。可以一次选择一个块，使用内存缓冲区，并产生输出。
- 整个关系，一元操作：一次从内存中看到所有或大部分元组，因此，一趟算法局限于大小为约为M（内存中可缓冲区的数量）或更小的关系。例如：分组操作符，去重操作符。
- 整个关系，二元操作：其他操作类型，例如：并，交，差，连接和积的集合形式以及包形式。至少每一个关系都要求至少一个操作对象的大小限制在M以内。
一趟算法
这里主要介绍基本操作符的一趟算法和嵌套循环链接（Nested-Loop-Join）。
基本操作符的一趟算法
一个操作对象数据较少，能够一次性读入内存。下面将对前面提到的三类操作符进行分别叙述。
一次单个元组操作： 将数据读入缓冲区，然后执行一元操作，把数据写入到缓冲区，最后输出到指定位置。
整个关系的一元操作：
对于去重操作：为了去重，我们可以一次一个地读取R的每一块，然后对每一个元组，需要判断：
1）. 第一次看到元组，将它复制到输出；
2）. 以前见过这个元组，不必输出它；
对于分组操作：在每一个元组创建一个项，根据具体分组操作进行执行：
1）. 对于MIN，MAX聚集来说，分别与当前值进行判断，如果合适，则将结果修改为新的值；
2）. 对于任意COUNT聚集，每个元组加1；
3）. 对于SUM，如果不为NULL，则累加值加上属性的值；
4）. AVG，需要记录两个字段，SUM和COUNT；
二元操作：先将较小的关系读入到内存中，并进行处理；然后再处理另一个关系；
1）集合并：将S读到内存的M-1个缓冲区中，并建立一个查找结构，然后将S复制到输出；然后读取R的每一个元组t，观察t是否在S中，如果不在则复制t到输出，否则跳过；
2）集合交：将S读到M-1个缓冲区中，并建立关键字的查找结构；然后读取R的每一个块，并对R的每一个元组t，观察t是否也在S中。如果在，则复制t到输出，否则跳过；
3）集合差（S-R）：将S读到内存并建立查找结构，然后读取R的每一块，并依次检查每一个元组t，如果t在S中，那么将t从S的内存中删除。最后将S剩余的元组复制到输出；
4）包交：每一个不同元组有对应的计数，包交即按照对应元组的计数进行交集计算，例如，<(a, 3), (b,4)> 和<(a, 2), (b, 5)>，则包交为<(a,2),(b,4)>；计算方法为与集合交相似，只是在记录中有计数器，然后根据计数器进行计算；
5）包差：包差与包交相对应，对于上例中，包差结果为：<(a, 1)>;
6）积：将S读到内存中，然后读取R的每一个块，对于R中的每一个元组t，与内存中S的每一个元组连接，在每一个连接而成的元组一形成后将其输出；
7）自然连接：R（X，Y）和S（Y，Z），读取S的所有元组，并构造以Y的属性为查找关键字的内存查找结构；读R每一块，利用R元组t中的Y属性作为查找关键字在S中查找，在S中每一个匹配的元组，将它与t连接后形成一个元组，并将结果输出。
嵌套循环链接
- 基于元组的嵌套循环连接算法
For S的每个元组s DO： For R中的每个元组r DO： IF r与s连接形成元组t THEN： output t； - 基于块的嵌套循环连接算法
1）对作为操作对象的两个关系的访问均按块组织；
2）使用尽可能多的内存来存储属于关系S的元组，S是外层循环的关系；For S中每一大小为M-1块的chunk： 将这些块读入主存缓冲区中； 将其元组组织为查找结构，查找关键字是R和S的公共属性； For R的每个块b： 将b读入主存； FOR 块b的每一个元组t DO 找出s在主存中的元组中那些能与t连接的元组； 输出t与这些元组中每一个的连接；
两趟算法
数据量太大而无法装入可利用的内存；可以采用多趟的算法进行处理，这里介绍两趟算法，更多趟的算法与两趟算法基本上类似。这里介绍一下三种算法：
- 基于排序的两趟算法；
- 基于散列的两趟算法；
- 基于索引的算法；
基于排序的两趟算法
这里先介绍两阶段归并排序，然后利用排序进行对应的操作符操作。
两阶段多路归并排序
阶段1: 不断将R中元组放到M个缓冲区，利用内存排序算法对它们进行排序，并将排序结果存到外存中；
阶段2: 将排好序的子表进行归并：将M-1个有序子表进行归并，执行以下操作：
1）找到所有子表中第一个元素的最小值；
2）将最小的元素移到输出块的第一个可用位置；
3）如果输出块已满，则写入到外存，并初始化输出缓冲区；
4）如果刚被取出最小元素的缓冲块的元素已耗尽，则将同一个有序子表中的下一个块读入到元素耗尽的缓冲块。如果没有块，则不执行操作。
利用排序去重
在第二阶段不断地复制每一块的第一个未考虑的元组t到输出块，并忽略与它相同的所有元组，同时将t拷贝到输出块，并将输出块中所有的t删除。因此，输出块对R的任何一个元组都只有一个实例；且它们是有序的。
利用排序分组和聚集
具体算法如下：
1）将R的元组每次读取M块到内存中，用L的元组属性作为排序关键字，对每M块进行排序，并将结果写入到外存；
2）为每个子表使用一个主存缓冲区，并将每一个子表的第一块装入其缓冲区；
3）在缓冲区可以获取的第一个元组反复查找排序关键字（分组属性）的最小值，这个最小值v成为下一分组，我们为它：
a）准备在这个分组的列表上计算所有聚集；
b）检查每个排序关键字为v的元组，并累积所需聚集；
c）如果一个缓冲区空了，则用同一子表中的下一个块替换它；
基于排序的并算法
具体算法如下：
1）创建R和S的排序子表；
2）为R和S的每一个子表使用一个内存缓冲区，用对应子表的第一块初始化个缓冲区；
3）重复地在所有缓冲区中查找剩余的第一个元组t，将t复制到输出，并且从缓冲区中删除t的所有副本。
基于排序的交和差算法
基本算法框架与并算法类似，在处理时采取以下策略：
a）对于集合交，如果t在R和S中都出现就输出t；
b）对于包交，输出t的次数是R和S中出现次数的最小值，如果有一个次数为0，则不输出；
c）对于集合差，R-S，当且仅当t出现在R中但不出现在S中时，输出t；
d）对于包差，R-S，输出t的次数是t在R中出现的次数减去在S中出现的次数，当R次数不大于S中的次数时，则不输出；
基于排序的连接算法
首先介绍一个简单算法，然后介绍一个较为有效的连接算法。
1. 简单算法
1) 用Y作为排序关键字，使用多路归并算法对S和R分别进行排序;
2) 仅用两个缓冲区，分别读入S和R的最小缓冲块，重复以下操作：
a） 在当前S和R的块的前端查找连接属性Y的最小值y；
b） 如果y在另一个关系的前部没有出现，则删除具有排序关键字y的元组；
c） 否则，找到两个关系中具有排序关键字y的所有元组。如果需要从排序的R和/或S中读取块，直到确定每一个每一个关系都不再有y的元组；
d） 通过连接R和S中具有共同的y值的元组所能形成的所有元组；
e） 如果一个关系在内存中已没有未考虑的元组，则重新加载缓冲区；
2. 更为有效的算法
归并（排序）-连接算法。
1） 用Y作为排序关键字，为R和S创建大小为M的排序子表；
2） 将每一个子表的第一块调进缓冲区，假设总共不超过M个子表；
3） 重复地在所有子表的第一个可以得到元组中查找最小的Y-值y。识别两个关系中具有Y-值y的所有元组，输出R和S中具有此公共Y-值所有元组的连接。
基于散列的两趟算法
首先将一个关系划分到M-1个桶中：M-1个缓冲区，如果缓冲区满，则写入到磁盘。
基于散列的去重算法
加入每个桶足够小，而能够装入到内存，那么基于散列的两趟算法就可行。基本思想就是对每一个桶单独进行处理。
基于散列的分组和聚集算法
将关系划分成桶后，然后对每一个桶进行单独的处理。
其他基于散列的算法也类似，包括：基于散列的并，交，差，连接等算法。
基于索引的算法
本章节将将蛋介绍基于索引的相关算法。
聚集和非聚集索引
如果一个关系的元组紧缩到能够存储的这些元组的尽可能少的块中，那么关系就是聚集的。
如果索引查询关键字的一定固定值的所有元组都出现在能够容纳它们的尽可能少的块中，那么就是聚集索引。
基于索引的操作
1） 基于索引的选择
如果是聚集的，那么有性能的优化，如果是非聚集的，仍需要读取整表；
2） 基于索引的连接
对于S（X，Y）和R（Y，Z），分别在Y上建立索引。对于R中的每一个块的每一个元组，根据S的Y索引进行查找，如果找到则输出。
3） 使用有效索引连接
可以采用普通的排序连接，zig-zag连接，类似归并方法。
多趟算法
使用多趟的算法可以在两趟算法基础上进行扩展。
例如对于两阶段多路排序算法，进行扩展：
1）基础：如果R可以装入M个块中，那么读入内存，使用内存排序，并将排序结果写入内存；
2）归纳：如果R不能够装入内存，将R的块分成M个组，称作R1，R2，…，R3。对每个i=1，2，…，M，递归排序。然后将M个排序的子表合并。
缓冲区管理策略
1）最近最少使用（LRU）：丢出最长时间内没有读或写的块；
2）先进先出（FIFO）：被同一个块占用时间最长的缓冲区被清空；
3）“时钟”算法（第二次机会）：每个缓冲区有一个标志（0或1），当一个块被读入或访问后，置为1；如果需要新的缓冲区时，按照顺时针旋转，查找到第一个为0的块，如果标志时1，则设为0；
4）系统控制：使用强制方式保护一些数据块；
总结
本文主要介绍数据库中物理计划执行，介绍了数据量较小的一趟算法，数据量较大的两趟算法和多趟算法，最后介绍了缓冲区管理的策略。
更多内容请参阅其他文章：