位图过滤器、其生成方法及用位图过滤器执行连接的方法

摘要

提供了生成位图过滤器的计算机实现的方法。接收过滤器参数，并且查询与过滤器参数相关联的第一数据源，以识别第一数据源中具有对应于过滤器参数的标识符的至少一个条目。执行第一过程，在该过程中，识别位图过滤器中的多个位位置中的零或一个单个位位置，该零或一个单个位位置对应于与过滤器参数对应的第一数据源的条目的标识符。每个标识符具有数值，基于对应标识符的数值来识别该位位置。单个位位置被分配给标识符，使得在对应于过滤器参数的每个标识符和位图过滤器中分配的位位置之间存在一对一映射。在分配的位位置处设置位。对第一数据源中具有对应于过滤器参数的标识符的另一条目重复第一过程。

说明书

技术领域

本申请涉及数据库中的查询处理，以及更具体地，涉及用于提高搜索查询的效率的方法和系统以及在数据库系统上调用的函数。

背景技术

随着技术的进步，以电子形式存储的信息量以及对搜索、组织和/或操纵这种信息的实时或伪实时能力的需求不断增加。数据库管理系统(有时也称为数据库和数据仓库)被设计为以方便有效搜索、检索或操纵选定信息的形式组织数据。典型的数据库管理系统允许用户提交“查询”或以查询语言调用一个或多个函数，来搜索、组织、检索和/或操纵满足特定条件的信息。

根据星型模式设计某些数据库，其中，所谓的事实表包含例如订单中的行项，具有所谓维度表的键，每个键描述订单的属性，例如，日期、客户、供应商、部件等。星型模式基准(SSB)是旨在测量数据仓库应用程序中交易性能的基准，其中，数据存储在事实表和维度表中。用于执行星型连接查询的数据库查询执行逻辑(与SSB中的查询一样)传统上严重依赖于散列连接和布隆过滤器(Bloom Filter)，并在列存储扫描期间应用过滤器的结果。减少评估散列函数、消除散列冲突的歧义、保存到散列表和解析散列表元所花费的时间将是有利的。此外，减少在布隆过滤器上运行所产生的资源将是有利的。

发明内容

根据本公开的第一方面，提供了生成位图过滤器的计算机实现的方法，方法包括：接收过滤器参数；查询与过滤器参数相关联的第一数据源，以识别第一数据源中的具有对应于过滤器参数的标识符的至少一个条目；执行第一过程，第一过程包括：识别位图过滤器中的多个位位置中的零或单个位位置，零或单个位位置对应于第一数据源的与过滤器参数对应的条目的标识符，其中，每个标识符具有数值，并且基于相应标识符的数值来识别位位置；向标识符分配单个位位置，使得在对应于过滤器参数的每个标识符和位图过滤器中分配的位位置之间存在一对一映射；并且在分配的位位置处设置位；并且对第一数据源中具有对应于过滤器参数的标识符的另一条目重复第一过程。

每个标识符和相关位位置之间的一对一映射本质上是确定性的，因此避免了冲突，从而减少了确定和评估散列冲突通常所需的计算工作量。标识符数值的直接使用提供了不会因散列函数的评估和散列输出而变慢的快速处理。此外，一对一映射确保位图过滤器的长度足以覆盖对应于过滤器参数的第一数据源的标识符，同时不会不必要地扩展。位图过滤器的设计逻辑和随后的生成允许扩展的位向量存储在计算机的高速缓冲存储器中，从而提供快速处理。

根据本公开的第二方面，提供了使用由第一方面的方法生成的位图过滤器的计算机实现的方法，该方法包括：使用位图过滤器过滤数据源，该过滤包括：识别位图过滤器中的多个位位置中的单个位位置，该单个位位置对应于数据源的条目的标识符，其中，每个标识符具有数值，并且基于相应标识符的数值来识别该位位置；向标识符分配单个位位置，使得在位图过滤器中每个标识符和分配的位位置之间存在一对一映射；识别是否在分配的位位置处设置位；并且当设置位时，输出数据源的条目；并且对数据源的另一条目重复过滤。

根据本公开的第三方面，提供了使用由第一方面生成的位图过滤器的计算机实现的方法，该方法包括：使位图过滤器的设置位与数据源的条目相关联，其中，设置位位于位图过滤器内的位位置；基于在与数据源的条目相关联的设置位的位位置、和位图过滤器中对应于不同的已知行标识符的位位置之间的位位置中设置的位数的总和，确定另一数据源中关联行的行标识符；询问对应于确定的行标识符的另一数据源的相关行；并且输出来自另一数据源的相关行的信息。

对应于过滤器参数的标识符与位图过滤器内的单个位位置的一对一映射，使得能够直接查找另一数据源的特定行，该特定行定义了对应于过滤器的标识符。整数标识符用作行数组的索引。以这种方式，使用不需要散列函数评估或者不需要遍历多于一行来执行查找的简化的逻辑。

根据本公开的第四方面，提供了使用扩展位向量的计算机实现的方法，扩展位向量包括a)位图过滤器，被配置为实现数据源的条目的标识符与位图过滤器内的位位置的一对一映射，以及b)位图过滤器中设置的位的多个计数器，其中，位图过滤器的每个位位置与多个计数器中的一个相关联，方法包括：将位图过滤器的设置位与数据源的条目相关联，其中，设置位位于位图过滤器内的位位置；基于与设置位的位位置相关联的计数器的计数，来确定另一数据源中的相关行的行标识符，其中，计数器的计数是在与数据源的条目相关联的设置位的位位置和位图过滤器中对应于不同的已知行标识符的位位置之间的位位置中的设置位的数量的总和；询问对应于确定的行标识符的另一数据源的相关行；并且将来自另一数据源的相关行的信息导入到结果表中。

扩展位向量具有双重功能：(1)作为位图过滤器；以及(2)作为映射来促进数据库连接。对于(1)，位图过滤器是确定性的，因此不会产生误报。对于(2)，扩展位向量有效地将稀疏标识符转换成一组密集标识符。使用单个结构来执行(1)和(2)，减少了所需的内存量，这又允许将该结构存储在高速缓冲存储器中，以便使用简化的代码进行快速访问。

根据本公开的第五方面，提供了使用扩展位向量的计算机实现的方法，扩展位向量包括a)位图过滤器，被配置为实现数据源的条目的标识符与位图过滤器内的位位置的一对一映射，以及b)位图过滤器中设置的位的多个计数器C1至Cn，其中，位图过滤器的每个位位置与多个计数器C1至Cn中的一个相关联，方法包括：在第一寄存器Reg E中存储位图过滤器；在第二寄存器Reg B1中存储数据源的相应多个条目的多个标识符，其中，多个标识符基于位图过滤器定义的最小标识符值来移位；将第一单指令多数据SIMD指令应用到第二寄存器Reg B1，其中，第一SIMD指令被应用到由第二寄存器存储的所有标识符；基于第一SIMD指令的应用，生成存储在第三寄存器Reg B2中的数据，其中，第三寄存器Reg B2包括对应于第二寄存器Reg B1的位图过滤器的多个字节地址；将第二SIMD指令应用到第一寄存器Reg E和第三寄存器Reg B2，其中，第二SIMD指令被应用到由第一寄存器和第三寄存器存储的所有标识符；基于第二SIMD指令生成存储在第四寄存器Reg C中的数据，其中，第四寄存器RegC包括对应于Reg B2的字节地址的第一寄存器Reg E的版本；将第三SIMD指令应用到第二寄存器Reg B1和第四寄存器Reg C，其中，第三SIMD指令被应用到由第四寄存器存储的所有标识符；基于第三SIMD指令生成存储在第五寄存器Reg D中的数据，其中，第五寄存器Reg D识别第二寄存器Reg B1中与位图过滤器匹配的那些标识符。

扩展位向量的设计逻辑和后续生成允许将扩展位向量存储在计算机的高速缓冲存储器中，从而提供快速处理。此外，SIMD实现还减少了计算工作量(周期数)，同时提高了查询执行速度。这种并行处理特别有利于在连接过程的探测阶段内实现加速的小探测动作，例如，探测由连接过程的构建阶段产生的小的行集合。在一个示例中，小的行集合可以足够小，使得用于构建边行集合的位图过滤器可以适合计算机处理器的寄存器组，例如，单指令多数据(SIMD)寄存器组。

附图说明

通过以下结合附图的详细描述，本公开的各种特征将变得显而易见，附图共同示出了本公开的特征，其中：

图1A是根据一个示例的星型模式数据库的示意图；

图1B是根据一个示例的数据源的示意图；

图1C是根据一个示例的生成位图过滤器的示意图；

图2是根据一个示例的生成位图过滤器的示意图；

图3是根据一个示例的生成位图过滤器的示意图；

图4A是根据一个示例的位图过滤器的示意图；

图4B是根据另一示例的位图过滤器的示意图；

图5是根据一个示例的生成图1的位图过滤器的方法的流程图；

图6是根据另一示例的生成图5的位图过滤器的方法的流程图；

图7是根据一个示例的数据源的示意图；

图8是根据一个示例的使用位图过滤器的示意图；

图9是根据一个示例的使用位图过滤器的示意图；

图10是根据另一示例的使用位图过滤器的示意图；

图11是根据一个示例的使用图8和图9的位图过滤器的方法的流程图；

图12是根据另一示例的使用位图过滤器的示意图；

图13是根据一个示例的使用图12的位图过滤器的方法的流程图；

图14是根据另一示例的使用扩展位图向量的示意图；

图15是根据另一示例的图14的扩展位向量方法的示意图；

图16是根据一个示例的使用图12的扩展位图向量的方法的流程图；

图17是根据一个示例的单指令多数据实现的示意图；

图18是根据一个示例的单指令多数据实现的示意图；

图19是根据一个示例的实现单指令多数据实现的方法的流程图；

图20是根据一个示例的装置的示意图。

具体实施方式

连接过程(join process)是执行与存储在关系数据库中的数据相关的查询的一种方式。连接过程有构建阶段，随后是探测阶段。

图1A示出了本文描述的实施例具有特定应用的星形模式数据库DB1。数据库DB1包括事实表10和三个维度表12、14、16，分别涉及日期、位置、名称。

维度表12、14和16中的每一个都可以与查询条件相关，并且形成连接过程的构建阶段的基础。因此，维度表12、14和16中的每一个都可以被称为构建侧数据源。如稍后更详细描述的，作为构建阶段的一部分，基于构建侧数据源并根据查询条件，生成过滤器和映射结构。

事实表10可以用作连接过程的探测阶段的一部分。因此，事实表10可以被称为探测侧数据源。在这样的探测阶段，询问探测侧数据源，以便使用探测侧数据源的行来探测在构建阶段生成的过滤器和映射结构。

图1B示出了对应于图1A的一个维度表12的数据，维度表12应用了本文描述的实施例。应当理解，实施例适用于维度表12、14、16中的任何一个，并且因此图1B所示的数据结构一般被称为第一数据源100。如图1B所示，第一数据源100具有多个条目140

第一数据源100可以是描述性数据源，其中，每个条目140

参考图1C，接收与第一数据源100相关联的过滤器参数50，并形成对第一数据源100的查询的基础，以识别第一数据源100的具有对应于过滤器参数50的标识符120

在图1C的示例中，过滤器参数50涉及周末。随后，对应于周末的数据源100的条目被识别为具有对应于过滤器参数50的标识符。

数据源100的具有对应于过滤器参数50的标识符的条目被识别为条目140

在构建阶段，通过将第一数据源100的对应于过滤器参数50(标识符120

最大标识符值-(减)最小标识符值+(加)1 (1)

在图1C的示例中，最大标识符值是“ID9”的9。最小标识符值是“ID3”的3。

因此，位图过滤器300的长度是：

9-3+1＝7位位置

如图1C所示，该示例中的位图过滤器300具有7个位位置350

在该示例中，单个位位置350

在分配位位置350

上述识别、分配和位设置过程可以统称为第一过程。对第一数据源100的子集200内的另一条目240

为了生成与过滤器参数50相关联的完整位图过滤器300，对第一数据源100的子集200的所有条目重复第一过程，导致位图过滤器300具有分配给对应于第一数据源100的子集200内的条目(240

由每个相关标识符和相关联的位位置之间的一对一映射生成的位图过滤器(例如，位图过滤器300)本质上是确定性的，因此避免了冲突，从而减少了确定和评估散列冲突通常需要的计算工作。

图2是根据数据源100的子集200生成的位图过滤器300的示意图。子集200的每个条目240

如上所述，使用对应于过滤器参数50的每个标识符(在该示例中：ID3、ID4、ID7、ID9)和位图过滤器300中的分配的位位置350

作为示例，一对一映射导致对应于接收到的过滤器参数的标识符的最小整数值映射到位图的第一位位置、和对应于接收到的过滤器参数的标识符的最大整数值映射到位图的最后位位置。参考图2，最小值标识符“ID3”映射到位图过滤器300的第一位位置350

对应于第一数据源100的与过滤器参数50对应的条目子集200的每个标识符120

在图3的示例中，函数F的执行将每个标识符220

这可以概括为：

标识符的数值-(减)最小值标识符的数值与(加)1(1)＝位位置

在当前示例中，子集200的条目240

4-3+1＝2

通过这种方式，ID4映射到第二位位置，即位图过滤器300内的位位置350

当位图过滤器具有与位图过滤器300不同的格式时，也可以实现标识符值和位图过滤器的位位置之间的一对一映射。图4A和图4B提供了其他位图过滤器302和305的示例，但没有示出这些位是被设置为二进制值1还是被设置为二进制值0；然而，与前面的讨论一致，每个位图的第一位位置和最后位位置将具有分别对应于最小位和最大位的设置位。通过这种方式，位图过滤器302和305不会不必要地长。在对应于过滤器的条目的子集由单个条目组成的示例中，如前所述生成的位图过滤器的最小位和最大位将是在单个位位置的相同位。

图4A示出了存储为多个字节303

参考图4A，该函数可以是模函数，该模函数：(1)通过将标识符的数值除以与每个字节相关联的位位置的数量来生成商，该商识别字节数；以及(2)余数，余数识别所识别的字节内的位数。在基于零的位编号系统0-7和基于零的字节编号系统的上下文中，模函数可以概括为：

在另一示例中，可以使用1-8的位编号系统，在这种情况下，用于识别位位置和向数据源的标识符分配位位置的函数可以是将商值和余数值加1的模函数。

对于位图过滤器302，应用于标识符值11(其中，最小值标识符是1)的模函数将如下：

商是1，所以识别字节303

在另一示例中，对于位图过滤器302，应用于标识符值16的模函数将如下，其中，最小值标识符是1：

商是1，所以识别字节303

在图4B所示的另一示例中，位图过滤器305可以被分成多个字306

对于位图过滤器305，具有基于零的字编号系统0-2和基于零的位编号系统0-31，可以以类似于位图过滤器302所述的方式使用模函数，其中，商识别位图过滤器305内的字，以及余数识别所识别的字内的位：

图5是生成图1至图3的位图过滤器300的方法400的流程图。方法400开始于框410，在框410，接收过滤器参数50。接下来，方法400前进到框420，在框420，查询与过滤器参数50相关联的第一数据源100，以识别第一数据源100中具有对应于过滤器参数50的标识符120

参考图6并参考图1C，框440的第一过程开始于框442，其中，识别位图过滤器300中的多个位位置350

然后该方法前进到框444，其中，单个位位置350

图7是数据源500的示意图。数据源500对应于图1中数据库DB1的事实表10。图7的数据源500具有多个条目540

因为数据源500是事实表，所以多个条目540

在另一示例中，数据源500可以是维度表。

图8是使用由前述方法生成的位图过滤器的示意图，例如，位图过滤器300。在这个示例中，使用位图过滤器300过滤图7的数据源500。换言之，使用数据源500的行来探测位图过滤器300。为了便于参考，在图8中仅再现了数据源500的日期相关部分。

由位图过滤器300执行的过滤过程类似于生成位图过滤器300的过程，因为输入值(例如，标识符值)被转换为位图过滤器的单个位位置。这种转换可以是函数应用到输入标识符值的数值上。这样，参考图3、图4A和图4B的“生成”示例讨论的不同函数也适用于过滤过程，现在将更详细地讨论过滤过程。

位图过滤器300被应用于数据源500，并将每个条目识别为与位图过滤器300匹配或不匹配。将位图过滤器300应用于数据源500，可以是对多个条目540

如上所述，位图过滤器300已经在位图过滤器300内的位位置处设置位，以滤掉不匹配项。如果数据源500的待过滤的项(例如，标识符520

在该示例中，标识符520

仔细观察过滤过程，首先通过对应于数据源500的条目540

图9是在数据源500的另一条目上使用位图过滤器300的示意图，具体而言，在参考图8讨论的条目540

在这个示例中，标识符520

在参考图8和图9描述的过滤过程中，在前述过滤过程之前可以存在额外步骤，因此可以称为预过滤步骤。额外步骤确定数据源500的条目540

如参考图2所述，基于标识符值ID3、ID4、ID7和ID9生成位图过滤器300。这样，与具有ID10的标识符520

在一个示例中，可以生成表示数据源(例如，数据源500)的标识符是否存在于位图过滤器(例如，位图过滤器300)中的数组。可以基于所讨论的标识符和位图过滤器内的相应字节地址之间的关系来生成这种数组。更详细地，识别对应于数据源的整数标识符的位位置。该位位置与位图过滤器内的字节地址相关联。询问位图过滤器中对应于字节地址的字节，以确定是否在识别的位位置处设置位。如果该位被设置，则数组中相应字节被设置为“1”，否则该字节被置为“0”。

图10是示出将条目540

这种进一步处理的一个示例可以是事实表条目540

进一步处理的另一示例是多重连接操作，其中，事实表条目和第一维度表的条目之间的第一连接操作的结果馈入第一连接操作的结果和第二维度表的条目之间的第二连接操作。如上所述，以这种方式操作符的应用可以看作是操作符树。

对应于数据源500的条目的标识符的单个位位置350

如上面参考图4A和图4B所解释的，位图过滤器300可以具有多个字节，其中，位图过滤器300的位位置的子集与每个字节相关联。在这种情况下，为了识别位位置并且将其分配给数据源500的标识符，可以使用函数，当执行该函数时，基于标识符的数值识别位图过滤器300的字节地址并识别所识别的字节内的位地址，其中，字节地址和位地址识别出单个位位置350

图11是使用并且更具体地探测由参考图1至图6讨论的方法生成的位图过滤器的方法800的流程图。方法800开始于框810，其中，使用位图过滤器300过滤数据源500。该方法进行到框820，其中，识别位图过滤器300中的多个位位置350

在识别之后，该方法进行到框830，其中，单个位位置350

在框840，该方法识别是否在分配的位位置350

在框850，如果该位被设置，则输出数据源500的条目。在输出之后，在框860，对数据源500的另一条目540

图12是使用由参考图1至图6讨论的方法生成的位图过滤器300的示意图。在该示例中，使用位图过滤器300过滤数据源900。即，位图过滤器由数据源900探测。数据源900对应于参考图7至图10描述的数据源500。参考图12描述的示例类似于参考图7至图10描述的示例，但是进一步描述了在识别另一数据源的相关行时使用位图过滤器，其中，该行对应于数据源900的标识符。

在图12的示例中，位图过滤器300在位位置350

数据源950是中间表。在该示例中，数据源950包含标识符952

基于在与数据源900的条目相关联的设置位的位位置350

在这个示例中，位位置350

总和3(3)将另一数据源950的第三行950

信息的输出可以是用于将不同数据源的匹配行拉在一起的连接过程的部分。

对应于过滤器参数的单个整数标识符与位图过滤器300内的单个位位置的一对一映射，使得能够直接查找到另一数据源的定义对应于过滤器的标识符的特定行。单个整数标识符充当行数组的索引。以这种方式，使用简化的逻辑，无需散列函数评估、散列输出验证(以确保没有冲突)或者遍历多于一行来执行查找。

图13是使用由参考图1至图6描述的方法生成的位图过滤器的方法1000的流程图。

方法1000开始于框1100，其中，位图过滤器300的设置位与数据源900的条目940

该方法进行到框1200，其中，基于在与数据源的条目相关联的设置位的位位置350

在确定之后，在框1300，询问对应于所确定的行标识符951

在询问之后，在框1400，输出来自数据源950的相关行950

图14是在数据源970上使用扩展位图向量600的示意图。扩展位图向量600包含位图过滤器650和多个计数器610

数据源970是与由数据源500和数据源900表示的事实表不同的事实表。数据源970包含由另一数据源定义的多个标识符980

多个计数器610

在该示例中，位位置650

扩展位向量600具有双重功能：(1)作为位图过滤器；以及(2)作为映射来促进数据库连接。对于(1)，位图过滤器是确定性的，因此不会产生误报。对于(2)，扩展位向量600有效地将稀疏标识符转换成一组密集标识符。使用单个结构来执行(1)和(2)，减少了所需的内存量，这又允许将该结构存储在高速缓冲存储器中，以便使用简化的代码进行快速访问。

在一个示例中，位图过滤器650的32位部分可以与32位预计算计数器交错。

数据源995具有与图12的示例的数据源950相同的功能，因为数据源995是包括对应于过滤器参数的多个条目995

在这个示例中，在识别数据源995的一行之后，该行中的信息可以输出到结果集999的行999

每个计数器610

图15是图14的扩展位图向量600的示意图。位图过滤器650被分成多个部分，包括第一部分651、第二部分652和第三部分653。位图过滤器650的第二部分652紧跟在第一部分651之后，并且包括所讨论的设置位，在这种情况下，设置位在位位置650

计数器610

计数器610

图16是使用扩展位向量600的方法2000的流程图，扩展位向量600包括a)位图过滤器650，被配置为实现数据源的条目的标识符与位图过滤器650内的位位置的一对一映射，以及b)位图过滤器650中设置的位的多个计数器610

方法2000开始于框2100，其中，位图过滤器650的设置位与数据源970的条目990

该方法进行到框2200，其中，基于与设置位的位位置650

在框2300，方法2000继续询问对应于所确定的行标识符996

在询问之后，在框2400，输出来自数据源995的相关行995

如上面简要提到的，根据参考图7至图19描述的方法的位图过滤器可以针对数据源的多个条目并行化。具体地，过滤过程的并行处理可以使用单指令多数据(SIMD)处理来实现。这种并行处理尤其有利于在连接过程的探测阶段内实现加速的小探测动作，例如，对于在构建侧具有一小组标识符的小探测。在一个示例中，一小组标识符的大小可以使得用于标识符的位图过滤器能够适合计算机处理器的寄存器组，例如，SIMD寄存器细。

在探测阶段，SIMD处理可用于使用由前述方法生成的位图过滤器过滤数据源，例如，位图过滤器300(参见图1C、图2、图3、图8、图9和图12)和位图过滤器650(参见图14和图15)。当确定扩展位图向量(例如，图14和图15的扩展位图向量600)的匹配标识符的行标识符时，也可以使用SIMD处理。前述用于生成位图过滤器的算法的流线型性质以及随后使用位图过滤器的过滤，能够实现通过SIMD的细粒度并行化。如下面将更详细讨论的，SIMD增强方法可以采用打包的编码标识符值，并且(1)对照位图过滤器检查值(即，使用位图过滤器过滤值)；以及(2)将值转换成数据源的行位置。在(1)的检查和(2)的转换之后，可以在至少一行探测侧数据源和至少一行构建侧数据源之间(在对应的识别的行位置)执行连接过程。

图17是根据实施例的SIMD过滤过程的输出的示意图。每个寄存器A至D都是SIMD寄存器，包含从计算机存储器加载的数据。对每个寄存器的操作可以是应用于所讨论的寄存器内的多个数据、优选所有数据的SIMD指令。在本公开的上下文中，“SIMD指令”可以指对寄存器内的相同数据部分进行操作的多个SIMD指令。

图17和图18中对每个寄存器的描述示出了加载到每个寄存器中的数据的逻辑配置。计算机存储器内数据的物理地址可以不同于寄存器内数据的所描述的逻辑配置和计算机存储器内数据的逻辑地址。

位图过滤器可以从计算机存储器加载到计算机处理器的一个或多个寄存器中。位图过滤器的大小确定从计算机存储器加载位图过滤器所需的寄存器数量。如果位图过滤器的长度超过寄存器的长度，例如，位图可以是128位并且寄存器可以是64位，则需要多个寄存器来存储位图。作为另一示例，位图过滤器可能需要32×256位寄存器。与计算机处理器相关联的编译器确定计算机处理器的哪些寄存器用于加载位图过滤器。

在位图过滤器的大小需要多个寄存器的情况下，可能需要一个或多个额外步骤来识别多个寄存器中的哪个寄存器与SIMD实现相关。下面将更详细地讨论额外步骤。

寄存器A(Reg A)是存储一部分位图过滤器670的计算机处理器的多个寄存器中的单个寄存器。为了便于参考，图17描述了Reg A的16位部分。至于位图过滤器300和位图过滤器650，位图过滤器670提供整数标识符值和位图过滤器670的单个位位置之间的一对一映射。

Reg A的位图过滤器670在位位置0、3、9和11处有设置位(由填充块表示)。因此，映射到位位置0、3、9和11中的一个的任何标识符值将被认为与位图过滤器670定义的过滤条件相匹配。

寄存器B1(Reg B1)表示要使用Reg A的位图过滤器670过滤的8位整数标识符序列。由于图17的示例使用基于零的编号系统，待过滤的标识符在Reg B1中由整数1、3、9和4表示，这些整数对应于位图过滤器670中表示的最小标识符值(对应于位图过滤器670的最小位位置)移位的每个标识符。因此，Reg B1的整数1、3、9和4识别了要从位图过滤器670中提取的相应位的位地址，从而可以进行过滤。在图17的示例中，最小位位置对应于最小标识符值4(4)：

向Reg B1应用操作以创建要存储在寄存器B2(Reg B2)中的数据，作为输出。在本示例中，对Reg B1应用逐个字节除法运算，将Reg B1的整数值除以8(8)。除法运算为Reg B1的每个整数(位地址)输出一个字节地址。在当前情况下：

在另一示例中，应用于Reg B1的操作可以是以下中的一个：按位OR操作、按位AND操作和掩码操作。

Reg B2表示与Reg B1的标识符相对应的Reg A的位图过滤器的字节的字节地址。

通过基于Reg B2对Reg A应用操作，创建寄存器C(Reg C)的内容。应用于Reg A的操作导致Reg C包含与Reg B2的识别的字节地址相对应的Reg A的数据版本。基于Reg B2应用于Reg A的操作可以是以下中的一个或多个：复制操作、加载操作、掩码操作、查找操作和获取操作。

寄存器D(Reg D)包含作为基于Reg B1的位地址应用于Reg C的操作的输出而产生的数据。该操作产生表示位图过滤器670中是否存在Reg B1的标识符的Reg D。Reg D为每个标识符值使用一个字节，其中，如果在位图过滤器670中不存在标识符(不匹配)，则该字节为“0”，以及如果在位图过滤器670中存在标识符(匹配)，则该字节为“1”。基于Reg B1应用于Reg C的操作可以是以下中的一个或多个：查找操作、获取操作和成对操作，例如，成对掩码、成对移位或成对AND。

在一个示例中，Reg D用作数据源(例如，事实表)的整数标识符的数组F[0…n-1]的输出数组Q[0…n-1]的基础，使得如果在位图过滤器670表示的过滤条件中不存在F[i]，则Q[i]＝0，否则Q[i]＝1。

如上所述，位图过滤器670被加载到多个寄存器中，并且Reg A是存储位图过滤器670的一部分的多个寄存器(未示出)中的单个寄存器。在图17的示例中，Reg A被识别为与Reg B1的标识符相关的寄存器，并且Reg B1的标识符是8位标识符。

如上所述，B1的标识符可以是16位标识符，因此Reg B1对于每个标识符值具有两个字节。在这种情况下，其中，位图过滤器的大小大于单个寄存器，位图过滤器被加载到多个寄存器中，并且实施两步过程，来识别位图过滤器内对应于16位标识符的位位置。首先，每个16位标识符的高位字节识别多个寄存器中包含对应于该标识符的位的相关寄存器。其次，每个16位标识符的低位字节确定对应于该标识符的位(如以上针对8位标识符所述)是否被设置。

图18是如何使用SIMD来确定扩展位图向量的匹配标识符的行位置的示意图。图18的示例可以结合图17的示例来实现，使得过滤和行识别过程一起操作。

图18的示例也可以结合前述示例来实现，其中，B1的标识符是16位标识符，并且位图过滤器大于单个寄存器，使得位图过滤器被加载到多个寄存器中，并且实现两阶段过程来识别位图过滤器内对应于16位标识符的位位置。在这种情况下，使用包括可以被加载到多个寄存器中并且被配置为实现数据源的条目的16位标识符与位位置的一对一映射的位图过滤器的扩展位向量的计算机实现的方法包括：识别多个寄存器中的对应于数据源的条目的标识符的寄存器，其中，每个标识符具有数值，并且基于对应标识符的数值来识别寄存器；并且识别寄存器中多个位位置中对应于标识符的单个位位置，其中，基于标识符的数值来识别位位置。在一个示例中，基于16位标识符的高位字节来识别寄存器，并且基于16位标识符的低位字节来识别标识符内的位位置。

图18的寄存器E(Reg E)是寄存器的表示，该寄存器存储RegA(为了便于参考，在图18中再现)的位图过滤器670的部分中设置位的计数。这样，RegA和Reg E一起存储扩展位图向量675，类似于图14的扩展位图向量600。

每个计数器C1、C2和C3定义位图过滤器的先前部分中设置位数量的计数。在这种情况下，计数器C1先于位图过滤器的第一字节(字节0)之前，因此计数器C1的计数为0(零)。计数器C2定义先前字节0中设置的数量的计数。在这种情况下，在字节0中设置位位置0和位位置3的位，因此计数器C2的计数为2(2)。C3计数器定义先前字节中设置的位数量的计数：字节0和字节1。在这种情况下，在字节0中设置位位置0和位位置3的位，在字节1中设置位位置9和位位置11的位，因此计数器C3的计数为4(4)。

图18中的寄存器B1、B2和D与图17中的寄存器B1、B2和D相同。虽然没有示出Reg C，但是从前面可以理解，它用于在Reg D中生成数据。

为了在中间数据源中为Reg B1的匹配的标识符识别行位置(例如，行标识符)，基于Reg B2和Reg E向Reg D应用操作，以创建存储在另一寄存器(寄存器F)中的数据，该寄存器指示与Reg B2的识别字节相关联的计数器的计数。基于Reg B2和Reg E应用到Reg D的操作将Reg E的相关计数器的版本输入到Reg F，并且可以是以下中的一个或多个操作：查找操作、复制操作、加载操作、掩码操作和获取操作。

更详细地说，与已识别字节(Reg B2)的设置位(来自Reg D)相关联的计数器版本从Reg E复制并输入到Reg F。

在图18的示例中，Reg D指示(使用“1”)B1的标识符3与Reg E的位图过滤器匹配。标识符3的字节地址是字节0(由Reg B2指示)。因此，计数器C1的计数(与字节0相关联)被复制并输入到Reg F。类似地，Reg D指示(使用“1”)B1的标识符9与Reg E的位图过滤器匹配。标识符9的字节地址是字节1(由Reg B2指示)。因此，计数器C2的计数(与字节1相关联)被复制并输入到Reg F。

对Reg F应用操作，以创建存储在另一寄存器(Reg G)中的数据，其中，Reg G指示对应于与Reg F的计数相关的匹配标识符的行位置，即Reg B1的标识符3和9。该操作将设置在由Reg B2指示的字节地址的字节中的位数添加到Reg F的计数中，该位数多达并且包括设置在由Reg B1指示的标识符的位地址的位。

对于Reg B1的标识符3，字节0中设置的位数(由Reg B2指示)(最多并包括位地址3处设置的位)为2(2)，因为设置位位置0处的位并且设置位位置3处的位(如所预期的，由于Reg D指示与标识符3相关联的位被设置)。根据先前段落的解释，行位置等于计数器C1的计数(0，由Reg F指示)和2(2)的总和，即2(2)。因此，中间表的第二行包含与Reg B1的标识符3相关联的信息。

对于Reg B1的标识符9，字节1中设置的位数(由Reg B2指示)(最多并包括位地址9处设置的位)为1(1)，因为位位置9处的位被设置并且这是字节1的第一个设置位。行位置等于计数器C2的计数(2，由Reg F指示)和1(1)的总和，即3(3)。因此，中间表的第三行包含与Reg B1的标识符9相关联的信息。

图18的示例的操作如下：

由Reg G引用的中间表是包含输入表(例如，类似图12的数据源900和图14的数据源970)的条目的表(例如，类似图12的950和图14的995)，这些条目与过滤器参数匹配，用于生成位图过滤器670。由Reg G引用的中间表的列包含与过滤器参数匹配的标识符。在这种情况下，标识符对应于Reg B1的标识符3和9(因为它们与Reg D指示的设置位相关)。标识符基于数值进行排序，由Reg G引用的中间表的每一行都有行标识符。Reg G表示定义标识符3和9中每一个的中间表的行。

在另一示例中，Reg E的设置位的计数器可以存储在与Reg A的位图过滤器相同的寄存器中。在一个示例中，计数器可以是32位计数器，并且被插入在位图过滤器的32位部分之间，形成扩展位向量。

在一个示例中，参考图17和图18描述的SIMD实现，可以针对加载位图过滤器的处理器的SIMD寄存器组中的每个寄存器进行重复，其中，重复次数对应于加载位图过滤器的SIMD寄存器的数量。例如，SIMD寄存器组可以由加载位图过滤器的最多8个寄存器组成。在一个示例中，位图过滤器的128位部分可以被加载到每个SIMD寄存器中。每个寄存器可以是256位寄存器。例如，在图17和图18的示例中，Reg A可以是存储位图过滤器670的8个寄存器中的一个。寄存器访问比存储器访问快得多，因此针对多达8个SIMD寄存器的每个寄存器重复图17和图18的SIMD实现，可以非常快速地处理多达8个SIMD寄存器中的数据。如果位图过滤器的一部分与探测无关，则该部分可以忽略，例如，通过屏蔽该部分。

参考图17和图18描述的SIMD实现，可以由具有SIMD扩展和任何大小的SIMD寄存器的处理器来实现。SIMD寄存器的示例包括：AVX-2SIMD寄存器和AVX-512寄存器。在替代示例中，对应于图1至图16的实施例可以在没有SIMD扩展的情况下实施，例如，使用任何现代处理器，例如，Intel Xeon、AMD Opteron和ARM。

图19是根据参考图17和图18描述的示例实现单指令多数据实现的方法3000的流程图。

参考图18所示的寄存器A和寄存器E的示例扩展位向量675来描述方法3000。寄存器A和寄存器E包括：a)Reg A中的位图过滤器670(参考图17描述)以及b)Reg E中的位图过滤器670中设置的位的多个计数器C1至Cn，其中，位图过滤器670的每个位位置与多个计数器C1至Cn中的一个相关联。方法3000开始于框3100，将位图过滤器670和多个计数器C1至Cn分别存储在寄存器Reg A和Reg E中。

接下来，方法3000进行到框3200，其中，数据源的相应多个条目的多个标识符存储在第二寄存器Reg B1中，其中，多个标识符中每一个的整数值基于位图过滤器670定义的最小标识符值移位。

在框3200的存储步骤之后，方法3000继续到框3300，其中，第一单指令多数据指令SIMD指令被应用到第二寄存器Reg B1。此后，方法3000前进到框3400，在框3400中，基于第一SIMD指令的应用，生成存储在第三寄存器Reg B2中的数据，其中，第三寄存器Reg B2包括对应于第二寄存器Reg B1的位图过滤器(670)的多个字节地址。

接下来，方法3000移动到框3500，其中，第二SIMD指令被应用到第一寄存器Reg A和第三寄存器Reg B2。在框3500之后，方法3000继续到框3600，在框3600中，基于第二SIMD指令，生成存储在第四寄存器Reg C中的数据，其中，第四寄存器Reg C包括对应于Reg B2的字节地址的第一寄存器Reg A的版本。

在框3600之后，在框3700，第三SIMD指令被应用于第二寄存器Reg B1和第四寄存器Reg C。接下来，在框3800，基于第三SIMD指令，生成存储在第五寄存器Reg D中的数据，其中，第五寄存器Reg D识别第二寄存器Reg B1的标识符是否与位图过滤器匹配(670)。

在框3700之后，在框3900，为与位图过滤器670匹配的每个标识符识别数据源中的行位置。框3900的识别由框3910、3920、3920和3940组成。在框3910，方法3000继续将第四SIMD指令应用到第三寄存器B2和第五寄存器Reg D。

方法3000进行到框3920，在框3920中，基于第四SIMD指令，生成存储在第六寄存器Reg F中的数据，其中，第六寄存器Reg F包括与Reg B2中指示的字节相关联的计数器的计数，该字节包含与位图过滤器匹配的标识符(670)，如Reg D中所示。

在框3920之后，方法3000继续到框3930，其中，第五SIMD指令被应用到第六寄存器Reg F。在该应用之后，在框3940，基于第五SIMD指令生成存储在第七寄存器Reg G中的数据，其中，第七寄存器Reg G包括与位图过滤器(670)匹配的每个标识符的行位置。

在一个示例中，方法3000可以包括输出步骤，其中，输出表示第五寄存器Reg D的数组。在另一示例中，方法3000可以包括输出步骤，其中，输出表示第七寄存器Reg G的数组。

图17至图19的SIMD实现示例能够加速数据库查询执行，以(1)识别是否由位图过滤器表示输入，以及(2)为与位图过滤器匹配的每个输入确定另一数据结构内的行位置(例如，行标识符)。(1)的识别和(2)的确定可以是连接过程的探测阶段的一部分。

本申请中描述的示例提供了数据库查询执行逻辑，该逻辑生成位图过滤器，使用位图过滤器过滤一系列输入值，并使用减少的计算周期(例如，减少评估散列函数所花费的时间)来确定对应于匹配输入值的行标识符。示例数据结构的设计逻辑和后续生成(例如，所描述的位图过滤器和扩展位图向量)允许数据结构存储在计算机的高速缓冲存储器中，并因此提供快速处理。此外，SIMD实现还减少了计算工作量(周期数)，同时提高了查询执行速度。

图20是配置有软件以执行本文描述的功能的示例性装置5000的示意图。装置5000具有计算机可读介质5100和处理器5300。计算机可读介质5100包含指令5200，当由处理器5300执行时，指令5200使得处理器5300执行以下一个或多个先前描述的方法，即方法400；方法800，方法1000；以及方法2000。处理器5300可以是参考图17、图18和图19讨论的处理器类型，例如，(a)具有或不具有SIMD扩展的处理器，例如，Intel Xeon、AMD Opteron、ARM等，以及(b)具有SIMD扩展的任何处理器，例如但不限于Intel AVX-2和AVX-512指令集。在前面描述中，出于解释的目的，阐述了某些示例的许多具体细节。说明书中对“示例”或类似语言的引用意味着结合该示例描述的特定特征、结构或特性包括在至少一个示例中，但不一定包括在其他示例中。

上述示例应被理解为说明性的。应当理解，关于任何一个示例所描述的任何特征可以单独使用，或者与所描述的其他特征结合使用，并且也可以与任何其他示例的一个或多个特征结合使用，或者与任何其他示例的任何组合结合使用。此外，也可以采用上面没有描述的等同物和修改。