Categories
程式開發

數據庫內核雜談(三):索引優化


在上一篇文章的末尾,我們留了一個坑。雖然通過列存,能夠避免讀取不必要的數據(沒使用的列)來提高查詢速度,但是對於下面這類點查詢(point query),還能不能進一步優化呢?

SELECT * FROM titanic_survivor WHERE age = 10;

答案是肯定的,解決方案就是今天的主題 – 索引(index)。

索引這個概念在我們日常生活中很常見。比如在很多書籍的最後,都配有關鍵字索引。它能幫助你快速地找到某個關鍵字所在的書頁。試想一下,如果沒有索引,想要查詢某個關鍵字所在的章節和書頁,可能唯一的辦法就是一頁一頁翻書直到找到為止。索引大大提高了查詢的速度!

數據庫的索引也正是為了解決這類問題:索引通過引入冗餘的數據存儲(類比書籍最後的索引章節),以此來提高查詢語句的速度。和上一期的結構類似,相較於列舉不同索引類型的分類法,我們依然從解決問題的角度來看不同類型的索引是為了解決哪些查詢而演化而來的。

回到上面這個點查詢語句,你能想到什麼辦法來優化執行?我們沿用上一期titanic_survivor的數據(下圖),一起來看。

數據庫內核雜談(三):索引優化 1

titanic_survivor

讀者可能很容易就會想到,我們可以建立一個哈希表(HashMap)。哈希表的鍵(key)存儲age的值,哈希表的值(value)存儲所有age為對應鍵值的row在存儲系統中的相對位置(如果使用csv文件存儲,它就是row的行號。如果用字節流存儲數據,它就是row對應於文件中的offset)。下圖是對於titanic_survovior的age列作索引。

數據庫內核雜談(三):索引優化 2

hash_table_age

有了這樣一個哈希表,當需要查詢年齡是35的倖存者時,只需要讀取行4和行5的數據即可。 (可能對於csv文件比較難描述這類優化。設想當數據文件是按字節流存儲時,可以用隨機文件讀取的API來讀取很小一部分數據) 雖然隨機讀取的平均效率遠低於順序讀取(因為文件系統需要尋道seek),但相比於讀取2行數據和一百萬行數據,前者的速度毋庸置疑得快。

這樣一個哈希表,就引出了第一類索引,哈希索引(Hash Index): 根據需要索引的列(並不限制為一個列,可以是多個列的組合),建立一個哈希表。讀取數據時,先根據索引列的鍵值找到對應的數據位置,然後讀取相應數據。

本文不是數據結構101,就不具體討論如何實現哈希函數,解決鍵衝突,對哈希表進行擴容縮容等的問題了。稍微聊一些工程實踐中的細節:選擇哈希函數的指標,肯定是速度越快越好。在輸入和輸出值域相同的情況下,衝突概率越低越好。下面列舉了一些開源且受歡迎的哈希函數實現,有興趣的同學可以深入學習:

  1. MurmurHash (2008):
    https://en.wikipedia.org/wiki/MurmurHash

  2. Google CityHash (2011):
    https://opensource.googleblog.com/2011/04/introducing-cityhash.html

  3. Google FarmHash (2014):
    https://opensource.googleblog.com/2014/03/introducing-farmhash.html

  4. CLHash (Carry-less) (2016):
    https://arxiv.org/abs/1503.03465

有同學提出疑問,提到哈希算法, 最先想到的就是MD5, SHA等的算法,為什麼這裡並沒有提及。因為這類算法被稱為密碼哈希算法(當然MD5已經多次被證明不安全了,請不要繼續用於加密。。)。為了追求安全性,這類算法具備特別的屬性,比如難以從一個已知的哈希值去逆推原始的消息以及雪崩效應(Avalanche effect): 即輸入發生微小變化也會導致輸出的不可區分性改變,從而犧牲了哈希運算的效率。建立哈希索引時並不需要這類安全屬性,因此會選擇性能更高的哈希算法。

著名的開源數據庫PostgreSQL就支持哈希索引,生成語句如下:

(CREATE INDEX index_name ON table_name USING HASH (column_name);

但在對應的文檔中,卻明確指出了不建議使用哈希索引。至於原因,我們先賣個關子,過一會再詳解。總結一下,為了提高點查詢的效率,我們引入了第一類索引,哈希索引。

哈希索引雖好,卻也不是萬能的。比如把查詢條件從點查詢改為範圍查詢,如下所示:

SELECT * FROM titanic_survivor WHERE age BETWEEN 1 AND 10;

有同學說,依然可以用哈希索引解決,只要做10次哈希索引的查詢即可。那我做得再絕一些:

SELECT * FROM titanic_survivor WHERE age > 10;

或者乾脆把age換成浮點類型。如此,哈希索引是萬萬沒轍了吧。

面對這類查詢,有什麼方法可以提高速度呢?有讀者會想到,如果把要查詢的列(此為age)進行排序,然後進行二分查找來定位,依次掃描列中滿足條件的數據,就可以避免全文件掃描了。沿用上面的示例,我們對titanic_survivor的age列排序,並且紀錄相應的行號, 如下圖所示:

數據庫內核雜談(三):索引優化 3

sorted_age_list

假設需要查詢年齡在20至40歲之間的倖存者,可以通過二分查找先定位到年齡22,然後依次順序讀取之後26,35和38歲的對應行的數據,當搜索至54歲時停止即可。概括一下方法:對相關列進行排序,用二分查找來快速定位然後順序查詢。二分查找1至100萬中的某個數需要20次查詢(2^20約等於100萬),有什麼方法可以再進一步提高效率?於是我們引出第二個使用的數據結構B樹和B+樹(B – tree, B+ – Tree)。

關於B樹和B+樹的具體實現細節,請參考相關數據結構書籍資料,這裡就不贅述了。簡單而言,B樹相當於把二分查找變成了N分查找,假設N為100,那查找範圍為(1, 100萬)就只需要3次分叉了(100^3 = 100萬)。 B+樹和B樹的區別就在於B樹在非葉節點也會存儲數據而B+樹僅在頁節點存儲數據。下圖示例為B+樹。

數據庫內核雜談(三):索引優化 4

B+ tree

這類索引就稱之為B樹索引。 B樹和B+樹通過引入有很多分枝的樹節點來提高定位速度以此來提高整體查詢速度,算得上是空間換時間的方法。同樣,在工程中還有很多可優化的細節。比如對於B+樹,只有頁節點存儲具體的數據信息,內節點和根節點僅僅是用於快速定位,因此衍生出了合併前綴(prefix compression)以及刪除無用後綴(suffix truncation)等的優化方法。再舉個常見的優化示例,B+樹的頁節點原本用來存儲對應列值的行在數據文件中的相對位置,所以讀取完索引後還需要根據相對位置去數據文件中讀取數據。但對於固定的查詢語句,可以提前知道其他哪些列也會經常被查詢,把這些列的數據直接存儲在索引中,進一步用空間來省去讀取數據文件的時間。比如,如果我們想要更進一步優化下面這個語句:

SELECT sex FROM titanic_survivor WHERE age > 10;

就可以把性別的信息存放在索引中。對應的SQL語句如下

CREATE INDEX btree_idx_age ON titanic_survivor(age) USING BTREE INCLUDE (sex);

為了能夠進一步優化範圍查詢,我們引出了第二類索引,B樹索引。現在可以聊聊上面埋下的伏筆為什麼Postgres並不建議使用哈希索引了。貼出原文(From Postgres 7.2 Doc):

Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks.

可見,雖然從理論上講,對於點查詢,哈希索引應該更快,而且存儲空間相對B樹索引更少。但是通過工程中的優化,可以讓B樹索引在點查詢中也毫不遜色。聊完了哈希索引和B樹索引,留一個思考題給讀者:拋開性能不說,用B樹索引讀取數據還能帶來一個隱形的好處,猜猜是什麼好處?我會把答案留在本文的最後。

說了這麼多B樹索引的優勢,它有什麼缺陷嗎? B樹的實現,增加和刪除數據會牽涉到節點的分離和合併,是比較複雜的(沒有同學在面試過程中遇到要求實現B樹這類的變態問題吧)。尤其是在高並發的環境下,對於節點的操作需要加鎖, 會進一步導致速度變慢。有沒有辦法進一步改進嗎?有!有一種比較偏門的數據結構 – 跳表(skip list)比B樹在這方面就更優秀。跳表的實現是一個多層次的鍊錶,底部鍊錶和B樹一樣是一列有序的鍵值對,通過在上層加入更鬆散的有序鍊錶來支持跳躍查詢(命名的由來)。下圖給出了跳表示例。

數據庫內核雜談(三):索引優化 5

skip list

理論上的時間複雜度和B樹是類似的。但為什麼說跳表對於高並發更好呢,我自己的理解是因為在新增節點時,跳表通過一個概率值來決定是否需要添加上層節點,實現起來,變化比較局部,不會有B樹那樣牽一發而動全身的變化,所以無論是加鎖實現,還是無鎖實現都對高並發支持更好。如果想要了解更多,請各位同學自行查閱。跳表的另一個優勢在於實現中對於內存的需求相對於B樹更少。可能這也是為什麼內存數據庫MemSql就支持跳表索引。其實跳表也有缺點,因為是用鍊錶實現,所以對於緩存並不是很友好。另一個缺點是,要支持逆向查詢,比如(age < 40),這就需要用雙向鍊錶實現,複雜度也會更高。

總結一下,為了更好得支持並發操作以及內存優化,我們引入了跳表索引。

B樹索引還有哪些情況是不適用的嗎?現在假設我們要對性別或者艙位做索引,但這些列本來基數(distinct value cardinality)就非常小,B樹帶來的快速定位優勢就沒有意義了。有什麼索引是適合這類查詢嗎?引出我們今天最後的一類索引 – 位圖索引。

位圖索引專門針對基數很小的列來做索引。比如對於性別,我們可以生成下列的索引:

數據庫內核雜談(三):索引優化 6

sex bitmap index
在查詢時,只要讀取位圖為1的行即可。有些情況下,位圖索引也支持多條件查詢,比如針對下列查詢語句

SELECT * FROM titanic_survivor WHERE sex = 'female' AND cabin = 'A'

我們可以同時對sex和cabin做位圖索引,然後對sex:female和cabin:A進行位圖與操作再讀取結果為1的行即可。除此之外,位圖索引的另一大優勢在於,相對於其他索引,存儲需求很小:對於每個基數,每一行數據只要1bit的存儲。所以當列的基數很大時,位圖索引就失去意義了。位圖索引的另一個劣勢在於,不適用於高並發環境,因為任何修改和添加,都需要對索引文件進行加鎖。

針對基數較小的列,我們引入了位圖索引來提高查詢速度。

小結

數據庫索引是用來進一步提高查詢語句的速度。針對不同的數據環境和不同索引的優缺點,我們介紹了以下這些方法:

1) 引入哈希索引用來提高點查詢效率

2) 引入B樹索引用來提高範圍查詢

3) 針對B樹索引對高並發支持的詬病,引入跳表索引

4) 針對基數較小的列,引入位圖索引

使用索引時,可以對每個表創建一個或多個索引。讀者可能會有疑問,那豈不是對每個列都創建索引,就是萬事大吉了。答案是否定的。索引是否能夠提升效率,取決於查詢語句以及數據的分佈。而是否決定使用索引,是由數據庫的優化器(之後會有專門的章節介紹優化器)決定的。另外,天下沒有免費的午餐。首先,索引是冗餘的數據存儲,是要佔據內存和磁盤空間的。二,索引數據要和表數據同步,在對修改數據的同時,也需要同步更新索引。如果索引太多,會大大降低數據導入和修改的吞吐量(可以在Postgres中做小實驗,在有和沒有索引的情況下,導入數據的時間相差甚遠)。工程實踐中,一般會在數據更新操作全部完成以後,再對錶建索引。如何正確創建的索引,是原先DBA的工作;一個有經驗的DBA,能夠根據查詢需求創建最高效的索引。在越來越智能的數據庫時代,很多數據庫已經可以根據查詢語句的類型,來提供創建索引的建議,畢竟沒有數據庫比數據庫本身更懂自己!

下面揭露思考題答案:用B樹索引讀取數據的另一個好處是什麼?那就是讀取的數據針對索引列是排過序的。這可是一個非常好的特性,假設查詢語句中本來就有排序需求(SQL關鍵字ORDER BY), 就不用再對數據進行排序了。另外有序列對於數據表的聯合(join),以及聚類(aggregation)都很有幫助,這些我們留到以後再介紹。

作者介紹:

顧仲賢,現任Facebook Tech Lead,專注於數據庫,分佈式系統,數據密集型應用後端架構與開發。擁有多年分佈式數據庫內核開發經驗,發表數十篇數據庫頂級期刊併申請獲得多項專利,對搜索,即時通訊系統有深刻理解,愛設計愛架構,持續跟進互聯網前沿技術。

2008年畢業於上海交大軟件學院,2012年,獲得美國加州大學戴維斯計算機碩士,博士學位;2013-2014年任Pivotal數據庫核心研發團隊資深工程師,開發開源數據庫優化器Orca;2016年作為初創員工加入Datometry,任首席工程師,負責全球首家數據庫虛擬化平台開發;2017年至今就職於Facebook任Tech Lead,領導重構搜索相關後端服務及數據管道, 管理即時通訊軟件WhatsApp數據平台負責數據收集,整理,並提供後續應用。

相關閱讀:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫

數據庫內核雜談(二):存儲“演化論”