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