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
Use an n-grams-based approximate search
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:
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".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:
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
:
- The minimum and maximum size of n-grams specified in
TOKENIZE_SUBSTRING
orTOKENIZE_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 causeSEARCH_NGRAMS
to miss misspelled short words. - Minimum number of n-grams that
SEARCH_NGRAMS
must match (set with themin_ngrams
andmin_ngrams_percent
arguments inSEARCH_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
- Learn about tokenization and Spanner tokenizers.
- Learn about search indexes.
- Learn about full-text search queries.