了解更多开源请访问：开源基础软件社区https://ost.51cto.com1984—关于分布式查询优化这部分是1984年分布式查询优化的总结，介绍了在分布式数据库中优化查询的各种技术。虽然没有涵盖关于该主题的所有建议算法，但概述了从现有算法中得出的相当多的想法。运营和成本措施假设关系数据库中的关系分布在不同的站点。本文中使用的关系数据操作包括投影、选择、连接和半连接。投影：选择符合关系的列。SELECT：选择符合关系的元组（行）。Join：就是合并两个表，然后选择满足关系的元组。半连接：属性A上从关系R2到关系R1的半连接用表示。其中R2为发送关系，R1为化简关系，A为连接属性。有时用来表示它可以通过在属性A上连接R2和R1来获得，然后将得到的关系投影到R1的模式上，半连接在数据库机器中很有用。如果不拆分关系，那么在投影和选择中，只涉及本地处理成本。但是，在进行join和semi-join时，除了本地处理成本外，还有不同站点之间的通信成本。例如，如果R1和R2在不同的站点，则R1必须发送到包含R2的站点。或者R2必须被送到R1的站来操作。本地处理成本通常根据磁盘访问次数和CPU处理时间来评估，而通信成本则根据传输的数据总量来表示。但本地处理成本对于本地网络更为重要。网络在这里主要被认为是地理上分散的计算机网络。我们假设将一定数量的数据（比如X）从一个站点传输到另一个站点的成本是c0+c1*X，其中c0是启动传输的启动成本，c1是比例常数。回答查询的成本可以用总成本或响应时间来表示。在上图（a）中，回答查询所需的X个数据单元从站点1传输到站点2，Y个数据单元从站点2传输到站点3，总成本为（c0+c1*X）+(c0+c1*Y)=2c0+c1*(X+Y)。响应时间是从发起查询到产生答案的时间。上图（b）中，站点1的X个数据单元和站点2的Z个数据单元并行传输到站点3回答查询，响应时间成本为c0+c1*X和c0+c1*的最大值Z，在本文中我们主要关注总成本的测量。由于传输的数据量会影响策略的成本，因此有人尝试降低成本。一种可能的方法是使用半连接。例如上图（a）中，从属性B上的关系R2到关系R1的半连接，可以将R2投影到属性B上，再将投影后的结果与R1连接起来。可以看出得到的结果比原来的R1小很多。当c0比较小的时候，这个semi-join是合理的。但另一方面，在上图（b）中，如果R1和R2之间有很多共同的值，使用半连接可能不划算，所以在进行半连接之前，它最好估计两个关系值之间的共同值个数。Estimation从上面可以看出，分布式性能查询处理算法的性能在很大程度上取决于一些中间关系的大小。因此，选择一个合理的估计算法是极其重要的。半连接后，R1投影在b属性上的问题可以用下面的球颜色问题来证明：“有n个球，m种颜色不同，如果从n个球中随机抽取t个球，求颜色的期望值。“可以得到如下公式：如果按照当前形式计算公式，其计算成本会变得非常大，当t取大时可能会造成溢出。半连接策略也可以看作是一个有向图，期望数也可以通过有向图来估计。将半连接策略视为有向图，其中顶点是Ri到Rj之间的关系。有向边表示从Ri到Rj的半连接，即Ri->Rj。执行的第一个半连接是入度为0的半连接。然后，生成简化的Rj，用表示。然后就是->，入度变为0，就会执行。显然，半连接策略中不会有有向环。假设有三个关系R1、R2、R3，每个关系都有属性值A和B。在上面的策略中，R1-B->R2-A->R3和R2-B->R1-A得到的关系->R3在执行半连接后是不相等的，因此，在半连接策略中计算关系的大小一定要了解操作的过程。三个阶段分布式查询的处理可以分为三个阶段：副本识别阶段、简化阶段和组装阶段。在副本识别阶段，查询条件中出现的每个关系的一个或多个副本被识别出来，用于处理查询。由于分布式数据库系统可能包含关系的多个复制副本，因此识别关系的适当副本以最小化传输成本可能不是一个容易的过程。在简化阶段，通常使用半连接来剔除不满足查询条件且需要最大成本降低的关系元组。例如，对于前面引用的带有关系副本的最佳选择查询，可以执行半连接来消除一些元组，而不会产生通信成本。如果半连接的结果不是最优结果，可以进行其他半连接以降低成本。在组装阶段，查询产生的关系被发送到站点以生成用户请求的输出。我们想指出的是，将查询处理策略分为三个阶段只会简化所涉及的概念。选择关系副本的合理策略是找到包含最少平均所选关系副本数的站点。不幸的是，这也是一个NP完全问题，即最难的确定性问题。但是，由于查询所引用的关系数量和包含这些关系的站点数量通常很少，因此通过枚举找到站点数量并不需要太多时间。稍后将详细描述还原阶段和组合阶段。树查询和循环查询特点：只有某些类型的查询可以使用半连接来解决。更准确地说，如果消除所有不满足查询条件的元组，则投影关系将完全减少。如果使用半连接来减少关系，则可能会产生较少的通信成本。但是查询中出现的关系可能不会完全减少。所以，拼凑关系的沟通成本还是很高的。因此，需要精确描述可以通过半连接完全减少的查询类型。树状查询图：关系的查询图可以转换为树状查询图。如果查询图不是树形的，那么这是一个循环查询。前面提到，如果查询是树查询，树查询的关系可以通过半连接完全缩减，但是循环查询不能通过半连接完全缩减。这说明了识别查询是否为树查询的重要性。有一个简单的算法可以识别，如下。该算法将查询作为输入，有两个关键步骤。最初，对于每个关系Rt，构造出现在条件中的关系的属性集J(Rt)。如前所述，假设存在三个关系R1R2R3。在第一步中，假设有一个关系保证可以通过替换表中的每个子元组来构造等价替换。替换后Ri仅出现在关系Ri.X=Rj.X中。显然，在查询图中，Ri和Rj成为相邻的，不属于任何循环。因此，消除R不会改变查询图的类型。图7中R3的A2属于R1，将R3到R4的边替换为R1到R4的边（以及R1到R3的边）。因此R3不属于任何循环，可以在不影响查询类型的情况下将其剔除。在第二步中，如果在第一步中消除了任何关系，则检查它是否导致了属性的消除。如果一个属性只有一个包含该属性的剩余关系，则该属性将被删除。（如果一组关系包含相同的属性，则它们的关系由该属性的相等性决定；因此，如果只有一个关系具有该属性，则关系不存在。）显然，删除一个属性会导致更新关系R。如果在算法结束时消除所有关系，则原始查询是树查询，因为算法不影响查询的类型（树查询或循环查询），空查询显然是树询问。如果算法末尾确实存在某些关系，则可以表明原始查询是循环查询。将循环查询转换为树查询因为树查询是完全可简化的，所以需要一种可以将循环查询转换为树查询的算法。基本上，存在三种不同的转换算法：(1)关系合并算法。(2)元组分解算法。(3)属性添加算法。关系合并算法只是将存在于循环中的某些关系连接起来以消除循环。例如，给定下图(a)所示的循环查询，该算法可以加入循环中的任意两个关系。这会导致循环消失。下图(b)显示了将R1和R2连接在一起的查询图。元组分解算法：R1thm算法是基于Wong和Youssefi的元组替换思想。该算法通过将循环查询分解为多个树子查询来消除循环。(3)属性添加算法：将循环中涉及的一些关系的一些属性添加到其他关系中，产生树查询。任何给定的关系都可以通过半连接完全简化。简单查询的最佳策略减少阶段中描述的查询处理算法是启发式的，不一定会产生最佳策略。在本节中，提出了一种简单查询的优化算法（其中出现在该查询约束中的所有关系都具有相同的属性，并且每个关系都具有一个属性）。策略的成本是由执行边表示的半连接的数据传输成本的总和。由于不可能在策略执行之前找到它的确切成本，因此通常的程序是最小化预期成本。对于简单的查询，优化策略可以满足一定的性质。他们的清单如下：所有的关系都应该出现在一个方向上。有两种情况。在第一种情况下，生成的站点是R1,R2。...嗯。在另一种情况下，站点不包含这n个关系中的任何一个。如果生成的站点不包含这n个关系中的任何一个，则最优策略中的所有关系都是不同的；也就是说，关系不会出现超过一次。这个结论相当明显，因为如果一个关系出现两次或更多次，那么该关系的第二次和后续出现可以从策略中删除，从而产生一个等效但成本更低的策略。因此，最优策略实际上是R1,R2。...嗯。对于简单的查询，可以很容易地获得最优策略。这里只描述TREG查询的最优策略，目的是为了得到彻底减少树查询尖点的最优策略。限制是任何两个关系最多有一个共同的连接属性。基于半连接的启发式讨论了两种使用半连接的查询处理算法。他们假设已经选择了查询引用的每个关系的副本，然后执行简化和组装阶段。第一种半连接X-A-Y的成本定义为将X.A从包含A的站点移动到包含Y的站点的成本（如果两个站点相同，则成本为零）。半连接的好处是运算前Y的大小减去运算后Y的大小。如果成本小于收益，则半连接是有利可图的。reduce阶段非常简单；它识别任何两个关系之间所有可能的半连接。估计每个半连接的成本和收益。然后选择成本最低的有利半连接。半连接策略可能影响的成本和收益会不断更新并参与到后续的半连接中。重复此过程，直到找不到合适的半连接为止。基于连接的算法虽然使用半连接减少了数据传输的次数，但它并不总是最佳解决方案。原因之一是，对于某些网络，交换的消息数量可能比传输的数据量更重要。毕竟，使用半连接时，可能会生成额外的消息。另一个原因是本地处理成本可能高得令人望而却步。最后，使用半连接的效果时间最小化是复杂的，尽管半连接可以并行执行。第二种：一位教授提出了一种算法，它是对上面给出的处理简单查询的最佳算法的概括。该算法构建的策略是n个子策略的并集，每个子??策略对应一个关系，n为查询引用的关系数。考虑用于查询的关系R。设A为R的一个join属性，找到一个最优的方式来简化R，只对属性A使用semi-join将R送到结果站点生成答案。枚举算法该算法首先将查询中的关系集分为两个互补组G1和G2，其中G1至少有两个关系，G2有零个或多个关系。接下来，通过将包含最大关系的站点指定为结果站点并将G1中的所有其他关系发送给它来获得G1中关系的子策略。它通过递归调用G2中的关系找到最小成本子策略。假设关系R1、R2、R3位于不同的位置，查询要求连接这三个关系，算法首先将R1、R2、R3划分为{{R1,R2},{R3}}。然后构造{R1,R2}的最小成本子策略，将两个关系R1和R2中较小的一个发送给另一个。将R1和R2（如T1）的关系加入第二组，求{T1,R3}的最小成本子策略。然后得到R1、R2、R3的连接策略。对{{R1,R3},{R2}}、{{R2,R3}、{R1}}和{{R1,R2,R3},{}}重复相同的过程。最后得到查询的最优策略。非数值算法将查询分解为链式查询并解决它们以获得答案。链式查询是指查询图为链的查询。一个给定的链式查询被分解成多个子查询，两个连续的子查询之间最多有一个公共变量。每个子查询都是不可约的。我们假设关系没有被分割，只考虑数据通信成本。如果一个子查询是一个有两个节点的链，比如Rx和Ry，那么要么Rx被发送到包含Ry的站点，要么Ry被发送到包含Rx的站点，这取决于哪种策略产生的成本更低。如果子查询是循环查询，则必须决定是一次处理整个子查询还是将其细分为多个部分。如果一个子查询有以下条件，将其细分以降低成本。假设给定一个指定为根节点的链式查询。该算法找到会合点，即查询引用的数据量最大的站点。然后，算法重复以下过程，直到获得链式查询的答案。从叶子开始，该算法首先将叶子与其父节点连接起来，然后将结果发送到集合点以检查它是否比将两个关系直接发送到集合点并在那里连接它们更便宜。如果前一种策略成本较低，则合并叶节点及其父节点以形成临时关系，并修改查询图以用新创建的关系替换图中连接两个关系的部分。否则，叶节点被发送到集合点并从查询图中删除。在修改后的查询图上重复此过程。当连接两个关系时，算法会将较小的关系发送到包含较大关系的站点并将它们合并。片段处理关系可以看作一个矩阵，其中行代表元组，列代表属性。关系的水平切片是矩阵行的子集。它是通过对关系应用选择操作获得的。有时一个水平段在一个站点被频繁访问，而另一个水平段在另一个站点被频繁引用。因此，根据站点的参考位置将片段分配给站点可能是有益的。关系的垂直切片是关系列的子集，是使用关系上的投影操作构造的。本节仅讨论水平分段。在这种方法中，引用分段关系的查询首先被分解为子查询。然后，使用第7节中描述的算法获得每个子查询的答案。所有子查询答案的并集就是查询的答案。转换方法或许处理查询的一种更系统的方法是转换方法。在这种方法中，有一组规则，其中每个规则将查询表达式转换为等效表达式。这个想法是重复应用规则以获得可以毫不费力地评估的表达式。通常，应用一元运算符（如project或select）后的结果关系往往比原始关系小，而应用二元运算符（如join或union）后的结果关系可能比原始关系大得多操作数。如果操作数位于不同的位置，则可以通过应用一元运算符来减小它们的大小，同时保持表达式的等价性。例如在属性B上加入RI(A,B,C)和R2(B,E,F)关系，然后将结果投影到属性(A,B,E)上，相当于投影到属性A和BR1用来消去C，R2投影到属性B和E上去消去F，然后将两者的简化关系连接起来。如果R1和R2位于不同的位置，则可以用较少的数据传输计算后一个表达式，因此更可取。2021—：地理分布式查询处理方法当今的全球化世界拓宽了数据分析应用程序的范围。大型组织在不同地点拥有多个数据库和IT基础设施组织需要在不同地点进行数据分析。以统一的方式支持地理分布的数据分析对于组织的日常运营至关重要。本节介绍了一个基于合规性的查询优化器，它考虑了使用我们的策略表达式以声明方式指定的数据流策略，以生成合规的地理分布式执行计划。前提示例有一家名为CarCO的公司，在三个地区设有分支机构。它的总部位于欧洲，并在欧洲设有多个办事处。数据库记录为DN。它在北美设有子公司。数据库表示为DE。供应商的制造单位在亚洲。该数据库表示为DA。数据表是：因为在实际的地理情况下，数据的传输是有规则约束的，称为数据流约束。假设CarCo不同地理位置的数据流向如下：1.北美客户在抑制账户余额信息后只能发送到国外。2.欧洲只能发送聚合订单数据到亚洲，订单价格不能发送到北美。3.只有从亚洲聚合的订单数量和扩展价格才能运送到欧洲。这里的工作目标有两个：1.确定一个简单有效的数据流策略。2.设置优化器。关于数据流策略定义数据流策略指定的信息以及该信息可以合法传输的方式和位置。我们使用数据流策略来表示位置D的信息可以传输到位置LD。指定策略规范的一种简单直接的方法——策略表达式。两条规定：1.用屏蔽函数（简单表达式和聚合表达式）转换数据。2.信息公开方式（表明哪些数据不允许发送）。查询示例如下：selectC.name,sum(O.totprice),sum(S.quantity)fromCustomASC,OrdersASO,SupplyASSwhereC.custkey=O.custkeyandO.ordkey=S.ordkeygroupbyC.name该查询的意思是查询Custom表中的name属性，C.custkey=O.custkey时Orders表中totprice的总和，O.ordkey=O.ordkey时Supply表中数量的总和S.ordkey，并带有name属性。这个简单的表达式假定该策略还允许将客户的市场细分和区域信息发送到欧洲，供CarCo的商业客户使用。我们可以使用以下策略表达式：shipcustkey,namefromCustomerCtoAsia,Europeshipmktseg,regionfromCustomerCtoEuropewheremktseg='commercial'聚合表达式虽然简单的表达式足以表示各种各样的数据流策略，但有些策略只允许传递聚合信息。将acctbal作为聚合总和，来自CustomerCto*groupbymktseg的avg，region兼容的优化查询处理系统将策略存储在策略目录中以进行查询优化。在查询时，基于合规性的查询优化器在枚举计划时使用此策略目录（通过策略评估器）来验证它们是否符合输入数据流策略。优化器使用此验证机制来了解最终查询执行计划(QEP)何时违反现有数据流策略。如果是，则拒绝执行查询。只有生成的QEP满足要求，才会继续执行查询。兼容的查询处理框架依赖于两个核心部分：(i)指定与每个数据位置关联的数据流策略，以及(ii)在这些策略下的查询优化过程。下面首先将数据流策略和一致性查询计划的概念形式化，然后定义一致性查询处理问题。跨境数据流动政策描述了对跨组织和/或地理边界的数据传输的限制。一般而言，数据流策略规定了哪些信息以及该信息可以合法传输的方式和位置。基于Volcano的优化器生成器1.引入了新的抽象逻辑属性来注释运算符。执行特性是一种逻辑属性，描述了运算符可以在何处合法执行，而传输特性则描述了运算符的输出可以在何处合法传输。如图，节点3代表一个执行特征，表示允许在北美执行。节点4代表发货功能，节点3的结果可以发货到欧洲和北美。根据数据流策略，一个算子节点可以有0个、1个或更多的执行和交付特征。2.调整每个物理算子的代价函数。成本函数已扩展以考虑运算符的执行特征，以防止优化器丢弃未注释运算符的计划/子计划。3.引入了一组规则，允许我们在计划枚举期间确定注释。它们使优化器能够在优化期间获得计划操作员的执行和交付特征。优化器通过其规则引擎将运算符节点与注释规则进行匹配，以获得它们的传输和执行特征。四个标注规则：(1)假设一个算子节点n具有执行特征，则l为合法操作执行的位置。(2)假设一个算子节点n具有一个执行特性，即当操作的所有输入都可以运送到l时，该操作就可以在l进行。例如，在美国加入来自欧洲和亚洲的数据，只有当两种类型的数据都可以合法地运送到美国时才合法。(3)假设运营商节点n具有传输特性，即传输特性是union传输特性和执行特性的结合，那么操作者的输出总是可以合法地传输到合法执行的地方。(4)假设运算符节点n具有传输特性，规则调用属于单个数据源的查询子表达式的策略评估。计划注释器-计划注释器在优化第一阶段的作用：它接收逻辑计划和基于合规性的优化目标作为输入，以输出带注释的QEP。合规性基于优化目标：将优化目标设置为指定非空传输特性需求的规划向量，以及所需的物理属性。优化过程假定给定逻辑表达式和基于合规性的优化目标，计划注释器从初始表达式树开始。计划注释器从初始表达式树开始，并通过Volcano的规则引擎重复应用规则，以枚举qep的搜索空间。规则是：1.代数等价规则。2、逻辑算子节点转换为物理算子节点的实现规则。3.强制规则可以“强制”输入具有特定的物理属性。计划注释器依靠Volcano的搜索引擎和基于成本的修剪来确定成本最低的注释计划。上图是经过优化的带注释的QEP查询图SiteSelector——优化的第二阶段已经有了带注释的QEP图。站点选择器的作用是继续放置操作员节点。可能的后果：计划成倍增长。从上面也可以看出，选址器不应该使用贪心法和穷举枚举，而是使用动态规划：一种递归的自上而下的记忆。选址算法：了解更多开源请访问：开源基础软件社区https://ost.51cto.com。
