RFC: Fuzzy Search

Issue Outline

Currently there is no fuzzy support in quickwit.

Fuzzy aims to provide a solution for mistypings (typographical errors). This is often done by finding all terms within a levenshtein distance.

fst is an excellent data-structure to apply fuzzy search, but it needs the complete dictionary even for exact searches. This does not work well for Quickwit, where the data is on S3 compatible storage and loading the whole dictionary or executing many requests is costly. For that reason Quickwit uses an sstable.
sstable is storing the keys sorted lexicographical in blocks of N terms. For each block the last key is stored in the metadata. With that metadata we can find the correct block. This block is then loaded and scanned for the term.

Potential Solutions

The proposed solutions try to address the problem of loading the whole dictionary or executing many requests against S3 compatible storage.

Allow fuzzy with prefix of length N

The terms are stored in lexicographical order. We could limit the fuzzy search to a certain prefix, so that we would load only a few blocks.

E.g. with the search term "malfiormed", we could take the prefix "ma" and load all blocks for that prefix and fuzzy scan them.
The prefix should be computed dynamical, to not load too much data. With this approach the prefix would not allow any fuzzy.

The blocks could be sstables (block scan for fuzzy matches) or fst dictionaries (using fst fuzzy capabilities).

Reconstructing original term / fuzzy guessing

Another approach would be to reverse the process by guessing misstypings and generate a term list from incoming search terms and use them as exact searches.
To limit the complexity, this guessing would only include a max levenshtein distance of 1.

For example we could apply all transpositions:
Expand incoming search search term: transpoes => [rtanspoes, tarnspoes, trnaspoes, trasnpoes, tranpsoes, transope, transpeos, transpose]

There are 4 common different error types: deletion, substitution, addition and transpose. Different error types have different number of generated terms.

Number generated terms

Deletions: length of original term
Transpose: length of original term - 1

Substitutions: theoretically too many
Addition: theoretically too many

Use statistical data-structure to limit the actual number of terms., e.g. we could record at which positions which characters occur. So we could skip guess inserting a character, if this character does never occur at this position.

Limit number of searches

Some typpos are more common than other, e.g. due to fat fingers (or small keyboards) or fast typing. We could rank the alternative terms by their probability and dismiss some.

Additionally we could build a xor filter containing all terms in the dictionary, to filter out non-matches. It will costs only around 9 bits per element => 1_000_000 terms would required 1,1MB, which should be loaded in the hot cache.

Further Considerations

When the dictionary is not too large, we can consider loading the whole dictionary and run a full fuzzy query on it. The dictionary could also be an fst in that case

This is an open RFC with no files, tests, or entry points named. Start by locating Quickwit's sstable term lookup and dictionary search implementation, then compare the proposed prefix, term-guessing, and filter approaches against the S3 request and dictionary-loading constraints. Done would require an agreed design, implementation scope, and validation criteria.