Why is a temp table a more efficient solution to the Halloween Problem than an eager spool?

This is what I call Manual Halloween Protection.

You can find an example of it being used with an update statement in my article Optimizing Update Queries. One has to be a bit careful to preserve the same semantics, for example by locking the target table against all concurrent modifications while the separate queries execute, if that is relevant in your scenario.

Why is the plan with the temp table more efficient? Isn't an eager spool mostly just an internal temp table anyway?

A spool has some of the characteristics of a temporary table, but the two are not exact equivalents. In particular, a spool is essentially a row-by-row unordered insert to a b-tree structure. It does benefit from locking and logging optimizations, but does not support bulk load optimizations.

Consequently, one can often get better performance by splitting the query in a natural way: Bulk loading the new rows into a temporary table or variable, then performing an optimized insert (without explicit Halloween Protection) from the temporary object.

Making this separation also allows you extra freedom to tune the read and write portions of the original statement separately.

As a side note, it is interesting to think about how the Halloween Problem might be addressed using row versions. Perhaps a future version of SQL Server will provide that feature in suitable circumstances.

---

As Michael Kutz alluded to in a comment, you could also explore the possibility of exploiting the hole-filling optimization to avoid explicit HP. One way to achieve this for the demo is to create a unique index (clustered if you like) on the ID column of A_HEAP_OF_MOSTLY_NEW_ROWS.

CREATE UNIQUE INDEX i ON dbo.A_HEAP_OF_MOSTLY_NEW_ROWS (ID);

With that guarantee in place the optimizer can use hole-filling and rowset sharing:

MERGE dbo.HALLOWEEN_IS_COMING_EARLY_THIS_YEAR WITH (SERIALIZABLE) AS HICETY
USING dbo.A_HEAP_OF_MOSTLY_NEW_ROWS AS AHOMNR
    ON AHOMNR.ID = HICETY.ID
WHEN NOT MATCHED BY TARGET
THEN INSERT (ID) VALUES (AHOMNR.ID);

While interesting, you will still be able to achieve better performance in many cases by employing carefully-implemented Manual Halloween Protection.

To expand on Paul's answer a bit, part of the difference in elapsed time between the spool and the temp table approaches seems to come down to the lack of support for the DML Request Sort option in the spool plan. With undocumented trace flag 8795, the elapsed time for the temp table approach jumps from 4400 ms to 5600 ms.

INSERT INTO dbo.HALLOWEEN_IS_COMING_EARLY_THIS_YEAR WITH (TABLOCK)
SELECT new_rows.ID
FROM #CONSULTANT_RECOMMENDED_TEMP_TABLE new_rows
OPTION (MAXDOP 1, QUERYTRACEON 8795);

Note that this isn't exactly equivalent to the insert performed by the spool plan. This query writes significantly more data to the transaction log.

The same effect can be seen in reverse with some trickery. It is possible to encourage SQL Server to use a sort instead of a spool for Halloween Protection. One implementation:

INSERT INTO dbo.HALLOWEEN_IS_COMING_EARLY_THIS_YEAR WITH (TABLOCK)
SELECT TOP (987654321) 
maybe_new_rows.ID
FROM dbo.A_HEAP_OF_MOSTLY_NEW_ROWS maybe_new_rows
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.HALLOWEEN_IS_COMING_EARLY_THIS_YEAR halloween
    WHERE maybe_new_rows.ID = halloween.ID
)
ORDER BY maybe_new_rows.ID, maybe_new_rows.ID + 1
OPTION (MAXDOP 1, QUERYTRACEON 7470, MERGE JOIN);

Now the plan has a TOP N Sort operator in place of the spool. The sort is a blocking operator so the spool is no longer necessary:

More importantly, we now have support for the DML Request Sort option. Looking at Actual Time Statistics again, the insert operator now only takes 1623 ms. The entire plan takes about 5400 ms to execute without requesting an actual plan.

As Hugo explains, the Eager Spool operator does preserve order. That can most easily be seen with a TOP PERCENT plan. It's unfortunate that the original query with the spool cannot take better advantage of the sorted nature of the data in the spool.