100万件オーダーのテーブル同士の差分を求めるという要件で10分超を10分以下に抑えるチューニングというのは、改善の余地が小さく労力に対する見返りが少ないと思われます。しかもバッチ処理であればなおさらです。バッチライン上に他にチューニングの余地がないか分析した方が生産的と思いますが、何か事情があるのでしょうか。
おそらく質問者さんが示されているSQLで既に、このようなケースで最も高速と想定されるHASH結合をオプティマイザは選択しているはずです(統計情報がきちんと採られていれば)。実行計画を確認してみてください。なお、ハッシュ結合の場合は結合キーに索引は不要です。
ただし、PGA上のHASHテーブルが溢れてしまうと一時表領域を使用するようになるのでパフォーマンスが低下します。実行計画のTempSpc項目を確認し、一時表領域が使用されていればPGAの拡張を検討してください。
ハッシュ結合
--追記--
key1,key2に索引を追加しても、今のSQLでは結局HASH結合が選択され索引は使用されないと思われます。表の大部分にアクセスするのであれば、1行ずつ索引を見るのはむしろ効率が良くないためです。
索引を追加して性能が改善する可能性があるのは、以下のようにnot exitsと相関複照会を用いたSQLに変更した場合です。こちらであればtableBの表アクセスが不要になるため、性能が向上するかもしれません。ただし、今度は索引へのアクセスが新たにコストとして追加されるため、実測して比較する必要があります。
sql
1select *
2from tableA tA
3where not exists (
4 select tB.key1
5 from tableB tB
6 where
7 tA.key1 = tB.key1
8 and tA.key2 = tB.key2
9)