granicus.if.org Git - postgresql/blob - src/backend/parser/parse_clause.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * parse_clause.c
   4  *        handle clauses in parser
   5  *
   6  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/parser/parse_clause.c,v 1.107 2003/02/13 05:06:34 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/heapam.h"
  19 #include "catalog/heap.h"
  20 #include "nodes/makefuncs.h"
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/tlist.h"
  23 #include "optimizer/var.h"
  24 #include "parser/analyze.h"
  25 #include "parser/parsetree.h"
  26 #include "parser/parse_clause.h"
  27 #include "parser/parse_coerce.h"
  28 #include "parser/parse_expr.h"
  29 #include "parser/parse_oper.h"
  30 #include "parser/parse_relation.h"
  31 #include "parser/parse_target.h"
  32 #include "parser/parse_type.h"
  33 #include "utils/builtins.h"
  34 #include "utils/guc.h"
  35
  36
  37 #define ORDER_CLAUSE 0
  38 #define GROUP_CLAUSE 1
  39 #define DISTINCT_ON_CLAUSE 2
  40
  41 static char *clauseText[] = {"ORDER BY", "GROUP BY", "DISTINCT ON"};
  42
  43 static void extractRemainingColumns(List *common_colnames,
  44                                                 List *src_colnames, List *src_colvars,
  45                                                 List **res_colnames, List **res_colvars);
  46 static Node *transformJoinUsingClause(ParseState *pstate,
  47                                                  List *leftVars, List *rightVars);
  48 static Node *transformJoinOnClause(ParseState *pstate, JoinExpr *j,
  49                                           List *containedRels);
  50 static RangeTblRef *transformTableEntry(ParseState *pstate, RangeVar *r);
  51 static RangeTblRef *transformRangeSubselect(ParseState *pstate,
  52                                                 RangeSubselect *r);
  53 static RangeTblRef *transformRangeFunction(ParseState *pstate,
  54                                            RangeFunction *r);
  55 static Node *transformFromClauseItem(ParseState *pstate, Node *n,
  56                                                 List **containedRels);
  57 static Node *buildMergedJoinVar(JoinType jointype,
  58                                    Var *l_colvar, Var *r_colvar);
  59 static TargetEntry *findTargetlistEntry(ParseState *pstate, Node *node,
  60                                         List *tlist, int clause);
  61 static List *addTargetToSortList(TargetEntry *tle, List *sortlist,
  62                                         List *targetlist, List *opname);
  63 static bool targetIsInSortList(TargetEntry *tle, List *sortList);
  64
  65
  66 /*
  67  * transformFromClause -
  68  *        Process the FROM clause and add items to the query's range table,
  69  *        joinlist, and namespace.
  70  *
  71  * Note: we assume that pstate's p_rtable, p_joinlist, and p_namespace lists
  72  * were initialized to NIL when the pstate was created.  We will add onto
  73  * any entries already present --- this is needed for rule processing, as
  74  * well as for UPDATE and DELETE.
  75  *
  76  * The range table may grow still further when we transform the expressions
  77  * in the query's quals and target list. (This is possible because in
  78  * POSTQUEL, we allowed references to relations not specified in the
  79  * from-clause.  PostgreSQL keeps this extension to standard SQL.)
  80  */
  81 void
  82 transformFromClause(ParseState *pstate, List *frmList)
  83 {
  84         List       *fl;
  85
  86         /*
  87          * The grammar will have produced a list of RangeVars,
  88          * RangeSubselects, RangeFunctions, and/or JoinExprs. Transform each
  89          * one (possibly adding entries to the rtable), check for duplicate
  90          * refnames, and then add it to the joinlist and namespace.
  91          */
  92         foreach(fl, frmList)
  93         {
  94                 Node       *n = lfirst(fl);
  95                 List       *containedRels;
  96
  97                 n = transformFromClauseItem(pstate, n, &containedRels);
  98                 checkNameSpaceConflicts(pstate, (Node *) pstate->p_namespace, n);
  99                 pstate->p_joinlist = lappend(pstate->p_joinlist, n);
 100                 pstate->p_namespace = lappend(pstate->p_namespace, n);
 101         }
 102 }
 103
 104 /*
 105  * setTargetTable
 106  *        Add the target relation of INSERT/UPDATE/DELETE to the range table,
 107  *        and make the special links to it in the ParseState.
 108  *
 109  *        We also open the target relation and acquire a write lock on it.
 110  *        This must be done before processing the FROM list, in case the target
 111  *        is also mentioned as a source relation --- we want to be sure to grab
 112  *        the write lock before any read lock.
 113  *
 114  *        If alsoSource is true, add the target to the query's joinlist and
 115  *        namespace.  For INSERT, we don't want the target to be joined to;
 116  *        it's a destination of tuples, not a source.   For UPDATE/DELETE,
 117  *        we do need to scan or join the target.  (NOTE: we do not bother
 118  *        to check for namespace conflict; we assume that the namespace was
 119  *        initially empty in these cases.)
 120  *
 121  *        Returns the rangetable index of the target relation.
 122  */
 123 int
 124 setTargetTable(ParseState *pstate, RangeVar *relation,
 125                            bool inh, bool alsoSource)
 126 {
 127         RangeTblEntry *rte;
 128         int                     rtindex;
 129
 130         /* Close old target; this could only happen for multi-action rules */
 131         if (pstate->p_target_relation != NULL)
 132                 heap_close(pstate->p_target_relation, NoLock);
 133
 134         /*
 135          * Open target rel and grab suitable lock (which we will hold till end
 136          * of transaction).
 137          *
 138          * analyze.c will eventually do the corresponding heap_close(), but *not*
 139          * release the lock.
 140          */
 141         pstate->p_target_relation = heap_openrv(relation, RowExclusiveLock);
 142
 143         /*
 144          * Now build an RTE.
 145          */
 146         rte = addRangeTableEntry(pstate, relation, NULL, inh, false);
 147         pstate->p_target_rangetblentry = rte;
 148
 149         /* assume new rte is at end */
 150         rtindex = length(pstate->p_rtable);
 151         Assert(rte == rt_fetch(rtindex, pstate->p_rtable));
 152
 153         /*
 154          * Override addRangeTableEntry's default checkForRead, and instead
 155          * mark target table as requiring write access.
 156          *
 157          * If we find an explicit reference to the rel later during parse
 158          * analysis, scanRTEForColumn will change checkForRead to 'true'
 159          * again.  That can't happen for INSERT but it is possible for UPDATE
 160          * and DELETE.
 161          */
 162         rte->checkForRead = false;
 163         rte->checkForWrite = true;
 164
 165         /*
 166          * If UPDATE/DELETE, add table to joinlist and namespace.
 167          */
 168         if (alsoSource)
 169                 addRTEtoQuery(pstate, rte, true, true);
 170
 171         return rtindex;
 172 }
 173
 174 /*
 175  * Simplify InhOption (yes/no/default) into boolean yes/no.
 176  *
 177  * The reason we do things this way is that we don't want to examine the
 178  * SQL_inheritance option flag until parse_analyze is run.      Otherwise,
 179  * we'd do the wrong thing with query strings that intermix SET commands
 180  * with queries.
 181  */
 182 bool
 183 interpretInhOption(InhOption inhOpt)
 184 {
 185         switch (inhOpt)
 186         {
 187                 case INH_NO:
 188                         return false;
 189                 case INH_YES:
 190                         return true;
 191                 case INH_DEFAULT:
 192                         return SQL_inheritance;
 193         }
 194         elog(ERROR, "Bogus InhOption value");
 195         return false;                           /* keep compiler quiet */
 196 }
 197
 198 /*
 199  * Extract all not-in-common columns from column lists of a source table
 200  */
 201 static void
 202 extractRemainingColumns(List *common_colnames,
 203                                                 List *src_colnames, List *src_colvars,
 204                                                 List **res_colnames, List **res_colvars)
 205 {
 206         List       *new_colnames = NIL;
 207         List       *new_colvars = NIL;
 208         List       *lnames,
 209                            *lvars = src_colvars;
 210
 211         foreach(lnames, src_colnames)
 212         {
 213                 char       *colname = strVal(lfirst(lnames));
 214                 bool            match = false;
 215                 List       *cnames;
 216
 217                 foreach(cnames, common_colnames)
 218                 {
 219                         char       *ccolname = strVal(lfirst(cnames));
 220
 221                         if (strcmp(colname, ccolname) == 0)
 222                         {
 223                                 match = true;
 224                                 break;
 225                         }
 226                 }
 227
 228                 if (!match)
 229                 {
 230                         new_colnames = lappend(new_colnames, lfirst(lnames));
 231                         new_colvars = lappend(new_colvars, lfirst(lvars));
 232                 }
 233
 234                 lvars = lnext(lvars);
 235         }
 236
 237         *res_colnames = new_colnames;
 238         *res_colvars = new_colvars;
 239 }
 240
 241 /* transformJoinUsingClause()
 242  *        Build a complete ON clause from a partially-transformed USING list.
 243  *        We are given lists of nodes representing left and right match columns.
 244  *        Result is a transformed qualification expression.
 245  */
 246 static Node *
 247 transformJoinUsingClause(ParseState *pstate, List *leftVars, List *rightVars)
 248 {
 249         Node       *result = NULL;
 250         List       *lvars,
 251                            *rvars = rightVars;
 252
 253         /*
 254          * We cheat a little bit here by building an untransformed operator
 255          * tree whose leaves are the already-transformed Vars.  This is OK
 256          * because transformExpr() won't complain about already-transformed
 257          * subnodes.
 258          */
 259         foreach(lvars, leftVars)
 260         {
 261                 Node       *lvar = (Node *) lfirst(lvars);
 262                 Node       *rvar = (Node *) lfirst(rvars);
 263                 A_Expr     *e;
 264
 265                 e = makeSimpleA_Expr(AEXPR_OP, "=", copyObject(lvar), copyObject(rvar));
 266
 267                 if (result == NULL)
 268                         result = (Node *) e;
 269                 else
 270                 {
 271                         A_Expr     *a;
 272
 273                         a = makeA_Expr(AEXPR_AND, NIL, result, (Node *) e);
 274                         result = (Node *) a;
 275                 }
 276
 277                 rvars = lnext(rvars);
 278         }
 279
 280         /*
 281          * Since the references are already Vars, and are certainly from the
 282          * input relations, we don't have to go through the same pushups that
 283          * transformJoinOnClause() does.  Just invoke transformExpr() to fix
 284          * up the operators, and we're done.
 285          */
 286         result = transformExpr(pstate, result);
 287
 288         result = coerce_to_boolean(result, "JOIN/USING");
 289
 290         return result;
 291 }       /* transformJoinUsingClause() */
 292
 293 /* transformJoinOnClause()
 294  *        Transform the qual conditions for JOIN/ON.
 295  *        Result is a transformed qualification expression.
 296  */
 297 static Node *
 298 transformJoinOnClause(ParseState *pstate, JoinExpr *j,
 299                                           List *containedRels)
 300 {
 301         Node       *result;
 302         List       *save_namespace;
 303         Relids          clause_varnos;
 304         int                     varno;
 305
 306         /*
 307          * This is a tad tricky, for two reasons.  First, the namespace that
 308          * the join expression should see is just the two subtrees of the JOIN
 309          * plus any outer references from upper pstate levels.  So,
 310          * temporarily set this pstate's namespace accordingly.  (We need not
 311          * check for refname conflicts, because transformFromClauseItem()
 312          * already did.) NOTE: this code is OK only because the ON clause
 313          * can't legally alter the namespace by causing implicit relation refs
 314          * to be added.
 315          */
 316         save_namespace = pstate->p_namespace;
 317         pstate->p_namespace = makeList2(j->larg, j->rarg);
 318
 319         /* This part is just like transformWhereClause() */
 320         result = transformExpr(pstate, j->quals);
 321
 322         result = coerce_to_boolean(result, "JOIN/ON");
 323
 324         pstate->p_namespace = save_namespace;
 325
 326         /*
 327          * Second, we need to check that the ON condition doesn't refer to any
 328          * rels outside the input subtrees of the JOIN.  It could do that
 329          * despite our hack on the namespace if it uses fully-qualified names.
 330          * So, grovel through the transformed clause and make sure there are
 331          * no bogus references.  (Outer references are OK, and are ignored
 332          * here.)
 333          */
 334         clause_varnos = pull_varnos(result);
 335         while ((varno = bms_first_member(clause_varnos)) >= 0)
 336         {
 337                 if (!intMember(varno, containedRels))
 338                 {
 339                         elog(ERROR, "JOIN/ON clause refers to \"%s\", which is not part of JOIN",
 340                                  rt_fetch(varno, pstate->p_rtable)->eref->aliasname);
 341                 }
 342         }
 343         bms_free(clause_varnos);
 344
 345         return result;
 346 }
 347
 348 /*
 349  * transformTableEntry --- transform a RangeVar (simple relation reference)
 350  */
 351 static RangeTblRef *
 352 transformTableEntry(ParseState *pstate, RangeVar *r)
 353 {
 354         RangeTblEntry *rte;
 355         RangeTblRef *rtr;
 356
 357         /*
 358          * mark this entry to indicate it comes from the FROM clause. In SQL,
 359          * the target list can only refer to range variables specified in the
 360          * from clause but we follow the more powerful POSTQUEL semantics and
 361          * automatically generate the range variable if not specified. However
 362          * there are times we need to know whether the entries are legitimate.
 363          */
 364         rte = addRangeTableEntry(pstate, r, r->alias,
 365                                                          interpretInhOption(r->inhOpt), true);
 366
 367         /*
 368          * We create a RangeTblRef, but we do not add it to the joinlist or
 369          * namespace; our caller must do that if appropriate.
 370          */
 371         rtr = makeNode(RangeTblRef);
 372         /* assume new rte is at end */
 373         rtr->rtindex = length(pstate->p_rtable);
 374         Assert(rte == rt_fetch(rtr->rtindex, pstate->p_rtable));
 375
 376         return rtr;
 377 }
 378
 379
 380 /*
 381  * transformRangeSubselect --- transform a sub-SELECT appearing in FROM
 382  */
 383 static RangeTblRef *
 384 transformRangeSubselect(ParseState *pstate, RangeSubselect *r)
 385 {
 386         List       *save_namespace;
 387         List       *parsetrees;
 388         Query      *query;
 389         RangeTblEntry *rte;
 390         RangeTblRef *rtr;
 391
 392         /*
 393          * We require user to supply an alias for a subselect, per SQL92. To
 394          * relax this, we'd have to be prepared to gin up a unique alias for
 395          * an unlabeled subselect.
 396          */
 397         if (r->alias == NULL)
 398                 elog(ERROR, "sub-select in FROM must have an alias");
 399
 400         /*
 401          * Analyze and transform the subquery.  This is a bit tricky because
 402          * we don't want the subquery to be able to see any FROM items already
 403          * created in the current query (per SQL92, the scope of a FROM item
 404          * does not include other FROM items).  But it does need to be able to
 405          * see any further-up parent states, so we can't just pass a null
 406          * parent pstate link.  So, temporarily make the current query level
 407          * have an empty namespace.
 408          */
 409         save_namespace = pstate->p_namespace;
 410         pstate->p_namespace = NIL;
 411
 412         parsetrees = parse_analyze(r->subquery, pstate);
 413
 414         pstate->p_namespace = save_namespace;
 415
 416         /*
 417          * Check that we got something reasonable.      Some of these conditions
 418          * are probably impossible given restrictions of the grammar, but
 419          * check 'em anyway.
 420          */
 421         if (length(parsetrees) != 1)
 422                 elog(ERROR, "Unexpected parse analysis result for subselect in FROM");
 423         query = (Query *) lfirst(parsetrees);
 424         if (query == NULL || !IsA(query, Query))
 425                 elog(ERROR, "Unexpected parse analysis result for subselect in FROM");
 426
 427         if (query->commandType != CMD_SELECT)
 428                 elog(ERROR, "Expected SELECT query from subselect in FROM");
 429         if (query->resultRelation != 0 || query->into != NULL || query->isPortal)
 430                 elog(ERROR, "Subselect in FROM may not have SELECT INTO");
 431
 432         /*
 433          * OK, build an RTE for the subquery.
 434          */
 435         rte = addRangeTableEntryForSubquery(pstate, query, r->alias, true);
 436
 437         /*
 438          * We create a RangeTblRef, but we do not add it to the joinlist or
 439          * namespace; our caller must do that if appropriate.
 440          */
 441         rtr = makeNode(RangeTblRef);
 442         /* assume new rte is at end */
 443         rtr->rtindex = length(pstate->p_rtable);
 444         Assert(rte == rt_fetch(rtr->rtindex, pstate->p_rtable));
 445
 446         return rtr;
 447 }
 448
 449
 450 /*
 451  * transformRangeFunction --- transform a function call appearing in FROM
 452  */
 453 static RangeTblRef *
 454 transformRangeFunction(ParseState *pstate, RangeFunction *r)
 455 {
 456         Node       *funcexpr;
 457         char       *funcname;
 458         List       *save_namespace;
 459         RangeTblEntry *rte;
 460         RangeTblRef *rtr;
 461
 462         /* Get function name for possible use as alias */
 463         Assert(IsA(r->funccallnode, FuncCall));
 464         funcname = strVal(llast(((FuncCall *) r->funccallnode)->funcname));
 465
 466         /*
 467          * Transform the raw FuncCall node.  This is a bit tricky because we
 468          * don't want the function expression to be able to see any FROM items
 469          * already created in the current query (compare to
 470          * transformRangeSubselect). But it does need to be able to see any
 471          * further-up parent states. So, temporarily make the current query
 472          * level have an empty namespace. NOTE: this code is OK only because
 473          * the expression can't legally alter the namespace by causing
 474          * implicit relation refs to be added.
 475          */
 476         save_namespace = pstate->p_namespace;
 477         pstate->p_namespace = NIL;
 478
 479         funcexpr = transformExpr(pstate, r->funccallnode);
 480
 481         pstate->p_namespace = save_namespace;
 482
 483         /*
 484          * We still need to check that the function parameters don't refer to
 485          * any other rels.      That could happen despite our hack on the
 486          * namespace if fully-qualified names are used.  So, check there are
 487          * no local Var references in the transformed expression.  (Outer
 488          * references are OK, and are ignored here.)
 489          */
 490         if (!bms_is_empty(pull_varnos(funcexpr)))
 491                 elog(ERROR, "FROM function expression may not refer to other relations of same query level");
 492
 493         /*
 494          * Disallow aggregate functions in the expression.      (No reason to
 495          * postpone this check until parseCheckAggregates.)
 496          */
 497         if (pstate->p_hasAggs)
 498         {
 499                 if (contain_agg_clause(funcexpr))
 500                         elog(ERROR, "cannot use aggregate function in FROM function expression");
 501         }
 502
 503         /*
 504          * If a coldeflist is supplied, ensure it defines a legal set of names
 505          * (no duplicates) and datatypes (no pseudo-types, for instance).
 506          */
 507         if (r->coldeflist)
 508         {
 509                 TupleDesc       tupdesc;
 510
 511                 tupdesc = BuildDescForRelation(r->coldeflist);
 512                 CheckAttributeNamesTypes(tupdesc, RELKIND_COMPOSITE_TYPE);
 513         }
 514
 515         /*
 516          * OK, build an RTE for the function.
 517          */
 518         rte = addRangeTableEntryForFunction(pstate, funcname, funcexpr,
 519                                                                                 r, true);
 520
 521         /*
 522          * We create a RangeTblRef, but we do not add it to the joinlist or
 523          * namespace; our caller must do that if appropriate.
 524          */
 525         rtr = makeNode(RangeTblRef);
 526         /* assume new rte is at end */
 527         rtr->rtindex = length(pstate->p_rtable);
 528         Assert(rte == rt_fetch(rtr->rtindex, pstate->p_rtable));
 529
 530         return rtr;
 531 }
 532
 533
 534 /*
 535  * transformFromClauseItem -
 536  *        Transform a FROM-clause item, adding any required entries to the
 537  *        range table list being built in the ParseState, and return the
 538  *        transformed item ready to include in the joinlist and namespace.
 539  *        This routine can recurse to handle SQL92 JOIN expressions.
 540  *
 541  *        Aside from the primary return value (the transformed joinlist item)
 542  *        this routine also returns an integer list of the rangetable indexes
 543  *        of all the base and join relations represented in the joinlist item.
 544  *        This list is needed for checking JOIN/ON conditions in higher levels.
 545  */
 546 static Node *
 547 transformFromClauseItem(ParseState *pstate, Node *n, List **containedRels)
 548 {
 549         if (IsA(n, RangeVar))
 550         {
 551                 /* Plain relation reference */
 552                 RangeTblRef *rtr;
 553
 554                 rtr = transformTableEntry(pstate, (RangeVar *) n);
 555                 *containedRels = makeListi1(rtr->rtindex);
 556                 return (Node *) rtr;
 557         }
 558         else if (IsA(n, RangeSubselect))
 559         {
 560                 /* sub-SELECT is like a plain relation */
 561                 RangeTblRef *rtr;
 562
 563                 rtr = transformRangeSubselect(pstate, (RangeSubselect *) n);
 564                 *containedRels = makeListi1(rtr->rtindex);
 565                 return (Node *) rtr;
 566         }
 567         else if (IsA(n, RangeFunction))
 568         {
 569                 /* function is like a plain relation */
 570                 RangeTblRef *rtr;
 571
 572                 rtr = transformRangeFunction(pstate, (RangeFunction *) n);
 573                 *containedRels = makeListi1(rtr->rtindex);
 574                 return (Node *) rtr;
 575         }
 576         else if (IsA(n, JoinExpr))
 577         {
 578                 /* A newfangled join expression */
 579                 JoinExpr   *j = (JoinExpr *) n;
 580                 List       *my_containedRels,
 581                                    *l_containedRels,
 582                                    *r_containedRels,
 583                                    *l_colnames,
 584                                    *r_colnames,
 585                                    *res_colnames,
 586                                    *l_colvars,
 587                                    *r_colvars,
 588                                    *res_colvars;
 589                 Index           leftrti,
 590                                         rightrti;
 591                 RangeTblEntry *rte;
 592
 593                 /*
 594                  * Recursively process the left and right subtrees
 595                  */
 596                 j->larg = transformFromClauseItem(pstate, j->larg, &l_containedRels);
 597                 j->rarg = transformFromClauseItem(pstate, j->rarg, &r_containedRels);
 598
 599                 /*
 600                  * Generate combined list of relation indexes for possible use by
 601                  * transformJoinOnClause below.
 602                  */
 603                 my_containedRels = nconc(l_containedRels, r_containedRels);
 604
 605                 /*
 606                  * Check for conflicting refnames in left and right subtrees. Must
 607                  * do this because higher levels will assume I hand back a self-
 608                  * consistent namespace subtree.
 609                  */
 610                 checkNameSpaceConflicts(pstate, j->larg, j->rarg);
 611
 612                 /*
 613                  * Extract column name and var lists from both subtrees
 614                  *
 615                  * Note: expandRTE returns new lists, safe for me to modify
 616                  */
 617                 if (IsA(j->larg, RangeTblRef))
 618                         leftrti = ((RangeTblRef *) j->larg)->rtindex;
 619                 else if (IsA(j->larg, JoinExpr))
 620                         leftrti = ((JoinExpr *) j->larg)->rtindex;
 621                 else
 622                 {
 623                         elog(ERROR, "transformFromClauseItem: unexpected subtree type");
 624                         leftrti = 0;            /* keep compiler quiet */
 625                 }
 626                 rte = rt_fetch(leftrti, pstate->p_rtable);
 627                 expandRTE(pstate, rte, &l_colnames, &l_colvars);
 628
 629                 if (IsA(j->rarg, RangeTblRef))
 630                         rightrti = ((RangeTblRef *) j->rarg)->rtindex;
 631                 else if (IsA(j->rarg, JoinExpr))
 632                         rightrti = ((JoinExpr *) j->rarg)->rtindex;
 633                 else
 634                 {
 635                         elog(ERROR, "transformFromClauseItem: unexpected subtree type");
 636                         rightrti = 0;           /* keep compiler quiet */
 637                 }
 638                 rte = rt_fetch(rightrti, pstate->p_rtable);
 639                 expandRTE(pstate, rte, &r_colnames, &r_colvars);
 640
 641                 /*
 642                  * Natural join does not explicitly specify columns; must generate
 643                  * columns to join. Need to run through the list of columns from
 644                  * each table or join result and match up the column names. Use
 645                  * the first table, and check every column in the second table for
 646                  * a match.  (We'll check that the matches were unique later on.)
 647                  * The result of this step is a list of column names just like an
 648                  * explicitly-written USING list.
 649                  */
 650                 if (j->isNatural)
 651                 {
 652                         List       *rlist = NIL;
 653                         List       *lx,
 654                                            *rx;
 655
 656                         Assert(j->using == NIL);        /* shouldn't have USING() too */
 657
 658                         foreach(lx, l_colnames)
 659                         {
 660                                 char       *l_colname = strVal(lfirst(lx));
 661                                 Value      *m_name = NULL;
 662
 663                                 foreach(rx, r_colnames)
 664                                 {
 665                                         char       *r_colname = strVal(lfirst(rx));
 666
 667                                         if (strcmp(l_colname, r_colname) == 0)
 668                                         {
 669                                                 m_name = makeString(l_colname);
 670                                                 break;
 671                                         }
 672                                 }
 673
 674                                 /* matched a right column? then keep as join column... */
 675                                 if (m_name != NULL)
 676                                         rlist = lappend(rlist, m_name);
 677                         }
 678
 679                         j->using = rlist;
 680                 }
 681
 682                 /*
 683                  * Now transform the join qualifications, if any.
 684                  */
 685                 res_colnames = NIL;
 686                 res_colvars = NIL;
 687
 688                 if (j->using)
 689                 {
 690                         /*
 691                          * JOIN/USING (or NATURAL JOIN, as transformed above).
 692                          * Transform the list into an explicit ON-condition, and
 693                          * generate a list of merged result columns.
 694                          */
 695                         List       *ucols = j->using;
 696                         List       *l_usingvars = NIL;
 697                         List       *r_usingvars = NIL;
 698                         List       *ucol;
 699
 700                         Assert(j->quals == NULL);       /* shouldn't have ON() too */
 701
 702                         foreach(ucol, ucols)
 703                         {
 704                                 char       *u_colname = strVal(lfirst(ucol));
 705                                 List       *col;
 706                                 int                     ndx;
 707                                 int                     l_index = -1;
 708                                 int                     r_index = -1;
 709                                 Var                *l_colvar,
 710                                                    *r_colvar;
 711
 712                                 /* Check for USING(foo,foo) */
 713                                 foreach(col, res_colnames)
 714                                 {
 715                                         char       *res_colname = strVal(lfirst(col));
 716
 717                                         if (strcmp(res_colname, u_colname) == 0)
 718                                                 elog(ERROR, "USING column name \"%s\" appears more than once", u_colname);
 719                                 }
 720
 721                                 /* Find it in left input */
 722                                 ndx = 0;
 723                                 foreach(col, l_colnames)
 724                                 {
 725                                         char       *l_colname = strVal(lfirst(col));
 726
 727                                         if (strcmp(l_colname, u_colname) == 0)
 728                                         {
 729                                                 if (l_index >= 0)
 730                                                         elog(ERROR, "Common column name \"%s\" appears more than once in left table", u_colname);
 731                                                 l_index = ndx;
 732                                         }
 733                                         ndx++;
 734                                 }
 735                                 if (l_index < 0)
 736                                         elog(ERROR, "JOIN/USING column \"%s\" not found in left table",
 737                                                  u_colname);
 738
 739                                 /* Find it in right input */
 740                                 ndx = 0;
 741                                 foreach(col, r_colnames)
 742                                 {
 743                                         char       *r_colname = strVal(lfirst(col));
 744
 745                                         if (strcmp(r_colname, u_colname) == 0)
 746                                         {
 747                                                 if (r_index >= 0)
 748                                                         elog(ERROR, "Common column name \"%s\" appears more than once in right table", u_colname);
 749                                                 r_index = ndx;
 750                                         }
 751                                         ndx++;
 752                                 }
 753                                 if (r_index < 0)
 754                                         elog(ERROR, "JOIN/USING column \"%s\" not found in right table",
 755                                                  u_colname);
 756
 757                                 l_colvar = nth(l_index, l_colvars);
 758                                 l_usingvars = lappend(l_usingvars, l_colvar);
 759                                 r_colvar = nth(r_index, r_colvars);
 760                                 r_usingvars = lappend(r_usingvars, r_colvar);
 761
 762                                 res_colnames = lappend(res_colnames, lfirst(ucol));
 763                                 res_colvars = lappend(res_colvars,
 764                                                                           buildMergedJoinVar(j->jointype,
 765                                                                                                                  l_colvar,
 766                                                                                                                  r_colvar));
 767                         }
 768
 769                         j->quals = transformJoinUsingClause(pstate,
 770                                                                                                 l_usingvars,
 771                                                                                                 r_usingvars);
 772                 }
 773                 else if (j->quals)
 774                 {
 775                         /* User-written ON-condition; transform it */
 776                         j->quals = transformJoinOnClause(pstate, j, my_containedRels);
 777                 }
 778                 else
 779                 {
 780                         /* CROSS JOIN: no quals */
 781                 }
 782
 783                 /* Add remaining columns from each side to the output columns */
 784                 extractRemainingColumns(res_colnames,
 785                                                                 l_colnames, l_colvars,
 786                                                                 &l_colnames, &l_colvars);
 787                 extractRemainingColumns(res_colnames,
 788                                                                 r_colnames, r_colvars,
 789                                                                 &r_colnames, &r_colvars);
 790                 res_colnames = nconc(res_colnames, l_colnames);
 791                 res_colvars = nconc(res_colvars, l_colvars);
 792                 res_colnames = nconc(res_colnames, r_colnames);
 793                 res_colvars = nconc(res_colvars, r_colvars);
 794
 795                 /*
 796                  * Check alias (AS clause), if any.
 797                  */
 798                 if (j->alias)
 799                 {
 800                         if (j->alias->colnames != NIL)
 801                         {
 802                                 if (length(j->alias->colnames) > length(res_colnames))
 803                                         elog(ERROR, "Column alias list for \"%s\" has too many entries",
 804                                                  j->alias->aliasname);
 805                         }
 806                 }
 807
 808                 /*
 809                  * Now build an RTE for the result of the join
 810                  */
 811                 rte = addRangeTableEntryForJoin(pstate,
 812                                                                                 res_colnames,
 813                                                                                 j->jointype,
 814                                                                                 res_colvars,
 815                                                                                 j->alias,
 816                                                                                 true);
 817
 818                 /* assume new rte is at end */
 819                 j->rtindex = length(pstate->p_rtable);
 820                 Assert(rte == rt_fetch(j->rtindex, pstate->p_rtable));
 821
 822                 /*
 823                  * Include join RTE in returned containedRels list
 824                  */
 825                 *containedRels = lconsi(j->rtindex, my_containedRels);
 826
 827                 return (Node *) j;
 828         }
 829         else
 830                 elog(ERROR, "transformFromClauseItem: unexpected node (internal error)"
 831                          "\n\t%s", nodeToString(n));
 832         return NULL;                            /* can't get here, just keep compiler
 833                                                                  * quiet */
 834 }
 835
 836 /*
 837  * buildMergedJoinVar -
 838  *        generate a suitable replacement expression for a merged join column
 839  */
 840 static Node *
 841 buildMergedJoinVar(JoinType jointype, Var *l_colvar, Var *r_colvar)
 842 {
 843         Oid                     outcoltype;
 844         int32           outcoltypmod;
 845         Node       *l_node,
 846                            *r_node,
 847                            *res_node;
 848
 849         /*
 850          * Choose output type if input types are dissimilar.
 851          */
 852         outcoltype = l_colvar->vartype;
 853         outcoltypmod = l_colvar->vartypmod;
 854         if (outcoltype != r_colvar->vartype)
 855         {
 856                 outcoltype = select_common_type(makeListo2(l_colvar->vartype,
 857                                                                                                    r_colvar->vartype),
 858                                                                                 "JOIN/USING");
 859                 outcoltypmod = -1;              /* ie, unknown */
 860         }
 861         else if (outcoltypmod != r_colvar->vartypmod)
 862         {
 863                 /* same type, but not same typmod */
 864                 outcoltypmod = -1;              /* ie, unknown */
 865         }
 866
 867         /*
 868          * Insert coercion functions if needed.  Note that a difference in
 869          * typmod can only happen if input has typmod but outcoltypmod is -1.
 870          * In that case we insert a RelabelType to clearly mark that result's
 871          * typmod is not same as input.
 872          */
 873         if (l_colvar->vartype != outcoltype)
 874                 l_node = coerce_type((Node *) l_colvar, l_colvar->vartype,
 875                                                          outcoltype,
 876                                                          COERCION_IMPLICIT, COERCE_IMPLICIT_CAST);
 877         else if (l_colvar->vartypmod != outcoltypmod)
 878                 l_node = (Node *) makeRelabelType((Expr *) l_colvar,
 879                                                                                   outcoltype, outcoltypmod,
 880                                                                                   COERCE_IMPLICIT_CAST);
 881         else
 882                 l_node = (Node *) l_colvar;
 883
 884         if (r_colvar->vartype != outcoltype)
 885                 r_node = coerce_type((Node *) r_colvar, r_colvar->vartype,
 886                                                          outcoltype,
 887                                                          COERCION_IMPLICIT, COERCE_IMPLICIT_CAST);
 888         else if (r_colvar->vartypmod != outcoltypmod)
 889                 r_node = (Node *) makeRelabelType((Expr *) r_colvar,
 890                                                                                   outcoltype, outcoltypmod,
 891                                                                                   COERCE_IMPLICIT_CAST);
 892         else
 893                 r_node = (Node *) r_colvar;
 894
 895         /*
 896          * Choose what to emit
 897          */
 898         switch (jointype)
 899         {
 900                 case JOIN_INNER:
 901
 902                         /*
 903                          * We can use either var; prefer non-coerced one if available.
 904                          */
 905                         if (IsA(l_node, Var))
 906                                 res_node = l_node;
 907                         else if (IsA(r_node, Var))
 908                                 res_node = r_node;
 909                         else
 910                                 res_node = l_node;
 911                         break;
 912                 case JOIN_LEFT:
 913                         /* Always use left var */
 914                         res_node = l_node;
 915                         break;
 916                 case JOIN_RIGHT:
 917                         /* Always use right var */
 918                         res_node = r_node;
 919                         break;
 920                 case JOIN_FULL:
 921                         {
 922                                 /*
 923                                  * Here we must build a COALESCE expression to ensure that
 924                                  * the join output is non-null if either input is.
 925                                  */
 926                                 CaseExpr   *c = makeNode(CaseExpr);
 927                                 CaseWhen   *w = makeNode(CaseWhen);
 928                                 NullTest   *n = makeNode(NullTest);
 929
 930                                 n->arg = (Expr *) l_node;
 931                                 n->nulltesttype = IS_NOT_NULL;
 932                                 w->expr = (Expr *) n;
 933                                 w->result = (Expr *) l_node;
 934                                 c->casetype = outcoltype;
 935                                 c->args = makeList1(w);
 936                                 c->defresult = (Expr *) r_node;
 937                                 res_node = (Node *) c;
 938                                 break;
 939                         }
 940                 default:
 941                         elog(ERROR, "buildMergedJoinVar: unexpected jointype %d",
 942                                  (int) jointype);
 943                         res_node = NULL;        /* keep compiler quiet */
 944                         break;
 945         }
 946
 947         return res_node;
 948 }
 949
 950
 951 /*
 952  * transformWhereClause -
 953  *        transforms the qualification and make sure it is of type Boolean
 954  */
 955 Node *
 956 transformWhereClause(ParseState *pstate, Node *clause)
 957 {
 958         Node       *qual;
 959
 960         if (clause == NULL)
 961                 return NULL;
 962
 963         qual = transformExpr(pstate, clause);
 964
 965         qual = coerce_to_boolean(qual, "WHERE");
 966
 967         return qual;
 968 }
 969
 970
 971 /*
 972  *      findTargetlistEntry -
 973  *        Returns the targetlist entry matching the given (untransformed) node.
 974  *        If no matching entry exists, one is created and appended to the target
 975  *        list as a "resjunk" node.
 976  *
 977  * node         the ORDER BY, GROUP BY, or DISTINCT ON expression to be matched
 978  * tlist        the existing target list (NB: this will never be NIL, which is a
 979  *                      good thing since we'd be unable to append to it if it were...)
 980  * clause       identifies clause type being processed.
 981  */
 982 static TargetEntry *
 983 findTargetlistEntry(ParseState *pstate, Node *node, List *tlist, int clause)
 984 {
 985         TargetEntry *target_result = NULL;
 986         List       *tl;
 987         Node       *expr;
 988
 989         /*----------
 990          * Handle two special cases as mandated by the SQL92 spec:
 991          *
 992          * 1. Bare ColumnName (no qualifier or subscripts)
 993          *        For a bare identifier, we search for a matching column name
 994          *        in the existing target list.  Multiple matches are an error
 995          *        unless they refer to identical values; for example,
 996          *        we allow      SELECT a, a FROM table ORDER BY a
 997          *        but not       SELECT a AS b, b FROM table ORDER BY b
 998          *        If no match is found, we fall through and treat the identifier
 999          *        as an expression.
1000          *        For GROUP BY, it is incorrect to match the grouping item against
1001          *        targetlist entries: according to SQL92, an identifier in GROUP BY
1002          *        is a reference to a column name exposed by FROM, not to a target
1003          *        list column.  However, many implementations (including pre-7.0
1004          *        PostgreSQL) accept this anyway.  So for GROUP BY, we look first
1005          *        to see if the identifier matches any FROM column name, and only
1006          *        try for a targetlist name if it doesn't.  This ensures that we
1007          *        adhere to the spec in the case where the name could be both.
1008          *        DISTINCT ON isn't in the standard, so we can do what we like there;
1009          *        we choose to make it work like ORDER BY, on the rather flimsy
1010          *        grounds that ordinary DISTINCT works on targetlist entries.
1011          *
1012          * 2. IntegerConstant
1013          *        This means to use the n'th item in the existing target list.
1014          *        Note that it would make no sense to order/group/distinct by an
1015          *        actual constant, so this does not create a conflict with our
1016          *        extension to order/group by an expression.
1017          *        GROUP BY column-number is not allowed by SQL92, but since
1018          *        the standard has no other behavior defined for this syntax,
1019          *        we may as well accept this common extension.
1020          *
1021          * Note that pre-existing resjunk targets must not be used in either case,
1022          * since the user didn't write them in his SELECT list.
1023          *
1024          * If neither special case applies, fall through to treat the item as
1025          * an expression.
1026          *----------
1027          */
1028         if (IsA(node, ColumnRef) &&
1029                 length(((ColumnRef *) node)->fields) == 1 &&
1030                 ((ColumnRef *) node)->indirection == NIL)
1031         {
1032                 char       *name = strVal(lfirst(((ColumnRef *) node)->fields));
1033
1034                 if (clause == GROUP_CLAUSE)
1035                 {
1036                         /*
1037                          * In GROUP BY, we must prefer a match against a FROM-clause
1038                          * column to one against the targetlist.  Look to see if there
1039                          * is a matching column.  If so, fall through to let
1040                          * transformExpr() do the rest.  NOTE: if name could refer
1041                          * ambiguously to more than one column name exposed by FROM,
1042                          * colnameToVar will elog(ERROR).  That's just what we want
1043                          * here.
1044                          */
1045                         if (colnameToVar(pstate, name) != NULL)
1046                                 name = NULL;
1047                 }
1048
1049                 if (name != NULL)
1050                 {
1051                         foreach(tl, tlist)
1052                         {
1053                                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1054                                 Resdom     *resnode = tle->resdom;
1055
1056                                 if (!resnode->resjunk &&
1057                                         strcmp(resnode->resname, name) == 0)
1058                                 {
1059                                         if (target_result != NULL)
1060                                         {
1061                                                 if (!equal(target_result->expr, tle->expr))
1062                                                         elog(ERROR, "%s '%s' is ambiguous",
1063                                                                  clauseText[clause], name);
1064                                         }
1065                                         else
1066                                                 target_result = tle;
1067                                         /* Stay in loop to check for ambiguity */
1068                                 }
1069                         }
1070                         if (target_result != NULL)
1071                                 return target_result;   /* return the first match */
1072                 }
1073         }
1074         if (IsA(node, A_Const))
1075         {
1076                 Value      *val = &((A_Const *) node)->val;
1077                 int                     targetlist_pos = 0;
1078                 int                     target_pos;
1079
1080                 if (!IsA(val, Integer))
1081                         elog(ERROR, "Non-integer constant in %s", clauseText[clause]);
1082                 target_pos = intVal(val);
1083                 foreach(tl, tlist)
1084                 {
1085                         TargetEntry *tle = (TargetEntry *) lfirst(tl);
1086                         Resdom     *resnode = tle->resdom;
1087
1088                         if (!resnode->resjunk)
1089                         {
1090                                 if (++targetlist_pos == target_pos)
1091                                         return tle; /* return the unique match */
1092                         }
1093                 }
1094                 elog(ERROR, "%s position %d is not in target list",
1095                          clauseText[clause], target_pos);
1096         }
1097
1098         /*
1099          * Otherwise, we have an expression (this is a Postgres extension not
1100          * found in SQL92).  Convert the untransformed node to a transformed
1101          * expression, and search for a match in the tlist. NOTE: it doesn't
1102          * really matter whether there is more than one match.  Also, we are
1103          * willing to match a resjunk target here, though the above cases must
1104          * ignore resjunk targets.
1105          */
1106         expr = transformExpr(pstate, node);
1107
1108         foreach(tl, tlist)
1109         {
1110                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1111
1112                 if (equal(expr, tle->expr))
1113                         return tle;
1114         }
1115
1116         /*
1117          * If no matches, construct a new target entry which is appended to
1118          * the end of the target list.  This target is given resjunk = TRUE so
1119          * that it will not be projected into the final tuple.
1120          */
1121         target_result = transformTargetEntry(pstate, node, expr, NULL, true, NULL);
1122         lappend(tlist, target_result);
1123
1124         return target_result;
1125 }
1126
1127
1128 /*
1129  * transformGroupClause -
1130  *        transform a GROUP BY clause
1131  */
1132 List *
1133 transformGroupClause(ParseState *pstate, List *grouplist, List *targetlist)
1134 {
1135         List       *glist = NIL,
1136                            *gl;
1137
1138         foreach(gl, grouplist)
1139         {
1140                 TargetEntry *tle;
1141
1142                 tle = findTargetlistEntry(pstate, lfirst(gl),
1143                                                                   targetlist, GROUP_CLAUSE);
1144
1145                 /* avoid making duplicate grouplist entries */
1146                 if (!targetIsInSortList(tle, glist))
1147                 {
1148                         GroupClause *grpcl = makeNode(GroupClause);
1149
1150                         grpcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
1151
1152                         grpcl->sortop = ordering_oper_opid(tle->resdom->restype);
1153
1154                         glist = lappend(glist, grpcl);
1155                 }
1156         }
1157
1158         return glist;
1159 }
1160
1161 /*
1162  * transformSortClause -
1163  *        transform an ORDER BY clause
1164  */
1165 List *
1166 transformSortClause(ParseState *pstate,
1167                                         List *orderlist,
1168                                         List *targetlist)
1169 {
1170         List       *sortlist = NIL;
1171         List       *olitem;
1172
1173         foreach(olitem, orderlist)
1174         {
1175                 SortGroupBy *sortby = lfirst(olitem);
1176                 TargetEntry *tle;
1177
1178                 tle = findTargetlistEntry(pstate, sortby->node,
1179                                                                   targetlist, ORDER_CLAUSE);
1180
1181                 sortlist = addTargetToSortList(tle, sortlist, targetlist,
1182                                                                            sortby->useOp);
1183         }
1184
1185         return sortlist;
1186 }
1187
1188 /*
1189  * transformDistinctClause -
1190  *        transform a DISTINCT or DISTINCT ON clause
1191  *
1192  * Since we may need to add items to the query's sortClause list, that list
1193  * is passed by reference.      We might also need to add items to the query's
1194  * targetlist, but we assume that cannot be empty initially, so we can
1195  * lappend to it even though the pointer is passed by value.
1196  */
1197 List *
1198 transformDistinctClause(ParseState *pstate, List *distinctlist,
1199                                                 List *targetlist, List **sortClause)
1200 {
1201         List       *result = NIL;
1202         List       *slitem;
1203         List       *dlitem;
1204
1205         /* No work if there was no DISTINCT clause */
1206         if (distinctlist == NIL)
1207                 return NIL;
1208
1209         if (lfirst(distinctlist) == NIL)
1210         {
1211                 /* We had SELECT DISTINCT */
1212
1213                 /*
1214                  * All non-resjunk elements from target list that are not already
1215                  * in the sort list should be added to it.      (We don't really care
1216                  * what order the DISTINCT fields are checked in, so we can leave
1217                  * the user's ORDER BY spec alone, and just add additional sort
1218                  * keys to it to ensure that all targetlist items get sorted.)
1219                  */
1220                 *sortClause = addAllTargetsToSortList(*sortClause, targetlist);
1221
1222                 /*
1223                  * Now, DISTINCT list consists of all non-resjunk sortlist items.
1224                  * Actually, all the sortlist items had better be non-resjunk!
1225                  * Otherwise, user wrote SELECT DISTINCT with an ORDER BY item
1226                  * that does not appear anywhere in the SELECT targetlist, and we
1227                  * can't implement that with only one sorting pass...
1228                  */
1229                 foreach(slitem, *sortClause)
1230                 {
1231                         SortClause *scl = (SortClause *) lfirst(slitem);
1232                         TargetEntry *tle = get_sortgroupclause_tle(scl, targetlist);
1233
1234                         if (tle->resdom->resjunk)
1235                                 elog(ERROR, "For SELECT DISTINCT, ORDER BY expressions must appear in target list");
1236                         else
1237                                 result = lappend(result, copyObject(scl));
1238                 }
1239         }
1240         else
1241         {
1242                 /* We had SELECT DISTINCT ON (expr, ...) */
1243
1244                 /*
1245                  * If the user writes both DISTINCT ON and ORDER BY, then the two
1246                  * expression lists must match (until one or the other runs out).
1247                  * Otherwise the ORDER BY requires a different sort order than the
1248                  * DISTINCT does, and we can't implement that with only one sort
1249                  * pass (and if we do two passes, the results will be rather
1250                  * unpredictable). However, it's OK to have more DISTINCT ON
1251                  * expressions than ORDER BY expressions; we can just add the
1252                  * extra DISTINCT values to the sort list, much as we did above
1253                  * for ordinary DISTINCT fields.
1254                  *
1255                  * Actually, it'd be OK for the common prefixes of the two lists to
1256                  * match in any order, but implementing that check seems like more
1257                  * trouble than it's worth.
1258                  */
1259                 List       *nextsortlist = *sortClause;
1260
1261                 foreach(dlitem, distinctlist)
1262                 {
1263                         TargetEntry *tle;
1264
1265                         tle = findTargetlistEntry(pstate, lfirst(dlitem),
1266                                                                           targetlist, DISTINCT_ON_CLAUSE);
1267
1268                         if (nextsortlist != NIL)
1269                         {
1270                                 SortClause *scl = (SortClause *) lfirst(nextsortlist);
1271
1272                                 if (tle->resdom->ressortgroupref != scl->tleSortGroupRef)
1273                                         elog(ERROR, "SELECT DISTINCT ON expressions must match initial ORDER BY expressions");
1274                                 result = lappend(result, copyObject(scl));
1275                                 nextsortlist = lnext(nextsortlist);
1276                         }
1277                         else
1278                         {
1279                                 *sortClause = addTargetToSortList(tle, *sortClause,
1280                                                                                                   targetlist, NIL);
1281
1282                                 /*
1283                                  * Probably, the tle should always have been added at the
1284                                  * end of the sort list ... but search to be safe.
1285                                  */
1286                                 foreach(slitem, *sortClause)
1287                                 {
1288                                         SortClause *scl = (SortClause *) lfirst(slitem);
1289
1290                                         if (tle->resdom->ressortgroupref == scl->tleSortGroupRef)
1291                                         {
1292                                                 result = lappend(result, copyObject(scl));
1293                                                 break;
1294                                         }
1295                                 }
1296                                 if (slitem == NIL)
1297                                         elog(ERROR, "transformDistinctClause: failed to add DISTINCT ON clause to target list");
1298                         }
1299                 }
1300         }
1301
1302         return result;
1303 }
1304
1305 /*
1306  * addAllTargetsToSortList
1307  *              Make sure all non-resjunk targets in the targetlist are in the
1308  *              ORDER BY list, adding the not-yet-sorted ones to the end of the list.
1309  *              This is typically used to help implement SELECT DISTINCT.
1310  *
1311  * Returns the updated ORDER BY list.
1312  */
1313 List *
1314 addAllTargetsToSortList(List *sortlist, List *targetlist)
1315 {
1316         List       *i;
1317
1318         foreach(i, targetlist)
1319         {
1320                 TargetEntry *tle = (TargetEntry *) lfirst(i);
1321
1322                 if (!tle->resdom->resjunk)
1323                         sortlist = addTargetToSortList(tle, sortlist, targetlist, NIL);
1324         }
1325         return sortlist;
1326 }
1327
1328 /*
1329  * addTargetToSortList
1330  *              If the given targetlist entry isn't already in the ORDER BY list,
1331  *              add it to the end of the list, using the sortop with given name
1332  *              or the default sort operator if opname == NIL.
1333  *
1334  * Returns the updated ORDER BY list.
1335  */
1336 static List *
1337 addTargetToSortList(TargetEntry *tle, List *sortlist, List *targetlist,
1338                                         List *opname)
1339 {
1340         /* avoid making duplicate sortlist entries */
1341         if (!targetIsInSortList(tle, sortlist))
1342         {
1343                 SortClause *sortcl = makeNode(SortClause);
1344
1345                 sortcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
1346
1347                 if (opname)
1348                         sortcl->sortop = compatible_oper_opid(opname,
1349                                                                                                   tle->resdom->restype,
1350                                                                                                   tle->resdom->restype,
1351                                                                                                   false);
1352                 else
1353                         sortcl->sortop = ordering_oper_opid(tle->resdom->restype);
1354
1355                 sortlist = lappend(sortlist, sortcl);
1356         }
1357         return sortlist;
1358 }
1359
1360 /*
1361  * assignSortGroupRef
1362  *        Assign the targetentry an unused ressortgroupref, if it doesn't
1363  *        already have one.  Return the assigned or pre-existing refnumber.
1364  *
1365  * 'tlist' is the targetlist containing (or to contain) the given targetentry.
1366  */
1367 Index
1368 assignSortGroupRef(TargetEntry *tle, List *tlist)
1369 {
1370         Index           maxRef;
1371         List       *l;
1372
1373         if (tle->resdom->ressortgroupref)       /* already has one? */
1374                 return tle->resdom->ressortgroupref;
1375
1376         /* easiest way to pick an unused refnumber: max used + 1 */
1377         maxRef = 0;
1378         foreach(l, tlist)
1379         {
1380                 Index           ref = ((TargetEntry *) lfirst(l))->resdom->ressortgroupref;
1381
1382                 if (ref > maxRef)
1383                         maxRef = ref;
1384         }
1385         tle->resdom->ressortgroupref = maxRef + 1;
1386         return tle->resdom->ressortgroupref;
1387 }
1388
1389 /*
1390  * targetIsInSortList
1391  *              Is the given target item already in the sortlist?
1392  *
1393  * Works for both SortClause and GroupClause lists.  Note that the main
1394  * reason we need this routine (and not just a quick test for nonzeroness
1395  * of ressortgroupref) is that a TLE might be in only one of the lists.
1396  */
1397 static bool
1398 targetIsInSortList(TargetEntry *tle, List *sortList)
1399 {
1400         Index           ref = tle->resdom->ressortgroupref;
1401         List       *i;
1402
1403         /* no need to scan list if tle has no marker */
1404         if (ref == 0)
1405                 return false;
1406
1407         foreach(i, sortList)
1408         {
1409                 SortClause *scl = (SortClause *) lfirst(i);
1410
1411                 if (scl->tleSortGroupRef == ref)
1412                         return true;
1413         }
1414         return false;
1415 }