Comment by pandalicious

sort/index the db table by string length, start your search with the closest length strings (bigger and smaller) and then stop if you find a levenshtein distance that's smaller than that the length difference between the key and the next closest length string? In many(most?) cases you'd still end up searching the whole table but at least in some cases you could end the search early.