Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 786
Michael J Swart Avatar asked Sep 15 '10 15:09

Michael J Swart


People also ask

How do I filter specific rows in SQL?

In SQL, the SELECT statement is used to return specific columns of data from a table. Similarly, the WHERE clause is used to choose the rows of a table, and the query will return only the rows that meet the given criteria.

How do you SELECT all records from one table that do not exist in another table in SQL Server?

How to Select All Records from One Table That Do Not Exist in Another Table in SQL? We can get the records in one table that doesn't exist in another table by using NOT IN or NOT EXISTS with the subqueries including the other table in the subqueries.

How do I get the latest record using timestamp in SQL?

To get the last updated record in SQL Server: We can write trigger (which automatically fires) i.e. whenever there is a change (update) that occurs on a row, the “lastupdatedby” column value should get updated by the current timestamp.


3 Answers

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
like image 99
OMG Ponies Avatar answered Oct 17 '22 15:10

OMG Ponies


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.

like image 32
Nathan Wheeler Avatar answered Oct 17 '22 15:10

Nathan Wheeler


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

like image 41
Martin Smith Avatar answered Oct 17 '22 15:10

Martin Smith