Well... 1 million rows is not huge these days. I'd say it's a pretty regular table size.
Make sure you:
1) Collect statistics on all tables involved,
2) Use appropriate CBO flavor (all_rows vs first_rows)
3) Set optimizer_index_% parameters approptiately
4) Index access is not always the fastest way to get the result.

Good luck.
Sergey