RelAlgOptimizer.cpp File Reference

#include "RelAlgOptimizer.h"
#include "Logger/Logger.h"
#include "RexVisitor.h"
#include "Visitors/RexSubQueryIdCollector.h"
#include <numeric>
#include <string>
#include <unordered_map>

Include dependency graph for RelAlgOptimizer.cpp:

Go to the source code of this file.

Classes
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexProjectInputRedirector
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexRebindInputsVisitor
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexInputCollector
class	anonymous_namespace{RelAlgOptimizer.cpp}::AvailabilityChecker
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexInputRenumberVisitor
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexInputSinker
class	anonymous_namespace{RelAlgOptimizer.cpp}::SubConditionReplacer
class	anonymous_namespace{RelAlgOptimizer.cpp}::RexInputRedirector
class	JoinTargetRebaser
class	SubConditionRemover

Namespaces
	anonymous_namespace{RelAlgOptimizer.cpp}

Functions
size_t	anonymous_namespace{RelAlgOptimizer.cpp}::get_actual_source_size (const RelProject *curr_project, const std::unordered_set< const RelProject * > &projects_to_remove)
bool	anonymous_namespace{RelAlgOptimizer.cpp}::safe_to_redirect (const RelProject *project, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web)
bool	anonymous_namespace{RelAlgOptimizer.cpp}::is_identical_copy (const RelProject *project, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web, const std::unordered_set< const RelProject * > &projects_to_remove, std::unordered_set< const RelProject * > &permutating_projects)
void	anonymous_namespace{RelAlgOptimizer.cpp}::propagate_rex_input_renumber (const RelFilter *excluded_root, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web)
void	anonymous_namespace{RelAlgOptimizer.cpp}::redirect_inputs_of (std::shared_ptr< RelAlgNode > node, const std::unordered_set< const RelProject * > &projects, const std::unordered_set< const RelProject * > &permutating_projects, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web)
void	anonymous_namespace{RelAlgOptimizer.cpp}::cleanup_dead_nodes (std::vector< std::shared_ptr< RelAlgNode >> &nodes)
std::unordered_set< const RelProject * >	anonymous_namespace{RelAlgOptimizer.cpp}::get_visible_projects (const RelAlgNode *root)
bool	anonymous_namespace{RelAlgOptimizer.cpp}::is_distinct (const size_t input_idx, const RelAlgNode *node)
std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * > >	build_du_web (const std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
bool	project_separates_sort (const RelProject *project, const RelAlgNode *next_node)
void	eliminate_identical_copy (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
size_t	anonymous_namespace{RelAlgOptimizer.cpp}::pick_always_live_col_idx (const RelAlgNode *node)
std::vector < std::unordered_set< size_t > >	anonymous_namespace{RelAlgOptimizer.cpp}::get_live_ins (const RelAlgNode *node, const std::unordered_map< const RelAlgNode *, std::unordered_set< size_t >> &live_outs)
bool	anonymous_namespace{RelAlgOptimizer.cpp}::any_dead_col_in (const RelAlgNode *node, const std::unordered_set< size_t > &live_outs)
bool	anonymous_namespace{RelAlgOptimizer.cpp}::does_redef_cols (const RelAlgNode *node)
void	anonymous_namespace{RelAlgOptimizer.cpp}::add_new_indices_for (const RelAlgNode *node, std::unordered_map< const RelAlgNode *, std::unordered_map< size_t, size_t >> &new_liveouts, const std::unordered_set< size_t > &old_liveouts, const std::unordered_set< const RelAlgNode * > &intact_nodes, const std::unordered_map< const RelAlgNode *, size_t > &orig_node_sizes)
std::vector< std::unique_ptr < const RexAgg > >	anonymous_namespace{RelAlgOptimizer.cpp}::renumber_rex_aggs (std::vector< std::unique_ptr< const RexAgg >> &agg_exprs, const std::unordered_map< size_t, size_t > &new_numbering)
SortField	anonymous_namespace{RelAlgOptimizer.cpp}::renumber_sort_field (const SortField &old_field, const std::unordered_map< size_t, size_t > &new_numbering)
std::unordered_map< const RelAlgNode *, std::unordered_set< size_t > >	anonymous_namespace{RelAlgOptimizer.cpp}::mark_live_columns (std::vector< std::shared_ptr< RelAlgNode >> &nodes)
std::string	anonymous_namespace{RelAlgOptimizer.cpp}::get_field_name (const RelAlgNode *node, size_t index)
void	anonymous_namespace{RelAlgOptimizer.cpp}::try_insert_coalesceable_proj (std::vector< std::shared_ptr< RelAlgNode >> &nodes, std::unordered_map< const RelAlgNode *, std::unordered_set< size_t >> &liveouts, std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web)
std::pair< std::unordered_map < const RelAlgNode *, std::unordered_map< size_t, size_t > >, std::vector< const RelAlgNode * > >	anonymous_namespace{RelAlgOptimizer.cpp}::sweep_dead_columns (const std::unordered_map< const RelAlgNode *, std::unordered_set< size_t >> &live_outs, const std::vector< std::shared_ptr< RelAlgNode >> &nodes, const std::unordered_set< const RelAlgNode * > &intact_nodes, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web, const std::unordered_map< const RelAlgNode *, size_t > &orig_node_sizes)
void	anonymous_namespace{RelAlgOptimizer.cpp}::propagate_input_renumbering (std::unordered_map< const RelAlgNode *, std::unordered_map< size_t, size_t >> &liveout_renumbering, const std::vector< const RelAlgNode * > &ready_nodes, const std::unordered_map< const RelAlgNode *, std::unordered_set< size_t >> &old_liveouts, const std::unordered_set< const RelAlgNode * > &intact_nodes, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web, const std::unordered_map< const RelAlgNode *, size_t > &orig_node_sizes)
void	eliminate_dead_columns (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	eliminate_dead_subqueries (std::vector< std::shared_ptr< RexSubQuery >> &subqueries, RelAlgNode const *root)
void	sink_projected_boolean_expr_to_join (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	anonymous_namespace{RelAlgOptimizer.cpp}::replace_all_usages (std::shared_ptr< const RelAlgNode > old_def_node, std::shared_ptr< const RelAlgNode > new_def_node, std::unordered_map< const RelAlgNode *, std::shared_ptr< RelAlgNode >> &deconst_mapping, std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode * >> &du_web)
void	fold_filters (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
std::vector< const RexScalar * >	find_hoistable_conditions (const RexScalar *condition, const RelAlgNode *source, const size_t first_col_idx, const size_t last_col_idx)
void	hoist_filter_cond_to_cross_join (std::vector< std::shared_ptr< RelAlgNode >> &nodes) noexcept
void	sync_field_names_if_necessary (std::shared_ptr< const RelProject > from_node, RelAlgNode *to_node) noexcept
void	simplify_sort (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 416 of file RelAlgOptimizer.cpp.

References CHECK.

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);
      CHECK(dynamic_cast<const RelJoin*>(walker) ||
            dynamic_cast<const RelProject*>(walker) ||
            dynamic_cast<const RelAggregate*>(walker) ||
            dynamic_cast<const RelFilter*>(walker) ||
            dynamic_cast<const RelSort*>(walker) ||
            dynamic_cast<const RelLeftDeepInnerJoin*>(walker) ||
            dynamic_cast<const RelLogicalValues*>(walker) ||
            dynamic_cast<const RelTableFunction*>(walker) ||
            dynamic_cast<const RelLogicalUnion*>(walker));
      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 caller graph for this function:

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

noexcept

Definition at line 1187 of file RelAlgOptimizer.cpp.

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

Referenced by RelAlgDagBuilder::optimizeDag().

                                                                                  {
  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(RelRexToStringConfig::defaults());
      // 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_dead_subqueries	(	std::vector< std::shared_ptr< RexSubQuery >> &	subqueries,
		RelAlgNode const *	root
	)

Definition at line 1253 of file RelAlgOptimizer.cpp.

References anonymous_namespace{Utm.h}::a, RexSubQueryIdCollector::getLiveRexSubQueryIds(), gpu_enabled::upper_bound(), and VLOG.

Referenced by RelAlgDagBuilder::optimizeDag().

                                                       {
  if (!subqueries.empty()) {
    auto live_ids = RexSubQueryIdCollector::getLiveRexSubQueryIds(root);
    auto sort_live_ids_first = [&live_ids](auto& a, auto& b) {
      return live_ids.count(a->getId()) && !live_ids.count(b->getId());
    };
    std::stable_sort(subqueries.begin(), subqueries.end(), sort_live_ids_first);
    size_t n_dead_subqueries;
    if (live_ids.count(subqueries.front()->getId())) {
      auto first_dead_itr = std::upper_bound(subqueries.cbegin(),
                                             subqueries.cend(),
                                             subqueries.front(),
                                             sort_live_ids_first);
      n_dead_subqueries = subqueries.cend() - first_dead_itr;
    } else {
      n_dead_subqueries = subqueries.size();
    }
    if (n_dead_subqueries) {
      VLOG(1) << "Eliminating " << n_dead_subqueries
              << (n_dead_subqueries == 1 ? " subquery." : " subqueries.");
      subqueries.resize(subqueries.size() - n_dead_subqueries);
      subqueries.shrink_to_fit();
    }
  }
}

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 494 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(), project_separates_sort(), anonymous_namespace{RelAlgOptimizer.cpp}::redirect_inputs_of(), and gpu_enabled::swap().

Referenced by RelAlgDagBuilder::optimizeDag().

                                                                                    {
  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 const visible_projs = get_visible_projects(nodes.back().get());
  for (auto node_it = nodes.begin(); node_it != nodes.end(); node_it++) {
    auto node = *node_it;
    auto project = std::dynamic_pointer_cast<RelProject>(node);
    auto next_node_it = std::next(node_it);
    if (project && project->isSimple() &&
        (!visible_projs.count(project.get()) || !project->isRenaming()) &&
        is_identical_copy(project.get(), web, projects, permutating_projects) &&
        !project_separates_sort(
            project.get(), next_node_it == nodes.end() ? nullptr : next_node_it->get())) {
      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:

std::vector<const RexScalar*> find_hoistable_conditions	(	const RexScalar *	condition,
		const RelAlgNode *	source,
		const size_t	first_col_idx,
		const size_t	last_col_idx
	)

Definition at line 1536 of file RelAlgOptimizer.cpp.

References RexAbstractInput::getIndex(), kAND, and kEQ.

Referenced by hoist_filter_cond_to_cross_join().

                                                                                   {
  if (auto rex_op = dynamic_cast<const RexOperator*>(condition)) {
    switch (rex_op->getOperator()) {
      case kAND: {
        std::vector<const RexScalar*> subconditions;
        size_t complete_subcond_count = 0;
        for (size_t i = 0; i < rex_op->size(); ++i) {
          auto conds = find_hoistable_conditions(
              rex_op->getOperand(i), source, first_col_idx, last_col_idx);
          if (conds.size() == size_t(1)) {
            ++complete_subcond_count;
          }
          subconditions.insert(subconditions.end(), conds.begin(), conds.end());
        }
        if (complete_subcond_count == rex_op->size()) {
          return {rex_op};
        } else {
          return {subconditions};
        }
        break;
      }
      case kEQ: {
        const auto lhs_conds = find_hoistable_conditions(
            rex_op->getOperand(0), source, first_col_idx, last_col_idx);
        const auto rhs_conds = find_hoistable_conditions(
            rex_op->getOperand(1), source, first_col_idx, last_col_idx);
        const auto lhs_in = lhs_conds.size() == 1
                                ? dynamic_cast<const RexInput*>(*lhs_conds.begin())
                                : nullptr;
        const auto rhs_in = rhs_conds.size() == 1
                                ? dynamic_cast<const RexInput*>(*rhs_conds.begin())
                                : nullptr;
        if (lhs_in && rhs_in) {
          return {rex_op};
        }
        return {};
        break;
      }
      default:
        break;
    }
    return {};
  }
  if (auto rex_in = dynamic_cast<const RexInput*>(condition)) {
    if (rex_in->getSourceNode() == source) {
      const auto col_idx = rex_in->getIndex();
      return {col_idx >= first_col_idx && col_idx <= last_col_idx ? condition : nullptr};
    }
    return {};
  }
  return {};
}

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 1468 of file RelAlgOptimizer.cpp.

References build_du_web(), CHECK, CHECK_EQ, anonymous_namespace{RelAlgOptimizer.cpp}::cleanup_dead_nodes(), logger::DEBUG2, RelRexToStringConfig::defaults(), logger::fast_logging_check(), g_max_log_length, kAND, kBOOLEAN, anonymous_namespace{RelAlgOptimizer.cpp}::replace_all_usages(), substring(), and VLOG.

Referenced by RelAlgDagBuilder::optimizeDag().

                                                                        {
  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())) {
        VLOG(1) << "Node ID=" << filter->getId() << " folded into "
                << "ID=" << folded_filter->getId();
        if (logger::fast_logging_check(logger::Severity::DEBUG2)) {
          auto node_str = folded_filter->toString(RelRexToStringConfig::defaults());
          auto [node_substr, post_fix] = ::substring(node_str, g_max_log_length);
          VLOG(2) << "Folded Node (ID: " << folded_filter->getId()
                  << ") contents: " << node_substr << post_fix;
        }
        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.rbegin()); node_it != nodes.rend(); ++node_it) {
      if (sink) {
        break;
      }
      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 1634 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::optimizeDag().

                                                          {
  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:

bool project_separates_sort	(	const RelProject *	project,
		const RelAlgNode *	next_node
	)

Return true if the input project separates two sort nodes, i.e. Sort -> Project -> Sort. This pattern often occurs in machine generated SQL, e.g. SELECT * FROM (SELECT * FROM t LIMIT 10) t0 LIMIT 1; Use this function to prevent optimizing out the intermediate project, as the project is required to ensure the first sort runs to completion prior to the second sort. Back to back sort nodes are not executable and will throw an error.

Definition at line 471 of file RelAlgOptimizer.cpp.

References CHECK, RelAlgNode::getInput(), RelAlgNode::inputCount(), and gpu_enabled::sort().

Referenced by eliminate_identical_copy().

                                                                                    {
  CHECK(project);
  if (!next_node) {
    return false;
  }

  auto sort = dynamic_cast<const RelSort*>(next_node);
  if (!sort) {
    return false;
  }
  if (!(project->inputCount() == 1)) {
    return false;
  }

  if (dynamic_cast<const RelSort*>(project->getInput(0))) {
    return true;
  }
  return false;
}

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 1759 of file RelAlgOptimizer.cpp.

References sync_field_names_if_necessary().

Referenced by RelAlgDagBuilder::optimizeDag().

                                                                         {
  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) {
      sync_field_names_if_necessary(project, /* an input of the second sort */
                                    const_cast<RelAlgNode*>(first_sort->getInput(0)));
      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 1320 of file RelAlgOptimizer.cpp.

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

Referenced by RelAlgDagBuilder::optimizeDag().

                                                          {
  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:

void sync_field_names_if_necessary ( std::shared_ptr< const RelProject >  from_node, RelAlgNode *  to_node  )

noexcept

Definition at line 1736 of file RelAlgOptimizer.cpp.

Referenced by simplify_sort().

                                                                 {
  auto from_fields = from_node->getFields();
  if (!from_fields.empty()) {
    if (auto proj_to = dynamic_cast<RelProject*>(to_node);
        proj_to && proj_to->getFields().size() == from_fields.size()) {
      proj_to->setFields(std::move(from_fields));
    } else if (auto agg_to = dynamic_cast<RelAggregate*>(to_node);
               agg_to && agg_to->getFields().size() == from_fields.size()) {
      agg_to->setFields(std::move(from_fields));
    } else if (auto compound_to = dynamic_cast<RelCompound*>(to_node);
               compound_to && compound_to->getFields().size() == from_fields.size()) {
      compound_to->setFields(std::move(from_fields));
    } else if (auto tf_to = dynamic_cast<RelTableFunction*>(to_node);
               tf_to && tf_to->getFields().size() == from_fields.size()) {
      tf_to->setFields(std::move(from_fields));
    }
  }
}

Here is the caller graph for this function: