Как быстро проверить попадание IP в диапазон?

Question

[Антон Корзунов]

На основе stackoverflow.com/questions/22125474/mysql-optimal... и миллионов других вариантов.
В общем случае

select * from ipBase where ? between start_ip and end_ip

работает не совсем правильно - запрос преобразуется в
select * from ipBase where start_ip<? and end_ip>?
Это формирует так называемый "открытый" интервал - найти все значения start_ip которые меньше заданного, и все end, которые больше.
Так как мы проверяем "точку" - это приведет в выборке вообще всех значений в базе в первой части, и пересечению с результатами второй.
Долго, дорого, очень.
Обычно решением является ограничить область поиска, те создать закрытый интервал. По факту диапазоны редко когда бывают более 32к значений "длиной", и запрос можно преобразовать в

select * from ipBase where ? between start_ip and end_ip and start_ip between ?-32k and ?.....

Это сильно быстрее, но не "алгоритмично",

Интересуют именно красивые идеи для решения задачи на SQL, и вообще (академические) варианты решения нахождения вхождения точки в отрезок. За O(logn) или меньше :P

Answer 1

[Fadmin]

Сколько записей у вас в таблице?
Как хранится IP адрес, какой тип данных?
Если IPv4 то подозреваю что записей немного.
Общим решением будет навесить индекс на оба поля, и приджойнить таблицу к себе же.

Comments

[Антон Корзунов]

Совет на удивление работает, только не совсем понимаю почему
SELECT * FROM `ipgeobase_ip` AS ip1 INNER JOIN ipgeobase_ip AS ip2 ON ip1.id = ip2.id WHERE ip1.ipfrom <3653624834 AND ip2.ipto >3653624833
В 10-100 раз быстрее чем
SELECT * FROM `ipgeobase_ip` as ip1 WHERE ip1.ipfrom<3653624834 and ip1.ipto>3653624833
Хотя первая строчка EXPLAIN у обоих одинаковая - скан всех записей до начала таблицы

[Fadmin]

Индексы были у вас?

[Антон Корзунов]

Fadmin: конечно. В том числе проверил как на одиночном двойном, так и отдельных на начало и конец. Время работы получается в районе 0.001(минимальные ipfrom) - 0.01(максимальные ipfrom), и, к сожалению, четко зависит от позиции запроса. Те fullscan таблицы в любом случае.

[Fadmin]

Хотите еще быстрее?

[Антон Корзунов]

В начале я хочу понять почему ваш вариант быстрее. Во вторых я хочу чтобы скорость приблизилась к самописным вариантам деревья, дитохомию, подсчет интервалось и тд.
Напрягает как-то что (если у нас есть таблица "точек") найти все точки во всех интервалах (потому что закрытые) чуть ли не быстрее чем найти интервал одной заданной точки.

[Fadmin]

А какая скорость у самописных вариантов?

[Антон Корзунов]

Fadmin: В 100 раз быстрее, но поддержка, масштабируемость, синхронизация, да просто потребление памяти - в переспективе не радуют. Как я говорил чуть ниже - у меня не IPшники - у меня просто диапазоны. Алгоритмически одного и тоже, просто данных больше.

[Fadmin]

В 100 раз наверное не получится разогнать, но можно попробовать еще один порядок выжать. В скайп?

Answer 2

[xmoonlight]

select id, 
GREATEST(INET_ATON(ipBase.ip)-INET_ATON(start_ip)) as ip2
LEAST(INET_ATON(end_ip)-INET_ATON(ipBase.ip)) as ip3
from ipBase
where ip2<start_ip OR ip3>end_ip
group by id

что-то в этом духе, но не проверял...

Comments

[Антон Корзунов]

Открытый интервал поиска, полный перебор

[xmoonlight]

Антон Корзунов: поменял в ответе... так должно быть?

[Антон Корзунов]

xmoonlight: нет. Проблемы поиска "до конца налево, до конца на право" я описан в начале топика. По сути требуется найти максимальное левое значение (BigMin) и минимальное правое (LitMax). Только нет такой команды :(