Кто-нибудь знает что-нибудь о OLAP Internals?

Question

Я немного знаю о внутренностях баз данных. Я на самом деле реализовал небольшой, простой механизм реляционных баз данных, используя структуры ISAM на дисковых и BTree-индексах и все такое. Это было весело и очень познавательно. Я знаю, что теперь я гораздо лучше разбираюсь в тщательной разработке схем баз данных и написании запросов, поскольку теперь я немного больше знаю о том, как работают СУБД.

Но я ничего не знаю о многомерных моделях данных OLAP, и мне было трудно найти какую-либо полезную информацию в Интернете.

Как информация хранится на диске? Какие структуры данных составляют куб? Если модель MOLAP не использует таблицы со столбцами и записями, тогда ... что? Какие структуры данных делают модель MOLAP настолько эффективной, особенно в многомерных данных? Используют ли реализации MOLAP что-то аналогичное индексам СУБД?

Почему серверы OLAP намного лучше обрабатывают специальные запросы? Агрегации того же типа, для обработки которых в обычной реляционной базе данных может потребоваться часов , могут обрабатываться в миллисекундах в кубе OLTP. Какова основная механика модели, которая делает это возможным?

Answer 1

Я реализовал несколько систем, которые имитировали работу кубов OLAP, и вот несколько вещей, которые мы сделали, чтобы заставить их работать.

1) Основные данные содержались в n-мерном массиве, все в памяти, и все ключи были реализованы через иерархии указателей на базовый массив. Таким образом, мы можем иметь несколько разных наборов ключей для одних и тех же данных. Данные в массиве были эквивалентны таблице фактов, часто она содержала только пару частей данных, в одном случае это была цена и количество проданных товаров.

2) Базовый массив часто был разреженным, поэтому, как только он был создан, мы использовали для удаления все пустые ячейки для экономии памяти - много арифметики с жестким указателем, но это работало.

3) Поскольку у нас были иерархии ключей, мы могли довольно легко написать подпрограммы для упрощения иерархии. Например, мы будем получать доступ к данным за год, просматривая ключи месяцев, которые, в свою очередь, сопоставляются с днями и / или неделями. На каждом уровне мы собирали данные как часть построения куба - вычисления выполнялись намного быстрее.

4) Мы не реализовали никакой язык запросов, но мы поддерживали детализацию по всем осям (до 7 в наших самых больших кубах), и это было напрямую связано с пользовательским интерфейсом, который понравился пользователям.

5) Мы реализовали ядро ​​в C ++, но сейчас я считаю, что C # может быть достаточно быстрым, но я бы беспокоился о том, как реализовать разреженные массивы.

Надеюсь, это поможет, звучит интересно.

Answer 2

В книге Microsoft SQL Server 2008 Analysis Services Unleashed подробно изложены некоторые особенности SSAS 2008. Это не совсем «вот как именно работает SSAS под капотом», но это довольно многообещающе, особенно в части структуры данных. (Это не так подробно / конкретно о точных алгоритмах.) Несколько вещей, которые я, как любитель в этой области, взял из этой книги. Это все о SSAS MOLAP:

• Несмотря на все разговоры о многомерных кубах, данные таблицы фактов (она же группа мер) по-прежнему, в первом приближении, в конечном итоге хранятся в основном в двумерных таблицах, по одной строке на каждый факт. Похоже, что в конечном итоге ряд операций OLAP состоит из итерации строк в 2D-таблицах.
• Однако данные внутри MOLAP потенциально намного меньше, чем внутри соответствующей таблицы SQL. Одна хитрость заключается в том, что каждая уникальная строка сохраняется только один раз, в «хранилище строк». Затем структуры данных могут ссылаться на строки в более компактной форме (в основном, по идентификатору строки). SSAS также сжимает строки в хранилище MOLAP в некоторой форме. Я предполагаю, что это сокращение позволяет большему количеству данных оставаться в оперативной памяти одновременно, и это хорошо.
• Точно так же SSAS часто может выполнять итерации по подмножеству данных, а не по полному набору данных. Несколько механизмов в игре:
  • По умолчанию SSAS создает хеш-индекс для каждого значения измерения / атрибута; таким образом, он «сразу» знает, какие страницы на диске содержат соответствующие данные, скажем, для Year = 1997.
  • Существует архитектура кэширования, в которой соответствующие подмножества данных хранятся в ОЗУ отдельно от всего набора данных. Например, вы могли кэшировать вложенный куб, в котором есть только несколько ваших полей, и который относится только к данным за 1997 год. Если запрос запрашивает только около 1997 года, то он будет повторяться только по этому вложенному кубу, что ускоряет процесс , (Но обратите внимание, что «субкуб» в первом приближении является просто 2D-таблицей.)
  • Если вы предопределенные агрегаты, то эти меньшие подмножества также можно предварительно вычислять во время обработки куба, а не просто вычислять / кэшировать по требованию.
• Строки таблицы фактов SSAS имеют фиксированный размер, что, по-видимому, помогает в некоторой форме. (В SQL, в отличие, у вас могут быть строковые столбцы переменной ширины.)
• Архитектура кэширования также означает, что после вычисления агрегации ее не нужно повторно загружать с диска и повторно вычислять снова и снова.

Вот некоторые из факторов, которые играют в SSAS. Я не могу утверждать, что нет и других жизненно важных вещей.