跳數(shù)索引(二級(jí)索引)

影響ClickHouse查詢性能的因素很多。在大多數(shù)場(chǎng)景中，關(guān)鍵因素是ClickHouse在計(jì)算查詢WHERE子句條件時(shí)是否可以使用主鍵。因此，選擇適用于最常見查詢模式的主鍵對(duì)于表的設(shè)計(jì)至關(guān)重要。

然而，無論如何仔細(xì)地調(diào)優(yōu)主鍵，不可避免地會(huì)出現(xiàn)不能有效使用它的查詢用例。用戶通常依賴于ClickHouse獲得時(shí)間序列類型的數(shù)據(jù)，但他們通常希望根據(jù)其他業(yè)務(wù)維度(如客戶id、網(wǎng)站URL或產(chǎn)品編號(hào))分析同一批數(shù)據(jù)。在這種情況下，查詢性能可能會(huì)相當(dāng)差，因?yàn)閼?yīng)用WHERE子句條件可能需要對(duì)每個(gè)列值進(jìn)行完整掃描。雖然ClickHouse在這些情況下仍然相對(duì)較快，但計(jì)算數(shù)百萬或數(shù)十億個(gè)單獨(dú)的值將導(dǎo)致“非索引”查詢的執(zhí)行速度比基于主鍵的查詢慢得多。

在傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中，解決這個(gè)問題的一種方法是將一個(gè)或多個(gè)“二級(jí)”索引附加到表上。這是一個(gè)b-樹結(jié)構(gòu)，允許數(shù)據(jù)庫(kù)在O(log(n))時(shí)間內(nèi)找到磁盤上所有匹配的行，而不是O(n)時(shí)間(一次表掃描)，其中n是行數(shù)。但是，這種類型的二級(jí)索引不適用于ClickHouse(或其他面向列的數(shù)據(jù)庫(kù))，因?yàn)榇疟P上沒有單獨(dú)的行可以添加到索引中。

相反，ClickHouse提供了一種不同類型的索引，在特定情況下可以顯著提高查詢速度。這些結(jié)構(gòu)被標(biāo)記為跳數(shù)索引，因?yàn)樗鼈兪笴lickHouse能夠跳過保證沒有匹配值的數(shù)據(jù)塊。

基本操作

用戶只能在MergeTree表引擎上使用數(shù)據(jù)跳數(shù)索引。每個(gè)跳數(shù)索引都有四個(gè)主要參數(shù)：

• 索引名稱。索引名用于在每個(gè)分區(qū)中創(chuàng)建索引文件。此外，在刪除或具體化索引時(shí)需要將其作為參數(shù)。
• 索引的表達(dá)式。索引表達(dá)式用于計(jì)算存儲(chǔ)在索引中的值集。它可以是列、簡(jiǎn)單操作符、函數(shù)的子集的組合。
• 類型。索引的類型控制計(jì)算，該計(jì)算決定是否可以跳過讀取和計(jì)算每個(gè)索引塊。
• GRANULARITY。每個(gè)索引塊由顆粒（granule）組成。例如，如果主表索引粒度為8192行，GRANULARITY為4，則每個(gè)索引“塊”將為32768行。

當(dāng)用戶創(chuàng)建數(shù)據(jù)跳數(shù)索引時(shí)，表的每個(gè)數(shù)據(jù)部分目錄中將有兩個(gè)額外的文件。

• skpidx{index_name}.idx：包含排序的表達(dá)式值。
• skpidx{index_name}.mrk2：包含關(guān)聯(lián)數(shù)據(jù)列文件中的相應(yīng)偏移量。

如果在執(zhí)行查詢并讀取相關(guān)列文件時(shí)，WHERE子句過濾條件的某些部分與跳數(shù)索引表達(dá)式匹配，ClickHouse將使用索引文件數(shù)據(jù)來確定每個(gè)相關(guān)的數(shù)據(jù)塊是必須被處理還是可以被繞過(假設(shè)塊還沒有通過應(yīng)用主鍵索引被排除)。這里用一個(gè)非常簡(jiǎn)單的示例：考慮以下加載了可預(yù)測(cè)數(shù)據(jù)的表。

CREATE TABLE skip_table
(  
my_key UInt64,  
my_value UInt64
)
ENGINE MergeTree 
primary key my_key
SETTINGS index_granularity=8192;

INSERT INTO skip_table 
SELECT number, intDiv(number,4096) 
FROM numbers(100000000);

當(dāng)執(zhí)行一個(gè)不使用主鍵的簡(jiǎn)單查詢時(shí)，將掃描my_value列所有的一億條記錄：

SELECT * FROM skip_table WHERE my_value IN (125,700)
┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘
8192 rows in set. Elapsed: 0.079 sec. Processed 100.00 million rows, 800.10 MB (1.26 billion rows/s., 10.10 GB/s.

增加一個(gè)基本的跳數(shù)索引：

ALTER TABLE skip_table ADD INDEX vix my_value TYPE set(100) GRANULARITY 2;

通常，跳數(shù)索引只應(yīng)用于新插入的數(shù)據(jù)，所以僅僅添加索引不會(huì)影響上述查詢。

要使已經(jīng)存在的數(shù)據(jù)生效，那執(zhí)行：

ALTER TABLE skip_table MATERIALIZE INDEX vix;

重跑SQL：

SELECT * FROM skip_table WHERE my_value IN (125, 700)
┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘
8192 rows in set. Elapsed: 0.051 sec. Processed 32.77 thousand rows, 360.45 KB (643.75 thousand rows/s., 7.08 MB/s.)

這次沒有再去處理1億行800MB的數(shù)據(jù)，ClickHouse只讀取和分析32768行360KB的數(shù)據(jù)—4個(gè)granule(顆粒)的數(shù)據(jù)。

下圖是更直觀的展示，這就是如何讀取和選擇my_value為125的4096行，以及如何跳過以下行而不從磁盤讀取:

通過在執(zhí)行查詢時(shí)啟用跟蹤，用戶可以看到關(guān)于跳數(shù)索引使用情況的詳細(xì)信息。在clickhouse-client中設(shè)置send_logs_level:

SET send_logs_level='trace';

這將在嘗試調(diào)優(yōu)查詢SQL和表索引時(shí)提供有用的調(diào)試信息。上面的例子中，調(diào)試日志顯示跳數(shù)索引過濾了大部分granule，只讀取了兩個(gè):

<Debug> default.skip_table (933d4b2c-8cea-4bf9-8c93-c56e900eefd1) (SelectExecutor): Index `vix` has dropped 6102/6104 granules.

跳數(shù)索引類型

minmax

這種輕量級(jí)索引類型不需要參數(shù)。它存儲(chǔ)每個(gè)塊的索引表達(dá)式的最小值和最大值(如果表達(dá)式是一個(gè)元組，它分別存儲(chǔ)元組元素的每個(gè)成員的值)。對(duì)于傾向于按值松散排序的列，這種類型非常理想。在查詢處理期間，這種索引類型的開銷通常是最小的。

這種類型的索引只適用于標(biāo)量或元組表達(dá)式——索引永遠(yuǎn)不適用于返回?cái)?shù)組或map數(shù)據(jù)類型的表達(dá)式。

set

這種輕量級(jí)索引類型接受單個(gè)參數(shù)max_size，即每個(gè)塊的值集(0允許無限數(shù)量的離散值)。這個(gè)集合包含塊中的所有值(如果值的數(shù)量超過max_size則為空)。這種索引類型適用于每組顆粒中基數(shù)較低(本質(zhì)上是“聚集在一起”)但總體基數(shù)較高的列。

該索引的成本、性能和有效性取決于塊中的基數(shù)。如果每個(gè)塊包含大量惟一值，那么針對(duì)大型索引集計(jì)算查詢條件將非常昂貴，或者由于索引超過max_size而為空，因此索引將不應(yīng)用。

Bloom Filter Types

Bloom filter是一種數(shù)據(jù)結(jié)構(gòu)，它允許對(duì)集合成員進(jìn)行高效的是否存在測(cè)試，但代價(jià)是有輕微的誤報(bào)。在跳數(shù)索引的使用場(chǎng)景，假陽性不是一個(gè)大問題，因?yàn)槲┮坏膯栴}只是讀取一些不必要的塊。潛在的假陽性意味著索引表達(dá)式應(yīng)該為真，否則有效的數(shù)據(jù)可能會(huì)被跳過。

因?yàn)锽loom filter可以更有效地處理大量離散值的測(cè)試，所以它們可以適用于大量條件表達(dá)式判斷的場(chǎng)景。特別的是Bloom filter索引可以應(yīng)用于數(shù)組，數(shù)組中的每個(gè)值都被測(cè)試，也可以應(yīng)用于map，通過使用mapKeys或mapValues函數(shù)將鍵或值轉(zhuǎn)換為數(shù)組。

有三種基于Bloom過濾器的數(shù)據(jù)跳數(shù)索引類型：

• 基本的bloom_filter接受一個(gè)可選參數(shù)，該參數(shù)表示在0到1之間允許的“假陽性”率(如果未指定，則使用.025)。

• 更專業(yè)的tokenbf_v1。需要三個(gè)參數(shù)，用來優(yōu)化布隆過濾器：（1）過濾器的大小字節(jié)(大過濾器有更少的假陽性，有更高的存儲(chǔ)成本)，（2）哈希函數(shù)的個(gè)數(shù)(更多的散列函數(shù)可以減少假陽性)。（3）布隆過濾器哈希函數(shù)的種子。有關(guān)這些參數(shù)如何影響布隆過濾器功能的更多細(xì)節(jié)，請(qǐng)參閱 這里 。此索引僅適用于String、FixedString和Map類型的數(shù)據(jù)。輸入表達(dá)式被分割為由非字母數(shù)字字符分隔的字符序列。例如，列值This is a candidate for a "full text" search將被分割為This is a candidate for full text search。它用于LIKE、EQUALS、in、hasToken()和類似的長(zhǎng)字符串中單詞和其他值的搜索。例如，一種可能的用途是在非結(jié)構(gòu)的應(yīng)用程序日志行列中搜索少量的類名或行號(hào)。

• 更專業(yè)的ngrambf_v1。該索引的功能與tokenbf_v1相同。在Bloom filter設(shè)置之前需要一個(gè)額外的參數(shù)，即要索引的ngram的大小。一個(gè)ngram是長(zhǎng)度為n的任何字符串，比如如果n是4，A short string會(huì)被分割為A sh`` sho, shor, hort, ort s, or st, r str, stri, trin, ring。這個(gè)索引對(duì)于文本搜索也很有用，特別是沒有單詞間斷的語言，比如中文。

跳數(shù)索引函數(shù)

跳數(shù)索引核心目的是限制流行查詢分析的數(shù)據(jù)量。鑒于ClickHouse數(shù)據(jù)的分析特性，這些查詢的模式在大多數(shù)情況下都包含函數(shù)表達(dá)式。因此，跳數(shù)索引必須與常用函數(shù)正確交互才能提高效率。這種情況可能發(fā)生在:

• 插入數(shù)據(jù)并將索引定義為一個(gè)函數(shù)表達(dá)式(表達(dá)式的結(jié)果存儲(chǔ)在索引文件中)或者
• 處理查詢，并將表達(dá)式應(yīng)用于存儲(chǔ)的索引值，以確定是否排除數(shù)據(jù)塊。

每種類型的跳數(shù)索引支持的函數(shù)列表可以查看 這里 。通常，集合索引和基于Bloom filter的索引(另一種類型的集合索引)都是無序的，因此不能用于范圍。相反，最大最小值索引在范圍中工作得特別好，因?yàn)榇_定范圍是否相交非?？?。部分匹配函數(shù)LIKE、startsWith、endsWith和hasToken的有效性取決于使用的索引類型、索引表達(dá)式和數(shù)據(jù)的特定形狀。

跳數(shù)索引的配置

有兩個(gè)可用的設(shè)置可應(yīng)用于跳數(shù)索引。

• use_skip_indexes (0或1，默認(rèn)為1)。不是所有查詢都可以有效地使用跳過索引。如果一個(gè)特定的過濾條件可能包含很多顆粒，那么應(yīng)用數(shù)據(jù)跳過索引將導(dǎo)致不必要的、有時(shí)甚至是非常大的成本。對(duì)于不太可能從任何跳過索引中獲益的查詢，將該值設(shè)置為0。
• force_data_skipping_indexes (以逗號(hào)分隔的索引名列表)。此設(shè)置可用于防止某些類型的低效查詢。在某些情況下，除非使用跳過索引，否則查詢表的開銷太大，如果將此設(shè)置與一個(gè)或多個(gè)索引名一起使用，則對(duì)于任何沒有使用所列索引的查詢將返回一個(gè)異常。這將防止編寫糟糕的查詢消耗服務(wù)器資源。

最佳實(shí)踐

跳數(shù)索引并不直觀，特別是對(duì)于來自RDMS領(lǐng)域并且習(xí)慣二級(jí)行索引或來自文檔存儲(chǔ)的反向索引的用戶來說。要獲得任何優(yōu)化，應(yīng)用ClickHouse數(shù)據(jù)跳數(shù)索引必須避免足夠多的顆粒讀取，以抵消計(jì)算索引的成本。關(guān)鍵是，如果一個(gè)值在一個(gè)索引塊中只出現(xiàn)一次，就意味著整個(gè)塊必須讀入內(nèi)存并計(jì)算，而索引開銷是不必要的。

考慮以下數(shù)據(jù)分布：

假設(shè)主鍵/順序是時(shí)間戳，并且在visitor_id上有一個(gè)索引?？紤]下面的查詢:

SELECT timestamp, url FROM table WHERE visitor_id = 1001

對(duì)于這種數(shù)據(jù)分布，傳統(tǒng)的二級(jí)索引非常有利。不是讀取所有的32678行來查找具有請(qǐng)求的visitor_id的5行，而是二級(jí)索引只包含5行位置，并且只從磁盤讀取這5行。ClickHouse數(shù)據(jù)跳過索引的情況正好相反。無論跳轉(zhuǎn)索引的類型是什么，visitor_id列中的所有32678值都將被測(cè)試。

因此，試圖通過簡(jiǎn)單地向鍵列添加索引來加速ClickHouse查詢的沖動(dòng)通常是不正確的。只有在研究了其他替代方法之后，才應(yīng)該使用此高級(jí)功能，例如修改主鍵(查看 如何選擇主鍵)、使用投影或使用實(shí)體化視圖。即使跳數(shù)索引是合適的，也經(jīng)常需要對(duì)索引和表進(jìn)行仔細(xì)的調(diào)優(yōu)。

在大多數(shù)情況下，一個(gè)有用的跳數(shù)索引需要主鍵和目標(biāo)的非主列/表達(dá)式之間具有很強(qiáng)的相關(guān)性。如果沒有相關(guān)性(如上圖所示)，那么在包含數(shù)千個(gè)值的塊中，至少有一行滿足過濾條件的可能性很高，并且只有幾個(gè)塊會(huì)被跳過。相反，如果主鍵的值范圍(如一天中的時(shí)間)與潛在索引列中的值強(qiáng)相關(guān)(如電視觀眾年齡)，則最小值類型的索引可能是有益的。注意，在插入數(shù)據(jù)時(shí)，可以增加這種相關(guān)性，方法是在sort /ORDER by鍵中包含額外的列，或者以在插入時(shí)對(duì)與主鍵關(guān)聯(lián)的值進(jìn)行分組的方式對(duì)插入進(jìn)行批處理。例如，即使主鍵是一個(gè)包含大量站點(diǎn)事件的時(shí)間戳，特定site_id的所有事件也都可以被分組并由寫入進(jìn)程插入到一起，這將導(dǎo)致許多只包含少量站點(diǎn)id的顆粒，因此當(dāng)根據(jù)特定的site_id值搜索時(shí)，可以跳過許多塊。

跳數(shù)索引的另一個(gè)候選者是高基數(shù)表達(dá)式，其中任何一個(gè)值在數(shù)據(jù)中都相對(duì)稀疏。一個(gè)可能的例子是跟蹤API請(qǐng)求中的錯(cuò)誤代碼的可觀察性平臺(tái)。某些錯(cuò)誤代碼雖然在數(shù)據(jù)中很少出現(xiàn)，但對(duì)搜索來說可能特別重要。error_code列上的set skip索引將允許繞過絕大多數(shù)不包含錯(cuò)誤的塊，從而顯著改善針對(duì)錯(cuò)誤的查詢。

最后，關(guān)鍵的最佳實(shí)踐是測(cè)試、測(cè)試、再測(cè)試。同樣，與用于搜索文檔的b-樹二級(jí)索引或倒排索引不同，跳數(shù)索引行為是不容易預(yù)測(cè)的。將它們添加到表中會(huì)在數(shù)據(jù)攝取和查詢方面產(chǎn)生很大的成本，這些查詢由于各種原因不能從索引中受益。它們應(yīng)該總是在真實(shí)世界的數(shù)據(jù)類型上進(jìn)行測(cè)試，測(cè)試應(yīng)該包括類型、粒度大小和其他參數(shù)的變化。測(cè)試通常會(huì)暴露僅僅通過思考不能發(fā)現(xiàn)的陷阱。