How do I speed up a SQL query that uses a BETWEEN condition?

Question

I have a table that looks like this:

ID    StartRange    EndRange
----------------------------
 1        1            3
 2        4            8
 3        9           12

And so on and so forth, so that there are over 5 million records. The last record looks something like this:

ID        StartRange    EndRange
---------------------------------
5235976   9894727374   9894727378

In other words, the StartRange and EndRange will never overlap for each record.

I need to do a query that finds the corresponding ID of a number that matches the range:

SELECT ID FROM BigTable WHERE '5000000' BETWEEN StartRange AND EndRange;

Unfortunately, this query takes several seconds to complete. I need to optimize it so that it takes the least amount of execution time. I did a little bit of research it looks like adding an index is not helpful because it would only apply if the number is exactly the StartRange or EndRange value, but not if it's between.

Does anyone have any tips or tricks I can use to bring down the execution time? Ideally I'd want it to be under 1 second if possible.

Answer 1

I had a similar problem with a table of ip address ranges and the below really did the trick for me. You'll want an index on at least StartRange.

SELECT ID
FROM BigTable
INNER JOIN
  (SELECT MAX(StartRange) AS start
   FROM BigTable
   WHERE StartRange <= @Target) AS s
ON StartRange = s.start
WHERE EndRange >= @Target;

Answer 2

Add a compound index to your table. This index must be made of the StartRange and EndRange fields:

ALTER TABLE `BigTable` ADD INDEX ( `StartRange` , `EndRange` );

Then use EXPLAIN on your query to check that the new index is used:

EXPLAIN SELECT ID FROM BigTable WHERE '5000000' BETWEEN StartRange AND EndRange;

The output shows that MySQL is unable to use the new index with this query. You may then rewrite your initial query:

SELECT ID FROM BigTable WHERE StartRange>='5000000' AND EndRange<='5000000'
                            OR EndRange>='5000000' AND StartRange<='5000000'

This new query will return the same results as your initial query. The good news are with EXPLAIN:

EXPLAIN SELECT ID FROM BigTable WHERE StartRange>='5000000' AND EndRange<='5000000'
                            OR EndRange>='5000000' AND StartRange<='5000000'

The output now shows that MySQL is able to use the new index.