一种面向列存储数据库的索引构建方法及装置

1.本发明涉及一种数据库索引构建方法及装置，特别是一种面向列存储数据库的索引构建方法及装置。


背景技术：

2.列存储数据库是基于列存储模式的数据库系统，主要面向联机分析处理(olap，online analytical processing)。相对于传统的行存储数据库而言，列存储数据库以字段作为数据存储和数据处理的基本单元，避免了查询处理过程中对不相关数据的读取，极大的降低了所需处理的数据量，从而提升了查询语句的执行效率。因此，在olap应用中，列存储数据库的性能明显优于行存储数据库。区别于行存储数据库，列存储数据库含有物化操作，即在查询处理过程中需对涉及到的多个独立存储的字段按照行号进行重组，以使得输出的查询结果依旧是以元组的方式展现给用户。当前的列存储数据库系统主要有c-store、infobright、sybase和monetdb等。
3.索引是用于提升数据库查询速度的重要技术之一，常见的索引方法有b树索引、哈希索引和位图索引。这些索引方法已被广泛应用于行存储数据库，且已取得了良好的效果。然而，上述索引方法应用于列存储数据库时存在着以下问题：1)索引构建方法与物化操作相分离：列存储数据库以字段为单位进行存储，上述索引方法只是针对字段建立了索引，而非行存储数据库中针对元组建立索引，即忽略了列存储数据库的独有操作——物化，导致相关字段的多次重复读取，使得这些索引方法在列存储数据库中的使用，不仅没有提升查询速度，反而降低了查询速度；2)索引方法的选取由数据库管理员(dba，databaseadministrator)依据经验确定，不仅对dba经验的依赖性较强，而且耗时较长：对同一字段，不同的索引方法所带来的查询速度提升差异很大，如果选取的索引方法合适，则能够最大限度的提升查询速度，反之，则会降低查询速度，也就是说，dba的经验对索引方法的选取影响很大；同时，列存储数据库是面向olap的，涉及的字段数量庞大，仅依靠dba来选取索引方法，耗时很长。因此，如何快速、准确的构建适用于列存储数据库的索引，以使得b树索引、哈希索引和位图索引能够有效提升列存储数据库的查询速度，是数据库领域急需解决的重要问题之一。


技术实现要素：

4.发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种面向列存储数据库的索引构建方法及装置。
5.为了解决上述技术问题，本发明公开了一种面向列存储数据库的索引构建方法及装置。
6.一种面向列存储数据库的索引构建方法，包括以下步骤：
7.步骤1：提取列存储数据库元数据文件中的索引字段及其索引构建方法，生成训练数据集；
8.步骤2：提取训练数据集中索引字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性；
9.步骤3：采用c4.5决策树算法，生成用于索引方法分类的决策树模型；
10.步骤4：根据历史查询语句，生成字段物化单元；
11.步骤5：基于每个字段物化单元，提取高频字段及其特征属性；
12.步骤6：为每个高频字段选取最优的索引构建方法，并构建索引。
13.本发明步骤2包括如下步骤：
14.步骤2-1，提取与数据相关的特征属性，读取各索引字段所属数据库表中存储的数据信息，获取索引字段的基数、总行数以及字段排序情况；
15.步骤2-2，提取与查询语句相关的特征属性，具体方法包括：
16.查询语句中的运算符与索引方法的选择也息息相关，诸如范围查询运算符主要使用b树索引，点查询运算符主要使用哈希索引，逻辑查询运算符主要使用位图索引。因此，本发明将查询语句涉及到的运算符分为三类：范围查询运算符，主要包括各种比较运算符(“》”、“《”、“》＝”、“《＝”、“between and”)；点查询运算符，主要包括等值查询运算符(“＝”)；逻辑查询运算符，主要包括各种逻辑运算符(“and运算符”、“or运算符”、“not运算符”)。
17.相应的，与查询语句相关的特征属性也分为三类：范围查询应用频率f
cr
、点查询应用频率f
cp
、逻辑查询应用频率f
cl
，具体计算方式如下：
[0018][0019][0020][0021]
其中，c表示训练数据集中三元组所涉及的索引字段，n表示从查询日志中提取的历史查询语句的总个数；r＝{“》”,“《”,“》＝”,“《＝”,“betweenand”},表示由范围查询运算符组成的集合；p＝{“＝”}，表示由点查询运算符组成的集合；l＝{“and”,“or”,“not”}，表示由逻辑查询运算符组成的集合。
[0022]
本发明步骤3包括：采用c4.5算法构建用于索引方法分类的决策树模型，其中，内部节点对应特征属性，叶子节点对应索引构建方法。
[0023]
本发明步骤4包括：
[0024]
步骤4-1，读取列存储数据库的日志文件，从中提取历史查询语句,构成集合q，q＝{qi|1≤i≤n}，qi表示第i个历史查询语句，n表示集合q中的历史查询语句的个数；
[0025]
步骤4-2，遍历集合q，对每个qi(1≤i≤n)进行解析，获取对应的数据库表集合ti(1≤i≤n)及其查询条件字段集合si(1≤i≤n)。
[0026]
步骤4-3，根据si(1≤i≤n)，构造物化字典；
[0027]
步骤4-4，根据物化字典，构造字段物化单元。
[0028]
本发明步骤4-2中所述第i(1≤i≤n)个查询语句对应的数据库表集合ti(1≤i≤n)为：
[0029][0030]
其中，t
i,k
表示ti中的第k个数据库表，表示集合ti中数据库表的个数。
[0031]
步骤4-2中所述第i(1≤i≤n)个查询语句对应的查询条件字段集合si(1≤i≤n)为：
[0032][0033]
其中，s
i,k
表示qi中属于表t
i,k
的字段集合；
[0034][0035]mi,k
表示集合s
i,k
中的字段个数。
[0036]
本发明中步骤4-3包括：
[0037]
遍历所有的si，对每个si执行如下步骤：
[0038]
步骤4-3-1，构造字段组合，方法如下；
[0039]
遍历所有的将每个s
i,k
中的字段按照其在查询语句集合q中的出现次数从高到低进行排序形成字段组合现次数从高到低进行排序形成字段组合其中，和分别表示s
i,k
中出现次数最高和最低的字段，m
i,k
表示集合中的字段个数；
[0040]
步骤4-3-2，构造字段重组单元，方法如下：
[0041]
从中，按序选取至少两个字段组成一个字段重组单元；中的字段总个数为mk，对于共有个字段重组单元
[0042]
步骤4-3-3，将上述字段重组单元存入物化字典：将字段重组单元及其出现次数存入物化字典d中；若字段重组单元在d中首次出现，则将其出现次数默认设置为1；若该字段重组单元已存在d中，则将其出现次数加1。
[0043]
本发明步骤4-4中构造字段物化单元方法包括：
[0044]
从物化字典d中选取出现次数超过给定阈值δ的字段重组单元，对这些字段重组单元进行物化，即将字段重组单元中涉及到的字段按照行号进行重组，以使得查询结果依旧是以元组的方式展现给用户。其中，δ＝n/3，n为集合q中历史查询语句的个数。
[0045]
本发明中步骤5包括：
[0046]
步骤5-1，基于每个字段物化单元所涉及的字段，提取在历史查询语句中出现次数最高的字段，作为该字段物化单元的高频字段；由于字段物化单元中各字段已按照其在历史查询语句集合q中的出现次数从高到低进行排序，所以字段物化单元的第1个字段即为该单元的高频字段。
[0047]
步骤5-2，提取各个高频字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性，提取方式和步骤2相同。
[0048]
本发明中步骤6包括：
[0049]
步骤6-1，为高频字段选取最优的索引构建方法，根据步骤5提取的特征属性和步骤3所构建的决策树分类模型，为每个字段物化单元中的高频字段选取最优的索引构建方法；
[0050]
步骤6-2，构建索引，依照决策树模型所选取的索引构建方法为各高频字段构建索引。
[0051]
一种面向列存储数据库的索引构建装置，包括数据获取模块、查询语句解析模块、字段特征提取模块、决策树构建模块、字段物化模块和索引构建模块；
[0052]
其中，数据获取模块：用于从列存储数据库的相关文件中获取构建索引所需要的数据，包括从元数据文件中获取表结构信息、从表数据文件中获取表数据信息、从日志文件中获取历史查询语句。
[0053]
查询语句解析模块：用于解析日志文件中提取的历史查询语句，获取每条历史查询语句所包含的数据库表及字段，用以构建字段重组单元和获取各字段的与查询语句相关的特征属性。
[0054]
字段特征提取模块：用于提取字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性。
[0055]
决策树构建模块：用于构建索引方法分类的决策树模型。该模块首先从表结构信息中提取各数据库表中的索引字段及其索引构建方法，以此构建训练数据集。随后，根据训练数据集中各索引字段及其特征属性，采用c4.5算法构建决策树模型。
[0056]
字段物化模块：用于构建字段物化单元。该模块首先基于历史查询语句生成字段重组单元，并将各字段重组单元连同其出现次数存入物化字典中；随后对物化字典中超过给定阈值的字段重组单元进行物化，即将字段重组单元所涉及的字段按照行号进行重组，生成字段物化单元。
[0057]
索引构建模块：用于选取数据库表中各字段物化单元的高频字段，随后根据这些字段的特征属性和所构建的决策树模型选取最优的索引构建方法，并依此构建方法构建索引。
[0058]
有益效果：本发明在列存储数据库的索引构建过程中融入物化操作，使得b树索引、哈希索引和位图索引能够有效提升列存储数据库的查询速度；同时，本发明引入c4.5决策树模型，降低了列存储数据库中索引方法选取对dba经验的依赖，加快了索引构建过程。
附图说明
[0059]
下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。
[0060]
图1是本发明方法的总体运行流程示意图。
[0061]
图2是本发明实施例涉及的数据库中a表的逻辑存储结构和物理存储结构(列存储)示意图。
[0062]
图3是本发明实施例中所构建的决策树模型示意图。
[0063]
图4是本发明实施例中物化后的a表的物理存储示意图。
[0064]
图5是本发明的装置模块示意图。
具体实施方式
[0065]
本发明提出了一种面向列存储数据库的索引构建方法及装置，总体运行流程如图1所示。
[0066]
具体的说，一种面向列存储数据库的索引构建方法包括以下步骤：
[0067]
步骤1：提取列存储数据库元数据文件中的索引字段及其索引构建方法，生成训练数据集。
[0068]
读取列存储数据库的元数据文件，提取索引字段的相关信息，组成三元组(表名称、索引字段名称、索引构建方法)。其中，索引构建方法包括b树索引、哈希索引和位图索引。根据三元组，生成训练数据集。
[0069]
例如，某列存储数据库中共包含6个表，100个查询语句。6个表分别命名为a表，b表，c表，d表，e表，f表。a表的列存储示意图如图2所示，其余表类似，不再列出。从该数据库的元数据文件中提取索引字段的三元组信息，生成训练数据集，如表1所示。
[0070]
编号表名字段名称索引构建方法1aa1b树索引2aa2位图索引3aa3哈希索引
…………
19dd1哈希索引20dd2b树索引
[0071]
表1训练数据集
[0072]
步骤2：提取训练数据集中索引字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性。
[0073]
具体包括如下步骤：
[0074]
步骤2.1：提取与数据相关的特征属性
[0075]
读取字段所属数据库表中存储的数据信息，获取该字段的基数、总行数以及字段排序情况；
[0076]
步骤2.2：提取与查询语句相关的特征属性
[0077]
查询语句中的运算符与索引方法的选择也息息相关，诸如范围查询运算符主要使用b树索引，点查询运算符主要使用哈希索引，逻辑查询运算符主要使用位图索引。因此，本发明将查询语句涉及到的运算符分为以下三类：范围查询运算符，主要包括各种比较运算符(“》”、“《”、“》＝”、“《＝”、“between and”)；点查询运算符，主要包括等值查询运算符(“＝”)；逻辑查询运算符，主要包括各种逻辑运算符(“and运算符”、“or运算符”、“not运算符”)。
[0078]
相应的，与查询语句相关的特征属性也分为三类：范围查询应用频率f
cr
、点查询应用频率f
cp
、逻辑查询应用频率f
cl
，具体计算方式如下：
[0079][0080][0081][0082]
其中，c表示训练数据集中各三元组所涉及的索引字段，n表示从查询日志中提取的历史查询语句的总个数；r＝{“》”,“《”,“》＝”,“《＝”,“betweenand”},表示由范围查询运算符组成的集合；p＝{“＝”}，表示由点查询运算符组成的集合；l＝{“and”,“or”,“not”}，表示由逻辑查询运算符组成的集合。
[0083]
延续上例，提取训练数据集中各索引字段的特征属性，首先从数据库的表数据文件中获取与数据相关的特征属性，包括字段基数、总行数、是否排序，如表2所示；其次，从数据库的历史查询语句集合中获取与查询语句相关的特征属性，即通过统计分析所有历史查询语句中各字段应用于三种类型操作符的次数，计算得到各个索引字段的范围查询应用频率f
cr
、点查询应用频率f
cp
、逻辑查询应用频率f
cl
，如表3所示。
[0084] a1a2a3…
d1d2基数100029900
…
678864总行数100010001000
…
23002300是否排序ynn
…
ny
[0085]
表2索引字段的与数据相关的特征属性
[0086] a1a2a3…
d1d2f
cr
0.760.120.07
…
0.120.91f
cp
0.130.230.72
…
0.830.04f
cl
0.110.650.21
…
0.050.05
[0087]
表3索引字段的与查询语句相关的特征属性
[0088]
步骤3：采用c4.5决策树算法，生成用于索引方法分类的决策树模型
[0089]
根据步骤1获取的训练数据集和步骤2提取的索引字段的特征属性，采用c4.5决策树算法构建用于索引分类的决策树模型。
[0090]
相对于id3和cart决策树算法，c4.5算法的优势在于可以对连续值进行处理，而步骤2中提到的特征属性涉及连续值，因此c4.5更适合于构建用于索引分类的决策树。决策树的内部节点对应特征属性，叶子节点对应索引构建方法。延续上例，采用c4.5决策树算法，以步骤1生成的训练数据集及步骤2提取的特征属性作为输入构建用于索引分类的决策树模型，生成的决策树模型如图3所示。
[0091]
步骤4：根据历史查询语句，生成字段物化单元
[0092]
步骤4.1：读取列存储数据库的日志文件，从中提取所有的历史查询语句，构成集合q，q＝{qi|1≤i≤n}，qi表示第i个历史查询语句，n表示集合q中的历史查询语句的个数；
[0093]
步骤4.2：遍历集合q，对每个qi(1≤i≤n)进行解析，获取对应的数据库表集合ti(1≤i≤n)、查询条件字段集合si(1≤i≤n)。其中，t
i,k
表示ti中的第k个数据库表，表示集合ti中数据库表的个数；s
i,k
表示qi中属于表t
i,k
的字段集合。具体的，m
i,k
表示集合s
i,k
中的字段个数。
[0094]
步骤4.3：根据si(1≤i≤n)，构造物化字典。
[0095]
遍历所有的si，对每个si执行如下步骤：
[0096]
步骤4.3.1：构造字段组合
[0097]
遍历所有的将每个s
i,k
中的字段按照其在查询语句集合q中的出现次数从高到低进行排序形成字段组合现次数从高到低进行排序形成字段组合其中，和分别表示s
i,k
中出现次数最高和最低的字段，m
i,k
表示集合中的字段个数；
[0098]
步骤4.3.2：构造字段重组单元
[0099]
从中，按序选取至少两个字段组成一个字段重组单元。由于中的字段总个数为mk，所以对于共有个字段重组单元
[0100]
步骤4.3.3：将上述字段重组单元存入物化字典
[0101]
将字段重组单元及其出现次数存入物化字典d中。若字段重组单元在d中首次出现，则将其出现次数默认设置为1；若该字段重组单元已存在d中，则将其出现次数加1。
[0102]
延续上例，提取查询日志中的所有历史查询语句构成集合q＝{qi|1≤i≤1000}。q中共有1000个历史查询语句，下面给出基于q1生成字段物化单元的具体过程，基于q＝{qi|2≤i≤1000}生成字段物化单元的过程类似，不再列出。
[0103]
q1：selecta.a1,a.a2,b.b1,b.b2
[0104]
froma，b
[0105]
where l1《a.a3《h
1 and l2《a.a6《h
2 and l3《a.a7《h3[0106]
l4《b.b4《h
4 and l5《b.b5《h
5 and l6《b.b8《h6[0107]
首先，对q1进行解析，获取数据库表集合t1和查询条件字段集合s1，其中，t1＝{t
1,1
＝a,t
1,2
＝b}，s1＝{s
1,1
＝{a3,a6,a7},s
1,2
＝{b4,b5,b8}}；
[0108]
其次，对s
1,1
和s
1,2
中的各字段按照其在历史查询语句集合q中的出现次数进行排序，生成字段组合和其中，
[0109]
然后，根据和分别生成字段重组单元集合，如下所示：
[0110][0111][0112]
最后，将上述字段重组单元及其出现次数存入物化字典d中。由于q1为第一个历史
查询语句，则上述所有单元的出现次数初始为1；对于后续的各历史查询语句，若字段重组单元在d中首次出现，则将其出现次数默认设置为1；若该字段重组单元已存在d中，则将其出现次数加1。
[0113]
步骤4.4：根据物化字典，构造字段物化单元。
[0114]
从物化字典d中选取出现次数超过给定阈值δ的字段重组单元，对这些字段重组单元进行物化，即将字段重组单元中涉及到的字段按照行号进行重组，以使得查询结果依旧是以元组的方式展现给用户。其中，，δ＝n/3，n为集合q中历史查询语句的个数。
[0115]
延续上例，通过对历史查询语句的分析，得到每个表的字段物化单元，图4所示为依据本例的历史查询语句所得到的物化后的a表的物理存储示意图，本实例中设定，δ＝n/3≈333，既选取d中出现次数超过333的字段重组单元进行物化，其余数据库表的物化存储结构类似。
[0116]
步骤5：基于每个字段物化单元，提取高频字段及其特征属性，具体步骤如下：
[0117]
步骤5.1：基于每个字段物化单元所涉及的字段，提取在历史查询语句中出现次数最高的字段，作为该字段物化单元的高频字段；由于字段物化单元中各字段已按照其在历史查询语句集合q中的出现次数从高到低进行排序，所以字段物化单元的第1个字段即为该单元的高频字段。
[0118]
步骤5.2：提取各个高频字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性，提取方式和步骤2相同。
[0119]
延续上例，为数据库表中的字段物化单元提取高频字段，并依照步骤2为这些字段提取特征属性。表4为高频字段的与数据相关的特征属性，表5为高频字段的与查询语句相关的特征属性。
[0120][0121][0122]
表4高频字段的与数据相关的特征属性
[0123] a8a9…a14fcr
0.650.15
…
0.21f
cp
0.230.72
…
0.11f
cl
0.120.13
…
0.68
[0124]
表5高频字段的与查询语句相关的特征属性
[0125]
步骤6：为每个高频字段选取最优的索引构建方法，并构建索引
[0126]
步骤6.1：为每个高频字段选取最优的索引构建方法。根据步骤5提取的特征属性和步骤3所构建的决策树分类模型，为每个字段物化单元中的高频字段选取最优的索引构建方法。
[0127]
步骤6.2：构建索引，依照决策树模型所选取的索引构建方法为各高频字段构建索
引。
[0128]
延续上例，依据图4所构建的决策树模型，为各个字段物化单元中的高频字段选取最优的索引构建方法，并依此方法构建索引，表6所示为数据库a表的字段物化单元中各高频字段的索引构建方法，其余表格类似，不再列出。
[0129] a8a9…a14
索引构建方法b树索引哈希索引
…
位图索引
[0130]
表6高频字段的索引构建方法
[0131]
本发明还提供一种面向列存储数据库的索引构建装置，如图5所示，该装置包括：
[0132]
数据获取模块：从列存储数据库的相关文件中获取构建索引所需的数据，包括从元数据文件中获取表结构信息、从表数据文件中获取表数据信息、从日志文件中获取历史查询语句。
[0133]
查询语句解析模块：解析日志文件中提取的历史查询语句，获取每条历史查询语句所包含的数据库表及字段，用以构建字段重组单元和获取各字段的与查询语句相关的特征属性。
[0134]
字段特征提取模块：提取字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性。
[0135]
决策树构建模块：构建用于索引方法分类的决策树模型。该模块首先从表结构信息中提取各数据库表中的索引字段及其索引构建方法，以此构建训练数据集。随后，根据训练数据集中各索引字段及其特征属性，采用c4.5算法构建决策树模型。
[0136]
字段物化模块：构建字段物化单元。该模块首先基于历史查询语句生成字段重组单元，并将各字段重组单元连同其出现次数存入物化字典中；随后对物化字典中超过给定阈值的字段重组单元进行物化，即将字段重组单元所涉及的字段按照行号进行重组，生成字段物化单元。
[0137]
索引构建模块：选取数据库表中各字段物化单元的高频字段，随后根据这些字段的特征属性和所构建的决策树模型选取最优的索引构建方法，并依此构建方法构建索引。
[0138]
进一步的，数据获取模块包括表结构信息获取子模块、表数据信息获取子模块、历史查询语句获取子模块。
[0139]
表结构信息获取子模块，用于从列存储数据库的元数据文件中获取数据库的表结构及其相关字段信息，对每个数据库表而言，具体包括所属数据库的名称、表名称、所涉及的所有字段；对表中的各个字段，进一步包括该字段是否为主键、是否构建索引和索引构建方法等。
[0140]
表数据信息获取子模块，用于从列存储数据库的表数据文件中获取各字段的相关数据信息。对每个字段而言，具体包括该字段所属数据库的名称、表名称、字段名称、该字段中数据的总行数、该字段中数据的基数、该字段是否排序等。
[0141]
历史查询语句获取子模块，用于从列存储数据库的日志文件中获取历史查询语句。
[0142]
进一步的，字段特征提取模块包括与数据相关的特征属性提取子模块和与查询语句相关的特征属性提取子模块。
[0143]
其中，与数据相关的特征属性提取子模块，用于为字段提取与数据相关的特征属
性，这些特征属性从该字段所属的表数据信息中提取，包括该字段中数据的总行数、该字段中数据的基数以及字段是否排序。
[0144]
与查询语句相关的特征属性提取子模块，用于为字段提取与查询语句相关的特征属性，包括范围查询应用频率、点查询应用频率、逻辑查询应用频率，这些特征属性通过对历史查询语句的统计分析得到。
[0145]
进一步的，决策树构建模块包括训练数据集构造子模块和决策树构建子模块。
[0146]
其中，训练数据集构造子模块，用于从表结构信息中提取各个表中索引字段的相关信息，组成三元组(表名称、索引字段名称、索引构建方法)，其中，索引构建方法包括b树索引、哈希索引和位图索引。根据三元组，生成训练数据集。
[0147]
决策树构建子模块，以训练数据集子模块生成的训练数据集为输入，采用c4.5决策树算法构建用于索引方法分类的决策树模型。其中，训练数据集中索引字段的特征属性通过字段特征提取模块进行提取。
[0148]
进一步的，字段物化模块包括字段重组单元构建子模块、物化字典构建子模块和字段物化单元构建子模块。
[0149]
字段重组单元构建子模块，基于各个历史查询语句出现的属于同一个数据库表的查询条件字段集合，构建字段重组单元。
[0150]
物化字典构建子模块，将各个字段重组单元连同其出现次数存入物化字典中。若字段重组单元在物化字典中首次出现，则将其出现次数默认设置为1；若该字段重组单元已存在物化字典中，则将其出现次数加1。
[0151]
字段物化单元构建子模块，用于构建字段物化单元，也就是对于物化字典中出现频率超过给定阈值的字段重组单元进行物化，即将字段重组单元所涉及的字段按照行号进行重组。
[0152]
进一步的，索引构建模块包括高频字段提取子模块和索引构建子模块。
[0153]
高频字段提取子模块，用于为每个字段物化单元提取高频字段。由于字段物化单元中的字段已按照其在历史查询语句中的出现次数从高到低进行排序，所以选取各个字段物化单元中的第1个字段作为高频字段。
[0154]
索引构建子模块，用于为高频字段选取最优的索引构建方法，并构建索引。高频字段的特征属性通过字段特征提取模块获得；随后，将这些特征属性作为决策树模型的输入，决策树的输出即为所选取的最优索引构建方法，按照此方法为高频字段构建索引。
[0155]
本发明提供了一种面向列存储数据库的索引构建方法及装置的思路及方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。

技术特征：
1.一种面向列存储数据库的索引构建方法，其特征在于，包括以下步骤：步骤1：提取列存储数据库元数据文件中的索引字段及其索引构建方法，生成训练数据集；步骤2：提取训练数据集中索引字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性；步骤3：采用c4.5决策树算法，生成用于索引方法分类的决策树模型；步骤4：根据历史查询语句，生成字段物化单元；步骤5：基于每个字段物化单元，提取高频字段及其特征属性；步骤6：为每个高频字段选取最优的索引构建方法，并构建索引。2.根据权利要求1所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤2包括如下步骤：步骤2-1，提取与数据相关的特征属性，读取各索引字段所属数据库表中存储的数据信息，获取索引字段的基数、总行数以及字段排序情况；步骤2-2，提取与查询语句相关的特征属性，具体方法包括：将查询语句涉及到的运算符分为以下三类：范围查询运算符，包括比较运算符；点查询运算符，包括等值查询运算符；逻辑查询运算符，包括逻辑运算符；将与查询语句相关的特征属性也分为三类：范围查询应用频率f
cr
、点查询应用频率f
cp
、逻辑查询应用频率f
cl
，具体计算方式如下：，具体计算方式如下：，具体计算方式如下：其中，c表示训练数据集中三元组所涉及的索引字段，n表示从查询日志中提取的历史查询语句的总个数；r＝{“>”,“<”,“>＝”,“<＝”,“betweenand”},表示由范围查询运算符组成的集合；p＝{“＝”}，表示由点查询运算符组成的集合；l＝{“and”,“or”,“not”}，表示由逻辑查询运算符组成的集合。3.根据权利要求2所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤3包括：采用c4.5算法构建用于索引分类的决策树模型，其中，内部节点对应特征属性，叶子节点对应索引构建方法。4.根据权利要求3所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤4包括：
步骤4-1，读取列存储数据库的日志文件，从中提取历史查询语句,构成集合q，q＝{q
i
|1≤i≤n}，q
i
表示第i个历史查询语句，n表示集合q中的历史查询语句的个数；步骤4-2，遍历集合q，对每个q
i
(1≤i≤n)进行解析，获取对应的数据库表集合t
i
(1≤i≤n)、查询条件字段集合s
i
(1≤i≤n)；步骤4-3，根据s
i
(1≤i≤n)，构造物化字典；步骤4-4，根据物化字典，构造字段物化单元。5.根据权利要求4所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤4-2中所述第i(1≤i≤n)个查询语句对应的数据库表集合t
i
(1≤i≤n)为：其中，t
i,k
表示t
i
中的第k个数据库表，表示集合t
i
中数据库表的个数；步骤4-2中所述第i(1≤i≤n)个查询语句对应的查询条件字段集合s
i
(1≤i≤n)为：其中，s
i,k
表示q
i
中属于表t
i,k
的字段集合；m
i,k
表示集合s
i,k
中的字段个数。6.根据权利要求5所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤4-3包括：遍历所有的s
i
，对每个s
i
执行如下步骤：步骤4-3-1，构造字段组合，方法如下；遍历所有的将每个s
i,k
中的字段按照其在查询语句集合q中的出现次数从高到低进行排序形成字段组合从高到低进行排序形成字段组合其中，和分别表示s
i,k
中出现次数最高和最低的字段，m
i,k
表示集合中的字段个数；步骤4-3-2，构造字段重组单元，方法如下：从中，按序选取至少两个字段组成一个字段重组单元；中的字段总个数为m
k
，对于共有个字段重组单元步骤4-3-3，将上述字段重组单元存入物化字典：将字段重组单元及其出现次数存入物化字典d中；若字段重组单元在d中首次出现，则将其出现次数默认设置为1；若该字段重组单元已存在d中，则将其出现次数加1。7.根据权利要求6所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤4-4中构造字段物化单元方法包括：从物化字典d中选取出现次数超过给定阈值δ的字段重组单元，对这些字段重组单元进行物化，即将字段重组单元中涉及到的字段按照行号进行重组，以使得查询结果依旧是以元组的方式展现给用户；其中，δ＝n/3，n为集合q中历史查询语句的个数。8.根据权利要求7所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤5包括：
步骤5-1，基于每个字段物化单元所涉及的字段，提取在历史查询语句中出现次数最高的字段，作为该字段物化单元的高频字段；由于字段物化单元中各字段已按照其在历史查询语句集合q中的出现次数从高到低进行排序，所以字段物化单元的第1个字段即为该单元的高频字段；步骤5-2，提取各个高频字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性，提取方式和步骤2相同。9.根据权利要求8所述的一种面向列存储数据库的索引构建方法，其特征在于，步骤6包括：步骤6-1，为高频字段选取最优的索引构建方法，根据步骤5提取的特征属性和步骤3所构建的决策树分类模型，为每个字段物化单元中的高频字段选取最优的索引构建方法；步骤6-2，构建索引，依照决策树模型所选取的索引构建方法为各高频字段构建索引。10.一种面向列存储数据库的索引构建装置，其特征在于，包括数据获取模块、查询语句解析模块、字段特征提取模块、决策树构建模块、字段物化模块和索引构建模块；其中，数据获取模块：用于从列存储数据库的相关文件中获取构建索引所需要的数据，包括从元数据文件中获取表结构信息、从表数据文件中获取表数据信息、从日志文件中获取历史查询语句；查询语句解析模块：用于解析日志文件中提取的历史查询语句，获取每条历史查询语句所包含的数据库表及字段，用以构建字段重组单元和获取各字段的与查询语句相关的特征属性；字段特征提取模块：用于提取字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性；决策树构建模块：用于构建索引方法分类的决策树模型；该模块首先从表结构信息中提取各数据库表中的索引字段及其索引构建方法，以此构建训练数据集；随后，根据训练数据集中各索引字段及其特征属性，采用c4.5算法构建决策树模型；字段物化模块：用于构建字段物化单元；该模块首先基于历史查询语句生成字段重组单元，并将各字段重组单元连同其出现次数存入物化字典中；随后对物化字典中超过给定阈值的字段重组单元进行物化，即将字段重组单元所涉及的字段按照行号进行重组，生成字段物化单元；索引构建模块：用于选取数据库表中各字段物化单元的高频字段，随后根据这些字段的特征属性和所构建的决策树模型选取最优的索引构建方法，并依此构建方法构建索引。

技术总结
本发明公开了一种面向列存储数据库的索引构建方法及装置，涉及数据库技术领域，方法包括：提取列存储数据库元数据文件中的索引字段及其索引构建方法，生成训练数据集；提取训练数据集中索引字段的特征属性，包括与数据相关的特征属性和与查询语句相关的特征属性；采用C4.5决策树算法，生成用于索引方法分类的决策树模型；根据历史查询语句，生成字段物化单元；基于每个字段物化单元，提取高频字段及其特征属性；为每个高频字段选取最优的索引构建方法，并构建索引。装置包括：数据获取模块、查询语句解析模块、字段特征提取模块、决策树构建模块、字段物化模块和索引构建模块。字段物化模块和索引构建模块。字段物化模块和索引构建模块。


技术研发人员：刘慧 郭婧 罗扬
受保护的技术使用者：金陵科技学院
技术研发日：2022.02.08
技术公布日：2022/5/25