分布式数据库查询优化PPT学习教案

1、会计学1分布式数据库查询优化分布式数据库查询优化分布式查询优化的目标 分布式数据库系统中进行查询优化的最终目标就是尽量使总代价最小和使查询响应时间最短。1.总代价：在分布式数据库系统中，除了包括在集中式数据库中的 CPU 代价和 I/O 代价（合称为局部处理代价）之外，由于数据分布在不同的结点上，在数据查询处理中还需要考虑到站点间传输数据的通信代价，因此，总代价=CPU 代价+I/O 代价+通信代价。2.响应时间：指从接收查询到完成查询的时间间隔。在分布式数据库系统中，响应时间既与通讯时间有关，又与局部处理时间有关。第1页/共16页第2页/共16页1.基于关系代数等价变换的优化基于关系代数等价

2、变换的优化 首先把查询内容转化为关系代数表达式，经过分析得到查询树，然后将原始查询树经过从全局到片段的变换变成了基于片段的查询树，最后经过一系列的基于关系代数等价变换规则的优化算法的转化，使该查询树中选择和投影操作尽可能靠近叶结点，笛卡儿乘积运算尽可能远离叶结点，这样就可以减少操作量和操作次数，从而达到查询优化的目的。第3页/共16页第4页/共16页第5页/共16页3.SDD_1 查询优化算法查询优化算法 大致思想是通过反复的获得有益半连接运算，减少每个站点上用于连接运算的数据，然后将所有站点的数据汇集到数据量最大的站点做最后装配。第6页/共16页处理过程主要包括三个步骤：1.初始化：从全部关

3、系中的半连接中生成有益的半连接集合；2.选择有益的半连接：从有益的半连接集合中找出最有益的半连接，将其添加到执行策略中，并相应地修改被影响关系的统计值(选择因子，关系的大小等)；3.选择组装场地：重复第一步，直到所有有益的半连接加入到执行策略中，关系经上面步骤缩减后，选择存储数据量最大的站点为组装场地；第7页/共16页4.基于查询图的贪婪算法基于查询图的贪婪算法 贪婪算法实际上是一种自底向上的启发式查询优化算法，在选择连接顺序时，总是使用一种简单而严格的选择方法，每次都是选取当前代价最小的一个连接，这样便可使整个系统最终查询的总代价达到最小。 基于查询图的贪婪查询实际上是一种动态优化方案，在具

4、体查询过程中，可以用中间查询结果的大小近似地表示当前通信代价的大小，因此，对于不同结点之间进行查询连接时，应当选取查询运算最小的中间结果，从而降低当前查询代价，达到局部最优。第8页/共16页算法设计： 1.对于相邻的结点进行连接查询时，首先需要找出中间结果最小的连接运算。然后把这两个相邻节点合并成一个节点。 2.采用与1中同样的方法继续在查询图中寻找最小的连接运算，把相邻的节点合并，如果合并的过程中查询图出现线段合并，线段上的值为原先两条线段值的成绩。 3.最后执行剩余两个节点的连接。第9页/共16页以下通过一个例子对该算法做扼要介绍:第10页/共16页图 3.8 中，圆圈内的数字表示站点号，

5、圆圈外的数字表示该站点的数据大小，直线上的数字表示该直线所连接的两个站点的选择因子。1.贪婪算法首先找出中间结果最小的连接运算。该图中，站点1和站点2做连接运算产生的中间结果最小，为 10*10*0.2=20。将图 3.8 中的站点1和站点2进行合并，变为图 3.9第11页/共16页图 3.9 中，站点 3 和站点 4 做连接运算的中间结果最小，为 10*10*0.330。将图 3.9 中的站点 3 和站点 4 进行合并，变为图 3.10。第12页/共16页将图 3.10 中的 12 和 34 进行合并就可以得出连接策略了，其中间结果大小为 20+30+20*30*0.06=86。第13页/共16页连接策略可以通过图 3.11 所示的二叉树表示。即(12)(34)。第14页/共16页 当两个站点合并引起两条线段合并