ExpressionRewrite.cpp File Reference

#include "QueryEngine/ExpressionRewrite.h"
#include <algorithm>
#include <boost/locale/conversion.hpp>
#include <unordered_set>
#include "Analyzer/Analyzer.h"
#include "Logger/Logger.h"
#include "Parser/ParserNode.h"
#include "QueryEngine/DeepCopyVisitor.h"
#include "QueryEngine/Execute.h"
#include "QueryEngine/RelAlgTranslator.h"
#include "QueryEngine/ScalarExprVisitor.h"
#include "QueryEngine/WindowExpressionRewrite.h"
#include "Shared/sqldefs.h"

Include dependency graph for ExpressionRewrite.cpp:

Go to the source code of this file.

Classes
class	anonymous_namespace{ExpressionRewrite.cpp}::OrToInVisitor
class	anonymous_namespace{ExpressionRewrite.cpp}::RecursiveOrToInVisitor
class	anonymous_namespace{ExpressionRewrite.cpp}::ArrayElementStringLiteralEncodingVisitor
class	anonymous_namespace{ExpressionRewrite.cpp}::ConstantFoldingVisitor
class	JoinCoveredQualVisitor

Namespaces
	anonymous_namespace{ExpressionRewrite.cpp}

Functions
const Analyzer::Expr *	anonymous_namespace{ExpressionRewrite.cpp}::strip_likelihood (const Analyzer::Expr *expr)
Analyzer::ExpressionPtr	rewrite_array_elements (Analyzer::Expr const *expr)
Analyzer::ExpressionPtr	rewrite_expr (const Analyzer::Expr *expr)
boost::optional < OverlapsJoinConjunction >	rewrite_overlaps_conjunction (const std::shared_ptr< Analyzer::Expr > expr)
std::list< std::shared_ptr < Analyzer::Expr > >	strip_join_covered_filter_quals (const std::list< std::shared_ptr< Analyzer::Expr >> &quals, const JoinQualsPerNestingLevel &join_quals)
std::shared_ptr< Analyzer::Expr >	fold_expr (const Analyzer::Expr *expr)
bool	self_join_not_covered_by_left_deep_tree (const Analyzer::ColumnVar *key_side, const Analyzer::ColumnVar *val_side, const int max_rte_covered)
const int	get_max_rte_scan_table (std::unordered_map< int, llvm::Value * > &scan_idx_to_hash_pos)

Variables
static const std::unordered_set < std::string >	anonymous_namespace{ExpressionRewrite.cpp}::overlaps_supported_functions
static const std::unordered_set < std::string >	anonymous_namespace{ExpressionRewrite.cpp}::requires_many_to_many

Function Documentation

std::shared_ptr<Analyzer::Expr> fold_expr

(

const Analyzer::Expr *

expr

)

Definition at line 992 of file ExpressionRewrite.cpp.

References kBIGINT, and anonymous_namespace{ExpressionRewrite.cpp}::strip_likelihood().

Referenced by RelAlgExecutor::createFilterWorkUnit(), anonymous_namespace{RelAlgExecutor.cpp}::set_transient_dict_maybe(), anonymous_namespace{RelAlgExecutor.cpp}::translate_quals(), anonymous_namespace{RelAlgExecutor.cpp}::translate_scalar_sources(), anonymous_namespace{RelAlgExecutor.cpp}::translate_targets(), RelAlgTranslator::translateBinaryGeoFunction(), RelAlgTranslator::translateDatePlusMinus(), RelAlgTranslator::translateGeoComparison(), and RelAlgTranslator::translateGeoFunctionArg().

                                                                {
  if (!expr) {
    return nullptr;
  }
  const auto expr_no_likelihood = strip_likelihood(expr);
  ConstantFoldingVisitor visitor;
  auto rewritten_expr = visitor.visit(expr_no_likelihood);
  if (visitor.get_num_overflows() > 0 && rewritten_expr->get_type_info().is_integer() &&
      rewritten_expr->get_type_info().get_type() != kBIGINT) {
    auto rewritten_expr_const =
        std::dynamic_pointer_cast<const Analyzer::Constant>(rewritten_expr);
    if (!rewritten_expr_const) {
      // Integer expression didn't fold completely the first time due to
      // overflows in smaller type subexpressions, trying again with a cast
      const auto& ti = SQLTypeInfo(kBIGINT, false);
      auto bigint_expr_no_likelihood = expr_no_likelihood->deep_copy()->add_cast(ti);
      auto rewritten_expr_take2 = visitor.visit(bigint_expr_no_likelihood.get());
      auto rewritten_expr_take2_const =
          std::dynamic_pointer_cast<Analyzer::Constant>(rewritten_expr_take2);
      if (rewritten_expr_take2_const) {
        // Managed to fold, switch to the new constant
        rewritten_expr = rewritten_expr_take2_const;
      }
    }
  }
  const auto expr_with_likelihood = dynamic_cast<const Analyzer::LikelihoodExpr*>(expr);
  if (expr_with_likelihood) {
    // Add back likelihood
    return std::make_shared<Analyzer::LikelihoodExpr>(
        rewritten_expr, expr_with_likelihood->get_likelihood());
  }
  return rewritten_expr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const int get_max_rte_scan_table

(

std::unordered_map< int, llvm::Value * > &

scan_idx_to_hash_pos

)

Definition at line 1037 of file ExpressionRewrite.cpp.

References INT32_MIN.

Referenced by BaselineJoinHashTable::codegenKey(), PerfectJoinHashTable::codegenMatchingSet(), and PerfectJoinHashTable::codegenSlot().

                                                             {
  int ret = INT32_MIN;
  for (auto& kv : scan_idx_to_hash_pos) {
    if (kv.first > ret) {
      ret = kv.first;
    }
  }
  return ret;
}

Here is the caller graph for this function:

Analyzer::ExpressionPtr rewrite_array_elements

(

Analyzer::Expr const *

expr

)

Definition at line 699 of file ExpressionRewrite.cpp.

Referenced by anonymous_namespace{RelAlgExecutor.cpp}::translate_scalar_sources(), and anonymous_namespace{RelAlgExecutor.cpp}::translate_scalar_sources_for_update().

                                                                       {
  return ArrayElementStringLiteralEncodingVisitor().visit(expr);
}

Here is the caller graph for this function:

Analyzer::ExpressionPtr rewrite_expr

(

const Analyzer::Expr *

expr

)

Definition at line 703 of file ExpressionRewrite.cpp.

References rewrite_avg_window(), rewrite_sum_window(), and anonymous_namespace{ExpressionRewrite.cpp}::strip_likelihood().

Referenced by RelAlgExecutor::createFilterWorkUnit(), qual_to_conjunctive_form(), qual_to_disjunctive_form(), anonymous_namespace{RelAlgExecutor.cpp}::rewrite_quals(), QueryRewriter::rewriteConstrainedByIn(), anonymous_namespace{RelAlgExecutor.cpp}::translate_scalar_sources(), anonymous_namespace{RelAlgExecutor.cpp}::translate_scalar_sources_for_update(), and anonymous_namespace{RelAlgExecutor.cpp}::translate_targets().

                                                             {
  const auto sum_window = rewrite_sum_window(expr);
  if (sum_window) {
    return sum_window;
  }
  const auto avg_window = rewrite_avg_window(expr);
  if (avg_window) {
    return avg_window;
  }
  const auto expr_no_likelihood = strip_likelihood(expr);
  // The following check is not strictly needed, but seems silly to transform a
  // simple string comparison to an IN just to codegen the same thing anyway.

  RecursiveOrToInVisitor visitor;
  auto rewritten_expr = visitor.visit(expr_no_likelihood);
  const auto expr_with_likelihood =
      std::dynamic_pointer_cast<const Analyzer::LikelihoodExpr>(rewritten_expr);
  if (expr_with_likelihood) {
    // Add back likelihood
    return std::make_shared<Analyzer::LikelihoodExpr>(
        rewritten_expr, expr_with_likelihood->get_likelihood());
  }
  return rewritten_expr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boost::optional<OverlapsJoinConjunction> rewrite_overlaps_conjunction

(

const std::shared_ptr< Analyzer::Expr >

expr

)

Definition at line 760 of file ExpressionRewrite.cpp.

References CHECK, CHECK_EQ, CHECK_GE, g_enable_distance_rangejoin, g_enable_hashjoin_many_to_many, logger::INFO, is_constructed_point(), kBOOLEAN, kGEOGRAPHY, kLE, kLT, kONE, kOVERLAPS, LOG, anonymous_namespace{ExpressionRewrite.cpp}::overlaps_supported_functions, anonymous_namespace{ExpressionRewrite.cpp}::requires_many_to_many, ScalarExprVisitor< T >::visit(), VLOG, and logger::WARNING.

Referenced by QueryRewriter::rewriteOverlapsJoin().

                                            {
  auto func_oper = dynamic_cast<Analyzer::FunctionOper*>(expr.get());
  if (func_oper) {
    const auto needs_many_many = [func_oper]() {
      return requires_many_to_many.find(func_oper->getName()) !=
             requires_many_to_many.end();
    };
    // TODO(adb): consider converting unordered set to an unordered map, potentially
    // storing the rewrite function we want to apply in the map
    if (overlaps_supported_functions.find(func_oper->getName()) !=
        overlaps_supported_functions.end()) {
      if (!g_enable_hashjoin_many_to_many && needs_many_many()) {
        LOG(WARNING) << "Many-to-many hashjoin support is disabled, unable to rewrite "
                     << func_oper->toString() << " to use accelerated geo join.";
        return boost::none;
      }

      DeepCopyVisitor deep_copy_visitor;
      if (func_oper->getName() == "ST_Overlaps") {
        CHECK_GE(func_oper->getArity(), size_t(2));
        // return empty quals, overlaps join quals
        // TODO(adb): we will likely want to actually check for true overlaps, but this
        // works for now

        auto lhs = func_oper->getOwnArg(0);
        auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
        CHECK(rewritten_lhs);

        auto rhs = func_oper->getOwnArg(1);
        auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
        CHECK(rewritten_rhs);

        auto overlaps_oper = makeExpr<Analyzer::BinOper>(
            kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);
        return OverlapsJoinConjunction{{}, {overlaps_oper}};
      }

      // TODO(jclay): This will work for Poly_Poly,but needs to change for others.
      CHECK_GE(func_oper->getArity(), size_t(4));
      if (func_oper->getName() == "ST_Contains_Polygon_Polygon" ||
          func_oper->getName() == "ST_Intersects_Polygon_Polygon" ||
          func_oper->getName() == "ST_Intersects_MultiPolygon_MultiPolygon" ||
          func_oper->getName() == "ST_Intersects_MultiPolygon_Polygon" ||
          func_oper->getName() == "ST_Intersects_Polygon_MultiPolygon") {
        auto lhs = func_oper->getOwnArg(3);
        auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
        CHECK(rewritten_lhs);
        auto rhs = func_oper->getOwnArg(1);
        auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
        CHECK(rewritten_rhs);

        auto overlaps_oper = makeExpr<Analyzer::BinOper>(
            kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);

        VLOG(1) << "Successfully converted to overlaps join";
        return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
      }

      auto lhs = func_oper->getOwnArg(2);
      auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
      CHECK(rewritten_lhs);
      const auto& lhs_ti = rewritten_lhs->get_type_info();

      if (!lhs_ti.is_geometry() && !is_constructed_point(rewritten_lhs.get())) {
        // TODO(adb): If ST_Contains is passed geospatial literals instead of columns, the
        // function will be expanded during translation rather than during code
        // generation. While this scenario does not make sense for the overlaps join, we
        // need to detect and abort the overlaps rewrite. Adding a GeospatialConstant
        // dervied class to the Analyzer may prove to be a better way to handle geo
        // literals, but for now we ensure the LHS type is a geospatial type, which would
        // mean the function has not been expanded to the physical types, yet.

        LOG(INFO) << "Unable to rewrite " << func_oper->getName()
                  << " to overlaps conjunction. LHS input type is neither a geospatial "
                     "column nor a constructed point\n"
                  << func_oper->toString();

        return boost::none;
      }

      // Read the bounds arg from the ST_Contains FuncOper (second argument)instead of the
      // poly column (first argument)
      auto rhs = func_oper->getOwnArg(1);
      auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
      CHECK(rewritten_rhs);

      // Check for compatible join ordering. If the join ordering does not match expected
      // ordering for overlaps, the join builder will fail.
      std::set<int> lhs_rte_idx;
      lhs->collect_rte_idx(lhs_rte_idx);
      CHECK(!lhs_rte_idx.empty());
      std::set<int> rhs_rte_idx;
      rhs->collect_rte_idx(rhs_rte_idx);
      CHECK(!rhs_rte_idx.empty());

      if (lhs_rte_idx.size() > 1 || rhs_rte_idx.size() > 1 || lhs_rte_idx > rhs_rte_idx) {
        LOG(INFO) << "Unable to rewrite " << func_oper->getName()
                  << " to overlaps conjunction. Cannot build hash table over LHS type. "
                     "Check join order.\n"
                  << func_oper->toString();
        return boost::none;
      }

      VLOG(1) << "Rewritten to use overlaps join with lhs as "
              << rewritten_lhs->toString() << " and rhs as " << rewritten_rhs->toString();

      auto overlaps_oper = makeExpr<Analyzer::BinOper>(
          kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);

      VLOG(1) << "Successfully converted to overlaps join";
      if (func_oper->getName() == "ST_Approx_Overlaps_MultiPolygon_Point"sv) {
        return OverlapsJoinConjunction{{}, {overlaps_oper}};
      } else {
        return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
      }
    } else {
      VLOG(1) << "Overlaps join not enabled for " << func_oper->getName();
    }
    return boost::none;
  }
  auto bin_oper = dynamic_cast<Analyzer::BinOper*>(expr.get());
  if (g_enable_distance_rangejoin && bin_oper &&
      (bin_oper->get_optype() == kLE || bin_oper->get_optype() == kLT)) {
    auto lhs = dynamic_cast<const Analyzer::GeoOperator*>(bin_oper->get_left_operand());
    auto rhs = dynamic_cast<const Analyzer::Constant*>(bin_oper->get_right_operand());
    if (lhs && rhs && lhs->getName() == "ST_Distance") {
      CHECK_EQ(lhs->size(), size_t(2));
      auto l_arg = lhs->getOperand(0);
      auto r_arg = lhs->getOperand(1);
      const bool is_geography = l_arg->get_type_info().get_subtype() == kGEOGRAPHY ||
                                r_arg->get_type_info().get_subtype() == kGEOGRAPHY;
      if (is_geography) {
        VLOG(1) << "Range join not yet supported for geodesic distance "
                << bin_oper->toString();
        return boost::none;
      }

      // Check for compatible join ordering. If the join ordering does not match expected
      // ordering for overlaps, the join builder will fail.
      std::set<int> lhs_rte_idx;
      l_arg->collect_rte_idx(lhs_rte_idx);
      CHECK(!lhs_rte_idx.empty());
      std::set<int> rhs_rte_idx;
      r_arg->collect_rte_idx(rhs_rte_idx);
      CHECK(!rhs_rte_idx.empty());

      if (lhs_rte_idx.size() > 1 || rhs_rte_idx.size() > 1 || lhs_rte_idx > rhs_rte_idx) {
        LOG(INFO) << "Unable to rewrite " << lhs->getName()
                  << " to overlaps conjunction. Cannot build hash table over LHS type. "
                     "Check join order.\n"
                  << bin_oper->toString();
        return boost::none;
      }

      const bool inclusive = bin_oper->get_optype() == kLE;
      auto range_expr = makeExpr<Analyzer::RangeOper>(
          inclusive, inclusive, r_arg->deep_copy(), rhs->deep_copy());
      auto overlaps_oper = makeExpr<Analyzer::BinOper>(
          kBOOLEAN, kOVERLAPS, kONE, l_arg->deep_copy(), range_expr);
      return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
    }
  }
  return boost::none;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool self_join_not_covered_by_left_deep_tree	(	const Analyzer::ColumnVar *	key_side,
		const Analyzer::ColumnVar *	val_side,
		const int	max_rte_covered
	)

Definition at line 1026 of file ExpressionRewrite.cpp.

References Analyzer::ColumnVar::get_rte_idx(), and Analyzer::ColumnVar::get_table_id().

Referenced by BaselineJoinHashTable::codegenKey(), PerfectJoinHashTable::codegenMatchingSet(), and PerfectJoinHashTable::codegenSlot().

                                                                        {
  if (key_side->get_table_id() == val_side->get_table_id() &&
      key_side->get_rte_idx() == val_side->get_rte_idx() &&
      key_side->get_rte_idx() > max_rte_covered) {
    return true;
  }
  return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

std::list<std::shared_ptr<Analyzer::Expr> > strip_join_covered_filter_quals	(	const std::list< std::shared_ptr< Analyzer::Expr >> &	quals,
		const JoinQualsPerNestingLevel &	join_quals
	)

Definition at line 968 of file ExpressionRewrite.cpp.

References g_strip_join_covered_quals, and ScalarExprVisitor< T >::visit().

Referenced by RelAlgExecutionUnit::createCountAllExecutionUnit().

                                                {
  if (!g_strip_join_covered_quals) {
    return quals;
  }

  if (join_quals.empty()) {
    return quals;
  }

  std::list<std::shared_ptr<Analyzer::Expr>> quals_to_return;

  JoinCoveredQualVisitor visitor(join_quals);
  for (const auto& qual : quals) {
    if (!visitor.visit(qual.get())) {
      // Not a covered qual, don't elide it from the filtered count
      quals_to_return.push_back(qual);
    }
  }

  return quals_to_return;
}

Here is the call graph for this function:

Here is the caller graph for this function: