Эффективный поиск в таблице диапазонов

У меня есть таблица диапазонов IP-адресов 1.6M с названиями организаций. IP-адреса преобразуются в целые числа. Стол в виде:Эффективный поиск в таблице диапазонов

enter image description here

У меня есть список из 2000 уникальных IP-адреса (например 321223, 531223, ....), которые должны быть переведены на имя организации.

я загрузил таблицу перевода в виде таблицы тузда с индексом на IP_from и IP_to. Я зацикливал IP-адреса 2000, запуская один запрос на IP-адрес, и через 15 минут отчет все еще работал. Запроса я использую

select organization from iptable where ip_addr BETWEEN ip_start AND ip_end

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

источник

2013-10-09 gitb

Вы хотите создать R-Tree (пространственный) индекс над '(IP_from, IP_to)'. – eggyal

Какие индексы вы использовали? –

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

Учитывая, что у вас уже есть индекс по ip_start, это то, как использовать его лучше, если предположить, что вы хотите сделать один доступ за IP (1234 в данном примере):

select organization from (
    select ip_end, organization 
    from iptable 
    where ip_start <= 1234 
    order by ip_start desc 
    limit 1 
) subqry where 1234 <= ip_end

Это будет использовать ваш чтобы начать сканирование, которое немедленно прекращается из-за limit 1. Стоимость должна быть незначительно выше, чем стоимость простого индексированного доступа. Конечно, этот метод основан на том, что диапазоны, определяемые ip_start и ip_end, никогда не перекрываются.

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

источник

2013-10-09 22:19:17

Вы, сэр, бог mysql (sql). Используя индекс и мой запрос из моего первоначального вопроса, я обнаружил, что 1) IP-адреса, которые были 9 цифр или меньше (например ,.248082010), заняли ~ 40 мс. 2) IP-адреса, превышающие миллиард, т. Е. 10 цифр (например, 1823194021), заняли около 600 мс, и это то, что убивало производительность. По вашему запросу все занимает 0,5 мс. Вау. – gitb

Спасибо @gitb, но если бы я был богом, мир был бы пантеоном ;-) Не возражаете, если я изменю название вашего вопроса на «Эффективный поиск в таблице диапазонов»? (или, может быть, у вас лучший титул). Это будет в направлении «эффективного поиска в переполнении стека», –

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

В любом случае вам нужно иметь индекс (IP_from, IP_to).

источник

2013-10-09 22:18:47 Joni

Вполне вероятно, что ни один из моих IP-адресов в 2000 году не будет отображаться в таблице поиска. Они будут падать между полями ** с ** и ** на **. Поэтому я не вижу, как я могу присоединиться. – gitb

Вы можете написать 'JOIN ON ip> = ip_from И ip <= ip_to' Не может быть столь же эффективным, как объединение с' = ', но с соответствующими индексами это не намного хуже. – Joni

@Joni, какие «правильные индексы» могут сообщить mysql, что только одна запись может соответствовать условию для данного 'ip'? –

Эффективный поиск в таблице диапазонов

ответ

Смежные вопросы