Header And Logo
|
#include "postgres.h"#include "nodes/makefuncs.h"#include "optimizer/clauses.h"#include "optimizer/prep.h"#include "utils/lsyscache.h"
Go to the source code of this file.
Functions | |
| static List * | pull_ands (List *andlist) |
| static List * | pull_ors (List *orlist) |
| static Expr * | find_duplicate_ors (Expr *qual) |
| static Expr * | process_duplicate_ors (List *orlist) |
| Node * | negate_clause (Node *node) |
| Expr * | canonicalize_qual (Expr *qual) |
Definition at line 285 of file prepqual.c.
References find_duplicate_ors(), and NULL.
Referenced by convert_EXISTS_to_ANY(), get_relation_constraints(), preprocess_expression(), and RelationGetIndexPredicate().
{
Expr *newqual;
/* Quick exit for empty qual */
if (qual == NULL)
return NULL;
/*
* Pull up redundant subclauses in OR-of-AND trees. We do this only
* within the top-level AND/OR structure; there's no point in looking
* deeper.
*/
newqual = find_duplicate_ors(qual);
return newqual;
}
Definition at line 399 of file prepqual.c.
References and_clause(), lappend(), lfirst, make_andclause(), or_clause(), process_duplicate_ors(), and pull_ands().
Referenced by canonicalize_qual().
{
if (or_clause((Node *) qual))
{
List *orlist = NIL;
ListCell *temp;
/* Recurse */
foreach(temp, ((BoolExpr *) qual)->args)
orlist = lappend(orlist, find_duplicate_ors(lfirst(temp)));
/*
* Don't need pull_ors() since this routine will never introduce an OR
* where there wasn't one before.
*/
return process_duplicate_ors(orlist);
}
else if (and_clause((Node *) qual))
{
List *andlist = NIL;
ListCell *temp;
/* Recurse */
foreach(temp, ((BoolExpr *) qual)->args)
andlist = lappend(andlist, find_duplicate_ors(lfirst(temp)));
/* Flatten any ANDs introduced just below here */
andlist = pull_ands(andlist);
/* The AND list can't get shorter, so result is always an AND */
return make_andclause(andlist);
}
else
return qual;
}
Definition at line 74 of file prepqual.c.
References AND_EXPR, BooleanTest::arg, NullTest::arg, NullTest::argisrow, BoolExpr::args, ScalarArrayOpExpr::args, OpExpr::args, BoolExpr::boolop, BooleanTest::booltesttype, Const::constisnull, Const::constvalue, DatumGetBool, elog, ERROR, get_negator(), ScalarArrayOpExpr::inputcollid, OpExpr::inputcollid, IS_FALSE, IS_NOT_FALSE, IS_NOT_NULL, IS_NOT_TRUE, IS_NOT_UNKNOWN, IS_NULL, IS_TRUE, IS_UNKNOWN, lappend(), lfirst, linitial, ScalarArrayOpExpr::location, OpExpr::location, make_andclause(), make_notclause(), make_orclause(), makeBoolConst(), makeNode, negate_clause(), nodeTag, NOT_EXPR, NULL, NullTest::nulltesttype, OpExpr::opcollid, ScalarArrayOpExpr::opfuncid, OpExpr::opfuncid, ScalarArrayOpExpr::opno, OpExpr::opno, OpExpr::opresulttype, OpExpr::opretset, OR_EXPR, T_BooleanTest, T_BoolExpr, T_Const, T_NullTest, T_OpExpr, T_ScalarArrayOpExpr, and ScalarArrayOpExpr::useOr.
Referenced by eval_const_expressions_mutator(), negate_clause(), and simplify_boolean_equality().
{
if (node == NULL) /* should not happen */
elog(ERROR, "can't negate an empty subexpression");
switch (nodeTag(node))
{
case T_Const:
{
Const *c = (Const *) node;
/* NOT NULL is still NULL */
if (c->constisnull)
return makeBoolConst(false, true);
/* otherwise pretty easy */
return makeBoolConst(!DatumGetBool(c->constvalue), false);
}
break;
case T_OpExpr:
{
/*
* Negate operator if possible: (NOT (< A B)) => (>= A B)
*/
OpExpr *opexpr = (OpExpr *) node;
Oid negator = get_negator(opexpr->opno);
if (negator)
{
OpExpr *newopexpr = makeNode(OpExpr);
newopexpr->opno = negator;
newopexpr->opfuncid = InvalidOid;
newopexpr->opresulttype = opexpr->opresulttype;
newopexpr->opretset = opexpr->opretset;
newopexpr->opcollid = opexpr->opcollid;
newopexpr->inputcollid = opexpr->inputcollid;
newopexpr->args = opexpr->args;
newopexpr->location = opexpr->location;
return (Node *) newopexpr;
}
}
break;
case T_ScalarArrayOpExpr:
{
/*
* Negate a ScalarArrayOpExpr if its operator has a negator;
* for example x = ANY (list) becomes x <> ALL (list)
*/
ScalarArrayOpExpr *saopexpr = (ScalarArrayOpExpr *) node;
Oid negator = get_negator(saopexpr->opno);
if (negator)
{
ScalarArrayOpExpr *newopexpr = makeNode(ScalarArrayOpExpr);
newopexpr->opno = negator;
newopexpr->opfuncid = InvalidOid;
newopexpr->useOr = !saopexpr->useOr;
newopexpr->inputcollid = saopexpr->inputcollid;
newopexpr->args = saopexpr->args;
newopexpr->location = saopexpr->location;
return (Node *) newopexpr;
}
}
break;
case T_BoolExpr:
{
BoolExpr *expr = (BoolExpr *) node;
switch (expr->boolop)
{
/*--------------------
* Apply DeMorgan's Laws:
* (NOT (AND A B)) => (OR (NOT A) (NOT B))
* (NOT (OR A B)) => (AND (NOT A) (NOT B))
* i.e., swap AND for OR and negate each subclause.
*
* If the input is already AND/OR flat and has no NOT
* directly above AND or OR, this transformation preserves
* those properties. For example, if no direct child of
* the given AND clause is an AND or a NOT-above-OR, then
* the recursive calls of negate_clause() can't return any
* OR clauses. So we needn't call pull_ors() before
* building a new OR clause. Similarly for the OR case.
*--------------------
*/
case AND_EXPR:
{
List *nargs = NIL;
ListCell *lc;
foreach(lc, expr->args)
{
nargs = lappend(nargs,
negate_clause(lfirst(lc)));
}
return (Node *) make_orclause(nargs);
}
break;
case OR_EXPR:
{
List *nargs = NIL;
ListCell *lc;
foreach(lc, expr->args)
{
nargs = lappend(nargs,
negate_clause(lfirst(lc)));
}
return (Node *) make_andclause(nargs);
}
break;
case NOT_EXPR:
/*
* NOT underneath NOT: they cancel. We assume the
* input is already simplified, so no need to recurse.
*/
return (Node *) linitial(expr->args);
default:
elog(ERROR, "unrecognized boolop: %d",
(int) expr->boolop);
break;
}
}
break;
case T_NullTest:
{
NullTest *expr = (NullTest *) node;
/*
* In the rowtype case, the two flavors of NullTest are *not*
* logical inverses, so we can't simplify. But it does work
* for scalar datatypes.
*/
if (!expr->argisrow)
{
NullTest *newexpr = makeNode(NullTest);
newexpr->arg = expr->arg;
newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?
IS_NOT_NULL : IS_NULL);
newexpr->argisrow = expr->argisrow;
return (Node *) newexpr;
}
}
break;
case T_BooleanTest:
{
BooleanTest *expr = (BooleanTest *) node;
BooleanTest *newexpr = makeNode(BooleanTest);
newexpr->arg = expr->arg;
switch (expr->booltesttype)
{
case IS_TRUE:
newexpr->booltesttype = IS_NOT_TRUE;
break;
case IS_NOT_TRUE:
newexpr->booltesttype = IS_TRUE;
break;
case IS_FALSE:
newexpr->booltesttype = IS_NOT_FALSE;
break;
case IS_NOT_FALSE:
newexpr->booltesttype = IS_FALSE;
break;
case IS_UNKNOWN:
newexpr->booltesttype = IS_NOT_UNKNOWN;
break;
case IS_NOT_UNKNOWN:
newexpr->booltesttype = IS_UNKNOWN;
break;
default:
elog(ERROR, "unrecognized booltesttype: %d",
(int) expr->booltesttype);
break;
}
return (Node *) newexpr;
}
break;
default:
/* else fall through */
break;
}
/*
* Otherwise we don't know how to simplify this, so just tack on an
* explicit NOT node.
*/
return (Node *) make_notclause((Expr *) node);
}
Definition at line 442 of file prepqual.c.
References and_clause(), equal(), lappend(), lfirst, linitial, list_difference(), list_length(), list_make1, list_member(), list_union(), make_andclause(), make_orclause(), NIL, pull_ands(), and pull_ors().
Referenced by find_duplicate_ors().
{
List *reference = NIL;
int num_subclauses = 0;
List *winners;
List *neworlist;
ListCell *temp;
if (orlist == NIL)
return NULL; /* probably can't happen */
if (list_length(orlist) == 1) /* single-expression OR (can this
* happen?) */
return linitial(orlist);
/*
* Choose the shortest AND clause as the reference list --- obviously, any
* subclause not in this clause isn't in all the clauses. If we find a
* clause that's not an AND, we can treat it as a one-element AND clause,
* which necessarily wins as shortest.
*/
foreach(temp, orlist)
{
Expr *clause = (Expr *) lfirst(temp);
if (and_clause((Node *) clause))
{
List *subclauses = ((BoolExpr *) clause)->args;
int nclauses = list_length(subclauses);
if (reference == NIL || nclauses < num_subclauses)
{
reference = subclauses;
num_subclauses = nclauses;
}
}
else
{
reference = list_make1(clause);
break;
}
}
/*
* Just in case, eliminate any duplicates in the reference list.
*/
reference = list_union(NIL, reference);
/*
* Check each element of the reference list to see if it's in all the OR
* clauses. Build a new list of winning clauses.
*/
winners = NIL;
foreach(temp, reference)
{
Expr *refclause = (Expr *) lfirst(temp);
bool win = true;
ListCell *temp2;
foreach(temp2, orlist)
{
Expr *clause = (Expr *) lfirst(temp2);
if (and_clause((Node *) clause))
{
if (!list_member(((BoolExpr *) clause)->args, refclause))
{
win = false;
break;
}
}
else
{
if (!equal(refclause, clause))
{
win = false;
break;
}
}
}
if (win)
winners = lappend(winners, refclause);
}
/*
* If no winners, we can't transform the OR
*/
if (winners == NIL)
return make_orclause(orlist);
/*
* Generate new OR list consisting of the remaining sub-clauses.
*
* If any clause degenerates to empty, then we have a situation like (A
* AND B) OR (A), which can be reduced to just A --- that is, the
* additional conditions in other arms of the OR are irrelevant.
*
* Note that because we use list_difference, any multiple occurrences of a
* winning clause in an AND sub-clause will be removed automatically.
*/
neworlist = NIL;
foreach(temp, orlist)
{
Expr *clause = (Expr *) lfirst(temp);
if (and_clause((Node *) clause))
{
List *subclauses = ((BoolExpr *) clause)->args;
subclauses = list_difference(subclauses, winners);
if (subclauses != NIL)
{
if (list_length(subclauses) == 1)
neworlist = lappend(neworlist, linitial(subclauses));
else
neworlist = lappend(neworlist, make_andclause(subclauses));
}
else
{
neworlist = NIL; /* degenerate case, see above */
break;
}
}
else
{
if (!list_member(winners, clause))
neworlist = lappend(neworlist, clause);
else
{
neworlist = NIL; /* degenerate case, see above */
break;
}
}
}
/*
* Append reduced OR to the winners list, if it's not degenerate, handling
* the special case of one element correctly (can that really happen?).
* Also be careful to maintain AND/OR flatness in case we pulled up a
* sub-sub-OR-clause.
*/
if (neworlist != NIL)
{
if (list_length(neworlist) == 1)
winners = lappend(winners, linitial(neworlist));
else
winners = lappend(winners, make_orclause(pull_ors(neworlist)));
}
/*
* And return the constructed AND clause, again being wary of a single
* element and AND/OR flatness.
*/
if (list_length(winners) == 1)
return (Expr *) linitial(winners);
else
return make_andclause(pull_ands(winners));
}
Definition at line 312 of file prepqual.c.
References and_clause(), arg, lappend(), lfirst, and list_concat().
Referenced by find_duplicate_ors(), and process_duplicate_ors().
{
List *out_list = NIL;
ListCell *arg;
foreach(arg, andlist)
{
Node *subexpr = (Node *) lfirst(arg);
/*
* Note: we can destructively concat the subexpression's arglist
* because we know the recursive invocation of pull_ands will have
* built a new arglist not shared with any other expr. Otherwise we'd
* need a list_copy here.
*/
if (and_clause(subexpr))
out_list = list_concat(out_list,
pull_ands(((BoolExpr *) subexpr)->args));
else
out_list = lappend(out_list, subexpr);
}
return out_list;
}
Definition at line 344 of file prepqual.c.
References arg, lappend(), lfirst, list_concat(), and or_clause().
Referenced by process_duplicate_ors().
{
List *out_list = NIL;
ListCell *arg;
foreach(arg, orlist)
{
Node *subexpr = (Node *) lfirst(arg);
/*
* Note: we can destructively concat the subexpression's arglist
* because we know the recursive invocation of pull_ors will have
* built a new arglist not shared with any other expr. Otherwise we'd
* need a list_copy here.
*/
if (or_clause(subexpr))
out_list = list_concat(out_list,
pull_ors(((BoolExpr *) subexpr)->args));
else
out_list = lappend(out_list, subexpr);
}
return out_list;
}
1.7.1