Improve SQL pagination query with large OFFSET

ImageSource: PlanetScale

Mở đầu

Số là gần đây dự án mình gặp 1 issues, đó là 1 thanh niên nào đó viết BOT để crawl dữ liệu, request vào trang TOP page để crawl list articles.

Request spam có dạng https://example.com/?page=page_number. Với page_number chạy từ 1 tới ~130.000

Mặc dù data các page đã được cache Redis, tuy nhiên khi truy vấn vào những page có id lớn, cache Redis đã bị expired nên truy vấn đều hit vào DB. Việc này khiến DB tăng tải và ảnh hưởng tới người dùng.

Giải pháp tạm thời là block spam requests qua AWS WAF, tuy nhiên root cause vẫn là do câu query bị chậm.

SELECT articles.id 
FROM articles 
WHERE deleted_at IS NULL 
  AND status = ?
  AND publish_datetime <= ?
ORDER BY hot_factor DESC, publish_datetime DESC, id DESC 
LIMIT ? OFFSET ?;

Trong bài viết này, mình chia sẻ về những bước đã làm để tìm cách improve performance cho câu query trên.

Improve performance

0. Precondition

• Bảng articles (trên môi trường staging) có khoảng 1,4 triệu record. (Trên production khoảng 2,4 triệu)
• Đã có sẵn 1 số indexes (được show trong các ví dụ bên dưới)

Dữ liệu test lấy từ môi trường staging.

1. Normal Query with offset 1002

Khởi động với normal query, offset = 1002.

mysql> SELECT id
    -> FROM articles
    -> WHERE deleted_at IS NULL
    ->   AND status = 'publish'
    ->   AND publish_datetime <= '2021-12-25 00:00:00'
    -> ORDER BY hot_factor DESC, publish_datetime DESC, id DESC
    -> LIMIT 10
    -> OFFSET 1002;
+---------+
| id      |
+---------+
| 2717956 |
| 2717954 |
| 2717955 |
| 2717953 |
| 2717939 |
| 2717937 |
| 2717935 |
| 2717938 |
| 2717936 |
| 2717933 |
+---------+
10 rows in set (1.02 sec)

mysql> EXPLAIN SELECT id  FROM articles WHERE deleted_at IS NULL    AND status = 'publish'   AND (publish_datetime <= '2021-12-25 00:00:00' )  ORDER BY hot_factor DESC, publish_datetime DESC, id DESC  LIMIT 10  OFFSET 1002\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: articles
   partitions: NULL
         type: index
possible_keys: status_publish_datetime_idx,status_publish_datetime_deleted_at_idx,status_idx
          key: hot_factor_publish_datetime_idx
      key_len: 11
          ref: NULL
         rows: 2024
     filtered: 5.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

Thời gian chạy: 1.02 s

Nhìn vào output của câu lệnh EXPLAIN, ta có thể thấy chiến lược thực thi của MySQL cho câu query này sẽ là:

1. Chọn table articles
2. Chọn index hot_factor_publish_datetime_idx (type: index nghĩa là MySQL sẽ scan full index tree), để Order và loại bỏ bớt (Filter) bớt các rows không thỏa mãn.
3. Row Estimation: MySQL ước tính là nó sẽ phải đọc khoảng 2024 rows từ index tree.
4. Filtering: Sau khi đọc ra các rows từ index tree, MySQL sử dụng câu lệnh WHERE để filter rows (Extra: Using Where). Filtered 5% tức là nó ước tính khoảng 5% số lượng rows sẽ thỏa mãn điều kiện.
5. Ordering: Sử dụng chính index hot_factor_publish_datetime_idx để order, do điều kiện order của mình là hot_factor, publish_datetime
6. Limit + Offset

Khi nhìn vào output của lệnh EXPLAIN, chúng ta nên chú ý tới 2 giá trị: type và rows.

Hiện tại, type index và rows 2024 vẫn đang khá ổn.

2. Tăng OFFSET để check với các page lớn

Các câu query dùng cho Pagination bằng OFFSET có 1 nhược điểm, đó là rất chậm nếu như OFFSET lớn. Lý do là MySQL không nhảy được ngay tới OFFSET mình truyền vào, mà phải scan và skip để tới vị trí mong muốn.

Bây giờ ta sẽ tăng thử OFFSET lên 100.000 để xem thử.

mysql> SELECT id  
FROM articles 
WHERE deleted_at IS NULL    
	AND status = 'publish'   
	AND (publish_datetime <= '2021-12-25 00:00:00' )  
ORDER BY hot_factor DESC, publish_datetime DESC, id DESC  
LIMIT 10  OFFSET 100000;

+---------+
| id      |
+---------+
| 2177159 |
| 2177152 |
| 2177151 |
| 2177148 |
| 2177146 |
| 2177150 |
| 2177149 |
| 2177147 |
| 2177145 |
| 2177144 |
+---------+
10 rows in set (38.45 sec)

mysql> EXPLAIN SELECT id  FROM articles WHERE deleted_at IS NULL    AND status = 'publish'   AND (publish_datetime <= '2021-12-25 00:00:00' )  ORDER BY hot_factor DESC, publish_datetime DESC, id DESC  LIMIT 10  OFFSET 100000\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: articles
   partitions: NULL
         type: ref
possible_keys: status_publish_datetime_idx,status_publish_datetime_deleted_at_idx,status_idx
          key: status_idx
      key_len: 1
          ref: const
         rows: 416909
     filtered: 3.33
        Extra: Using index condition; Using where; Using filesort
1 row in set, 1 warning (0.00 sec)

Hmm. 38.45s. Tại sao nó lại lâu thế?

Nếu nhìn qua thì ta thấy số lượng rows MySQL estimate phải scan đã tăng lên rất nhiều. Từ 2024 lên thành 416.909 🥲

Chiến lược thực thi trong câu này sẽ là:

1. Sử dụng index status_idx, duyệt index tree để lấy ra các rows thỏa mãn status = publish.
2. Nhìn vào mục Extra, ta thấy có 3 phần:
   • Using index condition: Do index chỉ match với 1 phần câu lệnh WHERE, nên MySQL chỉ sử dụng index để lấy ra các rows có status = publish.
   • Using where: Sau khi có các rows này rồi, nó tiếp tục thực hiện WHERE trên các rows này để filtering.
   • Using filesort: Do chúng ta ORDER BY hot_factor, publish_datetime, id, những fields này không nằm trong index => Nó cần tạo ra file tạm để sort (order) các kết quả.
3. Limit + OFFSET

Rõ ràng, việc filter theo status_idx không hiệu quả cho lắm. Đặc biệt là ở bước sử dụng filesort cho việc order. Việc này sẽ tốn thêm cost (do MySQL phải dùng Quicksort/Merge sort để order chứ không dùng được index) gây ra việc query bị chậm.

Vậy nếu chúng ta force sử dụng index hot_factor_publish_datetime_idx - index khá hiệu quả trong câu query đầu thì sao?

3. FORCE sử dụng index hot_factor_publish_datetime_idx

Với suy nghĩ là normal query đang sử dụng hot_factor_publish_datetime_idx, mình thử force sử dụng index này cho câu query với offset lớn xem sao? Biết đâu optimizer của MySQL detect index sai =))

mysql> SELECT id
    -> FROM articles
    -> FORCE INDEX (hot_factor_publish_datetime_idx)
    -> WHERE deleted_at IS NULL
    ->   AND status = 'publish'
    ->   AND (publish_datetime <= '2021-12-25 00:00:00')
    -> ORDER BY hot_factor DESC, publish_datetime DESC, id DESC
    -> LIMIT 10  OFFSET 100000
    -> ;
+---------+
| id      |
+---------+
| 2177159 |
| 2177152 |
| 2177151 |
| 2177148 |
| 2177146 |
| 2177150 |
| 2177149 |
| 2177147 |
| 2177145 |
| 2177144 |
+---------+
10 rows in set (4.88 sec)

mysql> EXPLAIN SELECT id FROM articles  FORCE INDEX (hot_factor_publish_datetime_idx) WHERE deleted_at IS NULL       AND status = 'publish'      AND (publish_datetime <= '2021-12-25 00:00:00')   ORDER BY hot_factor DESC, publish_datetime DESC, id DESC   LIMIT 10  OFFSET 100000\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: articles
   partitions: NULL
         type: index
possible_keys: NULL
          key: hot_factor_publish_datetime_idx
      key_len: 11
          ref: NULL
         rows: 100010
     filtered: 1.11
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

Câu query đã rút ngắn về còn 4.88s

Mình nghĩ 1 phần lớn tốc độ đã được cải thiện là do số lượng rows được rút về còn khoảng 100k, và không còn cần phải Using filesort nữa.

Theo như phần EXPLAIN, thì ta có thể hiểu là:

1. MySQL lựa chọn table articles
2. Do type: index => MySQL sẽ scan full index tree, với index là hot_factor_publish_datetime_idx, vừa order vừa filter.
3. Ước tính sẽ có khoảng 100.010 rows được lấy ra từ index.
4. Filtering: MySQL dùng WHERE command để filter rows (Extra: Using where) và nó dự tính sẽ lấy được khoảng 1.11% số lượng bản ghi thỏa mãn mệnh đề WHERE.
5. Ordering: Do index có bao gồm điều kiện order (hot_factor + publish_datetime), nên MySQL có thể dùng index cho phần sort kết quả.
6. Limit + OFFSET

Cách này có cải tiến hơn việc để tự MySQL Optimizer làm việc. Tuy nhiên, chúng ta cần hạn chế việc sử dụng FORCE INDEX, vì nó có thể đúng trong trường hợp này, nhưng lại dễ fail trong trường hợp khác.

Một cách tối ưu hơn?

Như vậy, tới đây thì ta đã có 1 tí ánh sáng cuối đường hầm, đó là cần tạo ra một index:

• Thỏa mãn điều kiện WHERE, ở đây là deleted_at, status, publish_datetime
• Index này có thể dùng để sort kết quả. Ở đây bao gồm: hot_factor, publish_datetime

=> Ta thử đánh index covering xem sao:

CREATE INDEX idx_articles_covering ON articles(deleted_at, status, publish_datetime, hot_factor, id);

Như vậy, covering index đã được tạo ra: deleted_at_status_publish_datetime_hot_factor_id với tên là: idx_articles_covering

Giờ chúng ta sẽ thử lại với câu query trên kia và xem kết quả.

mysql> SELECT id
    -> FROM articles
    -> WHERE deleted_at IS NULL
    ->     AND status = 'publish'
    ->     AND (publish_datetime <= '2021-12-25 00:00:00' )
    -> ORDER BY hot_factor DESC, publish_datetime DESC, id DESC
    -> LIMIT 10  OFFSET 100000;
+---------+
| id      |
+---------+
| 2177159 |
| 2177152 |
| 2177151 |
| 2177148 |
| 2177146 |
| 2177150 |
| 2177149 |
| 2177147 |
| 2177145 |
| 2177144 |
+---------+
10 rows in set (0.21 sec)

mysql> EXPLAIN SELECT id   FROM articles  WHERE deleted_at IS NULL         AND status = 'publish'        AND (publish_datetime <= '2021-12-25 00:00:00' )   ORDER BY hot_factor DESC, publish_datetime DESC, id DESC   LIMIT 10  OFFSET 100000\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: articles
   partitions: NULL
         type: range
possible_keys: status_publish_datetime_idx,status_publish_datetime_deleted_at_idx,status_idx,idx_articles_covering
          key: idx_articles_covering
      key_len: 13
          ref: NULL
         rows: 416909
     filtered: 100.00
        Extra: Using where; Using index; Using filesort
1 row in set, 1 warning (0.00 sec)

Hé. Kết quả câu query đã rút ngắn về còn 0.21s. Một kết quả khá ổn.

Tuy nhiên, ở đây chúng ta thấy có 1 vài vấn đề khi nhìn vào kết quả EXPLAIN:

1. key_len đang là 13 => Key đang rất dài, nên việc lưu trữ key này sẽ tốn nhiều storage. Khi truy vấn cũng có thể tốn thời gian hơn.
2. Cách thực thi của câu lệnh này sẽ là:
   • Sử dụng where với index idx_articles_covering (do đã cover đủ được 3 điều kiện WHERE)
   • Sử dụng index để duyệt các bản ghi thỏa mãn
   • Sau khi có kết quả, sử dụng filesort để sort kết quả.

Chúng ta nên hạn chế sử dụng filesort, vì việc này sẽ phụ thuộc vào IO của system. Nhưng câu query trên, tại sao nó lại đang sử dụng filesort???

Lý do chính là do sort order của chúng ta đang không match với order của index.

• Index chúng ta đang đánh theo order: deleted_at_status_publish_datetime_hot_factor_id
• Order condition của chúng ta đang để: hot_factor, publish_datetime, id.

=> Chúng ta có thể thử thêm 1 cách nữa, là đổi lại thứ tự trong index xem sao.

DROP INDEX idx_articles_covering ON articles;

CREATE INDEX idx_articles_covering ON articles(deleted_at, status, hot_factor, publish_datetime, id);

Giờ chúng ta sẽ thử truy vấn lại câu query:

mysql> SELECT id
    -> FROM articles
    -> WHERE deleted_at IS NULL
    ->     AND status = 'publish'
    ->     AND (publish_datetime <= '2021-12-25 00:00:00' )
    -> ORDER BY hot_factor DESC, publish_datetime DESC, id DESC
    -> LIMIT 10  OFFSET 100000;
+---------+
| id      |
+---------+
| 2177159 |
| 2177152 |
| 2177151 |
| 2177148 |
| 2177146 |
| 2177150 |
| 2177149 |
| 2177147 |
| 2177145 |
| 2177144 |
+---------+
10 rows in set (0.11 sec)

mysql> EXPLAIN SELECT id   FROM articles  WHERE deleted_at IS NULL         AND status = 'publish'        AND (publish_datetime <= '2021-12-25 00:00:00' )   ORDER BY hot_factor DESC, publish_datetime DESC, id DESC   LIMIT 10  OFFSET 100000\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: articles
   partitions: NULL
         type: ref
possible_keys: status_publish_datetime_idx,status_publish_datetime_deleted_at_idx,status_idx,idx_articles_covering
          key: idx_articles_covering
      key_len: 7
          ref: const,const
         rows: 416909
     filtered: 33.33
        Extra: Using where; Using index
1 row in set, 1 warning (0.00 sec)

Có vẻ khá ngon.

Kết quả câu truy vấn về còn 0.11s.

key_len về còn 7, phần Extra không còn sử dụng filesort do giờ nó có thể sort dựa vào index luôn.

Ngoài ra, có một sự khác biệt khi query nếu sử dụng 2 indexes trên, đó là mục type.

Với index đầu, type đang là range, do nó tìm trên nhánh deleted_at_status_publish_datetime, mà publish_datetime đang ở dạng range <= '2021-12-25 00:00:00'. Còn với index thứ hai, type là ref, do nó chỉ scan với nhánh deleted_at_status, còn publish_datetime sẽ được filer bằng điều kiện WHERE. Maybe đây cũng giúp tối ưu thêm 1 phần. (cái này mình không chắc =)) )

=> Chốt lại là sẽ chọn phương án cuối cùng!

Kết luận

Trước giờ mình chỉ quen dùng ORM, nên việc viết raw queries và tìm cách improve performance với mình là 1 việc khá ngượng tay =))

Ngồi viết bài này, mình tự rút ra được vài ý:

1. Muốn improve SQL query performance, trước hết phải hiểu được output của EXPLAIN command.
2. Từ output của EXPLAIN command, tìm hiểu xem câu lệnh sẽ được thực thi như thế nào? Đang sử dụng index nào? Có hiệu quả không? Có cần phải thêm các bước Extra nào khác không?
3. Nếu có thể, hạn chế sử dụng ORM, ít nhất là cho tới khi bạn thực sự hiểu SQL.

Hy vọng bài viết có thể giúp ích cho các bạn nếu gặp trường hợp tương tự.

References

Xin chân thành cảm ơn Copilot và các tác giả của những bài viết dưới đây vì những chia sẻ cực kì hữu ích ❤️

• https://viblo.asia/p/su-dung-explain-de-toi-uu-cau-lenh-mysql-BYjv44gmvxpV
• https://viblo.asia/p/mysql-indexing-PDOkqWxAGjx
• https://viblo.asia/p/mysql-index-condition-pushdown-ZjlealAZGqJ
• https://viblo.asia/p/mysql-performance-tuning-with-index-V3m5WdrbKO7