作者 | 刘垚
编辑 | 尔悦
小 T 导读：在应用或者实现分布式数据库（Distributed Database）时，会面临把一个表的数据依照肯定的策略扩散到各个数据库节点上的状况，随之而来的是多节点数据查问复杂性的问题，例如 Join 和子查问。本文将会为你解读分布式数据库下子查问和 Join 等简单 SQL 如何实现，来帮忙你更好地解决上述问题。
首先简略讲一下 SQL 的执行过程：
SQL ==> Parser ==> Translate & Semantic Check ==> Optimizer ==> Coordinator ==> Executer
- Parser 产生的是语法树，即 Abstract Syntax Tree；
- Translate & Semantic Check，这一步会从 Catalog 读取元数据，用元数据欠缺语法树，便于 Optimizer 应用。例如：常见的 select from tableA，个别会在这一步把“”换成 tableA 的列；
- Optimizer 产生的是优化之后的逻辑执行打算，即 Optimized Logical Plan，执行打算是个有向无环图，即 DAG；
- Coordinator 负责散发逻辑执行打算给各个节点去计算；
- Executer 会把逻辑执行打算转成物理执行打算，即 Physical Plan。
开源的数据库有很多，咱们能够联合一些支流数据库的源代码来了解子查问和 Join 的实现形式，比方关系型数据库：Impala、Presto、ClickHouse，时序数据库（Time- Series Database）：TDengine 等。上面从子查问和 Join 两局部进行剖析。
子查问局部
逻辑执行打算有多种 Node，别离对应着 SQL 中的各种计算，包含 Scan Node、Join Node、Aggregate Node、Sort Node、Project Node 等等，相应的物理执行打算的算子为 Scan Operator、Join Operator、Aggregate Operator、Sort Operator、Project Operator 等等。而数据库个别没有计算子查问的算子，这是因为将形象语法树转成逻辑执行打算之后，就曾经没有子查问的概念了，其运行逻辑是数据算子之间自下而上逐层传递，并逐层计算，并不特地计算子查问。上面讲一下分布式数据库针对子查问的一些相干解决。
首先，分布式数据库的优化器会将子查问扁平化解决，这种形式个别分为两种，一种是间接在语法树（AST）上做子查问扁平化（Subquery Flatten），另外一种是在生成逻辑执行打算时进行扁平化。这两种形式实质上大同小异，都要保障语义的等价性。但也并不是所有的子查问都能扁平化，有如下几种非凡状况：
- 子查问和父查问都有汇集函数
- 子查问有汇集函数，并且父查问有分组计算（Group By）
- 子查问有汇集函数，并且用子查问汇集函数的后果关联（Join）父查问的表
- 父查问有汇集函数，并且子查问有分组计算（Group By）
- 子查问有 Limit（限度返回后果的行数），并且父查问有过滤条件（Where）或者分组计算、排序（Order By）
- 其余
基于 AST 进行子查问扁平化时，须要先遍历语法数据，并按规定进行判断，进而去除不必要的子查问。对于生成逻辑执行打算时的子查问扁平化，在生成 Plan Node 时须要先去除冗余的 Node，举个例子，SQL：select colA from (select * from tA) group by colA;
一般来说，逻辑执行打算会有多个子打算，通常在须要网络传输时才会产生子打算，须要留神的是子打算和子查问之间并没有必然的分割，即有子查问不肯定对应一个子打算。
Join 局部
首先，分布式数据库会对 Join 进行优化，包含 Join 打消（例如基于主键外键去除不必要的 Join）、外连贯打消（Outer Join 转成 Inner Join）、Join Order 优化（基于数据的统计信息，用动静布局算法、贪婪算法或遗传算法等优化 Table 的 Join 程序）等等。
再讲一下 Join 的三种根本算法：Hash Join（必须要有等值连贯条件，例如 t1.colA = t2.colB）、Merge Join（左表和右表的数据都是有序的，按连贯条件中的列有序）、Nestloop Join（含有非等值连贯条件并且数据无序）。在理论当中，会把三种算法进行混合应用，这是因为 Join 条件能够同时蕴含等值连贯和非等值连贯，例如 t1.colA = t2.colB AND t1.colC > t2.colC
Hash Join
在进行 Join Order 优化时，优化器会调整左表和右表的程序，个别把小表放左边，大表放右边，并且抉择 Join 模式：Shuffle Join（依照关联条件，同时 shuffle 左表和右表，而后再计算 Join）或 Boradcast Join（把右表播送到左表所在的节点，留神左表不动，而后再计算 Join）。个别是基于代价去抉择 Join Order 优化，但思考到统计信息可能会存在误差，因而很多数据库能够通过 Hint、Query Option 等形式，由用户来指定 Join 程序、Join 模式等。
Hash Join 是目前最罕用的 Join 算法，大部分数据库都实现了 Hash Join。这种算法会先读取右表，并把右表的数据放入 Hash Map 里，如果存不下就会放入外存。通常状况下，各个数据库都会实现本人的 Hash Map，很少间接应用 STL 或 Boost 等第三方库中的 Hash Map，起因次要有两点：
- 定制化 Hash Map 会晋升 Join 计算速度。
- 定制化 Hash Map 能更精确地管制内存应用，当内存不足时，会应用外存，定制化 Hash Map 能够依据 Join 算法，优化 Swap 机制，缩小 Swap 的数据量。Hash Map 的构造如下：
右表可能含有反复的数据，所以会有 Duplicate Node。这里的反复数据是指 Join Key（Join 条件对应的列）的数据反复，并且其余列不反复，所以要别离缓存。留神上述图中，是通过 Hash 算法解决 Hash 抵触的问题，即不会把不同的 Join Key 放在同一个桶中。当然，事实操作中也有把不同的 Join Key 放在同一个桶中的状况，那须要遍历 List 能力确定查找的 Join Key 是否存在。
Merge Join
Merge Join 个别是在左表和右表的数据是有序的状况下应用。例如时序数据库 TDengine，数据按工夫戳列有序，那么用工夫戳列做 Join 时，TDengine database 会用 Merge Join 来计算，这样的一个益处是处理速度十分快，并且占用内存十分小。
Nestloop Join
这种 Join 算法速度十分慢，但对于全功能数据库而言是不可短少的。应用这种算法时，能够联合索引来提速。
总结而言，Hash Join 应用最广，实用于很多数据分析的场景，并且大部分数据库都反对；Merge Join 个别是在左右表数据有序时才会应用，不须要缓存数据，所以应用内存非常少，计算速度是三种 Join 算法中最快的；Nestloop Join 性能很差，分布式数据库个别很少应用，有些分布式数据库就不反对，能够通过索引来减速 Nestloop Join。
写在最初
下面咱们对子查问和 Join 两种简单 SQL 的实现形式做了具体解读，大家能够联合一些开源数据库的源代码来了解，像 TDengine 的源代码都能够在 GitHub 上看到，如果你对时序数据库的简单 SQL 实现有趣味，这就是一个不错的观摩对象。也欢送大家在下方评论区进行交换。
想理解更多 TDengine Database 的具体细节，欢送大家在 GitHub 上查看相干源代码。