Does a Levenshtein distance involve some computation for each single row?
PostgreSQL

Using PostgreSQL, you can create a trigram index on a column with the pgtrgm module and do a similarity search on it with the &lt;-&gt; operator,


  text &lt;-&gt; text Returns the “distance” between the arguments, that is one minus the similarity() value.


note there is also word_similarity. I would highly suggest checking out the module, as it explicitly addresses your concerns,


  Trigram matching is a very useful tool when used in conjunction with a full text index. In particular it can help to recognize misspelled input words that will not be matched directly by the full text search mechanism.