Header And Logo

PostgreSQL
| The world's most advanced open source database.

tlist.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * tlist.c
00004  *    Target list manipulation routines
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/optimizer/util/tlist.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 #include "postgres.h"
00016 
00017 #include "nodes/makefuncs.h"
00018 #include "nodes/nodeFuncs.h"
00019 #include "optimizer/tlist.h"
00020 
00021 
00022 /*****************************************************************************
00023  *      Target list creation and searching utilities
00024  *****************************************************************************/
00025 
00026 /*
00027  * tlist_member
00028  *    Finds the (first) member of the given tlist whose expression is
00029  *    equal() to the given expression.  Result is NULL if no such member.
00030  */
00031 TargetEntry *
00032 tlist_member(Node *node, List *targetlist)
00033 {
00034     ListCell   *temp;
00035 
00036     foreach(temp, targetlist)
00037     {
00038         TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
00039 
00040         if (equal(node, tlentry->expr))
00041             return tlentry;
00042     }
00043     return NULL;
00044 }
00045 
00046 /*
00047  * tlist_member_ignore_relabel
00048  *    Same as above, except that we ignore top-level RelabelType nodes
00049  *    while checking for a match.  This is needed for some scenarios
00050  *    involving binary-compatible sort operations.
00051  */
00052 TargetEntry *
00053 tlist_member_ignore_relabel(Node *node, List *targetlist)
00054 {
00055     ListCell   *temp;
00056 
00057     while (node && IsA(node, RelabelType))
00058         node = (Node *) ((RelabelType *) node)->arg;
00059 
00060     foreach(temp, targetlist)
00061     {
00062         TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
00063         Expr       *tlexpr = tlentry->expr;
00064 
00065         while (tlexpr && IsA(tlexpr, RelabelType))
00066             tlexpr = ((RelabelType *) tlexpr)->arg;
00067 
00068         if (equal(node, tlexpr))
00069             return tlentry;
00070     }
00071     return NULL;
00072 }
00073 
00074 /*
00075  * flatten_tlist
00076  *    Create a target list that only contains unique variables.
00077  *
00078  * Aggrefs and PlaceHolderVars in the input are treated according to
00079  * aggbehavior and phbehavior, for which see pull_var_clause().
00080  *
00081  * 'tlist' is the current target list
00082  *
00083  * Returns the "flattened" new target list.
00084  *
00085  * The result is entirely new structure sharing no nodes with the original.
00086  * Copying the Var nodes is probably overkill, but be safe for now.
00087  */
00088 List *
00089 flatten_tlist(List *tlist, PVCAggregateBehavior aggbehavior,
00090               PVCPlaceHolderBehavior phbehavior)
00091 {
00092     List       *vlist = pull_var_clause((Node *) tlist,
00093                                         aggbehavior,
00094                                         phbehavior);
00095     List       *new_tlist;
00096 
00097     new_tlist = add_to_flat_tlist(NIL, vlist);
00098     list_free(vlist);
00099     return new_tlist;
00100 }
00101 
00102 /*
00103  * add_to_flat_tlist
00104  *      Add more items to a flattened tlist (if they're not already in it)
00105  *
00106  * 'tlist' is the flattened tlist
00107  * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
00108  *
00109  * Returns the extended tlist.
00110  */
00111 List *
00112 add_to_flat_tlist(List *tlist, List *exprs)
00113 {
00114     int         next_resno = list_length(tlist) + 1;
00115     ListCell   *lc;
00116 
00117     foreach(lc, exprs)
00118     {
00119         Node       *expr = (Node *) lfirst(lc);
00120 
00121         if (!tlist_member(expr, tlist))
00122         {
00123             TargetEntry *tle;
00124 
00125             tle = makeTargetEntry(copyObject(expr),     /* copy needed?? */
00126                                   next_resno++,
00127                                   NULL,
00128                                   false);
00129             tlist = lappend(tlist, tle);
00130         }
00131     }
00132     return tlist;
00133 }
00134 
00135 
00136 /*
00137  * get_tlist_exprs
00138  *      Get just the expression subtrees of a tlist
00139  *
00140  * Resjunk columns are ignored unless includeJunk is true
00141  */
00142 List *
00143 get_tlist_exprs(List *tlist, bool includeJunk)
00144 {
00145     List       *result = NIL;
00146     ListCell   *l;
00147 
00148     foreach(l, tlist)
00149     {
00150         TargetEntry *tle = (TargetEntry *) lfirst(l);
00151 
00152         if (tle->resjunk && !includeJunk)
00153             continue;
00154 
00155         result = lappend(result, tle->expr);
00156     }
00157     return result;
00158 }
00159 
00160 
00161 /*
00162  * tlist_same_exprs
00163  *      Check whether two target lists contain the same expressions
00164  *
00165  * Note: this function is used to decide whether it's safe to jam a new tlist
00166  * into a non-projection-capable plan node.  Obviously we can't do that unless
00167  * the node's tlist shows it already returns the column values we want.
00168  * However, we can ignore the TargetEntry attributes resname, ressortgroupref,
00169  * resorigtbl, resorigcol, and resjunk, because those are only labelings that
00170  * don't affect the row values computed by the node.  (Moreover, if we didn't
00171  * ignore them, we'd frequently fail to make the desired optimization, since
00172  * the planner tends to not bother to make resname etc. valid in intermediate
00173  * plan nodes.)  Note that on success, the caller must still jam the desired
00174  * tlist into the plan node, else it won't have the desired labeling fields.
00175  */
00176 bool
00177 tlist_same_exprs(List *tlist1, List *tlist2)
00178 {
00179     ListCell   *lc1,
00180                *lc2;
00181 
00182     if (list_length(tlist1) != list_length(tlist2))
00183         return false;           /* not same length, so can't match */
00184 
00185     forboth(lc1, tlist1, lc2, tlist2)
00186     {
00187         TargetEntry *tle1 = (TargetEntry *) lfirst(lc1);
00188         TargetEntry *tle2 = (TargetEntry *) lfirst(lc2);
00189 
00190         if (!equal(tle1->expr, tle2->expr))
00191             return false;
00192     }
00193 
00194     return true;
00195 }
00196 
00197 
00198 /*
00199  * Does tlist have same output datatypes as listed in colTypes?
00200  *
00201  * Resjunk columns are ignored if junkOK is true; otherwise presence of
00202  * a resjunk column will always cause a 'false' result.
00203  *
00204  * Note: currently no callers care about comparing typmods.
00205  */
00206 bool
00207 tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
00208 {
00209     ListCell   *l;
00210     ListCell   *curColType = list_head(colTypes);
00211 
00212     foreach(l, tlist)
00213     {
00214         TargetEntry *tle = (TargetEntry *) lfirst(l);
00215 
00216         if (tle->resjunk)
00217         {
00218             if (!junkOK)
00219                 return false;
00220         }
00221         else
00222         {
00223             if (curColType == NULL)
00224                 return false;   /* tlist longer than colTypes */
00225             if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
00226                 return false;
00227             curColType = lnext(curColType);
00228         }
00229     }
00230     if (curColType != NULL)
00231         return false;           /* tlist shorter than colTypes */
00232     return true;
00233 }
00234 
00235 /*
00236  * Does tlist have same exposed collations as listed in colCollations?
00237  *
00238  * Identical logic to the above, but for collations.
00239  */
00240 bool
00241 tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
00242 {
00243     ListCell   *l;
00244     ListCell   *curColColl = list_head(colCollations);
00245 
00246     foreach(l, tlist)
00247     {
00248         TargetEntry *tle = (TargetEntry *) lfirst(l);
00249 
00250         if (tle->resjunk)
00251         {
00252             if (!junkOK)
00253                 return false;
00254         }
00255         else
00256         {
00257             if (curColColl == NULL)
00258                 return false;   /* tlist longer than colCollations */
00259             if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
00260                 return false;
00261             curColColl = lnext(curColColl);
00262         }
00263     }
00264     if (curColColl != NULL)
00265         return false;           /* tlist shorter than colCollations */
00266     return true;
00267 }
00268 
00269 
00270 /*
00271  * get_sortgroupref_tle
00272  *      Find the targetlist entry matching the given SortGroupRef index,
00273  *      and return it.
00274  */
00275 TargetEntry *
00276 get_sortgroupref_tle(Index sortref, List *targetList)
00277 {
00278     ListCell   *l;
00279 
00280     foreach(l, targetList)
00281     {
00282         TargetEntry *tle = (TargetEntry *) lfirst(l);
00283 
00284         if (tle->ressortgroupref == sortref)
00285             return tle;
00286     }
00287 
00288     elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
00289     return NULL;                /* keep compiler quiet */
00290 }
00291 
00292 /*
00293  * get_sortgroupclause_tle
00294  *      Find the targetlist entry matching the given SortGroupClause
00295  *      by ressortgroupref, and return it.
00296  */
00297 TargetEntry *
00298 get_sortgroupclause_tle(SortGroupClause *sgClause,
00299                         List *targetList)
00300 {
00301     return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
00302 }
00303 
00304 /*
00305  * get_sortgroupclause_expr
00306  *      Find the targetlist entry matching the given SortGroupClause
00307  *      by ressortgroupref, and return its expression.
00308  */
00309 Node *
00310 get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
00311 {
00312     TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
00313 
00314     return (Node *) tle->expr;
00315 }
00316 
00317 /*
00318  * get_sortgrouplist_exprs
00319  *      Given a list of SortGroupClauses, build a list
00320  *      of the referenced targetlist expressions.
00321  */
00322 List *
00323 get_sortgrouplist_exprs(List *sgClauses, List *targetList)
00324 {
00325     List       *result = NIL;
00326     ListCell   *l;
00327 
00328     foreach(l, sgClauses)
00329     {
00330         SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
00331         Node       *sortexpr;
00332 
00333         sortexpr = get_sortgroupclause_expr(sortcl, targetList);
00334         result = lappend(result, sortexpr);
00335     }
00336     return result;
00337 }
00338 
00339 
00340 /*****************************************************************************
00341  *      Functions to extract data from a list of SortGroupClauses
00342  *
00343  * These don't really belong in tlist.c, but they are sort of related to the
00344  * functions just above, and they don't seem to deserve their own file.
00345  *****************************************************************************/
00346 
00347 /*
00348  * extract_grouping_ops - make an array of the equality operator OIDs
00349  *      for a SortGroupClause list
00350  */
00351 Oid *
00352 extract_grouping_ops(List *groupClause)
00353 {
00354     int         numCols = list_length(groupClause);
00355     int         colno = 0;
00356     Oid        *groupOperators;
00357     ListCell   *glitem;
00358 
00359     groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
00360 
00361     foreach(glitem, groupClause)
00362     {
00363         SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
00364 
00365         groupOperators[colno] = groupcl->eqop;
00366         Assert(OidIsValid(groupOperators[colno]));
00367         colno++;
00368     }
00369 
00370     return groupOperators;
00371 }
00372 
00373 /*
00374  * extract_grouping_cols - make an array of the grouping column resnos
00375  *      for a SortGroupClause list
00376  */
00377 AttrNumber *
00378 extract_grouping_cols(List *groupClause, List *tlist)
00379 {
00380     AttrNumber *grpColIdx;
00381     int         numCols = list_length(groupClause);
00382     int         colno = 0;
00383     ListCell   *glitem;
00384 
00385     grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
00386 
00387     foreach(glitem, groupClause)
00388     {
00389         SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
00390         TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
00391 
00392         grpColIdx[colno++] = tle->resno;
00393     }
00394 
00395     return grpColIdx;
00396 }
00397 
00398 /*
00399  * grouping_is_sortable - is it possible to implement grouping list by sorting?
00400  *
00401  * This is easy since the parser will have included a sortop if one exists.
00402  */
00403 bool
00404 grouping_is_sortable(List *groupClause)
00405 {
00406     ListCell   *glitem;
00407 
00408     foreach(glitem, groupClause)
00409     {
00410         SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
00411 
00412         if (!OidIsValid(groupcl->sortop))
00413             return false;
00414     }
00415     return true;
00416 }
00417 
00418 /*
00419  * grouping_is_hashable - is it possible to implement grouping list by hashing?
00420  *
00421  * We rely on the parser to have set the hashable flag correctly.
00422  */
00423 bool
00424 grouping_is_hashable(List *groupClause)
00425 {
00426     ListCell   *glitem;
00427 
00428     foreach(glitem, groupClause)
00429     {
00430         SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
00431 
00432         if (!groupcl->hashable)
00433             return false;
00434     }
00435     return true;
00436 }