Lucene has basically always been really fast for just-plain-indexing-and-search. Certain additional features are pretty expensive to do the obvious way and came in as "it works" first and "it's fast" later. Reading the blog entry, this seems to be the case for fuzzy searches. One thing to take note of is that you can't just change your index structure for one feature, that might make other features slower and not worth it.