Sql-server – Why does SQL Server refuse to update these statistics with anything but fullscan

I noticed a relatively long running (20 min+) auto update statistics operation in a daily datawarehouse build. The table involved is

CREATE TABLE [dbo].[factWebAnalytics](
    [WebAnalyticsId] [bigint] IDENTITY(1,1) NOT NULL,
    [MarketKey] [int] NOT NULL CONSTRAINT [DF_factWebAnalytics_MarketKey]  DEFAULT ((-1)),
    /*Other columns removed*/
 CONSTRAINT [PK_factWebAnalytics] PRIMARY KEY CLUSTERED 
(
    [MarketKey] ASC,
    [WebAnalyticsId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [MarketKeyPS]([MarketKey])
) ON [MarketKeyPS]([MarketKey])

This is running on Microsoft SQL Server 2012 (SP1) – 11.0.3513.0 (X64) so writable columnstore indexes are not available.

The table contains data for two distinct Market keys. The build switches out the partition for a specific MarketKey to a staging table, disables the columnstore index, performs necessary writes, rebuilds the columnstore, then switches it back in.

The execution plan for the update statistics shows that it pulls out all rows from the table, sorts them, gets the estimated number of rows badly wrong and spills to tempdb with spill level 2.

Running

SELECT [s].[name] AS "Statistic",
       [sp].*
FROM   [sys].[stats] AS [s]
       OUTER APPLY sys.dm_db_stats_properties ([s].[object_id], [s].[stats_id]) AS [sp]
WHERE  [s].[object_id] = OBJECT_ID(N'[dbo].[factWebAnalytics]'); 

Shows

If I explicitly try and reduce the sample size of that index's statistics to that used by the others with

UPDATE STATISTICS [dbo].[factWebAnalytics] [PK_factWebAnalytics] WITH SAMPLE 897667 ROWS

The query runs for 20 minutes+ again and the execution plan shows that it is processing all rows not the 897,667 sample requested.

The statistics generated at the end of all this aren't very interesting and definitely don't seem to warrant the time spent on a full scan.

Statistics for INDEX 'PK_factWebAnalytics'.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Name                            Updated                         Rows                            Rows Sampled                    Steps                           Density                         Average Key Length              String Index                    
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PK_factWebAnalytics             Jan 22 2016 11:31AM             420072086                       420072086                       2                               0                               12                              NO                                                              420072086                       

All Density                     Average Length                  Columns                         
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0.5                             4                               MarketKey                       
2.380544E-09                    12                              MarketKey, WebAnalyticsId       

Histogram Steps                 
RANGE_HI_KEY                    RANGE_ROWS                      EQ_ROWS                         DISTINCT_RANGE_ROWS             AVG_RANGE_ROWS                  
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1                               0                               3.441652E+08                    0                               1                               
2                               0                               7.590685E+07                    0                               1                               

Any ideas why I am encountering this behaviour and what steps I can take other than using NORECOMPUTE on these?

A repro script is here. It simply creates a table with a clustered PK and a columnstore index and tries to update the PK stats with a low sample size. This does not use partitioning – showing that the partitioning aspect is not required. However the use of partitioning described above does make matters worse as switching out the partition and then switching it back in (even without any other changes) will increase the modification_counter by double the number of rows in the partition thus practically guaranteeing that the statistics will be considered stale and auto updated.

I've tried adding a non clustered index to the table as indicated in KB2986627 (both filtered with no rows and then, when that failed, a non filtered NCI also with no effect).

The repro did not show the problematic behaviour on build 11.0.6020.0 and after upgrading to SP3 the issue is now fixed.