StarRocks数据库查询加速及Colocation Join工作原理_ar

注：本篇文章阐述的是starrocks-3.2版本的colocation join

官网文章地址：

一、starrocks数据划分

在介绍colocation join之前，再回顾下starrocks的数据划分及tablet多副本机制。

starrocks支持两层的数据划分，第一层是range partition，第二层是hash bucket（tablet）。starrocks的数据表按照分区分桶规则，被水平切分成若干个数据分片（tablet，也称作数据分桶 bucket）存储在不同的be节点上，每个tablet都有多个副本（默认是3副本）。各个 tablet 之间的数据没有交集，并且在物理上是独立存储的。tablet 是数据移动、复制等操作的最小物理存储单元。一个 tablet 只属于一个数据分区（partition），而一个 partition 包含若干个 tablet。

下图说明 table、partition、bucket（tablet）的关系：

假设table 按照 range 的方式按照 date 字段进行分区，得到了 n 个 partition
每个 partition 通过相同的 hash 方式将其中的数据划分为 m 个 bucket（tablet）
从逻辑上来说，bucket 1 可以包含 n 个 partition 中划分得到的数据，比如下图中的 tablet 11、tablet 21、tablet n1

1.1 分区

逻辑概念，分区用于将数据划分成不同的区间，主要作用是将一张表按照分区键拆分成不同的管理单元。查询时，通过分区裁剪，可以减少扫描的数据量，显著优化查询性能。

1.2 分桶

物理概念，starrocks一般采用hash算法作为分桶算法。在同一分区内，分桶键哈希值相同的数据会划分到同一个tablet（数据分片），tablet以多副本冗余的形式存储，是数据均衡和恢复的最⼩单位，数据导入和查询最终都下沉到所涉及的 tablet副本上。

二、colocation join实现原理

2.1 colocate join概述

在数据分布满足一定条件的前提下，计算节点只需做本地 join，减少跨节点的数据移动和网络传输开销，提高查询性能。colocate join 十分适合几张大表按照相同字段分桶的场景，这样可以将数据预先存储到相同的分桶中，实现本地计算。

要理解这个算法，需要先了解以下几个概念：

colocation group（cg）：同一 cg 内的表需遵循相同的 colocation group schema（cgs），即表对应的分桶副本具有一致的分桶键、副本数量和副本放置方式。如此可以保证同一 cg 内，所有表的数据分布在相同一组 be 节点上。
colocation group schema（cgs）：用于描述一个 cg 中的table，和colocation相关的通用 schema 信息。包括分桶列类型，分桶数以及副本数等。
分桶编号bucket seq：一个表的数据，根据分桶列 hash、对桶数取模后落在某一个分桶内。假设一个 table 的分桶数为 8，则共有 [0, 1, 2, 3, 4, 5, 6, 7] 8 个分桶（bucket）。因此【分桶列 hash %桶数】一致的数据会划分到同一个桶中。

2.2 colocate join工作原理

colocation join 功能，是将一组拥有相同cgs 的 table 组成一个 cg。并保证这些 table 对应的数据分片会落在同一个 be 节点上。使得当 cg 内的表进行分桶列上的 join 操作时，可以通过直接进行本地数据 join，减少数据在节点之间的传输耗时。

因此核心问题直接转变成【如果保证这些table对应的数据分片会落在同一个be节点上？】

同一 cg 内的table必须保证以下属性：

（1）分桶列和分桶数

同一 cg内表的分桶键的类型、数量和顺序完全一致，并且桶数一致，从而保证多张表的数据分片能够一一对应地进行分布控制。

分桶列，即在建表语句中distributed by hash(col1, col2, ...) 中指定的列。分桶列决定了一张表的数据通过哪些列的值进行hash划分到不同的tablet 中。同一 cg内的 table 必须保证分桶列的类型和数量完全一致，并且桶数一致，才能保证多张表的数据分片能够一一对应的进行分布控制。

（2）副本数

同一个 cg内所有表的所有分区（partition）的副本数必须一致。如果不一致，可能出现某一个 tablet 的某一个副本，在同一个 be 上没有其他的表分片的副本对应。不过，同一个 cg 内的表，分区的个数、范围以及分区列的类型不要求一致。

ps：同一个 cg 内所有表的分区键，分区数量可以不同。因为partition只是一个逻辑上的分区，真正影响数据分布在哪一个be节点的是由bucket决定的。

综上，在固定了分桶列和分桶数后，同一个cg内的表会拥有相同的buckets seq。而副本数决定了每个分桶内的 tablet 的多个副本分别存放在哪些 be 上。假设buckets seq为 [0, 1, 2, 3, 4, 5, 6, 7]，be 节点有 [a, b, c, d] 4个。则一个可能的数据分布如下：

cg 内表的一致的数据分布定义和tablet副本映射，能够保证分桶列值相同的数据都在同一个 be 节点上，可以进行本地数据 join。其核心思想是「两次映射」，保证相同的 distributed key 的数据会被映射到相同的 bucket seq，再保证 bucket seq对应的 bucket 映射到相同的 be 节点：