OmniSciDB  cde582ebc3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ExpressionRewrite.h File Reference
#include <llvm/IR/Value.h>
#include <boost/optional.hpp>
#include <list>
#include <memory>
#include <vector>
#include "Analyzer/Analyzer.h"
#include "RelAlgExecutionUnit.h"
+ Include dependency graph for ExpressionRewrite.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  OverlapsJoinConjunction
 

Namespaces

 Analyzer
 

Functions

Analyzer::ExpressionPtr rewrite_expr (const Analyzer::Expr *)
 
Analyzer::ExpressionPtr rewrite_array_elements (const Analyzer::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::Exprfold_expr (const Analyzer::Expr *)
 
bool self_join_not_covered_by_left_deep_tree (const Analyzer::ColumnVar *lhs, const Analyzer::ColumnVar *rhs, const int max_rte_covered)
 
const int get_max_rte_scan_table (std::unordered_map< int, llvm::Value * > &scan_idx_to_hash_pos)
 

Function Documentation

std::shared_ptr<Analyzer::Expr> fold_expr ( const Analyzer::Expr )

Definition at line 1052 of file ExpressionRewrite.cpp.

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

Referenced by RelAlgExecutor::createFilterWorkUnit(), RelAlgExecutor::makeJoinQuals(), 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().

1052  {
1053  if (!expr) {
1054  return nullptr;
1055  }
1056  const auto expr_no_likelihood = strip_likelihood(expr);
1057  ConstantFoldingVisitor visitor;
1058  auto rewritten_expr = visitor.visit(expr_no_likelihood);
1059  if (visitor.get_num_overflows() > 0 && rewritten_expr->get_type_info().is_integer() &&
1060  rewritten_expr->get_type_info().get_type() != kBIGINT) {
1061  auto rewritten_expr_const =
1062  std::dynamic_pointer_cast<const Analyzer::Constant>(rewritten_expr);
1063  if (!rewritten_expr_const) {
1064  // Integer expression didn't fold completely the first time due to
1065  // overflows in smaller type subexpressions, trying again with a cast
1066  const auto& ti = SQLTypeInfo(kBIGINT, false);
1067  auto bigint_expr_no_likelihood = expr_no_likelihood->deep_copy()->add_cast(ti);
1068  auto rewritten_expr_take2 = visitor.visit(bigint_expr_no_likelihood.get());
1069  auto rewritten_expr_take2_const =
1070  std::dynamic_pointer_cast<Analyzer::Constant>(rewritten_expr_take2);
1071  if (rewritten_expr_take2_const) {
1072  // Managed to fold, switch to the new constant
1073  rewritten_expr = rewritten_expr_take2_const;
1074  }
1075  }
1076  }
1077  const auto expr_with_likelihood = dynamic_cast<const Analyzer::LikelihoodExpr*>(expr);
1078  if (expr_with_likelihood) {
1079  // Add back likelihood
1080  return std::make_shared<Analyzer::LikelihoodExpr>(
1081  rewritten_expr, expr_with_likelihood->get_likelihood());
1082  }
1083  return rewritten_expr;
1084 }
const Analyzer::Expr * strip_likelihood(const Analyzer::Expr *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 1097 of file ExpressionRewrite.cpp.

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

1098  {
1099  int ret = INT32_MIN;
1100  for (auto& kv : scan_idx_to_hash_pos) {
1101  if (kv.first > ret) {
1102  ret = kv.first;
1103  }
1104  }
1105  return ret;
1106 }

+ Here is the caller graph for this function:

Analyzer::ExpressionPtr rewrite_array_elements ( const Analyzer::Expr )

Definition at line 757 of file ExpressionRewrite.cpp.

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

757  {
758  return ArrayElementStringLiteralEncodingVisitor().visit(expr);
759 }

+ Here is the caller graph for this function:

Analyzer::ExpressionPtr rewrite_expr ( const Analyzer::Expr )

Definition at line 761 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().

761  {
762  const auto sum_window = rewrite_sum_window(expr);
763  if (sum_window) {
764  return sum_window;
765  }
766  const auto avg_window = rewrite_avg_window(expr);
767  if (avg_window) {
768  return avg_window;
769  }
770  const auto expr_no_likelihood = strip_likelihood(expr);
771  // The following check is not strictly needed, but seems silly to transform a
772  // simple string comparison to an IN just to codegen the same thing anyway.
773 
774  RecursiveOrToInVisitor visitor;
775  auto rewritten_expr = visitor.visit(expr_no_likelihood);
776  const auto expr_with_likelihood =
777  std::dynamic_pointer_cast<const Analyzer::LikelihoodExpr>(rewritten_expr);
778  if (expr_with_likelihood) {
779  // Add back likelihood
780  return std::make_shared<Analyzer::LikelihoodExpr>(
781  rewritten_expr, expr_with_likelihood->get_likelihood());
782  }
783  return rewritten_expr;
784 }
std::shared_ptr< Analyzer::WindowFunction > rewrite_avg_window(const Analyzer::Expr *expr)
std::shared_ptr< Analyzer::WindowFunction > rewrite_sum_window(const Analyzer::Expr *expr)
const Analyzer::Expr * strip_likelihood(const Analyzer::Expr *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 820 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().

821  {
822  auto func_oper = dynamic_cast<Analyzer::FunctionOper*>(expr.get());
823  if (func_oper) {
824  const auto needs_many_many = [func_oper]() {
825  return requires_many_to_many.find(func_oper->getName()) !=
826  requires_many_to_many.end();
827  };
828  // TODO(adb): consider converting unordered set to an unordered map, potentially
829  // storing the rewrite function we want to apply in the map
830  if (overlaps_supported_functions.find(func_oper->getName()) !=
832  if (!g_enable_hashjoin_many_to_many && needs_many_many()) {
833  LOG(WARNING) << "Many-to-many hashjoin support is disabled, unable to rewrite "
834  << func_oper->toString() << " to use accelerated geo join.";
835  return boost::none;
836  }
837 
838  DeepCopyVisitor deep_copy_visitor;
839  if (func_oper->getName() == "ST_Overlaps") {
840  CHECK_GE(func_oper->getArity(), size_t(2));
841  // return empty quals, overlaps join quals
842  // TODO(adb): we will likely want to actually check for true overlaps, but this
843  // works for now
844 
845  auto lhs = func_oper->getOwnArg(0);
846  auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
847  CHECK(rewritten_lhs);
848 
849  auto rhs = func_oper->getOwnArg(1);
850  auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
851  CHECK(rewritten_rhs);
852 
853  auto overlaps_oper = makeExpr<Analyzer::BinOper>(
854  kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);
855  return OverlapsJoinConjunction{{}, {overlaps_oper}};
856  }
857 
858  // TODO(jclay): This will work for Poly_Poly,but needs to change for others.
859  CHECK_GE(func_oper->getArity(), size_t(4));
860  if (func_oper->getName() == "ST_Contains_Polygon_Polygon" ||
861  func_oper->getName() == "ST_Intersects_Polygon_Polygon" ||
862  func_oper->getName() == "ST_Intersects_MultiPolygon_MultiPolygon" ||
863  func_oper->getName() == "ST_Intersects_MultiPolygon_Polygon" ||
864  func_oper->getName() == "ST_Intersects_Polygon_MultiPolygon") {
865  auto lhs = func_oper->getOwnArg(3);
866  auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
867  CHECK(rewritten_lhs);
868  auto rhs = func_oper->getOwnArg(1);
869  auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
870  CHECK(rewritten_rhs);
871 
872  auto overlaps_oper = makeExpr<Analyzer::BinOper>(
873  kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);
874 
875  VLOG(1) << "Successfully converted to overlaps join";
876  return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
877  }
878 
879  auto lhs = func_oper->getOwnArg(2);
880  auto rewritten_lhs = deep_copy_visitor.visit(lhs.get());
881  CHECK(rewritten_lhs);
882  const auto& lhs_ti = rewritten_lhs->get_type_info();
883 
884  if (!lhs_ti.is_geometry() && !is_constructed_point(rewritten_lhs.get())) {
885  // TODO(adb): If ST_Contains is passed geospatial literals instead of columns, the
886  // function will be expanded during translation rather than during code
887  // generation. While this scenario does not make sense for the overlaps join, we
888  // need to detect and abort the overlaps rewrite. Adding a GeospatialConstant
889  // dervied class to the Analyzer may prove to be a better way to handle geo
890  // literals, but for now we ensure the LHS type is a geospatial type, which would
891  // mean the function has not been expanded to the physical types, yet.
892 
893  LOG(INFO) << "Unable to rewrite " << func_oper->getName()
894  << " to overlaps conjunction. LHS input type is neither a geospatial "
895  "column nor a constructed point\n"
896  << func_oper->toString();
897 
898  return boost::none;
899  }
900 
901  // Read the bounds arg from the ST_Contains FuncOper (second argument)instead of the
902  // poly column (first argument)
903  auto rhs = func_oper->getOwnArg(1);
904  auto rewritten_rhs = deep_copy_visitor.visit(rhs.get());
905  CHECK(rewritten_rhs);
906 
907  // Check for compatible join ordering. If the join ordering does not match expected
908  // ordering for overlaps, the join builder will fail.
909  std::set<int> lhs_rte_idx;
910  lhs->collect_rte_idx(lhs_rte_idx);
911  CHECK(!lhs_rte_idx.empty());
912  std::set<int> rhs_rte_idx;
913  rhs->collect_rte_idx(rhs_rte_idx);
914  CHECK(!rhs_rte_idx.empty());
915 
916  if (lhs_rte_idx.size() > 1 || rhs_rte_idx.size() > 1 || lhs_rte_idx > rhs_rte_idx) {
917  LOG(INFO) << "Unable to rewrite " << func_oper->getName()
918  << " to overlaps conjunction. Cannot build hash table over LHS type. "
919  "Check join order.\n"
920  << func_oper->toString();
921  return boost::none;
922  }
923 
924  VLOG(1) << "Rewritten to use overlaps join with lhs as "
925  << rewritten_lhs->toString() << " and rhs as " << rewritten_rhs->toString();
926 
927  auto overlaps_oper = makeExpr<Analyzer::BinOper>(
928  kBOOLEAN, kOVERLAPS, kONE, rewritten_lhs, rewritten_rhs);
929 
930  VLOG(1) << "Successfully converted to overlaps join";
931  if (func_oper->getName() == "ST_Approx_Overlaps_MultiPolygon_Point"sv) {
932  return OverlapsJoinConjunction{{}, {overlaps_oper}};
933  } else {
934  return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
935  }
936  } else {
937  VLOG(1) << "Overlaps join not enabled for " << func_oper->getName();
938  }
939  return boost::none;
940  }
941  auto bin_oper = dynamic_cast<Analyzer::BinOper*>(expr.get());
942  if (g_enable_distance_rangejoin && bin_oper &&
943  (bin_oper->get_optype() == kLE || bin_oper->get_optype() == kLT)) {
944  auto lhs = dynamic_cast<const Analyzer::GeoOperator*>(bin_oper->get_left_operand());
945  auto rhs = dynamic_cast<const Analyzer::Constant*>(bin_oper->get_right_operand());
946  if (lhs && rhs && lhs->getName() == "ST_Distance") {
947  CHECK_EQ(lhs->size(), size_t(2));
948  auto l_arg = lhs->getOperand(0);
949  auto r_arg = lhs->getOperand(1);
950  const bool is_geography = l_arg->get_type_info().get_subtype() == kGEOGRAPHY ||
951  r_arg->get_type_info().get_subtype() == kGEOGRAPHY;
952  if (is_geography) {
953  VLOG(1) << "Range join not yet supported for geodesic distance "
954  << bin_oper->toString();
955  return boost::none;
956  }
957 
958  // Check for compatible join ordering. If the join ordering does not match expected
959  // ordering for overlaps, the join builder will fail.
960  std::set<int> lhs_rte_idx;
961  l_arg->collect_rte_idx(lhs_rte_idx);
962  CHECK(!lhs_rte_idx.empty());
963  std::set<int> rhs_rte_idx;
964  r_arg->collect_rte_idx(rhs_rte_idx);
965  CHECK(!rhs_rte_idx.empty());
966 
967  if (lhs_rte_idx.size() > 1 || rhs_rte_idx.size() > 1 || lhs_rte_idx > rhs_rte_idx) {
968  LOG(INFO) << "Unable to rewrite " << lhs->getName()
969  << " to overlaps conjunction. Cannot build hash table over LHS type. "
970  "Check join order.\n"
971  << bin_oper->toString();
972  return boost::none;
973  }
974 
975  const bool inclusive = bin_oper->get_optype() == kLE;
976  auto range_expr = makeExpr<Analyzer::RangeOper>(
977  inclusive, inclusive, r_arg->deep_copy(), rhs->deep_copy());
978  auto overlaps_oper = makeExpr<Analyzer::BinOper>(
979  kBOOLEAN, kOVERLAPS, kONE, l_arg->deep_copy(), range_expr);
980  return OverlapsJoinConjunction{{expr}, {overlaps_oper}};
981  }
982  }
983  return boost::none;
984 }
#define CHECK_EQ(x, y)
Definition: Logger.h:230
#define LOG(tag)
Definition: Logger.h:216
bool is_constructed_point(const Analyzer::Expr *expr)
Definition: Execute.h:1427
static const std::unordered_set< std::string > requires_many_to_many
Definition: sqldefs.h:34
#define CHECK_GE(x, y)
Definition: Logger.h:235
T visit(const Analyzer::Expr *expr) const
static const std::unordered_set< std::string > overlaps_supported_functions
bool g_enable_hashjoin_many_to_many
Definition: Execute.cpp:104
bool g_enable_distance_rangejoin
Definition: Execute.cpp:103
Definition: sqldefs.h:70
#define CHECK(condition)
Definition: Logger.h:222
Definition: sqldefs.h:32
#define VLOG(n)
Definition: Logger.h:316

+ 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 lhs,
const Analyzer::ColumnVar rhs,
const int  max_rte_covered 
)

Definition at line 1086 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().

1088  {
1089  if (key_side->get_table_id() == val_side->get_table_id() &&
1090  key_side->get_rte_idx() == val_side->get_rte_idx() &&
1091  key_side->get_rte_idx() > max_rte_covered) {
1092  return true;
1093  }
1094  return false;
1095 }

+ 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 1028 of file ExpressionRewrite.cpp.

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

Referenced by RelAlgExecutionUnit::createCountAllExecutionUnit().

1030  {
1032  return quals;
1033  }
1034 
1035  if (join_quals.empty()) {
1036  return quals;
1037  }
1038 
1039  std::list<std::shared_ptr<Analyzer::Expr>> quals_to_return;
1040 
1041  JoinCoveredQualVisitor visitor(join_quals);
1042  for (const auto& qual : quals) {
1043  if (!visitor.visit(qual.get())) {
1044  // Not a covered qual, don't elide it from the filtered count
1045  quals_to_return.push_back(qual);
1046  }
1047  }
1048 
1049  return quals_to_return;
1050 }
bool g_strip_join_covered_quals
Definition: Execute.cpp:107

+ Here is the call graph for this function:

+ Here is the caller graph for this function: