Its unclear if you are trying to match individual words (as in name matching) or entire phrases. The performance of any routine which has to match every row against every other row in a large table will always be a problem. The trick is to find a way of "rough matching" which can be indexed. In word checking, you might use the length of the words being matched, so that only those word close to each other in length are checked. Usually, users of Levenstein type routines will only accept matches with values less than (say) 4. In that case, the only words which can match must have lengths within 4 of each other. You can filter the data to eliminate the vast bulk of potential matches which can never match. There are lots of academic papers on improving the performance of matching routines, and they might be fruitful source of potential ideas for your matching problem. They often have long lists of references which can be consulted as well. Good luck.