[Backend Masterclass] Tại sao LIKE '%keyword%' là kẻ thù của B-Tree Index và Giải pháp Full-text Search

Chào anh em! khách hàng thì luôn muốn trải nghiệm hoàn hỏa. Họ vào một trang thương mại điện tự, gõ bừa cụm từ "chống nắng La Roche" và hi vọng app sẽ nhả ra chính xác sản phẩm "Kem chống nắng La Roche-Posay Anthelios" chỉ trong 50 mili-giây.

Với bản năng của một dev mới vào nghề, câu SQL đầu tiên nảy số trong đầu anh em sẽ là:

SELECT * FROM products WHERE name LIKE '%chống nắng La Roche%';

và bùm! Nếu database của bạn có hàng triệu sản phẩm, câu query này sẽ bắt server "đứng hình" mất vài giây. Ở bài trước , mình đã dặn anh em phải đánh Index. Nhưng đau đớn thay, B-Tree Index hoàn toàn bị vô hiệu hóa khi bạn đặt dấu % ở đầu chuỗi. Tại sao lại có chuyện ngang hàng trái như này?

1. Giải ngố: Tại sao B-Tree "bất lực" trước %keyword%?

Để hiểu được cốt lõi, anh em phải nhớ lại nguyên lý Left-Most Prefix (Từ trái sang phải) của cấu trúc cây B-Tree. Hãy tưởng tượng B-Tree Index giống hệt một Cuốn danh bạ điện thoại được sắp xếp theo thứ tự bảng chữ cái alphabet (A-Z).

Trường hợp 1: LIKE 'Kem%' (Không có % ở đầu) Giống như sếp bảo bạn: "Tìm cho anh những người tên bắt đầu bằng chữ K". Rất dễ! Bạn chỉ cần lật danh bạ đến vần K, đọc một loạt tên, đến khi nào chuyển sang vần L thì dừng lại. Index hoạt động hoàn hảo!
Trường hợp 2: LIKE '%chống nắng%' (Có % ở đầu) Giờ sếp bảo: "Tìm cho anh những người mà trong tên có chứa chữ 'chống nắng', nằm ở đâu cũng được". Lúc này cuốn danh bạ hoàn toàn vô dụng! Chữ "chống nắng" có thể nằm ở người tên "Kem chống nắng", hoặc "Sữa chống nắng", hoặc "Xịt chống nắng"... Vì dữ liệu đang được xếp theo chữ cái ĐẦU TIÊN, bạn không có cách nào khác ngoài việc... lật từng trang một từ đầu đến cuối cuốn danh bạ để soi xem tên ai có chứa từ đó.

Đó chính là thảm họa Full Table Scan. Database phải cày nát ổ cứng để đọc từng dòng của hàng triệu sản phẩm. Server CPU 100% là điều tất yếu.

2. Inverted Index (Chỉ mục đảo ngược) - Cuộc cách mạng tư duy

Để giải quyết bài toán này, các kĩ sư dữ liệu không dùng cấu trúc danh bạ điện thoại (B-Tree) nữa. Họ lấy cảm hứng từ phần Mục lục tra cứu từ vựng (Index) ở cuối những cuốn sách bách khoa toàn thư.

Khái niệm này gọi là Inverted Index.

Thay vì lưu: Sản phẩm 1 -> "Kem chống nắng La Roche-Posay" Nó sẽ làm một bước gọi là Tokenization (Tách từ). Nó băm cái tên sản phẩm ra thành các từ đơn lẻ và map ngược lại ID của sản phẩm:

| Keyword (Token) | Nằm ở các Document ID (Sản phẩm) | | kem | 1, 5, 89 | | chống | 1, 2, 5, 104 | | nắng | 1, 2, 5, 104 | | la | 1, 9, 200 | | roche | 1, 9, 200 | | posay | 1, 9, 200 |

Bây giờ, khi khách hàng gõ search "chống nắng", hệ thống không thèm đọc bảng Products nữa. Nó chọc thẳng vào bảng Inverted Index, tìm đúng dòng có chữ chống và nắng. Bảng này nói rằng: "Ê, 2 chữ này xuất hiện chung ở các ID số 1, 2, 5, 104 này!".

Phép màu xuất hiện! Thời gian truy xuất lại quay về O(1) hoặc O(log N) siêu tốc, bất kể chuỗi bạn tìm nằm ở giữa hay cuối câu.

3. Quái vật mang tên Elasticsearch

Các hệ quản trị CSDL quan hệ như MySQL hay PostgreSQL mặc dù có hỗ trợ Full-text Search cơ bản, nhưng chúng không được sinh ra để làm việc này một cách chuyên nghiệp. Khi dữ liệu lên đến hàng trăm GB, hoặc cần tìm kiếm gần đúng (Typo/Fuzzy search - gõ "chong nang" vẫn ra "chống nắng"), thì SQL truyền thống "khóc thét".

Đó là lúc anh em cần rước một "Quái vật" chuyên dụng về hệ thống: Elasticsearch.

Elasticsearch là một search engine phân tán, được build hoàn toàn dựa trên lõi kiến trúc Inverted Index. Sức mạnh của Elasticsearch khủng khiếp ở chỗ:

Tốc độ: Truy vấn hàng trăm triệu records trả về kết quả dưới 50ms.
Nhiều ngôn ngữ: Nó có các bộ tokenizer xử lý tiếng Việt cực kì xịn (chia từ "chống nắng" thành 1 token thay vì tách chữ "chống" và "nắng").
Scoring (Chấm điểm độ phù hợp): Không chỉ tìm ra, nó còn tính toán xem sản phẩm nào khớp với từ khóa nhất để đẩy lên Top 1 (bán hàng mà, cái này cực kì quan trọng).

Tổng kết & Next step

Tóm lại, nếu anh em làm tính năng Search có thanh công cụ tìm kiếm tự do cho người dùng:

Đừng bao giờ đụng đến LIKE '%keyword%' trên các bảng dữ liệu lớn.
Nếu dự án nhỏ, có thể dùng tạm tính năng Full-text Search của MySQL/PostgreSQL.
Nếu dự án lớn, data to, hãy mạnh dạn đề xuất sếp đưa Elasticsearch vào stack công nghệ.

Càng đào sâu, hệ thống của chúng ta càng có nhiều "đồ chơi". Ban đầu chỉ có con App và con Database. Giờ chúng ta đã có thêm Redis làm cache, có Elasticsearch làm search engine.

Nhưng anh em có nhận ra vấn đề không? Khi user cập nhật tên sản phẩm, chúng ta phải ghi vào MySQL, rồi phải ghi vào Redis (xóa cache), rồi lại phải call API sang Elasticsearch để update Inverted Index. Ghi 3 chỗ cùng lúc, nếu 1 chỗ xịt thì sao? Dữ liệu sẽ bất đồng bộ (Inconsistency) ngay!

Để giải bài toán giao tiếp bất đồng bộ giữa các component này, ở bài viết tới, mình sẽ dắt anh em làm quen với một khái niệm tối thượng trong Microservices:

👉 Bài sau: Message Broker và Kafka - Kẻ điều phối luồng dữ liệu khổng lồ của hệ thống.

Anh em thấy Inverted Index có ảo diệu không? Để lại comment và upvote nếu bài viết giúp anh em né được những "bãi mìn" trong tương lai nhé!