UNION означава UNION DISTINCT и това е сравнително бавно, тъй като ще проверява за дубликати, въпреки че няма да има такива. Искате UNION ALL:
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
Предполагам, че след тази промяна няма голяма разлика в производителността между трите заявки. Най-добрият начин да сте сигурни е да го измерите.