ch15 查询处理

查询处理基本步骤

• 语法分析与翻译
• 优化
• 执行计划
• 输出结果

查询处理

• 一个关系代数表达式有可能有很多等价表达式

$${\sigma }_{salary<75000}({\mathrm{\Pi }}_{salary}(instructor))$$$${\mathrm{\Pi }}_{salary}({\sigma }_{salary<75000}(instructor))$$

• 即便是同一个表达式也有不同算法来执行（用不用索引，...）
• 用于执行一个查询的源语操作序列叫做查询执行计划
  • 方案一：使用$salary$的索引找到$salary<75000$的$instructor$
  • 方案二：通过扫描$instructor$的每个元组找出满足$salary<75000$条件的元组
• 查询优化：在所有的等效执行计划中选择具有最小查询执行代价的计划

查询代价的度量

• 使用该查询对各种资源的使用情况进行度量
  • 磁盘存取
  • 执行一个查询所用的CPU时间
  • 网络通信代价
• 磁盘上存取是主要代价
  • 搜索磁盘次数*平均寻道时间
  • 读取的块数*平均块读取时间
  • 写入的块数*平均块写入时间
    • 写入的代价通常更大，因为写完得读一遍确保正确
• 我们只用传输磁盘块数以及搜索磁盘块数来度量查询计算计划的代价
  • $t_r$——传输一个块的时间
  • $t_s$——磁盘平均访问时间
  • 传输$b$个块以及执行$s$次磁盘搜索的操作代价：
  $$b\ast t_T+s\ast t_S$$
  • 忽略了CPU时间，实际应用应该考虑
  • 代价估算没有包括将操作的最终结果写回磁盘的代价

选择运算

• 等值运算
• 比较运算
• 复杂的选择运算，使用与或非连接

选择运算之文件扫描

• 算法A1（线性搜索）
  • 在线性搜索中，系统每扫描一个文件块，对所有记录进行测试，看它们是否满足条件
  • 时间代价 = $b_r$ 次磁盘传输 + $1$ 次磁盘搜索，其中 $b_r$ 代表文件中磁盘的块数
  • 对于作用在码属性上的等值选择操作，找到后就可以立即停止，平均时间代价 = $\frac{b_r}{2}$ 次磁盘传输 + $1$ 次磁盘搜索
  • 线性搜索可以被应用可以应用在任何情况，二分查找通常没有意义（不连续没顺序），除非有索引

利用索引的选择

• 索引选择：使用索引的搜索算法
  • 选择条件必须是索引的搜索码
• A2（主索引，码属性的等值比较）：对于具有主索引的码属性的等值比较，可以使用索引检索到满足相应等值条件的唯一一条记录
  • $Cost=(h_i+1)\ast (t_T+t_S)$，将$h_i$个块调入内存（不连续，每次都得搜索），找到了正确的$K$值后还需要将对应的块调进来
• A3（主索引，非码属性等值比较）：检索多条记录
  • 记录在文件中必须连续存储，$b$代表含指定搜索码值的记录的磁盘块数
  • $\begin{array}{r}Cost=h_i\ast (t_T+t_S)\\ +t_S+t_T\ast b\end{array}$，对树检索拿到第一个地址需要的时间是$h_i\ast (t_T+t_S)$，然后根据指针继续搜索找到第一条正确记录花费时间$t_S$，最后将所有正确的块全部调出来花费时间$t_T\ast b$
• A4（辅助索引，等值比较）
  • 如果等值条件是码属性上的，该策略能拿到唯一满足条件的记录
    • $Cost=(h_i+1)\ast (t_T+t_S)$
  • 索引字段是非码属性，可检索到多条记录
    • 每个$n$匹配的记录可能在不同的磁盘块中
    • 最坏情况是每一条自己一个块，$Cost=(h_i+n)\ast (t_T+t_S)$
    • 查询代价非常大

涉及比较的选择

• ${\sigma }_{A\le V}(r)$ 或者 ${\sigma }_{A\ge V}(r)$ 的实现方法
  • 线性搜索
  • 使用索引，A5或者A6
• A5（主索引，比较）（$A$上的关系是有序的）
  • 对于 ${\sigma }_{A\ge V}(r)$ ，使用索引找到 $\ge V$ 的第一个元组，从这里开始顺序扫描关系
  • 对于 ${\sigma }_{A\le V}(r)$ ，只需要顺序扫描关系找到 $>V$ 的第一个元组，不需要用索引
• A6（辅助索引，比较）
  • 对于 ${\sigma }_{A\ge V}(r)$ ，使用索引找到 $\ge V$ 的第一个元组，从这里开始顺序扫描索引，找到指向记录的指针
  • 对于 ${\sigma }_{A\le V}(r)$ ，只需要顺序扫描索引叶子节点找到指针，直到找到第一个 $>V$ 的索引项
  • 在这两种情况下检索记录时，每个记录都需要一次I/O，线性搜索的代价可能更小

复杂选择的实现——合取

• 合取：${\sigma }_{{\theta }_1\wedge {\theta }_2\wedge ...\wedge {\theta }_n}(r)$
• A7（使用一个索引的合取选择）
  • 选择一个 ${\theta }_i$ 以及A1到A6的算法使得 ${\sigma }_{{\theta }_i}(r)$ 的代价最小
  • 在内存中检索对检索到的记录验证其他条件是否成立
• A8（使用复合索引的合取选择）同时使用多个复合索引
• A9（使用标识符交集的合取选择）
  • 每个条件都有索引的记录指针或者记录标识
  • 获取所有的记录的指针集合，取交集
  • 按照交集结果取数据
  • 如果存在没有索引的条件则需要在内存中对检索到的记录进行测试

复杂选择的实现——析取

• 析取：${\sigma }_{{\theta }_1\vee {\theta }_2\vee ...\vee {\theta }_n}(r)$
• A10(使用标识符并集的析取选择)
  • 每个条件都有索引的记录指针或者记录标识
  • 获取所用的记录指针集合，取并集
  • 按照并集结果取数据

复杂选取的实现——否定

• 否定：${\sigma }_{\mathrm{\neg }\theta }(r)$
• 对文件进行线性扫描
• $\mathrm{\neg }\theta$ 的数据很少，并且有可用索引，可以用索引找到 $\mathrm{\neg }\theta$ 的数据

排序

• 为什么排序
  • order by语句
  • 连接操作的计算中排序的数据很有用
• 对于适合内存的关系可以直接使用快速排序
• 对于内存中无法容纳的关系，外部归并排序是一个很好的选择

外部归并排序

1. 第一阶段：创建多个排好序的归并段
2. 第二阶段：多趟归并

• 代价分析
  • 为了减少寻道次数，令 $b_r$ 为关系内所有元组数量，$b_b$ 为每个归并段一次可以写入/读出的块数，每个初始归并段有 $M$ 个元组，每趟归并可以归并 $\lfloor M/b_b\rfloor -1$ 个归并段（留一个块往他身上归并），总归并次数 $\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil$
  • 块传输的代价：每一趟都是 $2b_r$ （所有元组都得走一遍，读一次写一次），最后一次直接传给下个运算无需归并减掉一次，共 $b_r(2\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil +1)$
  • 寻道的代价：$\begin{array}{r}2\lceil b_r/M\rceil +\lceil b_r/b_b\rceil \ast \\ (2\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil -1)\end{array}$ , 初始化归并段花费 $2\lceil b_r/M\rceil$ ，归并的最后一次无需继续寻道

连接运算

• 连接运算分类：
  • 嵌套循环连接
  • 块嵌套循环连接
  • 索引嵌套循环连接
  • 归并连接
  • 散列连接
• 基于代价估计来选择合适的连接方法

嵌套循环连接

• 计算 $\theta$ 连接 $r{\bowtie }_{\theta }s$

for each tuple t_r in r do begin
    for each tuple t_s in s do begin
        测试元组对(t_r,t_s)是否满足连接条件θ
        如果满足，把t_r·t_s加到结果中
    end
end

其中的t_r·t_s指的是两者的连串 $\stackrel{⌢}{t_r{t}_s}$，即符合要求的连串加入到结果集合里

• $r$称为外层关系，$s$称为内层关系
• 无需索引，不管连接条件是什么
• 代价很大，逐个检查关系中元组对（从笛卡尔积里挑出来）
• 代价：在最坏情况下，缓冲区只能容纳每个关系的一个数据块，需要 $n_r{b}_s+b_r$ 次传输，$n_r+b_r$ 次磁盘搜索，$n_r$ 是外层记录数，$b_s$ 是内层块数，$b_r$ 是指外层需要更换块的次数
• 如果有较小的关系能放入内存中，我们选择它作为内层关系，此时只需要 $b_r+b_s$ 次块传输 + $2$ 次磁盘搜索

块嵌套循环连接

• 循环嵌套连接的一个变种，其中内层关系的每一块和外层关系的某一块对应

for each block B_r of r do begin
    for each block B_s of s do begin
        for each tuple t_r in B_r do begin
            for each tuple t_s in B_s do begin
                测试元组对(t_r,t_s)是否满足连接条件θ
                如果满足，把t_r·t_s加到结果中
            end
        end
    end
end

• 代价：最坏情况下需要 $b_r{b}_s+b_r$ 次块传输 + $2b_r$ 次磁盘搜索，对于外层关系的每一个块，内层关系$s$的每一块只需要读取一次
• 最好的情况：有一个关系能放在内存里作为内层关系，此时只需要 $b_r+b_s$ 次块传输 + $2$ 次磁盘搜索
• 改进嵌套循环算法和块嵌套循环算法
  • 在块嵌套循环中将内存中 $M$ 块里的 $M-2$ 块都作为外层关系的块单元，剩下两个作为内存关系和输出的缓冲区，此时 $Cost=\lceil b_r/(M-2)\rceil \ast b_s+b_r$ 次块传输 + $2\lceil b_r/(M-2)\rceil$ 次磁盘搜索
  • 如果等值连接中连接的属性是内层的码，那么内层只要找到第一条匹配的元组就可以在终止
  • 使用缓冲区的剩余块，对内层循环轮流做向前向后的扫描（LRU替换策略）
  • 内层循环连接属性上有索引可以使用更有效的索引查找法替代文件扫描法

索引查找法

• 可以代替文件扫描法
  • 连接时自然连接或者等值连接
  • 内层关系连接属性上存在可用索引（可以为了计算临时建一个索引）
• 对于外层关系 $r$ 的每一个元组 $t_r$ ，可以利用索引查找满足与 $t_r$ 的连接条件的 $s$ 中的元组
• 最坏情况：缓冲区只能容纳关系 $r$ 的一块和索引的一块，对于外层关系$r$的每一个元组，需要对$s$进行索引查找
• 连接的时间代价：$b_r(t_T+t_S)+n_r\ast c$，$t_T+t_S$ 是每一块的寻址时间和传输时间的和，$b_r$ 是关系 $r$ 的总块数，$c$ 是使用连接条件对关系 $s$ 进行单次选择操作的代价，$n_r$ 就是 $r$ 中元组的数目
• 如果两个关系 $r$ 和 $s$ 上均有索引的时候，一般把元组较少的当外层关系效果更好

归并链接

• 在连接属性上对全部关系进行排序（如果之间非有序），归并有序关系
• 算法类似归并排序的归并阶段，但出现重复元组需要特殊处理，每一对拥有相同连接值的元组必须被匹配
• 可以用与计算自然连接和等值连接
• 每个块只需要读一次
• 归并连接代价：$b_r+b_s$ 次块传输 + $\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil$ 次磁盘搜索 + 排序的代价（如果未排序），$b_b$ 是每次读入的块数
• 混合归并连接：如果关系本身有序，且另一个关系上有连接属性的B+树的辅助索引，可以直接将已排序关系和另一个关系上的B+树辅助索引的叶子节点进行归并，按照未排序的关系元组的地址进行排序，按照物理存储顺序检索元组，比随机查找更有效

散列链接

• 适用于等值连接和自然连接
• 用散列函数 $h$ 来划分两个关系的元组
• $h$ 是将 $JoinAttrs$ 值映射到 $\{0,1,\dots ,n\}$ 的散列函数，其中 $JoinAttrs$ 表示自然连接中 $r$ 与 $s$ 的公共属性
  • $r_0,r_1,\dots ,r_n$ 表示了关系 $r$ 的元组划分 每个元组 $t_r\in r$ 被放入划分 $r_i$ 中，其中 $i=h(t_r[JoinAttrs])$
  • $r_0,r_1,\dots ,r_n$ 表示了关系 $s$ 的元组划分 每个元组 $t_s\in s$ 被放入划分 $s_i$ 中，其中 $i=h(t_s[JoinAttrs])$
• 关系 $r_i$ 中的元组 $r$ 只需要与关系 $s_i$ 中的元组 $s$ 相比较，没有必要与其他任何划分里的元组 $s$ 相比较（相同的桶里可能有满足连接条件的一对元组，不过不同的桶里一定没有）
• 算法：
  1. 使用散列函数 $h$ 划分关系 $s$ 。当划分一个关系时，一个内存块被保留作为每个划分的输出缓冲区
  2. 如此划分关系 $r$
  3. 对于每一个 $i$ ：
     • 将 $s_i$ 装入内存，并且在它的连接属性上建立一个内存中的散列索引（和上一个不同）
     • 一个一个的从磁盘中读取 $r_i$ 的元组。使用内存散列索引，为每一个元组 $t_r$ 找到一个 $s_i$ 中的匹配元组 $t_s$ 。输出他们属性值的连串
  • $s$ 称为构造用输入，而 $r$ 称为探查用输入
• 应当选择合适的 $n$ 值和散列函数 $h$ ，以使得 $s_i$ 能够以被放入内存中
  • 通常 $n=\lceil b_s/M\rceil \ast f$ ,此处的 $f$ 是一个“附加因子”，通常约为1.2
  • 探查关系的划分是不需要放在内存中的
• 优化：递归划分： $n\ge M$ , $M$ 是内存块数，此时需要递归划分
  • 使用 $s$ 的 $M-1$ 个划分代替先前的 $n$ 个划分
  • 使用不同的散列函数进一步分割 $M-1$ 个划分
  • 对 $r$ 使用相同的划分方法
• 代价：在不考虑递归划分的情况下，需要 $3(b_r+b_s)+4n_h$ 次的块传输 + $2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )$ 次磁盘搜索
  • $3(b_r+b_s)$ 是由于划分时散列需要对所有块读一次写一次，在连接操作的时候还得读一次
  • $n_h$ 指的是桶的数量，数值较小的时候 $4n_h$ 可以忽略
  • $b_b$ 是每次读入的块数，$2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )$ 是因为一次散列一次连接
• 如果需要递归划分：
  • 每一次可以将划分大小减小成 $1/(M-1)$ ,不断重复操作直到多个划分最多占据 $M$ 块为止。则划分关系 $s$ 所需要的次数预计为 $\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil$
  • 最好选择较小的关系作为构造关系
  • 总代价估计
  $$2(b_r+b_s)\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil +b_r+b_s$$次的块传输,加上$$2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil$$次的磁盘搜索
  • 当内存中可以容纳整个构造用输入关系时，可以不必将关系划分为临时文件了，估计代价下降至 $b_r+b_s$

其他运算

• 去重——排序/散列
  • 排序之后相同的元组只留一个
  • 归并之后立即去重
  • 散列的相同元素一定在一个桶里
• 投影
  • 对每个元组投影，然后去重
• 集合运算 $\cup \cap -$
  • 先排序/散列，再扫描一次计算并交差
• 外连接
  • 方案一：计算相应的连接运算，加入失配元组（计算 $r-{\mathrm{\Pi }}_R(r\bowtie s)$）
  • 方案二：修改连接运算对应的程序
• 聚集——可以用与去重相同的方法来实现
  • 按照分组属性排序/散列过程中分组，然后每组计算聚集函数
  • 优化

表达式计算

• 目前只研究了单个关系运算如何执行
• 计算一个完整的表达式树的两种方法
  1. 物化 输入一个关系或者已完成的计算，产生一个表达式的结果，在磁盘中物化并它重复这个过程
  2. 流水线 将一个正在执行的操作部分结果传送到流水线的下个操作，使得两操作可以同时进行

物化

• 物化计算：从最底层开始，执行树中的计算，计算每一个中间结果，然后用于下一层运算
• 任何情况下物化运算都适用
• 将结果写入磁盘和读取他们的代价是非常大的（平时估算算法代价的时候我们都忽略了写入磁盘的代价）
• 双缓冲技术：使用两个缓冲区，其中一个用于连续执行算法，另一个用于写出结果

流水线

• 流水线：同时执行多个操作，一个操作的结果传递到下一个
• 不储存中间结果，直接传递元组到下一个运算，比实体代价小很多
• 流水线不总是可行的（排序，散列）
• 对于有效流水线，当作为输入的元组被接收时，立即使用计算算法得到输出元组
• 流水线执行方法
  • 需求驱动流水线
  • 生产者驱动流水线
• 需求驱动（消极计算）：后面的计算不停的向前边要数据，系统不停的向位于流水线顶端的操作发出需要元组的请求
• 生产驱动（积极计算）：各操作并不等待元组的请求，而是积极的产生元组，只有当一个输出缓冲区满了或者一个输入缓冲区空了，需要更多的元组来产生输出元组的时候，系统才会在各个操作中切换