《数据库系统概论》笔记：查询优化部分

作者: 日期:2010-08-11

字体大小: 小中大

　　进入优化查询部分：
　　总代价=I/O代价+CUP代价+内存代价

　　P159的例子还是让我觉得晦涩难懂！我恨课本！
　　这3个例子说下：
　　1. 假设A，B做连接，那么执行方式大概是：在内存中读入尽可能多的A，然后读入B。做连接操作，连接后的元组装满一块就写到中间文件。继续读B，做连接，直到内存中的A用完。
　　此时再次读入A表，执行上述操作。
　　完成广义笛卡尔积的连接后，进行满足逻辑条件的选择操作。
　　对上述结果做投影。
　　2. 不进行广义笛卡尔积连接，进行自然连接。后两步与上面一样
　　3. 先对B表做选择。然后读取A表，将A表和做了选择操作的B表做连接。
　　投影输出结果。

　　以上3个例子书本是为了做效率比较的，用了数学计算方式，我就做个印象的比较。
　　1. 做广义笛卡尔积连接的开销是巨大的（实际上现实中几乎不可能用到）
　　2. 自然连接的开销也很大
　　3. 做连接的主表应该是小表。所以例3将表B做了选择操作，然后与A表进行连接。
　　综上所述：连接是占用开销的主要因素，做连接的表应该先精简。

　　P161的查询优化一般准则：
　　1. 选择运算应该尽可能先做。
　　2. 执行连接前对关系做预处理。预处理1：建立索引。当建立索引后就不必读出全部的元组，而读出逻辑条件需求的元组。2：排序合并。该方法在连接之前按连接的属性列进行排序。如此可以保证连接的两个表都只读一次。（关于这个在脑子里多回忆一下，不知道会记得多久。本来画图的，结果停电了，画了一半没存，就算了）
　　3. 投影与选择同时进行。当对一个表进行这样的操作的时候，投影会扫描一次表，选择会扫描一次表。所以节省开销的方法是这两个操作同时进行。
　　4. 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。——书中原话。之所以摘抄原话是因为“双目运算”的意义我不是很清楚。大致理解的是：P56写的二目运算（传统的集合运算）
　　我如此理解：即涉及到两个表的操作的，均应该先做投影，或者结合结果投影掉不想要的属性列。如果在最后结果中有些属性列不需要则又要扫描一次表，此为浪费开销。这和先做选择，再做连接操作或预处理都是一个意思。
　　5. 继续摘抄书上晦涩难懂的原话（我恨课本）：把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算速度要比同样关系上的笛卡尔积省很多时间。
　　我的理解：1）别做广义笛卡尔积连接；2）要做就做自然连接；3）连接前记得先选择一下。
　　6. 当某个公共子表达式会被频繁使用的时候。这个子表达式的结果不是很大的关系。从外存读入该结果的时间比计算该结果的时间少很多。则把该子表达式的结果放入中间文件是合算的。
　　当查询的是视图时，定义视图的表达式就是公共子表达式的情况——此段话我不理解。
　　即：用I/O的开销换CPU的开销。

　　关系代数的变换规则。以下我均用通俗的方式表述。公式我也不会打。
　　规则1：连接、笛卡尔积交换律
　　即两个关系代数（理解为两个表好了），他们做连接、自然连接、笛卡尔积的时候可以互换位置。是完全等价的。
　　如果这个正确。那么做连接操作的时候，主表应该选择小表是不是应该的呢？从规则1来看，是无所谓的。但是考虑到磁盘的I/O和内存的利用，我想应该是小表放前。关于此我还需要验证一下。

　　规则2：连接、笛卡尔积的结合律
　　即3个或更多的表做连接、自然连接、笛卡尔积的操作的时候可以随便先做哪两个。

　　规则3：投影的串接定律
　　即对一个表做多少次投影，以最终的投影条件为准。在最终条件之前的各种投影条件都是废的。
　　对应准则4。该定律减少投影次数，反过来则将投影次数增多。

　　规则4：选择的串接定律
　　即对一个表做多少次选择，最后的选择结果是前面所做的各种选择的条件的交集。即多次选择的公共之处，就是最后选择的条件，从而得出最后选择的结果。
　　这个定律要求优化选择条件。
　　该定律减少选择次数，反过来则增加选择次数。
　　实际执行的是：把选择的条件分解，然后用多个（嵌套的）选择来表达。

　　规则5：选择与投影的交换律
　　即对一个表先做选择还是先做投影都是一回事。
　　这和前面的准则：选择投影一起做的准则是一致的。
　　本规则有个一般形式，该形式的作用是把一个投影转换为多个投影。理解为精简的投影再添加一些列进去。这个有必要把公式弄出来：
　　投影操作A列（选择操作F（E））=投影操作A列（选择操作F（投影操作A列B列（E）））
　　这个公式怎么理解呢？它强调选择操作F——中有不属于A列的属性B列。原书P163页。我讨厌书上写的这些艰深晦涩的东西。为什么不举个例子呢？难道都是老师的事情？书写清楚点不好？？
　　为什么我要对这个东西纠缠这么久呢？因为后面说规则5的一般形式可以把一个投影变换为多个投影。
　　该公式反过来看，就是多个投影选择的操作简化为一个选择一个投影。

　　规则6：选择与笛卡尔积的交换律
　　该规则就是：先做选择，后做连接。
　　假设A，B表，有如下3种情况：
　　1. 对A表可做F选择。则先对A表做F选择后再和B连接
　　2. 对A表可做F1选择，对B表可做F2选择。则先分别对这两个表做选择后，再做连接操作
　　3. 对A表颗做F1选择，对A，B表可做F2选择。则先对A做选择，然后做连接，对连接的结果做F2选择。

　　规则7：选择与并的交换
　　注意并的概念，前面有说了，就是把两个表摞起来，所以并操作是强调两个表的属性列都是一样的。
　　这个规则的意思是：把表并起来再做选择和做了选择再并是一回事。从这两个表有相同的属性列可以很容易理解这一点。
　　先做选择再并可以节省系统开销。

　　规则8：选择与差的交换
　　注意差的意义是：只留下重复的元组。
　　所以本规则的意义是：两个表先找出重复的元组再做选择操作和两个表先选择再找出重复的元组的操作是一样的。
　　和上面的规则一样。也很好理解。只是系统的开销应该会明显不同。先选择的操作开销会小些。

　　规则9：投影与笛卡尔积的交换
　　理解方式和7，8一样，笛卡尔积是元组上的操作（行上的操作）与列无关（注意理解自然连接的重复列是保留了其中一列的，这与上面的话不矛盾）。
　　所以两个表，先做连接再做投影，和先做投影，再做连接是一回事。
　　先做投影可以节省系统开销。

　　规则10：投影与并的交换
　　把两个表并了之后，再做投影，和先做投影再摞起来（并）的操作，是一回事。
　　先做投影可以节省系统开销。

　　以上规则的使用方法：
　　1. 用规则4——把关系的交集还是转化为单次的查询，即每次使用一个关系。
　　如：对一个表要做4种关系（F）的选择。那么就用嵌套的4次选择完成。
　　2. 对每一个选择，用4~8的规则，尽可能的把选择移到语法树的顶端。（顶端最先执行）
　　3. 对每一个投影，使用规则3，9，10，5中的一般形式尽可能的把它移到树的顶端。5为什么放在最后？是因为5规则即适用于选择又适用于投影。
　　注意规则3（干脆称之为最终投影规则）会使一些投影消失。而规则5把一个投影分裂为两个（关于此要好好理解下，目前是没摸清楚的）
　　4. 利用规则3，4，5。规则3：投影串接转化为一个投影；规则4：选择串接转化为一个选择；规则5：选择和投影的串接转化为一个选择后跟一个投影。
　　减少选择or投影的操作的目的是减少对表的扫描。所以这3个规则是为了让多个选择or投影能同时执行，或在一次扫描中全部完成。
　　5. 关于方法5，我是完全的看不懂，所以直接照抄了：
　　把上述得到的语法树的内节点分组。每一双目运算（广义笛卡尔积X，自然连接，并，差（书上就记了几个符号））和它所有的直接祖先为一组（这些直接祖先是选择，投影运算）。如果其后代直到叶子全是单目运算，则也将它们并入该组，但双目运算时笛卡尔积（X）、而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。
　　尝试着理解了一下：一组的意思大概就是这些可以放在一条直线上。如果理解错了，那就错了。
　　6. 第六步也直接抄录：
　　生成一个程序，每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。（这种保证的废话也说的出来）

　　随后举了一个应用：
　　1. 从这个应用中学到的是：把查询转换为语法树。结果在上，其它步骤在下。
　　2. 然后使用上述规则优化该树。一般来说，靠经验，但是对于特别复杂的查询，如果靠经验（脑力）都理不清楚的，直接使用规则也许就是更简单的办法。
　　3. 对索引、数据的存储分布等进行优化。操作如：选择的字段上加索引，连接的两个表进行排序，连接字段上加索引，连接字段进行排序。优化存储路径（DBA职责）
　　4. 查询计划——该计划应该是DBMS完成的。可能会做：
　　·对两个表做排序预处理
　　·对R1在连接属性上建索引
　　·对R2在连接属性上建索引
　　·在R1，R2的连接属性上均建索引
　　对多个查询计划的代价估计也要花费系统开销。计算代价主要考虑磁盘的I/O，CPU和内存的代价在粗略估算时可不考虑。
　　