How hard is it to do plain search first for crying out loud.

Funny you asked, turns out it is quite hard because you must know a lot more about nature of your data and also intricate user needs to design an effective system like that. Fuzzy search is like bluetooth, slap it on and it kind of sort of works. Afterall, everything is better with bluetooth.