Seleccione la consulta con tres donde las condiciones son lentas, pero la misma consulta con cualquier combinación de dos de las tres donde las condiciones son rápidas

Intente dividir el SQL existente en dos partes y vea cuáles son los tiempos de ejecución para cada una. Con suerte, esto le daría la parte responsable de la lentitud:

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

y la parte 2 (tenga en cuenta la unión interna aquí):

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

Espero que la parte 2 sea la que tome más tiempo. En esto, creo que un índice en table_1 y table_2 en date_coll ayudaría.

No creo que el índice compuesto ayude en absoluto en su selección.

Dicho esto, es difícil diagnosticar por qué las tres condiciones juntas afectarían tanto el rendimiento. Parece estar relacionado con su distribución de datos. No estoy seguro acerca de mySql, pero en Oracle, una recopilación de estadísticas en esas tablas marcaría la diferencia.

Espero que ayude.