5

I have a booking system in which I need to select any available room from the database. The basic setup is:

table: room
columns: id, maxGuests

table: roombooking
columns: id, startDate, endDate

table: roombooking_room:
columns: id, room_id, roombooking_id

I need to select rooms that can fit the requested guests in, or select two (or more) rooms to fit the guests in (as defined by maxGuests, obviously using the lowest/closet maxGuests first)

I could loop through my date range and use this sql:

SELECT `id`
FROM `room` 
WHERE `id` NOT IN
(
    SELECT `roombooking_room`.`room_id`
    FROM `roombooking_room`, `roombooking`
    WHERE `roombooking`.`confirmed` =1
    AND DATE(%s) BETWEEN `roombooking`.`startDate` AND `roombooking`.`endDate`
)
AND `room`.`maxGuests`>=%d

Where %$1 is the looped date and %2d is the number of guests to be booked in. But this will just return false if there are more guests than any room can take, and there must be a quicker way of doing this rather than looping with php and running the query?

This is similar to part of the sql I was thinking of: Getting Dates between a range of dates but with Mysql

Solution, based on ircmaxwell's answer:

$query = sprintf(
        "SELECT `id`, `maxGuests`
        FROM `room`
        WHERE `id` NOT IN
        (
            SELECT `roombooking_room`.`room_id`
            FROM `roombooking_room`
            JOIN `roombooking` ON `roombooking_room`.`roombooking_id` = `roombooking`.`id`
            WHERE `roombooking`.`confirmed` =1
            AND (`roomBooking`.`startDate` > DATE(%s) OR `roomBooking`.`endDate` < DATE(%s))
        )
        AND `maxGuests` <= %d ORDER BY `maxGuests` DESC",
        $endDate->toString('yyyy-MM-dd'), $startDate->toString('yyyy-MM-dd'), $noGuests);
        $result = $db->query($query);
        $result = $result->fetchAll();

        $rooms = array();
        $guests = 0;
        foreach($result as $res) {
            if($guests >= $noGuests) break;
            $guests += (int)$res['maxGuests'];
            $rooms[] = $res['id'];
        }
Improve this question
4
  • why do you have a separate roombooking_room table? shouldn't table roombooking: id, room_id, startDate, endDate be enough? Commented Nov 12, 2010 at 14:44
  • I think the SQL necessary to do what you want would, in realistic terms, be overly complex for what you are trying to achieve. What's wrong with looping and using PHP? You may also find that if you achieve the desired result with pure SQL, this solution may in fact be slower than looping with PHP. I'd be very interested in seeing the results, however, as I sometimes find myself asking a similar question (PHP vs SQL). Commented Nov 12, 2010 at 15:01
  • @Axaryday please see the comment on the answer below. It's needed because one booking period may have more than one room associated. Ie, I am staying with 10 people, one room can take 6 people, therefore i need two rooms but under the same booking Commented Nov 12, 2010 at 15:50
  • I may have misunderstood the question. I was under the impression that you wished to check a series of arbitrary dates (say, every weekend in August) rather than "between the 1st and 14th August". Apologies if this is the case. Commented Nov 12, 2010 at 15:51

3 Answers 3

Reset to default
6

Assuming that you are interested to place @Guests from @StartDate to @EndDate

SELECT DISTINCT r.id, 
FROM room r 
     LEFT JOIN roombooking_room rbr ON r.id = rbr.room_id
     LEFT JOIN roombooking ON rbr.roombooking_id = rb.id
WHERE COALESCE(@StartDate NOT BETWEEN rb.startDate AND rb.endDate, TRUE)
      AND COALESCE(@EndDate NOT BETWEEN rb.startDate AND rb.endDate, TRUE)
      AND @Guests < r.maxGuests

should give you a list of all rooms that are free and can accommodate given number of guests for the given period.

NOTES
This query works only for single rooms, if you want to look at multiple rooms you will need to apply the same criteria to a combination of rooms. For this you would need recursive queries or some helper tables. Also, COALESCE is there to take care of NULLs - if a room is not booked at all it would not have any records with dates to compare to, so it would not return completely free rooms. Date between date1 and date2 will return NULL if either date1 or date2 is null and coalesce will turn it to true (alternative is to do a UNION of completely free rooms; which might be faster).

With multiple rooms things get really interesting. Is that scenario big part of your problem? And which database are you using i.e. do you have access to recursive queries?

EDIT

As I stated multiple times before, your way of looking for a solution (greedy algorithm that looks at the largest free rooms first) is not the optimal if you want to get the best fit between required number of guests and rooms.

So, if you replace your foreach with

$bestCapacity = 0;
$bestSolution = array();

for ($i = 1; $i <= pow(2,sizeof($result))-1; $i++) {
    $solutionIdx = $i;
    $solutionGuests = 0;
    $solution = array();
    $j = 0;
    while ($solutionIdx > 0) :
        if ($solutionIdx % 2 == 1) {
            $solution[] = $result[$j]['id'];
            $solutionGuests += $result[$j]['maxGuests'];
        }
        $solutionIdx = intval($solutionIdx/2);
        $j++;
    endwhile;       
    if (($solutionGuests <= $bestCapacity || $bestCapacity == 0) && $solutionGuests >= $noGuests) {
        $bestCapacity = $solutionGuests;
        $bestSolution = $solution;
    }
}

print_r($bestSolution);
print_r($bestCapacity);

Will go through all possible combinations and find the solution that wastes the least number of spaces.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for this. It's not a must for multiple rooms - I could always hardcode the multiple room situation - but then that seems like giving up
@Ashley, the problem with multiple rooms is that you have to examine all the possible combinations of rooms to find the best solution (2^n-1). How many rooms could you typically have and how many are the same size?
For this site, only 14 rooms with between 6 and 10. But you are right, this could change for other clients and could cause problems. ircmaxwell makes a good point blow. Maybe I will go with my idea of getting the room with maxGuests and loop until there are no more guests to assign.
@Ashley, as I said before the loop will have problems finding the optimal solution. If you have n rows that might be a part of optimal solution then you have to inspect 2^n-1 combinations. This is not particularly suited for SQL (especially without recursion; is postgres an option for you?). Alternatively if you can't use recursion you could have a helper table that would list all the combinations, but even with 14 rooms (and if looking for exact optimum) you will have to inspect 2^14-1 in the worst case, which is around ~2*10^5 rows.
3

Ok, first off, the inner query you're using is a cartesian join, and will be VERY expensive. You need to specify join criteria (roombooking_room.booking_id = roombooking.id for example).

Secondly, assuming that you have a range of dates, what can we say about that? Well, let's call the start of your range rangeStartDate and rangeEndDate.

Now, what can we say about any other range of dates that does not have any form of overlap with this range? Well, the endDate must not be between be either the rangeStartDate and the rangeEndDate. Same with the startDate. And the rangeStartDate (and rangeEndDate, but we don't need to check it) cannot be between startDate and endDate...

So, assuming %1$s is rangeStartDate and %2$s is rangeEndDate, a comprehensive where clause might be:

WHERE `roomBooking`.`startDate` NOT BETWEEN %1$s AND %2s
    AND `roomBooking`.`endDate` NOT BETWEEN %1$s AND %2$$s
    AND %1s NOT BETWEEN `roomBooking`.`startDate` AND `roomBooking`.`endDate`

But, there's a simpler way of saying that. The only way for a range to be outside of another is for the start_date to be after the end_date, or the end_date be before the start_id

So, assuming %1$s is rangeStartDate and %2$s is rangeEndDate, another comprehensive where clause might be:

WHERE `roomBooking`.`startDate` > %2$s
    OR `roomBooking`.`endDate` < %1$s

So, that brings your overall query to:

SELECT `id`
FROM `room` 
WHERE `id` NOT IN
(
    SELECT `roombooking_room`.`room_id`
    FROM `roombooking_room`
    JOIN `roombooking` ON `roombooking_room`.`roombooking_id` = `roombooking`.`id`
    WHERE `roombooking`.`confirmed` =1
    AND (`roomBooking`.`startDate` > %2$s
        OR `roomBooking`.`endDate` < %1$s)
)
AND `room`.`maxGuests`>=%d

There are other ways of doing this as well, so keep looking...

Improve this answer

3 Comments

Thanks, I think this is the way forward and this will work perfectly fine for when maxGuests is less than or equal to the requested number of guests. I think I will have to run this, if it's unsuccessful then get the room with the maxGuests and minus that from the total guests and run this again. Loops with loops but I think it's the only way?
@Ashley, actually no and what you propose is not exhaustive - you might miss a good solution. Consider that you have 3 free rooms for a period, one with 10 spaces and two with 7 and you want to accommodate 14 people. With a greedy algorithm you will take up room of 10 and 7 and miss the solution of two rooms with 7 spaces.
So looping through seems like a good way. Organising rooms with their closet maxGuests (where noGuests >= maxGuests ORDER BY maxGuests limit 1) I reckon?
0 
SELECT rooms.id
FROM rooms LEFT JOIN bookings
ON booking.room_id = rooms.id
WHERE <booking overlaps date range of interest> AND <wherever else>
GROUP BY rooms.id
HAVING booking.id IS NULL

I might be miss remembering how left join works so you might need to use a slightly different condition on the having, maybe a count or a sum.

At worst, with suitable indexes, that should scan half the bookings.

Improve this answer

2 Comments

you normally don't use GROPY BY if you don't need aggregates and in the above case you are not using any - so you can kick out GROUP BY use DISTINCT on rooms.id and move HAVING to WHERE (you should move the condition to the where part even if you do have have aggregates/need group by; having is for the conditions on the aggregates and intended to be applied to the result set after the aggregates are calculated)
@Unreason: while that might work (or even, on second thought, be necessary) for the IS NULL version the exact opposite is true for the sum or count version. For them, the filter has to apply to the aggregate result thus the reason I used a HAVING rather than a WHERE clause.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.