I have a query that is currently taking an average of 2500ms to complete. My table is very narrow, but there are 44 million rows. What options do I have to improve performance, or is this as good as it gets?

The Query

SELECT TOP 1000 * FROM [CIA_WIZ].[dbo].[Heartbeats]
WHERE [DateEntered] BETWEEN '2011-08-30' and '2011-08-31'; 

The Table

CREATE TABLE [dbo].[Heartbeats](
    [ID] [int] IDENTITY(1,1) NOT NULL,
    [DeviceID] [int] NOT NULL,
    [IsPUp] [bit] NOT NULL,
    [IsWebUp] [bit] NOT NULL,
    [IsPingUp] [bit] NOT NULL,
    [DateEntered] [datetime] NOT NULL,
    [ID] ASC

The Index

CREATE NONCLUSTERED INDEX [CommonQueryIndex] ON [dbo].[Heartbeats] 
    [DateEntered] ASC,
    [DeviceID] ASC

Would adding additional indexes help? If so, what would they look like? The current performance is acceptable, because the query is only run occasionally, but I'm wondering as a learning exercise, is there anything I can do to make this faster?


When I change the query to use a force index hint, the query executes in 50ms:

SELECT TOP 1000 * FROM [CIA_WIZ].[dbo].[Heartbeats] WITH(INDEX(CommonQueryIndex))
WHERE [DateEntered] BETWEEN '2011-08-30' and '2011-08-31' 

Adding a correctly selective DeviceID clause also hits the 50ms range:

SELECT TOP 1000 * FROM [CIA_WIZ].[dbo].[Heartbeats]
WHERE [DateEntered] BETWEEN '2011-08-30' and '2011-08-31' AND DeviceID = 4;

If I add ORDER BY [DateEntered], [DeviceID] to the original query, I am in the 50ms range:

SELECT TOP 1000 * FROM [CIA_WIZ].[dbo].[Heartbeats]
WHERE [DateEntered] BETWEEN '2011-08-30' and '2011-08-31' 
ORDER BY [DateEntered], [DeviceID];

These all use the index I was expecting (CommonQueryIndex) so, I suppose my question is now, is there a way to force this index to be used on queries like this? Or is the size of my table throwing off the optimizer too much and I must just use an ORDER BY or a hint?

  • I guess you could add one more non clustered index on "DateEntered" which would increase the performance to some more extent – Praveen Aug 30 '12 at 19:28
  • @Praveen Would it basically be the same as my existing index? Do I need to do anything special since there will be two indexes on the same field? – Nate Aug 30 '12 at 19:31
  • @Nate, since the table is called heartbeat and there are 44million records involved I assume you have heavy inserts on this table? With indexing, you can only add a covering index to speed up. But as you mentioned you only use this query occasionally I would strongly advise against that if you do heavy inserts. It basically doubles your insert load. Are you running on enterprise edition? – Edward Dortland Aug 31 '12 at 14:21
  • I noticed that you have deviceID in your NC index. Is it possible to include that in your where clause? And would that bring down the result set below the threshold? <35k records (without the top 1000 clause). – Edward Dortland Aug 31 '12 at 14:23
  • 1
    last question, Are you always inserting in order of dateEntered? Or can these be out of order since devices might insert async from each other. You might try to change the clustered index to the DateEntered column. Your leave pages of your Clustered index are now 445 pages. That would double, if you would go from a int to a datetime. But in this case, that might not be to bad. – Edward Dortland Aug 31 '12 at 14:27

Why the the optimiser doesn't go for your your first index:

CREATE NONCLUSTERED INDEX [CommonQueryIndex] ON [dbo].[Heartbeats] 
    [DateEntered] ASC,
    [DeviceID] ASC

Is a matter of selectivity of the [DateEntered] Column.

You told us that your table has 44 million rows. the row size is:

4 bytes, for the ID, 4 bytes for the Device ID, 8 bytes for the date, and 1 byte for the 4 bit columns. that's 17 bytes + 7 bytes overhead for (tags, Null bitmap, var col offset,,col count) totals 24 Bytes per row.

That would rougly translate to 140k pages. To store those 44 million rows.

Now the optimiser can do two things:

  1. It could scan the table (clustered index scan)
  2. Or it could use your index. For every row in your index, it would then need to do a bookmark lookup in the clustered index.

Now at a certain point it just becomes more expensive to do all these single lookups in the clustered index for every index entry found in your non clustered index. The threshold for that is generally the total count of lookups should exceed 25% tot 33% of the total table page count.

So in this case: 140k/25%=35000 rows 140k/33%=46666 rows.

(@RBarryYoung, 35k is 0.08% of the total rows and 46666 is 0.10 %, so I think that is where the confusion was)

So if your where clause will result in somewhere between 35000 and 46666 rows.(this is underneath the top clause!) It's very likely that your non clustered will not be used and that the clustered index scan will be used.

The only two ways to change this are:

  1. Make your where clause more selective. (if possible)
  2. Drop the * and select only a few columns so you can use a covering index.

now sure you could create a covering index even when you use a select *. Hoever that just creates a massive overhead for your inserts/updates/deletes. We would have to know more about your work load (read vs write) to make sure if that's the best solution.

Changing from datetime to smalldatetime is a 16% reducion in size on clustered index and a 24% reduction in size on your non clustered index.

  • the scan threshold is normally much lower than that (10% or even lower), however since the range is a single day from over a year ago it should not make even that threshold. And a Clustered Index Scan is not a given, since a covering index was added. Since that index makes the WHERE clause SARG-able, it should be preferred. – RBarryYoung Aug 30 '12 at 20:53
  • @RBarryYoung I was trying to explain why the non clustered index on the [EnteredDate],[DeviceID] wasn't being used in the first place. Regarding the the Threshold I think we both agree, I'm only talking from a page perspective. I'll alter my answer to make it more clear. – Edward Dortland Aug 31 '12 at 5:53
  • Altered the answer to make it more clear what I was answering. I can't explain why the covering index that @RBarryYoung suggested isn't used. I tested it on a million rows just here, and the optimiser it using the covering index. – Edward Dortland Aug 31 '12 at 6:35
  • Thanks for a very comprehensive response, makes a lot of sense. With respect to the workload, the table has 150-300 inserts per 5 minute period and a few reads per day for reporting purposes. – Nate Aug 31 '12 at 14:19
  • The overhead head for the covering index isn't really significant given that it's a narrow table and the "covering" is just an addition to the pre-existing index that already included most of the row. – RBarryYoung Aug 31 '12 at 14:39

Is there a particular reason that your PK is clustered? Many people do this because it defaults that way, or they think that PKs must be clustered. No so. Clustered indexes are usually best for range queries (like this one) or on the foreign key of a child table.

An effect of a clustering index is that it bunches all of the data together because the data is stored on the leaf nodes of the cluster b tree. So, assuming that you are not asking for 'too wide' of a range, the optimizer will know exactly what part of the b tree contains the data and it won't have to find a row identifer and then hop over to where the data is (like it does when dealing with a NC index). What is 'too wide' of a range? A ridiculous example would be asking for 11 months of data from a table that only has a year's worth of records. Pulling one day of data should not be a problem, assuming that your statistics are up to date. (Though, the optimizer may get into trouble if you are looking for yesterday's data and you haven't updated stats for three days.)

Since you are running a "SELECT *" query, the engine will need to return all of the columns in the table (even if someone adds a new one that your app doesn't need at that moment) so a covering index or an index with included columns won't help much, if at all. (If you are including every column from the table in an index, you are doing something wrong.) The optimizer will probably ignore those NC indexes.

So, what to do?

My suggestion would be to drop the NC index, change the clustered PK to nonclustered and create a clustered index on [DateEntered]. Simpler is better, until it is proved otherwise.

  • Assuming the rows are inserted in increasing order this is the simplest answer - but inserting in non-linear order will cause fragmentation. – Kirk Broadhurst Sep 4 '12 at 1:04
  • Adding data to any b-tree structure will cause it to lose balance. Even if you are adding rows in cluster order, the indexes will lose balance. Re-indexing tables removes fragmentation, and any DBA will tell you that tables need to be re-indexed after "enough" data has been added to a table. (The definition of "enough" might be debated, or "when" might be a discussion.) I don't see anything in the question that says re-indexing can't be done for some reason. – Darin Strait Sep 5 '12 at 10:45

As long as you've got that "*" in there, then the only thing that I could imagine that would make much difference would be to change your index definition to this:

CREATE NONCLUSTERED INDEX [CommonQueryIndex] ON [dbo].[Heartbeats] 
    [DateEntered] ASC,
    [DeviceID] ASC
)INCLUDE (ID, IsWebUp, IsPingUp, IsPUp)

As I noted in the comments, it should use that index, but if it doesn't you can persuade it to with either an ORDER BY or an index hint.

  • I just tried this out and I'm still in pretty much the same spot, 2500ms wait for server response and 10ms client process time. – Nate Aug 30 '12 at 20:02
  • Post the query plan. – RBarryYoung Aug 30 '12 at 20:08
  • Looks like it is using the Clustered Index. (SELECT Cost: 0% <- Top Cost: 20% <- Clustered Index Scan PK_Heartbeats Cost: 80%) – Nate Aug 30 '12 at 20:15
  • Yeah, that's not right, somethings throwing the stats/optimizer off. Add a hint to force it to use the new index. – RBarryYoung Aug 30 '12 at 20:18
  • @Max Vernon: Maybe, but that should have been flagged on the query plan. – RBarryYoung Aug 30 '12 at 20:48

I'd look at this a bit differently.

  • Yes, I know it's an old thread but I'm intrigued.

I'd dump the datetime column - change it to an int. Have a lookup table or do a convert for your date.

Dump the clustered index - leave it as a heap and create a non-clustered index on the new INT column which represents the date. i.e. today would be 20121015. That order is important. Depending on how frequently you load the table, look at creating that index in DESC order. Maint cost will be higher and you will want to introduce a fill factor or partitioning. Partitioning would also help decrease your run time.

Lastly, if you can use SQL 2012, try using SEQUENCE - it will outperform identity() for inserts.

  • Interesting solution. While it is not obvious from my question, the time portion of the DateTime is very important. Generally I query based on date, to review specific times during that period. How would you adjust this solution to account for that? – Nate Nov 16 '12 at 15:21
  • In that case, keep the datetime column, add the int column for date (since your range is based on the date element and not the time element). You could also consider using the TIME datatype and then, effectively split the time apart from the date. In that manner, your data footprint is smaller and you still have the Time element of the column. – Jeremy Lowell Nov 16 '12 at 15:27
  • 1
    I'm not sure why I missed this earlier but use row compression on the clustered index and the non-clustered index as well. I just did a quick test with your table and here's what I found: I created a set of data (5.8 million rows) in the table defined above. I compressed (row) the clustered and nonclustered index. logical reads, based on your exact query, decreased from 2,074 to 1,433. That's a significant decrease and I'm confident that alone would help you out - and it's very low risk. – Jeremy Lowell Nov 16 '12 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.