引言
阿裡雲資料庫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 where
where 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 where
prewhere 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'] = 32
select * from index_test where hasPairEQ(keys, vals, ('aaa', 32));
--指定key的value大于條件 map['aaa'] > 32
select * from index_test where hasPairGT(keys, vals, ('aaa', 32));
--指定key的value大于等于條件 map['aaa'] >= 32
select * from index_test where hasPairGTE(keys, vals, ('aaa', 32));
--指定key的value小于條件 map['aaa'] < 32
select * from index_test where hasPairLT(keys, vals, ('aaa', 32));
--指定key的value小于等于條件 map['aaa'] <= 32
select * 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
字元串枚舉場景
cast((10000000 + rand(number) % 1000) as String)
資料量：1E (ClickHouse資料檔案316M)
ClickHouse 37.19s vs Lucene 46.279s
ClickHouse 160M vs Lucene 163M
數值散列場景
toFloat64(rand(100000000))
資料量：1E (ClickHouse資料檔案564M)
ClickHouse 32.20s vs Lucene BKD 86.456s
ClickHouse 801M vs Lucene BKD 755M
數值枚舉場景
rand(1000)
資料量：1E (ClickHouse資料檔案275M)
ClickHouse 12.81s vs Lucene BKD 78.0s
ClickHouse 160M vs Lucene BKD 184M
結語
二級索引功能的主要目的是為了彌補ClickHouse在搜尋場景下的不足，在分析場景下ClickHouse目前原有的技術已經比較豐富。希望通過本文大家對OLAP查詢優化有更深的了解，歡迎大家嘗試使用二級索引來解決多元搜尋問題，積極回報使用體驗問題。
![【MySQL資料庫】資料庫索引事務1.索引2.事務[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)