Really more of a DBA question. We don't know your structures, indexes, data volumes, etc and can't see your explain plan. The whole Toad part about the data starting to return instantly and 'select count(*) from' stats are fairly meaningless, unfortunately.
Check with your DBA. Perhaps you need a 'before sql' alter session to bump up the sort or hash area size for the query...