How to calculate distances between coordinates EFFICIENTLY in Oracle

Question

I have a large Oracle database ( 720,000 records aprox) where each record has its own geographic coordinates (lat & lng) and i need to select just the records that are in a specific distance from a point ( inside a specific radius).

Currently i've implemented a distance function (based on haversine) that i've found in an oracle forum but because the database is a bit big it spends about 50 seconds per select.

Any recomendations on how to do thi efficiently?. I know there is an extension called oracle spatial & locator but i don´t know if i can buy it or even how does it work. Thanks a lot in advance. Best regards

Answer 1

Use a better algorithm. Instead of calculating actual Euclidian distance, which requires a square-root calculation, do your select on the linear distance that requires only subtraction and addition. I.e. if your point is at (10, 10) and your radius is 5, select all places with points inside the square formed by (10 +/- 5, 10 +/- 5).

This will catch a small number of false positives in the corners of the square. Eliminate these by double-checking the results in your application by calculating the proper Euclidian distance.

Answer 2

Do provide more details about the specific format of the Lat and Long values, as well as the specific formula used for implementing haversine.

There are three approaches which can speed up things. Depending on the situation we can do at least two of these.

1. Weed-out as many records as possible by a simple attribute value comparaison.
   For these records, we don't need to calculate anything at all.
   For example, convert the maximum radius requirement to a [generous but approximate] range of the Longitude (and possibly latitude) values which would qualify

2. Use an alternative (possibly approximative) distance measurement.
   For example, it may be faster to calculate the square of the eucldidian distance, based on a rounded-up coordinates. (And of course to compare this with the square of desired radius)

3. Improve the way the haversine formula is implemented.