Question

Что я хочу:

Пользователь передает почтовый индекс или название города
Я ищу в своей базе данных 5 ближайших мест
Отображение 5 ближайших местоположений рядом с этой позицией для пользователя

Что у меня есть:

Скажем, таблица мест со следующимсодержимое:

(около 16000 строк)

CREATE TABLE `locations` (
 `locationID` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(150) NOT NULL,
 `firstname` varchar(100) DEFAULT NULL,
 `lastname` varchar(100) DEFAULT NULL,
 `street` varchar(100) NOT NULL,
 `city` varchar(100) NOT NULL,
 `state` varchar(100) NOT NULL,
 `zipcode` varchar(10) NOT NULL,
 `phone` varchar(20) NOT NULL,
 `web` varchar(255) DEFAULT NULL,
 `machine` enum('Unbekannt','Foo','Bar') DEFAULT 'Unbekannt',
 `surface` enum('Unbekannt','Foo','Bar','') DEFAULT 'Unbekannt',
 PRIMARY KEY (`locationID`)
) ENGINE=InnoDB AUTO_INCREMENT=25 DEFAULT CHARSET=utf8

ID
имя
почтовый индекс
город

Теперь у меня есть вторая таблица со всеми городами мира:

(примерно 3,4 миллиона строк)

CREATE TABLE `geoData` (
 `geoID` int(11) NOT NULL AUTO_INCREMENT,
 `countryCode` char(2) NOT NULL,
 `zipCode` varchar(20) NOT NULL,
 `name` varchar(180) NOT NULL,
 `state` varchar(100) NOT NULL,
 `stateCode` varchar(20) NOT NULL,
 `county` varchar(100) NOT NULL,
 `countyCode` varchar(20) NOT NULL,
 `community` varchar(100) NOT NULL,
 `communityCode` varchar(20) NOT NULL,
 `lat` mediumint(6) NOT NULL,
 `lon` mediumint(6) NOT NULL,
 PRIMARY KEY (`lon`,`lat`,`geoID`) USING BTREE,
 KEY `geoID` (`geoID`)
) ENGINE=InnoDB AUTO_INCREMENT=16482 DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (lat)
(PARTITION p0 VALUES LESS THAN (-880000) ENGINE = InnoDB,
PARTITION p1 VALUES LESS THAN (-860000) ENGINE = InnoDB,
PARTITION p2 VALUES LESS THAN (-840000) ENGINE = InnoDB,
PARTITION p3 VALUES LESS THAN (-820000) ENGINE = InnoDB,
PARTITION p4 VALUES LESS THAN (-800000) ENGINE = InnoDB,
PARTITION p5 VALUES LESS THAN (-780000) ENGINE = InnoDB,
PARTITION p6 VALUES LESS THAN (-760000) ENGINE = InnoDB,
PARTITION p7 VALUES LESS THAN (-740000) ENGINE = InnoDB,
PARTITION p8 VALUES LESS THAN (-720000) ENGINE = InnoDB,
PARTITION p9 VALUES LESS THAN (-700000) ENGINE = InnoDB,
PARTITION p10 VALUES LESS THAN (-680000) ENGINE = InnoDB,
PARTITION p11 VALUES LESS THAN (-660000) ENGINE = InnoDB,
PARTITION p12 VALUES LESS THAN (-640000) ENGINE = InnoDB,
PARTITION p13 VALUES LESS THAN (-620000) ENGINE = InnoDB,
PARTITION p14 VALUES LESS THAN (-600000) ENGINE = InnoDB,
PARTITION p15 VALUES LESS THAN (-580000) ENGINE = InnoDB,
PARTITION p16 VALUES LESS THAN (-560000) ENGINE = InnoDB,
PARTITION p17 VALUES LESS THAN (-540000) ENGINE = InnoDB,
PARTITION p18 VALUES LESS THAN (-520000) ENGINE = InnoDB,
PARTITION p19 VALUES LESS THAN (-500000) ENGINE = InnoDB,
PARTITION p20 VALUES LESS THAN (-480000) ENGINE = InnoDB,
PARTITION p21 VALUES LESS THAN (-460000) ENGINE = InnoDB,
PARTITION p22 VALUES LESS THAN (-440000) ENGINE = InnoDB,
PARTITION p23 VALUES LESS THAN (-420000) ENGINE = InnoDB,
PARTITION p24 VALUES LESS THAN (-400000) ENGINE = InnoDB,
PARTITION p25 VALUES LESS THAN (-380000) ENGINE = InnoDB,
PARTITION p26 VALUES LESS THAN (-360000) ENGINE = InnoDB,
PARTITION p27 VALUES LESS THAN (-340000) ENGINE = InnoDB,
PARTITION p28 VALUES LESS THAN (-320000) ENGINE = InnoDB,
PARTITION p29 VALUES LESS THAN (-300000) ENGINE = InnoDB,
PARTITION p30 VALUES LESS THAN (-280000) ENGINE = InnoDB,
PARTITION p31 VALUES LESS THAN (-260000) ENGINE = InnoDB,
PARTITION p32 VALUES LESS THAN (-240000) ENGINE = InnoDB,
PARTITION p33 VALUES LESS THAN (-220000) ENGINE = InnoDB,
PARTITION p34 VALUES LESS THAN (-200000) ENGINE = InnoDB,
PARTITION p35 VALUES LESS THAN (-180000) ENGINE = InnoDB,
PARTITION p36 VALUES LESS THAN (-160000) ENGINE = InnoDB,
PARTITION p37 VALUES LESS THAN (-140000) ENGINE = InnoDB,
PARTITION p38 VALUES LESS THAN (-120000) ENGINE = InnoDB,
PARTITION p39 VALUES LESS THAN (-100000) ENGINE = InnoDB,
PARTITION p40 VALUES LESS THAN (-80000) ENGINE = InnoDB,
PARTITION p41 VALUES LESS THAN (-60000) ENGINE = InnoDB,
PARTITION p42 VALUES LESS THAN (-40000) ENGINE = InnoDB,
PARTITION p43 VALUES LESS THAN (-20000) ENGINE = InnoDB,
PARTITION p44 VALUES LESS THAN (0) ENGINE = InnoDB,
PARTITION p45 VALUES LESS THAN (20000) ENGINE = InnoDB,
PARTITION p46 VALUES LESS THAN (40000) ENGINE = InnoDB,
PARTITION p47 VALUES LESS THAN (60000) ENGINE = InnoDB,
PARTITION p48 VALUES LESS THAN (80000) ENGINE = InnoDB,
PARTITION p49 VALUES LESS THAN (100000) ENGINE = InnoDB,
PARTITION p50 VALUES LESS THAN (120000) ENGINE = InnoDB,
PARTITION p51 VALUES LESS THAN (140000) ENGINE = InnoDB,
PARTITION p52 VALUES LESS THAN (160000) ENGINE = InnoDB,
PARTITION p53 VALUES LESS THAN (180000) ENGINE = InnoDB,
PARTITION p54 VALUES LESS THAN (200000) ENGINE = InnoDB,
PARTITION p55 VALUES LESS THAN (220000) ENGINE = InnoDB,
PARTITION p56 VALUES LESS THAN (240000) ENGINE = InnoDB,
PARTITION p57 VALUES LESS THAN (260000) ENGINE = InnoDB,
PARTITION p58 VALUES LESS THAN (280000) ENGINE = InnoDB,
PARTITION p59 VALUES LESS THAN (300000) ENGINE = InnoDB,
PARTITION p60 VALUES LESS THAN (320000) ENGINE = InnoDB,
PARTITION p61 VALUES LESS THAN (340000) ENGINE = InnoDB,
PARTITION p62 VALUES LESS THAN (360000) ENGINE = InnoDB,
PARTITION p63 VALUES LESS THAN (380000) ENGINE = InnoDB,
PARTITION p64 VALUES LESS THAN (400000) ENGINE = InnoDB,
PARTITION p65 VALUES LESS THAN (420000) ENGINE = InnoDB,
PARTITION p66 VALUES LESS THAN (440000) ENGINE = InnoDB,
PARTITION p67 VALUES LESS THAN (460000) ENGINE = InnoDB,
PARTITION p68 VALUES LESS THAN (480000) ENGINE = InnoDB,
PARTITION p69 VALUES LESS THAN (500000) ENGINE = InnoDB,
PARTITION p70 VALUES LESS THAN (520000) ENGINE = InnoDB,
PARTITION p71 VALUES LESS THAN (540000) ENGINE = InnoDB,
PARTITION p72 VALUES LESS THAN (560000) ENGINE = InnoDB,
PARTITION p73 VALUES LESS THAN (580000) ENGINE = InnoDB,
PARTITION p74 VALUES LESS THAN (600000) ENGINE = InnoDB,
PARTITION p75 VALUES LESS THAN (620000) ENGINE = InnoDB,
PARTITION p76 VALUES LESS THAN (640000) ENGINE = InnoDB,
PARTITION p77 VALUES LESS THAN (660000) ENGINE = InnoDB,
PARTITION p78 VALUES LESS THAN (680000) ENGINE = InnoDB,
PARTITION p79 VALUES LESS THAN (700000) ENGINE = InnoDB,
PARTITION p80 VALUES LESS THAN (720000) ENGINE = InnoDB,
PARTITION p81 VALUES LESS THAN (740000) ENGINE = InnoDB,
PARTITION p82 VALUES LESS THAN (760000) ENGINE = InnoDB,
PARTITION p83 VALUES LESS THAN (780000) ENGINE = InnoDB,
PARTITION p84 VALUES LESS THAN (800000) ENGINE = InnoDB,
PARTITION p85 VALUES LESS THAN (820000) ENGINE = InnoDB,
PARTITION p86 VALUES LESS THAN (840000) ENGINE = InnoDB,
PARTITION p87 VALUES LESS THAN (860000) ENGINE = InnoDB,
PARTITION p88 VALUES LESS THAN (880000) ENGINE = InnoDB,
PARTITION p89 VALUES LESS THAN MAXVALUE ENGINE = InnoDB) */

ID
город
почтовый индекс
широта
долгота

на основании этого статья и некоторые другие материалы по этому вопросу. У меня есть хранимая процедура, которая дает мне n местоположения / почтовые индексы ближайших городов вблизи точки (широта / долгота).

Моя хранимая процедура:

    BEGIN
    DECLARE _deg2rad DOUBLE DEFAULT PI()/1800000;

    SET @my_lat := _my_lat,
        @my_lon := _my_lon,
        @deg2dist := 0.0111325,  
        @start_deg := _start_dist / @deg2dist,  
        @max_deg := _max_dist / @deg2dist,
        @cutoff := @max_deg / SQRT(2),  
        @dlat := @start_deg,  
        @lon2lat := COS(_deg2rad * @my_lat),
        @iterations := 0;        

    SET @sql = CONCAT(
        "SELECT COUNT(*) INTO @near_ct
            FROM geoData
            WHERE lat    BETWEEN @my_lat - @dlat
                             AND @my_lat + @dlat   
              AND lon    BETWEEN @my_lon - @dlon
                             AND @my_lon + @dlon");
    PREPARE _sql FROM @sql;
    MainLoop: LOOP
        SET @iterations := @iterations + 1;
        SET @dlon := ABS(@dlat / @lon2lat);  
        SET @dlon := IF(ABS(@my_lat) + @dlat >= 900000, 3600001, @dlon);  
        EXECUTE _sql;
        IF ( @near_ct >= _limit OR         
             @dlat >= @cutoff ) THEN       
            LEAVE MainLoop;
        END IF;
        SET @dlat := LEAST(2 * @dlat, @cutoff);   
    END LOOP MainLoop;
    DEALLOCATE PREPARE _sql;

    SET @dlat := IF( @dlat >= @max_deg OR @dlon >= 1800000,
                @max_deg,
                GCDist(ABS(@my_lat), @my_lon,
                       ABS(@my_lat) - @dlat, @my_lon - @dlon) );
    SET @dlon := IFNULL(ASIN(SIN(_deg2rad * @dlat) /
                             COS(_deg2rad * @my_lat))
                            / _deg2rad 
                        , 3600001);    


    IF (ABS(@my_lon) + @dlon < 1800000 OR    
        ABS(@my_lat) + @dlat <  900000) THEN 
        SET @sql = CONCAT(
            "SELECT *,
                    @deg2dist * GCDist(@my_lat, @my_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @my_lon - @dlon
                              AND @my_lon + @dlon   
                HAVING dist <= ", _max_dist, "
                ORDER BY dist
                LIMIT ", _limit
                        );
    ELSE
        SET @west_lon := IF(@my_lon < 0, @my_lon, @my_lon - 3600000);
        SET @east_lon := @west_lon + 3600000;
        SET @sql = CONCAT(
            "( SELECT *,
                    @deg2dist * GCDist(@my_lat, @west_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat 
                  AND lon BETWEEN @west_lon - @dlon
                              AND @west_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            UNION ALL
            ( SELECT *,
                    @deg2dist * GCDist(@my_lat, @east_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @east_lon - @dlon
                              AND @east_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            ORDER BY dist
            LIMIT ", _limit
                        );
    END IF;

    PREPARE _sql FROM @sql;
    EXECUTE _sql;
    DEALLOCATE PREPARE _sql;
END

Моя проблема:

Я хотел бы указать почтовый индекс илиназвание города и начать мой поиск оттуда.Поэтому я подумал, что я запрашиваю эту информацию и просматриваю свою таблицу всех городов / почтовых индексов мира.После этого у меня есть информация о широте / долготе, если был найден только один результат, или я бы попросил пользователя выбрать правильный вариант в случае получения нескольких результатов.

После этого я начинаю поиск ближайших городов, близких к моей текущей позиции.Допустим, я хочу список из 50 городов / городов.И с этим, я пошел бы и посмотрел бы и видел, соответствует ли таблица, содержащая местоположения, 5 результатов там.

Если подумать, это звучит как плохая идея ...

Подход 1:

Я читал охранимые процедуры, запросы sql и monster и попробуйте получить следующее:

Передавая почтовый индекс / название города, я бы посмотрел это, взял свой лат / лон из огромной таблицы (возможно, как функция в mysql).) и с учетом этого я буду искать ближайшие города и сразу же присоединюсь к таблице местоположений и получу мои 5 ближайших мест.

Вопросы:

Как можно избежать нескольких совпадений для одного и того же названия города / почтового индекса?
Возможно ли это сделать с помощьюпростое объединение, чтобы получить 5 ближайших местоположений?

Подход 2:

Получить все значения широт / долгот моих местоположений и затем запустить процедуруна этом столе вместо.И просто использовать огромную таблицу, чтобы получить мою текущую позицию?

При этом мне нужно будет собрать все широты моего местоположения.Но это может быть лучшим способом.

Но наличие огромной базы данных всех городов / почтовых индексов только для определения местоположения кажется излишним.Я надеюсь, что есть альтернатива, может быть ... как-то ...

Подход 3

Если честно, эта функция, которую я хочу, кажется написанной миллион раздо.Так зачем мне изобретать велосипед?Но я понятия не имею, как найти нужные статьи или книги для достижения моей цели.

У кого-нибудь из вас есть идея лучшей практики для чего-то подобного?

Paul Spiegel · Answer 1 · 03 июня 2018

16K строк не так уж и много.

У меня есть таблица cities с 3,1M строк (данные взяты из https://www.maxmind.com/de/free-world-cities-database). Я создал "фальшивую" locations таблицус 16K различных случайных cityIds и некоторыми фиктивными данными. Я использую один столбец с POINT типом данных вместо latitude и longitude. И это то, что я получаю из довольно простых запросов на MySQL 5.7.18:

select l.*, c.*, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
from locations l
join cities c using (cityId)
order by dist
limit 5

Время выполнения составляет ~ 70 мс.

Это можно улучшить с помощью подзапроса:

select l.*, c.*, x.dist
from (
    select l.locationId, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
    from locations l
    join cities c using (cityId)
    order by dist
    limit 5
) x
join locations l using(locationId)
join cities c using(cityId)

Время выполнения: ~ 40 мс

Если вы храните geoPoint (избыточно) в таблице locations, вы можете избежать объединения с таблицей cities.

select l.*, st_distance(point(-0.127758, 51.507351), l.geoPoint) dist
from locations l
order by dist
limit 5

Время выполнения: ~ 17 мс

Вы все еще можете присоединиться к cities таблица подзапросу без потери производительности.

Обратите внимание, что все эти запросы будут вычислять расстояние для всех строк 16K и сортировать их. Но производительности может быть достаточно для вас.

Еслиэто не достаточно быстро, или таблица locations будет расти со временем, или если вы хотите искать вНапример, вы можете сделать что-то похожее с вашей процедурой, используя SPATIAL INDEX на geoPoint и MBRWithin() или MBRContains().

Алгоритм:

Определение небольшого многоугольника вокруг местоположения пользователя.
Увеличивайте размер многоугольника в цикле доон содержит как минимум 5 местоположений.
Используйте местоположения внутри многоугольника, чтобы выбрать 5 ближайших.

Обратите внимание, что в зависимости от того, какой тип многоугольника вы используете, вам может потребоваться увеличитьразмер еще раз после того, как вы нашли один с 5 местоположениями.Например, если вы используете квадрат (простая реализация), вы должны удвоить размер (увеличить длину в sqrt (2) ), чтобы быть абсолютно уверенным, что вы не пропустите место за пределамиквадрат, который находится ближе, чем 5-е место в пределах площади.Это потому, что квадрат не круг.Но если вы используете восьмиугольник, вы можете сказать - этого достаточно, и пропустить последний шаг.

Это может быть не самый лучший алгоритм.Но это довольно просто реализовать и должно достаточно хорошо масштабироваться.

Rick James · Answer 2 · 28 мая 2018

Первые комментарии ...

Я видел десятки (не миллионов) реализаций здесь и на других форумах;у тебя лучше, чем у большинства.

Согласно одному источнику данных (который я случайно скачал), в мире около 3,2 млн. городов.

Для производительности вам нужно избегать проверки всех3М рядов.Вы хорошо начали с растущей ограничительной рамки.Обратите внимание, что у вас должно быть

INDEX(lat, lon),
INDEX(lon, lat)

Оптимизатор будет выбирать между ними, и первый запрос (с COUNT(*)) будет видеть это как «покрытие».Это будет полоса вокруг земного шара или клин;определенное улучшение по сравнению с 3M строк.Наихудшая широта (+34 градуса) имеет 96K городов.(1 градус = 69 миль / 111 км.) Для одной десятой градуса 34,4 является наихудшим, с 10 тыс. Городов.

(Да, мне нравится такая головоломка с данными.)

И я вижу, что вы справляетесь с датой и полюсами.Я не думаю, что вы можете улучшить их в качестве особого случая.

(я только взглянул на формулы и константы.)

Справка по индексированию по геохэшу и Z-порядку.Но у них есть сбой в том, что вам нужно проверить до 4 областей вокруг цели - это все равно, что не понимать, что целые числа 199999 и 200000 действительно близки друг к другу, несмотря на то, что первая цифра каждого различна.

«Пользователь передает почтовый индекс или название города» - это точечный запрос в одну из двух простых таблиц.(За исключением того, что может быть дуплекс - более 320 из каждого из "Сан-Хосе" и "Сан-Антонио". Довольно далеко внизу списка находится первое неиспанское имя: "Виктория", всего 144 города.)

Во-вторых, моя реализация ... (Она имеет некоторые сходства с вашей.)

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

Это повышает производительность благодаря использованию PARTITIONing для сохраненияограничивающий прямоугольник примерно до квадрата вместо полосы или клина.Если вы ищете 5 ближайших, мой алгоритм редко будет касаться более нескольких десятков строк, и эти строки будут «кластеризованы» в небольшое количество блоков, тем самым сохраняя количество обращений к диску очень низким.

Критическая вещь в моем дизайне - иметь все необходимые столбцы в одной таблице.Найдя ближайшие 5, вы можете перейти к другим столам, чтобы получить вспомогательные вещи (номер телефона и т. Д.).

Что касается почтовых индексов, перед началом поиска 5 выберите их в лат / лон.ближайший.

Соединение внутри алгоритма может привести к снижению производительности.

Поиск 5 ближайших мест к почтовому индексу - каким путем я должен идти?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Поиск 5 ближайших мест к почтовому индексу - каким путем я должен идти?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы