SQL Server – Updating Statistics and Existing Execution Plans

The answer is close to your "stats updates automatically cause dependent query plans to be flushed". They don't "stick around"

• Flushing a plan from cache is determined by memory pressure.
• Statistics updates cause plan recompilations if AUTO_UPDATE_STATISTICS is on.
• Updated statistics only mean that individual statements in a batch plan need an optimality based recompile, it does not flush the whole thing.

The analogy might be separation of concerns: the stats thingy does stats, the plan cache widget does plan cache stuff. Statistics says "I've changed", and the consumer of this status decides what action to take: not the generator of this status.

See Execution Plan Caching and Reuse on MSDN.

Am I correct in saying that statistics are only used when creating the execution plan for a stored procedure, and they are not used in the actual execution context?

No, what happens is that the execution plan for a stored procedure is cached. Assuming there is enough available memory to continue holding the plan, it won't change unless one of the following happens (from Execution Plan Caching and Reuse in the SQL Server documentation, emphasis added):

• Changes made to a table or view referenced by the query (ALTER TABLE and ALTER VIEW).
• Changes made to a single procedure, which would drop all plans for that procedure from the cache (ALTER PROCEDURE).
• Changes to any indexes used by the execution plan.
• Updates on statistics used by the execution plan, generated either explicitly from a statement, such as UPDATE STATISTICS, or generated automatically.
• Dropping an index used by the execution plan.
• An explicit call to sp_recompile.
• Large numbers of changes to keys (generated by INSERT or DELETE statements from other users that modify a table referenced by the query).
• For tables with triggers, if the number of rows in the inserted or deleted tables grows significantly.
• Executing a stored procedure using the WITH RECOMPILE option.

So if the statistics are updated, the cached plan will automatically take the new stats into account and be recompiled.

How do you prevent execution plans from growing stale when you have a hundred thousand rows being added a day?

One way is if there are a lot of updates to the table, as mentioned above. A few hundred thousand changed rows may satisfy this condition. But if you want to be sure or have more granular control: by updating your stats. You can allow SQL Server to auto create and manage statistics, or manually do it yourself. You can find more info on either method at SQL Server Auto Update and Auto Create Statistics Options. When/if you do a weekly rebuild of indexes, this will also trigger the plans to be updated as well. Do some testing to see what is most beneficial to you, as updating statistics too often may not yield any real performance results.

If we're updating statistics frequently to combat this issue, would it make sense to use the OPTION (RECOMPILE) hint on this stored procedure's query?

You don't need to use RECOMPILE, since based off the excerpt above you can see that the execution plan gets updated appropriately whenever new stats are available. You may be fine with an end of day statistics update (if you're truly concerned) but I don't think it's explicitly a need based on what you've said so far. Again, though, I'd test it to see what impact this may have on your stored procedure performance and plan accordingly.