if that table has 1000 million of rows the proper way to deal with is range partition it using the criteria you use to delete your rows, then instead of deleting you drop partitions

what I do before 9iR2 is

1. insert append to a temp table with data I need
2. disbale the constraints
3. truncate the table
4. set indexes to unusable
5. change table to nologging and run ALTER SESSION SET SKIP_UNUSABLE_INDEXES = true
6. insert the data back to the original table
7. change table to logging
8. drop the temp table
9. enable novalidate PK/UK
10. enable novalidate FKs
11. rebuild the indexes nologging parallel
12. change indexes back to logging and noparallel