Comparing two date ranges when one range has a range of starting dates.

Question

I've got the next problem up from this one: http://stackoverflow.com/questions/143552/comparing-date-ranges

The solution to comparing two ranges is the query:

SELECT * FROM periods WHERE NOT (range_start > @check_period_end OR range_end < @check_period_start)

I have the added problem. I am allowing people to enter a range of periods. To be precise they enter a duration (i.e 1 week) and a range of start dates (i.e. first 2 weeks in may) and I have to find out if there is a one week slot in the range they specified.

The naive solution is to run the above query for every day in my range. So - to check for 3 days slots in a month range I'd have to run 30 queries. Is there a more efficient way?

For bonus points - I am using Django. Is there a good solution using the Django ORM?

Edit - In an effort to simplify the question I think I've turned it into a different question! My actual problem is to find 'free gaps'. I think this invalidates some of the 'pure SQL' approaches below. I thought it would be sensible to start a new question rather than muddling this one. Others are likely to find this question useful in it's current form.

Answer 1

This is not a good candidate for SQL.

However, in Django, you are freed from many SQL constraints.

First, define a method function in your Model that does what you want -- in Python.

For example

class MyThing( models.Model ):
    startDate = models.DateField(...)
    duration = models.IntegerField(...)
    def isInside( self, aDate, aDuration ):
        return aDate >= self.startDate and aDate+aDuration <= self.startDate+self.duration

Then use your isInside() method to qualify objects. This will do some of the work in Python, where it's much simpler than horsing around in SQL.

Define a custom Manager for complex queries like this. You're going to extend the basic query_set method to include logic similar to this.

for thing in MyThing.objects.filter( startDate__gte=aDate, startDate__lte=aDate+duration ):
    if thing.isInside( aDate, duration ):
        return thing

This will use SQL to get a subset of objects with dates that should include the interval you're looking for. You can then pick the final object's interval from that list.

Answer 2

How about this.

Create a table of dates, one row per caledar date.

  SELECT * FROM CalendarDates cd  
  LEFT JOIN period p 
      ON cd.caldate > p.end_date
      OR cd.caldate + duration < p.begin_date

  WHERE p.period_id IS NULL

Answer 3

The problem is simpler than it may seem at first glance, as the user is not directly specifying an end date in their criteria.

SELECT * FROM periods p
WHERE p.range_start >= @min_start
AND   p.range_start <= @max_start
AND   DATE_ADD(p.range_start, INTERVAL @duration DAY) <= p.range_end

Answer 4

You state that the user specifies (by way of example):

• 1 week period
• start date (1 May 2009)
• end date (15 May 2009)

You then state that you need to "find out if there is a one week slot in the range they specified". I'm not 100% certain what if I understand correctly, but this is what I get from that...

• There is a table of "available periods" (described by start/end dates)
• You need to find an "avaialble period" thich over laps with the User's start/end dates
• That overlap must last for at least 1 week (or whatever duration the user requires)

If that is the case, I would work it out as follows...

• Identify the periods that overlap
• Identify the first overlap date
• Identify the last overlap date
• If those dates are 7 days apart, it's a match

My solution in SQL would be...

SELECT
   *
FROM
   periods
WHERE 
   (range_start <= @check_end)
   AND (range_end >= @check_start)
   AND DATEDIFF(
          DAY,
          CASE WHEN range_start > @check_start THEN range_start ELSE @check_start END,
          CASE WHEN range_end   < @check_end   THEN range_end   ELSE @check_end   END
          )
       >= @required_duration-1

EDIT

This assumes start and end dates being Inclusive as implied by your example logic.
(A one day period being repesented by '2009 Jan 01' -> '2009 Jan 01')

I personally prefer start date Inclusive, end date Exclusive.
(A one day period being repesented by '2009 Jan 01' -> '2009 Jan 02')

The reason being that various mathmatical comparisons and manipulations become easier, but also because it doesn't rquire the reader to assume what level of accuracy you're working at.

• If working at an hour by hour level '2009 Jan 01' -> '2009 Jan 01' represents one hour.
• But '2009 Jan 01' -> '2009 Jan 02' is always a day if you know the end date is Exclusive.

Answer 5

In some cases, it turns out to be orders of magnitude faster to create one query that gets all of the data you might need, and then use the business logic language to filter these before testing.

It made for a saving of over 100x when doing something similar to this with rolling averages in an app I was working on.