数据库系统实现第四章（查询执行）、第五章（查询编译器）笔记
查询处理器
查询处理器的主要部分
查询编译概貌
每个操作符的算法的选择是将逻辑查询计划转变为物理查询计划过程中的一个必不可少的部分。
查询执行
物理查询计划操作符介绍
扫描表：
- 读一个关系R的所有元组，无论是表-扫描或是索引-扫描
排序-扫描：
- 若排序的属性a上有B树索引（B树索引是有序的吗？不是按照key值吗，key是属性a的值吗）或R是按a排序的索引顺序文件来存储的时候，可以直接对索引进行扫描即可得到所需排序的R。
- 若R很小，可以装进内存，那么可以使用表扫描或索引扫描得到元组，再使用主存排序算法
- 若R大，无法装进内存，通过多路归并得到排序好的R。
物理操作符计算模型
- 使用磁盘I/O数目作为操作符的“代价”
衡量代价的参数
- 关系R的所有元组所需的块的数目B(R)
- 关系R中的元组的数目 T(R)
- 关系的一个列中不同值的数目V(R,a)
实现物理操作符的迭代器
- 迭代器是三个方法的集合：Open(),GetNext(),Close()
- 使用迭代器时，同一时刻活跃的操作就有很多，元组只需要在操作符之间传递，无需将每个操作符得到的整个结果存放在磁盘或内存中。
一趟算法
- 至少一个操作对象能完全装入内存
一次单个元组操作的一趟算法
- 例子：选择和投影操作
- 因为输出缓冲区可能是其他操作的输入缓冲区，因此不把它算在所需空间内。
- R如果一开始在磁盘上（可能从其他操作过来），那么代价就是执行一个表-扫描or索引-扫描所需代价。
整个关系的一元操作的一趟算法
- 例子：分组操作符和去重操作符
消除重复
第一次看到该元组就将它复制到输出并且加入缓冲区中。
若缓冲区中存在该元组，就不必输出。为了加快判别，通常维护一个具有大量桶的散列表或者某种形式的平衡二叉查找树，可将散列表的存储开销忽视。
注：R中不重复的元组的block数要<= M（内存缓冲区的块数）
分组
- 在主存中为分组属性的每一个值创建一个项，该项包括：分组属性的值和每个聚集的一个或多个累计值。
- Min(),Max()函数，保持最小值或最大值即可。
- Count(),为组中见到的每个元组加1
- SUM(),增加非NULL属性a的值
- AVG(),总和&个数
- 直到扫描最后一个元组后，才开始为分组操作创建输出，故这种算法不适合迭代器结构，因为要求在Open方法的时候必须将全部分组做好（不实际）
- 同样用一个内存数据结构在已知分组属性值找到分组的项（散列表&各分组的项）
- 一般，关系R都没有聚簇，故读取R的全部元组需要进行T(R)次I/O
二元操作的一趟算法
例子：除了上方的操作之外的都可以归为这一类，如并、交、差、连接和积的集合形式以及包形式
以下假定,R是两个关系中较大的一个，将D放在内存中。
- 集合与包的区别：集合操作自动消除重复，包操作是不消除重复的
集合并
- 将S读到内存的M-1个缓冲区中建立一个查找结构，查找关键字是整个元组，现将S的元组都复制到输出。然后一次一块将R的每一块读到第M个缓冲区中，对于R的每一个元组t，观察t是否在S中，若不在，也将t复制到输出。
集合交
- 跟并类似，但t若在S中，复制到输出。
集合差
- R-S：检查R中每一个元组t，若t不在S中，将t复制到输出。
- S-R：检查R中每一个元组t，若t在S中，从主存中S的副本中删掉t，考虑完R的每一个元组后，将S中剩余的那些元组复制到输出。
包交
- 将S中每一个不同的元组与一个计数联系起来，其初值是该元组在S中出现的次数。读出R的每一块，对于R的每一个元组t，观察t是否在S中出现，若出现，且与t对应的计数为正值，那么输出t并将计数减1.
包差
- S-R：依次读取R的每个元组，若t在S中出现，则将与之对应的计数递减1，最后将内存中计数时正数的每一个元组复制到输出，复制的次数等于其计数。
- R-S：依次读取R的元组t，若t不在S中出现，则将t复制到输出，若t在S中出现，查看t对应的计数c的当前值，若c=0，则将t复制到输出，若c>0，则不将t复制到输出，但将c值减1。
积
- 读取R中的每一块，对R中每一个元组t与主存S(M-1个缓冲区)中的每一个元组连接，形成后即将其输出。输出所占空间很大，且处理R的每一个元组所耗的时间很长。
自然连接
- 将R(X,Y)与S(Y,Z)连接。
- 读取S的所有元组，构造一个以Y的属性为查找关键字的内存查找结构（M-1个缓冲块中）。
- 将R的每一块读到第M个缓冲块中，对于R的元组t，利用查找结构找到S中与t在Y的所有属性上相符合的元组与t进行连接后形成一个元组输出。
嵌套循环连接
R（X,Y）与S(Y,Z)连接，R在内循环，S在外循环，假定B(S)<=B(R)[外层循环中使用较小的关系略有优势]
没有必要要求有一个关系必须能装入内存
基于元组的嵌套循环连接：
改进：在R的连接属性（Y)上建立索引，便于查找元组。
基于元组的嵌套循环连接的迭代器
基于块的嵌套循环连接算法
- S作为外层循环，可能B(S)>=M,那么需要将S分多次迭代。
- R作为内层循环，每次读入一个块，依次将块中元组和缓冲区的S元组做连接，输出结果。
嵌套循环连接的分析：
- 代价与两个关系的大小(blocks数)的乘积再除以M得到的商成比例
总结
基于排序的两趟算法
- 数据先被读到内存处理了一下之后再写回磁盘，然后重新读取磁盘完成操作。
- 以下假定B(R)>M,将R分成大小为M的chunk并排序。
两阶段多路归并排序（2PMMS）
有一个子表的概念，子表不能超过M-1个（缓冲区数为M个），假定R占用B个块，因为每个子表可以包括M个块，于是子表数目为B/M,要求B/M <= M-1。
阶段1：将R中的元组放入M个缓冲区中，利用主存排序进行排序，将排序得到的子表存到外存外【保证每个子表（最多M个）是有序的】
阶段2：将排好序的子表进行归并（选择每个子表最前面的块读入M-1个缓冲使用归并进行排序）
利用排序去除重复
- 与2PMMS的阶段1一样，就是在阶段2时，不断复制每一块的第一个未考虑的元组t到输出并忽略与它相同的所有元组，即将输入快中所有的t删除。
利用排序进行分组和聚集
- 与2PMMS相似
- 阶段1：用分组属性作为排序关键字，对每M块排序
- 阶段2：查找分组属性的最小值，将该最小值v成为下一分组，然后为这个组计算出聚集值即可。
基于排序的并算法
- 与2PMMS相似
- 阶段1：创建R与S的排序子表
- 阶段2：为R和S的每个子表使用一个内存缓冲区，在缓冲区中找元组t，复制到输出，并且从缓冲区中删除t的所有副本。
基于排序的交和差算法
- 除了t的副本什么情况下复制到输出缓冲区有所区别之外，其他都一样。
基于排序的一个简单的连接算法
- 先将R和S都使用2PMMS根据连接值进行排序（假定只有一个连接键）
阶段1：R和S个占一块缓冲区，剩下的M-2都用来装连接值为y的所有元组
代价：5(B(R)+B(S))次磁盘I/O，B(R)<=M^2且B(S)<=M^2，用于连接的属性具有公共的值的所有元组必须能全部装入M个缓冲区中。
一个更有效的基于排序的连接
- 当连接属性具有公共的值元组不多的时候，可以将排序的第二阶段和连接本身合并。
- 区别：为R和S创建大小为M的排序的子表
总结
基于散列的两趟算法
- M个缓冲区，将关系R分到M-1个桶中，每一个桶和一个缓冲区联系起来，当一个缓冲区满了，就将它写到磁盘并且初始化另一个块。
- 上致跟上面都差不多..
缓冲区管理
- 之前的操作都假定可以获得数量M的内存缓冲区，但实际上缓冲区很少预先分配给操作符，是由缓冲区管理器来进行统一分配的。
缓冲区管理结构
- 有两个主要的缓冲区管理结构
- 缓冲区直接控制内存（缓冲区只有内存部分）
- 缓冲区在虚拟内存中分配空间（一部分缓冲区还在磁盘上，但是我们不关心），这情况下换进换出多了，会抖动。
- 一般，DBMS初始化时，都会先设缓冲区的数目（作为一个参数）。
缓冲区管理策略
- 跟操作系统中的调度策略一样…
- 查询处理的内存管理：
- 在某些DBMS中，内存是在多个缓冲池中（具有不同目的），有些是用来存放磁盘页面，有些是用来存放散列表。
- 最近最少使用（LRU)
- 缓冲区管理器保持每个块最后一次时间访问的表
- 先进先出(FIFO)
- “时钟”算法（第二次机会）
- 系统控制
- 针对“被钉住的”块（有其他指向它的块），缓冲区管理器都不能驱除它。
- 这节没怎么仔细看..
使用超过两趟的算法
- 这节没看..