That may be a wrong question to ask. If do not need exact levenshtein distance, but some measure of similarity then there are a lot of options. For example postgres has index-supported similarity based on amount of common trigrams.

https://www.postgresql.org/docs/11/pgtrgm.html