We update statistics weekly on SQL server. One week did did a particularly aggressive data cleanup and then ran stats which created a bad plan when the "tiny" table quickly grew.