Order by distance. Как?

Question

[l4m3r]

Есть большая таблица x, y, z координат.
Можно ли как-то одним запросом получить отсортировать по расстоянию по определённой точки (скажем [50, 50, 50]).
Или может по-другому спроектировать таблицу?

Comments

[Moskus]

Вы про пространственные расширения БД слышали?
Эти координаты - условные или географические/геодезические?

[l4m3r]

Moskus, не слышал. В mysql есть?
Координаты условные. Целочисленные с ограничением 0 <= x <= 1000. 0 <= y <= 1000. 0 <= z <= 1000.

[Moskus]

l4m3r, раз условные, то вычисляйте расстояние (формулу про корень из суммы квадратов разностей из школьной программы помните?), кладите в отдельную колонку, сортируйте по ней.

[l4m3r]

Moskus, неоптимальное решение. fullscan таблицы всякий раз. А если мне нужно всего пару ближайших записей получить? Всё равно фулскан.

[Moskus]

l4m3r, ну вы можете делать что-то с https://dev.mysql.com/doc/refman/5.7/en/spatial-fu...

Answer 1

[Иван Шумов]

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

Comments

[l4m3r]

В смысле вычисляемую колонку в select'е типа select *, func(...) as distance ... order by distance?
Но тогда получится FullScan при любом запросе же.

[Иван Шумов]

l4m3r, функцию не обязательно. Просто математический рассчет

[l4m3r]

Иван Шумов, Да. Получится такой запрос

select *, sqrt((x - :x, 2) + pow(y - :y, 2) + pow(z - :z, 2)) as distance from points order by distance limit 10.

Он работает. Но его никак не оптимизировать, да? Тут ни один индекс работать не будет и всегда fullscan.

[Иван Шумов]

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

[l4m3r]

Иван Шумов, я тоже думал про кластеры. Поделить координаты на зоны. Но если точка будет ближе к краю кластера, то ближайшая может быть уже в другом. И в итоге надо просматривать соседние и так далее. Как это все обрабатывать ума не приложу и забил.

[Иван Шумов]

l4m3r, и не надо. сколько у вас там точек?

[Иван Шумов]

l4m3r, видел я один документ на просторах интернета по теме )

[l4m3r]

Иван Шумов, спасибо! только узнал, что можно не заботиться, что таблица точек изменится извне или классы будут запускаться параллельно. И все поиски будут в пределах одного скрипта. Грубо говоря, можно копить кеш в php для быстрого поиска. Так намного легче. 2 дня насмарку)

[Иван Шумов]

l4m3r, у вас не практикуется такая вещь как архитектура?) или она есть, но ее никому не показывают?)

[l4m3r]

Иван Шумов, это же опять тестовое задание! чисто академическое. разумеется, в реальных задачах так делать неприемлимо. А какая архитектура у них там я хз. Пока не взяли ещё.

[Иван Шумов]

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

[l4m3r]

Иван Шумов,
Во-первых, я решил его сам. Это далеко не всё тестовое, а лишь один момент, который я вдобавок упростил чтобы понять суть, и который я тоже решил (написал выше об этом), но метод который я использовал мне показался неоптимальным - поэтому решил спросить совета ибо ничего не нагуглил подобное и не надумал.
Во-вторых, какую собственно помощь я получил? Про вычисляемую колонку я и так знал. Больше ничего.

[Иван Шумов]

l4m3r, дело в том что вы в любом случае пробуете получить помощь вместо того чтобы делать выводы из неудач. Хорошо желать избегать ошибок, но лучше это делать за свой счет

Answer 2

[Андрей Николаев]

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

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

Comments

[l4m3r]

то есть если таблица точек будет 1000 записей, то связей будет 1000*1000? Будет ли это быстрее?

[Андрей Николаев]

l4m3r, да, будет.
Как только у вас будет 10 миллионов точек, тогда будут уже вопросы, а пока подойдет и такой вариант.

Answer 3

[TheRonCronix]

Посчитать можно, для этого придется пройтись по всем строкам таблицы и для каждой из точек высчитать расстояние до вашей точки, а потом отсортировать. Но, если нужно выбрать лишь несколько ближайших точек или просто точки не слишком удаленные от заданной, то можно воспользоваться техникой bounding-box: представить, что вокруг точки куб или квадрат заданного размера и провести вычисление сначала в границах куба. Это позволит хоть как-то задействовать индексы.