granicus.if.org Git - postgresql/blob - src/backend/optimizer/util/tlist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * tlist.c
   4  *        Target list manipulation routines
   5  *
   6  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/util/tlist.c,v 1.80 2008/08/07 01:11:50 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "nodes/makefuncs.h"
  18 #include "optimizer/tlist.h"
  19 #include "optimizer/var.h"
  20 #include "parser/parse_expr.h"
  21 #include "utils/lsyscache.h"
  22
  23
  24 /*****************************************************************************
  25  *              Target list creation and searching utilities
  26  *****************************************************************************/
  27
  28 /*
  29  * tlist_member
  30  *        Finds the (first) member of the given tlist whose expression is
  31  *        equal() to the given expression.      Result is NULL if no such member.
  32  */
  33 TargetEntry *
  34 tlist_member(Node *node, List *targetlist)
  35 {
  36         ListCell   *temp;
  37
  38         foreach(temp, targetlist)
  39         {
  40                 TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
  41
  42                 if (equal(node, tlentry->expr))
  43                         return tlentry;
  44         }
  45         return NULL;
  46 }
  47
  48 /*
  49  * tlist_member_ignore_relabel
  50  *        Same as above, except that we ignore top-level RelabelType nodes
  51  *        while checking for a match.  This is needed for some scenarios
  52  *        involving binary-compatible sort operations.
  53  */
  54 TargetEntry *
  55 tlist_member_ignore_relabel(Node *node, List *targetlist)
  56 {
  57         ListCell   *temp;
  58
  59         while (node && IsA(node, RelabelType))
  60                 node = (Node *) ((RelabelType *) node)->arg;
  61
  62         foreach(temp, targetlist)
  63         {
  64                 TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
  65                 Expr       *tlexpr = tlentry->expr;
  66
  67                 while (tlexpr && IsA(tlexpr, RelabelType))
  68                         tlexpr = ((RelabelType *) tlexpr)->arg;
  69
  70                 if (equal(node, tlexpr))
  71                         return tlentry;
  72         }
  73         return NULL;
  74 }
  75
  76 /*
  77  * flatten_tlist
  78  *        Create a target list that only contains unique variables.
  79  *
  80  * Note that Vars with varlevelsup > 0 are not included in the output
  81  * tlist.  We expect that those will eventually be replaced with Params,
  82  * but that probably has not happened at the time this routine is called.
  83  *
  84  * 'tlist' is the current target list
  85  *
  86  * Returns the "flattened" new target list.
  87  *
  88  * The result is entirely new structure sharing no nodes with the original.
  89  * Copying the Var nodes is probably overkill, but be safe for now.
  90  */
  91 List *
  92 flatten_tlist(List *tlist)
  93 {
  94         List       *vlist = pull_var_clause((Node *) tlist, false);
  95         List       *new_tlist;
  96
  97         new_tlist = add_to_flat_tlist(NIL, vlist);
  98         list_free(vlist);
  99         return new_tlist;
 100 }
 101
 102 /*
 103  * add_to_flat_tlist
 104  *              Add more vars to a flattened tlist (if they're not already in it)
 105  *
 106  * 'tlist' is the flattened tlist
 107  * 'vars' is a list of var nodes
 108  *
 109  * Returns the extended tlist.
 110  */
 111 List *
 112 add_to_flat_tlist(List *tlist, List *vars)
 113 {
 114         int                     next_resno = list_length(tlist) + 1;
 115         ListCell   *v;
 116
 117         foreach(v, vars)
 118         {
 119                 Var                *var = (Var *) lfirst(v);
 120
 121                 if (!tlist_member((Node *) var, tlist))
 122                 {
 123                         TargetEntry *tle;
 124
 125                         tle = makeTargetEntry(copyObject(var),          /* copy needed?? */
 126                                                                   next_resno++,
 127                                                                   NULL,
 128                                                                   false);
 129                         tlist = lappend(tlist, tle);
 130                 }
 131         }
 132         return tlist;
 133 }
 134
 135
 136 /*
 137  * get_sortgroupref_tle
 138  *              Find the targetlist entry matching the given SortGroupRef index,
 139  *              and return it.
 140  */
 141 TargetEntry *
 142 get_sortgroupref_tle(Index sortref, List *targetList)
 143 {
 144         ListCell   *l;
 145
 146         foreach(l, targetList)
 147         {
 148                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 149
 150                 if (tle->ressortgroupref == sortref)
 151                         return tle;
 152         }
 153
 154         elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
 155         return NULL;                            /* keep compiler quiet */
 156 }
 157
 158 /*
 159  * get_sortgroupclause_tle
 160  *              Find the targetlist entry matching the given SortGroupClause
 161  *              by ressortgroupref, and return it.
 162  */
 163 TargetEntry *
 164 get_sortgroupclause_tle(SortGroupClause *sgClause,
 165                                                 List *targetList)
 166 {
 167         return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
 168 }
 169
 170 /*
 171  * get_sortgroupclause_expr
 172  *              Find the targetlist entry matching the given SortGroupClause
 173  *              by ressortgroupref, and return its expression.
 174  */
 175 Node *
 176 get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
 177 {
 178         TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
 179
 180         return (Node *) tle->expr;
 181 }
 182
 183 /*
 184  * get_sortgrouplist_exprs
 185  *              Given a list of SortGroupClauses, build a list
 186  *              of the referenced targetlist expressions.
 187  */
 188 List *
 189 get_sortgrouplist_exprs(List *sgClauses, List *targetList)
 190 {
 191         List       *result = NIL;
 192         ListCell   *l;
 193
 194         foreach(l, sgClauses)
 195         {
 196                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
 197                 Node       *sortexpr;
 198
 199                 sortexpr = get_sortgroupclause_expr(sortcl, targetList);
 200                 result = lappend(result, sortexpr);
 201         }
 202         return result;
 203 }
 204
 205
 206 /*****************************************************************************
 207  *              Functions to extract data from a list of SortGroupClauses
 208  *
 209  * These don't really belong in tlist.c, but they are sort of related to the
 210  * functions just above, and they don't seem to deserve their own file.
 211  *****************************************************************************/
 212
 213 /*
 214  * extract_grouping_ops - make an array of the equality operator OIDs
 215  *              for a SortGroupClause list
 216  */
 217 Oid *
 218 extract_grouping_ops(List *groupClause)
 219 {
 220         int                     numCols = list_length(groupClause);
 221         int                     colno = 0;
 222         Oid                *groupOperators;
 223         ListCell   *glitem;
 224
 225         groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
 226
 227         foreach(glitem, groupClause)
 228         {
 229                 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 230
 231                 groupOperators[colno] = groupcl->eqop;
 232                 Assert(OidIsValid(groupOperators[colno]));
 233                 colno++;
 234         }
 235
 236         return groupOperators;
 237 }
 238
 239 /*
 240  * extract_grouping_cols - make an array of the grouping column resnos
 241  *              for a SortGroupClause list
 242  */
 243 AttrNumber *
 244 extract_grouping_cols(List *groupClause, List *tlist)
 245 {
 246         AttrNumber *grpColIdx;
 247         int                     numCols = list_length(groupClause);
 248         int                     colno = 0;
 249         ListCell   *glitem;
 250
 251         grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 252
 253         foreach(glitem, groupClause)
 254         {
 255                 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 256                 TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
 257
 258                 grpColIdx[colno++] = tle->resno;
 259         }
 260
 261         return grpColIdx;
 262 }
 263
 264 /*
 265  * grouping_is_sortable - is it possible to implement grouping list by sorting?
 266  *
 267  * This is easy since the parser will have included a sortop if one exists.
 268  */
 269 bool
 270 grouping_is_sortable(List *groupClause)
 271 {
 272         ListCell   *glitem;
 273
 274         foreach(glitem, groupClause)
 275         {
 276                 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 277
 278                 if (!OidIsValid(groupcl->sortop))
 279                         return false;
 280         }
 281         return true;
 282 }
 283
 284 /*
 285  * grouping_is_hashable - is it possible to implement grouping list by hashing?
 286  *
 287  * We assume hashing is OK if the equality operators are marked oprcanhash.
 288  * (If there isn't actually a supporting hash function, the executor will
 289  * complain at runtime; but this is a misdeclaration of the operator, not
 290  * a system bug.)
 291  */
 292 bool
 293 grouping_is_hashable(List *groupClause)
 294 {
 295         ListCell   *glitem;
 296
 297         foreach(glitem, groupClause)
 298         {
 299                 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 300
 301                 if (!op_hashjoinable(groupcl->eqop))
 302                         return false;
 303         }
 304         return true;
 305 }
 306
 307
 308
 309 /*
 310  * Does tlist have same output datatypes as listed in colTypes?
 311  *
 312  * Resjunk columns are ignored if junkOK is true; otherwise presence of
 313  * a resjunk column will always cause a 'false' result.
 314  *
 315  * Note: currently no callers care about comparing typmods.
 316  */
 317 bool
 318 tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
 319 {
 320         ListCell   *l;
 321         ListCell   *curColType = list_head(colTypes);
 322
 323         foreach(l, tlist)
 324         {
 325                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 326
 327                 if (tle->resjunk)
 328                 {
 329                         if (!junkOK)
 330                                 return false;
 331                 }
 332                 else
 333                 {
 334                         if (curColType == NULL)
 335                                 return false;   /* tlist longer than colTypes */
 336                         if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
 337                                 return false;
 338                         curColType = lnext(curColType);
 339                 }
 340         }
 341         if (curColType != NULL)
 342                 return false;                   /* tlist shorter than colTypes */
 343         return true;
 344 }