UNION signifie UNION DISTINCT et cela est relativement lent car il vérifiera les doublons même s'il n'y en aura pas. Vous voulez UNION TOUS :
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
J'imagine qu'après ce changement, il n'y a pas beaucoup de différence de performances entre les trois requêtes. Le meilleur moyen d'en être sûr est de le mesurer.