Делаю серверный спам-фильтр. Алгоритм анализа сообщений уже отработан, но вот возникла проблема с длительной работой.
В общих чертах, система выглядит так:
На вход поступает сообщение, для него считается набор коэффициентов, потом эти коэффициенты сравниваются с уже рассчитанными для других, пришедщих ранее сообщений. Если по выбранному критерию коэффициенты текущие совпадают с коэффициентами, имеющимися в списке — сообщение считается повтором, помечается как подозрительное на спам и его коэффициенты далее не учитываются. Если же совпадение не отмечено — коэффициенты заносятся в список и сообщение считается оригиналом.
Все коэффициенты хранятся в одной таблице:
CREATE TABLE CoefLst(
[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
Coef1 float NOT NULL,
Coef2 float NOT NULL,
...
...
CoefN float NOT NULL,
AddDate datetime DEFAULT (getdate()) NOT NULL,
ParentID int NULL
)
Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".
Критерий сравнения таков:
IF
((CurrCoef1 >= Coef1 - @Delta) and (CurrCoef1 <= Coef1 + @Delta)) and
((CurrCoef2 >= Coef2 - @Delta) and (CurrCoef2 <= Coef2 + @Delta)) and
...
((CurrCoefN >= CoefN - @Delta) and (CurrCoefN <= CoefN + @Delta))
SET @RESULT = 'SPAM'ELSE SET @RESULT = 'NOT SPAM'
Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.
Как это можно исправить?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду. __>Как это можно исправить?
Никак не исправишь. Такой уж ты алгоритм придумал — сравнивать каждое входящее сообщение с каждым имеющимся.
Твой алгоритм имеет сложность порядка O(n^2), где n — число сообщений в базе.
Допустим, пришло 100 сообщений и имеется 100 000 сообщений. Это нормальные такие числа. Не очень большие.
Придется сделать 10 000 000 чтений и проверок.
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, _spin_, Вы писали:
S> Вычисляй Хэш, и отбирай зписи по этому хэшу и сравнивай значения. Надо понимать,что у тебя сравниваются все записи?
Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон
Coefn +- @Delta???
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, _spin_, Вы писали:
__>Делаю серверный спам-фильтр. Алгоритм анализа сообщений уже отработан, но вот возникла проблема с длительной работой.
__>В общих чертах, система выглядит так:
__>На вход поступает сообщение, для него считается набор коэффициентов, потом эти коэффициенты сравниваются с уже рассчитанными для других, пришедщих ранее сообщений. Если по выбранному критерию коэффициенты текущие совпадают с коэффициентами, имеющимися в списке — сообщение считается повтором, помечается как подозрительное на спам и его коэффициенты далее не учитываются. Если же совпадение не отмечено — коэффициенты заносятся в список и сообщение считается оригиналом.
__>Все коэффициенты хранятся в одной таблице:
__>
__>CREATE TABLE CoefLst(
__>[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
__>Coef1 float NOT NULL,
__>Coef2 float NOT NULL,
__>...
__>...
__>CoefN float NOT NULL,
__>AddDate datetime DEFAULT (getdate()) NOT NULL,
__>ParentID int NULL
__>)
__>
__>Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".
__>Критерий сравнения таков: __>[pascal]
Логику лучше реализовывать на сервере
CREATE TRIGGER ins_rec ON [dbo].[CoefLst] FOR INSERT
AS
DECLARE @Coef1 float
DECLARE @Coef2 float
DECLARE @Coef3 float
DECLARE @id int
DECLARE @delta float
--Можно прочитать откуданибудь если хочетсяSET @delta = 0.1
DECLARE ins_rec CURSOR FOR SELECT [Coef1], [Coef2], [Coef3], [id] FROM [inserted]
OPEN ins_rec
FETCH NEXT FROM ins_rec INTO @Coef1, @Coef2, @Coef3, @id
WHILE @@FETCH_STATUS = 0
BEGIN
IF EXISTS (SELECT [id] FROM CoefLst
WHERE (@Coef1 BETWEEN ([Coef1] - @delta) AND ([Coef1] + @delta)) AND
(@Coef2 BETWEEN ([Coef2] - @delta) AND ([Coef2] + @delta)) AND
(@Coef3 BETWEEN ([Coef3] - @delta) AND ([Coef3] + @delta)) AND
[id] <> @id --Запись кот. проверяется на спам уже в таблице
--Но в случае спама удалится при откате
)
BEGIN
ROLLBACK TRANSACTION
RAISERROR ('Error: ins_rec Спам', 15, 1)
RETURN
END
FETCH NEXT FROM ins_rec INTO @Coef1, @Coef2, @Coef3, @id
END
CLOSE ins_rec
DEALLOCATE ins_rec
GO
__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.
Сейчас на порядок быстрее и будет зависеть от скорости сервера
__>Как это можно исправить?
Твоё задание в качестве факультатива
Подсказки:
для начала:
CREATE TABLE CoefLst(
[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
Coef float NOT NULL,
CoefType int NOT NULL,
AddDate datetime DEFAULT (getdate()) NOT NULL,
ParentID int NULL
)
затем добавить индекс на Coef и переписать запрос в тригере.
Re: [MSSQL] Как будет быстрее?
От:
Аноним
Дата:
25.01.06 10:49
Оценка:
Здравствуйте, _spin_, Вы писали:
как вариант — иметь две таблицы для оригиналов и для спама:
в таблице оригиналов иметь уникальный индекс по полям коэфициентов, если индекс срабатывает помещать в таблицу спамов.
Здравствуйте, _spin_, Вы писали:
__>Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".
__>Критерий сравнения таков: __>
__>IF
__>((CurrCoef1 >= Coef1 - @Delta) and (CurrCoef1 <= Coef1 + @Delta)) and
__>((CurrCoef2 >= Coef2 - @Delta) and (CurrCoef2 <= Coef2 + @Delta)) and
__>...
__>((CurrCoefN >= CoefN - @Delta) and (CurrCoefN <= CoefN + @Delta))
__>SET @RESULT = 'SPAM'
__>ELSE SET @RESULT = 'NOT SPAM'
__>
__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.
__>Как это можно исправить?
1. Написать все в человеческом виде:
select id from CoefLst where
Coef1 between @coef1 - @delta and @coef1 + @delta
AND
Coef2 between @coef2 - @delta and @coef2 + @delta
AND
Coef3 between @coef3 - @delta and @coef3 + @delta
...
И никаких курсоров, тем более на клиенте!
2. Сделать индекс по Coef1, Coef2, Coef3...
Можно даже кластерный, т.к. эти значения со временем не изменяются.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Igor Trofimov, Вы писали:
iT>Никак не исправишь. Такой уж ты алгоритм придумал — сравнивать каждое входящее сообщение с каждым имеющимся. iT>Твой алгоритм имеет сложность порядка O(n^2), где n — число сообщений в базе. iT>Допустим, пришло 100 сообщений и имеется 100 000 сообщений. Это нормальные такие числа. Не очень большие. iT>Придется сделать 10 000 000 чтений и проверок.
iT>Короче, меняй алгоритм.
А как работают другие антиспамовые фильтры? Даже элементарные на основе списка адресов спамеров?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Serginio1, Вы писали:
S> Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон S>Coefn +- @Delta???
Суть в том, что критерий сравнения — "K из N". Т.е. необходимо, чтобы совпало только K коэффициентов из N, где N — общее число коэффициентов для текущего файла. Поэтому способ использовать BETWEEN я пока не придумал. Или под диапазонами имелось ввиду что-то другое, не between?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Использовать триггер с курсором на милионах записей — не самое удачное решение. Необходима скорость обработки не ниже 30 сообщений в секунду.
A>Сейчас на порядок быстрее и будет зависеть от скорости сервера
Сервер будет мощный, сейчас всё испытывается на 2х хьюлетовских друхпроцессорных рабочих станциях.
A>Твоё задание в качестве факультатива
A>Подсказки:
A>для начала:
A>
A>CREATE TABLE CoefLst(
A>[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
A>Coef float NOT NULL,
A>CoefType int NOT NULL,
A>AddDate datetime DEFAULT (getdate()) NOT NULL,
A>ParentID int NULL
A>)
A>
Добавляет сложностей с получением значения критерия отбора "K из N". Тип коэффициента всегда один, имеет значение его номер. Плюс такое изменение таблицы увеличивает количество записей в 20 с лишним раз. И из 10 миллионов мы получим 200. Не многовато ли? У меня сейчас есть базы, в которых более 500 млн.записей и работать с ними достаточно сложно.
A>затем добавить индекс на Coef и переписать запрос в тригере.
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Здравствуйте, Sinclair, Вы писали:
S>1. Написать все в человеческом виде: S>
S>select id from CoefLst where
S> Coef1 between @coef1 - @delta and @coef1 + @delta
S>AND
S> Coef2 between @coef2 - @delta and @coef2 + @delta
S>AND
S> Coef3 between @coef3 - @delta and @coef3 + @delta
S>...
S>
Красиво, согласен, но вот реализовать K из N? Т.е. считать сообщение спамом только если из N коэффициентов в соответствующие диапазоны попало K.
Я пока такого способа не придумал. Может есть свежие мысли?
S>И никаких курсоров, тем более на клиенте!
И не планировал
S>2. Сделать индекс по Coef1, Coef2, Coef3... S>Можно даже кластерный, т.к. эти значения со временем не изменяются.
Есть, только не кластерные.
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Здравствуйте, _spin_, Вы писали: __>Красиво, согласен, но вот реализовать K из N? Т.е. считать сообщение спамом только если из N коэффициентов в соответствующие диапазоны попало K. __>Я пока такого способа не придумал. Может есть свежие мысли?
пока нет.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, _spin_, Вы писали:
__>Здравствуйте, Serginio1, Вы писали:
S>>Здравствуйте, Serginio1, Вы писали:
S>> Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон S>>Coefn +- @Delta???
__>Суть в том, что критерий сравнения — "K из N". Т.е. необходимо, чтобы совпало только K коэффициентов из N, где N — общее число коэффициентов для текущего файла. Поэтому способ использовать BETWEEN я пока не придумал. Или под диапазонами имелось ввиду что-то другое, не between?
Если К из N то достаточно сложно, что либо оптимизировать. Хотя можно на первом этапе посмотреть, есть ли вообще K Coefn входящих вдиапозон используя индексы по Coef.
Все зависит от относительной величины Delta.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, _spin_, Вы писали:
__>Использовать триггер с курсором на милионах записей — не самое удачное решение. Необходима скорость обработки не ниже 30 сообщений в секунду.
Если быть внимательным курсор только то таблице inserted т.е. по тем записям кот. вставляются, как ты иначе обработаеш вставку 100 записей?
A>>Сейчас на порядок быстрее и будет зависеть от скорости сервера
__>Сервер будет мощный, сейчас всё испытывается на 2х хьюлетовских друхпроцессорных рабочих станциях.
Попробуй у меня на более слабом сервере скорость на порядок больше приведённой выше в топике.
__>Добавляет сложностей с получением значения критерия отбора "K из N". Тип коэффициента всегда один, имеет значение его номер. Плюс такое изменение таблицы увеличивает количество записей в 20 с лишним раз. И из 10 миллионов мы получим 200. Не многовато ли? У меня сейчас есть базы, в которых более 500 млн.записей и работать с ними достаточно сложно.
Тип коэффициента это и есть его номер в данном случае. Количество записей в таблице никого не должно смущать т.к. СКОРОСТЬ ВЫБОРКИ ЗАВИСИТ НЕ ОТ КОЛИЧЕСТВА ЗАПИСЕЙ А ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ, которые мы и повышаем: накладываем индекс на поле Coef, а затем ограничиваем выборку нижним и верхним значением коэффициента. В результате при наличии индекса сканирования всей таблицы не происходит и ты получаеш минимальную выборку а затем как следствие минимальные дальнейшие сравниения.
__>На вход поступает сообщение, для него считается набор коэффициентов, потом эти коэффициенты сравниваются с уже рассчитанными для других, пришедщих ранее сообщений. Если по выбранному критерию коэффициенты текущие совпадают с коэффициентами, имеющимися в списке — сообщение считается повтором, помечается как подозрительное на спам и его коэффициенты далее не учитываются. Если же совпадение не отмечено — коэффициенты заносятся в список и сообщение считается оригиналом.
Для таких задач лучще всего подойдут k-D деревья -- гарантированное логарифмическое время поиска.
Здравствуйте, Antipov, Вы писали:
A>Попробуй у меня на более слабом сервере скорость на порядок больше приведённой выше в топике.
Попробую, может ты и прав, но я сильно сомневаюсь.
A>Тип коэффициента это и есть его номер в данном случае. Количество записей в таблице никого не должно смущать т.к. СКОРОСТЬ ВЫБОРКИ ЗАВИСИТ НЕ ОТ КОЛИЧЕСТВА ЗАПИСЕЙ А ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ,
Где это написано? Из своего опыта могу сказать, что эту фразу лучше переделать так:
СКОРОСТЬ ВЫБОРКИ в болшей мере зависит ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ, а не ОТ КОЛИЧЕСТВА ЗАПИСЕЙ
Теоретически первая фраза верна, а вот на практике когда размер базы переваливает 500 Гб, а суммарное количество записей — 1 млрд, начинаются задержки выборки на уровне железа, т.к. резко возрастает количество seek'ов raid'а, выполняемое при отработке 1 запроса.
A>которые мы и повышаем: накладываем индекс на поле Coef, а затем ограничиваем выборку нижним и верхним значением коэффициента. В результате при наличии индекса сканирования всей таблицы не происходит и ты получаеш минимальную выборку а затем как следствие минимальные дальнейшие сравниения.
Возможно. Но реализовать мой критерий отбора на модифицированной таблице я не представляю как.
... << Scorpions — Holiday>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Hint: надо работать с N параметрами сообщения как с точкой в N-мерном пространстве с координатами (x1, x2 ... xN).
P.S. Здесь вполне можно применить и упрощенные варианты k-D деревьев, такие как quadtree и octree, если конечно распределение значений параметров более-менее линейное.
Здравствуйте, _spin_, Вы писали: __>Теоретически первая фраза верна, а вот на практике когда размер базы переваливает 500 Гб, а суммарное количество записей — 1 млрд, начинаются задержки выборки на уровне железа, т.к. резко возрастает количество seek'ов raid'а, выполняемое при отработке 1 запроса.
К сожалению, у меня нет достаточной практики для того, чтобы определить, что эффективнее — 10^6 записей с 10 полями или 10^7 записей с двумя полями.
Но в целом предложение Antipov'a выглядит достаточно привлекательно.
Дело в том, что в его случае мы можем сделать примерно так (это идея, а не конечное решение):
select message_id from coef_values where
(coef_id = @coef_id_1 and coef_value between @coef_1_value-@delta and @coef_1_value+@delta)
OR
(coef_id = @coef_id_2 and coef_value between @coef_2_value-@delta and @coef_2_value+@delta)
...
таким образом, мы получаем совпадения коээфициентов. Это можно сделать очень эффективно при помощи кластерного индекса по coef_id, coef_value — сканироваться будет минимум страниц, только фактические попадания. Должен быть index seek, а не index scan.
Теперь можно посчитать количество совпадающих коэффициентов для писем:
select count(*) as hit_count, message_id
from (/*тут наш селект, приведенный выше*/)
group by message_id
Ну, и ограничить их по количеству:
select count(*) as hit_count, message_id
from (select message_id from coef_values where
(coef_id = @coef_id_1 and coef_value between @coef_1_value-@delta and @coef_1_value+@delta)
OR
(coef_id = @coef_id_2 and coef_value between @coef_2_value-@delta and @coef_2_value+@delta)
) hits
group by message_id
having hit_count > @hit_count_threshold
Все зависит от распределения данных по hit_count. Боюсь, что более эффективный способ построить на линейных индексах не удастся.
Альтернатива только одна — рассматривать многомерные индексы. Правда, тут я тоже не очень понимаю, как правильно строить такой индекс, чтобы все было эффективно — большинство многомерных индексов нацелены на решение задачи proximity search, т.е. запросов вида
select * from point
where
X between @x_min and @x_max
AND
Y between @y_min and @y_max
AND
Z between @z_min and @z_max
Это ограничение расстояния по норме таксиста.
А нам нужен индекс для оптимизации запросов с другой нормой:
select * from point
where
(X between @x_min and @x_max AND Y between @y_min and @y_max)
OR
(Y between @y_min and @y_max AND Z between @z_min and @z_max)
OR
(Z between @z_min and @z_max AND X between @x_min and @x_max)
(это для поиска попаданий 2 из 3).
Можно попытаться изменить мат.модель так, чтобы расстояние вычислялось как-то по-другому; попытаться выразить тот факт, что для нас "близость" значений некоторого коэффициента важнее "дальности" значений другого. В твоей формуле работают "ступеньки", т.е. есть дельта, внутри которой попадание дает 1 очко, а снаружи — 0. И учитывается сумма этих очков.
Можно аппроксимировать эту ступеньку более гладкой монотонной функцией, которая равна 1 в случае точного совпадения, и 0 в случае большой разности коэффициентов; просуммировать полученные значения и их использовать в качестве расстояния.
Впрочем, я не уверен, что и это поможет. Дело в том, что лучшие из известных мне многомерных индексов могут гарантировать заполнение страниц порядка 1/(K+1) для K-мерного пространства. Это еще приемлемо для двух-трех измерений; для 10-мерного индекса расход дискового пространства будет просто кошмарным. Более компактные представления имеют время вставки порядка O(N), вместо О(logN), что делает их неприемлемыми для шибко динамических данных (а у тебя, как я понимаю, именно такой случай).
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, sch, Вы писали:
sch>P.S. Здесь вполне можно применить и упрощенные варианты k-D деревьев, такие как quadtree и octree, если конечно распределение значений параметров более-менее линейное.
Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.