有人知道 OLAP 内部原理吗？

Question

我对数据库内部结构有所了解。 我之前实际上已经实现了一个小型、简单的关系数据库引擎，使用磁盘上的 ISAM 结构和 BTree 索引以及诸如此类的东西。 这很有趣，而且很有教育意义。 我知道，现在我对 RDBMS 的底层工作原理有了更多的了解，我对仔细设计数据库模式和编写查询有了更多的认识。

但我对多维 OLAP 数据模型一无所知，而且我很难在互联网上找到任何有用的信息。

信息如何存储在磁盘上？ 立方体由哪些数据结构组成？ 如果 MOLAP 模型不使用带有列和记录的表，那么......怎么办？ 尤其是在高维数据中，什么样的数据结构使得MOLAP模型如此高效？ MOLAP 实现是否使用类似于 RDBMS 索引的东西？

为什么 OLAP 服务器在处理即席查询方面表现得如此出色？ 在普通关系数据库中可能需要数小时才能处理的同类聚合，在 OLTP 多维数据集中只需几毫秒即可处理。 使这成为可能的模型的基本机制是什么？

Answer 1

我已经实现了几个模仿 OLAP 多维数据集功能的系统，以下是我们为使它们正常工作而所做的一些事情。

1. 核心数据保存在一个 n 维数组中，全部位于内存中，所有键都是通过指向底层数组的指针层次结构来实现的。 通过这种方式，我们可以为相同的数据拥有多个不同的键集。 数组中的数据相当于事实表，通常它只有几条数据，在一个例子中是价格和销售数量。

2. 底层数组通常是稀疏的，因此一旦创建它，​​我们就会删除所有空白单元以节省内存 - 大量的硬核指针算术，但它有效。

3. 由于我们有键的层次结构，因此我们可以很容易地编写例程来轻松地向下/向上钻取层次结构。 例如，我们可以通过月份键来访问年份数据，而月份键又映射到天和/或周。 在每个级别，我们都会聚合数据作为构建多维数据集的一部分 - 使计算速度更快。

4. 我们没有实现任何类型的查询语言，但我们确实支持在所有轴上向下钻取（在我们最大的立方体中最多 7 个），并且这与用户喜欢的 UI 直接相关。

5. 我们在 C++ 中实现了核心内容，但现在我认为 C# 可能足够快，但我担心如何实现稀疏数组。

希望有帮助，听起来很有趣。

Answer 2

Microsoft SQL Server 2008 Analysis Services Unleashed一书详细阐述了 SSAS 的一些特殊性2008年，细节不错。 这并不完全是“SSAS 在幕后的工作原理”，但它很有启发性，尤其是在数据结构方面。 （关于确切的算法，它并不是那么详细/具体。）作为该领域的业余爱好者，我从这本书中收集了一些东西。 这就是 SSAS MOLAP 的全部内容：

• 尽管大家都在谈论多维立方体，但事实表（又名度量组）数据在第一个近似值中仍然最终存储在基本的 2D 表中，每个事实一行。 许多 OLAP 操作似乎最终都由迭代 2D 表中的行组成。
• 然而，MOLAP 内部的数据可能比相应 SQL 表内的数据小得多。 一个技巧是每个唯一的字符串仅在“字符串存储”中存储一次。 然后，数据结构可以以更紧凑的形式引用字符串（基本上通过字符串 ID）。 SSAS 还以某种形式压缩 MOLAP 存储中的行。 我认为这种缩小可以让更多数据同时保留在 RAM 中，这很好。
• 同样，SSAS 通常可以迭代数据的子集而不是完整的数据集。 有一些机制在发挥作用：
  • 默认情况下，SSAS 为每个维度/属性值构建哈希索引； 因此，它“立即”知道磁盘上的哪些页面包含相关数据，例如 Year=1997。
  • 有一个缓存架构，其中相关数据子集存储在与整个数据集分开的 RAM 中。 例如，您可能缓存了一个仅包含几个字段的子多维数据集，并且仅与 1997 年的数据有关。如果查询仅询问 1997 年的情况，那么它将仅迭代该子多维数据集，从而加快速度。 （但请注意，“子立方体”初步近似只是一个二维表格。）
  • 如果您是预定义聚合，那么这些较小的子集也可以在多维数据集处理时预先计算，而不仅仅是按需计算/缓存。
• SSAS 事实表行的大小是固定的，这可能在某种程度上有所帮助。 （相比之下，在 SQL 中，您可能拥有可变宽度的字符串列。）
• 缓存架构还意味着，一旦计算出聚合，就不需要从磁盘重新获取并一次又一次地重新计算。

无论如何，这些都是 SSAS 中发挥作用的一些因素。 我不能说没有其他重要的事情。