MySQL index optimize B-Tree

Có rất nhiều cách khác nhau để tối ưu hoá câu lệnh SQL nâng cao performance. Một trong số đó là đánh index cho các fields của table.

index là việc cấu trúc dữ liệu, lưu trữ theo một cơ chế nào đó để tìm ra các record một cách nhanh chóng. Index là rất cần thiết để tăng performace và ngày càng trở nên quan trọng hơn nếu dữ liệu trong database của bạn ngày một lớn, đối với các hệ thống nhỏ thì việc đánh index hầu như không có ý nghĩa, nhưng một khi data trong db ngày một tăng, thì các truy vấn db có thể trở nên chậm chập tỷ lệ với độ tăng data trong db. Việc hiểu sai về index có thể dẫn tới nguyên nhân làm cho performance không những không được cải thiện mà còn trở nên ì ạch hơn. cách đơn giản nhất để hiểu về cơ chế index làm việc trong MySQL đó là nghĩ về việc đánh số trang trong một quyển sách. Để tìm một topic cụ thể trong cuốn sách bạn thường tìm đến phần mục lục và tìm trang số thứ bao nhiêu trong quyển sách theo như topic mà bạn muốn. Trong MySQL có một cơ chế lưu trữ index theo cách tương tự. Giả sử khi chạy câu lệnh MySQL sau:

mysql> SELECT first_name FROM sakila.actor WHERE actor_id = 5;

Index sẽ được đánh trên cột actor_id, MySQL sẽ sử dụng index để tìm ra những dòng mà actor_id của nó là 5. Hay nói cách khác nó sẽ thực thi việc tìm kiếm dữ liệu trên value index và trả về bất cứ dòng dữ liệu nào có chứa dữ liệu đầu vào. Một Index có chứa dữ liệu từ một hoặc nhiều cột khác nhau trong table. Nếu bạn đánh index cho nhiều cột thì thứ tự cột là rất quan trong bởi vì MySQL chỉ có thể tìm kiếm hiệu quả về phía bên trái prefix của index (sẽ nói rõ hơn qua các ví dụ bên dưới). Việc tạo index trên 2 cột không giống với việc tạo index trên 2 cột riêng rẽ.

** Các kiểu index** Mỗi một kiểu được thiết kế cho các mục đích khác nhau, Index được thực thì ở tầng lưu trữ dữ liệu, do đó nó không có một chuẩn nào cả. Có rất nhiều kiểu index mà điển hình là B-tree index, hash index, R-tree index, full-text index ...

Thông thường khi ta nói đến index mà không chỉ rõ loại index thì đó là ám chỉ đến B-Tree index, nó sử dụng B-Tree data structure để lưu trữ dữ liệu. Hầu hết các bộ máy lưu trữ dữ liệu của MySQL đều hỗ trợ B-TRee index. Ý tưởng chính của B-Tree đó là tất cả các giá trị được lưu theo một trật tự. và mỗi node lá sẽ có chung khoảng cách với gốc. Một B-Tree index có thể làm nhanh tốc độ truy vấn là vì bộ máy lưu trữ dữ liệu sẽ không scan dữ liệu trên toàn bộ bảng để tìm dữ liệu cần có. Thay vào đó nó sẽ bắt đầu từ node gốc, mỗi một điểm trên nốt gốc sẽ giữ những con trỏ trỏ tới những nốt con và bộ máy lưu trữ sẽ dựa vào những con trỏ để scan dữ liệu. Nó sẽ tìm con trỏ bên phải bằng cách nhìn vào dữ liệu ở node pages, các node page có chứa dữ liệu của các node con. Bộ máy lưu trữ sẽ xác định việc dữ liệu có tồn tại hay không hay tìm được dữ liệu ở leaf page.

B-Tree lưu trữ indexed columns theo một thứ tự vì vậy chúng rất hữu ích cho việc tìm kiếm một khoảng dữ liệu. Ví dụ index được đánh cho một trường dữ liệu kiểu text, nếu tìm kiếm theo tên bắt đầu bằng một chữ cái nào đó thì việc tìm kiếm sẽ rất hiệu quả Giả sử có table

CREATE TABLE People ( last_name varchar(50) not null, first_name varchar(50) not null, dob date not null, gender enum('m', 'f')not null, key(last_name, first_name, dob) );

index sẽ chứa giá trị của last_name, first_name, và dob cho mỗi dòng dữ liệu,

Chú ý: Index sắp xếp dữ liệu thông qua thứ tự cột index trong câu lệnh tạo table

key(last_name, first_name, dob)

II.1. Các kiểu queries có thể sử dụng B-Tree index:

B-Tree index sẽ hiệu quả với việc tìm kiếm với full key value, key range hoặc key prefix. B-Tree chỉ thực sự hữu dụng khi search từ phía trái của index có nghĩa là: trong ví dụ trên index là

key(last_name, first_name, dob)

thì

select * from poeple where last_name=’Peter’ and first_name=’Smitth’ #index sẽ được sử dụng

nhưng câu dưới đây index sẽ không được dùng

mysql> explain select * from People where first_name='Smitth' ;
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.02 sec)

vì không search từ bên trái của index key chain, tức là phải last_name trước rồi đến first_name rồi đến dob.

Trường hợp dưới đây cũng không có tác dụng

mysql> explain select * from People where dob='1990' and first_name='Smitth';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
1 row in set, 2 warnings (0.00 sec)

cho dù đổi trật trự trong điều kiện where cũng không có tác dụng vì trong điều kiện where không có last_name

Match the full value Match tất cả key, value của dữ liệu cho tất cả các cột trong index

mysql> explain select * from People where last_name='Peter' and dob='1990' and first_name='Smitth';
+----+-------------+--------+------+---------------+--------------+---------+-------------------+------+-----------------------+
| id | select_type | table  | type | possible_keys | key          | key_len | ref               | rows | Extra                 |
+----+-------------+--------+------+---------------+--------------+---------+-------------------+------+-----------------------+
|  1 | SIMPLE      | People | ref  | b_tree_index  | b_tree_index | 107     | const,const,const |    1 | Using index condition |
+----+-------------+--------+------+---------------+--------------+---------+-------------------+------+-----------------------+
1 row in set, 4 warnings (0.04 sec)

Match a leftmost prefix

• Index chỉ được áp dụng khi truy vấn với column đầu tiên last_name

select * from poeple where last_name=’Peter’ 

Match a column prefix

• Có thể match phần đầu của value, nó chỉ được áp dụng cho cột đầu tiên của index ví dụ tìm last_name bắt đầu bằng chữ "K" chẳng hạn

mysql> explain select * from People where last_name like 'P%';
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+
| id | select_type | table  | type  | possible_keys | key          | key_len | ref  | rows | Extra                 |
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+
|  1 | SIMPLE      | People | range | b_tree_index  | b_tree_index | 52      | NULL |    1 | Using index condition |
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+

Match với một khoảng dữ liệu

• Cho phép match data với một khoảng value truyền vào, và nó chỉ áp dụng cho column đầu tiên của index

Match chính xác một phần và kết hợp match trường khác trong một khoảng dữ liệu

• Index này cho phép bạn tìm ra chính xác last_name sau đó tìm first name với môt khoảng giá trị như first_name bắt đầu bằng "k" chẳng hạn.

mysql> explain select * from People where last_name='Peter' and first_name like 'M%';
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+
| id | select_type | table  | type  | possible_keys | key          | key_len | ref  | rows | Extra                 |
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+
|  1 | SIMPLE      | People | range | b_tree_index  | b_tree_index | 104     | NULL |    1 | Using index condition |
+----+-------------+--------+-------+---------------+--------------+---------+------+------+-----------------------+

Index chỉ cho các câu truy vấn lấy dữ liệu Một lưu ý là B-Tree chỉ áp dụng cho việc truy vấn lấy ra dữ liệu chứ không có tác dụng cải thiện việc lưu trữ dữ liệu xuống db.

Hạn Chế của B-Tree:

• Nó sẽ là không hữu ích nếu việc tìm kiếm trong câu lệnh điều kiện không bắt đầu từ phía trái của index keys, như ở ví dụ trên

key(last_name, first_name, dob)

Nếu ta tìm kiếm theo first_name, dob => không có last_name, không bắt đầu từ phía trái của key nên index sẽ không có tác dụng trong trường hợp này.

Một điều nữa đó là index sẽ không có tác dụng search một trường được kết thúc bởi một ký tự nào đó ví dụ:

mysql> explain select * from People where last_name like  '%r';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.04 sec)

possible_keys là null.

• Hạn chế tiếp theo là bạn không thể bỏ qua cột của index, nghĩa là khi truy vấn nếu bạn không bắt đầu hay các field tìm kiếm không có trong thứ tự của keys thì index sẽ không có tác dụng cho toàn bộ các column ở trong condition Ví dụ tôi sẽ bỏ cột giữa first_name khi truy vấn key(last_name, first_name, dob)

mysql> explain select * from People where last_name='Peter' and dob='1990';
+----+-------------+--------+------+---------------+--------------+---------+-------+------+-----------------------+
| id | select_type | table  | type | possible_keys | key          | key_len | ref   | rows | Extra                 |
+----+-------------+--------+------+---------------+--------------+---------+-------+------+-----------------------+
|  1 | SIMPLE      | People | ref  | b_tree_index  | b_tree_index | 52      | const |    1 | Using index condition |
+----+-------------+--------+------+---------------+--------------+---------+-------+------+-----------------------+
1 row in set, 3 warnings (0.00 sec)

thì chỉ có cột đầu tiên last_name là được dùng index Một giới hạn nữa đó là khi trong điều kiện where của câu truy vấn nếu bất kỳ một columns nào đó sử dụng range condition thì những column đứng sau nó sẽ không được index ví dụ

select * from People where last_name=’Peter’ and first_name like ‘%r’ and dob=’1990’

tìm kiếm last name kết thúc bởi chữ r, đây là range condition. Như vậy khi tìm kiếm dob sẽ không được sử dụng index, mà index chỉ có tác dụng với 2 trường last_name và fist_name

Đánh index cho bảng dữ liệu là khá quan trọng, nó giúp làm tăng hiệu năng truy vấn xuống db của hệ thống, bên cạnh đó nếu hiểu sai, áp dụng sai thì việc đánh Index trở nên vô nghĩa không có tác dụng tăng performance mà còn làm chậm

Bài viết được tham khảo từ cuốn High Performance MySQL 3rd Edition