Ускорение этого запроса mysql

Question

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

[id (int)] [group (int)] [latitude (double)] [longitude(double)] 
[1]  [1]   [22.365598]   [12.55678] 
[2]  [1]   [22.365548]   [12.55238] 
[3]  [2]   [24.665348]   [13.10238] 

Теперь я хочу, чтобы каждый пункт внутри данной boudingbox.The boudingbox имеет размер Южной Африки и запрос должен возвращать около 7,000 результатов. Но для получения результатов требуется 30 секунд.

Этот запрос:

SELECT distinct(group), id from `table` 
where (latitude between -95.22 and 36.458 and longitude between -51.939 and 103.833); 

Индекс [широта, долгота] (ВТКЕЕ).

Как я могу ускорить это?

---

EDIT

То, что я хочу сделать

База данных содержит большой набор полигонов. Скажем, например, Национальные парки. Каждый узел в многоугольнике находится в этой таблице. Теперь я хочу проверить, находится ли национальный парк в пределах данной позиции.

Id - это идентификатор узла, группа - это многоугольник, к которому он принадлежит, а широта и долгота - это положение узла.

---

Когда я не использую отчетливо, запрос завершится за 3 секунды, но будет возвращено 900.000 результатов. который много для обработки в остальной части кода.

---

гуманного

Как Гордон Линофф в своем ответе говорит: это действительно большая поверхность. Запрос используется для некоторых реальных подробных результатов. С этой большой поверхностью я не должен использовать все узлы из всех полигонов, но использовать многоугольник многоугольника. Когда мне нужны подробные результаты для небольших поверхностей, этот запрос выполняется достаточно быстро.

Так что я думаю, что придерживаюсь этого.

Answer 1

Как указано под The Range Access Method for Multiple-Part Indexes:

оптимизатор пытается использовать дополнительные ключевые элементы для определения интервала до тех пор, пока оператор сравнения =, <=> или IS NULL. Если оператор >, <, >=, <=, !=, <>, BETWEEN или LIKE, оптимизатор использует его, но считает не более ключевыми части.

Другими словами, MySQL использует свой индекс только найти записи, в которых latitude попадает в указанный диапазон, тогда выбирает те записи из таблицы и сканирование через них, чтобы выполнить фильтр на longitude.

Причина, по которой MySQL делает это очевидно, если учесть, как B-tree структурирована:

 
          Bd 
       ________/ \_______ 
       /     \ 
       Ad     Cd 
      __/ \__    __/ \__ 
     /  \   /  \ 
      Ab  Bb   Cb  Db 
     /\ /\  /\ /\ 
     Aa Ac Ba Bc  Ca Cc Da Dc 

Фильтрование первую ключевую роль для диапазона (например, если первый символ в примере BETWEEN 'B' AND 'C' выше, но критерий широты в вашем случае) очень просто, потому что дерево уже отсортирован по отношению к первой ключевой части:

 
          Bd 
       ________/ \_______ 
       /     \ 
       \     Cd 
       \__    __/ 
        \   /
        Bb   Cb 
       /\  /\ 
        Ba Bc  Ca Cc 

Но в результате обрезок дерево не может помочь при фильтрации на второй ключевой части (например, порог e второй символ BETWEEN 'b' AND 'c' в этом примере, но критерий долготы в вашем случае), потому что это не, отсортированный относительно второй ключевой части. Напротив, если бы первая ключевая часть была отфильтрована для точного совпадения (а не диапазона), тогда полученное обрезанное дерево будет, а затем будет сортироваться по второй ключевой части.

Таким образом, B-деревья не могут помочь в поиске многомерных диапазонов. R-tree - это альтернативная структура данных, которая намного лучше подходит для подобных задач.MySQL может создавать индексы R-дерева, используя его spatial extensions:

1. Создать новый столбец spatial data type (например POINT), который будет держать ваши данные координат и index документ:

   ALTER TABLE `table` 
       ADD coordinates POINT, 
       ADD SPATIAL INDEX (coordinates); 
   

2. заселить этот столбец из ваших существующих данных:

   UPDATE `table` SET coordinates = Point(longitude, latitude); 
   

   Возможно, вы захотите определить триггеры и/или виды на ssist с дальнейшей миграцией.

3. Выполните поиск:

   SELECT DISTINCT `group`, id 
   FROM `table` 
   WHERE MBRContains(
        MultiPoint(Point(-51.939, -95.22), Point(103.833, 36.458)), 
        coordinates 
        ) 
   

   Что особенно приятно об этом подходе является то, что, как и в MySQL 5.6.1, можно use object shapes выполнять еще более точные поисковые запросы: например, определить полигоны, которые точно представляют национальные границы.

4. Обновить приложение, чтобы использовать этот новый столбец, например:

   SELECT X(coordinates) AS longitude, Y(coordinates) AS latitude FROM `table` 
   

   Вы можете определить триггеры и/или представления для содействия миграции.

5. Отбросьте старые колонки:

   ALTER TABLE `table` DROP longitude, DROP latitude; 
   

Однако, следует отметить, что пространственные расширения MySQL используют евклидовой геометрии (в то время как, очевидно, Земля имеет форму шара): это не должно повлиять выше но будьте осторожны с его использованием для выполнения расчетов, таких как расстояние.

Answer 2

Во-первых, круглые скобки не имеют значения для distinct. Таким образом, просто написать запрос как:

SELECT distinct `group`, id 
from `table` 
where latitude between -95.22 and 36.458 and 
     longitude between -51.939 and 103.833; 

Этот тип запроса - с двумя between с - это на самом деле не поддается индексах. You может попробуйте индекс на latitude, longitude или longitude, latitude, и он может предложить небольшое небольшое увеличение скорости.

Лучшим подходом является использование пространственных индексов. Here - это место, чтобы начать узнавать о них.

Однако даже пространственный индекс вряд ли поможет. Области в вашем аккаунте запросов составляют около 1/6 поверхности земли. Если ваша точка распределена равномерно, то это более 3 миллионов записей, которые необходимо агрегировать (для select distinct). Вероятно, вам не удастся получить действительно хорошую производительность для этого запроса.

Answer 3

Это не директ ответ на ваш вопрос, но если вы уже используете MySQL 5.5 или выше, и у вас есть выбор, чтобы изменить модель данных, я хотел бы предложить вам воспользоваться Point типа данных и добавить пространственный индекс

http://dev.mysql.com/doc/refman/5.0/en/using-spatial-data.html

в противном случае я хотел бы предложить вам оставить из отчетливый, так как он может быть узким местом производительности иногда и добавить group by вместо этого и я хотел бы предложить включить group в индекс, тоже.

Answer 4

Что делать, если вы добавляете поле, содержащее целочисленное поле с индексом для точного раздела? Ex. (latitude between -95.22 and 36.458 and longitude between -51.939 and 103.833); = 1; (some other lat/long span) = 2 и т. Д. Затем вы просто пересчитываете значения для каждой записи и сохраняете значения в новом поле. Все новые (обновленные) записи могут быть обработаны перед триггером insert (update), чтобы поле целого целого было установлено для каждой добавленной (обновленной записи). Все запросы SELECT будут использовать это поле вместо двойных полей lat/long. Это будет некоторая избыточность данных, но может помочь вам, если у вас ограниченный список территорий. Вы можете использовать вторую таблицу для хранения списка территорий и их идентификаторов.