anonymous_namespace{RelAlgOptimizer.cpp} Namespace Reference

Classes
class	AvailabilityChecker
class	RexInputCollector
class	RexInputRedirector
class	RexInputRenumberVisitor
class	RexInputSinker
class	RexProjectInputRedirector
class	RexRebindInputsVisitor
class	SubConditionReplacer

Functions
size_t	get_actual_source_size (const RelProject *curr_project, const std::unordered_set< const RelProject *> &projects_to_remove)
bool	safe_to_redirect (const RelProject *project, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode *>> &du_web)
bool	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	propagate_rex_input_renumber (const RelFilter *excluded_root, const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode *>> &du_web)
void	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	cleanup_dead_nodes (std::vector< std::shared_ptr< RelAlgNode >> &nodes)
std::unordered_set< const RelProject * >	get_visible_projects (const RelAlgNode *root)
bool	is_distinct (const size_t input_idx, const RelAlgNode *node)
size_t	pick_always_live_col_idx (const RelAlgNode *node)
std::vector< std::unordered_set< size_t > >	get_live_ins (const RelAlgNode *node, const std::unordered_map< const RelAlgNode *, std::unordered_set< size_t >> &live_outs)
bool	any_dead_col_in (const RelAlgNode *node, const std::unordered_set< size_t > &live_outs)
bool	does_redef_cols (const RelAlgNode *node)
void	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 > >	renumber_rex_aggs (std::vector< std::unique_ptr< const RexAgg >> &agg_exprs, const std::unordered_map< size_t, size_t > &new_numbering)
SortField	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 > >	mark_live_columns (std::vector< std::shared_ptr< RelAlgNode >> &nodes)
std::string	get_field_name (const RelAlgNode *node, size_t index)
void	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 * > >	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	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	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)

Function Documentation

add_new_indices_for()

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
	)

Definition at line 789 of file RelAlgOptimizer.cpp.

References CHECK, CHECK_GT, does_redef_cols(), RelAlgNode::getInput(), logger::INFO, RelAlgNode::inputCount(), LOG, RelAlgNode::size(), gpu_enabled::sort(), and RelAlgNode::toString().

Referenced by propagate_input_renumbering(), and sweep_dead_columns().

                                                                        {
  auto live_fields = old_liveouts;
  if (auto aggregate = dynamic_cast<const RelAggregate*>(node)) {
    for (size_t i = 0; i < aggregate->getGroupByCount(); ++i) {
      live_fields.insert(i);
    }
  }
  auto it_ok =
      new_liveouts.insert(std::make_pair(node, std::unordered_map<size_t, size_t>{}));
  CHECK(it_ok.second);
  auto& new_indices = it_ok.first->second;
  if (intact_nodes.count(node)) {
    for (size_t i = 0, e = node->size(); i < e; ++i) {
      new_indices.insert(std::make_pair(i, i));
    }
    return;
  }
  if (does_redef_cols(node)) {
    auto node_sz_it = orig_node_sizes.find(node);
    CHECK(node_sz_it != orig_node_sizes.end());
    const auto node_size = node_sz_it->second;
    CHECK_GT(node_size, live_fields.size());
    LOG(INFO) << node->toString() << " eliminated " << node_size - live_fields.size()
              << " columns.";
    std::vector<size_t> ordered_indices(live_fields.begin(), live_fields.end());
    std::sort(ordered_indices.begin(), ordered_indices.end());
    for (size_t i = 0; i < ordered_indices.size(); ++i) {
      new_indices.insert(std::make_pair(ordered_indices[i], i));
    }
    return;
  }
  std::vector<size_t> ordered_indices;
  for (size_t i = 0, old_base = 0, new_base = 0; i < node->inputCount(); ++i) {
    auto src = node->getInput(i);
    auto src_renum_it = new_liveouts.find(src);
    if (src_renum_it != new_liveouts.end()) {
      for (auto m : src_renum_it->second) {
        new_indices.insert(std::make_pair(old_base + m.first, new_base + m.second));
      }
      new_base += src_renum_it->second.size();
    } else if (dynamic_cast<const RelScan*>(src) || intact_nodes.count(src)) {
      for (size_t i = 0; i < src->size(); ++i) {
        new_indices.insert(std::make_pair(old_base + i, new_base + i));
      }
      new_base += src->size();
    } else {
      CHECK(false);
    }
    auto src_sz_it = orig_node_sizes.find(src);
    CHECK(src_sz_it != orig_node_sizes.end());
    old_base += src_sz_it->second;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

any_dead_col_in()

bool anonymous_namespace{RelAlgOptimizer.cpp}::any_dead_col_in	(	const RelAlgNode *	node,
		const std::unordered_set< size_t > &	live_outs
	)

Definition at line 745 of file RelAlgOptimizer.cpp.

References CHECK, and RelAlgNode::size().

Referenced by eliminate_dead_columns(), and try_insert_coalesceable_proj().

                                                                {
  CHECK(!dynamic_cast<const RelScan*>(node));
  if (auto aggregate = dynamic_cast<const RelAggregate*>(node)) {
    for (size_t i = aggregate->getGroupByCount(); i < aggregate->size(); ++i) {
      if (!live_outs.count(i)) {
        return true;
      }
    }
    return false;
  }

  return node->size() > live_outs.size();
}

Here is the call graph for this function:

Here is the caller graph for this function:

cleanup_dead_nodes()

void anonymous_namespace{RelAlgOptimizer.cpp}::cleanup_dead_nodes

(

std::vector< std::shared_ptr< RelAlgNode >> &

nodes

)

Definition at line 327 of file RelAlgOptimizer.cpp.

References logger::INFO, and LOG.

Referenced by eliminate_identical_copy(), and fold_filters().

                                                                     {
  for (auto nodeIt = nodes.rbegin(); nodeIt != nodes.rend(); ++nodeIt) {
    if (nodeIt->use_count() == 1) {
      LOG(INFO) << "ID=" << (*nodeIt)->getId() << " " << (*nodeIt)->toString()
                << " deleted!";
      nodeIt->reset();
    }
  }

  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 caller graph for this function:

does_redef_cols()

bool anonymous_namespace{RelAlgOptimizer.cpp}::does_redef_cols

(

const RelAlgNode *

node

)

Definition at line 760 of file RelAlgOptimizer.cpp.

Referenced by add_new_indices_for(), eliminate_dead_columns(), propagate_input_renumbering(), sweep_dead_columns(), and try_insert_coalesceable_proj().

                                             {
  return dynamic_cast<const RelAggregate*>(node) || dynamic_cast<const RelProject*>(node);
}

Here is the caller graph for this function:

get_actual_source_size()

size_t anonymous_namespace{RelAlgOptimizer.cpp}::get_actual_source_size	(	const RelProject *	curr_project,
		const std::unordered_set< const RelProject *> &	projects_to_remove
	)

Definition at line 98 of file RelAlgOptimizer.cpp.

References RelAlgNode::getInput(), and RelAlgNode::size().

Referenced by is_identical_copy().

                                                                   {
  auto source = curr_project->getInput(0);
  while (auto filter = dynamic_cast<const RelFilter*>(source)) {
    source = filter->getInput(0);
  }
  if (auto src_project = dynamic_cast<const RelProject*>(source)) {
    if (projects_to_remove.count(src_project)) {
      return get_actual_source_size(src_project, projects_to_remove);
    }
  }
  return curr_project->getInput(0)->size();
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_field_name()

std::string anonymous_namespace{RelAlgOptimizer.cpp}::get_field_name	(	const RelAlgNode *	node,
		size_t	index
	)

Definition at line 960 of file RelAlgOptimizer.cpp.

References CHECK, CHECK_EQ, CHECK_LT, RelAlgNode::getInput(), join(), and RelAlgNode::size().

Referenced by try_insert_coalesceable_proj().

                                                               {
  CHECK_LT(index, node->size());
  if (auto scan = dynamic_cast<const RelScan*>(node)) {
    return scan->getFieldName(index);
  }
  if (auto aggregate = dynamic_cast<const RelAggregate*>(node)) {
    CHECK_EQ(aggregate->size(), aggregate->getFields().size());
    return aggregate->getFieldName(index);
  }
  if (auto join = dynamic_cast<const RelJoin*>(node)) {
    const auto lhs_size = join->getInput(0)->size();
    if (index < lhs_size) {
      return get_field_name(join->getInput(0), index);
    }
    return get_field_name(join->getInput(1), index - lhs_size);
  }
  if (auto project = dynamic_cast<const RelProject*>(node)) {
    return project->getFieldName(index);
  }
  CHECK(dynamic_cast<const RelSort*>(node) || dynamic_cast<const RelFilter*>(node));
  return get_field_name(node->getInput(0), index);
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_live_ins()

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
	)

Definition at line 622 of file RelAlgOptimizer.cpp.

References CHECK, CHECK_EQ, CHECK_LT, join(), pick_always_live_col_idx(), run_benchmark_import::result, gpu_enabled::sort(), and RexVisitorBase< T >::visit().

Referenced by mark_live_columns().

                                                                                    {
  if (!node || dynamic_cast<const RelScan*>(node)) {
    return {};
  }
  RexInputCollector collector(node);
  auto it = live_outs.find(node);
  CHECK(it != live_outs.end());
  auto live_out = it->second;
  if (auto project = dynamic_cast<const RelProject*>(node)) {
    CHECK_EQ(size_t(1), project->inputCount());
    std::unordered_set<size_t> live_in;
    for (const auto& idx : live_out) {
      CHECK_LT(idx, project->size());
      auto partial_in = collector.visit(project->getProjectAt(idx));
      for (auto rex_in : partial_in) {
        live_in.insert(rex_in.getIndex());
      }
    }
    if (project->size() == 1 &&
        dynamic_cast<const RexLiteral*>(project->getProjectAt(0))) {
      CHECK(live_in.empty());
      live_in.insert(pick_always_live_col_idx(project->getInput(0)));
    }
    return {live_in};
  }
  if (auto aggregate = dynamic_cast<const RelAggregate*>(node)) {
    CHECK_EQ(size_t(1), aggregate->inputCount());
    const auto group_key_count = static_cast<size_t>(aggregate->getGroupByCount());
    const auto agg_expr_count = static_cast<size_t>(aggregate->getAggExprsCount());
    std::unordered_set<size_t> live_in;
    for (size_t i = 0; i < group_key_count; ++i) {
      live_in.insert(i);
    }
    bool has_count_star_only{false};
    for (const auto& idx : live_out) {
      if (idx < group_key_count) {
        continue;
      }
      const auto agg_idx = idx - group_key_count;
      CHECK_LT(agg_idx, agg_expr_count);
      const auto& cur_agg_expr = aggregate->getAggExprs()[agg_idx];
      const auto n_operands = cur_agg_expr->size();
      for (size_t i = 0; i < n_operands; ++i) {
        live_in.insert(static_cast<size_t>(cur_agg_expr->getOperand(i)));
      }
      if (n_operands == 0) {
        has_count_star_only = true;
      }
    }
    if (has_count_star_only && !group_key_count) {
      live_in.insert(size_t(0));
    }
    return {live_in};
  }
  if (auto join = dynamic_cast<const RelJoin*>(node)) {
    std::unordered_set<size_t> lhs_live_ins;
    std::unordered_set<size_t> rhs_live_ins;
    CHECK_EQ(size_t(2), join->inputCount());
    auto lhs = join->getInput(0);
    auto rhs = join->getInput(1);
    const auto rhs_idx_base = lhs->size();
    for (const auto idx : live_out) {
      if (idx < rhs_idx_base) {
        lhs_live_ins.insert(idx);
      } else {
        rhs_live_ins.insert(idx - rhs_idx_base);
      }
    }
    auto rex_ins = collector.visit(join->getCondition());
    for (const auto& rex_in : rex_ins) {
      const auto in_idx = static_cast<size_t>(rex_in.getIndex());
      if (rex_in.getSourceNode() == lhs) {
        lhs_live_ins.insert(in_idx);
        continue;
      }
      if (rex_in.getSourceNode() == rhs) {
        rhs_live_ins.insert(in_idx);
        continue;
      }
      CHECK(false);
    }
    return {lhs_live_ins, rhs_live_ins};
  }
  if (auto sort = dynamic_cast<const RelSort*>(node)) {
    CHECK_EQ(size_t(1), sort->inputCount());
    std::unordered_set<size_t> live_in(live_out.begin(), live_out.end());
    for (size_t i = 0; i < sort->collationCount(); ++i) {
      live_in.insert(sort->getCollation(i).getField());
    }
    return {live_in};
  }
  if (auto filter = dynamic_cast<const RelFilter*>(node)) {
    CHECK_EQ(size_t(1), filter->inputCount());
    std::unordered_set<size_t> live_in(live_out.begin(), live_out.end());
    auto rex_ins = collector.visit(filter->getCondition());
    for (const auto& rex_in : rex_ins) {
      live_in.insert(static_cast<size_t>(rex_in.getIndex()));
    }
    return {live_in};
  }
  if (auto table_func = dynamic_cast<const RelTableFunction*>(node)) {
    const auto input_count = table_func->size();
    std::unordered_set<size_t> live_in;
    for (size_t i = 0; i < input_count; i++) {
      live_in.insert(i);
    }

    std::vector<std::unordered_set<size_t>> result;
    // Is the computed result correct in general?
    for (size_t i = table_func->inputCount(); i > 0; i--) {
      result.push_back(live_in);
    }

    return result;
  }
  if (auto logical_union = dynamic_cast<const RelLogicalUnion*>(node)) {
    return std::vector<std::unordered_set<size_t>>(logical_union->inputCount(), live_out);
  }
  return {};
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_visible_projects()

std::unordered_set<const RelProject*> anonymous_namespace{RelAlgOptimizer.cpp}::get_visible_projects

(

const RelAlgNode *

root

)

Definition at line 346 of file RelAlgOptimizer.cpp.

References CHECK, RelAlgNode::getInput(), join(), and RelAlgNode::toString().

Referenced by eliminate_identical_copy().

                                                                                 {
  if (auto project = dynamic_cast<const RelProject*>(root)) {
    return {project};
  }

  if (dynamic_cast<const RelAggregate*>(root) || dynamic_cast<const RelScan*>(root) ||
      dynamic_cast<const RelLogicalValues*>(root) ||
      dynamic_cast<const RelModify*>(root)) {
    return std::unordered_set<const RelProject*>{};
  }

  if (auto join = dynamic_cast<const RelJoin*>(root)) {
    auto lhs_projs = get_visible_projects(join->getInput(0));
    auto rhs_projs = get_visible_projects(join->getInput(1));
    lhs_projs.insert(rhs_projs.begin(), rhs_projs.end());
    return lhs_projs;
  }

  if (auto logical_union = dynamic_cast<const RelLogicalUnion*>(root)) {
    auto projections = get_visible_projects(logical_union->getInput(0));
    for (size_t i = 1; i < logical_union->inputCount(); ++i) {
      auto next = get_visible_projects(logical_union->getInput(i));
      projections.insert(next.begin(), next.end());
    }
    return projections;
  }

  CHECK(dynamic_cast<const RelFilter*>(root) || dynamic_cast<const RelSort*>(root))
      << "root = " << root->toString();
  return get_visible_projects(root->getInput(0));
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_distinct()

bool anonymous_namespace{RelAlgOptimizer.cpp}::is_distinct	(	const size_t	input_idx,
		const RelAlgNode *	node
	)

Definition at line 379 of file RelAlgOptimizer.cpp.

References CHECK, CHECK_EQ, CHECK_LT, RelAlgNode::getInput(), and RelAlgNode::inputCount().

Referenced by Parser::FunctionRef::analyze(), Parser::QuerySpec::analyze(), Analyzer::AggExpr::deep_copy(), eliminate_identical_copy(), Analyzer::AggExpr::get_is_distinct(), Analyzer::Query::get_is_distinct(), Parser::QuerySpec::get_is_distinct(), Analyzer::AggExpr::operator==(), Analyzer::AggExpr::rewrite_with_child_targetlist(), Analyzer::Query::set_is_distinct(), Parser::QuerySpec::to_string(), Analyzer::AggExpr::toString(), and RelAlgTranslator::translateAggregateRex().

                                                                 {
  if (dynamic_cast<const RelFilter*>(node) || dynamic_cast<const RelSort*>(node)) {
    CHECK_EQ(size_t(1), node->inputCount());
    return is_distinct(input_idx, node->getInput(0));
  }
  if (auto aggregate = dynamic_cast<const RelAggregate*>(node)) {
    CHECK_EQ(size_t(1), node->inputCount());
    if (aggregate->getGroupByCount() == 1 && !input_idx) {
      return true;
    }
    if (input_idx < aggregate->getGroupByCount()) {
      return is_distinct(input_idx, node->getInput(0));
    }
    return false;
  }
  if (auto project = dynamic_cast<const RelProject*>(node)) {
    CHECK_LT(input_idx, project->size());
    if (auto input = dynamic_cast<const RexInput*>(project->getProjectAt(input_idx))) {
      CHECK_EQ(size_t(1), node->inputCount());
      return is_distinct(input->getIndex(), project->getInput(0));
    }
    return false;
  }
  CHECK(dynamic_cast<const RelJoin*>(node) || dynamic_cast<const RelScan*>(node));
  return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_identical_copy()

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
	)

Definition at line 130 of file RelAlgOptimizer.cpp.

References CHECK, get_actual_source_size(), RelProject::getProjectAt(), safe_to_redirect(), and RelProject::size().

Referenced by eliminate_identical_copy().

                                                               {
  auto source_size = get_actual_source_size(project, projects_to_remove);
  if (project->size() > source_size) {
    return false;
  }

  if (project->size() < source_size) {
    auto usrs_it = du_web.find(project);
    CHECK(usrs_it != du_web.end());
    bool guard_found = false;
    while (usrs_it->second.size() == size_t(1)) {
      auto only_usr = *usrs_it->second.begin();
      if (dynamic_cast<const RelProject*>(only_usr)) {
        guard_found = true;
        break;
      }
      if (dynamic_cast<const RelAggregate*>(only_usr) ||
          dynamic_cast<const RelSort*>(only_usr) ||
          dynamic_cast<const RelJoin*>(only_usr) ||
          dynamic_cast<const RelTableFunction*>(only_usr) ||
          dynamic_cast<const RelLogicalUnion*>(only_usr)) {
        return false;
      }
      CHECK(dynamic_cast<const RelFilter*>(only_usr))
          << "only_usr: " << only_usr->toString();
      usrs_it = du_web.find(only_usr);
      CHECK(usrs_it != du_web.end());
    }

    if (!guard_found) {
      return false;
    }
  }

  bool identical = true;
  for (size_t i = 0; i < project->size(); ++i) {
    auto target = dynamic_cast<const RexInput*>(project->getProjectAt(i));
    CHECK(target);
    if (i != target->getIndex()) {
      identical = false;
      break;
    }
  }

  if (identical) {
    return true;
  }

  if (safe_to_redirect(project, du_web)) {
    permutating_projects.insert(project);
    return true;
  }

  return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

mark_live_columns()

std::unordered_map<const RelAlgNode*, std::unordered_set<size_t> > anonymous_namespace{RelAlgOptimizer.cpp}::mark_live_columns

(

std::vector< std::shared_ptr< RelAlgNode >> &

nodes

)

Definition at line 906 of file RelAlgOptimizer.cpp.

References CHECK, CHECK_EQ, parse_ast::end, get_live_ins(), and gpu_enabled::iota().

Referenced by eliminate_dead_columns(), and sink_projected_boolean_expr_to_join().

                                                 {
  std::unordered_map<const RelAlgNode*, std::unordered_set<size_t>> live_outs;
  std::vector<const RelAlgNode*> work_set;
  for (auto node_it = nodes.rbegin(); node_it != nodes.rend(); ++node_it) {
    auto node = node_it->get();
    if (dynamic_cast<const RelScan*>(node) || live_outs.count(node) ||
        dynamic_cast<const RelModify*>(node) ||
        dynamic_cast<const RelTableFunction*>(node)) {
      continue;
    }
    std::vector<size_t> all_live(node->size());
    std::iota(all_live.begin(), all_live.end(), size_t(0));
    live_outs.insert(std::make_pair(
        node, std::unordered_set<size_t>(all_live.begin(), all_live.end())));

    work_set.push_back(node);
    while (!work_set.empty()) {
      auto walker = work_set.back();
      work_set.pop_back();
      CHECK(!dynamic_cast<const RelScan*>(walker));
      CHECK(live_outs.count(walker));
      auto live_ins = get_live_ins(walker, live_outs);
      CHECK_EQ(live_ins.size(), walker->inputCount());
      for (size_t i = 0; i < walker->inputCount(); ++i) {
        auto src = walker->getInput(i);
        if (dynamic_cast<const RelScan*>(src) ||
            dynamic_cast<const RelTableFunction*>(src) || live_ins[i].empty()) {
          continue;
        }
        if (!live_outs.count(src)) {
          live_outs.insert(std::make_pair(src, std::unordered_set<size_t>{}));
        }
        auto src_it = live_outs.find(src);
        CHECK(src_it != live_outs.end());
        auto& live_out = src_it->second;
        bool changed = false;
        if (!live_out.empty()) {
          live_out.insert(live_ins[i].begin(), live_ins[i].end());
          changed = true;
        } else {
          for (int idx : live_ins[i]) {
            changed |= live_out.insert(idx).second;
          }
        }
        if (changed) {
          work_set.push_back(src);
        }
      }
    }
  }
  return live_outs;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pick_always_live_col_idx()

size_t anonymous_namespace{RelAlgOptimizer.cpp}::pick_always_live_col_idx

(

const RelAlgNode *

node

)

Definition at line 593 of file RelAlgOptimizer.cpp.

References CHECK, join(), RelAlgNode::size(), and gpu_enabled::sort().

Referenced by get_live_ins().

                                                        {
  CHECK(node->size());
  RexInputCollector collector(node);
  if (auto filter = dynamic_cast<const RelFilter*>(node)) {
    auto rex_ins = collector.visit(filter->getCondition());
    if (!rex_ins.empty()) {
      return static_cast<size_t>(rex_ins.begin()->getIndex());
    }
    return pick_always_live_col_idx(filter->getInput(0));
  } else if (auto join = dynamic_cast<const RelJoin*>(node)) {
    auto rex_ins = collector.visit(join->getCondition());
    if (!rex_ins.empty()) {
      return static_cast<size_t>(rex_ins.begin()->getIndex());
    }
    if (auto lhs_idx = pick_always_live_col_idx(join->getInput(0))) {
      return lhs_idx;
    }
    if (auto rhs_idx = pick_always_live_col_idx(join->getInput(0))) {
      return rhs_idx + join->getInput(0)->size();
    }
  } else if (auto sort = dynamic_cast<const RelSort*>(node)) {
    if (sort->collationCount()) {
      return sort->getCollation(0).getField();
    }
    return pick_always_live_col_idx(sort->getInput(0));
  }
  return size_t(0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

propagate_input_renumbering()

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
	)

Definition at line 1105 of file RelAlgOptimizer.cpp.

References add_new_indices_for(), CHECK, does_redef_cols(), logger::FATAL, anonymous_namespace{RelAlgOptimizer.cpp}::AvailabilityChecker::hasAllSrcReady(), join(), LOG, renumber_rex_aggs(), renumber_sort_field(), gpu_enabled::sort(), and RexVisitorBase< T >::visit().

Referenced by eliminate_dead_columns().

                                                                        {
  RexInputRenumberVisitor renumberer(liveout_renumbering);
  AvailabilityChecker checker(liveout_renumbering, intact_nodes);
  std::deque<const RelAlgNode*> work_set(ready_nodes.begin(), ready_nodes.end());
  while (!work_set.empty()) {
    auto walker = work_set.front();
    work_set.pop_front();
    CHECK(!dynamic_cast<const RelScan*>(walker));
    auto node = const_cast<RelAlgNode*>(walker);
    if (auto project = dynamic_cast<RelProject*>(node)) {
      auto old_exprs = project->getExpressionsAndRelease();
      std::vector<std::unique_ptr<const RexScalar>> new_exprs;
      for (auto& expr : old_exprs) {
        new_exprs.push_back(renumberer.visit(expr.get()));
      }
      project->setExpressions(new_exprs);
    } else if (auto aggregate = dynamic_cast<RelAggregate*>(node)) {
      auto src_it = liveout_renumbering.find(node->getInput(0));
      CHECK(src_it != liveout_renumbering.end());
      auto old_exprs = aggregate->getAggExprsAndRelease();
      auto new_exprs = renumber_rex_aggs(old_exprs, src_it->second);
      aggregate->setAggExprs(new_exprs);
    } else if (auto join = dynamic_cast<RelJoin*>(node)) {
      auto new_condition = renumberer.visit(join->getCondition());
      join->setCondition(new_condition);
    } else if (auto filter = dynamic_cast<RelFilter*>(node)) {
      auto new_condition = renumberer.visit(filter->getCondition());
      filter->setCondition(new_condition);
    } else if (auto sort = dynamic_cast<RelSort*>(node)) {
      auto src_it = liveout_renumbering.find(node->getInput(0));
      CHECK(src_it != liveout_renumbering.end());
      std::vector<SortField> new_collations;
      for (size_t i = 0; i < sort->collationCount(); ++i) {
        new_collations.push_back(
            renumber_sort_field(sort->getCollation(i), src_it->second));
      }
      sort->setCollation(std::move(new_collations));
    } else if (!dynamic_cast<RelLogicalUnion*>(node)) {
      LOG(FATAL) << "Unhandled node type: " << node->toString();
    }

    // Ignore empty live_out due to some invalid node
    if (does_redef_cols(node) || intact_nodes.count(node)) {
      continue;
    }
    auto live_pair = old_liveouts.find(node);
    CHECK(live_pair != old_liveouts.end());
    auto live_out = live_pair->second;
    add_new_indices_for(
        node, liveout_renumbering, live_out, intact_nodes, orig_node_sizes);
    auto usrs_it = du_web.find(walker);
    CHECK(usrs_it != du_web.end());
    for (auto usr : usrs_it->second) {
      if (checker.hasAllSrcReady(usr)) {
        work_set.push_back(usr);
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

propagate_rex_input_renumber()

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
	)

Definition at line 191 of file RelAlgOptimizer.cpp.

References CHECK, and RelAlgNode::getInput().

Referenced by redirect_inputs_of().

                {
  CHECK(excluded_root);
  auto src_project = dynamic_cast<const RelProject*>(excluded_root->getInput(0));
  CHECK(src_project && src_project->isSimple());
  const auto indirect_join_src = dynamic_cast<const RelJoin*>(src_project->getInput(0));
  std::unordered_map<size_t, size_t> old_to_new_idx;
  for (size_t i = 0; i < src_project->size(); ++i) {
    auto rex_in = dynamic_cast<const RexInput*>(src_project->getProjectAt(i));
    CHECK(rex_in);
    size_t src_base = 0;
    if (indirect_join_src != nullptr &&
        indirect_join_src->getInput(1) == rex_in->getSourceNode()) {
      src_base = indirect_join_src->getInput(0)->size();
    }
    old_to_new_idx.insert(std::make_pair(i, src_base + rex_in->getIndex()));
    old_to_new_idx.insert(std::make_pair(i, rex_in->getIndex()));
  }
  CHECK(old_to_new_idx.size());
  RexInputRenumber<false> renumber(old_to_new_idx);
  auto usrs_it = du_web.find(excluded_root);
  CHECK(usrs_it != du_web.end());
  std::vector<const RelAlgNode*> work_set(usrs_it->second.begin(), usrs_it->second.end());
  while (!work_set.empty()) {
    auto node = work_set.back();
    work_set.pop_back();
    auto modified_node = const_cast<RelAlgNode*>(node);
    if (auto filter = dynamic_cast<RelFilter*>(modified_node)) {
      auto new_condition = renumber.visit(filter->getCondition());
      filter->setCondition(new_condition);
      auto usrs_it = du_web.find(filter);
      CHECK(usrs_it != du_web.end() && usrs_it->second.size() == 1);
      work_set.push_back(*usrs_it->second.begin());
      continue;
    }
    if (auto project = dynamic_cast<RelProject*>(modified_node)) {
      std::vector<std::unique_ptr<const RexScalar>> new_exprs;
      for (size_t i = 0; i < project->size(); ++i) {
        new_exprs.push_back(renumber.visit(project->getProjectAt(i)));
      }
      project->setExpressions(new_exprs);
      continue;
    }
    CHECK(false);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

redirect_inputs_of()

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
	)

Definition at line 241 of file RelAlgOptimizer.cpp.

References CHECK, join(), propagate_rex_input_renumber(), RexVisitorBase< T >::visit(), and anonymous_namespace{RelAlgOptimizer.cpp}::RexRebindInputsVisitor::visitNode().

Referenced by eliminate_identical_copy().

                {
  if (dynamic_cast<RelLogicalUnion*>(node.get())) {
    return;  // UNION keeps all Projection inputs.
  }
  std::shared_ptr<const RelProject> src_project = nullptr;
  for (size_t i = 0; i < node->inputCount(); ++i) {
    if (auto project =
            std::dynamic_pointer_cast<const RelProject>(node->getAndOwnInput(i))) {
      if (projects.count(project.get())) {
        src_project = project;
        break;
      }
    }
  }
  if (!src_project) {
    return;
  }
  if (auto join = std::dynamic_pointer_cast<RelJoin>(node)) {
    auto other_project =
        src_project == node->getAndOwnInput(0)
            ? std::dynamic_pointer_cast<const RelProject>(node->getAndOwnInput(1))
            : std::dynamic_pointer_cast<const RelProject>(node->getAndOwnInput(0));
    join->replaceInput(src_project, src_project->getAndOwnInput(0));
    RexRebindInputsVisitor rebinder(src_project.get(), src_project->getInput(0));
    auto usrs_it = du_web.find(join.get());
    CHECK(usrs_it != du_web.end());
    for (auto usr : usrs_it->second) {
      rebinder.visitNode(usr);
    }

    if (other_project && projects.count(other_project.get())) {
      join->replaceInput(other_project, other_project->getAndOwnInput(0));
      RexRebindInputsVisitor other_rebinder(other_project.get(),
                                            other_project->getInput(0));
      for (auto usr : usrs_it->second) {
        other_rebinder.visitNode(usr);
      }
    }
    return;
  }
  if (auto project = std::dynamic_pointer_cast<RelProject>(node)) {
    project->RelAlgNode::replaceInput(src_project, src_project->getAndOwnInput(0));
    RexProjectInputRedirector redirector(projects);
    std::vector<std::unique_ptr<const RexScalar>> new_exprs;
    for (size_t i = 0; i < project->size(); ++i) {
      new_exprs.push_back(redirector.visit(project->getProjectAt(i)));
    }
    project->setExpressions(new_exprs);
    return;
  }
  if (auto filter = std::dynamic_pointer_cast<RelFilter>(node)) {
    const bool is_permutating_proj = permutating_projects.count(src_project.get());
    if (is_permutating_proj || dynamic_cast<const RelJoin*>(src_project->getInput(0))) {
      if (is_permutating_proj) {
        propagate_rex_input_renumber(filter.get(), du_web);
      }
      filter->RelAlgNode::replaceInput(src_project, src_project->getAndOwnInput(0));
      RexProjectInputRedirector redirector(projects);
      auto new_condition = redirector.visit(filter->getCondition());
      filter->setCondition(new_condition);
    } else {
      filter->replaceInput(src_project, src_project->getAndOwnInput(0));
    }
    return;
  }
  if (std::dynamic_pointer_cast<RelSort>(node)) {
    auto const src_project_input = src_project->getInput(0);
    if (dynamic_cast<const RelScan*>(src_project_input) ||
        dynamic_cast<const RelLogicalValues*>(src_project_input) ||
        dynamic_cast<const RelLogicalUnion*>(src_project_input)) {
      return;
    }
  }
  if (std::dynamic_pointer_cast<RelModify>(node)) {
    return;  // NOTE:  Review this.  Not sure about this.
  }
  CHECK(std::dynamic_pointer_cast<RelAggregate>(node) ||
        std::dynamic_pointer_cast<RelSort>(node));
  node->replaceInput(src_project, src_project->getAndOwnInput(0));
}

Here is the call graph for this function:

Here is the caller graph for this function:

renumber_rex_aggs()

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
	)

Definition at line 872 of file RelAlgOptimizer.cpp.

Referenced by propagate_input_renumbering().

                                                           {
  std::vector<std::unique_ptr<const RexAgg>> new_exprs;
  for (auto& expr : agg_exprs) {
    if (expr->size() >= 1) {
      auto old_idx = expr->getOperand(0);
      auto idx_it = new_numbering.find(old_idx);
      if (idx_it != new_numbering.end()) {
        std::vector<size_t> operands;
        operands.push_back(idx_it->second);
        if (expr->size() == 2) {
          operands.push_back(expr->getOperand(1));
        }
        new_exprs.push_back(boost::make_unique<RexAgg>(
            expr->getKind(), expr->isDistinct(), expr->getType(), operands));
        continue;
      }
    }
    new_exprs.push_back(std::move(expr));
  }
  return new_exprs;
}

Here is the caller graph for this function:

renumber_sort_field()

SortField anonymous_namespace{RelAlgOptimizer.cpp}::renumber_sort_field	(	const SortField &	old_field,
		const std::unordered_map< size_t, size_t > &	new_numbering
	)

Definition at line 896 of file RelAlgOptimizer.cpp.

References SortField::getField(), SortField::getNullsPosition(), and SortField::getSortDir().

Referenced by propagate_input_renumbering().

                                                                                     {
  auto field_idx = old_field.getField();
  auto idx_it = new_numbering.find(field_idx);
  if (idx_it != new_numbering.end()) {
    field_idx = idx_it->second;
  }
  return SortField(field_idx, old_field.getSortDir(), old_field.getNullsPosition());
}

Here is the call graph for this function:

Here is the caller graph for this function:

replace_all_usages()

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
	)

Definition at line 1433 of file RelAlgOptimizer.cpp.

References CHECK.

Referenced by fold_filters().

                {
  auto usrs_it = du_web.find(old_def_node.get());
  RexInputRedirector redirector(new_def_node.get(), old_def_node.get());
  CHECK(usrs_it != du_web.end());
  for (auto usr : usrs_it->second) {
    auto usr_it = deconst_mapping.find(usr);
    CHECK(usr_it != deconst_mapping.end());
    usr_it->second->replaceInput(old_def_node, new_def_node);
  }
  auto new_usrs_it = du_web.find(new_def_node.get());
  CHECK(new_usrs_it != du_web.end());
  new_usrs_it->second.insert(usrs_it->second.begin(), usrs_it->second.end());
  usrs_it->second.clear();
}

Here is the caller graph for this function:

safe_to_redirect()

bool anonymous_namespace{RelAlgOptimizer.cpp}::safe_to_redirect	(	const RelProject *	project,
		const std::unordered_map< const RelAlgNode *, std::unordered_set< const RelAlgNode *>> &	du_web
	)

Definition at line 113 of file RelAlgOptimizer.cpp.

References CHECK, and RelProject::isSimple().

Referenced by is_identical_copy().

                {
  if (!project->isSimple()) {
    return false;
  }
  auto usrs_it = du_web.find(project);
  CHECK(usrs_it != du_web.end());
  for (auto usr : usrs_it->second) {
    if (!dynamic_cast<const RelProject*>(usr) && !dynamic_cast<const RelFilter*>(usr)) {
      return false;
    }
  }
  return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

sweep_dead_columns()

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
	)

Definition at line 1042 of file RelAlgOptimizer.cpp.

References add_new_indices_for(), CHECK, does_redef_cols(), and anonymous_namespace{RelAlgOptimizer.cpp}::AvailabilityChecker::hasAllSrcReady().

Referenced by eliminate_dead_columns().

                                                                        {
  std::unordered_map<const RelAlgNode*, std::unordered_map<size_t, size_t>>
      liveouts_renumbering;
  std::vector<const RelAlgNode*> ready_nodes;
  AvailabilityChecker checker(liveouts_renumbering, intact_nodes);
  for (auto node : nodes) {
    // Ignore empty live_out due to some invalid node
    if (!does_redef_cols(node.get()) || intact_nodes.count(node.get())) {
      continue;
    }
    auto live_pair = live_outs.find(node.get());
    CHECK(live_pair != live_outs.end());
    auto old_live_outs = live_pair->second;
    add_new_indices_for(
        node.get(), liveouts_renumbering, old_live_outs, intact_nodes, orig_node_sizes);
    if (auto aggregate = std::dynamic_pointer_cast<RelAggregate>(node)) {
      auto old_exprs = aggregate->getAggExprsAndRelease();
      std::vector<std::unique_ptr<const RexAgg>> new_exprs;
      auto key_name_it = aggregate->getFields().begin();
      std::vector<std::string> new_fields(key_name_it,
                                          key_name_it + aggregate->getGroupByCount());
      for (size_t i = aggregate->getGroupByCount(), j = 0;
           i < aggregate->getFields().size() && j < old_exprs.size();
           ++i, ++j) {
        if (old_live_outs.count(i)) {
          new_exprs.push_back(std::move(old_exprs[j]));
          new_fields.push_back(aggregate->getFieldName(i));
        }
      }
      aggregate->setAggExprs(new_exprs);
      aggregate->setFields(new_fields);
    } else if (auto project = std::dynamic_pointer_cast<RelProject>(node)) {
      auto old_exprs = project->getExpressionsAndRelease();
      std::vector<std::unique_ptr<const RexScalar>> new_exprs;
      std::vector<std::string> new_fields;
      for (size_t i = 0; i < old_exprs.size(); ++i) {
        if (old_live_outs.count(i)) {
          new_exprs.push_back(std::move(old_exprs[i]));
          new_fields.push_back(project->getFieldName(i));
        }
      }
      project->setExpressions(new_exprs);
      project->setFields(new_fields);
    } else {
      CHECK(false);
    }
    auto usrs_it = du_web.find(node.get());
    CHECK(usrs_it != du_web.end());
    for (auto usr : usrs_it->second) {
      if (checker.hasAllSrcReady(usr)) {
        ready_nodes.push_back(usr);
      }
    }
  }
  return {liveouts_renumbering, ready_nodes};
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_insert_coalesceable_proj()

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
	)

Definition at line 983 of file RelAlgOptimizer.cpp.

References any_dead_col_in(), CHECK, does_redef_cols(), get_field_name(), RelAlgNode::replaceInput(), and anonymous_namespace{RelAlgOptimizer.cpp}::RexRebindInputsVisitor::visitNode().

Referenced by eliminate_dead_columns().

                {
  std::vector<std::shared_ptr<RelAlgNode>> new_nodes;
  for (auto node : nodes) {
    new_nodes.push_back(node);
    if (!std::dynamic_pointer_cast<RelFilter>(node)) {
      continue;
    }
    const auto filter = node.get();
    auto liveout_it = liveouts.find(filter);
    CHECK(liveout_it != liveouts.end());
    auto& outs = liveout_it->second;
    if (!any_dead_col_in(filter, outs)) {
      continue;
    }
    auto usrs_it = du_web.find(filter);
    CHECK(usrs_it != du_web.end());
    auto& usrs = usrs_it->second;
    if (usrs.size() != 1 || does_redef_cols(*usrs.begin())) {
      continue;
    }
    auto only_usr = const_cast<RelAlgNode*>(*usrs.begin());

    std::vector<std::unique_ptr<const RexScalar>> exprs;
    std::vector<std::string> fields;
    for (size_t i = 0; i < filter->size(); ++i) {
      exprs.push_back(boost::make_unique<RexInput>(filter, i));
      fields.push_back(get_field_name(filter, i));
    }
    auto project_owner = std::make_shared<RelProject>(exprs, fields, node);
    auto project = project_owner.get();

    only_usr->replaceInput(node, project_owner);
    if (dynamic_cast<const RelJoin*>(only_usr)) {
      RexRebindInputsVisitor visitor(filter, project);
      for (auto usr : du_web[only_usr]) {
        visitor.visitNode(usr);
      }
    }

    liveouts.insert(std::make_pair(project, outs));

    usrs.clear();
    usrs.insert(project);
    du_web.insert(
        std::make_pair(project, std::unordered_set<const RelAlgNode*>{only_usr}));

    new_nodes.push_back(project_owner);
  }
  if (new_nodes.size() > nodes.size()) {
    nodes.swap(new_nodes);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function: