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.

Rewrote this question 2012-06-20 for clarity, check edits for older version

Background and Question

I collect data for a couple of sensors on some devices. This data I want to display for the user as curves in a graph, i.e. I want to plot the measured points and draw lines between them. The user is able to decide for what date range he wants to show values for by zooming and panning in the graph.

The number of measured values begins to add up and at this moment I have a number of values in the range of 500'000'000, and counting. For a single sensor I can at most find about 2'000'000 values as of now, but It will most likely increase. These values are not logged at an even interval (i.e. every second) but instead when a change can be measured (see the difference in the date column below).

Date  SensorValue
----- -----------
10    123
30    118
70    114
85    115
90    116
95    117

Since the display area for this graph is 1000px there's no point fetching all those values. Instead I try to fetch at most 1000 values and keep them evenly distributed inside the date range the user has zoomed in upon. Exactly which values inside the date range that is returned doesn't matter as long as they are evenly distributed in terms of the date (this is important to remember since they aren't logged at an even interval).

I store these values in a quite simple table as can be seen below, with only one (clustered) index. Notice that the Date is stored as an integer ("unix time") not as a datetime2 field. The table is partitioned by Date if that matters.

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
);

I'm searching for one of two things, either an improved query that will return these values faster, or a different approach on how to extract those values. If anything is unclear, keep asking me and I will try to answer.

My current approach

To achieve this I calculate the difference in time for the date range I'm fetching data for and divides this by the number of values I want to fetch at most. I store this in the variable I call @resolution below.

When I query the database it calculates and groups the matching rows by the date divided by @resolution and picks out one value per group. I do know that this is not a fool-proof algorithm. In some cases it returns more values than requested, but it doesn't matter that much for me since it at least keeps the number of values down to a manageable level.

For a sensor with small amount of data (tens of thousand of values), this is fairly quick but when it comes to a sensor with much data (millions of rows) it slows down and takes a couple of seconds (at least) to query the database. How should one go about querying for this information in a better way?

SELECT sv.SensorValue, sv.Date
  FROM SensorValues sv
  INNER JOIN (SELECT MAX(svInner.Date) AS svInner.Date
                FROM SensorValues svInner
                WHERE svInner.SensorId = @sensorid
                  AND svInner.DeviceId = @deviceid
                  AND svInner.Date BETWEEN @startdate AND @stopdate
                  AND svInner.Sensorvalue != -32767
                  AND svInner.SensorValue != -32768
                  GROUP BY svInner.Date / @resolution) j ON sv.Date = j.Date
  WHERE sv.SensorId = @sensorid
    AND sv.DeviceId = @deviceid
    AND sv.SensorValue != -32767
    AND sv.SensorValue != -32768
  ORDER BY sv.Date DESC

Query Plan for above query

Example: If I want to select 3 values between time 0 and 95 from the table example above I do the following.

I calculate the @resolution to (95-0)/3=31 and then for each row between time 0 and 95, calculates Date/@resolution (integer division everywhere):

Date  SensorValue Date/@resolution
----- ----------- ----------------
10    123         0
30    118         0
70    114         2
85    115         2
90    116         2
95    117         3

I then select one value from each group by using MAX(Date).

Date  SensorValue Date/@resolution
----- ----------- ----------------
30    118         0
90    116         2
95    117         3
share|improve this question
    
is Sensorvalue smallint? What version of SQL Server? –  gbn Jun 15 '12 at 12:51
    
@gbn: SensorValue is a regular int. SQL Server 2012 –  m__ Jun 15 '12 at 12:58
    
What results do you expect from your sample data, exactly? Why is Date shown as a datetime when the table definition shows it as an int? –  Aaron Bertrand Jun 18 '12 at 13:43
    
My bad, Date is integer but can be represented (by recalculation) as a string which I displayed for easier interpretion. I've also improved my example. –  m__ Jun 18 '12 at 14:02
add comment

3 Answers 3

Hmm how about something along the lines of adding a new modulo column....

  1. make a sensor data key 1, 2, 3 .... N an ascending unique counter up to N your final and last sensor data point.
  2. pick R your resolution, as in you want to select every Rth data point.
  3. for all rows, calculate M = P mod R, and store that value in a corresponding M column for all data.
  4. Select data where M = x where x is any number from 0 to R-1

SQL implementation: alter your tables so that the new key P is unique ascending and numeric from 1 to N. Alter the table so that the you also have a modulo column (integer).

create and execute procedure that fills your modulo column when you want to change the resolution.

Create procedure fillModulo
    @R int,  -- resolution parameter
    @N numeric  -- count of number of data points
As 
declare @j numeric = 1;  - our primary counter from one to the last data point

while @j <= @N     --while loop until the last data point
begin
    UPDATE SensorValues
    set modulo = @j%@R
    Where P_Id= @j;

    set @j = @j +1;
end 
go

exec fillModulo @R = 1000, @N = 5000000;
go

select your data, picking any number x from 0 to R. below we choose x = 0 for example.

Select * from SensorValues where modulo = 0

So the fillModulo procedure you only have to do once every time you want to adjust resolution or add new data (takes a seconds). But the select would be just a normal select where modulo = 0, which would take no extra time at all.

Alternatively, if you don't intend to change R you can fill the Modulo column automatically during the process that fills the table with data, so it would take a second there, but select is normal time.

Update: Ahh, alternatively see other answer. row_number() is possibly easier to use than altering your table.

share|improve this answer
    
Could've been a solution if it weren't that the resolution changes depending on the user's interactions with my application. –  m__ Jun 18 '12 at 5:30
    
I see then it may be easier to random sample as Rusanu mentioned. where sample size is S= N/R –  fa1c0n3r Jun 18 '12 at 9:28
    
you may want to give the user the option to save his loaded random sample in case they don't like static data that looks different each time they refresh view –  fa1c0n3r Jun 18 '12 at 9:48
add comment

Technically to display n-th value you use the ranking functions like RANK, DENSE_RANK or ROW_NUMBER. Which one exactly depends, but what you describe matches best ROW_NUMBER:

with cte as (
 select row_number() over (order by Date) as rn, *
 from table)
where rn % 1000 = 0;

But you are saying that you want o do this for performance reasons, avoid going through millions of rows. Such a query had already done the damage, it read from disk all the rows and had to sort them so the performance price was already payed.

A better alternative to selecting a random sample of data is to use the TABLESAMPLE clause, see Limiting Result Sets by Using TABLESAMPLE:

select * 
from table tablesample (100 rows);

TABLESAMPLE will be way more efficient as it actually avoids reading all the data, it only samples some of the pages in the table and returns all rows in the sampled pages.

But consider that if you use TABLESAMPLE your WHERE clause are applied after the sampling. So it may be that the sample does not contain any row for the device/sensor you're interested in. This is specially true for sensor with small data.

share|improve this answer
add comment

I don't think leaving items out of the list by filtering will really change the performance hit. You're still going to scan all the rows. But maybe you can try something like this, which avoids one scan, the self-join and any meaningless aggregation:

;WITH x AS
(
  SELECT SensorValue, [Date], 
    pn = ROW_NUMBER() OVER (PARTITION BY [Date] ORDER BY [Date]),
    rn = ROW_NUMBER() OVER (ORDER BY [Date])
  FROM dbo.SensorValues
  WHERE SensorId = @sensorid
  AND DeviceId = @deviceid
  AND [Date] BETWEEN @startdate AND @stopdate
  AND Sensorvalue NOT IN (-32767,-32768)
)
SELECT SensorValue, [Date]
  FROM x
  WHERE pn = 1
  AND (rn = 1 OR rn % @resolution = 0);
share|improve this answer
    
I tried it on my data but it actually performed slower :-( –  m__ Jun 18 '12 at 6:37
    
@m__ does your table have any indexes? –  Aaron Bertrand Jun 18 '12 at 11:12
    
my table definition is in the question. I've got a clustered primary key index, nothing else. –  m__ Jun 18 '12 at 11:42
    
Can you show an actual execution plan for both queries? I suspect an index involving SensorValue might help, but it would be good to understand how many rows we're talking about, cardinality of the clustered index columns, and differences in the two plans. Not sure why this one could possibly be worse. –  Aaron Bertrand Jun 18 '12 at 11:46
    
I've added the query plans in the question and the answer (next to the actual queries). I also ran SET STATISTICS TIME ON on each query and your query executed in 8717ms while my original query took 2738ms, running on the same data set. To add to that is that your query doesn't return the same values as mine does since it looks at the row number instead of the date. I don't have the dates evenly spread throughout the data set but I do want my result to be as evenly spread as possible, so this could become an issue for me. –  m__ Jun 18 '12 at 12:39
show 6 more comments

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.