Select the minimum of a calculated distance value without sorting

Question

I have a query dealing with geo distances. The query is super fast, returning in roughly .1175 seconds on my 2.24 million row table. However, I only need the lowest distance, and using the built-in order by is way too slow.

Is there any way to just keep track of a running minimum and just give me that?

For example, if I have these results:

city a - 45km
city b - 48km
city c - 12km 

can I just have it give me the 12km, keeping in mind that all the distance values are calculated?

Here is the query that sorts:

SELECT 
    City, 
    ( 
        6371 * 
        acos(
            cos(radians(-60.61384878636903)) * 
            cos(radians(st_x(location))) * 
            cos(radians(st_y(location)) - 
            radians(112.80061386895574)) + 
            sin(radians(-60.61384878636903)) * 
            sin(radians(st_x(location))))
        ) as distance 
FROM table_name 
HAVING distance <  5 
ORDER BY distance ASC LIMIT 1 

The table structure is as follows:

id - int(12)
location - Point()
City - varchar(255) 

The problem lies in that the order by flag takes way too long to sort the data and get the lowest. Can it just keep a running minimum and then just give me that without a major performance hit?

Answer 1

If all you want is the minimum distance, and not what city is at that distance,

SELECT  MIN( 6371 * acos( cos(radians(-60.61384878636903)) * 
        cos(radians(st_x(location))) * cos(radians(st_y(location)) - 
        radians(112.80061386895574)) + sin(radians(-60.61384878636903)) * 
        sin(radians(st_x(location)))) ) AS MinDistance
    FROM  table_name

If you want the closest city, and you care about speed, then it is much more complex. The following will find the closest city faster than the MIN, but it will require revamping the schema and the code.

Is this fast enough? I even asked for the 5 nearest cities. And asked to filter out the towns with 0 population:

mysql> CALL FindNearestLL(35.15, -90.05, 10, 100, 5, 'population > 0');
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
| id      | lat    | lon     | country | ascii_city   | city         | state | population | @gcd_ct := 0 | dist                | @gcd_ct := @gcd_ct + 1 |
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
| 3023545 | 351494 | -900489 | us      | memphis      | Memphis      | TN    |     641608 |            0 | 0.07478733189367963 |                      3 |
| 2917711 | 351464 | -901844 | us      | west memphis | West Memphis | AR    |      28065 |            0 |   7.605683607627499 |                      2 |
| 2916457 | 352144 | -901964 | us      | marion       | Marion       | AR    |       9227 |            0 |     9.3994963998986 |                      1 |
| 3020923 | 352044 | -898739 | us      | bartlett     | Bartlett     | TN    |      43264 |            0 |  10.643941157860604 |                      7 |
| 2974644 | 349889 | -900125 | us      | southaven    | Southaven    | MS    |      38578 |            0 |  11.344042217329935 |                      5 |
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
5 rows in set (0.00 sec)
Query OK, 0 rows affected (0.04 sec)

mysql> SELECT COUNT(*) FROM ll_table;
+----------+
| COUNT(*) |
+----------+
|  3173958 |
+----------+
1 row in set (5.04 sec)

Details and code. It involves PARTITIONing on latitude, PRIMARY KEY(longitude...), scaling of lat/lng, bounding box, and other 'tricks'. And it handles the poles and the international date line. (All of that is too much to spell out in this answer.)

To further confirm the efficiency, I did

FLUSH STATUS;
CALL...
SHOW SESSION STATUS LIKE 'Handler%';

mysql> show session status like 'Handler%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_read_first         | 1     |
| Handler_read_key           | 3     |
| Handler_read_next          | 1307  |  -- some index, some tmp
| Handler_read_rnd           | 5     |
| Handler_read_rnd_next      | 13    |
| Handler_write              | 12    |  -- it needed a tmp
+----------------------------+-------+

That is, it touched 1,307 rows, nowhere near all of the 3,173,958 rows in the table, which is what just getting the MIN would take.

Answer 2

You can use the MIN function the following way.

If you only need the distance and saves it in a table:

SELECT MIN(distance) FROM table_name;

Or not but you also need the city name

SELECT city_name, MIN(distance_alias)
FROM(SELECT city_name, SUM(distance) distance_alias
FROM table_name
GROUP BY city_name)derived_table_alias;