Are you measuring the time to retrieve the 4 million rows? or are you including the time to show them?

What are you expecting to get? if you're querying the full table, you need to get the full table. Indexes won't help, statistics won't help either, it's a plain simple table scan (or am I wrong?).