Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I'm storing sensor data in a table SensorValues. The table and primary key is as follows:

CREATE TABLE [dbo].[SensorValues](
  [DeviceId] [int] NOT NULL,
  [SensorId] [int] NOT NULL,
  [SensorValue] [int] NOT NULL,
  [Date] [int] NOT NULL,
CONSTRAINT [PK_SensorValues] PRIMARY KEY CLUSTERED 
(
  [DeviceId] ASC,
  [SensorId] ASC,
  [Date] DESC
) WITH (
    FILLFACTOR=75,
    DATA_COMPRESSION = PAGE,
    PAD_INDEX = OFF,
    STATISTICS_NORECOMPUTE = OFF,
    SORT_IN_TEMPDB = OFF,
    IGNORE_DUP_KEY = OFF,
    ONLINE = OFF,
    ALLOW_ROW_LOCKS = ON,
    ALLOW_PAGE_LOCKS = ON)
  ON [MyPartitioningScheme]([Date])

Yet, when I select the sensor value valid for a specific time the execution plan tells me it is doing a sort. Why is that?

I would have thought that since I store the values sorted by the Date column, the sorting would not occure. Or is it because the index isn't solely sorted by the Date column, i.e. it can't assume that the result set is sorted?

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010
  ORDER BY Date DESC

Execution Plan

Edit: Can I do this instead?

Since the table is sorted DeviceId, SensorId, Date and I do a SELECT specifying only one DeviceId and one SensorId, the output set should already be sorted by Date DESC. So I wonder if the following question would yield the same result in all cases?

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010

According to @Catcall below, the sort order is not the same as the storage order. I.e. we can't assume that the returned values are already in a sorted order.

Edit: I've tried this CROSS APPLY solution, no luck

@Martin Smith suggested I'd try to OUTER APPLY my result against the partitions. I found a blog post (Aligned non-clustered indexes on partitioned table) describing this similar problem and tried the somewhat similar solution to what Smith suggested. However, no luck here, the execution time is on par with my original solution.

WITH Boundaries(boundary_id)
AS
(
  SELECT boundary_id
  FROM sys.partition_functions pf
  JOIN sys.partition_range_values prf ON pf.function_id = prf.function_id
  WHERE pf.name = 'PF'
  AND prf.value <= 1339225010
  UNION ALL
  SELECT max(boundary_id) + 1
  FROM sys.partition_functions pf
  JOIN sys.partition_range_values prf ON pf.function_id = prf.function_id
  WHERE pf.name = 'PF'
  AND prf.value <= 1339225010
),
Top1(SensorValue)
AS
(
  SELECT TOP 1 d.SensorValue
  FROM Boundaries b
  CROSS APPLY
  (
    SELECT TOP 1 SensorValue
      FROM SensorValues
      WHERE  SensorId = 53
        AND DeviceId = 3819
        AND "Date" < 1339225010
        AND $Partition.PF(Date) = b.boundary_id
        ORDER BY Date DESC
  ) d
  ORDER BY d.Date DESC
)
SELECT SensorValue
FROM Top1
share|improve this question

migrated from stackoverflow.com Jun 13 '12 at 7:08

This question came from our site for professional and enthusiast programmers.

    
Have you tried ORDER BY DeviceID, SensorID, Date DESC ? –  ypercube Jun 12 '12 at 14:18
    
Can you replicate without compression and partitioning at all? What if you add OPTION MAXDOP 1? –  gbn Jun 12 '12 at 14:20
    
OPTION MAXDOP 1 does not help. As specified by @Martin Smith below, it seems as the partitioning is what's causing it... –  m__ Jun 13 '12 at 6:41

4 Answers 4

up vote 10 down vote accepted

For a non partitioned table I get the following plan

Plan 1

There is a single seek predicate on Seek Keys[1]: Prefix: DeviceId, SensorId = (3819, 53), Start: Date < 1339225010.

Meaning that SQL Server can perform an equality seek on the first two columns and then begin a range seek starting at 1339225010 and ordered FORWARD (as the index is defined with [Date] DESC)

The TOP operator will stop requesting more rows from the seek after the first row is emitted.

When I create the partition scheme and function

CREATE PARTITION FUNCTION PF (int)
AS RANGE LEFT FOR VALUES (1000, 1339225009 ,1339225010 , 1339225011);
GO
CREATE PARTITION SCHEME [MyPartitioningScheme]
AS PARTITION PF
ALL TO ([PRIMARY] );

And populate the table with the following data

INSERT INTO [dbo].[SensorValues]    
/*500 rows matching date and SensorId, DeviceId predicate*/
SELECT TOP (500) 3819,53,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0))           
FROM master..spt_values
UNION ALL
/*700 rows matching date but not SensorId, DeviceId predicate*/
SELECT TOP (700) 3819,52,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0))           
FROM master..spt_values
UNION ALL 
/*1100 rows matching SensorId, DeviceId predicate but not date */
SELECT TOP (1100) 3819,53,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0)) + 1339225011      
FROM master..spt_values

The plan on SQL Server 2008 looks as follows.

Plan 2

The actual number of rows emitted from the seek is 500. The plan shows seek predicates

Seek Keys[1]: Start: PtnId1000 <= 2, End: PtnId1000 >= 1, 
Seek Keys[2]: Prefix: DeviceId, SensorId = (3819, 53), Start: Date < 1339225010

Indicating it is using the skip scan approach described here

the query optimizer is extended so that a seek or scan operation with one condition can be done on PartitionID (as the logical leading column) and possibly other index key columns, and then a second-level seek, with a different condition, can be done on one or more additional columns, for each distinct value that meets the qualification for the first-level seek operation.

This plan is a serial plan and so for the specific query you have it seems that if SQL Server ensured that it processed the partitions in descending order of date that the original plan with the TOP would still work and it could stop processing after the first matching row was found rather than continuing on and outputting the remaining 499 matches.

In fact the plan on 2005 looks like it does take that approach

Plan on 2005

I'm not sure if it is straight forward to get the same plan on 2008 or maybe it would need an OUTER APPLY on sys.partition_range_values to simulate it.

share|improve this answer
    
Your idea seems logical, but I feel I'm over my head when it comes to the OUTER APPLY and sys.partition_range_values. Can you give me any hints or links to other sites that describes this approach? (and...I'm using sql server 2012 if that makes any difference) –  m__ Jun 13 '12 at 5:45
    
@m__ I won't have time to look at it now but the idea would be to have a nested loops plan (probably just use INNER LOOP JOIN rather than OUTER APPLY) with the driving table being two columns (left boundary, right boundary retrievable from sys.partition_range_values) and the inner side of the join just accessing one partition per execution. –  Martin Smith Jun 13 '12 at 7:22
    
And then change the query slightly to TOP 1 ... ORDER BY driving_table.left_boundary DESC, DATE desc with the idea of getting a plan where it processes each partition individually in descending date order and stops when the first row is found, similar to the 2005 plan –  Martin Smith Jun 13 '12 at 7:29
    
I found a blog post that used CROSS APPLY to fix the same problem, but it did not improve the execution time at all (see updated question). I will try to look inte your OUTER APPLY suggestion... –  m__ Jun 13 '12 at 8:11
    
@m__ - What plan do you get for that query you added to the question on 2012? When I try it on 2008 R2 with my example data I see it only pushing 1 row round rather than the 500 previously. It does look as though it is doing an unnecessary second join on SensorValues though. Why not just SELECT * FROM Top1? –  Martin Smith Jun 13 '12 at 9:25

A lot of people believe that a clustered index guarantees a sort order on output. But that's not what it does; it guarantees a storage order on disk.

See, for example, this blog post, and this longer discussion.

share|improve this answer
2  
Not what they are asking. They are asking why the plan requires a sort operator to get the TOP 1 ordered by date and what index would avoid that I think. –  Martin Smith Jun 12 '12 at 14:12
    
The OP said, "Since the table is sorted DeviceId, SensorId, Date and I do a SELECT specifying only one DeviceId and one SensorId, the output set should already be sorted by Date DESC." –  Mike Sherrill 'Cat Recall' Jun 12 '12 at 14:19
    
Ah sorry I see you were specifically addressing the "Can I do this instead?". –  Martin Smith Jun 12 '12 at 14:34
1  
Well, earlier, the OP also said, "I would have thought that since I store the values sorted by the Date column, the sorting would not occure [sic]." So at least part of the problem is that misconception about what a clustered index does. I think it's good to straighten that out anyway. –  Mike Sherrill 'Cat Recall' Jun 12 '12 at 14:41
    
Maybe I'm just being stubborn (so please forgive me ;-)). Anyhow, I've read the blog post by Hugo Kornelis and it is pretty straight forward. However, in his example he is using one clustered index and one non-clustered, the non-clustered index is smaller in size and is thereby being used in the execution plan. In my case I have only one clustered index, can sql server still return the values in wrong order (it has no smaller index to use and full table scans are way too slow)? –  m__ Jun 13 '12 at 9:28

I'm speculating that the SORT is needed because of parallel plan. I base this on some dim and distant blog article: but I found this on MSDN which may or may not justify this

So, try with MAXDOP 1 and see what happens...

Also hinted at in @sql kiwi's blog post on Simple Talk under "Exchange Operator" I think. And "DOP dependence" here

share|improve this answer
3  
Seems possible. When I run the OP's CREATE TABLE and the SELECT query on an empty table I get a serial plan with no sort operator. –  Martin Smith Jun 12 '12 at 14:27
    
@MartinSmith: Thanks Martin. Trying to find some reference to back this up too... –  gbn Jun 12 '12 at 14:29
    
Although I hadn't bothered setting up a partition function on date before. Now I have and seems to be partitioning is the culprit with 2005 possibly behaving better for this particular query. –  Martin Smith Jun 13 '12 at 0:00

Basically you are right - since the primary key is in the order "DeviceId, SensorId, Date", the data in the key is not sorted by date, so can't be used. If your key was in a different order "Date, DeviceId, SensorId", then the data in the key would be sorted by date, so could be used...

share|improve this answer
    
Changing the sort order gives me performance-issues because it has a hard time fetching values for the specific device. Would a non-clustered index, i.e. "CREATE NONCLUSTERED INDEX NewIndex ON SensorValues ( Date ASC )", do the trick? –  m__ Jun 12 '12 at 8:36
1  
Well, it did remove the sorting but instead added an Index Seek and Key Lookup. The resulting execution time is on par with my earlier solution. –  m__ Jun 12 '12 at 9:36
    
Sorry, I didn't mean to suggest you change your key, I was just illustrating the point! It really depends what you do most often - if you regularly read ordered by solely date, more often than the key access, then you could change your original key to be non clustered, and add a clustered index ordered solely by Date. It depends on what else you do with the table really –  Fergus Bown Jun 12 '12 at 9:40
    
Or you could just add a separate non clustered index, which should help, but won't help as much as a clustered index... –  Fergus Bown Jun 12 '12 at 9:42
    
Actually, I've just reread the question, and realised that I'm being dim - with the where clause you have specified, the change in index won't make any difference I don't think –  Fergus Bown Jun 12 '12 at 9:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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