I am using lucene 4.10.4.
Can anyone explain me how fuzzy search works? How much search time increases when compared to normal search?
Starting from Lucene 4, fuzzy search was implemented more efficiently, by usage of Fast string correction with Levenshtein automata paper
To make a very long story short this paper shows how to recognize the set of all words V in an index where the Levenshtein distance between V and the query does not exceed a distance d, which is exactly what one wants with Fuzzy Search.
Of course it still will be slower, than just straight lookup, that you will do for a concrete term, however it's not a performance killer anymore.