pg_trgm là gì? Tìm một đoạn giữa chuỗi bằng mẩu ba ký tự

Người dùng chỉ nhớ một phần biển số là 600.5. Để tìm chiếc xe, ứng dụng chạy câu lệnh:

SELECT *
FROM vehicles
WHERE plate LIKE '%600.5%';

Câu lệnh này tìm được những biển có chứa 600.5, chẳng hạn 47P-600.55 và 29A-600.59.

Nhưng như bài trước đã thấy, vì đoạn cần tìm có thể nằm ở bất kỳ đâu trong biển số, index B-tree thông thường không giúp PostgreSQL tìm thẳng đến những dòng phù hợp. Với bảng có 5 triệu xe, PostgreSQL phải đọc cả bảng để tìm ra 500 kết quả.

PostgreSQL có một phần mở rộng tên là pg_trgm, cung cấp một cách khác để xử lý bài toán này: chia chuỗi thành những mẩu ba ký tự.

Những mẩu ba ký tự giúp tìm biển số như thế nào?

PostgreSQL có các phần mở rộng

PostgreSQL có sẵn những tính năng cơ bản để lưu dữ liệu, chạy câu lệnh SQL và tạo index. Nhưng mỗi ứng dụng lại có những nhu cầu khác nhau.

Một ứng dụng bản đồ cần làm việc với vị trí và khoảng cách. Một ứng dụng bán hàng có thể cần tìm tên sản phẩm khi người dùng gõ sai. Nếu đưa tất cả những tính năng này vào phần cơ bản, PostgreSQL sẽ phải mang theo nhiều thứ mà không phải ứng dụng nào cũng cần.

Vì vậy, PostgreSQL cho phép bổ sung tính năng thông qua phần mở rộng (extension).

Có thể hình dung extension như một gói bổ sung cho database. Tùy vào mục đích, một extension có thể thêm hàm, kiểu dữ liệu, toán tử hoặc khả năng hỗ trợ index.

pg_trgm là một extension như vậy. Nó cung cấp các công cụ để làm việc với những mẩu ba ký tự trong chuỗi. Nhờ đó, PostgreSQL có thêm cách để hỗ trợ tìm kiếm một đoạn nằm giữa chuỗi và tìm các chuỗi gần giống nhau.

Để sử dụng, trước tiên ta kích hoạt extension trong database:

CREATE EXTENSION IF NOT EXISTS pg_trgm;

IF NOT EXISTS nghĩa là nếu pg_trgm đã được kích hoạt thì không cần tạo lại.

Lệnh này áp dụng cho database hiện tại. Nếu có nhiều database và muốn dùng pg_trgm trong từng database, ta cần kích hoạt nó ở từng nơi.

Sau khi kích hoạt, ta có thể thử cách pg_trgm chia một chuỗi thành các mẩu.

Trigram là gì?

Trigram là một nhóm gồm ba ký tự liên tiếp trong chuỗi.

Với chuỗi 60055, ta lấy ba ký tự đầu tiên, rồi dịch sang phải từng bước:

Kết quả là ba mẩu: 600, 005 và 055.

Nếu một chuỗi chứa 60055, nó chắc chắn cũng chứa ba mẩu này. pg_trgm dựa vào ý tưởng đó để giúp tìm kiếm trong chuỗi.

pg_trgm chia biển số như thế nào?

Xét biển số 47P-600.55. Khi tạo trigram, pg_trgm dùng dấu - và . để tách biển số thành ba nhóm: 47p, 600 và 55.

Với mỗi nhóm, nó thêm hai khoảng trắng ở đầu và một khoảng trắng ở cuối, rồi lấy các mẩu ba ký tự như trong hình:

Các khoảng trắng giúp đánh dấu điểm bắt đầu và kết thúc của mỗi nhóm. Chẳng hạn, mẩu ␣␣6 cho biết một nhóm bắt đầu bằng 6; còn 00␣ cho biết một nhóm kết thúc bằng 00.

Ta có thể dùng hàm show_trgm để tự xem kết quả:

SELECT show_trgm('47P-600.55');

{"  4","  5","  6"," 47"," 55"," 60","00 ",47p,"55 ",600,"7p "}

Trong kết quả SQL, khoảng trắng được in trực tiếp; trong hình, chúng được biểu diễn bằng ký hiệu ␣ để dễ nhìn.

Ta đã biết cách chia một biển số. Vậy đoạn người dùng nhập vào được xử lý như thế nào?

Mẫu tìm kiếm cho ra những mẩu nào?

Câu truy vấn ban đầu tìm mẫu:

LIKE '%600.5%'

Dấu % ở đầu cho phép có bất kỳ ký tự nào trước 600.5. Dấu % ở cuối cho phép có bất kỳ ký tự nào sau nó.

Vì vậy, cả hai biển dưới đây đều khớp:

47P-600.55
29A-1600.59

Chú ý rằng trong biển thứ hai, trước 600 còn có số 1. Ta không thể chắc nhóm chứa 600 bắt đầu bằng 6.

Khi phân tích mẫu LIKE, pg_trgm chỉ dựa vào những mẩu chắc chắn phải có ở mọi biển số khớp với mẫu đó.

Với %600.5%, có ba mẩu như vậy:

Mẩu	Vì sao biển khớp phải có?
600	Vì ba ký tự 600 nằm liền nhau trong đoạn cần tìm.
00␣	Vì dấu chấm ngay sau 600 đánh dấu kết thúc một nhóm.
␣␣5	Vì số 5 ngay sau dấu chấm bắt đầu một nhóm mới.

Còn mẩu ␣␣6 thì không chắc có. Biển 29A-1600.59 vẫn khớp với LIKE '%600.5%', nhưng nhóm 1600 bắt đầu bằng 1, không phải 6.

Tương tự, ta không thể chắc nhóm bắt đầu bằng 5 kết thúc ngay sau số 5, vì sau đó có thể còn ký tự khác.

Bây giờ, hãy dùng ba mẩu chắc chắn đó để xem biển nào có thể khớp.

Dùng các mẩu để tìm biển số

Giả sử ta có ba biển:

47P-600.55
51A-600.45
29A-1600.32

Đối chiếu từng biển với ba mẩu cần tìm:

Biển số	Có 600?	Có 00␣?	Có ␣␣5?	Có đủ ba mẩu?
47P-600.55	Có	Có	Có	Có
51A-600.45	Có	Có	Có	Có
29A-1600.32	Có	Có	Không	Không

Biển 29A-1600.32 không có mẩu ␣␣5. Nó không thể chứa đoạn 600.5, nên có thể bị loại.

Hai biển còn lại đều có đủ ba mẩu. Chúng trở thành ứng viên: những biển có thể khớp và cần được kiểm tra tiếp.

Tại sao không thể kết luận ngay rằng cả hai đều khớp?

Có đủ mẩu chưa chắc đã khớp

Nhìn lại hai ứng viên:

47P-600.55
51A-600.45

Cả hai đều có mẩu ␣␣5, nhưng mẩu đó đến từ hai vị trí khác nhau:

• Với 47P-600.55, nhóm 55 bắt đầu bằng 5.
• Với 51A-600.45, nhóm 51A bắt đầu bằng 5.

Biển thứ hai có đủ các mẩu, nhưng số 5 của nó nằm ở đầu biển. Ngay sau 600. là số 4, nên biển này không chứa đoạn 600.5.

Vì vậy, sau khi chọn ra các ứng viên dựa trên trigram, PostgreSQL vẫn cần kiểm tra lại điều kiện LIKE trên biển số thật.

Trong bảng thực hành 5 triệu xe, khi sử dụng một index hỗ trợ tìm theo trigram:

1. PostgreSQL tìm được 1.008 ứng viên có đủ các mẩu cần thiết.
2. PostgreSQL kiểm tra lại điều kiện LIKE trên các ứng viên.
3. 508 biển bị loại, còn lại 500 biển khớp.

Bước kiểm tra lại này được gọi là recheck.

Có đủ các mẩu là điều kiện cần, nhưng chưa đủ để kết luận chuỗi khớp.

Đoạn cần tìm quá ngắn thì sao?

Hãy so sánh hai câu truy vấn:

WHERE plate LIKE '%600%'

WHERE plate LIKE '%60%'

Với %600%, phần cố định ở giữa có ba ký tự, nên có thể dùng mẩu 600 để tìm các biển ứng viên.

Với %60%, phần cố định chỉ có hai ký tự. Hai bên lại là %, nên trước và sau 60 có thể là bất kỳ thứ gì. PostgreSQL không biết 60 nằm ở đầu, giữa hay cuối một nhóm và không rút ra được mẩu ba ký tự nào để thu hẹp tìm kiếm.

Trong bảng thực hành, PostgreSQL chọn quét cả bảng cho câu LIKE '%60%'.

Ngay cả khi đoạn cần tìm đủ ba ký tự, hiệu quả vẫn phụ thuộc vào dữ liệu. Nếu mẩu đó xuất hiện trong gần như mọi biển số, nó cũng không giúp loại được nhiều dòng.

pg_trgm còn giúp tìm chuỗi gần giống nhau

Cho đến lúc này, ta dùng trigram để hỗ trợ câu LIKE. Nhưng LIKE vẫn yêu cầu đoạn ký tự phải khớp chính xác.

Giả sử người dùng muốn tìm biển:

47P-600.55

Nhưng lại gõ thiếu dấu chấm:

47P-60055

Câu lệnh sau sẽ không tìm thấy biển đó:

SELECT *
FROM vehicles
WHERE plate LIKE '%47P-60055%';

Lý do là chuỗi 47P-60055 không xuất hiện nguyên vẹn trong 47P-600.55.

Trong trường hợp này, pg_trgm có thể giúp theo một cách khác: so sánh các mẩu của hai chuỗi để tính độ giống nhau.

SELECT similarity('47P-60055', '47P-600.55');

Hàm similarity trả về một số từ 0 đến 1. Số càng gần 1, hai chuỗi càng giống nhau theo cách tính dựa trên trigram của pg_trgm.

Ứng dụng có thể dùng thông tin đó để gợi ý những biển gần giống khi người dùng gõ sai. Nhưng đây là phép tìm khác với LIKE: ứng dụng cần quyết định mức độ giống nào là đủ và sắp xếp các gợi ý như thế nào.

Làm sao tìm nhanh các mẩu?

Đến đây, ta đã thấy vì sao việc chia chuỗi thành các mẩu ba ký tự có ích: nếu biển số thiếu một mẩu bắt buộc, ta biết nó không thể khớp.

Nhưng vẫn còn một vấn đề.

Giả sử cần tìm mẩu 600. Nếu PostgreSQL phải đọc cả 5 triệu biển số rồi kiểm tra từng biển có mẩu đó hay không, nó vẫn phải quét cả bảng.

Và việc kích hoạt pg_trgm cũng không tự tạo ra một index để tra cứu các mẩu.

Làm sao lưu các mẩu để tìm nhanh những biển số chứa chúng?