用于通过使用解压缩图进行数据访问的系统和方法

摘要

本公开涉及用于通过使用解压缩图进行数据访问的系统和方法。提供实现和利用用于解压缩数据库系统中的数据的技术的方法和设备，包括计算机程序产品。接收属于压缩数据集内的数据子集的查询。通过使用成本模型评估一个或多个解压缩策略。成本模型包含估计的过滤因子。基于一个或多个解压缩策略的评估结果，选择低成本解压缩策略。在压缩数据集内定位代表请求的数据子集的一个或多个字节。通过使用选择的解压缩策略仅解压缩与数据子集对应的压缩数据的一部分，同时使剩余的数据集保持压缩状态。

说明书

技术领域

本发明涉及数据库系统，更特别地，涉及用于数据库系统中的压 缩和解压缩技术。数据库系统管理大量的数据，并且一般使用数据压 缩作为用于减少用于容纳数据对象的盘和/或内存存储器的量的手段。

背景技术

例如，可从Armonk,NY的International Business Machines  Corporation得到的DB2数据库系统提供存储器优化特征，该存储器 优化特征为了减少盘空间和存储器基础构架要求，利用明显压缩盘上 的数据的压缩特征的组合。由于盘存储器系统常常可能是数据库解决 方案中最昂贵的部件，因此即使存储器子系统的很小的减少也可导致 整个数据库解决方案的明显的成本节省。在DB2数据库系统中使用的 一些数据压缩技术中包括行压缩、自适应行压缩和XML压缩。

虽然各种压缩技术一般明显节省内存和存储器使用，但它们在访 问数据时也引起更多地使用中央处理单元(CPU)资源(即，更高的 CPU使用)。因此，有利的是具有减少当仅需要访问压缩数据的一部 分时所需要的CPU资源的量的技术。

发明内容

根据本发明的一个实施例，提供实现和利用用于解压缩数据库系 统中的数据的技术的方法和设备，包括计算机程序产品。接收属于压 缩数据集内的数据子集的查询。通过使用成本模型评估一个或多个解 压缩策略。成本模型包含估计的过滤因子。基于一个或多个解压缩策 略的评估结果，选择低成本解压缩策略。在压缩的数据集内定位代表 请求的数据子集的一个或多个字节。通过使用选择的解压缩策略，仅 解压缩与数据子集对应的压缩数据的一部分，同时使剩余的数据集保 持在压缩状态。

在以下的附图和说明书中阐述本发明的一个或多个实施例的细 节。借助于说明书和附图以及权利要求，本发明的其它特征和优点将 十分明显。

附图说明

图1是示出根据一个实施例的用于解压缩数据的处理(100)的流 程图。

图2示出可根据一个实施例使用的计算机体系结构(200)。

在各附图中，类似的附图标记表示类似的要素。

具体实施方式

如上所述，诸如DB2数据库系统的许多数据库系统当前压缩整个 行，并且在需要访问行中的任意列时解压缩整个行。但是，当针对表 运行查询时，经常仅需要访问行中的列的子集(或者表中的页内的行 的子集)。这里描述的实施例通过提供为了提供特定查询所需要的数 据而确定需要扩展解压缩数据的哪个部分的方式，大大改善了仅需要 访问行的一部分的查询的性能。

所属技术领域的技术人员知道，本发明的各个方面可以实现为系 统、方法或计算机程序产品。因此，本发明的各个方面可以具体实现 为以下形式，即：完全的硬件实施方式、完全的软件实施方式(包括 固件、驻留软件、微代码等)，或硬件和软件方面结合的实施方式， 这里可以统称为“电路”、“模块”或“系统”。此外，在一些实施 例中，本发明的各个方面还可以实现为在一个或多个计算机可读介质 中的计算机程序产品的形式，该计算机可读介质中包含计算机可读的 程序代码。

可以采用一个或多个计算机可读介质的任意组合。计算机可读介 质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读 存储介质例如可以是—但不限于—电、磁、光、电磁、红外线、或半 导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介 质的更具体的例子(非穷举的列表)包括：具有一个或多个导线的电 连接、便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储 器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、 便携式紧凑盘只读存储器(CD-ROM)、光存储器件、磁存储器件、 或者上述的任意合适的组合。在本文件中，计算机可读存储介质可以 是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装 置或者器件使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传 播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据 信号可以采用多种形式，包括—但不限于—电磁信号、光信号或上述 的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储 介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播 或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用 的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输， 包括—但不限于—无线、有线、光缆、RF等等，或者上述的任意合 适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本发 明操作的计算机程序代码，所述程序设计语言包括面向对象的程序设 计语言—诸如Java、Smalltalk、C++等，还包括常规的过程式程序设 计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全 地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立 的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者 完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远 程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网 (WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如 利用因特网服务提供商来通过因特网连接)。

下面将参照根据本发明实施例的方法、装置(系统)和计算机程 序产品的流程图和/或框图描述本发明。应当理解，流程图和/或框图 的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机程 序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算 机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得 这些计算机程序指令在通过计算机或其它可编程数据处理装置的处理 器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的 功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些指 令使得计算机、其它可编程数据处理装置、或其他设备以特定方式工 作，从而，存储在计算机可读介质中的指令就产生出包括实现流程图 和/或框图中的一个或多个方框中规定的功能/动作的指令的制造品 (article of manufacture)。

计算机程序指令也可被加载到计算机、其它可编程数据处理设备 或其它装置上，以导致在计算机、其它可编程设备或其它装置上执行 的一系列的操作步骤产生计算机实现的过程，使得在计算机或其它可 编程设备上执行的指令提供用于实现在流程图和/或框图块中规定的 功能/动作的处理。

从图1可以看出，根据一个实施例的用于解压缩数据的处理(100) 从接收属于压缩数据集内的数据子集的查询(步骤102)开始。一般 地，在数据库系统中，构建包含关于需要访问行的什么列的信息的结 构。例如，在DBS数据库系统中，存在详述需要什么列以评估特定查 询的谓词以及需要检索什么列并将其输出到用于使行具有资格的调用 器的结构。响应于接收查询，数据库系统询问这些结构以确切地确定 对于谓词评估阶段以及对于选择列表处理需要行的什么部分(对于满 足谓词的行需要返回的行)。例如，给定具有20个列C1…C20的表， 会存在以下的查询：

SELECT C1,C17

FROM T1

WHERE C1＝12345；

在这种情况下，查询需要访问列C1以评估谓词；并且，当谓词 为真时，需要访问列C1和C17。出于解释的目的，假定各列10字节 长且列以次序C1、C2、C3、…20被存储。在这种情况下，列C1占 据行中的字节位置1～10，并且，列C17占据字节C161～C170。因此， 评估结构的代码确定评估行的谓词仅需要行的字节1～10。另外，对于 以上的选择列表，需要C1和C17，但是，由于以前对于谓词评估而 解压缩了C1，因此，如果实际返回行，那么仅需要解压缩C17。因此， 对于以上的查询，可以使用以下的解压缩策略：

阶段1解压缩(即，对于谓词评估需要列的解压缩)：

仅需要列C1(行的字节1～10)。

阶段2解压缩(对于选择列表需要所有剩余列的解压缩)：

由于已完成C1，因此仅需要列C17(行的字节161～170)。

本领域技术人员理解，存在确保所有需要的列在它们被需要之前 被解压缩的多种方式，并且，以上的二阶段例子仅是一个示例性实施 例。例如，作为以上方法的替代，阶段1可仅解压缩列C1和C17的 所有字节。在其它的实施例中，可存在需要行的不同部分的更多阶段， 即，可能是如果存在分组处理(group-by processing)，则也可在附 加阶段中解压缩分组处理所需要的列。因此，处理评估一个或多个解 压缩策略(步骤104)。在图1所示的实施例中，使用具有估计的过 滤因子的成本模型来提出最佳(如果过滤因子正确)解压缩方法。例 如，如果已知需要n1个循环来解压缩列C1，那么需要n17个循环来 解压缩列C17，并且谓词的过滤因子是0.25(即，所有行的1/4满足 谓词)，那么可以期望每个解压缩的成本会是n1+(n17*0.25)个循 环。类似地，如果用于解压缩从C1到C17的所有列的CPU时间是 n1…n17，那么如果n1…n17小于(n1+(n17*0.25))个循环，则解 压缩整个行会更合理。因此，通过在确定解压缩策略时使用这种成本 模型方法，能够提出行访问的最佳解压缩策略。本领域技术人员可以 理解，这种成本模型是可扩展的，并允许对于解压缩行/策略的不同部 分使用不同的软件和/或硬件方法。基于步骤104中的压缩策略的评估， 选择低成本解压缩策略(步骤106)。在本文中，还应注意，虽然在 本例子中使用“循环”，但它不必是实际循环。可出于选择“最佳” 解压缩策略的目的，可使用允许在两个或更多个解压缩方法之间进行 适当比较的任意类型的“计数”或“CPU单元”。

最后，使用选择的解压缩策略以实际访问行并定位数据的请求的 字节并解压缩它们(步骤108)。在以上的示例性查询中，数据库引 擎现在获知需要访问压缩行的字节1～10，以评估谓词。因此，作为解 压缩行的所有200个字节的替代，解压缩逻辑被调用以仅解压缩前10 个字节并然后停止。然后，可评估谓词。如果谓词评估为真，从而意 味着需要返回选择列，那么数据库引擎会然后尝试仅解压缩列C17所 需要的字节(字节161～170)。在这种情况下，解压缩算法被增强以 处理压缩数据的“子串”。为此，构建对于压缩数据的各令牌确切地 确定令牌代表多少字节的结构。许多数据库系统(包含DB2数据库系 统)当前使用Lempel-Ziv压缩，但是本领域技术人员可以理解，可以 类似地处理大多数的其它压缩算法。例如，虽然Lempel-Ziv压缩使用 令牌，但其它的压缩算法可使用知晓可变长度列的结构并且可被用于 确定当存在可变长度列时需要的字节序列的其它类型的单元或其它逻 辑。

例如，假定存在具有8个令牌的非常小的压缩字典且每个具有以 下的长度：

进一步假定存在压缩令牌的以下序列：

2,7,1,1,4,3,6,0,3,8,5,7

使用以上的令牌长度表，该处理可计数以确定需要解压缩什么令 牌以得到行的字节161～170。给定以上的信息，可以计算如下：

因此，当“计数”到压缩串时，很显然，第10个压缩令牌“8” 的长度是3个字节，并且覆盖行的字节159～161。选择列表所需要的 第一字节是字节161，因此解压缩会从令牌10开始。解压缩会然后继 续，直到行的字节170已被解压缩，这会在随后的令牌即令牌“5”上 发生。因此，通过仅解压缩令牌8和5(或者替代性地仅解压缩需要 的令牌的所需部分)，用于访问行的C17的所有数据现在是可用的。 一般地，“计数”到适当的偏移的成本远低于实际解压缩字节。因此， 仅解压缩需要的行的部分快得多。

应当注意，以上描述的处理(100)仅是一个示例性处理，并且， 可存在本领域技术人员容易想到的许多变更例。

例如，通过使用上述的成本模型方法，能够进行最优使用任何解 压缩策略的决定。例如，如果对于查询只需要解压缩列C1和C3，那 么可通过比较仅解压缩列C1和C3的成本与解压缩列C1、C2和C3 的成本，来进行成本估计。即使不需要列C2，解压缩整个连续的范围 也可能比单独地解压缩列C1和C3并且在它们之间计数快。类似地， 如果仅需要列C3，那么解压缩列C1…C3可能比单独地仅解压缩列 C3快，原因是列C1在行的开始处开始。因此，成本模型确保可比较 任何类型的子串解压缩方法，从而选择最低成本的替代方案。

还应注意，需要的列中的一些可能长度可变，并且一些可能处于 行内的可变偏移上。在这些情况下，简单的字节偏移可能是不够的。 可变长度列的长度可以以许多不同的方式被存储。例如，DB2使用两 种不同的方法来存储可变长度条目。在一种方法中，任何可变长度列 之前是其长度。在其它的方法中，存储图(map)，其中行给出对每 个可变长度列的开始的偏移。但这仅是两个例子。主要的点在于，存 在导致解压缩器知晓可变长度列的结构并且确定当存在可变长度列时 需要的字节序列的逻辑。偏移是否存储于行的中间或者它们是否在开 始处或者是否仅存在处于可变长字符串(varchar)前面的长度是无关 紧要的。解压缩图可构建为提供许多不同的结构，并且要点是在这些 方法中的任一个中，能够确定对于可变长度列实例所需要的实际字节。

例如，假定数据库系统存储对每个可变长字符串的开始的偏移， 这常被称为“重排序的行格式”。以下示出示例性行结构，诸如DB2 数据库系统中的行的结构。在这种情况下，每个可变长度列具有其存 储于行内的固定位置上的开始偏移。假定表存在有列C1、VC2、VC3， 其中C1是长度10的固定长度字符列，VC2和VC3是具有最大长度 100字节的可变长度字符字段。在这种情况下，行会看起来类似于如 下：

如果查询仅希望访问列VC3，那么可以使用子串解压缩以仅得到 VC3的开始偏移(作为Ofs(VC3)存储于压缩数据中))。然后， 解压缩将继续“计数”，直到遇到VC3的开始，并且继续解压缩，直 到遇到列的结尾(在这种情况下，对于最后的列，可完成解压缩，直 到压缩数据的结束)。由于子串解压缩能够迅速地在计数与解压缩之 间切换，因此能够迅速地解压缩行内的所需偏移，并然后使用它们以 规定后面的解压缩字节范围。在DB2数据库系统的当前实现中，例如， 解压缩所需要的字节的位置被给予地址的零终端阵列 (zero-terminated array)。例如，行被解压缩成地址WAPtr上的工 作区域，并且希望解压缩行的161～170的字节，阵列可构建如下：

WAPtr+160 WAPtr+169 0

这种阵列被称为解压缩图，因为该阵列指示需要解压缩行的什么 部分。虽然在一些实施例中还能够仅使得解压缩图存储偏移而不是地 址，但以上这种地址进入缓冲器的方法对于某些数据库系统实现可能 是更有效的。相反，如果希望访问在偏移14(原因是它用于上述Ofs (VC3))上的压缩数据内存储其开始位置的可变长度条目，那么解 压缩图可构建如下：

WAPtr+14 间接+1 待填充 开始解压缩 WAPtr+max Row Len 结束解压缩 0  

在这种情况下，第一偏移标有字段，所述字段指示该偏移上的二 字节字段应被添加到WAPtr并且在解压缩图中的下一条目上存储。 因此，解压缩图中的下一条目填充有应开始解压缩的偏移。由于VC3 是行的最后一列，因此“结束”解压缩偏移就被设定为最大行长度， 并且解压缩将就在所有压缩数据已被处理时终止。如果在VC3之后存 在其它可变长度列，那么它们的偏移可与类似的间接操作符一起使用 以指示压缩行的结束位置。应当注意，在一些情况下，解压缩行的整 个可变长度部分可能更快，并且也可因此计算该替代方案的成本估计。 例如，如果实现总是存储行的结尾处的所有可变长度列，那么可在没 有解压缩图中的任何“间接”的情况下单独解压缩行的尾端。

在可变长度列前面是它们的长度的情况下，能够使得使用该长度 的间接方法调整后面的解压缩位置。例如，如果请求第三可变长度列， 那么可以使用间接方法，其中向后面的解压缩图条目的特定偏移添加 某个值，由此考虑前面的可变长度条目的长度。本领域技术人员可以 理解，这种间接方法适于可变长度列的许多不同格式。

并且，应当注意，在一些实施例中，解压缩图还可能存储多个字 节范围。例如，如果存在总从以上的例子检索列C1和C17(但没有 谓词)的查询，那么解压缩图可被构建如下：

WAPtr+0 开始解压缩 WAPtr+9 停止解压缩 WAPtr+160 开始解压缩 WAPtr+169 停止解压缩 0 解压缩图的结尾

在这种方式，可以在不必解压缩整个行的情况下解压缩行的多个 不连续部分。

应当注意，虽然以上的描述常使用DB2 数据库系统，但是作为 例子，以上描述的技术当然适用于许多其它的范例。例如，压缩网络 流可能需要仅访问可预测偏移上的数据流的较小部分(即，头部或尾 部(trailer))。在这种情况下，能够仅计数和解压缩需要检查的流 的部分。因此，存在可应用上述一般技术的大量领域。

还应注意，虽然以上的例子关注在行的开始处开始并且向着行的 结尾处计数令牌或单元以识别要解压缩的适当字节的数据解压缩，但 可相反地应用类似的技术。即，解压缩可从行的结尾处而不是从行的 开始处开始。例如，在比方说行长200个字节且已知仅需要最后的20 个字节的情况下，这可能是特别有用的。在这种情况下，解压缩可从 行的结尾处开始，由此避免对于计数令牌或单元以识别需要解压缩哪 些字节的需要，并由此使得解压缩更加有效。本领域技术人员可以设 想这些技术的许多变化和/或组合。

图2表示可根据某些实施例使用的计算机体系结构(200)的示意 图。在某些实施例中，计算装置可实现计算机体系结构(200)。计算 机体系结构(200)适于存储和/或执行程序代码，并且包括通过系统 总线(220)与内存元件(204)直接或间接耦合的至少一个处理器(202)。 内存元件(204)可包含在程序代码的实际执行期间使用的本地内存、 大容量存储器和为了减少在执行期间必须从大容量存储器检索代码的 次数而提供至少一些程序代码的暂时存储的高速缓存存储器。内存元 件(204)包含操作系统(205)和一个或多个计算机程序(206)。

输入/输出(I/O)装置(212、214)(包含但不限于键盘、显示 器、指向装置等)可直接或者通过介入的I/O控制器(210)与系统耦 合。

网络适配器(208)也可与系统耦合以使得数据处理系统能够通过 介入的私有或公共网络变得与其它的数据处理系统或者远程打印机或 存储器装置耦合。调制解调器、线缆调制解调器和以太网卡仅是当前 可用类型的网络适配器(208)中的几个。

计算机体系结构(200)可与存储器装置(216)(例如，任意类 型的存储器装置；诸如磁盘驱动器、光盘驱动器、带驱动器等的非易 失性存储器区域)。存储器装置(216)可包含内部存储器装置或附接 的或网络可访问的存储器。存储器装置(216)中的计算机程序(206) 可以以在本领域中已知的方式被加载到内存元件(204)中并且由处理 器(202)执行。

计算机体系结构(200)可包含比示出的部件少的部件，可包含这 里未示出的附加的部件或者包含示出的部件和附加的部件的一些组 合。计算机体系结构(200)可包含在本领域中已知的任何计算装置、 诸如大型机、服务器、个人计算机、工作站、膝上型计算机、手持计 算机、电话设备、网络设备、虚拟化设备、存储控制器。

出于解释和描述的目的给出本发明的实施例的以上的描述。它不 是要详尽无遗的或者将实施例限于公开的确切的形式。鉴于以上的教 导，许多修改和变化是可能的。实施例的范围不是由该详细的描述而 是由所附的权利要求限定。以上的说明书、例子和数据提供制造的完 整描述和实施例的构成的使用。由于可在不背离本发明的精神和范围 的情况下提出许多实施例，因此实施例在于以下所附的权利要求或者 任何随后提交的权利要求和它们的等同。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、 方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点 上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的 一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现 规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现 中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。 例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以 按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/ 或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以 用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以 用专用硬件与计算机指令的组合来实现。

在这里使用的术语仅出于描述特定的实施例目的，并且不意在限 制本发明。如这里使用的那样，除非在上下文中另外明确指出，否则 单数形式“一种”、“一个”和“该”也意在包括多数形式。还应理 解，在本说明书中使用的术语“包括”和/或“包含”规定阐述的特征、 整数、步骤、操作、要素和/或部件的存在，但不排除存在或添加一个 或多个其它的特征、整数、步骤、操作、要素、部件和/或它们的组。

以下权利要求中所有装置或步骤加功能的对应结构、材料、动作 以及等同物是要包括用于与其他请求保护的要素组合而执行功能的任 何结构、材料或动作(如具体请求保护的)。给出本发明的描述是出 于解释和描述的目的给出的，但它不是详尽的或者将本发明限于公开 的形式。在不背离本发明的范围和精神的情况下，许多修改和变更对 本领域技术人员来说是十分明显的。选择和描述了实施例，以便最好 地解释本发明的原理和实际应用，并使得其他本领域技术人员能够理 解本发明的具有适于设想的特定用途的各种变化的各种实施例。