Liên hệ
IBSurgeon
Trang này được dịch bằng máy. Đọc bản gốc tiếng Anh. English

Chỉ mục NGRAM (HQbird): tìm kiếm chuỗi con với LIKE '%...%' và CONTAINING

← HQbird server features

Chỉ mục NGRAM tìm các hàng theo chuỗi con của một giá trị văn bản, để WHERE col LIKE '%error 404%' không cần đọc toàn bộ bảng. Nó dùng sparse n-gram, phương pháp của tính năng tìm kiếm mã nguồn GitHub (cách hiện thực theo SereneDB).

Cú pháp

CREATE NGRAM INDEX name ON table (column);
CREATE NGRAM INDEX name ON table COMPUTED BY (expression);
CREATE NGRAM INDEX name ON table (column) WHERE condition;
  • Một cột CHAR, VARCHAR hoặc BLOB SUB_TYPE TEXT, hoặc một biểu thức có kết quả là văn bản hoặc BLOB văn bản.
  • Cho phép mọi bộ ký tự và collation, kể cả không phân biệt hoa thường và dấu (UNICODE_CI, UNICODE_CI_AI) và các collation ICU (UNICODE, UTF8 với một locale).
  • Chỉ mục từng phần (WHERE) chỉ được dùng nếu truy vấn có cùng điều kiện.
  • Không cho phép: UNIQUE, DESCENDING, nhiều cột, CONCURRENTLY, BLOB nhị phân, mảng.
  • ALTER INDEX ... ACTIVE | INACTIVE, SET STATISTICS INDEX, DROP INDEX hoạt động như bình thường.
  • SHOW INDEX in ra NGRAM INDEX, isql -x in ra CREATE NGRAM INDEX.
  • ODS của cơ sở dữ liệu phải là 13.1 (mặc định của Firebird 5).

Các truy vấn sử dụng chỉ mục

SELECT ... WHERE col LIKE '%needle%';
SELECT ... WHERE col LIKE '%part1%part2%';
SELECT ... WHERE col LIKE 'pre_fix%' ESCAPE '\';
SELECT ... WHERE col LIKE ?;                   -- the pattern is a parameter
SELECT ... WHERE UPPER(col) LIKE '%NEEDLE%';  -- with an index COMPUTED BY (UPPER(col))
SELECT ... WHERE col CONTAINING 'needle';     -- see "CONTAINING" below
  • Mẫu phải có một phần literal dài ít nhất 3 ký tự (giữa % và _). Mẫu hằng không có phần như vậy sẽ không dùng chỉ mục. Tham số không có phần như vậy sẽ dẫn đến quét toàn bộ (kết quả vẫn đúng).
  • Chỉ mục có thể được kết hợp với các chỉ mục khác (AND).
  • LIKE luôn được kiểm tra lại cho mỗi hàng tìm thấy, nên chỉ mục không bao giờ thay đổi kết quả của truy vấn.
  • OR của nhiều LIKE dùng chỉ mục cho từng cái.
  • Không dùng cho: SIMILAR TO, STARTING WITH, =, các khoảng, IS NULL, ORDER BY, MIN/MAX.

Collation

Các khóa của chỉ mục được tạo từ cùng dạng chuẩn tắc của văn bản mà LIKE so sánh. Vì vậy với collation không phân biệt hoa thường, LIKE không phân biệt hoa thường, và chỉ mục tìm đúng các hàng đó:

CREATE TABLE doc (id INT, title VARCHAR(200) CHARACTER SET UTF8 COLLATE UNICODE_CI_AI);
CREATE NGRAM INDEX doc_title_ng ON doc (title);
SELECT id FROM doc WHERE title LIKE '%cafe%';   -- finds 'Café', 'CAFE', 'café'

Dạng chuẩn tắc của các collation ICU phụ thuộc vào phiên bản ICU, giống như với các chỉ mục thông thường. Sau khi thay đổi thư viện ICU, hãy dựng lại chỉ mục (ALTER INDEX ... INACTIVE, rồi ACTIVE).

CONTAINING

col CONTAINING 'x' không phân biệt hoa thường. Nó dùng chỉ mục NGRAM trong hai trường hợp:

  • col là UTF8 với collation Unicode không phân biệt hoa thường (UNICODE_CI, UNICODE_CI_AI): chỉ mục trên chính cột đó;
  • collation khác: chỉ mục COMPUTED BY (UPPER(col)). Viết truy vấn như bình thường, col CONTAINING 'x': optimizer tự tìm ra chỉ mục UPPER.

Không dùng cho các bộ ký tự đa byte khác UTF8 và UNICODE_FSS (ví dụ SJIS_0208) với collation mặc định của chúng: ở đó CONTAINING so sánh byte, không phải ký tự.

BLOB văn bản

CREATE TABLE note (id INT, body BLOB SUB_TYPE TEXT CHARACTER SET UTF8);
CREATE NGRAM INDEX note_body_ng ON note (body);
CREATE NGRAM INDEX note_body_up_ng ON note COMPUTED BY (UPPER(body));
SELECT id FROM note WHERE body LIKE '%timeout%';
SELECT id FROM note WHERE body CONTAINING 'Timeout';  -- uses note_body_up_ng
  • Chỉ mục chứa các gram của toàn bộ BLOB, với mọi độ dài. Server tạo các gram theo cửa sổ 64K ký tự và chỉ giữ các gram phân biệt, nên bộ nhớ cho các khóa phụ thuộc vào số gram phân biệt, không phụ thuộc vào kích thước BLOB. Một BLOB trong bộ ký tự đa byte được đọc toàn bộ, giống như LIKE đọc nó.
  • BLOB được đọc khi một hàng được chèn, khi BLOB bị thay đổi, và một lần nữa khi garbage collection xóa phiên bản cũ. Một UPDATE trên các cột khác giữ nguyên BLOB và không đọc nó (cũng vậy với chỉ mục COMPUTED BY (UPPER(body))).
  • Chỉ mục có một mục cho mỗi gram phân biệt của một hàng. Các tài liệu dài lặp lại nhiều gram: các tệp nguồn của Firebird cho 0,3 mục trên mỗi ký tự, các dòng ngắn 1,4.
  • Nạp dữ liệu trước, rồi tạo chỉ mục (xem “Kích thước và chi phí”).

Kết quả PLAN:

PLAN (MSG INDEX (MSG_TEXT_NG))

Select Expression
    -> Filter
        -> Table "MSG" Access By ID
            -> Bitmap
                -> Index "MSG_TEXT_NG" N-gram Scan

Kích thước và chi phí

Đo trên các dòng mã nguồn Firebird (953 000 hàng, 27 triệu ký tự): chỉ mục 188 MB (gấp 7,2 lần văn bản, gấp 1,7 lần bảng), dựng trong 16 s; LIKE '%word%' nhanh hơn quét toàn bộ từ 12 đến 4000 lần (từ 0,2 ms cho các từ hiếm đến 50 ms cho một từ có trong 35 000 hàng, so với 600 ms cho quét). Với UNICODE_CI_AI quét chậm hơn 6 lần (3,5 s), chỉ mục thì không: LIKE và CONTAINING nhanh hơn từ 20 đến 8000 lần.

  • Khoảng 1,4 mục chỉ mục trên mỗi ký tự văn bản (mỗi mục là một hash gram 8 byte và một số bản ghi). Hãy dự kiến chỉ mục lớn hơn văn bản vài lần.
  • Mỗi lần chèn thêm khoảng 1,4 mục B-tree trên mỗi ký tự: chèn vào một bảng có chỉ mục NGRAM chậm hơn nhiều so với không có. Mục tiêu là dữ liệu chủ yếu ghi thêm (log, tin nhắn, tài liệu) với ít cập nhật.
  • Cập nhật chỉ chèn các gram mới. Các gram cũ được garbage collection xóa khi không còn phiên bản bản ghi nào cần chúng nữa.
  • Việc tạo chỉ mục để lại 5% không gian trống trong mỗi trang, như CONCURRENTLY làm. Các gram của một bản ghi nằm trong nhiều trang lá; nếu không có không gian trống, các cập nhật đầu tiên sau khi tạo sẽ tách gần như mọi trang lá.
  • Một UPDATE không thay đổi cột được đánh chỉ mục (với chỉ mục trên biểu thức: các cột mà biểu thức dùng) hoàn toàn không tính gram.
  • Với nạp hàng loạt, hãy tạo chỉ mục sau khi nạp, hoặc đặt nó INACTIVE trong lúc nạp. 1 163 tệp nguồn (28 triệu ký tự) dưới dạng BLOB: nạp với hai chỉ mục NGRAM 419 s; nạp không có chỉ mục 0,6 s, rồi tạo cả hai chỉ mục 10,7 s.
  • Việc tạo chỉ mục sắp xếp tất cả các gram: không gian tạm khoảng 20 byte mỗi gram. ParallelWorkers tăng tốc việc tạo.

Tương thích với các server không hỗ trợ NGRAM

Chỉ mục được lưu trong ODS 13.1. Điều kiện của nó (RDB$CONDITION_BLR) bắt đầu bằng một biểu thức guard gây lỗi chuyển đổi. Một server không hỗ trợ NGRAM (Firebird 5.0.x gốc, HQbird cũ hơn):

  • mở được cơ sở dữ liệu; SELECT cho kết quả đúng và không dùng chỉ mục NGRAM;
  • từ chối INSERT và UPDATE vào bảng với lỗi conversion error from string "HQBIRD NGRAM INDEX: use HQbird server" (nên chỉ mục không bao giờ bị hỏng);
  • cho phép DELETE và sweep (chỉ mục giữ thêm các mục: chỉ tốn kích thước);
Query time: full scan vs NGRAM index
Speed-up of NGRAM vs full scan
Size: text, table, and NGRAM index
BLOB bulk load with and without NGRAM during load
  • không thể kích hoạt chỉ mục.

Đã kiểm thử với Firebird 5.0.4.1812 gốc và HQbird 5.0.4.1773. Các công cụ bên thứ ba có thể hiển thị chỉ mục là DESCENDING với một mệnh đề WHERE.

gbak sao lưu và phục hồi các chỉ mục NGRAM (việc phục hồi phải được thực hiện bởi HQbird có hỗ trợ NGRAM). Việc phục hồi bằng bản gốc thất bại trên một chỉ mục NGRAM trên cột BLOB (attempt to index BLOB column) và để cơ sở dữ liệu ở trạng thái offline (gfix -online đưa nó trực tuyến mà không có chỉ mục đó).