Module sequence 

Whether a string holds some pieces in order, answered on its FSST codes without decompressing it.

LIKE '%special%requests%' asks whether special is somewhere in a string and requests is somewhere after it. Finding each piece as soon as it can be found is never worse than finding it later, so the question is a walk over the bytes with one automaton per piece, each one handing over to the next when its piece is complete. Laid end to end that is one automaton with a state for every byte of every piece and one more for having found them all, and a string holds the pieces when its walk ends in that last state.

A compressed string is codes, and each code stands for up to eight bytes. Walking a code is walking its bytes, and since the bytes a code stands for do not change within a chunk, where a code takes each state can be worked out once per chunk and then looked up. A string is then one lookup per code rather than a decompression, a copy and a search over the bytes, and the lookups are filled in only for the states a string actually reached. See spec/perf/44-like-on-codes.md.

Walking is still a step per code for every string, and a filter that keeps nearly every row walks nearly every string to the end. grams is the sketch that saves the walk: a bit for each run of three bytes a string holds, hashed into sixty four. A string that holds a piece holds every run of three in it, so a string whose sketch lacks one of the piece’s bits cannot hold the piece, and only the strings whose sketch has all of them are walked. The writer keeps one sketch per row of a long text column, see spec/graph/12-the-order-the-suite-asks-for.md.

Structs

Coded

Sequence over the codes of one symbol table, with where each code takes each state worked out the first time it is needed.

Sequence

The automaton for some pieces that have to appear in order.

Functions

grams

The sketch of text: a bit for every run of three bytes in it, hashed into sixty four.