关系型数据库管理系统中删减聚类表的磁盘块

摘要

本发明公开涉及关系型数据库管理系统中删减聚类表的磁盘块。提供了用于生成“维度区域地图”的技术，维度区域地图使得数据库服务器基于查询中限定一个或多个维度表的过滤谓词避免扫描事实表的磁盘块。区域地图将事实表分成被称为“区域”的多组连续磁盘块。对于每个区域，确定维度表的一个或多个“分区”列中每一个的最小值和最大值并在区域地图中对其进行维护。对于包含分区列上过滤谓词的查询，可以将谓词值与为该分区列的区域维护的最小值和最大值进行比较以确定该区域的磁盘块扫描是否可以被跳过。

说明书

技术领域

本发明涉及关系型数据库管理系统，并且更具体地，涉及用于在 关系型数据库管理系统中聚类(cluster)表的技术。

背景技术

在本节中描述的方法是可以实行的方法，但不一定是先前已被构 想或实行的方法。因此，除非另外指出，否则不应当假设本节中描述 的任何方法仅仅因为它们被包括在本节中就被算作为现有技术。

在数据库系统的上下文中，“维度”是为数据提供类别的值的列 表。维度充当用于识别变量的值的索引。例如，如果销售数据具有每 个月单独的销售数字，则该数据具有MONTH维度。即，该数据通 过月进行组织。维度类似于关系型数据库中的键。通过两维或更多维 组织的数据被称为“多维数据”。

多维变量中的任何数据项都可以通过为变量的每个维度指定一个 成员来进行唯一且完全地选择。例如，如果sales变量通过MONTH、 PRODUCT和MARKET标出维度，则为MONTH维度指定 “January”、为PRODUCT维度指定“Stereos”和为MARKET维 度指定“Eastern Region”就为该变量唯一地指定了单个值。因此， 维度提供了简明和直观的组织和选择数据的方式，用于检索、更新和 执行计算。

多维数据可以存储在关系型数据库系统中。当多维数据存储在关 系型数据库系统中时，应用通过提交符合关系型数据库系统支持的数 据库语言的命令访问数据，最常见的数据库语言是结构化查询语言 (SQL)。

关系型数据库系统以关联表的形式存储数据，其中每个表都具有 一列或多列以及一行或多行。用于在关系型数据库系统中存储多维数 据的常规机制是将数据存储在表中，其中表以被称为星型架构(star  schema)的方式进行布置。在关系型数据库系统中，星型架构的特点 是存在一个或多个相对较大的表和若干个相对较小的表。较大的表没 有重复较小表中包含的信息，而是引用较小表中的行。在星型架构中， 较大的表被称为“事实表”，而较小的表被称为“维度表”。图1说 明了具有两个维度的示例性星型架构。

参考图1，它说明了包括表102、104和106的数据库100。表 102被命名为“stores(商店)”并且包含关于其中可能发生销售的 每个商店的信息。stores表102中每一行包含唯一的store-id和关于 对应于该store-id的特定商店的信息。表104被命名为“products (产品)”并且包含关于可以在任何商店销售的每种类型产品的信息。 products表104中每一行包含唯一的product-id以及关于特定产品 的信息。

表106被命名为“sales(销售)”并且包含在stores表102中表 示的每个商店中的每笔销售的信息。sales表106中每一行包括以美 元为单位的amount(量)、指示做出销售的商店的store-id、指示在 销售中售出的产品的product-id以及销售的日期。通常，销售的数 量将远远高于做出销售的商店的数量和由商店具有的产品数量。关于 在销售中包含的商店和产品的详细信息不必存储在sales表106的行 中，因为这些详细信息分别可以从stores表102和products表104 中得到。相反，表106的行包含引用在其它表102和104中存储的信 息的值(store-id和product-id)。因此，表102、104和106构成星 型架构，其中表106是事实表并且表102和104是维度表。

存储在事实表106中的数据只有两个维度，事实表106具有两个 列(STORE-ID和PRODUCT-ID)专门为这些维度存储外键值 (foreign key value)。通常，事实表专门用一列为与事实表中存储的多 维数据相关联的每个维度存储外键值。通过在事实表中存储引用维度 表中的行的外键值，事实表中的行可以保持在相对较小的尺寸并且事 实表的列的数量可以保持在相对较小的数量。例如，sales表106不 是包含stores表102的MANAGER(管理员)、CITY(城市)和 STATE(州)列中的值和products表104的SOURCE(来源)、 PARTS(件数)和COST(成本)列中的值，而是sales表106在两 个列中包含外键值，一列引用stores表102中的行并且另一列引用 products表104中的行。典型的事实表中行的数量可以是数十亿或者 更多。作为对照，维度表中行的数量通常少得多(例如，数十、数百 或数千)。相应地，典型的星型架构被构造成最小化在事实表的每一 行中储存的数据量。

对多维数据的查询可以检索受“维度键值”约束的事实表“度量” 的聚合。例如，针对图1中说明的表发出的查询可能从sales表106 检索在San Jose发生的所有“amount”值的总和。在这个例子中， 查询的执行包括联接来自sales表106的行和来自stores表102的行， 其中“city”列具有值“San Jose”。

这种类型的查询也称作“星型查询”。事实表的“度量”是不包 含外键值的事实表列中的值。例如，在sales表106的AMOUNT和 DATE(日期)列中的值分别是销售量度量和销售日期度量。“维度 键值”是与特定维度相关联的值。例如，用于“region”维度的维度 键值可以是“Northern Region”、“Southern Region”、“Eastern  Region”和“Western Region”。

在星型架构中，维度的维度键值通常存储在与该维度相关联的维 度表的维度键列中。例如，stores表102的维度键值存储在stores表 102的“store-id”列中。类似地，products表104的维度键值存储 在products表104的“product-id”列中。

星型查询通常包含维度表上的过滤谓词。以下是星型查询的例子， 其联接sales事实表106与合格的stores 102和products 104维度表。 stores维度表102由过滤谓词st.state＝“CA”限定并且products维 度表104由过滤谓词pr.cost>10限定。该示例星型查询通过商店城市 和产品来源请求对California州、价格超过10美元的产品的销售量 的总和。

SELECT st.city,pr.source,SUM(sa.amount)

FROM sales sa,stores st,products pr

WHERE sa.store-id＝st.store-id AND sa.product-id＝

pr.product-id AND st.state＝“CA”AND pr.cost>10

GROUP BY st.city,pr.source

用于提高关系型数据库管理系统中星型查询性能的一种方法是将 事实表中相关的数据组织在磁盘上连续的磁盘块中。“磁盘块”是被 关系型数据库管理系统用于存储数据库数据的数据存储装置的逻辑单 元。磁盘块具有块大小(例如，4KB)并且可以包含一个或多个底层 文件系统或操作系统块。除其它信息之外，磁盘块还可以包括一个或 多个表的一行或多行的数据，或者行的数据可以跨多个磁盘块。

在关系型数据库管理系统存储多维数据的上下文中，在磁盘上的 连续磁盘块中组织相关事实表数据被称作“聚类(clustering)”。 聚类通过促进压缩、索引和输入/输出(I/O)删减(prune)可以提 高关系型数据库管理系统中星型查询的性能。在关系型数据库管理系 统回答星型查询的上下文中，I/O删减指当为获得与星型查询相关的 数据而扫描事实表时避免对事实表的某些磁盘块进行磁盘扫描，这些 磁盘块已知不包含与星型查询有关的数据。最近的数据存储设备的技 术改进已经将数据库访问提高到这一点：即，当执行查询时，即使其 中有索引可用，数据库系统也有时执行表扫描来代替索引表访问。因 此，用于聚类以促进I/O删减的技术最近在业界已获得相当大的关注。

有多种不同的方法在关系型数据库管理系统中聚类事实表。在一 种方法中，事实表的行基于事实表的行的一列或多列中的值以线性顺 序存储在磁盘上。例如，事实表的行可以首先通过带有指定事实表的 一列或多列的ORDER BY子句的查询进行排序，然后将这些行以排 序的顺序存储在磁盘上的一个或多个连续的磁盘块中。在另一种方法 中，事实表基于事实表列中的值按照诸如Z-order曲线或Hilbert空 间填充曲线的空间填充曲线沿着多个维度进行聚类。在这两种方法中， 事实表仅基于事实表的列进行聚类。当星型查询包含事实表的列上的 过滤谓词时，当事实表基于那些列进行聚类时，这些方法促进了I/O 删减。

遗憾的是，关系型数据库管理系统中执行星型查询的性能瓶颈通 常是相对较大的事实表和维度表之间的联接，该联接被称作“星型联 接(star join)”。维度表通常在星型查询中被维度表上的一个或多 个通常为高选择性的过滤谓词限定。在许多情况下，星型查询不包含 事实表列上的任何过滤谓词。例如，以上示例星型查询包含限定 stores维度表102的过滤谓词st.state＝“CA”，并且包含限定 products维度表104的过滤谓词pr.cost>10，但是不包含sales表 106的AMOUNT列或DATE列上的任何过滤谓词。

仅基于事实表的列聚类事实表的关系型数据库管理系统在执行星 型联接时可能执行了浪费的事实表的磁盘扫描。磁盘扫描可能是浪费， 因为在没有事实表列上的任何过滤的情况下，事实表的聚类无所帮助， 并且可能需要扫描事实表的所有磁盘块。具体而言，即使sales表 106基于“date”进行聚类，与其中st.state＝“CA”的stores表 102的行以及与其中pr.cost>10的products表104的行联接的sales 表106的行也可能在sales表106内随机地分布。

在本节中描述的方法是可以实行的方法，但不一定是先前已被构 想或实行的方法。因此，除非另外指出，否则不应当假设本节中描述 的任何方法仅仅因为它们被包括在本节中就被算作为现有技术。

附图说明

附图中：

图1是说明示例星型架构的框图；

图2是根据本发明实施例的用于处理带有聚类子句的DDL语句 的数据库服务器组件的框图；

图3说明示例线性条目表；

图4是包含磁盘块的磁盘一部分的框图；

图5说明根据本发明的实施例的示例区域地图(zonemap)表和 包含具有分组成区域的磁盘块的图4的框图；

图6说明根据本发明的实施例的可能的维度区域地图的表结构；

图7是根据本发明的实施例由数据库服务器执行的磁盘扫描的流 程图；

图8说明根据本发明的实施例的可能的维度区域地图的表结构；

图9是说明本发明的实施例可以在其上实现的计算机系统的框图。

具体实施方式

描述了用于在关系型数据库管理系统中聚类表的方法和装置。在 以下描述中，为了解释的目的，阐述了众多具体的细节，以便提供对 本发明的透彻理解。但是，很显然，本发明没有这些具体细节也可以 实践。在其它情况下，众所周知的结构和设备以框图形式示出，以避 免不必要地混淆本发明。

总体概述

提供了一种技术，用于解决与关系型数据库管理系统中聚类事实 表的现有方法相关联的问题。根据本发明的一个方面，数据库服务器 基于来自一个或多个维度表的一列或多列的值聚类数据库中的事实表。 更具体地，行以排序的顺序存储在事实表中，并且行排序的顺序是基 于一个或多个维度表的一列或多列中的值。用户在“聚类标准”中规 定其中排序顺序所基于的维度表的列。数据库服务器响应于特定用户 发起的对事实表的数据库操作，使用聚类标准来自动地以排序的顺序 存储事实表中的行。

为了解释的目的，在聚类标准中规定的并且排序顺序所基于的维 度表的列在本文被称为“聚类维度列”。其中在聚类标准中规定的聚 类维度列的维度表在本文被称为“聚类维度表”。

本文提供了各种技术，用于基于在聚类标准中规定的聚类维度列 以排序的顺序存储事实表中的行。一般而言，过程包括数据库服务器 生成“聚类”查询，其中查询(a)选择一组“源”事实表行，(b) 在源事实表行和聚类维度表之间执行联接，以产生一组联接的行，其 中一组联接的行中的每一行对应于最多一个源事实表行，(c)利用 聚类维度列的值作为排序键排序联接的行，以及(d)以排序的顺序 在事实表中存储源事实表行。很明显，用作排序事实表行的基础的来 自聚类维度列的值没有存储在事实表中。

如在下文更详细解释的，源事实表行可以从事实表中或从其它来 源选择(例如，从外部表)。联接的行可以以线性顺序或以交错顺序 进行排序。交错排序可以基于诸如Z-order空间填充曲线或Hilbert 空间填充曲线的空间填充曲线。利用聚类维度列的值作为排序键排序 联接的行使得概念上彼此相关的源事实表行被存储成在事实表内物理 上彼此靠近。因为概念上相关的事实表行基于聚类维度列的值被存储 成物理上彼此靠近，所以在事实表的磁盘扫描期间基于聚类维度列上 过滤谓词的I/O删减是可能的。

根据本发明的另一个方面，在数据库中生成了访问结构，其允许 数据库服务器基于查询中限定一个或多个维度表的过滤谓词避免扫描 事实表的磁盘块。这种访问结构在下文被称作“维度区域地图 (zonemap)”。通常，维度区域地图生成过程包括将事实表分成下 文中称作“区域”的一组连续磁盘块。对于每个区域，确定用于维度 表的一个或多个“分区”列中每一个的最小值和最大值并在区域地图 中对其进行维护。对于包含分区列上过滤谓词的查询，可以将谓词值 与用于为区域维护的分区列的最小值和最大值进行比较，以确定该区 域是否包含满足过滤谓词的任何事实表的行。由于为区域维护的最小 和最大值是基于维度表的列的值确定的，因此，在事实表的磁盘扫描 期间基于限定维度列的过滤谓词的I/O删减是可能的。

聚类标准

如上所述，星型查询通常利用维度表上的过滤谓词限定维度表。 例如，在以下的示例星型查询中，countries维度表用两个过滤谓词 进行限定，一个在countries维度表的region列上并且另一个在 countries维度表的subregion列上。

SELECT countries.region,countries.subregion,countries.name,

sum(sales.amount_sold)

FROM sales JOIN countries ON sales.country_id＝

countries.country_id

WHERE countries.region＝‘Europe’AND countries.subregion＝

‘Eastern Europe’

GROUP BY countries.region,countries.subregion,countries.name

另外，如前面提到的，执行星型查询的性能瓶颈可能是事实表和 维度表之间的联接。在星型查询中的过滤谓词限定维度表的情况下， 通过I/O删减减少星型联接中包含的事实表的行数将是有益的。为了 促进这种I/O删减，用户使概念上相关的事实表行在事实表内物理上 存储得彼此靠近，其中“概念上相关”可以基于一个或多个维度表的 一列或多列中的值。

除了促进I/O删减之外，物理上将概念上相关的事实表行在事实 表内存储得彼此靠近还促进事实表的数据压缩以及事实表的索引。将 概念上相关的事实表行在事实表内存储得彼此靠近会导致事实表行的 一列或多列中的值彼此相似，从而导致这些列值更好的压缩。例如， 如果事实表行的列中的值以排序的顺序存储在磁盘上，则运行长度编 码压缩算法在压缩这种列中的数据时能够非常高效。在事实表的一个 或多个聚类列上创建索引有利于经这种索引提高访问事实表数据的性 能。提高事实表数据可访问性的原因是由于具有相同索引键值的事实 表行在磁盘上物理上接近。例如，由于事实表的聚类，如果具有特定 索引键值的所有事实表行都一起存储在磁盘块(或一组磁盘块)中， 则经索引检索这种事实表行会带来减少的磁盘I/O量。

在本文描述的某些实施例中，提供了用于基于一个或多个维度表 的一列或多列中的值聚类事实表的技术。但是，应当理解，该技术也 可以基于一个或多个维度表的一列或多列中的值和事实表的一列或多 列中的值应用到聚类事实表，或仅基于事实表的一列或多列中的值应 用到聚类事实表。

用于聚类标准的DDL接口

根据本发明的一个方面，提供了数据定义语言(DDL)接口， 用户能够通过它规定聚类标准与事实表相关联。聚类标准可以存储在 数据库中作为事实表的元数据。如以下更详细描述的，当生成聚类查 询来聚类事实表时，聚类标准从数据库中读取。

在一种实施例中，附加的“聚类”子句被添加到定义事实表的 DDL语句。这种DDL语句可以用在创建事实表、改变它的定义、或 定义，改变或修改事实表的列或约束的任何其它DDL动作的上下文 中。因此，当定义事实表时，用户可以方便地将聚类标准与事实表相 关联。例如，以下创建sales表的示例性DDL语句包括由关键字 “聚类”指示的聚类子句：

在这个描述中，用户规定的聚类标准的例子以示例SQL语句的 形式提供。应当理解，示例SQL语句的语法仅仅是示例性的。本发 明不限于例子的语法并且可以使用传递相同聚类标准语义的其它语法。

聚类标准-聚类维度列和联接标准

聚类标准用来基于一个或多个维度表中的值规定用于聚类事实表 的多个不同的聚类选项。在一种实施例中，聚类标准规定一个或多个 聚类维度列和联接标准。该一个或多个聚类维度列是用户希望通过其 排序事实表行的维度表的列，其中排序事实表行或者通过线性排序或 者通过交错排序。聚类维度列通常是用户预期星型查询包含其上过滤 谓词的维度表的列。

在本文的例子中，聚类维度列在聚类子句的子子句中作为排序方 法指示(sorting method directive)的参数规定。排序方法指示在以下 更详细地描述。例如，在以上聚类子句中，聚类维度列 countries.region、countries.subregion和countries.name被规定为排 序方法指示BY LINEAR ORDER的参数。但是，也可以使用规定维 度表的列的其它方式，其中用户希望通过其排序事实表的行，并且本 发明不限于这些例子的方式。例如，在隐含缺省排序方法指示的情况 下，聚类维度列可以由用户在聚类标准中规定，而无需任何排序方法 指示。

联接标准规定事实表的外键列和聚类维度表中的唯一键列，其中 用户希望通过其将事实表与聚类维度表联接。例如，以上示例DDL 语句中的聚类子句规定聚类维度列countries.region、 countries.subregion和countries.name，并且规定用于利用sales表的 country_id外键列和countries表的country_id唯一键列将sales事实 表与countries聚类维度表等值联接(equi-joining)的联接标准。等 值联接是特殊类型的联接，其中在联接谓词中只使用了等于比较运算 符(例如，“＝”)并且没有使用范围比较运算符(例如，“>”， “<”)。联接标准用来制定聚类查询，如以下更详细描述的。由于 联接标准中只规定了聚类维度表中的唯一键列，因此来自事实表的行 将被聚类查询用来自每个聚类维度表的最多一行进行联接并且来自事 实表的行将对应于由聚类查询构成的一组联接的行中的最多一行。

聚类标准可用来规定用于基于多于一个维度聚类事实表的聚类 选项，其中每个维度对应于不同的维度表。在这种情况下，联接标准 由用户提供，用于联接事实表和每个不同的维度表，如在以下示例聚 类子句中，其规定聚类维度列promotions.subcategory和 products.subcategory并且还规定用于利用sales表的promo_id外键 列和promotions表的promo_id唯一键列联接sales事实表和 promotions聚类维度表的联接标准。聚类子句还规定用于利用sales 表的prod_id外键列和products表的prod_id唯一键列联接sales事 实表和products聚类维度表的联接标准。

聚类标准-排序方法

根据本发明的实施例，聚类标准规定在由聚类查询构成的一组联 接的行上执行的排序类型。由聚类查询执行的排序类型确定由聚类查 询选择的一组源事实表行如何在事实表内进行聚类。一组源事实表行 如何在事实表内进行聚类确定可以通过基于查询中过滤谓词的I/O删 减实现的I/O效率。一般而言，排序类型是两种通用类型之一：线性 的或交错的。在这两者的情况下，排序可以基于聚类维度列。

聚类标准-线性排序方法

利用线性排序，通过聚类查询构成的联接的行基于联接的行中聚 类维度列的值以升序或降序顺序进行排序。如果在聚类标准中规定了 多于一个的聚类维度列，则如由用户在聚类标准中规定的多个聚类维 度列的序列定义排序的联接的行的组织。即，联接的行首先利用该序 列中第一个聚类维度列进行排序，然后那个排序的一组联接的行利用 序列中第二个聚类维度列进行排序，依此类推。源事实表行然后以排 序的线性顺序存储在连续磁盘块的事实表内。

线性排序可以在聚类子句中指定，其中聚类维度列的序列被规定 为线性排序顺序指示的参数。作为规定线性排序顺序的聚类子句的例 子，以下创建sales表的DDL语句中的聚类子句规定由聚类查询构 成的一组联接的行要首先基于联接的行的countries.region列中的值 进行排序，然后一组排序的联接的行要基于countries.subregion列中 的值进行排序，然后该一组排序的联接的行要通过countries.name列 中的值进行排序。

利用线性排序顺序，当星型查询包含聚类标准中规定的聚类维度 列序列前缀上的过滤谓词时，例如，如果星型查询包含 countries.region列上的过滤谓词，则能够实现最大的I/O删减益处。 但是，当星型查询包含仅仅聚类维度列的后缀上的过滤谓词或不包含 任何聚类维度列上的过滤谓词时，利用线性排序只能实现有限的I/O 删减益处或没有实现I/O删减益处。因此，通常只当大多数星型查询 包含聚类维度列序列前缀上的过滤谓词时或当期望除I/O删减之外的 诸如数据压缩(例如，通过运行长度编码)的聚类益处时，使用线性 排序顺序。如果需要更大的I/O删减灵活性，则用户可以选择聚类标 准中的交错排序方法。

聚类标准-交错排序方法

利用交错排序方法，事实表上的I/O删减可以在查询中的某个过 滤谓词上独立于查询中的其它过滤谓词来执行。特别地，I/O删减可 以针对查询中聚类维度列上的过滤谓词执行，而不管该聚类维度列在 聚类标准中的位置。例如，利用以下规定交错排序顺序的聚类标准， 在sales表上的I/O删减可以独立于彼此在promotions.subcategory 和products.subcategory列中的一列或多列上执行。

可以使用各种不同的方法来实现事实表中存储的行的交错排序。 一般而言，方法包括使用诸如Z-order曲线或Hilbert空间填充曲线 的空间填充曲线，这些曲线具有如下属性，即，有限n-维空间中彼 此靠近的点被映射到同样彼此接近的一维的值。概念上，n-维空间被 分成n-维的“立方体”单元(cell)。按照惯例，n-维空间的分区被 称为“立方体”，尽管维度的数量n可以是两或大于三。立方体的 每个单元被分配值的范围，n维中的每一维都有一个值的范围。维度 的数量n等于在聚类标准中规定的聚类维度列的数量。

对于要以交错顺序在事实表中存储的一组源事实表行来说，该一 组源事实表行中的每个源事实表行都基于由对应于源事实表行的聚类 查询构成的联接的行中聚类维度列的值和分配给单元的值的范围被映 射到立方体中的单元。多于一个的源事实表行可以被映射到立方体中 的单元。立方体中的一些单元可能没有任何源事实表行映射到它们。 空间填充曲线对单元实行线性排序。分配给单元的源事实表行以由空 间填充曲线实行的线性顺序存储在事实表中，其具有以下效果，即， 在n-维立方体中彼此靠近的概念上相关的行在事实表内也彼此靠近。

在以上例子中，缺省的空间填充曲线通过指示BY  INTERLEAVED ORDER暗示。缺省的空间填充曲线可以是许多已 知空间填充曲线中的任何一个，诸如Z-order空间填充曲线或 Hilbert空间填充曲线。作为替代，具体使用的空间填充曲线可以在 聚类标准中明确规定。例如，不是BY INTERLEAVED ORDER，相 反可以规定BY HILBERT ORDER或BY ZORDER。

关于用于多维聚类的Z-order空间填充曲线使用的进一步信息可 以在以下找到：Morton，G.M，A Computer Oriented Geodetic Data  Base and A New Technique in File Sequencing，国际商业机器公司， 1966年。关于用于多维聚类的Hilbert空间填充曲线使用的进一步信 息可以在以下出版物的第14章找到：Warren，Henry S.，Hacker’s  Delight，Addison-Wesley Professional，2003年。

聚类标准–何时聚类

根据本发明的一种实施例，聚类标准规定何时要执行事实表的聚 类。特别地，用户可以规定哪些动作触发事实表的聚类。一般而言， 有两种类型的动作可以触发事实表的聚类。一种类型的动作是将数据 加载到事实表中。利用这种类型，添加到事实表中的数据按照与事实 表相关联的聚类标准进行聚类。另一种类型的动作是将数据从事实表 的一个存储位置移动到另一个存储位置。移动的数据按照与事实表相 关联的聚类标准进行聚类。

能够触发事实表聚类的数据加载类型动作的例子是提交数据建模 语言(DML)语句来将行添加到事实表。INSERT语句是用于将行 添加到表的DML语句的例子。例如，聚类sales事实表可以在提交 以下INSERT语句时被触发：

INSERT INTO sales SELECT promo_id,prod_id,...amount_sold FROM sales_external

响应于接收到以上INSERT语句，由SELECT子子句从 sales_external表中选择的行将是由自动生成的聚类查询选择并以排 序的顺序存储在sales事实表中的源事实表行。

能够触发事实表聚类的数据移动类型动作的例子是事实表上的分 区维护操作。很一般地，分区是表的所有行的严格子集，其与表的其 它行共享相同的列和约束定义，但是可以具有与其它行不同的物理属 性。例如，表的两个分区可以存储在单独的存储设备上。能够触发事 实表聚类的分区维护操作包括将事实表的分区从一个数据存储位置移 动到另一个位置。当移动事实表的分区触发聚类时，源事实表行是要 被移动的分区的所有行。

能够触发事实表聚类的数据移动类型动作的另一个例子是事实表 的在线重定义。“源”表的在线重定义一般包括定义和创建临时表并 将源表的数据拷贝到临时表中，同时在复制期间允许源表可以被访问 以进行读和写操作。临时表可以用相对于源表来说新的结构定义。例 如，临时表可以删除列、添加列或从源表中重命名列。此外，从源表 拷贝到临时表的数据可以被转换。在数据被拷贝到临时表时所做的对 源表的更新被存储在日志中。在拷贝期间，日志中的数据可以与临时 表进行同步。一旦拷贝完成，源表和临时表就被短暂地锁定用于排它 访问，以将日志中任何剩余的变化与临时表进行同步并最终完成重定 义。在重定义最终完成之后，临时表是“新的”源表并且“老的”源 表可以丢弃。

为了在事实表的在线重定义期间进行聚类，由聚类查询选择的源 事实表行是源表的行。与源表相关联的聚类标准在拷贝源表到临时表 时被用来排序源表的行。源表的排序的行以排序的顺序存储在临时表 中。源表的排序的行也可以进行由在线重定义定义的任何数据转换。 存储在临时表中的行也可以在拷贝期间当源表日志与临时表同步时进 行聚类。如将源表的行拷贝到临时表时那样，当源表日志中的行与临 时表进行同步时，与源表相关联的聚类标准被用来在临时表中聚类源 表日志的行。

何时在事实表上发生聚类可以由用户在聚类子句中规定。例如， 以下创建sales表的DDL语句中聚类子句规定聚类应该在数据加载 动作(例如，当行被插入到sales表中时)和数据移动动作时(例如， 当sales表被分区或当sales表被在线重定义时)发生。

这里，关键字序列“YES ON LOAD”用来指示sales表的聚类 应该在数据加载动作时发生。关键字序列“YES ON DATA  MOVEMENT”用来指示sales表的聚类还应该在数据移动动作时发 生。缺省地，如果聚类在数据加载动作和数据移动动作时执行，则关 键字序列“NO ON LOAD”和/或“NO ON DATA MOVEMENT” 可用来选择性地禁用缺省聚类选项。当然，也可以使用其它的语法来 传达相同的语义。

处理DDL语句中的聚类子句

如上所述，定义事实表的DDL语句可能包含规定聚类标准的聚 类子句。例如，以下DDL语句包含将聚类标准添加到sales表的聚 类子句。

ALTER TABLE sales ADD CLUSTERING

sales JOIN promotions ON(sales.promo_id＝promotions.promo_id)

JOIN products ON(sales.prod_id＝products.prod_id)

BY INTERLEAVED ORDER(promotions.subcategory,

products.subcategory)

YES ON LOAD YES ONDATA MOVEMENT

用于处理DDL语句中聚类子句的数据库服务器组件在图2中进 行说明。首先，接收到定义事实表并带有聚类子句的DDL语句201。 语句201可以从各种不同的源接收。例如，语句201可以通过命令行 或图形用户界面从用户接收。作为替代，语句201可以从另一个计算 进程中接收，例如，将语句201通过网络发送到数据库服务器的远程 计算进程。这些只是语句201可能来源的一些例子，并且本发明不限 于从中可以接收语句201的任何特定源。

在接收到语句201时，语句201被提供给解析例程202。解析例 程202解析语句201，以产生表定义控制结构203。除表定义控制结 构203中其它可能的信息之外，结构203还规定DDL语句201中聚 类子句的一个或多个元素。结构203的这些元素可以包括任何聚类指 示，诸如事实表的聚类是否在数据加载动作时、数据移动动作时或数 据加载和数据移动动作这两者时发生。结构203的元素也可以包括一 个或多个聚类维度列、一个或多个聚类维度表以及在聚类子句中规定 的联接标准。

表定义执行驱动器204使用结构203来验证聚类子句并在数据库 中为表示聚类标准的定义的表创建表元数据。为了进行验证，驱动器 204验证聚类维度列和聚类维度表的存在。如果聚类维度表中的一个 或聚类维度列中的一个在数据库中不存在，则驱动器204可以利用错 误拒绝语句201。驱动器204还验证联接标准。联接标准的验证包括 在引用聚类维度表的事实表的外键列上执行外键验证。外键验证的至 少一部分包括驱动器204验证在联接标准中引用的聚类维度表的所有 联接列都具有唯一键约束并且由该联接标准规定的联接都是等值联接。 执行这种验证是确保当聚类查询基于联接标准联接源事实表行和聚类 维度表时，在联接的行集合中没有重复的源事实表行。如果驱动器 204确定聚类维度列的联接列中的一个不具有唯一键约束，则驱动器 204可以利用错误拒绝语句201。

假设语句201没有错误，则一旦被验证，驱动器204就将元数据 存储在数据库中表示聚类标准。例如，驱动器204可以在数据库的数 据字典表中或者在关于数据库数据的另一个信息储存库中存储元数据。

用于交错排序的函数

根据本发明的一种实施例，提供了用于在聚类查询中使用来将行 以交错顺序存储在事实表中的函数。该函数接受一至四个参数(表达 式)，并且返回原始串作为输出。

raw_string＝ORA_CLUSTERING(expr1[,expr2,expr3,expr4])

函数ORA_CLUSTERING把参数当作二进制数据并且评估这些 二进制参数上的空间填充曲线(例如，Hilbert空间填充曲线或Z- order函数)。评估是基于参数二进制表示的位混合。特别地，从每 个参数取第一位，然后从每个参数取第二位，然后从每个参数取第三 位，依此类推，以创建作为结果的位串。为了给每个参数一致的权重， 可以用填充值(例如，字节值0x00)将参数填充到其最大长度。然 后，返回的原始串的大小将是作为填充的参数的长度之和。为了效率， 函数的参数可以被截取成最大允许的字节数(例如，1000)。

在加载时聚类事实表

如前面提到的，与事实表相关联的聚类标准可以规定聚类要在加 载到事实表中的行上执行。将行加载到表中的典型方法是利用包含 SELECT子查询的INSERT DML语句。例如，以下INSERT语句 基于选自sales_external表中的行将行附加到sales表。

INSERT/*+APPEND*/INTO sales SELECT promo_id, PROD_ID,...amount_sold FROM sales_external.

根据本发明的一种实施例，将行加载到与聚类标准相关联的表的 DML语句被自动地转换成聚类查询。执行聚类查询而不是原始 DML语句来将行以排序的顺序加载到与聚类标准相关联的表中。生 成的聚类查询包括选择源事实表行的原始DML语句的select子查询、 聚类标准的联接标准以及通过聚类维度列并且以由聚类标准指定的排 序顺序(例如，线性或交错排序顺序)排序源事实表行的ORDER  BY子句。联接标准可以按需进行转换，使得事实表和维度表之间的 联接是左外联接(left outer join)，其中事实表是左侧表，使得由聚 类查询构成的一组联接的行中没有丢失的源事实表行。

作为例子，考虑以下创建sales表的DDL语句中规定的聚类标 准。

这里，源事实表行要基于promotions维度表的subcategory列和 products维度表的subcategory列以线性顺序在sales事实表中进行 聚类。

现在假设以下将行加载到sales事实表中的DML语句被提交给 数据库服务器。

INSERT INTO sales SELECT promo_id,prod_id,...

amount_sold FROM sales external

在接收到这个DML语句时，数据库服务器可以自动地将该 DML语句转换成以下聚类查询。

INSERT INTO sales

SELECT promo_id,prod_id,...amount_sold

FROM sales_external

LEFT OUTER JOIN promotions ON(sales.promo_id＝ promotions.promo_id)

LEFT OUTER JOIN products ON(sales.prod_id＝ products.prod_id)

ORDER BY promotions.subcategory,products.subcategory

在这个示例聚类查询中，包括了原始DML语句的select子查询。 因此，聚类查询将选择与原始DML语句会选择的相同的一组源事实 表行。联接标准已被转换成sales事实表与promotions和products 维度表之间的强制左外联接。添加了order by子句以按照聚类标准 中的排序指示BY LINEAR ORDER通过promotions.subcategory和 products.subcategory列的值以线性顺序排序源事实表行。

如所讨论的，源事实表行可以基于空间填充曲线以线性顺序或交 错顺序进行排序。为了这样做，数据库服务器可以生成调用聚类查询 的ORDER BY子句中的CLUSTERING函数的聚类查询。例如，假 设以上聚类标准不是规定BY LINEAR ORDER，而是规定BY INTERLEAVED ORDER，则数据库服务器可以自动地将DML语句 转换成以下聚类查询。

INSERT INTO sales

SELECT promo_id,prod_id,...amount_sold FROM sales_external

LEFT OUTER JOIN promotions ON(sales.promo_id＝ promotions.promo_id)

LEFT OUTER JOIN products ON(sales.prod_id＝ products.prod_id)

ORDER BY ORA_CLUSTERING(promotions.subcategory, products.subcategory)

这个聚类查询类似于当聚类标准中规定BY LINEAR ORDER时 生成的聚类查询。这个聚类查询的不同之处在于 ORA_CLUSTERING函数在ORDER BY子句中调用以实现源事实 表行的交错排序顺序。

区域地图(ZONEMAPS)

根据本发明的实施例，表扫描期间的I/O删减在数据库服务器中 通过使用区域地图得到促进。一般而言，区域地图是数据库访问结构， 其允许数据库服务器在扫描表时跳过表的某些磁盘块的磁盘扫描，因 为基于区域地图，已知跳过的磁盘块不会包含与正在为其执行表扫描 的查询相关的数据。

在高的级别，为表生成区域地图包括将表的磁盘块分成称作“区 域”的连续的磁盘块集合。对于每个区域，确定兴趣列的最小和最大 值。根据本发明的实施例，兴趣列可以是正在为其生成区域地图的表 的列(例如，事实表的列)或其它表的列(例如，维度表的列)。正 在为其生成区域地图的表在下文中称作“分区表”。区域地图为其维 护最小和最大值的“兴趣”列在下文中称作区域地图的“分区列”。 根据本发明的实施例，区域地图的分区列不必是(但可以是)分区表 的列。

当数据库服务器执行利用具有常量谓词值V的过滤谓词限定分 区列C之一的查询时，数据库服务器可以将值V与为区域确定的列 C的最小值和最大值进行比较，以确定该区域是否可能包含满足过滤 谓词的数据。如果该区域不可能满足查询的任何过滤谓词，则该区域 的磁盘块可以在分区表的表扫描期间被跳过。

过滤谓词可以是“分区列C<谓词运算符>常量V”形式的关系 谓词，其中<谓词运算符>是相等运算符(例如，“＝”)、小于或等 于运算符(例如，“<＝”)、小于运算符(例如，“<”)、大于运 算符(例如，“>”)、大于或等于运算符(例如，“>＝”)或不等 于运算符(例如，“<>”)。在谓词运算符是等于运算符的情况下， 如果谓词值V小于用于该区域的列C的最小值和如果谓词值V大于 用于该区域的列C的最大值，则该区域不可能满足过滤谓词。在谓 词运算符是小于运算符的情况下，如果谓词值V小于或等于用于该 区域的列C的最小值，则该区域不可能满足过滤谓词。在谓词运算 符是小于或等于运算符的情况下，如果谓词值V小于用于该区域的 列C的最小值，则该区域不可能满足过滤谓词。在谓词运算符是大 于运算符的情况下，如果谓词值V大于或等于用于该区域的列C的 最大值，则该区域不可能满足过滤谓词。在谓词运算符是大于或等于 运算符的情况下，如果谓词值V大于用于该区域的列C的最大值， 则该区域不可能满足过滤谓词。在谓词运算符是不等于运算符的情况 下，如果用于该区域的列C的最小值和最大值相等并且谓词值V等 于该最小和最大值，则该区域不可能满足过滤谓词。

作为替代，过滤谓词可以包含指定可替代常量值列表的IN列表， 例如，“where countries.region IN('Western Europe'，'Eastern  Europe')”。在过滤谓词包含IN列表的情况下，如果IN列表中的 每个谓词值V小于用于该区域的列C的最小值和如果IN列表中的每 个谓词值V大于用于该区域的列C的最大值，则该区域不可能满足 过滤谓词。

作为还有的另一种替代，过滤谓词可以包含具有常量字符串值或 作为通配符前缀的常量字符串值的LIKE运算符，例如， “countries.region LIKE'Western％'”。在过滤谓词包含具有常量 字符串值或作为通配符前缀的常量字符串值的LIKE运算符的情况下， 如果被LIKE运算符覆盖的字符串值区间的上界小于用于该区域的列 C的最小值或者如果被LIKE运算符覆盖的字符串值区间的下界大于 用于该区域的列C的最大值，则该区域不可能满足过滤谓词。例如， 如果上界串“Western”小于用于区域的列C的最小值或者如果下界 串“Western”大于用于区域的列C的最大值，则该区域不可能满足 “countries.region LIKE'Western％'”过滤谓词。

区域地图实例

作为利用区域地图来促进数据库服务器中I/O删减的例子，考虑 图3的数据库表300。表300有五列，命名为order_key(顺序键)、 ship_date(运送日期)、receipt_date(接收日期)、destination (目的地)和quantity(数量)。表300有八行，在图3中标记为 301-308。实际的实施例可能有多得多的行，数量为数百万、数十亿、 甚至更多。

现在参考图4，它说明了表300的行301-308可以如何以排序的 顺序存储在磁盘400的一部分上，即磁盘块401-404中。磁盘部分 400可以对应于磁盘的范围、片段、表空间或其它逻辑部分。磁盘部 分400被数据库服务器逻辑地视为以线性顺序布置的单独可寻址的一 组磁盘块。磁盘部分400的磁盘块按照其线性顺序被数据库服务器连 续地编号。当表的行以排序的顺序(例如，线性顺序或交错顺序)存 储在连续的磁盘块中时(例如，表300的行301-308存储在磁盘块 401-404中)，这些行被称为在表中被“聚类”。更一般而言，该表 被称为“聚类”的表。

在这个例子中，表300的行301-308基于ship_date列的值以线 性排序顺序存储。特别地，行301和302存储在磁盘块401中、行 303和304存储在磁盘块402中、行305和306存储在磁盘块403中 并且行307和308存储在磁盘块404中。实际的实施例中每个磁盘块 可以具有更多或更少的行和/或每个磁盘块可以具有不同数量的行或 在表内具有包含不同数量磁盘块的磁盘块。另外，表的行可以存储在 多得多的磁盘块中，数量为数十、数百、数千、数百万或更多。还有， 磁盘块可以存储多于一个表的行。

继续说明用于I/O删减的区域地图的使用，用于表300的区域地 图可以构造成其中每个区域由两个磁盘块组成。区域地图的每个区域 的最大磁盘块数量在本文中称为区域地图的“区域地图规模”。在一 种实施例中，区域地图的区域地图规模是用户可配置的。一般而言， 选择的区域地图规模是在最小化区域地图的区域数量和最大化I/O删 减效率之间的权衡，其中最小化区域地图的区域数量时，区域地图规 模相对较大，最大化I/O删减效率时，区域地图规模相对较小。

在一种实施例中，用户规定区域地图缩放因子S作为大于零的 整数值。然后数据库服务器将区域地图规模计算为2^S(即，2的S次 幂，其中S>0)。例如，如果用于区域地图的区域地图缩放因子是 10，则该区域地图的区域地图规模是1024个磁盘块。规定区域地图 缩放因子并计算区域地图规模的其它方式也是可能的并且本发明不限 于任何特定的方式。另外，数据库服务器可以基于各种因素计算用于 区域地图的缺省区域地图规模，其中因素包括分区表的行的数量、分 区表的磁盘块的数量以及磁盘块大小。

返回到例子，图5说明表300上的区域地图500。区域地图500 可以表示为表，并且可以如此存储在数据库中。在这个例子中，区域 地图缩放因子是1，并且区域地图规模是2¹或2。因此，图4的四个 磁盘块401-404被分成如图5中示出的两个区域501和502。每个区 域501和502包含两个连续的磁盘块。特别地，区域501包含连续的 磁盘块401和402，并且区域502包含连续的磁盘块403和404。

区域地图500的每一行511和512对应于区域地图的区域501 和502。特别地，行511对应于区域501并且行512对应于区域502。 区域地图500包括区域磁盘块范围列513，其为每个区域指定被该区 域覆盖的一组连续磁盘块中的第一块。更一般而言，列513为区域地 图500的每个区域指示或指定被区域覆盖的连续磁盘块的范围。例 如，假设磁盘块401-404被数据库服务器分别连续编号为1，2，3和 4，则列513中的值指示区域501覆盖连续的磁盘块401和402，并 且区域502覆盖连续的磁盘块403和404。区域地图500的列还包括 用于在其上构造区域地图500的每个分区列的最小值列514和最大 值列515。

基于区域地图500并且给定以下具有ship_date列上的过滤谓词 的查询，执行表300的全表扫描的数据库服务器可以跳过磁盘块3和 4的扫描，因为基于区域地图500的行512中列514B和515B中存储 的最小和最大值，那些磁盘块不会包含与查询相关的行。而是，只有 磁盘块1和2需要扫描。

SELECT*FROM lineitem WHERE ship_date＝'01-01-2008'

维度区域地图

“维度区域地图”是基于维度表的至少一列的聚类事实表的区域 地图。事实表的维度区域地图基于查询中维度表的列上的过滤谓词促 进了事实表的I/O删减。根据一种实施例，维度区域地图由“维度区 域地图查询”创建。该维度区域地图查询以物化(materialized)视 图的形式在数据库中创建区域地图。为了填充该视图，维度区域地图 查询从聚类事实表中选择行并且将它们与一个或多个维度表的行联接。 联接基于事实表的外键列和维度表的唯一键列。

根据本发明的一个方面，维度区域地图查询通过调用“区域标识 符分配”函数将选择的事实表行分组成区域。区域标识符分配函数将 选自事实表的行的行标识符映射到维度区域地图的区域。更具体而言， 在同一N个连续数据块内选自聚类事实表的所有行被映射到同一区 域，其中N基于维度区域地图的区域地图规模。此外，维度区域地 图查询为每个区域每个分区列计算最小值和最大值并将计算的值存储 在物化视图中。

例如，考虑按照在以下CREATE TABLE DDL语句中规定的以 下聚类标准基于countries(国家)维度表的region(地区)和 subregion(子地区)列聚类的sales事实表。

为了利用基于以上聚类标准聚类的sales事实表，sales事实表上 的维度区域地图可以通过以下维度区域地图查询生成。

CREATE MATERIALIZED ZONEMAP sales_zmap AS

SELECT SYS_OP_ZONE_ID(f.rowid),

MIN(c.region),MAX(c.region),

MIN(c.subregion),MAX(c.subregion)

FROM sales f LEFT JOIN countries c ON(f.country_id＝ c.country_id)

GROUP BY SYS_OP_ZONE_ID(f.rowid)

这里，执行sales事实表和countries维度表之间的左外联接，以 确保考虑了区域地图中所有选自sales事实表用于联接的行。 SYS_OP_ZONE_ID函数是区域标识符分配函数。 SYS_OP_ZONE_ID函数将输入行标识符映射到区域标识符。根据 SYS_OP_ZONE_ID，属于sales事实表的连续N个数据块集合的所 有行标识符被映射到同一区域，其中N是区域地图规模。GROUP  BY子子句用来为每个区域的两个分区列(countries.region和 countries.subregion)正确地计算最小值和最大值。结果产生的物化 视图sales_zmap将具有五列，一列存储区域识别符并且两列用于两 个分区列中的每一列，存储每个区域计算出的最小和最大值。

sales_zmap物化视图的列结构在图6中进行说明。如所示出的， 物化视图600有一列用于存储区域标识符(zone_id)和两列用于 countries.region和countries.subregion列中的每一列，存储为区域 计算出的最小和最大值。视图600的每一行对应于sales_zmap维度 区域地图的一个区域。

如提到的，当执行包含维度表列上过滤谓词的星型查询时，维度 区域地图促进了事实表的扫描删减。例如，sales_zmap维度区域地 图可以被数据库服务器使用，以在执行以下查询时促进I/O删减。

SELECT country_name,SUM(sales)

FROM sales f JOIN countries ON(sales.country_id＝

countries.country_id)

WHERE countries.region＝’Europe’AND

countries.subregion＝’West Europe’

GROUP BY countries.name

这里，sales事实表上的查询包含两个过滤谓词，每个分区列上 一个。这些列也是根据以上聚类标准以交错顺序聚类sales事实表的 列。基于这个查询，其中任一过滤谓词值(即，“Europe(欧洲)” 或“West Europe(西欧)”)都不在由维度区域地图中的最小和最 大值设置的范围内的区域的扫描可以被跳过。

如果事实表的聚类是在多个维度表上，则维度区域地图的创建类 似于其中事实表的聚类是在单个维度表上的情况。例如，如果sales 事实表通过countries和products维度表而不仅仅是如以上例子中的 countries维度表进行聚类，则可以执行以下维度区域地图查询区域 地图，以生成用于sales表的维度区域地图。

CREATE MATERIALIZED ZONEMAP sales_zmap AS

SELECT SYS_OP_ZONE_ID(f.rowid),

MIN(countries.region),MAX(countries.region),

MIN(countries.subregion),MAX(countries.subregion),

MIN(products.category),MAX(products.category),

MIN(products.subcategory),MAX(products.subcategory)

FROM sales f LEFT JOIN countries c ON(f.country_id＝ c.country_id)

LEFT JOIN products p ON(f.prod_id＝p.prod_id)

GROUP BY SYS_OP_ZONE_ID(f.rowid)

同单个维度的情况，维度区域地图查询执行事实表和每个维度表 之间的左外联接。因此，事实表中的行以行在事实表中存储的顺序 (例如，以聚类事实表时确定的线性或交错顺序)分配给区域地图的 区域。特别地，在事实表的前N个磁盘块中存储的事实表的行被分 配给区域地图的第一区域，在事实表的接下来N个磁盘块中存储的 事实表的行被分配给区域地图的第二区域，依此类推，其中N是区 域地图规模。

创建维度区域地图

如提到的，用于事实表的维度区域地图可以利用维度区域地图查 询来创建。在内部，区域地图可以被数据库服务器实现为物化视图。 根据本发明的一种实施例，维度区域地图查询是以关键字 “CREATE MATERIALIZED ZONEMAP”开始的DDL语句。在 本描述中根据特定的语法提供了CREATE MATERIALIZED ZONEMAP DDL语句的例子。当然，也可以使用其它的语法来传达 相同的语义。

用于创建维度区域地图的维度区域地图查询具有多个特征。其一， 维度区域地图查询可以引用事实表以及一个或多个维度表，每个维度 表左外联接到事实表。即，在区域地图查询中，事实表是在到维度表 的每个联接的左侧。这确保在区域地图中考虑了事实表的所有行。其 二，维度区域地图查询包含select子查询。select子查询包含区域标 识符分配函数的一次调用，连同事实表的列和/或维度表的列上的最 小和最大函数对调用。其三，维度区域地图查询包含GROUP BY子 句，该子句包含区域标识符分配函数的一次调用。区域标识符分配函 数由数据库服务器实现并且接受事实表中行的标识符作为输入，并且 返回其中输入事实表的行被分配到的维度区域地图的区域的标识符作 为输出。该分配是基于其中存储行的事实表的磁盘块和维度区域地图 的区域地图尺寸。维度区域地图查询的例子是：

CREATE MATERIALIZED ZONEMAP sales_zmap AS

SELECT SYS_OP_ZONE_ID(f.rowid),

MIN(countries.region),MAX(countries.region),

MIN(countries.subregion),MAX(countries.subregion),

MIN(products.category),MAX(products.category),

MIN(products.subcategory),MAX(products.subcategory)

FROM sales f LEFT JOIN countries c ON(f.country_id＝ c.country_id)

LEFT JOIN products p ON(f.prod_id＝p.prod_id)

GROUP BY SYS_OP_ZONE_ID(f.rowid)

根据一种实施例，维度区域地图的区域地图缩放因子可以在维度 区域地图查询中规定。例如，在以下维度区域地图查询中，规定区域 地图缩放因子是8。因此，维度区域地图的每个区域将跨越最多2⁸或 256个磁盘块。在没有明确的区域地图缩放因子时，数据库服务器可 以使用缺省的区域地图缩放因子。

CREATE MATERIALIZED ZONEMAP sales_zmap SCALE 8 AS

SELECT SYS_OP_ZONE_ID(f.rowid),

MIN(countries.region),MAX(countries.region),

MIN(countries.subregion),MAX(countries.subregion),

MIN(products.category),MAX(products.category),

MIN(products.subcategory),MAX(products.subcategory)

FROM sales f JOIN countries c ON(f.country_id＝c.country_id)

JOIN products p ON(f.prod_id＝p.prod_id)

GROUP BY SYS_OP_ZONE_ID(f.rowid)

在另一种实施例中，响应于规定聚类标准的DDL语句，所述 DDL语句包含作为聚类指示的子子句(sub-clause)的、创建维度区域 地图的指示，维度区域地图查询被自动地生成，并且被数据库服务器 执行。在一种实施例中，基于聚类标准创建维度区域地图的聚类标准 指示包含关键字“WITH MATERIALIZED ZONEMAP”。例如， 以下具有聚类标准的DDL语句创建“sales”事实表并且基于 “countries”维度表的“countries.region”和“countries.subregion” 列中的值按照线性排序顺序聚类“sales”事实表。该聚类标准还规定 维度区域地图应该在聚类“sales”事实表时创建。

响应于以上DDL语句，在“sales”事实表已根据在DDL语句 中规定的聚类标准聚类之后，数据库服务器可以创建以下维度区域地 图查询来创建请求的区域地图：

CREATE MATERIALIZED ZONEMAP sales_zmap AS

SELECT SYS_OP_ZONE_ID(sales.rowid),

MIN(countries.region),MAX(countries.region),

MIN(countries.subregion),MAX(countries.subregion)

FROM sales LEFT JOIN countries ON(sales.country_id＝ countries.country_id)

GROUP BY SYS_OP_ZONE_ID(sales.rowid)

扫描删减

根据本发明的一种实施例，事实表的维度区域地图由数据库服务 器在事实表的表扫描期间使用。维度区域地图被数据库服务器用于 I/O删减。特别地，数据库服务器使用维度区域地图在表扫描期间跳 过磁盘块的整个区域。由于维度区域地图的分区列可以是维度表的列， 因此基于星型查询中维度表上过滤谓词的扫描删减是可能的。

图7是根据本发明的实施例利用维度区域地图的事实表的磁盘扫 描700的流程图。在执行针对包含维度区域地图的一个或多个分区列 上过滤谓词的事实表的星型查询或其它查询的上下文中，扫描700可 以由数据库服务器执行。

查询可以包含仅仅事实表、仅仅一个或多个维度表、或在事实表 和一个或多个维度表两者上的过滤谓词。分区列可以仅仅是事实表的 列、仅仅是一个或多个维度表的列、或来自事实表和一个或多个维度 表两者的列。

分区列可以是各种不同的数据类型，包括数值、时间戳、行标识 符、浮点型、双精度型以及字符数据类型。如上所述，查询中分区列 上的过滤谓词可以：(1)是“分区列C<谓词运算符>常量V”形式 的关系谓词，其中<谓词运算符>是等于运算符(例如，“＝”)、小 于或等于运算符(例如，“<＝”)、小于运算符(例如，“<”)、 大于运算符(例如，“>”)、大于或等于运算符(例如，“>＝”) 或不等于运算符(例如，“<>”)，(2)包含规定可替代常量值列 表的IN列表，例如，“where countries.region IN(‘Western  Europe’，‘Eastern Europe’)”，或(3)包含具有常量字符串 值或作为通配符前缀的常量字符串值的LIKE运算符，例如， “countries.region LIKE'Western％'”。

查询可以利用联接词、析取或联接词与析取的混合将包括除分区 列之外其它列上的过滤谓词合并成对应于该查询WHERE子句的表 达式。取决于根据联接词和析取的WHERE子句表达式的构造，如 果表达式中分区列上所有过滤谓词中的一个或多个所有都没有被满足， 则表达式作为整体不可能被满足。例如，如果在表达式“WHERE  countries.region＝'Europe'AND countries.subregion＝‘West  Europe’”中任一过滤谓词都没有被满足，则表达式作为整体不能 被满足。作为另一个例子，如果在表达式“WHERE  countries.region＝‘Europe’OR countries.subregion＝'West Europe'” 中两个过滤谓词都没有被满足，则表达式作为整体不能被该行满足。

如果所有都没有被满足则意味着表达式作为整体不能被满足的查 询，其WHERE子句表达式中分区列上过滤谓词的最小集合在下文 称为查询的“删减”过滤谓词集合。查询的删减过滤谓词集合可以是 当WHERE子句表达式合并联接词中的过滤谓词时查询中分区列上 所有过滤谓词的严格子集。当针对事实表的查询具有非空的删减过滤 谓词集合时，可以在事实表的扫描700期间使用维度区域地图用于 I/O删减。如果查询具有空的删减过滤谓词集合时，则维度区域地图 不能为该查询提供I/O删减的益处。以下图7的扫描700的描述假设 针对事实表执行的查询具有非空的删减过滤谓词集合。

初始地，扫描700在事实表的初始磁盘块开始(方框701)。初 始磁盘块可以是事实表的第一个磁盘块，或对应于要扫描的事实表的 行标识符规定区间中第一个行标识符的事实表的后续磁盘块。回忆事 实表的磁盘块是被连续编号的。因此，存在构成事实表磁盘块的顺序 次序。

接着，包含初始磁盘块的维度区域地图的区域被确定(方框 702)。通常，这包括将初始磁盘块的磁盘块编号映射到覆盖包括初 始磁盘块的磁盘块区间的维度区域地图的区域。为了该目的，数据库 服务器可以维护区域标识符的磁盘块编号间的映射。作为一种可能的 映射的例子，维度区域地图可以具有存储维度区域地图的每个区域中 第一磁盘块编号的唯一键列。

作为磁盘块编号和维度区域地图区域之间可能的映射的例子，图 8说明具有列813的维度区域地图800的列结构，其中列813存储用 于维度区域地图800的区域的开始磁盘块编号。特别地，根据维度区 域地图800，具有区域标识符1的区域在磁盘块编号1处开始并且具 有区域标识符2的区域在磁盘块编号3处开始。由于磁盘块编号是连 续的，因此，如果开始磁盘块编号列的值按顺序取得，则开始磁盘编 号的值构成由维度区域地图的区域覆盖的磁盘块区间。另外，维度区 域地图的区域地图规模在创建维度区域地图时被建立。因此，维度区 域地图的区域地图规模在扫描700时是已知的。例如，维度区域地图 800的区域地图规模是二(2)。因此，在维度区域地图800中，区 域1覆盖磁盘块1至2并且区域2覆盖磁盘块3至4。

扫描700的剩余步骤703-709表示在维度区域地图的区域列表上 迭代，其开始于在步骤702确定的第一区域并且继续到列表中的最后 一个区域。列表中区域的顺序对应于被磁盘上的区域覆盖的磁盘块的 顺序。因此，在区域列表上从第一区域迭代到最后一个区域表示从第 一个区域的初始磁盘块开始到最后一个区域的最后一个磁盘块的事实 表的顺序扫描。列表中的一些区域可以取决于维度区域地图中存储的 最小和最大值被跳过。在步骤703，迭代从被设置为第一区域的当前 区域变量开始。

在步骤704，做出检查，以确定当前区域变量是否引用维度区域 地图的区域。如果初始磁盘块不在区域地图的任何区域内，则当前区 域变量不可能引用维度区域地图的区域。在这种情况下，执行从初始 磁盘块开始的事实表的全扫描(方框705)。如果已处理区域列表中 的最后一个区域，则当前区域变量也不可能在步骤709之后引用维度 区域地图的区域。在这种情况下，如果事实表没有更多的磁盘块要扫 描，则扫描700结束，或者，扫描700在最后一个区域的最后一个磁 盘块之后从第一磁盘块开始继续。

如果当前区域变量引用维度区域地图的区域，则在步骤705，数 据库服务器确定当前区域的扫描是否可以被跳过。该确定是基于查询 的一个或多个删减过滤谓词集合和如在维度区域地图中为当前区域所 记录的用于分区列的最大和最小值做出的。特别地，对于集合中的给 定删减过滤谓词，谓词值或删减过滤谓词的值与如在维度区域地图中 为区域所记录的用于删减过滤谓词的分区列的最小和/或最大值进行 比较。执行比较以确定当前区域是否可能包含满足删减过滤谓词的事 实表的行。具体而言，如果删减过滤谓词规定维度表的分区列，则执 行该比较来确定当前区域是否可能包含如果与维度表联接则满足删减 过滤谓词的事实表的行。如果删减过滤谓词规定事实表的分区列，则 执行比较来确定当前区域是否可能包含满足删减过滤谓词的事实表的 行。因此，维度区域地图的分区列不限于仅仅事实表的列，而是可以 包括维度表的列或只有维度表的列。如果集合中任何一个删减过滤谓 词都不可能被当前区域的行满足，则扫描700可以跳过当前区域的磁 盘块的磁盘扫描。如果集合中每个删减过滤谓词都可能被当前区域的 行满足，则扫描700不能跳过当前区域并且执行当前区域的磁盘块的 磁盘扫描。

当将谓词值或删减过滤谓词的值与如为维度区域地图中的区域所 记录的用于删减过滤谓词的分区列的最小和/或最大值进行比较时， 执行的比较取决于删减过滤谓词的类型。一般而言，删减过滤谓词可 以是三种不同类型之一：(1)删减过滤谓词可以是“分区列C<谓词 运算符>常量V”形式的关系谓词，(2)删减过滤谓词可以包含规定 可替代常量值列表的IN列表，或(3)删减过滤谓词可以包含具有 常量字符串值或作为通配符前缀的常量字符串值的LIKE运算符。

在删减过滤谓词是关系谓词的情况下，<谓词运算符>可以是等 于运算符(例如，“＝”)、小于或等于运算符(例如，“<＝”)、 小于运算符(例如，“<”)、大于运算符(例如，“>”)、大于 或等于给运算符(例如，“>＝”)或不等于运算符(例如， “<>”)。在谓词运算符是等于运算符的情况下，如果谓词值V小 于用于当前区域的列C的最小值和如果谓词值V大于用于当前区域 的列C的最大值，则当前区域不可能满足删减过滤谓词。在谓词运 算符是小于运算符的情况下，如果谓词值V小于或等于用于当前区 域的列C的最小值，则当前区域不可能满足删减过滤谓词。在谓词 运算符是小于或等于运算符的情况下，如果谓词值V小于用于当前 区域的列C的最小值，则当前区域不可能满足过滤谓词。在谓词运 算符是大于运算符的情况下，如果谓词值V大于或等于用于该区域 的列C的最大值，则该区域不可能满足删减过滤谓词。在谓词运算 符是大于或等于运算符的情况下，如果谓词值V大于用于当前区域 的列C的最大值，则当前区域不可能满足删减过滤谓词。在谓词运 算符是不等于运算符的情况下，如果用于当前区域的列C的最小值 和最大值相等并且谓词值V等于用于当前区域的列C的最小和最大 值，则当前区域不可能满足删减过滤谓词。

作为替代，删减过滤谓词可以包含规定可替代常量值列表的IN 列表，例如，“where countries.region IN('Western Europe'， 'Eastern Europe')”。在删减过滤谓词包含IN列表的情况下，如果 IN列表中每个谓词值V小于用于当前区域的列C的最小值和如果 IN列表中每个谓词值V大于用于当前区域的列C的最大值，则当前 区域不可能满足删减过滤谓词。

作为还有的另一种替代，删减过滤谓词可以包含具有常量字符串 值或作为通配符前缀的常量字符串值的LIKE运算符，例如， “countries.region LIKE'Western'”，“countries.region LIKE 'Western％'”，“countries.region LIKE'Western％abc'”或 “countries.region LIKE'Western％abc％def'”。在这些例子中，串 “Western”是常量字符串值并且‘％’字符是通配符。在删减过滤 谓词包含具有常量字符串值或作为通配符前缀的常量字符串值的 LIKE运算符的情况下，如果由LIKE运算符覆盖的字符串值的区间 上界小于用于当前区域的列C的最小值或者如果由LIKE运算符覆 盖的字符串值的区间下界大于用于当前区域的列C的最大值，则当 前区域不可能满足删减过滤谓词。例如，如果上界串“Western”小 于用于当前区域的列C的最小值或者如果下界串“Western”大于用 于当前区域的列C的最大值，则当前区域不可能满足 “countries.region LIKE'Western％'”删减过滤谓词。

如果查询中删减过滤谓词集合中的每个删减过滤谓词都可能被当 前区域满足，则执行当前区域的磁盘块的磁盘扫描(步骤707)。如 果当前区域是第一区域，则当前区域的扫描在初始磁盘块开始，并且 前进到第一区域的最后一个磁盘块。由于区域覆盖一组连续的磁盘块 并且磁盘块被连续地编号，因此第一区域的最后一个磁盘块可以根据 区域列表中下一区域的第一磁盘块的编号来确定。如果当前区域不是 第一区域，则当前区域的扫描在当前区域的第一磁盘块开始并且前进 到当前区域的最后一个磁盘块。作为替代，如果查询中没有删减过滤 谓词能被当前区域满足，则当前区域的扫描被跳过并且扫描前进到步 骤708。

在步骤708，确定区域列表中当前区域之后的下一区域。在步骤 709，当前区域变量被设置为下一区域并且扫描700返回到步骤704 来考虑新的当前区域。

区域地图驱动的扫描

图7用于I/O删减的方法是被开始于初始磁盘块的事实表的扫描 驱动的。当在事实表的扫描期间遇到区域时，咨询维度区域地图来确 定哪些区域可以被跳过。作为扫描驱动的I/O删减的替代，区域地图 驱动的事实表扫描也是可能的。根据这种替代的方法，在发起扫描之 前咨询维度区域地图来确定维度区域地图的哪些区域可能满足查询中 的至少一个删减过滤谓词。这种咨询产生需要被扫描的连续磁盘块的 范围。然后只在这些区域上执行扫描，并且其它不可能满足任何删减 过滤谓词的区域都不扫描。

硬件概述

根据一种实施例，本文所描述的技术由一个或多个专用计算设备 实现。专用计算设备可以是硬连线的以执行所述技术，或者可以包括 诸如持久性地编程为执行所述技术的一个或多个专用集成电路 (ASIC)或现场可编程门阵列(FPGA)的数字电子设备，或者可以 包括编程为按照固件、存储器、其它储存器或者其组合中的程序指令 执行所述技术的一个或多个通用硬件处理器。这种专用计算设备还可 以组合定制的硬连线逻辑、ASIC或FPGA与定制的编程来实现所述 技术。专用计算设备可以是台式计算机系统、便携式计算机系统、手 持式设备、联网设备或者结合硬连线和/或程序逻辑来实现所述技术 的任何其它设备。

例如，图9是说明本发明的实施例可以在其上实现的计算机系统 900的框图。计算机系统900包括总线902或者用于传送信息的其它 通信机制，以及与总线902耦合用于处理信息的硬件处理器904。硬 件处理器904可以是例如通用微处理器。

计算机系统900还包括耦合到总线902用于存储信息和要由处理 器904执行的指令的主存储器906，诸如随机存取存储器(RAM) 或其它动态存储设备。主存储器906还可以用于在要由处理器904执 行的指令执行期间存储临时变量或其它中间信息。当存储在处理器 904可访问的非暂时性存储介质中时，这种指令使计算机系统900变 成为执行指令中所规定的操作而定制的专用机器。

计算机系统900还包括只读存储器(ROM)908或者耦合到总 线902的其它静态存储设备，用于为处理器904存储静态信息和指令。 提供了存储设备910，诸如磁盘、光盘或固态驱动器，并且耦合到总 线902，用于存储信息和指令。

计算机系统900可以经总线902耦合到显示器912，诸如阴极射 线管(CRT)，用于向计算机用户显示信息。输入设备914，包括字 母数字和其它键，耦合到总线902，用于向处理器904传送信息和命 令选择。另一种类型的用户输入设备是游标控制装置916，诸如鼠标、 轨迹球或者游标方向键，用于向处理器904传送方向信息和命令选择 并且用于控制显示器912上的游标运动。这种输入设备通常具有在两 个轴，第一个轴(例如，x)和第二个轴(例如，y)，中的两个自由 度，以允许设备在平面内规定位置。

计算机系统900可以利用定制的硬连线逻辑、一个或多个ASIC 或FPGA、固件和/或程序逻辑来实现本文所述的技术，这些与计算 机系统相结合，使计算机系统900或者把计算机系统900编程为专用 机器。根据一种实施例，本文的技术由计算机系统900响应于执行包 含在主存储器906中的一条或多条指令的一个或多个序列而执行。这 种指令可以从另一存储介质，诸如存储设备910，读到主存储器906 中。包含在主存储器906中的指令序列的执行使处理器904执行本文 所述的过程步骤。在备选实施例中，硬连线的电路系统可以代替软件 指令或者与其结合使用。

如在本文所使用的，术语“存储介质”指存储使机器以特定方式 操作的数据和/或指令的任何非暂时性介质。这种存储介质可以包括 非易失性介质和/或易失性介质。非易失性介质包括例如光盘、磁盘 或固态驱动器，诸如存储设备910。易失性介质包括动态存储器，诸 如主存储器906。存储介质的常见形式包括，例如，软盘、柔性盘、 硬盘、固态驱动器、磁带，或者任何其它磁性数据存储介质，CD- ROM，任何其它光学数据存储介质，任何具有孔模式的物理介质， RAM、PROM和EPROM、FLASH-EPROM、NVRAM，任何其它 存储器芯片或盒式磁带。

存储介质与传输介质截然不同但是可以与其结合使用。传输介质 参与在存储介质之间传送信息。例如，传输介质包括同轴电缆、铜线 和光纤，包括包含总线902的配线。传输介质还可以采取声或光波的 形式，诸如在无线电波和红外线数据通信中产生的那些。

各种形式的介质可以参与把一条或多条指令的一个或多个序列携 带到处理器904供执行。例如，指令最初可以在远端计算机的磁盘或 固态驱动器上携带。远端计算机可以把指令加载到其动态存储器中并 且利用调制解调器经电话线发送指令。位于计算机系统900本地的调 制解调器可以在电话线上接收数据并且使用红外线发送器把数据转换 成红外线信号。红外线检测器可以接收在红外线信号中携带的数据并 且适当的电路系统可以把数据放在总线902上。总线902把数据携带 到主存储器906，处理器904从该主存储器906检索并执行指令。由 主存储器906接收的指令可以可选地在被处理器904执行之前或之后 存储在存储设备910上。

计算机系统900还包括耦合到总线902的通信接口918。通信接 口918提供耦合到网络链路920的双向数据通信，其中网络链路920 连接到本地网络922。例如，通信接口918可以是综合业务数字网络 (ISDN)卡、电缆调制解调器、卫星调制解调器，或者提供到对应 类型的电话线的数据通信连接的调制解调器。作为另一个例子，通信 接口918可以是提供到兼容的局域网(LAN)的数据通信连接的 LAN卡。无线链路也可以实现。在任何此类实现中，通信接口918 都发送和接收携带表示各种类型信息的数字信号流的电、电磁或光信 号。

网络链路920通常通过一个或多个网络向其它数据设备提供数据 通信。例如。网络链路920可以通过本地网络922提供到主计算机 924或者到由因特网服务提供商(ISP)926操作的数据设备的连接。 ISP 926又通过现在通常称为“因特网”928的全球分组数据通信网 络提供数据通信服务。本地网络922和因特网928都使用携带数字数 据流的电、电磁或光信号。通过各种网络的信号以及在网络链路920 上并通过通信接口918的信号是传输介质的示例形式，其中信号把数 字数据带到计算机系统900或者携带来自计算机系统900的数字数据。

计算机系统900可以通过网络、网络链路920和通信接口918发 送消息和接收数据，包括程序代码。在因特网例子中，服务器930可 以通过因特网928、ISP 926、本地网络922和通信接口918发送对应 于程序的所请求代码。

所接收的代码可以在其被接收时由处理器904执行，和/或存储 在存储设备910或其它非易失性储存器中，供随后执行。

在前面的说明书中，本发明的实施例已经参考众多的具体细节进 行了描述，这些细节可以从一种实现到另一种实现变化。因此，说明 书和附图应当在说明性而不是限制性的意义上考虑。本发明范围的唯 一且排他指示，以及申请人预期作为本发明的范围，是由本申请产生 的权利要求集合的字面和等效范围，以这种权利要求产生的具体形式， 包括任何后续的校正。