So... stale statistics? I.e. the optimizer making the query plan assuming that the table has thousands of records (because that's what it had earlier) and now it has hundreds of millions of records? A sudden order of magnitude change in table sizes isn't normal operation, for most DB platforms that requires running some "everything's different now, please recalculate statistics" command to maintain proper functioning.