Thanks for the feedback, I'm closing it as using an alternative search engine is out of the scope of this request. It's true that sequential scan of many text columns is slow but IMHO using something like elasticsearch is overkill and having to install this along with Redmine would be a deal breaker for a few. Plus, I'm not sure it's designed to run queries with complex conditions on other things than text (eg. private projects, privates notes, custom fields visibility vs. user's permissions). We can get pretty good results by using advanced full text search features of the RDBMS. I've made a POC with Postgres, a few indexes and some SQL changes, the COUNT query with the same data now takes a few milliseconds.
Full article: http://www.redmine.org/issues/15781