源码分析 | ClickHouse和他的朋友们(15)Group By 为什么这么快

本文首发于 2021-01-26 21:31:12

《ClickHouse 和他的朋友们》系列文章转载自圈内好友 BohuTANG 的博客,原文链接:
https://bohutang.me/2021/01/21/clickhouse-and-friends-groupby/
以下为正文。

在揭秘 ClickHouse Group By 之前,先聊聊数据库的性能对比测试问题。

在虎哥看来,一个“讲武德”的性能对比测试应该提供什么信息呢?

首先要尊重客观事实,在什么场景下,x 比 y 快?
其次是为什么 x 会比 y 快?

如果以上两条都做到了,还有一点也比较重要: x 的优势可以支撑多久? 是架构等带来的长期优势,还是一袋烟的优化所得,是否能持续跟上自己的灵魂。

如果只是贴几个妖艳的数字,算不上是 benchmark,而是 benchmarket。

好了,回到 Group By 正题。

相信很多同学已经体验到 ClickHouse Group By 的出色性能,本篇就来分析下快的原因。

首先安慰一下,ClickHouse 的 Group By 并没有使用高大上的黑科技,只是摸索了一条相对较优的方案。

一条 SQL

1
SELECT sum(number) FROM numbers(10) GROUP BY number % 3

我们就以这条简单的 SQL 作为线索,看看 ClickHouse 怎么实现 Group By 聚合。

1. 生成 AST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
EXPLAIN AST
SELECT sum(number)
FROM numbers(10)
GROUP BY number % 3

┌─explain─────────────────────────────────────┐
│ SelectWithUnionQuery (children 1) │
│ ExpressionList (children 1) │
│ SelectQuery (children 3) │
│ ExpressionList (children 1) │
Function sum (children 1) │ // sum 聚合
│ ExpressionList (children 1) │
│ Identifier number │
│ TablesInSelectQuery (children 1) │
│ TablesInSelectQueryElement (children 1) │
│ TableExpression (children 1) │
Function numbers (children 1) │
│ ExpressionList (children 1) │
│ Literal UInt64_10 │
│ ExpressionList (children 1) │
Function modulo (children 1) │ // number % 3 函数
│ ExpressionList (children 2) │
│ Identifier number │
│ Literal UInt64_3 │
└─────────────────────────────────────────────┘

2. 生成 Query Plan

1
2
3
4
5
6
7
8
9
10
11
12
EXPLAIN
SELECT sum(number)
FROM numbers(10)
GROUP BY number % 3

┌─explain───────────────────────────────────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │ // sum 聚合
│ Expression (Before GROUP BY) │ // number % 3
│ SettingQuotaAndLimits (Set limits and quota after reading from storage) │
│ ReadFromStorage (SystemNumbers) │
└───────────────────────────────────────────────────────────────────────────────┘

代码主要在 InterpreterSelectQuery::executeImpl@Interpreters/InterpreterSelectQuery.cpp

3. 生成 Pipeline

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
EXPLAIN PIPELINE
SELECT sum(number)
FROM numbers(10)
GROUP BY number % 3

┌─explain───────────────────────┐
│ (Expression) │
│ ExpressionTransform │
│ (Aggregating) │
│ AggregatingTransform │ // sum 计算
│ (Expression) │
│ ExpressionTransform │ // number % 3 计算
│ (SettingQuotaAndLimits) │
│ (ReadFromStorage) │
└───────────────────────────────┘

4. 执行 Pipeline

Pipeline 是从底部往上逐一执行。

4.1 ReadFromStorage

首先从 ReadFromStorage 执行,生成一个 block1, 数据如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
┌─number─┐
0
1
2
3
4
5
6
7
8
9
└────────┘
number类型为 UInt64

4.2 ExpressionTransform

ExpressionTransform 包含了 2 个 action:

  1. 名字为 number,type 为 INPUT
  2. 名字为 modulo(number, 3), type 为 FUNCTION

经过 ExpressionTransform 运行处理后生成一个新的 block2, 数据如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
┌─number─┬─modulo(number, 3)─┐
00
11
22
30
41
52
60
71
82
90
└────────┴───────────────────┘
number 类型为 UInt64
modulo(number, 3) 类型为 UInt8

代码主要在 ExpressionActions::execute@Interpreters/ExpressionActions.cpp

4.3 AggregatingTransform

AggregatingTransform 是 Group By 高性能的核心所在。
本示例中的 modulo(number, 3) 类型为 UInt8,在做优化上,ClickHouse 会选择使用数组代替 hashtable 作为分组,区分逻辑见 Interpreters/Aggregator.cpp

在计算 sum 的时候,首先会生成一个数组 [1024],然后做了一个编译展开(代码 addBatchLookupTable8@AggregateFunctions/IAggregateFunction.h):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static constexpr size_t UNROLL_COUNT = 4;
std::unique_ptr<Data[]> places{new Data[256 * UNROLL_COUNT]};
bool has_data[256 * UNROLL_COUNT]{}; /// Separate flags array to avoid heavy initialization.

size_t i = 0;

/// Aggregate data into different lookup tables.
size_t batch_size_unrolled = batch_size / UNROLL_COUNT * UNROLL_COUNT;
for (; i < batch_size_unrolled; i += UNROLL_COUNT)
{
for (size_t j = 0; j < UNROLL_COUNT; ++j)
{
size_t idx = j * 256 + key[i + j];
if (unlikely(!has_data[idx]))
{
new (&places[idx]) Data;
has_data[idx] = true;
}
func.add(reinterpret_cast<char *>(&places[idx]), columns, i + j, nullptr);
}
}

sum(number) … GROUP BY number % 3 计算方式:

1
2
3
array[0] = 0 + 3 + 6 + 9 = 18
array[1] = 1 + 4 + 7 = 12
array[2] = 2 + 5 + 8 = 15

这里只是针对 UInt8 做的一个优化分支,那么对于其他类型怎么优化处理呢?
ClickHouse 针对不同的类型分别提供了不同的 hashtable,声势比较浩大(代码见 Aggregator.h):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using AggregatedDataWithUInt8Key = FixedImplicitZeroHashMapWithCalculatedSize<UInt8, AggregateDataPtr>;
using AggregatedDataWithUInt16Key = FixedImplicitZeroHashMap<UInt16, AggregateDataPtr>;
using AggregatedDataWithUInt32Key = HashMap<UInt32, AggregateDataPtr, HashCRC32<UInt32>>;
using AggregatedDataWithUInt64Key = HashMap<UInt64, AggregateDataPtr, HashCRC32<UInt64>>;
using AggregatedDataWithShortStringKey = StringHashMap<AggregateDataPtr>;
using AggregatedDataWithStringKey = HashMapWithSavedHash<StringRef, AggregateDataPtr>;
using AggregatedDataWithKeys128 = HashMap<UInt128, AggregateDataPtr, UInt128HashCRC32>;
using AggregatedDataWithKeys256 = HashMap<DummyUInt256, AggregateDataPtr, UInt256HashCRC32>;
using AggregatedDataWithUInt32KeyTwoLevel = TwoLevelHashMap<UInt32, AggregateDataPtr, HashCRC32<UInt32>>;
using AggregatedDataWithUInt64KeyTwoLevel = TwoLevelHashMap<UInt64, AggregateDataPtr, HashCRC32<UInt64>>;
using AggregatedDataWithShortStringKeyTwoLevel = TwoLevelStringHashMap<AggregateDataPtr>;
using AggregatedDataWithStringKeyTwoLevel = TwoLevelHashMapWithSavedHash<StringRef, AggregateDataPtr>;
using AggregatedDataWithKeys128TwoLevel = TwoLevelHashMap<UInt128, AggregateDataPtr, UInt128HashCRC32>;
using AggregatedDataWithKeys256TwoLevel = TwoLevelHashMap<DummyUInt256, AggregateDataPtr, UInt256HashCRC32>;
using AggregatedDataWithUInt64KeyHash64 = HashMap<UInt64, AggregateDataPtr, DefaultHash<UInt64>>;
using AggregatedDataWithStringKeyHash64 = HashMapWithSavedHash<StringRef, AggregateDataPtr, StringRefHash64>;
using AggregatedDataWithKeys128Hash64 = HashMap<UInt128, AggregateDataPtr, UInt128Hash>;
using AggregatedDataWithKeys256Hash64 = HashMap<DummyUInt256, AggregateDataPtr, UInt256Hash>;

如果我们改成 GROUP BY number*100000 后,它会选择 AggregatedDataWithUInt64Key 的 hashtable 作为分组。

而且 ClickHouse 提供了一种 Two Level 方式,用语应对有大量分组 key 的情况,Level1 先分大组,Level2 小组可以并行计算。

针对 String 类型,根据不同的长度,hashtable 也做了很多优化,代码见 HashTable/StringHashMap.h

总结

ClickHouse 会根据 Group By 的最终类型,选择一个最优的 hashtable 或数组,作为分组基础数据结构,使内存和计算尽量最优。

这个”最优解“是怎么找到的?从 test 代码可以看出,是不停的尝试、测试验证出来的,浓厚的 bottom-up 哲学范。

hashtable 测试代码:Interpreters/tests

lookuptable 测试代码: tests/average.cpp


欢迎关注我的微信公众号【数据库内核】:分享主流开源数据库和存储引擎相关技术。

欢迎关注公众号数据库内核
标题 网址
GitHub https://dbkernel.github.io
知乎 https://www.zhihu.com/people/dbkernel/posts
思否(SegmentFault) https://segmentfault.com/u/dbkernel
掘金 https://juejin.im/user/5e9d3ed251882538083fed1f/posts
CSDN https://blog.csdn.net/dbkernel
博客园(cnblogs) https://www.cnblogs.com/dbkernel
文章目录
  1. 1. 一条 SQL
  2. 2. 1. 生成 AST
  3. 3. 2. 生成 Query Plan
  4. 4. 3. 生成 Pipeline
  5. 5. 4. 执行 Pipeline
    1. 5.1. 4.1 ReadFromStorage
    2. 5.2. 4.2 ExpressionTransform
    3. 5.3. 4.3 AggregatingTransform
  6. 6. 总结
|