RelAlgOptimizer.h File Reference

#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>

Include dependency graph for RelAlgOptimizer.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * > >	build_du_web (const std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	eliminate_identical_copy (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	eliminate_dead_columns (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	fold_filters (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	hoist_filter_cond_to_cross_join (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	simplify_sort (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	sink_projected_boolean_expr_to_join (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept

Function Documentation

std::unordered_map<const RelAlgNode*, std::unordered_set<const RelAlgNode*> > build_du_web ( const std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 387 of file RelAlgOptimizer.cpp.

References CHECK(), join(), and src.

Referenced by eliminate_dead_columns(), eliminate_identical_copy(), fold_filters(), hoist_filter_cond_to_cross_join(), and sink_projected_boolean_expr_to_join().

                                                                {
  std::unordered_map<const RelAlgNode*, std::unordered_set<const RelAlgNode*>> web;
  std::unordered_set<const RelAlgNode*> visited;
  std::vector<const RelAlgNode*> work_set;
  for (auto node : nodes) {
    if (std::dynamic_pointer_cast<RelScan>(node) ||
        std::dynamic_pointer_cast<RelModify>(node) || visited.count(node.get())) {
      continue;
    }
    work_set.push_back(node.get());
    while (!work_set.empty()) {
      auto walker = work_set.back();
      work_set.pop_back();
      if (visited.count(walker)) {
        continue;
      }
      CHECK(!web.count(walker));
      auto it_ok =
          web.insert(std::make_pair(walker, std::unordered_set<const RelAlgNode*>{}));
      CHECK(it_ok.second);
      visited.insert(walker);
      const auto join = dynamic_cast<const RelJoin*>(walker);
      const auto project = dynamic_cast<const RelProject*>(walker);
      const auto aggregate = dynamic_cast<const RelAggregate*>(walker);
      const auto filter = dynamic_cast<const RelFilter*>(walker);
      const auto sort = dynamic_cast<const RelSort*>(walker);
      const auto left_deep_join = dynamic_cast<const RelLeftDeepInnerJoin*>(walker);
      const auto logical_values = dynamic_cast<const RelLogicalValues*>(walker);
      const auto table_func = dynamic_cast<const RelTableFunction*>(walker);
      CHECK(join || project || aggregate || filter || sort || left_deep_join ||
            logical_values || table_func);
      for (size_t i = 0; i < walker->inputCount(); ++i) {
        auto src = walker->getInput(i);
        if (dynamic_cast<const RelScan*>(src) || dynamic_cast<const RelModify*>(src)) {
          continue;
        }
        if (web.empty() || !web.count(src)) {
          web.insert(std::make_pair(src, std::unordered_set<const RelAlgNode*>{}));
        }
        web[src].insert(walker);
        work_set.push_back(src);
      }
    }
  }
  return web;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void eliminate_dead_columns ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 1112 of file RelAlgOptimizer.cpp.

References anonymous_namespace{RelAlgOptimizer.cpp}::any_dead_col_in(), build_du_web(), CHECK(), anonymous_namespace{RelAlgOptimizer.cpp}::does_redef_cols(), LOG, anonymous_namespace{RelAlgOptimizer.cpp}::mark_live_columns(), anonymous_namespace{RelAlgOptimizer.cpp}::propagate_input_renumbering(), anonymous_namespace{RelAlgOptimizer.cpp}::sweep_dead_columns(), anonymous_namespace{RelAlgOptimizer.cpp}::try_insert_coalesceable_proj(), and logger::WARNING.

Referenced by RelAlgDagBuilder::build().

                                                                                  {
  if (nodes.empty()) {
    return;
  }
  auto root = nodes.back().get();
  if (!root) {
    return;
  }
  CHECK(!dynamic_cast<const RelScan*>(root) && !dynamic_cast<const RelJoin*>(root));
  // Mark
  auto old_liveouts = mark_live_columns(nodes);
  std::unordered_set<const RelAlgNode*> intact_nodes;
  bool has_dead_cols = false;
  for (auto live_pair : old_liveouts) {
    auto node = live_pair.first;
    const auto& outs = live_pair.second;
    if (outs.empty()) {
      LOG(WARNING) << "RA node with no used column: " << node->toString();
      // Ignore empty live_out due to some invalid node
      intact_nodes.insert(node);
    }
    if (any_dead_col_in(node, outs)) {
      has_dead_cols = true;
    } else {
      intact_nodes.insert(node);
    }
  }
  if (!has_dead_cols) {
    return;
  }
  auto web = build_du_web(nodes);
  try_insert_coalesceable_proj(nodes, old_liveouts, web);

  for (auto node : nodes) {
    if (intact_nodes.count(node.get()) || does_redef_cols(node.get())) {
      continue;
    }
    bool intact = true;
    for (size_t i = 0; i < node->inputCount(); ++i) {
      auto source = node->getInput(i);
      if (!dynamic_cast<const RelScan*>(source) && !intact_nodes.count(source)) {
        intact = false;
        break;
      }
    }
    if (intact) {
      intact_nodes.insert(node.get());
    }
  }

  std::unordered_map<const RelAlgNode*, size_t> orig_node_sizes;
  for (auto node : nodes) {
    orig_node_sizes.insert(std::make_pair(node.get(), node->size()));
  }
  // Sweep
  std::unordered_map<const RelAlgNode*, std::unordered_map<size_t, size_t>>
      liveout_renumbering;
  std::vector<const RelAlgNode*> ready_nodes;
  std::tie(liveout_renumbering, ready_nodes) =
      sweep_dead_columns(old_liveouts, nodes, intact_nodes, web, orig_node_sizes);
  // Propagate
  propagate_input_renumbering(
      liveout_renumbering, ready_nodes, old_liveouts, intact_nodes, web, orig_node_sizes);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void eliminate_identical_copy ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 438 of file RelAlgOptimizer.cpp.

References build_du_web(), CHECK(), CHECK_EQ, anonymous_namespace{RelAlgOptimizer.cpp}::cleanup_dead_nodes(), anonymous_namespace{RelAlgOptimizer.cpp}::get_visible_projects(), anonymous_namespace{RelAlgOptimizer.cpp}::is_distinct(), anonymous_namespace{RelAlgOptimizer.cpp}::is_identical_copy(), and anonymous_namespace{RelAlgOptimizer.cpp}::redirect_inputs_of().

Referenced by RelAlgDagBuilder::build().

                                                                                    {
  std::unordered_set<std::shared_ptr<const RelAlgNode>> copies;
  auto sink = nodes.back();
  for (auto node : nodes) {
    auto aggregate = std::dynamic_pointer_cast<const RelAggregate>(node);
    if (!aggregate || aggregate == sink ||
        !(aggregate->getGroupByCount() == 1 && aggregate->getAggExprsCount() == 0)) {
      continue;
    }
    auto project =
        std::dynamic_pointer_cast<const RelProject>(aggregate->getAndOwnInput(0));
    if (project && project->size() == aggregate->size() &&
        project->getFields() == aggregate->getFields()) {
      CHECK_EQ(size_t(0), copies.count(aggregate));
      copies.insert(aggregate);
    }
  }
  for (auto node : nodes) {
    if (!node->inputCount()) {
      continue;
    }
    auto last_source = node->getAndOwnInput(node->inputCount() - 1);
    if (!copies.count(last_source)) {
      continue;
    }
    auto aggregate = std::dynamic_pointer_cast<const RelAggregate>(last_source);
    CHECK(aggregate);
    if (!std::dynamic_pointer_cast<const RelJoin>(node) || aggregate->size() != 1) {
      continue;
    }
    auto project =
        std::dynamic_pointer_cast<const RelProject>(aggregate->getAndOwnInput(0));
    CHECK(project);
    CHECK_EQ(size_t(1), project->size());
    if (!is_distinct(size_t(0), project.get())) {
      continue;
    }
    auto new_source = project->getAndOwnInput(0);
    if (std::dynamic_pointer_cast<const RelSort>(new_source) ||
        std::dynamic_pointer_cast<const RelScan>(new_source)) {
      node->replaceInput(last_source, new_source);
    }
  }
  decltype(copies)().swap(copies);

  auto web = build_du_web(nodes);

  std::unordered_set<const RelProject*> projects;
  std::unordered_set<const RelProject*> permutating_projects;
  auto visible_projs = get_visible_projects(nodes.back().get());
  for (auto node : nodes) {
    auto project = std::dynamic_pointer_cast<RelProject>(node);
    if (project && project->isSimple() &&
        (!visible_projs.count(project.get()) || !project->isRenaming()) &&
        is_identical_copy(project.get(), web, projects, permutating_projects)) {
      projects.insert(project.get());
    }
  }

  for (auto node : nodes) {
    redirect_inputs_of(node, projects, permutating_projects, web);
  }

  cleanup_dead_nodes(nodes);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void fold_filters ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 1365 of file RelAlgOptimizer.cpp.

References build_du_web(), CHECK(), CHECK_EQ, anonymous_namespace{RelAlgOptimizer.cpp}::cleanup_dead_nodes(), logger::INFO, kAND, kBOOLEAN, LOG, and anonymous_namespace{RelAlgOptimizer.cpp}::replace_all_usages().

Referenced by RelAlgDagBuilder::build().

                                                                        {
  std::unordered_map<const RelAlgNode*, std::shared_ptr<RelAlgNode>> deconst_mapping;
  for (auto node : nodes) {
    deconst_mapping.insert(std::make_pair(node.get(), node));
  }

  auto web = build_du_web(nodes);
  for (auto node_it = nodes.rbegin(); node_it != nodes.rend(); ++node_it) {
    auto& node = *node_it;
    if (auto filter = std::dynamic_pointer_cast<RelFilter>(node)) {
      CHECK_EQ(filter->inputCount(), size_t(1));
      auto src_filter = dynamic_cast<const RelFilter*>(filter->getInput(0));
      if (!src_filter) {
        continue;
      }
      auto siblings_it = web.find(src_filter);
      if (siblings_it == web.end() || siblings_it->second.size() != size_t(1)) {
        continue;
      }
      auto src_it = deconst_mapping.find(src_filter);
      CHECK(src_it != deconst_mapping.end());
      auto folded_filter = std::dynamic_pointer_cast<RelFilter>(src_it->second);
      CHECK(folded_filter);
      // TODO(miyu) : drop filter w/ only expression valued constant TRUE?
      if (auto rex_operator = dynamic_cast<const RexOperator*>(filter->getCondition())) {
        LOG(INFO) << "ID=" << filter->getId() << " " << filter->toString()
                  << " folded into "
                  << "ID=" << folded_filter->getId() << " " << folded_filter->toString()
                  << std::endl;
        std::vector<std::unique_ptr<const RexScalar>> operands;
        operands.emplace_back(folded_filter->getAndReleaseCondition());
        auto old_condition = dynamic_cast<const RexOperator*>(operands.back().get());
        CHECK(old_condition && old_condition->getType().get_type() == kBOOLEAN);
        RexInputRedirector redirector(folded_filter.get(), folded_filter->getInput(0));
        operands.push_back(redirector.visit(rex_operator));
        auto other_condition = dynamic_cast<const RexOperator*>(operands.back().get());
        CHECK(other_condition && other_condition->getType().get_type() == kBOOLEAN);
        const bool notnull = old_condition->getType().get_notnull() &&
                             other_condition->getType().get_notnull();
        auto new_condition = std::unique_ptr<const RexScalar>(
            new RexOperator(kAND, operands, SQLTypeInfo(kBOOLEAN, notnull)));
        folded_filter->setCondition(new_condition);
        replace_all_usages(filter, folded_filter, deconst_mapping, web);
        deconst_mapping.erase(filter.get());
        web.erase(filter.get());
        web[filter->getInput(0)].erase(filter.get());
        node.reset();
      }
    }
  }

  if (!nodes.empty()) {
    auto sink = nodes.back();
    for (auto node_it = std::next(nodes.rend()); !sink && node_it != nodes.rbegin();
         ++node_it) {
      sink = *node_it;
    }
    CHECK(sink);
    cleanup_dead_nodes(nodes);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void hoist_filter_cond_to_cross_join ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 1525 of file RelAlgOptimizer.cpp.

References build_du_web(), CHECK(), find_hoistable_conditions(), RelFilter::getCondition(), RelAlgNode::getInput(), INNER, join(), kAND, kBOOLEAN, RelFilter::setCondition(), and RexVisitorBase< T >::visit().

Referenced by RelAlgDagBuilder::build().

                                                          {
  std::unordered_set<const RelAlgNode*> visited;
  auto web = build_du_web(nodes);
  for (auto node : nodes) {
    if (visited.count(node.get())) {
      continue;
    }
    visited.insert(node.get());
    auto join = dynamic_cast<RelJoin*>(node.get());
    if (join && join->getJoinType() == JoinType::INNER) {
      // Only allow cross join for now.
      if (auto literal = dynamic_cast<const RexLiteral*>(join->getCondition())) {
        // Assume Calcite always generates an inner join on constant boolean true for
        // cross join.
        CHECK(literal->getType() == kBOOLEAN && literal->getVal<bool>());
        size_t first_col_idx = 0;
        const RelFilter* filter = nullptr;
        std::vector<const RelJoin*> join_seq{join};
        for (const RelJoin* curr_join = join; !filter;) {
          auto usrs_it = web.find(curr_join);
          CHECK(usrs_it != web.end());
          if (usrs_it->second.size() != size_t(1)) {
            break;
          }
          auto only_usr = *usrs_it->second.begin();
          if (auto usr_join = dynamic_cast<const RelJoin*>(only_usr)) {
            if (join == usr_join->getInput(1)) {
              const auto src1_offset = usr_join->getInput(0)->size();
              first_col_idx += src1_offset;
            }
            join_seq.push_back(usr_join);
            curr_join = usr_join;
            continue;
          }

          filter = dynamic_cast<const RelFilter*>(only_usr);
          break;
        }
        if (!filter) {
          visited.insert(join_seq.begin(), join_seq.end());
          continue;
        }
        const auto src_join = dynamic_cast<const RelJoin*>(filter->getInput(0));
        CHECK(src_join);
        auto modified_filter = const_cast<RelFilter*>(filter);

        if (src_join == join) {
          std::unique_ptr<const RexScalar> filter_condition(
              modified_filter->getAndReleaseCondition());
          std::unique_ptr<const RexScalar> true_condition =
              boost::make_unique<RexLiteral>(true,
                                             kBOOLEAN,
                                             kBOOLEAN,
                                             unsigned(-2147483648),
                                             1,
                                             unsigned(-2147483648),
                                             1);
          modified_filter->setCondition(true_condition);
          join->setCondition(filter_condition);
          continue;
        }
        const auto src1_base = src_join->getInput(0)->size();
        auto source =
            first_col_idx < src1_base ? src_join->getInput(0) : src_join->getInput(1);
        first_col_idx =
            first_col_idx < src1_base ? first_col_idx : first_col_idx - src1_base;
        auto join_conditions =
            find_hoistable_conditions(filter->getCondition(),
                                      source,
                                      first_col_idx,
                                      first_col_idx + join->size() - 1);
        if (join_conditions.empty()) {
          continue;
        }

        JoinTargetRebaser rebaser(join, first_col_idx);
        if (join_conditions.size() == 1) {
          auto new_join_condition = rebaser.visit(*join_conditions.begin());
          join->setCondition(new_join_condition);
        } else {
          std::vector<std::unique_ptr<const RexScalar>> operands;
          bool notnull = true;
          for (size_t i = 0; i < join_conditions.size(); ++i) {
            operands.emplace_back(rebaser.visit(join_conditions[i]));
            auto old_subcond = dynamic_cast<const RexOperator*>(join_conditions[i]);
            CHECK(old_subcond && old_subcond->getType().get_type() == kBOOLEAN);
            notnull = notnull && old_subcond->getType().get_notnull();
          }
          auto new_join_condition = std::unique_ptr<const RexScalar>(
              new RexOperator(kAND, operands, SQLTypeInfo(kBOOLEAN, notnull)));
          join->setCondition(new_join_condition);
        }

        SubConditionRemover remover(join_conditions);
        auto new_filter_condition = remover.visit(filter->getCondition());
        modified_filter->setCondition(new_filter_condition);
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void simplify_sort ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 1630 of file RelAlgOptimizer.cpp.

References RelAlgNode::replaceInput().

Referenced by RelAlgDagBuilder::build().

                                                                         {
  if (nodes.size() < 3) {
    return;
  }
  for (size_t i = 0; i <= nodes.size() - 3;) {
    auto first_sort = std::dynamic_pointer_cast<RelSort>(nodes[i]);
    const auto project = std::dynamic_pointer_cast<const RelProject>(nodes[i + 1]);
    auto second_sort = std::dynamic_pointer_cast<RelSort>(nodes[i + 2]);
    if (first_sort && second_sort && project && project->isIdentity() &&
        *first_sort == *second_sort) {
      second_sort->replaceInput(second_sort->getAndOwnInput(0),
                                first_sort->getAndOwnInput(0));
      nodes[i].reset();
      nodes[i + 1].reset();
      i += 3;
    } else {
      ++i;
    }
  }

  std::vector<std::shared_ptr<RelAlgNode>> new_nodes;
  for (auto node : nodes) {
    if (!node) {
      continue;
    }
    new_nodes.push_back(node);
  }
  nodes.swap(new_nodes);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void sink_projected_boolean_expr_to_join ( std::vector< std::shared_ptr< RelAlgNode >> &  nodes )

noexcept

Definition at line 1217 of file RelAlgOptimizer.cpp.

References build_du_web(), CHECK(), CHECK_EQ, join(), kBOOLEAN, and anonymous_namespace{RelAlgOptimizer.cpp}::mark_live_columns().

Referenced by RelAlgDagBuilder::build().

                                                          {
  auto web = build_du_web(nodes);
  auto liveouts = mark_live_columns(nodes);
  for (auto node : nodes) {
    auto project = std::dynamic_pointer_cast<RelProject>(node);
    // TODO(miyu): relax RelScan limitation
    if (!project || project->isSimple() ||
        !dynamic_cast<const RelScan*>(project->getInput(0))) {
      continue;
    }
    auto usrs_it = web.find(project.get());
    CHECK(usrs_it != web.end());
    auto& usrs = usrs_it->second;
    if (usrs.size() != 1) {
      continue;
    }
    auto join = dynamic_cast<RelJoin*>(const_cast<RelAlgNode*>(*usrs.begin()));
    if (!join) {
      continue;
    }
    auto outs_it = liveouts.find(join);
    CHECK(outs_it != liveouts.end());
    std::unordered_map<size_t, size_t> in_to_out_index;
    std::unordered_set<size_t> boolean_expr_indicies;
    bool discarded = false;
    for (size_t i = 0; i < project->size(); ++i) {
      auto oper = dynamic_cast<const RexOperator*>(project->getProjectAt(i));
      if (oper && oper->getType().get_type() == kBOOLEAN) {
        boolean_expr_indicies.insert(i);
      } else {
        // TODO(miyu): relax?
        if (auto input = dynamic_cast<const RexInput*>(project->getProjectAt(i))) {
          in_to_out_index.insert(std::make_pair(input->getIndex(), i));
        } else {
          discarded = true;
        }
      }
    }
    if (discarded || boolean_expr_indicies.empty()) {
      continue;
    }
    const size_t index_base =
        join->getInput(0) == project.get() ? 0 : join->getInput(0)->size();
    for (auto i : boolean_expr_indicies) {
      auto join_idx = index_base + i;
      if (outs_it->second.count(join_idx)) {
        discarded = true;
        break;
      }
    }
    if (discarded) {
      continue;
    }
    RexInputCollector collector(project.get());
    std::vector<size_t> unloaded_input_indices;
    std::unordered_map<size_t, std::unique_ptr<const RexScalar>> in_idx_to_new_subcond;
    // Given all are dead right after join, safe to sink
    for (auto i : boolean_expr_indicies) {
      auto rex_ins = collector.visit(project->getProjectAt(i));
      for (auto& in : rex_ins) {
        CHECK_EQ(in.getSourceNode(), project->getInput(0));
        if (!in_to_out_index.count(in.getIndex())) {
          auto curr_out_index = project->size() + unloaded_input_indices.size();
          in_to_out_index.insert(std::make_pair(in.getIndex(), curr_out_index));
          unloaded_input_indices.push_back(in.getIndex());
        }
        RexInputSinker sinker(in_to_out_index, project.get());
        in_idx_to_new_subcond.insert(
            std::make_pair(i, sinker.visit(project->getProjectAt(i))));
      }
    }
    if (in_idx_to_new_subcond.empty()) {
      continue;
    }
    std::vector<std::unique_ptr<const RexScalar>> new_projections;
    for (size_t i = 0; i < project->size(); ++i) {
      if (boolean_expr_indicies.count(i)) {
        new_projections.push_back(boost::make_unique<RexInput>(project->getInput(0), 0));
      } else {
        auto rex_input = dynamic_cast<const RexInput*>(project->getProjectAt(i));
        CHECK(rex_input != nullptr);
        new_projections.push_back(rex_input->deepCopy());
      }
    }
    for (auto i : unloaded_input_indices) {
      new_projections.push_back(boost::make_unique<RexInput>(project->getInput(0), i));
    }
    project->setExpressions(new_projections);

    SubConditionReplacer replacer(in_idx_to_new_subcond);
    auto new_condition = replacer.visit(join->getCondition());
    join->setCondition(new_condition);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function: