Want to replace fulltext, and %foo% search with something better (and faster)

[Hanter]

I have a site (built in php) where I have roughly a million records in a mysql table. There is a very complex "advanced" search which allows the data to be searched, sorted, and ordered in hundreds if not thousands of various ways. Unfortunately, mysql search isn't that good, and is extremely slow. Average search takes 5 seconds currently, and the only way I can make the site function is by caching all the searches for a week (there are over 1.1 million cache files just for searches currently). I have "ghetto fuzzy search" which I implement via the soundex() function.I wanted to see what I can do about replacing the mysql based search with something a bit faster, and something that would return accurate results. I also need the output to be totally skinnable, as the results page isn't just text, but pictures, and complex css.I looked at sphinx, but there is no fuzzy search there, which I'd very much like to have.