The RDF-3X engine for scalable management of RDF data—-part1数据库VAOVA的博客-

本文由学者Thomas Neumann和Gerhard Weikum于2009/09/01在《The VLDB Journal 》联合发表

本文完整的系统RDF-3X，从最初为RDF数据的管理和查询而设计，具有精简索引和查询处理的RISC风格的结构。查询优化器为复杂查询选择最佳连接顺序，成本模型=整个连接路径的统计。RDF-3X优化了查询，还通过分段体系结构支持在线更新：推迟对主数据库索引的直接更新，将其应用于紧凑差异索引，以分批方式再将差异索引合并到主索引。

将三元组与相同属性名称映射到属性表中，映射到列存储，并创建频繁连接的实例化图。管理大规模RDF数据=存储布局+索引编制+查询处理：

• 缺少全局模式和谓词名称的多样性在数据库设计存在问题。

• 通过对RDF数据细粒度建模，具有大量联接的查询会构成部分工作负载。这要求特定选择查询处理算法并谨慎优化复杂的联接查询；

• 联接顺序和其他执行计划的优化需数据统计选择性估计。

• RDF使用XML语法且SPARQL涉及类似于XML路径表达式的搜索模式。

RDF-3X实现基于三个关键原则：

• 物理设计在“大型三元组表”上创建的索引与工作负载无关，所有索引的总存储空间小于主数据。

• 查询处理器是RISC风格，主要依靠合并连接排序索引列表，可通过三元组表的“穷举式”索引实现。

• 查询优化器集中在生成执行计划时的连接顺序，采用动态规划计划枚举，并使用基于RDF特定统计概要的成本模型。

大多数RDF数据库不是只读的都是查询密集型的，但必须至少支持增量加载，甚至支持在线更新新三元组，用于注释现有数据。开发了一种暂缓索引更新的暂存体系结构处理RDF-3X用于快速查询的主动索引。更新是在工作空间和差异索引中收集，然后以批处理合并到主数据库索引。SPARQL查询对构成RDF数据图三元组的模式匹配查询，SPARQL引入两个查询修饰符：distinct关键字指定必须消除重复项，reduce关键字指定可以重复但无需消除。减少关键字的目标是通过允许优化帮助RDF查询，但查询输出存在不确定性。将RDF三元组映射到关系表上的三种方法：

• 所有三元组都存储在单个、大型的三元组表。
• 三元组按其谓词名称分组，所有三元组均具有相同的谓词名称。
• 三元组是基于谓词名称聚类，基于工作负载中相同实体类或共现的谓词。

通过创建“正确的”索引集可快速地处理合并联接，将所有三元组存储在压缩聚类B+树。三元组在B+树中按字典排序，将SPARQL模式转换为范围扫描。为了确保仅通过执行一次索引扫描就可在模式三元组的任何位置使用变量回答所有可能的模式，在六个单独的索引中保留S，P和O的所有六种可能排列。压缩方案受文本检索系统中反向列表方法的启发，概括为id三元组。对于压缩，在节省空间和CPU消耗之间需权衡解压缩或解释压缩项目，详细信息如下：

算法会计算到前一个元组的增量，如果增量小，则直接编码在头字节；否则，为每个树值计算δi值并调用编码。编码将规模写入标头字节，然后写入δi的非零尾部。在解压缩期间，简单从头字节中重建大小。压缩方案使用LZ77压缩比原始数据压缩更好。LZ77压缩将索引大小缩小了两倍，但增加了CPU时间，所以RDF-3X查询不使用LZ77。压缩索引主要是单独压缩每个叶页。分页压缩优点：

• 通过B+树遍历查找任何页并直接读取三元组， 如果压缩的块更大，就必须解压前页。

• 压缩索引就像一般B+树，简化了压缩索引到引擎部分的集成并保留RISC特性。

对SPARQL，索引部分三元组而不是全部三元组，如下所示：

构建聚合索引，每个索引仅存储三元组中的两个条目及聚合计数（在完整三元组中该对的出现次数）。聚合索引存储（value1，value2，count）而不是（value1，value2，value3），伪代码如图所示：

编译SPARQL查询的第一步是转换，如图说明了SPARQL查询的转化：SPARQL允许许多语法快捷方式简化查询公式（图a），每个联合查询解析并扩展为三元组（图b）。三元组的每个组成部分是文字或变量。当查询由单个三元模式组成时，可通过一次范围扫描回答查询。当查询由多个三重模式组成时，将各模式的结果结合（图d），所以需要在查询图（图c）使用连接排序算法。

每个三元模式都对应于查询图中的一个节点，概念上每个节点对整个数据库扫描。查询图中的边反映了联合变量的出现：当且仅当两个节点中具有共同查询变量时，两个节点发生连接。使用查询图构造（未优化的）执行计划如下：

• 为每个三重图案创建索引扫描，模式中的文字决定扫描范围。
• 为查询图中的每个边添加连接，如果无法连接，则添加选择。
• 如果查询图断开连接，根据需要增加交叉联系从而获得单个连接树。
• 添加包含所有FILTER谓词的选择。
• 查询的projection子句包含distinct选项，则添加聚合运算符消除结果重复项。
• 添加字典查找运算符，通过其转换产生ID并返回字符串。

优化器为目标查询找到了最佳扫描策略和最佳连接顺序。

处理析取查询
SPARQL允许某些形式的析取：UNION表达式返回由两个或更多模式组产生的绑定的并集。如果有任何结果，则OPTIONAL表达式将返回模式组的绑定，否则返回NULL值。在查询转换和优化过程中，将UNION和OPTIONAL中的模式组视为嵌套子查询，即首先转换和优化嵌套模式组。在外部查询的翻译和优化过程中将其视为具有特殊成本和基数的基本关系。对于UNION，我们添加模式组结果的并集，对于OPTIONAL，将结果添加到基本原则，可更积极地优化查询。

保留结果基数
标准的SPARQL语义要求生成正确数量的变量绑定，虽然有很多重复。从处理角度，应避免产生和保留重复的额外工作。通过在查询处理期间跟踪每个元组的多重性来解决问题的查询处理。扫描未聚合的索引会产生多重性，而聚合索引会报告重复数量为多重性。联接运算符使乘数相乘获得每个输出元组的重复数。

实施问题
运行时系统具有很强的RISC：大多数运算符仅处理整数编码的ID，消耗和产生id元组流，比较ID等。三元组中的每个条目都是必须产生的id属性，或是绑定到文字的字符串，如果在前缀中，则会影响开始/停止条件；如果未绑定的条目在前，则说明选择。无需在运行时检查不同条件，可在查询编译时处理。每个条目都是id属性或文字。一个三元组有三个条目，则有八种组合。使用具有索引扫描运算符的八种不同实现方法的单接口， 减少系统代码中条件分支的数量。

查询优化的要求
优化SPARQL执行计划的关键是联接排序，其解决方案通常基于各种形式的动态规划或随机化。本文的执行计划具有特定的形式：尽可能长时间使用保持顺序的合并联接，仅对最后几个运算符使用到哈希联接。

基于DP的计划枚举
寻找最佳执行计划基于自下而上的DP框架。通过查询图的子图组织DP表，维持每个子图的最优计划和结果输出顺序。如果有子图有多个计划，而又没有计划在另一个计划中占主导地位，则所有计划保留在DP表中。优化程序通过扫描基本关系为DP表播种，播种分两步过程：

• 优化器分析查询，检查在查询的其他部分中使用了哪些变量绑定。如果未使用变量，则可使用聚合索引将其映射。
• 优化器决定要使用哪个索引。

修剪执行计划的搜索空间基于估计的执行成本。优化器为每个生成计划调用成本模型，并修剪由较便宜的替代方案主导的等效计划。优化器可在所有三重排列上使用索引，所以按任意顺序生成元组，排序不仅由索引扫描创建，由选择引起的函数依赖关系创建。

未完待续，接下篇。。。