引言

阿里雲資料庫ClickHouse二級索引功能近日已正式釋出上線，主要彌補了ClickHouse在海量資料分析場景下，多維度點查能力不足的短板。在以往服務使用者的過程中，作者發現絕大部分使用者對ClickHouse單表查詢效能最佳化問題感到無從下手，藉此機會，本文會先為大家展開介紹ClickHouse在單表分析查詢效能最佳化上的幾個方法，基本涵蓋了OLAP領域儲存層掃描加速的所有常用手段。在解決過各種各樣業務場景下的效能最佳化問題後，作者發現目前ClickHouse在解決多維搜尋問題上確實能力不足，一條點查常常浪費巨大的IO、CPU資源，於是雲資料庫ClickHouse自研了二級索引功能來徹底解決問題，本文會詳細介紹二級索引的DDL語法、幾個典型適用場景和特色功能。希望可以透過本文讓大家對ClickHouse在OLAP場景下的能力有更深的理解，同時闡述清楚二級索引適用的搜尋場景。

儲存掃描效能最佳化

在介紹各類OLAP儲存掃描效能最佳化技術之前，作者先在這裡申明一個簡單的代價模型和一些OLAP的背景知識。本文使用最簡單的代價模型來計算OLAP儲存掃描階段的開銷：磁碟掃描讀取的資料量。在類似ClickHouse這樣純列式的儲存和計算引擎中，資料的壓縮、計算、流轉都是以列塊為單位按列進行的。在ClickHouse中，只能對資料列以塊為單位進行定位讀取，雖然使用者的查詢是按照uid查詢確定的某一條記錄，但是從磁碟讀取的資料量會被放大成塊大小 * 列數。本文中不考慮資料快取(BlockCache / PageCache)這些最佳化因素，因為Cache可以達到的最佳化效果不是穩定的。

排序鍵最佳化-跳躍掃描

排序鍵是ClickHouse最主要依賴的儲存掃描加速技術，它的含義是讓儲存層每個DataPart裡的資料按照排序鍵進行嚴格有序儲存。正是這種有序儲存的模式，構成了ClickHouse "跳躍"掃描的基礎和重複資料高壓縮比的能力（對於ClickHouse的MergeTree儲存結構不熟悉的同學可以參考往期文章《ClickHouse核心分析-MergeTree的儲存結構和查詢加速》）。

CREATE TABLE order_info(    `oid`   UInt64,                     --訂單ID    `buyer_nick`    String,     --買家ID    `seller_nick`   String,     --店鋪ID    `payment`   Decimal64(4), --訂單金額    `order_status`  UInt8,         --訂單狀態    ...    `gmt_order_create`  DateTime, --下單時間    `gmt_order_pay` DateTime,         --付款時間    `gmt_update_time` DateTime,     --記錄變更時間    INDEX oid_idx (oid) TYPE minmax GRANULARITY 32)ENGINE = MergeTree()PARTITION BY toYYYYMMDD(gmt_order_create)         --以天為單位分割槽ORDER BY (seller_nick, gmt_order_create, oid) --排序鍵PRIMARY KEY (seller_nick, gmt_order_create)     --主鍵SETTINGS index_granularity = 8192;

以一個簡單的訂單業務場景為例（表結構如上），order by定義了資料檔案中的記錄會按照店鋪ID , 下單時間以及訂單號組合排序鍵進行絕對有序儲存，而primary key和index_granularity兩者則定義了排序鍵上的索引結構長什麼樣子，ClickHouse為每一個有序的資料檔案構造了一個"跳躍陣列"作為索引，這個"跳躍陣列"中的記錄是從原資料中按一定間隔抽取出來得到的（簡化理解就是每隔index_granularity抽取一行記錄），同時只保留primary key定義裡的seller_nick, gmt_order_create兩個字首列。如下圖所示，有了這個全記憶體的"跳躍陣列"作為索引，最佳化器可以快速排除掉和查詢無關的行號區間，大大減少磁碟掃描的資料量。至於為何不把oid列放到primary key中，讀者可以仔細思考一下原因，和index_granularity設定值大小也有關。

作者碰到過很多使用者在把mysql的binlog資料遷移到ClickHouse上做分析時，照搬照抄mysql上的主鍵定義，導致ClickHouse的排序鍵索引基本沒有發揮出任何作用，查詢效能主要就是靠ClickHouse牛逼的資料並行掃描能力和高效的列式計算引擎在硬抗，這也從側面反應出ClickHouse在OLAP場景下的絕對效能優勢，沒有任何索引依舊可以很快。業務系統中的mysql主要側重單條記錄的事務更新，主鍵是可以簡單明瞭定義成oid，但是在OLAP場景下查詢都需要做大資料量的掃描分析，ClickHouse需要用排序鍵索引來進行"跳躍"掃描，使用者建表時應儘量把業務記錄生命週期中不變的欄位都放入排序鍵(一般distinct count越小的列放在越前)。

分割槽鍵最佳化-MinMax裁剪

繼續上一節中的業務場景，當業務需要查詢某一段時間內所有店鋪的全部訂單量時，primary key中定義的"跳躍"陣列索引效用就不那麼明顯了，查詢如下：

select count(*) from order_info where gmt_order_create > '2020-0802 00:00:00' and gmt_order_create < '2020-0804 15:00:00'

ClickHouse中的primary key索引有一個致命問題是，當前綴列的離散度(distinct value count)非常大時，在後續列上的過濾條件起到的"跳躍"加速作用就很微弱了。這個其實很好理解，當"跳躍陣列"中相鄰的兩個元組是('a', 1)和('a', 10086)時，我們可以推斷出第二列在對應的行號區間內值域是[1, 10086]；若相鄰的元素是('a', 1)和('b', 10086)，則第二列的值域範圍就變成(-inf, +inf)了，無法依據第二列的過濾條件進行跳過。

這時候就需要用到partition by優化了，ClickHouse中不同分割槽的資料是在物理上隔離開的，同時在資料生命管理上也是獨立的。partition by就好像是多個DataPart檔案集合(資料分割槽)之間的"有序狀態"，而上一節中的order by則是單個DataPart檔案內部記錄的"有序狀態"。每一個DataPart檔案只屬於一個數據分割槽，同時在記憶體裡保有partition by列的MinMax值記錄。上述查詢case中，最佳化器根據每個DataPart的gmt_order_create最大值最小值可以快速裁剪掉不相關的DataPart，這中裁剪方式對資料的篩選效率比排序鍵索引更高。

這裡教大家一個小技巧，如果業務方既要根據下單時間範圍聚合分析，又要根據付款時間範圍聚合分析，該如何設計分割槽鍵呢？像這類有業務相關性的兩個時間列，同時時間差距上又是有業務約束的情況下，我們可以把partition by定義成：

(toYYYYMMDD(gmt_order_create), (gmt_order_pay - gmt_order_create)/3600/240)

這樣一來DataPart在gmt_order_create和gmt_order_pay兩列上就都有了MinMax裁剪索引。在設計資料分割槽時，大家需要注意兩點：

1）partition by會對DataPart起到物理隔離，所以資料分割槽過細的情況下會導致底層的DataPart數量膨脹，一定程度影響那種大範圍的查詢效能，要控制partition by的粒度；

2）partition by和order by都是讓資料存放達到"有序狀態"的技術，定義的時候應當儘量錯開使用不同的列來定義兩者，order by的第一個列一定不要重複放到partition by裡，一般來說時間列更適合放在partition by上。

Skipping index最佳化-MetaScan

在ClickHouse開源版本里，使用者就可以透過自定義index來加速分析查詢。但是實際使用中，絕大部分使用者都不理解這個文件上寫的"skipping index"是個什麼原理？為什麼建立index之後查詢一點都沒有變快或者反而變慢了？？？因為"skipping index"並不是真正意義上的索引，正常的索引都是讓資料按照索引key進行聚集，或者把行號按照索引key聚集起來。而ClickHouse的"skipping index"並不會做任何聚集的事情，它只是加速篩選Block的一種手段。以 INDEX oid_idx (oid) TYPE minmax GRANULARITY 32 這個索引定義為例，它會對oid列的每32個列存塊做一個minmax值統計，統計結果存放在單獨的索引檔案裡。下面的查詢在沒有oid skipping index的情況下，至少需要掃描5天的資料檔案，才能找到對應的oid行。有了索引後，資料掃描的邏輯變成了先掃描oid索引檔案，檢查oid的minmax區間是否覆蓋目標值，後續掃描主表的時候可以跳過不相關的Block，這其實就是在OLAP裡常用的Block Meta Scan技術。

select *from order_info where gmt_order_create > '2020-0802 00:00:00' and gmt_order_create < '2020-0807 00:00:00'and oid = 726495;

當oid列存塊的minmax區間都很大時，這個skipping index就無法起到加速作用，甚至會讓查詢更慢。實際在這個業務場景下oid的skipping idex是有作用的。上一節講過在同一個DataPart內資料主要是按照店鋪ID和下單時間進行排序，所有在同一個DataPart內的oid列存塊minmax區間基本都是重疊的。但是ClickHouse的MergeTree還有一個隱含的有序狀態：那就是同一個partition下的多個DataPart是處於按寫入時間排列的有序狀態，而業務系統裡的oid是一個自增序列，剛好寫入ClickHouse的資料oid基本也是按照時間遞增的趨勢，不同DataPart之間的oid列存塊minmax就基本是錯開的。

不難理解，skipping index對查詢的加速效果是一個常數級別的，索引掃描的時間是和資料量成正比的。除了minmax型別的skipping index，還有set型別索引，它適用的場景也是要求列值隨著寫入時間有明顯區域性性。剩下的bloom_filter、ngrambf_v1、tokenbf_v1則是透過把完整的字串列或者字串列分詞後的token用bloom_filter生成高壓縮比的簽名來進行排除Block，在長字串的場景下有一定加速空間。

Prewhere最佳化-兩階段掃描

前面三節講到的所有效能最佳化技術基本都是依賴資料的"有序性"來加速掃描滿足條件的Block，這也意味著滿足查詢條件的資料本身就是存在某種"區域性性"的。正常的業務場景中只要滿足條件的資料本身存在"區域性性"就一定能透過上面的三種方法來加速查詢。在設計業務系統時，我們甚至應該刻意去創造出更多的"區域性性"，例如本文例子中的oid如果是設計成"toYYYYMMDDhh(gmt_order_create)+店鋪ID+遞增序列"，那就可以在DataPart內部篩選上獲得"區域性性"，查詢會更快，讀者們可以深入思考下這個問題。

在OLAP場景下最難搞定的問題就是滿足查詢條件的資料沒有任何"區域性性"：查詢條件命中的資料可能性數不多，但是分佈非常散亂，每一個列存塊中都有一兩條記錄滿足條件。這種情況下因為列式儲存的關係，只要塊中有一條記錄命中系統就需要讀取完整的塊，最後幾百上千倍的資料量需要從磁碟中讀取。當然這是個極端情況，很多時候情況是一部分列存塊中沒有滿足條件的記錄，一部分列存塊中包含少量滿足條件的記錄，整體呈現隨機無序。這種場景下當然可以對查詢條件列加上類似lucene的倒排索引快速定位到命中記錄的行號集合，但索引是有額外儲存、構建成本的，更好的方法是採用兩階段掃描來加速。

以下面的查詢為例，正常的執行邏輯中儲存層掃描會把5天內的全部列資料從磁碟讀取出來，然後計算引擎再按照order_status列過濾出滿足條件的行。在兩階段掃描的框架下，prewhere表示式會下推到儲存掃描過程中執行，優先掃描出order_status列存塊，檢查是否有記錄滿足條件，再把滿足條件行的其他列讀取出來，當沒有任何記錄滿足條件時，其他列的塊資料就可以跳過不讀了。

--常規select *from order_info wherewhere order_status = 2 --訂單取消and gmt_order_create > '2020-0802 00:00:00' and gmt_order_create < '2020-0807 00:00:00'；--兩階段掃描select *from order_info whereprewhere order_status = 2 --訂單取消where gmt_order_create > '2020-0802 00:00:00' and gmt_order_create < '2020-0807 00:00:00'；

這種兩階段掃描的思想就是優先掃描篩選率高的列進行過濾，再按需掃描其他列的塊。在OLAP幾百列的大寬表分析場景下，這種加速方式減少的IO效果是非常明顯的。但是瓶頸也是確定的，至少需要把某個單列的資料全部掃描出來。目前大家在使用prewhere加速的時候最好是根據資料分佈情況來挑選最有篩選率同時掃描資料量最少的過濾條件。當遇上那種每個Block中都有一兩條記錄滿足查詢條件的極端情況時，嘗試使用ClickHouse的物化檢視來解決吧。物化檢視的作用不光是預聚合計算，也可以讓資料換個排序鍵重新有序儲存一份。還有一種zorder的技術也能緩解一部分此類問題，有興趣的同學可以自己瞭解一下。

小結

前面四節分別介紹了ClickHouse中四種不同的查詢加速技術，當滿足查詢條件的資料有明顯的"區域性性"時，大家可以透過前三種低成本的手段來加速查詢。最後介紹了針對資料分佈非常散亂的場景下，prewhere可以緩解多列分析的IO壓力。實際上這四種最佳化手段都是可以結合使用的，本文拆開闡述只是為了方便大家理解它們的本質。延續上一節的問題，當資料分佈非常散亂，同時查詢命中的記錄又只有若干條的場景下，就算使用prewhere進行兩階段掃描，它的IO放大問題也依舊是非常明顯的。簡單的例子就是查詢某個特定買家id(buyer_nick)的購買記錄，買家id在資料表中的分佈是完全散亂的，同時買家id列全表掃描的代價過大。所以阿里雲ClickHouse推出了二級索引功能，專門來解決這種少量結果的搜尋問題。這裡如何定義結果的少呢？一般列存系統中一個列存塊包括接近10000行記錄，當滿足搜尋條件的記錄數比列存塊小一個數量級時(篩選率超過100000:1)，二級索引才能發揮比較明顯的效能優勢。

二級索引多維搜尋

ClickHouse的二級索引在設計的時候對標的就是ElasticSearch的多維搜尋能力，支援多索引列條件交併差檢索。同時對比ElasticSearch又有更貼近ClickHouse的易用性最佳化，總體特點概括如下：

多列聯合索引 & 表示式索引函式下推In Set Clause下推多值索引 & 字典索引高壓縮比 1:1 vs lucene 8.7向量化構建 4X vs lucene 8.7

常規索引

二級索引在建立表時的定義語句示例如下：

CREATE TABLE index_test (  id UInt64,   d DateTime,   x UInt64,  y UInt64,   tag String,  KEY tag_idx tag TYPE range, --單列索引  KEY d_idx toStartOfHour(d) TYPE range, --表示式索引  KEY combo_idx (toStartOfHour(d)，x, y) TYPE range, --多列聯合索引) ENGINE = MergeTree() ORDER BY id;

其他二級索引相關的修改DDL如下：

--刪除索引定義Alter table index_test DROP KEY tag_idx;--增加索引定義Alter table index_test ADD KEY tag_idx tag TYPE range;--清除資料分割槽下的索引檔案Alter table index_test CLEAR KEY tag_idx tag in partition partition_expr;--重新構建資料分割槽下的索引檔案Alter table index_test MATERIALIZE KEY tag_idx tag in partition partition_expr;

支援多列索引的目的是減少特定查詢pattern下的索引結果歸併，針對QPS要求特別高的查詢使用者可以建立針對性的多列索引達到極致的檢索效能。而表示式索引主要是方便使用者進行自由的檢索粒度變換，考慮以下兩個典型場景：

1）索引中的時間列在搜尋條件中，只會以小時粒度進行過濾，這種情況下使用者可以對toStartOfHour(time)表示式建立索引，可以一定程度加速索引構建，同時對time列的時間過濾條件都可以自動轉換下推索引。

2）索引中的id列是由UUID構成，UUID幾乎是可以保證永久distinct的字串序列，直接對id構建索引會導致索引檔案太大。這時使用者可以使用字首函式擷取UUID來構建索引，如prefix8(id)是擷取8個byte的字首，對應的還有prefix4和prefix16，prefixUTF4、prefixUTF8、prefixUTF16則是用來擷取UTF編碼的。

值得注意的是，使用者對錶達式構建索引後，原列上的查詢條件也可以正常下推索引，不需要特意改寫查詢。同樣使用者對原列構建索引，過濾條件上對原列加了表示式的情況下，最佳化器也都可以正常下推索引。

In Set Clause下推則是一個關聯搜尋的典型場景，作者經常碰到此類場景：user的屬性是一張單獨的大寬表，user的行為記錄又是另一張單獨的表，對user的搜尋需要先從user行為記錄表中聚合過濾出滿足條件的user id，再用user ids從屬性表中取出明細記錄。這種in subquery的場景下，ClickHouse也可以自動下推索引進行加速。

多值索引

多值索引主要針對的是array型別列上has()/hasAll()/hasAny()條件的搜尋加速，array列時標籤分析裡常用的資料型別，每條記錄會attach對個標籤，存放在一個array列裡。對這個標籤列的過濾以往只能透過暴力掃描過濾，ClickHouse二級索引專門擴充套件了多值索引型別解決此類問題，索引定義示例如下：

CREATE TABLE index_test (  id UInt64,   tags Array(String),  KEY tag_idx tag TYPE array --多值索引) ENGINE = MergeTree() ORDER BY id;--包含單個標籤select * from index_test where has(tags, 'aaa');--包含所有標籤select * from index_test where hasAll(tags, ['aaa', 'bbb']);--包含任意標籤select * from index_test where has(tags, ['aaa', 'ccc']);

字典索引

字典索引主要是針對那種使用兩個array型別列模擬Map的場景進行檢索加速，key和value是兩個單獨的array列，透過元素的position一一對應進行kv關聯。ClickHouse二級索引專門為這種場景擴充套件了檢索函式和索引型別支援，索引定義示例如下：

CREATE TABLE index_test (  id UInt64,   keys Array(String),  vals Array(UInt32),  KEY kv_idx (keys, vals) TYPE map --字典索引) ENGINE = MergeTree() ORDER BY id;--指定key的value等值條件 map['aaa'] = 32select * from index_test where hasPairEQ(keys, vals, ('aaa', 32));--指定key的value大於條件 map['aaa'] > 32select * from index_test where hasPairGT(keys, vals, ('aaa', 32));--指定key的value大於等於條件 map['aaa'] >= 32select * from index_test where hasPairGTE(keys, vals, ('aaa', 32));--指定key的value小於條件 map['aaa'] < 32select * from index_test where hasPairLT(keys, vals, ('aaa', 32));--指定key的value小於等於條件 map['aaa'] <= 32select * from index_test where hasPairLTE(keys, vals, ('aaa', 32));

索引構建效能

作者對ClickHouse的二級索引構建效能和索引壓縮率做了全方位多場景下的測試，主要對比的是lucene 8.7的倒排索引和BKD索引。ElasticSearch底層的索引就是採用的lucene，這裡的效能資料讀者可以作個參考，但並不代表ElasticSearch和ClickHouse二級索引功能端到端的效能水平。因為ClickHouse的二級索引是在DataPart merge的時候進行構建，瞭解ClickHouse MergeTree儲存引擎的同學應該明白MergeTree存在寫放大的情況(一條記錄merge多次)，同時merge又完全是非同步的行為。

日誌trace_id場景

mock資料方法：

substringUTF8(cast (generateUUIDv4() as String), 1, 16)

資料量：1E (ClickHouse資料檔案1.5G)

構建耗時：

ClickHouse 65.32s vs Lucene 487.255s

索引檔案大小：

ClickHouse 1.4G vs Lucene 1.3G

字串列舉場景

mock資料方法：

cast((10000000 + rand(number) % 1000) as String)

資料量：1E (ClickHouse資料檔案316M)

構建耗時：

ClickHouse 37.19s vs Lucene 46.279s

索引檔案大小：

ClickHouse 160M vs Lucene 163M

數值雜湊場景

mock資料方法：

toFloat64(rand(100000000))

資料量：1E (ClickHouse資料檔案564M)

構建耗時：

ClickHouse 32.20s vs Lucene BKD 86.456s

索引檔案大小：

ClickHouse 801M vs Lucene BKD 755M

數值列舉場景

mock資料方法：

rand(1000)

資料量：1E (ClickHouse資料檔案275M)

構建耗時：

ClickHouse 12.81s vs Lucene BKD 78.0s

索引檔案大小：

ClickHouse 160M vs Lucene BKD 184M

結語

二級索引功能的主要目的是為了彌補ClickHouse在搜尋場景下的不足，在分析場景下ClickHouse目前原有的技術已經比較豐富。希望透過本文大家對OLAP查詢最佳化有更深的理解，歡迎大家嘗試使用二級索引來解決多維搜尋問題，積極反饋使用體驗問題。