Getting around optimizer limitations with an IN() list

January 9, 2010

Author

Morgan Tocker

Insight for Developers

MySQL

Share this Post:

There was a discussion on LinkedIn one month ago that caught my eye:

Database search by “within x number of miles” radius?

Anyone out there created a zipcode database and created a “search within x numer of miles” function ?
Thankful for any tips you can throw my way..

J

A few people commented that some solutions wouldn’t scale. To understand why these sorts of geographic search queries are problematic in MySQL, it’s best to show some execution plans on dummy data:

<br><br>EXPLAIN SELECT * FROM coordinates FORCE INDEX (x_y_col_a) WHERE x BETWEEN 30 and 40 <br>AND y BETWEEN 50 AND 60 AND col_a = 'set1';<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>| id | select_type | table       | type  | possible_keys | key       | key_len | ref  | rows | Extra       |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>|  1 | SIMPLE      | coordinates | range | x_y_col_a     | x_y_col_a | 38      | NULL | 4032 | Using where |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>1 row in set (0.00 sec)<br><br>EXPLAIN SELECT * FROM coordinates FORCE INDEX (x_y_col_a) WHERE x BETWEEN 30 and 40;<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>| id | select_type | table       | type  | possible_keys | key       | key_len | ref  | rows | Extra       |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>|  1 | SIMPLE      | coordinates | range | x_y_col_a     | x_y_col_a | 3       | NULL | 4032 | Using where |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>1 row in set (0.01 sec)<br><br>SELECT count(*) FROM coordinates FORCE INDEX (x_y_col_a) WHERE x BETWEEN 30 AND 40 <br>AND y BETWEEN 50 AND 60 AND col_a = 'set1';<br>+----------+<br>| count(*) |<br>+----------+<br>|        1 |<br>+----------+<br>1 row in set (0.00 sec)<br><br>SELECT count(*) FROM coordinates FORCE INDEX (x_y_col_a) WHERE x BETWEEN 30 and 40;<br>+----------+<br>| count(*) |<br>+----------+<br>|     1664 |<br>+----------+<br>1 row in set (0.01 sec)<br><br>

Did you notice that we estimate just as many rows on the first EXPLAIN as the second one? That doesn’t make any sense! The index covers x,y and col_a and should be eliminating a lot of searching, since there is only one row which meets this condition!

The reason for this is simply a missing feature of the MySQL optimizer – and it has to do with using x BETWEEN 30 and 40 (and it’s also true with x >= 30 AND x <= 40). Using a range like this prevents us from using the rest of the index. There is a workaround, but it’s not pretty:

<br>EXPLAIN SELECT * FROM coordinates WHERE x IN<br>(30.30,30.61,31.18,31.26,31.72,32.11,32.25,32.30,32.42,32.91,33.27, <br>33.69,33.79,33.93,34.62,34.78,35.10,35.41,36.62,36.93,37.17,38.93,39.20,<br>39.56,39.84,39.87) AND y IN (59.58,56.81,57.27,54.14,56.43,51.87,54.59,<br>59.56,57.42,54.13,56.79,59.45) AND col_a = 'set1';<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>| id | select_type | table       | type  | possible_keys | key       | key_len | ref  | rows | Extra       |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>|  1 | SIMPLE      | coordinates | range | x_y_col_a     | x_y_col_a | 38      | NULL |  312 | Using where |<br>+----+-------------+-------------+-------+---------------+-----------+---------+------+------+-------------+<br>1 row in set (0.00 sec)<br>

The ugliest thing about this, is that in real life you wouldn’t know all your possible values of X or Y, and so you may end up with a very big IN list. The workaround to this, is to create steppings of the value X and Y that we can use for indexes:

<br>ALTER TABLE coordinates ADD x_floor INT NOT NULL, ADD y_floor INT NOT NULL, DROP INDEX x_y_col_a,<br>ADD INDEX x_floor_y_floor_col_a (x_floor, y_floor, col_a);<br><br>UPDATE coordinates SET x_floor = FLOOR(x), y_floor = FLOOR(y);<br><br>EXPLAIN SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) <br>AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1'G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: SIMPLE<br>        table: coordinates<br>         type: range<br>possible_keys: x_floor_y_floor_col_a<br>          key: x_floor_y_floor_col_a<br>      key_len: 40<br>          ref: NULL<br>         rows: 121<br>        Extra: Using where<br>1 row in set (0.00 sec)<br>

ALTER TABLE coordinates ADD x_floor INT NOT NULL, ADD y_floor INT NOT NULL, DROP INDEX x_y_col_a, ADD INDEX x_floor_y_floor_col_a (x_floor, y_floor, col_a); UPDATE coordinates SET x_floor = FLOOR(x), y_floor = FLOOR(y); EXPLAIN SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1'G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: coordinates type: range possible_keys: x_floor_y_floor_col_a key: x_floor_y_floor_col_a key_len: 40 ref: NULL rows: 121 Extra: Using where 1 row in set (0.00 sec)

Fantastic! The only remaining problem with this query is that it’s not quite identical to our original. In this query 60.79 will be floored to 60 (and erroneously included in our results):

<br>SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) <br>AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1';<br>+-----+-------+-------+-------+-------+---------+---------+<br>| id  | x     | y     | col_a | col_b | x_floor | y_floor |<br>+-----+-------+-------+-------+-------+---------+---------+<br>| 144 | 33.79 | 54.59 | set1  | NULL  |      33 |      54 |<br>|  38 | 39.20 | 60.79 | set1  | NULL  |      39 |      60 |<br>+-----+-------+-------+-------+-------+---------+---------+<br>2 rows in set (0.00 sec)<br>

SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1'; +-----+-------+-------+-------+-------+---------+---------+ | id | x | y | col_a | col_b | x_floor | y_floor | +-----+-------+-------+-------+-------+---------+---------+ | 144 | 33.79 | 54.59 | set1 | NULL | 33 | 54 | | 38 | 39.20 | 60.79 | set1 | NULL | 39 | 60 | +-----+-------+-------+-------+-------+---------+---------+ 2 rows in set (0.00 sec)

However, this is a quick fix by re-including the original WHERE conditions (we are just no longer using an index on them):

<br>EXPLAIN SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) <br>AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) <br>AND col_a = 'set1' AND x BETWEEN 30 and 40 AND y BETWEEN 50 AND 60G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: SIMPLE<br>        table: coordinates<br>         type: range<br>possible_keys: x_floor_y_floor_col_a<br>          key: x_floor_y_floor_col_a<br>      key_len: 40<br>          ref: NULL<br>         rows: 121<br>        Extra: Using where<br>1 row in set (0.00 sec)<br><br>SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) <br>AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) <br>AND col_a = 'set1' AND x BETWEEN 30 and 40 AND y BETWEEN 50 AND 60;<br>+-----+-------+-------+-------+-------+---------+---------+<br>| id  | x     | y     | col_a | col_b | x_floor | y_floor |<br>+-----+-------+-------+-------+-------+---------+---------+<br>| 144 | 33.79 | 54.59 | set1  | NULL  |      33 |      54 |<br>+-----+-------+-------+-------+-------+---------+---------+<br>1 row in set (0.00 sec)<br>

EXPLAIN SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1' AND x BETWEEN 30 and 40 AND y BETWEEN 50 AND 60G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: coordinates type: range possible_keys: x_floor_y_floor_col_a key: x_floor_y_floor_col_a key_len: 40 ref: NULL rows: 121 Extra: Using where 1 row in set (0.00 sec) SELECT * FROM coordinates WHERE x_floor in (30,31,32,33,34,35,36,37,38,39,40) AND y_floor in (50,51,52,53,54,55,56,57,58,59,60) AND col_a = 'set1' AND x BETWEEN 30 and 40 AND y BETWEEN 50 AND 60; +-----+-------+-------+-------+-------+---------+---------+ | id | x | y | col_a | col_b | x_floor | y_floor | +-----+-------+-------+-------+-------+---------+---------+ | 144 | 33.79 | 54.59 | set1 | NULL | 33 | 54 | +-----+-------+-------+-------+-------+---------+---------+ 1 row in set (0.00 sec)

Conclusion:

My examples were only on a small amount of data (16 000 rows) that fitted in memory, but the original query would have full table scanned if I didn’t use a FORCE INDEX hint. Add more data, and if X can’t filter out enough rows by itself this can create a real problem.

Workarounds are all very good, but they also make applications more difficult to maintain. If you really want to do these types of queries, you should give Sphinx a try.