Оптимизировать перекрывающийся диапазон дат в MySQL

Я хочу найти идентификатор заказов, которые накладываются друг на друга. Каждое бронирование принадлежит 1 автомобилю и всегда имеет начало и конец .

Вот таблица:

CREATE TABLE booking (
  id int(11) NOT NULL AUTO_INCREMENT,
  car_id int(11),
  start datetime,
  end datetime,
  primary key(id)
);

CREATE INDEX car_start_end on booking (car_id, start, end);

Я хочу вернуть все заказы, которые перекрываются с другим бронированием. Отображение в паре в каждом ряду. Например: если booking1 перекрывается с booking2 и booking3 , это должно быть указано как 2 пары

+------------+----------+
|   id1      |  id2     |
+------------+----------+
| booking1   | booking2 |
| booking1   | booking3 |
+------------+----------+
  • Обратите внимание, что оба бронирования должны быть на одной машине.

  • Нет повторяющихся пар. Например, если booking1 и booking2 уже получены, не должно быть другой пары с booking2 и booking1 .

Пример дублированного бронирования (с указанием полной информации о бронировании):

+------+---------------------+---------------------+--------+-----+---------------------+---------------------+
| id1  |     start1          | end1                | car_id | id2 |       start2        |          end2       |
+------+---------------------+---------------------+--------+---------------------------+---------------------+
|  1   | 2019-01-01 12:00:00 | 2019-01-01 15:00:00 |   1    |  2  | 2019-01-01 14:00:00 | 2019-01-01 16:00:00 |
+------+---------------------+---------------------+--------+-----+---------------------+---------------------+

Мой текущий запрос sql:

SELECT b1.id, b2.id from booking b1
INNER JOIN booking b2 ON b1.car_id = b2.car_id
  -- condition for overlapping detection
  AND b1.start < b2.end
  AND b1.end > b2.start

  -- remove self overlap
  AND b1.id < b2.id;

У меня также есть индекс для:

  • (car_id, start, end)
  • id

Однако я не очень удовлетворен результатом, когда я пробую 1 миллион записей, и на это уходит целая вечность.

Anw для улучшения? Я использую MySQL 5.6 на моем местном.

скрипка

Изменить: Обновить скрипку с 1000 случайных данных бронирования.

Всего 2 ответа


Рассмотрим следующее; набор данных ок. 8000 рядов, включающих 100 автомобилей, арендованных на срок от 1 до 6 дней в течение года ...

DROP TABLE IF EXISTS bookings;

CREATE TABLE bookings
(booking_id SERIAL PRIMARY KEY
,car_id INT NOT NULL
,booking_start DATE
,booking_end DATE
);

INSERT INTO bookings VALUES
(1,1,񟭔-01-01',񟭔-01-02');

INSERT INTO bookings 
SELECT NULL,RAND()*100,񟭔-01-01'+INTERVAL (1 + RAND()*330) DAY,NULL FROM bookings;
-- REPEAT ABOVE UNTIL YOU HAVE CA. 8000 rows --

UPDATE bookings SET booking_end = booking_start + INTERVAL (1 + RAND()*5) DAY;

ALTER TABLE bookings ADD INDEX(car_id,booking_start,booking_end);

SELECT SQL_NO_CACHE DISTINCT x.* -- yes, I'm still using a very old version of MySQL
                        FROM bookings x 
                        JOIN bookings y 
                          ON y.booking_id > x.booking_id 
                         AND y.car_id = x.car_id 
                         AND y.booking_end > x.booking_start 
                         AND y.booking_start <= x.booking_end
                       WHERE x.booking_start BETWEEN 񟭔-01-01' AND 񟭕-01-01'
+------------+--------+---------------+-------------+
| booking_id | car_id | booking_start | booking_end |
+------------+--------+---------------+-------------+
|          2 |     85 | 2020-08-04    | 2020-08-05  |
|          3 |     69 | 2020-11-24    | 2020-11-27  |
|          4 |     89 | 2020-06-05    | 2020-06-10  |
|          5 |     69 | 2020-01-08    | 2020-01-12  |
...
|       8122 |     36 | 2020-04-07    | 2020-04-11  |
|       8123 |     36 | 2020-11-02    | 2020-11-05  |
+------------+--------+---------------+-------------+
4195 rows in set (1.57 sec)

1,5 секунды мне кажется разумным. Я признаю, что EXPLAIN для вышесказанного выглядит не очень хорошо, но я должен признаться, что застрял на том, как его улучшить ...

+----+-------------+-------+------+---------------------------+--------+---------+---------------+------+------------------------------+
| id | select_type | table | type | possible_keys             | key    | key_len | ref           | rows | Extra                        |
+----+-------------+-------+------+---------------------------+--------+---------+---------------+------+------------------------------+
|  1 | SIMPLE      | x     | ALL  | PRIMARY,booking_id,car_id | NULL   | NULL    | NULL          | 8192 | Using where; Using temporary |
|  1 | SIMPLE      | y     | ref  | PRIMARY,booking_id,car_id | car_id | 4       | test.x.car_id |   81 | Using where; Distinct        |
+----+-------------+-------+------+---------------------------+--------+---------+---------------+------+------------------------------+

Я только придумал следующее, которое сбрасывает информацию, другое бронирование:

SELECT b1.id from booking b1
WHERE EXISTS(SELECT * FROM booking b2
             WHERE b1.car_id = b2.car_id
             AND b1.start < b2.end
             AND b2.start < b1.end
             AND b1.id < b2.id);

Следующее даст все перекрывающиеся заказы, но не парные. Однако 3 бронирования могут пересекаться - одновременно даже.

SELECT b1.id from booking b1
WHERE EXISTS(SELECT * FROM booking b2
             WHERE b1.car_id = b2.car_id
             AND b1.start < b2.end
             AND b2.start < b1.end);

Есть идеи?

10000