4

A rental system uses a booking table to store all bookings and reservations:

booking | item | startdate        | enddate
1       | 42   | 2013-10-25 16:00 | 2013-10-27 12:00
2       | 42   | 2013-10-27 14:00 | 2013-10-28 18:00
3       | 42   | 2013-10-30 09:00 | 2013-11-01 09:00
…

Let’s say a user wants to rent item 42 from 2013-10-27 12:00 until 2013-10-28 12:00 which is a period of one day. The system will tell him, that the item is not available in the given time frame, since booking no. 2 collides.

Now I want to suggest the earliest rental date and time when the selected item is available again. Of course considering the user’s requested period (1 day) beginning with the user’s desired date and time.

So in the case above, I’m looking for an SQL query that returns 2013-10-28 18:00, since the earliest date since 2013-10-27 12:00 at which item 42 will be available for 1 day, is from 2013-10-28 18:00 until 2013-10-29 18:00.

So I need to to find a gap between bookings, that is big enough to hold the user’s reservation and that is as close a possible to the desired start date.

Or in other words: I need to find the first booking for a given item, after which there’s enough free time to place the user’s booking.

Is this possible in plain SQL without having to iterate over every booking and its successor?

4
  • "as close as possible to the desired start date." Does this really mean "as soon as possible on or after the desired start date/time?"
    – O. Jones
    Commented Oct 22, 2013 at 22:14
  • @OllieJones It means as soon as possible after the desired date/time.
    – Rob
    Commented Oct 22, 2013 at 22:17
  • Booking systems usually have a defined granularity, is this the case in yours? (Do booking times have to be exact hours, or maybe allow minutes, but only in multiples of 15? 12:00, 12:15, etc?)
    – MatBailie
    Commented Oct 22, 2013 at 22:21
  • @MatBailie In my case booking times are always exact hours. So the minimum rental period is one hour going from XX:00 to YY:00.
    – Rob
    Commented Oct 22, 2013 at 22:24

6 Answers 6

3

If you can't redesign your database to use something more efficient, this will get the answer. You'll obviously want to parameterize it. It says find either the desired date, or the earliest end date where the hire interval doesn't overlap an existing booking:

Select
    min(startdate)
From (
    select
        cast('2013-10-27 12:00' as datetime) startdate
    from
        dual
    union all
    select
        enddate
    from
        booking
    where
        enddate > cast('2013-10-27 12:00' as datetime) and
        item = 42
    ) b1
Where
    not exists (
        select 
             'x'
        from
            booking b2
        where
            item = 42 and
            b1.startdate < b2.enddate and
            b2.startdate < date_add(b1.startdate, interval 24 hour)
    );

Example Fiddle

2
SELECT startfree,secondsfree FROM (
  SELECT
    @lastenddate AS startfree,
    UNIX_TIMESTAMP(startdate)-UNIX_TIMESTAMP(@lastenddate) AS secondsfree,
    @lastenddate:=enddate AS ignoreme
  FROM
    (SELECT startdate,enddate FROM bookings WHERE item=42) AS schedule,
    (SELECT @lastenddate:=NOW()) AS init
  ORDER BY startdate
) AS baseview
WHERE startfree>='2013-10-27 12:00:00'
  AND secondsfree>=86400
ORDER BY startfree
LIMIT 1
;

Some explanation: The inner query uses a variable to move the iteration into SQL, the outer query finds the needed row.

That said, I would not do this in SQL, if the DB structure is like the given. You could reduce the iteration count by using some smort WHERE in the inner query to a sane timespan, but chances are, this won't perform well.

EDIT

A caveat: I did not check, but I assume, this won't work, if there are no prior reservations in the list - this should not be a problem, as in this case your first reservation attempt (original time) will work.

EDIT

SQLfiddle

3
  • I would pre-seed @lastenddate. Something like SELECT @lastenddate:=COALESCE(MAX(enddate), '2013-10-27 12:00:00') FROM bookings WHERE startdate < '2013-10-27 12:00:00', then also use that in a WHERE clause to search only from that point onwards.
    – MatBailie
    Commented Oct 22, 2013 at 22:56
  • You already have several nested queries, I'm sure that would be fine. Just change the init and add WHERE schedule.startdate >= init.timestamp? Something like that?
    – MatBailie
    Commented Oct 22, 2013 at 22:59
  • This is what I meant with "You could reduce the iteration count by using some smart WHERE in the inner query" Commented Oct 22, 2013 at 23:00
1

Searching for overlapping date ranges generally yields poor performance in SQL. For that reason having a "Calendar" of available slots often makes things a lot more efficient.

For example, the booking 2013-10-25 16:00 => 2013-10-27 12:00 would actually be represented by 44 records, each one hour long.

The "gap" until the next booking at 2013-10-27 14:00 would then be represented by 2 records, each one hours long.

Then, each record could also have the duration (in time, or number of slots) until the next change.

 slot_start_time  | booking | item | remaining_duration
------------------+---------+------+--------------------
 2013-10-27 10:00 |    1    |  42  |      2
 2013-10-27 11:00 |    1    |  42  |      1
 2013-10-27 12:00 |  NULL   |  42  |      2
 2013-10-27 13:00 |  NULL   |  42  |      1
 2013-10-27 14:00 |    2    |  42  |     28
 2013-10-27 15:00 |    2    |  42  |     27
 ...              |  ...    | ...  |    ...
 2013-10-28 17:00 |    2    |  42  |      1
 2013-10-28 18:00 |  NULL   |  42  |     39
 2013-10-28 19:00 |  NULL   |  42  |     38

Then your query just becomes:

SELECT
  *
FROM
  slots
WHERE
  slot_start_time >= '2013-10-27 12:00'
  AND remaining_duration >= 24
  AND booking IS NULL
ORDER BY
  slot_start_time ASC
LIMIT
  1
1
  • Interesting, but that means when the new found booking-possibility is actually accepted by the customer and you need to INSERT that into the database, you need to change the remaining_duration value of all the records belonging the booking right before this new booking, correct?
    – asontu
    Commented Oct 23, 2013 at 0:20
1

OK this isn't pretty in MySQL. That's because we have to fake rownum values in subqueries.

The basic approach is to join the appropriate subset of the booking table to itself offset by one.

Here's the basic list of reservations for item 42, ordered by reservation time. We can't order by booking_id, because those aren't guaranteed to be in order of reservation time. (You're trying to insert a new reservation between two existing ones, eh?) http://sqlfiddle.com/#!2/62383/9/0

  SELECT @aserial := @aserial+1 AS rownum,
         booking.*
    FROM booking,
         (SELECT @aserial:= 0) AS q
   WHERE item = 42
   ORDER BY startdate, enddate

Here is that subset joined to itself. The trick is the a.rownum+1 = b.rownum, which joins each row to the one that comes right after it in the booking table subset. http://sqlfiddle.com/#!2/62383/8/0

SELECT a.booking_id, a.startdate asta, a.enddate aend, 
                     b.startdate bsta, b.enddate bend 
  FROM (
      SELECT @aserial := @aserial+1 AS rownum,
             booking.*
        FROM booking,
             (SELECT @aserial:= 0) AS q
       WHERE item = 42
       ORDER BY startdate, enddate
       ) AS a
  JOIN (
      SELECT @bserial := @bserial+1 AS rownum,
             booking.*
        FROM booking,
             (SELECT @bserial:= 0) AS q
       WHERE item = 42
       ORDER BY startdate, enddate
       ) AS b ON a.rownum+1 = b.rownum

Here it is again, showing each reservation (except the last one) and the number of hours following it. http://sqlfiddle.com/#!2/62383/15/0

SELECT a.booking_id, a.startdate, a.enddate, 
       TIMESTAMPDIFF(HOUR, a.enddate, b.startdate) gaphours 
  FROM (
      SELECT @aserial := @aserial+1 AS rownum,
             booking.*
        FROM booking,
             (SELECT @aserial:= 0) AS q
       WHERE item = 42
       ORDER BY startdate, enddate
       ) AS a
  JOIN (
      SELECT @bserial := @bserial+1 AS rownum,
             booking.*
        FROM booking,
             (SELECT @bserial:= 0) AS q
       WHERE item = 42
       ORDER BY startdate, enddate
       ) AS b ON a.rownum+1 = b.rownum

So, if you're looking for the starting time and ending time of the earliest twelve-hour slot you can use that result set to do this: http://sqlfiddle.com/#!2/62383/18/0

SELECT MIN(enddate) startdate, MIN(enddate) + INTERVAL 12 HOUR as enddate
   FROM (
    SELECT a.booking_id, a.startdate, a.enddate, 
           TIMESTAMPDIFF(HOUR, a.enddate, b.startdate) gaphours 
      FROM (
          SELECT @aserial := @aserial+1 AS rownum,
                 booking.*
            FROM booking,
                 (SELECT @aserial:= 0) AS q
           WHERE item = 42
           ORDER BY startdate, enddate
           ) AS a
      JOIN (
          SELECT @bserial := @bserial+1 AS rownum,
                 booking.*
            FROM booking,
                 (SELECT @bserial:= 0) AS q
           WHERE item = 42
           ORDER BY startdate, enddate
           ) AS b ON a.rownum+1 = b.rownum
    ) AS gaps
    WHERE gaphours >= 12
1

here is the query, it will return needed date, obvious condition - there should be some bookings in table, but as I see from question - you do this check:

SELECT min(enddate)
FROM
(
    select a.enddate from table4 as a
    where
        a.item=42 
    and
        DATE_ADD(a.enddate, INTERVAL 1 day) <= ifnull(
            (select min(b.startdate)
            from table4 as b where b.startdate>=a.enddate and a.item=b.item),
        a.enddate)
    and
        a.enddate>=now()
    union all
    select greatest(ifnull(max(enddate), now()),now()) from table4
) as q

you change change INTERVAL 1 day to INTERVAL ### hour

2
  • Condition s. You need a booking After as well as Before the period you're trying to book. Probably "dumb markers", a booking of 0 hours at 2000-01-01 and 2999-12-31
    – MatBailie
    Commented Oct 22, 2013 at 23:03
  • @MatBailie you're right, updated query to work properly in this case too Commented Oct 22, 2013 at 23:09
1

If I have understood your requirements correctly, you could try self-JOINing book with itself, to get the "empty" spaces, and then fit. This is MySQL only (I believe it can be adapted to others - certainly PostgreSQL):

SELECT book.*, TIMESTAMPDIFF(MINUTE, book.enddate, book.best) AS width FROM
(
    SELECT book.*, MIN(book1.startdate) AS best
    FROM book
    JOIN book AS book1 USING (item)
    WHERE item = 42 AND book1.startdate >= book.enddate
    GROUP BY book.booking
) AS book HAVING width > 110 ORDER BY startdate LIMIT 1;

In the above example, "110" is the looked-for minimum width in minutes.

Same thing, a bit less readable (for me), a SELECT removed (very fast SELECT, so little advantage):

SELECT book.*, MIN(book1.startdate) AS best
  FROM book
  JOIN book AS book1 ON (book.item = book1.item AND book.item = 42)
WHERE book1.startdate >= book.enddate
  GROUP BY book.booking
  HAVING TIMESTAMPDIFF(MINUTE, book.enddate, best) > 110
  ORDER BY startdate LIMIT 1;

In your case, one day is 1440 minutes and

SELECT book.*, MIN(book1.startdate) AS best       FROM book       JOIN book AS book1 ON (book.item = book1.item AND book.item = 42)     WHERE book1.startdate >= book.enddate       GROUP BY book.booking       HAVING TIMESTAMPDIFF(MINUTE, book.enddate, best) >= 1440       ORDER BY startdate LIMIT 1;
+---------+------+---------------------+---------------------+---------------------+
| booking | item | startdate           | enddate             | best                |
+---------+------+---------------------+---------------------+---------------------+
|       2 |   42 | 2013-10-27 14:00:00 | 2013-10-28 18:00:00 | 2013-10-30 09:00:00 |
+---------+------+---------------------+---------------------+---------------------+
1 row in set (0.00 sec)

...the period returned is 2, i.e., at the end of booking 2, and until "best" which is booking 3, a period of at least 1440 minutes is available.

An issue could be that if no periods are available, the query returns nothing -- then you need another query to fetch the farthest enddate. You can do this with an UNION and LIMIT 1 of course, but I think it would be best to only run the 'recovery' query on demand, programmatically (i.e. if empty(query) then new_query...).

Also, in the inner WHERE you should add a check for NOW() to avoid dates in the past. If expired bookings are moved to inactive storage, this could be unnecessary.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.