Have you collected histograms statistics? Run analyze on the table, collecting the istogram statistics and try the query again. Try analyze with compute if the table is not too big.