> Shouldn't queries get the job done much faster?
NO!
Queries WELL WRITTEN running against a DB with optimized key and logic will run fast...
Queries in general are no better than the coder creating them
And in ALL CASES, if you are asking a query to read 5 millions records, make calculations on them and then return 300000 records out of them, it will take time, no matter WHAT and how well optimized everything is. In a case like that, it's your process logic that needs to change.
So the LOGIC of your data access is the first problem to solve, then the query optimization with appropriate keys