mysql - 如何优化此存储过程？

Question

我需要一些帮助来优化这个过程：

DELIMITER $$

CREATE DEFINER=`ryan`@`%` PROCEDURE `GetCitiesInRadius`(
    cityID  numeric (15), 
    `range`  numeric (15)
)
BEGIN 
    DECLARE lat1  decimal (5,2);
    DECLARE long1  decimal (5,2);
    DECLARE rangeFactor  decimal (7,6);
    SET rangeFactor = 0.014457;
    SELECT `latitude`,`longitude` into  lat1,long1
    FROM  world_cities as wc WHERE city_id = cityID;

    SELECT 
        wc.city_id, 
        wc.accent_city as city, 
        s.state_name as state, 
        c.short_name as country,
        GetDistance(lat1, long1, wc.`latitude`, wc.`longitude`) as dist
        FROM  world_cities as wc
        left join states s on wc.state_id = s.state_id
        left join countries c on wc.country_id = c.country_id
        WHERE
        wc.`latitude` BETWEEN lat1 -(`range` * rangeFactor) AND lat1 + (`range` * rangeFactor)
        AND wc.`longitude` BETWEEN long1 - (`range` * rangeFactor) AND long1 + (`range` * rangeFactor)
        AND GetDistance(lat1, long1, wc.`latitude`, wc.`longitude`) <= `range`
        ORDER BY dist limit 6;
END

这是我对查询主要部分的解释：

+----+-------------+-------+--------+---------------+--------------+---------+--------------------------+------+----------------------------------------------+
| id | select_type | table | type   | possible_keys | key          | key_len | ref                      | rows | Extra                                        |
+----+-------------+-------+--------+---------------+--------------+---------+--------------------------+------+----------------------------------------------+
|  1 | SIMPLE      | B     | range  | idx_lat_long  | idx_lat_long | 12      | NULL                     | 7619 | Using where; Using temporary; Using filesort |
|  1 | SIMPLE      | s     | eq_ref | PRIMARY       | PRIMARY      | 4       | civilipedia.B.state_id   |    1 |                                              |
|  1 | SIMPLE      | c     | eq_ref | PRIMARY       | PRIMARY      | 1       | civilipedia.B.country_id |    1 | Using where                                  |
+----+-------------+-------+--------+---------------+--------------+---------+--------------------------+------+----------------------------------------------+
3 rows in set (0.00 sec)

以下是索引：

mysql> show indexes from world_cities;
+--------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table        | Non_unique | Key_name      | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+--------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| world_cities |          0 | PRIMARY       |            1 | city_id     | A         |     3173958 |     NULL | NULL   |      | BTREE      |         |
| world_cities |          1 | country_id    |            1 | country_id  | A         |       23510 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | city          |            1 | city        | A         |     3173958 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | accent_city   |            1 | accent_city | A         |     3173958 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | idx_pop       |            1 | population  | A         |       28854 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | idx_lat_long  |            1 | latitude    | A         |     1057986 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | idx_lat_long  |            2 | longitude   | A         |     3173958 |     NULL | NULL   | YES  | BTREE      |         |
| world_cities |          1 | accent_city_2 |            1 | accent_city | NULL      |     1586979 |     NULL | NULL   | YES  | FULLTEXT   |         |
+--------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
8 rows in set (0.01 sec)

您在查询中看到的函数我认为不会导致速度变慢，但这里是函数：

CREATE DEFINER=`ryan`@`%` FUNCTION `GetDistance`(lat1  numeric (9,6),
    lon1  numeric (9,6), 
    lat2  numeric (9,6),
    lon2  numeric (9,6)  ) RETURNS decimal(10,5)
BEGIN 
    DECLARE  x  decimal (20,10);
    DECLARE  pi  decimal (21,20); 
    SET  pi = 3.14159265358979323846; 
    SET  x = sin( lat1 * pi/180 ) * sin( lat2 * pi/180  ) + cos( 
        lat1 *pi/180 ) * cos( lat2 * pi/180 ) * cos( (lon2 * pi/180) -
        (lon1 *pi/180)
    );
    SET  x = atan( ( sqrt( 1- power( x, 2 ) ) ) / x );
    RETURN  ( 1.852 * 60.0 * ((x/pi)*180) ) / 1.609344;
END

Answer 1

据我所知，您的逻辑并没有直接错误会使这变慢，所以问题最终是您不能在此查询中使用任何索引。

MySQL 需要进行全表扫描并将 WHERE 子句的功能应用于每一行以确定它是否通过了条件。目前使用了 1 个索引：idx_lat_long.

这有点糟糕的索引，该long部分永远不会被使用，因为该lat部分是一个浮点数。但至少您设法有效地过滤掉了latitude范围之外的所有行。但这很可能..这些仍然很多。

实际上，在经度上你会得到稍微好一点的结果，因为人类只生活在地球的中间 30%。我们在水平方向上非常分散，但不是在垂直方向上。

无论如何，进一步最小化该字段的最佳方法是尝试过滤掉一般区域中的尽可能多的记录。现在它是地球上一个完整的垂直条带，试着让它成为一个边界框。

你可以天真地把地球切成 10x10 段。在最好的情况下，这将确保查询仅限于地球的 10% ;)。

但是，一旦您的边界框超出分隔线段，则只能在索引中使用第一个坐标（纬度或经度），您最终会遇到同样的问题。

所以当我想到这个问题时，我开始以不同的方式思考这个问题。相反，我将地球分成了 4 个部分（比如说，地图上的东北、西北、东南、西南）。所以这给了我这样的坐标：

• 0,0
• 0,1
• 1,0
• 1,1

我没有将 x 和 y 值放在 2 个单独的字段中，而是将其用作位字段并同时存储两者。

然后我再次划分了 4 个盒子中的每一个，这给了我们 2 组坐标。外坐标和内坐标。我仍然在同一个字段中对此进行编码，这意味着我们现在将 4 位用于我们的 8x8 坐标系。

我们能走多远？如果我们假设一个 64 位整数字段，这意味着 32 位可以用于 2 个坐标中的每一个。这为我们提供了一个 4294967295 x 4294967295 的网格系统，全部编码到一个数据库字段中。

该字段的美妙之处在于您可以对其进行索引。这有时被称为（我相信）四叉树。如果您需要在数据库中选择一个大区域，您只需计算 64 位左上角坐标（在 4294967295 x 4294967295 网格系统中）和左下角，并且可以保证该框中的任何内容也将是两个数之内。

你怎么得到这些数字。让我们偷懒，假设我们的 x 和 y 坐标的范围都在 -180 到 180 度之间。（y 坐标当然是一半，但我们很懒惰）。

首先，我们将其设为正数：

// assuming x and y are our long and lat.

var x+=180;
var y+=180;

所以现在这些最大值是 360，并且（4294967295 / 360 大约是 11930464）。

因此，要转换为我们的新网格系统，我们只需：

var x*=11930464;
var y*=11930464;

现在我们必须区分数字，我们需要将它们变成 1 个数字。x 的第 1 位，然后 y 的第 1 位，x 的第 2 位，y 的第 2 位，依此类推。

// The 'morton number' 
morton = 0
// The current bit we're interleaving
bit = 1
// The position of the bit we're interleaving
position = 0

while(bit <= latitude or bit <= longitude) {

  if (bit & latitude) morton = morton | 1 << (2*position+1)
  if (bit & longitude) morton = morton | 1 << (2*position)

  position += 1
  bit = 1 << position

}

我称最终变量为 'morton'，是 1966 年提出它的人。

所以这最终给我们留下了以下内容：

1. 对于数据库中的每一行，计算 morton 数并将其存储。
2. 每当您进行查询时，首先确定最大边界框（作为 morton 数）并对其进行过滤。

这将大大减少您需要检查的记录数量。

这是我编写的一个存储过程，它将为您进行计算：

CREATE FUNCTION getGeoMorton(lat DOUBLE, lng DOUBLE) RETURNS BIGINT UNSIGNED DETERMINISTIC 
BEGIN

  -- 11930464 is round(maximum value of a 32bit integer / 360 degrees) 

  DECLARE bit, morton, pos BIGINT UNSIGNED DEFAULT 0;  

  SET @lat = CAST((lat + 90) * 11930464 AS UNSIGNED);
  SET @lng = CAST((lng + 180) * 11930464 AS UNSIGNED);
  SET bit = 1;

  WHILE bit <= @lat || bit <= @lng DO 

    IF(bit & @lat) THEN SET morton = morton | ( 1 << (2 * pos + 1)); END IF;
    IF(bit & @lng) THEN SET morton = morton | ( 1 << (2 * pos)); END IF;

    SET pos = pos + 1;

    SET bit = 1 << pos;

  END WHILE; 

  RETURN morton;
END;

一些警告：

1. 绝对最坏的情况仍然会扫描整个表的 50%。不过，这种机会非常低，而且我已经看到大多数实际查询的性能绝对显着提高。
2. 在这种情况下，边界框假定为欧几里得空间，意思是.. 一个平面。实际上，您的边界框不是精确的正方形，当靠近两极时它们会严重扭曲。只要让盒子大一点（取决于你想要的精确度），你就可以走得很远。大多数现实世界的数据通常也不靠近两极；）。请记住，此过滤器只是一个“粗略过滤器”，可以最大限度地去除可能不需要的行。
3. 这是基于所谓的Z-Order 曲线。为了获得更好的性能，如果您喜欢冒险……您可以尝试选择希尔伯特曲线。这条曲线奇怪地旋转，这确保了在最坏的情况下，您只会扫描大约 25% 的桌子。神奇！一般来说，这也会过滤掉更多不需要的行。

这一切的来源：当我遇到同样的问题并试图创造性地找到解决方案时，我写了 3 篇关于这个主题的博文。与 MySQL 的 GEO 索引相比，我获得了更好的性能。

• http://www.rooftopsolutions.nl/blog/229
• http://www.rooftopsolutions.nl/blog/230
• http://www.rooftopsolutions.nl/blog/231