Tìm các chuỗi tương tự với PostgreSQL một cách nhanh chóng

Theo cách bạn có nó, sự tương đồng giữa mọi phần tử và mọi phần tử khác của bảng phải được tính toán (gần như là một phép nối chéo). Nếu bảng của bạn có 1000 hàng, đó đã là 1.000.000 (!) Phép tính tương tự, trước đó chúng có thể được kiểm tra theo tình trạng và sắp xếp. Cân khủng khiếp.

Sử dụng SET pg_trgm.similarity_threshold và % thay vào đó. Cả hai đều được cung cấp bởi pg_trgm mô-đun. Bằng cách này, chỉ số GiST hình bát quái có thể được sử dụng để tạo ra hiệu quả lớn.

Tham số cấu hình pg_trgm.similarity_threshold đã thay thế các hàm set_limit() và show_limit() trong Postgres 9.6. Các chức năng không dùng nữa vẫn hoạt động (kể từ Postgres 13). Ngoài ra, hiệu suất của các chỉ số GIN và GiST được cải thiện theo nhiều cách kể từ Postgres 9.1.

Hãy thử thay thế:

SET pg_trgm.similarity_threshold = 0.8;  -- Postgres 9.6 or later
  
SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   names n1
JOIN   names n2 ON n1.name <> n2.name
               AND n1.name % n2.name
ORDER  BY sim DESC;

Nhanh hơn theo mức độ lớn, nhưng vẫn chậm.

pg_trgm.similarity_threshold là một tùy chọn "tùy chỉnh", có thể được xử lý giống như bất kỳ tùy chọn nào khác. Xem:

Truy vấn một tham số (cài đặt postgresql.conf) như "max_connections"

Bạn có thể muốn hạn chế số lượng các cặp có thể có bằng cách thêm các điều kiện tiên quyết (như khớp các chữ cái đầu tiên) trước tham gia chéo (và hỗ trợ điều đó với một chỉ số chức năng phù hợp). Hiệu suất của tham gia chéo xấu đi với O (N²) .

Điều này không hoạt động bởi vì bạn không thể tham chiếu đến các cột đầu ra trong WHERE hoặc HAVING mệnh đề:

WHERE ... sim > 0.8

Đó là theo tiêu chuẩn SQL (được xử lý khá lỏng lẻo bởi một số RDBMS khác). Mặt khác:

ORDER BY sim DESC

Hoạt động bởi vì các cột đầu ra có thể được sử dụng trong GROUP BY và ORDER BY . Xem:

Kết quả tính toán sử dụng lại PostgreSQL trong một truy vấn chọn lọc

Trường hợp thử nghiệm

Tôi đã chạy thử nghiệm nhanh trên máy chủ thử nghiệm cũ của mình để xác minh các tuyên bố của mình.
PostgreSQL 9.1.4. Thời gian được thực hiện với EXPLAIN ANALYZE (tốt nhất trong số 5).

CREATE TEMP table t AS 
SELECT some_col AS name FROM some_table LIMIT 1000;  -- real life test strings

Vòng kiểm tra đầu tiên với chỉ số GIN:

CREATE INDEX t_gin ON t USING gin(name gin_trgm_ops);  -- round1: with GIN index

Vòng kiểm tra thứ hai với chỉ số GIST:

DROP INDEX t_gin;
CREATE INDEX t_gist ON t USING gist(name gist_trgm_ops);

Truy vấn mới:

SELECT set_limit(0.8);

SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   t n1
JOIN   t n2 ON n1.name <> n2.name
           AND n1.name % n2.name
ORDER  BY sim DESC;

Đã sử dụng chỉ mục GIN, 64 lần truy cập:tổng thời gian chạy:484,022 mili giây
Đã sử dụng chỉ mục GIST, 64 lần truy cập:tổng thời gian chạy: 248,772 mili giây

Truy vấn cũ:

SELECT (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
FROM   t n1, t n2
WHERE  n1.name != n2.name
AND    similarity(n1.name, n2.name) > 0.8
ORDER  BY sim DESC;

Chỉ mục GIN không đã sử dụng, 64 lần truy cập:tổng thời gian chạy:6345,833 mili giây
Chỉ mục GIST không đã sử dụng, 64 lần truy cập:tổng thời gian chạy:6335,975 mili giây

Nếu không thì kết quả giống hệt nhau. Lời khuyên là tốt. Và điều này là cho chỉ 1000 hàng !

GIN hay GiST?

GIN thường cung cấp hiệu suất đọc vượt trội:

Sự khác biệt giữa chỉ số GiST và GIN

Nhưng không phải trong trường hợp cụ thể này!

Điều này có thể được triển khai khá hiệu quả bởi chỉ mục GiST, nhưng không phải chỉ mục byGIN.

Chỉ mục nhiều cột trên 3 trường có kiểu dữ liệu không đồng nhất