SQL Server efficiently filter rows where times are not near another table's times

Question

I have two tables and I'm looking for the rows in one table where a time column is not near any of the values in another table's time column. (Near is defined as within a minute).

Here's a code sample:

create table temp1
(
    id int identity primary key,
    value datetime not null 
)
GO

create index ix_temp1 on temp1(value, id);
GO

set nocount on
insert temp1 (value) values (DATEADD(second, rand() * 1000000, '20100101'))
GO 15000

table temp2 is set up identical:

create table temp2
(
    id int identity primary key,
    value datetime not null 
)
GO

create index ix_temp2 on temp2(value, id);
GO

set nocount on
insert temp2 (value) values (DATEADD(second, rand() * 1000000, '20100101'))
GO 15000

And here's my first crack at it (which is very inefficient)

SELECT t1.id, t1.value
FROM temp1 t1
LEFT JOIN temp2 t2
    ON t1.value between DATEADD(MINUTE, -1, t2.value) and DATEADD(MINUTE, 1, t2.value)
WHERE t2.value is null

I'm looking for ways to do this more efficiently. All solutions will be considered (new indexes, SSIS solution, CLR solutions, temp tables, cursors etc...)

Answer 1

Take off both indexes and try again

Answer 2

my first suggestion is to give this to one of the developers and have them code up an algorithm in C or C#

otherwise here is an idea. take the original data in the table and create new rows for plus and minus one minute. might be a lot of data if you're using seconds. then compare it with the data from the second table like you were doing

Answer 3

The LEFT JOIN/IS NULL isn't as efficient on SQL Server as NOT IN or NOT EXISTS when columns are not nullable - see this link for details.

That said, this:

SELECT t1.id,
       t1.value
  FROM temp1 t1
 WHERE NOT EXISTS(SELECT NULL
                    FROM temp2 t2
                   WHERE t2.value BETWEEN DATEADD(MINUTE, -1, t1.value)  
                                      AND DATEADD(MINUTE, 1, t1.value))

...still has a problem in that function use (IE: DATEADD) renders the index useless. You're altering the data of the column (temporarily, without writing it back to the table) while the index is on the original value.

I'm at a loss for options if you want the precision. Otherwise, if you alter the datetime before it's inserted into the temp table then you gain:

1. ability to straight compare: t1.value = t2.value
2. ability to use the index, assuming optimizer believes it can be of use

Answer 4

This seems to do it pretty quick:

SELECT t.id,
       t.value
FROM 
(
   SELECT t1.id, 
          t1.value, 
          (SELECT MIN(temp2.value) FROM temp2 WHERE temp2.value >= t1.value) as theNext, 
          (SELECT MAX(temp2.value) FROM temp2 WHERE temp2.value <= t1.value) as thePrev
   FROM temp1 t1
) t 
WHERE DATEDIFF(second, t.value, t.theNext) > 60 
  AND DATEDIFF(second, t.thePrev, t.value) > 60

and it doesn't require any restructure of your tables.

Make sure and use seconds for the comparison, since minutes will get rounded. This runs in less than a second on my machine using your specifications for table creation.

EDIT: Added <= and >= to theNext and thePrev calculations. This prevents a false positive where temp1.value is equal to temp2.value.

Answer 5

Answer Rewritten

For your original query changing the Join condition from

LEFT JOIN temp2 t2
 ON t1.value BETWEEN DATEADD(MINUTE, -1, t2.value) AND DATEADD(MINUTE, 1, t2.value)

to

LEFT JOIN temp2 t2
 ON t2.value BETWEEN DATEADD(MINUTE, -1, t1.value) AND DATEADD(MINUTE, 1, t1.value)

Makes a huge difference.

In both it has a scan on temp1 as the outer input to the nested loops iterator. However for the first one the condition on temp2 is not sargable so it needs to do a scan on the whole of temp2 for each row in temp1. For the second version it can do a much more reasonable range seek on the index to retrieve the matching row(s).

However the Not Exists solution as per @OMG's answer is more efficient in SQL Server

Execution Plans:

(Ignore the "Cost Relative to the Batch" for the second one - The estimated rows are way off actual so this figure is misleading)

Answer 6

I dealt with an issue similar to this by converting the DateTime value to the integer number of minutes since 1/1/2000--and writing that value into a column in my database table. So (in your case) the table would look like this:

create table temp2
(
    id int identity primary key,
    timeValue int not null
)

To compare with this table, just convert your comparison value to the integer number of minutes (I use a user-defined function for this) and compare.

DECLARE @newTime int;
SET @newTime = dbo.fnGetComparisonTime(@DateTimeValue)

Then retrieve your data:

SELECT id, timeValue 
FROM temp2
WHERE timeValue NOT BETWEEN (@newTime - 1) AND @newTime;

And the convert time to integer minutes function?

CREATE FUNCTION dbo.fnGetComparisonTime
    (
        @DateTimeValue datetime
    )
RETURNS int
AS
BEGIN
    -- Declarations
    DECLARE @Output int
    DECLARE @StartDate datetime

    SET @StartDate = '2000-01-01 00:00:00'
    SET @Output = DATEDIFF(minute, @StartDate, @ReportDateTime)    

    -- And we're done!
    RETURN @Output

END

You can play around with the SELECT statement, of course, to get the results you want. Converting DateTime values to minutes is WAY faster than handling this with dates directly.

You might ask--is there a Y2K kind of problem with this? (You will, after all, run out of minutes at 31^2 - 1 minutes.) Yes--in about 7000 years. Be sure to document your code carefully....

Answer 7

This is really fast..

;WITH Time_CTE (ID,Table1_Time,Table2_Time) AS ( SELECT t1.id, t1.value AS Table1_Time, t2.value AS Table2_Time FROM temp1 t1 INNER JOIN temp2 t2 ON YEAR(t1.value) = YEAR(t2.value) AND MONTH(t1.value) = MONTH(t2.value) AND DAY(t1.value) = DAY(t2.value) )

SELECT TCTE.id, TCTE.Table1_Time FROM Time_CTE TCTE WHERE DATEDIFF(ss,Table1_Time,Table2_Time) < 61 OR DATEDIFF(ss,Table2_Time,Table1_Time) < 61