16

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
1
  • 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, 2012 at 6:41

4 Answers 4

13

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.

1
9

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, a follow-up, and this longer discussion.

3
  • 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. Jun 12, 2012 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, 2012 at 9:28
  • I've moved this to a new question (off topic)
    – m__
    Jun 13, 2012 at 17:29
5

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

1
  • 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. Jun 13, 2012 at 0:00
1

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...

1
  • I had already tried changing the key the way you mentioned, so don't feel sorry. Anyway, will try creating the non-clustered index over all 3 columns and see what that gives me. (the quest for the missing index continues... ;-))
    – m__
    Jun 12, 2012 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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