分布式数据库技术：对象查询处理器

2023-10-28 理论教育版权反馈

【摘要】：几乎所有的对象查询处理器都使用关系型系统定制开发的优化技术。通过继承层次存取对象的优化也是面向对象和关系查询处理相区别的问题。图15.8对象查询处理方法对象的复杂结构及其上面提及的那些与关系查询的四点主要差异导致对象查询的优化和关系查询比较有很大不同。查询优化器可以计算整棵处理树的成本。

关系型DBMS获益于早期的一个精确的、形式化的查询模型定义和一个普遍接受别的代数原语集。

几乎所有的对象查询处理器都使用关系型系统定制开发的优化技术。但是，大部分问题说明，在对象系统中问题要复杂得多。

●关系查询语言在简单类型系统上工作时，只有一个简单型，即关系。关系语言的闭包性意味着每个关系运算施加在一个或两个操作数关系上，产生的结果仍然是一个关系。对象上的运算并不保证计算结果是封闭的。即使只考虑对象关系算符，也要注意一些问题。对象代数算符的结果通常是对象集（或组合），它们可能来自不同的型。如果对象语言在对象代数算符下是封闭的，那么这些不同的对象集可以是其他算符的操作数。这要求开发详细阐述型的推理模式，以决定哪些方法可以应用到这些对象集的所有对象上。更进一步，对象代数算符常操作在语义不同的组合型（如set、bag、list）上，蕴含对型演绎模式附加的需求，以决定不同组合上结果的型。

●关系查询优化依赖于数据物理存储（存取路径），这对查询优化是可用的。在对象系统中，方法和数据封装在一起至少会产生两个问题。首先，决定执行方法的成本比计算一条路径存取一个属性的成本更高。事实上，查询优化器必须考虑执行问题，这并不容易，因为是用通用的程序设计语言编写的。其次，封装产生的问题与查询优化器的存储信息可用性相关。有些系统通过将查询优化器处理成可以打破封装性和直接存取信息的形式。还有些系统使用一种机制，将其成本“暴露”为其接口的一部分。

●对象可以有（也是）非常复杂的结构，从一个对象的状态指向另一个对象的状态。存取复杂对象涉及路径表达式。路径表达式的优化是对象查询语言中的一个困难的、核心的问题。对象属于型，也继承层次相关的型。通过继承层次存取对象的优化也是面向对象和关系查询处理相区别的问题。

●对象DBMS里缺乏普遍接受的对象模型定义。

对象查询处理和优化是一个重要的研究课题，其中分布环境的问题还需深入研究。

Munta Srinivas等在其论文中给出了图15.8来说明对象查询处理方法。

pagenumber_ebook=350,pagenumber_book=335

图15.8　对象查询处理方法

对象的复杂结构及其上面提及的那些与关系查询的四点主要差异导致对象查询的优化和关系查询比较有很大不同。首先，型的问题会导致新的问题，封装特性、复杂结构与继承性等也是问题产生的根源。

关于面向对象数据库系统的查询语言，一般是使用说明性语言（declarative language）。为了简化，下面的讨论将运算局限在对象演算/代数算符，尽管现实要复杂得多。

查询语言的形态是演算优化，因此，首先是处理演算表达式。

●对象查询处理方法使用重复谓词消除方法，运用标识和重写技术，将查询约简成规范型。

●规范表达式后转换成一个等价的对象代数表达式。此时呈现的是一种嵌套形态，可以用算符树来表示，只是叶子变成了类。

●检查代数表达式的型的一致性。

●利用等价保留重写规则将表达式写成与型一致的代数表达式。

●通过优化代数表达式产生执行计划。

1.查询处理问题

查询处理方法在对象DBMS中与关系系统相仿，下面讨论其中的一些主要问题。

●代数优化：查询处理方法会涉及代数优化，相关内容前面章节已介绍，在此不再赘述。

●搜索空间和变换规则：代数优化的好处是代数优化表达式可以通过良型代数性质来变换，这类性质如传递性、交换性和分布性。

变换规则与特定对象代数密切相关。因为这种代数是为各个对象代数及其组合定义的。缺乏标准是涉及对象的代数优化最麻烦的问题。一般来说，这种变换规则与关系系统相似。但也有区别，关系系统涉及的是平面关系，而面向对象系统涉及的是类，后者是多维的。换言之，后者涉及的语义更丰富。

这里讨论一般状态。在对象DBMS里，变换规则的考虑类同于关系系统里的情况，但也有些区别。关系查询表达式是定义在平面关系上的，而对象查询则是定义在类（汇集或集合）上的，它们之间存在子型和组合关系。这些关系就要求一些新的规则。

采用参考文献［11］中的例子，我们考察三个对象算符：并（记作∪）、交（记作∩）和参数选择（记作PσF〈Q1，…，Qk〉）^[18]。这里，并和交的语义与传统的集合论语义相同，而选择则是使用对象（Q1，…，Qk）的集合为参数选择对象（某种意义上是半连接的一般式）。这些算符的结果也是对象集。Özsu等在其研究中也定义了一些规则，例如（为了简化，用QSet表示Q1…Qk；RSet同）：交换规则：（PσF1〈QSet〉）σF2〈RSet〉⇔（PσF2〈RSet〉）σF1〈QSet〉；分配规则：（P∪Q）σF〈RSet〉⇔（PσF〈RSet〉）∪（QσF〈RSet〉）。(www.chuimin.cn)

●搜索算法：穷尽搜索算法枚举计算整个搜索空间，为每个等价表达式使用一个成本函数，然后找出其中开销最少的一个。在DBMS里，枚举搜索算法的组合性质要比在关系型系统中更重要。有论点是，在一个查询里，如果连接数超过10，则枚举搜索策略不可行。在像决策支持系统这类应用系统里，虽然对象DBMS是一个很好的支持，但可以发现其查询更复杂。进一步，对象系统中会涉及执行路径表达式，一种方法是将它们显式表示为连接，用好的连接算法来优化它们。这种情况下，查询里的连接和其他有连接语义操作的数目都可以大于10。也可以使用随机搜索算法来限定搜索空间的区域。遗憾的是，对对象DBMS来说，这一方面的研究不多。

●成本函数：成本函数与存储数据的各种信息相关。一般要考虑数据项的个数、每个数据项的大小、组织结构（如是否有索引）等。这些信息在关系型系统中是可用的，但是在对象DBMS中就不同。

成本函数可以递归定义为代数处理树。如果对象的内部结构对查询优化器而言是不可见的，则必须定义每个节点（代表一个代数操作）的成本函数。一种方法是把这种成本置为对象接口的一部分。因为代数操作是定义在型-汇集上的行为（方法），代数处理树的节点是行为的应用。实现每个行为的函数多种多样（代表不同的算法），其中行为将其成本暴露为执行算法与它们实施操作汇集上的一个函数。查询优化器可以计算整棵处理树的成本。

●路径表达式：大部分对象查询语言允许查询谓词涉及沿着参考链对象存取的条件。这些参考链称为路径表达式（有时也指复杂谓词或蕴含连接）。如路径表达式c.engine.manufacturer.name指的是检索对象c的引擎值里制造商的名字，c定义在型Car上。这样，优化路径表达式的计算也是一个需要关注的问题。

路径表达式允许用一种简洁的高级表示法通过对象组合（聚集）图表示导航，用公式表示其值深度嵌套在对象结构里的谓词。路径表达式可以是单值也可以是集合值。可以出现在查询里，作为谓词的一部分，查询的目标，或者投影表的一部分。路径表达式是单值的，如果路径表达式里的每个成分都是单值的。若其中至少有一个是集合值，则称路径表达式是集合值（set-valued）。

路径表达式的优化横跨整个查询处理过程。在用户查询的解析期间或之后，但在代数优化之前，查询编译器必须认识到哪些路径表达式是可以优化的。这可以通过将路径表达式变换为等价的逻辑代数表达式这种重写技术实现。一旦路径表达式用代数形式表示以后，查询优化器探索等价代数空间和执行计划，找出成本最小的路径表达式。最后，优化执行计划可能涉及有效计算路径表达式的算法问题，包括哈希连接、复杂对象聚合，或者通过路径索引的索引扫描。

●重写和代数优化：再来看路径表达式c.engine.manufacturer.name，假设每个汽车实例有一个指向Engine对象的指针，每个引擎有一个指向Manufacturer对象的指针，每个制造商实例有一个名字字段。假设Engine和Manufacturer型有一个相应的型外延（type extent）。上述路径的前两个链接（links）涉及从磁盘检索引擎和制造商。第三条路只涉及查看制造商对象里的一个字段。因此，只有前两个链接才有优化机会。对象查询优化器需要一种机制区分路径里的这些链接，表示尽可能地优化。典型的这是通过重写阶段实现的。

一个可能性是使用基于型的重写技术。这种方法将代数和基于型的重写技术统一起来，允许提取公共子表达式，支持启发式方法来限制重写。型信息是通过将一个查询的初始复杂自变量分解成更简单算符的集合，将路径表达式重写成蕴含连接算符。规则定义为将连接算符变换成使用路径索引（若可用）的索引化扫描。

●路径索引：对象查询优化的真实扫描依赖于设计索引结构，以加速路径表达式的计算。索引路径表达式的计算仅代表对象查询优化中的一种查询执行算法。换言之，通过路径索引有效计算路径表达式只代表代数算符实现选择的一个汇集。

2.查询执行的进一步讨论

关系型DBMS获益于关系代数运算和存储系统存取原语的对应性。因此，查询表达式执行计划的生成本质上关心执行各个代数算符及其组合的最有效算法的选择和实现。在对象DBMS里，问题更复杂，因为行为上定义的对象抽象级别及其存储各不相同。对象的封装特性隐藏了实现细节，将方法的存储和对象封装到一起，也对设计提出了挑战。

实施时，从查询表达式中生成查询执行计划，当查询重写步骤结束时，通过将查询表达式映射成一个很好定义的对象管理器接口调用集合。对象管理器接口包括执行算法集合。

现在考虑对象汇集（object collection）。对象汇集指的是一个对象组，某种程度上可以看成是与关系对应。

查询执行引擎需要对象汇集的三类基本算法：汇集扫描算法、索引扫描算法和集合匹配算法。

1）汇集扫描算法

汇集扫描（collection scan）算法是一个直接算法，用于顺序存取汇集里的所有对象。

2）索引扫描

索引扫描算法通过索引存取汇集里选择的对象。当然，也可以将深度嵌套在对象结构上的值进行定义索引（即路径索引）。

3）集合匹配算法

集合匹配算法是将对象的多个汇集作为输入，按照某种判据产生对象聚合。这种算法包含连接算法、交算法和装配算法等。

路径表达式会跨越组合对象的组合关系。执行路径表达式的可能方法是将之转换成源和目标对象集间的连接。已经有很多连接算法，如混合哈希连接或基于指针的哈希连接等。混合哈希连接采用除法留余原则连接属性上的哈希函数将两个操作数递归分解成吊桶。每个吊桶可以完全存放到内存。在内存里连接每对吊桶，以产生结果。基于指针的哈希连接用于操作数汇集（记作R）里的每个对象由一个指针指向另一个操作数汇集（记作S）里的一个对象。

交算法分为三步：第一步将R按照与混合哈希连接算法类似的方式分割，区别只是交算法按OID（而不是连接属性）分割，对象集S则不分割。第二步，R的每个分割Ri和S连接，通过将r∈R里的每个对象按照其指向S中相应对象的指针构造哈希表。所得结果是将所有指向S中同一页面的R对象落在一起，并在同一个哈希表记录项里。第三步是构造Ri的哈希表以后，扫描其中的每个记录项，读出S中相应的页面，将指向该页面R中的所有对象和S中的相应对象连接。连接算法和交算法本质上都是集中式算法。

装配算法是另外一个连接执行算法，这是基于指针的哈希连接算法的推广，用于计算多向连接（multi-way join）。学术界已经建议将装配算法作为新的对象代数算符。这个操作有效地将不要求特定处理的对象状态的分片合成起来，作为复杂对象返回到内存中。它将复杂对象的磁盘表示转换成就绪的可遍历的内存表示。

总之，对象查询优化是一个开放的课题，值得继续探索和研究。

分布式数据库技术：对象查询处理器

相关推荐