Same query has different execution plans in Prod vs Test

I have a query that runs in Prod every 30 minutes. Up until yesterday it runs in seconds. Suddenly it’s taking 7 minutes.

I copied the table to Test, created the indexes & gathered statistics. It runs in seconds.

In Prod, even after rebuilding indexes and updating statistics on the table with fullscan, it’s still not performing any better. The actual execution plan in prod looks very different to test and is showing actual reads on one part of the query to be 400 million rows (there are only 1.5 million in the table).

I ran it in test with no indexes (~5 seconds) and then with indexes and all run sub-second.

In Prod, I’ve dropped the Primary Key / Clustered index, updated the statistics (update statistics interface.statsload) and rebuilt it and still it takes 8-10 minutes to run.

Also tried dropping the PK and running it again. Actual Plan shows a very thick pipe in one step with about 9 million actual rows on a full scan. When I do a select Count(*) on the table, it only shows 1.5M rows. Why is that ? I’m sure that’s feeding into it somehow.

I’m baffled. Any pointers on where I could start to look for a root cause here maybe ? I can post more info (plans, table columns, indexes) if needed.