MySql performance find all users that are within 1 km

Question

I have mysql table, need to find all users that are within 1 km of each other Table:

Geo
----------
id(int)
location(geometry)  with spatial index
username(string)

could be solved:

1. iterate by users i ... n
2. for each select all users within specific polygon, using index
3. send msg each other

so complexity would be ~O(n) or more (depends on index), any other solutions with better performance?

Answer 1

As your data is 2D, and you know your radius, you can build a grid index for your data. Then each cell will send messages to each neighboring cell only.

Computing the cell assignment is O(n). So this should bring this task down to n * O(m * m), when m is your maximum cell occupancy.

Note that it's hard to guarantee anything here. If all your objects are within a radius of 1 km, no index will help you much. Everybody has to send to everybody else, os it will be quadratic.

Answer 2

Mysql uses R-Tree to for spatial indexes so as long as your index fits in memory you should have better than O(n) performance.