一种数据仓库中基于连接索引的查询优化方法

摘要

本发明涉及一种数据仓库中基于连接索引的查询优化方法，步骤为：创建基于维表代理键的事实表外键连接索引；创建连接索引更新策略；当维表上存在谓词条件时，通过连接索引直接访问维表记录后需要进行谓词判断，参照位图连接索引通过动态位图连接索引计算生成连接位图索引；当维表上的选择率很低时，维表位图进一步压缩以提高维表位图计算的cache层次；采用基于协处理器内存计算的参照位图连接索引计算方法，只使用数组和位图数据结构，计算简单的内存地址访问。本发明能有效提高位图索引的计算性能，并且能与GPU、Xeon PhiTM等高性能协处理器相结合，加速索引计算性能，可以广泛在数据仓库领域中应用。

说明书

技术领域

本发明涉及一种种数据仓库领域中的查询处理方法，特别是关于一种数据仓库中基于连接索引(join index)的查询优化方法。

背景技术

数据仓库是一种基于多维数据模型的复杂数据集，在基于数据库的OLAP(Relational OLAP，ROLAP)查询处理时需要将事实表和多个维表连接起来执行复杂的分析查询命令，连接操作的性能一直是分析型查询处理(OLAP)最重要的问题。连接索引是一种通过预连接创建两个或多个表记录之间连接关系的索引，连接索引中记录了不同表之间连接记录的地址关系。在查询处理时，通过连接索引可以直接获得两个表连接记录的地址完成连接操作，消除按照连接键值进行查找的连接操作代价。连接索引主要应用于分析型数据库中，用以优化代价较大的两表或多表之间的连接操作。位图连接索引(bitmap join index)是连接索引的扩展技术，它是面向两个表的连接关系创建的位图索引，数据仓库中通常使用位图连接索引优化维度表和事实表的连接操作性能。位图连接索引可以理解为在事实表上为与事实表连接的维表属性创建的位图索引，当查询的WHERE子句中包含该维表属性的谓词表达式时，通过位图连接索引可以快速返回满足事实表和维表连接条件以及谓词表达式的维表属性所对应的事实表的行。连接索引是数据仓库中提高事实表与维表间连接操作性能的重要技术，它的主要缺点是索引存储空间代价较大，当OLAP查询中涉及事实表与多个维表之间的连接操作，以及查询中涉及维表上的多个属性时，连接索引的存储空间代价随之增加，维表属性上取值数量的增加也导致在位图连接索引中位图计算代价的增长。当前数据仓库应用特点从多维查询向高维查询过渡，OLAP查询中包含越来越多的连接表和维表属性，且更新频率越来越高，传统的连接索引技术面临巨大的存储和索引维护代价。

发明内容

针对上述问题，本发明的目的是提供一种数据仓库中基于连接索引的查询优化方法，该方法适应于大内存、多核处理器平台上的内存列存储数据仓库的实时OLAP查询处理应用，能有效提高位图索引的计算性能，并且能与GPU、XeonPhi^TM等高性能协处理器相结合，加速索引计算性能。

为实现上述目的，本发明采取以下技术方案：一种数据仓库中基于连接索引的查询优化方法，其特征在于：所述查询优化方法包括以下步骤：1)创建基于维表代理键的事实表外键连接索引；2)创建连接索引更新策略：当维表中插入新记录时，自动为其分配新的代理键值；代理键不包含语义，记录的更新操作只修改语义属性值，不对代理键进行修改；数据仓库中被参照的表中记录的删除需要满足参照表中相应记录首先被删除的条件；3)当维表上存在谓词条件时，通过连接索引直接访问维表记录后需要进行谓词判断，参照位图连接索引通过动态位图连接索引计算生成连接位图索引，优化事实表扫描性能；4)在数据仓库中，当维表上的选择率很低时，维表位图进一步压缩以提高维表位图计算的cache层次；5)采用基于协处理器内存计算的参照位图连接索引计算方法，只使用数组和位图数据结构，计算简单的内存地址访问，能够在众核协处理器上完成计算过程。

所述步骤1)中，当维表采用列存储或定长记录的行存储时，维表代理键直接映射为维表记录的偏移地址，事实表外键列的值直接映射为维表记录偏移地址，实现基于连接索引的查询处理。

所述步骤1)中，创建连接索引包括以下几种策略：(1)当维表使用代理键作为主键时，事实表外键直接作为连接索引；(2)当维表主键不是代理键但能函数映射为代理键时，通过函数映射实现连接索引；(3)当维表主键是复合主键或不能函数映射为代理键的主键时，通过主-外键同步更新或增加代理键外键的方法创建连接索引；(4)事实表与维表之间，以及雪花模型中维表之间基于代理键参照引用的外键机制使外键作为连接索引使用，优化表间连接操作。

所述步骤2)中，当维表记录需要删除时，需要保证代理键的顺序性，采用两种更新策略：(1)设置一个删除向量D_Vec，存储删除的维表记录的代理键值，保留当前删除记录的存储空间；当插入新记录时，为新记录分配删除向量中的代理键值，将新插入的记录写入删除记录代理键对应的存储空间，填补删除记录留下的记录空洞；(2)通过记录交换实现记录删除：当维表记录删除后，将维表中最后一条记录置换到当前删除记录的位置，代理键更新为当前位置的代理键值，同时需要在事实表中将交换的维表记录对应的外键更新为置换后的代理键。

所述步骤3)中，参照位图连接索引的计算过程分为以下几个步骤：(1)根据查询谓词生成维表位图，将SQL命令分解为在各个维表上的选择子句，根据维表过滤条件创建维表位图，事实表外键按维表位图的大小和选择率优先执行与较小的、低选择率的维表位图上进行的参照位图连接索引计算；(2)通过事实表外键连接索引映射到维表位图，根据维表位图映射位置的取值生成连接位图，连接位图中满足维表查询条件的位置设置为1，否则置为0；(3)按照连接位图中1的位置访问下一个事实表外键对应的偏移地址，将其对应的值映射到下一个维表位图的位置，根据维表位图该位置的值更新连接位图对应的位置的取值；依次处理完各个事实表外键列后生成查询最终的连接位图，即连接位图通过事实表外键参照维表位图而动态生成。

所述步骤4)中，将原始维表位图中连续的512位映射为一个二级位图位，较小的二级位图比原始的维表位图具有更高的cache访问性能；二级位图机制对应低选择率查询，当查询选择率低于0.195％时能将大量的维表位图内存访问优化为对较小二级位图的cache访问。

所述步骤5)中，基于协处理器内存计算的参照位图连接索引计算方法包括以下步骤：(1)划分连接位图索引计算数据集：根据协处理器内存容量划分用于连接索引位图计算的数据集；(2)维表位图创建及复制：将查询改写为维表上的谓词操作并在相应的维表上创建维表位图，然后将维表位图通过PCI-E通道传输到协处理器内存；(3)连接位图索引计算：在协处理器上，对协处理器内存中的事实表外键列和从CPU内存复制的维表位图进行并行的连接索引位图计算，生成连接索引位图，标识事实表中满足查询谓词条件的记录偏移地址；(4)连接位图索引传输：当查询的选择率较高时，将连接索引位图直接传输给CPU，当查询的选择率很低时，将连接索引位图转换为压缩形式，即记录位图中1位置的向量，将较小的连接索引向量传输给CPU；当采用INT型向量时，当查询选择率低于3.125％时，向量存储的空间低于位图；(5)基于连接位图索引的查询处理：基于连接索引能实现一种“无连接”的查询处理，通过事实表外键向维属性列的直接地址映射访问完成查询处理任务，也能将连接位图索引作为事实表上的一种索引访问机制，为数据库查询处理引擎提供额外的索引访问功能。

所述步骤(1)中，划分连接位图索引计算数据集的最优方案为按照数据仓库中事实表外键的大小配置具有同等大小内存的协处理器；当协处理器内存小于事实表外键列大小时，采用水平分片或垂直分片的方式将数据仓库的一个水平分片的全部外键列或者访问频率较高的外键列存储于协处理器内存，完成对数据仓库子集或部分维度上的连接位图索引计算。

所述步骤(5)中，协处理器完成连接索引位图计算后将连接索引位图传回CPU，通过位图或向量对庞大的事实表进行索引访问。

本发明由于采取以上技术方案，其具有以下优点：1、本发明利用数据仓库通用的维表代理键(连续的自然序列，如1,2,3…)机制实现事实表外键与维表代理键的直接映射，将事实表外键转换为连接索引，减少连接索引额外的存储开销与维护代价。2、本发明通过参照位图索引方法实现动态位图连接索引，相对于位图连接索引，查询只需要根据维表谓词条件生成较小的、满足查询条件的维表位图，不需要为众多的维表属性值创建连接位图；事实表相应的外键映射到维表位图上，动态创建满足该维表连接条件的连接位图，消除了位图连接索引多个位图的计算。参照位图连接索引技术不需要预先创建较大的位图连接索引，在查询执行时动态地生成较小的维表位图，然后执行事实表外键与较小的维表位图上基于连接索引的动态位图计算，实时创建事实表与该维表的连接位图。3、本发明在数据仓库星形连接和维表属性取值较多时有较好的性能。相对而言，在传统的位图连接索引机制中，随着连接表数量的增加和维表属性取值的增加，连接索引的存储空间代价迅速增长，位图计算代价也随之增长。4、本发明采用的维表位图将维表上大量的维属性取值统一映射到唯一的维表位图，构建参照位图索引的性能只取决于维表的数量，与维属性取值的多少无关。5、本发明的连接索引计算过程只包含固定大小的事实表外键列和较小的维表位图，计算过程为简单的位图访问，输出为事实表连接位图，是一种数据量较小，输入、输出数据集较小，计算密集的负载，适合于通过GPU、Xeon Phi^TM等高性能协处理器进行连接索引计算加速，提高查询处理的整体性能。6、本发明通过外键地址映射优化技术消除连接索引的存储开销，通过维表位图引用实时计算连接位图，提高了位图索引的计算性能。本发明可以广泛在数据仓库领域中应用。

附图说明

图1是本发明中数据仓库存储模型上的连接索引机制；图1(A)是基于维表代理键的连接索引示意图；图1(B)是在非代理键表间建立连接索引的示意图；图1(C)是复杂数据仓库模型中通过代理键建立连接索引图的示意图；

图2是本发明中维表采用代理键时的更新机制示意图；图2(A)是基于删除代理键重用的维表更新机制，新插入的维表记录使用已经删除的维表代理键值；图2(B)是基于代理键转换的维表更新机制，通过维表中末尾的记录转换到删除记录的位置维持代理键的连续，代理键转换后需要将事实表中对应维记录的外键同步更新；

图3是本发明实施例中星形连接位图索引示意图；

图4是本发明中参照位图连接索引示意图；图4(A)是基于维表位图直接映射机制的参照位图索引示意图，事实表外键值直接映射到维表位图生成事实表连接位图，当位图稀疏时可以采用只存储位图中“1”值位置的压缩存储模式；图4(B)是基于直接映射的参照连接索引，适合于维表位图小于cache或者维表位图上选择率较高的应用场景；图4(C)是当维表位图稀疏时通过哈希表存储维表位图中“1”的位置值，通过事实表外键在哈希表上探测完成连接索引生成位图的计算；图4(D)是针对较大的维表上稀疏位图的参照位图连接索引，通过多级位图映射提高维表位图参照时的数据局部性；

图5是本发明实施例中基于协处理器执行框架示意图。

具体实施方式

下面结合附图和实施例对本发明进行详细的描述。

如图1所示，本发明提供一种数据仓库中基于连接索引的查询优化方法，该方法是基于数据仓库星形模型、雪花形模型上的连接索引优化处理方法，其包括以下步骤：

1)创建基于维表代理键的事实表外键连接索引。当维表采用列存储或定长记录的行存储时，维表代理键可以直接映射为维表记录的偏移地址，事实表外键列的值可以直接映射为维表记录偏移地址，实现基于连接索引的查询处理。

其中，创建连接索引包括以下几种策略：

(1)当维表使用代理键作为主键时，事实表外键可以直接作为连接索引。如图1(A)所示，在列存储或定长行存储的维表中代理键等价于维表记录的偏移地址，与维表相应的事实表外键值可以直接映射为维表记录偏移地址，实现事实表记录与维表记录的直接连接；

(2)当维表主键不是代理键但可以函数映射为代理键时，可以通过函数映射实现连接索引。如图1(A)所示，SSB(Star Schema Benchmark，简称SSB，星形模式基准)中的Date表主键d_datekey为日期格式的连续数据，Date表记录的偏移地址可以用当前日期与起始日期之间相差的天数来函数映射。在数据库系统中日期值表示为连续的整数，表示从公元前4712年1月1日起到公元9999年12月31日的天数序列，如图1(C)TPC-DS中date_dim表中主键值最小为2415022，表示日期维表的起始日期为1900-01-02，记录地址可以映射为当前记录日期键值与起始日期键值的差值，映射函数为f(key)＝key-key₀。

(3)当维表主键是复合主键或不可函数映射为代理键的主键时，可以通过主-外键同步更新或增加代理键外键的方法创建连接索引。如图1(B)所示，TPC-H中ORDER表的主键ORDERKEY不是代理键，LINEITEM表中的外键ORDERKEY不能用作连接索引。由于ORDER表的主键和LINEITEM表的外键具有相同的物理存储顺序，可以通过归并扫描方法将ORDER表的主键ORDERKEY更新为代理键，并同步更新LINEITEM表中的外键列ORDERKEY的值，使更新后的外键列ORDERKEY成为连接索引。PARTSUPP表的复合主键(PARTKEY,SUPPKEY)无法直接映射为记录地址，需要为PARTSUPP表额外创建一个代理键列SK_PS，然后在事实表中增加一个参照SK_PS的外键列FK_PS，将FK_PS用作LINEITEM表与PARTSUPP表之间的连接索引。

(4)数据仓库普遍使用代理键作为主键来简化主键表示、优化连接时键值计算代价和标识维表记录的多个版本，事实表与维表之间，以及雪花模型中维表之间基于代理键参照引用的外键机制使外键可以作为连接索引使用，优化表间连接操作。如图1(C)所示，复杂数据仓库模式中通过参照完整性约束关系建立了一个基于外键连接索引的有向图结构，记录可以通过外键连接索引直接或间接地访问其下级参照引用表中的记录，实现了数据库中基于连接索引的连接操作。

2)创建连接索引更新策略。外键连接索引机制需要满足维表代理键机制，当维表记录更新时需要保持代理键的连续性。当维表中插入新记录时，自动为其分配新的代理键值；代理键不包含语义，记录的更新操作只修改语义属性值，不对代理键进行修改；数据仓库中被参照的表中记录的删除需要满足参照表中相应记录首先被删除的条件，而数据仓库中的事实表数据通常是只读的，不支持记录删除操作，当数据仓库中过期的记录被移出时，通常不需要删除相应的维表记录。

当维表记录需要删除时，需要保证代理键的顺序性。如图2所示，本发明采用两种更新策略：

(1)设置一个删除向量D_Vec，存储删除的维表记录的代理键值，保留当前删除记录的存储空间。当插入新记录时，为新记录分配删除向量中的代理键值，将新插入的记录写入删除记录代理键对应的存储空间，填补删除记录留下的记录“空洞”。由于代理键不包含任何语义，删除记录的代理键及存储空间复用不影响查询处理结果，如图2(A)所示。

(2)通过记录置换实现记录删除。如图2(B)所示，当维表记录删除后，将维表中最后一条记录置换到当前删除记录的位置，代理键更新为当前位置的代理键值，同时需要在事实表(参照表)中将交换的维表记录对应的外键更新为交换后的代理键。

上述两种更新策略中，第一种更新策略是一种lazy-update方式，通过代理键的重新分配实现代理键的连续和存储空间的连续；第二种更新策略是一种eager-update方式，当维表中大量记录删除时及时地对维表记录进行重组，提高维表存储访问效率，但相应的事实表外键更新代价较大。

3)当维表上存在谓词条件时，通过连接索引直接访问维表记录后需要进行谓词判断，主-外键参照约束一对多的模式导致较大的冗余计算代价。参照位图连接索引通过动态位图连接索引计算生成连接位图索引，优化事实表扫描性能。如图3所示，参照位图连接索引的计算过程分为以下几个步骤：

(1)根据查询谓词生成维表位图。将SQL命令分解为在各个维表上的选择子句，根据维表过滤条件创建维表位图，事实表外键按维表位图的大小和选择率优先执行与较小的、低选择率的维表位图上进行的参照位图连接索引计算。

(2)通过事实表外键连接索引映射到维表位图，根据维表位图映射位置的取值生成连接位图，连接位图中满足维表查询条件的位置设置为1，否则置为0。

(3)按照连接位图中“1”的位置访问下一个事实表外键对应的偏移地址，将其对应的值映射到下一个维表位图的位置，根据维表位图该位置的值更新连接位图对应的位置的取值；依次处理完各个事实表外键列后生成查询最终的连接位图，即连接位图通过事实表外键参照维表位图而动态生成。

当维表位图小于cache size时，连接位图的创建约等于事实表外键扫描代价，维表位图参照计算在cache中完成。当前18核CPU(ProcessorE7-8890 v32.50 GHz))的LLC(Last Level Cache，最后一级共享cache)达到45MB，当维表位图小于LLC大小时连接位图的动态生成具有良好的cache性能，也就是说当前45MB的共享LLC架构支持维表的最大行数为45×8×10⁶＝3.6×10⁸行。当维表位图小于512(512KB L2 cache)×8×10³＝4×10⁶行时，维表位图参照计算发生在L2 cache中，当维表位图小于32(32KB L1 cache)×8×10³＝2.56×10⁵行时，维表位图参照计算发生在L1 cache中，维表位图越小，维表位图参照计算的cache性能越高。

4)如图4所示，在数据仓库中，OLAP查询在维表上的选择率通常较高，基于外键连接索引的维表位图直接内存地址访问具有较好的性能(如图4(A)所示)，当维表上的选择率很低时，维表位图可以进一步压缩以提高维表位图计算的cache层次，提高位图索引计算性能。

图4(B)是基于维表位图直接映射访问的参照位图连接索引的计算过程，每个外键连接索引直接将键值映射到对应的维表位图位置，根据位图值更新连接位图。当选择率非常低时，位图中有效的“1”的值的存储效率较低。当位图大小小于cache大小时，即使维表位图的选择率很低，维表位图参照引用位图计算也具有较高的性能。

图4(C)是将选择率很低的维表位图存储为哈希表结构，位图的位置作为哈希值。在当前内存数据库使用的典型的chained-bucket结构的哈希表中，需要额外的bucket及表示bucket指针的数据结构，增加了冗余数据存储代价，只有当原始维表位图的大小小于维表位图位置哈希表时，基于哈希表的维表位图参照引用才有较好的数据访问性能。但基于哈希表的维表位图访问相对于直接的维表位图访问需要较高的CPU cycle。

图4(D)是针对较大维表上的稀疏位图而采用的多级位图结构。在原始维表位图的基础上建立二级位图，将原始维表位图连续的m个位图的逻辑OR结果映射为一位，创建一个n位原始维表位图上的n/m位的二级位图。事实表外键与维表位图的参照引用操作分解为两个处理过程，首先由事实表外键在二级维表位图上通过参照引用创建连接位图，然后通过连接位图索引再次访问事实表外键，完成事实表外键与原始维表位图的参照引用计算。

在本发明中将原始维表位图中连续的512位映射为一个二级位图位，较小的二级位图比原始的维表位图具有更高的cache访问性能。内存访问的基本单位是cache line(64字节，512位)，二维位图中的一个“0”的值意味着其对应的原始维表位图中某段连续的512位全部取值为“0”，访问这些位对应的内存访问可以转换为访问cache中较小的二维位图，不需要与事实表外键进行参照引用计算，经过事实表外键在二级位图上的第一趟过滤，过滤掉了大量不必要的事实表外键参照引用计算。二维位图中的一个“1”的值意味着其对应的原始维表位图中某段连续的512位中至少有一个取值为“1”的位，在事实表外键列的第二趟参照引用计算中，每一个外键向维表位图映射访问完成最终的维表参照引用计算。

二级位图机制对应低选择率查询，当查询选择率低于0.195％(1/512)时能将大量的维表位图内存访问优化为对较小二级位图的cache访问。

5)采用基于协处理器内存计算的参照位图连接索引计算方法，只使用数组和位图数据结构，计算简单的内存地址访问，能够高效地在众核协处理器上完成计算过程。

当前的众核协处理器，如GPU、Phi、FPGA等，集成了大量的计算单元，具有优异的并行计算能力。协处理器通常配置有较大的设备内存(device memory)，但相对于内存仍然较小，协处理器通过PCI-E与CPU连接，内存与协处理器之间通过PCI-E通道数据传输的延迟较大。如图5所示，本发明采用的基于协处理器内存计算的参照位图连接索引计算方法包括以下步骤：

(1)划分连接位图索引计算数据集

根据协处理器内存容量划分用于连接索引位图计算的数据集。最优的方案是按照数据仓库中事实表外键的大小配置具有同等大小内存的协处理器，以保证连接位图索引计算能够实现完成在协处理器内存的高性能计算。当协处理器内存小于事实表外键列大小时，可以采用水平分片或垂直分片的方式将数据仓库的一个水平分片的全部外键列或者访问频率较高的外键列存储于协处理器内存，完成对数据仓库子集或部分维度上的连接位图索引计算。

(2)维表位图创建及复制

将查询改写为维表上的谓词操作并在相应的维表上创建维表位图，然后将维表位图通过PCI-E通道传输到协处理器内存。

(3)连接位图索引计算

在协处理器上，对协处理器内存中的事实表外键列和从CPU内存复制的维表位图进行并行的连接索引位图计算，生成连接索引位图，标识事实表中满足查询谓词条件的记录偏移地址。

(4)连接位图索引传输

当查询的选择率较高时，将连接索引位图直接传输给CPU，当查询的选择率很低时，将连接索引位图转换为压缩形式，即记录位图中“1”位置的向量，将较小的连接索引向量传输给CPU。当采用INT型向量时，当查询选择率低于3.125％(1/32)时，向量存储的空间低于位图。

(5)基于连接位图索引的查询处理

基于连接索引可以实现一种“无连接”的查询处理，通过事实表外键向维属性列的直接地址映射访问完成查询处理任务，也可以将连接位图索引作为事实表上的一种索引访问机制，为数据库查询处理引擎提供额外的索引访问功能。

协处理器完成连接索引位图计算后将连接索引位图传回CPU，通过位图或向量对庞大的事实表进行索引访问。OLAP查询通常在每个维上的选择率较高，但多维上的总选择率通常较低，连接位图索引访问能够消除大量无效事实表的访问代价，加速OLAP查询处理性能。

综上所述，在本发明中，以数据仓库的代理键为基础构建了外键的连接索引，在不增加额外的连接索引存储代价的同时将原始的外键列转换为连接索引，实现了在内存中外键与参照表记录的直接内存地址映射访问，消除了传统的连接操作代价，简化了查询实现算法。进一步地，根据OLAP查询中维表上的谓词操作生成维表位图，事实表外键通过内存地址映射访问维表位图，创建连接索引位图，提高事实表扫描效率。通过外键连接索引机制，以数组、位图、内存地址访问等简单的数据类型的计算实现了动态生成连接索引位图的过程，消除了传统位图连接索引中的索引存储、维护和索引计算代价。连接索引位图的计算过程包含固定的事实表外键列和维表位图，是一种简单但计算量较大的任务，适合于协处理器计算。本发明提出的连接索引位图计算技术可以由CPU完成，也可以将连接索引位图计算涉及的事实表外键列存储在协处理器内存，由协处理器完成连接索引位图的计算过程，协同CPU上的OLAP查询处理。

上述各实施例仅用于说明本发明，各个步骤都是可以有所变化的，在本发明技术方案的基础上，凡根据本发明原理对个别步骤进行的改进和等同变换，均不应排除在本发明的保护范围之外。