Basically the problem is the high number of projects and customfields. (for example 1135 projects and 362 customfields)

The first time this query runs it has to check which custom fields can be displayed. Because projects aren't limited this means it has to perform 1135 x 362 = 410870 checks if a custom field should be displayed. At the moment this means we run 410870 DB queries (you can see these if you turn on SQL debug logging). What's even worse is that some of the columns in the table we're querying don't have indexes so the db lookups take quite long. In other words these 400000+ queries can take hours to run!

These queries do get cached. After the cache is populated a search only takes 1 second to return the 297 results. The problem is though that this cache is cleared whenever the field configs change which I'm assuming on an instance with this many projects/fields is quite often. Given how long it takes to populate the cache it probably needs to be repopulated all the time.

For now there's isn't really a good solution other than to limit the number of projects and issue types when querying.

Adding DB indexes alone wont fix this since we're simply firing off too many queries. We need to figure out a way to reduce the number of queries!