分类
uncategorized

ClickHouse内幕(6)基于索引的查询优化

ClickHouse索引采用唯一聚簇索引的方式,即Part内数据按照order by keys有序,本文讨论ClickHouse基于有序性的查询算子优化方式。

实验前准备:

后续的讨论主要基于实验进行。

CREATE TABLE test_in_order
(
    `a` UInt64,
    `b` UInt64,
    `c` UInt64,
    `d` UInt64
)
ENGINE = MergeTree
ORDER BY (a, b);

表中总共有3个part,每个part数据量4条。

PS: 用户可以在插入数据前提前关闭后台merge,以避免part合并成一个,如果part合并成一个将影响查询并行度,可能对实验有影响,以下查询可以关闭后台merge:system stop merges test_in_order

一、Sort算子(read_in_order)

如果order by查询的order by字段与表的order by keys的前缀列匹配,那么可以根据数据的有序特性对查询进行优化。

1.Sort算子的执行流程

首先看下对于order by查询的order by字段与表的order by keys的前缀列不匹配的场景order by如何执行,比如下面的查询:

query_1: EXPLAIN PIPELINE SELECT b FROM read_in_order ORDER BY b ASC

它的执行计划如下:

┌─explain───────────────────────────────┐
│ (Expression)                          │
│ ExpressionTransform                   │
│   (Sorting)                           │
│   MergingSortedTransform 3 → 1        │
│     MergeSortingTransform × 3         │
│       LimitsCheckingTransform × 3     │
│         PartialSortingTransform × 3   │
│           (Expression)                │
│           ExpressionTransform × 3     │
│             (ReadFromMergeTree)       │
│             MergeTreeThread × 3 0 → 1 │
└───────────────────────────────────────┘

排序算法由3个Transform组成,其中

1)PartialSortingTransform对单个Chunk进行排序;

2)MergeSortingTransform对单个stream进行排序;

3)MergingSortedTransform合并多个有序的stream进行全局sort-merge排序

如果查询的order by字段与表的order by keys的前缀列匹配,那么可以根据数据的有序特性对查询进行优化,优化开关:optimize_read_in_order

2.关闭optimize_read_in_order

以下查询的order by字段与表的order by keys的前缀列匹配

query_3: EXPLAIN PIPELINE SELECT b FROM test_in_order ORDER BY a ASC, b ASCSETTINGS optimize_read_in_order = 0 -- 关闭read_in_order优化

查看order by语句的pipeline执行计划

┌─explain───────────────────────────┐
│ (Expression)                      │
│ ExpressionTransform               │
│   (Sorting)                       │
│   MergingSortedTransform 3 → 1    │
│     MergeSortingTransform × 3     │
│       (Expression)                │
│       ExpressionTransform × 3     │
│         (ReadFromMergeTree)       │
│         MergeTreeThread × 3 0 → 1 │
└───────────────────────────────────┘

此时order by算子的算法

1)首先MergeSortingTransform对输入的stream进行排序

2)然后MergingSortedTransform将多个排好序的stream进行合并,并输出一个整体有序的stream,也是最终的排序结果。

这里有个疑问在关闭read_in_order优化的查询计划中,系统直接默认了MergeSortingTransform的输入在Chunk内是有序的,这里其实是一个默认优化,因为order by查询的order by字段与表的order by keys的前缀列匹配,所以数据在Chunk内部一定是有序的。

3. 打开optimize_read_in_order

┌─explain──────────────────────────┐
│ (Expression)                     │
│ ExpressionTransform              │
│   (Sorting)                      │
│   MergingSortedTransform 3 → 1   │
│     (Expression)                 │
│     ExpressionTransform × 3      │
│       (ReadFromMergeTree)        │
│       MergeTreeInOrder × 3 0 → 1 │
└──────────────────────────────────┘

可以看到打开optimize_read_in_order后,算法中只有一个MergingSortedTransform,省略了单个stream内排序的步骤,对于排序查询来说省略了大部分的计算,对查询性能提升有很大帮助。

二、Distinct算子(distinct_in_order)

如果distinct查询的distinct字段与表的order by keys的前缀列匹配,那么可以根据数据的有序特性对查询进行优化,优化开关:optimize_distinct_in_order。通过以下实验进行说明:

1. 关闭optimize_distinct_in_order

查看distinct语句的pipeline执行计划

query_2: EXPLAIN PIPELINE SELECT DISTINCT * FROM woo.test_in_order SETTINGS optimize_distinct_in_order = 0 -- 关闭distinct in order优化
┌─explain─────────────────────────────┐
│ (Expression)                        │
│ ExpressionTransform                 │
│   (Distinct)                        │
│   DistinctTransform                 │
│     Resize 3 → 1                    │
│       (Distinct)                    │
│       DistinctTransform × 3         │
│         (Expression)                │
│         ExpressionTransform × 3     │
│           (ReadFromMergeTree)       │
│           MergeTreeThread × 3 0 → 1 │
└─────────────────────────────────────┘

可以看到最底层的SCAN有2个processor,上层的distinct操作被分成了两个阶段,首先在processor内部进行初步distinct,然后进行final distinct,合并两个processor的数据,整体上到采用了两阶段的distinct计算方法。

2.打开optimize_distinct_in_order

┌─explain────────────────────────────────┐
│ (Expression)                           │
│ ExpressionTransform                    │
│   (Distinct)                           │
│   DistinctTransform                    │
│     Resize 3 → 1                       │
│       (Distinct)                       │
│       DistinctSortedChunkTransform × 3 │
│         (Expression)                   │
│         ExpressionTransform × 3        │
│           (ReadFromMergeTree)          │
│           MergeTreeThread × 3 0 → 1    │
└────────────────────────────────────────┘

可以看到初步distinct和final distinct采用了不同的transform,DistinctSortedStreamTransformDistinctTransform

DistinctSortedStreamTransform:对单个stream内的数据进行distinct操作,因为distinct列跟表的order by keys的前缀列匹配,scan算子读取数据的时候一个stream只从一个part内读取数据,那么每个distinct transform输入的数据就是有序的。所以distinct算法有:

DistinctSortedStreamTransform算法一:

Transform中保留最后一个输入的数据作为状态,对于每个输入的新数据如果跟保留的状态相同,那么忽略,如果不同则将上一个状态输出给上一个算子,然后保留当前的数据最为状态。这种算法对于在整个stream内部全局去重时间和空间复杂度都有极大的降低。

DistinctSortedStreamTransform算法二:(ClickHouse采用的)

Transform对与每个Chunk(ClickHouse中Transform数据处理的基本单位,默认大约6.5w行),首先将相同的数据划分成多个Range,并设置一个mask数组,然后将相同的数据删除掉,最后返回删除重复数据的Chunk。

三、聚合算子(aggregation_in_order)

如果group by查询的order by字段与表的order by keys的前缀列匹配,那么可以根据数据的有序特性对查询进行优化,优化开关:optimize_aggregation_in_order

1.关闭optimize_aggregation_in_order

查看group by语句的pipeline执行计划:

query_4: EXPLAIN PIPELINE SELECT a FROM test_in_order GROUP BY a SETTINGS optimize_aggregation_in_order = 0 -- 关闭read_in_order优化
┌─explain─────────────────────────────┐
│ (Expression)                        │
│ ExpressionTransform × 8             │
│   (Aggregating)                     │
│   Resize 3 → 8                      │
│     AggregatingTransform × 3        │
│       StrictResize 3 → 3            │
│         (Expression)                │
│         ExpressionTransform × 3     │
│           (ReadFromMergeTree)       │
│           MergeTreeThread × 3 0 → 1 │
└─────────────────────────────────────┘

2.打开optimize_aggregation_in_order

执行计划如下:

┌─explain───────────────────────────────────────┐
│ (Expression)                                  │
│ ExpressionTransform × 8                       │
│   (Aggregating)                               │
│   MergingAggregatedBucketTransform × 8        │
│     Resize 1 → 8                              │
│       FinishAggregatingInOrderTransform 3 → 1 │
│         AggregatingInOrderTransform × 3       │
│           (Expression)                        │
│           ExpressionTransform × 3             │
│             (ReadFromMergeTree)               │
│             MergeTreeInOrder × 3 0 → 1        │
└───────────────────────────────────────────────┘

可以看到打开optimize_aggregation_in_order后aggregating算法由三个步骤组成:

1)首先AggregatingInOrderTransform会将stream内连续的相同的key进行预聚合,预聚合后在当前stream内相同keys的数据只会有一条;

2)FinishAggregatingInOrderTransform将接收到的多个stream内的数据进行重新分组使得输出的chunk间数据是有序的,假设前一个chunk中group by keys最大的一条数据是5,当前即将输出的chunk中没有大于5的数据;

3)MergingAggregatedBucketTransform的作用是进行最终的merge aggregating。

FinishAggregatingInOrderTransform的分组算法如下:

假设有3个stream当前算子会维护3个Chunk,每一次选取在当前的3个Chunk内找到最后一条数据的最小值,比如初始状态最小值是5,然后将3个Chunk内所有小于5的数据一次性取走,如此反复如果一个Chunk被取光,需要从改stream内拉取新的Chunk。

这种算法保证了FinishAggregatingInOrderTransform每次向下游输出的Chunk的最大值小于下一次Chunk的最小值,便于后续步骤的优化。

版权声明:文章为作者辛勤劳动的成果,转载请注明作者与出处。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注