diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 435438a1735..9c82297e242 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -751,7 +751,8 @@ clause_selectivity_ext(PlannerInfo *root, * so that per-subclause selectivities can be cached. */ if (rinfo->orclause) - clause = (Node *) rinfo->orclause; + {clause = (Node *) rinfo->orclause; + } else clause = (Node *) rinfo->clause; } @@ -823,6 +824,7 @@ clause_selectivity_ext(PlannerInfo *root, * Almost the same thing as clauselist_selectivity, but with the * clauses connected by OR. */ + s1 = clauselist_selectivity_or(root, ((BoolExpr *) clause)->args, varRelid, diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c index 6ef9d14b902..81b11865203 100644 --- a/src/backend/optimizer/util/orclauses.c +++ b/src/backend/optimizer/util/orclauses.c @@ -22,6 +22,10 @@ #include "optimizer/optimizer.h" #include "optimizer/orclauses.h" #include "optimizer/restrictinfo.h" +#include "utils/lsyscache.h" +#include "parser/parse_expr.h" +#include "parser/parse_coerce.h" +#include "parser/parse_oper.h" static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel); @@ -29,6 +33,300 @@ static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel); static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, Expr *orclause, RestrictInfo *join_or_rinfo); +typedef struct OrClauseGroupEntry +{ + Node *node; + List *consts; + Oid collation; + Oid opno; + RestrictInfo *rinfo; + Expr *expr; +} OrClauseGroupEntry; + +/* + * Pass through baserestrictinfo clauses and try to convert OR clauses into IN + * Return a modified clause list or just the same baserestrictinfo, if no + * changes have made. + * XXX: do not change source list of clauses at all. + */ +static List * +transform_ors(PlannerInfo *root, List *baserestrictinfo) +{ + ListCell *lc; + ListCell *lc_cp; + List *modified_rinfo = NIL; + bool something_changed = false; + List *baserestrictinfo_origin = list_copy(baserestrictinfo); + + /* + * Complexity of a clause could be arbitrarily sophisticated. Here, we will + * look up only on the top level of clause list. + * XXX: It is substantiated? Could we change something here? + */ + forboth (lc, baserestrictinfo, lc_cp, baserestrictinfo_origin) + { + RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc); + RestrictInfo *rinfo_base = lfirst_node(RestrictInfo, lc_cp); + List *or_list = NIL; + ListCell *lc_eargs, + *lc_rargs, + *lc_args; + List *groups_list = NIL; + + if (!restriction_is_or_clause(rinfo)) + { + /* Add a clause without changes */ + modified_rinfo = lappend(modified_rinfo, rinfo); + continue; + } + + /* + * NOTE: + * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains + * a list of sub-restrictinfo args, and rinfo->clause - which is the + * same expression, made from bare clauses. To not break selectivity + * caches and other optimizations, use both: + * - use rinfos from orclause if no transformation needed + * - use bare quals from rinfo->clause in the case of transformation, + * to create new RestrictInfo: in this case we have no options to avoid + * selectivity estimation procedure. + */ + forboth(lc_eargs, ((BoolExpr *) rinfo->clause)->args, + lc_rargs, ((BoolExpr *) rinfo->orclause)->args) + { + Expr *bare_orarg = (Expr *) lfirst(lc_eargs); + RestrictInfo *sub_rinfo; + Node *const_expr; + Node *non_const_expr; + ListCell *lc_groups; + OrClauseGroupEntry *gentry; + Oid opno; + + /* It may be one more boolean expression, skip it for now */ + if (!IsA(lfirst(lc_rargs), RestrictInfo)) + { + or_list = lappend(or_list, (void *) bare_orarg); + continue; + } + + sub_rinfo = lfirst_node(RestrictInfo, lc_rargs); + + /* Check: it is an expr of the form 'F(x) oper ConstExpr' */ + if (!IsA(bare_orarg, OpExpr) || + !(bms_is_empty(sub_rinfo->left_relids) ^ + bms_is_empty(sub_rinfo->right_relids)) || + contain_volatile_functions((Node *) bare_orarg)) + { + /* Again, it's not the expr we can transform */ + or_list = lappend(or_list, (void *) bare_orarg); + continue; + } + + /* Get pointers to constant and expression sides of the clause */ + const_expr =bms_is_empty(sub_rinfo->left_relids) ? + get_leftop(sub_rinfo->clause) : + get_rightop(sub_rinfo->clause); + non_const_expr = bms_is_empty(sub_rinfo->left_relids) ? + get_rightop(sub_rinfo->clause) : + get_leftop(sub_rinfo->clause); + + opno = ((OpExpr *) sub_rinfo->clause)->opno; + if (!op_mergejoinable(opno, exprType(non_const_expr))) + { + /* And again, filter out non-equality operators */ + or_list = lappend(or_list, (void *) bare_orarg); + continue; + } + + /* + * At this point we definitely have a transformable clause. + * Classify it and add into specific group of clauses, or create new + * group. + * TODO: to manage complexity in the case of many different clauses + * (X1=C1) OR (X2=C2 OR) ... (XN = CN) we could invent something + * like a hash table (htab key ???). + */ + foreach(lc_groups, groups_list) + { + OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups); + + Assert(v->node != NULL); + + if (equal(v->node, non_const_expr)) + { + v->consts = lappend(v->consts, const_expr); + non_const_expr = NULL; + break; + } + } + + if (non_const_expr == NULL) + /* + * The clause classified successfully and added into existed + * clause group. + */ + continue; + + /* New clause group needed */ + gentry = palloc(sizeof(OrClauseGroupEntry)); + gentry->node = non_const_expr; + gentry->consts = list_make1(const_expr); + gentry->collation = exprInputCollation((Node *)sub_rinfo->clause); + gentry->opno = opno; + gentry->rinfo = sub_rinfo; + gentry->expr = bare_orarg; + groups_list = lappend(groups_list, (void *) gentry); + } + + if (groups_list == NIL) + { + /* + * No any transformations possible with this rinfo, just add itself + * to the list and go further. + */ + modified_rinfo = lappend(modified_rinfo, rinfo); + continue; + } + + /* Let's convert each group of clauses to an IN operation. */ + + /* + * Go through the list of groups and convert each, where number of + * consts more than 1. trivial groups move to OR-list again + */ + + foreach(lc_args, groups_list) + { + OrClauseGroupEntry *gentry = (OrClauseGroupEntry *) lfirst(lc_args); + List *allexprs; + Oid scalar_type; + Oid array_type; + + Assert(list_length(gentry->consts) > 0); + + if (list_length(gentry->consts) == 1) + { + /* + * Only one element in the class. Return rinfo into the BoolExpr + * args list unchanged. + */ + list_free(gentry->consts); + or_list = lappend(or_list, gentry->expr); + continue; + } + + /* + * Do the transformation. + * + * First of all, try to select a common type for the array elements. + * Note that since the LHS' type is first in the list, it will be + * preferred when there is doubt (eg, when all the RHS items are + * unknown literals). + * + * Note: use list_concat here not lcons, to avoid damaging rnonvars. + * + * As a source of insides, use make_scalar_array_op() + */ + allexprs = list_concat(list_make1(gentry->node), gentry->consts); + scalar_type = select_common_type(NULL, allexprs, NULL, NULL); + + if (scalar_type != RECORDOID && OidIsValid(scalar_type)) + array_type = get_array_type(scalar_type); + else + array_type = InvalidOid; + + if (array_type != InvalidOid) + { + /* + * OK: coerce all the right-hand non-Var inputs to the common + * type and build an ArrayExpr for them. + */ + List *aexprs; + ArrayExpr *newa; + ScalarArrayOpExpr *saopexpr; + ListCell *l; + + aexprs = NIL; + + foreach(l, gentry->consts) + { + Node *rexpr = (Node *) lfirst(l); + + rexpr = coerce_to_common_type(NULL, rexpr, + scalar_type, + "IN"); + aexprs = lappend(aexprs, rexpr); + } + + newa = makeNode(ArrayExpr); + /* array_collid will be set by parse_collate.c */ + newa->element_typeid = scalar_type; + newa->array_typeid = array_type; + newa->multidims = false; + newa->elements = aexprs; + newa->location = -1; + + saopexpr = + (ScalarArrayOpExpr *) + make_scalar_array_op(NULL, + list_make1(makeString((char *) "=")), + true, + gentry->node, + (Node *) newa, + -1); + + or_list = lappend(or_list, (void *) saopexpr); + } + else + { + list_free(gentry->consts); + or_list = lappend(or_list, gentry->expr); + continue; + } + } + + /* + * Make a new version of the restriction. Remember source restriction + * can be used in another path (SeqScan, for example). + */ + + /* One more trick: assemble correct clause */ + rinfo = make_restrictinfo(root, + list_length(or_list) > 1 ? make_orclause(or_list) : + (Expr *) linitial(or_list), + rinfo->is_pushed_down, + rinfo->has_clone, + rinfo->is_clone, + rinfo->pseudoconstant, + rinfo->security_level, + rinfo->required_relids, + rinfo->incompatible_relids, + rinfo->outer_relids); + rinfo->eval_cost=rinfo_base->eval_cost; + rinfo->norm_selec=rinfo_base->norm_selec; + rinfo->outer_selec=rinfo_base->outer_selec; + rinfo->left_bucketsize=rinfo_base->left_bucketsize; + rinfo->right_bucketsize=rinfo_base->right_bucketsize; + rinfo->left_mcvfreq=rinfo_base->left_mcvfreq; + rinfo->right_mcvfreq=rinfo_base->right_mcvfreq; + + modified_rinfo = lappend(modified_rinfo, rinfo); + list_free_deep(groups_list); + something_changed = true; + } + + /* + * Check if transformation has made. If nothing changed - return + * baserestrictinfo as is. + */ + if (something_changed) + { + return modified_rinfo; + } + + list_free(modified_rinfo); + return baserestrictinfo; +} /* * extract_restriction_or_clauses @@ -93,6 +391,10 @@ extract_restriction_or_clauses(PlannerInfo *root) if (rel->reloptkind != RELOPT_BASEREL) continue; + if (rel->reloptkind == RELOPT_BASEREL) + rel->baserestrictinfo = transform_ors(root, rel->baserestrictinfo); + rel->joininfo = transform_ors(root, rel->joininfo); + /* * Find potentially interesting OR joinclauses. We can use any * joinclause that is considered safe to move to this rel by the