Why does adding ORDER BY makes the select much faster?

Question

First query, 900ms:

SELECT * FROM geoip.isp_ipv4 
WHERE INET_ATON(?) BETWEEN start_ip AND last_ip LIMIT 1

Second query, 0.5ms:

SELECT * FROM geoip.isp_ipv4 
WHERE INET_ATON(?) BETWEEN start_ip AND last_ip ORDER BY start_ip DESC LIMIT 1

I wonder why there is so much performance difference.

There could be only one result for a given ip, so the sorting doesn't change the returned row in any way...But why is it so faster?

It's the maxmind geoip db (1.59M rows), this is my table structure:

CREATE TABLE `isp_ipv4` (
  `start_ip` int(10) unsigned NOT NULL,
  `last_ip` int(10) unsigned NOT NULL,
  `asn` mediumint(8) unsigned DEFAULT NULL,
  `isp` varchar(100) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  `organization` varchar(100) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  `osn` varchar(100) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`start_ip`),
  KEY `last_ip` (`last_ip`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

I'm on MySQL 5.7.17, the same happens in both dev (Windows 10) and production (Ubuntu trusty)

---

The EXPLAINs are identical:

# id, select_type, table, partitions, type, possible_keys, key, key_len, ref, rows, filtered, Extra
'1', 'SIMPLE', 'isp_ipv4', NULL, 'range', 'PRIMARY,last_ip', 'PRIMARY', '4', NULL, '795214', '50.00', 'Using where'
'1', 'SIMPLE', 'isp_ipv4', NULL, 'range', 'PRIMARY,last_ip', 'PRIMARY', '4', NULL, '795214', '50.00', 'Using where'

Answer 1

What was the IP? 1.1.1.1 would do best by starting from the beginning. 255.255.255.255 would work better by starting at the end.

The EXPLAIN does not say whether the "range" was scanned ascending or descending. I don't even think EXPLAIN FORMAT=JSON SELECT ... would point this out.

So... I think your fast one had a high IP address and did start from the end due to the ORDER BY.

More discussion of the intractability of queries like this, plus a solution if the ranges are non-overlapping.