sysprg Dimitry SibiryakovЕсли предыдущий приведенный мною запрос не справится, релевантность
только полная а количество критериев ограничено парой дюжин то self-join
с правильными индексами обеспечит работу влет.Предположим есть записи, характеризующиеся некоторыми атрибутами и этих записей много, как говорилось в постановке задачи - порядка 100 миллионов. Пусть пользователь хочет поискать те записи, у которых пара атрибутов строго равна указанным значениям. Вот такая простая задачка. Но при таком большом числе записей интуитивно ясно (и в проблемной области так оно и есть), что, скорее всего, найдется много записей, у которых данный атрибут равен данному значению. Скажем - 10 тысяч записей вдоль одного атрибута и 10 тысяч вдоль другого. А пересечение у них может быть очень компактным - быть может 100, а то и 10 записей! Собственно за этим пересечением и "охотится" наш пользователь, подавая запрос... На умении искать такие пересечения мы делаем деньги. :)
Как нам быстро найти пересечение, не перебирая 10 тысяч записей движением вдоль только одного атрибута? Если мы будем перебирать 10 тысяч записей двигаясь вдоль какого-то атрибута - то мы прогрузим работой весь кластер, так как (скорее всего) эти 10 тысяч записей окажутся размазанными по всем машинам кластера... Нам нужен поиск, быстро сходящийся к нужной области многомерного пространства - без подъема в память всех записей вдоль одного из атрибутов.
Ладно, это еще ничего - тут можно пересечь списки записей, которые возможно будут компактными и будут храниться на нескольких машинах. Современные базы типа DB2 и Oracle так и сделают, при наличии отдельных индексов по атрибутам. Может быть - при наличии индекса по паре {ID атрибута, значение} в Вашем примере.
Но представьте себе, что вдоль одного из атрибутов у нас 2 миллиона записей, а вдоль другого - 10 тысяч. И опять-таки пересечение между ними - в 100 записей. В этом случае пересекать списки не получится - так как один из них очень длинный (2 миллиона элементов) и наверняка он размазан по всему кластеру. Или же хранящая его машина будет перегружена работой (особенно если он "популярный" - участвует во многих запросах).
Собственно больше всего меня интересует база данных, которая умеет решать эту задачу, или алгоритм ее решения, или мысли по этому алгоритму. DB2 или Oracle, например, даже потенциально будучи интересными в плане масштабируемости, тут ничем не помогут IMHO, так как в них просто в принципе нет способов индексации адекватных этой задаче. У них только списки да bitmaps.
Атрибуты (колонки в виртуальной разряженной таблице, размерности пространства) добавляются динамически в процессе работы - поэтому классические способы индексирования встроенные в саму базу типа DB2 или Oracle тут не подходят. И никто не знает, какие пары (или, скажем, тройки) атрибутов будут интересны пользователю, чтобы заранее построить по ним объединенные индексы.
Извините за вторжение.
Долго читал этот топик и все никак не мог понять, что же конкретно хочет и ищет автор.
Но вот у него мелькнули слова "На умении искать такие пересечения мы делаем деньги" и вообще словами "анализ данных" повеяло.
Может вам нужен типа такой продукт
http://www.sybase.ru/Syb/products/databases/sybaseiq/iq_12_5.htm
И вообще, помотреть в сторону хранилищ данных и анализа, я Sybase в качестве примера привел. Это должно быть как раз то что Вам надо.
Только будьте готовы к тому , что основная работа здесь будет это именно граммотно спроектировать такое хранилище под вашу задачу.