В качестве расширения своего предыдущего предложения — оптимизация для сужения множества поиска.
Откинем булевские атрибуты, считая их целочисленными для универсальности.
Имеем атрибуты A1, A2… An. Каждый из этих атрибутов имеет некоторый диапазон значений.
Для каждого атрибута разбиваем соответствующий диапазон на k_i кусков, каждый из которых обозначим через Ai_1, Ai_2...Ai_k_i.
Далее, имеем множество всех объектов ALL с упомянутыми атрибутами.
Возьмем атрибут A1 и разобьем множество ALL на непересекающиеся подмножества ALL_A1_j, где 1 <= j <= k_1, такие, что ALL_A1_j содержит объекты, у которых значение атрибута A1 находится в диапазоне A1_j.
Далее, с каждым этим подмножеством производится аналогичное разбиение по атрибуту A2. Потом каждое подмножество разбивается по значениям атрибута A3 и так далее до An.
Таким образом имеется дерево разбиения множества ALL по диапазонам значений всех атрибутов.
Теперь, можно считать, что при поиске заданы желаемые диапазоны для всех атрибутов: если какой-то атрибут при поиске не указан, значит желаемым диапазон — множество всех значений атрибута.
Для каждого атрибута Ai в начале отбираются такие диапазоны Ai_k, которые пересекаются с желаемым.
После этого делается обход по дереву разбиений в глубину: то есть, начиная от корня ALL идем в ALL_A1_k1, из которого в ALL_A1_k1_A2_k1 и так далее, пока не получим некоторое подмножество объектов, из которых линейным образом отбираются нужные, после этого возвращаемся на шаг назад и идем дальше.
В худшем случае, обход по дереву разбиений может иметь линейную сложность, а по факту, чуть хуже, чем простой линейный перебор.
Но при удачном выборе порядка атрибутов и диапазонов разбиений круг поиска может уменьшиться во много раз (вплоть до вырожденного случая, когда параметрам поиска будет соответствовать строго одно подмножество, которое находится за константное время).
