Anton DemidovЯ вам еще раз настоятельно рекомендую освежить в памяти принципы работы bitmap индексов в Оракле или EVT индексов у DB2. Индексируйте таким образом все колонки с атрибутами и тогла БД сможет просто применяя битовые операции быстро найти необходимые пересечения.Сказу замечу, что bitmap-индексы подходят только для тех атрибутов, которые являются перечислениями (или у которых очень мало значений в реальной базе данных). Особенно хороши они для бинарных атрибутов. :) К счастью, многие атрибуты в реальном приложении будут бинарными, многие другие - перечислениями. И bitmaps для них применимы.
Однако, bitmaps не панацея и в моей задаче не помогают существенно ускорить выборки. Предположим, что у нас есть две битовых маски - на два "популярных" значения двух разных атрибутов.
В одном случае у нас есть битовая маска содержащая 10 тысяч единиц, в другом случае - 10 миллионов (при общей длине несжатой маски в 100 миллионов битов). Первую битовую маску хорошая СУБД эффективно сожмет. Вторую тоже может немножко поджать, но накладные расходы на компрессию велики и она не станет с ней заморачиваться. И вот у нас есть битовая маска длиной в 100 миллионов битов. Это 100000000 битов / 8 = ~11 мегабайтов данных.
Если ради каждого запроса мы будем считывать с диска для проверки (или для наложения по AND) эти 11 мегабайтов в каждом запросе - система не справится с нагрузкой. Если даже предположить, что эти 11 мегабайтов лежат в памяти одной машины - то все равно плохо, так как данная машина станет "бутылочным горлом" (если этот атрибут популярный и все за ним лезут к этой машине)...
Если эти 11 мегабайт поделить на страницы и размазать по кластеру - тогда ради элементарного слияния двух атрибутов мы будем дергать сотни хостов, собирая кусочки битовой карты...
Не говоря уже о том, что таких индексов для атрибута-перечисления будет несколько - по одному на каждое значение.
Так что не всегда они целесообразны и помогают.

Выбегалло2. пользователь запрашивает товар с атрибутами 1, 10 и 121. Допустим, эти атрибуты могут храниться в колонках 1, 20 и 54.А зачем нужно такое переименование? Почему атрибуты 1, 10 и 121 не хранятся прямо в колонках 1, 10 и 121? Чтобы сделать возможным хранение нескольких разных атрибутов в одной и той же колонке, если они не могут быть указаны для одного товара одновременно (в силу семантики типов товаров)? Если так, тогда я понимаю Вашу идею, иначе извиняюсь, но ничего не понял - поэтому задаю вопрос на уточнение...

ВыбегаллоПри формировании запроса приложение учитывает, в каких колонках эти атрибуты имеются, и создает SELECT * from tovar where col1 = 1 and col20 = 10 and col54=121. Уверяю вас, данный запрос при наличии индекса на каждую колонку (и up to date статистики по этому индексу) будет летать - сначала выберется наиболее избирательный индекс, затем выберется сотня строк, потом , если СУБД не позволяет использовать одновременно 2 индекса, банально проверятся значения в остальных колонках - короче, совершенно стандартная ситуация, давно и прочно отработанная.Уверяю Вас, в этой ситуации внутренне СУБД поведет себя именно так, как я неоднократно описывал - она займется пересечениями коротких списков с очень длинными (или наложениями очень длинных битмапов) и в результате мы получим неприемлемое быстродействие. К тому же в Вашей схемы Вы не учитываете, что далеко не все атрибуты бинарные, часто нас интересует не только факт наличия атрибута, но и его значение - оно задает критерий выборки.

Андрей - он же дядя Сэм1. Инвестору Вы, конечно, предоставите некий прототип подобной системы? Пусть работающий с обработкой 10 или 100 запросов в сек., но РАБОТАЮЩИЙ?У нас есть хорошо проработанная схема данных для нашего проекта, которая позволяет решить все поставленные в его рамках задачи (которые мы видим на данный момент). Но у нас пока что нет законченного технического решения для СУБД под эту схему.

Что же касается инвесторов, то не факт, что нужно привлекать в такой проект инвестиции с самого начала, отдавая кому-то часть компании. ЕСЛИ у нас получится наша задумка, то мы вообще не хотим продавать фирму, поэтому нам не все равно, кто там будет в совете директоров. :)

Андрей - он же дядя СэмНет ли такого прототипа уже сейчас? Или макета прототипа, где описана система с задачами, с картинками как это представляется в работе и т.п.?Сейчас нет необходимости в прототипе. Если это будет целесообразно, то всегда можно сделать работающий прототип, использующий предложенную тут схему entiry-attribute-value. Но это техническая сторона вопроса, кроме которой в проекте есть не менее важная идея массового сервиса, точнее группы сервисов, основанных на базе данных с такими характеристиками, как было описано.
Сервис по своей сущности задуман именно как глобальный и поэтому для меня так важно быстродействие СУБД. Мы считаем, что в этой области на рынке победит тот, кто запустит подобный сервис первым и (это важно!) не захлебнется от взрывного роста трафика.

Андрей - он же дядя Сэм2. А кого Вы представляете? Ну там юридическое лицо (фирма, НИИ и т.д.) или физическое лицо (себя лично)?Себя лично.

Андрей - он же дядя СэмЧто Вы ЛИЧНО хотите вложить это дело (в смысле какую роль видите за собой) хотя бы на первых этапах проекта?Если решение проблемы масштабируемости будет найдено, то проект, который сейчас существует как идея , превратится в проект моей маленькой startup-компании.

Чернышев Андрей ЛеонидовичПосле фантастического заявления про "хорошо проработанную схему данных", под которую не удалось подобрать СУБД, уже не удивительно почему sysprg не ответил на простой вопрос о результатах простого эксперимента.Эксперимент, о котором Вы говорите, лишен смысла. Общее представление по количеству атрибутов и разных значений этих атрибутов у нас есть и общая картина приводилась мной в процессе обсуждения. Этого достаточно.
Точная информация о распределении значений и атрибутов просто в принципе не может быть получена по простой причине - мы не можем знать этого до запуска проекта и более того, эти распределения будут существенно меняться в процессе эволюции сервиса.
Когда появляется новый информационный сервис люди начинают осваивать его и находят ему различные применения, иногда даже неочевидные для создателей сервиса. Заранее никто не может предсказать, каково будет распределение данных в подобном сервисе и главное - оно будет меняться в процессе работы и по мере роста популярности.
Просто задумайтесь на досуге над простым вопросом - могли ли создатели www.ebay.com ЗАРАНЕЕ знать, какой будет статистика наполнения базы и запросов?
Поэтому вообще не нужно закладываться на распределения значений. Той информации об общей картине, которую я Вам сообщил, достаточно для разработки архитектуры.
Далее, когда Вы говорите об объеме индексов, например, это подразумевает, что разработана какая-то модель потока запросов от пользователей. Но по условиям задачи мы не знаем характер этих запросов! Пройдет пара лет, пока такая статистика будет собрана. Строить какие-то модели бессмысленно - это интеллектуальный онанизм, который отнимет время, а модели окажутся неадекватными реальным шаблонам пользовательских запросов.
Не нужно затачиваться ни на что, кроме общей схемы. Нужно общее решение задачи быстрой выборки из разряженного, но очень многомерного пространства. Не идеальное, но ОПТИМАЛЬНОЕ решение этой задачи.
Как я понимаю, Вы ничего предложить по этой теме не можете?

pavelvpБитовые индексы очень хорошо сжимаются - в десятки раз - простыми алгоритмами.Согласен, они хорошо сжимаются простыми алгоритмами, но только в двух случаях - или если они разряженные, или если распределение единиц там далеко от случайного. Чтобы сделать его не случайным, нужно отсортировать записи в базе данных по тому атрибуту, для которого мы строим битовую маску или же должна быть четко выраженная корреляция между первичным ключом, по которому отсортированы записи, и нашим атрибутом. Атрибутов много, а первичный ключ один, большинство атрибутов с ним четкой корреляции не имеют, поэтому битовая маска будет "случайной". Если там сопоставимое количество единиц и нулей, то разряженной ее не назовешь. Эффективно сжать такие маски можно только компрессией общего вида, из которых наиболее эффективной по скорости будет какая-нибудь адаптация методов семейства LZ к двоичному алфавиту. Это не будет быстро работать и поэтому никем не используется на практике для on-line транзакций, насколько мне известно. Простые же методы компрессии хорошо жмут только сильно разряженные битовые маски.

pavelvpВы считаете, что накладные расходы на межузловой трафик будут меньше, чем расходы на сжатие/распаковку битмапа?Даже если эту битовую маску идеально сжать самым совершенным методом, то в моем примере она займет в сжатом виде ~2.4 мегабайта. Пересекать битовые маски такого размера в каждом запросе - согласитесь будет накладно по быстродействию даже при десятках тысяч запросов в секунду, о сотнях же тысяч запросов в секунду не может быть и речи при разумной стоимости железа.

pavelvpВы пускаетесь в пространные рассуждения по поводу многомерных пространств, но при этом создаётся в печатление абсолютного непонимания элементарных вещей (например R-деревья и т.п. в Вашей задаче неприменимы вовсе не по причине взрыва размерности...).Во-первых, R-деревья это отнюдь не тривиальные вещи, во-вторых, для моей задачи они не подходят именно из-за "взрыва размерности" - как показали различные исследования, эта структура при размерности в районе 5-6 проигрывает полному перебору.

pavelvpС одной стороны Вы говорите о распределённой системе, но при этом постоянно что-то куда-то хотитете перекачать в немерянных объёмах...Наоборот, я не хочу ничего перекачивать в немерянных объемах, и именно поэтому мне нужна структура индекса, которая быстро выходит на нужную область пространства. Качать в немерянных объемах мне придется при традиционном подходе (с индексами по отдельным атрибутам или с индексом по классическому разложению в модели EAV).

pavelvpКогда же речь заходит о "распределении" нагрузки, Вам это снова не нравится - как так все узлы нагружать, нехорошо! Так что Вы хотите?Наоборот, я за распределение нагрузки - только за такое, которое O(размер выборки), а не O(количество узлов).

shuklinИзвините что вмешуюсь, но не во всех движках. В Cerebrum "колонок" в "таблице" может быть до 2х млрд. Это в текущей версии. Добавлять аттрибуты к записи можно независимо от наличия "колонок" в "таблицах". Одну и ту же запись можно держать одновременно в разных таблицах и иметь для нее разные колонки соответсвенно для каждой таблицы. и тд. и тп...Согласен с Вами, что от терминологии таблиц вообще целесообразно отказаться в таких задачах (и в плане реализации таблицы тоже не лучшая идея), но для описания постановки задачи или при реализации поверх существующих СУБД можно пользоваться и табличной терминологией.

pavelvpЧто значит быстро? Каковы Ваши критерии? Миллион запросов в секунду - это не критерий...Идеальное решение - это время порядка O(m*ln(N)), где m - это объем окончательного результата выборки, N - количество записей в базе данных.
Решения, основанные на индексах по отдельным атрибутам, дают в плохом случае время пропорциональное O(d*N*ln(N)), где d - это размерность подпространства выборки.
Вдоль отдельно взятого атрибута у нас могут быть выбраны практически все записи в неудачном случае - поэтому в формуле фигурирует "N". Поэтому при плохом стечение обстоятельств результат даже хуже, чем O(N), то есть хуже полного перебора.
Меня это не устраивает, значит, нужно что-то промежуточное между идеальным решением и "классическим" - но ближе к идеальному.

Чернышев Андрей ЛеонидовичДля простого эксперимента, который легко провести, не нужна никакая "точная информация о распределении значений и атрибутов".В таком эксперименте вообще нет необходимости, потому, что его результаты могут быть получены просто через несложные выкладки на бумаге при знании устройства индексов в СУБД.

Чернышев Андрей ЛеонидовичВаши отвлеченные рассуждения о "какой-то модели потока запросов" и т.п. противоречат Вашим ключевым высказываниям:
1) "схема данных хорошо проработана" (уже !);
2) "мне нужна структура индекса, которая быстро выходит на нужную область пространства.
Структура индекса, с которой давно можно было провести простейший эксперимент на любых мыслимых и не мыслимых "объемах", не просто "быстро выходит на область", а сразу выдает результат (при "отсечениях" - "быстро выходит на область").Если я построю превышающее число атомов во Вселенной количество индексов (все неупорядоченные сочетания по 5 злементов из 1000), тогда - да, а иначе Ваше предложение вообще бесполезно. Или Вы имеете ввиду не то, что описали.

AAron sysprgОднако, при ста миллионах записей (прогнозируемое наполнение базы уже в первые годы работы) ... зачем Вам 1000-нодовый кластер для хранения 100млн. записей???Не для хранения, но для скорости обработки запросов. 1000 процессоров это как ни крути намного больше, чем возможности самой лучшей SMP-системы, у которой еще и память общая - и так как на 200 гигабайт никакого L1-L3 кэша не хватит, то эта память - бутылочное горло всей системы. Вообще мне сложно понять, зачем (кроме аргумента традиций и больших наработок) сейчас нужны машины с 64 CPU, когда намного быстрее будет работь 64 CPU каждый со своей индивидуальной полноценной памятью (отдельной шиной и модулями памяти) и быстрым интерконнектом (Infiniband, etc). Просто видимо кластера делать не умеют хорошо на уровне софта СУБД. :)

AAronСколько это будет в ГБ? 10? 20? 100? Ну скажем, 200. Ну и купите себе 200ГБ ОЗУ...Собственно данных около 200ГБ и будет, не считая индексов и blob. Через пару-тройку лет конечно, не сразу.

AAronу меня в месяц данных 250-300млн. приходит... а тут - первые годы. У других, еще больше.Я имею ввиду данные, требующие оперативной обработки в задачах поиска, в реальном времени. Хранилище данных для особых специальных нужд и истории - это отдельная задача, но там не так критично быстродействие и сойдет традиционная архитектура.

Чернышев Андрей ЛеонидовичВы теперь уточняете, что все "атрибуты" "записи" заполняются, но пользователи указывают в запросе условия на 5 или менее атрибутов?Нет, это просто типичное число атрибутов в одном запросе - пользователю редко нужно больше 5 атрибутов одновременно (но даже если он сам задает меньше 5 атрибутов, то зачастую 2-3 атрибута подкидываются неявным образом). Так что 4-6 атрибутов в запросе будут типичной цифрой.

Я соглашусь с Вами (если правильно понимаю), что отсечения лишних записей по 5 атрибутам практически всегда будет достаточно для отличного быстродействия даже более сложных запросов. Если бы по 5 атрибутам, но ПРОИЗВОЛЬНО выбранным (из тысячи доступных), база искала бы быстро - остальное было бы делом техники...

Сложность в том, что практически всегда в запрос попадает хотя бы один атрибут из числа примерно 20-30 таких атрибутов, у которых интересному для пользователя значению (или диапазону значений) соответствует несколько миллионов записей. А вот другие атрибуты могут быть самые разные и общем случае нет корреляции между тем, какой именно атрибут из этих 20-30 "плохих" выбран и какой дополнительный атрибут будет взят вместе с ним...

Чернышев Андрей ЛеонидовичИли, действительно, "ничего не известно" ? Тогда в каждой "записи" могут быть введены все "атрибуты", и каждый из миллиардов пользователей может установить в запросе условия на все "атрибуты", которые в данный момент имеются в "отношении". Ведь "Ваша система" должна нормально функционировать и в этом случае ? Правильно ?Потенциально могут быть введены и все атрибуты, и кто-то так и сделает (хотя бы из вредности), но на практике количество атрибутов падает по экспоненте по сравнению с количеством пользователей, которые хотят запрос такой сложности. Типичное значение - 5 атрибутов в запросе. Из них всегда есть 1, 2 а то и 3 атрибута с длинными диапазонами интересующих значений - причем разные, а не одни и те же три атрибута (по которым был бы построен индекс заранее).