The query optimizer has always had a feature where if we use a cached plan for a query and we reach an nscanned that is 10x the nscanned that was recorded when the query plan was saved in the cache, then we attempt using other query plans as well. But this check is only triggered if a high nscanned is observed before 101 matches are found. After 101 matches are found, we're stuck using the cached plan only.

We should add additional checks (eg, deviation from avg run time or total nscanned) to guard against keeping bad plans.