sql - Finding free slots in a booking system

Question

In my question about searching for date ranges I tried simplifying the problem and inadvertently posed a different and simpler problem.

Rather than complicate that question with an edit I am going to ask the problem I actually intended.

I have two tables Property and Booking. Bookings have a foreign key to Properties and also start and end date.

The user is searching for free slots and supplies a desired duration in days. They also supply a range of start dates that they are interested in. Therefore a search will be along the lines of: "Find me all properties I want a 3 day slot which starts anytime in May."

Now I can do this by: 1. Running 31 queries for each potential start day 2. Finding all bookings in May, condense them into one array of 31 booleans representing days and loop through looking for slots.

I assume (2) is more efficient in most cases. Is there any better algorithms? Is there a pure SQL solution.

I will be using Django and my dataset is small so I will probably be OK with a 'dumb' approuch but I am curious to know what the best algorithm looks like.

Answer 1

Probably overkill for your application - but:

A relatively simple way of improving your searches at the expense of making the 'write' process more complicated, would be to change the Booking table to make it an 'Availability' table.

Add in a boolean column to indicate if the slot is free or booked (or better still put in the id of the customer who's booked it, and use 0 if the slot is free).

Start off with a single free slot, 1st Jan 2009 -> 31st Dec 20??

When you get a booking split the free slot into 3 (two inserts and one update), the booked slot and the two available slots.

Keep doing that and as the time frame gets more fragmented the booking process will consist of one of the following:

• Assigning an entire 'available slot' to someone (one update)
• Splitting an 'available slot' into two (one update and one insert)
• Splitting a slot into 3 (as above) if someone books the middle section out of an available slot.

That's not incredibly complicated to manage and the search process becomes a simple query: finding any slots in the required time frame that are available (booked=false or customerid=0, whichever way you go with it) where enddate - startdate >= the number of days you want.

It doubles the size of the booking/availability table, and makes bookings less simple, but the trade off is that the search process is about as easy as it gets.