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值放在两个单独的字段中，而是将其用作位字段并一次存储了两者。

然后，我将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的第一位，然后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

}

我将最终变量称为“莫顿”，即1966年提出该变量的那个人。

因此，这最终使我们有了以下内容：


对于数据库中的每一行，计算莫顿数并将其存储。
无论何时进行查询，都首先要确定最大边界框（作为莫顿数）并对其进行过滤。


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

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

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;

一些警告：


绝对最坏的情况仍然会扫描整个表的50％。不过，这种机会非常少，而且我已经看到大多数现实世界查询的性能绝对提高。
在这种情况下，边界框假定为 Eucllidean space，即..平面。实际上，您的边界框不是精确的正方形，并且在靠近两极时会严重扭曲。通过将盒子做得更大一些（取决于您想要的精确度），您可以走得很远。大多数现实世界中的数据通常也不是两极；）。请记住，此过滤器只是一个“粗糙的过滤器”，可将大部分可能的不需要的行取出。
这基于所谓的 Z-Order curve。为了获得更好的性能，如果您喜欢冒险..您可以尝试使用 Hilbert Curve instead。该曲线奇怪地旋转，以确保在最坏的情况下，您仅扫描桌子的25％。通常，这一行还将过滤出更多不需要的行。


所有资源的来源：当我遇到相同的问题并试图创造性地寻求解决方案时，我写了3篇关于该主题的博客文章。与MySQL的GEO索引相比，我的性能要好得多。


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