查询代价的度量

[1] 基本步骤: 语法分析与翻译 (物理层上使用的表达式) ——优化——执行

[2] 查询代价的度量: 磁盘存取、执行查询的CPU时间、并行/分布式系统的通信代价
查询计算计划: 传送磁盘块数、搜索磁盘次数
写磁盘的代价通常是读磁盘的两倍 (写后重新读验证写操作成功)

[3] 优化器通常努力尽可能降低查询计划总的资源消耗, 而不是缩低响应时间

选择

[1] 文件扫描是存取数据最低级的操作

[2] B+树的根通常放在内存的缓冲区, 甚至全部非叶级别都在内存中

[3] 码属性等值比较得到唯一一条记录, 非码属性等值比较得到多条记录

[4] A5主索引比较: A大于v, A大于等于v: 在索引中找到v检索出满足A=v的首条记录然后到文件末尾进行文件扫描
A小于v, A小于等于v: 没必要查找索引, 从文件头开始扫描直到遇到A=v的记录

[5] A6辅助索引比较: 使用有序辅助索引

复杂选择

选择中: and为合取, or为析取 / 标识符中: and为交, or为并

[1] A7利用一个索引and
首先判断是够存在某个简单条件中的某个属性上的一条索引(存取路径), 存在则使用A2~A6
内存中测试记录是否满足其他简单条件

[2] A8利用组合索引and(多个属性上建立的一个索引)

[3] A9通过标识符的and实现and

• 前提: 各个条件所设计的字段有带记录指针的索引
  使用记录指针或者记录标识符, 所有满足单个条件的记录指针的交集为满足and条件的指针的集合, 从而获得实际的记录
  否则: 可以用剩余条件对所检索到的记录进行测试
• 代价: 扫描各个单独索引代价的和+获取检索到的指针列表的交集中的记录
  对指针列表进行排序并按照拍寻顺序检索记录可以减少代价
  1. 把指向一个磁盘块中所有记录的指针归并到一起, 从而只需要进行一次I/O操作
  2. 磁盘块的读取也要按照存储次序进行, 磁盘臂移动最少

[4] A10通过标识符的or实现or

• 前提: 各个条件所设计的字段有带记录指针的索引
  使用记录指针或者记录标识符, 所有满足单个条件的记录指针的并集为满足or条件的指针的集合, 从而获得实际的记录
• 否则: 线性扫描, 同时对每个元组进行or条件测试

排序

[1] 逻辑排序: 在排序码上建索引然后使用索引按序读取关系——顺序读区元组可能导致每读取一个元组就要访问一次磁盘

[2] 物理排序:

• 内存中能够完全容纳: 标准排序技术 (如快速排序)
• 不能全部放在内存中的关系的排序: 外部排序

[3] N路归并算法

1. 建立多个排序好的归并段, 假设内存缓冲区中可以用于排序的块数为M
   读入关系的M快数据; 在内存中排序; 写到归并段文件R中
2. 对归并段归并, 假设有N个归并段
   为每个归并段文件分配一个内存缓冲块+一个存放结果的数据块
   在所有缓冲块中按序挑选第一个元组, 把这个元组作为输出写出 并从缓冲块中删除;
   如果任何一个归并段文件R的缓冲块为空并且没有达到R末尾, 读入R的下一块到相应缓冲块;
   直到所有的缓冲块均空
3. 输出: 文件也在缓冲中 (减少写磁盘的次数)
   第一阶段产生多于M个归并段, 或者不能为每个归并段分配一个块: 多趟进行, 每趟用M-1个归并段作为输入

[4] 代价分析

• 磁盘块传输
  读入关系的数据块并写入: 2b次磁盘块传输
  初始归并段数: b/M
  共需要归并趟数: log(M-1)(n/M) , 因为每次归并会使归并段数减少为原来的1/(M-1); 每一趟归并读写各一次
  共计: b*(2*log(M-1)(n/M)+1)
• 磁盘搜索
  产生归并段: 读取归并段数据; 写回数据
  归并阶段: 每次读bb块数据(每个归并段分配bb个缓冲块), 每一趟归并需要b/bb次磁盘搜索
  除了最后一趟, 其他写回磁盘也需要b/bb次磁盘搜索, 因为磁盘头在写回的连续块的间隔中可能已经移到别处
  输出分配bb个块, 每一趟可以归并M/bb-1个归并段
  共计: 2*b/M + b/bb*(2*log(M/bb-1)(b/M)-1)

连接

是否有索引可用? 关系的物理存储形式?

• 若连接的结果大小几乎与两个关系的笛卡尔积相当, 则采用块嵌套循环
• 若存在索引, 使用索引嵌套循环
• 若关系已排序, 使用归并连接
• 散列连接将关系划分为多个部分, 每个部分都可以被内存容纳, 划分过程通过连接属性上的散列函数进行, 相应划分对可以独立的进行连接
  因为归并连接需要做更多的排序, 所以消耗的资源更多。通常来讲, 能够使用归并连接, 散列连接都可以发挥更好的性能

(块/索引)嵌套循环

[1] 内表被外表驱动, 外表返回的每一行都要在内表中检索找到与它匹配的行

[2] 适用于被连接的数据子集较小的情况, 要把返回子集较小表的作为外表
如果缓冲区太小, 内存不能完全容纳任何一个关系, 以块的方式处理关系

[3] 进一步改进:

• 连接属性是内层关系的码, 对于每个外层关系元组, 内层只要循环找到首条匹配元组就可以终止
• 可以不以磁盘块作为分块单位, 而是以内存中最多容纳的大小
• 对内层循环轮流向前、向后扫描, 对磁盘块读写请求进行排序, 使得上一次扫描留在缓冲区中的数据可以重用, 减少磁盘存取次数

[4] 内表有索引时利用索引
如果两个表都有索引, 把元组较少的关系作为外层关系, 否则磁盘代价还是会增加(因为尽管块传输次数减少了, 但是有更多的磁盘搜索代价, 磁盘搜索代价比块传输要高)

归并连接

[1] 前提: 两张关系表数据排好序

[2] 步骤:

1. 先比较两张关系表的第一个元素
2. 如果第一个元素相等, 将这两条数据放到结果集中, 然后比较下一个元素
3. 如果不相等, 取小的元素所在表的下一个元素
4. 重复前面的几步操作, 直到其中一张表的数据比较完

[3] 混合归并: 一个关系排序, 另一个未排序但是有B+树辅助索引, 可以讲排序关系与辅助索引叶结点进行归并
得到: 已排序关系的元组及未排序关系的元组地址
按照未排序关系元组地址进行排序, 对相关元组按照物理存储顺序进行有效检索, 完成连接

散列连接

[1] 思想: ri中的元组r只需要与si中的元组s比较, 不需要与其他任何划分里的元组s相比较

[2] 步骤: 将两个表中较小的一个在内存中构造一个散列表作为驱动表, 扫描另一个表(探查表), 同样对JOIN KEY进行哈希后探测是否可以JOIN。

[3] 适用于记录集比较大的情况

[4] 递归划分: 如果哈希表太大, 无法一次构造在内存中, 则分成若干趟
每一趟使用的散列函数与上一趟不同, 系统不断重复输入的分裂过程直到构造用输入关系的每个划分都能被内存容纳为止

[5] 溢出处理: 散列索引大于主存

• 增加划分数(避让因子20%)
• 溢出分解: 若si太大, 适用年龄一个散列函数进一步划分, ri同样处理
• 溢出避免: 首先将s划分成许多小划分, 然后在确保每个组合后的划分都能被内存容纳的前提下进行组合

如果大量元组在连接属性有相同的值, 不采用创建内存散列索引, 而是用嵌套循环连接

[6] 混合散列连接: 内存相对较大, 但不足以容纳整个s关系

1. 划分阶段: 为每一个划分提供一个缓冲区内存块+一个输入缓冲区内存块
   划分后, 让s0完全在内存中且可以建立散列索引
2. 划分r: r0的元组不写回磁盘, 而是在元组产生时查找驻留在内存中的s0散列索引, 并产生连接后的元组
   r0的元组使用后抛弃, 不占用空间
3. 其他划分的元组按鸥亭当时写出, 以后再连接

其他运算

[1] 去除重复

• 排序: 删除其他副本只保留一个
  外排: 创建归并段文件时发现重复元组, 写回磁盘之前去除重复元组(减少块传输次数)
• 散列: 基于一个散列函数对整个关系划分, 每个划分读入内存, 建立内存散列索引
  创建散列索引时, 只插入不在索引中的元组, 否则元组被抛弃

[2] 投影: 每个元组做投影, 然后取出重复记录
如果属性含有关系的码, 则结果中不会有重复元组

[3] 集合运算

• 排序: 代价: br+bs次磁盘搜索 + br+bs次块传输
• 散列: 对于每种运算用相同的散列函数对两个关系进行划分

[4] 外连接
例子: takes左外连接student: 包含takes于student的连接; 对于takes中每一个在student中没有匹配对元组, student的属性取空值
实现:

• 计算连接, 然后将适当的元组加入连接结果(使用投影和集合差)
• 对连接算法加以修改
  嵌套循环连接算法: 把与内层关系的任何元组都不匹配的外层关系元组在填充空值后写入结果, 即可扩展为左外连接
  归并连接: 归并完成后将两个关系/某一个关系中与另一个关系任何元组都不匹配的元组填充空值后写入结果, 即可扩展为全外连接/左右外连接

[5] 聚合函数

• 使用排序或散列, 将元组聚集成组, 对每一组应用聚合运算获得结果
  在组的构造过程中实现聚合运算, 而不是在所有元组聚集成组之后运算
• 内存中将可容纳有序树结构或散列索引, 聚合在b次块传输+1次磁盘搜索中完成
  其他方法: 3b次块传输+2b次磁盘搜索 (最坏情况)

散列和排序是对偶的, 任何可以用散列实现的操作也可以用排序实现

表达式计算

物化

[1] 每个操作的结果物化到一个临时关系写到磁盘
代价: 运算代价+运算结果写到磁盘的代价

[2] 双缓冲: 一个用于连续执行算法, 一个用于写出结果——CPU和I/O可以并行
通过为输出缓冲非配额外的磁盘块, 以及每次同时写出多个块——减少磁盘搜索次数

流水线

[1] 例如: 先连接后投影可以当连接操作产生一个结果元组时, 该元组马上传递给投影操作处理

[2] 好处: 消除读写临时关系的代价, 减少查询计算代价
如果一个查询计算计划的根操作符合并到流水线, 可以迅速产生查询结果

[3] 实现

[4] 排序本质上是阻塞操作: 直到所有输入元组被检查, 才能输出结果
连接本身不是阻塞操作, 但是散列连接算法是一个阻塞操作: 输出任何元组之前, 要求两个输入被完全取回并被划分