【官方】MariaDB Optimization and Indexes 中文版(七)

ACMUG征集原创技术文章。详情请添加 A_CMUG或者扫描文末二维码关注我们的微信公众号。有奖征稿,请发送稿件至:acmug@acmug.com。
3306现金有奖征稿说明:知识无价,劳动有偿,ACMUG特约撰稿人有奖回报计划(修订版)


作者: MariaDB官方授权资词翻译组翻译

资词翻译组,由数名数据库技术爱好者组成,旨在传播技术,帮助他人,提升自我。目前的成员有:田丽芳,强昌金,王竹峰,侯军伟,吕智超,刘启荣,周彦伟,古雷。
译事三难:信、达、雅。信者,真也,真者,不伪也;达者,至也,至者,无过无不及也;雅者,文学性也,文学性者,当雅则雅当俗则俗也。我们深知能达成此三事,绝非一日之功,亦非常人所能。然,苟利国家生死以,岂因祸福避趋之。我们还是希望竭尽所能,不遗余力,做一点微小的工作,提高姿势水平。由于能力有限,水平一般,有错误不妥之处,还请批评指正,希望能得到大家的资词。

资词翻译组获得MySQL Server团队和MariaDB官方授权,翻译相关技术文章。


Latitude/Longitude Indexing

问题

当你想要找到离你最近的10家比萨店,但是你又没办法高效的从海量数据库中找到。数据库索引所擅长的是一维空间的索引,但是在二维空间中,是比较弱的。

下面的方法你可以已经尝试过了:

  1. 在纬度上面建一个索引,在经度上面再建一个索引——但优化器只会使用其中一个。
  2. 在纬度和经度上面建一个联合索引——但是它依然很难胜任。
  3. 有时候,最终可能采取的还是全表扫描的方法——Yuck。

这个时候使用函数SQRT(…) < … ——不管使用哪个索引,都不可能解决问题。

也尝试使用 纬度 BETWEEN … AND 经度 BETWEEN… ——在使用这样的索引时,有希望能解决问题。

要达到的目标是,只关注那些“靠近”的记录,需要同时考虑两个方向,指向目标坐标lat/lng。

一个解决方案 — 首先是原理

他确实凑效,虽然不完美,但是比其它方式都要好。

在什么列上面做分区?看上去在纬度和经度上面做是一个好的主意。要知道经度在宽度上变化,从亦道处的68英里(111公里),到极地处的0,所以纬度看起来是一个更好的选择。

多少个分区合适?这并不重要,考虑下面几个问题:

  1. 90分区——每一个2度。(我并不喜欢一个表有太多的分区,90似乎太多了。)
  2. 50-100——均匀分布。(This requires code. 对于2.7M的地名, 85个分区从0.5度到极地的非常宽的分区。)
  3. 分区个数不要多于100,因为在分区实施时,效率会比较低。

如何分区?其实,MariaDB和MySQL都非常挑剔。所以FLOAT/DOUBLE被排除了。DECIMAL也被排除了,所以我们遇到一些问题(we are stuck with some kludge如何翻译)。很重要的是,我们需要将经纬度信息转换为和INT类型一样的大小,并且使用RANGE做分区。

代表性的选择

为了得到一个可以在分区中使用的数据类型,你需要给纬度和经度做“分级”处理。(这里只考虑*INTs,其它数据类型会用来做比较。)

Datatype Bytes resolution
------------------ ----- --------------------------------
Deg*100 (SMALLINT) 4 1570 m 1.0 mi Cities
DECIMAL(4,2)/(5,2) 5 1570 m 1.0 mi Cities
SMALLINT scaled 4 682 m 0.4 mi Cities
Deg*10000 (MEDIUMINT) 6 16 m 52 ft Houses/Businesses
DECIMAL(6,4)/(7,4) 7 16 m 52 ft Houses/Businesses
MEDIUMINT scaled 6 2.7 m 8.8 ft
FLOAT 8 1.7 m 5.6 ft
DECIMAL(8,6)/(9,6) 9 16cm 1/2 ft Friends in a mall
Deg*10000000 (INT) 8 16mm 5/8 in Marbles
DOUBLE 16 3.5nm ... Fleas on a dog

(按照精度排序)

上面表格的意思是:
Deg*100 (SMALLINT)——用经纬度的值,乘上100,再做ROUND操作,然后存为SMALLINT类型的值,这样对每一个维度,都会使用2个字节的空间,总共需要4字节。两点之间相隔大约1570米,但会被注册为相同的经度和纬度值。

纬度使用类型DECIMAL(4,2)存储,经度使用类型DECIMAL(5,2) 存储,这样占用2+3个字节,但是效果比不上Deg*100。

SMALLINT scaled——纬度通过(degrees / 90 32767),然后再做ROUND的运算,转换为SMALLINT SIGNED类型的值;经度通过做 (degrees / 180 32767)的运算来转换。

FLOAT 有24个重要的位,DOUBLE有53个。(他们在分区方面,是不能正常工作的,但为了完整性,还是被包括了进来。人们经常会使用DOUBLE类型,但没有意识到这完全是一个多余的类型,也不知道他占用多少空间。)

可以确信的是,你可能会做DEG1000的分表类型,或者其它“范围内”的方法,但都没有什么优势。DEG1000所占用的空间,和DEG10000是一样的,但精度比DEG10000小。

所以,从列中表遍历一遍,看看你需要多大的精度,然后找一个适合你的。然后,因为我们会使用纬度为“partition key”,所以它必须要被限制为INTs类型的。举例来说,我会使用Deg*10000 (MEDIUMINT)类型来存储。

GCDist — compute “great circle distance”

GCDist是一个可以正确的计算地球两点之间距离的FUNCTION助手。

该代码在2011年老式PC上的每次调用的基准测试时间为大约20微秒,如果你需要检查100万个点,那就需要20秒——比一个WEB应用快多了。所以,这个Procedure的一个目标,就是尽可能的减少对这个函数的调用。这个代码出现之后,有了这个Procedure,这个函数的调用次数只需要几十次,或者几百次,除非在极端条件下。

当然,你可以使用毕达哥拉斯公式,并且他在大多数应用中都可以工作。但是它不会额外的努力地去做GC。而且,GC可以跨越极点也可以跨越日界线。

为了高效,GCDist知道你所选择的精度并且对他们硬编码。我选择了“”Deg*10000””,所以该函数期望用350000来表示35度。如果你选择了一个不同的精度,你需要修改代码。

GCDist()有4个缩放之后的DOUBLE——lat1, lon1, lat2, lon2——并且返回一个被缩放的表示“度数”的数字用来代表距离。

代表性选择的表中显示52英尺的解决方案是Deg10000 和 DECIMAL(x,4),这里说明一下他是如何计算出来的:测量lat/lng (0,0) 和 (0.0001,00001) 之间的对角线:GCDist(0,0,1,1) 69.172 / 10000 * 5280 = 51.65, 其中:

  1. 69.172英里/度
  2. 每度10000个单位
  3. 5280英尺/英里

(不,这个函数不能补偿地球是一个扁圆球体,等等)

要求的表结构

将有一个表(按需添加标准化的表)。这个表必须如下所示被分区且有索引。
字段和索引

  • 以RANGE(lat)来分区
  • lat — 按比例缩小的纬度(见上文)
  • lon — 按比例缩小的经度
  • 主键(lon, lat, …) — lon必须是第一个,必须添加一个其它来使lon唯一
  • id — (可选择的)你可能需要根据你的目的来确定这些行;如果你愿意可以采用AUTO_INCREMENT
  • INDEX(id) — 如果idAUTO_INCREMENT,那这个普通索引(不是唯一索引,也不是主键索引)是必须的
  • ENGINE=InnoDB — 这样的话主键将会是’聚簇索引’
  • 其它索引 — 保持最小量(只是对于大表的一个常规性能规则)

对于这个讨论的大部分内容,lat假定为MEDIUMINT — 从-90到+90按比例缩小10000倍。对于lon从-180到+180也是这样。

主键必须如下:

  • lon开头,因为算法需要这个InnoDB会提供的’聚集’
  • 在某处包括lat,因为它是分区键
  • 含有一些使键唯一的标识(lon+lat不可能足够标识唯一性)

查找附近这个功能的存储程序会做很多类似如下的SELECT:

WHERE lat BETWEEN @my_lat - @dlat
 AND @my_lat + @dlat -- PARTITION Pruning and bounding box
 AND lon BETWEEN @my_lon - @dlon
 AND @my_lon + @dlon -- first part of PK
 AND condition -- filter out non-pizza parlors

查询计划会做如下内容:

  • 基于纬度做分区’修剪’;然后
  • 在一个分区中(是一个有效的表),使用lon做一个’聚簇’范围的扫描;然后
  • 使用’条件’去筛选出你期待的行,并复核lat,这样设计只造成非常小的硬盘块读取,这是该设计的主要目的。

注意这甚至不能叫做GCDist。当ORDER BY和LIMIT被使用时That comes in the last pass

stored procedure有一个循环。至少有两个SELECT被执行,但要通过适当的调优;通常不多于6个SELECT就会被执行。因为是通过表中的主键来查找,每个SELECT只会命中一个块,有时会更多。通过比较多个设计的性能来计算块的命中数目比较粗糙但是一种有效的方式。通过比较,一个全表稻苗可能会涉及到成千上万个块。一个简单的INDEX(lat)可能只造成命中几百个块。

过滤…一个对于寻找附近这个功能的存储过程的内容包括一个WHERE子句中的布尔表达式(‘条件’)。如果你不需要任何过滤,用‘1’来忽略它。为了避免‘SQL注入’,不要让网络用户放置任意表达式;相反,从他们提供的输入内容来构建出‘条件’,从而确保它是安全的。

算法

算法因其复杂性在stored procedure中被呈现出来。

  • 你给一块’区域’设定一个起始宽度和一些要寻找的项目
  • 它会建立一个围绕你所在地方的’区域’
  • 一个SELECT语句会被执行去查看在这块区域里有多少个项目
  • 重复以上内容,加倍这块区域的宽度,知道找到足够的项目
  • 现在,一个’最终’的SELECT被执行去获取准确的距离,将它们排序(ORDER BY)和LIMIT得到期待的数目
  • 如果跨越极点或日界线,则会使用一个更复杂的SELECT
    下一节(‘性能’)应该能把这些内容讲的更清楚因为其中加入了一些例子。

性能

因为所有的变化,获得一个有意义的基准线是很难的。所以,这里给出一些煞有介事的替代内容。
每个SELECT都被一个由纬度范围和经度范围所定义的区域所限定。(查看上面所提到的WHERE子句,或者在下面的举例代码中查看)因为经线扭曲的方式,区域中的经线会比纬线的角度更大。假设你正在查找的地方在纬度分区是3度。那是200多英里(超过300km),所以你很很能会得到一个小于这个分区范围的纬度区域。尽管如此,如果你正在一个纬度带的边缘查找,那这个区域可能会跨越两个分区。在分区修剪为一个(有时更多)分区后,查询就会被一个经度范围所约束。(记住,主键要以lon开头。)如果一个InnoDB数据块含有100行(一条唾手可得的规则),select语句会涉及到一个(或一些)块。如果这个区域跨越了两个(或更多)分区,那相同的逻辑规则会被应用到每个分区中。

所以,扫描一个区域会涉及到至少一个块;很少超过几个块。块的数目大部分依赖于数据集的大小。

这个算法的主要使用情景是当数据明显大于将要存入缓存的大小(the buffer pool)。因此,主要的目标是减小磁盘命中数目。

现在让我们看一些边缘案例,并认为块的数目仍然优于(经常性的)传统的索引技巧。

如果你在一个密集的城市里寻找星巴克怎么办?将会有很多,可能每平方英里有几百个。如果你开始猜测在100英里处,SELECTs会命中很多区块 — 没有效率。在这种情况下,‘起始距离’应该要小,比如,2英里。假设你的APP想要找到最近的10个商店。在这个例子中,你可能会在一个分区的一个InnoDB块中的2英里内找到多于10个星巴克。即使有第二个SELECT语句去完成这个查询,它将会命中相同的块。总结:一个块命中 == 低代价

假设你以一个5英里的区域开始,因为在世界上的一些密集城市里5英里半径的范围内会有超过200家星巴克,这意味着再我们的区域中可能会有300家。那涉及到了4个硬盘块,和少量的CPU去处理完这300条记录。仍然不是太坏。

现在,假设你身处太平洋上的一个远洋游轮上。在船上有一个星巴克,但是你正在查找最近的10个。如果你仍以2英里开始查找,这会花费几次迭代来找到10个位置。但是,无论如何让我们讨论一下这个问题。第一次探查会命中一个分区(可能是2个),并只找到了一个命中。第二次探查将这块区域的宽度加倍;4英里将仍然给予你一次命中 — 在同一个块中有相同的命中,它现在被缓存了,所以我们不能将它计为第二次硬盘I/O。最终这个区域会足够款以至于跨越许多的分区。每个多余的分区将会是一次新的硬盘命中并发现在这个区域中没有位点。最后,这块区域会命中智利或夏威夷或斐济并找到一些位点,也许足以停止这个迭代。因此决定硬盘命中的主要准则是分区命中数目,我们不想把世界分成太多个分区。假设,如果有40个分区,那么我刚才描述的案例中可能有20次硬盘命中。

2度的分区可能对商场或饭店的全局表比较有利。一个5英里的起始距离可能在筛选星巴克时较有利。20英里可能对一个百货公司更好。

现在,让我们讨论一下’最后’的SELECT,在其中这块区域被SQRT(2)扩展了而且它使用大的循环公式去精确的排序N个结果。这个SQRT(2)是假设N个项目都在这个区域的角落里。依此来扩大这个区域很大程度的让我们缓存了一些刚好在旧的区域外围的任意其它位点。

首先,注意这个’最后’的SELECT命中了相同的迭代中命中的块,加上一些可能命中的其他块。很难预测有多少额外的块会被命中。这儿有一个问题案例。你在一个沙漠中间,这个区域在不断的增长。最终它发现了N个位点。有一个大城市刚好位于这个迭代得到的最终区域的外围。现在这个’最终’的SELECT起作用了,它包含了大量的这个大城市的位点。’很多位点’ → ‘很多块’ → ‘很多硬盘命中’

参考代码讨论

这里有一些stored procedureFindNearest()的要点。

  • 对’我’要找的地方离得有多近作出猜测
  • 在过滤后,查看我周围的’区域’中有多少个项目
  • 如果不够,重复,加倍该区域的宽度
  • 在找到足够的项目,或者因为我们要找的’太远’而放弃后,做最后一个ORDER或LIMIT来获得所有的数据

注意这个循环很少使用lat/lng范围中的’区域’。这是粗略的,但是与分区和索引配合的很好,并避免了调用GCDist(直到最后一步)。在相同的代码中,我采用15英里作为起始值。调整这个会对程序性能有一些影响,但是影响会因使用案例的不同而不同。一个粗略的设置半径的方式是猜测约一半时间里期待的LIMIT会找到什么。(这个值在存储过程中是硬编码)

传递给FindNearest()的参数:

  • 你的纬度 — -90..90(没有缩放 — 查看存储过程中的硬编码)
  • 你的经度 — -180..180(没有缩放)
  • 起始距离 — (英里或公里) — 查看下面的讨论
  • 最大距离 — 按英里或公里 — 查看存储过程中的硬编码
  • 限制 — 最小数目的项目返回
  • 条件 — 在’AND’后面加入一些条件(上述有更多的讨论)

函数会找到最近的项目,直到能匹配到条件为止,但是在最大距离时它会放弃。(如果你身处南极,为什么要搜索那么远去找第十个必胜客呢?)

因为’缩放’、’硬编码’、’条件’、表名等,这个存储过程并不真正的通用;代码必须为每一个应用都修改。是的,我本来可以把它设计成通用的。但是太混乱了。

“_start_dist”提供了一些性能上的控制。让塔太小会导致额外的迭代;太大的话会导致更多的行被选中。如果你选择调整这个存储过程,就做到以下内容。在调用SP获取大量典型的值后”SELECT @iterations”。如果这个值经常是1,那么减小_start_dist。如果它经常是2或者更大,就增大_start_dist。

时间选择:10ms以下是’典型’的用法;对于任何数据集大小。对于异常情况会更慢(较低的最小距离、较大的最大距离、穿越日界线、不好的过滤、冷缓存等等)

结尾案例:

  • 靠使用GC距离而不是Pythagoras,距离是’正确’的甚至接近两极
  • 两极 — 即使是’最近’的也大约360度(经度),找不到它
  • 日界线 — 有一个很小的,’被包含的’,代码段用来跨越这个日界线。例如:你在经线+179度,而最近的项目位于-179度

程序返回了一个结果集,SELECT *,距离。

  • 只有符合你条件并在最大距离之内的行被返回
  • 最多限制的行被返回
  • 行会被排序,’最近’的在前面
  • ‘dist’会以英里或公里来表示(基于SP中的一个不变的硬编码)

参考代码,假设选择deg*10000和’miles’

这个版本是基于精度”Deg*10000 (MEDIUMINT)”的。

DELIMITER //

drop function if exists GCDist //
CREATE FUNCTION GCDist (
 _lat1 DOUBLE, -- Scaled Degrees north for one point
 _lon1 DOUBLE, -- Scaled Degrees west for one point
 _lat2 DOUBLE, -- other point
 _lon2 DOUBLE
 ) RETURNS DOUBLE
 DETERMINISTIC
 CONTAINS SQL -- SQL but does not read or write
 SQL SECURITY INVOKER -- No special privileges granted
-- Input is a pair of latitudes/longitudes multiplied by 10000.
-- For example, the south pole has latitude -900000.
-- Multiply output by .0069172 to get miles between the two points
-- or by .0111325 to get kilometers
BEGIN
 -- Hardcoded constant:
 DECLARE _deg2rad DOUBLE DEFAULT PI()/1800000; -- For scaled by 1e4 to MEDIUMINT
 DECLARE _rlat1 DOUBLE DEFAULT _deg2rad * _lat1;
 DECLARE _rlat2 DOUBLE DEFAULT _deg2rad * _lat2;
 -- compute as if earth's radius = 1.0
 DECLARE _rlond DOUBLE DEFAULT _deg2rad * (_lon1 - _lon2);
 DECLARE _m DOUBLE DEFAULT COS(_rlat2);
 DECLARE _x DOUBLE DEFAULT COS(_rlat1) - _m * COS(_rlond);
 DECLARE _y DOUBLE DEFAULT _m * SIN(_rlond);
 DECLARE _z DOUBLE DEFAULT SIN(_rlat1) - SIN(_rlat2);
 DECLARE _n DOUBLE DEFAULT SQRT(
 _x * _x +
 _y * _y +
 _z * _z );
 RETURN 2 * ASIN(_n / 2) / _deg2rad; -- again--scaled degrees
END;
//
DELIMITER ;

DELIMITER //
-- FindNearest (about my 6th approach)
drop procedure if exists FindNearest6 //
CREATE
PROCEDURE FindNearest (
 IN _my_lat DOUBLE, -- Latitude of me [-90..90] (not scaled)
 IN _my_lon DOUBLE, -- Longitude [-180..180]
 IN _START_dist DOUBLE, -- Starting estimate of how far to search: miles or km
 IN _max_dist DOUBLE, -- Limit how far to search: miles or km
 IN _limit INT, -- How many items to try to get
 IN _condition VARCHAR(1111) -- will be ANDed in a WHERE clause
 )
 DETERMINISTIC
BEGIN
 -- lat and lng are in degrees -90..+90 and -180..+180
 -- All computations done in Latitude degrees.
 -- Thing to tailor
 -- *Locations* -- the table
 -- Scaling of lat, lon; here using *10000 in MEDIUMINT
 -- Table name
 -- miles versus km.

-- Hardcoded constant:
 DECLARE _deg2rad DOUBLE DEFAULT PI()/1800000; -- For scaled by 1e4 to MEDIUMINT

-- Cannot use params in PREPARE, so switch to @variables:
 -- Hardcoded constant:
 SET @my_lat := _my_lat * 10000,
 @my_lon := _my_lon * 10000,
 @deg2dist := 0.0069172, -- 69.172 for miles; 111.325 for km *** (mi vs km)
 @start_deg := _start_dist / @deg2dist, -- Start with this radius first (eg, 15 miles)
 @max_deg := _max_dist / @deg2dist,
 @cutoff := @max_deg / SQRT(2), -- (slightly pessimistic)
 @dlat := @start_deg, -- note: must stay positive
 @lon2lat := COS(_deg2rad * @my_lat),
 @iterations := 0; -- just debugging

-- Loop through, expanding search
 -- Search a 'square', repeat with bigger square until find enough rows
 -- If the inital probe found _limit rows, then probably the first
 -- iteration here will find the desired data.
 -- Hardcoded table name:
 -- This is the "first SELECT":
 SET @sql = CONCAT(
 "SELECT COUNT(*) INTO @near_ct
 FROM Locations
 WHERE lat BETWEEN @my_lat - @dlat
 AND @my_lat + @dlat -- PARTITION Pruning and bounding box
 AND lon BETWEEN @my_lon - @dlon
 AND @my_lon + @dlon -- first part of PK
 AND ", _condition);
 PREPARE _sql FROM @sql;
 MainLoop: LOOP
 SET @iterations := @iterations + 1;
 -- The main probe: Search a 'square'
 SET @dlon := ABS(@dlat / @lon2lat); -- good enough for now -- note: must stay positive
 -- Hardcoded constants:
 SET @dlon := IF(ABS(@my_lat) + @dlat >= 900000, 3600001, @dlon); -- near a Pole
 EXECUTE _sql;
 IF ( @near_ct >= _limit OR -- Found enough
 @dlat >= @cutoff ) THEN -- Give up (too far)
 LEAVE MainLoop;
 END IF;
 -- Expand 'square':
 SET @dlat := LEAST(2 * @dlat, @cutoff); -- Double the radius to search
 END LOOP MainLoop;
 DEALLOCATE PREPARE _sql;

-- Out of loop because found _limit items, or going too far.
 -- Expand range by about 1.4 (but not past _max_dist),
 -- then fetch details on nearest 10.

-- Hardcoded constant:
 SET @dlat := IF( @dlat >= @max_deg OR @dlon >= 1800000,
 @max_deg,
 GCDist(ABS(@my_lat), @my_lon,
 ABS(@my_lat) - @dlat, @my_lon - @dlon) );
 -- ABS: go toward equator to find farthest corner (also avoids poles)
 -- Dateline: not a problem (see GCDist code)

-- Reach for longitude line at right angle:
 -- sin(dlon)*cos(lat) = sin(dlat)
 -- Hardcoded constant:
 SET @dlon := IFNULL(ASIN(SIN(_deg2rad * @dlat) /
 COS(_deg2rad * @my_lat))
 / _deg2rad -- precise
 , 3600001); -- must be too near a pole

-- This is the "last SELECT":
 -- Hardcoded constants:
 IF (ABS(@my_lon) + @dlon < 1800000 OR -- Usual case - not crossing dateline
 ABS(@my_lat) + @dlat < 900000) THEN -- crossing pole, so dateline not an issue
 -- Hardcoded table name:
 SET @sql = CONCAT(
 "SELECT *,
 @deg2dist * GCDist(@my_lat, @my_lon, lat, lon) AS dist
 FROM Locations
 WHERE lat BETWEEN @my_lat - @dlat
 AND @my_lat + @dlat -- PARTITION Pruning and bounding box
 AND lon BETWEEN @my_lon - @dlon
 AND @my_lon + @dlon -- first part of PK
 AND ", _condition, "
 HAVING dist <= ", _max_dist, "
 ORDER BY dist
 LIMIT ", _limit
 );
 ELSE
 -- Hardcoded constants and table name:
 -- Circle crosses dateline, do two SELECTs, one for each side
 SET @west_lon := IF(@my_lon < 0, @my_lon, @my_lon - 3600000);
 SET @east_lon := @west_lon + 3600000;
 -- One of those will be beyond +/- 180; this gets points beyond the dateline
 SET @sql = CONCAT(
 "( SELECT *,
 @deg2dist * GCDist(@my_lat, @west_lon, lat, lon) AS dist
 FROM Locations
 WHERE lat BETWEEN @my_lat - @dlat
 AND @my_lat + @dlat -- PARTITION Pruning and bounding box
 AND lon BETWEEN @west_lon - @dlon
 AND @west_lon + @dlon -- first part of PK
 AND ", _condition, "
 HAVING dist <= ", _max_dist, " )
 UNION ALL
 ( SELECT *,
 @deg2dist * GCDist(@my_lat, @east_lon, lat, lon) AS dist
 FROM Locations
 WHERE lat BETWEEN @my_lat - @dlat
 AND @my_lat + @dlat -- PARTITION Pruning and bounding box
 AND lon BETWEEN @east_lon - @dlon
 AND @east_lon + @dlon -- first part of PK
 AND ", _condition, "
 HAVING dist <= ", _max_dist, " )
 ORDER BY dist
 LIMIT ", _limit
 );
 END IF;

PREPARE _sql FROM @sql;
 EXECUTE _sql;
 DEALLOCATE PREPARE _sql;
END;
//
DELIMITER ;
<<code>>

== Sample

Find the 5 cities with non-zero population (out of 3 million) nearest to (+35.15, -90.15). Start with a 10-mile bounding box and give up at 100 miles.

<< code >>
CALL FindNearestLL(35.15, -90.05, 10, 100, 5, 'population > 0');
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
| id | lat | lon | country | ascii_city | city | state | population | @gcd_ct := 0 | dist | @gcd_ct := @gcd_ct + 1 |
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
| 3023545 | 351494 | -900489 | us | memphis | Memphis | TN | 641608 | 0 | 0.07478733189367963 | 3 |
| 2917711 | 351464 | -901844 | us | west memphis | West Memphis | AR | 28065 | 0 | 7.605683607627499 | 2 |
| 2916457 | 352144 | -901964 | us | marion | Marion | AR | 9227 | 0 | 9.3994963998986 | 1 |
| 3020923 | 352044 | -898739 | us | bartlett | Bartlett | TN | 43264 | 0 | 10.643941157860604 | 7 |
| 2974644 | 349889 | -900125 | us | southaven | Southaven | MS | 38578 | 0 | 11.344042217329935 | 5 |
+---------+--------+---------+---------+--------------+--------------+-------+------------+--------------+---------------------+------------------------+
5 rows in set (0.00 sec)
Query OK, 0 rows affected (0.04 sec)

SELECT COUNT(*) FROM ll_table;
+----------+
| COUNT(*) |
+----------+
| 3173958 |
+----------+
1 row in set (5.04 sec)

FLUSH STATUS;
CALL...
SHOW SESSION STATUS LIKE 'Handler%';

show session status like 'Handler%';
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| Handler_read_first | 1 |
| Handler_read_key | 3 |
| Handler_read_next | 1307 | -- some index, some tmp, but far less than 3 million.
| Handler_read_rnd | 5 |
| Handler_read_rnd_next | 13 |
| Handler_write | 12 | -- it needed a tmp
+----------------------------+-------+

后记

这有一个效率是GCDist函数两倍的算法Haversine,但是他有一个在计算一个点与其自身的距离时返回NULL的致命缺陷。(这是因为计算一个稍微大于1.0的数,然后取其ACOS的值导致的)。

参考

Rick James graciously allowed us to use this article in the Knowledge Base.

Rick James’ site has other useful tips, how-tos, optimizations, and debugging tips.

Original source: http://mysql.rjweb.org/doc.php/latlng


注:ACMUG收录技术文章版权属于原作者本人所有。如有疑问,请联系作者。

看完转发,手留余香。关注我们,一起进步。
关注ACMUG公众号,参与社区活动,交流开源技术,分享学习心得,一起共同进步。


发表评论