Speeding up Count(*) on large tables

The indexed view should be among the fastest options, with the lowest maintenance overhead, when implemented optimally.

Modifications are incremental (deltas) as I explain in detail in Indexed View Maintenance in Execution Plans (a full recount is not performed on every base table update); however, you do need to ensure that the delta update parts of the execution plan have efficient access methods (like any query).

It is typically quite simple to identify a missing index from the INSERT/UPDATE/DELETE execution plan. Perhaps you could add an illustrative post-execution (actual) execution plan to your question.

Automatic matching of query text to an indexed view is only available in Enterprise Edition (and equivalents). In other editions, you must use the WITH (NOEXPAND) table hint. There are also good reasons to use NOEXPAND even on Enterprise Edition.

Regarding the demo code: Make sure you specify the hint using WITH (NOEXPAND). The way you have written it, NOEXPAND is parsed as an alias. Note also that only materialized (indexed) views can have a NOEXPAND hint.

If you are unable to add a hint directly, this would be an excellent use of a Plan Guide. A plan guide can also be used to ensure that a query that matches an indexed view (without naming it explicitly) actually uses the indexed view.

Remember that without NOEXPAND on a materialized (indexed) view, SQL Server always expands the view definition at the start of plan compilation. Enterprise Edition may (or may not) match (parts of) a query to an indexed view depending on its assessment of the costs of each option.

Related Q & A:

• How can I make sure the SQL Server query optimizer uses the exact tables in the query
• Why does the READPAST hint cause indexed views to be ignored?
• What factors go into an Indexed View's Clustered Index being selected?

If you're stuck on SQL Server 2012 you could try creating an index on just the clustered index key. It might be a little smaller than an index on a TINYINT column. You could also try adding page compression to your index. That could make your query faster but it depends on the data in the table.

If you're able to upgrade to SQL Server 2016 then you can create a nonclustered columnstore index on the table. That will make COUNT(*) queries extremely fast with a lower overhead on DML operations. Here's a quick demo:

DROP TABLE IF EXISTS #Items;

CREATE TABLE #Items (
    CLUST_KEY BIGINT NOT NULL,
    SMALL_COLUMN TINYINT NOT NULL,
    FILLER VARCHAR(50) NOT NULL,
    PRIMARY KEY (CLUST_KEY)
);

INSERT INTO #Items WITH (TABLOCK)
SELECT
    ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
    , 1
    , REPLICATE('Z', 50)
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

CREATE INDEX NCI ON #Items (SMALL_COLUMN);

SET STATISTICS TIME ON;

-- CPU time = 312 ms,  elapsed time = 320 ms.
SELECT COUNT(*)
FROM #Items
OPTION (MAXDOP 1);


CREATE NONCLUSTERED COLUMNSTORE INDEX NCCI ON #Items (SMALL_COLUMN);

-- CPU time = 0 ms,  elapsed time = 1 ms.
SELECT COUNT(*)
FROM #Items
OPTION (MAXDOP 1);

With the NCCI I'm able to count six million rows in under 20 ms.