Чернышев Андрей ЛеонидовичА почему Вы, sysprg, говорите про "индекс по одному упорядоченному набору полей" ? И не уточняете - сколько в среднем "атрибутов" имеют не пустые значения в каждой Вашей "динамической записи" ? Может всего 5 (5!=120). Проведите простейший эксперимент по поддержке n! сочетаний при индексировании "динамических записей", где n - число непустых атрибутов.
Очень мало атрибутов (единицы) присутствуют именно в каждой записи. Однако многие атрибуты заполнены у большинства записей - таких около двух десятков. Не вижу между ними разницы с точки зрения ускорения поиска (атрибут заполнен у большинства записей или он заполнен строго у всех записей).
А еще есть несколько десятков атрибутов, заполненных более чем у одного процента записей. Однако, при ста миллионах записей (прогнозируемое наполнение базы уже в первые годы работы) это означает, что несколько десятков атрибутов заданы для 1-5 миллионов записей.
Остальные же атрибуты действительно "мало популярны" - им соответствует сотня, тысяча или десятки тысяч записей (из 100 миллионов).
Если смотреть на значения атрибутов, то увы - есть такие значения, для которых объем выборки - миллионы или даже десятки миллионов записей. И эти значения будут часто фигурировать в запросах. Однако их пересечения могут быть удивительно компактны.
В качестве иллюстрации я привел вымышленный пример базы товаров для какого-нибудь "ebay" - когда, например, есть 100 тысяч медиа-товаров, в атрибутах которых значится "русский язык", есть 10 тысяч товаров, которые классифицированы как "книга" (не важно, на каком языке) и 2 миллиона товаров выставлены на продажу в городе "Нью-Йорк". Однако в Нью-Йорке выставлены на продажу всего-навсего 100 русскоязычных книг...
Но мы не знаем заранее, что заинтересует пользователя - и у нас нет заранее построенного индекса для свертки "город" * "язык" * "тип товара". Разных пользователей интересуют разные срезы...

Чернышев Андрей ЛеонидовичЧто касается "добавления атрибутов в процессе работы", то это ничего не усложняет, если всегда индексируются все сочетания. Можно подумать об "интеллекте", основанном на простых статистиках, и не индексировать "маловостребованные" сочетания (при необходимости проиндексировать). И если уж распределять нагрузку, то именно по индексированию сочетаний.Да, возможно, что динамическая и при этом автоматическая (от статистики запросов) генерация нужных индексов - это хорошая идея.
Но это не панацея - запросов будет много и они разнообразны - поэтому нужна и базисная структура, которая бы в любом случае неплохо справлялась с задачей БЕЗ дополнительных "частных" индексов. Если просто динамически строить индексы (и даже уничтожать старые по какому-нибудь LRU), то из-за разнообразия пользовательских запросов все время уйдет на генерацию этих самых индексов. И никакой памяти под них не хватит.

ВыбегаллоА по теме - интересно было бы Sybase IQ попробовать (как вам уже посоветовали), поскольку с ихним хранением данных (только ненулевых) по столбцам он очень подходит для сильноразреженных матриц.
Спасибо за советы :) и действительно Sybase IQ интересная разработка именно для таких задач.