Поиск свободных слотов в системе бронирования

Question

В мой вопрос о поиске диапазонов дат Я попытался упростить проблему и непреднамеренно поставил другую и более простую проблему.

Вместо того, чтобы усложнить этот вопрос редактированием, я собираюсь задать задачу, которую я на самом деле намеревался.

У меня есть две таблицы недвижимости и бронирования. Заказы имеют внешний ключ для свойств, а также дату начала и окончания.

Пользователь ищет свободные слоты и предоставляет желаемую продолжительность в днях. Они также предоставляют диапазон дат начала, которые их интересуют. Поэтому поиск будет выглядеть следующим образом: «Найдите мне все свойства, которые я хочу, чтобы 3-дневный слот начинался в любое время в мае».

Теперь я могу сделать это: 1. Запуск 31 запроса для каждого потенциального дня начала 2. Найдите все заказы в мае, соберите их в один массив из 31 логических значений, представляющих дни, и просмотрите все слоты.

Я полагаю, что (2) в большинстве случаев более эффективно. Есть ли лучшие алгоритмы? Есть ли чисто SQL-решение.

Я буду использовать Django, и мой набор данных небольшой, поэтому я, вероятно, буду в порядке с «тупым» приложением, но мне любопытно узнать, как выглядит лучший алгоритм.

Answer 1

Определения таблиц помогли бы, но здесь идет. Это должно работать для MS SQL Server, но это должно быть тривиальной задачей, чтобы преобразовать его в MySQL, как только вы поймете идею, лежащую в основе.

Таблица Calendar - это просто стандартная служебная таблица со всеми датами в ней, которую полезно иметь в вашей базе данных. Если у вас его еще нет, я предлагаю создать его и заполнить.

CREATE TABLE Calendar
(
     date        DATETIME     NOT NULL,
     is_holiday  BIT          NOT NULL,
     -- any other columns that might be relevant for your business
     CONSTRAINT PK_Calendar PRIMARY KEY CLUSTERED (date)
)

Затем вам нужно будет заполнить таблицу любыми датами, которые могут иметь значение для вашего бизнеса. Даже если вы вернетесь на 100 лет назад и вперёд на 100 лет, в таблице все равно будет менее 75 тыс. Строк, и они будут сгруппированы по дате, поэтому работать с ними нужно быстро и легко. Это значительно упрощает многие запросы на основе дат.

SELECT
     P.property_id,
     C.date
FROM
     Calendar C
JOIN Properties P ON 1=1
WHERE
     C.date BETWEEN @search_start_date AND @search_end_date AND
     NOT EXISTS
     (
          SELECT
               *
          FROM
               Bookings B
          WHERE
               B.property_id = P.property_id AND
               B.start_date <= DATEADD(dy, @slot_length, C.date) AND  -- You would use MySQLs date function
               B.end_date   >= C.date
     )

Или альтернативно:

SELECT
     P.property_id,
     C.date
FROM
     Calendar C
JOIN Properties P ON 1=1
LEFT OUTER JOIN Bookings B ON
               B.property_id = P.property_id AND
               B.start_date <= DATEADD(dy, @slot_length, C.date) AND  -- You would use MySQLs date function
               B.end_date   >= C.date
WHERE
     C.date BETWEEN @search_start_date AND @search_end_date AND
     B.booking_id IS NULL

Answer 2

Вероятно, излишне для вашего приложения - но:

Относительно простым способом улучшения поиска за счет усложнения процесса записи будет изменение таблицы бронирования, чтобы сделать ее таблицей доступности.

Добавьте в логический столбец, чтобы указать, свободен ли слот или забронирован (или еще лучше указать идентификатор клиента, который его забронировал, и используйте 0, если слот свободен).

Начните с одного свободного слота, 1 января 2009 -> 31 декабря 20 ??

Когда вы получаете бронирование, разделите свободный слот на 3 (два вкладыша и одно обновление), забронированный слот и два доступных слота.

Продолжайте делать это, и по мере того, как временные рамки будут более фрагментированными, процесс бронирования будет состоять из одного из следующих действий:

• Назначение кому-либо всего «доступного слота» (одно обновление)
• Разделение «доступного слота» на два (одно обновление и одна вставка)
• Разделение слота на 3 (как указано выше), если кто-то заказывает среднюю секцию из доступного слота.

Управлять этим не так уж сложно, и процесс поиска становится простым запросом: поиск любых доступных временных интервалов в требуемом интервале времени (booked = false или customerid = 0, в зависимости от того, как вы это делаете) где enddate - startdate> = количество дней, которое вы хотите.

Это удваивает размер таблицы бронирования / доступности и делает заказы менее простыми, но компромисс в том, что процесс поиска так же прост, как и начинается.