27 并发控制

事务并发执行带来的问题：

1. 会产生多个事务同时存取同一数据的情况
2. 可能会存取和存储不正确的数据，破坏事务隔离性和数据库的一致性

多事务执行方式：

1. 事务串行执行：每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行。这种实现不能充分利用系统资源，发挥数据库共享资源的特点。

2. 交叉并发方式（Interleaved Concurrency）：在单处理机系统中，事务的并行执行是这些并行事务的并行操作轮流交叉执行。单处理机系统中的并行事务并没有真正地并行运行，但能够减少处理机的空间时间，提高系统的效率。在多处理机上，每个不同的核可以同时处理不同的事务。

   对时间进行切片，比如先执行事务一的前三分一，再去执行事务二的前三分一，来回分配时间以达到宏观上并行的效果（单处理机上微观来看仍然是串行的）

3. 同时并发方式（Simultaneous Concurrency）：多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行。这是最理想的并发方式，但受制于硬件环境，同时也需要更复杂的并发方式机制

事务是并发控制的基本单位

并发控制机制的任务：

• 对并发操作进行正确调度
• 保证事务的隔离性
• 保证数据库的一致性

并发操作可能带来的数据不一致性：

• 丢失修改（Lost Update）：丢失修改指的是两个事务读入了同一个数据，又分别先后写回数据库，由于读取时两者是同时读取，修改时并不知道另一个事务修改了该数据，于是写回的时候有一个事务的更新就被另一个事务给覆盖了。
• 不可重复读（Non-repeatable Read）：不可重复读指的是事务一读取数据后，事务二更新了数据导致事务一无法再读取到之前的结果，有时也称为幻影现象（Phantom Row）：
  • 事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值
  • 事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录神秘地消失了。
  • 事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。
• 读脏数据（Dirty Read）：
  • 事务T1修改某一数据，并将其写回磁盘
  • 事务T2读取同一数据后，T1由于某种原因被撤销（ROLLBACK）
  • 这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致
  • T2读到的数据就为“脏”数据，即不正确的数据

数据不一致性：由于并发操作破坏了事务的隔离性

并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性

对数据库的应用有时允许某些不一致性，例如有些统计工作涉及数据量很大，读到一些“脏”数据对统计精度没什么影响，可以降低对一致性的要求以减少系统开销

并发控制的主要技术

• 封锁（Locking）
• 时间戳（Timestamp）
• 乐观控制法
• 多版本并发控制（MVCC）

28 封锁

• 封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁
• 加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。
• 封锁是实现并发控制的一个非常重要的技术
• 一个事务对某个数据对象加锁后究竟拥有什么样的控制由封锁的类型决定。
• 基本封锁类型
  • 排它锁（Exclusive Locks，简记为X锁）
  • 共享锁（Share Locks，简记为S锁）

28.1 锁的类型

1. 排它锁：又称为写锁
   • 若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。
   • 保证其他事务在T释放A上的锁之前不能再读取和修改A。
2. 共享锁：又称为读锁
   • 若事务T对数据对象A加上S锁，则事务T可以读但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。
   • 保证其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。

锁的相容矩阵

T2/T1	X	S	-
X	N	N	Y
S	N	Y	Y
-	Y	Y	Y

在锁的相容矩阵中：

• 最左边一列表示事务T1已经获得的数据对象上的锁的类型，其中横线表示没有加锁。
• 最上面一行表示另一事务T2对同一数据对象发出的封锁请求。
• T2的封锁请求能否被满足用矩阵中的Y和N表示:
  • Y表示事务T2的封锁要求与T1已持有的锁相容，封锁请求可以满足
  • N表示T2的封锁请求与T1已持有的锁冲突，T2的请求被拒绝

在运用X锁和S锁对数据对象加锁的时候，需要约定一些规则，这些规则称为封锁协议（Locking Protocol），主要包括：事务何时申请X锁或S锁，事务的持锁时间应该多长，事务应该何时释放锁。

对封锁方式规定不同的规则，就形成了各种不同的封锁协议，它们分别在不同的程度上为并发操作的正确调度提供一定的保证。

28.2 一级封锁协议

内容：事务T在修改数据R之前必须先对其加X锁，直到事务结束才能释放。

事务结束的标志：

• 正常结束（COMMIT）
• 非正常结束（ROLLBACK）

一级封锁协议可以防止丢失修改，并保证事务T是可恢复的。在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读脏数据。

28.2.1 例子

28.3 二级封锁协议

内容：一级封锁协议加上事务T在读取数据R之前必须先对其加上S锁，读完后即可释放S锁。

二级封锁协议可以防止丢失修改和读“脏”数据。在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。

28.3.1 例子

28.4 三级封锁协议

内容：一级封锁协议机上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。

三级封锁协议可防止丢失修改、读脏数据和不可重复读。

28.4.1 例子

• 三级协议的主要区别：什么操作需要申请封锁以及何时释放锁。
• 不同的封锁协议使事务达到的一致性级别不同：封锁协议级别越高，一致性程度越高

	X锁		S锁		一致性保证
	操作结束释放	事务结束释放	操作结束释放	事务结束释放	不丢失修改	不读“脏”数据	可重复读
一级封锁协议		是			是
二级封锁协议		是	是		是	是
三级封锁协议		是		是	是	是	是

28.5 活锁

由于并发之间的调度其实不是可预测的，所以有可能某个事务在并发中会处于永远等待的状态，这个情况我们称为“活锁”。解决活锁一般是采用先来先服务（First Come First Service, FCFS）的处理。下面的情形介绍了一种典型的活锁情况：

• 事务 $T_1$ 封锁了数据 $R$
• 事务 $T_2$ 又请求封锁 $R$，于是 $T_2$ 等待。
• $T_3$ 也请求封锁 $R$，当 $T_1$ 释放了 $R$ 上的封锁之后系统首先批准了$T_3$ 的请求，$T_2$ 仍然等待。
• $T_4$ 又请求封锁 $R$，当 $T_3$ 释放了 $R$ 上的封锁之后系统又批准了 $T_4$ 的请求……
• $T_2$ 有可能永远等待，这就是活锁的情形

先来先服务

当多个事务请求封锁同一个数据对象的时候，DBMS按请求封锁的先手次序对这些事务排队，该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁

28.6 死锁

典型的情况：

• 事务 $T_1$ 封锁了数据 $R_1$
• $T_2$ 封锁了数据 $R_2$
• $T_1$ 又请求封锁 $R_2$ ，因 $T_2$ 已封锁了 $R_2$ ，于是 $T_1$ 等待 $T_2$ 释放$R_2$ 上的锁
• 接着 $T_2$ 又申请封锁 $R_1$ ，因 $T_1$ 已封锁了 $R_1$ ，$T_2$ 也只能等待 $T_1$ 释放 $R_1$ 上的锁
• 这样 $T_1$ 在等待 $T_2$ ，而 $T_2$ 又在等待 $T_1$ ，T1和T2两个事务永远不能结束，形成死锁

28.6.1 死锁的预防

产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。

预防死锁的主要策略就是破坏产生死锁的条件，一般有如下的两种方法：

1. 一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。

   存在的问题：降低了系统的并发度。同时要实现精确的确定需要封锁的对象是比较困难的。

2. 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。

   存在的问题：维护成本比较高，随着数据的不断更新需要不断维护这个封锁顺序。同时也很难实现，因为事务执行期间的封锁请求可能会动态变化，很难确定某个事务要先封锁哪一个对象。

上述两种方法一般是OS上用的预防死锁的方法，在DBMS中一般采用诊断出死锁并解除死锁的办法。

28.6.2 死锁的诊断

1. 超时法：如果一个事务的等待时间超过规定的时间，就认为发生了死锁。

   优点：实现简单：

   缺点：有可能会误判死锁，且如果时间设置太长，则死锁发生后可能不能及时发现。

2. 等待图法：并发控制子系统周期性地（比如每隔数秒）生成事务等待图来检测事务是否有回路，有的话则表示系统中出现了死锁。

28.6.3 死锁的解除

• 选择一个处理死锁代价最小的事务，将其撤消
• 释放此事务持有的所有的锁，使其它事务能继续运行下去

29 事务调度

数据库管理系统对并发事务不同的调度可能会产生不同的结果。串行调度是正确的，执行结果等价于串行调度的调度也是正确的，称为可串行化（Serializable）调度。

可串行化调度：多个事务的并发执行时正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。

可串行性（Serializability）：可串行性是并发事务正确调度的准则。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确的调度。

29.1 冲突可串行化

冲突可串行化是一个比可串行化更严格的条件，商用系统中的调度器采用。

冲突操作：冲突操作是指不同的事务对同一数据的读写操作和写写操作。除此之外的其他操作是不冲突的操作。

不能交换的动作：

• 同一事物的两个操作
• 不同事务的冲突操作。

一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度

• 若一个调度是冲突可串行化，则一定是可串行化的调度
• 可用这种方法判断一个调度是否是冲突可串行化的

冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。

29.2 两段锁协议

数据库管理系统普遍采用两段锁协议的方法实现并发调度的可串行性，从而保证调度的正确性

两段锁协议：两段锁协议是指所有事务必须分两个阶段，对数据项加锁和对数据项解锁

• 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
• 在释放一个封锁之后，事务不再申请和获得任何其他封锁

“两段”锁的含义：事务分为两个阶段

• 第一阶段是获得封锁，也称为扩展阶段：事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
• 第二阶段是释放封锁，也称为收缩阶段：事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁

遵守两段锁协议的调度一定是一个可串行化的调度。

• 事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。
• 若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
• 若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议

29.2.1 两段锁协议与防止死锁的一次封锁法区别

• 一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议
• 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

30 封锁粒度

封锁对象的大小称为封锁粒度（Granularity）。封锁的对象包括逻辑单元和物理单元。

选择封锁粒度原则

• 封锁粒度与系统的并发度和并发控制的开销密切相关。
  • 封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；
  • 封锁的粒度越小，并发度较高，但系统开销也就越大

例：若封锁粒度是数据页，事务T1需要修改元组L1，则T1必须对包含L1的整个数据页A加锁。如果T1对A加锁后事务T2要修改A中元组L2，则T2被迫等待，直到T1释放A。

如果封锁粒度是元组，则T1和T2可以同时对L1和L2加锁，不需要互相等待，提高了系统的并行度。

又如，事务T需要读取整个表，若封锁粒度是元组，T必须对表中的每一个元组加锁，开销极大

30.1 多粒度封锁

多粒度封锁（Multiple Granularity Locking）：在一个系统中同时支持多种封锁粒度提供不同的事务选择。

如何选择封锁粒度：同时考虑封锁开销和并发度两个因素, 适当选择封锁粒度：

• 需要处理多个关系的大量元组的用户事务：以数据库为封锁单位
• 需要处理大量元组的用户事务：以关系为封锁单元
• 只处理少量元组的用户事务：以元组为封锁单位

多粒度树：

• 以树形结构来表示多级封锁粒度
• 根结点是整个数据库，表示最大的粒度
• 叶结点表示最小的数据粒度

多粒度封锁协议

• 允许多粒度树中的每个结点被独立地加锁
• 对一个结点加锁意味着这个结点的所有**后裔结点（即子节点）**也被加以同样类型的锁
• 在多粒度封锁中一个数据对象可能以两种方式封锁：
  • 显式封锁: 直接加到数据对象上的封锁
  • 隐式封锁:是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
• 显式封锁和隐式封锁的效果是一样的

30.2 意向锁

引进意向锁（intention lock）目的：提高对某个数据对象加锁时系统的检查效率

内容：如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁。对任一结点加基本锁，必须先对它的上层结点加意向锁。例如，对任一元组加锁时，必须先对它所在的数据库和关系加意向锁

常用意向锁

• 共享意向排它锁（Share Intent Exclusive Lock，简称SIX锁）
  • 如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。
  • 例：对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。
• 意向共享锁（Intent Share Lock，简称IS锁）
  • 如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁
  • 例如：事务T1要对R1中某个元组加S锁，则要首先对关系R1和数据库加IS锁
• 意向排它锁（Intent Exclusive Lock，简称IX锁）
  • 如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁
  • 例如：事务T1要对R1中某个元组加X锁，则要首先对关系R1和数据库加IX锁

意向锁的相容矩阵

	S	X	IS	IX	SIX	-
S	Y	N	Y	N	N	Y
X	N	N	N	N	N	Y
IS	Y	N	Y	Y	Y	Y
IX	N	N	Y	Y	N	Y
SIX	N	N	Y	N	N	Y
-	Y	Y	Y	Y	Y	Y

锁的强度

锁的强度的偏序关系：

• 锁的强度是指它对其他锁的排斥程度
• 一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然

具有意向锁的多粒度封锁方法

• 申请封锁时应该按自上而下的次序进行
• 释放封锁时则应该按自下而上的次序进行
• 具有意向锁的多粒度封锁方法：
  • 提高了系统的并发度
  • 减少了加锁和解锁的开销
  • 在实际的DBMS产品中得到广泛的应用。

31 查询处理

31.1 查询分析

查询分析的任务：对查询语句进行扫描、词法分析和语法分析

• 词法分析：从查询语句中识别出正确的语言符号
• 语法分析：进行语法检查

个人理解：类似于编译器做的编译工作，主要就是检查语法的正确性。（注意这步还不会检查关系名和属性名的有效性，而是要到查询检查中才会检查）

31.2 查询检查

查询检查的任务：

• 合法权检查
• 视图转换
• 安全性检查
• 完整性初步检查

根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效。如果是对视图的操作，则要用 视图消解方法 把堆视图的操作转换成对基本表的操作。

根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查（检查执行该查询的用户是否有对应的权限）

检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。

关系数据库管理系统一般都用 查询树，也称为 语法分析树 来表示扩展的关系代数表达式。

31.3 查询优化

查询优化的任务：选择一个高效执行的查询处理策略

查询优化的分类：

1. 代数优化/逻辑优化：指关系代数表达式的优化（比如优化顺序或者替换为效率更高的查询方法）
2. 物理优化：指存取路径和底层操作算法的选择。

查询优化的选择依据：

• 基于规则（rule based）
• 基于代价（cost based）
• 基于语义（semantic based）

31.4 查询执行

查询执行的任务：依据优化器得到的执行策略生成查询执行计划

代码生成器（Code Generator） 生成执行查询计划的代码

两种执行的方法：

• 自顶向下
• 自底向上

31.5 选择操作的实现

选择操作的典型实现方法：

1. 全表扫描方法（Table Scan）：对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出

   适合小表不适合大表

2. 索引扫描方法（Index Scan）：适用于选择条件中的属性上有索引（例如B+树索引或Hash索引），通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。

假设我们有一个 student 表，我们需要执行以下的语句：

SELECT *
FROM `student`
WHERE <条件表达式>

这里的条件表达式有以下四种：

1. 无条件（即查询所有元组）
2. student_no = '201215121'
3. student_age > 20
4. student_dept = 'CS' AND student_age > 20

全表扫描算法：

假设可以使用的内存为 $M$ 块，全表扫描算法的思想如下所示：

1. 按照物理次序读取 student 的 $M$ 块到内存。
2. 检查内存你的每个元组 $t$，如果满足选择条件，则输出 $t$
3. 如果 student 还有其他块未被处理，则重复1和2

索引扫描算法

假设现在的条件表达式是第二种，且 student_no 上有索引。则索引扫描算法就会：

1. 通过索引（或散列）得到 student_no 为 '201215121' 元组的指针
2. 通过元组指针在 student 表中检索到该学生。

假设现在的条件表达式是第三种，且 student_age 上B+树索引。则索引扫描算法就会：

1. 使用B+树索引找到 student_age = 20 的索引项，以此为入口点在B+树的顺序集上得到 student_age > 20 的所有元组指针
2. 通过这些元组指针到 student 表中检索到所有年龄大于20的学生

假设现在的条件表达式是第四种，且 student_dept 和 student_age 上都有索引（可能是单列索引也可能是组合索引）。则索引扫描算法可能会有以下两种实现：

1. 分别利用 Index Scan 找到 student_dept = 'CS' 的一组元祖指针和 student_age > 20 的另一组元祖指针，然后求这两组指针的交集，再到 student 表中检索。
2. 找到 student_dept = 'CS' 的一组元组指针，通过这些元组指针到 student 表中检索，并对得到的元组检查另一些选择条件（如 student_age > 20 是否满足）

31.6 连接操作的实现

连接操作是查询处理中最耗时的操作之一，本节只讨论等值连接（或自然连接）最常用的实现算法：

1. 嵌套循环算法（Nested Loop Join）
2. 排序-合并算法（Sort-Merge Join 或 Merge Join）
3. 索引连接（Index Join）算法
4. Hash Join 算法

以如下的查询语句为例子：

SELECT *
FROM student, student_class
WHERE `student`.`student_no` = `student_class`.`student_no`;

嵌套循环算法（Nested Loop Join）：

• 对外层循环（student 表）的每一个元组，检索内层循环（student_class 表）中的每一个元组。
• 检查这两个元组在连接属性 student_no 上是否相等。
• 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。

即一个二重循环，Java等价代码可以这样表示：

List<Student> studentList;
List<StudentClass> studentClassList;
List<Answer> ansList; // 这是student和student_class 连接的答案元组

for (Student student : studentList) {
    for (StudentClass studentClass : studentClassList) {
        if (studentList.studentNo == studentClass.studentNo) {
            // 连接加入ansList中
            break;
        }
    }
}

排序-合并算法（Sort-Merge Join 或 Merge-Join）

1. 如果连接的表没有排好序，先对 student 表和 student_class 表按连接属性 student_no 排序。
2. 取 student 表中第一个 student_no，依次扫描 student_class 表中具有相同 student_no 的元组。
3. 当扫描到 student_no 不相同的第一个 student_class 元组时，返回 student 表扫描它的下一个元组，再扫描 student_class 表中具有相同 student_no 的元组，把它们连接起来。

即大概的流程如下：比如现在 student 表中有三个元组，student_no 分别为1,2,3，student_class 表中有六个元组，分别为1,1,2,3,3,3。则先排序（这里已经排序好了），然后扫描student 的第一个元组，得到 student_no = 1，然后扫描 student_class，前两个元组的 student_no 都相同，扫描到 student_no = 2 时，因为与 student 表中取出的 student_no 不同，则返回 student 表，然后取下一个 student_no = 2，然后回到 student_class 取下一个， student_no = 2。如此遍历下去即可。

优点：

• student 表和 student_class 表都只要扫描一遍
• 如果两个表原来无序，执行时间要加上对两个表的排序时间
• 对于大表，先排序后使用排序-合并连接算法执行连接，总的时间一般仍会减少

索引连接（Index Join）算法：

1. 在 student_class 表上已经建立属性 student_no 的索引
2. 对 student 中的每一个元组，由 student_no 值通过 student_class 的索引查找相应的 student_class 元组。
3. 把这些 student_class 元组和 student 元组连接起来。
4. 循环执行第二步和第三步，直到 student 表中的元组处理完为止。

Hash Join算法

1. 把连接属性作为hash码，用同一个hash函数把 student 表和 student_class 表中的元组散列到hash表中
2. 划分阶段（building phase, 也称为 partitioning phase）
   • 对包含较少元组的表（student 表）进行一遍处理
   • 把它的元组按hash函数分散到hash表的桶中
3. 试探阶段（probing phase, 也称为连接阶段 join phase）
   • 对另一个表（student_class 表）进行一遍处理
   • 把 student_class 表的元组也按同一个hash函数（hash码是连接属性）进行散列
   • 把 student_class 元组与桶中来自 student 表并与之相匹配的元组连接起来。

Hash Join算法的前提：假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中。

32 查询优化

关系系统的查询优化：

• 是关系数据库管理系统实现的关键技术又是关系系统的优点所在
• 减轻了用户选择存取路径的负担

关系查询优化是影响关系数据库管理系统性能的关键因素

由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性

非关系系统的查询优化：

• 用户使用过程化的语言表达查询要求，执行何种记录级的操作以及操作的序列是由用户来决定的。
• 用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。
• 如果用户做了不当的选择，系统是无法对此加以改进的。

查询优化的优点：

• 用户不必考虑如何最好地表达查询以获得较好的效率
• 系统可以比用户程序的“优化”做得更好
  • 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。
  • 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
  • 优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。
  • 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

查询优化的总目标

• 关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案
  • 集中式数据库
    • 执行开销主要包括：磁盘存取块数（I/O代价） + 处理机时间（CPU代价） + 查询的内存开销
    • I/O代价是最主要的
  • 分布式数据库
    • 总代价=I/O代价+CPU代价+内存代价＋通信代价
• 查询优化的总目标
  • 选择有效的策略
  • 求得给定关系表达式的值
  • 使得查询代价最小（实际上是较小，因为需要权衡多因素，不可能达到最完美）
• 一个关系查询可以对应不同的执行方案，其效率可能相差非常大。

33 代数优化

代数优化策略：通过对关系代数表达式的等价变换来提高查询效率

关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

两个关系表达式 $E_1$ 和 $E_2$ 是等价的，可记为 $E_1 \equiv E_2$

常用的等价变换规则

1. 连接、笛卡尔积交换律：
2. 连接、笛卡尔积结合律
3. 投影的串接定律
4. 选择的串接定律
5. 选择与投影操作的交换律
6. 选择与笛卡尔积的交换律
7. 选择与并的交换律
8. 选择与差与运算的分配律
9. 选择对自然连接的分配律
10. 投影与笛卡尔积的分配律
11. 投影与并的分配律

典型的启发式规则

1. 选择运算尽可能先做：这是在优化策略中最重要、最基本的一条
2. 把投影和选择运算同时进行：若有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
3. 把投影同其前或其后的双目运算结合起来：没有必要为了去掉某些字段而扫描一遍关系。
4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算：连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
5. 找出公共子表达式
   • 如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的
   • 当查询的是视图时，定义视图的表达式就是公共子表达式的情况

33.1 查询树的启发式优化

遵循这些启发式规则，应用等价变换公式来优化关系表达式的算法。

• 算法：关系表达式的优化
• 输入：一个关系表达式的查询树
• 输出：优化的查询树
• 方法：利用等价变换规则

34 物理优化

代数优化改变查询语句中操作的次序好组合，不涉及底层的存取路径。对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的。物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划。

物理优化方法

• 基于规则的启发式优化：启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是最好的规则。
• 基于代价估算的优化：优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
• 两者结合的优化办法：
  • 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量。
  • 然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案。

34.1 启发式规则

选择操作的启发式规则

对于小关系，使用全表顺序扫描，即使选择列上有索引。

对于大关系，启发式规则有：

1. 对于选择条件是 主码 = 值 的查询：
   • 查询结果最多是一个元组，可以选择主码索引
   • 一般的关系数据库管理系统会自动建立主码索引。
2. 对于选择条件是 非主属性 = 值 的查询，并且选择列上有索引：
   • 要估算查询结果的元组数目：
     • 如果比例较小，可以使用索引扫描方法
     • 否则还是使用全表顺序扫描
3. 对于选择条件是属性上的非等值查询或范围查询，并且选择列上有索引：
   • 要估算查询结果的元组数目：
     • 如果比例较小，可以使用索引扫描方法
     • 否则还是使用全表顺序扫描
4. 对于用 AND 连接的合取选择条件：
   • 如果有设计这些属性的组合索引：优先采用组合索引扫描方法。
   • 如果某些属性上有一般的索引，可以用索引扫描方法：
     • 通过分别查找满足每个条件的指针，求指针的交集
     • 通过索引查找满足部分条件的元组，然后在扫描这些元组时判断是否满足剩余条件。
   • 其他情况：使用全表顺序扫描
5. 对于用 OR 连接的析取选择条件，一般使用全表顺序扫描。

连接操作的启发式规则

1. 如果2个表都已经按照连接属性排序
   • 选用排序-合并算法
2. 如果一个表在连接属性上有索引
   • 选用索引连接算法
3. 如果上面2个规则都不适用，其中一个表较小
   • 选用hash join算法
4. 可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(B)较少的表，作为外表(外循环的表) 。
   • 理由：
     • 设连接表 R 与 S 分别占用的块数为 Br 与 Bs，连接操作使用的内存缓冲区块数为 K，分配 K-1 块给外表，如果 R 为外表，则嵌套循环法存取的块数为 $Br+\frac{Br \times Bs}{K-1}$
     • 显然应该选块数小的表作为外表

Reference

1. 数据库系统概论（第五版）
2. 数据库系统概念
3. 南京大学软件学院2022春季学期数据管理基础课程