It looks like you're new here. If you want to get involved, click one of these buttons!
Amazing! Sign our contributors' agreement and then join us on GitHub.
Another good way to index your tables when you have an existing system like this is to turn on query logging, let it run for awhile, then look at the most frequent queries. Now place indexes on the columns you search on (where w=x and y=z). If you do a lot of searching on tables that become large, this can help tremendously.
Way too many variables to even speculate why this would be happening on a particular install.