NGRAM indeks (HQbird): pretraga podniza pomoću LIKE '%...%' i CONTAINING

← HQbird server features

NGRAM indeks pronalazi redove po podnizu tekstualne vrednosti, tako da WHERE col LIKE '%error 404%' ne mora da čita celu tabelu. Koristi retke n-grame (sparse n-grams), metodu GitHub pretrage koda (implementacija prati SereneDB).

Sintaksa

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;

Jedna kolona tipa CHAR, VARCHAR ili BLOB SUB_TYPE TEXT, ili izraz sa tekstualnim rezultatom ili tekstualnim BLOB-om.
Dozvoljen je svaki skup karaktera i kolacija, takođe neosetljiv na velika/mala slova i akcente (UNICODE_CI, UNICODE_CI_AI) i ICU kolacije (UNICODE, UTF8 sa lokalom).
Parcijalni indeks (WHERE) se koristi samo ako upit ima isti uslov.
Nije dozvoljeno: UNIQUE, DESCENDING, više kolona, CONCURRENTLY, binarni BLOB-ovi, nizovi.
ALTER INDEX ... ACTIVE | INACTIVE, SET STATISTICS INDEX, DROP INDEX rade kao i obično.
SHOW INDEX prikazuje NGRAM INDEX, isql -x prikazuje CREATE NGRAM INDEX.
ODS baze podataka mora biti 13.1 (podrazumevano za Firebird 5).

Upiti koji koriste indeks

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

Šablon mora imati literalni deo od najmanje 3 karaktera (između % i _). Konstantan šablon bez takvog dela ne koristi indeks. Parametar bez takvog dela daje puno skeniranje (rezultat je i dalje ispravan).
Indeks se može kombinovati sa drugim indeksima (AND).
LIKE se uvek ponovo proverava za svaki pronađeni red, tako da indeks nikada ne menja rezultat upita.
OR od nekoliko LIKE koristi indeks za svaki od njih.
Ne koristi se za: SIMILAR TO, STARTING WITH, =, opsege, IS NULL, ORDER BY, MIN/MAX.

Kolacije

Ključevi indeksa se prave od istog kanonskog oblika teksta koji LIKE poredi. Zato je sa kolacijom neosetljivom na velika/mala slova LIKE neosetljiv na velika/mala slova, a indeks pronalazi iste redove:

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

Kanonski oblik ICU kolacija zavisi od verzije ICU, kao i za obične indekse. Nakon promene ICU biblioteke, ponovo izgradite indeks (ALTER INDEX ... INACTIVE, zatim ACTIVE).

CONTAINING

col CONTAINING 'x' je neosetljiv na velika/mala slova. Koristi NGRAM indeks u dva slučaja:

col je UTF8 sa Unicode kolacijom neosetljivom na velika/mala slova (UNICODE_CI, UNICODE_CI_AI): indeks na samoj koloni;
bilo koja druga kolacija: indeks COMPUTED BY (UPPER(col)). Pišite upit kao i obično, col CONTAINING 'x': optimizator sam pronalazi UPPER indeks.

Ne koristi se za višebajtne skupove karaktera osim UTF8 i UNICODE_FSS (na primer SJIS_0208) sa njihovim podrazumevanim kolacijama: tamo CONTAINING poredi bajtove, a ne karaktere.

Tekstualni BLOB-ovi

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

Indeks sadrži gramove celog BLOB-a, bilo koje dužine. Server pravi gramove u prozorima od 64K karaktera i čuva samo različite gramove, tako da memorija za ključeve zavisi od broja različitih gramova, a ne od veličine BLOB-a. BLOB u višebajtnom skupu karaktera se čita ceo, kao što ga LIKE čita.
BLOB se čita kada se red ubaci, kada se BLOB izmeni, i još jednom kada garbage collection ukloni staru verziju. UPDATE drugih kolona zadržava isti BLOB i ne čita ga (takođe za indeks COMPUTED BY (UPPER(body))).
Indeks ima jedan unos za svaki različiti gram u redu. Dugački dokumenti ponavljaju mnogo gramova: izvorni fajlovi Firebird-a daju 0,3 unosa po karakteru, kratki redovi 1,4.
Prvo učitajte podatke, zatim kreirajte indeks (videti „Veličina i cena").

Izlaz plana:

PLAN (MSG INDEX (MSG_TEXT_NG))

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

Veličina i cena

Izmereno na redovima izvornog koda Firebird-a (953 000 redova, 27 miliona karaktera): indeks 188 MB (7,2 x tekst, 1,7 x tabela), izgrađen za 16 s; LIKE '%word%' od 12 do 4000 puta brže od punog skeniranja (od 0,2 ms za retke reči do 50 ms za reč u 35 000 redova, naspram 600 ms za skeniranje). Sa UNICODE_CI_AI skeniranje je 6 puta sporije (3,5 s), indeks nije: LIKE i CONTAINING su od 20 do 8000 puta brži.

Oko 1,4 unosa indeksa po karakteru teksta (svaki unos je 8-bajtni heš grama i broj zapisa). Očekujte indeks nekoliko puta veći od teksta.
Svaki insert dodaje oko 1,4 B-tree unosa po karakteru: inserti u tabelu sa NGRAM indeksom su mnogo sporiji nego bez njega. Ciljna su uglavnom dopisivana (append-mostly) podaci (logovi, poruke, dokumenti) sa retkim izmenama.
Izmene ubacuju samo nove gramove. Stari gramovi se uklanjaju garbage collection-om kada im više nije potrebna nijedna verzija zapisa.
Kreiranje indeksa ostavlja 5% slobodnog prostora u svakoj stranici, kao što to radi CONCURRENTLY. Gramovi jednog zapisa su u mnogim list-stranicama; bez slobodnog prostora prve izmene nakon kreiranja dele skoro svaku list-stranicu.
UPDATE koji ne menja indeksiranu kolonu (za indeks na izrazu: kolone koje izraz koristi) uopšte ne računa gramove.
Za masovno učitavanje, kreirajte indeks nakon učitavanja, ili ga učinite INACTIVE tokom učitavanja. 1 163 izvorna fajla (28 miliona karaktera) kao BLOB-ovi: učitavanje sa dva NGRAM indeksa 419 s; učitavanje bez indeksa 0,6 s, zatim kreiranje oba indeksa 10,7 s.
Kreiranje indeksa sortira sve gramove: privremeni prostor je oko 20 bajtova po gramu. ParallelWorkers ubrzava kreiranje.

Kompatibilnost sa serverima bez NGRAM podrške

Indeks se čuva u ODS 13.1. Njegov uslov (RDB$CONDITION_BLR) počinje guard izrazom koji pada sa greškom konverzije. Server bez NGRAM podrške (standardni Firebird 5.0.x, stariji HQbird):

otvara bazu podataka; SELECT daje ispravne rezultate i ne koristi NGRAM indeks;
odbija INSERT i UPDATE u tabelu sa greškom conversion error from string "HQBIRD NGRAM INDEX: use HQbird server" (tako da indeks nikada nije oštećen);
dozvoljava DELETE i sweep (indeks zadržava dodatne unose: samo cena veličine);

BLOB bulk load with and without NGRAM during load

ne može da aktivira indeks.

Testirano sa standardnim Firebird 5.0.4.1812 i HQbird 5.0.4.1773. Alati trećih strana mogu prikazati indeks kao DESCENDING sa WHERE klauzulom.

gbak pravi rezervne kopije i vraća NGRAM indekse (vraćanje mora da uradi HQbird sa NGRAM podrškom). Standardno vraćanje pada na NGRAM indeksu na BLOB koloni (attempt to index BLOB column) i ostavlja bazu podataka offline (gfix -online je vraća online bez tog indeksa).