2-3:查询处理

查询处理指从数据库中提取数据时涉及的一系列活动， 将用高层数据库语言表示的查询语句翻译为能在文件系统的物理层上使用的表达式 为优化查询而进行各种转换 查询实际执行

概述

SQL查询语句－＞关系代数表达式／语法分析树－＞进一步确定每一步实现方法［查询执行计划］

查询代价的度量

在磁盘上存取数据的代价常是最主要的代价 响应时间依赖于主存中缓冲区的大小 多张磁盘系统响应时间依赖于访问在磁盘的分布 优化器通常努力去尽可能降低查询计划总的资源消耗

选择运算

在查询处理中， 文件扫描是存取数据最低级的操作 文件扫描是用于定位，检索满足选择条件的记录的搜索算法

使用文件扫描和索引的选择

使用h_{i}表示B^{+}树的高度 －　A1［线性搜索］ 按记录块，逐块搜索

－　A2［主索引，码属性等值比较］ 是否为主索引和码属性是两个概念 主索引，意思是记录按搜索码有序存储 码属性，意思是搜索码是记录的主码／超码［可唯一确定记录］ －　A3［主索引，非码属性等值比较］ 非码属性，意思是搜索码不是记录的主码／超码， 此时给定一个搜索码对应的记录可能有一个或多个． 主索引决定了，具有此搜索码的记录必定顺序存储 －　A4［辅助索引，等值比较］ 辅助索引，意思是记录不按搜索码有序存储 若搜索码为码属性，则搜索成功可得唯一匹配记录 若搜索码为非码属性，则搜索成功可能有一个或多个匹配记录

涉及比较的选择

－　A5［主索引，比较］ 在选择条件是比较时， 可用顺序主索引［如B^{+}树主索引］ 对A>=v 在索引中寻找值ｖ 以检索出满足条件A=v的首条记录 从该元组开始到文件末尾进行一次文件扫描就返回所有满足该条件的元组 对A>v 文件扫描从第一条满足A>v的记录开始 对形如A<v或A<=v的比较式 没必要查找索引 对A<v 简单地从文件头开始扫描，直到遇上［但不包含］首条满足A=v的元组为止 A<=v类似 这两种情况下，索引没什么用处 －　A6［辅助索引，比较］ 可使有序辅助索引指导涉及<,<=,>,>=的比较条件的检索 对<及<=情形 扫描最底层索引块是从最小值开始直到ｖ为止 对>及>=情形， 扫描从ｖ开始直到最大值为止 辅助索引提供了指向记录的指针 我们需使用指针以取得实际的记录 连续的记录可能存在于不同的磁盘块 辅助索引应该仅在选择得到的记录很少时，使用

复杂选择的实现

－　合取 σ_{θ_{1}∧ ...∧ θ_{n})(r) －　析取 σ_{θ_{1}∨ ...∨ θ_{n})(r) 所有满足单个简单条件θ_{i}的记录的并集满足该析取条件 －　取反 选择操作σ_{¬θ)(r)的结果就是关系ｒ中对条件θ取值为假的元组的集合 如没有空值的话，该结果就是那些不在σ_{θ}(r)中的元组的集合 可用下列算法之一来实现涉及多个简单条件的合取或析取的选择操作 －　A7［利用一个索引的合取选择］ 首先判断是否存在某个简单条件中的某个属性上的一条存取路径 若存在， 则可用选择算法A2-A6中的一个来检索满足该条件的记录 然后在内存缓冲区中， 通过测试每条检索到的记录是否满足其余的简单条件， 来最终完成这个操作 为减少代价， 选择某个θ_{i}及A1~A6算法之一 它们的组合可使σ_{θ_{i}}(r)的代价达到最小 －　A8［使用组合索引的合取选择］ 某些合取选择可能可使用合适的组合索引［即在多个属性上建立的一个索引］ 如选择指定的是两个或多个属性上的等值条件 且在这些属性字段的组合上又存在组合索引 则可直接搜索索引 索引的类型将决定使用A2,A3,A4算法中的哪一个 －　A9［通过标识符的交叉实现合取选择］ 利用记录指针或记录标识符 该算法要求各个条件所涉及的字段上带有记录指针的索引 该算法对每个索引进行扫描， 获取哪些指向满足单个条件的记录的指针 所有检索到的指针的交集就是哪些满足合取条件的指针的集合 然后算法利用该指针集合获取实际的记录 如并非各个条件上均存在索引，算法要用剩余条件对所检索到的记录进行测试 算法A9的代价是扫描各个单独索引代价的总和加上获取检索到的指针列表的交集中的记录的代价 对指针列表进行排序并按照排序顺序检索记录能减少该算法的代价 故， １，应把指向一个磁盘块中所有记录的指针归并到一起， 这样只需通过一次I/O即可获取到在该磁盘块中选择的所有记录 ２．磁盘块的读取也要按存储次序执行，这样磁盘臂的移动最少 －　A10［通过标识符的并实现析取选择］ 如在析取选择中所有条件上均有相应的存取路径存在， 则逐个扫描索引获取满足单个条件的元组指针 检索到的所有指针的并集就是指向满足析取条件的所有元组的指针集 然后利用这些指针检索实际的记录 然而即使，只有其中的一个条件不存在存取路径 也不得不对这个关系进行一次线性扫描以找出那些满足该条件的元组 故，只要析取式中有一个这样的条件最有效的存取方法就是线性扫描 扫描的同时对每个元组进行析取条件测试

排序

通过在排序码上建立索引， 然后使用该索引按序读取关系， 可完成对关系的排序 然而，这一过程仅仅在逻辑上通过索引对关系排序 没有在物理上排序 故，顺序读取元组可能导致每读一个元组就要访问一次磁盘 由于记录数目可能比磁盘块数目大很多， 因此这样代价很大 故，有时需在物理上对记录排序

外部排序归并算法

对不能全部放在内存中的关系的排序称为外排序 外排序中最常用的技术是外部排序归并算法 令Ｍ表示内存缓冲区中可用于排序的块数 即内存的缓冲区能容纳的磁盘块数 －　第一阶段 建立多个排好序的归并段 每个归并段都是排序过的 但仅包含关系中的部分记录 i = 0 repeat 读入关系的Ｍ块数据或剩下的不足Ｍ块的数据 在内存中对关系的这一部分进行排序 将排好序的数据写到归并段文件R_{i}中 i = i + 1 until 达到关系末尾 －　第二阶段 对归并段进行排序 暂时假定归并段的总数Ｎ小于Ｍ 这样我们可为每个归并段文件分配一个块， 此外剩下的空间还应能容纳存放结果的一个块 归并阶段的工作流程如下 为Ｎ个归并段文件R_{i}各分配一个内存缓冲块，并分别读入一个数据块 repeat 在所有缓冲块中按序挑选第一个元组 把该元组作为输出写出，并将其从缓冲块中删除 if 任何一个归并段文件R_{i}的缓冲块为空并且没有到达R_{i}末尾 then 读入R_{i}的下一块到相应的缓冲块 until 所有的缓冲块为空 归并阶段的输出是已排序的关系 输出文件也被缓冲以减少写磁盘次数 上面的归并算法是对标准内存排序归并算法中的二路归并算法的推广 由于该算法对Ｎ个归并断奶进行归并 因此称他为Ｎ路归并 一般， 若关系比内存大得多 则在第一阶段可能产生Ｍ个甚至更多的归并段 且在归并阶段为每个归并段分配一个块是不可能的 在这种情况下 归并操作需要分多趟进行 由于内存足以容纳Ｍ－１个缓冲块， 因此每趟归并可以用Ｍ－１个归并段作为输入 最初那趟归并过程如下， 头Ｍ－１个归并段如前第二点所述进行归并得到一个归并段作为下一趟的输入 接下来的Ｍ－１个归并段类似地进行归并 如此下去 直到所有的初始归并段都处理过为止 此时，归并段的数目减少到原来的１／（Ｍ－１） 如归并后归并段数目仍大于Ｍ 则以上一趟归并创建的归并段作为输入进行下一趟归并 每一趟归并段的数目均减少为原来的１／（Ｍ－１） 如有需要归并过程将不断重复 直到归并段数目小于Ｍ 此时作最后一趟归并 得到排序的输出结果 为方便说明， 假定每块只能容纳一个元组［f_{r}=1］ 同时假定内存最多只能提供３个块 在归并阶段，两个块用于输入，另一个块用于输出

这个外部归并排序依赖于每个块内记录是原子的． 即排序不会另一个块内记录进行重组．［否则，步骤２归并融合，需每次取Ｍ－１个缓冲块首个记录比较，并选一最小，写到M块末尾这样来迭代］

外部排序归并的代价分析

主要考虑涉及的磁盘块的传输和搜索次数

连接运算

嵌套循环连接

一个计算r ⋈_{θ} s的简单算法 for each 元组t_{r} in r do begin for each 元组t_{s} in s do begin 测试元组对(t_{r}, t_{s})是否满足连接条件θ 如果满足，把t_{r}*t_{s}加到结果中 end end

块嵌套循环连接

for each 块B_{r} of r do begin for each 块B_{s} of s do begin for each 元组t_{r} in B_{r} do begin for each 元组t_{s} in B_{s} do begin 测试元组对(t_{r},t_{s})是否满足连接条件 如满足，加入到结果 end end end end

索引嵌套循环连接

在嵌套循环连接中， 若内层循环在连接属性上有索引 可用索引查找替代文件扫描 对外层关系ｒ的每一个元组t_{r} 可利用索引查找ｓ中和元组t_{r}满足连接条件的元组

其他运算

表达式计算

物化

运算的每个中间结果被创建［物化］，然后用于下一层运算

流水线

一个操作的结果将传送到下一个操作 创建一个操作的流水线可带来好处： －　能消除读和写临时关系的代价

流水线的实现

－　在一条需求驱动的流水线中 系统不同向位于流水线顶端的操作发出需要元组的请求， 当一个操作收到需要元组的请求， 就计算下一个［若干个］元组并返回 如操作的输入不是来自流水线 则返回的下一个［若干个］元组可由输入关系计算得到 如操作的某些输入来自流水线， 操作也发出请求以获得来自流水线输入的元组［使用，计算，传给父层］ －　在一条生产者驱动的流水线中 各操作不等待元组请求 而是积极地产生元组