如何在 Oracle 中有效地计算坐标之间的距离

How to calculate distances between coordinates EFFICIENTLY in Oracle

提问by Fgblanch

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).

我有一个大型 Oracle 数据库（大约 720,000 条记录），其中每条记录都有自己的地理坐标（纬度和经度），我只需要选择距点（特定半径内）特定距离内的记录。

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.

目前我已经实现了我在 oracle 论坛中找到的距离函数（基于半正弦），但由于数据库有点大，每次选择花费大约 50 秒。

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

关于如何有效地做到这一点的任何建议？我知道有一个名为 oracle spatial & locator 的扩展，但我不知道我是否可以购买它，甚至不知道它是如何工作的。非常感谢。此致

回答by JSB????

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).

使用更好的算法。不要计算需要平方根计算的实际欧几里得距离，而是选择只需要减法和加法的线性距离。即，如果您的点位于 (10, 10) 并且您的半径为 5，则选择所有点位于由 (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.

这将在正方形的角落捕获少量误报。通过计算适当的欧几里得距离来仔细检查应用程序中的结果来消除这些。

回答by mjv

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

请提供有关 Lat 和 Long 值的特定格式以及用于实现半正弦的特定公式的更多详细信息。

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.

1. 通过简单的属性值比较，剔除尽可能多的记录。
   对于这些记录，我们根本不需要计算任何东西。
   例如，将最大半径要求转换为符合条件的经度（可能还有纬度）值的 [宽泛但近似] 范围

2. 使用替代（可能是近似的）距离测量。
   例如，基于四舍五入的坐标计算欧几里得距离的平方可能更快。（当然，将其与所需半径的平方进行比较）

3. 改进半正弦公式的实施方式。

回答by tvanfosson

A couple of suggestions, if you aren't already doing them...

一些建议，如果你还没有这样做......

1. Since the Haversine calculation requires the angles in radians, if you are storing latitude and longitude in degrees, add a couple of columns and precompute the radian equivalents. More generally, pre-compute any of the values in the function that you can for the formula and store them.

2. Consider using a simpler function to eliminate points that are well outside the radius, running the Haversine function only on those that are potential matches based on the simpler function. For degrees you could use SQRT( (69.1*dLat)²+ (53*dLong)²) ) and use some fudge factor (10%). Run your Haversine calculation only on the points that match the cruder approximation if you need better than what the simpler calculation provides.

1. 由于Haversine计算需要以弧度为单位的角度，如果您以度为单位存储纬度和经度，请添加几列并预先计算弧度等值。更一般地，预先计算函数中您可以为公式计算的任何值并存储它们。

2. 考虑使用更简单的函数来消除远在半径之外的点，仅对基于更简单函数的潜在匹配点运行Haversine 函数。对于学位，您可以使用 SQRT( (69.1*dLat) ²+ (53*dLong) ²) ) 并使用一些软糖因子 (10%)。如果您需要比更简单的计算提供的更好的结果，则仅在与更粗略的近似值匹配的点上运行 Haversine 计算。

回答by PaulJ

If you have the license then Oracle Spatial might be of use

如果您有许可证，那么 Oracle Spatial 可能有用

Oracle Docs - Oracle Spatial

Oracle 文档 - Oracle Spatial

I've not used it but a quick scan of the docs would point to the function SDO_WITHIN_DISTANCE

我没有使用过它，但快速扫描文档会指向函数SDO_WITHIN_DISTANCE

回答by David Oneill

Is the "specific distance" somewhat constant? IE are you always searching for "all points within 1 mile" or does the radius change?

“特定距离”是否有些恒定？IE 您是否一直在搜索“1 英里内的所有点”或半径是否发生变化？

What percentage of the total records do you expect to get back in any given query? 10%? .10%?

您希望在任何给定查询中返回的总记录的百分比是多少？10%？.10%？

If you will always have the same radius, build a grid of squares with the same length as the radius. Assign each a list of neighboring squares. Each point will know what square it is in, from which you can get a list of all the neighboring squares. Then run the calculation on only the points in those squares. This is similar to the other answers that have popped up, but will be quicker because the linear calculations are approximated in an indexed lookup rather than calculated between every point.

如果您将始终具有相同的半径，请构建一个长度与半径相同的正方形网格。为每个人分配一个相邻方块的列表。每个点都会知道它在哪个方格中，您可以从中获得所有相邻方格的列表。然后仅对这些正方形中的点运行计算。这类似于弹出的其他答案，但会更快，因为线性计算是在索引查找中近似计算的，而不是在每个点之间计算。

Even with a variable radius, you can still use the above, but you'll have to calculate how many 'neighbors' to include. These are only feasible if you're expecting to get a small subset of the total from any individual query.

即使半径可变，您仍然可以使用上述方法，但您必须计算要包含多少个“邻居”。只有当您希望从任何单个查询中获得总数的一小部分时，这些才可行。

回答by mooreds

If you don't need the distance to be too accurate, you can just treat the earth as flat. From this discussion:

如果你不需要距离太精确，你可以把地球当作平面来对待。从这个讨论：

Approximate distance in miles:

sqrt(x * x + y * y)

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

以英里为单位的近似距离：

sqrt(x * x + y * y)

其中 x = 69.1 * (lat2 - lat1) 和 y = 53.0 * (lon2 - lon1)

I recently did some optimizing for mysql (outlined here: www.mooreds.com/wordpress/archives/000547 [sorry, I only get 1 hyperlink per post] ) but am not sure how many of the steps I went through are applicable to Oracle. Some definitely are (like using a bounding box if possible).

我最近对 ​​mysql 做了一些优化（在此概述：www.mooreds.com/wordpress/archives/000547 [抱歉，我每篇文章只得到 1 个超链接]）但不确定我经历的有多少步骤适用于 Oracle . 有些肯定是（如可能的话使用边界框）。

回答by Sally

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 53.0 magic number... to also take into account the change in latitude. (Get progressively smaller as you move toward the poles.)

您可以获得更准确的结果……如果您更改 53.0 幻数……还要考虑纬度的变化。（随着您向两极移动，逐渐变小。）

Does anyone have that magic-magic formula?

有没有人有那个神奇的魔法公式？

回答by DimaA6_ABC

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

首先，Haversine 并不完美，因为地球不是一个完美的球体——阅读http://www.movable-type.co.uk/scripts/latlong-vincenty.html

Second - PL/SQL is not a perfect tool to program calculations with many lines of code which will be called many times. If you go with Java or C++ implementing your math, you will give huge performance improvement. C++ or Java code can be called from Oracle just like a function.

第二 - PL/SQL 不是一个完美的工具，可以用很多行的代码来编程计算，这些代码会被多次调用。如果您使用 Java 或 C++ 来实现您的数学，您将获得巨大的性能提升。可以像函数一样从 Oracle 调用 C++ 或 Java 代码。

Third - people who commented that you need to cut out as many points as possible with simple rectangular boxing are very correct. Create an index by longitude and latitude columns, it will help to execute that boxing clause.

第三 - 评论说你需要用简单的矩形框切出尽可能多的点的人是非常正确的。通过经度和纬度列创建索引，这将有助于执行该装箱子句。

Lastly, I don't think Oracle Spatial has to be involved here - it is an overkill. If you already have it and created SDO_GEOMETRY column, this is one story, but if not - I would not consider it.

最后，我认为这里不必涉及 Oracle Spatial - 这是一种矫枉过正。如果您已经拥有它并创建了 SDO_GEOMETRY 列，这是一个故事，但如果没有 - 我不会考虑它。