Effectively selecting the closest (distance) record from a database

Question

I've got a database with a 40k venues and growing right now.

Assuming I'm the red dot

I want to be able to retrieve the closest record as quickly as possible.

However the distance too the next item could be anything. And there also might be 0-n matches. But do I need to load all 40000 results when I'm just looking for 1?

How can I sort the records by distance? Should it be done in MYSQL, or PHP? This calculation happens at almost every request, per user, per page, so the solution needs to be quick.

Edit Thanks for the quick and promising answers, I'll need to review these resources, and will accept/comment on answers within a few days.

Answer 1

this problem is covered in this Scribd presentation (theory + math formulas + Mysql): Geo Distance with MySQL

I hope it covers everything you need

Answer 2

The easiest solution is to simple calculate the distance for each record and sort by this value. The problem is: This is very expensive and You can't use an index for that. You can lower the costs by only looking at a subset of your records, perhaps limiting by a bounding box as some posters here suggest.

If you want a clear and fast solution, have a look at the Spatial Extensions of MySQL. These are made exactly for what you want to do. These support:

• A new Column-Type 'Point'
• A special index type optimized for distance-queries
• A distance-operator.

This howto provides some examples:

CREATE TABLE address (
  address CHAR(80) NOT NULL,
  address_loc POINT NOT NULL,
  PRIMARY KEY(address),
  SPATIAL KEY(address_loc)
);
CREATE TABLE cab (
  cab_id INT AUTO_INCREMENT NOT NULL,
  cab_driver CHAR(80) NOT NULL,
  cab_loc POINT NOT NULL,
  PRIMARY KEY(cab_id),
  SPATIAL KEY(cab_loc)
);

SELECT
  c.cab_driver,
  ROUND(GLength(LineStringFromWKB(LineString(AsBinary(c.cab_loc),
                                             AsBinary(a.address_loc)))))
    AS distance
FROM cab c, address a
WHERE a.address = 'Foobar street 110'
ORDER BY distance ASC LIMIT 1;