关于数据库:StarRocks-技术内幕-Join-查询优化

6次阅读

共计 11157 个字符，预计需要花费 28 分钟才能阅读完成。

作者：贺凯，StarRocks Committer

导读：欢送来到 StarRocks 技术底细系列文章，咱们将为你全方位揭晓 StarRocks 背地的技术原理和实际细节，助你逐渐上手这款明星开源数据库产品。

本文整顿自作者在 StarRocks 线下 MeetUp 的分享，次要介绍 StarRocks 在 Join 查问布局上的教训和摸索。文章次要分为四个局部：Join 背景，Join 逻辑优化，Join Reorder，分布式 Join 布局。

#01

Join 背景

—

1、Join 类型

​

上图列举了常见的 Join 类型：

  • Cross Join：左表和右表的一个笛卡尔积。
  • Full / Left / Right Outer Join：Outer Join 须要依据语义，对两表 / 左表 / 右表上没有匹配上的行进行补 Null。
  • Anti Join：输入连贯关系上没有匹配上的数据行，通常 Anti Join 呈现在 not in 或者 not exists 子查问的布局中。
  • Semi Join：与 Anti Join 相同，只输入在连贯关系上匹配的数据行即可。
  • Inner Join：输入左表和右表的交加，依据连贯条件产生一对多的后果行。

2、Join 优化的难点

Join 的执行效率通常分成两局部来优化，一是进步单机上 Join 算子的效率，二是布局一个正当的 Join 打算，尽可能地缩小 Join 的输出 / 执行老本。本文次要集中在后者的介绍上，那么接下来就从 Join 优化的难点开始讲起。

  • 难点一，Join 的实现形式多。

​

如上图所示，不同 Join 的实现形式在不同场景下效率不同，如 Sort-Merge Join 在 Join 有序数据时，效率可能远高于 Hash Join，然而在数据 Hash 散布的分布式数据库里，Hash Join 的效率可能远比 Sort-Merge 高。而数据库则须要针对不同的场景，抉择适合的 Join 形式。

  • 难点二，多表 Join 的执行程序。

​

在多表 Join 的场景下，抉择度高的 Join 先执行，会进步整个 SQL 的效率，然而怎么判断出 Join 的执行程序呢？这却是十分困难的。

如上图所示，在 Left-Deep 模型下，N 个表 Join 可能的排列个数有 2^n- 1 个，然而在 Bushy 模型下，排列个数高达 2^(n-1) * C(n-1)个，对于数据库而言，查找一个最佳 Join 程序的耗时和老本是指数级的增长。

  • 难点三，Join 的成果难以评估。

​

在执行 SQL 之前，数据库难以精确评估一个 Join 理论的执行成果，通常咱们都认为小表 Join 大表的抉择度高于大表 Join 大表。然而理论状况下呢？显然并不是这样的，还有很多一对多的场景，甚至在更简单的 SQL 中，存在各种聚合、过滤的算子，在数据通过一系列运算后，数据库系统对于 Join 的输出都会难以评估精确。

  • 难点四，单机最优的打算不等于分布式最优。

​

在分布式系统中，会通过 Re-Shuffle 或者播送数据的形式，将须要的数据发送到目标端参加计算，分布式数据库中 Join 也是如此。但这也带来了另外一个问题，一个单机数据库上最优的执行打算，因为没有思考数据的散布 & 网络传输的开销，放在分布式数据库上未必是最优的执行打算。分布式数据库在布局 Join 的执行打算和执行形式时，须要思考数据的散布和网络老本。

3、SQL 的优化流程

​

StarRocks 对于 SQL 的优化次要通过优化器实现，次要集中在 Rewrite 和 Optimize 阶段。对于优化器的具体介绍能够参考 StarRocks 优化器代码导读（https://zhuanlan.zhihu.com/p/…）。

4、Join 优化的准则

StarRocks 目前 Join 的算法次要是一个 Hash Join，默认应用右表去构建 Hash 表，在这个前提下，咱们总结了五个优化方向：

  1. 不同 Join 类型的算子，性能是不同的，尽可能使用性能高的 Join 类型，防止使用性能差的 Join 类型。依据 Join 输入的数据量，大抵上的性能排序：Semi-Join/Anti-Join > Inner Join > Outer Join > Full Outer Join > Cross Join。
  2. Hash Join 实现时，应用小表做 Hash 表，远比用一个大表做 Hash 表高效。
  3. 多表 Join 时，优先执行抉择度高的 Join，能大幅缩小后续 Join 的开销。
  4. 尽可能减少参加 Join 的数据量。
  5. 尽可能减少分布式 Join 产生的网络老本。

#02

Join 逻辑优化

—

这部分次要给大家介绍一些 Join 上的启发式规定。

1、类型转换

第一个优化规定紧贴着后面所说的第一个优化准则，也就是把低效率的 Join 类型转为高效的 Join 类型，次要包含以下三个转换规则。

  • 转换规则一：Cross Join 转换为 Inner Join

当 Cross Join 满足某个束缚时，能够将 Cross Join 转为 Inner Join。该束缚为：Join 上至多存在一个示意连贯关系的谓词。例如：

-- 转换前
Select *  From t1, t2 Where t1.v1 = t2.v1; 

-- 转换后, Where t1.v1 = t2.v1 是连贯关系谓词
Select *  From t1 Inner Join t2 On t1.v1 = t2.v1;
  • 转换规则二：Outer Join 转换为 Inner Join

当满足以下束缚时，能够将 Outer Join 转为 Inner Join：

  1. Left / Right Outer Join 上存在一个 Right / Left 表的相干谓词；
  2. 该相干谓词是一个严格（Restrick Null）谓词。

例如：

-- 转换前                
Select *  From t1 Left Outer Join t2 On t1.v1 = t2.v1 Where t2.v1 > 0; 
-- 转换后，t2.v1 > 0 是一个 t2 表上的严格谓词
Select *  From t1 Inner Join t2 On t1.v1 = t2.v1 Where t2.v1 > 0;

须要留神的是，在 Outer Join 中，须要依据 On 子句的连贯谓词进行补 Null 操作，而不是过滤，所以该转换规则不实用 On 子句中的连贯谓词。例如：

Select *  From t1 Left Outer Join t2 On t1.v1 = t2.v1 And t2.v1 > 1; 
-- 显然，下面的 SQL 和上面 SQL 的语义并不等价
Select *  From t1 Inner Join t2  On t1.v1 = t2.v1 And t2.v1 > 1;

这里须要提到一个概念，即严格（Restrick Null）谓词。StarRocks 把一个能够过滤掉 Null 值的谓词叫做严格谓词，例如 a > 0；而不能过滤 Null 的谓词，叫做非严格谓词，例如：a IS Null。大部分谓词都是严格谓词，非严格谓词次要是 IS Null、IF、CASE WHEN 或函数形成的谓词。

StarRocks 对于严格谓词的判断，用了一个简略的办法：将须要检测的列全副替换成 Null，而后进行表达式化简。如果后果是 True，意味着输出为 Null 时，Where 子句无奈过滤数据，那么该谓词是一个非严格谓词；反之，如果后果是 False 或 Null，那么是一个严格谓词。

​

  • 转换规则三：Full Outer Join 转为 Left / Right Outer Join

同样，当满足该束缚时，Full Outer Join 能够转为 Left / Right Outer Join：存在一个能够 bind 到 Left / Right 表的严格谓词。例如：

-- 转换前
Select *  From t1 Full Outer Join t2 On t1.v1 = t2.v1 Where t1.v1 > 0; 
-- 转换后，t1.v1 > 0 是一个左表上的谓词，且是一个严格谓词
Select *  From t1 Left Outer Join t2 On t1.v1 = t2.v1 Where t1.v1 >

2、谓词下推

谓词下推是一个 Join 上十分重要，也是很罕用的一个优化规定，其次要目标是提前过滤 Join 的输出，从而晋升 Join 的性能。

对于 Where 子句，当满足以下束缚时，咱们能够进行谓词下推，并且随同着谓词下推，咱们能够做 Join 类型转换：

  1. 任意 Join 类型；
  2. Where 谓词能够 bind 到其中一个输出上。

例如：

Select *  
From t1 Left Outer Join t2 On t1.v1 = t2.v1 
        Left Outer Join t3 On t2.v2 = t3.v2 
Where t1.v1 = 1 And t2.v1 = 2 And t3.v2 = 3;

其谓词下推的流程如下。

第一步，别离下推 (t1.v1 = 1 And t2.v1 = 2) 和 (t3.v2 = 3)，因为满足类型转换规定(t1 Left Outer Join t2) Left Outer Join t3 转换为 (t1 Left Outer Join t2) Inner Join t3。

​

第二步，持续下推 (t1.v1 = 1) 和 (t2.v1 = 2)，且 t1 Left Outer Join t2 转换为 t1 Inner Join t2。

​

须要留神的是，对于 On 子句上的连贯谓词，其下推的规定和 Where 子句有所不同，这里咱们分为 Inner  Join 和其余 Join 类型两种状况。

第一种状况是，对于 Inner Join，On 子句上的连贯谓词下推，和 Where 子句雷同，下面曾经叙述过，这里不再反复。

第二种状况是，对于 Outer / Semi / Anti Join 的连贯谓词下推，须要满足以下束缚，且下推过程中无奈进行类型转换：

  • 必须为 [Left/Right] Outer/Semi/Anti Join；
  • 连贯谓词只能 bind 到 [Right/Left] 输出上。

例如：

Select *  
From t1 Left Outer Join t2 On t1.v1 = t2.v1 And t1.v1 = 1 And t2.v1 = 2 
        Left Outer Join t3 On t2.v2 = t3.v2 And t3.v2 = 3;

其 On 连贯谓词下推的流程如下。

第一步，下推 t1 Left Join t2 Left Join t3 上能够 bind 到右表的连贯谓词 (t3.v2 = 3)，此时无奈将 Left Outer Join 转换为 Inner Join。

​

第二步，下推 t1 Left Join t2 上能够 bind 到右表的连贯谓词 (t2.v1 = 2)。因为 t1.v1 = 1 是 bind 到左表的，下推当前会过滤 t1 的数据，所以该行为与 Left Outer Join 语义不符，无奈下推该谓词。

​

3、谓词提取

在之前的谓词下推的规定中，只能下推满足合取语义的谓词，例如 t1.v1 = 1 And t2.v1 = 2 And t3.v2 = 3 中，三个子谓词都是通过合取谓词连贯，而无奈下推析取语义的谓词，例如 t1.v1 = 1 Or t2.v1 = 2 Or t3.v2 = 3。

然而在理论场景中，析取谓词也非常常见，对此 StarRocks 做了一个提取谓词（列值推导）的优化。通过一系列的交并集操作，将析取谓词中的列值范畴提取出合取谓词，继而下推合取谓词。例如：

-- 谓词提取前        
Select *  
From t1 Join t2 On t1.v1 = t2.v1 
Where (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4)
 
-- 利用 (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 进行列值推导，推导出（t2.v1 >= 2），（t1.v2 IN (3, 4)）两个谓词
Select *  
From t1 Join t2 On t1.v1 = t2.v1  
Where (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 
AND t2.v1 >= 2 AND t1.v2 IN (3, 4);

这里须要留神的是，提取进去的谓词范畴可能是原始谓词范畴的超集，所以不肯定能间接替换原始谓词。

4、等价推导

在谓词上，除了上述的谓词提取，还有另一个重要的优化，叫等价推导。等价推导次要利用了 Join 的连贯关系，从左表 / 右表列的取值范畴，推导出右表 / 左表对应列的取值范畴。例如：

-- 原始 SQL
Select *  
From t1 Join t2 On t1.v1 = t2.v1 
Where (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 

-- 利用 (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 进行列值推导，推导出（t2.v1 >= 2），（t1.v2 IN (3, 4)）两个谓词
Select *  
From t1 Join t2 On t1.v1 = t2.v1  
Where (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 
AND t2.v1 >= 2 AND t1.v2 IN (3, 4); 

-- 利用连贯谓词 (t1.v1 = t2.v1) 和(t2.v1 >= 2)进行等价推导，推导出（t1.v1 >= 2）谓词
Select *  
From t1 Join t2 On t1.v1 = t2.v1 
Where (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4) 
AND t2.v1 >= 2 AND t1.v2 IN (3, 4) AND t1.v1 >= 2;

当然，等价推导的作用范畴并不像谓词提取一样宽泛，谓词提取能够在任意谓词上进行，但等价推导和谓词下推相似，在不同的 Join 上有不同的条件束缚，这里同样分为 Where 谓词和 On 连贯谓词来解析。

Where 谓词：

  • 简直没有束缚，能够从左表的谓词推导出右表，反之亦可。

On 连贯谓词：

  • 在 Inner Join 上和 Where 谓词雷同，没有条件束缚；
  • 除 Inner Join 外，仅反对 Semi Join 和 Outer Join，且仅反对与 Join 方向相同的单向推导。例如，Left Outer Join 能够从左表的谓词推导出右表的谓词，Right Outer Join 能够从右表的谓词推导出左表的谓词。

为什么在 Outer / Semi Join 上存在单向的限度呢？起因也很简略，以 Left Outer Join 为例，在谓词下推的规定中有提到，Left Outer Join 只能下推右表的谓词，而左表的谓词则因为守法语义导致无奈下推。所以执行等价推导时，从右表谓词推导出的左表谓词，同样须要满足该束缚。

那么在这个前提下，推导进去的左表谓词并不能起到提前过滤数据的作用，而且还会带来执行额定谓词的开销，所以 Outer / Semi Join 只反对单向推导。

对于等价推导的实现，StarRocks 是通过保护了两个 Map 实现的。一个 Map 用于保护 Column 和 Column 之间的等价关系，另一个 Map 则用来保护 Column 到 Value 或者表达式的等值关系，通过这两个 Map 互相查找，实现等价推导。如图：

​

5、Limit 下推

除了谓词能够下推，Join 上也反对 Limit 的下推。当 SQL 是一个 Outer Join 或 Cross Join 时，能够将 Limit 下推到输入行数稳固的孩子上。其中，Left Outer Join 输入行数至多和左孩子统一，那么 Limit 能够下推到左表上，Right Outer Join 反之。

-- 下推前
Select * 
From t1 Left Outer Join t2 On  t1.v1 = t2.v1 
Limit 100; 

-- 下推后
Select * 
From (Select * From t1 Limit 100) t Left Outer Join t2 On t.v1 = t2.v1 
Limit 100;

比拟非凡的是 Cross Join 和 Full Outer Join、Cross Join 的输入是一个笛卡尔积，行数是左表 x 右表；而 Full Outer Join 的输入行数，则至多是左表 + 右表，所以这两种 Join 能够在左表和右表上各下推一个 Limit。例如：

-- 下推前
Select * 
From t1 Join t2
Limit 100; 

-- 下推后
Select * 
From (Select * From t1 Limit 100) x1 Join 
     (Select * From t2 Limit 100)
Limit 100;

#03

Join Reorder

—

Join Reorder 用于推断多表 Join 的执行程序，数据库须要尽可能地先执行一个高抉择度的 Join，这样就能缩小后续 Join 的输出数据，从而晋升性能。

StarRocks 的 Join Reorder，次要是在一个间断的 Inner Join 或者 Cross Join 上工作。以下图为例，StarRocks 会将一组间断的 Inner / Cross Join 叫做一个 Multi Join Node，而 Multi Join Node 就是一个 Join Reorder 的单位，即下推存在两个 Multi Join Node，StarRocks 将别离对着两个 Multi Join Node 进行 Join Reorder 推导。

​

目前业界实现 JoinReorder 的算法有很多种，或者基于不同模型的，例如：

  • Heuristic：基于启发式规定的，相似 MemSQL，通过定义维度表核心表排 Join 程序。
  • Left-Deep：左深树模型，搜寻空间小，然而不肯定最优。
  • Bushy：浓密树模型，搜寻空间大，蕴含最优解。其常见的一些 reorder 算法有：

Exhaustive(Commutativity + Associativity) 

Greedy

Simulated annealing

DP（DPsize, DPsub，DPccp…）

Genetic：GreenPlum

 …… 

其中 StarRocks 实现了 Left-Deep、Exhaustive、Greedy、DPsub，接下来会着重介绍一下 StarRocks 中 Exhaustive、Greedy 的实现。

1、Exhaustive

穷举算法通常包含两个规定，通过这两个规定基本上笼罩 Join 的全排列组合。

  • 规定一：Join 的交换律。

A Join B 转为 B Join A，转换过程中须要留神 Join 类型的变动，比方 Left Outer Join 替换后变为 Right Outer Join。

​

  • 规定二：Join 的结合律。

(A Join B) Join C 转为 A Join（B Join C)。结合律上 StarRocks 又分为两种，一种是 Inner / Cross Join 的结合律，另一种是 Semi Join 的结合律。

​

2、Greedy

StarRocks 在贪婪算法上次要参考多序列贪婪算法，其次做了一个小改良，就是对于贪婪算法每层产生的后果，StarRocks 都会保留 10 个最优解（可能不是全局最优），以此往后迭代，最终计算出 10 个贪婪最优的 Plan。

当然，因为贪婪算法的局限性，这样的优化只是进步了计算出全局最优解的概率，并不能保障肯定失去全局最优的 Plan。

​

3、Cost Model

StarRocks 应用这些 Join Reorder 的算法推导出 N 个 Plan，最终会依据 Cost Model 的算法，估算出每个 Join 的 Cost，整个 Cost 的计算公式如下：

Join Cost: CPU * (Row(L) + Row(R)) + Memory * Row(R)

其中 Row(L）、Row(R) 别离示意 Join 左右孩子的输入行数，公式次要是思考 CPU 开销，以及 Hash Join 右表做 Hash 表内存的开销，下图具体展现了 StarRocks 中 Join 的输入行数的计算形式。

​

此外，因为不同算法摸索 Join Reorder 的空间不同，StarRocks 依照算法的空间复杂度和耗时做了根本的测试，具体如下。

​

基于上述耗时的论断，StarRocks 对各个算法的执行做了简略的限度。当在 4 表以内的 Join Reorder 应用穷举算法；4~10 表时会别离应用左深、贪婪、动静布局算法产生 1 个、10 个、1 个打算，并且在此基础上会应用 Join 交换律摸索更多的 Plan；当 10 表以上时，StarRocks 就只应用贪婪和左深产生的 11 个 Plan 为根底进行 Reorder；另外，在  StarRocks 没有统计信息时，基于 Cost 的贪婪和动规都无奈很好地工作，所以只会应用左深产生的 1 个 Plan 为根底 Reorder。

​

#04

分布式 Join 布局

—

在后面介绍完一个 Join 查问的一些逻辑上的优化点后，前面会联合 StarRocks 作为一个分布式数据库，在分布式 Join 执行上的优化。

1、MPP 并行执行

首先，StarRocks 的执行框架是一个 MPP 的并行执行架构，整体架构如图所示，以一个简略的 Join SQL 为例，StarRocks 执行 A Join B 的流程如下：

  1. 依照 A 表和 B 表的散布信息别离从不同的机器上读取数据；
  2. 依照 Join 的连贯谓词，将 A 表和 B 表的数据 Re-Shuffle 到同一批机器上；
  3. 单机 Join 执行，输入后果。

能够看到，理论执行过程中，不只是一台机器参加计算，A 表的机器、B 表的机器、Join 的机器可能都不是同一批机器，两头会波及到网络传输、数据交换等操作。而在这个过程中，很天然地就带来了网络操作的开销。所以对于 StarRocks，优化分布式 Join 效率中比拟重要的一个措施，就是尽可能地缩小网络开销，更正当地拆分 / 散发整个查问打算，尽可能将并行执行的劣势施展进去。

​

2、分布式 Join 优化

这里先介绍一些 StarRocks 能够生成的分布式执行打算，以一个最简略的 Join 为例：

Select * From A Join B on A.a = B.b

​

能够看到，StarRocks 理论执行中会产生 5 种最根本的分布式 Plan：

  • Shuffle Join：别离将 A、B 两表的数据依照连贯关系都 Shuffle 到同一批机器上，再进行 Join 操作。
  • Broadcast Join：通过将 B 表的数据全量的播送到 A 表的机器上，在 A 表的机器上进行 Join 操作，相比拟于 Shuffle Join，节俭了 A 表的数据 Shuffle，然而 B 表的数据是全量播送，适宜 B 表是个小表的场景。
  • Bucket Shuffle Join：在 Broadcast 的根底上进一步优化，将 B 表依照 A 表的散布形式 Shuffle 到 A 表的机器上进行 Join 操作，B 表 Shuffle 的数据量全局只有一份，比 Broadcast 少传输了很多倍数据量。当然，有约束条件限度，Join 的连贯关系必须和 A 表的散布统一。
  • Colocate Join：通过建表时指定 A 表和 B 表是同一个 Colocate Group，意味着 A、B 表的散布完全一致，那么当 Join 的连贯关系和 A、B 表散布统一时，StarRocks 能够间接在 A、B 表的机器上间接 Join，不须要进行数据 Shuffle。
  • Replicate Join：StarRocks 的试验性功能，当每一台 A 表的机器上都存在一份残缺的 B 表数据时，间接在本地进行 Join 操作，该 Join 的约束条件比拟严格，基本上意味着 B 表的正本数须要和整个集群的机器数保持一致，所以实际意义并不现实。

StarRocks 会对每个 Join 都尝试生成上述 5 种分布式 Join 打算，然而因为不同 Join 类型的语义限度，实际上一些非凡的 Join 类型只能生成特定的分布式 Join 打算。例如，Cross Join 只能生成 Broadcast Join。

3、摸索分布式 Join

StarRocks 的分布式 Join 打算，是通过一系列的 Distribution Property 推导产生的。以下述的 Join SQL 的 Shuffle Join Plan 为例，Join 会自顶向下地向 A、B 表别离要求 Shuffle Property。

当 Scan 节点无奈满足该要求时，会通过 Enforce 操作，退出一个 Shuffle 的操作节点，用于满足 Join 的要求。最初在生成执行打算时，StarRocks 会将 Shuffle 节点“翻译”成一个 Exchange 节点，通过该节点实现网络数据的传输和替换。

其余的分布式 Join 生成形式和 Shuffle Join 相似，都是由 Join 向下要求不同的属性推导出。

Select * From A Join B on A.a = B.b

​

4、简单的分布式 Join

在用户场景中，用户的 SQL 远比后面的一个 A Join B 简单得多，可能是 3 表 Join，也可能是 4 表 Join。实际上，StarRocks 对于更简单的 Join，同样也会生成更简单多样的分布式 Plan，但都是基于上述最根底的几种 Join 形式推导进去的。例如：

Select * From A Join B on A.a = B.b Join C on A.a = C.c

这里简略举几个 StarRocks 基于 Shuffle Join 和 Broadcast Join 生成的分布式 Plan：

​

当然，如果持续引入 Colocate Join 和 Bucket Shuffle Join，StarRocks 还能够推导出上面这样一些 Plan：

​

对于下面这些简单的分布式 Join Plan，其推导原理和后面的原理简直统一。Distribution Property 在节点间会始终向下传递，进而推导出各种 Join 组合的分布式 Plan。具体的推导实现也能够参考 StarRocks 优化器代码导读（https://zhuanlan.zhihu.com/p/…）。

5、Global Runtime Filter

除了分布式 Plan 的这样一些摸索外，StarRocks 在布局 Plan 时，还会联合 Join 算子的执行特点，来结构全局性的 Global Runtime Filter 这样一个优化。StarRocks 的 Hash Join 执行过程如下：

1.  StarRocks 先查问失去全量的右表数据；

  1. 将右表的数据结构为一个 Hash 表；
  2. 再去拉取左表的数据；
  3. 基于 Hash 表来构建 Join 的连贯关系；
  4. 输入 Join 后果。

那么，Global Runtime Filter 的工作机会就在 Step 2 和 Step 3 之间，StarRocks 在失去右表的数据后，通过这些运行时数据结构进去一个过滤谓词，在拉取左表数据前先将这样一个 Runime 的过滤谓词下发到左表的 Scan 节点，从而帮忙左表的 Scan 节点提前过滤数据，最终达到缩小 Join 输出的目标。

目前 Global Runtime Filter 反对的过滤形式为：Min / Max、In predicate 和 Bloom Filter。示意图如下：

​

#05

总结

—

本文讲述了 StarRocks 对 Join 查问优化的实际和摸索，所有的优化都是紧贴提到的优化准则。当然，用户在自行优化 SQL 时，也齐全能够参考如下 5 点，以及 StarRocks 提供的性能进行优化。

  1. 不同 Join 类型的算子，性能是不同的，尽可能使用性能高的 Join 类型，防止使用性能差的 Join 类型。依据 Join 输入的数据量，大抵的性能排序为：Semi-Join/Anti-Join > Inner Join > Outer Join > Full Outer Join > Cross Join。
  2. Hash Join 的实现时，应用小表做 Hash 表，远比用一个大表做 Hash 表高效。
  3. 多表 Join 时，优先执行抉择度高的 Join，能大幅缩小后续 Join 的开销。
  4. 尽可能减少参加 Join 的数据量。
  5. 尽可能减少分布式 Join 产生的网络老本。

StarRocks 在反对了那么多优化后，也有了更多的心得和更多的布局，比方：

  • 反对更多的 Join 实现形式，更智能地联合上下文抉择更适合的 Join 实现算子；
  • 联合 StarRocks 的个性，反对更多特定的 Join Reorder 算法；
  • 尽可能地解决 Cost 估算的问题，引入更多的算法或者数据结构来确保估算后果；
  • 反对更多调度形式，可能优化网络老本开销。

读到这里，好学的你是不是又产生了一些新思考与启发？

扫描下方用户群二维码退出 StarRocks 社区一起自在交换！

​

对于 StarRocks

面世两年多来，StarRocks 始终专一打造世界顶级的新一代极速全场景 MPP 数据库，帮忙企业建设“极速对立”的数据分析新范式，助力企业全面数字化经营。

以后曾经帮忙腾讯、携程、顺丰、Airbnb、滴滴、京东、众安保险等超过 170 家大型用户构建了全新的数据分析能力，生产环境中稳固运行的 StarRocks 服务器数目达数千台。

2021 年 9 月，StarRocks 源代码凋谢，在 GitHub 上的星数已超过 3400 个。StarRocks 的寰球社区飞速成长，至今已有超百位贡献者，社群用户冲破 7000 人，吸引几十家国内外行业头部企业参加共建。

正文完
数据库
发表至： 数据库
2022-11-03
 0
关于数据库:数据库系统概论王珊第九章关系查询处理和关系优化第二节查询优化
关于数据库:网关和ip地址一样吗
关于数据库:Kyligence-助力重庆银行获-IDC-FinTech-突破奖认可
关于数据库:使用-Easysearch-还原-Elasticsearch-快照数据

站内搜索

-「」