Skip to main content
SereneDBSereneDB
875Contact Us

generate_wildcard_ngrams

The generate_wildcard_ngrams template indexes text for wildcard and prefix matching.

It wraps an inner tokenizer to split the input into terms, then emits boundary-marked character n-grams of each term so that LIKE-style patterns can be answered from the index instead of by a full scan. Each term is wrapped in one marker byte at each end before the grams are cut, so a leading-anchored prefix and a trailing-anchored suffix stay distinguishable from a match in the middle of a term. The template also stores the terms it saw, and a candidate the grams select is re-checked against that stored copy whenever the grams alone cannot decide the pattern, so a match is exact rather than gram-approximate. For plain substring search over code and logs, generate_sparse_ngrams is usually the better fit.

As a function: generate_wildcard_ngrams(value, ngram_size := 3) — 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.

SQL
SELECT array_length(generate_wildcard_ngrams('search', 3), 1) AS grams;
 grams
-------
     7

Options​

OptionTypeDefaultDescription
NGRAM_SIZEinteger3Gram length in codepoints, measured over the marker-wrapped term. Minimum 2

The nested tokenizer is the first argument and NGRAM_SIZE the second: generate_wildcard_ngrams(split_text_csv(' '), 3).

An NGRAM_SIZE below 2 is rejected with "ngram_size" must be at least 2; there is no upper bound. The nested tokenizer is required for a new dictionary — generate_wildcard_ngrams(3) fails with generate_wildcard_ngrams() requires a nested analyzer as its first argument. The template supports the FREQUENCY and POSITION feature flags, with POSITION requiring FREQUENCY; NORM and OFFSET are rejected at CREATE TEXT SEARCH DICTIONARY time with an error that names them, such as Unsupported index features are specified: offset, norm.

Tokenization​

The nested tokenizer, the first argument, first splits the input into terms. Every term is then wrapped in a single marker byte (0x1F) at each end, and windows of NGRAM_SIZE codepoints slide across the wrapped term one codepoint at a time. Each window spans NGRAM_SIZE codepoints or stops at the trailing marker, whichever comes first, so the last gram of a term is two symbols long. A term yields exactly one gram more than it has codepoints.

Writing the marker as ⟨M⟩, with NGRAM_SIZE = 3 the term search yields ⟨M⟩se, sea, ear, arc, rch, ch⟨M⟩ and h⟨M⟩, and cat yields ⟨M⟩ca, cat, at⟨M⟩ and t⟨M⟩. The marker byte is part of the gram text — these grams are an internal representation rather than something you inspect with ts_lexize, and you query them indirectly through LIKE-style patterns.

Gram lengths always count codepoints, whatever the nested tokenizer is; there is no INPUT_TYPE option here. Input that is not valid UTF-8 is not rejected: symbol boundaries fall back to a lead-byte walk. The wildcard layer changes no bytes of its own, so all case, accent and normalization behaviour belongs to the nested tokenizer. Alongside the grams the template stores the encoded term stream of the value; a value whose nested tokenizer produced no terms emits no tokens and stores nothing.

Searching​

Index a column with the wildcard dictionary, then match it with ts_like. A SQL LIKE predicate on that column, with or without ESCAPE, is lowered to the same filter, so it too is answered from the indexed grams instead of a full scan. The grams only select candidate documents. Because the terms themselves are stored, a candidate is re-checked against that copy whenever the grams alone cannot decide the match, so the result is exact rather than gram-approximate. The pattern is cut at its wildcards: every piece of at least NGRAM_SIZE codepoints selects through its grams, and when no piece is that long, the longest one selects the terms that have a gram beginning with it. A pattern that is a single piece with % at most at its ends — abc%, %abc, %abc%, abc — is decided by the grams alone, without re-checking, when the piece is shorter than NGRAM_SIZE codepoints or the dictionary has POSITION; such a pattern can also match a term that itself contains the marker byte. The pattern always applies to one whole nested term at a time — with a delimiter tokenizer that means per word, never across the value. On a VARCHAR[] or VARCHAR[N] column the nested tokenizer analyzes every element on its own, and a row matches when any term of any element matches the pattern. Enabling POSITION requires the grams of a pattern fragment to occur adjacently instead of merely co-occurring, which leaves fewer candidates to re-check. When the predicate is the whole search condition or one of its AND operands, the re-check runs as one more filter of the scan, next to filters on included columns such as x > 0: the stored terms of the candidates are read block by block, and EXPLAIN shows Verify: table filter on the node. Under OR, under NOT, next to ts_offsets(), in ts_dict_agg and with a vector score it stays inside the index filter, shown as Verify: inline; a pattern the grams decide alone shows Verify: false. Every wildcard hit receives the same constant score, so BM25() and TFIDF() do not rank wildcard matches against each other.

A substring pattern matches anywhere in a term:

SQL
CREATE INDEX terms_idx ON terms USING inverted (id, term wildcard_dict);
VACUUM (REFRESH_TABLE) terms;
SELECT id, term FROM terms_idx WHERE term @@ ts_like('%ear%') ORDER BY id;
 id | term
----+----------
  1 | search
  2 | research

A prefix pattern is anchored to the start of a term:

SQL
SELECT id, term FROM terms_idx WHERE term @@ ts_like('sea%') ORDER BY id;
 id | term
----+---------
  1 | search
  3 | seabird

The same dictionary in the expression form, indexing a second table:

SQL
CREATE TEXT SEARCH DICTIONARY wildcard_expr AS generate_wildcard_ngrams(split_text_csv(' '), 3);
CREATE INDEX terms_expr_idx ON terms_expr USING inverted (id, term wildcard_expr);
VACUUM (REFRESH_TABLE) terms_expr;
SELECT id, term FROM terms_expr_idx WHERE term @@ ts_like('%ear%') ORDER BY id;
 id | term
----+----------
  1 | search
  2 | research

ts_regexp works on the same column and, as on any other dictionary, matches one whole nested term. It goes through the same filter as ts_like, which hands that filter its pattern as a regular expression: a pattern made only of literals, . and .* is cut at its wildcards in the same way, so .*a and x.*x select through their short pieces, and when every . in it also matches a line break, as under (?s), it is decided by the grams alone exactly when the LIKE pattern it spells would be. Any other pattern selects candidates through the pieces of text it requires — an exact term, a prefix, a suffix, an inner literal, the branches of an alternation — and every candidate is re-checked against the stored term with the full regular expression, so the result is exact. Under (?i) a letter that has case selects through all of its cases: (?i)abc requires one of the eight spellings from abc to ABC, and (?i)k also accepts the Kelvin sign U+212A, which the regular expression engine folds into k. A pattern the regular expression engine rejects matches no row.

SQL
SELECT id, term FROM terms_idx WHERE term @@ ts_regexp('(re)?sea.*') ORDER BY id;
 id | term
----+----------
  1 | search
  2 | research
  3 | seabird

See also​

Edit this page ↗