MySQL(MariaDB) InnoDB Clustered Index & Secondary Index

2021 年 9 月 2 日

每每到了懷疑自己的時候就會開始寫文章記錄一下，這大概是一個循環吧。

前陣子直接被這標題的問題考倒了，所以就花一些時間了解一下，這才發現其實有很多東西我只看到了表層，卻沒有深入去瞭解他的原理。而且還是這種很常用的東西，總之是該檢討一下。稍微瀏覽了一遍，留下一些筆記方便以後可以複習。

我認為在了解完這個term之後，能夠幫助我們更有效地知道該如何建立Index，甚至去比較該選擇哪一套資料庫來達到最佳化的效益。

B+tree

在了解clustered index前我們要先知道在資料庫中indexing的基本結構，大部分常見的資料庫（MySQL, PostgreSQL, Oracle）的indexing預設都是以B+tree的結構進行儲存及排序，這樣能夠有效地減少在查找資料時間複雜度，反正就是樹的查找，所以可以只需要樹的高度的時間。而樹的深度（以有十億多個rows的table來舉例）大概會被控制在5層左右(The Depth of B-tree)，能讓I/O讀取的時間減少到只有5次左右。

更棒的是，我們還可以假設前3層non-leaf node(page)通常都會被放在cache中，讓我們的query更只需要1~2個I/O讀取就能夠達成了。

https://dba.stackexchange.com/questions/155945/b-tree-structure-with-buckets-begginer-question

Index Organized Tables (IOT) & Heap Table

除了B+Tree以外，不同種DB的indexing的儲存機制還是有些許的不同，這邊會以兩個較常見的種類來做說明，MySQL的InnoDB是使用IOT，而PostgreSQL是使用Heap Table。

Index Organized Tables

https://www.spirithy.com/2019/11/18/innodb-index-and-slow-sql/

簡單地來說這種儲存方式就是會建立一個B+Tree，並把整筆完整資料並按照順序存在Leaf Node(Page)上。用上圖來舉例，Col1是PK，B-Tree會用Col1去排出整個樹，在最後的LeafNode上把Col2, Col3其餘的資料都放在上面。因為每個LeafNode都有一個指標會指向下一個順序的LeafNode，在做range的query的時候，只要找到最小的Node就可以一直找到最大的了。

使用這種機制的優點在於（相對於Heap Table）：

像上述所提到的能夠對PK直接用range的方式把一個範圍的資料直接傳回
對Page只需要一次I/O讀取就能夠完成取得資料

而缺點：

當tree的leaf進行merge跟split的時候會物理性的移動Leaf Node上的實際資料
因為一個Page(Node)上會儲存多個有順序性的資料，很容易發生讀寫同時在同一個Leaf Page上，導致一些競爭的情形出現。

Heap Table

https://juanignaciosl.github.io/postgresql/2016/06/04/sql-performance-explained-cylicon-valley.html

Heap Table的儲存方式在做Indexing的時候其實跟IOT是一樣的就是用B-Tree，但他的資料並沒有存在Tree的Leaf上，取而代之的是只有指標而已，這些指標指向另一個資料結構中的該筆資料，而這個資料結構就稱為Heap Table——這裡的Heap跟那個做priority的那個Heap是不同的東西，在這所說的只是一個用來做亂數儲存的結構——在Heap Table中的資料並沒有順序性，而是隨機儲存的。

使用Heap Table的優點有（相對於IOT）：

資料在進行merge或split的時候，因為在leaf上並不是存著整筆資料，所以只需變動樹的結構，Heap Table是保持不變的，移動的只有指標，減少了不少物理性的移動。
因為實際資料是隨機性的散落在Heap Table的各處，所以發生競爭某個page的情形會減少

缺點的部分：

在做range query的時候不像IOT可以直接把資料返回，而是要經由指標去一個一個從Heap Table中找出來，所以基本上他多做了一次讀取的動作。

MySQL (MariaDB) InnoDB Clustered Index

說了那麼多，終於來到重頭戲了。Clustered Index我認為它所代表的比較是儲存跟查找的方式而非單純indexing。（這邊要特別註明是InnoDB，因為MySQL的另一種Engine是用Heap Table來做儲存的）

而InnoDB所使用的儲存機制就是上面所提到的IOT，而每個table的clustered index也只會有一個，因為會用來儲存所有實際資料。clustered index的key通常就是我們所謂的primary key。但如果你沒有選出PK的話，照Mysql的manual所描述的。(Clustered and Secondary Indexes)

- When you define a PRIMARY KEY on a table, InnoDB uses it as the clustered index. A primary key should be defined for each table. If there is no logical unique and non-null column or set of columns to use a the primary key, add an auto-increment column. Auto-increment column values are unique and are added automatically as new rows are inserted.

- If you do not define a PRIMARY KEY for a table, InnoDB uses the first UNIQUE index with all key columns defined as NOT NULL as the clustered index.

- If a table has no PRIMARY KEY or suitable UNIQUE index, InnoDB generates a hidden clustered index named GEN_CLUST_INDEX on a synthetic column that contains row ID values. The rows are ordered by the row ID that InnoDB assigns. The row ID is a 6-byte field that increases monotonically as new rows are inserted. Thus, the rows ordered by the row ID are physically in order of insertion.

使用PK
使用第一個所有key column都為NOT NULL的unique index
如果兩者都沒有，InnodDB會自己產生一個並把他藏起來。

這樣的儲存方式就像前面提到的，可以把有順序性的資料照著他們的順序來儲存，且照順序寫InnoDB能讓每個page的儲存空間達到他最大的效益。（參照15.6.2.2 The Physical Structure of an InnoDB Index）

When new records are inserted into an InnoDB clustered index, InnoDB tries to leave 1/16 of the page free for future insertions and updates of the index records. If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.

照上述：

資料如果基本上都照順序寫入，它能夠讓一個page保持在15/16滿。
但如果資料是隨機寫入的，page的使用空間會在1/2~15/16的範圍內，這樣可能會造成空間上的浪費。

至於查找方式，我就用下圖來舉個例子，這是一張非常簡單的table。

http://www.geekphilip.com/2013/06/14/clustered-indexes-vs-non-clustered-indexes/

CREATE TABLE test_table(    id   INTEGER PRIMARY KEY,    name VARCHAR(100));

假如要查找id = 25的value的時候

SELECT * FROM test_table WHERE id = 25;

他會從B+tree的最上面照著每個condition去做查找，用上述的圖來做說明他會從最上層然後一路往下到第一個Leaf Page上去找到他要的資料。

但假如這時候我們要找的是

SELECT * FROM test_table WHERE name = "Frog";

這時候他就不會用到index了，他會從第一個leaf page一直找一直找直到找到他想要的資料，雖然上面的圖只有四個pages，但如果這時有上百個pages甚至更多時，而且很不幸地你要找的資料在最後一個Page，這時候你就會開始覺得『這query怎麼那麼久啊。』

然後這時候就會說：『好吧，我們來見個index好惹。』

MySQL (MariaDB) InnoDB Secondary Index

是的，平常我們在用InnoDB所提到的這裡要不要建個index，通常就是指這個。他跟Clustered Index不一樣，一張table可以建立64個，且另一點更重要的是，他在最終的Leaf Page上儲存的東西不是整個資料，而是你建立index時所指定column的值以及該筆資料的PK。

How Secondary Indexes Relate to the Clustered Index

Indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.

If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.

另外secondary index最重要的東西就是他查找資料的方式了，當我們要找的column不包含在index中時，InnoDB會用存在index page上的pk回去clustered Index中查找到特定row的資料。

我們用下面的圖還有一些query來做個說明，這是張有指定PK且有另外建立index的Table。

CREATE TABLE test_table (    id INTEGER PRIMARY KEY,    name VARCHAR(100),    amount INTEGER,    INDEX(amount));
INSERT test_table VALUES (1, "Cat", 10),(2, "Dog", 2),(3, "Fish", 3),(4, "Cow", 6),(5, "Bird", 5),...,(10, "Bear", 9);

所以他會有一個長這樣的clustered Index。（實際長出來可能不是這樣，只是簡單示意而已）

以及這樣的Secondary Index。（實際長出來可能不是這樣，只是簡單示意而已）

當我們下了這樣的Query，並用EXPLAIN來看一下他實際query時使用到的東西。

EXPLAIN SELECT id,amount FROM test_table WHERE amount < 5;

可以看到在Extra的部分有出現possible_keys是amount，也就是我們另外建立的Index，另一個更重要的是在Extra的部分顯示 ”Using where; Using Index”。Using Where可以先不用理他，重點是Using Index。

- Using index (JSON property: using_index)

The column information is retrieved from the table using only information in the index tree without having to do an additional seek to read the actual row. This strategy can be used when the query uses only columns that are part of a single index.

For InnoDB tables that have a user-defined clustered index, that index can be used even when Using index is absent from the Extra column. This is the case if type is index and key is PRIMARY.

也就是說當它顯示Using Index的時候表示他只需要從Index就能找到我們所需要的東西，沒有必要再回到clustered index找。也就是說他搜尋的步驟是這樣。

那我們來實驗看看讓他回傳all的EXPLAIN會有什麼結果。

EXPLAIN SELECT * FROM test_table WHERE amount < 5;

Using Index消失了，因為這個query需要用到沒有包含在index內的name，所以他用index找到我們要的值以及對應的pk，之後回到clustered index裡去查詢他的資料。他的查詢步驟會是這樣。

這樣的查找有什麼問題嗎？其實要說沒問題也是可以吧，這就是一種trade off吧，如果我們把所有欄位都存在index裡的話，會導致這個index變得十分臃腫，所以會讓我們在寫入進去花更多的精力在維護這個index，這就表示要花更多的時間去做寫入。我們能做的事情就是儘量去減少回傳所有欄位的值的查詢，也就是儘量不要使用SELECT *且明確知道我們所需要的欄位。

像在這邊的話，假如amount跟name常常會一起需要回傳的話我們可以把(amount, name)放在一起做一個compound index（雖然這邊只有兩個欄位，但實際上可能這是一個有很多欄位的table）可能會是種解法，但這又是另一個話題惹。

其實這時候我們還有另外一個思考角度，也就是前面提到IOT的另一種儲存形式Heap Table。

在Postgresql中是使用Heap Table來做儲存的，所以他不會被clustered index所侷限。而是所有index都跟secondary index類似，index的page只儲存指定欄位的值以及heap table的指標。也就是說他減少了用pk再回去查找clustered index的這個步驟，可以直接到heap table拿到所有資料，減少了一些查找的動作。懶得再製一張圖，就用這張圖來想像吧，反正裡面不是存key的值而是heap table的指標，所以就可以直接拿到想要的資料不用再重新回到clustered Index做一次查詢。