Пересечение множеств в бд - профи обосрались?!

phpdude

Сообщения: 26646 Репутация: N Группа: в ухо
Сен. 2, 2010, 8:07 д.п.
короче задачка - есть пулы ип адресов, они пересекаются, их много ~ 500 тыс строк. отсортированы в порядке уменьшения размера пула. как это дело "пересечь", то есть

например для ипа

212.45.5.198

select id,ip_from,ip_to,data1,data2,data3,ip_to-ip_from from ranges where 3559720390 BETWEEN ip_from and ip_to

108060 3559718912 3559727103 176 0 0 8191
242774 3559718912 3559727103 176 728 1001 8191
242898 3559720384 3559720391 176 728 1001 7

ну чо фабьен? обоссался?)
Спустя 220 сек.
это одноразовая операция, поэтому на скорость в принципе похуй, если будет выполняться пару минут или немногим больше)
Сапожник без сапог
artoodetoo

Сообщения: 5147 Репутация: N Группа: в ухо
Сен. 2, 2010, 8:31 д.п., спустя 24 минуты 14 секунд
Пересечения диапазонов значений, а не множеств?

Диапазоны НЕ пересекаются если
a.ip_to < b.ip_from OR a.ip_from > b.ip_to
накладываем отрицание и получаем искомое:
NOT (a.ip_to < b.ip_from OR a.ip_from > b.ip_to)
или то же самое
a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from

Для параметров $from, $to
SELECT a.id, a.ip_from, a.ip_to FROM ranges AS a WHERE a.ip_from <= $to AND a.ip_to >= $from

Самоперечечение
SELECT a.id AS aid, b.id AS bid, min(a.ip_from, b.ip_from) AS ip_from, max(a.ip_to, b.ip_to) AS ip_to FROM ranges AS a, ranges AS b WHERE a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from
ιιlllιlllι унц-унц
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 2, 2010, 8:33 д.п., спустя 1 минуту 31 секунду

artoodetoo, я чуток не это видимо имел ввиду судя по запросу, мне надо разбить всю базу на БОЛЬШЕЕ количество отрезков у которых будут концы - начала меньших подмножеств :)

то бишь если по руски было

1 .. 15
4 .. 5

станет

1 .. 4
4 .. 5
5 .. 15

:)

Сапожник без сапог
artoodetoo

Сообщения: 5147 Репутация: N Группа: в ухо
Сен. 2, 2010, 8:53 д.п., спустя 20 минут 18 секунд
ну это почти то же самое.
1) находим пересекающиеся отрезки
2) выводим четыре точки min, middle1, middle2, max
точки min и middle1, а также middle2 и max теоретически могут совпадать — дальше уже скрипт должен решать сколько здесь диапазонов: возможно от 1 до 3

я немного наврал по поводу использования min() и max() — их нельзя использовать со значениями, только как аггрегатные, вместо этого есть
LEAST() - аналог min() в PHP
GREATEST() — аналог max() в PHP
SELECT a.id AS aid, b.id AS bid, least(a.ip_from, b.ip_from) AS ip_min, greatest(a.ip_from, b.ip_from) AS ip_middle1, least(a.ip_to, b.ip_to) AS ip_middle2, greatest(a.ip_to, b.ip_to) AS ip_max FROM ranges AS a, ranges AS b WHERE a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from

Спустя 112 сек.
если надо выбрать только те пары, диапазоны, которые бьются на три — делаем условие строже
[tt]a.ip_from < b.ip_to AND a.ip_to > b.ip_from[/tt]
ιιlllιlllι унц-унц
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 2, 2010, 8:59 д.п., спустя 6 минут 18 секунд

возможно красавец)) но я уже на c# пишу утилку для этой задачки, ибо на мускуль не надеюсь))

Сапожник без сапог
artoodetoo

Сообщения: 5147 Репутация: N Группа: в ухо

Сен. 2, 2010, 9:01 д.п., спустя 1 минуту 29 секунд

не "возможно", а точно

ιιlllιlllι унц-унц
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 2, 2010, 9:15 д.п., спустя 14 минут 5 секунд

artoodetoo, возможно - потому что диапазонов вложенных бывает больше 2ух)) штук 10 может быть легко
Спустя 18 сек.
подождал минуту выполнения твоего запроса и понял что наверное безнадежно ))))))))))))))))))))))))

Сапожник без сапог
artoodetoo

Сообщения: 5147 Репутация: N Группа: в ухо
Сен. 2, 2010, 10:10 д.п., спустя 55 минут 27 секунд
добавил еще a.id < b.id в наивной попытке сократить число сравниваемых пар
SELECT a.id AS aid, b.id AS bid, least(a.ip_from, b.ip_from) AS ip_min, greatest(a.ip_from, b.ip_from) AS ip_middle1, least(a.ip_to, b.ip_to) AS ip_middle2, greatest(a.ip_to, b.ip_to) AS ip_max FROM ranges AS a, ranges AS b WHERE (a.id < b.id) AND (a.ip_from < b.ip_to AND a.ip_to > b.ip_from) ORDER BY a.id

однако!!! прикинь, если записей 1000, то необходимо сравнить где-то 1000*1000/2 диапазонов. у меня на локалхосте порядка 20сек занимает с выводом
а на 500k записях будет намного дольше :) я не вижу способа как кардинально ускорить.
ranges.zip (28)
ιιlllιlllι унц-унц
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 2, 2010, 10 д.п., спустя 23 часа 49 минут 32 секунды

а на 500k записях будет намного дольше :) я не вижу способа как кардинально ускорить.

на c# я написал мержер, который делает эту работу за 4 секунды с небольшим)

Сапожник без сапог
artoodetoo

Сообщения: 5147 Репутация: N Группа: в ухо

Сен. 2, 2010, 10:06 д.п., спустя 5 минут 55 секунд

все держит в оперативке?

ιιlllιlllι унц-унц
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 2, 2010, 10:15 д.п., спустя 9 минут 12 секунд

все держит в оперативке?
нет :)

ну это тоже конечно, просто не все пересчитывает)

Сапожник без сапог
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 3, 2010, 1:29 д.п., спустя 15 часов 13 минут 56 секунд

вы все еще используете бд?)

я написал поиск по всей этой хуйне, который в 100 раз ебет в зад мускуль :D

Спустя 33 сек.
решил не пересекать множества вообще, так и ищет несколько диапазонов

Сапожник без сапог
krasun

Сообщения: 1370 Репутация: N Группа: Джедаи

Сен. 3, 2010, 1:31 д.п., спустя 2 минуты 7 секунд

вы все еще используете бд?)

[подъеб]а как ты все это сделал без бд?[/подъеб]

Спустя 17 сек.
а почему тэг [подъеб] не работает?
phpdude

Сообщения: 26646 Репутация: N Группа: в ухо

Сен. 3, 2010, 1:32 д.п., спустя 42 секунды

а почему тэг [подъеб] не работает?

можем выписать тебе свн :)

Сапожник без сапог

Пожалуйста, авторизуйтесь, чтобы написать комментарий!

Пересечение множеств в бд - профи обосрались?!

Войти