Skip to main content
5 of 8
added 163 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 KNN queries on MySQL for example, to find the nearest point in PostgreSQL with PostGIS, I can do

SELECT *
FROM t1
CROSS JOIN t2
WHERE t1.id = 42
ORDER BY t1.geom <-> t2.geom
LIMIT 1;

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 use the k-nearest neighbors algorithm (k-NN) on a spatial index with <->. 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