Кто-нибудь знает что-нибудь о внутренних OLAP-серверах?

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

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

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

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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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