前言

前兩周寫過一篇《基於Lucene查詢原理分析Elasticsearch的性能》，在最後留了一個彩蛋，說下一篇會介紹一種可以極大的優化查詢性能的技術。本文就來介紹這種技術——IndexSorting。

因為IndexSorting是在ES6.0之後才作為實驗性的功能加入，相關的介紹資料還比較少，所以大部分人對它不夠了解。另一方面是，想要理解它為什麼能夠優化性能、適合哪些場景、內部如何實現、有何副作用等，也需要花一翻功夫。所以本文專門對IndexSorting進行一個介紹，並分析它的作用、實現、適用場景等。如果你的場景能用上IndexSorting，那麼它肯定會給你帶來一個巨大的性能提升！

什麼是IndexSorting？

IndexSorting是ES的新功能

在Elasticsearch中，IndexSorting是一個很新的功能，6.0版本才引入，並且標記這個功能是Beta版(6.5版本可能會去掉Beta標記)。

在Lucene中，IndexSorting其實已經發展了一段時間。最早在10年，Lucene提供了一個IndexSorter的工具，作為一個離線工具可以對Index數據排序後生成一個新的Index。後來13年加入了SortingMergePolicy，在Segment進行merge的時候可以生成排好序的新Segment，在17年又加入了Sorting on flushed segment的功能，在Segment最初生成時就進行排序。另一方面是Lucene在查詢時也做了很多優化，如果有IndexSorting，很多地方做了提前中斷，後面會講提前中斷對查詢性能的巨大作用。經過幾次Lucene的改進和優化，IndexSorting這個功能也終於被集成進Elasticsearch。

IndexSorting是一種預排序

與查詢時的Sort不同，IndexSorting是一種預排序，即數據預先按照某種方式進行排序，它是Index的一個設置，不可更改。大家知道，Elasticsearch的底層是Lucene，Lucene中是以Segment為單位進行查詢的，這裡說的IndexSorting對數據進行預排序也是在每個Segment內有序的。

一個Segment中的每個文檔，都會被分配一個docID，docID從0開始，順序分配。在沒有IndexSorting時，docID是按照文檔寫入的順序進行分配的，在設置了IndexSorting之後，docID的順序就與IndexSorting的順序一致。

舉個例子來說，假如文檔中有一列為Timestamp，我們在IndexSorting中設置按照Timestamp逆序排序，那麼在一個Segment內，docID越小，對應的文檔的Timestamp越大，即按照Timestamp從大到小的順序分配docID。

為什麼IndexSorting可以優化性能？

提前中斷

IndexSorting能夠優化性能，主要就是靠四個字，「提前中斷」。但是提前中斷是有條件的，需要查詢的Sort順序與IndexSorting的順序相同，並且不需要獲取符合條件的記錄總數(TotalHits)。

Lucene中的倒排鏈都是按照docID從小到大的順序排列的，在進行組合條件查詢時，也是按照docID從小到大的順序選出符合條件的doc。那麼當查詢時的Sort順序與IndexSorting的順序相同時，會發生什麼呢？

比如查詢時希望按照Timestamp降序排序後返回100條結果，在Lucene中進行查詢時，發現docID對應的doc順序也剛好是Timestamp降序排序的，那麼查詢到前100個符合條件的結果即可返回，這100個一定也是Timestamp最大的100個，這就做到了提前中斷。

提前中斷可以極大的提升查詢性能，特別是當一個查詢條件命中的文檔數量非常多的時候。在沒有IndexSorting時，必須把所有符合條件的文檔的docID掃描一遍，並且讀取這些doc的一些字段來排序，選出符合條件的doc。有了IndexSorting之後，只需要選出前Top個doc即可，避免了全部掃描，性能甚至可以提升幾個數量級。

IndexSorting提高了數據壓縮率

Lucene中使用了很多的壓縮算法來對數據進行壓縮，壓縮一方面減少了磁盤使用量，另一方面也減少了查詢時讀取磁盤的數據量和IO次數等，對查詢性能有很大幫助。

Lucene中同時包括行存(Store)與列存(DocValues)的存儲方式，但不管是行存還是列存，當應用IndexSorting後，相鄰數據的相似度就會越高，也就越利於壓縮。這不僅僅是體現在排序字段上，也體現在其他字段的相似度上。比如時序場景，當按照時間排序後，各個Metrics的值的近似度也會越大。所以IndexSorting可以提高數據的壓縮率。

IndexSorting是否適合我的場景？

由排序條件決定是否適合

IndexSorting最大的作用就是優化查詢性能，其適用的場景就是能夠被其優化的場景，比如說：

1. 查詢時需要根據某列或者某幾列排序後返回的場景：讓IndexSorting順序跟要查詢的Sort順序一致，讓Lucene能夠提前中斷來提升性能。
2. 不關心結果順序的場景：也可以按照某列IndexSorting，查詢時也設置按照這一列Sort即可。
3. 有幾種排序需求的場景：IndexSorting起碼可以優化一種排序需求，其餘的幾種需求可以考慮是否多建幾個索引，用空間換時間。

也有些場景不能被其優化，比如根據文檔相似度分數排序的場景，這時候很難進行預排序，因為相似分數是每次查詢時才算出來的。

根據查詢原理看是否能優化

上面提到Lucene會按照docID從小到大的順序選出符合條件的doc，但是有時查詢並不是慢在這個篩選過程，而是構造docID列表的過程，這時IndexSorting帶來的優化效果會比較有限。

因為Lucene的查詢原理是比較複雜的，這裡只列舉兩個例子：

1. 對於字符串進行Range查詢，且Range範圍內有很多符合條件的Term的場景。這個場景下，查詢可能會慢在兩個地方，一個是Range範圍內符合條件的Term非常多，掃描FST耗時很大，另一個如果這些Term對應的doc數很多，要構造BitSet也會非常耗時。因為利用IndexSorting的提前中斷是發生在BitSet構造好之後，所以並不能優化到這個地方的性能。
2. 對數字類型在BKD-Tree上進行範圍查找時，因為BKD-Tree里的docID不是順序排列的，所以並不像倒排鏈一樣可以順序讀取。如果BKD-Tree上符合條件的docID很多，構造BitSet也很耗時，也不是IndexSorting能夠優化到的。

考慮對寫入性能的影響

IndexSorting優化的是查詢性能，因為在寫入時需要對數據進行排序，所以降低了寫性能。如果寫性能是目前的性能瓶頸，或者看重寫性能要高於查詢性能，那麼不適合使用IndexSorting。

IndexSorting是如何實現的？

本文介紹一下IndexSorting的實現細節，這也有助於大家理解它對寫入性能產生的影響。IndexSorting可以保證在每個Segment中，數據都是按照設置的方式進行排序的，這要解決兩個問題：

1. Lucene的Flush操作會生成Segment，這時候生成的Segment如何保證數據有序。
2. 多個Segment進行合併時如何保證有序。

1. Flush時保證Segment內數據有序

大家知道，數據寫入Lucene後，並不是立即可查的，要生成Segment之後才能被查到。為了保證近實時的查詢，ES會每隔一秒進行一次Refresh，Refresh就會調用到Lucene的Flush生成新的Segment。額外說的一點是，Lucene的Flush不同於ES的Flush，ES的Flush保證數據落盤，調用的是Lucene的commit，裏面會調用fsync，這裡的關係值得額外寫一篇文章來說清楚。

我們需要先知道Flush前數據是一個什麼樣的狀態，才能知道Flush時如何對這些數據排序。每個doc寫入進來之後，按照寫入順序被分配一個docID，然後被IndexingChain處理，依次要對invert index、store fields、doc values和point values進行處理，有些數據會直接寫到文件里，主要是store field和term vector，其他的數據會放到memory buffer中。

在Flush時，首先根據設定的列排序，這個排序可以利用內存中的doc values，排序之後得到老的docID到新docID的映射，因為之前docID是按照寫入順序生成的，現在重排後，生成的是新的排列。如果排序後與原來順序完全一致，那麼什麼都不做，跟之前流程一樣進行Flush。

如果排序後順序發生變化，如何排序呢？對於已經寫到文件中的數據，比如store field和term vector，需要從文件中讀出來，重新排列後再寫到一個新文件里，原來的文件就相當於一個臨時文件。對於內存中的數據結構，直接在內存中重排後寫到文件中。

相比沒有IndexSorting時，對性能影響比較大的一塊就是store field的重排，因為這部分需要從文件中讀出再寫回，而其他部分都是內存操作，性能影響稍小一些。這裡我們也可以做一些思考，如果將store field和term vector這類數據也buffer在內存中，是否可以提升IndexSorting開啟時的寫入性能？

2. Merge時保證新的Segment數據有序

由於Flush時Segment已經是有序的了，所以在Merge時也就可以採用非常高效的Merge Sort的方式進行。

總結

IndexSorting是一種能夠極大提高查詢效率的技術，它通過預排序和提前中斷大大減少了需要掃描的數據量，而且附帶的優化是可以提高壓縮率，減少存儲空間。對於查詢時需要按照某列排序的場景，它非常有用，但對於相關性分數排序的場景則無法通過預排序來優化。IndexSorting的缺點是對寫入性能有影響，主要是體現在Segment的Flush和Merge階段，對於非常看重寫入性能的場景也不適合使用。總體上說，這是一項非常有用也很新的技術，相信它在Lucene和ES中的重要性會越來越強，也會有越來越多的業務場景受益於這個功能。