Why are execution plans wildly different when selecting 1000 rows vs 2000? Consider the queries below.  The only difference is 1000 vs 2000 rows returned.

SELECT TOP 1000 lwa.Message INTO #foo
FROM dbo.LogWidgetsAPI lwa (NOLOCK)
ORDER BY lwa.TimeStamp


vs

SELECT TOP 2000 lwa.Message INTO #foo
FROM dbo.LogWidgetsAPI lwa (NOLOCK)
ORDER BY lwa.TimeStamp


However, 1000 rows are returned in under a second, while the query with 2000 rows takes significantly longer.

The query plan for the first query is reasonably simple:



but the 2nd query is using parallelization:


What would using just 1k rows more force parallelization?

P.S.  The table contains over 6 million records and TimeStamp column is indexed.
As per other comments, it sounds like the cost threshold for parallelism is too low, and is making queries go parallel even when the process to do so/ gather the streams makes your process take longer.

Try setting that to 50, or experimenting with different numbers.

Also, worth a read: https://www.brentozar.com/archive/2017/03/why-cost-threshold-for-parallelism-shouldnt-be-set-to-5/