位图过滤器、其生成方法及用位图过滤器执行连接的方法与流程
:随着技术的进步，以电子形式存储的信息量以及对搜索、组织和/或操纵这种信息的实时或伪实时能力的需求不断增加。
数据库管理系统(有时也称为数据库和数据仓库)被设计为以方便有效搜索、检索或操纵选定信息的形式组织数据。
根据星型模式设计某些数据库，其中，所谓的事实表包含例如订单中的行项，具有所谓维度表的键，每个键描述订单的属性，例如，日期、客户、供应商、部件等。
星型模式基准(ssb)是旨在测量数据仓库应用程序中交易性能的基准，其中，数据存储在事实表和维度表中。
用于执行星型连接查询的数据库查询执行逻辑(与ssb中的查询一样)传统上严重依赖于散列连接和布隆过滤器(bloomfilter)，并在列存储扫描期间应用过滤器的结果。
减少评估散列函数、消除散列冲突的歧义、保存到散列表和解析散列表元所花费的时间将是有利的。
此外，减少在布隆过滤器上运行所产生的资源将是有利的。
技术实现要素:根据本公开的第一方面，提供了生成位图过滤器的计算机实现的方法，方法包括:接收过滤器参数;查询与过滤器参数相关联的第一数据源，以识别第一数据源中的具有对应于过滤器参数的标识符的至少一个条目;执行第一过程，第一过程包括:识别位图过滤器中的多个位位置中的零或单个位位置，零或单个位位置对应于第一数据源的与过滤器参数对应的条目的标识符，其中，每个标识符具有数值，并且基于相应标识符的数值来识别位位置;向标识符分配单个位位置，使得在对应于过滤器参数的每个标识符和位图过滤器中分配的位位置之间存在一对一映射;并且在分配的位位置处设置位;并且对第一数据源中具有对应于过滤器参数的标识符的另一条目重复第一过程。
每个标识符和相关位位置之间的一对一映射本质上是确定性的，因此避免了冲突，从而减少了确定和评估散列冲突通常所需的计算工作量。
标识符数值的直接使用提供了不会因散列函数的评估和散列输出而变慢的快速处理。
此外，一对一映射确保位图过滤器的长度足以覆盖对应于过滤器参数的第一数据源的标识符，同时不会不必要地扩展。
位图过滤器的设计逻辑和随后的生成允许扩展的位向量存储在计算机的高速缓冲存储器中，从而提供快速处理。
根据本公开的第二方面，提供了使用由第一方面的方法生成的位图过滤器的计算机实现的方法，该方法包括:使用位图过滤器过滤数据源，该过滤包括:识别位图过滤器中的多个位位置中的单个位位置，该单个位位置对应于数据源的条目的标识符，其中，每个标识符具有数值，并且基于相应标识符的数值来识别该位位置;向标识符分配单个位位置，使得在位图过滤器中每个标识符和分配的位位置之间存在一对一映射;识别是否在分配的位位置处设置位;并且当设置位时，输出数据源的条目;并且对数据源的另一条目重复过滤。
根据本公开的第三方面，提供了使用由第一方面生成的位图过滤器的计算机实现的方法，该方法包括:使位图过滤器的设置位与数据源的条目相关联，其中，设置位位于位图过滤器内的位位置;基于在与数据源的条目相关联的设置位的位位置、和位图过滤器中对应于不同的已知行标识符的位位置之间的位位置中设置的位数的总和，确定另一数据源中关联行的行标识符;询问对应于确定的行标识符的另一数据源的相关行;并且输出来自另一数据源的相关行的信息。
对应于过滤器参数的标识符与位图过滤器内的单个位位置的一对一映射，使得能够直接查找另一数据源的特定行，该特定行定义了对应于过滤器的标识符。
以这种方式，使用不需要散列函数评估或者不需要遍历多于一行来执行查找的简化的逻辑。
根据本公开的第四方面，提供了使用扩展位向量的计算机实现的方法，扩展位向量包括a)位图过滤器，被配置为实现数据源的条目的标识符与位图过滤器内的位位置的一对一映射，以及b)位图过滤器中设置的位的多个计数器，其中，位图过滤器的每个位位置与多个计数器中的一个相关联，方法包括:将位图过滤器的设置位与数据源的条目相关联，其中，设置位位于位图过滤器内的位位置;基于与设置位的位位置相关联的计数器的计数，来确定另一数据源中的相关行的行标识符，其中，计数器的计数是在与数据源的条目相关联的设置位的位位置和位图过滤器中对应于不同的已知行标识符的位位置之间的位位置中的设置位的数量的总和;询问对应于确定的行标识符的另一数据源的相关行;并且将来自另一数据源的相关行的信息导入到结果表中。
扩展位向量具有双重功能:(1)作为位图过滤器;以及(2)作为映射来促进数据库连接。
对于(2)，扩展位向量有效地将稀疏标识符转换成一组密集标识符。
使用单个结构来执行(1)和(2)，减少了所需的内存量，这又允许将该结构存储在高速缓冲存储器中，以便使用简化的代码进行快速访问。
根据本公开的第五方面，提供了使用扩展位向量的计算机实现的方法，扩展位向量包括a)位图过滤器，被配置为实现数据源的条目的标识符与位图过滤器内的位位置的一对一映射，以及b)位图过滤器中设置的位的多个计数器c1至cn，其中，位图过滤器的每个位位置与多个计数器c1至cn中的一个相关联，方法包括:在第一寄存器rege中存储位图过滤器;在第二寄存器regb1中存储数据源的相应多个条目的多个标识符，其中，多个标识符基于位图过滤器定义的最小标识符值来移位;将第一单指令多数据simd指令应用到第二寄存器regb1，其中，第一simd指令被应用到由第二寄存器存储的所有标识符;基于第一simd指令的应用，生成存储在第三寄存器regb2中的数据，其中，第三寄存器regb2包括对应于第二寄存器regb1的位图过滤器的多个字节地址;将第二simd指令应用到第一寄存器rege和第三寄存器regb2，其中，第二simd指令被应用到由第一寄存器和第三寄存器存储的所有标识符;基于第二simd指令生成存储在第四寄存器regc中的数据，其中，第四寄存器regc包括对应于regb2的字节地址的第一寄存器rege的版本;将第三simd指令应用到第二寄存器regb1和第四寄存器regc，其中，第三simd指令被应用到由第四寄存器存储的所有标识符;基于第三simd指令生成存储在第五寄存器regd中的数据，其中，第五寄存器regd识别第二寄存器regb1中与位图过滤器匹配的那些标识符。
扩展位向量的设计逻辑和后续生成允许将扩展位向量存储在计算机的高速缓冲存储器中，从而提供快速处理。
此外，simd实现还减少了计算工作量(周期数)，同时提高了查询执行速度。
这种并行处理特别有利于在连接过程的探测阶段内实现加速的小探测动作，例如，探测由连接过程的构建阶段产生的小的行集合。
在一个示例中，小的行集合可以足够小，使得用于构建边行集合的位图过滤器可以适合计算机处理器的寄存器组，例如，单指令多数据(simd)寄存器组。
连接过程有构建阶段，随后是探测阶段。
图1a示出了本文描述的实施例具有特定应用的星形模式数据库db1。
数据库db1包括事实表10和三个维度表12、14、16，分别涉及日期、位置、名称。
如稍后更详细描述的，作为构建阶段的一部分，基于构建侧数据源并根据查询条件，生成过滤器和映射结构。
事实表10可以用作连接过程的探测阶段的一部分。
因此，事实表10可以被称为探测侧数据源。
在这样的探测阶段，询问探测侧数据源，以便使用探测侧数据源的行来探测在构建阶段生成的过滤器和映射结构。
应当理解，实施例适用于维度表12、14、16中的任何一个，并且因此图1b所示的数据结构一般被称为第一数据源100。
如图1b所示，第一数据源100具有多个条目140a-i，每个条目具有相应的标识符120a-i。
每个标识符120a-i识别其对应的条目，使得第一数据源100内的条目140a-i彼此不同。
例如，条目140a对应于标识符120a，“id1”，以及条目140b对应于标识符120b，“id2”。
id1不同于id2(以及第一数据源100的任何其他标识符)，因此将条目140a与第一数据源100的任何其他条目140b-i区分开来。
这对于第一数据源100的每个标识符120a-i是相同的。
每个标识符120a-i在第一数据源100中可以是唯一的。
在一个示例中，每个标识符120a-i可以是唯一的整数值。
整数值可以是单个整数。
每个标识符120a-i是相关条目140a-i的主键。
第一数据源100可以是描述性数据源，其中，每个条目140a-i定义其对应的标识符120a-i。
在图1b的示例中，维度表12涉及日期，并且条目140c包含日期“03/27/10”，其定义了标识符120c，id3。
参考图1c，接收与第一数据源100相关联的过滤器参数50，并形成对第一数据源100的查询的基础，以识别第一数据源100的具有对应于过滤器参数50的标识符120a-i的多个条目140a-i中的至少一个条目。
因此，第一数据源可以被视为构建侧数据源。
在图1c的示例中，过滤器参数50涉及周末。
随后，对应于周末的数据源100的条目被识别为具有对应于过滤器参数50的标识符。
数据源100的具有对应于过滤器参数50的标识符的条目被识别为条目140a-i的子集200(条目240a-d)。
查看数据源100，子集200包括具有对应于过滤器参数50的标识符120c，d，g，i(id3、id4、id7、id9)的条目240a-d。
条目240a具有标识符120c，并且包含日期“03/27/10”，该日期被定义为星期六，因此落在周末(参见图1b)，并且对应于与周末相关的过滤器参数50。
子集的识别在图1c中由每个标识符的双箭头和从过滤器参数50延伸的虚线的交互来表示。
在构建阶段，通过将第一数据源100的对应于过滤器参数50(标识符120c，d，g，i)的标识符120a-i映射到位图过滤器300中的位位置，来生成位图过滤器300。
位图过滤器的长度由多个位位置以及最小和最大位位置来定义，并且由对应于过滤器参数的标识符(即，子集200的标识符)来设置，这避免了位图过滤器具有不必要的长度。
最小标识符值是“id3”的3。
每个标识符120a-i具有数值，并且基于对应标识符120a-i的数值来识别位图300中的位置350a-g。
应当理解，通常，可以识别位图过滤器300中的多个位位置350a-g的零或多个位位置。
在该示例中，单个位位置350e被分配给标识符120g，这意味着条目240c的标识符id7被分配给位图300的位图位置350e。
在分配位位置350e之后，在分配的位位置350e处设置位(在图1c中由位图300的位位置350e处的填充块表示)。
在位位置350e处设置的位是将位值设置为二进制1。
上述识别、分配和位设置过程可以统称为第一过程。
对第一数据源100的子集200内的另一条目240a，b，d重复第一过程。
作为示例，可以针对条目240d的标识符120i重复第一过程。
为了生成与过滤器参数50相关联的完整位图过滤器300，对第一数据源100的子集200的所有条目重复第一过程，导致位图过滤器300具有分配给对应于第一数据源100的子集200内的条目(240a-d)的每个标识符120a-i的每个位位置350a-g的设置位，并且从而对应于过滤器参数50。
由每个相关标识符和相关联的位位置之间的一对一映射生成的位图过滤器(例如，位图过滤器300)本质上是确定性的，因此避免了冲突，从而减少了确定和评估散列冲突通常需要的计算工作。
图2是根据数据源100的子集200生成的位图过滤器300的示意图。
子集200的每个条目240a-d具有相关联的标识符220a-d，并且被映射到位图过滤器300中的位位置。
子集200的标识符220a-d对应于与条目240a-d相关联的第一数据源100内的标识符。
在这个示例中，id3映射到位位置350a，id4映射到位位置350b，id7映射到位位置350e，以及id9映射到位位置350g。
如上所述，使用对应于过滤器参数50的每个标识符(在该示例中:id3、id4、id7、id9)和位图过滤器300中的分配的位位置350a-g之间的一对一映射，来生成位图过滤器300。
一对一映射确保位图过滤器300的长度足以覆盖与对应于过滤器参数50的第一数据源100的条目子集200相关联的整数值，同时不会不必要地扩展。
作为示例，一对一映射导致对应于接收到的过滤器参数的标识符的最小整数值映射到位图的第一位位置、和对应于接收到的过滤器参数的标识符的最大整数值映射到位图的最后位位置。
参考图2，最小值标识符“id3”映射到位图过滤器300的第一位位置350a，以及最大值标识符“id9”映射到最后位位置350g。
对应于第一数据源100的与过滤器参数50对应的条目子集200的每个标识符120a-i的单个位位置350a-g的识别，可以通过将函数应用于标识符120a-i的数值来实现，使得函数的执行直接根据标识符220a-i的数值生成单个位位置350a-g。
虚线框说明了函数f在每个标识符上的直接应用。
例如，“f(id3)”表示函数f在标识符id3220a的数值“3”上的应用。
以这种方式直接使用数值取代了评估散列函数、比较散列输出以确保没有冲突、以及存储散列值的需求。
例如，可以从每个标识符220a-d的数值中减去子集200的条目240a-d的最小值标识符，然后通过添加数值1来归一化所得值，使得位位置在位图过滤器300的长度内。
因此，为了识别对应于标识符id4的单个位位置350a-g，该函数确定如下:4-3+1=2通过这种方式，id4映射到第二位位置，即位图过滤器300内的位位置350b。
当位图过滤器具有与位图过滤器300不同的格式时，也可以实现标识符值和位图过滤器的位位置之间的一对一映射。
通过这种方式，位图过滤器302和305不会不必要地长。
在对应于过滤器的条目的子集由单个条目组成的示例中，如前所述生成的位图过滤器的最小位和最大位将是在单个位位置的相同位。
图4a示出了存储为多个字节3030-3的位图过滤器302。
在本示例中，每个字节都与8位位置相关联。
例如，字节3030与位位置3040-7相关联，字节3031与位位置3048-15相关联，字节3032与位位置30416-23相关联，以及字节3033与位位置30424-31相关联。
在图4a的示例中，为了识别位图过滤器302的位位置并将其分配给数据源的标识符，可以使用函数，在执行该函数时，基于标识符的数值识别位图过滤器302的字节地址和所识别的字节内的位地址，其中，字节地址和位地址识别位图过滤器302内的单个位位置。
余数为2，因此识别字节3031内的位30410。
在图4a中，该位位置由“x”标记。
在另一示例中，对于位图过滤器302，应用于标识符值16的模函数将如下，其中，最小值标识符是1:商是1，所以识别字节3031。
在图4a中，该位位置由“y”标记。
在图4b所示的另一示例中，位图过滤器305可以被分成多个字3060-2，其中，每个字与多个位位置相关联。
在图4b的示例中，为了识别位图过滤器305的位位置并将该位位置分配给数据源的标识符，可以使用函数，在执行该函数时，基于标识符的数值来识别位图过滤器305的字和所识别的字内的位地址，其中，该字和位地址识别位图过滤器305内的单个位位置。
方法400开始于框410，在框410，接收过滤器参数50。
接下来，方法400前进到框420，在框420，查询与过滤器参数50相关联的第一数据源100，以识别第一数据源100中具有对应于过滤器参数50的标识符120a-i的至少一个条目240a-d。
在该查询之后，在框440，对该条目执行涉及识别、分配和位设置的第一过程。
在第一过程之后，在框450，对于第一数据源100中具有对应于过滤器参数50的标识符120a-i的另一条目240a，b，d，重复第一过程。
优选地，对所有这样的条目重复该过程。
参考图6并参考图1c，框440的第一过程开始于框442，其中，识别位图过滤器300中的多个位位置350a-g中的单个位位置350a-g，被识别为对应于与过滤器参数50对应的第一数据源100的条目240c的标识符120g。
如前所述，每个标识符120a-i具有数值，并且基于对应标识符120a-i的数值来识别位位置350a-g。
然后该方法前进到框444，其中，单个位位置350e被分配给标识符120g，使得在对应于过滤器参数50的每个标识符120a-i和位图过滤器300中的分配的位位置350a-g之间存在一对一映射。
在分配之后，在框446，分配的位位置350e处的位被设置。
过滤过程(探测阶段)图7是数据源500的示意图。
数据源500对应于图1中数据库db1的事实表10。
数据源500的每个标识符520a-r被称为唯一识别不同数据源的条目的外键，即，日期维度表12中的条目。
这样，数据源500可以在多个条目540a-r的不同条目中包含多于一个相同标识符520a-r。
例如，在该示例中，与条目540a相关联的标识符520a与和条目520e相关联的标识符520e相同;都是id5。
因为数据源500是事实表，所以多个条目540a-r中的每个条目还将包含由除维度表12之外的数据源定义的其他标识符。
在该示例中，数据源500还包含与维度表14相关联的标识符(通常称为i14)、和与维度表16相关联的多个标识符(通常称为i16)。
多个条目540a-r中的每个条目由多个标识符中的一个标识符来定义，通常称为i10。
因此，数据源500可以被视为探测侧数据源。
在另一示例中，数据源500可以是维度表。
在这个示例中，使用位图过滤器300过滤图7的数据源500。
为了便于参考，在图8中仅再现了数据源500的日期相关部分。
由位图过滤器300执行的过滤过程类似于生成位图过滤器300的过程，因为输入值(例如，标识符值)被转换为位图过滤器的单个位位置。
这种转换可以是函数应用到输入标识符值的数值上。
位图过滤器300被应用于数据源500，并将每个条目识别为与位图过滤器300匹配或不匹配。
将位图过滤器300应用于数据源500，可以是对多个条目540a-r的依次应用或并行应用。
下面参考图17至图19更详细地描述并行处理。
如上所述，位图过滤器300已经在位图过滤器300内的位位置处设置位，以滤掉不匹配项。
如果数据源500的待过滤的项(例如，标识符520a-r)被映射到具有位设置的位位置，则该待过滤的项被识别为匹配。
另一方面，如果待过滤的项被映射到没有位设置的位位置，则带过滤的项被识别为不匹配并被丢弃。
在该示例中，标识符520d被映射到具有位设置的位位置350a，因此条目540d被识别为匹配。
仔细观察过滤过程，首先通过对应于数据源500的条目540a-r的标识符520a-r的位图过滤器300中的多个位位置350a-g的单个位位置的识别，使用位图过滤器300过滤数据源500。
每个标识符520a-r具有数值，并且基于对应标识符520d的数值来识别位位置350a。
单个位位置350a被分配给标识符520d，使得在每个标识符520a-r和位图过滤器300中的分配的位位置350a-g之间存在一对一映射。
在分配之后，进行关于是否在分配的位位置350a处设置位的识别。
如果该位被设置，则输出数据源500的条目，以供进一步考虑。
然后对数据源500的另一条目540a-r重复过滤。
数据源500的标识符的数值的直接使用提供了不会因评估散列函数和散列输出而变慢的快速处理。
在另一示例中，位图过滤器300可以并行地应用于数据源500的所有条目或多个条目而应用于数据源500。
因此，如果位图被并行应用于所有条目，则不需要对数据源500的另一条目540a-r重复过滤，或者如果位图被应用于多个条目，则重复次数会减少。
图9是在数据源500的另一条目上使用位图过滤器300的示意图，具体而言，在参考图8讨论的条目540d之后的条目540e。
如上所述，如果待过滤的项被映射到没有位设置的位位置，则待过滤的项被识别为不匹配并被丢弃。
在这个示例中，标识符520e被映射到没有位设置的位位置350c，因此条目540e被识别为不匹配。
在参考图8和图9描述的过滤过程中，在前述过滤过程之前可以存在额外步骤，因此可以称为预过滤步骤。
额外步骤确定数据源500的条目540a-r的标识符520a-r的数值在位图过滤器300表示的标识符值的整数范围内。
即，预过滤步骤确定条目540a-r的标识符520a-r的数值在位图过滤器300覆盖的最小标识符值和最大标识符值的范围内。
如上面参考图1c所解释的，位图过滤器300的长度足以覆盖与对应于过滤器参数50的第一数据源100的条目的子集200相关联的标识符的整数值，同时不会不必要地扩展到与过滤过程无关的整数值。
这样，预过滤步骤确认位图过滤器300是否需要用于标识符。
如参考图2所述，基于标识符值id3、id4、id7和id9生成位图过滤器300。
这样，与具有id10的标识符520i相关联的条目540i在位图过滤器300的范围之外，因此可以被识别为不匹配，而无需继续过滤过程。
标识符520b、520k(id2)和520h、520n(id1)也是如此。
在一个示例中，可以生成表示数据源(例如，数据源500)的标识符是否存在于位图过滤器(例如，位图过滤器300)中的数组。
可以基于所讨论的标识符和位图过滤器内的相应字节地址之间的关系来生成这种数组。
更详细地，识别对应于数据源的整数标识符的位位置。
询问位图过滤器中对应于字节地址的字节，以确定是否在识别的位位置处设置位。
如果该位被设置，则数组中相应字节被设置为“1”，否则该字节被置为“0”。
图10是示出将条目540d输出到条目740a以供不同操作进一步处理的示意图。
进一步处理可以是使用关系代数操作符的处理。
这种进一步处理的一个示例可以是事实表条目540d和定义标识符id3的信息之间的连接操作符，在这个示例中，该连接操作符是存储在图1b的维度表12中的日期相关信息。
在连接操作符之后，其他操作符可以应用于连接操作的输出，例如，“分组”操作符、“排序”操作符和“限制”操作符。
连接操作符和后续操作符的应用被视为操作符树，其中，一个操作符的输出是下一个操作符的输入。
进一步处理的另一示例是多重连接操作，其中，事实表条目和第一维度表的条目之间的第一连接操作的结果馈入第一连接操作的结果和第二维度表的条目之间的第二连接操作。
如上所述，以这种方式操作符的应用可以看作是操作符树。
对应于数据源500的条目的标识符的单个位位置350a-g的识别，可以通过将函数应用于标识符520a-r的数值来实现，使得函数的执行直接根据标识符520a-r的数值生成单个位位置350a-g。
在生成位图过滤器300(图3、图4a和图4b)的上下文中描述的与映射相关的函数f，也适用于将数据源500的标识符映射到位图过滤器300的位位置。
如上面参考图4a和图4b所解释的，位图过滤器300可以具有多个字节，其中，位图过滤器300的位位置的子集与每个字节相关联。
在这种情况下，为了识别位位置并且将其分配给数据源500的标识符，可以使用函数，当执行该函数时，基于标识符的数值识别位图过滤器300的字节地址并识别所识别的字节内的位地址，其中，字节地址和位地址识别出单个位位置350a-g。
该方法进行到框820，其中，识别位图过滤器300中的多个位位置350a-g中的单个位位置350a，其对应于数据源500的条目540a-r的标识符520a-r。
在识别之后，该方法进行到框830，其中，单个位位置350a被分配给标识符520d，使得在每个标识符520a-r和位图过滤器300中的分配的位位置350a-g之间存在一对一映射。
在框840，该方法识别是否在分配的位位置350a处设置位。
在框850，如果该位被设置，则输出数据源500的条目。
在输出之后，在框860，对数据源500的另一条目540a-r重复过滤810。
在另一示例中，可以在输出数据源500的条目之前或同时进行重复过滤。
即，位图过滤器由数据源900探测。
数据源900对应于参考图7至图10描述的数据源500。
在图12的示例中，位图过滤器300在位位置350e处的设置位与数据源900的条目940g相关联，这样，条目940g的标识符920g与位图过滤器300匹配。
条目940g的匹配标识符920g与用于生成位图过滤器300的另一数据源的行相关联，更具体地，由该行定义。
在这个示例中，另一个数据源是第一数据源100(见图1b);与日期相关的维度表12。
数据源900的每个标识符都是外键。
数据源950是中间表。
在该示例中，数据源950包含标识符952a-d和定义每个标识符952a-d的相应日期信息953a-d。
如上所述，日期信息953a-d源自第一数据源100。
标识符952a-d对应于位图过滤器300内的位位置。
数据源950还包含每行的多个行标识符951a-d。
行标识符均对应于多个条目950a-d中的一个，并且具有数值。
基于标识符952a-d的数值对多个条目950a-d进行排序，并且对于每个条目，多个行标识符951a-d递增1。
在该示例中，多个条目950a-d基于标识符952a-d的数值以升序排序。
数据源950作为构建阶段的一部分，可能与位图过滤器300同时生成。
基于在与数据源900的条目相关联的设置位的位位置350e和位图过滤器中对应于不同的已知行标识符r1950a的位位置350a之间的位位置中设置的位数的总和，确定数据源950内对应于数据源900的匹配标识符的行位置。
在该示例中，总和是位位置350e处设置的位之前并包括该位的位数。
因此，位位置350a是对应于位图过滤器300中的最小位的位置。
在这个示例中，位位置350e和位位置350a之间设置的位数的总和是3(3)。
总和包括在位位置350e和350a处设置的位。
总和3(3)将另一数据源950的第三行950c识别为与标识符id7相关联。
行950c的识别便于对行950c的询问，这又允许输出来自数据源950的相关行950c的信息(示意性地显示为记录960)。
信息的输出可以是用于将不同数据源的匹配行拉在一起的连接过程的部分。
对应于过滤器参数的单个整数标识符与位图过滤器300内的单个位位置的一对一映射，使得能够直接查找到另一数据源的定义对应于过滤器的标识符的特定行。
以这种方式，使用简化的逻辑，无需散列函数评估、散列输出验证(以确保没有冲突)或者遍历多于一行来执行查找。
方法1000开始于框1100，其中，位图过滤器300的设置位与数据源900的条目940g相关联，其中，设置位位于位图过滤器300内的位位置350e。
该方法进行到框1200，其中，基于在与数据源的条目相关联的设置位的位位置350e和位图过滤器中对应于不同的已知行标识符的位位置350a之间的位位置中设置的位数的总和，来确定另一数据源950中的相关联的行950a-d的行位置，例如，行标识符951a-d。
在确定之后，在框1300，询问对应于所确定的行标识符951c的数据源950的相关联的行950c。
在询问之后，在框1400，输出来自数据源950的相关行950c的信息。
图14是在数据源970上使用扩展位图向量600的示意图。
扩展位图向量600包含位图过滤器650和多个计数器610a-c，并且提供了组织相关数据的实用方式，这减少了所需的内存量。
位图过滤器650被配置为实现数据源970的条目的标识符与位图过滤器650内的位位置的一对一映射。
至于图12，图14描述了探测阶段的实现，这可能是连接过程的一部分。
也可能已经生成多个计数器610a-c，作为构建阶段的一部分。
数据源970是与由数据源500和数据源900表示的事实表不同的事实表。
数据源970包含由另一数据源定义的多个标识符980a-r，例如，图1的维度表14(与位置相关)。
在该示例中，基于对应于与位置相关的过滤器参数的位置标识符，生成位图过滤器650。
因此，基于由多个标识符980a-r定义的位置，过滤数据源970。
多个计数器610a-c对位图过滤器650中设置的位进行计数。
位图过滤器650的每个位位置650a-1与多个计数器610a-c中的一个相关联，使得多个计数器610a-c与位图过滤器650交错。
在该示例中，位位置650a-d与计数器610a相关联，位位置650e-h与计数器610b相关联，以及位位置650i-1与计数器610c相关联。
对于(2)，扩展位向量600有效地将稀疏标识符转换成一组密集标识符。
在一个示例中，位图过滤器650的32位部分可以与32位预计算计数器交错。
数据源995具有与图12的示例的数据源950相同的功能，因为数据源995是包括对应于过滤器参数的多个条目995a-d的中间表。
数据源995可能在构建阶段与位图向量600同时生成。
另外，类似于数据源950，数据源995具有:1)多个条目995a-d，具有对应于位图过滤器650中的设置位的对应标识符998a-d，其中，每个条目包含定义对应标识符的信息;以及2)多个行标识符996a-d，每个对应于多个条目995a-d中的一个，多个条目995a-d以标识符998a-d的升序排序，并且对于每个条目，多个行标识符996a-d递增1。
在这个示例中，在识别数据源995的一行之后，该行中的信息可以输出到结果集999的行999a，作为连接操作的一部分。
如前所述，输出(例如，结果集999)可以使用关系代数操作符进行进一步处理。
每个计数器610a-c对位图过滤器650中在与计数器相关联的位位置之前的位位置中设置的位数进行计数，因此定义位图过滤器650中设置位的滚动计数。
每个计数器的计数添加到增量上，该增量表示在与计数器相关联的位位置中设置的位数，该位位置位于所讨论的设置位的位位置之前并包括所讨论的设置位的位位置。
图15是图14的扩展位图向量600的示意图。
位图过滤器650的第二部分652紧跟在第一部分651之后，并且包括所讨论的设置位，在这种情况下，设置位在位位置650f处。
位图过滤器650的每个部分与多个计数器610a-c中的一个相关联。
每个计数器定义位图650的所有前面部分中设置的位计数，并且因此可以被认为是累积计数。
计数器610b与设置位的位位置650f、以及位图过滤器650的第二部分652内的其他位位置相关联。
计数器610b定义位图过滤器650的第一部分651中设置的位计数，该第一部分651位于位图过滤器650的包含设置位的位位置650f的第二部分652之前。
计数器610c与包含设置位的位位置650j、以及位图650的第三部分653内的其他位位置相关联。
第一部分651包含一个设置位，第二部分包含两个设置位，因此计数器610c的计数为3。
图16是使用扩展位向量600的方法2000的流程图，扩展位向量600包括a)位图过滤器650，被配置为实现数据源的条目的标识符与位图过滤器650内的位位置的一对一映射，以及b)位图过滤器650中设置的位的多个计数器610a-c。
位图过滤器650的每个位位置650a-i与多个计数器610a-c中的一个相关联。
方法2000开始于框2100，其中，位图过滤器650的设置位与数据源970的条目990c相关联，其中，设置位位于位图过滤器650内的位位置650f。
在一个示例中，框2100的关联可以识别位图过滤器650中的多个位位置中的单个位位置650f，多个位位置对应于数据源970的条目的标识符980a-r，其中，每个标识符980a-r具有数值，并且基于对应标识符980a-r的数值来识别位位置650f。
在识别之后，单个位位置650f被分配给标识符980c，使得在每个标识符980a-r和位图过滤器650中分配的位位置之间存在一对一映射。
该方法进行到框2200，其中，基于与设置位的位位置650f相关联的计数器610b的计数，来确定另一数据源995中的相关行的行标识符996a-d。
计数器610b的计数是与数据源970的条目相关联的设置位的位位置650f和位图过滤器650中对应于不同的已知行标识符的位位置650a之间的位位置中的设置位的数量的总和。
在框2300，方法2000继续询问对应于所确定的行标识符996c的数据源995的相关行995c。
在询问之后，在框2400，输出来自数据源995的相关行995c的信息(由图14的记录999示出)。
如前所述，可以对数据源995的行995c应用进一步的处理，例如，额外关系代数操作符。
单指令多数据(simd)实现如上面简要提到的，根据参考图7至图19描述的方法的位图过滤器可以针对数据源的多个条目并行化。
具体地，过滤过程的并行处理可以使用单指令多数据(simd)处理来实现。
这种并行处理尤其有利于在连接过程的探测阶段内实现加速的小探测动作，例如，对于在构建侧具有一小组标识符的小探测。
在一个示例中，一小组标识符的大小可以使得用于标识符的位图过滤器能够适合计算机处理器的寄存器组，例如，simd寄存器细。
当确定扩展位图向量(例如，图14和图15的扩展位图向量600)的匹配标识符的行标识符时，也可以使用simd处理。
前述用于生成位图过滤器的算法的流线型性质以及随后使用位图过滤器的过滤，能够实现通过simd的细粒度并行化。
在(1)的检查和(2)的转换之后，可以在至少一行探测侧数据源和至少一行构建侧数据源之间(在对应的识别的行位置)执行连接过程。
图17是根据实施例的simd过滤过程的输出的示意图。
对每个寄存器的操作可以是应用于所讨论的寄存器内的多个数据、优选所有数据的simd指令。
在本公开的上下文中，“simd指令”可以指对寄存器内的相同数据部分进行操作的多个simd指令。
图17和图18中对每个寄存器的描述示出了加载到每个寄存器中的数据的逻辑配置。
位图过滤器可以从计算机存储器加载到计算机处理器的一个或多个寄存器中。
位图过滤器的大小确定从计算机存储器加载位图过滤器所需的寄存器数量。
如果位图过滤器的长度超过寄存器的长度，例如，位图可以是128位并且寄存器可以是64位，则需要多个寄存器来存储位图。
作为另一示例，位图过滤器可能需要32×256位寄存器。
在位图过滤器的大小需要多个寄存器的情况下，可能需要一个或多个额外步骤来识别多个寄存器中的哪个寄存器与simd实现相关。
下面将更详细地讨论额外步骤。
寄存器a(rega)是存储一部分位图过滤器670的计算机处理器的多个寄存器中的单个寄存器。
为了便于参考，图17描述了rega的16位部分。
至于位图过滤器300和位图过滤器650，位图过滤器670提供整数标识符值和位图过滤器670的单个位位置之间的一对一映射。
由于图17的示例使用基于零的编号系统，待过滤的标识符在regb1中由整数1、3、9和4表示，这些整数对应于位图过滤器670中表示的最小标识符值(对应于位图过滤器670的最小位位置)移位的每个标识符。
在图17的示例中，最小位位置对应于最小标识符值4(4):向regb1应用操作以创建要存储在寄存器b2(regb2)中的数据，作为输出。
在本示例中，对regb1应用逐个字节除法运算，将regb1的整数值除以8(8)。
除法运算为regb1的每个整数(位地址)输出一个字节地址。
在当前情况下:regb1的整数值操作regb2的字节地址1÷803÷809÷814÷80在另一示例中，应用于regb1的操作可以是以下中的一个:按位or操作、按位and操作和掩码操作。
regb2表示与regb1的标识符相对应的rega的位图过滤器的字节的字节地址。
通过基于regb2对rega应用操作，创建寄存器c(regc)的内容。
应用于rega的操作导致regc包含与regb2的识别的字节地址相对应的rega的数据版本。
寄存器d(regd)包含作为基于regb1的位地址应用于regc的操作的输出而产生的数据。
该操作产生表示位图过滤器670中是否存在regb1的标识符的regd。
regd为每个标识符值使用一个字节，其中，如果在位图过滤器670中不存在标识符(不匹配)，则该字节为“0”，以及如果在位图过滤器670中存在标识符(匹配)，则该字节为“1”。
基于regb1应用于regc的操作可以是以下中的一个或多个:查找操作、获取操作和成对操作，例如，成对掩码、成对移位或成对and。
如上所述，位图过滤器670被加载到多个寄存器中，并且rega是存储位图过滤器670的一部分的多个寄存器(未示出)中的单个寄存器。
在图17的示例中，rega被识别为与regb1的标识符相关的寄存器，并且regb1的标识符是8位标识符。
如上所述，b1的标识符可以是16位标识符，因此regb1对于每个标识符值具有两个字节。
在这种情况下，其中，位图过滤器的大小大于单个寄存器，位图过滤器被加载到多个寄存器中，并且实施两步过程，来识别位图过滤器内对应于16位标识符的位位置。
首先，每个16位标识符的高位字节识别多个寄存器中包含对应于该标识符的位的相关寄存器。
其次，每个16位标识符的低位字节确定对应于该标识符的位(如以上针对8位标识符所述)是否被设置。
图18是如何使用simd来确定扩展位图向量的匹配标识符的行位置的示意图。
图18的示例可以结合图17的示例来实现，使得过滤和行识别过程一起操作。
在这种情况下，使用包括可以被加载到多个寄存器中并且被配置为实现数据源的条目的16位标识符与位位置的一对一映射的位图过滤器的扩展位向量的计算机实现的方法包括:识别多个寄存器中的对应于数据源的条目的标识符的寄存器，其中，每个标识符具有数值，并且基于对应标识符的数值来识别寄存器;并且识别寄存器中多个位位置中对应于标识符的单个位位置，其中，基于标识符的数值来识别位位置。
在一个示例中，基于16位标识符的高位字节来识别寄存器，并且基于16位标识符的低位字节来识别标识符内的位位置。
图18的寄存器e(rege)是寄存器的表示，该寄存器存储rega(为了便于参考，在图18中再现)的位图过滤器670的部分中设置位的计数。
这样，rega和rege一起存储扩展位图向量675，类似于图14的扩展位图向量600。
计数器c2定义先前字节0中设置的数量的计数。
虽然没有示出regc，但是从前面可以理解，它用于在regd中生成数据。
为了在中间数据源中为regb1的匹配的标识符识别行位置(例如，行标识符)，基于regb2和rege向regd应用操作，以创建存储在另一寄存器(寄存器f)中的数据，该寄存器指示与regb2的识别字节相关联的计数器的计数。
在图18的示例中，regd指示(使用“1”)b1的标识符3与rege的位图过滤器匹配。
对regf应用操作，以创建存储在另一寄存器(regg)中的数据，其中，regg指示对应于与regf的计数相关的匹配标识符的行位置，即regb1的标识符3和9。
该操作将设置在由regb2指示的字节地址的字节中的位数添加到regf的计数中，该位数多达并且包括设置在由regb1指示的标识符的位地址的位。
因此，中间表的第二行包含与regb1的标识符3相关联的信息。
因此，中间表的第三行包含与regb1的标识符9相关联的信息。
图18的示例的操作如下:regf操作regg的行标识符0+222+13由regg引用的中间表是包含输入表(例如，类似图12的数据源900和图14的数据源970)的条目的表(例如，类似图12的950和图14的995)，这些条目与过滤器参数匹配，用于生成位图过滤器670。
由regg引用的中间表的列包含与过滤器参数匹配的标识符。
在这种情况下，标识符对应于regb1的标识符3和9(因为它们与regd指示的设置位相关)。
标识符基于数值进行排序，由regg引用的中间表的每一行都有行标识符。
在另一示例中，rege的设置位的计数器可以存储在与rega的位图过滤器相同的寄存器中。
在一个示例中，计数器可以是32位计数器，并且被插入在位图过滤器的32位部分之间，形成扩展位向量。
例如，simd寄存器组可以由加载位图过滤器的最多8个寄存器组成。
每个寄存器可以是256位寄存器。
例如，在图17和图18的示例中，rega可以是存储位图过滤器670的8个寄存器中的一个。
寄存器访问比存储器访问快得多，因此针对多达8个simd寄存器的每个寄存器重复图17和图18的simd实现，可以非常快速地处理多达8个simd寄存器中的数据。
如果位图过滤器的一部分与探测无关，则该部分可以忽略，例如，通过屏蔽该部分。
参考图17和图18描述的simd实现，可以由具有simd扩展和任何大小的simd寄存器的处理器来实现。
simd寄存器的示例包括:avx-2simd寄存器和avx-512寄存器。
在替代示例中，对应于图1至图16的实施例可以在没有simd扩展的情况下实施，例如，使用任何现代处理器，例如，intelxeon、amdopteron和arm。
图19是根据参考图17和图18描述的示例实现单指令多数据实现的方法3000的流程图。
参考图18所示的寄存器a和寄存器e的示例扩展位向量675来描述方法3000。
寄存器a和寄存器e包括:a)rega中的位图过滤器670(参考图17描述)以及b)rege中的位图过滤器670中设置的位的多个计数器c1至cn，其中，位图过滤器670的每个位位置与多个计数器c1至cn中的一个相关联。
方法3000开始于框3100，将位图过滤器670和多个计数器c1至cn分别存储在寄存器rega和rege中。
接下来，方法3000进行到框3200，其中，数据源的相应多个条目的多个标识符存储在第二寄存器regb1中，其中，多个标识符中每一个的整数值基于位图过滤器670定义的最小标识符值移位。
在框3200的存储步骤之后，方法3000继续到框3300，其中，第一单指令多数据指令simd指令被应用到第二寄存器regb1。
此后，方法3000前进到框3400，在框3400中，基于第一simd指令的应用，生成存储在第三寄存器regb2中的数据，其中，第三寄存器regb2包括对应于第二寄存器regb1的位图过滤器(670)的多个字节地址。
接下来，方法3000移动到框3500，其中，第二simd指令被应用到第一寄存器rega和第三寄存器regb2。
在框3500之后，方法3000继续到框3600，在框3600中，基于第二simd指令，生成存储在第四寄存器regc中的数据，其中，第四寄存器regc包括对应于regb2的字节地址的第一寄存器rega的版本。
在框3600之后，在框3700，第三simd指令被应用于第二寄存器regb1和第四寄存器regc。
接下来，在框3800，基于第三simd指令，生成存储在第五寄存器regd中的数据，其中，第五寄存器regd识别第二寄存器regb1的标识符是否与位图过滤器匹配(670)。
在框3700之后，在框3900，为与位图过滤器670匹配的每个标识符识别数据源中的行位置。
框3900的识别由框3910、3920、3920和3940组成。
在框3910，方法3000继续将第四simd指令应用到第三寄存器b2和第五寄存器regd。
方法3000进行到框3920，在框3920中，基于第四simd指令，生成存储在第六寄存器regf中的数据，其中，第六寄存器regf包括与regb2中指示的字节相关联的计数器的计数，该字节包含与位图过滤器匹配的标识符(670)，如regd中所示。
在该应用之后，在框3940，基于第五simd指令生成存储在第七寄存器regg中的数据，其中，第七寄存器regg包括与位图过滤器(670)匹配的每个标识符的行位置。
在一个示例中，方法3000可以包括输出步骤，其中，输出表示第五寄存器regd的数组。
在另一示例中，方法3000可以包括输出步骤，其中，输出表示第七寄存器regg的数组。
(1)的识别和(2)的确定可以是连接过程的探测阶段的一部分。
本申请中描述的示例提供了数据库查询执行逻辑，该逻辑生成位图过滤器，使用位图过滤器过滤一系列输入值，并使用减少的计算周期(例如，减少评估散列函数所花费的时间)来确定对应于匹配输入值的行标识符。
示例数据结构的设计逻辑和后续生成(例如，所描述的位图过滤器和扩展位图向量)允许数据结构存储在计算机的高速缓冲存储器中，并因此提供快速处理。
图20是配置有软件以执行本文描述的功能的示例性装置5000的示意图。
装置5000具有计算机可读介质5100和处理器5300。
计算机可读介质5100包含指令5200，当由处理器5300执行时，指令5200使得处理器5300执行以下一个或多个先前描述的方法，即方法400;方法800，方法1000;以及方法2000。
处理器5300可以是参考图17、图18和图19讨论的处理器类型，例如，(a)具有或不具有simd扩展的处理器，例如，intelxeon、amdopteron、arm等，以及(b)具有simd扩展的任何处理器，例如但不限于intelavx-2和avx-512指令集。
在前面描述中，出于解释的目的，阐述了某些示例的许多具体细节。
说明书中对“示例”或类似语言的引用意味着结合该示例描述的特定特征、结构或特性包括在至少一个示例中，但不一定包括在其他示例中。
上述示例应被理解为说明性的。
应当理解，关于任何一个示例所描述的任何特征可以单独使用，或者与所描述的其他特征结合使用，并且也可以与任何其他示例的一个或多个特征结合使用，或者与任何其他示例的任何组合结合使用。
此外，也可以采用上面没有描述的等同物和修改。