LIKE '%i=42%' is the query that code, logs and identifiers need, and a word
tokenizer can't help with it: i=42 is not a word. The classic index for
substring search is trigrams, as in PostgreSQL's
pg_trgm: index every
window of three characters, look up the trigrams of the needle and intersect
their posting lists. It works, but trigrams are common. A 16-character needle
has 14 of them, and many come with long lists.
GitHub's code search replaced trigrams with sparse n-grams, described in
The technology behind GitHub's new code search,
and the danlark1/sparse_ngrams
library implements them. In SereneDB they come from the
generate_sparse_ngrams
tokenizer, which
Code search over a data lake, without moving the data
put to work on 11.5 million solutions. This post is about how it chooses its
grams.
Grams from pair weights
The selection starts with a weight for every pair of adjacent characters: a hash of the two, which looks random but is fixed by the characters. A gram is a run of at least three characters whose two border pairs both weigh more than every pair inside it. In GitHub's words, it selects "intervals where the inner weights are strictly smaller than the weights at the borders".
Here are the 11 pair hashes of for(int i=42, ranked from 1, the lowest, to
11 (␣ is the space):
pair fo or r( (i in nt t␣ ␣i i= =4 42
rank 8 2 4 10 3 9 6 1 5 11 7
for(i is a gram: its borders fo (8) and (i (10) both outrank or (2)
and r( (4) inside it. for(int is not, because (i (10) inside it outranks
the border fo (8). A trigram has no pair inside, so every trigram qualifies,
and the line has its 10 trigrams plus 7 longer grams: for(, for(i, (int,
t␣i=, t␣i=4, nt␣i=4 and (int␣i=4. Grams are capped at
max_ngram_length, 16 characters by default.
Whether a run is a gram depends only on its own characters, never on the text around it. Everything else rests on that: a gram of the needle is a gram of every line that contains the needle.
One pass with a stack
The tokenizer finds every gram in one pass from left to right, with a stack of
pairs whose weights decrease from the bottom up. Each new pair pops the lower
pairs off the top and emits a gram from each popped pair to itself. Then it
emits one more from the first pair that stays and goes on the stack. A popped
pair can't begin a later gram, since the new pair outranks it and would sit
inside. On for(int i=42, or stays above fo (gram for); r( pops or
(or() and stops at fo (for(); (i pops r( (r(i) and fo (for(i)
and leaves the stack empty. The core of StepAll:
const size_t end = i + Window<Generic>();
const size_t min_pos = end - std::min(end, _options.max_ngram_length);
while (top != base && hash > top[-1].hash) {
if (top[-1].pos < min_pos) {
top = base;
break;
}
Emit<Generic>(out, top[-1].pos, end);
while (top - base > 1 && top[-1].hash == top[-2].hash) {
--top;
}
--top;
}
if (top != base && top[-1].pos >= min_pos) {
Emit<Generic>(out, top[-1].pos, end);
}
*top++ = {hash, static_cast<uint32_t>(i)};
min_pos enforces the cap: a pair too far back can't begin a gram, and
everything under it on the stack is farther back still, so the stack is
dropped. Equal weights collapse, so that a pair inside a gram is always
strictly lower than its borders. Every pair goes on the stack once and comes
off at most once, so the pass is linear and a line yields fewer than two grams
per character.
The query needs a chain
At query time, covering := true runs the same weights but keeps only the
grams that chain the record pairs: the pairs above every pair to their left, up
to the highest one, and above every pair to their right after it. In
for(int i=42 those are fo, (i, =4 and 42, so the chain is for(i,
(int␣i=4 and =42, three lookups where trigrams need ten. Each link is a
gram of the needle, so it is a gram of any line that contains the needle, and
requiring all three can't lose a row. For a needle longer than the cap, the
walk emits links early so that none outgrows it.
The two sides are two dictionaries that differ only in covering, declared
like any other (A text search dictionary is an SQL expression covers the
syntax). The column gets the first, and a query runs the needle through the
second:
CREATE TEXT SEARCH DICTIONARY code_grams AS generate_sparse_ngrams();
CREATE TEXT SEARCH DICTIONARY code_grams_q AS
generate_sparse_ngrams(covering := true);
CREATE INDEX code_idx ON code_lines USING inverted (id, line code_grams);
SELECT id, line
FROM code_idx
WHERE line @@ ts_all(ts_tokenize(ARRAY['return false;'], 'code_grams_q'))
AND line LIKE '%return false;%';
ts_tokenize keeps each gram of the chain a single term and ts_all requires
them all. LIKE then checks the candidates. Plain strings would be analyzed by
the column's own dictionary instead, which emits every gram of a string and
accepts any one of them: the chain of size_t i = 0 passed as strings,
ts_all(ts_lexize('code_grams_q', ...)), lets 359 rows of the corpus below
through instead of 12. ts_any(..., k) asks for any k of the grams, the fuzzy
search the data-lake post showed. A needle shorter than three characters has
no grams at all, so the index has nothing to look up and such a needle needs a
plain LIKE.
What sparse n-grams cost and save
To put numbers on it, we indexed 5,000 lines of C++ from the sources under
iresearch/analysis, without blank lines and license headers, 149,471 bytes
in all (SereneDB 26.10.1). They yield 250,861 sparse grams, 1.7 per
character. Sparse grams include every trigram, so the index is larger: 236,914
postings and 34,251 distinct terms, against 130,182 postings and 8,845 terms
for trigrams (generate_ngrams(3, 3)).
The savings are on the query side. Twelve needles of 4 to 16 characters need 2
to 5 grams each instead of 2 to 14 trigrams. Their grams let through the same
rows as all of their trigrams together, the exact matches plus at most two.
The postings their terms hold, the sum of the document frequencies, come to
5,467 against 23,669 for the trigrams, 4.3 times fewer. size_t i = 0 is the
extreme case: 2 grams over 27 postings against 10 trigrams over 3,293, and both
let exactly its 12 rows through. On every needle, the rows left after the exact
check were the rows a plain scan over the table returns. (Document frequencies
come from a Python mirror of the tokenizer, which gave the same grams as 26.10.1
on 240 random strings and on every needle here.)
The knobs
max_ngram_length caps a gram. min_ngram_length, 3 by default, changes the
selection itself: the weights become hashes of min_ngram_length - 1
characters instead of pairs, so every gram spans at least that many. Both
lengths are refused below 3 when the dictionary is created, and the tokenizer
clamps them to 3 as well. min_cutoff_length keeps the selection and drops
its short grams, on both sides. With a cutoff of 4 the corpus index falls to
106,732 postings, below the trigrams, but short grams leave the queries too:
kBatch lets 56 rows through instead of 4 and #include < 233 instead of
104, while if ( keeps no gram at all. The two dictionaries have to agree on
all three options.
The template is also a pipeline stage, so other stages can go in front of it.
With normalize_tokens(case := 'lower') | generate_sparse_ngrams() on both
sides and ILIKE for the check, the search ignores case.
Inside the tokenizer
The weight is two multiplications and a fold, with the same two 64-bit constants as the reference library. The first is MurmurHash2's multiplier.
IRS_FORCE_INLINE uint32_t HashPair(uint32_t a0, uint32_t a1) {
const uint64_t a = a0 * kMul1 + a1 * kMul2;
return a + (~a >> 47);
}
The tokenizer hashes up to kBatch, 8,192 pairs, into a scratch array before
the stack walks them. Each hash depends only on its own pair, so the compiler
vectorizes the loop. The same loop ORs every byte it reads into an
accumulator, and a high bit sends the value down a second path that hashes
code points instead of bytes, so a gram never cuts a character in two. Bytes
are read as unsigned. x86's char is signed, and when the first version read
it that way, a byte above 0x7F hashed differently on x86 and on ARM; fixing
that changed the x86 index terms of non-ASCII text.
On x86 the hash loop is chosen at startup: __builtin_cpu_supports picks
FillHashesAvx512 on CPUs with AVX-512F and DQ. That function is the scalar
loop itself, compiled for AVX-512, so both paths compute the same hashes by
construction, and the tests compare the output on 20,000-character inputs
with a reference implementation on whichever path the machine picks. What
differs is the code. In a toy compile with clang 21 and the default x86 build's
-march=haswell, the plain loop emulates its 64-bit multiplies with 32-bit
ones (vpmuludq), while the AVX-512 version uses vpmullq on 512-bit
registers.
The stack is walked in place: a fixed array of max_ngram_length + 66 entries
and a pointer to its top, with no allocation per pair. When it fills up, the
entries too old to begin a gram go in one memmove. Grams leave as (begin,
end) offsets into the value, gathered in a buffer and handed to the token sink
in batches.
Takeaways
- Let the text pick the grams. A gram depends only on its own characters, so a needle's grams turn up wherever the needle does.
- Index everything, query a chain. A sparse n-gram index stores every gram, trigrams included; a query needs only the links between record pairs.
- Count postings, not terms. The sparse index is larger than a trigram index, and its queries read about a quarter of the postings.
- Hash ahead of the stack. A batch of independent hashes is a loop the compiler can vectorize, with native 64-bit multiplies on AVX-512.
If you find this work interesting, a star on GitHub helps an early-stage project more than you might think.