一种Gaia系统中的多表连接优化方法

1.一种Gaia系统中的多表连接优化方法，其特征在于，包括以下步骤：S1：获取原连接树的属性信息，其中，所述属性信息包括原连接树包含的源表的数量以及中间表的数量、每个源表中各列的属性码、每个中间表中各列的属性码、原连接树的健值、原连接树的输出表、输出表各列的属性码，其中，健值为用户指定的属性码，则两个源表之间、源表与中间表之间按照健值进行等值连接，且不同源表之间、不同源表与中间表之间采用的健值不完全相同，并将源表的数量记为M，中间表的数量记为N，且N＝M-2；S2：根据原连接树的属性信息为每个健值构建索引条目，其中，每个索引条目至少包括两个索引位，第一个索引位用于存储健值，其余索引位用于存储列号，且每个索引条目存储的列号的确定方法为：分别将各健值作为当前健值执行以下步骤：S21：确定包含当前健值的源表；S22：从步骤S21确定的各源表中获取当前健值所在列的列号，并将得到的列号作为存储的列号；S3：对各源表进行编号，并根据各源表编号构建编号列表，其中，编号列表包括M列，每一列存储一个源表的编号；S4：分别将各索引条目作为当前索引条目执行有向连接操作，建立编号列表与各索引条目之间的有向连接，得到有向索引图，所述有向连接操作为：将当前索引条目中用于存储列号的各索引位分别作为当前索引位执行以下步骤：确定当前索引位存储的列号对应的源表，并将其记为当前源表；判断当前源表是否已与其他索引条目建立有向连接关系，若为否，则建立从当前源表编号的所在列到当前索引位的直接有向连接；若为是，则建立从当前源表编号的所在列到当前索引位的间接有向连接，其中，间接有向连接的建立方法为：获取已与当前源表建立有向连接关系的所有索引位，并将所有索引位均记为中间索引位，其中，有向连接关系包括直接有向连接和间接有向连接；在各中间索引位中获取最后与当前源表建立有向连接关系的索引位，并将该索引位作为末尾索引位；建立从末尾索引位到当前索引位的有向连接，实现从当前源表编号的所在列到当前索引位的间接有向连接；S5：基于有向索引图，采用动态规划法得到各源表的连接关系表达式，根据连接关系表达式重新构建连接树，完成多表连接的优化。 2.如权利要求1所述的一种Gaia系统中的多表连接优化方法，其特征在于，所述采用动态规划法得到各源表的连接关系表达式具体包括以下步骤：S51：分别将各源表作为当前源表执行以下步骤，得到各源表对应的一阶配对表、与一阶配对表进行等值连接而生成的一阶中间表：从有向索引图中获取与当前源表享有相同健值的所有源表，并将其记为一阶备选源表；分别获取当前源表与各一阶备选源表的等值连接代价，将最小等值连接代价对应的一阶备选源表作为与当前源表进行等值连接的一阶配对表；将当前源表与一阶配对表进行等值连接，得到一阶中间表，并将该等值连接关系记为一阶表达式；S52：分别将各源表作为当前源表执行连接更新操作，以得到各源表对应的等值连接代价最小的连接方式，其中，所述连接更新操作具体为：在除当前源表以外的其他源表于步骤S51得到的一阶中间表中，获取与当前源表享有相同健值的所有一阶中间表，并将其记为一阶备选中间表；在除当前源表和一阶配对表以外的其他源表中，获取与当前源表在步骤S51得到的一阶中间表享有相同健值的所有源表，并将其记为二阶备选源表；分别获取当前源表与各一阶备选中间表的等值连接代价、当前源表在步骤S51得到的一阶中间表与各二阶备选源表的等值连接代价，将最小等值连接代价对应的一阶备选中间表或二阶备选源表作为与当前源表进行等值连接的二阶配对表，并将该等值连接关系记为二阶表达式；S53：以此类推，分别将各源表作为当前源表，在其他源表于上一次连接更新操作得到的中间表中找出与当前源表享有相同健值的中间表，然后获取找出的中间表与当前源表的等值连接代价；同时，在除当前源表和已与当前源表建立等值连接关系的源表以外的其他源表中，找出与当前源表在上一次连接更新操作得到的中间表享有相同健值的源表，然后获取找出的源表与当前源表于上一次连接更新操作得到的中间表的等值连接代价；最后获取本步骤得到的最小值等值连接代价对应的表达式，直到获取各源表的连接关系表达式。 3.如权利要求2所述的一种Gaia系统中的多表连接优化方法，其特征在于，将需要计算等值连接代价的两个表中行数较少的记为I 0 ，另一个记为I 1 ；所述等值连接代价的代价函数Cost的计算公式为：Cost＝w 0 ×Cost ship +w 1 ×Cost cpu +w 2 ×Cost IO其中，w 0 为I 0 和I 1 在Gaia系统中的当前节点完成等值连接后，将等值连接结果传输给下一个节点时的I/O代价权重，Cost ship 为I 0 和I 1 在Gaia系统中的当前节点完成等值连接后，将等值连接结果传输给下一个节点时的I/O代价，w 1 为CPU对I 0 和I 1 进行等值连接时的计算代价权重，Cost cpu 为CPU对I 0 和I 1 进行等值连接时的计算代价，w 2 为I 0 和I 1 在Gaia系统中的当前节点完成等值连接后，将等值连接过程传输给本地文件系统时的I/O代价权重，Cost IO 为I 0 和I 1 在Gaia系统中的当前节点完成等值连接后，将等值连接过程传输给本地文件系统时的I/O代价。 4.如权利要求3所述的一种Gaia系统中的多表连接优化方法，其特征在于，所述代价函数中的Cost ship 的计算公式如下：Cost ship ＝Cost RR ×f ship +Cost BF ×(1-f ship )其中，Cost RR 为采用Repartition-Repartition策略进行传输时的传输代价，Cost BF 为采用Broadcast-Forward策略进行传输时的传输代价，f ship 为设定的第一选择因子；且有：Cost RR ＝S(PartitionShip(I 0 ))+S(PartitionShip(I 1 ))Cost BF ＝(n-1)×S(I 0 ),T(I 0 )<T(I 1 )其中，PartitionShip(I 0 )表示将I 0 通过分区函数发送到下一个节点的内容，PartitionShip(I 1 )表示将I 1 通过分区函数发送到下一个节点的内容，S(PartitionShip(I 0 ))表示I 0 通过分区函数发送到下一个节点的内容的体积，S(PartitionShip(I 1 ))表示I 1 通过分区函数发送到下一个节点的内容的体积，S(I 0 )表示表I 0 的总体积，T(I 0 )表示表I 0 的行数，T(I 1 )表示表I 1 的行数，n表示分布式节点的数量；表I 0 和I 1 的体积的计算公式为：其中，x＝0和1，S(I x )为总体积，T(I x )为表的行数，c i 为表的第i列，dataType of表示获取第i列的数据类型，columns为表I 0 和I 1 设定的需要保留的列数，sizeof表示获取第i列的数据类型占用的体积；所述代价函数中的Cost cpu 计算公式为：其中，f join 为设定的第二选择因子，且有：其中， 为采用Hybrid-Hash策略进行连接时的CPU计算代价， 为采用Sort-Merge策略进行连接时的CPU计算代价，lb(T(I 0 )为T(I 0 )以2为底的对数，lb(T(I 1 )为T(I 1 )以2为底的对数；所述代价函数中的Cost cpu 计算公式为：其中， 为采用Hybrid-Hash策略进行连接时的I/O连接代价， 为采用Sort-Merge策略进行连接时的I/O连接代价，且有：其中，M为节点的内存大小。 5.如权利要求4所述的一种Gaia系统中的多表连接优化方法，其特征在于，在判断任意两个表是否可等值连接时，根据有向索引图对两个表对应的索引条目进行溯源，若两个表对应的索引条目相同，则两个表享有相同的健值；同时，若两个表可等值连接，则在两个表对应的索引条目中，将两个表对应的索引位进行标记；若两个表需要进行等值连接代价的计算，则两个表要保留的列数columns的确定方法如下：分别判断I 0 和I 1 各列的属性码是否为原连接树中设定的输出表中各列的属性码，若是，则该列保留；分别判断I 0 和I 1 在进行等值连接时，两者对应的索引条目中的索引位是否全都被标记，若所有索引位均被标记，则删除两个表中与该索引条目对应的列。