One of the biggest problems and most frequent complaints we’ve had with the WordPress.org Plugins Directory is the horrible, horrible search results.
No longer. We’re now using Sphinx (a “free open-source SQL full-text search engine”) to power search on the Plugins Directory both from the website and from within your blog’s admin (Plugins → Add New).
It works much better. There are a few oddities floating around (our fault not sphinx’s) that we’ll be cleaning up shortly, but we’re happy enough with it on the whole to start letting everyone else use it 
Currently, the search only indexes the plugin’s title and description/installation/FAQ/etc. (from the plugin’s readme.txt file), but we’ll be adding things like authors and tags soon.
