---
description: '從底層簡介關聯性資料庫 I/O 讀取的原理，詳細分析 index 是如何運作。 #RDBMS #index'
---

# Relation Database Index Overview

### Relation Database Context

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

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

<figure><img src="https://853423727-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MZBn9owI5fBe0HrECdk%2Fuploads%2FDxDWHxGjNMbKYUQ9fN1W%2Fimage.png?alt=media&#x26;token=c1d77ec8-0c3b-48ba-96be-b9fcc8d94ea9" alt=""><figcaption><p>ref:  <a href="https://www.pragimtech.com/blog/sql-optimization/how-do-sql-indexes-work/">https://www.pragimtech.com/blog/sql-optimization/how-do-sql-indexes-work/</a></p></figcaption></figure>

* 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

{% @mermaid/diagram content="stateDiagram-v2
    state is_end <<choice>>
    is_end --> [*]
    state is_read_cache <<choice>>
    is_read_cache --> is_end: found in cache (0ms)
    state is_read_buffer <<choice>>
    is_read_buffer --> store_into_cache: found in buffer
    store_into_cache --> is_end 

    [*] --> Read_Cache
    Read_Cache --> is_read_cache
    is_read_cache --> Read_Buffer: not found in cache
    Read_Buffer --> is_read_buffer
    is_read_buffer --> Read_disk: (4ms)
    Read_disk --> Rotate_buffer: (random or sequential read)
    Rotate_buffer --> is_read_buffer: (1ms)" fullWidth="false" %}

* What is the Pre-Fetch in RDBMS?

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

<figure><img src="https://853423727-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MZBn9owI5fBe0HrECdk%2Fuploads%2F1x9QZIu6NBAy8m0W5okm%2Fimage.png?alt=media&#x26;token=f4055001-33c2-4267-b005-d222bb242890" alt=""><figcaption><p>ref:[2] figuer 2.7</p></figcaption></figure>



### Index Perfomance Factories

在資料庫中 Index 是用來加速讀取使用，index 的原理是以比較小的資料集合 reference 比較大的資料集合; 換句話說，以部分資料來 reference 完整資料。 而在讀取 Index pages 因為量體比較小，利用 memory 速度快於 disk 的優勢快速的找到 table pages.&#x20;

影響讀取速度的關鍵在於：**使用 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,

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

E.q. 1&#x20;

```sql
// 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&#x20;

E.q. 2

```sql
// 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)&#x20;
2. fetch rows

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

E.q.3&#x20;

```sql
// 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&#x20;

```sql
// 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 則會高頻率的造成問題&#x20;

#### 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 能夠有效減少  table 建置成本，而考慮到 I/O time 的話，未必 index 能夠有效的優化效率。因此在 SQL 的 Search plan 會依照可能的 index hit rate 選擇較佳效率的做法，未必會全然使用 index

```sql
// 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
```

Example: 以 Postgres Parallel Hash Join 為例：

1. DB 會將  p.price  = 305.6 先進行一次 filter，若有index 則會使用index 建立 hash table
2. 進行 o.product\_id = p.id 比對（此時為 full table scan，並且會以平行處理的方式進行）
3. 再進行merge

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

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

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 設計是否合理
   1. 考慮該 SQL 所下的 filter 適合哪一種搜尋，再進一步設計 index. ex 當語句是屬於大範圍搜尋且返回資料大的情況下，則未必需要設計 index，因為如果 db 絕大部分使用 random read，有可能實際的速度比 full scan 來得慢，亦或者db 直接使用 full scan 而 index 反而成為拖慢 db 寫入速度
   2. 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](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.
