SQL query executing slowly (for some parameter values)

Question

I have a SQL Server 2005 database with several tables. One of the tables is used to store timestamps and message counters for several devices, and has the following columns:

CREATE TABLE [dbo].[Timestamps] (
[Id] [uniqueidentifier] NOT NULL,
[MessageCounter] [bigint] NULL,
[TimeReceived] [bigint] NULL,
[DeviceTime] [bigint] NULL,
[DeviceId] [int] NULL
)

Id is the unique primary key (Guid.Comb), and I have indexes on both DeviceId and MessageCounter columns.

What I want to do is find the last inserted row (the row with the largest MessageCounter) for a certain device.

The thing that is strange is that a query for device no. 4 (and all other devices except no.1) returns almost instantaneously:

select top 1 * 
   from "Timestamps"
   where DeviceId = 4
   order by MessageCounter desc

but the same query for device no. 1 takes forever to complete:

select top 1 * 
   from "Timestamps"
   where DeviceId = 1 /* this is the only line changed */
   order by MessageCounter desc

The strangest thing is that device 1 has much less rows than device 4:

select count(*) from "Timestamps" where DeviceId = 4
(returns 1,839,210)

select count(*) from "Timestamps" where DeviceId = 1
(returns 323,276).

Does anyone have a clue what I could be doing wrong?

[Edit]

From the execution plans for both queries, it is clearly visible that Device 1 (lower diagram) creates a much larger number of rows in Index scan:

Execution plans for device 4 (upper) and device 1 (lower) http://img295.imageshack.us/img295/5784/execplans.png

The difference is when I hover the Index Scan nodes on execution plan diagrams:

Device 4 Actual Number of Rows: 1

Device 1 Actual Number of Rows: approx. 6,500,000

6,500,000 rows is a very strange number, since my select count(*) query returns around 300,000 rows for device 1!

Answer 1

Try creating an index on (DeviceId, MessageCounter DESC).

Also, try this query:

select * 
   from "Timestamps"
   where DeviceId = 1
   and MessageCounter = (SELECT MAX(MessageCounter) FROM "Timestamps" WHERE DeviceID = 1)

Just guessing: The performance difference might be because DeviceId = 1 is spread across more pages than DeviceId = 4. By sorting, I suspect you are dredging up all matching pages, even if you end up selecting only the top row.