Изберете заявка с три, когато условията са бавни, но същата заявка с всяка комбинация от две от трите, където условията са бързи

Опитайте се да разделите съществуващия SQL на две части и вижте какви са времената за изпълнение за всяка. Надяваме се, че това ще ви даде каква част е отговорна за бавността:

част 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 да е тази, която ще отнеме повече време. В това мисля, че би помогнал индекс на table_1 и table_2 на date_coll.

Не мисля, че съставният индекс би помогнал изобщо при избора ви.

Това каза, че е трудно да се диагностицира защо трите условия заедно биха повлияли толкова зле на производителността. Изглежда, че е свързано с разпространението на вашите данни. Не съм сигурен за mySql, но в Oracle събирането на статистически данни за тези таблици би имало значение.

Надявам се да помогне.