How to add typo tolerance to a MySQL product search without scanning every word

Mohamed Dhia Hachem — Mon, 09 Nov 2026 13:29:36 +0000

A shopper types hedphones. Your store sells headphones. WooCommerce's default search runs a LIKE '%hedphones%' against post titles and content, finds no such letters anywhere, and shows "No products were found".

You can fix this without Elasticsearch, using nothing but MySQL or MariaDB. The naive way is to compare the query with every word in your catalogue using an edit-distance function, which is too slow to run on every keystroke. Here is the approach that avoids it.

Step 1: build a dictionary

Pull every distinct word out of your searchable text and give it an id.

CREATE TABLE terms (
  term_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  term    VARCHAR(64) NOT NULL UNIQUE,
  df      INT UNSIGNED NOT NULL  -- how many products contain the word
);

Step 2: index each word by its trigrams

Split each word into overlapping three-letter pieces, padded so that the start and end of the word count too. sam becomes ^sa, sam, am$.

function trigrams(string $word): array {
    $w = '^' . $word . '$';
    $out = [];
    for ($i = 0; $i < mb_strlen($w) - 2; $i++) {
        $out[] = crc32(mb_substr($w, $i, 3));
    }
    return array_values(array_unique($out));
}

Store one row per word and trigram. Storing the word's length next to each trigram is the detail that makes the query cheap.

CREATE TABLE term_grams (
  g       INT UNSIGNED NOT NULL,
  len     TINYINT UNSIGNED NOT NULL,
  term_id INT UNSIGNED NOT NULL,
  PRIMARY KEY (g, len, term_id)
);

Step 3: get a small set of candidates

Two words that differ by one typo still share most of their trigrams, so you can ask the index for words sharing enough of them, and only of a similar length.

SELECT term_id, COUNT(*) AS shared
FROM term_grams
WHERE g IN (/* the query's trigrams */)
  AND len BETWEEN :len - :d AND :len + :d
GROUP BY term_id
HAVING shared >= :threshold
ORDER BY shared DESC
LIMIT 200;

The threshold is where people slip up. A substitution in the middle of a word changes three trigrams, so it's tempting to subtract 3 per allowed edit. But two swapped neighbouring letters count as one typo for a shopper, and a swap can change four padded trigrams. So use:

threshold = max(1, number_of_query_trigrams - 4 * allowed_edits)

Step 4: compute the real distance on those candidates only

Now run an exact comparison in PHP on the few candidates left. Use optimal string alignment rather than plain Levenshtein, so that a swap (haedphones) costs one edit and not two.

function osa(string $a, string $b): int {
    $a = mb_str_split($a); $b = mb_str_split($b);
    $la = count($a); $lb = count($b);
    $d = [];
    for ($i = 0; $i <= $la; $i++) $d[$i][0] = $i;
    for ($j = 0; $j <= $lb; $j++) $d[0][$j] = $j;
    for ($i = 1; $i <= $la; $i++) {
        for ($j = 1; $j <= $lb; $j++) {
            $cost = $a[$i-1] === $b[$j-1] ? 0 : 1;
            $d[$i][$j] = min($d[$i-1][$j] + 1, $d[$i][$j-1] + 1, $d[$i-1][$j-1] + $cost);
            if ($i > 1 && $j > 1 && $a[$i-1] === $b[$j-2] && $a[$i-2] === $b[$j-1]) {
                $d[$i][$j] = min($d[$i][$j], $d[$i-2][$j-2] + 1);
            }
        }
    }
    return $d[$la][$lb];
}

Sort the survivors by distance first and by df second, so a common word beats a rare one at the same distance.

Rules that matter in a shop

A working matcher still gives bad results without a few limits:

Never correct anything containing a digit. PIX-NOVA12 must not turn into PIX-NOVA13, because that is a different product.
Scale the edits with word length. One typo from about 4 letters and two from about 8 is a reasonable start. Below that, cat and car collide.
Prefer exact matches. If the word exists in the dictionary, don't fuzz it.
Handle unfinished words separately. Trigrams can't connect a misspelled fragment like hedph to a long word, because they share too few pieces. Live search needs a prefix check for that case.

Does it stay fast?

In our tests of this design on a 10,000-product store, the search took about 13 ms (median) on a laptop and about 32 ms on a cheap shared host. The whole HTTP request was around 400 ms on that host, and most of that was WordPress loading, so the bottleneck stops being the query.

Disclosure: this was written for the team behind LimberSearch, a paid WooCommerce search plugin that uses this approach, with AI assistance. The code above is a simplified version written for this post. If you want to know whether misspellings currently fail on your own store, there's a free test.