开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第一课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/22
第一课（二）
内容介绍：
一、基于关系代数的查询优化算法及实例
二、物理查询优化（暨物理实现算法选择与次序优化）
三、代价估算
四、事务处理
五、数据库系统体系结构
二、物理查询优化（暨物理实现算法选择与次序优化）
1. 物理查询优化——总体思路
（1）为什么要物理查询优化?
一个例子: σCname=“数据结构”(Course)的执行方案
方案1:表空间扫描方法
直接对 Course 表进行扫描，从第一条检索到最后一条，将满足条件的记录找出
方案2:利用 Course 上的 Cname 排序索引的方法
利用排序索引可以进行诸如二分查找等快速检索，找到相应的索引项，依据指针将满足条件的记录找出。
索引调入内存中可以建二叉查找树，根据根节点，根节点比它小的往左边走，比它大的往右边走，如果相等就是找到了，从根节点一直往叶节点走。
>当条件更复杂时，可选择的方案还会更多
物理优化会有以下问题：究竟用哪一个算法的程序来执行?为什么如此选择?
物理优化其实就是一个选择的问题，就是在这两种或者多种方案中选择哪一个。
（2）物理查询运算符
物理查询运算符通常是关系代数操作符的—个特定实现。
获取关系元组的操作：
√TableScan(R)---表空间扫描算法
最基本方法，缺点是如果数据量过大，就非常耗时
√SortTableScan(R)---表空间扫描排序算法
lndexScan(R)---索引扫描算法
√SortlndexScan(R)---索引扫描排序算法
关系操作的各种实现算法：
√σF(R), πα(R), δ(R), γ(R), τ(R),集合上的操作: ︶s , ⌒s, －s，包上的操作: ︶B, ⌒B, －B，积，连接:PRODUCT , JOIN
√一趟算法、两趟算法;基于索引算法、基于散列算法、基于排序算法;迭代器构造--流水化、物化;
流水线化就是把这一个表达式树的各个运算串联起来，可以想象每一个运算符它的实现都是一个小程序，然后把这些程序组合起来，组合成一个大程序，那么怎么来组合这个程序就是流水线化。流水线化还涉及到并行的问题，如果讲并行数据库的话，那流水线可以潜在的进行并行，但是这个内容这里就不去讲了。
另外，物化就是这个表达式当中，如果有视图，那么怎么来做视图，一种就一个虚的视图，就是一个虚表；还一种把它变成实的视图，就把这个视图做查询执行一遍，执行一遍以后把结果像一个表一样保存起来。那么，这时候你再进行这个视图上的查询就不用再执行一遍，原理就是空间换时间。这样后面再进行这个视图的查询，就不用重复算，但是代价就算完以后，要把数据存起来，等于重复存里边，因为这个视图数据都是来源于底下的基本表，本来基本表都有了，那你算一遍，相当于把基本表里的数据提出来，又单独存一次，就等于重复存了，数据冗余。
但是好处是通过这样减少了计算，就节省时间了，这个就叫空间换时间，这是一个基本策略，就叫物化。但物化有一个增量修改问题，就是视图底下的基本表如果发生改变，进行了增删改操作，内容发生变化，那么视图的内容也要跟着改变。这时有两种方法解决，一种是周期性的刷新，就是变化之后视图先不管；还有一种是基本表改变之后，马上就启动一个程序，这个程序就会对视图做相应增量式修改。比如说在基本表删除一行，在视图里头也会删除那行相关的数据，如果插入一行，就在视图里插入一行，这叫增量操作。
物理优化总体思路，就是它先从那个 SQL 语句经过编译转换成一个语法树，转换成一个关系代数表达式。然后进行语法优化，也就是逻辑层优化，得到优化后的这个表达式树。这个树得到后，就是逻查询计划，进行执行优化，在物理层进行优化。
实际上就是为每个关系代数的运算选取优化的执行层例行程序，形成一个物理查询计划。物理查询计划，它的执行优化主要就是先获得数据库的相关信息，就是统计信息，实现同一个关系操作，它可能有不同的运行程序，比如筛选，逻辑上就是一个条件筛选，但是实现的时候，可以对这个表进行扫描，也可以用索引扫描，有它有好多种方法，所以它要选取相应的执行层例行程序，选取时要进行代价估算，估算花费的成本，成本主要是时间成本或者io次数、磁盘操作所需的块数，估算完成之后选择最少的，然后形成查询计划。物理查询计划就是基于不同算法实现程序构造。
下图就是整个物理查询的框架示意图：
2. 如何衡量一个物理查询计划的好与坏?
DBMS 如何衡量物理查询计划的优劣呢?
衡量I/O访问次数
衡量CPU的占用时间
内存使用代价(与缓冲区数目与大小的匹配)
中间结果存储代价
计算量(如搜索记录、合并记录、排序记录、字段值的计算等)
网络通信量
最主要的是衡量I/O的访问次数，访问次数越少，计划就越好。
内存代价主要是缓冲区，比如说表连接，表连接对缓冲区非常敏感，缓冲区多可能一遍扫描，缓冲区少就会多次扫描。
依据什么信息来计算这些方案的上述各种指标呢?这是一个定量分析问题，定量分析有一些叫统计信息。
3.依据什么信息判断物理查询计划的好与坏?
依据数据库的一些统计信息---存放在数据字典或系统目录中的
TR或T(R):关系R的元组数目;
BR或B(R):关系R的磁盘块数目;
lR或l(R):关系R的每个元组的字节数;
fp或f(R):R的块因子，即一块能够存储的R的元组数目
V(A, R):R中属性A出现不同值的数目，即IПIa(R)的数目.
SC(A,R): R中属性A的选择基数，满足A上等值条件的平均记录数
b:每个磁盘块的字节数;
… …
>DBMS依据上述统计信息对DB操作的各种物理查询计划进行评估，以确定最优的计划予以执行。
统计信息，它实际上一般是存放在数据字典或系统数据目录里头。系统目录/数据字典，分为两类，一类就是模式信息，就是表名字、表头的信息，表有哪些列；还有一类叫统计信息，上面内容是统计信息的指标，这个统计信息，指标包括比如一个关系有多少行，这时查计数是不用数的，其实只要把那个一放就可以了，比如学校有三万名学生，这个值就等于3万。如果要查count *，比如select count * from student，后面无条件，比如校长想知道学校现有多少学生，马上就打一个语句select count * from student，数字就出来了。其实都不用去数，因为那个数字就在上面，有个计数器插入一行加一，删除一行减一。
这个关系占用的磁盘块数，比如3万个学生，假定一个学生的记录是200个字节，那么一个块儿大小是4K，就四千，四千被两百一除就可以算，一个块里头假如放20个学生，那么3万个学生，就能算出实际存放占用的物理块数。还有跟索引有关的，关系当中每一个元组的字节数，还有块因子，块因子就是一个块中能够存储的R的原子数目。
还有跟属性有关的，属性有关的V（A，R），R这个关系当中属性a出现的不同值个数，那么这个不同值个数实际上就是对它做投影以后消除以后的数目，那么这有两种情况，比如这个a是主属性，候选键，那么它的数目就跟这个行数是一样的，比方说学生学号上的属性的不同值个数，那么有3万学生就有3万个不同值。但是有的就不一样，比如学院，学院投影下来以后，比如这个学院里头有20个学员，那么就有20个不同值，如果性别，就两个不同值。另外就是属性a 的筛选基数，满足a上等值条件的平均记录数，这个实际上是概率问题。还有每个磁盘块的字节数，以上就是统计信息。
统计信息在行车的例子中，比如司机开车，他制定行车路线，也有统计，统计路的信息，这条路多长，多宽，几个车道。另外动态的有几个红绿灯、立交桥。司机根据这个信息，就可以估算出走这段路花多长时间。其实我们现在用电子地图，电子地图估算时间很准，它还去可以推荐路线，一条路上有多少红绿灯，车流量多少也能算出来。通过这段路线大概花多长时间？比方花20分钟，这段少花15分钟，它累加起来，然后可能再加个算法，有这些就可以估算出来。
上述信息如何获得呢?
4.如何收集这些信息?
>当一个表装入内存和创建索引的时候，统计信息不是被自动收集的，必须由 DBA 使用特定的命令来完成信息统计，这些命令就是收集统计信息并把其存入系统目录中的实用程序
>随着表的更新操作，统计信息可能会过时，过时的统计信息会使 DBMS 确定方案时决策错误，因此要求 DBA定期的对有频繁更新操作的 Table 进行统计
> DBA 要熟悉统计信息收集命令的使用，并定期执行
>IBM DB2使用 Runstats 收集统计信息
RUNSTATS ON TABLE username.tablename
[ WITH DISTRIBUTION[ AND DETAILED ]
{ INDEXES ALL | INDEX indexname} ];
>例如，收集 SCT 数据库的 Student 表的统计信息
Runstats on table SCT.student ;
>Oracle 使用 Analyze 命令收集统计信息并将其放入系统表中
ANALYZE { INDEX |TABLE | CLUSTER }
indexname | tablename | clustername }
COMPUTE STATISTICS
{ FOR TABLE | FOR ALL [ INDEXED ]COLUMNS [SIZE n]};
>例如，收集 SCT 数据库的 Student 表的统计信息
Analyze table student compute statistics for table ;
