Hi,
As Peter says, if this query is to run faster, it needs to start with some other table than the sales_flat_order since reading all of this table will take time. The question is, as Rick states, whether any of the conditions have high selectivity. That is, the condition will significantly reduce the number of rows that will need to be inspected. If so, the query execution should start with that table. If there are no selective conditions, there is probably not much that can be improved.
You say that you have done all things I suggested, but with little impact. Could you show the resulting query and the explain output you get with that query?
I would also be able to say more if I could have the optimizer trace for the query. See
http://oysteing.blogspot.com/2016/01/how-to-get-optimizer-trace-for-query.html for how to obtain the trace.
Finally, MySQL 5.7 has improved cardinality and filtering estimates. You could try your query on 5.7 to see if you get a better plan.
Øystein Grøvlen,
Senior Principal Software Engineer,
MySQL Group, Oracle,
Trondheim, Norway