在压缩的可变长度字符串上进行谓词评估的方法和设备

摘要

公开了一种在压缩的可变长度字符串上进行谓词评估的方法和设备。所述方法包括：确定谓词的假阳性范围的上下界，所述假阳性范围是所述谓词评估的结果可能产生假阳性错误的范围；对所述假阳性范围的上下界进行压缩编码；将所述压缩的可变长度字符串与压缩编码后的假阳性范围的上下界进行第一比较；以及至少根据第一比较的结果确定谓词评估的结果。该方法充分利用了在压缩数据上进行谓词评估的性能优势，提高了查询处理的性能。

说明书

技术领域

本发明涉及关系型数据库领域，更具体地，涉及一种在压缩的可变长度字 符串上进行谓词评估(predicateevaluation)的方法和设备。

背景技术

近来的研究已经表明，在关系型数据库中进行查询处理时，在数据库中存 储的压缩数据上直接进行谓词评估、而不是将压缩数据解压缩之后再对解压缩 的数据进行谓词评估能够大大提高查询处理的性能。在本领域中，通常将依序 包含自变量、操作关系运算符或逻辑运算符、连接常量且所述自变量不包含函 数、表达式、或分句的谓词称作简单谓词，简称谓词。在数据库语言中，所述 操作关系运算符或逻辑运算符可以包括“＝”、“>”、“>＝”、“<”、“<＝”、“NOT”、 “IN”、“LIKE”、“BETWEEN”等。所谓对数据进行谓词评估，即确定该数据是 否满足该谓词，如果满足则谓词评估结果为真，否则谓词评估结果为假。

在数据库中存储的压缩数据上直接进行谓词评估的关键是压缩编码的保 序，即压缩数据的顺序关系应当与解压缩(原始)数据的顺序关系保持一致，以 确保谓词评估的结果正确。例如，假设谓词是‘age<10’，则对于满足该谓词的 age的值(例如，1,2,…,9)，其压缩编码后的值encoded(age)应当小于该谓词中 的常量“10”压缩编码后的值encoded(10)。目前，对于诸如整型、小数、双精度、 定长字符串等数据类型，本领域中已经提出了一些能够较好地保序的压缩编码 方案。然而，对于可变长度字符串数据类型，尚无令人满意的解决方法，其原 因在于在关系型数据库中，可变长度字符串存在两种比较语义：尾部空格不敏 感语义和尾部空格敏感语义。

在尾部空格不敏感语义下对可变长度字符串进行比较时，具有不同长度的 字符串将在低位用空格字符填充至相同长度后再进行比较；而在尾部空格敏感 语义下，具有不同长度的字符串将直接按照字母顺序进行比较。例如，对于如 下5个用16进制的ASCII码表示的可变长度字符串{x'31',x'3118',x'3120',x'31 2020',x'3132'}，在尾部空格不敏感语义下，低位填充空格字符(空格字符的 ASCII码为20)后分别对应于{x'312020',x'311820',x'312020',x'312020',x'31 3220'}，因此其排序是x'3118'<x'31'＝x'3120'＝x'312020'<x'3132'；而在尾 部空格敏感语义下这5个可变长度字符串的排序则是x'31'<x'3118'<x'3120'< x'312020'<x'3132'。可见，在尾部空格不敏感语义和尾部空格敏感语义下，可 变长度字符串具有不同的排序，因此很难找到一种对于这两种语义均能够保序 的适当的压缩编码方式。

针对这一情况，现有的解决方案通常是在对原始数据进行压缩编码时采用 使得压缩编码后的数据的顺序与尾部空格敏感语义下的顺序一致的压缩编码方 法，该方案在按照尾部空格敏感语义进行谓词评估时，可以直接在压缩编码的 数据上进行谓词评估，而如果希望按照尾部空格不敏感语义进行谓词评估，则 需要对压缩编码的数据进行解压缩，随后对解压缩的数据进行谓词评估。显然， 这种解决方案不支持按照尾部空格不敏感语义在压缩编码的数据上进行谓词评 估，因此不能很好地利用在压缩数据上直接进行谓词评估的性能优势。

发明内容

鉴于以上问题而提出了本发明。本发明的目的并不是提出一种对于尾部空 格不敏感语义和尾部空格敏感语义均能够保序的新的压缩编码方式，而是提供 一种在对于按照与尾部空格敏感语义下的顺序一致的压缩编码方式编码的可变 长度字符串按照尾部空格不敏感语义进行谓词评估时、不需进行解压缩就能够 直接在压缩编码的可变长度字符串上进行谓词评估的方法和设备。

根据本发明的一个方面，提供了一种在压缩的可变长度字符串上进行谓词 评估的方法，包括：确定谓词的假阳性范围的上下界，所述假阳性范围是所述 谓词评估的结果可能产生假阳性错误的范围；对所述假阳性范围的上下界进行 压缩编码；将所述压缩的可变长度字符串与压缩编码后的假阳性范围的上下界 进行第一比较；以及至少根据第一比较的结果确定谓词评估的结果。

根据本发明的另一个方面，提供了一种在压缩的可变长度字符串上进行谓 词评估的设备，包括：范围确定单元，配置为确定谓词的假阳性范围的上下界， 所述假阳性范围是所述谓词评估的结果可能产生假阳性错误的范围；编码单元， 配置为对所述假阳性范围的上下界进行压缩编码；比较单元，配置为将所述压 缩的可变长度字符串与压缩编码后的假阳性范围的上下界进行第一比较；以及 结果确定单元，配置为至少根据所述第一比较的结果确定谓词评估的结果。

根据本发明上述方面的方法和设备在对于按照与尾部空格敏感语义下的顺 序一致的压缩编码方式编码的可变长度字符串按照尾部空格不敏感语义进行谓 词评估时，能够直接在压缩编码的可变长度字符串上进行谓词评估而不需解压 缩所述字符串，从而利用了在压缩数据上进行谓词评估的性能优势，提高了查 询处理的性能。另一方面，通过根据本发明上述方面的方法和设备，使得与尾 部空格敏感语义下的顺序一致的压缩编码方式可以同时支持在两种语义下在压 缩数据上的谓词评估，从而增强了可用性。

附图说明

通过结合附图对本公开示例性实施方式进行更详细的描述，本公开的上述 以及其它目的、特征和优势将变得更加明显，其中，在本公开示例性实施方式 中，相同的参考标号通常代表相同部件。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12 的框图。

图2示出了根据本发明第一实施例的在压缩的可变长度字符串上进行谓词 评估的方法的流程图。

图3示出了在根据本发明第一实施例的方法中根据第一比较的结果和第二 比较的结果确定谓词评估的结果的处理的流程图。

图4示出了根据本发明第二实施例的在压缩的可变长度字符串上进行谓词 评估的方法的流程图。

图5例示了根据本发明实施例的在压缩的可变长度字符串上进行谓词评估 的设备的结构的框图。

具体实施方式

下面将参照附图更详细地描述本公开的优选实施方式。虽然附图中显示了 本公开的优选实施方式，然而应该理解，可以以各种形式实现本公开而不应被 这里阐述的实施方式所限制。相反，提供这些实施方式是为了使本公开更加透 彻和完整，并且能够将本公开的范围完整地传达给本领域的技术人员。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12 的框图。图1显示的计算机系统/服务器12仅仅是一个示例，不应对本发明实 施例的功能和使用范围带来任何限制。

如图1所示，计算机系统/服务器12以通用计算设备的形式表现。计算机 系统/服务器12的组件可以包括但不限于：一个或者多个处理器或者处理单元 16，系统存储器28，连接不同系统组件(包括系统存储器28和处理单元16)的 总线18。

总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器控 制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线 结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构(ISA) 总线，微通道体系结构(MAC)总线，增强型ISA总线、视频电子标准协会(VESA) 局域总线以及外围组件互连(PCI)总线。

计算机系统/服务器12典型地包括多种计算机系统可读介质。这些介质可 以是任何能够被计算机系统/服务器12访问的可用介质，包括易失性和非易失 性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如随 机存取存储器(RAM)30和/或高速缓存存储器32。计算机系统/服务器12可以进 一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作 为举例，存储系统34可以用于读写不可移动的、非易失性磁介质(图1未显示， 通常称为“硬盘驱动器”)。尽管图1中未示出，可以提供用于对可移动非易失性 磁盘(例如“软盘”)读写的磁盘驱动器，以及对可移动非易失性光盘(例如 CD-ROM,DVD-ROM或者其它光介质)读写的光盘驱动器。在这些情况下，每 个驱动器可以通过一个或者多个数据介质接口与总线18相连。存储器28可以 包括至少一个程序产品，该程序产品具有一组(例如至少一个)程序模块，这些 程序模块被配置以执行本发明各实施例的功能。

具有一组(至少一个)程序模块42的程序/实用工具40，可以存储在例如存 储器28中，这样的程序模块42包括——但不限于——操作系统、一个或者多 个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中 可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中的功 能和/或方法。

计算机系统/服务器12也可以与一个或多个外部设备14(例如键盘、指向设 备、显示器24等)通信，还可与一个或者多个使得用户能与该计算机系统/服务 器12交互的设备通信，和/或与使得该计算机系统/服务器12能与一个或多个其 它计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这种通信 可以通过输入/输出(I/O)接口22进行。并且，计算机系统/服务器12还可以通过 网络适配器20与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公 共网络，例如因特网)通信。如图所示，网络适配器20通过总线18与计算机系 统/服务器12的其它模块通信。应当明白，尽管图中未示出，可以结合计算机 系统/服务器12使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱 动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据 备份存储系统等。

[第一实施例]

下面将参考图2对根据本发明第一实施例的在压缩的可变长度字符串上进 行谓词评估的方法进行描述。在该实施例中，以压缩的可变长度字符串是利用 使得压缩编码后的数据的顺序与尾部空格敏感语义下的顺序一致的压缩编码方 法压缩得到的、并且在尾部空格不敏感语义下进行所述谓词评估为例进行说明。

首先对本实施例的基本思想及所涉及的技术术语进行简单的说明。

尽管如上文中提到的，在尾部空格不敏感语义和尾部空格敏感语义下，可 变长度字符串具有不同的排序，因此很难找到一种对于这两种语义均能够保序 的适当的压缩编码方式，但是实际大多数可变长度字符串在这两种语义下的排 序大致是相同的，仅少部分特殊字符串的排序可能是不同的。因此，对于一种 语义(例如尾部空格敏感语义)严格保序的压缩编码方式对于另一种语义(例如尾 部空格不敏感语义)是大致保序的。也就是说，在例如对于按照与尾部空格敏感 语义下的顺序一致的压缩编码方式压缩的可变长度字符串按照尾部空格不敏感 语义进行谓词评估时，大多数压缩字符串的谓词评估结果是正确的，仅很少一 部分的谓词评估结果可能是错误的。例如，假设谓词是col>‘b’，col包括如下 7个varchar(3)类型的可变长度字符串{‘b’,‘ba’,, ‘ab’,‘ght’,‘bΔ’(假设Δ代表小于空格字符的特殊字符),‘bbΔ’}。能够理解，这7 个字符串在尾部空格不敏感语义下的排序是而其采用与尾部空格敏感语义下的顺序一致的压缩编码方式压缩 后的排序为由此可见，在尾部空格不敏感 语义下直接在压缩的字符串上进行谓词评估时，大多数字符串的谓词评估结果 都是正确的，仅尾部包含空格字符或小于空格字符的特殊字符的字符串‘bΔ’和 的谓词评估结果是错误的。更明确的说，由于在尾部空格不敏感语义下， ‘bΔ’<‘b’，因此在对它们进行谓词评估时，评估结果应当为假；然 而，由于压缩编码后的encoded(‘bΔ’)>encoded(‘b’)，所以在直接在压缩后的字符串上进行谓词评估时，错误地确定评 估结果为真。鉴于上述情况，在本实施例中，在尾部空格不敏感语义下进行谓 词评估时，直接在压缩编码的可变长度字符串上进行谓词评估，并且仅当谓词 评估的结果有问题时，解压缩该压缩的可变长度字符串，并对解压缩后的可变 长度字符串进行谓词评估以得到正确的谓词评估的结果。

具体的，本领域中已知，对于诸如整型谓词、小数谓词、定长字符串谓词 等，均可以改写为谓词范围的形式。例如，整型谓词‘age>10’可以改写为age 在(10，+∞)的区间范围内；定长字符串谓词‘name＝8’可以改写为name在[8,8] 的区间范围内。按照这一思路，在本实施例中，将可变长度字符串谓词改写为 谓词范围的形式，并利用统计学中的假阳性(falsepositive)错误和假阴性(false negative)错误来确定在压缩的可变长度字符串上的谓词评估的结果是否有问 题。

假阳性错误又叫第一型错误，如果在假设检定中零假设事实上成立，但统 计检验的结果不支持零假设(拒绝零假设)，则这种错误称为第一型错误；假阴 性错误又叫第二型错误，如果零假设事实上不成立，但统计检验的结果支持零 假设(接受零假设)，则这种错误称为第二型错误。例如，对于计算机防病毒软 件来说，如果防病毒软件把没有感染病毒的文件报告为感染了病毒，就是假阳 性错误，通俗的说就是“误报”；相反，如果防病毒软件把感染了病毒的文件报 告为没有感染病毒(即没有检测出病毒)，就是假阴性错误，通俗的说就是“漏报”。 在本实施例中，对于一个可变长度字符串谓词，分别确定其假阳性范围和假阴 性范围，其中假阳性范围是谓词评估的结果可能产生假阳性错误的范围，假阴 性范围是谓词评估的结果可能产生假阴性错误的范围。能够理解，假阳性范围 比正确的谓词范围要大或至少等于该正确的谓词范围，因此所有满足谓词的可 变长度字符串都会落在该范围内(即对于该假阳性范围的谓词评估结果为真)， 并且一些不满足谓词的可变长度字符串可能也会落在该范围内；假阴性范围比 正确的谓词范围要小或至多等于该正确的谓词范围，因此所有落在该范围内(即 对于该假阴性范围的谓词评估结果为真)的可变长度字符串都满足谓词，并且一 些满足谓词的可变长度字符串可能没有落在该范围内。进一步可以推知，如果 压缩字符串对于假阳性范围和假阴性范围内的评估结果一致，即都为真或都为 假，则谓词评估结果是正确的；而如果压缩字符串对于假阳性范围和假阴性范 围内的评估结果不一致，则无法确定谓词评估结果是什么，因此可以解压缩该 压缩的可变长度字符串，并对解压缩后的可变长度字符串进行谓词评估。

回到图2，如图2所示，在步骤S21中，确定谓词的假阳性范围的上下界， 所述假阳性范围是所述谓词评估的结果可能产生假阳性错误的范围；在步骤 S22中，确定所述谓词的假阴性范围的上下界，所述假阴性范围是所述谓词评 估的结果可能产生假阴性错误的范围。

如前所述，假阳性错误和假阴性错误是统计学中的公知术语。能够理解， 在本实施例中，假阳性错误是指在谓词评估的正确结果为假的情况下错误地确 定结果为真的错误，假阴性错误是指在谓词评估的正确结果为真的情况下错误 地确定结果为假的错误。假阳性范围的上下界和假阴性范围的上下界可以根据 具体的谓词来确定，以下举例予以说明。

在一个示例中，对于谓词Col＝‘ab’(假设Col为varchar(6)类型)，能 够理解，在对于按照与尾部空格敏感语义下的顺序一致的压缩编码方式编码的 可变长度字符串按照尾部空格不敏感语义进行谓词评估时，诸如等尾部为空格的可变长度字符串的谓词评估结果可能是有问题的。因 为上述字符串采用与尾部空格敏感语义下的顺序一致的压缩编码方式压缩编码 得到的值均大于谓词中的常量‘ab’压缩编码后的值，由此会导致认为字符串 不满足谓词Col＝‘ab’；但是在尾部空格不敏感语义下，具有不 同长度的字符串将在低位用空格字符填充至相同长度后再进行比较，因此 与‘ab’是相等，即实际应该是满足谓词Col ＝‘ab’的。因此对于谓词Col＝‘ab’，可以将假阳性范围设为从而将上述等包含在该范围内，进而使得这些字符串对于假阳 性范围的谓词评估结果为真。可以看出，该假阳性范围比正确的谓词范围要大， 因此所有满足谓词的可变长度字符串都会落在该范围内。另一方面，对于谓词 Col＝‘ab’，可以将假阴性范围设为[‘ab’,‘ab’]。如上文所述，该假阴性范围比正 确的谓词范围要小，其可能会漏掉诸如等实际满足谓词的字符 串，但是所有落在该范围内的可变长度字符串都满足谓词。可以按照这一思路 类似的确定其他谓词的假阳性范围和假阴性范围。例如，表1示出了当Col为 varchar(6)类型时，对于几种常见的谓词所确定的示例性的假阳性范围的上下 界和假阴性范围的上下界。

表1

表1中所列出的仅仅是几种常见的谓词，其他谓词也可以类似的确定假阳 性范围和假阴性范围。例如对于谓词Col<>‘ab’，其假阳性范围和假阴性范围 分别可以使用上表中示出的谓词Col＝‘ab’的假阳性范围的补集和假阴性范围的 补集；再比如，对于谓词ColBETWEENval1ANDval2，可以将其拆成Col>＝ val1ANDCol<＝val2，并分别应用上表中列出的范围。

此外，表1中是以谓词中包含的常量为具体值‘ab’为例而给出的假阳性范 围和假阴性范围，其对于谓词中包含的常量为诸如‘bc’、‘XYZ’、‘X12ab’等的 情形也同样适用。更明确的说，如果我们用padForUB(val)来表示在谓词中 包含的常量val尾部填充空格至等于可变长度字符串的设定长度(例如，如果 Col为varchar(6)则填充空格至长度为6)，则上面的表1可以一般化为如下 的表1’。

表1’

谓词 假阳性范围 假阴性范围 Col＝val [val,padForUB(val)] [val,val] Col<val [-∞,padForUB(val)) [-∞,val) Col<＝val [-∞,padForUB(val)] [-∞,val] Col>val [val,+∞] (padForUB(val),+∞] Col>＝val [val,+∞] [padForUB(val),+∞]

另一方面，表1中对于各个谓词所给出的假阳性范围和假阴性范围仅仅是 一个示例，本领域技术人员可以根据具体的谓词以及具体要求(例如，谓词评估 的准确度、速度等)来确定假阳性范围的上下界和假阴性范围的上下界，只要确 保假阳性范围比正确的谓词范围大或至少等于该正确的谓词范围以保证所有满 足谓词的可变长度字符串都会落在该范围内、而假阴性范围比正确的谓词评估 的范围小或至多等于该正确的谓词范围以保证所有落在该范围内的可变长度字 符串都满足谓词即可。例如，对于表1中的谓词Col＝‘ab’，Col<‘ab’，Col <＝‘ab’，可以将其假阳性范围的上界扩展至‘ab！’或者‘ab#’或者‘ab*’等等(‘！’、‘#’、 ‘*’字符的ASCII码均比空格字符的ASCII码大)，甚至进一步扩展至‘aba’、‘ac’、 +∞等等。再比如，对于谓词Col>‘ab’，Col>＝‘ab’，可以将其假阴性范围的下 界缩窄至‘ab！’或者‘ab#’或者‘ab*’等等，甚至进一步缩窄至‘aba’、‘ac’、+∞等等， 并且可以将其假阳性范围的下界扩展至‘aa’、‘aZ’、-∞等等。

在另一个示例中，对于谓词(假设Col为varchar(6)类型)， 能够理解，在对于按照与尾部空格敏感语义下的顺序一致的压缩编码方式编码 的可变长度字符串按照尾部空格不敏感语义进行谓词评估时，诸如‘ab’的可变 长度字符串的谓词评估结果可能是有问题的。因为该字符串采用与尾部空格敏 感语义下的顺序一致的压缩编码方式压缩编码得到的值小于谓词中的常量 压缩编码后的值，由此会导致认为字符串‘ab’不满足谓词但是在尾部空格不敏感语义下，具有不同长度的字符串将在低位用 空格字符填充至相同长度后再进行比较，因此‘ab’是大于的，即‘ab’实 际应该是满足谓词的。因此对于谓词可以将假阳 性范围设为[‘ab’,+∞]，从而将上述‘ab’包含在该范围内，进而使得该字符串对 于假阳性范围的谓词评估结果为真。可以看出，该假阳性范围比正确的谓词范 围要大，因此所有满足谓词的可变长度字符串都会落在该范围内。另一方面， 对于谓词可以将假阴性范围设为如上文所 述，该假阴性范围比正确的谓词范围要小，其可能会漏掉一些实际满足谓词的 字符串，但是所有落在该范围内的可变长度字符串都满足谓词。可以按照这一 思路类似的确定其他谓词的假阳性范围和假阴性范围。例如，表2示出了当Col 为varchar(6)类型时，对于几种常见的谓词所确定的示例性的假阳性范围的 上下界和假阴性范围的上下界。

表2

表2中所列出的仅仅是几种常见的谓词，其他谓词也可以类似的确定假阳 性范围和假阴性范围。例如对于谓词其假阳性范围和假阴性 范围分别可以使用上表中示出的谓词的假阳性范围的补集和假阴 性范围的补集；再比如，对于谓词ColBETWEENval1ANDval2，可以将其拆 成Col>＝val1ANDCol<＝val2，并分别应用上表中列出的范围。

此外，表2中是以谓词中包含的常量为具体值为例而给出的假阳 性范围和假阴性范围，其对于谓词中包含的常量为诸如‘bcΔa’、‘X1aΔa’等的情形也同样适用。更明确的说，如果我们用stripForLB(val)来表示 谓词中包含的常量字符串val中从最高位字符到第一个小于空格的字符的前一 个字符形成的字符串，用padForUB(val)来表示在谓词中包含的常量val尾部 填充空格至等于可变长度字符串的设定长度(例如，如果Col为varchar(6) 则填充空格至长度为6)，则上面的表2可以一般化为如下的表2’。

表2’

另一方面，与表1中类似，表2中对于各个谓词所给出的假阳性范围和假 阴性范围仅仅是一个示例，本领域技术人员同样可以根据具体的谓词以及具体 要求(例如，谓词评估的准确度、速度等)来确定假阳性范围的上下界和假阴性 范围的上下界，只要确保假阳性范围比正确的谓词范围大或至少等于该正确的 谓词范围以保证所有满足谓词的可变长度字符串都会落在该范围内、而假阴性 范围比正确的谓词评估的范围小或至多等于该正确的谓词范围以保证所有落在 该范围内的可变长度字符串都满足谓词即可。例如，对于谓词可以将其假阴性范围的下界缩窄至‘abΔa！’或者‘abΔa#’或者 ‘abΔa*’等等，甚至进一步缩窄至‘abΔaa’、‘ac’、+∞等等。再比如，对于谓词可以将其假阳性范围的下界设为‘abΔ’、‘abΔa’等等，并且可以将其上 界扩展至或者或者等等(‘！’、‘#’、‘*’字符的ASCII 码均比空格字符的ASCII码大)，甚至进一步扩展至‘abΔaa’、‘ac’、+∞等等。

以上已经通过示例描述了如何确定谓词的假阳性范围的上下界以及假阴性 范围的上下界。如上文所述，表1’和表2’中所给出的假阳性范围和假阴性范围 仅仅是一个示例，本领域技术人员可以根据具体的谓词以及诸如谓词评估的精 确度、速度等具体要求来确定假阳性范围的上下界和假阴性范围的上下界。例 如，能够理解，为了获得较快的谓词评估速度，在能够确保所有满足谓词的字 符串都落在假阳性范围内的前提下，假阳性范围越小越好，而在能够确保落在 假阴性范围内的所有字符串都满足谓词的前提下，假阴性范围越大越好。

回到图2，随后，在步骤S23中，对所述假阳性范围的上下界进行压缩编 码。

在该步骤中，采用对可变长度字符串进行压缩编码时使用的编码方法对假 阳性范围的上下界进行压缩编码。例如，假设谓词是col>‘abc’，假阳性范围的 上下界分别为+∞和‘abc’，则压缩编码后的假阳性范围的上下界分别为 encoded(+∞)和encoded(‘abc’)。

在步骤S24中，对所述假阴性范围的上下界进行压缩编码。

与步骤S23中类似，在该步骤中，也采用对可变长度字符串进行压缩编码 时使用的编码方法对假阴性范围的上下界进行压缩编码。例如，假设假阴性范 围的上下界分别为+∞和则压缩编码后的假阳性范围的上下界分别 为encoded(+∞)和encoded

在步骤S25中，将所述压缩的可变长度字符串与压缩编码后的假阳性范围 的上下界进行第一比较。

在该步骤中，通过将压缩的可变长度字符串与压缩编码后的假阳性范围的 上下界进行比较，来确定该压缩的可变长度字符串是否落在压缩编码后的假阳 性范围的上下界限定的范围(下文中简称为“压缩编码后的假阳性范围”)中。 例如，假设所述压缩的可变长度字符串是encoded(‘abca’)，在该步骤中将其与 步骤S23中作为示例给出的压缩编码的上下界encoded(+∞)和encoded(‘abc’)进 行比较，以确定encoded(‘abca’)是否在压缩编码的假阳性范围[encoded(+∞), encoded(‘abc’)]内。

在步骤S26中，将所述压缩的可变长度字符串与压缩编码后的假阴性范围 的上下界进行第二比较。

与步骤S25中类似，在该步骤中，通过将压缩的可变长度字符串与压缩编 码后的假阴性范围的上下界进行比较，来确定该压缩的可变长度字符串是否落 在压缩编码后的假阴性阳性范围的上下界限定的范围(下文中简称为“压缩编码 后的假阴性范围”)中。例如，在该步骤中将压缩的可变长度字符串encoded (‘abca’)与步骤S24中作为示例给出的压缩编码的上下界encoded(+∞)和 encoded进行比较，以确定encoded(‘abca’)是否在压缩编码的假阴 性范围[encoded(+∞),encoded]内。

随后，在步骤S27，根据第一比较的结果和第二比较的结果确定谓词评估 的结果。

在该步骤中，根据压缩的可变长度字符串是否落在压缩编码后的假阳性范 围中以及是否落在压缩编码后的假阳性范围中，来确定谓词评估的结果。下面 将参考图3对这一处理过程进行描述。

如图3所示，在步骤S31，响应于所述压缩的可变长度字符串在由压缩编 码后的假阳性范围的上下界限定的范围内，确定第一评估结果为真，否则确定 第一评估结果为假。

例如，对于如上述步骤S25中所示的示例，由于压缩的可变长度字符串 encoded(‘abca’)在压缩编码的假阳性范围[encoded(+∞),encoded(‘abc’)]内，因 此，确定第一评估结果为真。

在步骤S32，响应于所述压缩的可变长度字符串在由压缩编码后的假阴性 范围的上下界限定的范围内，确定第二评估结果为真，否则确定第二评估结果 为假。

例如，对于如上述步骤S26中所示的示例，由于压缩的可变长度字符串 encoded(‘abca’)在压缩编码的假阳性范围[encoded(+∞),encoded] 内，因此，确定第二评估结果为真。

随后，在步骤S33，响应于第一评估结果和第二评估结果一致，确定谓词 评估的结果为该第一评估结果。

如上文中所述，如果压缩字符串对于假阳性范围和假阴性范围内的评估结 果一致，即都为真或都为假，则谓词评估结果是正确的。例如，如上述步骤S31 和步骤S32中所例示的，第一评估结果和第二评估结果均为真，即压缩的可变 长度字符串encoded(‘abca’)对于假阳性范围和假阴性范围内的评估结果是一 致的，均为真。此时，可以确定在该压缩的可变长度字符串encoded(‘abca’) 上的谓词评估结果为真，即与第一评估结果一致(当然，也与第二评估结果一 致)。

至此，完成了不进行解压缩直接在压缩的可变长度字符串上进行谓词评估 的处理。

可选的，根据本实施例的在压缩的可变长度字符串上进行谓词评估的方法 还可以包括：在步骤S34，响应于第一评估结果和第二评估结果不一致，解压 缩所述压缩的可变长度字符串，并对该解压缩的可变长度字符串进行谓词评估 以得到谓词评估的结果。

如前所述，如果压缩字符串对于假阳性范围和假阴性范围内的评估结果不 一致，则无法确定谓词评估结果是什么，因此在该步骤中，解压缩该压缩的可 变长度字符串，并采用本领域中公知的传统方法、在尾部空格不敏感语义下对 该解压缩后的可变长度字符串进行谓词评估以确定谓词评估的结果。

为了便于理解，下面结合具体示例，对根据本实施例的在压缩的可变长度 字符串上进行谓词评估的方法进行说明。

假设谓词是Col>‘ab’，Col为varchar(6)类型。假设在步骤S21和S22 中，采用表1中示出的示例，确定了该谓词的假阳性范围的上下界分别为 +∞,‘ab’，假阴性范围的上下界分别为+∞，随后，在步骤S23对 所述假阳性范围的上下界压缩编码，得到压缩编码后的假阳性范围的上下界 encoded(+∞)和encoded(‘ab’)，在步骤S24对所述假阴性范围的上下界压缩编码， 得到压缩编码后的假阴性范围的上下界encoded(+∞)和encoded

在一个示例中，假设压缩的可变长度字符串是encoded(‘abc’)。在该情形 下，在步骤S25中，将其与压缩编码后的假阳性范围的上下界encoded(+∞)和 encoded(‘ab’)进行比较，并确定encoded(‘abc’)在[encoded(+∞),encoded(‘ab’)] 内；类似的，在步骤S26中，将其与压缩编码后的假阴性范围的上下界 encoded(+∞)和encoded进行比较，并确定encoded(‘abc’)在 [encoded(+∞),encoded]内。随后，在步骤S27，根据步骤S25的 比较结果，确定第一评估结果为真，并根据步骤S26的比较结果，确定第二评 估结果也为真。由于第一评估结果和第二评估结果一致，均为真，从而可以确 定‘abc’的谓词评估的结果为真。

在另一个示例中，假设压缩的可变长度字符串是encoded(‘aa’)。在该情 形下，在步骤S25中，将其与压缩编码后的假阳性范围的上下界encoded(+∞) 和encoded(‘ab’)进行比较，并确定encoded(‘aa’)不在[encoded(+∞),encoded(‘ab’)] 内；类似的，在步骤S26中，将其与压缩编码后的假阴性范围的上下界 encoded(+∞)和encoded进行比较，并确定encoded(‘aa’)不在 [encoded(+∞),encoded]内。随后，在步骤S27，根据步骤S25的 比较结果，确定第一评估结果为假，并根据步骤S26的比较结果，确定第二评 估结果为假。由于第一评估结果和第二评估结果一致，均为假，从而可以确定‘aa’ 的谓词评估的结果为假。

在又一个示例中，假设压缩的可变长度字符串是encoded(‘abΔ’)。在该情 形下，在步骤S25中，将其与压缩编码后的假阳性范围的上下界encoded(+∞) 和encoded(‘ab’)进行比较，并确定encoded(‘abΔ’)在[encoded(+∞),encoded(‘ab’)] 内；类似的，在步骤S26中，将其与压缩编码后的假阴性范围的上下界 encoded(+∞)和encoded进行比较，并确定encoded(‘abΔ’)不在 [encoded(+∞),encoded]内。随后，在步骤S27，根据步骤S25的 比较结果，确定第一评估结果为真，并根据步骤S26的比较结果，确定第二评 估结果为假。由于第一评估结果和第二评估结果不一致，在步骤S27中解压缩 所述压缩的可变长度字符串encoded(‘abΔ’)得到解压缩的可变长度字符串 ‘abΔ’，并根据本领域中传统的谓词评估方法判断出在尾部空格不敏感语义下， ‘abΔ’不满足Col>‘ab’，由此确定谓词评估的结果为假。

需要说明的是，虽然以上按照从步骤S21到S27的顺序对根据本实施例的 在压缩的可变长度字符串上进行谓词评估的方法进行了说明，但这仅仅是一种 示例，所述步骤S21到S27并非必须按照所描述的顺序来执行。例如，可以在 顺序执行了步骤S21、S23、S25之后再顺序执行步骤S22、S24、S26，或者可 以在执行步骤S21、S23、S25的同时并行的执行步骤S22、S24、S26，等等。

以上已经对根据本发明第一实施例的在压缩的可变长度字符串上进行谓词 评估的方法进行了描述。在该实施例中，在对于按照与尾部空格敏感语义下的 顺序一致的压缩编码方式编码的可变长度字符串按照尾部空格不敏感语义进行 谓词评估时，通过利用谓词的假阳性范围和假阴性范围，在压缩编码的可变长 度字符串上直接进行谓词评估而不进行解码，并且仅当谓词评估的结果有问题 时，解压缩该压缩的可变长度字符串，并对解压缩后的可变长度字符串进行谓 词评估以得到正确的谓词评估的结果。该实施例充分利用了在压缩数据上进行 谓词评估的性能优势，从而提高了查询处理的性能。

[第二实施例]

在根据第一实施例的在压缩的可变长度字符串上进行谓词评估的方法中， 对于一个可变长度字符串谓词，分别确定其假阳性范围和假阴性范围，并且随 后根据压缩的可变长度字符串是否落在压缩编码的假阳性范围和假阴性范围 中，来确定谓词评估的结果。然而，事实上，在很多情况下，并不需要确定假 阴性范围并随后确定压缩的可变长度字符串是否落在压缩编码的假阴性范围中 (即第一实施例中的步骤S21、S24和S26中的处理)。下面，将举例进行说明。

比如，根据上文中的描述可知，假阳性范围大于等于假阴性范围，因此如 果压缩编码的可变长度字符串没有落在压缩编码的假阳性范围内，则其必然也 不会落在压缩编码的假阴性范围内。在这样的情况下，显然不再需要确定假阴 性范围并随后确定压缩的可变长度字符串是否落在压缩编码的假阴性范围内。

再比如，如果假阴性范围的上下界压缩编码后的值与假阳性范围的上下界 压缩编码后的值分别相等，则显然不再需要确定压缩的可变长度字符串是否落 在压缩编码的假阴性范围内。

再比如，对于查询中例如通过外键关系而生成的中间谓词，由于执行该谓 词后还要进行其他查询处理，因此对于该中间谓词的谓词评估结果不需要太准 确。由于假阳性范围大于等于正确的谓词范围从而所有满足谓词的字符串都会 落在该范围内，因此可以仅采用假阳性范围进行谓词评估，并在后续的其他查 询处理进一步过滤掉实际上不满足该谓词的字符串。事实上，能够理解，除了 查询中通过外键关系而生成的中间谓词外，在其他对于谓词评估结果的准确性 要求不高的情形中，也可以仅采用假阳性范围进行谓词评估。

在根据本实施例的在压缩的可变长度字符串上进行谓词评估的方法中，仅 确定假阳性范围而不确定假阴性范围，并根据压缩的可变长度字符串是否落在 压缩编码的假阳性范围中，来确定谓词评估的结果。图4示出了根据本实施例 的在压缩的可变长度字符串上进行谓词评估的方法的流程图。下面，将参考图 4进行描述。

如图4所示，在步骤S41中，确定谓词的假阳性范围的上下界，所述假阳 性范围是所述谓词评估的结果可能产生假阳性错误的范围。

在该步骤中，可以类似的采用例如第一实施例中给出的表1’和表2’中例示 的假阳性范围。当然，表1’和表2’中例示的假阳性范围仅仅是一个示例，而并 非是限制性的。本领域技术人员可以根据具体的谓词以及诸如谓词评估的精确 度、速度等具体要求来确定假阳性范围的上下界。例如，能够理解，为了获得 较快的谓词评估速度，在能够确保所有满足谓词的压缩字符串都落在假阳性范 围内的前提下，假阳性范围越小越好。

该步骤S41中的操作与上文中描述的步骤S21中的操作相同，此处不再赘 述。

在步骤S42中，对所述假阳性范围的上下界进行压缩编码。

在该步骤中，采用对可变长度字符串进行压缩编码时使用的编码方法对假 阳性范围的上下界进行压缩编码。例如，假设谓词是col>‘abc’，假阳性范围的 上下界分别为+∞和‘abc’，则压缩编码后的假阳性范围的上下界分别为 encoded(+∞)和encoded(‘abc’)。

在步骤S43中，将所述压缩的可变长度字符串与压缩编码后的假阳性范围 的上下界进行第一比较。

在该步骤中，通过将压缩的可变长度字符串与压缩编码后的假阳性范围的 上下界进行比较，来确定该压缩的可变长度字符串是否落在压缩编码后的假阳 性范围中。例如，假设所述压缩的可变长度字符串是encoded(‘abca’)，在该步 骤中将其与步骤S42中作为示例给出的压缩编码的上下界encoded(+∞)和 encoded(‘abc’)进行比较，以确定encoded(‘abca’)是否在压缩编码的假阳性范 围[encoded(+∞),encoded(‘abc’)]内。

随后，在步骤S44中，根据第一比较的结果确定谓词评估的结果。

具体的，如果第一比较的结果是压缩的可变长度字符串落在压缩编码后的 假阳性范围中，则确定谓词评估的结果为真，否则确定谓词评估的结果为假。

例如，对于如上述步骤S43中所示的示例，由于压缩的可变长度字符串 encoded(‘abca’)在压缩编码的假阳性范围[encoded(+∞),encoded(‘abc’)]内，因 此，确定谓词评估的结果为真。

以上对根据本发明第二实施例的在压缩的可变长度字符串上进行谓词评估 的方法进行了描述。在该实施例中，在对于按照与尾部空格敏感语义下的顺序 一致的压缩编码方式编码的可变长度字符串按照尾部空格不敏感语义进行谓词 评估时，通过利用谓词的假阳性范围，在压缩编码的可变长度字符串上直接进 行谓词评估而不进行解码。该实施例充分利用了在压缩数据上进行谓词评估的 性能优势，从而提高了查询处理的性能。另一方面，与第一实施例相比，在本 实施例中仅利用假阳性范围进行谓词评估，由于不需要设定假阴性范围并进行 与该范围相关的操作，因此进一步提高了查询处理的速度。

下面，参照图5来描述根据本发明实施例的在压缩的可变长度字符串上进 行谓词评估的设备的结构框图。具体的，在下文中，以压缩的可变长度字符串 是利用使得压缩编码后的数据的顺序与尾部空格敏感语义下的顺序一致的压缩 编码方法压缩得到的、并且在尾部空格不敏感语义下进行所述谓词评估为例进 行说明。

根据本发明实施例的进行谓词评估的设备500可以执行以上各个实施例中 所述的在压缩的可变长度字符串上进行谓词评估方法。如图5所示，该进行谓 词评估的设备500包括：范围确定单元501，编码单元502，比较单元503，以 及结果确定单元504。

范围确定单元501确定谓词的假阳性范围的上下界，所述假阳性范围是所 述谓词评估的结果可能产生假阳性错误的范围。如前所述，假阳性错误是在谓 词评估的正确结果为假的情况下错误的确定结果为真的错误。具体的，范围确 定单元501可以类似的采用例如第一实施例中给出的表1’和表2’中例示的假阳 性范围。当然，表1’和表2’中例示的假阳性范围仅仅是一个示例，而并非是限 制性的。本领域技术人员可以根据具体的谓词以及诸如谓词评估的精确度、速 度等具体要求通过范围确定单元501来确定假阳性范围的上下界。例如，能够 理解，为了获得较快的谓词评估速度，在能够确保所有满足谓词的压缩字符串 都落在假阳性范围内的前提下，假阳性范围越小越好。

编码单元502对所述假阳性范围的上下界进行压缩编码。具体的，编码单 元502采用对可变长度字符串进行压缩编码时使用的编码方法对由范围确定单 元501确定的假阳性范围的上下界进行压缩编码。

比较单元503将压缩的可变长度字符串与压缩编码后的假阳性范围的上下 界进行第一比较。具体的，比较单元503通过将压缩的可变长度字符串与从编 码单元502得到的压缩编码后的假阳性范围的上下界进行比较，来确定该压缩 的可变长度字符串是否落在压缩编码后的假阳性范围中。

结果确定单元504根据所述第一比较的结果确定谓词评估的结果。具体的， 如果比较单元503确定的第一比较的结果是压缩的可变长度字符串落在压缩编 码后的假阳性范围中，则结果确定单元504确定谓词评估的结果为真，否则确 定谓词评估的结果为假。

可选的，范围确定单元501还可以进一步确定谓词的假阴性范围的上下界， 所述假阴性范围是所述谓词评估的结果可能产生假阴性错误的范围。如前所述， 假阴性错误是在谓词评估的正确结果为真的情况下错误的确定结果为假的错 误。具体的，范围确定单元501可以类似的采用例如第一实施例中给出的表1’ 和表2’中例示的阴阳性范围。当然，表1’和表2’中例示的假阴性范围仅仅是一 个示例，而并非是限制性的。本领域技术人员可以根据具体的谓词以及诸如谓 词评估的精确度、速度等具体要求通过范围确定单元501来确定假阴性范围的 上下界。

可选的，编码单元502可以进一步对所述假阴性范围的上下界进行压缩编 码。具体的，编码单元502采用对可变长度字符串进行压缩编码时使用的编码 方法对由范围确定单元501确定的假阴性范围的上下界进行压缩编码。

可选的，比较单元503可以进一步将压缩的可变长度字符串与压缩编码后 的假阴性范围的上下界进行第一比较。具体的，比较单元503通过将压缩的可 变长度字符串与从编码单元502得到的压缩编码后的假阴性范围的上下界进行 比较，来确定该压缩的可变长度字符串是否落在压缩编码后的假阴性范围中。

可选的，结果确定单元504也可以根据所述第一比较的结果和第二比较的 结果确定谓词评估的结果。如图5所示，结果确定单元504可以进一步包括第 一子确定单元5041、第二子确定单元5042和结果确定子单元5043。具体的， 第一子确定单元5041根据比较单元503的比较结果确定第一评估的结果，即如 果比较单元503确定压缩的可变长度字符串在由压缩编码后的假阳性范围的上 下界限定的范围内，则第一子确定单元5041确定第一评估结果为真，否则确定 第一评估结果为假。第二子确定单元5042同样根据比较单元503的比较结果确 定第二评估的结果，即如果比较单元503确定压缩的可变长度字符串在由所述 压缩编码后的假阴性范围的上下界限定的范围内，则第二子确定单元5042确定 第二评估结果为真，否则确定第二评估结果为假。结果确定子单元5043根据第 一评估和第二评估结果，来确定谓词评估的结果。具体的，如果第一评估结果 和第二评估结果一致，则结果确定子单元5043确定谓词评估的结果为该第一评 估结果；如果第一评估结果和第二评估结果不一致，则结果确定子单元5043 解压缩所述压缩的可变长度字符串，并对该解压缩的可变长度字符串进行谓词 评估以得到谓词评估的结果。

以上对根据本发明实施例的在压缩的可变长度字符串上进行谓词评估的设 备进行了描述。在该实施例中，在对于按照与尾部空格敏感语义下的顺序一致 的压缩编码方式编码的可变长度字符串按照尾部空格不敏感语义进行谓词评估 时，通过利用谓词的假阳性范围(和假阴性范围)，在压缩编码的可变长度字符 串上直接进行谓词评估而不进行解码。该实施例充分利用了在压缩数据上进行 谓词评估的性能优势，从而提高了查询处理的性能。

本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括 计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机 可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令 的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、 磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合 适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式 计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程 只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只 读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例 如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。 这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或 者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过 光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各 个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下 载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线 传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理 设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该 计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质 中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA) 指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以 一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括 面向对象的编程语言—诸如Smalltalk、C++等，以及常规的过程式编程语言— 诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机 上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用 户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。 在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域 网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例 如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算 机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现 场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机 可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程 图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框 以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编 程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机 或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的 一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令 存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/ 或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个 制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的 各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、 或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一 系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数 据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方 框中规定的功能/动作。

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

以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的， 并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的 情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。 本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场 中的技术的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露 的各实施例。