Have you set indexes on relevant attributes in the entity? This can speed up your query A LOT.
When doing so, make note that your server needs enough memory to keep all the indexes in memory, this way, when executing a query, it remembers it, causing it to return your data much faster.
Disclaimer: My technical (database) experience isn't that high, so I might be wrong on some points. However, this solved a lot of our performance issues (eg, pages taking 5 seconds to load)