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

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 2

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 3

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)

ExecutionPlans http://img812.imageshack.us/img812/457/executionplans.jpg