從Indexing的角度切入MySQL-Innodb與PostgreSQL的效能比較

如果你用的資料庫是屬於 Relational Database ,在這個年代用SQL進行資料庫的存取已經變成一件理所當然的事了。MySQL 、PostgreSQL 、MsSQL…不論是開源抑或是由大廠主導的 SQL 專案都擁有各自的擁護者 。

其實如果單純以使用與操作的角度去這些不同的資料庫的官網和 document 看過一圈,可能不太容易看出有什麼關鍵性的差異。然而儘管這些資料庫在表面上看起來都提供了類似 Function ,但是對於同樣的一個邏輯, 不同家的資料庫之間的底層的物理實作卻有不少大相徑庭的地方。

這篇文章想要以 MySQL (在本文中所參考的儲存引擎為 innodb ) 和PostgreSQL 為例,來討論一些 Relational Database 在底層操作資料時的一些基本原理。 更確切地說,從DB系統管理Index的方式來切入。

# Indexes : 決定資料存取速度的關鍵

首先來談談 MySQL 和 PostgreSQL 在資料儲存上最關鍵的差異 : Indexes 。

網路上的教學都會說, 對於 table 中經常需要用來當作查詢依據的 column ,把它設成 index 速度就會提升。這背後的原因是因為對於資料庫背後儲存資料的 Data structure 來說 ,被選為 Index 的 Column 就會成為資料結構中的排序依據。

“假設”某個資料庫背後是用 Binary Tree(實際上通常是 B-Tree 的各種延伸版本)來當作核心資料結構的話,一筆資料的 row 就是一個 node。 那例如說在下圖的資料結構,一筆資料會有Name、Height、id 三個欄位,那當我們把欄位 “ id” 設為 index的話 ,這棵樹(也就是資料庫存放資料的結構)就會照著 id 的值來排序。

看到這裡有自己設計過 DB Schema 的朋友們可能就會好奇,

“咦但是有時候我同一張 table 裡面會有好幾個 column 會設成 index 耶

那這樣資料庫要以哪個為基準排序啊?”

在討論這個問題前我們必須先瞭解兩個概念:clustered index 和 non-clustered index。

# Clustered Index 與 Non-Clustered Index

如果要用一句話概括說明這兩者的差異,可以說 Clustered Index 是“完整資料(包含所有 column)在 Storage 中實際上的排序依據 ” 而 Non-clustered Index則是 “跟完整資料分開來放的欄位子集合的排序依據”。

說得白話一點就是完整的資料在 storage 裡面用 clustered-index 當作排序依據, clustered-index 相近的資料在 storage 中也會在比較接近的位置。 且因爲他是實際上 storage 在 partition 資料時的依據,所以只能有一個 clustered index。

而資料庫會另外複製幾份被使用者選為 non-clustered index 的 column 資料, 在其他 storage 的空間創造只包含這些 non-clustered index 的資料結構。每多一個 index 就多創造一份。而這些 non-clustered index 跟實際上 storage中的資料的物理位置沒有直接的關連。

以上面的例子為例, id(預設是 Primary Key)就是 clustered index ,而如果使用者在 name 和 height 上都 create index 的話(預設狀況 create 新的 index 就是 non-clustered index),資料庫會創造出額外的兩份複製的子集合資料結構。


這兩個新的 tree 分別各自以不同的 non-clustered index 進行排序.。當使用者要查詢資料時, 資料庫就會從判斷指令中的條件使用的欄位是否是有被設為index 的欄位,有的話就會從對應的 tree 裡面尋找。

例如下 SELECT * WHERE Height > 165 ,資料庫不會從圖一中原本包含完整資料的結構中尋找, 而是會從複製出來的圖二的結構中尋找對應的 node。

然而眼尖的朋友可能發現, 如果是**SELECT ***的話,就算在圖二的 tree 中找到了需要的 nodes,裡面也沒有包含其他欄位的資料讓我回傳啊!

一個可能的解法是在 create index 時下INCLUDE clause ,可以讓資料庫在創建新的 non-clustered index tree 時把被 include 的欄位資料一起放進去。 但是如果 table 中的欄位很多,那這樣每次要 create 新的 index 時創造出來的新的tree 就會無敵大,對 storage 是一個大負荷。

所以實際上除了用 clustered index 排序的原本資料外,這些額外的 index tree的節點都還包括了一個 field,放的正是 clustered index。 例如圖二以 height 當non-clustered index 的 tree 中實際上會有額外對應的 clustered index (此例中也就是 id )

SELECT * WHERE Height > 165這個指令在查詢時就會變成先從此樹中找到符合條件的node,再用對應的clustered index(id)去圖一中的樹查詢。

以上這個流程就是 MySQL-Innodb 中用 index 加速資料查詢的流程和原理

看來很完美! 收工~

..

……

然而現實總是殘酷的, 這樣的流程有個潛在的大問題。

先從 non-clustered index 取得 clustered index 再去查詢,看起來只是從查詢一次變成兩次而已, 然而實際上如果進行非常大範圍的Range Query, non-clustered index一個range中對應的clustered-index資料在實際硬碟的存放位置是非常散亂的,這個查詢clustered-index tree的步驟會在Storage中發生非常巨量的Random Access,效能的大幅下降是可以預期。

如果我們想要 Select 全部的欄位,但是卻不想要回去 clustered-index tree 裡面查詢, 有辦法嗎?

# PostgreSQL的解法:

PostgreSQL看到了 MySQL-Innodb 中這樣的痛點, 所以在設計上採取了一個策略 : 不使用 clustered index tree。

沒有 clustered index 意味著的就是完整的原始資料無法進行排序(因為沒有排序的依據) 在 PostgreSQL 的中存放完整資料的地方稱之為 Heap。 這個Heap 是個無序的結構,每一筆資料存在 storage 中是不給予這些資料順序任何的保證的。

而 non-clustered index 的部分,,PostgreSQL 則是從在每個 node 裡面儲存Clustered-index,改成儲存一個指向 Heap 中對應完整資料的 row 所在位置的指標. (注意此處的指標不是 memory 的指標,而是用來在資料庫中標記唯一所在位置的 Page 的資訊) *

看到這裡可能會有人想問,“那為何 MySQL不也直接在 Non-clustered index tree的 node 中存放指標就好了?

這點也正是 PostgreSQL 以 Heap 存放原始完整資料的主要原因. 因為 Heap 不保證資料順序,所以任何資料被 update 或 insert ,現有的其他資料都不需要變更存放的位置, 相較之下 Innodb 因為是依照 clustered index 來排序,任何資料的 clustered index 被更改或插入新的資料都會造成其他資料的存放位置依照index 發生相對應的變化。
(以 B-Tree 來說, 會為了維持 tree 的 balance 而發生樹的結構的變化,因為clustered index 必須反映實際物理位置,所以 clustered index 順序更新必須同時更新 disk 中的資料位置, 造成大量的時間消耗)

正是因為資料位置的不變的特性,讓 PostgreSQL 的指標實現成為可能。所以在PostgreSQL 中,用 Non-clustered index 查詢資料,不需要再跑去 clustered index tree 裡面查詢,直接拿指標位置去 storage 裡面對應的 Page 取出資料即可。

然而這樣的設計並非沒有 Trade-Off 的。

儘管在用 Non-clustered Index 進行 SELECT * 之類的查詢時會因為少一次tree lookup 而有效率上的提升。但因為這種實現方式完全捨棄了 clustered-index,所以如果是用 primary key(以Innodb 來說就是 clustered index ) 來查詢, 反而會多了一個用指標查詢的步驟。

且因為 Heap 沒有辦法保證任何資料在物理上的 Locality(在前面提過, clustered index 才有辦法保證 index 跟 storage 中物理位置的相似性),所以無法像 MySQL-Innodb 一樣以 clustered-index 進行 Range Query 時有Locality的優勢。

綜上所述,我們大致可以把這兩種資料庫實現Indexing的方式用以下幾點歸納:

以剛剛包含了 id、 Name 跟 Height 的 table (person) 為例 :(當然以下的前提都是資料的 rows 非常非常多的狀況,且我們把 id、Name、 Height 都 create Index)

SELECT p.*
FROM person p
WHERE p.Height < 170;

對這樣的指令來說, 因為要 Select 全部的欄位, 而查詢條件是 non-clustered index, 所以根據我們前面所說,因為 MySQL-Innodb 還必須去 clustered index tree 裡面搜尋一遍,是可以預期 PostgreSQL 是比較快的。

SELECT p.*
FROM person p
WHERE p.id > 18;

這個指令,儘管要 Select 全部的欄位,但因為 id 是 clustered index, 用id來當作查詢條件時對 Innodb 來說就直接在 clusterd index tree 裡面搜尋了,找到就可直接回傳。而對 PostgreSQL 來說因為id仍然是 non-clusterd index (跟 Heap 分開的), 所以 PostgreSQL 反而還會多了一次用指標去資料庫把資料撈出來的步驟。 因此這樣的操作是可以預期 MySQL 是有優勢的。

SELECT p.Name
FROM person p
WHERE p.Name = "David";

至於這個指令,因為要回傳的 column 就是 non-clustered index,所以不論是Innodb 還是 PostgreSQL 都只要在查詢 non-clustered index tree 時直接回傳Name 就好了, 跟 Clustered Index tree 和 Heap 都沒關係,所以兩者的資料儲存方式不同不會讓這樣的查詢有太大效能差異。

# 結論 :

一般來說如果用 Primary Key 來查詢時,因為 MySQL-Innodb 是用 Clustered-index, 所以速度較快,尤其在進行 Range Query 時因為 clustered-index在Storage 中的 locality,所以速度會大幅提升。

而如果是需要經常對不同欄位進行檢索的 Table, 因為 PostgreSQL 在 non-clustered index 的資料結構的節點中有直接存放實際資料的位置,所以速度會比起要再次去 clustered index 資料結構查詢的 MySQL-Innodb來的快。

另外,當要 select 的欄位全部都被 include 在 non-clustered index 的資料結構中時,理論上兩者的效率便不會有太大的差別。(不過, INCLUDE clause只支援 PostgreSQL11 以後的版本,因此如果 PostgreSQL 沒有 INCLUDE 的話Innodb 還是會快一些的)

更多同分類文章

隨機推薦

  1. 基於 JS 原型鏈的攻擊手法:Prototype Pollution
  2. 不識廬山真面目:Clickjacking 點擊劫持攻擊
  3. 關於 email security 的大小事 — 設定篇 SPF
  4. 淺談 XSS 攻擊與防禦的各個環節
  5. 隱藏在 React 下的機制: Fiber