MySQL Index Condition Pushdown

Để tôi kể cho các bạn nghe câu chuyện về bản thân tôi.

Khi mới học MySQL ở trường đại học, tôi thấy index khá thú vị, và chỉ cần có index là mọi thứ sẽ rõ ràng và truy vấn sẽ nhanh hơn. Hồi ý tôi chỉ biết đến index theo mỗi id, và do vậy sẽ có 2 loại index chính, đó là index theo 1 cột và index 2 cột trong bảng quan hệ nhiều nhiều.

• Index theo 1 cột

CREATE TABLE users(
    id INT(11) AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(255)
);

• Index theo nhiều cột (giả sử rằng 1 user học nhiều trường đại học)

CREATE TABLE user_universities(
    id INT(11) AUTO_INCREMENT PRIMARY KEY,
    user_id INT(11),
    university_id INT(11),
    KEY (user_id, university_id)
);

Trường hợp thứ nhất thì quá đơn giản và không có gì để nói, trường hợp thứ 2, tôi cũng cho là nó đơn giản, và tôi thoải máy chạy các câu query loại WHERE user_id = 1, WHERE university_id = 1, WHERE university_id = 1 AND user_id = 1.

Đến một ngày tôi nhận được cảnh báo của 1 đàn anh, rằng 3 câu query trên của tôi thì có đến 2 câu không dùng được index. MySQL yêu cầu thứ tự chặt chẽ từ tráng sang phải trong việc dùng index với nhiều cột, và do vậy trường 2 câu query sau của tôi dùng trực tiếp university_id mà không dùng đến user_id thì chẳng khác nào có index bằng thừa.

Tôi cho đây là 1 kinh nghiệm quý báu, tìm tòi đọc sách và cuốn High Performance MySQL 3rd Edition đã giải thích điều đó rất rõ, qua bức hình này.

Hình 1. Lưu trữ multiple columns index trong InnoB (High performance MySQL 3rd edition, p.150)

Bạn đọc có thể tham khảo bài viết này của tôi để hiểu rõ hơn đôi chút.

Kinh nghiệm về việc dùng multiple columns index theo tôi trong nhiều năm, cho đến 1 ngày tôi đọc 1 bài viết (không tiện link ở đây), rằng cái thời viết truy vấn với thứ tự chặt chẽ từ trái sang phải đã qua rồi, vì MySQL từ 5.6 đã có Index Condition Pushdown, và không phải lo về việc viết không đúng thứ tự nữa (yeah3).

Thật là tuyệt vời, vậy là dù cho sách viết đàng hoàng, thì High Performance MySQL 3rd Edition là viết cho MySQL 5.5, phải chăng MySQL 5.6 có bước cải tiến lớn đến vậy. Chúng ta cùng tìm hiểu xem có thực Index Condition Pushdown tuyệt vời đến thế không?

Nhắc lại về cơ chế lưu index của MySQL

Tôi đã viết một bài về vấn đề index của MySQL rồi, nên sẽ không nói cụ thể nữa. Căn bản thì MySQL lưu 1 BTree cho key, key này có thể là 1 cột hoặc nhiều cột trong bảng. Key sẽ có con trỏ để trỏ đến bản ghi với đầy đủ dữ liệu trong DB.

Tìm kiếm có key nhanh hơn không có key, bởi nếu dùng key chúng ta chỉ cần tìm trên 1 BTree đã được sắp xếp có tổ chức, nên có thể tìm dễ dàng key và qua đó truy vấn đến bản ghi đầy đủ trong DB. Ngược lại nếu không dùng key, chúng ta phải duyệt từng dòng của bảng. Thao tác này rất tốn kém, vì làm việc trên 1 lượng dữ liệu lớn với nhiều thao tác IO.

Key bao gồm nhiều cột (như Hình 1) là hình thức lưu trữ mà ở đó mỗi node của BTree là 1 kiểu cấu trúc bao gồm các cột của bảng. Thay vì so sánh chỉ 1 cột thì key bao gồm nhiều cột thực hiện so sánh lần lượt từ trái sang phải để quyết định thứ tự trước sau trong cây.

Index condition pushdown(ICP) nghĩa là gì

Đây là một khái niệm không hề đơn giản và cần hiểu biết tương đối rõ về cơ chế của MySQL. Hy vọng bạn đọc đã nắm vững phần lý thuyết trên trước khi đi đến phần này.

Ở MySQL truyền thống, tức là phiên bản dưới 5.6 chưa có Index Condition Pushdown, storage engine chỉ cố tìm kiếm máy móc theo index có sẵn, sau đó nó trả về đầy đủ cả dòng trong bảng về cho MySQL server. MySQL server từ đó tiếp tục đánh giá điều kiện WHERE để đưa ra kết quả cuối cùng. Mặc dù bản chất BTree hỗ trợ tìm kiếm theo range, tuy nhiên khi làm việc với nhiều columns, nó có những hạn chế nhất định. Đây chính là điểm yếu khi không có ICP.

Ở MySQL từ 5.6 trở lên, với storage engine là InnoDB và MyISAM, MySQL server sẽ xác định 1 phần của điều kiện mà chỉ dùng các trường của key. MySQL server chỉ truyền 1 phần điều kiện đó cho storage engine, và tại đây storage engine, thay vì duyệt toàn bộ bảng, thì duyệt trên cây index của bảng đó. Nếu điều kiện thoả mãn thì mới trả về cả dòng của bảng

Thêm 1 chú ý nữa là ở MySQL 5.6 thì ICP không hoạt động với partitioned tables, vấn đề này đã được giải quyết ở MySQL 5.7.

Vai trò quan trọng của ICP là giảm số thao tác đọc full bản ghi trong bảng, qua đó giúp giảm số thao tác IO. Vì chỉ duyệt trên index là BTree nên việc giảm số lượng thao tác IO giúp tăng hiệu năng của MySQL rất nhiều.

Để có thể hiểu rõ hơn về ICP, chúng ta đến với ví dụ sau.

Chúng ta có bảng users, có zipcode, lastname, firstname, birthday.

CREATE TABLE users(
    id INT(11) AUTO_INCREMENT PRIMARY KEY,
    zipcode VARCHAR(8),
    lastname VARCHAR(32),
    firstname VARCHAR(32),
    birthday DATE,
    KEY zipcode_lastname_firstname(zipcode, lastname, firstname)
);

Bây giờ chúng ta thử đến với query sau đây.

SELECT * FROM users
    WHERE zipcode = '12345'
    AND lastname LIKE 'foo%'
    AND firstname = 'bar';

Với câu query này, chúng ta đã viết đúng thứ tự của KEY zipcode_lastname_firstname, tuy nhiên để ý rằng câu query LIKE với lastname sẽ khiến index của chúng ta chỉ hoạt động đến lastname và không hoạt động đến firstname. BTree hỗ trợ tìm kiếm theo range, ở đây có thể hiểu là so sánh key zipcode_lastname_firstname mà lớn hơn bộ ('12345', 'foo', null) và nhỏ hơn bộ ('12345', 'fop', null) (p là ký tự liền sau o), tuy nhiên tuyệt đối không hỗ trợ tìm kiếm với firstname vì trước đó lastname đã phải tìm theo range rồi.

Cụ thể, nếu không có ICP, MySQL hoạt động như sau.

1. Storage engine sẽ trả về cho MySQL server đầy đủ thông tin (full record) của tất cả các bản ghi mà có zipcode và lastname thoả mãn điều kiện WHERE.
2. MySQL server tiếp tục kiểm tra điều kiện còn lại của firstname để lọc ra các bản ghi thoả mãn.

Công việc này có sự tốn kém về thao tác IO do việc phải load các full record ra thay vì chỉ làm việc với BTree (Lưu ý là BTree chỉ lưu index, secondary key trỏ đến primary key và primary key trỏ đến vị trí lưu đầy đủ bản ghi).

Vậy với ICP, MySQL hoạt động ra sao?

1. Tìm kiếm theo left prefix của key bằng BTree truyền thống.
2. Tiếp tục sử dụng điều kiện tìm kiếm để kiểm tra các index đã lấy được từ BTree.
3. Trả về cho MySQL server bản ghi đầy đủ sau khi đã duyệt theo tất cả các điều kiện "có thể".
4. MySQL server tiếp tục kiểm tra các điều kiện khác nếu có.

Bước 1 và 2 đều làm ở storage engine, và do vậy giảm thiểu được 1 số lượng lớn các bản ghi bị duyệt toàn bộ cũng như các thao tác IO.

Đến đây, chắc các bạn đã hiểu được cách làm việc của ICP. Nếu còn chưa dám chắc, hãy thử phân tích xem trường hợp sau đây ICP có hoạt động hay không và hoạt động như thế nào.

SELECT * FROM users
    WHERE zipcode = '12345'
    AND lastname LIKE '%foo%'
    AND firstname LIKE '%bar%';

Nếu bạn không thể tìm được câu trả lời, có thể tham khoả MySQL Reference Manual

Quay lại với câu chuyện tôi kể ở đầu bài. Liệu có phải ICP sẽ giúp chúng ta viết query thế nào cũng được và không cần quan tâm đến thứ tự cũng như đầy đủ các thành phần trong Multiple column indexes không?

Câu trả lời là không, chúng ta vẫn nên tuân thủ đúng thứ tự và quy tắc truyền thống của MySQL. Nếu tuân thủ đúng quy tắc left prefix, thì chúng ta có thể tận dụng được tất cả các điểm mạnh của BTree, một cấu trúc dữ liệu tuyệt vời cho tìm kiếm. Các kết quả mà BTree truyền thống trả về sẽ được duyệt thủ công, chỉ giúp giảm số thao tác IO, chứ không dùng hết đặc thù tìm kiếm của BTree được.

1. MySQL 5.6 Reference Manual: Index Condition Pushdown Optimization

2. Percona: Index Condition Pushdown in MySQL 5.6 and MariaDB 5.5 and its performance impact

3. Blog của 1 MySQL Optimizer Developer: Index Condition Pushdown to the rescue!