NGRAM index (HQbird): substring search with LIKE '%...%' and CONTAINING

← HQbird server features

An NGRAM index finds rows by a substring of a text value, so that WHERE col LIKE '%error 404%' does not need to read the whole table. It uses sparse n-grams, the method of GitHub code search (implementation follows SereneDB).

Syntax

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;

• One CHAR, VARCHAR or BLOB SUB_TYPE TEXT column, or an expression with a text or text BLOB result.
• Every character set and collation is allowed, also case and accent insensitive (UNICODE_CI, UNICODE_CI_AI) and ICU collations (UNICODE, UTF8 with a locale).
• A partial index (WHERE) is used only if the query has the same condition.
• Not allowed: UNIQUE, DESCENDING, several columns, CONCURRENTLY, binary BLOBs, arrays.
• ALTER INDEX ... ACTIVE | INACTIVE, SET STATISTICS INDEX, DROP INDEX work as usual.
• SHOW INDEX prints NGRAM INDEX, isql -x prints CREATE NGRAM INDEX.
• The database ODS must be 13.1 (the default for Firebird 5).

Queries that use the index

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

• The pattern must have a literal part of at least 3 characters (between % and _). A constant pattern without such a part does not use the index. A parameter without such a part gives a full scan (the result is still correct).
• The index can be combined with other indexes (AND).
• LIKE is always checked again for every found row, so the index never changes the result of a query.
• OR of several LIKE uses the index for each of them.
• Not used for: SIMILAR TO, STARTING WITH, =, ranges, IS NULL, ORDER BY, MIN/MAX.

Collations

The index keys are made of the same canonical form of the text that LIKE compares. So with a case insensitive collation LIKE is case insensitive, and the index finds the same rows:

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é'

The canonical form of ICU collations depends on the ICU version, as for ordinary indexes. After a change of the ICU library, rebuild the index (ALTER INDEX ... INACTIVE, then ACTIVE).

CONTAINING

col CONTAINING 'x' is case insensitive. It uses an NGRAM index in two cases:

• col is UTF8 with a case insensitive Unicode collation (UNICODE_CI, UNICODE_CI_AI): an index on the column itself;
• any other collation: an index COMPUTED BY (UPPER(col)). Write the query as usual, col CONTAINING 'x': the optimizer finds the UPPER index itself.

Not used for multi-byte character sets other than UTF8 and UNICODE_FSS (for example SJIS_0208) with their default collations: there CONTAINING compares bytes, not characters.

Text BLOBs

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

• The index has the grams of the whole BLOB, of any length. The server makes the grams in windows of 64K characters and keeps only distinct grams, so the memory for the keys depends on the number of distinct grams, not on the BLOB size. A BLOB in a multi-byte character set is read whole, as LIKE reads it.
• The BLOB is read when a row is inserted, when the BLOB is changed, and once more when garbage collection removes the old version. An UPDATE of other columns keeps the same BLOB and does not read it (also for an index COMPUTED BY (UPPER(body))).
• The index has one entry for each distinct gram of a row. Long documents repeat many grams: the source files of Firebird give 0.3 entries per character, short lines 1.4.
• Load the data first, then create the index (see “Size and cost”).

Plan output:

PLAN (MSG INDEX (MSG_TEXT_NG))

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

Size and cost

Measured on the lines of the Firebird source code (953 000 rows, 27 million characters): index 188 MB (7.2× the text, 1.7× the table), built in 16 s; LIKE '%word%' 12 to 4000 times faster than a full scan (from 0.2 ms for rare words to 50 ms for a word in 35 000 rows, against 600 ms for the scan). With UNICODE_CI_AI the scan is 6 times slower (3.5 s), the index is not: LIKE and CONTAINING are 20 to 8000 times faster.

Query speed

Index size

Bulk load cost

For a bulk load, create the index after the load, or make it INACTIVE during the load. 1 163 source files (28 million characters) as BLOBs:

• About 1.4 index entries per character of text (each entry is an 8-byte gram hash and a record number). Expect an index several times larger than the text.
• Every insert adds about 1.4 B-tree entries per character: inserts into a table with an NGRAM index are much slower than without it. The target is append-mostly data (logs, messages, documents) with rare updates.
• Updates insert only the new grams. Old grams are removed by garbage collection when no record version needs them any more.
• Index creation leaves 5% free space in each page, as CONCURRENTLY does. The grams of one record are in many leaf pages; without free space the first updates after the creation split almost every leaf page.
• An UPDATE that does not change the indexed column (for an index on an expression: the columns that the expression uses) does not compute grams at all.
• Index creation sorts all grams: temporary space is about 20 bytes per gram. ParallelWorkers speeds up the creation.

Compatibility with servers without NGRAM support

The index is stored in ODS 13.1. Its condition (RDB$CONDITION_BLR) starts with a guard expression that fails with a conversion error. A server without NGRAM support (stock Firebird 5.0.x, older HQbird):

• opens the database; SELECT gives right results and does not use the NGRAM index;
• refuses INSERT and UPDATE into the table with the error conversion error from string "HQBIRD NGRAM INDEX: use HQbird server" (so the index is never corrupted);
• allows DELETE and sweep (the index keeps extra entries: only a size cost);
• can not activate the index.

Tested with stock Firebird 5.0.4.1812 and HQbird 5.0.4.1773. Third-party tools may show the index as DESCENDING with a WHERE clause.

gbak backs up and restores NGRAM indexes (the restore must be done by HQbird with NGRAM support). A stock restore fails on an NGRAM index on a BLOB column (attempt to index BLOB column) and leaves the database offline (gfix -online brings it online without that index).