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

64次阅读

共计 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
关于数据库:赵强老师MySQL高可用架构MHA
关于数据库:如何掌握openGauss数据库核心技术秘诀二拿捏执行器技术2
关于数据库:峰会回顾-基于StarRocks百草味如何通过数据赋能快消品行业
关于数据库:论文领读Presto-SQL-on-Everything