分布式数据库查询优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分布式数据库的查询优化,1.分布式查询优化的目标,2.分布式查询优化的方法,分布式查询优化的目标,分布式数据库系统中进行查询优化的最终目标就是尽量使总代价最小和使查询响应时间最短。1.总代价：在分布式数据库系统中，除了包括在集中式数据库中的 CPU 代价和 I/O 代价（合称为局部处理代价）之外，由于数据分布在不同的结点上，在数据查询处理中还需要考虑到站点间传输数据的通信代价，因此，总代价=CPU 代价+I/O 代价+通信代价。,2.响应时间：指从接收查询到完成查询的时间间隔。在分布式数据库系统中，响应时间既与通讯时间有关，又与局部处理时间有关。,分布式查询优化的目标,分布式查询优化的方法,1.基于关系代数等价变换的优化,首先把查询内容转化为关系代数表达式，经过分析得到查询树，然后将原始查询树经过从全局到片段的变换变成了基于片段的查询树，最后经过一系列的基于关系代数等价变换规则的优化算法的转化，使该查询树中选择和投影操作尽可能靠近叶结点，笛卡儿乘积运算尽可能远离叶结点，这样就可以减少操作量和操作次数，从而达到查询优化的目的。,分布式查询优化的方法,2.基于语义信息的优化,语义查询是利用数据库的完整性约束定义把初始的查询转为一个语义等价的，但是处理代价更小的查询。与一般的查询处理过程所不同的是，基于语义信息的查询处理扩展了传统的数据字典，在 IDB（Intelligent Database）中加入了新的语义信息规则，增添了语义优化过程。使用这种方法不仅可以提高查询的效率并且可把一般查询对于非索引属性的检索转变成为一个对索引属性的检索。但是又存在着增加处理时间的不足。在查询数据量较大的分布式数据库中宜于使用该算法。,分布式查询优化的方法,分布式查询优化的方法,3.SDD_1 查询优化算法,大致思想是通过反复的获得有益半连接运算，减少每个站点上用于连接运算的数据，然后将所有站点的数据汇集到数据量最大的站点做最后装配。,分布式查询优化的方法,处理过程主要包括三个步骤：,1.初始化：从全部关系中的半连接中生成有益的半连接集合；,2.选择有益的半连接：从有益的半连接集合中找出最有益的半连接，将其添加到执行策略中，并相应地修改被影响关系的统计值(选择因子，关系的大小等)；,3.选择组装场地：重复第一步，直到所有有益的半连接加入到执行策略中，关系经上面步骤缩减后，选择存储数据量最大的站点为组装场地；,分布式查询优化的方法,4,.基于查询图的贪婪算法,贪婪算法实际上是一种自底向上的启发式查询优化算法，在选择连接顺序时，总是使用一种简单而严格的选择方法，每次都是选取当前代价最小的一个连接，这样便可使整个系统最终查询的总代价达到最小,。,基于查询图的贪婪查询实际上是一种动态优化方案，在具体查询过程中，可以用中间查询结果的大小近似地表示当前通信代价的大小，因此，对于不同结点之间进行查询连接时，应当选取查询运算最小的中间结果，从而降低当前查询代价，达到局部最优。,分布式查询优化的方法,算法设计：,1.对于相邻的结点进行连接查询时，首先需要找出中间结果最小的连接运算。然后把这两个相邻节点合并成一个节点。,2.采用与1中同样的方法继续在查询图中寻找最小的连接运算，把相邻的节点合并，如果合并的过程中查询图出现线段合并，线段上的值为原先两条线段值的成绩。,3.最后执行剩余两个节点的连接。,以下通过一个例子对该算法做扼要介绍,:,分布式查询优化的方法,图 3.8 中，圆圈内的数字表示站点号，圆圈外的数字表示该站点的数据大小，直线上的数字表示该直线所连接的两个站点的选择因子。,1.贪婪算法首先找出中间结果最小的连接运算。该图中，站点1和站点2做连接运算产生的中间结果最小，为 10*10*0.2=20。将图 3.8 中的站点1和站点2进行合并，变为图 3.9,分布式查询优化的方法,分布式查询优化的方法,图 3.9 中，站点 3 和站点 4 做连接运算的中间结果最小，为 10*10*0.330。将图 3.9 中的站点 3 和站点 4 进行合并，变为图 3.10,。,分布式查询优化的方法,将图 3.10 中的 12 和 34 进行合并就可以得出连接策略了，其中间结果大小,为 20+30+20*30*0.06=86。,连接策略可以通过图 3.11 所示的二叉树表示。即(12)(34)。,分布式查询优化的方法,当两个站点合并引起两条线段合并时，新的选择因子取原来两个选择因子的乘积为近似值。,该算法没有提及中间结果如何存放，没有使用半连接来减少通信代价。,该算法求得的解不一定是最优的。,分布式查询优化的方法,