Geek Answers Handbook

How to calculate distance between coordinates EFFECTIVELY in Oracle

I have a large Oracle database (720,000 aprox records), where each record has its own geographical coordinates (lat and lng), and I need to select only records that are at a certain distance from the point (within a certain radius).

Currently, I have implemented a distance function (based on haversine) that I found in the oracle forum, but since the database is a bit large, it takes about 50 seconds to choose.

Any recommendations on how to do this efficiently ?. I know there is an extension called the oracle space and the locator, but I don’t know if I can buy it or even how it works. Thank you very much in advance. Regards

+4
source share
8 answers

Use the best algorithm. Instead of calculating the actual Euclidean distance, which requires a square root calculation, make your choice at a linear distance that only requires subtraction and addition. That is, if your point is at (10, 10), and your radius is 5, select all the places with points inside the square formed by (10 +/- 5, 10 +/- 5).

This will result in a small amount of false positives in the corners of the square. Eliminate them by double checking the results in your application, calculating the correct Euclidean distance.

+5
source

Provide more detailed information about the specific format of the Lat and Long values, as well as the specific formula used to implement haversine.

There are three approaches that can speed things up. Depending on the situation, we can make at least two of them.

  • Discard as many records as possible by simply matching attribute values .
    For these records, we do not need to calculate anything at all.
    For example, convert the maximum radius requirement to the [generous but approximate] range of longitude values ​​(and possibly latitude) that will qualify

  • Use an alternative (possibly approximate) distance measurement .
    For example, it’s faster to calculate the square of the Euclidean distance based on rounded coordinates. (And, of course, compare this with the square of the desired radius)

  • Improve the application of the haversine formula .

+5
source

A few suggestions if you are not already making them ...

  • Since angles in radians are required to calculate Haversin, if you store latitude and longitude in degrees, add a couple of columns and compare radian equivalents first. More generally, pre-compute any of the values ​​in the function that you can use for the formula and save them.

  • Consider using a simpler function to eliminate points that are outside the radius by running the Haversine function only on those that are potential matches based on a simpler function. For degrees, you can use SQRT ((69.1 * dLat) 2 + (53 * dLong) 2 )) and use some fudge factor (10%). Perform Haversine calculations only at points that correspond to a coarser approximation if you need better than what provides a simpler calculation.

+4
source

If you have a license, then Oracle Spatial may be useful.

Oracle Docs - Oracle Spatial

I did not use it, but a quick scan of the documents pointed to the SDO_WITHIN_DISTANCE function

+3
source

Is the "specific distance" somewhat constant? IE are you always looking for "all points within 1 mile" or is the radius changing?

What percentage of the total number of records do you expect to receive in any given query? ten%? 0.10%?

If you always have the same radius, build a grid of squares with the same length as the radius. Assign each list of adjacent squares. Each item will know in which square it is located, from which you can get a list of all neighboring squares. Then run the calculation only at the points of these squares. This is similar to other answers that have appeared, but will be faster, because linear calculations are approximated by an indexed search, and not calculated between each point.

Even with a variable radius, you can still use the above, but you will need to calculate how many "neighbors" you need to include. This is only possible if you expect to receive a small subset of the total from any single query.

+2
source

If you do not want the distance to be too accurate, you can simply consider the earth as flat. From this discussion :

Approximate Miles:

sqrt(x * x + y * y)

where x = 69.1 * (lat2 - lat1) and y = 53.0 * (lon2 - lon1)

I recently optimized a bit for mysql (described here: www.mooreds.com/wordpress/archives/000547 [sorry, I only get 1 hyperlink per message]), but I'm not sure how many of the steps I went through apply to Oracle . Some of them (for example, using a bounding box).

+1
source 
 Approximate distance in miles: sqrt(x * x + y * y) where x = 69.1 * (lat2 - lat1) and y = 53.0 * (lon2 - lon1)

You can get a much more accurate result ... if you change the magic number 53.0 ... to also take into account the change in latitude. (As you move towards the poles, gradually become smaller.)

Does anyone have this magical magic?

0
source

First of all, Haversin is not perfect, because the Earth is not an ideal sphere - read http://www.movable-type.co.uk/scripts/latlong-vincenty.html

Second, PL / SQL is not an ideal tool for programming calculations with many lines of code that will be called many times. If you go with Java or C ++, implementing your math, you will get a huge increase in productivity. C ++ or Java code can be called from Oracle in the same way as a function.

Thirdly, people who commented that you need to cut as many points as possible with a simple rectangular box are very correct. Create an index on the longitude and latitude columns, this will help fulfill this boxing sentence.

Finally, I do not think that Oracle Spatial should be involved here - this is overkill. If you already have the created SDO_GEOMETRY column, this is one story, but if not, I would not have thought.

0
source

More articles:


All Articles