UNION oznacza UNION DISTINCT i jest stosunkowo powolny, ponieważ sprawdza duplikaty, nawet jeśli ich nie będzie. Chcesz 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
Wyobrażam sobie, że po tej zmianie nie ma dużej różnicy w wydajności między trzema zapytaniami. Najlepszym sposobem, aby się upewnić, jest jego zmierzenie.