Expressing the query using different syntax can sometimes help communicate your wish to use a non-clustered index to the optimizer. You should find the form below gives you the plan you want:
SELECT
[ID],
[DeviceID],
[IsPUp],
[IsWebUp],
[IsPingUp],
[DateEntered]
FROM [dbo].[Heartbeats]
WHERE
[ID] IN
(
-- Keys
SELECT TOP (1000)
[ID]
FROM [dbo].[Heartbeats]
WHERE
[DateEntered] >= CONVERT(datetime, '2011-08-30', 121)
AND [DateEntered] < CONVERT(datetime, '2011-08-31', 121)
);
Compare that plan with the one produced when the non-clustered index is forced with a hint:
SELECT TOP (1000)
*
FROM [dbo].[Heartbeats] WITH (INDEX(CommonQueryIndex))
WHERE
[DateEntered] BETWEEN '2011-08-30' and '2011-08-31';
The plans are essentially the same (a Key Lookup is nothing more than a seek on the clustered index). Both plan forms will only ever perform one seek on the non-clustered index and a maximum of 1000 lookups into the clustered index.
The important difference is in the position of the Top operator. Positioned between the two seeks, the Top prevents the optimizer from replacing the two seeking operations with a logically-equivalent scan of the clustered index. The optimizer works by replacing parts of a logical plan with equivalent relational operations. Top is not a relational operator, so the rewrite prevents the transformation to a clustered index scan. If the optimizer were able to reposition the Top operator, it would still prefer the scan over the seek + lookup because of the way cost estimation works.
Costing of scans and seeks
At a very high level, the optimizer's cost model for scans and seeks is quite simple: it estimates that 320 random seeks cost the same as reading 1350 pages in a scan. This probably bears little resemblance to the hardware capabilities of any particular modern I/O system, but it does work reasonably well as a practical model.
The model also makes a number of simplifying assumptions, a major one being that every query is assumed to start with no data or index pages already in cache. The implication is that every I/O will result in a physical I/O - though this will rarely be the case in practice. Even with a cold cache, pre-fetching and read-ahead mean that the pages needed are actually quite likely to be in memory by the time the query processor needs them.
Another consideration is that the first request for a row that is not in memory will cause the whole page to be fetched from disk. Subsequent requests for rows on the same page will very likely not incur a physical I/O. The costing model does contain logic to take some account of effects like this, but it is not perfect.
All these things (and more) means the optimizer tends to switch to a scan earlier than in probably should. Random I/O is only 'much more expensive' than 'sequential' I/O if a physical operation results - accessing pages in memory is very fast indeed. Even where a physical read is required, a scan may not result in sequential reads at all due to fragmentation, and seeks may be collocated such that the pattern is essentially sequential. Add to that the changing performance characteristic of modern I/O systems (especially solid-state) and the whole thing starts to look very shaky.
Row Goals
The presence of a Top operator in a plan modifies the costing approach. The optimizer is smart enough to know that finding 1000 rows using a scan will likely not require scanning the whole clustered index - it can stop as soon as 1000 rows have been found. It sets a 'row goal' of 1000 rows at the Top operator and uses statistical information to work back from there to estimate how many rows it expects to need from the row source (a scan in this case). I wrote about the details of this calculation here.
The images in this answer were created using SQL Sentry Plan Explorer.
