I have been asked to provide functionality in our database to search for a given address based on distance from a given point.

What I have considered doing is adding longitude and latitude fields to each record and then doing a search based on whether it fits within a coordinate box (maximum & minimum values), but I am worried about performance issues. I have looked around the internet to see if there are any documented solutions for this sort of thing, but I can't find any.

Another I am considering is having a table simply for geographic coordinates, using a hybrid UTM (Universal Transverse Mercator) and longitude/latitude approach, so the table would be:
- utm
- longitude
- latitude
- entityId
The idea being that the utm value would limit the result set in which the box test would need to be done on the longitude/latitude fields.

If anyone has a better approach, please could you share it with us? If it changes anything I will be using MySQL, from Java.

Surely you can just calculate it from the longitude and latitude directly.
I searched for "distance between longitude and latitude" in Google and it showed this page which looked spot on as it shows the formulas used.

Working it out by formula will be much faster. It also means you won't have to enter a million different values to lookup in the table.

Is your geographic area so large or your precisions requirements to tight that you have to account for the curvature of the Earth?

mike: the formulas I already had, my issue is what th most optimal way of finding a match in the database. Basically imagine I have a bounding box representing the search area ( x,y to x+width,y+height ), what would the most optimal way of finding matching entries in the database be? Are there any storage optimisations that would help make the search faster? I am told that I need to plan for 3 million+ entries.

My first guess would be to pull all the entries where the x and y coordinates are within a rough range of the target - say 100 miles - then go through all the entries you've then extracted to find the one with the minimum exact distance using the formula. (EDIT) You'd probably want to store this set of coordinates in a work table. If you use the formula alone then you'll be table scanning each time.

You would want the latitude and longitude to be the initial part of the index to make it reasonably quick. You could also use a country code to narrow down the search. You could also adjust the range value up or down depending on how many initial matches you get.

The other option is to allow the user to select a city that's nearest to them on whatever form you show to them. I'd be surprised if many people knew what their latitude and longitude were (it's different for me because I live near Greenwich London which makes one of them 0). I certainly wouldn't know what my UTM coordinates were.

the moving type formulae are pretty good. I get an error of less than .03% on distance calculations, bearings are accurate enough for my purposes

the formulae handle curvature of the earth, mind you you could generate the equivalent of a lookup table (eg at lat of 20 one minute of long = x, at 30..... and so on).. that would give you your range. The potetnial problem is that your SQL will return a square rather than a range circle.. so the risk is that you will inlcude some targets which are in the corners and further away than the targets on the theoretical range circle.

If I were you I'd store the true geodetic position as latitude and longitude, as decimal degrees
I'd do a calculation which gave your range and then query the db for positions within that range.
if you want closest (geographical) position then subtract the target position for the actual position (the one you are comapring to) and order by the ABS of the difference. that should give you a closest to list/ Id then generate a true distance in your front end (and possibly reorder in the front end). you could do the calculation in SQL.. although it would be a pig to debug

the alternative to calculate the true distance between points means writing a function. theoretically you could do the calculation in SQL.. although it would be a pig to debug. if geographical precision is important then you will have to write a function or inline SQL.

.. in reality you only need to do the range calculation for the longitude as this does vary with position on the globe. mind you I think you could do an approximation, seeing as 1 degree of latitude = 60nm, which is approximately 1.1 statutory miles. at 50 degrees latitude 1 degree of longtitude is approximately 60% of 1 degree of longitude at the equator

depending on how big your search area is the curvature of the earth may not be too significant.. it will be more of a problems as your position nears the poles

Although I'd never heard of UTM 'till you mentioned it, my impression is that its an old style approximation. predating the advent of computers.. I think you will get close enough with a simple SQL query. It depends on how accurate your results 'MUST' be. I suspect the U part of the UTM may not actaully be 'UNIVERSAL' in use.

other usefull references include (well ones that have been usefull to me.

http://williams.best.vwh.net/avform.htm#Crs
http://www.geomidpoint.com/destination/calculation.html
http://cuinl.tripod.com/Tips/math9.htm
http://www.colorado.edu/geography/gc.../distance.html

It might help if you gave a bit more detail on what you hold in the database and what it is you're looking up. Are you just trying to tell a customer where the closest office is to his address or is it a bit more in depth. It may also help to say what database you're using - Oracle allows you to build indexes on formulas but I suspect the formulas mentioned would be too complex for it to use.