Плоский GeoIP или диапазон в одной колонке

В опубликованной накануне (февраль, 2012) статье озаглавленной «Определение страны по IP: тестируем скорость алгоритмов» сравнивались реализации на уровне БД и нативной реализации. Мы же предлагаем рассмотреть ещё более оптимальный и простой алгоритм, который может быть реализован как в БД, так и в нативном варианте – плоские диапазоны.

Имплементация или алгоритм?

Нисколько не умаляя нативного варианта, давайте попробуем сравнивать не имплементации, а именно алгоритмы. Текущий алгоритм использует две колонки в варианте с БД и также границы диапазонов в нативном. А что если мы будем, хранить не диапазоны, а только их начальные точки? Аналогичная идея в комментах к статье уже высказана: «…Все хранить не надо, только концы диапазонов …». Ведь в этом случае поиск у нас явно ускоряется в два раза – нам надо найти только начало диапазона, в который входит значение. Тем, кто заметит, что существуют пустые диапазоны, мы ответим, что и их можно хранить: начало пустоты и значение, которое её символизирует.

Простые диапазоны или вложенные?

На рассмотренной в предыдущем примере, простом на наш взгляд, была использована GeoLite Country, у которой диапазоны не пересекаются и нет проблемы вложенных диапазонов. В более сложном случае, таком, как например российский IpGeoBase, диапазоны нещадно пересекаются и уже простыми запросами вида needle between start and end мы не обойдёмся. Но на помощь нам как раз приходит урощение алгоритма поиска!

Концепция плоских диапазонов

Давайте рассмотрим и сравним концепцию плоских диапазонов на примере с БД. Также для простоты будем рассматривать вариант поиска одного значения за раз, а не списка значений. Подзаголовок будет вопросом, а два элемента списка – ответами для обычного и плоского диапазонов.

Что это такое?

• Три колонки: start, end, value
• Две колонки: start, value

Как пустые диапазоны учитываются?

• Никак – в простом диапазоне их не требуется учитывать, так как в случае запроса на пустой диапазон вернётся ноль записей.
• Хранится начало пустого диапазона в колонке start и некое обозначение пустоты в колонке value – это может быть NULL, но и может быть 0, в том случае, если мы используем составной первичный ключ на start и value.

Насколько больше записей в итоге получается?

• В простом случае, типа GeoLiteCountry – 160222.
  В сложном, типа IpGeoBase – 39449.
  В сложном и старом типа IpGeoBase предыдущего формата, где много идущих подряд диапазонов (например, от ноября 2011 года) – 148666.
• GeoLiteCountry – 161619. Увеличение менее, чем на 1%.
  IpGeoBase – 46047. Увеличение всего на 16%.
  IpGeoBase предыдущего формата – 31156. Уменьшение на целых 80%!

Как по нему искать?

• В простом случае: needle between start and end limit 1.
  В сложном, когда у нас имеются вложенности уже надо подключать дополнительную колонку diff, которая в составном индексе будет использована и в итоге получается ужас типа: needle between start and end order by end, diff limit 1.
• Любой из случаев будет простой: neddle >= start order by start desc limit 1.

Что приходится делать БД или любому другому провадеру поиска?

• Сначала сходить в одном направлении, а потом удостовериться, что с другого направления всё хорошо. Т.е. в общем случае сделать два движения.
• Всегда идти в одном направлении.

Как его получить?

• Он уже у нас имеется – любая загрузка из файла с диапазонами geoip.
• Взять таблицу с тремя колонками и с помощью особой уличной магии преобразовать её в таблицу с тремя колонками. См. Приложение 1.

Заключение

Вы конечно спросите – а как нам преобразовать данные в плоский вид и насколько объёмы увеличатся? Отвечаем с конца: объёмы увеличатся примерно в два раза, а SQL преобразования мы ниже выложим с комментами (см. Приложение 1).
PS: Скорее всего при применении концепции плоских диапазонов в нативном варианте всё будет ещё более космически мгновенно. Просьба к тем, кто может проверить – проверить это утверждение.
PS2: Также что-то мне подсказывает, что в эру более активного IPv6, если к тому времени не будет распространены HUGEINT`ы, также весьма пригодятся плоские диапазоны, если хранение будет в виде CHAR`а.

Приложение 1. Создание плоских диапазонов на примере MySQL

Взято с github.com/garex/geoip-flat-range, а именно с github.com/garex/geoip-flat-range/blob/master/01-create-flat-range-mysql.sql

-- Create intermediate table with 3 columns
-- Change this to your columns and/or table
drop table if exists t3;
create table t3
select
    range_start f, range_end t, country_code v
    from countries_ips
;
alter table t3 add primary key (f,t,v);

-- Create target table with 2 columns and fill it with all distinct ranges borders
drop table if exists t2;
create table t2
select distinct border as f, (select max(v) from t3) as v from (
    select f-1 as border from t3
    union select f from t3
    union select t from t3
    union select t+1 from t3
) inn
order by f;
-- Here we just reset value column as it was filled by max value to have auto created column with needed type
update t2 set v = null;

-- We can add PK here, as all our range borders are unique
alter table t2 add primary key(f);

-- Adding diff column, that will help us to order ranges during main update
alter table t3 add column diff int(10) unsigned, add unique index dif_f(diff, f);
update t3 set diff = t-f;

-- Create helper table, that will help to smooth main update
drop table if exists t3diff;
create table t3diff
select distinct diff from t3 order by diff;

-- Here are our MAIN update
update t3diff, t2, t3 set t2.v = t3.v where t3.diff = t3diff.diff and t2.f between t3.f and t3.t;

-- We dont' need 'em anymore
drop table if exists t3;
drop table if exists t3diff;

-- We should remove records, that points to the same value and is one after another
alter table t2 drop primary key;
alter table t2 add column row_number int(10) unsigned not null auto_increment primary key;
alter table t2 add column next_row_number int(10) unsigned not null;
update t2 set next_row_number = row_number + 1;
alter table t2 add unique index next_row_number_v (next_row_number, v);

delete t2.* from t2, (
    select cur.row_number from t2 as cur
    join t2 prev on cur.row_number = prev.next_row_number and cur.v = prev.v    
) as inn
where t2.row_number = inn.row_number;

-- Also we dont' need first record
delete from t2 where row_number = 1;

-- Removing extra columns, that will not help us anymore
-- And also adding primary key on key and value to just always use index instead of table
alter table t2
    drop column row_number,
    drop column next_row_number,
    drop primary key,
    drop index next_row_number_v,
    add primary key (f, v)
;

-- ... And renaming target table to more human readable form
-- Change table`s/columns` names/definitions to your tables/columns
drop table if exists countries_ips_flat;
alter table t2
    rename to countries_ips_flat,
    change column f range_start int(20) unsigned not null default 0 first,
    change column v country_code varchar(2) not null default '' after range_start;

-- Comparing records count and check, that's all is ok
select
    (select count(*) from countries_ips) as default_range_records,
    (select count(*) from countries_ips_flat) as flat_range_records;