---
tags: Series PostgreSQL
---

# 003: Hiểu về Index để tăng performance với PostgreSQL P2

Bài viết nằm trong series [Performance optimization với PostgreSQL](https://hackmd.io/@datbv/rk74QmqFd).

Với bài trước, ta đã biết các loại **index** phổ biến trong Relational Database:
> - B-Tree index.
> - Bitmap index.
> - Hash index.

Và một số loại **index** đặc biệt trong PostgreSQL:
> - GiST.
> - SP-GiST.
> - GIN.
> - BRIN.

Om hơi lâu suốt từ bài 1 rồi :joy:, bài viết hôm nay sẽ tìm hiểu về **B-Tree index**.

## 1) B-Tree index (Balanced Tree index)

### 1.1) What
Binary Tree và Binary Search Tree, rất quen thuộc và phổ biến. B-Tree index sử dụng cấu trúc dữ liệu Binary Tree để lưu trữ và BST thực hiện việc tìm kiếm. Nó có một vài tính chất sau:
- Phổ biến và được dùng nhiều nhất trong các loại index.
- Sử dụng khi số lượng các giá trị không lặp lại (distinct value) của cột nhiều (high cardinality).
- Tự cân bằng khi dữ liệu column index thay đổi.
- Độ phức tạp bằng chiều cao của cây. Complexity O(logn).

Một điều cần chú ý ở tính chất thứ hai, vì sao nên áp dụng khi **high cardinality**? Nếu áp dụng với column low cardinality như **gender** có 2 - 4 giá trị. BST gần như không thu được nhiều lợi ích so với **seq scan**. Sẽ có loại **index** khác cho các column này là **bitmap index**.

### 1.2) How

Quay lại bài trước, ta có thể index cho nhiều column với nhau, gọi là **composite index**. Bài toán rất hay có phần tìm kiếm dựa trên họ tên, thử một câu query trước:

EXPLAIN ANALYZE SELECT * FROM ENGINEER WHERE first_name = 'Dominique' AND last_name = 'Rice';

Chắc chắn vẫn là **seq scan** với bộ filter cho where condition.


Tiến hành tạo **index** cho 2 column `first_name` và `last_name` sau đó chạy lại query:

CREATE INDEX idx_engineer_firstname_lastname ON ENGINEER(first_name, last_name);

EXPLAIN ANALYZE SELECT * FROM ENGINEER WHERE first_name = 'Dominique' AND last_name = 'Rice';


Nhìn vào thông số **execution time**, khác bọt được thể hiện rõ. Tốc độ query sau khi index tăng chóng mặt khoảng 90 lần.

Thử một query khác, thực tế hay tìm kiếm với điều kiện `LIKE`. Tìm kiếm các engineer có `first_name` là `Dominique` và `last_name` chứa `a`:

EXPLAIN ANALYZE SELECT * FROM ENGINEER WHERE first_name = 'Dominique' AND last_name LIKE '%a%';


Plan có vẻ rắc rối hơn nhưng có **index scan**, **execution time** vẫn ổn. Đi qua **plan** chút xem nó hoạt động thế nào. **Chú ý cách đọc plan sẽ đi từ trong ra ngoài, không phải từ trên xuống dưới**:
- Step đầu tiên dễ dàng nhận thấy là **index scan** với điều kiện `first_name = Dominique` trước, lọc ra đc 58 rows.
- Sau đó thực hiện filter với cả 2 điều kiện `first_name = Dominique` và `last_name LIKE %a%`, loại bỏ được 43 rows.
- Kết quả thu được 15 rows với thời gian chưa đến 1 ms.

Tiếp tục, tìm các engineer có `last_name` là `Parker` và `first_name` chứa `v`:

EXPLAIN ANALYZE SELECT * FROM ENGINEER WHERE first_name LIKE '%v%' AND last_name = 'Parker';

Đọc **plan** xem có gì khác thường không.


Đù, các **Senior** lại bịp bợm, **execution time** tăng bất thường, không có **index scan** mà là **seq scan**? Tìm hiểu lại cơ chế của **B-Tree index** xem thế nào.

Bản chất của việc **index** là tạo ra table mới lưu các giá trị không trùng nhau của tất cả các giá trị trong một hoặc nhiều column. Sau đó, scan trên **index table** (cơ chế BST) với các condition để tìm kết quả. Do vậy, nó phù hợp với các truy vấn:
- **Match full value**:
- Tìm kiếm với giá trị chính xác. Sử dụng với các điều kiện so sánh equal (=).
- **Match a column prefix**:
- **Composite index** với nhiều column. Ví dụ như trên `idx_engineer_firstname_lastname` trên 2 column `first_name` và `last_name`. Khi thực hiện tìm kiếm, **index scan** chỉ được sử dụng khi điều kiện cho column đầu tiên là **match value**, ngược lại sẽ không áp dụng được. Giải thích, tất cả các tên đều được sắp xếp theo `first_name` sau đó là `last_name`. Nếu có trước `first_name`, dễ dàng thu nhỏ được tập tìm kiếm và tiếp tục scan trên đó để tìm `last_name`. Ngược lại, nếu cho `last_name` và một phần của `first_name` (không có prefix) thì bó tay, phải **seq scan** là đúng rồi. Dễ hiểu hơn rồi, hóa ra **Senior** không bịp :joy_cat:.
- **Match a range of full values**:
- Tìm kiếm với.. rất nhiều giá trị chính xác. Cụ thể là điều kiện IN hoặc các điều kiện so sánh (`>`, `<`, `>=`, `<=`).

Từ đó, rút ra vài chú ý khi sử dụng **B-Tree index**:
- Không có tác dụng khi tìm kiếm text sử dụng điều kiện LIKE '%%'. Index nữa index mãi thì tốc độ tìm kiếm.. không thay đổi (chung thủy thật), tốc độ insert còn tăng lên.
- Với **composite index**, các điều kiện cần **match full value** hoặc **match mostleft column** để đạt hiệu quả tối đa.

## 2) Bitmap index

### 2.1) What?

Có một câu ứng viên hay được hỏi: **Theo em, có nên đánh index cho các cột có ít giá trị (low cardinality), ví dụ như cột giới tính?**

Không nên vì bảng đó có ít giá trị, **indexing** vừa tốn mà không cải thiện nhiều tốc tộ. Mình thấy đa số các bạn trả lời như vậy, thậm chí search google cũng rất nhiều người khuyên như vậy?

Trả lời như trên cũng được nhưng chưa gãi đúng chỗ ngứa lắm.

Câu trả lời của mình như sau:
> - Bản chất của việc **indexing** vẫn là **seq scan** (dựa vào BST) nhưng trên **table index**. Mục đích giảm không gian tìm kiếm từ **table chính** xuống **table index**, từ đó cải thiện tốc độ query.
> - Do đó, nếu chỉ **indexing** cho column gender thì không gian tìm kiếm giảm không đáng kể. Ví dụ gender có 2 giá trị, giảm từ N xuống N/2, complexity vẫn là O(N). Ngoài ra còn thời gian truy cập vào **main table** để fetch data. Nếu **indexing** vẫn có khả năng giảm thời gian tìm kiếm.
> - Cần dựa trên nhu cầu thực tế, có query nào dùng điều kiện với column đó không để tạo **index** kết hợp với **index** khác hoặc **composite index**.

Vòng vo dài dòng quá, con số nói lên tất cả, đã có **analyze** và **explain**. Bắt đầu với query sau:

EXPLAIN ANALYZE SELECT * FROM Engineer WHERE gender = 2;


Chưa cần xem **query plan** đã biết sử dụng **seq scan**. **Cost** trong khoảng 0..2367 và **actual time** là 0.019..339. Thêm index trên column gender và chạy lại xem thế nào:

CREATE INDEX idx_engineer_gender ON ENGINEER(gender);

EXPLAIN ANALYZE SELECT * FROM Engineer WHERE gender = 2;


Với index, **cost** giảm từ 2367 xuống 1712, tuy nhiên **actual time** giảm không nhiều, đúng như dự đoán. Anw, **cost** giảm tức là các step liên quan đến computation đã giảm, từ đó giảm stress cho CPU, cũng không tệ.

Chú ý một chút, **plan** lúc này không sử dụng **index scan** mà đã chuyển sang **bitmap index scan**. PostgreSQL khá thông minh, nó phụ thuộc vào tính chất của column để quyết định **index** trên column đó là gì. Với **gender**, low cardinality nên nó lựa chọn **bitmap index**.

Bản chất của **bitmap index** vẫn sử dụng cấu trúc B-Tree, tuy nhiên nó lưu trữ thông tin khác với B-Tree index. **B-Tree index** mapping index với một hoặc nhiều rowId. **Bitmap index** mapping index với giá trị bit tương ứng của column. Ví dụ có 3 giá trị của gender: Male, Female, Unknown. Tạo ra 3 bit tương ứng 0, 1, 2 cho 3 giá trị đó và mapping với column trong table chính.


### 2.2) How

Chốt lại, **bitmap index** có các tính chất:
> - Phù hợp với các column **low cardinality**.
> - Lưu bit cho mỗi giá trị nên giảm dung lượng lưu trữ cần dùng.
> - Chỉ hiệu quả với tìm kiếm **full match value**.
> - Kết hợp với nhiều index khác để tăng tốc độ với OR, AND.

Tuy nhiên, nó cũng có hạn chế:
> - Nếu thêm hoặc bớt một giá trị cần build lại toàn bộ **index table**. Với B-Tree index chỉ cần re-balance tree.
> - Riêng với PostgreSQL, **bitmap index** được lưu trên memory vì size của nó khá nhỏ, từ đó tăng tốc độ truy vấn. Vì vậy khi restart nó cần build lại toàn bộ **bitmap index**. Để tránh nhược điểm này, trong thực tế sẽ sử dụng kết hợp với column khác tạo thành **composite index**.

Postgres rất thông minh, nó dựa trên các tính chất của column để quyết định sử dụng loại index nào. Thậm chí có thể chuyển đổi qua lại giữa các index type (dựa trên tính chất column) để tối ưu tốc độ truy vấn. Tất nhiên cost để chuyển đổi là rất lớn, cực kì lớn.

Dài quá khó tiêu, tạm thời kết thúc tại đây, bài tiếp theo mình sẽ bàn luận về các loại index còn lại nhé :nerd_face:.

### Reference
- https://hackmd.io/@datbv/rk74QmqFd#Reference

© [Dat Bui](https://www.linkedin.com/in/datbv/)