Despite of the query length, this is very highly optimized. Have you run this single query manually on the database and it took 500ms to respond? I'm asking because I have manually tested these queries in depth (with query explanations and logs) for more than a month before release, and the final results from the database rarely took more than 20 ms to respond, even on a server with over 100k+ records – even more complex ones with custom fields and such. The short answer is, that I don't think that it is possible to optimize this query further, in any ways.
If the response time is in fact that high, then I recommend checking/restarting the database server first to make sure it's not some process stuck in there.
As an example, this server runs on a 10$/month VPS, and the index table is 255 920 rows, and the query above (not the exact copy, but same equivalent) executed in 2.6 milliseconds, returning 1792 rows: https://i.imgur.com/UNSdMXX.png
Repetitive queries are even faster.
More in-depth explanation: This query is executed on the index table, with a subquery on the taxonomy terms table, excluding objects from term 61. Notice that the “LIKE” query part is respecting the rules to not break the indexing, to bypass the much slower operation. The slowest part is actually this term exclusion, as it needs to join the terms table with the term relationships table. There is no way of bypassing that, as there is no single table containing post type relationships and term relationships exclusively. The wp_term_relationships needs an extra join to be able to tell if the object is in fact the the object typre requested and not something else.
If there was a table containing only post type object relations to terms, this could be optimized even further, using only a sub-select query on that single table.
If you like my products, don't forget to rate them on codecanyon :)