# Most Efficient Way to Retrieve Date Ranges

What's the most efficient way to retrieve date ranges with a table structure like this?

``````create table SomeDateTable
(
id int identity(1, 1) not null,
StartDate datetime not null,
EndDate datetime not null
)
go
``````

Say you want a range for both `StartDate` and `EndDate`. So in other words, if `StartDate` falls in between `@StartDateBegin` and `@StartDateEnd`, and `EndDate` falls in between `@EndDateBegin` and `@EndDateEnd`, then do something.

-

This is a hard problem to solve in general, but there are a couple of things we can do to help the optimizer choose a plan. This script creates a table with 10,000 rows with a known pseudo-random distribution of rows to illustrate:

``````CREATE TABLE dbo.SomeDateTable
(
Id          INTEGER IDENTITY(1, 1) PRIMARY KEY NOT NULL,
StartDate   DATETIME NOT NULL,
EndDate     DATETIME NOT NULL
);
GO
SET STATISTICS XML OFF
SET NOCOUNT ON;
DECLARE
@i  INTEGER = 1,
@s  FLOAT = RAND(20120104),
@e  FLOAT = RAND();

WHILE @i <= 10000
BEGIN
INSERT dbo.SomeDateTable
(
StartDate,
EndDate
)
VALUES
(
DATEADD(DAY, @s * 365, {d '2009-01-01'}),
DATEADD(DAY, @s * 365 + @e * 14, {d '2009-01-01'})
)

SELECT
@s = RAND(),
@e = RAND(),
@i += 1
END
``````

The first question is how to index this table. One option is to provide two indexes on the `DATETIME` columns, so the optimizer can at least choose whether to seek on `StartDate` or `EndDate`.

``````CREATE INDEX nc1 ON dbo.SomeDateTable (StartDate, EndDate)
CREATE INDEX nc2 ON dbo.SomeDateTable (EndDate, StartDate)
``````

Naturally, the inequalities on both `StartDate` and `EndDate` mean that only one column in each index can support a seek in the example query, but this is about the best we can do. We might consider making the second column in each index an `INCLUDE` rather than a key, but we might have other queries that can perform an equality seek on the leading column and an inequality seek on the second column. Also, we may get better statistics this way. Anyway...

``````DECLARE
@StartDateBegin DATETIME = {d '2009-08-01'},
@StartDateEnd DATETIME = {d '2009-10-15'},
@EndDateBegin DATETIME = {d '2009-08-05'},
@EndDateEnd DATETIME = {d '2009-10-22'}

SELECT
COUNT_BIG(*)
FROM dbo.SomeDateTable AS sdt
WHERE
sdt.StartDate BETWEEN @StartDateBegin AND @StartDateEnd
AND sdt.EndDate BETWEEN @EndDateBegin AND @EndDateEnd
``````

This query uses variables, so in general the optimizer will guess at selectivity and distribution, resulting in a guessed cardinality estimate of 81 rows. In fact, the query produces 2076 rows, a discrepancy that might be important in a more complex example.

On SQL Server 2008 SP1 CU5 or later (or R2 RTM CU1) we can take advantage of the Parameter Embedding Optimization to get better estimates, simply by adding `OPTION (RECOMPILE)` to the `SELECT` query above. This causes a compilation just before the batch executes, allowing SQL Server to 'see' the real parameter values and optimize for those. With this change, the estimate improves to 468 rows (though you do need to check the runtime plan to see this). This estimate is better than 81 rows, but still not all that close. The modelling extensions enabled by trace flag 2301 may help in some cases, but not with this query.

The problem is where the rows qualified by the two range searches overlap. One of the simplifying assumptions made in the optimizer's costing and cardinality estimation component is that predicates are independent (so if both have a selectivity of 50%, the result of applying both is assumed to qualify 50% of 50% = 25% of the rows). Where this sort of correlation is a problem, we can often work around it with multi-column and/or filtered statistics. With two ranges with unknown start and end points, this becomes impractical. This is where we sometimes have to resort to rewriting the query to a form that happens to produce a better estimate:

``````SELECT COUNT(*) FROM
(
SELECT
sdt.Id
FROM dbo.SomeDateTable AS sdt
WHERE
sdt.StartDate BETWEEN @StartDateBegin AND @StartDateEnd
INTERSECT
SELECT
sdt.Id
FROM dbo.SomeDateTable AS sdt
WHERE
sdt.EndDate BETWEEN @EndDateBegin AND @EndDateEnd
) AS intersected (id)
OPTION (RECOMPILE)
``````

This form happens to produce a runtime estimate of 2110 rows (versus 2076 actual). Unless you have TF 2301 on, in which case the more advanced modelling techniques see through the trick and produce exactly the same estimate as before: 468 rows.

One day SQL Server might gain native support for intervals. If that comes with good statistical support, developers might dread tuning query plans like this a little less.

Paul

-
Paul, great explanation. Isn't the second query with the `intersect` a bit more expensive? The latter is two index seeks and a hash match, whereas the former is just a simple index seek. I think I may be missing the point where the `intersect` query would be more advisable. – Thomas Stringer Jan 4 '12 at 14:56
Paul, from my perspective this is an excellent explanation of some of the complexities involved in such problems. Whatever we do, our estimates based on correlations might be wildly off. For example, hotel guests coming Friday night may be most likely to leave Sunday morning, expect during school breaks. We can spend a lot of effort and not gain much. – A-K Jan 4 '12 at 15:04
@Alex Granted, and in a shop where you are paid by the query, you might not have the time to worry about such stuff :) On the other hand, other people do have the time and may just be interested in the geeky details. – Paul White Jan 4 '12 at 16:05
Ah, I see. Perfect!!! Thanks! – Thomas Stringer Jan 4 '12 at 16:06
@SQL Kiwi: these things are very interesting to me, and I do have time to drill down, but I think that SQL Server optimizer is not the best tool to handle such problems, putting it mildly ;) – A-K Jan 4 '12 at 17:05

I do not know a solution that is fast for all data distributions, but if all your ranges are short, we can usually speed it up. If, for instance, ranges are shorter than one day, instead of this query:

``````SELECT  TaskId ,
StartedAt ,
FinishedAt
WHERE   '20101203' BETWEEN StartedAt AND FinishedAt
``````

we can add one more condition:

``````SELECT  TaskId ,