《数据库系统实现》学习笔记
0 关键字含义
关系：实际上是一张二维表，表的每一行是一个元素，每一列是一项属性。
元组：指的是一个关系上属性集的笛卡尔积的一个元素。大部分情况一下，我们可以理解为表的一行数据。
0 关系代数基本概念
五种基本操作：
并（Union）：设关系R和关系S具有相同的属性n，且相应的属性取自同一个域，则关系R和关系S的并由属于R或属于S的元组组成，其结果仍为n元的关系
差（Difference）：设关系R和关系S具有相同的属性n，且相应的属性取自同一个域，则关系R和关系S的差由属于关系R而不属于关系S的元组组成，其结果仍为n元的关系
笛卡尔积（Cartesian Product）：设关系R和关系S的属性分别为r和s。定义R和S的笛卡尔积是一个(r+s)元的元组集合，每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组
投影（Projection）：对关系进行垂直分割，消去某些列，并重新安排列的顺序，再删去重复元组
选择（Selection）：根据某些条件对关系做水平分割，即选择符合条件的元组
四种组合操作：
交（Intersection）：设关系R和关系S具有相同的属性n，且相应的属性取自同一个域，则关系R和关系S的交由既属于关系R又属于关系S的元组组成，其结果仍为n元的关系。关系的交可以由关系的差来表示。
联接（Join）：连接操作是笛卡尔积和选择操作的组合。
自然联接（Natural Join）：是一种特殊的等值联接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。
除（Division）：设两个关系R和S的属性分别为r和s(设r>s>0)，那么R除S是一个(r-s)元的元组的集合。它是满足下列条件的最大关系：其中每个元组t与S中的每个元组u组成的新元组<t,u>必在关系R中。除运算是笛卡尔积的逆运算。
4 查询执行
SQL是关系模型操作的高层次抽象，所以SQL可以转化为一系列关系代数操作。执行关系代数操作的基本方法有扫描、散列、排序、索引等，这些方法对内存容量所做的假设也有所不同，一些算法假设内存可以容纳参与关系代数操作的数据对象，另外一些算法假设操作对象太大，内存无法容纳。这些算法在代价和结构上有明显的差别。
4.0 查询编译预览
查询编译可以分为三大步骤：
a) 分析，建立查询的分析树。
b) 查询重写，分析树被转化为初始查询计划，这种查询计划通常是查询的代数表达式。然后初始查询计划被转化为一个预期所需执行时间较小的等价查询计划，也被成为逻辑查询计划。
c) 物理计划生成，通常是通过给b中产出的逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序，逻辑计划被转化为物理查询计划。物理查询计划也是用表达式树来表示，同时还包含很多细节，如被查询的关系是怎样被访问的，以及一个关系何时或是否应该被排序。
b和c部分通常被称作查询优化器，它们是查询编译的难点。为了选择最好的查询计划，我们需要判断：
- 查询的哪一个代数等价形式会为查询带来最有效的算法。
- 对选中形式的每一个操作，应当使用什么算法实现。
- 数据如何从一个操作传到另一个操作。
这些选择都依赖关于数据库的元数据。
4.1 物理查询计划操作符介绍
物理查询计划由操作符构成，每一个操作符实现物理查询计划中的一步。物理操作符常常是一个关系代数操作的特定实现，除此之外，也有一些无关任务，例如扫描表，将关系代数要操作的某个关系的每个元组调入内存。
4.1.1 扫描表
读取一个关系R的整个内容，这个操作符的一个变体包含一个简单的谓词(仅读出关系R中满足这个谓词的元组)。
定位关系R中元组的基本方法
- 表-扫描，关系R大部分情况是存放在硬盘中，关系R中的元组排列存放在硬盘块中。系统知道包含关系R元组的块是哪些，并且可以一个接一个地读取这些块。
- 索引-扫描，如果关系R的任意属性上有索引，那么我们可以通过索引来得到R的所有元组，即使元组存放的块不是连续的。
4.1.2 扫描表时的排序
在读取一个关系的元组时，很多情况需要将关系排序。SQL中有 ORDER BY 语句会要求对关系排序，另外还有数据库关系代数操作的具体算法上也需要对关系进行排序(后面会讲到)。
排序-扫描的具体实现有多种方法，例如想产生关系R上按属性a排序的关系，假设a上有B-数索引或者R是按a排序的索引属性存储的，那么用索引扫描即可。假设关系R很小，则可以用表扫描，然后在内存中排序。假设关系R很大，那么后边会讲到用多路归并方法排序。
4.1.3 物理操作符计算模型
一个查询通常包括好几个关系代数操作，相应的物理查询计划由几个物理计划操作符组成。挑选最优的物理计划操作符需要预估每个操作符的代价。磁盘IO的数目是数据库衡量物理计划操作符代价的标准，这里有两个假设，第一操作符的对象位于硬盘、但结果在内存中，第二一个查询的中间操作结果也应该在内存中。
4.1.4 衡量代价的参数
我们设定，内存的一个缓冲区大小和硬盘块大小一致，我们用M表示缓冲区的数目。
当描述一个关系R的大小时，绝大部分情况下，我们想知道的是关系R的所有元组所需要的硬盘块的数目。我们用$B(R)$表示聚集的关系R所占用的硬盘块数，简记为$B$。
我们用$T(R)$表示关系R的元组总数，简记为$T$，一个硬盘块能容纳的元组数表示为$T/B$。
我们用$V(R,a)$表示关系R中a属性的不同值数目，以此可推，$V(R,a1,a2...an)=T(R)$。
4.1.5 扫描操作符的IO代价
假设关系R是聚集的，那么表扫描操作符的代价近似为B，如果关系R能够全部装进内存，那排序扫描的代价也是B。
如果关系R不是聚集的，即元组分散在不同的硬盘块中，那么表扫描的代价就是T，如果关系R能够全部装进内存，那排序扫描的代价也是T。
4.1.6 实现物理操作符的迭代器
许多物理操作符可以实现为迭代器。迭代器有三个方法，这三个方法允许使用者一次获得一个元组。
- Open()，这个方法启动获取元组的过程，但并不获取元组，它用于初始化。
- GetNext()，这个方法返回结果中的下一个元组，并对数据结构做必要的调整以得到后续元组。调用对象通常循环调用该方法获取元组直到返回空。
- Close()，当使用者获取到所有元组，则需要调用该方法关闭数据连接。
使用迭代器的好处：同一时刻活跃的操作有很多，元组按照需要在操作符之间传递，这样就减少了存储要求。
表扫描的迭代器实现，在open方法中获取第一个块的第一个元组，在next方法中判断加载下一个块和元组。
排序扫描的迭代器实现，在open方法中读取整个关系R，然后排序，在next方法中顺序读取。
并操作的迭代器实现，在open方法中先调用第一个关系的迭代器，在next方法中判断第一个关系是否结束，如果结束就打开第二个关系的迭代器。
4.2 一趟算法
如何执行逻辑查询计划中的每个单独步骤(例如连接或选择)？逻辑查询计划转为物理查询计划的一个部分就是选择算法。大体上分为三类：
- 基于排序的方法
- 基于散列的方法
- 基于索引的方法
按照算法难度和代价分为三个等级：
- 一趟算法，仅从硬盘读取一次数据，大部分应用于操作对象能完全放入内存。
- 两趟算法，数据量太大，不能一次全部读入内存，但又不是特别大(后面会讨论什么是特别大)。算法特点是首先从硬盘读取一遍数据，按照某种方式处理完后再写入硬盘，之后在第二趟中读取数据进一步处理。
- 多趟算法，对处理的数据量大小没有限制，是对两趟算法的递归推广。
操作符的分类：
- 一次单个元组，一元操作。这类操作（选择$\sigma$和投影$\pi$）不需要一次在内存中装入整个关系，这样可以一次读一个。
- 整个关系，一元操作。这些单操作对象需要一次从内存中看到全部元组。一趟算法局限于最大M个缓冲区的关系读取，一般是分组操作符$\gamma$和去重操作符$\delta$。
- 整个关系，二元操作。交$\cap$、并$\cup$、差$-$，连接和积的集合形式和包形式。要求这类操作的一个关系操作对象大小限制在M以内。
4.2.1 一次单个元组的一趟算法
非常简单，如果关系R是聚集的，那么IO代价是B。如果是非聚集的，代价是T。
有一个例外，带有在索引上属性和常量比较的选择扫描，效率会显著提高，
在open方法中非阻塞
4.2.2 整个关系的一元操作的一趟算法
消除重复
一次读取一个块，但对于每个元组要进行判断：
- 是第一个出现的元组，复制到缓冲区并输出。
- 以前见过，不用输出。
要求：$B(\delta(R)) <= M$
在open方法中非阻塞
分组
在内存中为分组创建一个项，在项中存有分组的属性值和聚集的一个或者多个累计值。
- 对于MIN或MAX，只需要存一个最小值或最大值。
- 对于COUNT，项内每见到一个元组加一。
- 对于SUM，如果项内见到的被sum值不为NULL，则累加被sum值。
- AVG情况复杂，需要保持两个累计值，个数和和。
这里需要注意，在open方法中，所有元组扫描完成后才能结束。
在open方法中阻塞
4.2.3 二元操作的一趟算法
交、并、差、积和连接操作。为了操作集合操作和包操作，这里用B和S分别表示包和集合。为了简化连接的讨论，仅考虑自然连接，$\theta$连接可以被认为是积或自然连接后额外增加的条件。
包并
包的并可以通过一种非常简单的一趟算法计算出来。$R\cup_BS$，先复制关系R的元组到内存，再复制关系S的每一个元组到内存。IO代价为$B(R)+B(S)$，$M=1$就够用。
在open方法中非阻塞
其他操作则需要将R和S中较小数量的关系读到内存并建立合适的数据结构。其内存要求是$min(B(R),B(S)) <= M$，以下我们假设S关系数据量最小。
集合并
将S读入内存，生成查找结构，Key为整个元组。然后一个一个地读取R的元组t，假如元组t在S中，就跳过，否则就输出。最后输出S的元组。
在open方法中非阻塞
集合交
将S读入内存，生成查找结构，Key为整个元组。然后一个一个地读取R的元组t，假如元组t在S中，就输出，否则就跳过。
在open方法中非阻塞
集合差
$R-_SS$：将S读入内存，生成查找结构，Key为整个元组。然后一个一个地读取R的元组t，假如元组t在S中，就跳过，否则输出。
$S-_SR$：将S读入内存，生成查找结构，Key为整个元组。然后一个一个地读取R的元组t，假如元组t在S中，那么删除内存中的元组t。处理完R的所有元组后，输出内存中剩余的元组。
在open方法中阻塞
包交
存储S的元组和元组出现的次数计数，注意，相同元组只存一份，计数加一。然后一个一个地读取R的元组t，假如元组t在S中，且计数不为0，则输出t并将计数减一。
在open方法中非阻塞
包差
$S-_BR$：存储S的元组和元组出现的次数计数，注意，相同元组只存一份，计数加一。然后一个一个地读取R的元组t，假如元组t在S中，且计数不为0，则将计数减一。最后输出内存中剩余元组，输出次数为计数值。
$R-_BS$：存储S的元组和元组出现的次数计数，注意，相同元组只存一份，计数加一。然后一个一个地读取R的元组t，假如元组t在S中，且计数不为0，则将计数减一，如果元组t不在S中或在S中且计数为0，则输出。
在open方法中阻塞
积
将S读入内存，不需要特殊结构。然后一个一个地读取R的元组t，与S的每一个元组连接并输出。
在open方法中非阻塞
自然连接
$R(X,Y)$和$S(Y,Z)$自然连接，$Y$表示$R$和$S$的所有公共属性。
- 读取S的所有元组，并生成以Y为查找关键字的内存结构。
- 然后一个一个地读取R的元组t，判断t是否可以与S的元组连接，如果可以就连接输出。
在open方法中非阻塞
4.3 嵌套循环连接
在讨论更复杂的方法之前，先来看看嵌套循环连接操作算法。这些算法某种意义上来说需要一趟半。因为两个操作对象中的一个对象元组只用读取一次，而另一个操作对象的元组需要重复读取。
嵌套循环连接可以用于任何大小的关系。
在一趟算法的积和自然连接中，要求一个关系可以完全读入内存。而实际上，我们每个关系只读入一个元组，或者一块。
如果按块读取，那么块少的关系应该在循环外侧。例如$B(R)=1000$，$B(S)=500$，$M=100$，先循环关系R、再循环关系S所需读取块数为：10次外循环乘100+10次外循环乘5次内循环乘100=6000，先循环关系S、再循环关系R所需读取块数为：5次外循环乘100+5次外循环乘10次内循环乘100=5500。
4.4 基于排序的两趟算法
4.4.1 两阶段多路归并排序
假设我们有M个内存缓冲区进行排序，可以通过两趟的算法对非常大的关系进行排序，这种算法叫做两阶段多路归并排序(Two-Phase, Multiway Merge-Sort, TPMMS)。
- 阶段1：不断地将关系R中的元组放入M个缓冲区，利用内存排序算法对他们排序，并且将排序后的子表存入硬盘。
- 阶段2：将排序好的子表进行归并。在这个阶段中，最多能对M-1个有序子表进行归并，这就限制了R的大小。
归并流程如下：
- 加载每个子表的第一块做缓冲块。
- 找到所有块中最小的元素移到输出缓冲区(只有一块)。
- 如果输出块已满，则将它写入硬盘新位置，并归零输出块。
- 如果被取出的最小元素所在块元素已耗尽，则取对应子表的下一块，如果子表中没有块，则保持该缓冲区为空。
- 调至第二步，直到所有缓冲区为空。
根据阶段1和阶段2可知，最多有M-1个子表，每个子表最多有M个块，所以关系R最多有$(M-1)*M$个块，近似表示为$M^2$。在整个过程中，需要读关系2两次，写关系1次。共计IO次数为3B。
例子：假设块大小为16KB，内存为1GB，那么M=1GB/16KB=16K，B最大为$16K*16K=2^{28}$，总大小为4TB。
4.4.2 利用排序去重
在阶段2的归并流程2中，找到所有块中的最小元素并移到输出缓冲区，在这个操作上，先检查输出缓冲区是否有相同元组，如果有就忽略。
4.4.3 利用排序进行分组和聚集
在阶段1中，取分组属性作为排序关键字。在阶段2的归并流程2中，先判断是否有分组属性值相同的元组，有就做聚集操作，没有就直接输出。
4.4.4 基于排序的并算法
包并(4.2.3)算法与操作对象无关，但集合并算法与操作对象大小有关系。
在阶段1中，对关系R和S分别创建排序子表。在阶段2归并流程1中，为关系R和S的每个子表都使用缓冲区。在流程2中，在把元组t输入输出缓冲区后，删除输入缓冲区中和元组t相同的元组。
4.4.5 基于排序的交和差算法
算法和4.4.4节类似
- 对于集合交：如果元组t在R和S中都出现，就输出t。
- 对于包交：输出的t的次数是在R和S中出现的最小次数。
- 对于集合差：关系R集合减S，当且仅当t出现在R中，但不在S中，就输出t。
- 对于包差：关系R包减S，输出t的次数是t在R中出现的次数减去在S中出现的次数。
4.4.6 基于排序的一个简单连接算法
R(X,Y)和S(Y,Z)自然连接，Y表示R和S的所有公共属性。
- 用Y作为排序关键字，使用TPMMS对R进行排序。
- 对S也做排序。
- 对归并好的R和S，使用两个缓冲区。一个给R的当前块，一个给S的当前块。重复以下步骤：
- 在当前R和S的块找到Y的最小值y。
- 如果y在另一个关系中没有出现，那么就删除有关键字y的元组。
- 否则，找到两个关系中具有相关关键字y的所有元组。
- 输出通过连接R和S中具有共同y值的元组连接。
- 如果一个关系在内存中已没有要考虑的元组，就加载下一个元组。
- 磁盘IO代价：$5(B(R)+B(S))$
- $B(R) <= M \cup B(S) <= M$
- 所有用于连接的一个值的对应所有元组必须能装入缓冲区
4.4.8 一种更有效的基于排序的连接
如果拥有公共值的元组太多，4.4.6算法就不可行。那么可以在排序的第二阶段和连接做合并。
- 用Y做关键字，对R和S生成排序子表
- 将每个子表的第一块调入缓冲区。
- 重复地在所有子表的最新元组中第一个查找最小值y。识别两个关系中具有y值的所有元组。输出这些元组的连接。如果有一个子表的缓冲区处理完毕，则重新将磁盘上的块装入其中。
4.5 基于散列的两趟算法
思想如下，如果数据量太大不能存储内存，就使用一个合适的散列关键字散列一个或多个操作对象的所有元组。使用该算法，能使我们把所有需要一起考虑的元组分配到相同的桶。
消除重复、分组和聚集、交并差、连接
4.6 基于索引的算法
非聚簇的关系不可能有一个聚簇的索引，但聚簇的关系可以有非聚簇的索引。
基于索引的选择。在没有索引的情况下磁盘IO为B或T。如果选择的属性在索引上，那么磁盘IO为$B(R)/V(R,a)$。
使用索引的连接。磁盘IO最差情况为为$T(R)T(S)/V(S,Y)$、最好情况为$T(R)B(S)/V(S,Y)$
4.7 缓冲区管理
缓冲区管理策略
最近最少使用(LRU)
清空最长时间没有读写的块，这种方法要求保持一张缓冲区块的被访问最后一次时间的表。
先进先出(FIFO)
占用时间最长的块先被清空。B-数的根更容易被写回硬盘。
时钟算法(第二次机会)
该算法是LRU的最普遍的一个近似实现。实现方法是将缓冲区块看成一个环，每个块有一个标记(0或1，初始值为0)，指针指向其中一个块。如果想读写某一个块，就把这个块的标志置为1。如果想找到一个可用的块，就顺时针旋转，找到第一个0，然后将其设置成1，在找的过程中扫过的块如果标志位1就将其标志设置成0。
4.8 使用超过两趟的算法
略
5 查询编译器
5.1 语法分析和预处理
5.1.1 语法分析和语法分析树
语法分析器接收类似SQL的文本，并转换为语法分析树。树的节点由以下两者构成：
- 原子：词法成分，例如关键字(select)，关系或属性的名称，常数，括号，运算符，以及其他模式
- 语法类：在一个查询中的成分构成。例如
<Query>表示select-from-where形式的查询，<Condition>表示属于条件的表达式。
如果一个节点是原子，那么该节点没有子节点。如果一个节点是语法类，则其子节点通过该语言的语法规则进行描述。
5.1.2 SQL的简单子集语法
<Query> ::= SELECT <SelList> FROM <FromList> WHERE <Condition>
<SelList> ::= <Attrbute> , <SelList>
<SelList> ::= <Attrbute>
<FromList> ::== <Relation> , <FromList>
<FromList> ::== <Relation>
<Condition> ::== <Condition> AND <Condition>
<Condition> ::== <Attrbute> IN ( <Query> )
<Condition> ::== <Attrbute> = <Attrbute>
<Condition> ::== <Attrbute> like <Pattern>
<Attrbute> 为任意表示当前数据库模式的属性的字符串
<Relation> 为当前模式中作为关系而言的字符串
<Pattern> 为任何用引号括起来的字符串
5.1.3 预处理器
虚视图替换，语义检查。
- 检查关系的使用（模式）。
- 检查和解析属性的使用（关系与属性）。
- 检查类型（筛选条件类型）。
5.2 用于改进查询计划的代数定律
5.2.1 交换律和结合律
积，连接，并，交都满足交换律和结合律。
交换律
- $ R \times S = S \times R $
- $ R \Join S = S \Join R $
- $ R \cup S = S \cup R $
- $ R \cap S = S \cap R $
- $ (R \times S) \times T = R \times ( S \times T ) $
- $ (R \Join S) \Join T = R \Join (S \Join T) $
- $ (R \cup S) \cup T = R \cup (S \cup T) $
- $ (R \cap S) \cap T = R \cap (S \cap T) $
5.2.2 涉及选择的定律
由于选择可以明显减少关系的大小，因此进行有效查询处理的最重要规则之一就是只要不改变表达式的结果，就把选择在语法树上尽可能的下移。
- $ \sigma C_1 \quad AND \quad C_2 (R) = \sigma C_1(\sigma C_2(R)) $
- $ \sigma C_1(\sigma C_2(R)) = \sigma C_2(\sigma C_1(R)) $
- $ \sigma C_1 \quad OR \quad C_2 (R) = \sigma C_1(R) \cup \sigma C_2(R) $
涉及$\sigma$的另一类定律允许我们对二元运算符进行下推选择：积、并、交、差、连接。有三中类型定律，这取决于下推选择到每个参数是可选的还是必须的。
- 对于并，选择必须下推到两个参数中。
- 对于差，选择必须下推到第一个参数，下推到第二个参数是可选的。
- 对于其他运算符，只要求选择下推到第一个参数。对于连接和积，将选择下推到两个参数是没有意义的，因为参数可能有也可能没有所要求的属性。即使可以下推到两者，该做法也不一定能改进计划。
因此对于并的定律是：
- $ \sigma C(R \cup S) = \sigma C(R) \cup \sigma C(S) $
对于差的定律：
- $ \sigma C(R-S) = \sigma C(R) - S $
- $ \sigma C(R-S) = \sigma C(R) - \sigma C(S) $
下面这些定律允许将选择下推到一个或者两个参数，对于选择$\sigma _C$，我们只能将其下推到包含C所涉及的全部属性的关系中。假设关系R中有C提及的所有属性，有以下定律：
- $ \sigma C(R \times S) = \sigma C(R) \times S $
- $ \sigma C(R \Join S) = \sigma C(R) \Join S $
- $ \sigma C(R \Join _D S) = \sigma C(R) \Join _D S $
- $ \sigma C(R \cap S) = \sigma C(R) \cap S $
如果C只涉及S的属性，则有：
- $ \sigma C (R \times S) = R \times \sigma C (S) $
对于其他3个运算符$\Join $、$ \Join_D $和 $ \cap $ 类似。如果关系R和S都包含C的属性，那么有诸如以下的定律：
- $ \sigma C(R \Join S) = \sigma C(R) \Join \sigma C(S) $
一些平凡的定律
- 任何对空关系的选择为空。
- 如果C总是为真的条件，则$ \sigma C(R) = R $。
- 如果R为空，$R \cup S = S$。
5.2.3 下推选择
5.2.2节的规则是查询优化器的有力工具，在包含虚视图时，需要先将选择尽可能往树的上部移，然后再把选择下推到所有可能分支。
5.2.4 涉及投影的定律
下推投影是有用的，但是一般而言不如下推选择那么有用，因为投影不改变元组数，只改变元组长度。
投影定律原理：
- 可以在表达式树的任意位置引入投影，只要他所消除的属性是其上的运算符从来不会用到的，也不在整个表达式的结果之中。
5.2.5 有关连接和积的定律
- $ R \Join _C S = \sigma C(R \times S ) $
- $ R \Join S = \pi _L (\sigma C(R \times S)) $
5.2.6 有关消除重复的定律
- $ \delta(R \times S) = \delta(R) \times \delta(S) $
- $ \delta(R \Join S) = \delta(R) \Join \delta(S) $
- $ \delta(R \Join _C S) = \delta(R) \Join _C \delta(S) $
- $ \delta(\sigma C(R)) = \sigma C (\delta (R)) $
- $ \delta(R \cap_BS) = \delta(R)\cap_BS = R\cap_B\delta(S) =\delta(R)\cap_B\delta(S) $
5.2.7 涉及分组和聚集的定律
- $ \delta(\gamma L(R)) = \gamma L(R) $
- $ \gamma L(R) = \gamma (\pi_M(R)) $ ,其中，M包含L中提到的所有属性。
- $ \gamma L(R) = \gamma L(\delta(R)) $，当且仅当$\gamma L$不受重复行影响（例如Min、Max等）
5.3 从语法分析树到逻辑查询计划
在5.1节，我们构造好了语法分析树，接下来需要把语法树转化为逻辑查询计划。
第一步，按适当的群组用一个或者多个关系代数运算符替代语法树上的节点和结构。第二步，利用第一步中产生的关系代数表达式，将其转换成我们所期待的可被转成最有效的物理查询计划的一个表达式。
5.3.1 转换成关系代数
select-from-where结构的关系代数的非正式陈述为：
如果我们有一个包含<Condition>的没有子查询的<Query>，则可以用一个关系代数表达式替换整个成分——选择列表、from列表以及条件，其中代数表达式自底向上由下面这些内容组成：
<FromList>中提及的全部关系的积是以下运算符的参数。- 选择$\sigma_C$，其中C就是要被替换成分中
<Condition>表达式，同时又是下面运算符的参数。 - 投影$\pi_L$，其中L是
<SelList>中的属性列表。
5.3.2 从条件中去除子查询
对于<Condition>中包含子查询的语法树，我们将引入运算符的中间形式，他介于语法分析树的语法类与作用到关系上的关系代数运算符之间。该运算符通常被成为两参数选择。我们将不带参数的标签为$\sigma$的节点表示经转换后的语法树中的两参数选择。该节点之下有一个左子节点，它表示要对其做选择运算的关系R，以及一个右子节点，它表示作用到关系R的每个原则上的条件表达式。两个参数均可表示为语法树、表达式树或两者的混合。
选择条件的限制
为什么要去除子查询？选择$\sigma$的条件实际上是针对每一个元组的筛选，即每拿出一个元组，都要执行一遍选择条件，判断满不满足。如果有子查询，则每拿出一个元组，就要执行一遍子查询，明显不现实。即使子查询与元组无关，那也对代价计算的影响很大。
规则的非正式描述，假设我们有一个两参数选择，其中第一个参数代表的关系R，第二个参数形如t in S的<Condition>，其中S是一个非相关子查询，t是R的元组。我们按照以下方式变换：
- 用S的表达式树替换
<Condition>，如果S有重复，则在S的表达式的根部增加$\delta$运算。 - 用单参数选择$\sigma_C$替换两参数选择，其中C是元组t和关系S中相应属性取等值条件。
- 给选择$\sigma_C$一个参数，他是R和S的积。
5.3.3 逻辑查询计划的改进
当我们把我们的查询语句转换为关系代数时，我们获得了一个可能的逻辑查询计划。下一步是在5.2节列出的代数定律上重写计划。
一下是优化器最常用到的：
- 选择尽可能深地推入表达式树。如果一个选择条件是多个条件的AND，我们可以把该条件分解并分别将每个条件下推。
- 投影下推。
- 消除重复有时可以消去，或者移到树中更方便的未知。
- 某些选择可以与下面的积相结合从而转为等值连接。
5.4 运算代价的估计
逻辑查询计划会对应多个物理查询计划，如何评价每个物理查询计划、或者估计实现的代价。通过以下选择进行代价枚举：
- 满足结合律和分配律的运算。
- 在逻辑计划中每个运算符的算法。
- 其他运算符。
- 参数从一个运算符传送到下一个运算符的方式。
为了做出每项选择，我们需要知道各个物理计划的代价是多少，在没有执行计划的前提下，我们不能准确地知道其代价。执行一个查询计划要比选一个计划所做的工作多，我们也不想同时执行多个查询计划。因此，我们必须能够预估某个计划的代价。
5.4.3 选择运算大小的估计
令$ S=\sigma_{A=c}(R) $，有以下估计：
$$ T(S) = T(R)/V(R,A) $$
如果$ S=\sigma_{a>=10}(R) $，有以下估计：
$$ T(S) = T(R)/3 $$
$ S=\sigma_{a!=10}(R) $我们认为取的是全量数据$T(S)$。
AND条件，建议是不同选择概率的乘积。
OR条件，大小难以估计，例如$ S=\sigma_{C_1 \quad or \quad C_2}(R) $。当C1和C2相互独立，n为元组总数，m1表示满足C1的元组数，m2表示满足C2的元组数，有：
$$ T(S) = n(1-(1-m_1/n)(1-m_2/n)) $$
5.4.4 连接运算大小的估计
三种情况：
- 没有相交的Y值，$T(R\Join S)=0$
- Y是S的主键，且是R的的外键，$T(R\Join S)=T(R)$
- S和R的所有元组都有相同的Y值，$T(R\Join S)=T(R)T(S)$
通常情况的估计：
$$ T(R\Join S)=T(R)T(S)/max(V(R,Y),V(S,Y)) $$
5.4.7 其他运算大小的估计
并
较大者加较小者的一半
交
较小者的一半
差
$ T(R) - T(S)/2 $
消除重复
$min(T(R)/2,\times V(R,a_i))$
分组和聚集
$T(R)/2$
5.7 物理查询计划选择的完成
经过分析查询，转化为初始的逻辑查询计划和优化。基于代价估计选择物理查询计划。将逻辑计划转化为完整地物理计划还需要以下这些内容：
- 执行计划的算法的选择。
- 中间结果何时被物化（存储在硬盘中）。
- 物理查询计划的运算符注释（包含存储关系的访问方法细节和相关代数运算的执行算法的细节）。