Lab 5 查询优化

基础功能

查询重写

分解复合的选择谓词见 Optimizer::SplitPredicates.

遍历查询计划树, 若查询树的节点为 Filter 类型, 对应的谓词为 LOGIC 类型, 且逻辑表达式为 AND 类型, 则将谓词的左右子表达式作为新的 Filter 节点添加到查询计划树中, 同时维护节点间的父子关系.

下推选择运算见 Optimizer::PushDownFilter 与 Optimizer::PushDownSeqScan.

对于 Filter 类型的节点, 若谓词为 Comparison 且为 ColumnValue 和 ColumnValue 的比较, 则为连接谓词, 将其保存到 Optimizer 类的成员变量 std::vector<FilterOperator> join_filters_ 中; 否则为普通谓词, 将其保存到成员变量 std::vector<FilterOperator> simple_filters_ 中. 注意对子节点递归调用 PushDown.
通过 Operator::OutputColumns().GetColumns() 获取当前 SeqScan 节点的全部列名, 判断成员变量保存的普通谓词是否使用这些列, 并在此 SeqScan 节点上方添加 Filter 节点.

笛卡尔积转连接见 Optimizer::PushDownJoin.

对 NestedLoopJoin 节点通过 Operator::OutputColumns().GetColumns() 获取当前 SeqScan 节点的全部列名, 判断成员变量保存的连接谓词是否可以用于该节点, 如果有将连接谓词添加到该节点的 join_condition, 实现笛卡尔积到连接的转换.

基于贪心算法的连接顺序选择

基于贪心算法的连接顺序选择见 Optimizer::ReorderJoin.

使用如下结构体存储当前表的元信息:

struct TableInfo {
 public:
  std::string name;
  uint32_t cardinality;
  std::unordered_set<std::string> columns;
  std::unordered_map<std::string, uint32_t> distinct;
  SeqScanOperator seq_scan;
};

递归扫描查询计划树, 记录所有 SeqScan 节点和 NestedLoopJoin 节点, 将 SeqScan 节点对应的表格元信息存储在 table_infos 中, 通过贪心算法对 table_infos 进行重排序. 从其中记录的 SeqScan 节点自底向上依次构建 NestedLoopJoin 节点, 并替换原始的以 NestedLoopJoin 节点为根的子树.