1

Table in question:

CREATE TABLE `observations` (
  `time_of_observation` datetime NOT NULL,
  `station` varchar(5) NOT NULL,
  `number` varchar(20) NOT NULL,
  `destination` varchar(100) NOT NULL,
  `type` varchar(20) NOT NULL,
  `departure_time` datetime NOT NULL,
  `owner` varchar(20) NOT NULL,
  `altered` tinyint(1) NOT NULL DEFAULT '0',
  `delay` bigint(20) NOT NULL DEFAULT '0',
  `notes` text CHARACTER SET latin1,
  `route_text` text,
  `info` text CHARACTER SET latin1,
  `delay_text` text CHARACTER SET latin1,
  KEY `uindex2` (`time_of_observation`,`departure_time`,`number`,`delay`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

With index:

+--------------+------------+----------+--------------+---------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table        | Non_unique | Key_name | Seq_in_index | Column_name         | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------------+------------+----------+--------------+---------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| observations |          1 | uindex2  |            1 | time_of_observation | A         |       58588 |     NULL | NULL   |      | BTREE      |         |               |
| observations |          1 | uindex2  |            2 | departure_time      | A         |     5507365 |     NULL | NULL   |      | BTREE      |         |               |
| observations |          1 | uindex2  |            3 | number              | A         |    11014731 |     NULL | NULL   |      | BTREE      |         |               |
| observations |          1 | uindex2  |            4 | delay               | A         |    11014731 |     NULL | NULL   |      | BTREE      |         |               |
+--------------+------------+----------+--------------+---------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

Query:

SELECT time_of_observation as last_seen_on, number, departure_time,
       departure_delay as last_known_delay
FROM observations as o1
WHERE NOT EXISTS (
  SELECT 1 
  FROM observations o2
  WHERE o1.number = o2.number
  AND o1.departure_time = o2.departure_time
  AND o1.time_of_observation < o2.time_of_observation
);`

number and departure_time uniquely identify an observed entity. Goal of this query is to find for each entity the last observation and the delay seen on this last observation.

This query is currently running for 140 hours (and has not finished) with the table containing ~11 million rows.

See EXPLAIN:

+------+--------------------+-------+-------+---------------+---------+---------+------+----------+--------------------------+
| id   | select_type        | table | type  | possible_keys | key     | key_len | ref  | rows     | Extra                    |
+------+--------------------+-------+-------+---------------+---------+---------+------+----------+--------------------------+
|    1 | PRIMARY            | o1    | index | NULL          | uindex2 | 86      | NULL | 11014731 | Using where; Using index |
|    2 | DEPENDENT SUBQUERY | o2    | index | uindex2       | uindex2 | 86      | NULL | 11014731 | Using where; Using index |
+------+--------------------+-------+-------+---------------+---------+---------+------+----------+--------------------------+

Am I doing something wrong here? Is it possible to optimize this query? Should it be this slow?

  • 1
    An index on (number, departure_time, time_of_observation) would help. Please also add all the indexes that the table has. Or better the output of SHOW CREATE TABLE observations ; – ypercubeᵀᴹ Jan 11 at 13:00
  • All indexes on the table are there in my question. I have run the command and replaced my initial creation query with the result. Only difference is the added index. I can try that index, but why would an index on (number, departure_time, time_of_observation) be better than the current index? Edit: Because of the order in my WHERE clause? Would that have such an impact? – Jim Jan 11 at 14:14
  • Specify your server version - maybe your task is solvable easily using window functions? WHERE o1.number = o1.number - misprint? – Akina Jan 11 at 17:01
1

First of all you need to get rid of the dependent subquery.
For this you could rewrite your query like this:

SELECT o.time_of_observation as last_seen_on, o.number,
       o.departure_time, o.departure_delay as last_known_delay
FROM observations as o
JOIN (  SELECT
        number,
        departure_time
        MIN(time_of_observation) AS minobstime
        FROM observations
        GROUP BY 
        number,
        departure_time
) m ON m.number = o.number
   AND m.departure_time = o.departure_time
   AND m.minobstime = o.time_of_observation;

or this:

SELECT o1.time_of_observation as last_seen_on, o1.number,
       o1.departure_time, o1.departure_delay as last_known_delay
FROM observations as o1
LEFT JOIN observations as o2 ON o1.number = o1.number
  AND o1.departure_time = o2.departure_time
  AND o1.time_of_observation < o2.time_of_observation
WHERE o2.<any column, preferably your primary key> IS NULL;

Then it would be a good idea if you had a primary key. It can be an auto_increment column, too.

The columns in the index you have are in the wrong order. time_of_observation should be the last column in the index. First should be the columns where you make an equality comparison, then the ones where you scan a range.

Create an index like (number, departure_time, time_of_observation) and try one of the two queries from above.

  • Thank you for the answer. The index you and @yper-crazyhat-cubeᵀᴹ mentioned improved all queries a bit. Concerning your first query. MIN should be MAX as I am trying to find the last observation time and not the first right? Both queries remove the dependent subquery. However the first query still use 10 million rows in both select queries. Whereas your second query only lists 1.7 million for both simple queries! I'm running the second one right now, and will update with results. – Jim Jan 11 at 15:01
  • Second query finished with correct results in 2 hours and 1 min. Thanks for the help! – Jim Jan 11 at 17:06
  • The (number, departure_time, time_of_observation) is NOT unique (at first, this index did not exist at all). So it is theoretically possible that there exists duplicates with different departure_delay value. In that case your queries will select random value. – Akina Jan 11 at 17:11
  • Very true. I know from the source of the data however that this is the case. – Jim Jan 11 at 17:19
  • See my Answer for further index improvement. – Rick James Jan 11 at 21:46
1

Maybe your server version allows

SELECT MAX(time_of_observation) as last_seen_on, 
       number, 
       departure_time, 
       FIRST_VALUE(departure_delay) 
             OVER (PARTITION BY number, departure_time 
                   ORDER BY time_of_observation DESC /* , departure_delay DESC */ ) as last_known_delay
FROM observations
GROUP BY number, departure_time

?

  • It does and this one seems promising as well. Second query in @tombom 's answer did the trick for me already, but I will give this one a try as well and report the results. – Jim Jan 11 at 17:09
  • @Jim The index mentioned by tombom and yper-crazyhat-cube needed for this query too. – Akina Jan 11 at 17:13
  • @Jim - please test this query (if you have 8.0 or 10.1); it would be interesting to see if the new OVER is well optimized. – Rick James Jan 11 at 21:45
  • I have tested it. It completed in less than 15 minutes. However, the results were not identical to the other queries. I can't see why though.. – Jim Jan 13 at 9:34
0

This is a "groupwise-max" problem. Your approach will do about 60 trillion operations!

Every InnoDB table should have an explicit PRIMARY KEY. If this is UNIQUE, then make it the PK:

(`time_of_observation`,`departure_time`,`number`,`delay`)

But, that is not the optimal order, especially for this query (even after fixed by tombom's first suggestion). It needs an index starting with (number, departure_time, time_of_observation, ...). If the above 4 columns are unique, then do

PRIMARY KEY (number, departure_time, time_of_observation, delay)

If not unique, then add an id:

id  INT UNSIGNED  AUTO_INCREMENT  NOT NULL,
...
PRIMARY KEY (number, departure_time, time_of_observation, delay, id),
INDEX(id)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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