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?