* 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.
