分布式数据库查询

数据库查询组长：郭培伦组员：牟斌皓、李骁汇报人：郭培伦目录：•分布式数据库特点•查询优化的意义•分布式查询处理的层次结构•分布式查询优化•常用分布式查询数据优化策略分布式数据库特点：数据的物理分布性数据的逻辑整体性站点自治性分布式数据库查询优化的研究意义：分布式查询处理作为分布式数据库研究主要问题之一，它是用户与分布式数据库之间的接口，在分布式数据库中由于数据的分布与冗余，使得数据在各站点间的传输代价成为查询处理的主要矛盾；另一方面，数据的分布与冗余也增加了查询的并发处理的可能性，从而可以缩短查询处理的响应时间，提高处理速度。因此，与集中式数据库相比，分布式查询处理增加了不少新内容与复杂性。分布式查询处理的层次结构查询分解数据本地化全局优化局部优化查询分解•查询分解是将查询问题(如SQL语句)转换成一个定义在全局关系上的关系代数表达式。这一层的做法与集中式DBMS相同，因为并未涉及分布问题。本层转换所需要信息在全局概念模式中得到数据本地化•数据本地化是把一个在全局关系上的查询进行具体化到合适片段上的查询。这一变换所需要信息在分片模式和片段的分配模式中获得。全局优化•全局优化输入是分片查询，全局优化是找出分片查询的最佳操作次序，包括使得代价函数最小。全局优化一个重要方面是关于连接操作的优化，全局优化处理层输出是一个优化的、片段上的关系代数查询。这层转换所需要信息来自数据库的统计信息，包括各站点片段统计信息、资源信息和通信信息等。局部优化•局部优化由与查询有关片段的各个站点执行。它由该站点上的DBMS进行优化，采用集中式数据库系统中查询优化的算法，所需要信息来自于局部模式。分布式查询优化全局优化层基于半连接算法的查询优化基于直接连接算法的查询优化数据本地化层数据本地化阶段一般采用的是基于关系代数等价变换的优化算法分布式查询处理的过程实质是利用数据传递策略和局部数据处理策略，把分布查询转化为局部查询的过程。分布式查询处理数据传递局部处理分布式数据库系统中，用户可以用全局查询评议对多个数据库同时进行查询，即为全局查询。查询过程逻辑分解评议转换优化组合全局查询过程：逻辑分解成几个子查询，每个子查询对应一个局部数据若全局查询评议与局部查询评议不同，则进行语言的等价转换各个子查询的结果优化组合后返回。常用的分布式数据库的查询优化策略基于关系代数等价变换的优化算法基于半连接操作的查询优化算法基于直接连接操作的查询优化算法基于关系代数等价变换优化算法的基本原理：•把查询问题转变为关系代数表达式，分析得到查询树(语法树)•进行从全局到片段的变换得到基于片段上的查询树•利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。关系代数等价变换规则的优化算法•利用关系代数等价变换规则，把查询树中连接和合并操作尽可能上提(向树根方向移)。选择和投影操作尽可能下移(向树叶方向移)到片段的定义处。这就是说，尽可能先执行选择和投影操作，后执行连接和合并操作。经过选择和投影操作不但可以减少其后操作的操作量，而且还可以减少操作次数。基于半连接操作的查询优化算法基本思想•数据以整个关系在网络中传输，这显然是一种冗余的方法，在一个关系传输到另一场地后，并非每个数据都参与连接操作或都是有用，因此，不参与连接的数据或无用的数据不必在网络中来回传输基于半连接的优化策略的基本原理•采用半连接操作，在网络中只传输参与连接的数据。基于直接连接操作的查询优化算法•基于直接连接操作的查询优化是一种完全在连接的基础上考虑查询处理的策略。直接连接使用场合•a)查询目标表中的属性很少，也不是某连接条件属性。•b)半连接的缩减效果较差时。Reference•[1]BellD,GrimsonJ.Distributeddatabasesystems[M].Addison-WesleyLongmanPublishingCo.,Inc.,1998.•[2]DwyerPA.Automatedqueryoptimizationmethodusingbothglobalandparallellocaloptimizationsformaterializationaccessplanningfordistributeddatabases:U.S.Patent4,769,772[P].2010.•[3]ChaudhuriS.Anoverviewofqueryoptimizationinrelationalsystems[C]//ProceedingsoftheseventeenthACMSIGACT-SIGMOD-SIGARTsymposiumonPrinciplesofdatabasesystems.ACM,2000(3):34-43.