分布式数据库如何实现 Join？

作者 齐木

用关系型数据库一定多多少少会用到 Join 操作。常见的 Join 有 Nested-Loop Join Hash Join Sort Merge Join 等等。实际在 OLTP 场景中 最常用的就是基于索引点查的 Index Nested-Loop Join 这样的 Join 往往能在极短的时间内返回 相信这也是大多数开发同学对 Join 的感受。

PolarDB-X 不仅语法兼容 MySQL 作为分布式数据库 也力求保持与单机数据库一致的使用体验。在分布式场景下 Join 的两张表可能都是分布式表 因此需要通过多次网络请求获取相应的数据。如何高效地实现这一点呢

MySQL 的 Join 实现

我们先看看单机数据库上的 Join 是怎么做的。MySQL 支持的 Join 算法很有限

Nested-Loop Join (NL Join)Batched Key Access Join (BKA Join)Block Nested-Loop Join 版本 8.0.20 Hash Join (版本 8.0.18)

如果 Join 两侧的任何一张表上 join key 列存在索引 那么 MySQL 通常会使用基于索引的 BKA Join 或 NL Join 我们实际使用中的绝大多数情形都对应这种方式。如果 Join 两侧都没有索引可以用 那么 MySQL 只能退而求其次选择 Block Nested-Loop Join 或 Hash Join 取决于 MySQL 版本 。我们今天主要关注 NL 和 BKA Join。

Nested-Loop Join 是最简单的 Join 形式 可以看作一个两层 For 循环。对于外表 也称为驱动表 中的每一行 循环检查内表 也称为被驱动表 的每一行 如果满足 Join 条件则作为 Join 结果输出。如果 Join Key 在内侧表有索引可用 那么内表的循环可以大大简化——只要查索引即可拿到可以 Join 的行 无需遍历整个表。我们也将这种带索引的 NL Join 称为 Index Nested-Loop Join。

# Nested-Loop Join
for outer_row in outer_table:
 for inner_row in inner_table:
 if join_condition is True:
 output (outer_row, inner_row)
# Index Nested-Loop Join
for outer_row in outer_table:
 for inner_row in inner_index.lookup(outer_join_key):
 if join_condition is True:
 output (outer_row, inner_row)

注 *左右滑动阅览

下面的例子中 orders 表通过 customer 表的主键 c_custkey 与之进行 Join MySQL 会使用 Index NL Join 算法完成 Join。

/* Query 1 */
SELECT o_orderkey, o_custkey, c_name
FROM orders JOIN customer ON o_custkey c_custkey
WHERE o_orderkey BETWEEN 1001 AND 1005

注 *左右滑动阅览

BKA Join 可以看作一个性能优化版的 Index Nested-Loop Join。之所以称为 Batched 是因为它的实现使用了存储引擎提供的 MRR Multi-Range Read 接口批量进行索引查询 并通过 PK 排序的方法 将随机索引回表转化为顺序回表 一定程度上加速了查索引的磁盘 IO。

下面的例子中 Join Key 命中的是二级索引 并且 SELECT 的列包含二级索引中所不包含的列 因此需要进行索引回表得到完整的 Join 结果。

/* Query 2 */
SELECT c_name, c_custkey, o_orderkey, o_totalprice
FROM customer JOIN orders ON c_cutkey o_custkey
WHERE c_custkey BETWEEN 13 AND 15

注 *左右滑动阅览

通常 OLTP 查询中 Join 驱动侧的数据量不大 并且 Join 往往都有能匹配的索引。这种情况下 NL Join、BKA Join 的代价与驱动侧的数据量呈线性相关 可以迅速计算出结果。

PolarDB-X 的 Lookup Join

PolarDB-X 的架构与 MySQL 有很大的不同 它的架构可以分为 SQL 层和存储层 SQL 层的计算节点需要计算数据所在的分片 然后从多个 DN 节点 数据节点 拉取所需的数据。

对于 Join 查询 如果恰好 Join Key 和拆分键一致 那么可以将其下推到 DN 执行。否则 就需要在 CN 节点执行 Join。PolarDB-X 支持多种 Join 算法 包括 Lookup Join、Nested-Loop Join、Hash Join、Sort-Merge Join 等多种执行方式。在 OLTP 查询中最常用的就是类似 MySQL BKA Join 的 Lookup Join 本文主要介绍 Lookup Join 其他 Join 诸如 Hash Join、Nested-Loop Join 等将在以后的文章中介绍。

除了 Join 本身的功能需求 PolarDB-X 的 Lookup Join 的设计中还要考虑以下两个性能需求

批量。在分布式数据库中 CN 到 DN 的每一次查询都会经过网络 RPC 其延迟相比 MySQL 的本地调用要大几个数量级 因此批量处理显得更为重要。并发。由于数据可能分布在多个 DN 节点上 如果依次遍历则会引入大量不必要的等待 最好的做法是并发地对所有 DN 进行查询 这样每批数据仅需一次网络 round-trip。

Lookup Join 的执行过程如下 非索引回表情形

从驱动侧拉取一批数据。通常情况下数据量不会很多 如果数据较多 那么每个批的大小受到 lookup 端的分片数量以及是否可以进行分片裁剪限制。批大小的选择会直接影响查询性能 如果批特别小会导致 RPC 次数太高 批太大则会导致内存中暂存的数据量膨胀 高并发情况下可能导致 OOM。默认情况下我们尽可能让每个分片平均查询 50 个值、最多不超过 300 个值。计算 batch 内每行数据所在分片 由于 lookup 侧是一个分区表 驱动表的每行数据要 lookup 的数据位于不同的分区中。只有包含数据的分片才需要参与 Join 如果没有任何值被路由到某个分片上 那么这个分片也无需被 Lookup。并发请求所有需要 lookup 的分片 并将查到的数据行以 Join Key 为 Key 构建成哈希表 缓存在内存中。类似于 Hash Join 利用哈希表为驱动侧的每行找到与其 Join 的行 取决于 Join 类型 可能 Join 出 0 行、1 行或多行。

/* Query 1 */
SELECT o_orderkey, o_custkey, c_name
FROM orders JOIN customer ON o_cutkey c_custkey
WHERE o_orderkey BETWEEN 1001 AND 1005

注 *左右滑动阅览

这个过程中有一些有趣的细节 例如 当要 lookup 的列不止一列 例如 X A AND Y B 时如何处理 这时可以通过 row-expression 组成多列的 IN 条件。如果多列 IN 条件中出现 NULL 如何处理 对于 Anti-Join 如何处理 这些就不在这里展开了 有兴趣的同学可以在评论交流。

对于绝大多数 TP 查询 Lookup Join 都可以通过一次 lookup 完成 Join 将延迟降到了最低。

全局索引与 Lookup Join

PolarDB-X 还支持全局索引 用户可以为分区表创建全局索引表 加快对索引键的查询。和本地索引一样 如果查询中包含索引未覆盖的列 全局索引也需要进行回表。回表的做法和上一小节的 Lookup Join 过程是完全一致的 不难理解——索引回表可以看作一种特殊的 1:1 的 Join。

依赖全局索引的 Join 则更为复杂一些 回忆下 MySQL 的 BKA Join 需要进行两次 lookup

第一次用 Join key 查询全局索引表 用于 Join 第二次用全局索引表中的主键查询主表 用于索引回表 将回表结果以 PK 为 key 构建哈希表 与2中的查询结果 Join 得到完整的 Join 右侧数据将完整的 Join 右侧数据以 Join Key 为 key 构建哈希表 与 1 的数据 Join 得到最终 Join 结果

/* Query 2 */
SELECT c_name, c_custkey, o_orderkey, o_totalprice
FROM customer JOIN orders ON c_cutkey o_custkey
WHERE c_custkey BETWEEN 13 AND 15

注 *左右滑动阅览

绝大多数 OLTP 查询数据量都能通过单个 batch 完成 完成查询的总延迟为 3 次 round-trip。不难证明在分布式情况下这是最优的。

此外 PolarDB-X 也允许用户手动将更多的列加入全局索引的覆盖列 牺牲部分写入性能换取更好的读取性能 如果所有列均被覆盖则无需进行回表 只需两轮 round-trip 即可。更进一步 PolarDB-X 鼓励用户通过合理设计拆分键尽可能将 Join 下推。

参考资料

1. Enhancing Productivity with MySQL 5.6 New Features

2. MySQL · 特性分析 · 优化器 MRR BKA

3. ?Block Nested-Loop and Batched Key Access Joins

【相关阅读】

PolarDB-X 让“Online DDL”更Online

PolarDB-X SQL限流 为您的核心业务保驾护航

通篇干货 纵观 PolarDB-X 并行计算框架

HTAP 数据库“必修课” PolarDB-X Online Schema Change

PolarDB-X 向量化引擎的类型绑定与代码生成

每次都需要解释大量指令 使用 PolarDB-X 向量化引擎

PolarDB-X 面向 HTAP 的混合执行器

PolarDB-X 面向 HTAP 的 CBO 优化器

如宝马3系和5系 PolarDB-X 与 DRDS 并驾齐驱

PolarDB-X 存储架构之“基于Paxos的最佳生产实践”

PolarDB-X 私有协议 提升集群的性能和稳定性

技术解读 | PolarDB-X 分布式事务的实现

技术解读 | PolarDB-X 强一致分布式事务

PolarDB-X 一致性共识协议 (X-Paxos)

本文转自网络，原文链接：https://developer.aliyun.com/article/783392
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！