| 主权项 |
一种基于列存储模型的查询优化方法，其特征在于，步骤为：步骤1、接收用户按关系表进行的SQL查询输入，记为select L from R<sub>1</sub>，… , R<sub>m</sub> where ∧/∨(A<sub>1</sub>，……A<sub>n</sub>)，其中R<sub>i</sub>为关系表，L是关系的属性集，A<sub>1</sub>，……A<sub>n</sub>是由与节点或者或节点连接的谓词；步骤2：将上述SQL语句转换为按二元表进行的查询，记为select L from (K<sub>1</sub>×K<sub>2</sub>×……) where ∧/∨(A<sub>1</sub>，……A<sub>n</sub>)，其中，K<sub>i</sub>是查询相关的列；步骤3、初始的逻辑计划树生成，其具体步骤为：1） 利用关系代数等价变换规则将作用于同列的一元谓词进行下推并合并；2） 将同表的一元谓词结点集通过AND结点自底向上依次连接成一棵左深逻辑查询子树，为每个表形成单表查询子树；3） 将上述步骤中产生的所有单表查询子树用JOIN结点自底向上依次连接成一棵完整的逻辑查询树，将不同表列之间的连接条件存储到相应JOIN结点中；步骤4、为步骤3中产生的逻辑查询计划树进行同表连接顺序优化，其具体步骤为：1）为其每个选择结点计算选择率；2）找出选择率最小的叶子结点记为min_node；3）从元数据读取min_node对应列的列值索引value_index情况；4）如果min_node没有建立列值索引，则从有列值索引的列中找出选择率最小的结点记为index_min_node；5）如果min_node建有列值索引或者index_min_node不存在，则将min_node与单表查询子树最底端左结点互换；6）如果min_node没有建立列值索引并且index_min_node存在，则将min_node与单表查询子树最底端左结点的右兄弟互换，并将index_min_node与单表查询子树最底端左结点互换；步骤5、根据步骤3逻辑计划树中保存的连接信息为每个关系表登记连接关系集J；步骤6、根据集合J判断关系表的类型，与多个表存在连接关系的为事实表，其余的为维表；步骤7、单事实表连接顺序优化，具体步骤为：对于每个事实表与其关联的维表，将事实表的逻辑查询子树下推到查询树底层，根据连接选择性从优到劣依次连接与该事实表连接的各维表的逻辑查询子树，形成一棵左深逻辑查询子树；步骤8、多事实表连接顺序优化，具体步骤为：将步骤7中产生的左深逻辑查询子树用JOIN结点连接成一棵紧密树，并根据维表重复情况将相关单事实表查询树中的相应连接条件转移到JOIN结点中。 |
