Skip to main content
8 of 8
added 19 characters in body
Evan Carroll
  • 64.7k
  • 49
  • 251
  • 496

Does MySQL or MariaDB support GIS KNN Index Queries (k-nearest neighbors)?

Can you do k-nearest neighbors algorithm (k-NN) queries on MySQL for example, to find the nearest point in PostgreSQL with PostGIS, I can run a kNN query on the spatial index with <->

SELECT ST_AsText(geom), city
FROM person.address
ORDER BY geom <-> 'POINT(-121.626 47.8315)'
FETCH FIRST 7 ROWS ONLY;

SQL Server has a similar method,

DECLARE @g geography = 'POINT(-121.626 47.8315)';

SELECT TOP(7) SpatialLocation.ToString(), City
FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);

Both PostgreSQL and SQL Server have KNN. What is the MySQL equivalent of <-> to do KNN on their spatial index?


If you don't know what KNN is, you can see a description of it here

The KNN system works by evaluating distances between bounding boxes inside the PostGIS R-Tree index.

Because the index is built using the bounding boxes of geometries, the distances between any geometries that are not points will be inexact: they will be the distances between the bounding boxes of geometries.

The kicker here is that the KNN approach,

  1. Does not require you to confine the query to a distance with a WHERE clause
  2. Does not calculate all of the distances between all of the points
  3. Can find the nearest point on the index.

This question is specifically about the method in which the job gets done. I realize I can get the same result, with substantially more work by calculating the distance from each point to every other point, then ORDERing, and LIMITing.*

Evan Carroll
  • 64.7k
  • 49
  • 251
  • 496