查询处理
查询代价的度量
在课本提出的模型中，主要以从存储中传输的块数和随机IO访问数作为估计查询执行代价的两个重要因素。
记\(t_T\)为磁盘子系统传输一个数据块的时间，\(t_S\)为平均的块访问时间（磁盘寻道时间加上旋转延迟），传输一个b个块并进行S次随机IO访问的运算将要花费\(b*t_T+S*t_S\)。
选择运算
选择运算有很多种，根据不同的搜索算法，和不同的存储数据结构，有不同的代价。
图中的\(t_S\)是磁盘寻道时间，\(t_T\)是磁盘传输时间，\(b_r\)是磁盘块数。 \(h_i\)是索引高度
只要提前知道匹配元组的数量，查询优化器就可以根据代价估计在使用辅助索引和使用线性搜索之间进行选择。但是经常无法精确得知。
PostgreSQL使用位图索引扫描的混合算法。获取辅助索引块，但不直接获取，而是标记位图，然后对位图中为1的块进行线性搜索。是一种折中的算法。
而对于复杂的选择，比如包含合取和析取，还有否定等，有其他的方法。
使用合取举例：
- A7(使用一个索引的合取选择)：判断对于其中一个简单条件中的属性是否存在一条存取路径可用。如果可用就用A2~A6的一种选择算法来检索所有记录，再在内存中进行剩下是否满足的判断。
- A8（使用组合索引）
- A9（使用标识交集的合取选择）各个条件涉及的字段上都带有记录指针的索引，该算法对每个索引进行扫描，以获取指向满足单个条件的元组的指针。所有指针的交集就是满足合取条件的元组的指针集合。
- A10（使用标识并集的析取选择）如果析取条件中涉及的属性都带有记录指针的索引，则可以对每个索引进行扫描，以获取指向满足单个条件的元组的指针。所有指针的并集就是满足析取条件的元组的指针集合。
排序
通过在排序码上建立索引，然后使用该索引按序读取关系，可以完成对关系的排序。但这一过程仅仅在逻辑上通过索引对关系进行排序，而没有在物理上进行排序。因此按序读取元组可能导致随机IO访问。
由于读磁盘块的IO代价很高，所以需要专门设计排序算法。
外排序 - 归并算法
对不能全部放入内存中的关系进行的排序被称为外排序。对于外排序最常用的基数是外排序 - 归并算法。
首先设M标识主存的缓冲区中可用于排序的块数。
在第一阶段，创建多个排好序的归并段，其仅包含关系的部分记录。
在第二阶段，对归并段进行归并，假设归并段总数N小于M，可以为每个归并段分配一个块，并且还有剩下的空间能够为输出保留一个块，归并阶段的操作如下：
如果关系比内存大得多，第一阶段可能产生M各甚至更多的归并段，并且在归并阶段为每个归并段分配一个块是不可能的。所以需要分多趟进行。
初始趟：对前M-1个归并段进行归并，然后得到单个归并段作为下一趟的输入。对接下来的M-1个归并段进行类似的操作，直到处理所有的归并段为止。每次这样操作完归并段的数量就会减少为原来的1/(M-1).
代价分析：令\(b_r\)为包含关系r的记录块数，在第一阶段读入关系的每个块然后将它们重新写出，共需要\(2b_r\)次块传输。初始归并段的数量为\(\lceil \frac{b_r}{M} \rceil\)，在贵宾过程中，每次在一个归并段中读入一个块会导致大量寻道，所以尽量一次读取或写入更多的块，表示为\(b_b\)，这就需要将\(b_b\)个缓冲块分配给输入的归并段和输出的归并段。每趟归并可以归并\(\left\lfloor \frac{M}{b_b} \right\rfloor -1\)个归并段。总共需要的趟数为\(\left\lceil \log_{M/b_b-1} \left\lceil \frac{b_r}{M} \right\rceil \right\rceil\)。
连接运算
嵌套循环连接
这个是最简单的做法，但是代价昂贵，对于每条记录都要进行一次寻道和块传输，最坏情况下一条记录对应一次块传输。
需要\(b_r * b_s + b_r\)次读内存。（在只能放下一个缓冲区的情况下）
块嵌套 - 循环连接
如果缓冲区没办法放下任何一个关系，使用基于每个块的方式处理而不是基于元组处理仍然能带来性能上的提升。
这种做法在最坏情况下只需要\(b_r*b_s+b_r\)次块传输，和\(2*b_r\)次寻道（对内层关系的每次扫描需要一次寻道，对外层关系的每次扫描需要一次寻道）
进一步的优化：每次读入都尽可能地多用几次，比如可以读入M-2个外层关系地块，然后读入1个内层关系的块，然后进行连接，这样内层关系的扫描次数从\(b_r\)次减少到了\(b_r/(M-2)\)次。
总次数就是\(\lceil \frac {b_R} {(M-2)} \rceil * b_S + b_R\)（把R作为外层循环，假设R是比较小的，因为相乘的结果总是不变的，但是后面那个常数还能再小一点。）
如果内层循环的连接属性上有索引可用，可以使用更高效的索引查找来代替文件扫描。
归并 - 连接
该做法可以用于计算自然连接和等值连接，假设关系\(r(R)\)和\(s(S)\)都按照\(R\cap S\)排序，则可以对两个关系进行归并，在归并过程中进行连接。
该算法要求每个\(S_s\)元组集合都能够装入主存。如果不能装入，就使用多趟算法，类似上面的块嵌套 - 循环连接。
如果两个关系在连接属性上都存在辅助索引时，可以对未排序的元组执行归并-连接运算的一种变种。通过索引扫描记录，从而顺序检索记录。但是并不是物理逻辑下最优的。
注意代价还引入了一个\(b_b\)，代表的是分配给每个归并块的缓冲块块数（因为在比较大的时候没办法整个归并块放入内存）
散列 - 连接
使用散列函数h来划分两个关系的元组，基本思想是把每个关系的元组划分成在连接属性值上具有相同散列值的集合。
这种连接方法基于这样的思想：如果两个元组在连接属性上具有相同的值，那么它们在散列值上也具有相同的值。如果散列值不相同，则两个元组不可能匹配。
其他运算
去重 - 和排序等价。
投影 - 一次扫描就行了。
集合运算 - 并交合集合差运算，首先要对两个关系进行排序，然后对每个已排序的关系扫描一次以产生结果。
外连接（比如左外连接）：首先计算对应的连接，将结果存为对应的临时关系\(q_1\)，接着计算\(r-\prod_R(q_1)\)已得到r中未参与连接的元组。
聚集：和去重一样的方式实现。
表达式执行
可以使用物化方法，将一个表达式构建为一个表达式树，然后从叶节点往根执行运算。
有一个技术是double buffering（双缓冲），其中一块用于执行算法，另一块用于写出结果，通过并行执行CPU活动和IO活动，允许算法执行的更快。
另一种方式是通过流水线的方法，通过减少产生的临时文件数，可以提高查询的效率。可以将多个能够同时做的运算合并到一起，比如选择和投影。这种执行方式叫做流水线执行。
流水线可以按下面两种方式之一来执行：
- 需求驱动流水线：在需要结果时，才执行运算。
- 生产者驱动流水线：在可以执行运算时，就执行运算。
需求驱动流水线每个运算都可以作为迭代算子实现，提供open()、next()、close()方法。调用open()后，对next()的每次调用都会下一个输出元组。只有在调用迭代器的时候才会进行运算。
生产者驱动流水线会创建一个缓冲区保存一个运算传递给下一个运算的元组，不同运算的进程和线程会并发执行。流水线底部每个运算不断产生输出元组，并将其放入输出缓冲区，直到该缓冲区已满。然后就会等待其父运算将该元组从缓冲区移除。
表达式树中的每条边可以是物化的（阻塞的）/流水化的（非阻塞的）
重点
查询处理过程：SQL解析、语法/语义检查、查询树/查询图的生成
代数优化与物理优化
查询优化：基于规则的优化、基于代价的优化
常见执行计划：嵌套循环连接，排序 - 合并连接，哈希连接
嵌套循环（Nested-Loop），Block Nested-Loop、分页大小，缓存替换策略等进行I/O代价分析