diff options
Diffstat (limited to 'src/backend/optimizer/util')
| -rw-r--r-- | src/backend/optimizer/util/Makefile | 31 | ||||
| -rw-r--r-- | src/backend/optimizer/util/clauses.c | 2324 | ||||
| -rw-r--r-- | src/backend/optimizer/util/joininfo.c | 76 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 620 | ||||
| -rw-r--r-- | src/backend/optimizer/util/plancat.c | 363 | ||||
| -rw-r--r-- | src/backend/optimizer/util/relnode.c | 679 | ||||
| -rw-r--r-- | src/backend/optimizer/util/restrictinfo.c | 82 | ||||
| -rw-r--r-- | src/backend/optimizer/util/tlist.c | 257 | ||||
| -rw-r--r-- | src/backend/optimizer/util/var.c | 370 |
9 files changed, 0 insertions, 4802 deletions
diff --git a/src/backend/optimizer/util/Makefile b/src/backend/optimizer/util/Makefile deleted file mode 100644 index 471cfdf6b9b..00000000000 --- a/src/backend/optimizer/util/Makefile +++ /dev/null @@ -1,31 +0,0 @@ -#------------------------------------------------------------------------- -# -# Makefile-- -# Makefile for optimizer/util -# -# IDENTIFICATION -# $Header: /cvsroot/pgsql/src/backend/optimizer/util/Makefile,v 1.14 2000/09/29 18:21:23 tgl Exp $ -# -#------------------------------------------------------------------------- - -subdir = src/backend/optimizer/util -top_builddir = ../../../.. -include $(top_builddir)/src/Makefile.global - -OBJS = restrictinfo.o clauses.o plancat.o \ - joininfo.o pathnode.o relnode.o tlist.o var.o - -all: SUBSYS.o - -SUBSYS.o: $(OBJS) - $(LD) $(LDREL) $(LDOUT) SUBSYS.o $(OBJS) - -depend dep: - $(CC) -MM $(CFLAGS) *.c >depend - -clean: - rm -f SUBSYS.o $(OBJS) - -ifeq (depend,$(wildcard depend)) -include depend -endif diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c deleted file mode 100644 index 366a23c5cd0..00000000000 --- a/src/backend/optimizer/util/clauses.c +++ /dev/null @@ -1,2324 +0,0 @@ -/*------------------------------------------------------------------------- - * - * clauses.c - * routines to manipulate qualification clauses - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.101 2002/06/20 20:29:31 momjian Exp $ - * - * HISTORY - * AUTHOR DATE MAJOR EVENT - * Andrew Yu Nov 3, 1994 clause.c and clauses.c combined - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "catalog/pg_operator.h" -#include "catalog/pg_proc.h" -#include "catalog/pg_type.h" -#include "executor/executor.h" -#include "nodes/makefuncs.h" -#include "nodes/nodeFuncs.h" -#include "optimizer/clauses.h" -#include "optimizer/tlist.h" -#include "optimizer/var.h" -#include "parser/parsetree.h" -#include "utils/datum.h" -#include "utils/lsyscache.h" -#include "utils/syscache.h" - - -/* note that pg_type.h hardwires size of bool as 1 ... duplicate it */ -#define MAKEBOOLCONST(val,isnull) \ - ((Node *) makeConst(BOOLOID, 1, (Datum) (val), \ - (isnull), true, false, false)) - -typedef struct -{ - Query *query; - List *groupClauses; -} check_subplans_for_ungrouped_vars_context; - -static bool contain_agg_clause_walker(Node *node, void *context); -static bool pull_agg_clause_walker(Node *node, List **listptr); -static bool expression_returns_set_walker(Node *node, void *context); -static bool contain_subplans_walker(Node *node, void *context); -static bool pull_subplans_walker(Node *node, List **listptr); -static bool check_subplans_for_ungrouped_vars_walker(Node *node, - check_subplans_for_ungrouped_vars_context * context); -static bool contain_mutable_functions_walker(Node *node, void *context); -static bool contain_volatile_functions_walker(Node *node, void *context); -static Node *eval_const_expressions_mutator(Node *node, void *context); -static Expr *simplify_op_or_func(Expr *expr, List *args); - - -Expr * -make_clause(int type, Node *oper, List *args) -{ - Expr *expr = makeNode(Expr); - - switch (type) - { - case AND_EXPR: - case OR_EXPR: - case NOT_EXPR: - expr->typeOid = BOOLOID; - break; - case OP_EXPR: - expr->typeOid = ((Oper *) oper)->opresulttype; - break; - case FUNC_EXPR: - expr->typeOid = ((Func *) oper)->funcresulttype; - break; - default: - elog(ERROR, "make_clause: unsupported type %d", type); - break; - } - expr->opType = type; - expr->oper = oper; /* ignored for AND, OR, NOT */ - expr->args = args; - return expr; -} - - -/***************************************************************************** - * OPERATOR clause functions - *****************************************************************************/ - - -/* - * is_opclause - * - * Returns t iff the clause is an operator clause: - * (op expr expr) or (op expr). - * - * [historical note: is_clause has the exact functionality and is used - * throughout the code. They're renamed to is_opclause for clarity. - * - ay 10/94.] - */ -bool -is_opclause(Node *clause) -{ - return (clause != NULL && - IsA(clause, Expr) && - ((Expr *) clause)->opType == OP_EXPR); -} - -/* - * make_opclause - * Creates a clause given its operator left operand and right - * operand (if it is non-null). - * - */ -Expr * -make_opclause(Oper *op, Var *leftop, Var *rightop) -{ - Expr *expr = makeNode(Expr); - - expr->typeOid = op->opresulttype; - expr->opType = OP_EXPR; - expr->oper = (Node *) op; - if (rightop) - expr->args = makeList2(leftop, rightop); - else - expr->args = makeList1(leftop); - return expr; -} - -/* - * get_leftop - * - * Returns the left operand of a clause of the form (op expr expr) - * or (op expr) - * - * NB: for historical reasons, the result is declared Var *, even - * though many callers can cope with results that are not Vars. - * The result really ought to be declared Expr * or Node *. - */ -Var * -get_leftop(Expr *clause) -{ - if (clause->args != NULL) - return lfirst(clause->args); - else - return NULL; -} - -/* - * get_rightop - * - * Returns the right operand in a clause of the form (op expr expr). - * NB: result will be NULL if applied to a unary op clause. - */ -Var * -get_rightop(Expr *clause) -{ - if (clause->args != NULL && lnext(clause->args) != NULL) - return lfirst(lnext(clause->args)); - else - return NULL; -} - -/***************************************************************************** - * FUNC clause functions - *****************************************************************************/ - -/* - * is_funcclause - * - * Returns t iff the clause is a function clause: (func { expr }). - * - */ -bool -is_funcclause(Node *clause) -{ - return (clause != NULL && - IsA(clause, Expr) && - ((Expr *) clause)->opType == FUNC_EXPR); -} - -/* - * make_funcclause - * - * Creates a function clause given the FUNC node and the functional - * arguments. - * - */ -Expr * -make_funcclause(Func *func, List *funcargs) -{ - Expr *expr = makeNode(Expr); - - expr->typeOid = func->funcresulttype; - expr->opType = FUNC_EXPR; - expr->oper = (Node *) func; - expr->args = funcargs; - return expr; -} - -/***************************************************************************** - * OR clause functions - *****************************************************************************/ - -/* - * or_clause - * - * Returns t iff the clause is an 'or' clause: (OR { expr }). - * - */ -bool -or_clause(Node *clause) -{ - return (clause != NULL && - IsA(clause, Expr) && - ((Expr *) clause)->opType == OR_EXPR); -} - -/* - * make_orclause - * - * Creates an 'or' clause given a list of its subclauses. - * - */ -Expr * -make_orclause(List *orclauses) -{ - Expr *expr = makeNode(Expr); - - expr->typeOid = BOOLOID; - expr->opType = OR_EXPR; - expr->oper = NULL; - expr->args = orclauses; - return expr; -} - -/***************************************************************************** - * NOT clause functions - *****************************************************************************/ - -/* - * not_clause - * - * Returns t iff this is a 'not' clause: (NOT expr). - * - */ -bool -not_clause(Node *clause) -{ - return (clause != NULL && - IsA(clause, Expr) && - ((Expr *) clause)->opType == NOT_EXPR); -} - -/* - * make_notclause - * - * Create a 'not' clause given the expression to be negated. - * - */ -Expr * -make_notclause(Expr *notclause) -{ - Expr *expr = makeNode(Expr); - - expr->typeOid = BOOLOID; - expr->opType = NOT_EXPR; - expr->oper = NULL; - expr->args = makeList1(notclause); - return expr; -} - -/* - * get_notclausearg - * - * Retrieve the clause within a 'not' clause - * - */ -Expr * -get_notclausearg(Expr *notclause) -{ - return lfirst(notclause->args); -} - -/***************************************************************************** - * AND clause functions - *****************************************************************************/ - - -/* - * and_clause - * - * Returns t iff its argument is an 'and' clause: (AND { expr }). - * - */ -bool -and_clause(Node *clause) -{ - return (clause != NULL && - IsA(clause, Expr) && - ((Expr *) clause)->opType == AND_EXPR); -} - -/* - * make_andclause - * - * Create an 'and' clause given its arguments in a list. - */ -Expr * -make_andclause(List *andclauses) -{ - Expr *expr = makeNode(Expr); - - expr->typeOid = BOOLOID; - expr->opType = AND_EXPR; - expr->oper = NULL; - expr->args = andclauses; - return expr; -} - -/* - * make_and_qual - * - * Variant of make_andclause for ANDing two qual conditions together. - * Qual conditions have the property that a NULL nodetree is interpreted - * as 'true'. - */ -Node * -make_and_qual(Node *qual1, Node *qual2) -{ - if (qual1 == NULL) - return qual2; - if (qual2 == NULL) - return qual1; - return (Node *) make_andclause(makeList2(qual1, qual2)); -} - -/* - * Sometimes (such as in the result of canonicalize_qual or the input of - * ExecQual), we use lists of expression nodes with implicit AND semantics. - * - * These functions convert between an AND-semantics expression list and the - * ordinary representation of a boolean expression. - * - * Note that an empty list is considered equivalent to TRUE. - */ -Expr * -make_ands_explicit(List *andclauses) -{ - if (andclauses == NIL) - return (Expr *) MAKEBOOLCONST(true, false); - else if (lnext(andclauses) == NIL) - return (Expr *) lfirst(andclauses); - else - return make_andclause(andclauses); -} - -List * -make_ands_implicit(Expr *clause) -{ - /* - * NB: because the parser sets the qual field to NULL in a query that - * has no WHERE clause, we must consider a NULL input clause as TRUE, - * even though one might more reasonably think it FALSE. Grumble. If - * this causes trouble, consider changing the parser's behavior. - */ - if (clause == NULL) - return NIL; /* NULL -> NIL list == TRUE */ - else if (and_clause((Node *) clause)) - return clause->args; - else if (IsA(clause, Const) && - !((Const *) clause)->constisnull && - DatumGetBool(((Const *) clause)->constvalue)) - return NIL; /* constant TRUE input -> NIL list */ - else - return makeList1(clause); -} - - -/***************************************************************************** - * Aggregate-function clause manipulation - *****************************************************************************/ - -/* - * contain_agg_clause - * Recursively search for Aggref nodes within a clause. - * - * Returns true if any aggregate found. - */ -bool -contain_agg_clause(Node *clause) -{ - return contain_agg_clause_walker(clause, NULL); -} - -static bool -contain_agg_clause_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (IsA(node, Aggref)) - return true; /* abort the tree traversal and return - * true */ - return expression_tree_walker(node, contain_agg_clause_walker, context); -} - -/* - * pull_agg_clause - * Recursively pulls all Aggref nodes from an expression tree. - * - * Returns list of Aggref nodes found. Note the nodes themselves are not - * copied, only referenced. - * - * Note: this also checks for nested aggregates, which are an error. - */ -List * -pull_agg_clause(Node *clause) -{ - List *result = NIL; - - pull_agg_clause_walker(clause, &result); - return result; -} - -static bool -pull_agg_clause_walker(Node *node, List **listptr) -{ - if (node == NULL) - return false; - if (IsA(node, Aggref)) - { - *listptr = lappend(*listptr, node); - - /* - * Complain if the aggregate's argument contains any aggregates; - * nested agg functions are semantically nonsensical. - */ - if (contain_agg_clause(((Aggref *) node)->target)) - elog(ERROR, "Aggregate function calls may not be nested"); - - /* - * Having checked that, we need not recurse into the argument. - */ - return false; - } - return expression_tree_walker(node, pull_agg_clause_walker, - (void *) listptr); -} - - -/***************************************************************************** - * Support for expressions returning sets - *****************************************************************************/ - -/* - * expression_returns_set - * Test whethe an expression returns a set result. - * - * Because we use expression_tree_walker(), this can also be applied to - * whole targetlists; it'll produce TRUE if any one of the tlist items - * returns a set. - */ -bool -expression_returns_set(Node *clause) -{ - return expression_returns_set_walker(clause, NULL); -} - -static bool -expression_returns_set_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (IsA(node, Expr)) - { - Expr *expr = (Expr *) node; - - switch (expr->opType) - { - case OP_EXPR: - if (((Oper *) expr->oper)->opretset) - return true; - /* else fall through to check args */ - break; - case FUNC_EXPR: - if (((Func *) expr->oper)->funcretset) - return true; - /* else fall through to check args */ - break; - case OR_EXPR: - case AND_EXPR: - case NOT_EXPR: - /* Booleans can't return a set, so no need to recurse */ - return false; - case SUBPLAN_EXPR: - /* Subplans can't presently return sets either */ - return false; - } - } - /* Avoid recursion for some other cases that can't return a set */ - if (IsA(node, Aggref)) - return false; - if (IsA(node, SubLink)) - return false; - return expression_tree_walker(node, expression_returns_set_walker, - context); -} - -/***************************************************************************** - * Subplan clause manipulation - *****************************************************************************/ - -/* - * contain_subplans - * Recursively search for subplan nodes within a clause. - * - * If we see a SubLink node, we will return TRUE. This is only possible if - * the expression tree hasn't yet been transformed by subselect.c. We do not - * know whether the node will produce a true subplan or just an initplan, - * but we make the conservative assumption that it will be a subplan. - * - * Returns true if any subplan found. - */ -bool -contain_subplans(Node *clause) -{ - return contain_subplans_walker(clause, NULL); -} - -static bool -contain_subplans_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (is_subplan(node) || IsA(node, SubLink)) - return true; /* abort the tree traversal and return - * true */ - return expression_tree_walker(node, contain_subplans_walker, context); -} - -/* - * pull_subplans - * Recursively pulls all subplans from an expression tree. - * - * Returns list of subplan nodes found. Note the nodes themselves are not - * copied, only referenced. - */ -List * -pull_subplans(Node *clause) -{ - List *result = NIL; - - pull_subplans_walker(clause, &result); - return result; -} - -static bool -pull_subplans_walker(Node *node, List **listptr) -{ - if (node == NULL) - return false; - if (is_subplan(node)) - { - *listptr = lappend(*listptr, ((Expr *) node)->oper); - /* fall through to check args to subplan */ - } - return expression_tree_walker(node, pull_subplans_walker, - (void *) listptr); -} - -/* - * check_subplans_for_ungrouped_vars - * Check for subplans that are being passed ungrouped variables as - * parameters; generate an error message if any are found. - * - * In most contexts, ungrouped variables will be detected by the parser (see - * parse_agg.c, check_ungrouped_columns()). But that routine currently does - * not check subplans, because the necessary info is not computed until the - * planner runs. So we do it here, after we have processed sublinks into - * subplans. This ought to be cleaned up someday. - * - * A deficiency in this scheme is that any outer reference var must be - * grouped by itself; we don't recognize groupable expressions within - * subselects. For example, consider - * SELECT - * (SELECT x FROM bar where y = (foo.a + foo.b)) - * FROM foo - * GROUP BY a + b; - * This query will be rejected although it could be allowed. - */ -void -check_subplans_for_ungrouped_vars(Query *query) -{ - check_subplans_for_ungrouped_vars_context context; - List *gl; - - context.query = query; - - /* - * Build a list of the acceptable GROUP BY expressions for use in the - * walker (to avoid repeated scans of the targetlist within the - * recursive routine). - */ - context.groupClauses = NIL; - foreach(gl, query->groupClause) - { - GroupClause *grpcl = lfirst(gl); - Node *expr; - - expr = get_sortgroupclause_expr(grpcl, query->targetList); - context.groupClauses = lcons(expr, context.groupClauses); - } - - /* - * Recursively scan the targetlist and the HAVING clause. WHERE and - * JOIN/ON conditions are not examined, since they are evaluated - * before grouping. - */ - check_subplans_for_ungrouped_vars_walker((Node *) query->targetList, - &context); - check_subplans_for_ungrouped_vars_walker(query->havingQual, - &context); - - freeList(context.groupClauses); -} - -static bool -check_subplans_for_ungrouped_vars_walker(Node *node, - check_subplans_for_ungrouped_vars_context * context) -{ - List *gl; - - if (node == NULL) - return false; - if (IsA(node, Const) ||IsA(node, Param)) - return false; /* constants are always acceptable */ - - /* - * If we find an aggregate function, do not recurse into its - * arguments. Subplans invoked within aggregate calls are allowed to - * receive ungrouped variables. (This test and the next one should - * match the logic in parse_agg.c's check_ungrouped_columns().) - */ - if (IsA(node, Aggref)) - return false; - - /* - * Check to see if subexpression as a whole matches any GROUP BY item. - * We need to do this at every recursion level so that we recognize - * GROUPed-BY expressions before reaching variables within them. - */ - foreach(gl, context->groupClauses) - { - if (equal(node, lfirst(gl))) - return false; /* acceptable, do not descend more */ - } - - /* - * We can ignore Vars other than in subplan args lists, since the - * parser already checked 'em. - */ - if (is_subplan(node)) - { - /* - * The args list of the subplan node represents attributes from - * outside passed into the sublink. - */ - List *t; - - foreach(t, ((Expr *) node)->args) - { - Node *thisarg = lfirst(t); - Var *var; - bool contained_in_group_clause; - - /* - * We do not care about args that are not local variables; - * params or outer-level vars are not our responsibility to - * check. (The outer-level query passing them to us needs to - * worry, instead.) - */ - if (!IsA(thisarg, Var)) - continue; - var = (Var *) thisarg; - if (var->varlevelsup > 0) - continue; - - /* - * Else, see if it is a grouping column. - */ - contained_in_group_clause = false; - foreach(gl, context->groupClauses) - { - if (equal(thisarg, lfirst(gl))) - { - contained_in_group_clause = true; - break; - } - } - - if (!contained_in_group_clause) - { - /* Found an ungrouped argument. Complain. */ - RangeTblEntry *rte; - char *attname; - - Assert(var->varno > 0 && - (int) var->varno <= length(context->query->rtable)); - rte = rt_fetch(var->varno, context->query->rtable); - attname = get_rte_attribute_name(rte, var->varattno); - elog(ERROR, "Sub-SELECT uses un-GROUPed attribute %s.%s from outer query", - rte->eref->aliasname, attname); - } - } - } - return expression_tree_walker(node, - check_subplans_for_ungrouped_vars_walker, - (void *) context); -} - - -/***************************************************************************** - * Check clauses for mutable functions - *****************************************************************************/ - -/* - * contain_mutable_functions - * Recursively search for mutable functions within a clause. - * - * Returns true if any mutable function (or operator implemented by a - * mutable function) is found. This test is needed so that we don't - * mistakenly think that something like "WHERE random() < 0.5" can be treated - * as a constant qualification. - * - * XXX we do not examine sublinks/subplans to see if they contain uses of - * mutable functions. It's not real clear if that is correct or not... - */ -bool -contain_mutable_functions(Node *clause) -{ - return contain_mutable_functions_walker(clause, NULL); -} - -static bool -contain_mutable_functions_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (IsA(node, Expr)) - { - Expr *expr = (Expr *) node; - - switch (expr->opType) - { - case OP_EXPR: - if (op_volatile(((Oper *) expr->oper)->opno) != PROVOLATILE_IMMUTABLE) - return true; - break; - case FUNC_EXPR: - if (func_volatile(((Func *) expr->oper)->funcid) != PROVOLATILE_IMMUTABLE) - return true; - break; - default: - break; - } - } - return expression_tree_walker(node, contain_mutable_functions_walker, - context); -} - - -/***************************************************************************** - * Check clauses for volatile functions - *****************************************************************************/ - -/* - * contain_volatile_functions - * Recursively search for volatile functions within a clause. - * - * Returns true if any volatile function (or operator implemented by a - * volatile function) is found. This test prevents invalid conversions - * of volatile expressions into indexscan quals. - * - * XXX we do not examine sublinks/subplans to see if they contain uses of - * volatile functions. It's not real clear if that is correct or not... - */ -bool -contain_volatile_functions(Node *clause) -{ - return contain_volatile_functions_walker(clause, NULL); -} - -static bool -contain_volatile_functions_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (IsA(node, Expr)) - { - Expr *expr = (Expr *) node; - - switch (expr->opType) - { - case OP_EXPR: - if (op_volatile(((Oper *) expr->oper)->opno) == PROVOLATILE_VOLATILE) - return true; - break; - case FUNC_EXPR: - if (func_volatile(((Func *) expr->oper)->funcid) == PROVOLATILE_VOLATILE) - return true; - break; - default: - break; - } - } - return expression_tree_walker(node, contain_volatile_functions_walker, - context); -} - - -/***************************************************************************** - * Check for "pseudo-constant" clauses - *****************************************************************************/ - -/* - * is_pseudo_constant_clause - * Detect whether a clause is "constant", ie, it contains no variables - * of the current query level and no uses of volatile functions. - * Such a clause is not necessarily a true constant: it can still contain - * Params and outer-level Vars, not to mention functions whose results - * may vary from one statement to the next. However, the clause's value - * will be constant over any one scan of the current query, so it can be - * used as an indexscan key or (if a top-level qual) can be pushed up to - * become a gating qual. - */ -bool -is_pseudo_constant_clause(Node *clause) -{ - /* - * We could implement this check in one recursive scan. But since the - * check for volatile functions is both moderately expensive and - * unlikely to fail, it seems better to look for Vars first and only - * check for volatile functions if we find no Vars. - */ - if (!contain_var_clause(clause) && - !contain_volatile_functions(clause)) - return true; - return false; -} - -/* - * pull_constant_clauses - * Scan through a list of qualifications and separate "constant" quals - * from those that are not. - * - * Returns a list of the pseudo-constant clauses in constantQual and the - * remaining quals as the return value. - */ -List * -pull_constant_clauses(List *quals, List **constantQual) -{ - List *constqual = NIL; - List *restqual = NIL; - List *q; - - foreach(q, quals) - { - Node *qual = (Node *) lfirst(q); - - if (is_pseudo_constant_clause(qual)) - constqual = lappend(constqual, qual); - else - restqual = lappend(restqual, qual); - } - *constantQual = constqual; - return restqual; -} - - -/***************************************************************************** - * Tests on clauses of queries - * - * Possibly this code should go someplace else, since this isn't quite the - * same meaning of "clause" as is used elsewhere in this module. But I can't - * think of a better place for it... - *****************************************************************************/ - -/* - * Test whether a sort/group reference value appears in the given list of - * SortClause (or GroupClause) nodes. - * - * Because GroupClause is typedef'd as SortClause, either kind of - * node list can be passed without casting. - */ -static bool -sortgroupref_is_present(Index sortgroupref, List *clauselist) -{ - List *clause; - - foreach(clause, clauselist) - { - SortClause *scl = (SortClause *) lfirst(clause); - - if (scl->tleSortGroupRef == sortgroupref) - return true; - } - return false; -} - -/* - * Test whether a query uses DISTINCT ON, ie, has a distinct-list that is - * not the same as the set of output columns. - */ -bool -has_distinct_on_clause(Query *query) -{ - List *targetList; - - /* Is there a DISTINCT clause at all? */ - if (query->distinctClause == NIL) - return false; - - /* - * If the DISTINCT list contains all the nonjunk targetlist items, and - * nothing else (ie, no junk tlist items), then it's a simple - * DISTINCT, else it's DISTINCT ON. We do not require the lists to be - * in the same order (since the parser may have adjusted the DISTINCT - * clause ordering to agree with ORDER BY). Furthermore, a - * non-DISTINCT junk tlist item that is in the sortClause is also - * evidence of DISTINCT ON, since we don't allow ORDER BY on junk - * tlist items when plain DISTINCT is used. - * - * This code assumes that the DISTINCT list is valid, ie, all its entries - * match some entry of the tlist. - */ - foreach(targetList, query->targetList) - { - TargetEntry *tle = (TargetEntry *) lfirst(targetList); - Index ressortgroupref = tle->resdom->ressortgroupref; - - if (ressortgroupref == 0) - { - if (tle->resdom->resjunk) - continue; /* we can ignore unsorted junk cols */ - return true; /* definitely not in DISTINCT list */ - } - if (sortgroupref_is_present(ressortgroupref, query->distinctClause)) - { - if (tle->resdom->resjunk) - return true; /* junk TLE in DISTINCT means DISTINCT ON */ - /* else this TLE is okay, keep looking */ - } - else - { - /* This TLE is not in DISTINCT list */ - if (!tle->resdom->resjunk) - return true; /* non-junk, non-DISTINCT, so DISTINCT ON */ - if (sortgroupref_is_present(ressortgroupref, query->sortClause)) - return true; /* sorted, non-distinct junk */ - /* unsorted junk is okay, keep looking */ - } - } - /* It's a simple DISTINCT */ - return false; -} - - -/***************************************************************************** - * * - * General clause-manipulating routines * - * * - *****************************************************************************/ - -/* - * clause_get_relids_vars - * Retrieves distinct relids and vars appearing within a clause. - * - * '*relids' is set to an integer list of all distinct "varno"s appearing - * in Vars within the clause. - * '*vars' is set to a list of all distinct Vars appearing within the clause. - * Var nodes are considered distinct if they have different varno - * or varattno values. If there are several occurrences of the same - * varno/varattno, you get a randomly chosen one... - * - * Note that upper-level vars are ignored, since they normally will - * become Params with respect to this query level. - */ -void -clause_get_relids_vars(Node *clause, Relids *relids, List **vars) -{ - List *clvars = pull_var_clause(clause, false); - List *varno_list = NIL; - List *var_list = NIL; - List *i; - - foreach(i, clvars) - { - Var *var = (Var *) lfirst(i); - List *vi; - - if (!intMember(var->varno, varno_list)) - varno_list = lconsi(var->varno, varno_list); - foreach(vi, var_list) - { - Var *in_list = (Var *) lfirst(vi); - - if (in_list->varno == var->varno && - in_list->varattno == var->varattno) - break; - } - if (vi == NIL) - var_list = lcons(var, var_list); - } - freeList(clvars); - - *relids = varno_list; - *vars = var_list; -} - -/* - * NumRelids - * (formerly clause_relids) - * - * Returns the number of different relations referenced in 'clause'. - */ -int -NumRelids(Node *clause) -{ - List *varno_list = pull_varnos(clause); - int result = length(varno_list); - - freeList(varno_list); - return result; -} - -/*-------------------- - * CommuteClause: commute a binary operator clause - * - * XXX the clause is destructively modified! - *-------------------- - */ -void -CommuteClause(Expr *clause) -{ - Oid opoid; - HeapTuple optup; - Form_pg_operator commuTup; - Oper *commu; - Node *temp; - - if (!is_opclause((Node *) clause) || - length(clause->args) != 2) - elog(ERROR, "CommuteClause: applied to non-binary-operator clause"); - - opoid = ((Oper *) clause->oper)->opno; - - optup = SearchSysCache(OPEROID, - ObjectIdGetDatum(get_commutator(opoid)), - 0, 0, 0); - if (!HeapTupleIsValid(optup)) - elog(ERROR, "CommuteClause: no commutator for operator %u", opoid); - - commuTup = (Form_pg_operator) GETSTRUCT(optup); - - commu = makeOper(optup->t_data->t_oid, - commuTup->oprcode, - commuTup->oprresult, - ((Oper *) clause->oper)->opretset); - - ReleaseSysCache(optup); - - /* - * re-form the clause in-place! - */ - clause->oper = (Node *) commu; - temp = lfirst(clause->args); - lfirst(clause->args) = lsecond(clause->args); - lsecond(clause->args) = temp; -} - - -/*-------------------- - * eval_const_expressions - * - * Reduce any recognizably constant subexpressions of the given - * expression tree, for example "2 + 2" => "4". More interestingly, - * we can reduce certain boolean expressions even when they contain - * non-constant subexpressions: "x OR true" => "true" no matter what - * the subexpression x is. (XXX We assume that no such subexpression - * will have important side-effects, which is not necessarily a good - * assumption in the presence of user-defined functions; do we need a - * pg_proc flag that prevents discarding the execution of a function?) - * - * We do understand that certain functions may deliver non-constant - * results even with constant inputs, "nextval()" being the classic - * example. Functions that are not marked "immutable" in pg_proc - * will not be pre-evaluated here, although we will reduce their - * arguments as far as possible. - * - * We assume that the tree has already been type-checked and contains - * only operators and functions that are reasonable to try to execute. - * - * This routine should be invoked before converting sublinks to subplans - * (subselect.c's SS_process_sublinks()). The converted form contains - * bogus "Const" nodes that are actually placeholders where the executor - * will insert values from the inner plan, and obviously we mustn't try - * to reduce the expression as though these were really constants. - * As a safeguard, if we happen to find an already-converted SubPlan node, - * we will return it unchanged rather than recursing into it. - *-------------------- - */ -Node * -eval_const_expressions(Node *node) -{ - /* no context or special setup needed, so away we go... */ - return eval_const_expressions_mutator(node, NULL); -} - -static Node * -eval_const_expressions_mutator(Node *node, void *context) -{ - if (node == NULL) - return NULL; - if (IsA(node, Expr)) - { - Expr *expr = (Expr *) node; - List *args; - Const *const_input; - Expr *newexpr; - - /* - * Reduce constants in the Expr's arguments. We know args is - * either NIL or a List node, so we can call - * expression_tree_mutator directly rather than recursing to self. - */ - args = (List *) expression_tree_mutator((Node *) expr->args, - eval_const_expressions_mutator, - (void *) context); - - switch (expr->opType) - { - case OP_EXPR: - case FUNC_EXPR: - - /* - * Code for op/func case is pretty bulky, so split it out - * as a separate function. - */ - newexpr = simplify_op_or_func(expr, args); - if (newexpr) /* successfully simplified it */ - return (Node *) newexpr; - - /* - * else fall out to build new Expr node with simplified - * args - */ - break; - case OR_EXPR: - { - - /*---------- - * OR arguments are handled as follows: - * non constant: keep - * FALSE: drop (does not affect result) - * TRUE: force result to TRUE - * NULL: keep only one - * We keep one NULL input because ExecEvalOr returns NULL - * when no input is TRUE and at least one is NULL. - *---------- - */ - List *newargs = NIL; - List *arg; - bool haveNull = false; - bool forceTrue = false; - - foreach(arg, args) - { - if (!IsA(lfirst(arg), Const)) - { - newargs = lappend(newargs, lfirst(arg)); - continue; - } - const_input = (Const *) lfirst(arg); - if (const_input->constisnull) - haveNull = true; - else if (DatumGetBool(const_input->constvalue)) - forceTrue = true; - /* otherwise, we can drop the constant-false input */ - } - - /* - * We could return TRUE before falling out of the - * loop, but this coding method will be easier to - * adapt if we ever add a notion of non-removable - * functions. We'd need to check all the inputs for - * non-removability. - */ - if (forceTrue) - return MAKEBOOLCONST(true, false); - if (haveNull) - newargs = lappend(newargs, MAKEBOOLCONST(false, true)); - /* If all the inputs are FALSE, result is FALSE */ - if (newargs == NIL) - return MAKEBOOLCONST(false, false); - /* If only one nonconst-or-NULL input, it's the result */ - if (lnext(newargs) == NIL) - return (Node *) lfirst(newargs); - /* Else we still need an OR node */ - return (Node *) make_orclause(newargs); - } - case AND_EXPR: - { - - /*---------- - * AND arguments are handled as follows: - * non constant: keep - * TRUE: drop (does not affect result) - * FALSE: force result to FALSE - * NULL: keep only one - * We keep one NULL input because ExecEvalAnd returns NULL - * when no input is FALSE and at least one is NULL. - *---------- - */ - List *newargs = NIL; - List *arg; - bool haveNull = false; - bool forceFalse = false; - - foreach(arg, args) - { - if (!IsA(lfirst(arg), Const)) - { - newargs = lappend(newargs, lfirst(arg)); - continue; - } - const_input = (Const *) lfirst(arg); - if (const_input->constisnull) - haveNull = true; - else if (!DatumGetBool(const_input->constvalue)) - forceFalse = true; - /* otherwise, we can drop the constant-true input */ - } - - /* - * We could return FALSE before falling out of the - * loop, but this coding method will be easier to - * adapt if we ever add a notion of non-removable - * functions. We'd need to check all the inputs for - * non-removability. - */ - if (forceFalse) - return MAKEBOOLCONST(false, false); - if (haveNull) - newargs = lappend(newargs, MAKEBOOLCONST(false, true)); - /* If all the inputs are TRUE, result is TRUE */ - if (newargs == NIL) - return MAKEBOOLCONST(true, false); - /* If only one nonconst-or-NULL input, it's the result */ - if (lnext(newargs) == NIL) - return (Node *) lfirst(newargs); - /* Else we still need an AND node */ - return (Node *) make_andclause(newargs); - } - case NOT_EXPR: - Assert(length(args) == 1); - if (!IsA(lfirst(args), Const)) - break; - const_input = (Const *) lfirst(args); - /* NOT NULL => NULL */ - if (const_input->constisnull) - return MAKEBOOLCONST(false, true); - /* otherwise pretty easy */ - return MAKEBOOLCONST(!DatumGetBool(const_input->constvalue), - false); - case SUBPLAN_EXPR: - - /* - * Safety measure per notes at head of this routine: - * return a SubPlan unchanged. Too late to do anything - * with it. The arglist simplification above was wasted - * work (the list probably only contains Var nodes - * anyway). - */ - return (Node *) expr; - default: - elog(ERROR, "eval_const_expressions: unexpected opType %d", - (int) expr->opType); - break; - } - - /* - * If we break out of the above switch on opType, then the - * expression cannot be simplified any further, so build and - * return a replacement Expr node using the possibly-simplified - * arguments and the original oper node. Can't use make_clause() - * here because we want to be sure the typeOid field is - * preserved... - */ - newexpr = makeNode(Expr); - newexpr->typeOid = expr->typeOid; - newexpr->opType = expr->opType; - newexpr->oper = expr->oper; - newexpr->args = args; - return (Node *) newexpr; - } - if (IsA(node, RelabelType)) - { - /* - * If we can simplify the input to a constant, then we don't need - * the RelabelType node anymore: just change the type field of the - * Const node. Otherwise, must copy the RelabelType node. - */ - RelabelType *relabel = (RelabelType *) node; - Node *arg; - - arg = eval_const_expressions_mutator(relabel->arg, context); - - /* - * If we find stacked RelabelTypes (eg, from foo :: int :: oid) we - * can discard all but the top one. - */ - while (arg && IsA(arg, RelabelType)) - arg = ((RelabelType *) arg)->arg; - - if (arg && IsA(arg, Const)) - { - Const *con = (Const *) arg; - - con->consttype = relabel->resulttype; - - /* - * relabel's resulttypmod is discarded, which is OK for now; - * if the type actually needs a runtime length coercion then - * there should be a function call to do it just above this - * node. - */ - return (Node *) con; - } - else - { - RelabelType *newrelabel = makeNode(RelabelType); - - newrelabel->arg = arg; - newrelabel->resulttype = relabel->resulttype; - newrelabel->resulttypmod = relabel->resulttypmod; - return (Node *) newrelabel; - } - } - if (IsA(node, CaseExpr)) - { - - /*---------- - * CASE expressions can be simplified if there are constant - * condition clauses: - * FALSE (or NULL): drop the alternative - * TRUE: drop all remaining alternatives - * If the first non-FALSE alternative is a constant TRUE, we can - * simplify the entire CASE to that alternative's expression. - * If there are no non-FALSE alternatives, we simplify the entire - * CASE to the default result (ELSE result). - *---------- - */ - CaseExpr *caseexpr = (CaseExpr *) node; - CaseExpr *newcase; - List *newargs = NIL; - Node *defresult; - Const *const_input; - List *arg; - - foreach(arg, caseexpr->args) - { - /* Simplify this alternative's condition and result */ - CaseWhen *casewhen = (CaseWhen *) - expression_tree_mutator((Node *) lfirst(arg), - eval_const_expressions_mutator, - (void *) context); - - Assert(IsA(casewhen, CaseWhen)); - if (casewhen->expr == NULL || - !IsA(casewhen->expr, Const)) - { - newargs = lappend(newargs, casewhen); - continue; - } - const_input = (Const *) casewhen->expr; - if (const_input->constisnull || - !DatumGetBool(const_input->constvalue)) - continue; /* drop alternative with FALSE condition */ - - /* - * Found a TRUE condition. If it's the first (un-dropped) - * alternative, the CASE reduces to just this alternative. - */ - if (newargs == NIL) - return casewhen->result; - - /* - * Otherwise, add it to the list, and drop all the rest. - */ - newargs = lappend(newargs, casewhen); - break; - } - - /* Simplify the default result */ - defresult = eval_const_expressions_mutator(caseexpr->defresult, - context); - - /* - * If no non-FALSE alternatives, CASE reduces to the default - * result - */ - if (newargs == NIL) - return defresult; - /* Otherwise we need a new CASE node */ - newcase = makeNode(CaseExpr); - newcase->casetype = caseexpr->casetype; - newcase->arg = NULL; - newcase->args = newargs; - newcase->defresult = defresult; - return (Node *) newcase; - } - - /* - * For any node type not handled above, we recurse using - * expression_tree_mutator, which will copy the node unchanged but try - * to simplify its arguments (if any) using this routine. For example: - * we cannot eliminate an ArrayRef node, but we might be able to - * simplify constant expressions in its subscripts. - */ - return expression_tree_mutator(node, eval_const_expressions_mutator, - (void *) context); -} - -/* - * Subroutine for eval_const_expressions: try to evaluate an op or func - * - * Inputs are the op or func Expr node, and the pre-simplified argument list. - * Returns a simplified expression if successful, or NULL if cannot - * simplify the op/func. - * - * XXX Possible future improvement: if the func is SQL-language, and its - * definition is simply "SELECT expression", we could parse and substitute - * the expression here. This would avoid much runtime overhead, and perhaps - * expose opportunities for constant-folding within the expression even if - * not all the func's input args are constants. It'd be appropriate to do - * that here, not in the parser, since we wouldn't want it to happen until - * after rule substitution/rewriting. - */ -static Expr * -simplify_op_or_func(Expr *expr, List *args) -{ - List *arg; - Oid funcid; - Oid result_typeid; - HeapTuple func_tuple; - Form_pg_proc funcform; - char provolatile; - bool proisstrict; - bool proretset; - int16 resultTypLen; - bool resultTypByVal; - Expr *newexpr; - ExprContext *econtext; - Datum const_val; - bool has_nonconst_input = false; - bool has_null_input = false; - bool const_is_null; - - /* - * Check for constant inputs and especially constant-NULL inputs. - */ - foreach(arg, args) - { - if (IsA(lfirst(arg), Const)) - has_null_input |= ((Const *) lfirst(arg))->constisnull; - else - has_nonconst_input = true; - } - - /* - * If the function is strict and has a constant-NULL input, it will - * never be called at all, so we can replace the call by a NULL - * constant even if there are other inputs that aren't constant. - * Otherwise, we can only simplify if all inputs are constants. We can - * skip the function lookup if neither case applies. - */ - if (has_nonconst_input && !has_null_input) - return NULL; - - /* - * Get the function procedure's OID and look to see whether it is - * marked immutable. - * - * Note we take the result type from the Oper or Func node, not the - * pg_proc tuple; probably necessary for binary-compatibility cases. - * - */ - if (expr->opType == OP_EXPR) - { - Oper *oper = (Oper *) expr->oper; - - replace_opid(oper); /* OK to scribble on input to this extent */ - funcid = oper->opid; - result_typeid = oper->opresulttype; - } - else - { - Func *func = (Func *) expr->oper; - - funcid = func->funcid; - result_typeid = func->funcresulttype; - } - - /* - * we could use func_volatile() here, but we need several fields out - * of the func tuple, so might as well just look it up once. - */ - func_tuple = SearchSysCache(PROCOID, - ObjectIdGetDatum(funcid), - 0, 0, 0); - if (!HeapTupleIsValid(func_tuple)) - elog(ERROR, "Function OID %u does not exist", funcid); - funcform = (Form_pg_proc) GETSTRUCT(func_tuple); - provolatile = funcform->provolatile; - proisstrict = funcform->proisstrict; - proretset = funcform->proretset; - ReleaseSysCache(func_tuple); - - if (provolatile != PROVOLATILE_IMMUTABLE) - return NULL; - - /* - * Also check to make sure it doesn't return a set. - */ - if (proretset) - return NULL; - - /* - * Now that we know if the function is strict, we can finish the - * checks for simplifiable inputs that we started above. - */ - if (proisstrict && has_null_input) - { - /* - * It's strict and has NULL input, so must produce NULL output. - * Return a NULL constant of the right type. - */ - return (Expr *) makeNullConst(result_typeid); - } - - /* - * Otherwise, can simplify only if all inputs are constants. (For a - * non-strict function, constant NULL inputs are treated the same as - * constant non-NULL inputs.) - */ - if (has_nonconst_input) - return NULL; - - /* - * OK, looks like we can simplify this operator/function. - * - * We use the executor's routine ExecEvalExpr() to avoid duplication of - * code and ensure we get the same result as the executor would get. - * - * Build a new Expr node containing the already-simplified arguments. The - * only other setup needed here is the replace_opid() that we already - * did for the OP_EXPR case. - */ - newexpr = makeNode(Expr); - newexpr->typeOid = expr->typeOid; - newexpr->opType = expr->opType; - newexpr->oper = expr->oper; - newexpr->args = args; - - /* Get info needed about result datatype */ - get_typlenbyval(result_typeid, &resultTypLen, &resultTypByVal); - - /* - * It is OK to pass a dummy econtext because none of the - * ExecEvalExpr() code used in this situation will use econtext. That - * might seem fortuitous, but it's not so unreasonable --- a constant - * expression does not depend on context, by definition, n'est ce pas? - */ - econtext = MakeExprContext(NULL, CurrentMemoryContext); - - const_val = ExecEvalExprSwitchContext((Node *) newexpr, econtext, - &const_is_null, NULL); - - /* Must copy result out of sub-context used by expression eval */ - if (!const_is_null) - const_val = datumCopy(const_val, resultTypByVal, resultTypLen); - - FreeExprContext(econtext); - pfree(newexpr); - - /* - * Make the constant result node. - */ - return (Expr *) makeConst(result_typeid, resultTypLen, - const_val, const_is_null, - resultTypByVal, false, false); -} - - -/* - * Standard expression-tree walking support - * - * We used to have near-duplicate code in many different routines that - * understood how to recurse through an expression node tree. That was - * a pain to maintain, and we frequently had bugs due to some particular - * routine neglecting to support a particular node type. In most cases, - * these routines only actually care about certain node types, and don't - * care about other types except insofar as they have to recurse through - * non-primitive node types. Therefore, we now provide generic tree-walking - * logic to consolidate the redundant "boilerplate" code. There are - * two versions: expression_tree_walker() and expression_tree_mutator(). - */ - -/*-------------------- - * expression_tree_walker() is designed to support routines that traverse - * a tree in a read-only fashion (although it will also work for routines - * that modify nodes in-place but never add/delete/replace nodes). - * A walker routine should look like this: - * - * bool my_walker (Node *node, my_struct *context) - * { - * if (node == NULL) - * return false; - * // check for nodes that special work is required for, eg: - * if (IsA(node, Var)) - * { - * ... do special actions for Var nodes - * } - * else if (IsA(node, ...)) - * { - * ... do special actions for other node types - * } - * // for any node type not specially processed, do: - * return expression_tree_walker(node, my_walker, (void *) context); - * } - * - * The "context" argument points to a struct that holds whatever context - * information the walker routine needs --- it can be used to return data - * gathered by the walker, too. This argument is not touched by - * expression_tree_walker, but it is passed down to recursive sub-invocations - * of my_walker. The tree walk is started from a setup routine that - * fills in the appropriate context struct, calls my_walker with the top-level - * node of the tree, and then examines the results. - * - * The walker routine should return "false" to continue the tree walk, or - * "true" to abort the walk and immediately return "true" to the top-level - * caller. This can be used to short-circuit the traversal if the walker - * has found what it came for. "false" is returned to the top-level caller - * iff no invocation of the walker returned "true". - * - * The node types handled by expression_tree_walker include all those - * normally found in target lists and qualifier clauses during the planning - * stage. In particular, it handles List nodes since a cnf-ified qual clause - * will have List structure at the top level, and it handles TargetEntry nodes - * so that a scan of a target list can be handled without additional code. - * (But only the "expr" part of a TargetEntry is examined, unless the walker - * chooses to process TargetEntry nodes specially.) Also, RangeTblRef, - * FromExpr, JoinExpr, and SetOperationStmt nodes are handled, so that query - * jointrees and setOperation trees can be processed without additional code. - * - * expression_tree_walker will handle SubLink and SubPlan nodes by recursing - * normally into the "lefthand" arguments (which belong to the outer plan). - * It will also call the walker on the sub-Query node; however, when - * expression_tree_walker itself is called on a Query node, it does nothing - * and returns "false". The net effect is that unless the walker does - * something special at a Query node, sub-selects will not be visited - * during an expression tree walk. This is exactly the behavior wanted - * in many cases --- and for those walkers that do want to recurse into - * sub-selects, special behavior is typically needed anyway at the entry - * to a sub-select (such as incrementing a depth counter). A walker that - * wants to examine sub-selects should include code along the lines of: - * - * if (IsA(node, Query)) - * { - * adjust context for subquery; - * result = query_tree_walker((Query *) node, my_walker, context, - * true); // to visit subquery RTEs too - * restore context if needed; - * return result; - * } - * - * query_tree_walker is a convenience routine (see below) that calls the - * walker on all the expression subtrees of the given Query node. - * - * NOTE: currently, because make_subplan() clears the subselect link in - * a SubLink node, it is not actually possible to recurse into subselects - * of an already-planned expression tree. This is OK for current uses, - * but ought to be cleaned up when we redesign querytree processing. - *-------------------- - */ - -bool -expression_tree_walker(Node *node, - bool (*walker) (), - void *context) -{ - List *temp; - - /* - * The walker has already visited the current node, and so we need - * only recurse into any sub-nodes it has. - * - * We assume that the walker is not interested in List nodes per se, so - * when we expect a List we just recurse directly to self without - * bothering to call the walker. - */ - if (node == NULL) - return false; - switch (nodeTag(node)) - { - case T_Const: - case T_Var: - case T_Param: - case T_RangeTblRef: - /* primitive node types with no subnodes */ - break; - case T_Expr: - { - Expr *expr = (Expr *) node; - - if (expr->opType == SUBPLAN_EXPR) - { - /* recurse to the SubLink node (skipping SubPlan!) */ - if (walker((Node *) ((SubPlan *) expr->oper)->sublink, - context)) - return true; - } - /* for all Expr node types, examine args list */ - if (expression_tree_walker((Node *) expr->args, - walker, context)) - return true; - } - break; - case T_Aggref: - return walker(((Aggref *) node)->target, context); - case T_ArrayRef: - { - ArrayRef *aref = (ArrayRef *) node; - - /* recurse directly for upper/lower array index lists */ - if (expression_tree_walker((Node *) aref->refupperindexpr, - walker, context)) - return true; - if (expression_tree_walker((Node *) aref->reflowerindexpr, - walker, context)) - return true; - /* walker must see the refexpr and refassgnexpr, however */ - if (walker(aref->refexpr, context)) - return true; - if (walker(aref->refassgnexpr, context)) - return true; - } - break; - case T_FieldSelect: - return walker(((FieldSelect *) node)->arg, context); - case T_RelabelType: - return walker(((RelabelType *) node)->arg, context); - case T_CaseExpr: - { - CaseExpr *caseexpr = (CaseExpr *) node; - - /* we assume walker doesn't care about CaseWhens, either */ - foreach(temp, caseexpr->args) - { - CaseWhen *when = (CaseWhen *) lfirst(temp); - - Assert(IsA(when, CaseWhen)); - if (walker(when->expr, context)) - return true; - if (walker(when->result, context)) - return true; - } - /* caseexpr->arg should be null, but we'll check it anyway */ - if (walker(caseexpr->arg, context)) - return true; - if (walker(caseexpr->defresult, context)) - return true; - } - break; - case T_NullTest: - return walker(((NullTest *) node)->arg, context); - case T_BooleanTest: - return walker(((BooleanTest *) node)->arg, context); - case T_SubLink: - { - SubLink *sublink = (SubLink *) node; - - /* - * If the SubLink has already been processed by - * subselect.c, it will have lefthand=NIL, and we need to - * scan the oper list. Otherwise we only need to look at - * the lefthand list (the incomplete Oper nodes in the - * oper list are deemed uninteresting, perhaps even - * confusing). - */ - if (sublink->lefthand) - { - if (walker((Node *) sublink->lefthand, context)) - return true; - } - else - { - if (walker((Node *) sublink->oper, context)) - return true; - } - - /* - * Also invoke the walker on the sublink's Query node, so - * it can recurse into the sub-query if it wants to. - */ - return walker(sublink->subselect, context); - } - break; - case T_Query: - /* Do nothing with a sub-Query, per discussion above */ - break; - case T_List: - foreach(temp, (List *) node) - { - if (walker((Node *) lfirst(temp), context)) - return true; - } - break; - case T_TargetEntry: - return walker(((TargetEntry *) node)->expr, context); - case T_FromExpr: - { - FromExpr *from = (FromExpr *) node; - - if (walker(from->fromlist, context)) - return true; - if (walker(from->quals, context)) - return true; - } - break; - case T_JoinExpr: - { - JoinExpr *join = (JoinExpr *) node; - - if (walker(join->larg, context)) - return true; - if (walker(join->rarg, context)) - return true; - if (walker(join->quals, context)) - return true; - /* - * alias clause, using list are deemed uninteresting. - */ - } - break; - case T_SetOperationStmt: - { - SetOperationStmt *setop = (SetOperationStmt *) node; - - if (walker(setop->larg, context)) - return true; - if (walker(setop->rarg, context)) - return true; - } - break; - default: - elog(ERROR, "expression_tree_walker: Unexpected node type %d", - nodeTag(node)); - break; - } - return false; -} - -/* - * query_tree_walker --- initiate a walk of a Query's expressions - * - * This routine exists just to reduce the number of places that need to know - * where all the expression subtrees of a Query are. Note it can be used - * for starting a walk at top level of a Query regardless of whether the - * walker intends to descend into subqueries. It is also useful for - * descending into subqueries within a walker. - * - * If visitQueryRTEs is true, the walker will also be called on sub-Query - * nodes present in subquery rangetable entries of the given Query. This - * is optional since some callers handle those sub-queries separately, - * or don't really want to see subqueries anyway. - */ -bool -query_tree_walker(Query *query, - bool (*walker) (), - void *context, - bool visitQueryRTEs) -{ - List *rt; - - Assert(query != NULL && IsA(query, Query)); - - if (walker((Node *) query->targetList, context)) - return true; - if (walker((Node *) query->jointree, context)) - return true; - if (walker(query->setOperations, context)) - return true; - if (walker(query->havingQual, context)) - return true; - foreach(rt, query->rtable) - { - RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt); - - switch (rte->rtekind) - { - case RTE_RELATION: - case RTE_SPECIAL: - /* nothing to do */ - break; - case RTE_SUBQUERY: - if (visitQueryRTEs) - if (walker(rte->subquery, context)) - return true; - break; - case RTE_JOIN: - if (walker(rte->joinaliasvars, context)) - return true; - break; - case RTE_FUNCTION: - if (walker(rte->funcexpr, context)) - return true; - break; - } - } - return false; -} - - -/*-------------------- - * expression_tree_mutator() is designed to support routines that make a - * modified copy of an expression tree, with some nodes being added, - * removed, or replaced by new subtrees. The original tree is (normally) - * not changed. Each recursion level is responsible for returning a copy of - * (or appropriately modified substitute for) the subtree it is handed. - * A mutator routine should look like this: - * - * Node * my_mutator (Node *node, my_struct *context) - * { - * if (node == NULL) - * return NULL; - * // check for nodes that special work is required for, eg: - * if (IsA(node, Var)) - * { - * ... create and return modified copy of Var node - * } - * else if (IsA(node, ...)) - * { - * ... do special transformations of other node types - * } - * // for any node type not specially processed, do: - * return expression_tree_mutator(node, my_mutator, (void *) context); - * } - * - * The "context" argument points to a struct that holds whatever context - * information the mutator routine needs --- it can be used to return extra - * data gathered by the mutator, too. This argument is not touched by - * expression_tree_mutator, but it is passed down to recursive sub-invocations - * of my_mutator. The tree walk is started from a setup routine that - * fills in the appropriate context struct, calls my_mutator with the - * top-level node of the tree, and does any required post-processing. - * - * Each level of recursion must return an appropriately modified Node. - * If expression_tree_mutator() is called, it will make an exact copy - * of the given Node, but invoke my_mutator() to copy the sub-node(s) - * of that Node. In this way, my_mutator() has full control over the - * copying process but need not directly deal with expression trees - * that it has no interest in. - * - * Just as for expression_tree_walker, the node types handled by - * expression_tree_mutator include all those normally found in target lists - * and qualifier clauses during the planning stage. - * - * expression_tree_mutator will handle a SUBPLAN_EXPR node by recursing into - * the args and slink->oper lists (which belong to the outer plan), but it - * will simply copy the link to the inner plan, since that's typically what - * expression tree mutators want. A mutator that wants to modify the subplan - * can force appropriate behavior by recognizing subplan expression nodes - * and doing the right thing. - * - * Bare SubLink nodes (without a SUBPLAN_EXPR) are handled by recursing into - * the "lefthand" argument list only. (A bare SubLink should be seen only if - * the tree has not yet been processed by subselect.c.) Again, this can be - * overridden by the mutator, but it seems to be the most useful default - * behavior. - *-------------------- - */ - -Node * -expression_tree_mutator(Node *node, - Node *(*mutator) (), - void *context) -{ - /* - * The mutator has already decided not to modify the current node, but - * we must call the mutator for any sub-nodes. - */ - -#define FLATCOPY(newnode, node, nodetype) \ - ( (newnode) = makeNode(nodetype), \ - memcpy((newnode), (node), sizeof(nodetype)) ) - -#define CHECKFLATCOPY(newnode, node, nodetype) \ - ( AssertMacro(IsA((node), nodetype)), \ - (newnode) = makeNode(nodetype), \ - memcpy((newnode), (node), sizeof(nodetype)) ) - -#define MUTATE(newfield, oldfield, fieldtype) \ - ( (newfield) = (fieldtype) mutator((Node *) (oldfield), context) ) - - if (node == NULL) - return NULL; - switch (nodeTag(node)) - { - case T_Const: - case T_Var: - case T_Param: - case T_RangeTblRef: - /* primitive node types with no subnodes */ - return (Node *) copyObject(node); - case T_Expr: - { - Expr *expr = (Expr *) node; - Expr *newnode; - - FLATCOPY(newnode, expr, Expr); - - if (expr->opType == SUBPLAN_EXPR) - { - SubLink *oldsublink = ((SubPlan *) expr->oper)->sublink; - SubPlan *newsubplan; - - /* flat-copy the oper node, which is a SubPlan */ - CHECKFLATCOPY(newsubplan, expr->oper, SubPlan); - newnode->oper = (Node *) newsubplan; - /* likewise its SubLink node */ - CHECKFLATCOPY(newsubplan->sublink, oldsublink, SubLink); - - /* - * transform args list (params to be passed to - * subplan) - */ - MUTATE(newnode->args, expr->args, List *); - /* transform sublink's oper list as well */ - MUTATE(newsubplan->sublink->oper, oldsublink->oper, List *); - - /* - * but not the subplan itself, which is referenced - * as-is - */ - } - else - { - /* - * for other Expr node types, just transform args - * list, linking to original oper node (OK?) - */ - MUTATE(newnode->args, expr->args, List *); - } - return (Node *) newnode; - } - break; - case T_Aggref: - { - Aggref *aggref = (Aggref *) node; - Aggref *newnode; - - FLATCOPY(newnode, aggref, Aggref); - MUTATE(newnode->target, aggref->target, Node *); - return (Node *) newnode; - } - break; - case T_ArrayRef: - { - ArrayRef *arrayref = (ArrayRef *) node; - ArrayRef *newnode; - - FLATCOPY(newnode, arrayref, ArrayRef); - MUTATE(newnode->refupperindexpr, arrayref->refupperindexpr, - List *); - MUTATE(newnode->reflowerindexpr, arrayref->reflowerindexpr, - List *); - MUTATE(newnode->refexpr, arrayref->refexpr, - Node *); - MUTATE(newnode->refassgnexpr, arrayref->refassgnexpr, - Node *); - return (Node *) newnode; - } - break; - case T_FieldSelect: - { - FieldSelect *fselect = (FieldSelect *) node; - FieldSelect *newnode; - - FLATCOPY(newnode, fselect, FieldSelect); - MUTATE(newnode->arg, fselect->arg, Node *); - return (Node *) newnode; - } - break; - case T_RelabelType: - { - RelabelType *relabel = (RelabelType *) node; - RelabelType *newnode; - - FLATCOPY(newnode, relabel, RelabelType); - MUTATE(newnode->arg, relabel->arg, Node *); - return (Node *) newnode; - } - break; - case T_CaseExpr: - { - CaseExpr *caseexpr = (CaseExpr *) node; - CaseExpr *newnode; - - FLATCOPY(newnode, caseexpr, CaseExpr); - MUTATE(newnode->args, caseexpr->args, List *); - /* caseexpr->arg should be null, but we'll check it anyway */ - MUTATE(newnode->arg, caseexpr->arg, Node *); - MUTATE(newnode->defresult, caseexpr->defresult, Node *); - return (Node *) newnode; - } - break; - case T_CaseWhen: - { - CaseWhen *casewhen = (CaseWhen *) node; - CaseWhen *newnode; - - FLATCOPY(newnode, casewhen, CaseWhen); - MUTATE(newnode->expr, casewhen->expr, Node *); - MUTATE(newnode->result, casewhen->result, Node *); - return (Node *) newnode; - } - break; - case T_NullTest: - { - NullTest *ntest = (NullTest *) node; - NullTest *newnode; - - FLATCOPY(newnode, ntest, NullTest); - MUTATE(newnode->arg, ntest->arg, Node *); - return (Node *) newnode; - } - break; - case T_BooleanTest: - { - BooleanTest *btest = (BooleanTest *) node; - BooleanTest *newnode; - - FLATCOPY(newnode, btest, BooleanTest); - MUTATE(newnode->arg, btest->arg, Node *); - return (Node *) newnode; - } - break; - case T_SubLink: - { - /* - * A "bare" SubLink (note we will not come here if we - * found a SUBPLAN_EXPR node above it). Transform the - * lefthand side, but not the oper list nor the subquery. - */ - SubLink *sublink = (SubLink *) node; - SubLink *newnode; - - FLATCOPY(newnode, sublink, SubLink); - MUTATE(newnode->lefthand, sublink->lefthand, List *); - return (Node *) newnode; - } - break; - case T_List: - { - /* - * We assume the mutator isn't interested in the list - * nodes per se, so just invoke it on each list element. - * NOTE: this would fail badly on a list with integer - * elements! - */ - List *resultlist = NIL; - List *temp; - - foreach(temp, (List *) node) - { - resultlist = lappend(resultlist, - mutator((Node *) lfirst(temp), - context)); - } - return (Node *) resultlist; - } - break; - case T_TargetEntry: - { - /* - * We mutate the expression, but not the resdom, by - * default. - */ - TargetEntry *targetentry = (TargetEntry *) node; - TargetEntry *newnode; - - FLATCOPY(newnode, targetentry, TargetEntry); - MUTATE(newnode->expr, targetentry->expr, Node *); - return (Node *) newnode; - } - break; - case T_FromExpr: - { - FromExpr *from = (FromExpr *) node; - FromExpr *newnode; - - FLATCOPY(newnode, from, FromExpr); - MUTATE(newnode->fromlist, from->fromlist, List *); - MUTATE(newnode->quals, from->quals, Node *); - return (Node *) newnode; - } - break; - case T_JoinExpr: - { - JoinExpr *join = (JoinExpr *) node; - JoinExpr *newnode; - - FLATCOPY(newnode, join, JoinExpr); - MUTATE(newnode->larg, join->larg, Node *); - MUTATE(newnode->rarg, join->rarg, Node *); - MUTATE(newnode->quals, join->quals, Node *); - /* We do not mutate alias or using by default */ - return (Node *) newnode; - } - break; - case T_SetOperationStmt: - { - SetOperationStmt *setop = (SetOperationStmt *) node; - SetOperationStmt *newnode; - - FLATCOPY(newnode, setop, SetOperationStmt); - MUTATE(newnode->larg, setop->larg, Node *); - MUTATE(newnode->rarg, setop->rarg, Node *); - return (Node *) newnode; - } - break; - default: - elog(ERROR, "expression_tree_mutator: Unexpected node type %d", - nodeTag(node)); - break; - } - /* can't get here, but keep compiler happy */ - return NULL; -} - - -/* - * query_tree_mutator --- initiate modification of a Query's expressions - * - * This routine exists just to reduce the number of places that need to know - * where all the expression subtrees of a Query are. Note it can be used - * for starting a walk at top level of a Query regardless of whether the - * mutator intends to descend into subqueries. It is also useful for - * descending into subqueries within a mutator. - * - * The specified Query node is modified-in-place; do a FLATCOPY() beforehand - * if you don't want to change the original. All substructure is safely - * copied, however. - * - * If visitQueryRTEs is true, the mutator will also be called on sub-Query - * nodes present in subquery rangetable entries of the given Query. This - * is optional since some callers handle those sub-queries separately, - * or don't really want to see subqueries anyway. - */ -void -query_tree_mutator(Query *query, - Node *(*mutator) (), - void *context, - bool visitQueryRTEs) -{ - List *newrt = NIL; - List *rt; - - Assert(query != NULL && IsA(query, Query)); - - MUTATE(query->targetList, query->targetList, List *); - MUTATE(query->jointree, query->jointree, FromExpr *); - MUTATE(query->setOperations, query->setOperations, Node *); - MUTATE(query->havingQual, query->havingQual, Node *); - foreach(rt, query->rtable) - { - RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt); - RangeTblEntry *newrte; - - switch (rte->rtekind) - { - case RTE_RELATION: - case RTE_SPECIAL: - /* nothing to do, don't bother to make a copy */ - break; - case RTE_SUBQUERY: - if (visitQueryRTEs) - { - FLATCOPY(newrte, rte, RangeTblEntry); - CHECKFLATCOPY(newrte->subquery, rte->subquery, Query); - MUTATE(newrte->subquery, newrte->subquery, Query *); - rte = newrte; - } - break; - case RTE_JOIN: - FLATCOPY(newrte, rte, RangeTblEntry); - MUTATE(newrte->joinaliasvars, rte->joinaliasvars, List *); - rte = newrte; - break; - case RTE_FUNCTION: - FLATCOPY(newrte, rte, RangeTblEntry); - MUTATE(newrte->funcexpr, rte->funcexpr, Node *); - rte = newrte; - break; - } - newrt = lappend(newrt, rte); - } - query->rtable = newrt; -} diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c deleted file mode 100644 index 0f3cf201908..00000000000 --- a/src/backend/optimizer/util/joininfo.c +++ /dev/null @@ -1,76 +0,0 @@ -/*------------------------------------------------------------------------- - * - * joininfo.c - * JoinInfo node manipulation routines - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.31 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - - -#include "optimizer/joininfo.h" - -static JoinInfo *joininfo_member(List *join_relids, List *joininfo_list); - -/* - * joininfo_member - * Determines whether a node has already been created for a join - * between a set of join relations and the relation described by - * 'joininfo_list'. - * - * 'join_relids' is a list of relids corresponding to the join relation - * 'joininfo_list' is the list of joininfo nodes against which this is - * checked - * - * Returns the corresponding node in 'joininfo_list' if such a node - * exists. - * - */ -static JoinInfo * -joininfo_member(List *join_relids, List *joininfo_list) -{ - List *i; - - foreach(i, joininfo_list) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(i); - - if (sameseti(join_relids, joininfo->unjoined_relids)) - return joininfo; - } - return NULL; -} - - -/* - * find_joininfo_node - * Find the joininfo node within a relation entry corresponding - * to a join between 'this_rel' and the relations in 'join_relids'. - * A new node is created and added to the relation entry's joininfo - * field if the desired one can't be found. - * - * Returns a joininfo node. - * - */ -JoinInfo * -find_joininfo_node(RelOptInfo *this_rel, Relids join_relids) -{ - JoinInfo *joininfo = joininfo_member(join_relids, - this_rel->joininfo); - - if (joininfo == NULL) - { - joininfo = makeNode(JoinInfo); - joininfo->unjoined_relids = join_relids; - joininfo->jinfo_restrictinfo = NIL; - this_rel->joininfo = lcons(joininfo, this_rel->joininfo); - } - return joininfo; -} diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c deleted file mode 100644 index 4b3c9809b8b..00000000000 --- a/src/backend/optimizer/util/pathnode.c +++ /dev/null @@ -1,620 +0,0 @@ -/*------------------------------------------------------------------------- - * - * pathnode.c - * Routines to manipulate pathlists and create path nodes - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.78 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include <math.h> - -#include "nodes/plannodes.h" -#include "optimizer/cost.h" -#include "optimizer/pathnode.h" -#include "optimizer/paths.h" -#include "optimizer/restrictinfo.h" - - -/***************************************************************************** - * MISC. PATH UTILITIES - *****************************************************************************/ - -/* - * compare_path_costs - * Return -1, 0, or +1 according as path1 is cheaper, the same cost, - * or more expensive than path2 for the specified criterion. - */ -int -compare_path_costs(Path *path1, Path *path2, CostSelector criterion) -{ - if (criterion == STARTUP_COST) - { - if (path1->startup_cost < path2->startup_cost) - return -1; - if (path1->startup_cost > path2->startup_cost) - return +1; - - /* - * If paths have the same startup cost (not at all unlikely), - * order them by total cost. - */ - if (path1->total_cost < path2->total_cost) - return -1; - if (path1->total_cost > path2->total_cost) - return +1; - } - else - { - if (path1->total_cost < path2->total_cost) - return -1; - if (path1->total_cost > path2->total_cost) - return +1; - - /* - * If paths have the same total cost, order them by startup cost. - */ - if (path1->startup_cost < path2->startup_cost) - return -1; - if (path1->startup_cost > path2->startup_cost) - return +1; - } - return 0; -} - -/* - * compare_path_fractional_costs - * Return -1, 0, or +1 according as path1 is cheaper, the same cost, - * or more expensive than path2 for fetching the specified fraction - * of the total tuples. - * - * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the - * path with the cheaper total_cost. - */ -int -compare_fractional_path_costs(Path *path1, Path *path2, - double fraction) -{ - Cost cost1, - cost2; - - if (fraction <= 0.0 || fraction >= 1.0) - return compare_path_costs(path1, path2, TOTAL_COST); - cost1 = path1->startup_cost + - fraction * (path1->total_cost - path1->startup_cost); - cost2 = path2->startup_cost + - fraction * (path2->total_cost - path2->startup_cost); - if (cost1 < cost2) - return -1; - if (cost1 > cost2) - return +1; - return 0; -} - -/* - * set_cheapest - * Find the minimum-cost paths from among a relation's paths, - * and save them in the rel's cheapest-path fields. - * - * This is normally called only after we've finished constructing the path - * list for the rel node. - * - * If we find two paths of identical costs, try to keep the better-sorted one. - * The paths might have unrelated sort orderings, in which case we can only - * guess which might be better to keep, but if one is superior then we - * definitely should keep it. - */ -void -set_cheapest(RelOptInfo *parent_rel) -{ - List *pathlist = parent_rel->pathlist; - List *p; - Path *cheapest_startup_path; - Path *cheapest_total_path; - - Assert(IsA(parent_rel, RelOptInfo)); - - if (pathlist == NIL) - elog(ERROR, "Unable to devise a query plan for the given query"); - - cheapest_startup_path = cheapest_total_path = (Path *) lfirst(pathlist); - - foreach(p, lnext(pathlist)) - { - Path *path = (Path *) lfirst(p); - int cmp; - - cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST); - if (cmp > 0 || - (cmp == 0 && - compare_pathkeys(cheapest_startup_path->pathkeys, - path->pathkeys) == PATHKEYS_BETTER2)) - cheapest_startup_path = path; - - cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST); - if (cmp > 0 || - (cmp == 0 && - compare_pathkeys(cheapest_total_path->pathkeys, - path->pathkeys) == PATHKEYS_BETTER2)) - cheapest_total_path = path; - } - - parent_rel->cheapest_startup_path = cheapest_startup_path; - parent_rel->cheapest_total_path = cheapest_total_path; -} - -/* - * add_path - * Consider a potential implementation path for the specified parent rel, - * and add it to the rel's pathlist if it is worthy of consideration. - * A path is worthy if it has either a better sort order (better pathkeys) - * or cheaper cost (on either dimension) than any of the existing old paths. - * - * Unless parent_rel->pruneable is false, we also remove from the rel's - * pathlist any old paths that are dominated by new_path --- that is, - * new_path is both cheaper and at least as well ordered. - * - * The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths - * at the front. No code depends on that for correctness; it's simply - * a speed hack within this routine. Doing it that way makes it more - * likely that we will reject an inferior path after a few comparisons, - * rather than many comparisons. - * - * NOTE: discarded Path objects are immediately pfree'd to reduce planner - * memory consumption. We dare not try to free the substructure of a Path, - * since much of it may be shared with other Paths or the query tree itself; - * but just recycling discarded Path nodes is a very useful savings in - * a large join tree. We can recycle the List nodes of pathlist, too. - * - * 'parent_rel' is the relation entry to which the path corresponds. - * 'new_path' is a potential path for parent_rel. - * - * Returns nothing, but modifies parent_rel->pathlist. - */ -void -add_path(RelOptInfo *parent_rel, Path *new_path) -{ - bool accept_new = true; /* unless we find a superior old - * path */ - List *insert_after = NIL; /* where to insert new item */ - List *p1_prev = NIL; - List *p1; - - /* - * Loop to check proposed new path against old paths. Note it is - * possible for more than one old path to be tossed out because - * new_path dominates it. - */ - p1 = parent_rel->pathlist; /* cannot use foreach here */ - while (p1 != NIL) - { - Path *old_path = (Path *) lfirst(p1); - bool remove_old = false; /* unless new proves superior */ - int costcmp; - - costcmp = compare_path_costs(new_path, old_path, TOTAL_COST); - - /* - * If the two paths compare differently for startup and total - * cost, then we want to keep both, and we can skip the (much - * slower) comparison of pathkeys. If they compare the same, - * proceed with the pathkeys comparison. Note: this test relies - * on the fact that compare_path_costs will only return 0 if both - * costs are equal (and, therefore, there's no need to call it - * twice in that case). - */ - if (costcmp == 0 || - costcmp == compare_path_costs(new_path, old_path, - STARTUP_COST)) - { - switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys)) - { - case PATHKEYS_EQUAL: - if (costcmp < 0) - remove_old = true; /* new dominates old */ - else - accept_new = false; /* old equals or dominates - * new */ - break; - case PATHKEYS_BETTER1: - if (costcmp <= 0) - remove_old = true; /* new dominates old */ - break; - case PATHKEYS_BETTER2: - if (costcmp >= 0) - accept_new = false; /* old dominates new */ - break; - case PATHKEYS_DIFFERENT: - /* keep both paths, since they have different ordering */ - break; - } - } - - /* - * Remove current element from pathlist if dominated by new, - * unless xfunc told us not to remove any paths. - */ - if (remove_old && parent_rel->pruneable) - { - List *p1_next = lnext(p1); - - if (p1_prev) - lnext(p1_prev) = p1_next; - else - parent_rel->pathlist = p1_next; - pfree(old_path); - pfree(p1); /* this is why we can't use foreach */ - p1 = p1_next; - } - else - { - /* new belongs after this old path if it has cost >= old's */ - if (costcmp >= 0) - insert_after = p1; - p1_prev = p1; - p1 = lnext(p1); - } - - /* - * If we found an old path that dominates new_path, we can quit - * scanning the pathlist; we will not add new_path, and we assume - * new_path cannot dominate any other elements of the pathlist. - */ - if (!accept_new) - break; - } - - if (accept_new) - { - /* Accept the new path: insert it at proper place in pathlist */ - if (insert_after) - lnext(insert_after) = lcons(new_path, lnext(insert_after)); - else - parent_rel->pathlist = lcons(new_path, parent_rel->pathlist); - } - else - { - /* Reject and recycle the new path */ - pfree(new_path); - } -} - - -/***************************************************************************** - * PATH NODE CREATION ROUTINES - *****************************************************************************/ - -/* - * create_seqscan_path - * Creates a path corresponding to a sequential scan, returning the - * pathnode. - */ -Path * -create_seqscan_path(Query *root, RelOptInfo *rel) -{ - Path *pathnode = makeNode(Path); - - pathnode->pathtype = T_SeqScan; - pathnode->parent = rel; - pathnode->pathkeys = NIL; /* seqscan has unordered result */ - - cost_seqscan(pathnode, root, rel); - - return pathnode; -} - -/* - * create_index_path - * Creates a path node for an index scan. - * - * 'rel' is the parent rel - * 'index' is an index on 'rel' - * 'restriction_clauses' is a list of RestrictInfo nodes - * to be used as index qual conditions in the scan. - * 'pathkeys' describes the ordering of the path. - * 'indexscandir' is ForwardScanDirection or BackwardScanDirection - * for an ordered index, or NoMovementScanDirection for - * an unordered index. - * - * Returns the new path node. - */ -IndexPath * -create_index_path(Query *root, - RelOptInfo *rel, - IndexOptInfo *index, - List *restriction_clauses, - List *pathkeys, - ScanDirection indexscandir) -{ - IndexPath *pathnode = makeNode(IndexPath); - List *indexquals; - - pathnode->path.pathtype = T_IndexScan; - pathnode->path.parent = rel; - pathnode->path.pathkeys = pathkeys; - - indexquals = get_actual_clauses(restriction_clauses); - /* expand special operators to indexquals the executor can handle */ - indexquals = expand_indexqual_conditions(indexquals); - - /* - * We are making a pathnode for a single-scan indexscan; therefore, - * both indexinfo and indexqual should be single-element lists. - */ - pathnode->indexinfo = makeList1(index); - pathnode->indexqual = makeList1(indexquals); - - pathnode->indexscandir = indexscandir; - - /* - * This routine is only used to generate "standalone" indexpaths, not - * nestloop inner indexpaths. So joinrelids is always NIL and the - * number of rows is the same as the parent rel's estimate. - */ - pathnode->joinrelids = NIL; /* no join clauses here */ - pathnode->alljoinquals = false; - pathnode->rows = rel->rows; - - /* - * Not sure if this is necessary, but it should help if the statistics - * are too far off - */ - if (index->indpred && index->tuples < pathnode->rows) - pathnode->rows = index->tuples; - - cost_index(&pathnode->path, root, rel, index, indexquals, false); - - return pathnode; -} - -/* - * create_tidscan_path - * Creates a path corresponding to a tid_direct scan, returning the - * pathnode. - */ -TidPath * -create_tidscan_path(Query *root, RelOptInfo *rel, List *tideval) -{ - TidPath *pathnode = makeNode(TidPath); - - pathnode->path.pathtype = T_TidScan; - pathnode->path.parent = rel; - pathnode->path.pathkeys = NIL; - pathnode->tideval = copyObject(tideval); /* is copy really - * necessary? */ - pathnode->unjoined_relids = NIL; - - cost_tidscan(&pathnode->path, root, rel, tideval); - - /* - * divide selectivity for each clause to get an equal selectivity as - * IndexScan does OK ? - */ - - return pathnode; -} - -/* - * create_append_path - * Creates a path corresponding to an Append plan, returning the - * pathnode. - * - */ -AppendPath * -create_append_path(RelOptInfo *rel, List *subpaths) -{ - AppendPath *pathnode = makeNode(AppendPath); - List *l; - - pathnode->path.pathtype = T_Append; - pathnode->path.parent = rel; - pathnode->path.pathkeys = NIL; /* result is always considered - * unsorted */ - pathnode->subpaths = subpaths; - - pathnode->path.startup_cost = 0; - pathnode->path.total_cost = 0; - foreach(l, subpaths) - { - Path *subpath = (Path *) lfirst(l); - - if (l == subpaths) /* first node? */ - pathnode->path.startup_cost = subpath->startup_cost; - pathnode->path.total_cost += subpath->total_cost; - } - - return pathnode; -} - -/* - * create_subqueryscan_path - * Creates a path corresponding to a sequential scan of a subquery, - * returning the pathnode. - */ -Path * -create_subqueryscan_path(RelOptInfo *rel) -{ - Path *pathnode = makeNode(Path); - - pathnode->pathtype = T_SubqueryScan; - pathnode->parent = rel; - pathnode->pathkeys = NIL; /* for now, assume unordered result */ - - /* just copy the subplan's cost estimates */ - pathnode->startup_cost = rel->subplan->startup_cost; - pathnode->total_cost = rel->subplan->total_cost; - - return pathnode; -} - -/* - * create_functionscan_path - * Creates a path corresponding to a sequential scan of a function, - * returning the pathnode. - */ -Path * -create_functionscan_path(Query *root, RelOptInfo *rel) -{ - Path *pathnode = makeNode(Path); - - pathnode->pathtype = T_FunctionScan; - pathnode->parent = rel; - pathnode->pathkeys = NIL; /* for now, assume unordered result */ - - cost_functionscan(pathnode, root, rel); - - return pathnode; -} - -/* - * create_nestloop_path - * Creates a pathnode corresponding to a nestloop join between two - * relations. - * - * 'joinrel' is the join relation. - * 'jointype' is the type of join required - * 'outer_path' is the outer path - * 'inner_path' is the inner path - * 'restrict_clauses' are the RestrictInfo nodes to apply at the join - * 'pathkeys' are the path keys of the new join path - * - * Returns the resulting path node. - */ -NestPath * -create_nestloop_path(Query *root, - RelOptInfo *joinrel, - JoinType jointype, - Path *outer_path, - Path *inner_path, - List *restrict_clauses, - List *pathkeys) -{ - NestPath *pathnode = makeNode(NestPath); - - pathnode->path.pathtype = T_NestLoop; - pathnode->path.parent = joinrel; - pathnode->jointype = jointype; - pathnode->outerjoinpath = outer_path; - pathnode->innerjoinpath = inner_path; - pathnode->joinrestrictinfo = restrict_clauses; - pathnode->path.pathkeys = pathkeys; - - cost_nestloop(&pathnode->path, root, outer_path, inner_path, - restrict_clauses); - - return pathnode; -} - -/* - * create_mergejoin_path - * Creates a pathnode corresponding to a mergejoin join between - * two relations - * - * 'joinrel' is the join relation - * 'jointype' is the type of join required - * 'outer_path' is the outer path - * 'inner_path' is the inner path - * 'restrict_clauses' are the RestrictInfo nodes to apply at the join - * 'pathkeys' are the path keys of the new join path - * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses - * (this should be a subset of the restrict_clauses list) - * 'outersortkeys' are the sort varkeys for the outer relation - * 'innersortkeys' are the sort varkeys for the inner relation - */ -MergePath * -create_mergejoin_path(Query *root, - RelOptInfo *joinrel, - JoinType jointype, - Path *outer_path, - Path *inner_path, - List *restrict_clauses, - List *pathkeys, - List *mergeclauses, - List *outersortkeys, - List *innersortkeys) -{ - MergePath *pathnode = makeNode(MergePath); - - /* - * If the given paths are already well enough ordered, we can skip - * doing an explicit sort. - */ - if (outersortkeys && - pathkeys_contained_in(outersortkeys, outer_path->pathkeys)) - outersortkeys = NIL; - if (innersortkeys && - pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) - innersortkeys = NIL; - - pathnode->jpath.path.pathtype = T_MergeJoin; - pathnode->jpath.path.parent = joinrel; - pathnode->jpath.jointype = jointype; - pathnode->jpath.outerjoinpath = outer_path; - pathnode->jpath.innerjoinpath = inner_path; - pathnode->jpath.joinrestrictinfo = restrict_clauses; - pathnode->jpath.path.pathkeys = pathkeys; - pathnode->path_mergeclauses = mergeclauses; - pathnode->outersortkeys = outersortkeys; - pathnode->innersortkeys = innersortkeys; - - cost_mergejoin(&pathnode->jpath.path, - root, - outer_path, - inner_path, - restrict_clauses, - mergeclauses, - outersortkeys, - innersortkeys); - - return pathnode; -} - -/* - * create_hashjoin_path - * Creates a pathnode corresponding to a hash join between two relations. - * - * 'joinrel' is the join relation - * 'jointype' is the type of join required - * 'outer_path' is the cheapest outer path - * 'inner_path' is the cheapest inner path - * 'restrict_clauses' are the RestrictInfo nodes to apply at the join - * 'hashclauses' is a list of the hash join clause (always a 1-element list) - * (this should be a subset of the restrict_clauses list) - */ -HashPath * -create_hashjoin_path(Query *root, - RelOptInfo *joinrel, - JoinType jointype, - Path *outer_path, - Path *inner_path, - List *restrict_clauses, - List *hashclauses) -{ - HashPath *pathnode = makeNode(HashPath); - - pathnode->jpath.path.pathtype = T_HashJoin; - pathnode->jpath.path.parent = joinrel; - pathnode->jpath.jointype = jointype; - pathnode->jpath.outerjoinpath = outer_path; - pathnode->jpath.innerjoinpath = inner_path; - pathnode->jpath.joinrestrictinfo = restrict_clauses; - /* A hashjoin never has pathkeys, since its ordering is unpredictable */ - pathnode->jpath.path.pathkeys = NIL; - pathnode->path_hashclauses = hashclauses; - - cost_hashjoin(&pathnode->jpath.path, - root, - outer_path, - inner_path, - restrict_clauses, - hashclauses); - - return pathnode; -} diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c deleted file mode 100644 index b9a91d18627..00000000000 --- a/src/backend/optimizer/util/plancat.c +++ /dev/null @@ -1,363 +0,0 @@ -/*------------------------------------------------------------------------- - * - * plancat.c - * routines for accessing the system catalogs - * - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.73 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include <math.h> - -#include "access/genam.h" -#include "access/heapam.h" -#include "catalog/catname.h" -#include "catalog/pg_amop.h" -#include "catalog/pg_inherits.h" -#include "catalog/pg_index.h" -#include "optimizer/clauses.h" -#include "optimizer/plancat.h" -#include "parser/parsetree.h" -#include "utils/builtins.h" -#include "utils/fmgroids.h" -#include "utils/lsyscache.h" -#include "utils/relcache.h" -#include "utils/syscache.h" -#include "catalog/catalog.h" -#include "miscadmin.h" - - -/* - * get_relation_info - - * Retrieves catalog information for a given relation. - * Given the Oid of the relation, return the following info: - * whether the relation has secondary indices - * number of pages - * number of tuples - */ -void -get_relation_info(Oid relationObjectId, - bool *hasindex, long *pages, double *tuples) -{ - HeapTuple relationTuple; - Form_pg_class relation; - - relationTuple = SearchSysCache(RELOID, - ObjectIdGetDatum(relationObjectId), - 0, 0, 0); - if (!HeapTupleIsValid(relationTuple)) - elog(ERROR, "get_relation_info: Relation %u not found", - relationObjectId); - relation = (Form_pg_class) GETSTRUCT(relationTuple); - - if (IsIgnoringSystemIndexes() && IsSystemClass(relation)) - *hasindex = false; - else - *hasindex = relation->relhasindex; - - *pages = relation->relpages; - *tuples = relation->reltuples; - - ReleaseSysCache(relationTuple); -} - -/* - * find_secondary_indexes - * Creates a list of IndexOptInfo nodes containing information for each - * secondary index defined on the specified relation. - * - * 'relationObjectId' is the OID of the relation for which indices are wanted - * - * Returns a list of new IndexOptInfo nodes. - */ -List * -find_secondary_indexes(Oid relationObjectId) -{ - List *indexinfos = NIL; - List *indexoidlist, - *indexoidscan; - Relation relation; - - /* - * We used to scan pg_index directly, but now the relcache offers a - * cached list of OID indexes for each relation. So, get that list - * and then use the syscache to obtain pg_index entries. - */ - relation = heap_open(relationObjectId, AccessShareLock); - indexoidlist = RelationGetIndexList(relation); - - foreach(indexoidscan, indexoidlist) - { - Oid indexoid = lfirsti(indexoidscan); - Relation indexRelation; - Form_pg_index index; - IndexOptInfo *info; - int i; - int16 amorderstrategy; - - /* Extract info from the relation descriptor for the index */ - indexRelation = index_open(indexoid); - - info = makeNode(IndexOptInfo); - - /* - * Need to make these arrays large enough to be sure there is room - * for a terminating 0 at the end of each one. - */ - info->classlist = (Oid *) palloc(sizeof(Oid) * (INDEX_MAX_KEYS + 1)); - info->indexkeys = (int *) palloc(sizeof(int) * (INDEX_MAX_KEYS + 1)); - info->ordering = (Oid *) palloc(sizeof(Oid) * (INDEX_MAX_KEYS + 1)); - - /* Extract info from the pg_index tuple */ - index = indexRelation->rd_index; - info->indexoid = index->indexrelid; - info->indproc = index->indproc; /* functional index ?? */ - if (VARSIZE(&index->indpred) > VARHDRSZ) /* partial index ?? */ - { - char *predString; - - predString = DatumGetCString(DirectFunctionCall1(textout, - PointerGetDatum(&index->indpred))); - info->indpred = (List *) stringToNode(predString); - pfree(predString); - } - else - info->indpred = NIL; - info->unique = index->indisunique; - - for (i = 0; i < INDEX_MAX_KEYS; i++) - { - if (index->indclass[i] == (Oid) 0) - break; - info->classlist[i] = index->indclass[i]; - } - info->classlist[i] = (Oid) 0; - info->ncolumns = i; - - for (i = 0; i < INDEX_MAX_KEYS; i++) - { - if (index->indkey[i] == 0) - break; - info->indexkeys[i] = index->indkey[i]; - } - info->indexkeys[i] = 0; - info->nkeys = i; - - info->relam = indexRelation->rd_rel->relam; - info->pages = indexRelation->rd_rel->relpages; - info->tuples = indexRelation->rd_rel->reltuples; - info->amcostestimate = index_cost_estimator(indexRelation); - amorderstrategy = indexRelation->rd_am->amorderstrategy; - - /* - * Fetch the ordering operators associated with the index, if any. - */ - MemSet(info->ordering, 0, sizeof(Oid) * (INDEX_MAX_KEYS + 1)); - if (amorderstrategy != 0) - { - int oprindex = amorderstrategy - 1; - - for (i = 0; i < info->ncolumns; i++) - { - info->ordering[i] = indexRelation->rd_operator[oprindex]; - oprindex += indexRelation->rd_am->amstrategies; - } - } - - index_close(indexRelation); - - indexinfos = lcons(info, indexinfos); - } - - freeList(indexoidlist); - - /* XXX keep the lock here? */ - heap_close(relation, AccessShareLock); - - return indexinfos; -} - -/* - * restriction_selectivity - * - * Returns the selectivity of a specified restriction operator clause. - * This code executes registered procedures stored in the - * operator relation, by calling the function manager. - * - * varRelid is either 0 or a rangetable index. See clause_selectivity() - * for details about its meaning. - */ -Selectivity -restriction_selectivity(Query *root, - Oid operator, - List *args, - int varRelid) -{ - RegProcedure oprrest = get_oprrest(operator); - float8 result; - - /* - * if the oprrest procedure is missing for whatever reason, use a - * selectivity of 0.5 - */ - if (!oprrest) - return (Selectivity) 0.5; - - result = DatumGetFloat8(OidFunctionCall4(oprrest, - PointerGetDatum(root), - ObjectIdGetDatum(operator), - PointerGetDatum(args), - Int32GetDatum(varRelid))); - - if (result < 0.0 || result > 1.0) - elog(ERROR, "restriction_selectivity: bad value %f", result); - - return (Selectivity) result; -} - -/* - * join_selectivity - * - * Returns the selectivity of a specified join operator clause. - * This code executes registered procedures stored in the - * operator relation, by calling the function manager. - */ -Selectivity -join_selectivity(Query *root, - Oid operator, - List *args) -{ - RegProcedure oprjoin = get_oprjoin(operator); - float8 result; - - /* - * if the oprjoin procedure is missing for whatever reason, use a - * selectivity of 0.5 - */ - if (!oprjoin) - return (Selectivity) 0.5; - - result = DatumGetFloat8(OidFunctionCall3(oprjoin, - PointerGetDatum(root), - ObjectIdGetDatum(operator), - PointerGetDatum(args))); - - if (result < 0.0 || result > 1.0) - elog(ERROR, "join_selectivity: bad value %f", result); - - return (Selectivity) result; -} - -/* - * find_inheritance_children - * - * Returns an integer list containing the OIDs of all relations which - * inherit *directly* from the relation with OID 'inhparent'. - * - * XXX might be a good idea to create an index on pg_inherits' inhparent - * field, so that we can use an indexscan instead of sequential scan here. - * However, in typical databases pg_inherits won't have enough entries to - * justify an indexscan... - */ -List * -find_inheritance_children(Oid inhparent) -{ - List *list = NIL; - Relation relation; - HeapScanDesc scan; - HeapTuple inheritsTuple; - Oid inhrelid; - ScanKeyData key[1]; - - /* - * Can skip the scan if pg_class shows the relation has never had a - * subclass. - */ - if (!has_subclass(inhparent)) - return NIL; - - ScanKeyEntryInitialize(&key[0], - (bits16) 0x0, - (AttrNumber) Anum_pg_inherits_inhparent, - (RegProcedure) F_OIDEQ, - ObjectIdGetDatum(inhparent)); - relation = heap_openr(InheritsRelationName, AccessShareLock); - scan = heap_beginscan(relation, SnapshotNow, 1, key); - while ((inheritsTuple = heap_getnext(scan, ForwardScanDirection)) != NULL) - { - inhrelid = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhrelid; - list = lappendi(list, inhrelid); - } - heap_endscan(scan); - heap_close(relation, AccessShareLock); - return list; -} - -/* - * has_subclass - * - * In the current implementation, has_subclass returns whether a - * particular class *might* have a subclass. It will not return the - * correct result if a class had a subclass which was later dropped. - * This is because relhassubclass in pg_class is not updated when a - * subclass is dropped, primarily because of concurrency concerns. - * - * Currently has_subclass is only used as an efficiency hack to skip - * unnecessary inheritance searches, so this is OK. - */ -bool -has_subclass(Oid relationId) -{ - HeapTuple tuple; - bool result; - - tuple = SearchSysCache(RELOID, - ObjectIdGetDatum(relationId), - 0, 0, 0); - if (!HeapTupleIsValid(tuple)) - elog(ERROR, "has_subclass: Relation %u not found", relationId); - - result = ((Form_pg_class) GETSTRUCT(tuple))->relhassubclass; - ReleaseSysCache(tuple); - return result; -} - -/* - * has_unique_index - * - * Detect whether there is a unique index on the specified attribute - * of the specified relation, thus allowing us to conclude that all - * the (non-null) values of the attribute are distinct. - */ -bool -has_unique_index(RelOptInfo *rel, AttrNumber attno) -{ - List *ilist; - - foreach(ilist, rel->indexlist) - { - IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); - - /* - * Note: ignore functional and partial indexes, since they don't - * allow us to conclude that all attr values are distinct. Also, a - * multicolumn unique index doesn't allow us to conclude that just - * the specified attr is unique. - */ - if (index->unique && - index->nkeys == 1 && - index->indexkeys[0] == attno && - index->indproc == InvalidOid && - index->indpred == NIL) - return true; - } - return false; -} diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c deleted file mode 100644 index 978d9f0b303..00000000000 --- a/src/backend/optimizer/util/relnode.c +++ /dev/null @@ -1,679 +0,0 @@ -/*------------------------------------------------------------------------- - * - * relnode.c - * Relation-node lookup/construction routines - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.38 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include "optimizer/cost.h" -#include "optimizer/joininfo.h" -#include "optimizer/pathnode.h" -#include "optimizer/paths.h" -#include "optimizer/plancat.h" -#include "optimizer/tlist.h" -#include "parser/parsetree.h" - - -static RelOptInfo *make_base_rel(Query *root, int relid); -static List *new_join_tlist(List *tlist, int first_resdomno); -static List *build_joinrel_restrictlist(Query *root, - RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel); -static void build_joinrel_joinlist(RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel); -static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list); -static void subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list); - - -/* - * build_base_rel - * Construct a new base relation RelOptInfo, and put it in the query's - * base_rel_list. - */ -void -build_base_rel(Query *root, int relid) -{ - List *rels; - RelOptInfo *rel; - - /* Rel should not exist already */ - foreach(rels, root->base_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of base_rel_list */ - if (lfirsti(rel->relids) == relid) - elog(ERROR, "build_base_rel: rel already exists"); - } - - /* It should not exist as an "other" rel, either */ - foreach(rels, root->other_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) - elog(ERROR, "build_base_rel: rel already exists as 'other' rel"); - } - - /* No existing RelOptInfo for this base rel, so make a new one */ - rel = make_base_rel(root, relid); - - /* and add it to the list */ - root->base_rel_list = lcons(rel, root->base_rel_list); -} - -/* - * build_other_rel - * Returns relation entry corresponding to 'relid', creating a new one - * if necessary. This is for 'other' relations, which are much like - * base relations except that they live in a different list. - */ -RelOptInfo * -build_other_rel(Query *root, int relid) -{ - List *rels; - RelOptInfo *rel; - - /* Already made? */ - foreach(rels, root->other_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of other_rel_list */ - if (lfirsti(rel->relids) == relid) - return rel; - } - - /* It should not exist as a base rel */ - foreach(rels, root->base_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) - elog(ERROR, "build_other_rel: rel already exists as base rel"); - } - - /* No existing RelOptInfo for this other rel, so make a new one */ - rel = make_base_rel(root, relid); - - /* if it's not a join rel, must be a child rel */ - if (rel->reloptkind == RELOPT_BASEREL) - rel->reloptkind = RELOPT_OTHER_CHILD_REL; - - /* and add it to the list */ - root->other_rel_list = lcons(rel, root->other_rel_list); - - return rel; -} - -/* - * make_base_rel - * Construct a base-relation RelOptInfo for the specified rangetable index. - * - * Common code for build_base_rel and build_other_rel. - */ -static RelOptInfo * -make_base_rel(Query *root, int relid) -{ - RelOptInfo *rel = makeNode(RelOptInfo); - RangeTblEntry *rte = rt_fetch(relid, root->rtable); - - rel->reloptkind = RELOPT_BASEREL; - rel->relids = makeListi1(relid); - rel->rows = 0; - rel->width = 0; - rel->targetlist = NIL; - rel->pathlist = NIL; - rel->cheapest_startup_path = NULL; - rel->cheapest_total_path = NULL; - rel->pruneable = true; - rel->rtekind = rte->rtekind; - rel->indexlist = NIL; - rel->pages = 0; - rel->tuples = 0; - rel->subplan = NULL; - rel->joinrti = 0; - rel->joinrteids = NIL; - rel->baserestrictinfo = NIL; - rel->baserestrictcost = 0; - rel->outerjoinset = NIL; - rel->joininfo = NIL; - rel->innerjoin = NIL; - - /* Check type of rtable entry */ - switch (rte->rtekind) - { - case RTE_RELATION: - { - /* Table --- retrieve statistics from the system catalogs */ - bool indexed; - - get_relation_info(rte->relid, - &indexed, &rel->pages, &rel->tuples); - if (indexed) - rel->indexlist = find_secondary_indexes(rte->relid); - break; - } - case RTE_SUBQUERY: - case RTE_FUNCTION: - /* Subquery or function --- nothing to do here */ - break; - case RTE_JOIN: - /* Join --- must be an otherrel */ - rel->reloptkind = RELOPT_OTHER_JOIN_REL; - break; - default: - elog(ERROR, "make_base_rel: unsupported RTE kind %d", - (int) rte->rtekind); - break; - } - - return rel; -} - -/* - * find_base_rel - * Find a base or other relation entry, which must already exist - * (since we'd have no idea which list to add it to). - */ -RelOptInfo * -find_base_rel(Query *root, int relid) -{ - List *rels; - RelOptInfo *rel; - - foreach(rels, root->base_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - /* length(rel->relids) == 1 for all members of base_rel_list */ - if (lfirsti(rel->relids) == relid) - return rel; - } - - foreach(rels, root->other_rel_list) - { - rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) - return rel; - } - - elog(ERROR, "find_base_rel: no relation entry for relid %d", relid); - - return NULL; /* keep compiler quiet */ -} - -/* - * find_other_rel - * Find an otherrel entry, if one exists for the given relid. - * Return NULL if no entry. - */ -RelOptInfo * -find_other_rel(Query *root, int relid) -{ - List *rels; - - foreach(rels, root->other_rel_list) - { - RelOptInfo *rel = (RelOptInfo *) lfirst(rels); - - if (lfirsti(rel->relids) == relid) - return rel; - } - return NULL; -} - -/* - * find_other_rel_for_join - * Look for an otherrel for a join RTE matching the given baserel set. - * Return NULL if no entry. - */ -RelOptInfo * -find_other_rel_for_join(Query *root, List *relids) -{ - List *rels; - - foreach(rels, root->other_rel_list) - { - RelOptInfo *rel = (RelOptInfo *) lfirst(rels); - - if (rel->reloptkind == RELOPT_OTHER_JOIN_REL - && sameseti(relids, rel->outerjoinset)) - return rel; - } - return NULL; -} - -/* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a list of RT indexes), - * or NULL if none exists. This is for join relations. - * - * Note: there is probably no good reason for this to be called from - * anywhere except build_join_rel, but keep it as a separate routine - * just in case. - */ -static RelOptInfo * -find_join_rel(Query *root, Relids relids) -{ - List *joinrels; - - foreach(joinrels, root->join_rel_list) - { - RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels); - - if (sameseti(rel->relids, relids)) - return rel; - } - - return NULL; -} - -/* - * build_join_rel - * Returns relation entry corresponding to the union of two given rels, - * creating a new relation entry if none already exists. - * - * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be - * joined - * 'jointype': type of join (inner/outer) - * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr - * receives the list of RestrictInfo nodes that apply to this - * particular pair of joinable relations. - * - * restrictlist_ptr makes the routine's API a little grotty, but it saves - * duplicated calculation of the restrictlist... - */ -RelOptInfo * -build_join_rel(Query *root, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel, - JoinType jointype, - List **restrictlist_ptr) -{ - List *joinrelids; - RelOptInfo *joinrel; - RelOptInfo *joinrterel; - List *restrictlist; - List *new_outer_tlist; - List *new_inner_tlist; - - /* We should never try to join two overlapping sets of rels. */ - Assert(nonoverlap_setsi(outer_rel->relids, inner_rel->relids)); - - /* - * See if we already have a joinrel for this set of base rels. - * - * nconc(listCopy(x), y) is an idiom for making a new list without - * changing either input list. - */ - joinrelids = nconc(listCopy(outer_rel->relids), inner_rel->relids); - joinrel = find_join_rel(root, joinrelids); - - if (joinrel) - { - /* - * Yes, so we only need to figure the restrictlist for this - * particular pair of component relations. - */ - if (restrictlist_ptr) - *restrictlist_ptr = build_joinrel_restrictlist(root, - joinrel, - outer_rel, - inner_rel); - return joinrel; - } - - /* - * Nope, so make one. - */ - joinrel = makeNode(RelOptInfo); - joinrel->reloptkind = RELOPT_JOINREL; - joinrel->relids = joinrelids; - joinrel->rows = 0; - joinrel->width = 0; - joinrel->targetlist = NIL; - joinrel->pathlist = NIL; - joinrel->cheapest_startup_path = NULL; - joinrel->cheapest_total_path = NULL; - joinrel->pruneable = true; - joinrel->rtekind = RTE_JOIN; - joinrel->indexlist = NIL; - joinrel->pages = 0; - joinrel->tuples = 0; - joinrel->subplan = NULL; - joinrel->joinrti = 0; - joinrel->joinrteids = nconc(listCopy(outer_rel->joinrteids), - inner_rel->joinrteids); - joinrel->baserestrictinfo = NIL; - joinrel->baserestrictcost = 0; - joinrel->outerjoinset = NIL; - joinrel->joininfo = NIL; - joinrel->innerjoin = NIL; - - /* Is there a join RTE matching this join? */ - joinrterel = find_other_rel_for_join(root, joinrelids); - if (joinrterel) - { - /* Yes, remember its RT index */ - joinrel->joinrti = lfirsti(joinrterel->relids); - joinrel->joinrteids = lconsi(joinrel->joinrti, joinrel->joinrteids); - } - - /* - * Create a new tlist by removing irrelevant elements from both tlists - * of the outer and inner join relations and then merging the results - * together. - * - * XXX right now we don't remove any irrelevant elements, we just - * append the two tlists together. Someday consider pruning vars from the - * join's targetlist if they are needed only to evaluate restriction - * clauses of this join, and will never be accessed at higher levels of - * the plantree. - * - * NOTE: the tlist order for a join rel will depend on which pair of - * outer and inner rels we first try to build it from. But the - * contents should be the same regardless. - */ - new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1); - new_inner_tlist = new_join_tlist(inner_rel->targetlist, - length(new_outer_tlist) + 1); - joinrel->targetlist = nconc(new_outer_tlist, new_inner_tlist); - - /* - * If there are any alias variables attached to the matching join RTE, - * attach them to the tlist too, so that they will be evaluated for use - * at higher plan levels. - */ - if (joinrterel) - { - List *jrtetl; - - foreach(jrtetl, joinrterel->targetlist) - { - TargetEntry *jrtete = lfirst(jrtetl); - - add_var_to_tlist(joinrel, (Var *) jrtete->expr); - } - } - - /* - * Construct restrict and join clause lists for the new joinrel. (The - * caller might or might not need the restrictlist, but I need it - * anyway for set_joinrel_size_estimates().) - */ - restrictlist = build_joinrel_restrictlist(root, - joinrel, - outer_rel, - inner_rel); - if (restrictlist_ptr) - *restrictlist_ptr = restrictlist; - build_joinrel_joinlist(joinrel, outer_rel, inner_rel); - - /* - * Set estimates of the joinrel's size. - */ - set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, - jointype, restrictlist); - - /* - * Add the joinrel to the query's joinrel list. - */ - root->join_rel_list = lcons(joinrel, root->join_rel_list); - - return joinrel; -} - -/* - * new_join_tlist - * Builds a join relation's target list by keeping those elements that - * will be in the final target list and any other elements that are still - * needed for future joins. For a target list entry to still be needed - * for future joins, its 'joinlist' field must not be empty after removal - * of all relids in 'other_relids'. - * - * XXX the above comment refers to code that is long dead and gone; - * we don't keep track of joinlists for individual targetlist entries - * anymore. For now, all vars present in either input tlist will be - * emitted in the join's tlist. - * - * 'tlist' is the target list of one of the join relations - * 'first_resdomno' is the resdom number to use for the first created - * target list entry - * - * Returns the new target list. - */ -static List * -new_join_tlist(List *tlist, - int first_resdomno) -{ - int resdomno = first_resdomno - 1; - List *t_list = NIL; - List *i; - - foreach(i, tlist) - { - TargetEntry *xtl = lfirst(i); - - resdomno += 1; - t_list = lappend(t_list, - create_tl_element(get_expr(xtl), resdomno)); - } - - return t_list; -} - -/* - * build_joinrel_restrictlist - * build_joinrel_joinlist - * These routines build lists of restriction and join clauses for a - * join relation from the joininfo lists of the relations it joins. - * - * These routines are separate because the restriction list must be - * built afresh for each pair of input sub-relations we consider, whereas - * the join lists need only be computed once for any join RelOptInfo. - * The join lists are fully determined by the set of rels making up the - * joinrel, so we should get the same results (up to ordering) from any - * candidate pair of sub-relations. But the restriction list is whatever - * is not handled in the sub-relations, so it depends on which - * sub-relations are considered. - * - * If a join clause from an input relation refers to base rels still not - * present in the joinrel, then it is still a join clause for the joinrel; - * we put it into an appropriate JoinInfo list for the joinrel. Otherwise, - * the clause is now a restrict clause for the joined relation, and we - * return it to the caller of build_joinrel_restrictlist() to be stored in - * join paths made from this pair of sub-relations. (It will not need to - * be considered further up the join tree.) - * - * When building a restriction list, we eliminate redundant clauses. - * We don't try to do that for join clause lists, since the join clauses - * aren't really doing anything, just waiting to become part of higher - * levels' restriction lists. - * - * 'joinrel' is a join relation node - * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined - * to form joinrel. - * - * build_joinrel_restrictlist() returns a list of relevant restrictinfos, - * whereas build_joinrel_joinlist() stores its results in the joinrel's - * joininfo lists. One or the other must accept each given clause! - * - * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass - * up to the join relation. I believe this is no longer necessary, because - * RestrictInfo nodes are no longer context-dependent. Instead, just include - * the original nodes in the lists made for the join relation. - */ -static List * -build_joinrel_restrictlist(Query *root, - RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel) -{ - List *result = NIL; - List *rlist; - List *item; - - /* - * Collect all the clauses that syntactically belong at this level. - */ - rlist = nconc(subbuild_joinrel_restrictlist(joinrel, - outer_rel->joininfo), - subbuild_joinrel_restrictlist(joinrel, - inner_rel->joininfo)); - - /* - * Eliminate duplicate and redundant clauses. - * - * We must eliminate duplicates, since we will see many of the same - * clauses arriving from both input relations. Also, if a clause is a - * mergejoinable clause, it's possible that it is redundant with - * previous clauses (see optimizer/README for discussion). We detect - * that case and omit the redundant clause from the result list. - * - * We can detect redundant mergejoinable clauses very cheaply by using - * their left and right pathkeys, which uniquely identify the sets of - * equijoined variables in question. All the members of a pathkey set - * that are in the left relation have already been forced to be equal; - * likewise for those in the right relation. So, we need to have only - * one clause that checks equality between any set member on the left - * and any member on the right; by transitivity, all the rest are then - * equal. - */ - foreach(item, rlist) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(item); - - /* eliminate duplicates */ - if (member(rinfo, result)) - continue; - - /* check for redundant merge clauses */ - if (rinfo->mergejoinoperator != InvalidOid) - { - bool redundant = false; - List *olditem; - - cache_mergeclause_pathkeys(root, rinfo); - - foreach(olditem, result) - { - RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem); - - if (oldrinfo->mergejoinoperator != InvalidOid && - rinfo->left_pathkey == oldrinfo->left_pathkey && - rinfo->right_pathkey == oldrinfo->right_pathkey) - { - redundant = true; - break; - } - } - - if (redundant) - continue; - } - - /* otherwise, add it to result list */ - result = lappend(result, rinfo); - } - - freeList(rlist); - - return result; -} - -static void -build_joinrel_joinlist(RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel) -{ - subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo); - subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo); -} - -static List * -subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list) -{ - List *restrictlist = NIL; - List *xjoininfo; - - foreach(xjoininfo, joininfo_list) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - - if (is_subseti(joininfo->unjoined_relids, joinrel->relids)) - { - /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. - * - * We must copy the list to avoid disturbing the input relation, - * but we can use a shallow copy. - */ - restrictlist = nconc(restrictlist, - listCopy(joininfo->jinfo_restrictinfo)); - } - else - { - /* - * These clauses are still join clauses at this level, so we - * ignore them in this routine. - */ - } - } - - return restrictlist; -} - -static void -subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list) -{ - List *xjoininfo; - - foreach(xjoininfo, joininfo_list) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - Relids new_unjoined_relids; - - new_unjoined_relids = set_differencei(joininfo->unjoined_relids, - joinrel->relids); - if (new_unjoined_relids == NIL) - { - /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. So we - * can ignore them in this routine. - */ - } - else - { - /* - * These clauses are still join clauses at this level, so find - * or make the appropriate JoinInfo item for the joinrel, and - * add the clauses to it (eliminating duplicates). - */ - JoinInfo *new_joininfo; - - new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids); - new_joininfo->jinfo_restrictinfo = - set_union(new_joininfo->jinfo_restrictinfo, - joininfo->jinfo_restrictinfo); - } - } -} diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c deleted file mode 100644 index c9f1e75e232..00000000000 --- a/src/backend/optimizer/util/restrictinfo.c +++ /dev/null @@ -1,82 +0,0 @@ -/*------------------------------------------------------------------------- - * - * restrictinfo.c - * RestrictInfo node manipulation routines. - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.14 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - - -#include "optimizer/clauses.h" -#include "optimizer/restrictinfo.h" - -/* - * restriction_is_or_clause - * - * Returns t iff the restrictinfo node contains an 'or' clause. - * - */ -bool -restriction_is_or_clause(RestrictInfo *restrictinfo) -{ - if (restrictinfo != NULL && - or_clause((Node *) restrictinfo->clause)) - return true; - else - return false; -} - -/* - * get_actual_clauses - * - * Returns a list containing the clauses from 'restrictinfo_list'. - * - */ -List * -get_actual_clauses(List *restrictinfo_list) -{ - List *result = NIL; - List *temp; - - foreach(temp, restrictinfo_list) - { - RestrictInfo *clause = (RestrictInfo *) lfirst(temp); - - result = lappend(result, clause->clause); - } - return result; -} - -/* - * get_actual_join_clauses - * - * Extract clauses from 'restrictinfo_list', separating those that - * syntactically match the join level from those that were pushed down. - */ -void -get_actual_join_clauses(List *restrictinfo_list, - List **joinquals, List **otherquals) -{ - List *temp; - - *joinquals = NIL; - *otherquals = NIL; - - foreach(temp, restrictinfo_list) - { - RestrictInfo *clause = (RestrictInfo *) lfirst(temp); - - if (clause->ispusheddown) - *otherquals = lappend(*otherquals, clause->clause); - else - *joinquals = lappend(*joinquals, clause->clause); - } -} diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c deleted file mode 100644 index fa8c89862f4..00000000000 --- a/src/backend/optimizer/util/tlist.c +++ /dev/null @@ -1,257 +0,0 @@ -/*------------------------------------------------------------------------- - * - * tlist.c - * Target list manipulation routines - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/tlist.c,v 1.52 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include "nodes/makefuncs.h" -#include "optimizer/tlist.h" -#include "optimizer/var.h" - - -/***************************************************************************** - * ---------- RELATION node target list routines ---------- - *****************************************************************************/ - -/* - * tlistentry_member - * Finds the (first) member of the given tlist whose expression is - * equal() to the given expression. Result is NULL if no such member. - */ -TargetEntry * -tlistentry_member(Node *node, List *targetlist) -{ - List *temp; - - foreach(temp, targetlist) - { - TargetEntry *tlentry = (TargetEntry *) lfirst(temp); - - if (equal(node, tlentry->expr)) - return tlentry; - } - return NULL; -} - -#ifdef NOT_USED -/* - * matching_tlist_expr - * Same as tlistentry_member(), except returns the tlist expression - * rather than its parent TargetEntry node. - */ -Node * -matching_tlist_expr(Node *node, List *targetlist) -{ - TargetEntry *tlentry; - - tlentry = tlistentry_member(node, targetlist); - if (tlentry) - return tlentry->expr; - - return (Node *) NULL; -} -#endif - -/* - * tlist_member - * Same as tlistentry_member(), except returns the Resdom node - * rather than its parent TargetEntry node. - */ -Resdom * -tlist_member(Node *node, List *targetlist) -{ - TargetEntry *tlentry; - - tlentry = tlistentry_member(node, targetlist); - if (tlentry) - return tlentry->resdom; - - return (Resdom *) NULL; -} - -/* - * add_var_to_tlist - * Creates a targetlist entry corresponding to the supplied var node - * 'var' and adds the new targetlist entry to the targetlist field of - * 'rel'. No entry is created if 'var' is already in the tlist. - */ -void -add_var_to_tlist(RelOptInfo *rel, Var *var) -{ - if (!tlistentry_member((Node *) var, rel->targetlist)) - { - /* XXX is copyObject necessary here? */ - rel->targetlist = lappend(rel->targetlist, - create_tl_element((Var *) copyObject(var), - length(rel->targetlist) + 1)); - } -} - -/* - * create_tl_element - * Creates a target list entry node and its associated (resdom var) pair - * with its resdom number equal to 'resdomno'. - */ -TargetEntry * -create_tl_element(Var *var, int resdomno) -{ - return makeTargetEntry(makeResdom(resdomno, - var->vartype, - var->vartypmod, - NULL, - false), - (Node *) var); -} - -/***************************************************************************** - * ---------- GENERAL target list routines ---------- - *****************************************************************************/ - -/* - * new_unsorted_tlist - * Creates a copy of a target list by creating new resdom nodes - * without sort information. - * - * 'targetlist' is the target list to be copied. - * - * Returns the resulting target list. - * - */ -List * -new_unsorted_tlist(List *targetlist) -{ - List *new_targetlist = (List *) copyObject((Node *) targetlist); - List *x; - - foreach(x, new_targetlist) - { - TargetEntry *tle = (TargetEntry *) lfirst(x); - - tle->resdom->reskey = 0; - tle->resdom->reskeyop = (Oid) 0; - } - return new_targetlist; -} - -/* - * flatten_tlist - * Create a target list that only contains unique variables. - * - * Note that Vars with varlevelsup > 0 are not included in the output - * tlist. We expect that those will eventually be replaced with Params, - * but that probably has not happened at the time this routine is called. - * - * 'tlist' is the current target list - * - * Returns the "flattened" new target list. - * - * The result is entirely new structure sharing no nodes with the original. - * Copying the Var nodes is probably overkill, but be safe for now. - */ -List * -flatten_tlist(List *tlist) -{ - List *vlist = pull_var_clause((Node *) tlist, false); - List *new_tlist; - - new_tlist = add_to_flat_tlist(NIL, vlist); - freeList(vlist); - return new_tlist; -} - -/* - * add_to_flat_tlist - * Add more vars to a flattened tlist (if they're not already in it) - * - * 'tlist' is the flattened tlist - * 'vars' is a list of var nodes - * - * Returns the extended tlist. - */ -List * -add_to_flat_tlist(List *tlist, List *vars) -{ - int next_resdomno = length(tlist) + 1; - List *v; - - foreach(v, vars) - { - Var *var = lfirst(v); - - if (!tlistentry_member((Node *) var, tlist)) - { - Resdom *r; - - r = makeResdom(next_resdomno++, - var->vartype, - var->vartypmod, - NULL, - false); - tlist = lappend(tlist, - makeTargetEntry(r, copyObject(var))); - } - } - return tlist; -} - -Var * -get_expr(TargetEntry *tle) -{ - Assert(tle != NULL); - Assert(tle->expr != NULL); - - return (Var *) tle->expr; -} - -/* - * get_sortgroupclause_tle - * Find the targetlist entry matching the given SortClause - * (or GroupClause) by ressortgroupref, and return it. - * - * Because GroupClause is typedef'd as SortClause, either kind of - * node can be passed without casting. - */ -TargetEntry * -get_sortgroupclause_tle(SortClause *sortClause, - List *targetList) -{ - Index refnumber = sortClause->tleSortGroupRef; - List *l; - - foreach(l, targetList) - { - TargetEntry *tle = (TargetEntry *) lfirst(l); - - if (tle->resdom->ressortgroupref == refnumber) - return tle; - } - - elog(ERROR, "get_sortgroupclause_tle: ORDER/GROUP BY expression not found in targetlist"); - return NULL; /* keep compiler quiet */ -} - -/* - * get_sortgroupclause_expr - * Find the targetlist entry matching the given SortClause - * (or GroupClause) by ressortgroupref, and return its expression. - * - * Because GroupClause is typedef'd as SortClause, either kind of - * node can be passed without casting. - */ -Node * -get_sortgroupclause_expr(SortClause *sortClause, List *targetList) -{ - TargetEntry *tle = get_sortgroupclause_tle(sortClause, targetList); - - return tle->expr; -} diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c deleted file mode 100644 index 776636ff595..00000000000 --- a/src/backend/optimizer/util/var.c +++ /dev/null @@ -1,370 +0,0 @@ -/*------------------------------------------------------------------------- - * - * var.c - * Var node manipulation routines - * - * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.38 2002/06/20 20:29:31 momjian Exp $ - * - *------------------------------------------------------------------------- - */ -#include "postgres.h" - -#include "nodes/plannodes.h" -#include "optimizer/clauses.h" -#include "optimizer/var.h" -#include "parser/parsetree.h" - - -typedef struct -{ - List *varlist; - int sublevels_up; -} pull_varnos_context; - -typedef struct -{ - int varno; - int varattno; - int sublevels_up; -} contain_var_reference_context; - -typedef struct -{ - List *varlist; - bool includeUpperVars; -} pull_var_clause_context; - -typedef struct -{ - List *rtable; - bool force; -} flatten_join_alias_vars_context; - -static bool pull_varnos_walker(Node *node, - pull_varnos_context *context); -static bool contain_var_reference_walker(Node *node, - contain_var_reference_context *context); -static bool contain_var_clause_walker(Node *node, void *context); -static bool pull_var_clause_walker(Node *node, - pull_var_clause_context *context); -static Node *flatten_join_alias_vars_mutator(Node *node, - flatten_join_alias_vars_context *context); - - -/* - * pull_varnos - * - * Create a list of all the distinct varnos present in a parsetree. - * Only varnos that reference level-zero rtable entries are considered. - * - * NOTE: this is used on not-yet-planned expressions. It may therefore find - * bare SubLinks, and if so it needs to recurse into them to look for uplevel - * references to the desired rtable level! But when we find a completed - * SubPlan, we only need to look at the parameters passed to the subplan. - */ -List * -pull_varnos(Node *node) -{ - pull_varnos_context context; - - context.varlist = NIL; - context.sublevels_up = 0; - - /* - * Must be prepared to start with a Query or a bare expression tree; - * if it's a Query, go straight to query_tree_walker to make sure that - * sublevels_up doesn't get incremented prematurely. - */ - if (node && IsA(node, Query)) - query_tree_walker((Query *) node, pull_varnos_walker, - (void *) &context, true); - else - pull_varnos_walker(node, &context); - - return context.varlist; -} - -static bool -pull_varnos_walker(Node *node, pull_varnos_context *context) -{ - if (node == NULL) - return false; - if (IsA(node, Var)) - { - Var *var = (Var *) node; - - if (var->varlevelsup == context->sublevels_up && - !intMember(var->varno, context->varlist)) - context->varlist = lconsi(var->varno, context->varlist); - return false; - } - if (is_subplan(node)) - { - /* - * Already-planned subquery. Examine the args list (parameters to - * be passed to subquery), as well as the "oper" list which is - * executed by the outer query. But short-circuit recursion into - * the subquery itself, which would be a waste of effort. - */ - Expr *expr = (Expr *) node; - - if (pull_varnos_walker((Node *) ((SubPlan *) expr->oper)->sublink->oper, - context)) - return true; - if (pull_varnos_walker((Node *) expr->args, - context)) - return true; - return false; - } - if (IsA(node, Query)) - { - /* Recurse into RTE subquery or not-yet-planned sublink subquery */ - bool result; - - context->sublevels_up++; - result = query_tree_walker((Query *) node, pull_varnos_walker, - (void *) context, true); - context->sublevels_up--; - return result; - } - return expression_tree_walker(node, pull_varnos_walker, - (void *) context); -} - - -/* - * contain_var_reference - * - * Detect whether a parsetree contains any references to a specified - * attribute of a specified rtable entry. - * - * NOTE: this is used on not-yet-planned expressions. It may therefore find - * bare SubLinks, and if so it needs to recurse into them to look for uplevel - * references to the desired rtable entry! But when we find a completed - * SubPlan, we only need to look at the parameters passed to the subplan. - */ -bool -contain_var_reference(Node *node, int varno, int varattno, int levelsup) -{ - contain_var_reference_context context; - - context.varno = varno; - context.varattno = varattno; - context.sublevels_up = levelsup; - - /* - * Must be prepared to start with a Query or a bare expression tree; - * if it's a Query, go straight to query_tree_walker to make sure that - * sublevels_up doesn't get incremented prematurely. - */ - if (node && IsA(node, Query)) - return query_tree_walker((Query *) node, - contain_var_reference_walker, - (void *) &context, true); - else - return contain_var_reference_walker(node, &context); -} - -static bool -contain_var_reference_walker(Node *node, - contain_var_reference_context *context) -{ - if (node == NULL) - return false; - if (IsA(node, Var)) - { - Var *var = (Var *) node; - - if (var->varno == context->varno && - var->varattno == context->varattno && - var->varlevelsup == context->sublevels_up) - return true; - return false; - } - if (is_subplan(node)) - { - /* - * Already-planned subquery. Examine the args list (parameters to - * be passed to subquery), as well as the "oper" list which is - * executed by the outer query. But short-circuit recursion into - * the subquery itself, which would be a waste of effort. - */ - Expr *expr = (Expr *) node; - - if (contain_var_reference_walker((Node *) ((SubPlan *) expr->oper)->sublink->oper, - context)) - return true; - if (contain_var_reference_walker((Node *) expr->args, - context)) - return true; - return false; - } - if (IsA(node, Query)) - { - /* Recurse into RTE subquery or not-yet-planned sublink subquery */ - bool result; - - context->sublevels_up++; - result = query_tree_walker((Query *) node, - contain_var_reference_walker, - (void *) context, true); - context->sublevels_up--; - return result; - } - return expression_tree_walker(node, contain_var_reference_walker, - (void *) context); -} - - -/* - * contain_whole_tuple_var - * - * Detect whether a parsetree contains any references to the whole - * tuple of a given rtable entry (ie, a Var with varattno = 0). - */ -bool -contain_whole_tuple_var(Node *node, int varno, int levelsup) -{ - return contain_var_reference(node, varno, InvalidAttrNumber, levelsup); -} - - -/* - * contain_var_clause - * Recursively scan a clause to discover whether it contains any Var nodes - * (of the current query level). - * - * Returns true if any varnode found. - * - * Does not examine subqueries, therefore must only be used after reduction - * of sublinks to subplans! - */ -bool -contain_var_clause(Node *node) -{ - return contain_var_clause_walker(node, NULL); -} - -static bool -contain_var_clause_walker(Node *node, void *context) -{ - if (node == NULL) - return false; - if (IsA(node, Var)) - { - if (((Var *) node)->varlevelsup == 0) - return true; /* abort the tree traversal and return - * true */ - return false; - } - return expression_tree_walker(node, contain_var_clause_walker, context); -} - - -/* - * pull_var_clause - * Recursively pulls all var nodes from an expression clause. - * - * Upper-level vars (with varlevelsup > 0) are included only - * if includeUpperVars is true. Most callers probably want - * to ignore upper-level vars. - * - * Returns list of varnodes found. Note the varnodes themselves are not - * copied, only referenced. - * - * Does not examine subqueries, therefore must only be used after reduction - * of sublinks to subplans! - */ -List * -pull_var_clause(Node *node, bool includeUpperVars) -{ - pull_var_clause_context context; - - context.varlist = NIL; - context.includeUpperVars = includeUpperVars; - - pull_var_clause_walker(node, &context); - return context.varlist; -} - -static bool -pull_var_clause_walker(Node *node, pull_var_clause_context *context) -{ - if (node == NULL) - return false; - if (IsA(node, Var)) - { - if (((Var *) node)->varlevelsup == 0 || context->includeUpperVars) - context->varlist = lappend(context->varlist, node); - return false; - } - return expression_tree_walker(node, pull_var_clause_walker, - (void *) context); -} - - -/* - * flatten_join_alias_vars - * Replace Vars that reference JOIN outputs with references to the original - * relation variables instead. This allows quals involving such vars to be - * pushed down. - * - * If force is TRUE then we will reduce all JOIN alias Vars to non-alias Vars - * or expressions thereof (there may be COALESCE and/or type conversions - * involved). If force is FALSE we will not expand a Var to a non-Var - * expression. This is a hack to avoid confusing mergejoin planning, which - * currently cannot cope with non-Var join items --- we leave the join vars - * as Vars till after planning is done, then expand them during setrefs.c. - * - * Upper-level vars (with varlevelsup > 0) are ignored; normally there - * should not be any by the time this routine is called. - * - * Does not examine subqueries, therefore must only be used after reduction - * of sublinks to subplans! - */ -Node * -flatten_join_alias_vars(Node *node, List *rtable, bool force) -{ - flatten_join_alias_vars_context context; - - context.rtable = rtable; - context.force = force; - - return flatten_join_alias_vars_mutator(node, &context); -} - -static Node * -flatten_join_alias_vars_mutator(Node *node, - flatten_join_alias_vars_context *context) -{ - if (node == NULL) - return NULL; - if (IsA(node, Var)) - { - Var *var = (Var *) node; - RangeTblEntry *rte; - Node *newvar; - - if (var->varlevelsup != 0) - return node; /* no need to copy, really */ - rte = rt_fetch(var->varno, context->rtable); - if (rte->rtekind != RTE_JOIN) - return node; - Assert(var->varattno > 0); - newvar = (Node *) nth(var->varattno - 1, rte->joinaliasvars); - if (IsA(newvar, Var) || context->force) - { - /* expand it; recurse in case join input is itself a join */ - return flatten_join_alias_vars_mutator(newvar, context); - } - /* we don't want to force expansion of this alias Var */ - return node; - } - return expression_tree_mutator(node, flatten_join_alias_vars_mutator, - (void *) context); -} |