Why SELECT COUNT(*) performs clustered index scan?

Question

I have the following table:

CREATE TABLE [dbo].[Addr](
    [Address] [char](34) NOT NULL,
 CONSTRAINT [PK_Addr] PRIMARY KEY CLUSTERED 
(
    [Address] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

And I am trying to execute a query:

SELECT COUNT(*)
FROM Addr

When table contains about 8 million records, it was executing immediately. But now table contains 21 million records, and query is executing very slow. Managemet Studio shows the next estimated plan:

Screenshot from Storage tab (Table Properties):

I am using MSSQL 2008 Express 10.50.1617.0. Why this simple query has such complicated plan?

Answer 1

This plan is not complicated at all. To count the number of records, the engine has to scan entire table, but since there's a clustered index, it uses it. With no clustered index, thre would be Table Scan instead of Clustered Index Scan. If you had non-clustered index on any column, the optimizer would most probably choose that index to count the records, and the operation would be faster.