Tuesday, January 25, 2011

Handling time-interval searches in SQL Server

Often with SQL Server you are faced with the situation of finding records (event) that overlap a search interval as illustrated below.


Often I have seen this code up as something complex that follows the above diagram:

WHERE (EndAt BETWEEN @StartDate and @EndDate AND StartAt =< @StartDate) OR (StartAt BETWEEN @StartDate and @EndDate AND EndAt >= @EndDate) OR (StartAt BETWEEN @StartDate and @EndDate AND EndAt BETWEEN @StartDate AND @EndDate) OR (StartAt =< @StartDate AND EndAt >= @EndDate)

Needless to say,  8 expressions and 3 ORs is a bit of pain…  An alternative solution is to interchanges the search and event time intervals resulting in a simpler evaluation consisting of 6 expressions and 3 ORs, some improvement.. but still not ideal

WHERE (@StartDate BETWEEN StartAt and EndAt) OR (@EndDate BETWEEN StartAt and EndAt) OR (@StartDate =< StartAt and @EndDate >= EndAt) OR (@StartDate >= StartAt and @EndDate <= EndAt)

Another technique that can work well if the search intervals are restricted to DATE instead of DateTime is to create a trigger on the table and then insert the record primary key and the integer value for every date that the event occurs on. This transforms the above into a much simpler query as shown below:


Now the search walks an index and ORs are totally avoided.  Performance has now improved by a factor of 10 to 1000. The number of indices have dropped. The size of an index is reduced (an Int index takes half the space as a DateTime).  Events Insert are typically a rare event, Search is a frequent event. Doing more work for a rare execution (trigger code)  and less work for a frequent execution is often how you can improve performance.


IMHO, often SQL Developers do not look at the net Expected Work when tuning – instead, they look at tuning on an item by item basis resulting in poor optimization.

1 comment:

  1. SELECT ... WHERE StartAt <= @EndDate AND EndAt >= @StartDate