第5章：查询执行与优化

逻辑计划与物理算子

逻辑连接说明结果应满足什么关系，物理连接决定怎样计算。嵌套循环、排序归并与哈希连接可实现相同的等值连接，却使用不同内存与 I/O 模式。

迭代器模型让父算子反复向子算子索取元组；向量化按批处理，降低逐元组调用开销；流水线让多个算子连续处理数据，而排序等阻塞算子往往要先消费大量输入。

R 有 1000 页，S 有 100 页，缓冲有 102 页。块嵌套循环可用约 100 页存外表块、1 页扫内表、1 页输出缓冲。以 R 为外表，忽略结果写出成本：

1000+\left\lceil\frac{1000}{100}\right\rceil100=2000\text{ 页 I/O}.

以 S 为外表，则约为 $100+1\times1000=1100$ 。外表小不总是所有连接算法的唯一规则，但在这个模型下能直接算出差异。

若 S 可作为哈希表整体驻留内存，哈希连接也可能只扫描两表一次；实际哈希表有额外开销，不能仅凭数据页数等于缓冲页数断言一定放得下。

外部排序先生成内存大小的有序段，再多路归并。每一完整读写轮通常花费约 $2N$ 页 I/O，最终输出是否物化会改变最后一轮成本。

哈希连接若内存不足，可先分区，再逐对处理对应分区。数据倾斜会让某个分区特别大，破坏均匀散列的理想成本估计，需要额外处理。

优化器利用等价变换、连接顺序和物理算子候选搜索低成本计划。选择率估计依赖直方图、频率和列间相关性。若假设两个条件独立，而它们实际上强相关，中间结果基数就可能严重估错。

过滤下推通常减少数据量，但外连接、NULL、非确定函数和副作用会限制可用的改写。语义等价是前提，成本改善是另一个判断。