Есть ли способ оптимизировать сложный математический запрос в MySQL?

Question

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

Я выполняю запрос по миллионам записей, чтобы найти все координаты x, y, z (это звезды) вдоль линейного столбца от системы a до системы b с заданным радиусом. Я работаю через PHP с большим количеством других работ, выполняемых в результирующем наборе. Я получаю результаты от скрипта примерно за 16 секунд. Задержка запроса составляет около 7 из этих 16 секунд.

Основная логика запроса:

SELECT name, coordinates, and distance from end point 
FROM stars 
WHERE all stars are in a column of given radius between start and end points 
ORDER BY distance from end point DESC 

где положение требует двух отдельных вычислений, они это:

Где расчета 1:

Calculate if the stars are within the space of the column using constants and x,y,z 

Где расчет 2:

Limit the column radius to a given figure. 
(This where clause also performs similar calculations with the same constants and x,y,z.) 

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

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

Запрос легче читать, как определено до подстановки переменных:

SELECT 
    name, 
    x, 
    y, 
    z, 
    SQRT(
     pow(`x`-" . $bx . ",2)+ 
     pow(`y`-" . $by . ",2)+ 
     pow(`z`-" . $bz . ",2) 
    ) d 
FROM 
    stars 
WHERE 
    (((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) between 0 and 1 
AND 
    SQRT(((($ax + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cx))-`x`)*(($ax + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cx))-`x`))+((($ay + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cy))-`y`)*(($ay + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cy))-`y`))+((($az + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cz))-`z`)*(($az + ((((`x`*$cx+`y`*$cy+`z`*$cz)-($constant_1))/($constant_2)) * $cz))-`z`))) 
     <=$radius 
ORDER BY 
    SQRT(
     pow(`x`-" . $bx . ",2)+ 
     pow(`y`-" . $by . ",2)+ 
     pow(`z`-" . $bz . ",2) 
    ) DESC 

Окончательный запуск запроса в базе данных выглядит следующим образом: (Для простоты я использую данные примеры, где много из константы 0.)

SELECT 
    name, 
    x, 
    y, 
    z, 
    SQRT(pow(`x`-25.21875,2)+ pow(`y`--20.90625,2)+ pow(`z`-25899.96875,2)) d 
FROM 
    stars 
WHERE 
    (((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) 
    between 0 and 1 
AND 
    SQRT((((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * 25.21875))-`x`)*((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * 25.21875))-`x`))+(((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * -20.90625))-`y`)*((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * -20.90625))-`y`))+(((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * 25899.96875))-`z`)*((0 + ((((`x`*25.21875+`y`*-20.90625+`z`*25899.96875)-(0))/(670809454.308)) * 25899.96875))-`z`))) 
    <=600 
ORDER BY 
    SQRT(pow(`x`-25.21875,2)+ pow(`y`--20.90625,2)+ pow(`z`-25899.96875,2)) DESC 

Мое определение таблицы выглядит следующим образом:

CREATE TABLE IF NOT EXISTS `stars` (
    `localkey` bigint(20) NOT NULL AUTO_INCREMENT, 
    `id` bigint(20) NOT NULL, 
    `x` double NOT NULL, 
    `y` double NOT NULL, 
    `z` double NOT NULL, 
    `name` varchar(100) COLLATE utf8_unicode_ci NOT NULL, 
PRIMARY KEY (`localkey`), 
UNIQUE KEY `id` (`id`), 
KEY `x` (`x`), 
KEY `y` (`y`), 
KEY `z` (`z`), 
KEY `xyz` (`x`,`y`,`z`), 
KEY `name` (`name`) 
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci 

объяснить результатов запроса не указывает на использование индекса и дополнительной сложности:

extra: Using where; Using filesort; 

То, что я пытался до сих пор:

• Настройка различных типов данных для оптимизации использования памяти и индексации (Даже если моя математика делает маловероятными индексы когда-либо использоваться)
• Использование цикла PHP и нескольких меньших запросов вместо этого одного огромного (потребовалось больше времени с несколькими запросами.)
• Копирование в таблицу памяти перед запуском запроса (Таблица слишком rge для установки в память)
• Копирование только части таблицы (localkey, x, y, z) в память. (Это подойдет, но осталось так мало от max_heap_size для других процессов, что этого не стоило.)

Есть ли другие варианты, которые мне не хватает?

Спасибо!

Answer 1

Предполагая, что только меньшая подмножество ваших записей будет соответствовать, вы можете уменьшить математическую нагрузку, выполнив сначала базовую «прямоугольную» фильтрацию. например нет смысла выполнять полное декартовое расстояние для КАЖДОЙ записи в таблице, только чтобы выбросить большую часть из них.

Простая «окно» проверка границы только простое вычитание и сравнение:

SELECT ... 
FROM (
    SELECT ... 
    WHERE (
     (abs($x_coord - x_coordinate) <= $max_distance) 
    OR (abs($y_coord - y_coordinate) <= $max_distance) 
    ) 
) AS square_filter 
WHERE ... full calculation here 

Из cousre, вы делаете 3d позицию, так что это немного сложнее, но это должно дать вам основное идея.

Answer 2

В дополнении к отличному предложению быстрой предварительной фильтрации, Marc B предложенного выше, когда вы делаете ваш второй проход, вы можете сэкономить немного вычисления на расстоянии формуле два способов:

1) использование (xk) * (xk) вместо вызова pow (xk, ...)

2) пропустите квадратный корень и вычислите квадрат расстояния. Затем вы сравните с квадратом расстояния, которое вам нужно, которое нужно только вычислить один раз.

Answer 3

Наряду с двумя предложенными великими математическими оптимизациями наибольший скачок в повышении скорости будет представлять собой форму , сводящую к минимуму любые вычисления и сокращение вашего места поиска. Это означает пространственное индексирование.

Я не эксперт в MySQL, но идея заключается в том, что вы предварительно генерируете пространственные индексы в трехмерном пространстве, поэтому ваше пространство поиска значительно сокращается.

Чтобы быть более точным, с полным сканированием таблицы ваша сложность становится O (n^2). Время, требуемое для поиска, увеличивается с размером таблицы и тем, как далеко по таблице вы выполняете поиск. Однако с пространственным индексом на основе дерева его можно уменьшить до O (n log n)

Подумайте об этом, разделив пространство на кубики фиксированного размера (и кубики внутри кубов). В отличие от того, как Google Map устраивает плитки. Теперь с индексированием у вас есть «червоточина» для каждого куба на основе исходных координат, так как вы можете вычислить куб, вы можете найти звезду с O (n) времени. Тогда все, что вам нужно сделать, это запустить поиск в этом кубе.

Вот некоторые ссылки в MySQL docs на пространственные индексы.

Я столкнулся с аналогичной проблемой, связанной с данными LiDAR в двух координатах несколько лет назад. Вот ссылка на мой вопрос и ответы, которые могут помочь вам получить некоторые идеи:

https://gis.stackexchange.com/questions/12030/optimize-nearest-neighbor-query-on-70-million-point-cloud-on-sql-server-2008

Answer 4

ограничительной рамки подход может даже использовать индекс одной размеров. Но не так, как написано Марком. Вместо этого:

`x` BETWEEN $x - $dist AND $x + $dist 

Общий принцип заключается в том, что вы не должны скрывать индексированную переменную в функции. ABS в этом примере.

Также ...

ORDER BY d -- this will avoid recomputing the SQRT 

ли двойной минус в pow(y--20.90625,2) действительно работает? Чтобы это исправить, поменять их местами:

pow(-20.90625 - `y`,2) 

Это грязнее установить, но умножать может быть быстрее, чем POW:

(-20.90625 - `y`) * (-20.90625 - `y`)