2

如我错了请纠正我。

用户在我的网站上创建了三种方法来获得最近的房屋：

  1. 要创建一个包含两列（纬度、经度）的表，它们都是浮动的，然后说：

这里是：

$latitude = 50;
$longitude = 60;

SELECT * FROM my_table
    WHERE (latitude  <= $latitude+10  AND latitude  >= $latitude-10)
      AND (longitude <= $longitude+10 AND longitude >= $longitude-10)

例如，这里的 10 表示 1 公里。

在这种方法中，我们还可以使用harvesine 公式。

  1. 要将这些列（纬度，经度）合并到一列名为点的 POINT 类型，然后再次一一搜索每一行。

  2. 要将多个点（用户创建的房屋的坐标）分类为一个国家（即城市）的一个部分的类别，如果查询带有 $latitude 和 $longitude 以查看最近的房屋，我将检查它们存储在哪个类别中为了不搜索所有行，而只搜索此查询（坐标）所属的部分。

正如我猜测的那样，由于表格每一行的条件，方法 1 很慢，如果我使用 harvesine 公式，它又会变慢。

如果我使用 ST_Distance ，它似乎又很慢，因为它再次有很多计算。

但是，如果我使用方法 3，检查每个部分的特定点用户似乎比检查所有行更快。我知道如何为每个家庭设置点但是我不知道如何创建多个家庭位置作为一个部分可能在另一个表中。

InnoDB 支持新版本的 MySQL 和 MariaDB 空间索引中的 BTW。

我的问题：

  1. 方法 1 真的很慢吗，或者其他 ST_* 函数是否与这种方法相同，以使用其中提到的那些公式一一检查所有行？哪个更快？

  2. 除了简单的条件之外，方法 2 是否可以使其更快？我的意思是当使用 POINT 类型而不是 float 并使用 ST_* 函数而不是自己做时，它是否会做出任何改变？我想知道算法是否不同。

  3. 如果方法 3 是这三种方法中最快的，我如何对点进行分类以避免搜索表中的所有行？

  4. 如何使用空间索引使其尽可能快？

  5. 如果存在任何其他方法并且我没有提及，您能否告诉我如何通过在 PHP/Laravel 中的 MySQL/MariaDB 中获得坐标来获得最近的房屋？

谢谢大家

4

2 回答 2

4

您使用哪个公式计算距离并不重要。更重要的是您必须阅读、处理和排序的行数。在最好的情况下，您可以在 WHERE 子句中使用条件索引来限制处理的行数。您可以尝试对您的位置进行分类 - 但这取决于您的数据的性质，如果这会运作良好。您还需要找出要使用的“类别”。更通用的解决方案是使用SPATIAL INDEX和ST_Within()函数。

现在让我们运行一些测试..

在我的数据库（MySQL 5.7.18）中，我有下表：

CREATE TABLE `cities` (
    `cityId` MEDIUMINT(9) UNSIGNED NOT NULL AUTO_INCREMENT,
    `country` CHAR(2) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `city` VARCHAR(100) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `accentCity` VARCHAR(100) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `region` CHAR(2) NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `population` INT(10) UNSIGNED NULL DEFAULT NULL,
    `latitude` DECIMAL(10,7) NOT NULL,
    `longitude` DECIMAL(10,7) NOT NULL,
    `geoPoint` POINT NOT NULL,
    PRIMARY KEY (`cityId`),
    SPATIAL INDEX `geoPoint` (`geoPoint`)
) COLLATE='utf8mb4_unicode_ci' ENGINE=InnoDB

数据来自自由世界城市数据库，包含 3173958 (3.1M) 行。

注意geoPoint是多余的，等于POINT(longitude, latitude)。

考虑到用户位于伦敦的某个地方

set @lon = 0.0;
set @lat = 51.5;

并且您想从cities表中找到最近的位置。

一个“琐碎”的查询将是

select c.cityId, c.accentCity, st_distance_sphere(c.geoPoint, point(@lon, @lat)) as dist
from cities c
order by dist
limit 1

结果是

988204 Blackwall 1085.8212159861014

执行时间：~ 4.970 秒

如果你使用不太复杂的函数ST_Distance()，你会得到相同的结果，执行时间约为 4.580 秒——差别不大。

请注意，您不需要在表中存储地理点。你可以好好利用(point(c.longitude, c.latitude)代替c.geoPoint. 令我惊讶的是，它甚至更快（约 3.6 秒ST_Distance，约 4.0 秒ST_Distance_Sphere）。geoPoint如果我根本没有专栏，它可能会更快。但这仍然无关紧要，因为您不希望用户等待，所以如果您可以做得更好，请登录以获得响应。

现在让我们看看如何将SPATIAL INDEX与ST_Within().

您需要定义一个包含最近位置的多边形。一种简单的方法是使用ST_Buffer()，它将生成一个具有 32 个点的多边形，并且几乎是一个圆*。

set @point = point(@lon, @lat);
set @radius = 0.1;
set @polygon = ST_Buffer(@point, @radius);

select c.cityId, c.accentCity, st_distance_sphere(c.geoPoint, point(@lon, @lat)) as dist
from cities c
where st_within(c.geoPoint, @polygon)
order by dist
limit 1

结果是一样的。执行时间约为 0.000 秒（这就是我的客户（HeidiSQL）所说的）。

* 请注意，@radius以度数表示，因此多边形将更像椭圆而不是圆形。但是在我的测试中，我总是得到与简单而缓慢的解决方案相同的结果。在我在生产代码中使用它之前，我会调查更多的边缘情况。

现在您需要为您的应用程序/数据找到最佳半径。如果它太小 - 你可能得不到任何结果，或者错过最近的点。如果它太大 - 您可能需要处理太多行。

这是给定测试用例的一些数字：

  • @radius = 0.001：没有结果
  • @radius = 0.01：恰好一个位置（有点幸运） - 执行时间 ~ 0.000 秒
  • @radius = 0.1：55 个位置 - 执行时间 ~ 0.000 秒
  • @radius = 1.0：2183 个位置 - 执行时间 ~ 0.030 秒
于 2018-07-22T20:51:41.607 回答
1

边界框和半正弦

在您的简介SELECT中，您使用的是“边界框”方法，其中在地图上绘制了一个粗略的正方形。然而，它有几个缺陷。

  • 50 和 60 大概是度数；你说10是公里。您不能将它们混合在一起而不转换其中一种。
  • 经度比纬度短；需要一个cos()来解决这个问题。

拥有这些有助于边界框，它显着过滤行，然后可选的半正弦测试使测试范围更广。

INDEX(latitude)
INDEX(longitude)

这种方法具有“中等”性能——其中一个索引将与边界框一起使用，从而快速将候选对象限制在全球范围内的东西（或南北）条纹。但这可能仍然是很多候选人。

通过过滤掉大部分行，Haversine 调用的数量还不错；不用担心函数的性能。

如果您有 100 万个房屋，则包含 5 个房屋（加上一些未通过半正弦检查的房屋）的最终边界框可能会涉及数千行——因为只使用了两个索引之一。这仍然比获取所有百万行并使用距离函数检查每一行要好得多。

POINT 和 SPATIAL 索引

切换到POINT需要切换到SPATIAL索引。在这种模式下，ST_Distance_Sphere()可用而不是haversine。（注意：该功能仅存在于最近的版本中。）

通过过滤掉大部分行，对ST_Distanceor的调用次数ST_Distance_Sphere并不算太差；不用担心函数的性能。

SPATIAL搜索使用 R-Trees。我对他们在您的查询中的表现没有很好的感觉。

方法 3

通过从另一个点分类开始，您会增加复杂性。您还需要检查相邻区域以查看附近是否有点。如果没有更多细节，我无法判断相对表现。

我的方法

我有一些复杂的代码可以扩展到任意多个点。由于您的数据集可能足够小，可以缓存在 RAM 中，因此对您来说可能有点过头了。 http://mysql.rjweb.org/doc.php/latlng

对于只有一百万个家庭，上面的索引对可能“足够好”，所以你不需要求助于“我的算法”。我的算法将只触及大约 20 行以获得所需的 5 行——无论总行数如何。

其他注意事项

如果你同时存储 lat/lng 和POINT，表格会很庞大；如果尝试混合边界框和ST功能，请记住这一点。

于 2018-07-20T00:58:14.967 回答