Comments 93
PRIMARY KEY (`ipn1`),
INDEX `ipn2` (`ipn2`)
Я бы на вашем месте снёс свой обзор в черновики и пошёл учить мат. часть про индексы в MySql
INDEX `ipn2` (`ipn2`)
Я бы на вашем месте снёс свой обзор в черновики и пошёл учить мат. часть про индексы в MySql
Хм, и что не так с индексами хоть бы намекнули. Да и тут вообще-то рассматриваются популярные решения, встречающиеся в инете.
Нормальная структура для использования индекса и запрос должны быть примерно такими:
Индекс должен быть сдвоенным в общем.
CREATE TABLE `worldip` (
`start` int(10) UNSIGNED NOT NULL default '0',
`end` int(10) UNSIGNED NOT NULL default '0',
`code` varchar(2) NOT NULL default '',
PRIMARY KEY (`start`,`end`)
) ENGINE=MyISAM;
SELECT code FROM `worldip` WHERE `start` <= INET_ATON('IP') AND `end` >= INET_ATON('IP') LIMIT 1
Индекс должен быть сдвоенным в общем.
Я в статье не правильно описал проблему, индекс то используется, только можно сказать не полноценно.
И составные индексы тут погоды не делает.
Вот explain для двух вариантов, первый для составного ключа, второй вариант для двух отдельных индексов
Второй вариант даже чуть лучше
И составные индексы тут погоды не делает.
Вот explain для двух вариантов, первый для составного ключа, второй вариант для двух отдельных индексов
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE ip2country_copy range PRIMARY PRIMARY 4 NULL 1648 Using where
1 SIMPLE ip2country_copy range PRIMARY,idn2 PRIMARY 4 NULL 1579 Using where
Второй вариант даже чуть лучше
А что именно там? Как раз запрос с вложенным SELECT который там советуют для определения страны по IP и участвует в этом тесте. Просто, есть еще два более простых запроса, хотелось наглядно показать насколько они тормозные.
Честно-говоря, не совсем понятно зачем этот sub-select вообще нужен, т.е. зачем усложнять запрос.
Когда два года назад решал эту же задачу на базе MaxMind, то обошелся
просто запросом:
SELECT * FROM ip2country WHERE `ipn1` <= INET_ATON('IP') ORDER BY `ipn1` DESC LIMIT 1
где индекс по полю `ipn1` будет использоваться как для фильтра, так и для сортировки.
Зачем вообще добавлять условие
WHERE `ipn2` >= INET_ATON('IP')
?
Когда два года назад решал эту же задачу на базе MaxMind, то обошелся
просто запросом:
SELECT * FROM ip2country WHERE `ipn1` <= INET_ATON('IP') ORDER BY `ipn1` DESC LIMIT 1
где индекс по полю `ipn1` будет использоваться как для фильтра, так и для сортировки.
Зачем вообще добавлять условие
WHERE `ipn2` >= INET_ATON('IP')
?
В таком запросе индекс не будет использоваться.
mysql> EXPLAIN SELECT code FROM `worldip` USE INDEX (PRIMARY)
WHERE `start` <= INET_ATON('8.8.8.8') AND `end` >= INET_ATON('8.8.8.8') LIMIT 1;
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
| 1 | SIMPLE | worldip | system | PRIMARY | NULL | NULL | NULL | 1 | |
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
Для такого запроса вторая часть индекса не будет использоваться никогда.
Два разных индекса в этом случае будут удобнее в том смысле, что оптимизатор сможет выбирать.
Два разных индекса в этом случае будут удобнее в том смысле, что оптимизатор сможет выбирать.
SELECT code FROM `worldip` WHERE `start` <= INET_ATON('IP') AND `end` >= INET_ATON('IP') LIMIT 1
Индекс должен быть сдвоенным в общем.
Второй сегмент индекса будет задействован в случае, если на первый наложено условие по равенству, а в вашем случае это не так, будет скан диапазона по первому полю от минимальных значений до искомого IP, и чем больше значение INET_ATON('IP'), тем хуже.
структура mysql базы необязательно должна быть такой:
можно хранить 1.1.1.0\24, и запрос тогда будет совсем другим.
можно хранить 1.1.1.0\24, и запрос тогда будет совсем другим.
Не очень представляю как в таком случае сделать быструю выборку.
Вы не правильно их готовите.
Вы пробуете искать в базе по открытому интервалу, те в начале ищем ВСЕХ левее, потом ВСЕХ правее. Потом пересекаем.
А можно и проще.
Вариант 1 — WHERE ip1<$ip ORDER BY ip1 DESC LIMIT 1.
Потому что нет пересекающихся регионов, есть вложенные.
Это это открытый интервал.
Найдем максимальную ширину IP адреса. те MAX(ip2-ip1). В зависимости от базы это значение разное, но вообще — не более 32к те /16
Вариант 2 — WHERE ip1 between ($ip-$maxWidth) and $ip ORDER BY ip1 DESC LIMIT 1.
Таким образом поиск производиться в закрытом диапазоне.
Также есть вариант когда у нас составной индекс, и можно искать как WHERE (ip1>$1 and ip2<$2) and(ip1<$ip and ip2>$ip) еще более ограничивая вариативность операций в базе.
Вы пробуете искать в базе по открытому интервалу, те в начале ищем ВСЕХ левее, потом ВСЕХ правее. Потом пересекаем.
А можно и проще.
Вариант 1 — WHERE ip1<$ip ORDER BY ip1 DESC LIMIT 1.
Потому что нет пересекающихся регионов, есть вложенные.
Это это открытый интервал.
Найдем максимальную ширину IP адреса. те MAX(ip2-ip1). В зависимости от базы это значение разное, но вообще — не более 32к те /16
Вариант 2 — WHERE ip1 between ($ip-$maxWidth) and $ip ORDER BY ip1 DESC LIMIT 1.
Таким образом поиск производиться в закрытом диапазоне.
Также есть вариант когда у нас составной индекс, и можно искать как WHERE (ip1>$1 and ip2<$2) and(ip1<$ip and ip2>$ip) еще более ограничивая вариативность операций в базе.
На самом деле диапазоны бывают и даже по 30 млн. к примеру (28.0.0.0-30.255.255.255 — US)
Да я и не говорил, что не могу такую выборку сделать, я имел ввиду, что она не получится быстрее запроса с вложенным SELECT.
По-поводу составного индекса, выше уже замечали, что нормально работает, если по одному из столбцов стоит равенство, в случае когда у обоих значений стоит больше/меньше, то лучше вообще индекс по одному полю строить.
Да я и не говорил, что не могу такую выборку сделать, я имел ввиду, что она не получится быстрее запроса с вложенным SELECT.
По-поводу составного индекса, выше уже замечали, что нормально работает, если по одному из столбцов стоит равенство, в случае когда у обоих значений стоит больше/меньше, то лучше вообще индекс по одному полю строить.
Добавьте пожалуйста в обзор эту базу:
www.wipmania.com/ru/base/
Там как раз нормально с индексом используется mysql
www.wipmania.com/ru/base/
Там как раз нормально с индексом используется mysql
Там просто объединенный индекс, он работает так же как два индекса отдельных. Я в статье несколько неправильно сформулировал насчет индекса. Сейчас подправлю.
UFO just landed and posted this here
А если таблицу в MySQL уже отсортированной хранить? Если использовать в MySQL таблицы в памяти?
Если памяти достаточно и буфера настроены так, как полагается — тогда innodb и так будет держать всё в памяти. Сортировка есть в индексах, а вы предлагаете по какому полю её хранить сортированной?
По ipn1, тогда в subquery не потребуется сортировка.
Сортировка не потребуется, если субд будет знать, что сортировка уже есть. А без order by порядок ничем не гарантируется.
Что-то не понял вашу мысль.
Основная идея: чем хранение таблицы в отсортированном состоянии поможет? Какую операцию это упростит?
Очевидно же: уйдёт сортировка по полю в подзапросе.
Не уйдёт — субд не гарантирует порядок в резалтсете без указания сортировки.
Оптимизация, способ хранения данных на диске, кеширование и прочее вполне могут всё испортить.
Оптимизация, способ хранения данных на диске, кеширование и прочее вполне могут всё испортить.
Вы это сами придумали или в документацию всё-таки посмотрели?
dev.mysql.com/doc/refman/5.1/en/alter-table.html
ORDER BY enables you to create the new table with the rows in a specific order. Note that the table does not remain in this order after inserts and deletes. This option is useful primarily when you know that you are mostly to query the rows in a certain order most of the time. By using this option after major changes to the table, you might be able to get higher performance. In some cases, it might make sorting easier for MySQL if the table is in order by the column that you want to order it by later.
dev.mysql.com/doc/refman/5.1/en/alter-table.html
WHERE `ipn1` <= INET_ATON('IP') ORDER BY `ipn1` DESCДля этого вложенного запроса индекс по `ipn1` разрулит и сортировку.
Что именно вы хотите улучшить, убрав сортировку и добавив указанный выше костыль?
Он «разрулит» сортировку не каким-то магическим образом. Это работа, менее серьёзная, но работа. «Костыль», как вы изволили выразиться, призван избавить MySQL от этой работы. Конечно, у него есть недостатки (описанные в документации выше), поэтому он применяется для данных, которые меняются редко (как списки geoip).
С чем вы пытаетесь поспорить, я не понимаю.
С чем вы пытаетесь поспорить, я не понимаю.
«менее серьёзная, чем сортировка таблицы, но работа»
Отнюдь нет, он НИКАКОЙ работы производить не будет.
`WHERE `ipn1` <= INET_ATON('IP')` — для этого условия мы в дереве находим первый ряд, для которого условие истинно (поиск в B-Tree, LogN)
`ORDER BY `ipn1` DESC` — по индексу мы будем идти от больших к меньших (mysql не поддерживает desc, так что всегда именно так)
`LIMIT 1` — берём первый ряд (тот самый, который мы уже нашли в шаге 1)
никакой дополнительной работы тут нет. Сортировка тут несёт декларативную задачу, просто подсказывая в какую сторону отсчитывать ряды.
С чем я пытаюсь поспорить — с тем, что ваше предложение имеет хоть какую-то практическую пользу
`WHERE `ipn1` <= INET_ATON('IP')` — для этого условия мы в дереве находим первый ряд, для которого условие истинно (поиск в B-Tree, LogN)
`ORDER BY `ipn1` DESC` — по индексу мы будем идти от больших к меньших (mysql не поддерживает desc, так что всегда именно так)
`LIMIT 1` — берём первый ряд (тот самый, который мы уже нашли в шаге 1)
никакой дополнительной работы тут нет. Сортировка тут несёт декларативную задачу, просто подсказывая в какую сторону отсчитывать ряды.
С чем я пытаюсь поспорить — с тем, что ваше предложение имеет хоть какую-то практическую пользу
По умолчанию в MySQL нет никакой сортировки. Сортировка будет только тогда, когда мы в запросе напишем ORDER BY.
Прошу прощения, это должен был быть ответ к этому комментарию
По-умолчанию — нет. Можно добиться, чтобы была.
Спасибо, отличный инструмент.
А тоже самое, но уже с точностью до города?
А тоже самое, но уже с точностью до города?
UFO just landed and posted this here
ежу понятно, что древовидные алгоритмы в разы быстрее линейных.
сам как-то писал велосипед по определению города по IP
а алгоритме использовался RBTree с ключом IPmin в котором лежала структура: IPmax, CityId
Тестирование показывало отличные результаты (по Городам RF, BY, UA) но база занимала много памяти
Была идея использовать его в качестве модуля для nginx
к сожалению инвестор решение отверг и я переключился на реализацию других проектов
сам как-то писал велосипед по определению города по IP
а алгоритме использовался RBTree с ключом IPmin в котором лежала структура: IPmax, CityId
Тестирование показывало отличные результаты (по Городам RF, BY, UA) но база занимала много памяти
Была идея использовать его в качестве модуля для nginx
к сожалению инвестор решение отверг и я переключился на реализацию других проектов
Автор, скоро уже PHP 6 выйдет, а вы еще в PHP4 стиле пишите. А за обзор спасибо.
Как не ухищряйся, а быстрее памяти не прыгнешь, так что все равно в чем хранить и как выбирать.
Самое главное формат хранения адресов.
Самое главное формат хранения адресов.
Я бы предложил свести поиск к
select country from table where table.ip>= '11.22.33.44' order by table.ip limit 1
ну и кластерный индекс по ip, храинть конец диапазона.
select country from table where table.ip>= '11.22.33.44' order by table.ip limit 1
ну и кластерный индекс по ip, храинть конец диапазона.
А с PostgreSQL не пробовали тесты проводить? У них есть расширение ip4r, которое достаточно шустро ищет по IP.
UFO just landed and posted this here
Сам не так давно возился с базами геотаргетинга.
Было бы интересно, если бы автор рассказал про свой формат бинарной базы.
Когда я пытался воссоздать бинарную базу GeoIPCity, то смог сделать это по алгоритму с этой страницы Compressing dictionaries with a DAWG.
Ну а про скорость, php — странное решение в вопросах скорости. У того же MaxMind есть C-API и доступ к нему из PHP. Я вот взял питоновскую обёртку вокруг С-API и получил скорость 310 000 запросов в секунду, а ваш тест 50 000.
P.S. Кстати у вас ошибка в sxgeo_bench.php, неправильно указано имя класса
Было бы интересно, если бы автор рассказал про свой формат бинарной базы.
Когда я пытался воссоздать бинарную базу GeoIPCity, то смог сделать это по алгоритму с этой страницы Compressing dictionaries with a DAWG.
Ну а про скорость, php — странное решение в вопросах скорости. У того же MaxMind есть C-API и доступ к нему из PHP. Я вот взял питоновскую обёртку вокруг С-API и получил скорость 310 000 запросов в секунду, а ваш тест 50 000.
P.S. Кстати у вас ошибка в sxgeo_bench.php, неправильно указано имя класса
О формате еще напишу, если будет многим интересно. В дальнейшем также думаю выложу скрипт для конвертирования, пока сыроват, и еще в доработке.
Что касается PHP, это просто мой основной язык, потому на нем привычнее. Но думаю потом вполне можно портировать на другие языки, алгоритм довольно простой.
P.S. Спасибо ошибку поправил.
Что касается PHP, это просто мой основной язык, потому на нем привычнее. Но думаю потом вполне можно портировать на другие языки, алгоритм довольно простой.
P.S. Спасибо ошибку поправил.
нас (wipmania) много спрашивали базу в бинарном формате, но сделать свой — руки не доходили, можно ли пользовать ваш? Тогда следующие базы выложим дополнительно и в этом виде.
У нас есть база в бинарном виде, но она для модуля geoip из xtables-addons для iptables.
У нас есть база в бинарном виде, но она для модуля geoip из xtables-addons для iptables.
Да конечно, в планах популяризировать формат.
Вот конвертнул базу WIPmania в формат SxGeo можно потестить.
Вот конвертнул базу WIPmania в формат SxGeo можно потестить.
Автору однозначно плюс за то, что поделился создал качественный продукт и поделился им.
Скажите, пожалуйста, а как можно сконвертировать базу от MaxMind, например, в формат вашей базы? В статье не нашёл. Спасибо
Скажите, пожалуйста, а как можно сконвертировать базу от MaxMind, например, в формат вашей базы? В статье не нашёл. Спасибо
Пока, что скрипт конвертилки не выкладываю в открытый доступ, т.к. еще планируется доделать работу с базами для городов, и он в очень девелоперском состоянии, стрёмно выглядит. Если интересно могу сгенерить бинарник по любой другой базе, кидайте в личку.
А вообще планируете выкладывать? Базы то постоянно обновляются. Каждый раз не хотелось бы вас дёргать :)
Стрёмно выглядит — выкладывайте на гитхаб и принимайте пулл-реквесты. Социальное программирование оно такое :-)
(Не иронизирую, на самом деле так и есть — чем раньше продукт в любом состоянии появится на публике — тем раньше получит полезный фидбэк)
(Не иронизирую, на самом деле так и есть — чем раньше продукт в любом состоянии появится на публике — тем раньше получит полезный фидбэк)
нужна версия на С и перекодировщик из других форматов в ваш, иначе в реально высоконагруженом проекте не имеет применения
совершенно некорректно сравнивать БД и специальные программные средства — работающие в памяти
для начала посмотрите как именно работает between в MySQL, в статье как раз показано как делать такое на БД
habrahabr.ru/blogs/mysql/125467/
извинияюсь что ссылка на мой пост — зато на хабр.
А второе засуньте все индексы и таблицы в кэш и посмотрите на скорость — поверьте она вас приятно удивит (10000/sec для MySQL это далеко не предел)
для начала посмотрите как именно работает between в MySQL, в статье как раз показано как делать такое на БД
habrahabr.ru/blogs/mysql/125467/
извинияюсь что ссылка на мой пост — зато на хабр.
А второе засуньте все индексы и таблицы в кэш и посмотрите на скорость — поверьте она вас приятно удивит (10000/sec для MySQL это далеко не предел)
Почему это сравнивать некорректно? Я сравнивал решения, которые часто встречаются в инете и применяют для одной и той же задачи. У меня не стояло задачи добиться максимальной производительности каждого из вариантов.
Из спортивного интереса набросал тест, делающий выборку стран по случайным IP из массива в памяти — получилось около 10000000 IP/sec. Подозреваю, что основное влияние на результаты оказал собственно скрипт тестирования.
На каком языке этот тест был? Железо же тоже отличается.
Delphi 7, Core i3 2120 в одном потоке. Это не php, но раз тестируется скорость — полезно для понимания результатов. Было интересно почему такие маленькие цифры.
Ну это уже видимо издержки скриптовых языков с динамической типизацией, ради интереса попробовал загнать базу полностью в массив, прибавка получилась 20%, но и памяти больше жрёт.
Интересно будет портировать SxGeo, на какой-нибудь компилируемый язык.
Интересно будет портировать SxGeo, на какой-нибудь компилируемый язык.
Если я не ошибаюсь, то автор определяет по диапазону ip, а вы по ключу в массиве, что конечно быстрей, но вам придется тогда хранить вообще все ip в этом массиве, что лишено смысла.
Понравилась статья, все подробно описано, а главное, т.е. вывод — просто няшка, ничего не навязывается, а хочется сразу взять и даже не тестировать, а уже использовать.
Конечно понятно, что чем больше IP/сек, тем меньше ресурсов сервера используется. Но меня интересует вопрос с другой стороны. Сколько IP/сек может потребоваться огромному сайту (гугл, фэйсбук или что-то такое)? Ведь для каждого пользователя это нужно определить только в редких случаях. Например, при первом входе, на этапе регистрации или при смене его места нахождения (гео-сервисы). Как мне кажется, этот максимум получится не таким и большим, например, 10 000 IP/сек
zapimir, а Вы можете выложить скрипт-конвертер GeoIP->SxGeo? Хочется иметь возможность переодически «освежать» базу, не завися от графика выхода новых версий.
Порадовала молниеносная скорость даже на SXGEO_FILE.
Теперь о пожеланиях: хотелось бы видеть список стран в виде полного названия, а не только двухбуквенного кода. Вообщем-то, можно добавить файл с определением массива, вроде такого $sxgeoCountries = array('EN' => 'England', 'RU' => 'Russia', 'US' => 'United States'). На этой странице было бы неплохо повесить черные tooltip'ы на флажки: driversworld.us/app/user/profile/?id=1
Теперь о пожеланиях: хотелось бы видеть список стран в виде полного названия, а не только двухбуквенного кода. Вообщем-то, можно добавить файл с определением массива, вроде такого $sxgeoCountries = array('EN' => 'England', 'RU' => 'Russia', 'US' => 'United States'). На этой странице было бы неплохо повесить черные tooltip'ы на флажки: driversworld.us/app/user/profile/?id=1
А что на счёт mod_geoip?
На сайте есть сравнение, если я правильно понял, то разница между PHP и C API колоссальная www.maxmind.com/app/benchmark
И ещё такой момент, у вас используется небольшая GeoIP Country. Работают ли ваши графики так же со 150-мегабайтной базой GeoIPOrg?
На сайте есть сравнение, если я правильно понял, то разница между PHP и C API колоссальная www.maxmind.com/app/benchmark
И ещё такой момент, у вас используется небольшая GeoIP Country. Работают ли ваши графики так же со 150-мегабайтной базой GeoIPOrg?
На тему скорости определения принадлежности IP к некоему IP range пробегал в интернетах замечательный пост: nponeccop.livejournal.com/225261.html
и вдогонку к нему: swizard.livejournal.com/177303.html
и вдогонку к нему: swizard.livejournal.com/177303.html
Определять то надо не 10000 ip за один запуск. А по 1 ip 10000 раз! А это значит открывать и считывать файл не 1 раз а 10,000. И соответственно совсем другие цифры.
Решение на С держит все в памяти (т.к. работает в фоне). Скрипт же на РНР вынужден считывать каждый раз заново.
Хотя за скрипт в целом большое спасибо!
Решение на С держит все в памяти (т.к. работает в фоне). Скрипт же на РНР вынужден считывать каждый раз заново.
Хотя за скрипт в целом большое спасибо!
Тут тестировались алгоритмы, так что пропорции на других языках будут близкими, ничто не мешает мой алгоритм переписать на Си.
Тут так же как с алгоритмами поиска, поиск перебором, будет всегда медленнее бинарного поиска, независимо от языка.
Тут так же как с алгоритмами поиска, поиск перебором, будет всегда медленнее бинарного поиска, независимо от языка.
спасибо за минус в карму.
все таки на хабре в основном душевно больные люди с комплексами
все таки на хабре в основном душевно больные люди с комплексами
С чего это мне минусы Вам ставить, еще и в карму? Не страдаю подобным.
Извините, я редко тут чтото пишу, но именно после комментария к вашему топику карма упала еще на один пункт.
По сабжу — реально не хватает скрипта для перевода MindMax в ваш формат. Уже подумываю о том чтобы переписать ваш алгоритм как РНР-расширение
По сабжу — реально не хватает скрипта для перевода MindMax в ваш формат. Уже подумываю о том чтобы переписать ваш алгоритм как РНР-расширение
Скрипт для конвертации будет, как и подробное описание формата. Формат будет открытым и универсальным (универсальным в том плане, что можно свои данные хранить в БД).
Я уже сделал новую версию с поддержкой как стран, так и городов, работает в 4-5 раз быстрее GeoIP.
Сейчас готовлю к запуску сайт (на этой неделе запустим), на котором будет и документация, и свежие базы данных. В том числе будет собственная БД, так как в GeoLite City куча мусора и неточностей.
Так что пока с PHP-расширением лучше подождать.
P.S. Карму плюсанул ;)
Я уже сделал новую версию с поддержкой как стран, так и городов, работает в 4-5 раз быстрее GeoIP.
Сейчас готовлю к запуску сайт (на этой неделе запустим), на котором будет и документация, и свежие базы данных. В том числе будет собственная БД, так как в GeoLite City куча мусора и неточностей.
Так что пока с PHP-расширением лучше подождать.
P.S. Карму плюсанул ;)
Спасибо! Не за карму конечно, а за работу над вашим проектом. Сейчас пишем баннерку, скорее всего в ней придётся использовать ваше решение т.к. нагрузки будут большие.
PS до вчерашнего дня у нас использовались запросы с where ip_min={$ip}
— до прочтения этого топика не задумывался о том какие они на самом деле тормозные)
PS до вчерашнего дня у нас использовались запросы с where ip_min={$ip}
— до прочтения этого топика не задумывался о том какие они на самом деле тормозные)
Sign up to leave a comment.
Определение страны по IP: тестируем скорость алгоритмов