DrDoc - 5:12 pm on Jul 12, 2013 (gmt 0)
I have tables with tens of millions of records which I perform advanced calculations on -- none of which take longer than half a second to complete.
9 seconds for 500k records -- something's definitely amiss. The suggestion to run EXPLAIN SELECT may provide useful. That said -- even if the indexes may seem okay it may still be possible to improve them.