Might not be the solution for you, but on versions prior to 11 there is an optimization issue with the BAQ engine. Its not recommended as you shouldn’t have to specific company criteria, but it gives a noticeable boost in some cases. Take a look at my findings
Any calculated fields? SQL sucks at functions when it comes to speed