T-SQL query using completely different plan depending on number of rows I'm updating

I have a SQL UPDATE statement with a "TOP (X)" clause, and the row I'm updating values in has about 4 billion rows. When I use "TOP (10)", I get one execution plan that executes almost instantly, but when I use "TOP (50)" or larger, the query never (at least, not while I'm waiting) finishes, and it uses a completely different execution plan. The smaller query uses a very simple plan with a pair of index seeks and a nested loop join, where the exact same query (with a different number of rows in the TOP clause of the UPDATE statement) uses a plan that involves two different index seeks, a table spool, parallelism, and a bunch of other complexity.

I've used "OPTION (USE PLAN...)" to force it to use the execution plan generated by the smaller query - when I do this, I can update as many as 100,000 rows in a few seconds. I know the query plan is good, but SQL Server will only choose that plan on its own when only a small number of rows are involved - any decently large row count in my update will result in the sub-optimal plan.

I thought the parallelism might be to blame, so I set MAXDOP 1 on the query, but to no effect - that step is gone, but the poor choice/performance isn't. I also ran sp_updatestats just this morning to ensure that wasn't the cause.

I've attached the two execution plans - the shorter one is also the quicker one. Additionally, here's the query in question (it's worth noting that the SELECT I've included seems to be quick in the cases of both small and large row counts):

update top (10000) FactSubscriberUsage3
               set AccountID = sma.CustomerID
    --select top 50 f.AccountID, sma.CustomerID
      from FactSubscriberUsage3 f
      join dimTime t
        on f.TimeID = t.TimeID
      join #mac sma
        on f.macid = sma.macid
       and t.TimeValue between sma.StartDate and sma.enddate 
     where f.AccountID = 0 --There's a filtered index on the table for this

Here's the quick plan:

And here's the slower one:

Is there

The index on dimTime is changing. The quicker plan is using a _dta index. First off, make sure that isn't marked as a hypothetical index in sys.indexes.

Thinking you could be bypassing some parameterization by using the #mac table to filter instead of just supplying the start/end dates like this WHERE t.TimeValue between @StartDate and @enddate. Get rid of that temp table.

StackExchange Database Administrators Q#20178, answer score: 3