---
tags: Series PostgreSQL
---

# 001: Có những cách nào để tối ưu SQL Query?

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

## 1) Overview
SQL là ngôn ngữ truy vấn dữ liệu dạng bảng được phát triển vào những năm 1970s. Mặc dù hơn 50 tuổi đời nhưng vẫn được sử dụng phổ biến. Câu hỏi đặt ra, có bí ẩn gì mà nó phổ biến và tồn tại lâu đến vậy?

Ngắn gọn thôi, vì nó phù hợp, rất phù hợp, cực kì phù hợp để truy vấn dữ liệu dạng bảng với Relational Database. Vài năm trước rộ lên phong trào NoSQL cho các Non-relational Database. Tuy nhiên đẳng cấp vẫn là mãi mãi, sau vài năm phát triển các kĩ sư nhận ra không thể bỏ SQL và Relational Database và nó đang trỗi dậy mạnh mẽ. Khá giống [Monolithic Architecture vs Microservice Architecture](https://hackmd.io/@datbv/HkbQumIY_).

Gần như tất cả các thể loại data từ đơn giản đến phức tạp đều có khả năng cấu trúc được dưới dữ liệu dạng bảng. Ngoài ra, một lý do nữa nó phổ biến là các query viết dưới dạng khai báo, chúng ta chỉ ra những gì mình muốn và không quan tâm đến việc nó được thực thi như thế nào.
> - SELECT * FROM ENGINEER e WHERE e.title = 'Software Engineer';

Kết quả của query trên là tất cả những ông kĩ sư có title **Software Engineer**. Để làm được như vậy:
> - SQL query sẽ chuyển từ câu lệnh khai báo sang dạng thủ tục (procedural form) để được thực thi.
> - Sau khi chuyển sang dạng **procedural**, nó được với cái tên mĩ miều hơn **Execution plan**.
> - **Execution plan** bao gồm một chuỗi các bước như scanning, filtering, joining data.

Chúng ta không can thiệp được vào quá trình chuyển đổi từ **SQL query** sang **execution plan**. Do đó, **plan** có thể hiệu quả hoặc không, tùy thuộc vào nhiều yếu tố như số lượng records ảnh hưởng đến thời gian scanning. Cách **join table** chưa phù hợp...

Chốt lại có những cách nào để tối ưu query?

## 2) Scanning table
**Scanning table** là một trong những hành động đơn giản nhất của **execution plan**. Hiểu đơn giản, nó là hành động tuyến tính, đọc từng row từ đầu đến cuối, so sánh với các điều kiện và trả về kết quả. Do vậy, thời gian tìm kiếm sẽ phụ thuộc vào số lượng row table.


Một vài tính chất của **scanning table**:
> - Duyệt qua từng table row.
> - Data được lưu dưới disk (HDD/SSD) không giống như table chúng ta thấy mà nó sẽ nằm trong một **block of data**. Do đó phải fetch block of data lên để xử lý.
> - Thực hiện filter hoặc áp dụng các condition dựa trên query với mỗi row.
> - Time complexity tỉ lệ thuận với số lượng row O(n).

**Scanning table** trông cũng đơn giản dễ dùng. Nhưng cuộc đời thì lại không màu hường đến thế. Với table có hàng triệu row thì.. không dám nghĩ tiếp. Vậy ta cần có cách để làm cho nó hiệu quả hơn, đó là áp dụng **indexing**.
> - Junior: anh ơi em query table này rất chậm, có cách nào cải thiện tốc độ không?
> - Senior: em đã đánh index chưa?

## 3) Indexing
Cụ thể hơn, **indexing** là cái quái gì?

Một vài cách diễn tả lấy ví dụ về cuốn sách với phần mục lục được coi là **index**, nó cũng đúng nhưng chưa đủ và chưa nổi bật được cách thức hoạt động. Xem hình minh họa trước nhé.


Bản chất quá trình **indexing** là việc chuyển đổi một/nhiều column sang một bảng mới (DB System sẽ quản lý table này) với các tính chất:
> - Table **index** được sắp xếp theo thứ tự. Giá trị là giá trị của một/nhiều column được đánh **index**.
> - Tìm kiếm nhanh hơn với một vài điều kiện trên column được đánh **index**.
> - Mỗi index được ánh xạ sang một hoặc nhiều row trong table chính.
> - Có thể index được nhiều cột cùng lúc, gọi là **composite index**.

Nhìn qua ta thấy thay vì **scanning** trên table chính, ta **scanning** trên table index, khác gì nhau nhỉ?
> - Thứ nhất, thay vì lấy toàn bộ row, ta chỉ lấy column được index để thực hiện tìm kiếm.
> - Thứ hai, table index được sắp xếp nên việc scan đơn giản hơn. Thay vì scan toàn bộ, sử dụng cấu trúc Binary Tree để tiến hành scan. Phổ biến và thông dụng nhất chính là B-Tree index, B-Tree là Balanced Tree, không phải Binary Tree nhé.

Ngoài B-Tree index, còn nhiều loại index khác mình sẽ giới thiệu cụ thể trong bài sau:
> - Hash index
> - Bitmap index
> - Specialized index

Như vậy, chúng ta hiểu để tăng tốc query cần thực hiện **indexing**. Tuy nhiên, không thể index tùy tiện, hãy nhìn lại hình minh họa trên:
> - Khi thực hiện index, phải tạo thêm bảng mới để lưu giá trị index. Càng nhiều index càng nhiều bảng, càng nhiều thao tác phải thực hiện dẫn đến tốc độ insert giảm, tăng dung lượng lưu trữ.
> - Ngoài ra, các giá trị trong table index phải được sắp xếp để phục vụ tìm kiếm, thêm mới row sẽ cần sắp xếp lại table index cho phù hợp dẫn đến tốc độ insert giảm.

## 4) Joining table
Tất nhiên, thực tế query chẳng bao giờ trên một bảng mà join rất nhiều bảng với nhau. Nên việc join table thế nào cũng ảnh hưởng đến tốc độ query. Có rất nhiều kiểu join khác nhau như: Inner join, Outer join, Cross join...

Nhưng phần này sẽ không bàn luận đến cái đó, mình muốn nói về cơ chế **joining table**. Cụ thể có 3 cơ chế chính:
> - Nested loop join
> - Hash join
> - Sort merge join

**Nested loop join** thực hiện so sánh tất cả các row trên 2 table:
> - Duyệt qua từng table row.
> - Với mỗi row, duyệt qua từng row của table còn lại.
> - Với mỗi step như vậy cần thực hiện việc so sánh FK.
> - Đơn giản nhưng tốn hiệu năng.

**Hash join** thực hiện hash các giá trị của FK và join dựa trên các giá trị matching đó:
> - Hash FK của table nhỏ hơn (số lượng row ít hơn).
> - Lưu các giá trị hash đó vào **hash table** để thực hiện so sánh.
> - Scan table lớn hơn, thực hiện hash FK và compare với các giá trị trong **hash table**. Có vẻ không khác **nested loop join** nhỉ? Lưu ý tốc độ truy xuất trong **hash table** là O(1) nhé nên có khác nhau đó.

**Sort merge join** thực hiện sắp xếp 2 table dựa trên FK và join để tận dụng lợi thế của **ordering**:
> - Sắp xếp cả 2 table.
> - Các bước tiếp theo thực hiện giống nested loop join.
> - Tuy nhiên sẽ dừng lại khi không tìm thấy các giá trị trùng nhau vì tận dụng lợi thế của **ordering**.

Mỗi cơ chế join sẽ phù hợp với từng điều kiện khác nhau. Cụ thể hơn về cách hoạt động, khi nào áp dụng cơ chế nào mình sẽ giới thiệu kĩ hơn ở bài sau.

## 5) Partitioning
Một cách khác cũng giúp tăng performance query đó là **partitioning data**:
> - Chia table thành các sub-table nhỏ hơn dựa trên một vài thuộc tính.
> - Từ đó, số lượng record giảm, dẫn đến tốc độ scanning nhanh hơn, tăng performance khi query.
> - Phù hợp với các table có số lượng record cực lớn.

Tuy nhiên nhược điểm của nó là khi các record được update. Thuộc tính bị thay đổi dẫn đến các record được re-assigned về đúng sub-table, expensive cost.


Vì table được phân chia ra nhiều sub-table nên ta cần biết chính xác record muốn tìm kiếm nằm ở sub-table nào để tận dụng lợi thế của **partitioning data**. Để làm được điều đó, chúng ta sử dụng **partition key** để thực hiện **partitioning**. **Partition key** có thể là khoảng thời gian (năm 2020, 2021) hoặc các giá trị với số lượng ít (giới tính Nam, Nữ).

Ngoài ra, các **sub-table** cũng được coi là 1 table, có thể thực hiện **indexing** cho chúng. Từ đây dẫn đến 2 loại index cho **partitioning** là:
> - **Local index**: cho các sub-table thuộc table chính, lợi thế là giảm thời gian truy cập đến từng row trong **sub-table**.
> - **Global index**: cho table chính, tìm kiếm các record thuộc toàn bộ các **sub-table**.

Với mỗi loại index sẽ phù hợp với từng điều kiện khác nhau. Ví dụ **partitioning** table Engineer dựa trên **partition key** là gender, chia thành 2 **sub-table** là **Male** và **Female**. Nếu tìm kiếm các engineer nam trên 18 tuổi thì **local index** sẽ phù hợp hơn. Tìm kiếm tất cả engineer trên 18 tuổi sẽ sử dụng **global index**.

Với bài này, chúng ta đã biết một vài cách để optimize SQL query. Bài sau mình sẽ đi chi tiết vào cơ chế và ứng dụng của từng cách trong thực tế.

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

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