Find approximate matches with fuzzy search

This page describes how to use a fuzzy search as part of a full-text search.

In addition to performing exact token searches using the SEARCH and SEARCH_SUBSTRING functions, Spanner also supports approximate (or fuzzy) searches. Fuzzy searches find matching documents despite small differences between the query and the document.

Spanner supports the following types of fuzzy search:

  • N-grams-based approximate search
  • Phonetic search using Soundex

N-grams-based fuzzy search relies on the same substring tokenization that a substring search requires. The configuration of the tokenizer is important as it affects search quality and performance. The following example shows how to create a query with misspelled or differently spelled words to find approximate matches in the search index.

Schema

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (
    TOKENIZE_SUBSTRING(AlbumTitle, ngram_size_min=>2, ngram_size_max=>3,
                       relative_search_types=>["word_prefix", "word_suffix"])) HIDDEN
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsIndex
ON Albums(AlbumTitle_Tokens)
STORING (AlbumTitle);

Query

The following query finds the albums with titles that are the closest to "Hatel Kaliphorn", such as "Hotel California".

SELECT AlbumId
FROM Albums
WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn")
ORDER BY SCORE_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn") DESC
LIMIT 10

Optimize performance and recall for an n-grams-based approximate search

The sample query in the previous section searches in two phases, using two different functions:

  1. SEARCH_NGRAMS finds all candidate albums that have shared n-grams with the search query. For example, three-character n-grams for "California" include [cal, ali, lif, ifo, for, orn, rni, nia] and for "Kaliphorn" include [kal, ali, lip, iph, pho, hor, orn]. The shared n-grams in these data sets are [ali, orn]. By default, SEARCH_NGRAMS matches all documents with at least two shared n-grams, therefore "Kaliphorn" matches "California".
  2. SCORE_NGRAMS ranks matches by similarity. The similarity of two strings is defined as a ratio of distinct shared n-grams to distinct non-shared n-grams:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Usually the search_query is the same across both SEARCH_NGRAMS and SCORE_NGRAMS function.

The recommended way to do this is to use the argument with query parameters rather than string literal and specify the same query parameter in the SEARCH_NGRAMS and SCORE_NGRAMS functions.

Spanner has three configuration arguments that can be used with SEARCH_NGRAMS:

  1. The minimum and maximum size of n-grams specified in TOKENIZE_SUBSTRING or TOKENIZE_NGRAMS. We don't recommend one character n-grams because they match a very large number of documents. On the other hand, long n-grams cause SEARCH_NGRAMS to miss misspelled short words.
  2. Minimum number of n-grams that SEARCH_NGRAMS must match (set with the min_ngrams and min_ngrams_percent arguments in SEARCH_NGRAMS). Higher numbers typically make the query faster, but reduce recall.

In order to achieve a good balance between performance and recall, these arguments can be configured to fit the specific query and workload.

We also recommend including an inner LIMIT to avoid creating very expensive queries when a combination of popular n-grams is encountered:

SELECT AlbumId
FROM (
  SELECT AlbumId,
         SCORE_NGRAMS(AlbumTitle_Tokens, @p) AS score
  FROM Albums
  WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, @p)
  LIMIT 10000  # inner limit
)
ORDER BY score DESC
LIMIT 10  # outer limit

N-grams-based fuzzy search versus enhanced query mode

Alongside n-grams-based fuzzy search, the enhanced query mode also handles some misspelled words. Thus, there is some overlap between the two features. The following table summarizes the differences:

n-grams-based fuzzy search Enhanced query mode
Cost Requires a more expensive substring tokenization based on n-grams Requires a less expensive full-text tokenization
Search query types Works well with short documents with a few words, such as with a person name, city name, or product name Works equally well with any size documents and any size search queries
Partial words search Performs a substring search that allows for misspellings Only supports a search for entire words (SEARCH_SUBSTRING doesn't support the enhance_query argument)
Misspelled words Supports misspelled words in either index or query Only supports misspelled words in the query
Corrections Finds any misspelled matches, even if the match isn't a real word Corrects misspellings for common, well-known words

Perform a phonetic search with Soundex

Spanner provides the SOUNDEX function for finding words that are spelled differently, but sound the same. For example, SOUNDEX("steven"), SOUNDEX("stephen") andSOUNDEX("stefan") are all "s315", while SOUNDEX("stella") is "s340". SOUNDEX is case sensitive and only works for Latin-based alphabets.

Phonetic search with SOUNDEX can be implemented with a generated column and a search index as shown in the following example:

CREATE TABLE Singers (
  SingerId INT64,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN,
  Name STRING(MAX),
  NameSoundex STRING(MAX) AS (LOWER(SOUNDEX(Name))),
  NameSoundex_Tokens TOKENLIST AS (TOKEN(NameSoundex)) HIDDEN
) PRIMARY KEY(SingerId);

CREATE SEARCH INDEX SingersPhoneticIndex ON Singers(AlbumTitle_Tokens, NameSoundex_Tokens);

The following query matches "stefan" to "Steven" on SOUNDEX, along with AlbumTitle containing "cat":

SELECT SingerId
FROM Singers
WHERE NameSoundex = LOWER(SOUNDEX("stefan")) AND SEARCH(AlbumTitle_Tokens, "cat")

What's next