commit c4ac2ff765d9b68a3ff2a3461804489721770d06
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Mon Jun 21 00:14:54 2010 +0000

    Fix mishandling of whole-row Vars referencing a view or sub-select.
    If such a Var appeared within a nested sub-select, we failed to translate it
    correctly during pullup of the view, because the recursive call to
    replace_rte_variables_mutator was looking for the wrong sublevels_up value.
    Bug was introduced during the addition of the PlaceHolderVar mechanism.
    Per bug #5514 from Marcos Castedo.

  commit e5536e77
  Author: Tom Lane <tgl@sss.pgh.pa.us>
  Date:   Mon Aug 25 22:42:34 2008 +0000

      Move exprType(), exprTypmod(), expression_tree_walker(), and related routines
      into nodes/nodeFuncs, so as to reduce wanton cross-subsystem #includes inside
      the backend.  There's probably more that should be done along this line,
      but this is a start anyway
Signed-off-by: NShreedhar Hardikar <shardikar@pivotal.io>

We had a bunch of fixmes that we added as part of the subselect merge;
All of the fixmes are now marked as `GPDB_84_MERGE_FIXME` so that they can
be grepped easily.

commit 2bdd765f79df947b46a8b5a22e3b993b58cd6d32
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Wed Sep 2 17:52:33 2009 +0000

    Fix subquery pullup to wrap a PlaceHolderVar around the entire RowExpr
    that's generated for a whole-row Var referencing the subquery, when the
    subquery is in the nullable side of an outer join.  The previous coding
    instead put PlaceHolderVars around the elements of the RowExpr.  The effect
    was that when the outer join made the subquery outputs go to null, the
    whole-row Var produced ROW(NULL,NULL,...) rather than just NULL.  There
    are arguments afoot about whether those things ought to be semantically
    indistinguishable, but for the moment they are not entirely so, and the
    planner needs to take care that its machinations preserve the difference.
    Per bug #5025.

    Making this feasible required refactoring ResolveNew() to allow more caller
    control over what is substituted for a Var.  I chose to make ResolveNew()
    a wrapper around a new general-purpose function replace_rte_variables().
    I also fixed the ancient bogosity that ResolveNew might fail to set
    a query's hasSubLinks field after inserting a SubLink in it.  Although
    all current callers make sure that happens anyway, we've had bugs of that
    sort before, and it seemed like a good time to install a proper solution.

    Back-patch to 8.4.  The problem can be demonstrated clear back to 8.0,
    but the fix would be too invasive in earlier branches; not to mention
    that people may be depending on the subtly-incorrect behavior.  The
    8.4 series is new enough that fixing this probably won't cause complaints,
    but it might in older branches.  Also, 8.4 shows the incorrect behavior
    in more cases than older branches do, because it is able to flatten
    subqueries in more cases.
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

commit c59d8dd4
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Tue Apr 28 21:31:16 2009 +0000

    Improve pull_up_subqueries logic so that it doesn't insert unnecessary
    PlaceHolderVar nodes in join quals appearing in or below the lowest
    outer join that could null the subquery being pulled up.  This improves
    the planner's ability to recognize constant join quals, and probably
    helps with detection of common sort keys (equivalence classes) as well.
Signed-off-by: NDhanashree Kashid <dkashid@pivotal.io>

commit 31468d05
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Wed Oct 22 20:17:52 2008 +0000

    Dept of better ideas: refrain from creating the planner's placeholder_list
    until vars are distributed to rels during query_planner() startup.  We don't
    really need it before that, and not building it early has some advantages.
    First, we don't need to put it through the various preprocessing steps, which
    saves some cycles and eliminates the need for a number of routines to support
    PlaceHolderInfo nodes at all.  Second, this means one less unused plan for any
    sub-SELECT appearing in a placeholder's expression, since we don't build
    placeholder_list until after sublink expansion is complete.
Signed-off-by: NDhanashree Kashid <dkashid@pivotal.io>

commit e6ae3b5d
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Tue Oct 21 20:42:53 2008 +0000

    Add a concept of "placeholder" variables to the planner.  These are variables
    that represent some expression that we desire to compute below the top level
    of the plan, and then let that value "bubble up" as though it were a plain
    Var (ie, a column value).

    The immediate application is to allow sub-selects to be flattened even when
    they are below an outer join and have non-nullable output expressions.
    Formerly we couldn't flatten because such an expression wouldn't properly
    go to NULL when evaluated above the outer join.  Now, we wrap it in a
    PlaceHolderVar and arrange for the actual evaluation to occur below the outer
    join.  When the resulting Var bubbles up through the join, it will be set to
    NULL if necessary, yielding the correct results.  This fixes a planner
    limitation that's existed since 7.1.

    In future we might want to use this mechanism to re-introduce some form of
    Hellerstein's "expensive functions" optimization, ie place the evaluation of
    an expensive function at the most suitable point in the plan tree.
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

0. Fix up post join dedup logic after cherry-pick
0. Fix pull_up_sublinks_jointree_recurse returning garbage relids
0. Update gporca, rangefuncs, eagerfree answer fileis
	1. gporca
	Previously we were generating a Hash Inner Join with an
	HashAggregate for deduplication. Now we generate a Hash
	Semi Join in which case we do not need to deduplicate the
	inner.

	2. rangefuncs
	We updated this answer file during the cherry-pick of
	e006a24a since there was a change in plan.
	After these cherry-picks, we are back to the original
	plan as master. Hence we see the original error.

	3. eagerfree
	We are generating a not-very-useful subquery scan node
	with this change. This is not producing wrong results.
	But this subqeury scan needs to be removed.
	We will file a follow-up chore to investigate and fix this.

0. We no longer need helper function `hasSemiJoin()` to check whether
this specialInfo list has any specialJoinInfos constructed for Semi Join
(IN/EXISTS sublink). We have moved that check inside
`cdb_set_cheapest_dedup()`

0. We are not exercising the pre-join-deduplication code path after
this cherry-pick. Before this merge, we had three CDB specific
nodes in `InClauseInfo` in which we recorded information for
pre-join-dedup in case of simple uncorrelated IN sublinks.
`try_join_unique`, `sub_targetlist` and `InOperators`
Since we now have `SpecialJoinInfo` instead of `InClauseInfo`, we need
to devise a way to record this information in `SpecialJoinInfo`.
We have filed a follow-up story for this.

Ref [#142356521]
Signed-off-by: NDhanashree Kashid <dkashid@pivotal.io>

commit e549722a
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Wed Feb 25 03:30:38 2009 +0000

    Get rid of the rather fuzzily defined FlattenedSubLink node type in favor of
    making pull_up_sublinks() construct a full-blown JoinExpr tree representation
    of IN/EXISTS SubLinks that it is able to convert to semi or anti joins.
    This makes pull_up_sublinks() a shade more complex, but the gain in semantic
    clarity is worth it.  I still have more to do in this area to address the
    previously-discussed problems, but this commit in itself fixes at least one
    bug in HEAD, as shown by added regression test case.

Ref [#142356521]
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

commit 19e34b62
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Sun Aug 17 01:20:00 2008 +0000

    Improve sublink pullup code to handle ANY/EXISTS sublinks that are at top
    level of a JOIN/ON clause, not only at top level of WHERE.  (However, we
    can't do this in an outer join's ON clause, unless the ANY/EXISTS refers
    only to the nullable side of the outer join, so that it can effectively
    be pushed down into the nullable side.)  Per request from Kevin Grittner.

    In passing, fix a bug in the initial implementation of EXISTS pullup:
    it would Assert if the EXIST's WHERE clause used a join alias variable.
    Since we haven't yet flattened join aliases when this transformation
    happens, it's necessary to include join relids in the computed set of
    RHS relids.

Ref [#142356521]
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

After merging with e006a24a, Anti Semi Join will
be denoted by `JOIN_ANTI` instead of `JOIN_LASJ`

Ref [#142355175]
Signed-off-by: NDhanashree Kashid <dkashid@pivotal.io>

With the new flow, we don't need the following functions:

 - pull_up_IN_clauses
 - convert_EXISTS_to_join
 - convert_NOT_EXISTS_to_antijoin
 - not_null_inner_vars
 - safe_to_convert_NOT_EXISTS
 - convert_sublink_to_join

Ref [#142355175]
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

Original Flow:
cdb_flatten_sublinks
	+--> pull_up_IN_clauses
		+--> convert_sublink_to_join

New Flow:
cdb_flatten_sublinks
	+--> pull_up_sublinks

This commit contains relevant changes for the above flow.

Previously, `try_join_unique` was part of `InClauseInfo`. It was getting
set in `convert_IN_to_join()` and used in `cdb_make_rel_dedup_info()`.
Now, since `InClauseInfo` is not present and we construct
`FlattenedSublink` instead in `convert_ANY_sublink_to_join()`. And later
in the flow, we construct `SpecialJoinInfo` from `FlattenedSublink` in
`deconstruct_sublink_quals_to_rel()`. Hence, adding `try_join_unique` as
part of both `FlattenedSublink` and `SpecialJoinInfo`.

Ref [#142355175]
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

commit e006a24a
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Thu Aug 14 18:48:00 2008 +0000

    Implement SEMI and ANTI joins in the planner and executor.  (Semijoins replace
    the old JOIN_IN code, but antijoins are new functionality.)  Teach the planner
    to convert appropriate EXISTS and NOT EXISTS subqueries into semi and anti
    joins respectively.  Also, LEFT JOINs with suitable upper-level IS NULL
    filters are recognized as being anti joins.  Unify the InClauseInfo and
    OuterJoinInfo infrastructure into "SpecialJoinInfo".  With that change,
    it becomes possible to associate a SpecialJoinInfo with every join attempt,
    which permits some cleanup of join selectivity estimation.  That needs to be
    taken much further than this patch does, but the next step is to change the
    API for oprjoin selectivity functions, which seems like material for a
    separate patch.  So for the moment the output size estimates for semi and
    especially anti joins are quite bogus.

Ref [#142355175]
Signed-off-by: NEkta Khanna <ekhanna@pivotal.io>

A Motion node often needs to "merge" the incoming streams, to preserve the
overall sort order. Instead of carrying sort order information throughout
the later stages of planning, in the Flow struct, pass it as argument
directly to make_motion() and other functions, where a Motion node is
created. This simplifies things.

To make that work, we can no longer rely on apply_motion() to add the final
Motion on top of the plan, when the (sub-)query contains an ORDER BY. That's
because we no longer have that information available at apply_motion(). Add
the Motion node in grouping_planner() instead, where we still have that
information, as a path key.

When I started to work on this, this also fixed a bug, where the sortColIdx
of plan flow node may refer to wrong resno. A test case for that is
included. However, that case was since fixed by other coincidental changes
to partition elimination, so now this is just refactoring.

In GPDB, we have so far used a WindowFrame struct to represent the start
and end window bound, in a ROWS/RANGE BETWEEN clause, while PostgreSQL
uses the combination of  a frameOptions bitmask and start and end
expressions. Refactor to replace the WindowFrame with the upstream
representation.

In the upstream, two different structs are used to represent a window
definition. WindowDef in the grammar, which is transformed into
WindowClause during parse analysis. In GPDB, we've been using the same
struct, WindowSpec, in both stages. Split it up, to match the upstream.

The representation of the window frame, i.e. "ROWS/RANGE BETWEEN ..." was
different between the upstream implementation and the GPDB one. We now use
the upstream frameOptions+startOffset+endOffset representation in raw
WindowDef parse node, but it's still converted to the WindowFrame
representation for the later stages, so WindowClause still uses that. I
will switch over the rest of the codebase to the upstream representation as
a separate patch.

Also, refactor WINDOW clause deparsing to be closer to upstream.

One notable difference is that the old WindowSpec.winspec field corresponds
to the winref field in WindowDef andWindowClause, except that the new
'winref' is 1-based, while the old field was 0-based.

Another noteworthy thing is that this forbids specifying "OVER (w
ROWS/RANGE BETWEEN ...", if the window "w" already specified a window frame,
i.e. a different ROWS/RANGE BETWEEN. There was one such case in the
regression suite, in window_views, and this updates the expected output of
that to be an error.

This bumps the copyright years to the appropriate years after not
having been updated for some time.  Also reformats existing code
headers to match the upstream style to ensure consistency.

This brought in postgres/postgres@44d5be0 pretty much wholesale, except:

1. We leave `WITH RECURSIVE` for a later commit. The code is brought in,
    but kept dormant by us bailing early at the parser whenever there is
    a recursive CTE.
2. We use `ShareInputScan` in the stead of `CteScan`. ShareInputScan is
    basically the parallel-capable `CteScan`. (See `set_cte_pathlist`
    and `create_ctescan_plan`)
3. Consequently we do not put the sub-plan for the CTE in a
    pseudo-initplan: it is directly present in the main plan tree
    instead, hence we disable `SS_process_ctes` inside
    `subquery_planner`
4. Another corollary is that all new operators (`CteScan`,
    `RecursiveUnion`, and `WorkTableScan`) are dead code right now. But
    they will come to live once we bring in parallel implementation of
    `WITH RECURSIVE`

In general this commit reduces the divergence between Greenplum and
upstream.

User visible changes:
The merge in parser enables a corner case previously treated as error:
you can now specify fewer columns in your `WITH` clause than the actual
projected columns in the body subquery of the `WITH`.

Original commit message:

> Implement SQL-standard WITH clauses, including WITH RECURSIVE.
>
> There are some unimplemented aspects: recursive queries must use UNION ALL
> (should allow UNION too), and we don't have SEARCH or CYCLE clauses.
> These might or might not get done for 8.4, but even without them it's a
> pretty useful feature.
>
> There are also a couple of small loose ends and definitional quibbles,
> which I'll send a memo about to pgsql-hackers shortly.  But let's land
> the patch now so we can get on with other development.
>
> Yoshiyuki Asaba, with lots of help from Tatsuo Ishii and Tom Lane
>

(cherry picked from commit 44d5be0e)

When we have a correlated subquery with EXISTS and CTE, the planner
produces wrong plan as:

```
pivotal=# explain with t as (select 1) select * from foo where exists (select * from bar where foo.a = 'a' and foo.b = 'b');
                                             QUERY PLAN
----------------------------------------------------------------------------------------------------
 Gather Motion 3:1  (slice3; segments: 3)  (cost=0.01..1522.03 rows=5055210000 width=16)
   ->  Nested Loop  (cost=0.01..1522.03 rows=1685070000 width=16)
         ->  Broadcast Motion 1:3  (slice2; segments: 1)  (cost=0.01..0.03 rows=1 width=0)
               ->  Limit  (cost=0.01..0.01 rows=1 width=0)
                     ->  Gather Motion 3:1  (slice1; segments: 3)  (cost=0.01..0.03 rows=1 width=0)
                           ->  Limit  (cost=0.01..0.01 rows=1 width=0)
                                 ->  Result  (cost=0.01..811.00 rows=23700 width=0)
                                       One-Time Filter: $0 = 'a'::bpchar AND $1 = 'b'::bpchar
                                       ->  Seq Scan on bar  (cost=0.01..811.00 rows=23700 width=0)
         ->  Seq Scan on foo  (cost=0.00..811.00 rows=23700 width=16)
 Optimizer status: legacy query optimizer
(11 rows)
```

This failed during execution because $0 is referenced across the slices.

Root Cause:
That's because planner produce a plan with `$0` aka `param` but without
`subplan`.  The `param` is created by `replace_outer_var()`, when planner
detects a query referring to relations from its outer/parent query.  Such `var`
is created when removing `sublink` in `convert_EXISTS_to_join()` function.  In
that function, when handling the `EXISTS` query, we convert the `EXISTS_sublink`
to a `subquery RTE` (and expect it to get pulled up later by
`pull_up_subquery()`.  However the subquery cannot be pulled-up by
`pull_up_subquery()` since it is not a simple subquery (`is_simple_subquery()`
returns false because of CTE in this case).  In this case, the `sublink` got
removed, hence it cannot produce the `subplan` (which is an valid option).  And
the `var` left behind as outer-reference, and then covered to param, which is
blowed up during query execution.  There is a mismatching conditions between
`convert_EXISTS_to_join()` and `pull_up_subquery()` about whether this subquery
can be pulled-up.

The fix is to reuse `is_simple_subquery()` checking when
`convert_EXISTS_to_join()`, so that it can be consistent with
`pull_up_subquery()` on whether subquery can be pulled or not.

The correct plan after fix is:

```
pivotal=# explain with t as (select 1) select * from foo where exists (select * from bar where foo.a = 'a' and foo.b = 'b');
                                                      QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
 Gather Motion 3:1  (slice2; segments: 3)  (cost=0.00..1977.50 rows=35550 width=16)
   ->  Seq Scan on foo  (cost=0.00..1977.50 rows=11850 width=16)
         Filter: (subplan)
         SubPlan 1
           ->  Result  (cost=0.01..811.00 rows=23700 width=16)
                 One-Time Filter: $0 = 'a'::bpchar AND $1 = 'b'::bpchar
                 ->  Result  (cost=882.11..1593.11 rows=23700 width=16)
                       ->  Materialize  (cost=882.11..1593.11 rows=23700 width=16)
                             ->  Broadcast Motion 3:3  (slice1; segments: 3)  (cost=0.01..811.00 rows=23700 width=16)
                                   ->  Seq Scan on bar  (cost=0.01..811.00 rows=23700 width=16)
 Optimizer status: legacy query optimizer
(11 rows)
```
Signed-off-by: NDhanashree Kashid <dkashid@pivotal.io>

And some other cosmetic cleanup to match upstream better.

This makes merging easier.

parent, not only those with RangeTblRefs. We need them in ExecCheckRTPerms.

Report by Brendan O'Shea. Back-patch to 8.2, where pull_up_simple_union_all
was introduced.

are declared to return set, and consist of just a single SELECT.  We
can replace the FROM-item with a sub-SELECT and then optimize much as
if we were dealing with a view.  Patch from Richard Rowell, cleaned up
by me.

types of unspecified parameters when submitted via extended query protocol.
This worked in 8.2 but I had broken it during plancache changes.  DECLARE
CURSOR is now treated almost exactly like a plain SELECT through parse
analysis, rewrite, and planning; only just before sending to the executor
do we divert it away to ProcessUtility.  This requires a special-case check
in a number of places, but practically all of them were already special-casing
SELECT INTO, so it's not too ugly.  (Maybe it would be a good idea to merge
the two by treating IntoClause as a form of utility statement?  Not going to
worry about that now, though.)  That approach doesn't work for EXPLAIN,
however, so for that I punted and used a klugy solution of running parse
analysis an extra time if under extended query protocol.

this code was last gone over, there wasn't really any alternative to
globals because we didn't have the PlannerInfo struct being passed all
through the planner code.  Now that we do, we can restructure things
to avoid non-reentrancy.  I'm fooling with this because otherwise I'd
have had to add another global variable for the planned compact
range table list.

representation of equivalence classes of variables.  This is an extensive
rewrite, but it brings a number of benefits:
* planner no longer fails in the presence of "incomplete" operator families
that don't offer operators for every possible combination of datatypes.
* avoid generating and then discarding redundant equality clauses.
* remove bogus assumption that derived equalities always use operators
named "=".
* mergejoins can work with a variety of sort orders (e.g., descending) now,
instead of tying each mergejoinable operator to exactly one sort order.
* better recognition of redundant sort columns.
* can make use of equalities appearing underneath an outer join.

back-stamped for this.

functions in its targetlist, to avoid introducing multiple evaluations
of volatile functions that textually appear only once.  This is a
slightly tighter version of Jaime Casanova's recent patch.

merely a matter of fixing the error check, since the underlying Portal
infrastructure already handles it.  This in turn allows these statements
to be used in some existing plpgsql and plperl contexts, such as a
plpgsql FOR loop.  Also, do some marginal code cleanup in places that
were being sloppy about distinguishing SELECT from SELECT INTO.

plpgsql support to come later.  Along the way, convert execMain's
SELECT INTO support into a DestReceiver, in order to eliminate some ugly
special cases.

Jonah Harris and Tom Lane

same data type and same typmod, we show that typmod as the output
typmod, rather than generic -1.  This responds to several complaints
over the past few years about UNIONs unexpectedly dropping length or
precision info.

support both FOR UPDATE and FOR SHARE in one command, as well as both
NOWAIT and normal WAIT behavior.  The more general code is actually
simpler and cleaner.