original article: https://xiang753017.gitbook.io/zixiang-blog/database/relation-database-index-overview

Relation Database Context

Relation Database 的資料結構稱 page，key 指的是一個 row 的 unique key，而 Row 是指記憶體位置。Pages 是以 B-Tree 儲存，

1. Non-Leaf 的 Page 會是指的是 index 而這樣的 row 會指設到下一個 Non-Leaf 的 Page 或者 Leaf-Page
2. Leaf Page 指的是實際的 table row
   

• How Do Database Retrieve data?

在資料庫在讀取資料的時候，要找所對應的page 且輸出給 user。而實際的 activities 如下圖[1][2]：

1. Read Cache: 從cache 取得 page，時間約 0ms
2. Read Buffer: 從 buffer queue 取得時間約 3 ms
3. Read Disk: 從 disk 取得所要的pages
   3.1 Random Read: about 0.1 MB/s到0.5 MB/s usually use in specific search ex: where a = :a
   3.2 Sequential Read: about 40 MB /s. usually use in range search ex: where a > :a
4. Rotate Buffer: 對buffer 進行更新
5. Store cache: 更新cache

以 2005 年[1]當時候的硬體，若從 disk 找到資料 Random read 約 10ms的時間，
現今2025 年 SSD 讀寫速度： Random Read 約500 mb/s, Sequence Read 8000mb/s

• What is the Pre-Fetch in RDBMS?
  Pre-Fetch 的意思是指在搜集需要的資料的時候，當找到全部 hit 到 index之後再進行 Retrive data，可參考下圖; 反之沒有Pre-Fetch 就是當Scan 一個 index 之後直接去 retrieve 資料，變成是 sequence 的方式。
  

Index Perfomance Factories

在資料庫中 Index 是用來加速讀取使用，index 的原理是以比較小的資料集合 reference 比較大的資料集合; 換句話說，以部分資料來 reference 完整資料。 而在讀取 Index pages 因為量體比較小，利用 memory 速度快於 disk 的優勢快速的找到 table pages.
影響讀取速度的關鍵在於：使用 Random Read & Sequence Read 的次數 (速度比為 Random Read : Sequence Read = 1 : 15)

以參考資料[2]的基本假設作為以下舉例，分別的讀取速率為：

1. Random Read: 10 ms
2. Sequence Read: 1 ms
3. Fetch Data: 0.1 ms
   Example Table 有五個欄位 id 為 primary key

CREATE TABLE example_table (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100),
    created_at TIMESTAMP,
    status BOOLEAN
)

E.q. 1

-- total 1,000,000 rows
select * from  example_table where id = :id

Explain:

1. db 使用 random read 讀取 pk index
2. db 使用 random read 讀取 table row
3. db fetch data
   Total 時間為： 10ms + 10ms+ 0.1 ms 約 20ms

E.q. 2

-- total 1,000,000 rows
-- hit rate 1% = 100,000
select * from  example_table where name = :name

Explain:

1. db 使用 sequence read 全區域搜尋，共有 1% 的命中率 (100,000 rows)
2. fetch rows:

Total 時間為： 1 ms * 1,000,000 + 100,000 * 0.1 ms = 1000s + 10s = 1010 s

E.q.3

-- total 1,000,000 rows, 
-- index (name, id)
-  hit rate 1% = 100,000
select id, name from  example_table where name = :name

Explain:

1. db 使用 random read 讀取 index
   Total 時間為： 10 ms

因為 index 已經包含需要fetch 的資料，因此並不需要去取得 table 資料
index 是具有順序性的 (name, id) 會從 name 開始搜尋再往下到 id, 因此 index = (id, name) 則在上述無法hit 到 index

E.q.4

-- total 1,000,000 rows, 
-- index (name, id)
-  hit rate 1% = 100,000
select * from example_table where name = :name

Explain:

1. db 使用 random read 讀取 index
2. db 使用 random/sequence read 讀取 table row
3. 使用 random/sequence read 取決於資料相鄰的程度，
4. 相鄰 seq read; 不相鄰 random read
5. db fetch data
   Best case Total 時間為： 10ms + 100,000 * 1ms + 100,000 * 0.1 ms = 10ms + 100s + 10s = 110 s
   Worst case Total 時間為：10ms + 100,000 * 10ms + 100,000 * 0.1 ms = 10ms + 1000s + 10s = 1010s

Index Design

Build A Index Cost

[2]Index 加速的原理，主要是有效的減少需要搜尋的量體，近一步減少在搜尋的 I/O time。但是建制 Index 會在 Create/Update/Delete 的時候消耗寫入的速度。

一般來說 index 都是以 Random wirte 進行寫入，在傳統的 HDD 中大約 10 ms ; SSD 則是約 0.1 ms，換句話說，以HDD為例有10 個 index 要進行插入，則會需要 10 * 10 ms 約 100 ms。
此外在高速寫入下，也會造成 disk 的本身的負擔劇增，導致系統性地被拖累
以下提供 rule 作為評估的一個標準[2](page 60):

1. N: the number of indexes with random inserts
2. I = insert rate (table rows per second)
3. D = the number of disk drives (excluding spares)
   L = N * I/D; if L < 1 則幾乎不會有影響; 1 < L < 10 則大概已經會有影響disk 的效率; L > 10 則會高頻率的造成問題

How many stars of index are reasonable?

Star 的意思是指，以多少的 col 組成的 index。舉個例子，a col 與 b col 組成的 index 稱之2 star index。其中超過 3 個含以上的 col 組成的index 稱之為 3 star index or Fat index

• 2 Star index is more reasonable compare with 3 star or Fat index
  根據index 的原理，index 加速主要是依靠量體小的優勢，利用 memory 速度，能快速找到 table page. 因此index 如果越接近於 table 的 col 數量，就越趨近於在進行 full scan 的意思。 index 本身加速依靠 hit rate, 3 star 的 index 本身的利用率其實不高，因為 index 本身搜尋有順序性的限制。 ex index (a, b) 這一組index 能使用的狀況只有在 搜尋 包含 a or a+b 這兩個狀況。所以 3 star index 命中率低且額外的消耗 Create/Update/Delete 成本，並不一定划算。

Index 對於Join 的影響

Join 主要的兩種方式為 Hash Join & Nest-loop Join ，從時間複雜度的角度分別為 O(N+M), O(N*M)，而 index 在 merge 的步驟，實際上會直接使需要 merge 的量體變小，而考慮到 I/O time 的話，未必 index 能夠有效的優化效率。因此在 SQL 的 Search plan 會依照可能的 index hit rate 選擇較佳效率的做法，未必會全然使用 index

Example:
以參考資料[2]的基本假設作為以下舉例，分別的讀取速率為：

1. Random Read: 10 ms
2. Sequence Read: 1 ms
3. Fetch Data: 0.1 ms

-- orders has prouducts.id FK
-- order has 10,000,000 rows, products has 20,000,000
select * from orders o, products p where o.product_id = p.id and p.price  = 305.65

• Eq.1 products.price is a index, hit rate high

1. index hit rate 極高，假設 p.price = 305.65 只有 10筆 hit
2. 製作 order hash table 約 10,000,000 rows 且塞選符合( o.product_id = p.id ) 使用 sequence read with 3 workers
3. Merge

Total= 10ms + 10* 10ms + 3,333,333 * 1ms = 10 + 100ms + 3,333s = 3333s

• Eq.2 products.price is a index, hit rate low

1. index hit rate 不高，假設 p.price = 305.65 只有 100,000筆 hit
2. 製作 order hash table 約 10,000,000 rows 且塞選符合( o.product_id = p.id ) 使用 sequence read with 3 workers
3. Merge

Total= 10ms + 100,000* 10ms + 3,333,333 * 1ms = 10 ms+ 1000s + 3,333s = 4,333s

• Eq.3 products.price search by sequnce read

1. 10,000,000 rows at p.price = 305.65 with sequence read
2. 製作 order hash table 約 10,000,000 rows 且塞選符合( o.product_id = p.id ) 使用 sequence read with 3 workers
3. Merge

Total= 10,000,000 * 1ms + 3,333,333 * 1ms = 10,000s + 3333s = 13333 s

Performance Tuning

1. Index 成本非常高，建制的時候依靠 random write, 讀取 index 通常會使用 random read. 當 filter 搜尋到 raw table 之後大部分情況可能使用 random read + sequence read 取得資料，取決於資料相鄰的程度。

2. 思考該 SQL 語句以及使用情境會需要返回多少資料量，進一步推算 index 設計是否合理
   a. 考慮該 SQL 所下的 filter 適合哪一種搜尋，再進一步設計 index. ex 當語句是屬於大範圍搜尋且返回資料大的情況下，則未必需要設計 index，因為如果 db 絕大部分使用 random read，有可能實際的速度比 full scan 來得慢，亦或者db 直接使用 full scan 而 index 反而成為拖慢 db 寫入速度
   b. Join 的原理，原則上是會拆成小 table 進行 full a 找 b 表的行為，考慮到 I/O 實際需要經過的資料集，進行 index 設計，或者不使用 Join 搜尋。ex 當 a,b 表都具有 1000 萬的資料量，當執行 hash Join , db 會先將比較小的資料集 進行一次 filter 並建立 hash table，在對比較大的資料進行一次 full scan and filter. 在這種情況下，index的作用未必有顯著效果。

3. 須監控 SQL 的效率，找出 low sql 在近一步討論 index 是否合理，或者 SQL 是否為最佳。

Reference

[1] https://dev.mysql.com/doc/refman/8.4/en/innodb-buffer-pool.html
[2] Lahdenmaki, Tapio, and Mike Leach. Relational Database Index Design and the Optimizers: DB2, Oracle, SQL Server, et al. John Wiley & Sons, 2005.