ClickHouse索引采用唯一聚簇索引的方式，即Part內(nèi)數(shù)據(jù)按照order by keys有序，在整個(gè)查詢計(jì)劃中，如果算子能夠有效利用輸入數(shù)據(jù)的有序性，對(duì)算子的執(zhí)行性能將有巨大的提升。本文討論ClickHouse基于索引的查詢算子優(yōu)化方式。

在整個(gè)查詢計(jì)劃中Sort、Distinct、聚合這3個(gè)算子相比其他算子比如：過(guò)濾、projection等有如下幾個(gè)特點(diǎn)：1.算子需要再內(nèi)存中保存狀態(tài)，內(nèi)存代價(jià)高；2.算子計(jì)算代價(jià)高；3.算子會(huì)阻斷執(zhí)行pipeline，待所有數(shù)據(jù)計(jì)算完整后才會(huì)向下游輸出數(shù)據(jù)。所以上算子往往是整個(gè)查詢的瓶頸算子。

本文詳細(xì)討論，3個(gè)算子基于索引的查詢優(yōu)化前后，在計(jì)算、內(nèi)存和pipeline阻斷上的影響。

實(shí)驗(yàn)前準(zhǔn)備：

后續(xù)的討論主要基于實(shí)驗(yàn)進(jìn)行。

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

表中總共有3個(gè)part，每個(gè)part數(shù)據(jù)量4條。

PS： 用戶可以在插入數(shù)據(jù)前提前關(guān)閉后臺(tái)merge，以避免part合并成一個(gè)，如果part合并成一個(gè)將影響查詢并行度，可能對(duì)實(shí)驗(yàn)有影響，以下查詢可以關(guān)閉后臺(tái)merge：system stop merges test_in_order

一、Sort算子

如果order by查詢的order by字段與表的order by keys的前綴列匹配，那么可以根據(jù)數(shù)據(jù)的有序特性對(duì)Sort算子進(jìn)行優(yōu)化。

1.Sort算子實(shí)現(xiàn)方式

首先看下不能利用主鍵有序性的場(chǎng)景，即對(duì)于order by查詢的order by字段與表的order by keys的前綴列不匹配。比如下面的查詢：

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

它的執(zhí)行計(jì)劃如下：

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

排序算法由3個(gè)Transform組成，其中

1）PartialSortingTransform對(duì)單個(gè)Chunk進(jìn)行排序；

2）MergeSortingTransform對(duì)單個(gè)stream進(jìn)行排序；

3）MergingSortedTransform合并多個(gè)有序的stream進(jìn)行全局sort-merge排序

如果查詢的order by字段與表的order by keys的前綴列匹配，那么可以根據(jù)數(shù)據(jù)的有序特性對(duì)查詢進(jìn)行優(yōu)化，優(yōu)化開(kāi)關(guān)：optimize_read_in_order。

2.匹配索引列的查詢

以下查詢的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 -- 關(guān)閉read_in_order優(yōu)化

查看order by語(yǔ)句的pipeline執(zhí)行計(jì)劃

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

此時(shí)order by算子的算法

1）首先MergeSortingTransform對(duì)輸入的stream進(jìn)行排序

2）然后MergingSortedTransform將多個(gè)排好序的stream進(jìn)行合并，并輸出一個(gè)整體有序的stream，也是最終的排序結(jié)果。

這里有個(gè)疑問(wèn)在關(guān)閉read_in_order優(yōu)化的查詢計(jì)劃中，系統(tǒng)直接默認(rèn)了MergeSortingTransform的輸入在Chunk內(nèi)是有序的，這里其實(shí)是一個(gè)默認(rèn)優(yōu)化，因?yàn)閛rder by查詢的order by字段與表的order by keys的前綴列匹配，所以數(shù)據(jù)在Chunk內(nèi)部一定是有序的。

3. 開(kāi)啟優(yōu)化optimize_read_in_order

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

4. 優(yōu)化分析

打開(kāi)optimize_read_in_order后：

1.對(duì)于計(jì)算方面：算法中只有一個(gè)MergingSortedTransform，省略了單個(gè)stream內(nèi)排序的步驟

2.由于內(nèi)存方面：由于MergeSortingTransform是消耗內(nèi)存最大的步驟，所以優(yōu)化后可以節(jié)約大量的內(nèi)存

3.對(duì)于poipeline阻塞：MergeSortingTransform會(huì)阻塞整個(gè)pipeline，所以優(yōu)化后也消除了對(duì)pipeline的阻塞

二、Distinct算子

如果distinct查詢的distinct字段與表的order by keys的前綴列匹配，那么可以根據(jù)數(shù)據(jù)的有序特性對(duì)Distinct算子進(jìn)行優(yōu)化，優(yōu)化開(kāi)關(guān)：optimize_distinct_in_order。通過(guò)以下實(shí)驗(yàn)進(jìn)行說(shuō)明：

1. Distinct算子實(shí)現(xiàn)方式

查看distinct語(yǔ)句的pipeline執(zhí)行計(jì)劃

query_2: EXPLAIN PIPELINE SELECT DISTINCT * FROM woo.test_in_order SETTINGS optimize_distinct_in_order = 0 -- 關(guān)閉distinct in order優(yōu)化

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

Distinct算子采用兩階段的方式，首先第一個(gè)DistinctTransform在內(nèi)部進(jìn)行初步distinct，其并行度為3，可以簡(jiǎn)單的認(rèn)為有3個(gè)線程在同時(shí)執(zhí)行。然后第二個(gè)DistinctTransform進(jìn)行final distinct。

每個(gè)DistinctTransform的計(jì)算方式為：首先構(gòu)建一個(gè)HashSet數(shù)據(jù)結(jié)構(gòu)，然后根據(jù)HashSet，構(gòu)建一個(gè)Filter Mask（如果當(dāng)前key存在于HashSet中，則過(guò)濾掉），最后過(guò)濾掉不需要的數(shù)據(jù)。

2.開(kāi)啟優(yōu)化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，DistinctSortedChunkTransform和DistinctTransform。

DistinctSortedChunkTransform：對(duì)單個(gè)stream內(nèi)的數(shù)據(jù)進(jìn)行distinct操作，因?yàn)閐istinct列跟表的order by keys的前綴列匹配，scan算子讀取數(shù)據(jù)的時(shí)候一個(gè)stream只從一個(gè)part內(nèi)讀取數(shù)據(jù)，那么每個(gè)distinct transform輸入的數(shù)據(jù)就是有序的。所以distinct算法有：

DistinctSortedChunkTransform算法一：

Transform中保留最后一個(gè)輸入的數(shù)據(jù)作為狀態(tài)，對(duì)于每個(gè)輸入的新數(shù)據(jù)如果跟保留的狀態(tài)相同，那么忽略，如果不同則將上一個(gè)狀態(tài)輸出給上一個(gè)算子，然后保留當(dāng)前的數(shù)據(jù)最為狀態(tài)。這種算法對(duì)于在整個(gè)stream內(nèi)部全局去重時(shí)間和空間復(fù)雜度都有極大的降低。

DistinctSortedStreamTransform算法二：(ClickHouse采用的)

Transform對(duì)與每個(gè)Chunk（ClickHouse中Transform數(shù)據(jù)處理的基本單位，默認(rèn)大約6.5w行），首先將相同的數(shù)據(jù)劃分成多個(gè)Range，并設(shè)置一個(gè)mask數(shù)組，然后將相同的數(shù)據(jù)刪除掉，最后返回刪除重復(fù)數(shù)據(jù)的Chunk。

3. 優(yōu)化分析

打開(kāi)optimize_distinct_in_order后：主要對(duì)于第一階段的distinct步驟進(jìn)行了優(yōu)化，從基于HashSet過(guò)濾的算法到基于連續(xù)相同值的算法。

1.對(duì)于計(jì)算方面：優(yōu)化后的算法，省去了Hash計(jì)算，但多了判斷相等的步驟，在不同數(shù)據(jù)基數(shù)集大小下，各有優(yōu)劣。

2.由于內(nèi)存方面：優(yōu)化后的算法，不需要存儲(chǔ)HashSet

3.對(duì)于poipeline阻塞：優(yōu)化前后都不會(huì)阻塞pipeline

三、聚合算子

如果group by查詢的order by字段與表的order by keys的前綴列匹配，那么可以根據(jù)數(shù)據(jù)的有序特性對(duì)聚合算子進(jìn)行優(yōu)化，優(yōu)化開(kāi)關(guān)：optimize_aggregation_in_order。

1.聚合算子實(shí)現(xiàn)方式

查看group by語(yǔ)句的pipeline執(zhí)行計(jì)劃：

query_4: EXPLAIN PIPELINE SELECT a FROM test_in_order GROUP BY a SETTINGS optimize_aggregation_in_order = 0 -- 關(guān)閉read_in_order優(yōu)化

┌─explain─────────────────────────────┐
│ (Expression)                        │
│ ExpressionTransform × 8             │
│   (Aggregating)                     │
│   Resize 3 → 8                      │
│     AggregatingTransform × 3        │
│       StrictResize 3 → 3            │
│         (Expression)                │
│         ExpressionTransform × 3     │
│           (ReadFromMergeTree)       │
│           MergeTreeThread × 3 0 → 1 │
└─────────────────────────────────────┘

對(duì)于聚合算子的整體算法沒(méi)有在執(zhí)行計(jì)劃中完整顯示出來(lái)，其宏觀上采用兩階段的聚合算法，其完整算法如下：1.AggregatingTransform進(jìn)行初步聚合，這一步可以并行計(jì)算；2.ConvertingAggregatedToChunksTransform進(jìn)行第二階段聚合。（PS：為簡(jiǎn)化起見(jiàn)，忽略two level HashMap，和spill to disk的介紹）。

2.開(kāi)啟優(yōu)化optimize_aggregation_in_order

執(zhí)行計(jì)劃如下：

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

可以看到打開(kāi)optimize_aggregation_in_order后aggregating算法由三個(gè)步驟組成：

1）首先AggregatingInOrderTransform會(huì)將stream內(nèi)連續(xù)的相同的key進(jìn)行預(yù)聚合，預(yù)聚合后在當(dāng)前stream內(nèi)相同keys的數(shù)據(jù)只會(huì)有一條；

2）FinishAggregatingInOrderTransform將接收到的多個(gè)stream內(nèi)的數(shù)據(jù)進(jìn)行重新分組使得輸出的chunk間數(shù)據(jù)是有序的，假設(shè)前一個(gè)chunk中g(shù)roup by keys最大的一條數(shù)據(jù)是5，當(dāng)前即將輸出的chunk中沒(méi)有大于5的數(shù)據(jù)；

3）MergingAggregatedBucketTransform的作用是進(jìn)行最終的merge aggregating。

FinishAggregatingInOrderTransform的分組算法如下：

假設(shè)有3個(gè)stream當(dāng)前算子會(huì)維護(hù)3個(gè)Chunk，每一次選取在當(dāng)前的3個(gè)Chunk內(nèi)找到最后一條數(shù)據(jù)的最小值，比如初始狀態(tài)最小值是5，然后將3個(gè)Chunk內(nèi)所有小于5的數(shù)據(jù)一次性取走，如此反復(fù)如果一個(gè)Chunk被取光，需要從改stream內(nèi)拉取新的Chunk。

這種算法保證了每次FinishAggregatingInOrderTransform向下游輸出的Chunk的最大值小于下一次Chunk的最小值，便于后續(xù)步驟的優(yōu)化。

3.優(yōu)化分析

打開(kāi)optimize_aggregation_in_order后：主要對(duì)于第一階段的聚合步驟進(jìn)行了優(yōu)化，從基于HashMap的算法到基于連續(xù)相同值的算法。

1.對(duì)于計(jì)算方面：優(yōu)化后的算法，減少了Hash計(jì)算，但多了判斷相等的步驟，在不同數(shù)據(jù)基數(shù)集大小下，各有優(yōu)劣。

2.由于內(nèi)存方面：優(yōu)化前后無(wú)差別

3.對(duì)于poipeline阻塞：優(yōu)化前后無(wú)差別

四、優(yōu)化小結(jié)

在整個(gè)查詢計(jì)劃中Sort、Distinct、聚合這3個(gè)算子算子往往是整個(gè)查詢的瓶頸算子，所以值得對(duì)其進(jìn)行深度優(yōu)化。ClickHouse通過(guò)利用算子輸入數(shù)據(jù)的有序性，優(yōu)化算子的算法或者選擇不同的算法，在計(jì)算、內(nèi)存和pipeline阻塞三個(gè)方面均有不同程度的優(yōu)化。

審核編輯 黃宇