Twenty minutes for half a billion rows doesn't look that bad.

You may want to try append hint.

Also, if tables are partitioned you may want to use parallel processing; for a few partitions you may want to set degree of parallelism to the number of partitions.