如何優化此存儲過程？

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％。我們非常分散，但不是真正的垂直。

無論如何，到現場進一步減少的最好辦法是嘗試在一般區域中過濾掉儘可能多條記錄。現在它在地球上是一條完整的垂直條帶，試圖使它成爲一個邊界框。

你可以天真的骰子中說，10×10段的地球。這將在最好的情況下確保查詢被限制在地球的10％;）。

但只要你的邊框超過分離段，只有第一個座標（LAT或LNG）可以用到索引和你結束了同樣的問題。

所以，當我想到了這個問題，我開始不同的思考這個。相反，我將地球分成四段（可以說，地圖上是東北，西北，東南，西南）。所以這給了我像座標：

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

而不是把x和y的值在2單獨的字段，我用它作爲一個字段，並立即存儲。

然後我再次分開的4個盒子中的每1個盒子，這給了我們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和（360分之4294967295約爲11930464）。

所以轉換成我們新的網格系統，我們只是做：

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

現在我們就來個不同的數字，我們需要把它們變成1號。 x的第1位，那麼比特y 1，位×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. 每當您執行查詢時，首先確定最大邊界框（作爲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. 在這種情況下，邊界框假定爲Eucllidean space，意思是......平坦的表面。實際上，你的邊界框不是精確的正方形，當它們靠近極點時它們會嚴重彎曲。通過將盒子放大一點（取決於你想要的確切程度），你可以變得相當遠。大多數現實世界的數據也往往不接近極點;）。請記住，這個過濾器只是一個'粗略過濾器'，用於獲取大部分可能不需要的行。
3. 這是基於所謂的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