使用 PHP/Laravel 从 MySQL/MariaDB 获取所有 POI 的方法哪种更快

Question

如果我错了请纠正我。

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

创建一个包含两列（纬度、经度）的 table 并且它们都是浮点数并说：

这里是：

$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 公式。

将这些列（纬度、经度）合并到一个名为 point 的列中，然后逐行搜索。
将多个点（用户创建的房屋的坐标）分类为一个国家的一个部分的类别，即城市，如果查询带有 $latitude 和 $longitude 以查看最近的房屋，我将检查它们存储在哪个类别中，以便不搜索所有行，而仅搜索此查询（坐标）所属的部分。

我猜第 1 种方法很慢，因为 table 的每一行的条件，如果我使用 harvesine 公式，又会很慢。

如果我使用 ST_Distance，它似乎又很慢，因为它又需要大量的计算。

但是，如果我使用方法 3，似乎检查特定点用户的每个部分比检查所有行更快。我知道如何为每个家庭设置点，但我不知道如何在另一个 table.

中创建多个家庭位置作为一个部分

顺便说一下，MySQL 的新版本和 InnoDB 支持 MariaDB 空间索引。

我的问题：

方法 1 是否真的很慢，或者其他 ST_* 函数是否与此方法相同，以使用其中提到的那些公式一一检查所有行？哪个更快？
除了简单的条件之外，方法 2 是否还做了其他事情来使其更快？我的意思是，当使用 POINT 类型而不是 float 并使用 ST_* 函数而不是自己做时，它会做出任何改变吗？我想知道是不是算法不一样
如果方法 3 是这三种方法中最快的，我如何对点进行分类才能不搜索 table?
[=60 中的所有行=]
如何使用空间索引使其尽可能快？
如果有任何其他方法存在而我没有提到，你能告诉我如何通过 MySQL/MariaDB 中的坐标 PHP/Laravel 中的坐标来找到最近的房屋吗?

谢谢大家

Answer 1

边界框和 Haversine

在您的简短 SELECT 中，您使用的是 "bounding box" 方法，其中在地图上绘制了一个粗略的正方形。然而，它有几个缺陷。

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

有了这些有助于边界框，它显着过滤行，然后可选的 haversine 测试围绕测试的范围。

INDEX(latitude)
INDEX(longitude)

这种方法具有 "medium" 性能 -- 一个索引将与边界框一起使用，从而快速将候选者限制为东西方向（或南北）条纹环绕全球。但这可能还是很多候选人。

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

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

点和空间索引

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

通过过滤掉大部分行，调用 ST_Distance 或 ST_Distance_Sphere 的次数还算不错；不用担心功能的性能。

SPATIAL 搜索使用 R 树。我对他们在您的查询中的表现感觉不太好。

方法 3

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

我的方法

我有一些复杂的代码可以扩展到任意多点。因为你的数据集可能小到可以缓存在 RAM 中，所以它对你来说可能有点过分了。 http://mysql.rjweb.org/doc.php/latlng

对于只有一百万的家庭，上面的一对索引可能是 "good enough"，因此您不需要求助于 "my algorithm"。我的算法将只触及大约 20 行以获得所需的 5 行——无论总行数如何。

其他注意事项

如果同时存储 lat/lng 和 POINT，则 table 会很笨重；如果尝试混合边界框和 ST 函数，请记住这一点。

Answer 2

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

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

在我的数据库中 (MySQL 5.7.18) 我有以下 table:

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

数据来自Free World Cities Database，包含3173958（3.1M）行。

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

假设用户位于伦敦某处

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

并且您想从 cities table.

中找到最近的位置

一个 "trivial" 查询将是

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 秒 - 差别不大。

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

现在让我们看看如何将 空间索引 与 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 是以度数表示的，因此多边形更像是椭圆而不是圆形。但是在我的测试中，我总是得到与简单而缓慢的解决方案相同的结果。在我的生产代码中使用它之前，我会调查更多的边缘情况。

现在您需要为 application/data 找到最佳半径。如果它太小 - 你可能得不到结果，或者错过最近的点。如果它太大 - 您可能需要处理太多行。

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

@radius = 0.001: 无结果
@radius = 0.01：恰好一个位置（有点幸运）- 执行时间 ~ 0.000 秒
@radius = 0.1: 55 个位置 - 执行时间 ~ 0.000 秒
@radius = 1.0: 2183 个位置 - 执行时间 ~ 0.030 秒

使用 PHP/Laravel 从 MySQL/MariaDB 获取所有 POI 的方法哪种更快

Which approach is faster for getting all POIs from MySQL/MariaDB with PHP/Laravel

mysql

spatial

mariadb

point-of-interest

laravel