2021-01-12：多维快查多维查询系统，你了解的解决方案都有哪些？

福哥答案2021-01-12：

这个面试题很偏，连题意都不知道。

多维表达式 (MDX) 是用于在 MicrosoftAnalysis Services 中处理和检索多维数据的查询语言。MDX 基于 XML for Analysis (XMLA) 规范，并带有特定于 SQL ServerAnalysis Services 的扩展。MDX 使用由标识符、值、语句、函数和运算符组成的表达式，Analysis Services 可以通过计算表达式来检索某个对象（如集或成员）或标量值（如字符串或数字）。

SQL ServerAnalysis Services 中的 MDX 查询和表达式可用于执行以下操作：

1.从 SQL ServerAnalysis Services 多维数据集向客户端应用程序返回数据。

2.设置查询结果的格式。

3.执行多维数据集设计任务，包括定义计算成员、命名集、范围分配和关键绩效指标 (KPI)。

4.执行管理任务，包括维度和单元安全性。

MDX 在很多方面与关系数据库常用的 SQL 语法看起来很相似。但是，MDX 并非 SQL 语言的扩展，在许多方面都有别于 SQL。为了创建用于设计或保护多维数据集的 MDX 表达式，或创建 MDX 查询以返回多维数据并设置其格式，您需要了解有关 MDX 和维度建模的基本概念、MDX 语法元素、MDX 运算符、MDX 语句以及 MDX 函数。

摘要：网络应用中内容主导的系统需要管理海量的多维数据，比如新闻网页中的标题、图片、作者、时间等多维信息;拼接成网页地址的多个字符串片段;视频分发系统中描述一个片段的多个特征等。大规模多维数据通常是以集合的形式保存在互联网系统中的。因此，需要一种表示多维集合元素的数据结构以及判断元素是否属于某个集合的算法，也就是多维集合的元素表示与存在性查询算法。类似的解决方案除了有低时间和空间复杂度的要求，而且还要能够支持灵活的查找方式，并有效处理高相关查询。　　本文的研究工作采用了一种概率型数据结构来表示多维集合的元素，这种刻画能够有效地节省空间，并保存同一个元素不同属性之间的关联信息，从而实现快速准确的查询。在此基础上，提出了一种能够快速准确地支持多维集合中的元素表示与存在性查询的数据结构和相关算法。　　我们提出的大规模多维数据查询算法（乘积型布鲁姆过滤器Cartesian-join ofBloom Filters，简称CBF）不仅能够较好的处理完整查询、不完整查询和相关查询，而且还能够有较低的时间复杂度和空间复杂度。相比传统的基于表的解决方案，CBF能够明显节省存储空间;与标准布鲁姆过滤器比较，CBF能够使用同样的空间支持多维元素的完整查询，同时还能额外支持提供不完整信息的元素存在性查询。　　论文从理论上推导出了CBF的虚警率的解析表达式和最优哈希函数个数与元素个数及存储空间的关系，证实了CBF的虚警率具有与SBF基本相同的形式。从理论上分析了算法的时间复杂度和空间复杂度，CBF的时间复杂度与维数成正比，与集合元素个数无关。在占用空间不低于其下限的情况下，CBF空间复杂度与标准的布鲁姆过滤器相同。　　我们使用公共数据集与合成数据集来检验我们的理论推导的正确性。公共数据集由56663条二维数据构成，用于验证CBF虚警率和最优哈希函数个数解析表达式。合成数据集用来验证时间复杂度、空间复杂度、算法可用性等内容。我们选取了虚警率与最优哈希函数实验、维度扩展性实验、完整查询实验、不完整查询实验、空间复杂度实验和时间复杂度实验。并将实验结果与理论推导进行比较。实验证明了我们的理论推导的准确性。在实验中，我们使用大约10个比特来保存一个元素，虚警率约为1％。　　为了使用多线程技术来加速集合表示和存在性查询过程，我们迸一步提出了基于CBF的改进算法——并行化乘积型布鲁姆过滤器Parallel Cartesian-join ofBloom Filters，简称PCBF。该算法在继承CBF的优势的同时，避免了对同一个元素进行哈希时不同哈希数据点出现冲突的问题，能够较好地支持多线程加速，可以较快地完成集合元素表示。我们通过理论分析和实验验证了PCBF的算法特性。理论分析和实验证明，PCBF的性能和CBF基本一致，同时可以在使用多线程加速技术后有较好的性能。　　最后，本文展示了CBF和PCBF算法的应用场景和未来的研究方向。