Skip to main content

Edit this page

generate_sparse_ngrams

The generate_sparse_ngrams template indexes text for substring search — finding an arbitrary fragment anywhere inside a value, the way LIKE '%fragment%' does, but accelerated by an inverted index instead of a full scan.

It targets text where splitting on word boundaries does not help: source code, log lines, URLs, file paths, identifiers, serial numbers. For that kind of data a plain word tokenizer cannot answer "which rows contain i=42", and an generate_ngrams dictionary that could do so would bloat the index with every overlapping window. generate_sparse_ngrams keeps the index compact by emitting only a small, carefully chosen set of variable-length grams, while still letting any substring query be answered exactly.

As a function: generate_sparse_ngrams(value, max_ngram_length := 16, covering := false) — the value first, then the options in the order below. See tokenizer functions for how a value, a list and a chain of calls behave.

Query
SELECT generate_sparse_ngrams('abcd') AS tokens;
Result
 tokens---------------- {abc,bcd,abcd}

How you use it​

Substring search needs two dictionaries built from this template — they differ only in the COVERING option:

  • an indexing dictionary (COVERING = false) attached to the column, and
  • a querying dictionary (COVERING = true) used to tokenize the search string.

A query then matches every row whose indexed grams contain all of the query's grams (ts_all). That conjunction returns a small candidate set, which a LIKE predicate filters down to exact matches. The index does the expensive narrowing; LIKE only runs on the few rows that survive.

Options​

OptionTypeDefaultDescription
COVERINGbooleanfalseWhich side the dictionary serves. Leave false for the dictionary attached to the indexed column. Set true for the dictionary used to tokenize query strings, so their grams can be AND-ed together to find containing rows.
MAX_NGRAM_LENGTHinteger16Largest gram length, in characters. It caps the grams the indexing side emits and bounds how long the querying side lets a covering gram grow, so a covering gram can come out shorter than the cap. Longer grams are more selective, so queries return fewer false candidates to verify, at the cost of a larger index. Values below 3 are rejected when the dictionary is created.

The template supports the FREQUENCY and NORM feature flags, so BM25() can rank rows by how much of the query they contain; NORM requires FREQUENCY. POSITION and OFFSET are not supported: setting either fails when the dictionary is created. ts_offsets() and ts_highlight() still work over a generate_sparse_ngrams dictionary — with no offsets in the index they re-analyze the value at query time.

Tokenization​

Unlike generate_ngrams, which emits every sliding window in its length range, generate_sparse_ngrams picks a small set of variable-length grams that still let any substring query be answered. The COVERING option controls which set: the indexing side (false) stores enough grams to cover the value, while the querying side (true) emits only the few grams a search string must share with a row.

The selection runs over hashes of adjacent character pairs, so every gram boundary falls between characters. A gram is a verbatim slice of the value: nothing is case-folded, accent-stripped or Unicode-normalized, and there is no locale or case option to change that. Lengths count codepoints, so a gram never cuts a multi-byte UTF-8 sequence in half and its term text is valid UTF-8 whenever the value is; input that is not valid UTF-8 is never rejected, character boundaries just fall back to a lead-byte walk. Every gram spans at least 3 characters, which is why shorter values produce nothing at all: he yields {} and hel yields {hel}, and the two-character 日本 yields {} even though it is 6 bytes. A search fragment shorter than 3 characters likewise has no grams to require, so it cannot be answered from the index at all and has to be found with LIKE alone.

InputOptionsTokens
hello worldindexing (COVERING = false){hel,ell,llo,"lo ","o w","lo w"," wo","lo wo",wor,orl,worl,rld}
hello worldquerying (COVERING = true){hel,ell,llo,rld,worl,"lo wo"}
hello worldindexing, MAX_NGRAM_LENGTH = 4{hel,ell,llo,"lo ","o w","lo w"," wo",wor,orl,worl,rld}
日本語テキストindexing (COVERING = false){日本語,本語テ,語テキ,本語テキ,日本語テキ,テキス,キスト}

Tokens come out in the order of the selection walk, not sorted by where they start in the value. Here the querying set is a subset of the indexing set, so requiring all of a query's grams (ts_all) narrows the scan to rows whose stored grams cover the search string; those rows are candidates, and LIKE confirms the exact matches. The verified token streams appear in the examples below.

Examples​

Create the indexing dictionary and inspect the grams it stores per value with ts_lexize. It enables FREQUENCY and NORM so BM25() can rank later:

Query
CREATE TEXT SEARCH DICTIONARY code_grams AS    generate_sparse_ngrams()    WITH (frequency, norm);
SELECT ts_lexize('code_grams', 'hello world');
Result
 ts_lexize----------------------------------------------------------------- {hel,ell,llo,"lo ","o w","lo w"," wo","lo wo",wor,orl,worl,rld}

Create the querying dictionary with COVERING = true. For the same string it emits a much smaller set — the grams to require together when searching:

Query
CREATE TEXT SEARCH DICTIONARY code_grams_q AS    generate_sparse_ngrams(covering := true);
SELECT ts_lexize('code_grams_q', 'hello world');
Result
 ts_lexize-------------------------------- {hel,ell,llo,rld,worl,"lo wo"}

Attach the indexing dictionary to a column, then search for a substring by requiring all of its query grams and confirming exactness with LIKE. ts_highlight(code) wraps the matched region so you can see what was found:

Query
CREATE TABLE snippets (id INT, code TEXT);
INSERT INTO snippets VALUES    (1, 'for(int i=42; i<n; ++i) total += data[i];'),    (2, 'for(int j=0; j<n; ++j) total -= data[j];'),    (3, 'while(n--) { sum += *ptr++; }'),    (4, 'hello world');
CREATE INDEX snippets_idx ON snippets USING inverted (id, code code_grams);
SELECT id, ts_highlight(code) AS matchFROM snippets_idxWHERE code @@ ts_all(ts_lexize('code_grams_q', 'for(int i=42'))  AND code LIKE '%for(int i=42%'ORDER BY id;
Result
 id | match----+------------------------------------------------  1 | <b>for(int i=42</b>; i<n; ++i) total += data[i

Requiring only some of the query grams with ts_any(..., k) instead of all of them makes the search approximate. Rows that share more grams with the query rank higher under BM25(), so the closest matches surface first, and ts_highlight(code) shows how much of each row matched:

Query
CREATE TABLE ranked (id INT, code TEXT);
INSERT INTO ranked VALUES    (1, 'while l < r: m = (l + r) // 2'),    (2, 'some noise prefix; m = (l + r) // 2'),    (3, 'much longer noise that matches nothing at all; r) // 2'),    (4, 'completely unrelated text');
CREATE INDEX ranked_idx ON ranked USING inverted (id, code code_grams);
SELECT id, ts_highlight(code) AS matchFROM ranked_idxWHERE code @@ ts_any(ts_lexize('code_grams_q', 'while l < r: m = (l + r) // 2'), 1)ORDER BY bm25(ranked_idx.tableoid) DESC;
Result
 id | match----+---------------------------------------------------------------  1 | <b>while l < r: m = (l + r) // 2</b>  2 | some noise prefix; <b>m = (l + r) // 2</b>  3 | much longer noise that matches nothing at all; <b>r) // 2</b>

Deriving the querying dictionary​

The querying dictionary repeats the indexing dictionary's gram settings with COVERING switched on, and carries no feature flags of its own because nothing is indexed with it:

Query
CREATE TEXT SEARCH DICTIONARY code_grams_q2 AS    generate_sparse_ngrams(covering := true);
SELECT ts_lexize('code_grams_q2', 'for(int i=42');
Result
 ts_lexize------------------------ {for(i,"(int i=4",=42}

Tuning gram length​

Lowering MAX_NGRAM_LENGTH caps how long a gram can grow. Here the longer lo wo gram the default keeps is dropped, yielding a smaller index at the cost of less selective queries:

Query
CREATE TEXT SEARCH DICTIONARY code_grams_short AS    generate_sparse_ngrams(4);
SELECT ts_lexize('code_grams_short', 'hello world');
Result
 ts_lexize--------------------------------------------------------- {hel,ell,llo,"lo ","o w","lo w"," wo",wor,orl,worl,rld}

See also​