Seleziona query con tre in cui le condizioni sono lente, ma la stessa query con qualsiasi combinazione di due delle tre in cui le condizioni sono veloci

Prova a dividere l'SQL esistente in due parti e guarda quali sono i tempi di esecuzione per ciascuna. Si spera che questo ti dia quale parte è responsabile della lentezza:

parte 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

e parte 2 (nota qui il join interno):

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

Mi aspetto che la parte 2 sia quella che richiede più tempo. In questo penso che un indice sia su table_1 che table_2 su date_coll aiuterebbe.

Non credo che l'indice composito aiuterebbe affatto nella tua selezione.

Detto questo, è difficile diagnosticare il motivo per cui le tre condizioni insieme avrebbero un impatto così negativo sulle prestazioni. Sembra essere correlato alla tua distribuzione dei dati. Non sono sicuro di mySql ma in Oracle una raccolta di statistiche su quelle tabelle farebbe la differenza.

Spero che aiuti.