UNION significa UNION DISTINCT e questo è relativamente lento in quanto verificherà la presenza di duplicati anche se non ce ne saranno. Vuoi 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
Immagino che dopo questa modifica non ci sia molta differenza di prestazioni tra le tre query. Il modo migliore per esserne sicuri è misurarlo.