条件が遅い3つのクエリを選択しますが、条件が速い3つのうち2つを任意に組み合わせた同じクエリ

既存のSQLを2つの部分に分割して、それぞれの実行時間を確認してください。これにより、速度低下の原因となる部分がわかります。

パート1：

SELECT table_1.id
  FROM table_1
  LEFT JOIN table_2
    ON (table_1.id = table_2.id)
 WHERE table_1.col_condition_1 = 0
   AND table_1.col_condition_2 NOT IN (3, 4)
   AND table_2.id is NULL

パート2（ここで内部結合に注意してください）：

SELECT table_1.id
  FROM table_1
  JOIN table_2
    ON (table_1.id = table_2.id)
 WHERE table_1.col_condition_1 = 0
   AND table_1.col_condition_2 NOT IN (3, 4)
   AND table_1.date_col > table_2.date_col

パート2はもっと時間がかかると思います。これでは、date_collのtable_1とtable_2の両方のインデックスが役立つと思います。

複合インデックスがあなたの選択にまったく役立たないと思います。

これは、3つの条件が一緒になってパフォーマンスに悪影響を与える理由を診断するのは難しいと述べました。それはあなたのデータ分布に関係しているようです。 mySqlについてはよくわかりませんが、Oracleでは、これらのテーブルの統計コレクションが違いを生むでしょう。

お役に立てば幸いです。