Здравствуйте, _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), что делает их неприемлемыми для шибко динамических данных (а у тебя, как я понимаю, именно такой случай).