Sql Server 2005 COUNT on view takes too long

I have a paged list of newsletters in my website and I use this view to load it.

This is the view (without the list of columns selected):

SELECT * FROM dbo.NewsletterHistory 
INNER JOIN dbo.Newsletter ON dbo.NewsletterHistory.NewsletterId = dbo.Newsletter.NewsletterId 
INNER JOIN dbo.sysNewsletterHistoryState ON dbo.NewsletterHistory.sysNewsletterHistoryStateId = dbo.sysNewsletterHistoryState.sysNewslett开发者_如何学JAVAerHistoryStateId 
LEFT JOIN dbo.Client ON dbo.NewsletterHistory.AboutUserId = dbo.Client.ParentUserId

The problem appears when I try to execute a count query in order to show the paged list.

In NewsletterHistory table I have about 700.000 rows.

select count(*) from dbo.NewsletterHistoryView newsletter0_ where newsletter0_.DeliveryMethod  11 

This count query takes about 33 seconds to execute.

I can't just store this number of records somewhere because the paged list can be filtered.

Any ideas about how to resolve this problem?

Create an index on the NewsletterHistory table with the following columns

NewsletterId
sysNewsletterHistoryStateId
AboutUserId

I dont know your data, so try different orders of the three columns to find the fastest one. If its still not fast enough, give me more info.

Instead of using Count(*) you can use Count(PrimaryID).

Display Execution plan and add missing indexes.

an ugly solution .... throw your results into a temp table do the count... but i'd go with indexes...

Use the SQl Server management studio -> tools -> Database engine tuning advisor... place all your scripts there that use that table and let it tell you what will be the best indexes to build. It kind of helps doing it manually ... through trail and error