Relation Database Index Overview

從底層關聯性資料庫IO讀取的原理，詳細分析index 是如何運作。 #RDBMS #index

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

ref: https://www.pragimtech.com/blog/sql-optimization/how-do-sql-indexes-work/

• 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

   1. Random Read: about 0.1 MB/s到0.5 MB/s usually use in specific search ex: where a = :a

   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 的方式。

ref:[2] figuer 2.7

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

   1. 使用 random/sequence read 取決於資料相鄰的程度，

   2. 相鄰 seq read; 不相鄰 random read

3. 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 約 3,333,333 rows (n log n) 使用 sequence read

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 約 3,333,333 rows (n log n) 使用 sequence read

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 約 3,333,333 rows (n log n) 使用 sequence read

3. Merge

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

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.