0

この手順を最適化するには、助けが必要です。

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
4

1 に答える 1

2

私が知る限り、これを遅くするロジックに直接問題があるわけではないので、問題は、このクエリでインデックスを使用できないことです。

MySQL は、完全なテーブル スキャンを実行し、WHERE 句の関数を各行に適用して、条件を満たしているかどうかを判断する必要があります。現在、1 つのインデックスが使用されています: idx_lat_long

これは少し悪いインデックスです。この部分は floatlongであるため、使用されることはありません。latしかし、少なくとも、latitude範囲外のすべての行を効果的に除外することができました。しかし、おそらく..これらはまだたくさんあります。

人間は実際には地球の中央 30% にしか住んでいないため、実際には経度でわずかに良い結果が得られます。私たちは水平方向に大きく広がっていますが、垂直方向にはあまり広がっていません。

とにかく、フィールドをさらに最小化する最善の方法は、一般的な領域でできるだけ多くのレコードを除外することです。現時点では、地球上で完全に垂直なストリップになっています。バウンディング ボックスを作成してみてください。

たとえば、10x10 セグメントで単純に地球をさいの目に切ることができます。これにより、クエリが地球の 10% に制限されることが最善のケースになります ;)。

しかし、バウンディング ボックスが別のセグメントを超えるとすぐに、最初の座標 (緯度または経度) のみがインデックスで使用され、同じ問題が発生します。

ですから、この問題について考えたとき、私はこれについて別の方法で考え始めました。代わりに、地球を 4 つのセグメント (たとえば、地図上で北東、北西、南東、南西) に分割しました。これにより、次のような座標が得られます。

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

x と y の値を 2 つの別々のフィールドに入れる代わりに、ビット フィールドとして使用し、両方を一度に格納しました。

次に、再び分割した 4 つのボックスの 1 つごとに、2 つの座標セットが得られます。外側と内側の座標。これはまだ同じフィールドでエンコードしています。つまり、8x8 座標系に 4 ビットを使用しています。

どこまで行ける?64 ビットの整数フィールドを想定すると、2 つの座標のそれぞれに 32 ビットを使用できることを意味します。これにより、4294967295 x 4294967295 のグリッド システムがすべて 1 つのデータベース フィールドにエンコードされます。

このフィールドの優れた点は、インデックスを作成できることです。これは、Quad-tree と呼ばれることもあります (私はそう思います)。データベースで大きな領域を選択する必要がある場合は、64 ビットの左上座標 (4294967295 x 4294967295 グリッド システム) と左下座標を計算するだけで、そのボックスにあるものもすべて選択されることが保証されます。 2つの数の中で。

どうやってそれらの数字にたどり着くのですか?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

}

私は最後の変数を「モートン」と呼んでいます.1966年にそれを思いついた人です.

したがって、最終的には次のようになります。

  1. データベースの各行について、モートン数を計算して保存します。
  2. クエリを実行するときはいつでも、最初に最大バウンディング ボックスを (モートン数として) 決定し、それをフィルタリングします。

これにより、チェックする必要のあるレコードの数が大幅に削減されます。

これは、私が作成したストアド プロシージャであり、計算を行います。

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 オーダー カーブに基づいています。さらに優れたパフォーマンスを得るには、冒険好きなら..代わりにヒルベルト曲線を試すことができます。この曲線は奇妙に回転するため、最悪のシナリオでは、テーブルの約 25% しかスキャンできません..魔法! 一般に、これはより多くの不要な行もフィルタリングします。

このすべてのソース: 同じ問題に遭遇し、創造的に解決策を見つけようとしたときに、このトピックについて 3 つのブログ投稿を書きました。MySQL の GEO インデックスと比較して、これではるかに優れたパフォーマンスが得られました。

于 2013-03-26T02:14:10.320 に答える