[Solved] Optimise mysql self join overlapping date range

EverSQL Database Performance Knowledge Base

Optimise mysql self join overlapping date range

Database type:

I want to find id of the bookings that are overlapped each other. Each booking belongs to 1 car and it always has start and end.

Here is the table:

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);

I want to return all the bookings that are overlapped with another booking. Display in pair in each row. E.g: if booking1 overlapped with booking2 and booking3, it must be shown as 2 pairs

+------------+----------+
|   id1      |  id2     |
+------------+----------+
| booking1   | booking2 |
| booking1   | booking3 |
+------------+----------+

Example a duplicated booking (showing the full booking details):

+------+---------------------+---------------------+--------+-----+---------------------+---------------------+
| 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 |
+------+---------------------+---------------------+--------+-----+---------------------+---------------------+

My current sql query:

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;

I also have index for:

However I am not really satisfy with the result where I try with 1million records and it takes forever to run.

Anw to improve ? I am using mysql 5.6 on my local.

Fiddle

Edit: Update fiddle with 1000 random bookings data.

How to optimize this SQL query?

The following recommendations will help you in your SQL tuning process.
You'll find 3 sections below:

  1. Description of the steps you can take to speed up the query.
  2. The optimal indexes for this query, which you can copy and create in your database.
  3. An automatically re-written query you can copy and execute in your database.
The optimization process and recommendations:
  1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
Optimal indexes for this query:
ALTER TABLE `booking` ADD INDEX `booking_idx_car_id_end` (`car_id`,`end`);
The optimized query:
SELECT
        b1.id,
        b2.id 
    FROM
        booking b1 
    INNER JOIN
        booking b2 
            ON b1.car_id = b2.car_id 
            AND b1.start < b2.end 
            AND b1.end > b2.start 
            AND b1.id < b2.id

Related Articles



* original question posted on StackOverflow here.