* 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 <>
is\_end --> \[\*]
state is\_read\_cache <>
is\_read\_cache --> is\_end: found in cache (0ms)
state is\_read\_buffer <>
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 的方式。
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,
```sql
CREATE TABLE example_table (
id INT PRIMARY KEY,
name VARCHAR(100),
email VARCHAR(100),
created_at TIMESTAMP,
status BOOLEAN
)
```
E.q. 1
```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
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)
2. fetch rows
Total 時間為： 1 ms \* 1,000,000 + 100,000 \* 0.1 ms = 1000s + 10s = 1010 s
E.q.3
```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
```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 則會高頻率的造成問題
#### 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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://xiang753017.gitbook.io/zixiang-blog/database/relation-database-index-overview.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.