UNION significa UNION DISTINCT e isso é relativamente lento, pois verificará se há duplicatas, mesmo que não haja nenhuma. Você quer 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
Imagino que após essa alteração não haja muita diferença de desempenho entre as três consultas. A melhor maneira de ter certeza é medindo.
