Are you using CBO ?

Are your stats for the tables and indexes up to date ?