Slow delete query on table with composite index
Oracle uses the following strategy when deleting data. It:


identifies the rows that need to be deleted (it does use your PRIMARY KEY index to check the RUN_ID value, but because the RUN_ID is not the first column in the index it needs to 'skip' values in the index).
it deletes the record in the online version of the data
it writes a physical record to the transaction / redo log to record the values that were deleted


Oracle works on a per-block bases for it's redo log:


  A redo record, also called a redo entry, is made up of a group of change vectors, each of which is a description of a change made to a single block in the database


Each time you change a record, the block it is stored in is changed, and the difference is recorded in the redo log. The number of blocks you change is a key factor in determining the amount of redo-log work that you do. The number of blocks is closely related to the amount of data you are changing, and the way that the data is distributed.

If you are deleting a bunch of records that are all stored really close to each other, then the chances are that the number of blocks that are affected will be small. If the records are scattered on many blocks, then the number of blocks affected is high.

Based on the key you have specified for your data "DEAL_ID", "RUN_ID" it appears to me that your data for a specific RUN_ID will be scattered all over the database.

This means that, for each time you delete the data, you are actually inserting 400,000 redo-log entries, modifying 400,000 blocks of storage (let's say 8K each, so that's 3GB of IO), and generally processing the system quite hard.

So, apart from the basic problem of deleting 400K records, and inserting 400K redo-entries, and writing all that data to disk, what else could it be?

Locks will likely need to be escalated. Oracle will start by trying to lock the records one at a time, but will quickly find that the lock-management requires a bigger lock strategy, so it make replace the row-locks with block-locks, and then finally escalate the block locks to a full table lock. In itself, this is not a significant performance problem, but what is a problem is if anyone else is running anything against the table.... the lock escalation will have to wait until all other locks on the table are serviced. Only then will it gain exclusive access.

Ways to improve the performance would be:


monitor the database. Confirm that IO is a real problem
monitor the lock strategies... are there significant lock-wait situations.
reduce the logging requirments...  physically order the data in the same order as the RUN_ID. you can 'cluster' the data, or, in Oracle terms, you can have "index organized table". Much fewer blocks will change with this.
improve the log-device performance - put your log files on an SSD?