[Mysql] Đánh Index cho hiệu năng cao - P2

Hash indexes

Một hash index nằm trong hash table và hữu dụng chỉ khi tìm kiếm chính xác giá trị của column sử dụng index. Với mỗi dòng, storage engine tính toán hash code của index của cột tương ứng, hash code sinh là là hash code đảm bảo có giá trị nhỏ và phải khác với những hash code sinh ra từ column có giá trị khác. Nó chứa hash code của index và một con trỏ tới hàng đó trên hash table.

Trong MySQL, chỉ có memroy storage engie hỗ trợ explicit hash index. Chúng là default index cho memory table, mặc dù memory table cũng có B-Tree index. Memory engine hỗ trợ nonunique hash index - một điều không bình thường trong thế thới database. Nếu nhiều giá trị có cùng 1 hashcode, index lưu tất cả pointer đến row trong cùng 1 entry của hash table, nó sử dụng linked list. Ví dụ ta có bảng sau:

CREATE TABLE testhash ( fname VARCHAR(50) NOT NULL, lname VARCHAR(50) NOT NULL, KEY USING HASH(fname) ) ENGINE=MEMORY;

Chứa dữ liệu:

SELECT * FROM testhash;

+--------+-----------+

| fname | lname |

+--------+-----------+

| Arjen | Lentz |

| Baron | Schwartz |

| Peter | Zaitsev |

| Vadim | Tkachenko |

+--------+-----------+

Bây giờ giả sử index sử dụng 1 hàm hash giả tưởng tên là f(), trả về các giá trị như sau:

f('Arjen')= 2323 f('Baron')= 7437 f('Peter')= 8784 f('Vadim')= 2458

Index hash table sẽ như thế này:

Slot Value 2323 Pointer to row 1 2458 Pointer to row 4 7437 Pointer to row 2 8784 Pointer to row 3

Chú ý rằng những slot của hast table được sắp xếp theo thứ tự, nhưng row thì không. Bây h thì thực hiện query: mysql> SELECT lname FROM testhash WHERE fname='Peter'; MySQL sẽ tính toán giá trị hash của ‘Peter’ và sử dụng nó để tìm kiếm index. Bởi vì f(‘Peter’) = 8784, MySQL sẽ tìm vào index có giá trị 8784 và pointer của hàng đó trỏ vào row 3. Bởi vì index chính nó lưu trữ một giá trị nhỏ, hash index rất gọn và tìm kiếm cũng rất nhanh. Tuy nhiên, hash index có những hạn chế sau:

• Bởi vì index chứa hash code và cả pointer thay vì chính giá trị column, MySQL không thể dùng giá trị của index để tránh khỏi đọc giá trị của column đó. May mắn là access trên memory row rất là nhanh nên nó k phải giảm hiệu năng.
• MySQL không thể dùng hash index để sắp xếp vì chúng không sắp xếp row theo thứ tự.
• Hash index không support tìm kiếm 1 phần của key, bởi vì tính toán hash phụ thuộc vào toàn bộ value. Nếu bạn có index của A, B nhưng chỉ sử dụng where với mình A thì không được.
• Hash index hỗ trợ toán tử so so sánh bằng như =, in, và <=>. Nó không thể tìm kiếm theo range.
• Access data trong hash index rất nhanh trừ ki bị trường hợp 1 key nhiều value. Ví dụ, nếu bạn thêm 1 row, linked list phải thêm vào pointer của row đó, khi xóa đi thì lại phải tìm lại đến index đó rồi xóa trong linked list đi. Có thể làm mất thời gian.

Những hạn chế này làm cho hash index chỉ hữu dụng trong một vài trường hợp đặc biệt. Tuy nhiên, khi chúng được sử dụng đúng hoàn cảnh thì performance được nâng cao khủng khiếp. Một ví dụ về data-warehousing application sử dụng rất nhiều star schema cho nên bạn phải join rất nhiều bảng. Hash index là lựa chọn tuyệt vời. InnoDB có một tính năng đặc biệt là adaptive hash indexes. Khi InnoDB chú ý rằng một số index đặc biệt được access nhiều lần, nó sẽ build hash index cho row đó lên trên trước B-Tree index để làm tăng tốc tìm kiếm index. Công việc này được thực hiện tự động và bạn không làm cách nào thay đổi nó mà chỉ tắt nó đi được thôi.

Building your own hash indexes.

Nếu storage engine của bạn không support hash index, bạn có thể giả lập nó bằng cách tương tự như InnoDB sử dụng. Nó giúp bạn đạt được một số lợi ích của hash index như size nhỏ, look up fast.

Ý tưởng rất đơn giản: create pseudohash index lên trên B-Tree index. Nó không giống chính xác hash lắm bởi vì nó vẫn sử dụng B-Tree index lookup. Nhưng nó vẫn sử dụng hash lookup thay vì value look up. Tất cả những gì cần làm là viết thêm hash function đằng sau where trong câu query.

Một ví dụ của cách tiếp cận này là với URL lookup. URL sẽ làm B-Tree phình to vì nó dài, bạn có thể query bình thường như sau:

mysql> SELECT id FROM url WHERE url="http://www.mysql.com";

Nhưng nếu bỏ đi index của url column và thêm index url_crc column, thì bạn có thể làm như thế này:

SELECT id FROM url WHERE url="http://www.mysql.com" AND url_crc=CRC32("http://www.mysql.com");

Cách này chạy nhanh hơn vì MySQL query optimizer nhận thấy index nhỏ, nhanh của url_crc và sẽ thực hiện index lookup trước. Kể cả khi có nhiều hàng chung url_crc thì nó vẫn rất nhanh nếu bạn muốn tìm chính xác. Một cách khác là đánh index cho toàn bộ url column, nhưng sẽ chạy rất lâu.

Một điểm trừ của cách tiếp cận này là nó cần quản lý hash value. Bạn có thể làm bằng tay hoặc từ MySQL 5.0 trở đi có thể dùng trigger. Ví dụ tiếp theo sẽ show làm cách nào để dùng trigger update url_crc column khi bạn insert hay update row. Đầu tiên hãy tạo table:

CREATE TABLE pseudohash ( id int unsigned NOT NULL auto_increment, url varchar(255) NOT NULL, url_crc int unsigned NOT NULL DEFAULT 0, PRIMARY KEY(id) );

Bây giờ tạo trigger. Chúng tôi dùng DELIMITER nên có thể sử dụng dấu chấm phẩy trong trigger:

DELIMITER // CREATE TRIGGER pseudohash_crc_ins BEFORE INSERT ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc=crc32(NEW.url); END; // CREATE TRIGGER pseudohash_crc_upd BEFORE UPDATE ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc=crc32(NEW.url); END; // DELIMITER ;

Những việc còn lại chỉ là đảm bảo trigger sẽ quản lý hash:

INSERT INTO pseudohash (url) VALUES ('http://www.mysql.com'); SELECT * FROM pseudohash;

+----+----------------------+------------+

| id | url | url_crc |

+----+----------------------+------------+

| 1 | http://www.mysql.com | 1560514994 |

+----+----------------------+------------+

UPDATE pseudohash SET url='http://www.mysql.com/' WHERE id=1; SELECT * FROM pseudohash;

+----+---------------------- +------------+

| id | url | url_crc |

+----+---------------------- +------------+

| 1 | http://www.mysql.com/ | 1558250469 |

+----+---------------------- +------------+

Nếu bạn sử dụng cách tiếp cận này, bạn ko nên sử dụng SHA1() hoặc MD5() function. Chúng sử dụng string dài, sẽ làm tốt space và tăng response time. Chúng là những hàm mã hóa mạnh được thiết kể để tránh tối đa trùng lặp nhưng nó không phải là mục đích của bạn ở đây. Một hàm hash đơn giản có thể gây ra sự trùng lặp chấp nhân được và cho performance cao hơn.

Nếu bảng của bạn có rất nhiều row và CRC32() sảy ra rất nhiều collisions, hãy sử dụng 64-bit hash function. Chắc chắn là phải sử dụng fucntion trả về integer không phải string. Một cách để implement 64-bit hash function là chỉ lấy 1 phần giá trị của MD5(). Cách này có thể thiếu hiệu quả hơn so với tự define hash function:

SELECT CONV(RIGHT(MD5('http://www.mysql.com/'), 16), 16, 10) AS HASH64;

+---------------------+

| HASH64 |

+---------------------+

| 9761173720318281581 |

+---------------------+