AUTO_UPDATE_STATISTICS and FULLSCAN in SQL Server 2008 R2
Auto updates always use sampling with the percentage being calculated from the number of rows in the index.

From your SO post:

 Just FYI, the two indexes were PKs of tables having 280M+ and 55M+ rows, respectively.


I guess this is a good example of why SQL Server won't allow a FULLSCAN auto update. The impact of reading that many rows unplanned could cause as many headaches as it solves.

Two options:


Disable auto update and schedule the full scan.
Nudge/hint/sledgehammer the query optimiser in to using the preferred plan, without relying on statistics being 100% accurate.


John Sansom was trying to lead you down the second route with his comment on your SO post, your response suggests you're not keen on the idea?


  I don't really see what that has to do with the actual question...
  anyway, consider that the suboptimal plan used two clustered-index
  scans whereas in the optimal one they are not present (replaced by
  seeks on the same indexes).


If it's not viable to full scan frequently enough to keep the statistics current and maintain the good execution plan, there are other options. The right options can be suggested given the right information on the problem execution plan. A couple of suggestions to start:

Ascending Keys and Auto Quick Corrected Statistics - A not uncommon statistics issue with large tables is ascending data, dates and identity columns for example. Filters on data created after the last statistics update can result in execution plans expecting very low selectivity when in fact large numbers of rows exist.

Hints and/or plan guides - OPTIMIZE FOR and RECOMPILE may be applicable to your scenario. KEEPFIXED PLAN could be used in conjunction with forcing a recompile immediately following a scheduled statistics update.

Plan Forcing - Capture your good plan, attach it to the problem query.

Edit: update following comment regarding this being a vendor application

This is exactly why plan guides exist, giving the DBA a chance to influence execution plans when modifying source code is not possible. There are two approaches (both code samples taken from BOL):


Create an object (if the target is a stored procedure) or SQL Plan (if matching a single statement) guide, as outlined in Understanding Plan Guides and either apply OPTION hints or attach the good execution plan by capture.





USE AdventureWorks2008R2;
GO
SELECT City, StateProvinceID, PostalCode FROM Person.Address ORDER BY PostalCode DESC;
GO
DECLARE @xml_showplan nvarchar(max);
SET @xml_showplan = (SELECT query_plan
    FROM sys.dm_exec_query_stats AS qs 
    CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) AS st
    CROSS APPLY sys.dm_exec_text_query_plan(qs.plan_handle, DEFAULT, DEFAULT) AS qp
    WHERE st.text LIKE N'SELECT City, StateProvinceID, PostalCode FROM Person.Address ORDER BY PostalCode DESC;%');

EXEC sp_create_plan_guide 
    @name = N'Guide1_from_XML_showplan', 
    @stmt = N'SELECT City, StateProvinceID, PostalCode FROM Person.Address ORDER BY PostalCode DESC;', 
    @type = N'SQL',
    @module_or_batch = NULL, 
    @params = NULL, 
    @hints = @xml_showplan;
GO



Create a guide from the cached execution plan, while it's "good", using sp_create_plan_from_guide





USE AdventureWorks2008R2;
GO
SELECT WorkOrderID, p.Name, OrderQty, DueDate
FROM Production.WorkOrder AS w 
JOIN Production.Product AS p ON w.ProductID = p.ProductID
WHERE p.ProductSubcategoryID &gt; 4
ORDER BY p.Name, DueDate;
GO
-- Inspect the query plan by using dynamic management views.
SELECT * FROM sys.dm_exec_query_stats AS qs
CROSS APPLY sys.dm_exec_sql_text(sql_handle)
CROSS APPLY sys.dm_exec_text_query_plan(qs.plan_handle, qs.statement_start_offset, qs.statement_end_offset) AS qp
WHERE text LIKE N'SELECT WorkOrderID, p.Name, OrderQty, DueDate%';
GO
-- Create a plan guide for the query by specifying the query plan in the plan cache.
DECLARE @plan_handle varbinary(64);
DECLARE @offset int;
SELECT @plan_handle = plan_handle, @offset = qs.statement_start_offset
FROM sys.dm_exec_query_stats AS qs
CROSS APPLY sys.dm_exec_sql_text(sql_handle) AS st
CROSS APPLY sys.dm_exec_text_query_plan(qs.plan_handle, qs.statement_start_offset, qs.statement_end_offset) AS qp
WHERE text LIKE N'SELECT WorkOrderID, p.Name, OrderQty, DueDate%';

EXECUTE sp_create_plan_guide_from_handle 
    @name =  N'Guide1',
    @plan_handle = @plan_handle,
    @statement_start_offset = @offset;
GO
-- Verify that the plan guide is created.
SELECT * FROM sys.plan_guides
WHERE scope_batch LIKE N'SELECT WorkOrderID, p.Name, OrderQty, DueDate%';
GO