UNIÓN significa UNION DISTINCT y esto es relativamente lento ya que buscará duplicados aunque no haya ninguno. Quieres UNIR TODOS:
SELECT *, 0 AS head FROM foo WHERE id IN (1,2,3)
UNION ALL
SELECT *, 1 AS head FROM foo WHERE id NOT IN (1,2,3)
ORDER BY head, created_date
Me imagino que después de este cambio no hay mucha diferencia en el rendimiento entre las tres consultas. La mejor manera de estar seguro es medirlo.
