WIP patch for parameterized inner paths - Mailing list pgsql-hackers

Well, since I see other committers sending in patches the day after the
nominal commitfest deadline, I don't feel too bad about being a bit late
as well.  Attached is a WIP patch for parameterized paths, along the
lines we have discussed before:
http://archives.postgresql.org/pgsql-hackers/2009-10/msg00994.php
http://archives.postgresql.org/pgsql-hackers/2011-05/msg01136.php
http://archives.postgresql.org/pgsql-hackers/2011-11/msg00543.php

While this is far from complete, it's sufficient to fix the example
that Andres Freund gave here:
http://archives.postgresql.org/pgsql-hackers/2010-05/msg00889.php
For reference, 8.3 and earlier produced a plan like this for Andres'
example:

 Index Scan using c_value_key on c  (cost=0.00..24.83 rows=1 width=0)
   Index Cond: (value = 1)
   Filter: (subplan)
   SubPlan
     ->  Nested Loop  (cost=0.00..16.56 rows=1 width=12)
           ->  Index Scan using b__c_id on b  (cost=0.00..8.27 rows=1 width=8)
                 Index Cond: (c_id = $0)
           ->  Index Scan using a__b_id on a  (cost=0.00..8.27 rows=1 width=8)
                 Index Cond: (a.b_id = b.b_id)

8.4 through 9.1 produce something like this:

 Nested Loop Semi Join  (cost=1543.00..4486.27 rows=1 width=0)
   Join Filter: (c.c_id = b.c_id)
   ->  Index Scan using c_value_key on c  (cost=0.00..8.27 rows=1 width=4)
         Index Cond: (value = 1)
   ->  Hash Join  (cost=1543.00..3853.00 rows=50000 width=4)
         Hash Cond: (a.b_id = b.b_id)
         ->  Seq Scan on a  (cost=0.00..722.00 rows=50000 width=4)
         ->  Hash  (cost=722.00..722.00 rows=50000 width=8)
               ->  Seq Scan on b  (cost=0.00..722.00 rows=50000 width=8)

which is just as bad as the cost estimate makes it look.  With this
patch, HEAD produces:

 Nested Loop Semi Join  (cost=0.00..24.84 rows=1 width=0)
   ->  Index Scan using c_value_key on c  (cost=0.00..8.27 rows=1 width=4)
         Index Cond: (value = 1)
   ->  Nested Loop  (cost=0.00..16.56 rows=1 width=4)
         ->  Index Scan using b__c_id on b  (cost=0.00..8.27 rows=1 width=8)
               Index Cond: (c_id = c.c_id)
         ->  Index Only Scan using a__b_id on a  (cost=0.00..8.27 rows=1 width=4
)
               Index Cond: (b_id = b.b_id)

which is effectively the same thing as 8.3's plan, although now the idea
that it's a semijoin is explicit.

Although this patch gets the infrastructure in place, there is a lot
left to do, notably:

* Initial generation of parameterized indexpaths in indxpath.c is quite
stupid.  To minimize the patch footprint, I left alone as much as I could
of the existing structure in that file whereby indexable join clauses are
selected if they match a specific target outer relation.  I think that
that logic needs to be torn apart and instead drive the process by
considering all clauses matching a specific index; which is going to mean
considerable refactoring, but it'll be localized within indxpath.c.

* joinpath.c doesn't yet consider parameterized input paths for
hash and merge joins.  This means that in the above example, the
lower-level join can *only* be done as a nestloop; which is okay for the
numbers of rows in this example, but there's a range of rowcounts where
we'd like to have something smarter at that join step.  The trick here is
mainly to not consider an unreasonably large number of possible plans.

* The whole thing needs performance testing to see if or how much slower
it makes the planner.  I'm not sure that there's much point in that until
the code is less bogus around the above two areas; although if it's really
horridly slower as-is on any complex queries, we've got a problem.

* There are several places where we intentionally lobotomized subquery
pullup to prevent the worst cases of 8.3-to-8.4 plan regressions as a
result of being unable to pass parameters through intermediate joins.
Probably that could get undone now, but I need to do some testing with
the example cases that persuaded us to put those hacks in.

* I think it should now be a fairly localized matter to support nestloop
joins with inner TID scans, which is a capability that's been requested
more than once, even though the use-cases aren't real wide.

* There's assorted now-dead code that I've not bothered to remove yet,
and the costsize.c APIs could stand some more refactoring.  This is
just in the nature of cleanup so I left it for a separate patch.

Anyway, I'm hoping to keep hacking at this for a couple more days before
the CF gets into full swing, and hopefully arrive at something committable
for 9.2.  I'd really like to get this fixed in this cycle, since it's
been a problem for several releases now.

Comments?

            regards, tom lane


diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml
index 07c816c38f279b057eab32d7f4b9eb06f7b193d4..28f2ae162753e105fffc24b922881eae39da60c5 100644
*** a/doc/src/sgml/indexam.sgml
--- b/doc/src/sgml/indexam.sgml
*************** amcanreturn (Relation indexRelation);
*** 289,295 ****
  void
  amcostestimate (PlannerInfo *root,
                  IndexPath *path,
!                 RelOptInfo *outer_rel,
                  Cost *indexStartupCost,
                  Cost *indexTotalCost,
                  Selectivity *indexSelectivity,
--- 289,295 ----
  void
  amcostestimate (PlannerInfo *root,
                  IndexPath *path,
!                 double loop_count,
                  Cost *indexStartupCost,
                  Cost *indexTotalCost,
                  Selectivity *indexSelectivity,
*************** amrestrpos (IndexScanDesc scan);
*** 928,934 ****
  void
  amcostestimate (PlannerInfo *root,
                  IndexPath *path,
!                 RelOptInfo *outer_rel,
                  Cost *indexStartupCost,
                  Cost *indexTotalCost,
                  Selectivity *indexSelectivity,
--- 928,934 ----
  void
  amcostestimate (PlannerInfo *root,
                  IndexPath *path,
!                 double loop_count,
                  Cost *indexStartupCost,
                  Cost *indexTotalCost,
                  Selectivity *indexSelectivity,
*************** amcostestimate (PlannerInfo *root,
*** 958,973 ****
      </varlistentry>

      <varlistentry>
!      <term><parameter>outer_rel</></term>
       <listitem>
        <para>
!        If the index is being considered for use in a join inner indexscan,
!        the planner's information about the outer side of the join.  Otherwise
!        <symbol>NULL</>.  When non-<symbol>NULL</>, some of the qual clauses
!        will be join clauses for joins
!        with this rel rather than being simple restriction clauses.  Also,
!        the cost estimator should expect that the index scan will be repeated
!        for each row of the outer rel.
        </para>
       </listitem>
      </varlistentry>
--- 958,972 ----
      </varlistentry>

      <varlistentry>
!      <term><parameter>loop_count</></term>
       <listitem>
        <para>
!        The number of repetitions of the index scan that should be factored
!        into the cost estimates.  This will typically be greater than one when
!        considering a parameterized scan for use in the inside of a nestloop
!        join.  Note that the cost estimates should still be for just one scan;
!        a larger <parameter>loop_count</> means that it may be appropriate
!        to allow for some caching effects across multiple scans.
        </para>
       </listitem>
      </varlistentry>
*************** amcostestimate (PlannerInfo *root,
*** 1062,1069 ****
    </para>

    <para>
!    In the join case, the returned numbers should be averages expected for
!    any one scan of the index.
    </para>

    <procedure>
--- 1061,1068 ----
    </para>

    <para>
!    When <parameter>loop_count</> is greater than one, the returned numbers
!    should be averages expected for any one scan of the index.
    </para>

    <procedure>
*************** cost_qual_eval(&index_qual_cost, pat
*** 1121,1127 ****
  </programlisting>

       However, the above does not account for amortization of index reads
!      across repeated index scans in the join case.
      </para>
     </step>

--- 1120,1126 ----
  </programlisting>

       However, the above does not account for amortization of index reads
!      across repeated index scans.
      </para>
     </step>

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 3b5fb20964e7153a859bb639f15fd0be8bb8778b..4c904e03296051cf2c95fdcd3d4a029aea9dc142 100644
*** a/src/backend/nodes/bitmapset.c
--- b/src/backend/nodes/bitmapset.c
*************** bms_is_subset(const Bitmapset *a, const
*** 336,341 ****
--- 336,418 ----
  }

  /*
+  * bms_subset_compare - compare A and B for equality/subset relationships
+  *
+  * This is more efficient than testing bms_is_subset in both directions.
+  */
+ BMS_Comparison
+ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
+ {
+     BMS_Comparison result;
+     int            shortlen;
+     int            longlen;
+     int            i;
+
+     /* Handle cases where either input is NULL */
+     if (a == NULL)
+     {
+         if (b == NULL)
+             return BMS_EQUAL;
+         return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
+     }
+     if (b == NULL)
+         return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
+     /* Check common words */
+     result = BMS_EQUAL;            /* status so far */
+     shortlen = Min(a->nwords, b->nwords);
+     for (i = 0; i < shortlen; i++)
+     {
+         bitmapword aword = a->words[i];
+         bitmapword bword = b->words[i];
+
+         if ((aword & ~bword) != 0)
+         {
+             /* a is not a subset of b */
+             if (result == BMS_SUBSET1)
+                 return BMS_DIFFERENT;
+             result = BMS_SUBSET2;
+         }
+         if ((bword & ~aword) != 0)
+         {
+             /* b is not a subset of a */
+             if (result == BMS_SUBSET2)
+                 return BMS_DIFFERENT;
+             result = BMS_SUBSET1;
+         }
+     }
+     /* Check extra words */
+     if (a->nwords > b->nwords)
+     {
+         longlen = a->nwords;
+         for (; i < longlen; i++)
+         {
+             if (a->words[i] != 0)
+             {
+                 /* a is not a subset of b */
+                 if (result == BMS_SUBSET1)
+                     return BMS_DIFFERENT;
+                 result = BMS_SUBSET2;
+             }
+         }
+     }
+     else if (a->nwords < b->nwords)
+     {
+         longlen = b->nwords;
+         for (; i < longlen; i++)
+         {
+             if (b->words[i] != 0)
+             {
+                 /* b is not a subset of a */
+                 if (result == BMS_SUBSET2)
+                     return BMS_DIFFERENT;
+                 result = BMS_SUBSET1;
+             }
+         }
+     }
+     return result;
+ }
+
+ /*
   * bms_is_member - is X a member of A?
   */
  bool
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 8bc19478357e66d3fe8723da693672939c401ae2..3df2d1e23b4cda966c9bd74c116ebb830291a172 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPathInfo(StringInfo str, const Path
*** 1475,1483 ****
      WRITE_ENUM_FIELD(pathtype, NodeTag);
      appendStringInfo(str, " :parent_relids ");
      _outBitmapset(str, node->parent->relids);
      WRITE_FLOAT_FIELD(startup_cost, "%.2f");
      WRITE_FLOAT_FIELD(total_cost, "%.2f");
-     WRITE_NODE_FIELD(pathkeys);
  }

  /*
--- 1475,1486 ----
      WRITE_ENUM_FIELD(pathtype, NodeTag);
      appendStringInfo(str, " :parent_relids ");
      _outBitmapset(str, node->parent->relids);
+     WRITE_BITMAPSET_FIELD(required_outer);
+     WRITE_NODE_FIELD(param_clauses);
+     WRITE_NODE_FIELD(pathkeys);
+     WRITE_FLOAT_FIELD(rows, "%.0f");
      WRITE_FLOAT_FIELD(startup_cost, "%.2f");
      WRITE_FLOAT_FIELD(total_cost, "%.2f");
  }

  /*
*************** _outIndexPath(StringInfo str, const Inde
*** 1515,1525 ****
      WRITE_NODE_FIELD(indexqualcols);
      WRITE_NODE_FIELD(indexorderbys);
      WRITE_NODE_FIELD(indexorderbycols);
-     WRITE_BOOL_FIELD(isjoininner);
      WRITE_ENUM_FIELD(indexscandir, ScanDirection);
      WRITE_FLOAT_FIELD(indextotalcost, "%.2f");
      WRITE_FLOAT_FIELD(indexselectivity, "%.4f");
-     WRITE_FLOAT_FIELD(rows, "%.0f");
  }

  static void
--- 1518,1526 ----
*************** _outBitmapHeapPath(StringInfo str, const
*** 1530,1537 ****
      _outPathInfo(str, (const Path *) node);

      WRITE_NODE_FIELD(bitmapqual);
-     WRITE_BOOL_FIELD(isjoininner);
-     WRITE_FLOAT_FIELD(rows, "%.0f");
  }

  static void
--- 1531,1536 ----
*************** _outUniquePath(StringInfo str, const Uni
*** 1628,1634 ****
      WRITE_ENUM_FIELD(umethod, UniquePathMethod);
      WRITE_NODE_FIELD(in_operators);
      WRITE_NODE_FIELD(uniq_exprs);
-     WRITE_FLOAT_FIELD(rows, "%.0f");
  }

  static void
--- 1627,1632 ----
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index aaa754cbb18e78823135bbc4a1acfbaa1f93c88f..15d631c1f8059756ecc6f3857759af1ac6b6e685 100644
*** a/src/backend/optimizer/README
--- b/src/backend/optimizer/README
*************** ways.  All the Paths made for a given re
*** 78,87 ****
  RelOptInfo.pathlist.  (Actually, we discard Paths that are obviously
  inferior alternatives before they ever get into the pathlist --- what
  ends up in the pathlist is the cheapest way of generating each potentially
! useful sort ordering of the relation.)  Also create a RelOptInfo.joininfo
! list including all the join clauses that involve this relation.  For
! example, the WHERE clause "tab1.col1 = tab2.col1" generates entries in
! both tab1 and tab2's joininfo lists.

  If we have only a single base relation in the query, we are done.
  Otherwise we have to figure out how to join the base relations into a
--- 78,87 ----
  RelOptInfo.pathlist.  (Actually, we discard Paths that are obviously
  inferior alternatives before they ever get into the pathlist --- what
  ends up in the pathlist is the cheapest way of generating each potentially
! useful sort ordering and parameterization of the relation.)  Also create a
! RelOptInfo.joininfo list including all the join clauses that involve this
! relation.  For example, the WHERE clause "tab1.col1 = tab2.col1" generates
! entries in both tab1 and tab2's joininfo lists.

  If we have only a single base relation in the query, we are done.
  Otherwise we have to figure out how to join the base relations into a
*************** for it or the cheapest path with the des
*** 173,184 ****
  than applying a sort to the cheapest other path).

  If the query contains one-sided outer joins (LEFT or RIGHT joins), or
! IN or EXISTS WHERE clauses that were converted to joins, then some of
! the possible join orders may be illegal.  These are excluded by having
! join_is_legal consult a side list of such "special" joins to see
! whether a proposed join is illegal.  (The same consultation allows it
! to see which join style should be applied for a valid join, ie,
! JOIN_INNER, JOIN_LEFT, etc.)


  Valid OUTER JOIN Optimizations
--- 173,184 ----
  than applying a sort to the cheapest other path).

  If the query contains one-sided outer joins (LEFT or RIGHT joins), or
! IN or EXISTS WHERE clauses that were converted to semijoins or antijoins,
! then some of the possible join orders may be illegal.  These are excluded
! by having join_is_legal consult a side list of such "special" joins to see
! whether a proposed join is illegal.  (The same consultation allows it to
! see which join style should be applied for a valid join, ie, JOIN_INNER,
! JOIN_LEFT, etc.)


  Valid OUTER JOIN Optimizations
*************** multi-column index generates a list with
*** 526,537 ****
  are two possible sort orders and two possible PathKey lists it can
  generate.)

! Note that a bitmap scan or multi-pass indexscan (OR clause scan) has NIL
! pathkeys since we can say nothing about the overall order of its result.
! Also, an indexscan on an unordered type of index generates NIL pathkeys.
! However, we can always create a pathkey by doing an explicit sort.  The
! pathkeys for a Sort plan's output just represent the sort key fields and
! the ordering operators used.

  Things get more interesting when we consider joins.  Suppose we do a
  mergejoin between A and B using the mergeclause A.X = B.Y.  The output
--- 526,536 ----
  are two possible sort orders and two possible PathKey lists it can
  generate.)

! Note that a bitmap scan has NIL pathkeys since we can say nothing about
! the overall order of its result.  Also, an indexscan on an unordered type
! of index generates NIL pathkeys.  However, we can always create a pathkey
! by doing an explicit sort.  The pathkeys for a Sort plan's output just
! represent the sort key fields and the ordering operators used.

  Things get more interesting when we consider joins.  Suppose we do a
  mergejoin between A and B using the mergeclause A.X = B.Y.  The output
*************** Currently this happens only for queries
*** 668,671 ****
--- 667,753 ----
  with different orderings, for which extra sorts are needed anyway.


+ Parameterized Paths
+ -------------------
+
+ The naive way to join two relations using a clause like WHERE A.X = B.Y
+ is to generate a nestloop plan like this:
+
+     NestLoop
+         Filter: A.X = B.Y
+         -> Seq Scan on A
+         -> Seq Scan on B
+
+ We can make this better by using a merge or hash join, but it still
+ requires scanning all of both input relations.  If A is very small and B is
+ very large, but there is an index on B.Y, it can be enormously better to do
+ something like this:
+
+     NestLoop
+         -> Seq Scan on A
+         -> Index Scan using B_Y_IDX on B
+             Index Condition: B.Y = A.X
+
+ Here, we are expecting that for each row scanned from A, the nestloop
+ plan node will pass down the current value of A.X into the scan of B.
+ That allows the indexscan to treat A.X as a constant for any one
+ invocation, and thereby use it as an index key.  This is the only plan type
+ that can avoid fetching all of B, and for small numbers of rows coming from
+ A, that will dominate every other consideration.  (As A gets larger, this
+ gets less attractive, and eventually a merge or hash join will win instead.
+ So we have to cost out all the alternatives to decide what to do.)
+
+ It can be useful for the parameter value to be passed down through
+ intermediate layers of joins, for example:
+
+     NestLoop
+         -> Seq Scan on A
+         Hash Join
+             Join Condition: B.Y = C.W
+             -> Seq Scan on B
+             -> Index Scan using C_Z_IDX on C
+                 Index Condition: C.Z = A.X
+
+ If all joins are plain inner joins then this is unnecessary, because
+ it's always possible to reorder the joins so that a parameter is used
+ immediately below the nestloop node that provides it.  But in the
+ presence of outer joins, join reordering may not be possible, and then
+ this option can be critical.  Before version 9.2, Postgres used ad-hoc
+ methods for planning and executing such queries, and those methods could
+ not handle passing parameters down through multiple join levels.
+
+ To plan such queries, we now use a notion of a "parameterized path",
+ which is a path that makes use of a join clause to a relation that's not
+ scanned by the path.  In the example just above, we would construct a
+ path representing the possibility of doing this:
+
+     -> Index Scan using C_Z_IDX on C
+         Index Condition: C.Z = A.X
+
+ This path will be marked as being parameterized by relation A.  (Note that
+ this is only one of the possible access paths for C; we'd still have a
+ plain unparameterized seqscan, and perhaps other possibilities.)  The
+ parameterization marker does not prevent joining the path to B, so one of
+ the paths generated for the joinrel {B C} will represent
+
+     Hash Join
+         Join Condition: B.Y = C.W
+         -> Seq Scan on B
+         -> Index Scan using C_Z_IDX on C
+             Index Condition: C.Z = A.X
+
+ This path is still marked as being parameterized by A.  When we attempt to
+ join {B C} to A to form the complete join tree, such a path can only be
+ used as the inner side of a nestloop join: it will be ignored for other
+ possible join types.  So we will form a join path representing the query
+ plan shown above, and it will compete in the usual way with paths built
+ from non-parameterized scans.
+
+ To limit planning time, we have to avoid generating an unreasonably large
+ number of parameterized paths.  We do this by only generating parameterized
+ relation scan paths for index scans, and then only for indexes for which
+ suitable join clauses are available.  There are also heuristics in join
+ planning that try to limit the number of parameterized paths considered.
+
+
  -- bjm & tgl
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b085553a1adbfee633ae6399cf6e188ec465368a..df768f6bcb9abd4fe36a3ab856dac4c189326865 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** static void set_plain_rel_pathlist(Plann
*** 53,58 ****
--- 53,62 ----
                         RangeTblEntry *rte);
  static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
                          Index rti, RangeTblEntry *rte);
+ static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
+                            List *live_childrels,
+                            List *all_child_pathkeys,
+                            Relids required_outer);
  static List *accumulate_append_subpath(List *subpaths, Path *path);
  static void set_dummy_rel_pathlist(RelOptInfo *rel);
  static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 300,305 ****
--- 304,310 ----
      List       *live_childrels = NIL;
      List       *subpaths = NIL;
      List       *all_child_pathkeys = NIL;
+     List       *all_child_outers = NIL;
      double        parent_rows;
      double        parent_size;
      double       *parent_attrsizes;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 326,333 ****
      parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));

      /*
!      * Generate access paths for each member relation, and pick the cheapest
!      * path for each one.
       */
      foreach(l, root->append_rel_list)
      {
--- 331,340 ----
      parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));

      /*
!      * Generate access paths for each member relation, and remember the
!      * cheapest path for each one.  Also, identify all pathkeys (orderings)
!      * and parameterizations (required_outer sets) available for the member
!      * relations.
       */
      foreach(l, root->append_rel_list)
      {
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 394,401 ****
          {
              /*
               * This child need not be scanned, so we can omit it from the
!              * appendrel.  Mark it with a dummy cheapest-path though, in case
!              * best_appendrel_indexscan() looks at it later.
               */
              set_dummy_rel_pathlist(childrel);
              continue;
--- 401,408 ----
          {
              /*
               * This child need not be scanned, so we can omit it from the
!              * appendrel.  Mark it with a dummy cheapest-path though, for
!              * safety.
               */
              set_dummy_rel_pathlist(childrel);
              continue;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 457,497 ****
          subpaths = accumulate_append_subpath(subpaths,
                                               childrel->cheapest_total_path);

!         /* Remember which childrels are live, for MergeAppend logic below */
          live_childrels = lappend(live_childrels, childrel);

          /*
!          * Collect a list of all the available path orderings for all the
!          * children.  We use this as a heuristic to indicate which sort
!          * orderings we should build MergeAppend paths for.
           */
          foreach(lcp, childrel->pathlist)
          {
              Path       *childpath = (Path *) lfirst(lcp);
              List       *childkeys = childpath->pathkeys;
!             ListCell   *lpk;
!             bool        found = false;
!
!             /* Ignore unsorted paths */
!             if (childkeys == NIL)
!                 continue;

!             /* Have we already seen this ordering? */
!             foreach(lpk, all_child_pathkeys)
              {
!                 List       *existing_pathkeys = (List *) lfirst(lpk);

!                 if (compare_pathkeys(existing_pathkeys,
!                                      childkeys) == PATHKEYS_EQUAL)
                  {
!                     found = true;
!                     break;
                  }
              }
!             if (!found)
              {
!                 /* No, so add it to all_child_pathkeys */
!                 all_child_pathkeys = lappend(all_child_pathkeys, childkeys);
              }
          }

--- 464,534 ----
          subpaths = accumulate_append_subpath(subpaths,
                                               childrel->cheapest_total_path);

!         /* Remember which childrels are live, for logic below */
          live_childrels = lappend(live_childrels, childrel);

          /*
!          * Collect lists of all the available path orderings and
!          * parameterizations for all the children.  We use these as a
!          * heuristic to indicate which sort orderings and parameterizations we
!          * should build Append and MergeAppend paths for.
           */
          foreach(lcp, childrel->pathlist)
          {
              Path       *childpath = (Path *) lfirst(lcp);
              List       *childkeys = childpath->pathkeys;
!             Relids        childouter = childpath->required_outer;

!             /* Unsorted paths don't contribute to pathkey list */
!             if (childkeys != NIL)
              {
!                 ListCell   *lpk;
!                 bool        found = false;

!                 /* Have we already seen this ordering? */
!                 foreach(lpk, all_child_pathkeys)
                  {
!                     List       *existing_pathkeys = (List *) lfirst(lpk);
!
!                     if (compare_pathkeys(existing_pathkeys,
!                                          childkeys) == PATHKEYS_EQUAL)
!                     {
!                         found = true;
!                         break;
!                     }
!                 }
!                 if (!found)
!                 {
!                     /* No, so add it to all_child_pathkeys */
!                     all_child_pathkeys = lappend(all_child_pathkeys,
!                                                  childkeys);
                  }
              }
!
!             /* Unparameterized paths don't contribute to param-set list */
!             /* XXX should fix indxpath,c to avoid bogus paths */
!             if (childouter && !bms_is_member(rel->relid, childouter))
              {
!                 ListCell   *lco;
!                 bool        found = false;
!
!                 /* Have we already seen this param set? */
!                 foreach(lco, all_child_outers)
!                 {
!                     Relids    existing_outers = (Relids) lfirst(lco);
!
!                     if (bms_equal(existing_outers, childouter))
!                     {
!                         found = true;
!                         break;
!                     }
!                 }
!                 if (!found)
!                 {
!                     /* No, so add it to all_child_outers */
!                     all_child_outers = lappend(all_child_outers,
!                                                childouter);
!                 }
              }
          }

*************** set_append_rel_pathlist(PlannerInfo *roo
*** 562,583 ****
      pfree(parent_attrsizes);

      /*
!      * Next, build an unordered Append path for the rel.  (Note: this is
!      * correct even if we have zero or one live subpath due to constraint
!      * exclusion.)
       */
      add_path(rel, (Path *) create_append_path(rel, subpaths));

      /*
!      * Next, build MergeAppend paths based on the collected list of child
!      * pathkeys.  We consider both cheapest-startup and cheapest-total cases,
!      * ie, for each interesting ordering, collect all the cheapest startup
!      * subpaths and all the cheapest total paths, and build a MergeAppend path
!      * for each list.
       */
!     foreach(l, all_child_pathkeys)
      {
!         List       *pathkeys = (List *) lfirst(l);
          List       *startup_subpaths = NIL;
          List       *total_subpaths = NIL;
          bool        startup_neq_total = false;
--- 599,679 ----
      pfree(parent_attrsizes);

      /*
!      * Next, build an unordered, unparameterized Append path for the rel.
!      * (Note: this is correct even if we have zero or one live subpath due to
!      * constraint exclusion.)
       */
      add_path(rel, (Path *) create_append_path(rel, subpaths));

      /*
!      * Build unparameterized MergeAppend paths based on the collected list of
!      * child pathkeys.
       */
!     generate_mergeappend_paths(root, rel, live_childrels,
!                                all_child_pathkeys, NULL);
!
!     /*
!      * Build Append and MergeAppend paths for each parameterization seen
!      * among the child rels.  (This may look pretty expensive, but in most
!      * cases of practical interest, the child relations will tend to expose
!      * the same parameterizations and pathkeys, so that not that many cases
!      * actually get considered here.)
!      */
!     foreach(l, all_child_outers)
      {
!         Relids    required_outer = (Relids) lfirst(l);
!         ListCell   *lcr;
!
!         /* Select the child paths for an Append with this parameterization */
!         subpaths = NIL;
!         foreach(lcr, live_childrels)
!         {
!             RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
!             Path       *cheapest_total;
!
!             cheapest_total =
!                 get_cheapest_path_for_pathkeys(childrel->pathlist,
!                                                NIL,
!                                                required_outer,
!                                                TOTAL_COST);
!             Assert(cheapest_total != NULL);
!
!             subpaths = accumulate_append_subpath(subpaths, cheapest_total);
!         }
!         add_path(rel, (Path *) create_append_path(rel, subpaths));
!
!         /* And build parameterized MergeAppend paths */
!         generate_mergeappend_paths(root, rel, live_childrels,
!                                    all_child_pathkeys, required_outer);
!     }
!
!     /* Select cheapest paths */
!     set_cheapest(rel);
! }
!
! /*
!  * generate_mergeappend_paths
!  *        Generate MergeAppend paths for an append relation
!  *
!  * Generate a path for each ordering (pathkey list) appearing in
!  * all_child_pathkeys.  If required_outer isn't NULL, accept paths having
!  * those relations as required outer relations.
!  *
!  * We consider both cheapest-startup and cheapest-total cases, ie, for each
!  * interesting ordering, collect all the cheapest startup subpaths and all the
!  * cheapest total paths, and build a MergeAppend path for each case.
!  */
! static void
! generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
!                            List *live_childrels,
!                            List *all_child_pathkeys,
!                            Relids required_outer)
! {
!     ListCell   *lcp;
!
!     foreach(lcp, all_child_pathkeys)
!     {
!         List       *pathkeys = (List *) lfirst(lcp);
          List       *startup_subpaths = NIL;
          List       *total_subpaths = NIL;
          bool        startup_neq_total = false;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 594,608 ****
              cheapest_startup =
                  get_cheapest_path_for_pathkeys(childrel->pathlist,
                                                 pathkeys,
                                                 STARTUP_COST);
              cheapest_total =
                  get_cheapest_path_for_pathkeys(childrel->pathlist,
                                                 pathkeys,
                                                 TOTAL_COST);

              /*
               * If we can't find any paths with the right order just add the
!              * cheapest-total path; we'll have to sort it.
               */
              if (cheapest_startup == NULL)
                  cheapest_startup = childrel->cheapest_total_path;
--- 690,707 ----
              cheapest_startup =
                  get_cheapest_path_for_pathkeys(childrel->pathlist,
                                                 pathkeys,
+                                                required_outer,
                                                 STARTUP_COST);
              cheapest_total =
                  get_cheapest_path_for_pathkeys(childrel->pathlist,
                                                 pathkeys,
+                                                required_outer,
                                                 TOTAL_COST);

              /*
               * If we can't find any paths with the right order just add the
!              * cheapest-total path; we'll have to sort it.  XXX should use
!              * cheapest path for required_outer.
               */
              if (cheapest_startup == NULL)
                  cheapest_startup = childrel->cheapest_total_path;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 634,642 ****
                                                              total_subpaths,
                                                              pathkeys));
      }
-
-     /* Select cheapest path */
-     set_cheapest(rel);
  }

  /*
--- 733,738 ----
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e1c070ea92c625ffa9593d26dbab369dcd566b55..e51faac9a91609e89b2a0e1680fc62b3f4f57b50 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
***************
*** 40,46 ****
   * path's result.  A caller can estimate the cost of fetching a partial
   * result by interpolating between startup_cost and total_cost.  In detail:
   *        actual_cost = startup_cost +
!  *            (total_cost - startup_cost) * tuples_to_fetch / path->parent->rows;
   * Note that a base relation's rows count (and, by extension, plan_rows for
   * plan nodes below the LIMIT node) are set without regard to any LIMIT, so
   * that this equation works properly.  (Also, these routines guarantee not to
--- 40,46 ----
   * path's result.  A caller can estimate the cost of fetching a partial
   * result by interpolating between startup_cost and total_cost.  In detail:
   *        actual_cost = startup_cost +
!  *            (total_cost - startup_cost) * tuples_to_fetch / path->rows;
   * Note that a base relation's rows count (and, by extension, plan_rows for
   * plan nodes below the LIMIT node) are set without regard to any LIMIT, so
   * that this equation works properly.  (Also, these routines guarantee not to
***************
*** 48,58 ****
   * applied as a top-level plan node.
   *
   * For largely historical reasons, most of the routines in this module use
!  * the passed result Path only to store their startup_cost and total_cost
!  * results into.  All the input data they need is passed as separate
   * parameters, even though much of it could be extracted from the Path.
   * An exception is made for the cost_XXXjoin() routines, which expect all
!  * the non-cost fields of the passed XXXPath to be filled in, and similarly
   * cost_index() assumes the passed IndexPath is valid except for its output
   * values.
   *
--- 48,58 ----
   * applied as a top-level plan node.
   *
   * For largely historical reasons, most of the routines in this module use
!  * the passed result Path only to store their results (rows, startup_cost and
!  * total_cost) into.  All the input data they need is passed as separate
   * parameters, even though much of it could be extracted from the Path.
   * An exception is made for the cost_XXXjoin() routines, which expect all
!  * the other fields of the passed XXXPath to be filled in, and similarly
   * cost_index() assumes the passed IndexPath is valid except for its output
   * values.
   *
***************
*** 90,104 ****

  #define LOG2(x)  (log(x) / 0.693147180559945)

- /*
-  * Some Paths return less than the nominal number of rows of their parent
-  * relations; join nodes need to do this to get the correct input count:
-  */
- #define PATH_ROWS(path) \
-     (IsA(path, UniquePath) ? \
-      ((UniquePath *) (path))->rows : \
-      (path)->parent->rows)
-

  double        seq_page_cost = DEFAULT_SEQ_PAGE_COST;
  double        random_page_cost = DEFAULT_RANDOM_PAGE_COST;
--- 90,95 ----
*************** static bool adjust_semi_join(PlannerInfo
*** 141,146 ****
--- 132,145 ----
                   bool *indexed_join_quals);
  static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
                     List *quals);
+ static void set_joinpath_size_estimate(PlannerInfo *root, JoinPath *path,
+                            SpecialJoinInfo *sjinfo,
+                            List *restrictlist);
+ static double calc_joinrel_size_estimate(PlannerInfo *root,
+                            double outer_rows,
+                            double inner_rows,
+                            SpecialJoinInfo *sjinfo,
+                            List *restrictlist);
  static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
  static double relation_byte_size(double tuples, int width);
  static double page_size(double tuples, int width);
*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 184,189 ****
--- 183,191 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_RELATION);

+     /* For now, at least, seqscans are never parameterized */
+     path->rows = baserel->rows;
+
      if (!enable_seqscan)
          startup_cost += disable_cost;

*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 212,225 ****
   *
   * 'path' describes the indexscan under consideration, and is complete
   *        except for the fields to be set by this routine
!  * 'outer_rel' is the outer relation when we are considering using the index
!  *        scan as the inside of a nestloop join (hence, some of the indexquals
!  *        are join clauses, and we should expect repeated scans of the index);
!  *        NULL for a plain index scan
   *
!  * In addition to startup_cost and total_cost, cost_index() sets the path's
!  * indextotalcost and indexselectivity fields.  These values are needed if
!  * the IndexPath is used in a BitmapIndexScan.
   *
   * NOTE: path->indexquals must contain only clauses usable as index
   * restrictions.  Any additional quals evaluated as qpquals may reduce the
--- 214,225 ----
   *
   * 'path' describes the indexscan under consideration, and is complete
   *        except for the fields to be set by this routine
!  * 'loop_count' is the number of repetitions of the indexscan to factor into
!  *        estimates of caching behavior
   *
!  * In addition to rows, startup_cost and total_cost, cost_index() sets the
!  * path's indextotalcost and indexselectivity fields.  These values will be
!  * needed if the IndexPath is used in a BitmapIndexScan.
   *
   * NOTE: path->indexquals must contain only clauses usable as index
   * restrictions.  Any additional quals evaluated as qpquals may reduce the
*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 227,233 ****
   * we have to fetch from the table, so they don't reduce the scan cost.
   */
  void
! cost_index(IndexPath *path, PlannerInfo *root, RelOptInfo *outer_rel)
  {
      IndexOptInfo *index = path->indexinfo;
      RelOptInfo *baserel = index->rel;
--- 227,233 ----
   * we have to fetch from the table, so they don't reduce the scan cost.
   */
  void
! cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
  {
      IndexOptInfo *index = path->indexinfo;
      RelOptInfo *baserel = index->rel;
*************** cost_index(IndexPath *path, PlannerInfo
*** 253,258 ****
--- 253,299 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_RELATION);

+     /* Estimate the number of rows returned by the indexscan */
+     if (path->path.required_outer)
+     {
+         /*
+          * The estimate should be less than baserel->rows because of the
+          * additional selectivity of the join clauses.  Since indexclauses may
+          * contain both restriction and join clauses, we have to do a set
+          * union to get the full set of clauses that must be considered to
+          * compute the correct selectivity.  (Without the union operation, we
+          * might have some restriction clauses appearing twice, which'd
+          * mislead clauselist_selectivity into double-counting their
+          * selectivity.  However, since RestrictInfo nodes aren't copied when
+          * linking them into different lists, it should be sufficient to use
+          * pointer comparison to remove duplicates.)
+          *
+          * Note that we force the clauses to be treated as non-join clauses
+          * during selectivity estimation.
+          */
+         List       *allclauses;
+
+         allclauses = list_union_ptr(baserel->baserestrictinfo,
+                                     path->indexclauses);
+         path->path.rows = baserel->tuples *
+             clauselist_selectivity(root,
+                                    allclauses,
+                                    baserel->relid,    /* do not use 0! */
+                                    JOIN_INNER,
+                                    NULL);
+         if (path->path.rows > baserel->rows)
+             path->path.rows = baserel->rows;
+         path->path.rows = clamp_row_est(path->path.rows);
+     }
+     else
+     {
+         /*
+          * The number of rows is the same as the parent rel's estimate, since
+          * this isn't a parameterized path.
+          */
+         path->path.rows = baserel->rows;
+     }
+
      if (!enable_indexscan)
          startup_cost += disable_cost;
      /* we don't need to check enable_indexonlyscan; indxpath.c does that */
*************** cost_index(IndexPath *path, PlannerInfo
*** 266,272 ****
      OidFunctionCall7(index->amcostestimate,
                       PointerGetDatum(root),
                       PointerGetDatum(path),
!                      PointerGetDatum(outer_rel),
                       PointerGetDatum(&indexStartupCost),
                       PointerGetDatum(&indexTotalCost),
                       PointerGetDatum(&indexSelectivity),
--- 307,313 ----
      OidFunctionCall7(index->amcostestimate,
                       PointerGetDatum(root),
                       PointerGetDatum(path),
!                      Float8GetDatum(loop_count),
                       PointerGetDatum(&indexStartupCost),
                       PointerGetDatum(&indexTotalCost),
                       PointerGetDatum(&indexSelectivity),
*************** cost_index(IndexPath *path, PlannerInfo
*** 319,325 ****
       * that this query will fetch; but it's not clear how to do better.
       *----------
       */
!     if (outer_rel != NULL && outer_rel->rows > 1)
      {
          /*
           * For repeated indexscans, the appropriate estimate for the
--- 360,366 ----
       * that this query will fetch; but it's not clear how to do better.
       *----------
       */
!     if (loop_count > 1)
      {
          /*
           * For repeated indexscans, the appropriate estimate for the
*************** cost_index(IndexPath *path, PlannerInfo
*** 329,337 ****
           * pro-rate the costs for one scan.  In this case we assume all the
           * fetches are random accesses.
           */
!         double        num_scans = outer_rel->rows;
!
!         pages_fetched = index_pages_fetched(tuples_fetched * num_scans,
                                              baserel->pages,
                                              (double) index->pages,
                                              root);
--- 370,376 ----
           * pro-rate the costs for one scan.  In this case we assume all the
           * fetches are random accesses.
           */
!         pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
                                              baserel->pages,
                                              (double) index->pages,
                                              root);
*************** cost_index(IndexPath *path, PlannerInfo
*** 339,345 ****
          if (indexonly)
              pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));

!         max_IO_cost = (pages_fetched * spc_random_page_cost) / num_scans;

          /*
           * In the perfectly correlated case, the number of pages touched by
--- 378,384 ----
          if (indexonly)
              pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));

!         max_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;

          /*
           * In the perfectly correlated case, the number of pages touched by
*************** cost_index(IndexPath *path, PlannerInfo
*** 353,359 ****
           */
          pages_fetched = ceil(indexSelectivity * (double) baserel->pages);

!         pages_fetched = index_pages_fetched(pages_fetched * num_scans,
                                              baserel->pages,
                                              (double) index->pages,
                                              root);
--- 392,398 ----
           */
          pages_fetched = ceil(indexSelectivity * (double) baserel->pages);

!         pages_fetched = index_pages_fetched(pages_fetched * loop_count,
                                              baserel->pages,
                                              (double) index->pages,
                                              root);
*************** cost_index(IndexPath *path, PlannerInfo
*** 361,367 ****
          if (indexonly)
              pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));

!         min_IO_cost = (pages_fetched * spc_random_page_cost) / num_scans;
      }
      else
      {
--- 400,406 ----
          if (indexonly)
              pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));

!         min_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
      }
      else
      {
*************** cost_index(IndexPath *path, PlannerInfo
*** 417,423 ****
      startup_cost += baserel->baserestrictcost.startup;
      cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;

!     if (outer_rel == NULL)
      {
          QualCost    index_qual_cost;

--- 456,462 ----
      startup_cost += baserel->baserestrictcost.startup;
      cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;

!     if (path->path.required_outer == NULL)
      {
          QualCost    index_qual_cost;

*************** get_indexpath_pages(Path *bitmapqual)
*** 578,594 ****
   *
   * 'baserel' is the relation to be scanned
   * 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
!  * 'outer_rel' is the outer relation when we are considering using the bitmap
!  *        scan as the inside of a nestloop join (hence, some of the indexquals
!  *        are join clauses, and we should expect repeated scans of the table);
!  *        NULL for a plain bitmap scan
   *
!  * Note: if this is a join inner path, the component IndexPaths in bitmapqual
!  * should have been costed accordingly.
   */
  void
  cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
!                       Path *bitmapqual, RelOptInfo *outer_rel)
  {
      Cost        startup_cost = 0;
      Cost        run_cost = 0;
--- 617,631 ----
   *
   * 'baserel' is the relation to be scanned
   * 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
!  * 'loop_count' is the number of repetitions of the indexscan to factor into
!  *        estimates of caching behavior
   *
!  * Note: the component IndexPaths in bitmapqual should have been costed
!  * using the same loop_count.
   */
  void
  cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
!                       Path *bitmapqual, double loop_count)
  {
      Cost        startup_cost = 0;
      Cost        run_cost = 0;
*************** cost_bitmap_heap_scan(Path *path, Planne
*** 607,612 ****
--- 644,677 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_RELATION);

+     /* Estimate the number of rows returned by the bitmap scan */
+     if (path->required_outer)
+     {
+         /*
+          * The estimate should be less than baserel->rows because of the
+          * additional selectivity of the join clauses.  We make use of the
+          * selectivity estimated for the bitmap to do this; this isn't really
+          * quite right since there may be restriction conditions not included
+          * in the bitmap ...
+          */
+         Cost        indexTotalCost;
+         Selectivity indexSelectivity;
+
+         cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
+         path->rows = baserel->tuples * indexSelectivity;
+         if (path->rows > baserel->rows)
+             path->rows = baserel->rows;
+         path->rows = clamp_row_est(path->rows);
+     }
+     else
+     {
+         /*
+          * The number of rows is the same as the parent rel's estimate, since
+          * this isn't a parameterized path.
+          */
+         path->rows = baserel->rows;
+     }
+
      if (!enable_bitmapscan)
          startup_cost += disable_cost;

*************** cost_bitmap_heap_scan(Path *path, Planne
*** 630,636 ****

      T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;

!     if (outer_rel != NULL && outer_rel->rows > 1)
      {
          /*
           * For repeated bitmap scans, scale up the number of tuples fetched in
--- 695,701 ----

      T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;

!     if (loop_count > 1)
      {
          /*
           * For repeated bitmap scans, scale up the number of tuples fetched in
*************** cost_bitmap_heap_scan(Path *path, Planne
*** 638,650 ****
           * estimate the number of pages fetched by all the scans. Then
           * pro-rate for one scan.
           */
!         double        num_scans = outer_rel->rows;
!
!         pages_fetched = index_pages_fetched(tuples_fetched * num_scans,
                                              baserel->pages,
                                              get_indexpath_pages(bitmapqual),
                                              root);
!         pages_fetched /= num_scans;
      }
      else
      {
--- 703,713 ----
           * estimate the number of pages fetched by all the scans. Then
           * pro-rate for one scan.
           */
!         pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
                                              baserel->pages,
                                              get_indexpath_pages(bitmapqual),
                                              root);
!         pages_fetched /= loop_count;
      }
      else
      {
*************** cost_bitmap_tree_node(Path *path, Cost *
*** 711,717 ****
           * scan doesn't look to be the same cost as an indexscan to retrieve a
           * single tuple.
           */
!         *cost += 0.1 * cpu_operator_cost * ((IndexPath *) path)->rows;
      }
      else if (IsA(path, BitmapAndPath))
      {
--- 774,780 ----
           * scan doesn't look to be the same cost as an indexscan to retrieve a
           * single tuple.
           */
!         *cost += 0.1 * cpu_operator_cost * path->rows;
      }
      else if (IsA(path, BitmapAndPath))
      {
*************** cost_bitmap_and_node(BitmapAndPath *path
*** 772,777 ****
--- 835,841 ----
              totalCost += 100.0 * cpu_operator_cost;
      }
      path->bitmapselectivity = selec;
+     path->path.rows = path->path.parent->rows; /* not really used */
      path->path.startup_cost = totalCost;
      path->path.total_cost = totalCost;
  }
*************** cost_bitmap_or_node(BitmapOrPath *path,
*** 817,822 ****
--- 881,887 ----
              totalCost += 100.0 * cpu_operator_cost;
      }
      path->bitmapselectivity = Min(selec, 1.0);
+     path->path.rows = path->path.parent->rows; /* not really used */
      path->path.startup_cost = totalCost;
      path->path.total_cost = totalCost;
  }
*************** cost_tidscan(Path *path, PlannerInfo *ro
*** 842,847 ****
--- 907,915 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_RELATION);

+     /* For now, tidscans are never parameterized */
+     path->rows = baserel->rows;
+
      /* Count how many tuples we expect to retrieve */
      ntuples = 0;
      foreach(l, tidquals)
*************** cost_subqueryscan(Path *path, RelOptInfo
*** 923,928 ****
--- 991,999 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_SUBQUERY);

+     /* subqueryscans are never parameterized */
+     path->rows = baserel->rows;
+
      /*
       * Cost of path is cost of evaluating the subplan, plus cost of evaluating
       * any restriction clauses that will be attached to the SubqueryScan node,
*************** cost_functionscan(Path *path, PlannerInf
*** 957,962 ****
--- 1028,1036 ----
      rte = planner_rt_fetch(baserel->relid, root);
      Assert(rte->rtekind == RTE_FUNCTION);

+     /* functionscans are never parameterized */
+     path->rows = baserel->rows;
+
      /*
       * Estimate costs of executing the function expression.
       *
*************** cost_valuesscan(Path *path, PlannerInfo
*** 998,1003 ****
--- 1072,1080 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_VALUES);

+     /* valuesscans are never parameterized */
+     path->rows = baserel->rows;
+
      /*
       * For now, estimate list evaluation cost at one operator eval per list
       * (probably pretty bogus, but is it worth being smarter?)
*************** cost_ctescan(Path *path, PlannerInfo *ro
*** 1034,1039 ****
--- 1111,1119 ----
      Assert(baserel->relid > 0);
      Assert(baserel->rtekind == RTE_CTE);

+     /* ctescans are never parameterized */
+     path->rows = baserel->rows;
+
      /* Charge one CPU tuple cost per row for tuplestore manipulation */
      cpu_per_tuple = cpu_tuple_cost;

*************** cost_sort(Path *path, PlannerInfo *root,
*** 1152,1157 ****
--- 1232,1239 ----
      if (!enable_sort)
          startup_cost += disable_cost;

+     path->rows = tuples;
+
      /*
       * We want to be sure the cost of a sort is never estimated as zero, even
       * if passed-in tuple count is zero.  Besides, mustn't do log(0)...
*************** cost_material(Path *path,
*** 1320,1325 ****
--- 1402,1409 ----
      double        nbytes = relation_byte_size(tuples, width);
      long        work_mem_bytes = work_mem * 1024L;

+     path->rows = tuples;
+
      /*
       * Whether spilling or not, charge 2x cpu_operator_cost per tuple to
       * reflect bookkeeping overhead.  (This rate must be more than what
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1369,1374 ****
--- 1453,1459 ----
           Cost input_startup_cost, Cost input_total_cost,
           double input_tuples)
  {
+     double        output_tuples;
      Cost        startup_cost;
      Cost        total_cost;
      AggClauseCosts dummy_aggcosts;
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1411,1416 ****
--- 1496,1502 ----
          startup_cost += aggcosts->finalCost;
          /* we aren't grouping */
          total_cost = startup_cost + cpu_tuple_cost;
+         output_tuples = 1;
      }
      else if (aggstrategy == AGG_SORTED)
      {
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1423,1428 ****
--- 1509,1515 ----
          total_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
          total_cost += aggcosts->finalCost * numGroups;
          total_cost += cpu_tuple_cost * numGroups;
+         output_tuples = numGroups;
      }
      else
      {
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1434,1441 ****
--- 1521,1530 ----
          total_cost = startup_cost;
          total_cost += aggcosts->finalCost * numGroups;
          total_cost += cpu_tuple_cost * numGroups;
+         output_tuples = numGroups;
      }

+     path->rows = output_tuples;
      path->startup_cost = startup_cost;
      path->total_cost = total_cost;
  }
*************** cost_windowagg(Path *path, PlannerInfo *
*** 1498,1503 ****
--- 1587,1593 ----
      total_cost += cpu_operator_cost * (numPartCols + numOrderCols) * input_tuples;
      total_cost += cpu_tuple_cost * input_tuples;

+     path->rows = input_tuples;
      path->startup_cost = startup_cost;
      path->total_cost = total_cost;
  }
*************** cost_group(Path *path, PlannerInfo *root
*** 1528,1587 ****
       */
      total_cost += cpu_operator_cost * input_tuples * numGroupCols;

      path->startup_cost = startup_cost;
      path->total_cost = total_cost;
  }

  /*
-  * If a nestloop's inner path is an indexscan, be sure to use its estimated
-  * output row count, which may be lower than the restriction-clause-only row
-  * count of its parent.  (We don't include this case in the PATH_ROWS macro
-  * because it applies *only* to a nestloop's inner relation.)  We have to
-  * be prepared to recurse through Append or MergeAppend nodes in case of an
-  * appendrel.  (It's not clear MergeAppend can be seen here, but we may as
-  * well handle it if so.)
-  */
- static double
- nestloop_inner_path_rows(Path *path)
- {
-     double        result;
-
-     if (IsA(path, IndexPath))
-         result = ((IndexPath *) path)->rows;
-     else if (IsA(path, BitmapHeapPath))
-         result = ((BitmapHeapPath *) path)->rows;
-     else if (IsA(path, AppendPath))
-     {
-         ListCell   *l;
-
-         result = 0;
-         foreach(l, ((AppendPath *) path)->subpaths)
-         {
-             result += nestloop_inner_path_rows((Path *) lfirst(l));
-         }
-     }
-     else if (IsA(path, MergeAppendPath))
-     {
-         ListCell   *l;
-
-         result = 0;
-         foreach(l, ((MergeAppendPath *) path)->subpaths)
-         {
-             result += nestloop_inner_path_rows((Path *) lfirst(l));
-         }
-     }
-     else
-         result = PATH_ROWS(path);
-
-     return result;
- }
-
- /*
   * cost_nestloop
   *      Determines and returns the cost of joining two relations using the
   *      nested loop algorithm.
   *
!  * 'path' is already filled in except for the cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   */
  void
--- 1618,1634 ----
       */
      total_cost += cpu_operator_cost * input_tuples * numGroupCols;

+     path->rows = numGroups;
      path->startup_cost = startup_cost;
      path->total_cost = total_cost;
  }

  /*
   * cost_nestloop
   *      Determines and returns the cost of joining two relations using the
   *      nested loop algorithm.
   *
!  * 'path' is already filled in except for the rows and cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   */
  void
*************** cost_nestloop(NestPath *path, PlannerInf
*** 1597,1609 ****
      Cost        inner_rescan_run_cost;
      Cost        cpu_per_tuple;
      QualCost    restrict_qual_cost;
!     double        outer_path_rows = PATH_ROWS(outer_path);
!     double        inner_path_rows = nestloop_inner_path_rows(inner_path);
      double        ntuples;
      Selectivity outer_match_frac;
      Selectivity match_count;
      bool        indexed_join_quals;

      if (!enable_nestloop)
          startup_cost += disable_cost;

--- 1644,1676 ----
      Cost        inner_rescan_run_cost;
      Cost        cpu_per_tuple;
      QualCost    restrict_qual_cost;
!     double        outer_path_rows = outer_path->rows;
!     double        inner_path_rows = inner_path->rows;
      double        ntuples;
      Selectivity outer_match_frac;
      Selectivity match_count;
      bool        indexed_join_quals;

+     /* Estimate the number of rows returned by the join */
+     if (path->path.required_outer)
+     {
+         List   *jclauses;
+
+         /*
+          * The nestloop is (still) parameterized because of upper-level join
+          * clauses used by the input paths.  So the rowcount estimate should
+          * be less than the joinrel's row count because of the additional
+          * selectivity of those join clauses.  To estimate the size we need
+          * to know which of the joinrestrictinfo clauses nominally associated
+          * with the join have been applied in the inner input path.
+          */
+         jclauses = select_nonredundant_join_clauses(path->joinrestrictinfo,
+                                          path->innerjoinpath->param_clauses);
+         set_joinpath_size_estimate(root, path, sjinfo, jclauses);
+     }
+     else
+         path->path.rows = path->path.parent->rows;
+
      if (!enable_nestloop)
          startup_cost += disable_cost;

*************** cost_nestloop(NestPath *path, PlannerInf
*** 1729,1735 ****
   * no possibility of wanting to keep both paths.  So it seems best to make
   * the decision here and record it in the path's materialize_inner field.
   *
!  * 'path' is already filled in except for the cost fields and materialize_inner
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Notes: path's mergeclauses should be a subset of the joinrestrictinfo list;
--- 1796,1803 ----
   * no possibility of wanting to keep both paths.  So it seems best to make
   * the decision here and record it in the path's materialize_inner field.
   *
!  * 'path' is already filled in except for the rows and cost fields and
!  *        materialize_inner
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Notes: path's mergeclauses should be a subset of the joinrestrictinfo list;
*************** cost_mergejoin(MergePath *path, PlannerI
*** 1753,1760 ****
                  mat_inner_cost;
      QualCost    merge_qual_cost;
      QualCost    qp_qual_cost;
!     double        outer_path_rows = PATH_ROWS(outer_path);
!     double        inner_path_rows = PATH_ROWS(inner_path);
      double        outer_rows,
                  inner_rows,
                  outer_skip_rows,
--- 1821,1828 ----
                  mat_inner_cost;
      QualCost    merge_qual_cost;
      QualCost    qp_qual_cost;
!     double        outer_path_rows = outer_path->rows;
!     double        inner_path_rows = inner_path->rows;
      double        outer_rows,
                  inner_rows,
                  outer_skip_rows,
*************** cost_mergejoin(MergePath *path, PlannerI
*** 1768,1773 ****
--- 1836,1844 ----
                  innerendsel;
      Path        sort_path;        /* dummy for result of cost_sort */

+     set_joinpath_size_estimate(root, &path->jpath, sjinfo,
+                                path->jpath.joinrestrictinfo);
+
      /* Protect some assumptions below that rowcounts aren't zero or NaN */
      if (outer_path_rows <= 0 || isnan(outer_path_rows))
          outer_path_rows = 1;
*************** cached_scansel(PlannerInfo *root, Restri
*** 2152,2158 ****
   *      Determines and returns the cost of joining two relations using the
   *      hash join algorithm.
   *
!  * 'path' is already filled in except for the cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Note: path's hashclauses should be a subset of the joinrestrictinfo list
--- 2223,2229 ----
   *      Determines and returns the cost of joining two relations using the
   *      hash join algorithm.
   *
!  * 'path' is already filled in except for the rows and cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Note: path's hashclauses should be a subset of the joinrestrictinfo list
*************** cost_hashjoin(HashPath *path, PlannerInf
*** 2169,2176 ****
      QualCost    hash_qual_cost;
      QualCost    qp_qual_cost;
      double        hashjointuples;
!     double        outer_path_rows = PATH_ROWS(outer_path);
!     double        inner_path_rows = PATH_ROWS(inner_path);
      int            num_hashclauses = list_length(hashclauses);
      int            numbuckets;
      int            numbatches;
--- 2240,2247 ----
      QualCost    hash_qual_cost;
      QualCost    qp_qual_cost;
      double        hashjointuples;
!     double        outer_path_rows = outer_path->rows;
!     double        inner_path_rows = inner_path->rows;
      int            num_hashclauses = list_length(hashclauses);
      int            numbuckets;
      int            numbatches;
*************** cost_hashjoin(HashPath *path, PlannerInf
*** 2181,2186 ****
--- 2252,2260 ----
      Selectivity match_count;
      ListCell   *hcl;

+     set_joinpath_size_estimate(root, &path->jpath, sjinfo,
+                                path->jpath.joinrestrictinfo);
+
      if (!enable_hashjoin)
          startup_cost += disable_cost;

*************** cost_rescan(PlannerInfo *root, Path *pat
*** 2545,2552 ****
                   * cpu_tuple_cost per tuple, unless the result is large enough
                   * to spill to disk.
                   */
!                 Cost        run_cost = cpu_tuple_cost * path->parent->rows;
!                 double        nbytes = relation_byte_size(path->parent->rows,
                                                          path->parent->width);
                  long        work_mem_bytes = work_mem * 1024L;

--- 2619,2626 ----
                   * cpu_tuple_cost per tuple, unless the result is large enough
                   * to spill to disk.
                   */
!                 Cost        run_cost = cpu_tuple_cost * path->rows;
!                 double        nbytes = relation_byte_size(path->rows,
                                                          path->parent->width);
                  long        work_mem_bytes = work_mem * 1024L;

*************** cost_rescan(PlannerInfo *root, Path *pat
*** 2572,2579 ****
                   * the run_cost charge in cost_sort, and also see comments in
                   * cost_material before you change it.)
                   */
!                 Cost        run_cost = cpu_operator_cost * path->parent->rows;
!                 double        nbytes = relation_byte_size(path->parent->rows,
                                                          path->parent->width);
                  long        work_mem_bytes = work_mem * 1024L;

--- 2646,2653 ----
                   * the run_cost charge in cost_sort, and also see comments in
                   * cost_material before you change it.)
                   */
!                 Cost        run_cost = cpu_operator_cost * path->rows;
!                 double        nbytes = relation_byte_size(path->rows,
                                                          path->parent->width);
                  long        work_mem_bytes = work_mem * 1024L;

*************** cost_qual_eval_walker(Node *node, cost_q
*** 2850,2856 ****
   * We should therefore adjust some of the cost components for this effect.
   * This function computes some estimates needed for these adjustments.
   *
!  * 'path' is already filled in except for the cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Returns TRUE if this is a SEMI or ANTI join, FALSE if not.
--- 2924,2930 ----
   * We should therefore adjust some of the cost components for this effect.
   * This function computes some estimates needed for these adjustments.
   *
!  * 'path' is already filled in except for the rows and cost fields
   * 'sjinfo' is extra info about the join for selectivity estimation
   *
   * Returns TRUE if this is a SEMI or ANTI join, FALSE if not.
*************** adjust_semi_join(PlannerInfo *root, Join
*** 2954,2962 ****
       * nselec * inner_rows / jselec.
       *
       * Note: it is correct to use the inner rel's "rows" count here, not
!      * PATH_ROWS(), even if the inner path under consideration is an inner
!      * indexscan.  This is because we have included all the join clauses in
!      * the selectivity estimate, even ones used in an inner indexscan.
       */
      if (jselec > 0)                /* protect against zero divide */
      {
--- 3028,3036 ----
       * nselec * inner_rows / jselec.
       *
       * Note: it is correct to use the inner rel's "rows" count here, not
!      * innerjoinpath->rows, even if the inner path under consideration is
!      * parameterized.  This is because we have included all the join clauses
!      * in the selectivity estimate, even ones used in an inner indexscan.
       */
      if (jselec > 0)                /* protect against zero divide */
      {
*************** adjust_semi_join(PlannerInfo *root, Join
*** 2981,2989 ****
          {
              List       *nrclauses;

!             nrclauses = select_nonredundant_join_clauses(root,
!                                                       path->joinrestrictinfo,
!                                                          path->innerjoinpath);
              *indexed_join_quals = (nrclauses == NIL);
          }
          else
--- 3055,3063 ----
          {
              List       *nrclauses;

!             nrclauses =
!                 select_nonredundant_join_clauses(path->joinrestrictinfo,
!                                                  path->innerjoinpath->param_clauses);
              *indexed_join_quals = (nrclauses == NIL);
          }
          else
*************** static double
*** 3025,3032 ****
  approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
  {
      double        tuples;
!     double        outer_tuples = path->outerjoinpath->parent->rows;
!     double        inner_tuples = path->innerjoinpath->parent->rows;
      SpecialJoinInfo sjinfo;
      Selectivity selec = 1.0;
      ListCell   *l;
--- 3099,3106 ----
  approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
  {
      double        tuples;
!     double        outer_tuples = path->outerjoinpath->rows;
!     double        inner_tuples = path->innerjoinpath->rows;
      SpecialJoinInfo sjinfo;
      Selectivity selec = 1.0;
      ListCell   *l;
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3123,3128 ****
--- 3197,3251 ----
                             SpecialJoinInfo *sjinfo,
                             List *restrictlist)
  {
+     rel->rows = calc_joinrel_size_estimate(root,
+                                            outer_rel->rows,
+                                            inner_rel->rows,
+                                            sjinfo,
+                                            restrictlist);
+ }
+
+ /*
+  * set_joinpath_size_estimate
+  *        Set the rows estimate for the given join path.
+  *
+  * If the join is not parameterized by any joinclauses from higher joins, the
+  * estimate is the same as previously computed by set_joinrel_size_estimates.
+  * Otherwise, we estimate afresh using the identical logic, but with the rows
+  * estimates from the input paths (which are typically less than their rels'
+  * regular row estimates) and the restriction clauses actually being applied
+  * at the join.
+  */
+ static void
+ set_joinpath_size_estimate(PlannerInfo *root, JoinPath *path,
+                            SpecialJoinInfo *sjinfo,
+                            List *restrictlist)
+ {
+     if (path->path.required_outer)
+     {
+         path->path.rows = calc_joinrel_size_estimate(root,
+                                                      path->outerjoinpath->rows,
+                                                      path->innerjoinpath->rows,
+                                                      sjinfo,
+                                                      restrictlist);
+         /* For safety, make sure result is not more than the base estimate */
+         if (path->path.rows > path->path.parent->rows)
+             path->path.rows = path->path.parent->rows;
+     }
+     else
+         path->path.rows = path->path.parent->rows;
+ }
+
+ /*
+  * calc_joinrel_size_estimate
+  *        Workhorse for set_joinrel_size_estimates and set_joinpath_size_estimate
+  */
+ static double
+ calc_joinrel_size_estimate(PlannerInfo *root,
+                            double outer_rows,
+                            double inner_rows,
+                            SpecialJoinInfo *sjinfo,
+                            List *restrictlist)
+ {
      JoinType    jointype = sjinfo->jointype;
      Selectivity jselec;
      Selectivity pselec;
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3197,3224 ****
      switch (jointype)
      {
          case JOIN_INNER:
!             nrows = outer_rel->rows * inner_rel->rows * jselec;
              break;
          case JOIN_LEFT:
!             nrows = outer_rel->rows * inner_rel->rows * jselec;
!             if (nrows < outer_rel->rows)
!                 nrows = outer_rel->rows;
              nrows *= pselec;
              break;
          case JOIN_FULL:
!             nrows = outer_rel->rows * inner_rel->rows * jselec;
!             if (nrows < outer_rel->rows)
!                 nrows = outer_rel->rows;
!             if (nrows < inner_rel->rows)
!                 nrows = inner_rel->rows;
              nrows *= pselec;
              break;
          case JOIN_SEMI:
!             nrows = outer_rel->rows * jselec;
              /* pselec not used */
              break;
          case JOIN_ANTI:
!             nrows = outer_rel->rows * (1.0 - jselec);
              nrows *= pselec;
              break;
          default:
--- 3320,3347 ----
      switch (jointype)
      {
          case JOIN_INNER:
!             nrows = outer_rows * inner_rows * jselec;
              break;
          case JOIN_LEFT:
!             nrows = outer_rows * inner_rows * jselec;
!             if (nrows < outer_rows)
!                 nrows = outer_rows;
              nrows *= pselec;
              break;
          case JOIN_FULL:
!             nrows = outer_rows * inner_rows * jselec;
!             if (nrows < outer_rows)
!                 nrows = outer_rows;
!             if (nrows < inner_rows)
!                 nrows = inner_rows;
              nrows *= pselec;
              break;
          case JOIN_SEMI:
!             nrows = outer_rows * jselec;
              /* pselec not used */
              break;
          case JOIN_ANTI:
!             nrows = outer_rows * (1.0 - jselec);
              nrows *= pselec;
              break;
          default:
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3228,3234 ****
              break;
      }

!     rel->rows = clamp_row_est(nrows);
  }

  /*
--- 3351,3357 ----
              break;
      }

!     return clamp_row_est(nrows);
  }

  /*
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 11ee2317376b03d443d7ec25c745f51497d8a808..5f42407a6f8a782e1c311ca76fdf4b7b8895ed7e 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** typedef struct
*** 73,90 ****

  static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
                      List *clauses, List *outer_clauses,
!                     bool istoplevel, RelOptInfo *outer_rel,
                      SaOpControl saop_control, ScanTypeControl scantype);
  static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
                  List *clauses, List *outer_clauses,
!                 bool istoplevel, RelOptInfo *outer_rel);
  static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
!                   List *paths, RelOptInfo *outer_rel);
  static int    path_usage_comparator(const void *a, const void *b);
  static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                      Path *ipath, RelOptInfo *outer_rel);
  static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                     List *paths, RelOptInfo *outer_rel);
  static PathClauseUsage *classify_index_clause_usage(Path *path,
                              List **clauselist);
  static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
--- 73,95 ----

  static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
                      List *clauses, List *outer_clauses,
!                     bool istoplevel,
!                     Relids outer_relids, double outer_rows,
                      SaOpControl saop_control, ScanTypeControl scantype);
  static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
                  List *clauses, List *outer_clauses,
!                 bool istoplevel,
!                 Relids outer_relids, double outer_rows);
  static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
!                   List *paths,
!                   Relids outer_relids, double outer_rows);
  static int    path_usage_comparator(const void *a, const void *b);
  static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                      Path *ipath,
!                      Relids outer_relids, double outer_rows);
  static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                     List *paths,
!                     Relids outer_relids, double outer_rows);
  static PathClauseUsage *classify_index_clause_usage(Path *path,
                              List **clauselist);
  static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
*************** static Expr *match_clause_to_ordering_op
*** 118,125 ****
  static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
  static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
                    Relids outer_relids);
  static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
!                       Relids outer_relids, bool isouterjoin);
  static bool match_boolean_index_clause(Node *clause, int indexcol,
                             IndexOptInfo *index);
  static bool match_special_index_operator(Expr *clause,
--- 123,132 ----
  static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
  static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
                    Relids outer_relids);
+ static void find_parameterized_indexscans(PlannerInfo *root, RelOptInfo *rel,
+                               Relids outer_relids, double outer_rows);
  static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
!                       Relids outer_relids);
  static bool match_boolean_index_clause(Node *clause, int indexcol,
                             IndexOptInfo *index);
  static bool match_special_index_operator(Expr *clause,
*************** static Const *string_to_const(const char
*** 152,172 ****
   *
   * There are two basic kinds of index scans.  A "plain" index scan uses
   * only restriction clauses (possibly none at all) in its indexqual,
!  * so it can be applied in any context.  An "innerjoin" index scan uses
   * join clauses (plus restriction clauses, if available) in its indexqual.
!  * Therefore it can only be used as the inner relation of a nestloop
!  * join against an outer rel that includes all the other rels mentioned
!  * in its join clauses.  In that context, values for the other rels'
   * attributes are available and fixed during any one scan of the indexpath.
   *
!  * An IndexPath is generated and submitted to add_path() for each plain index
!  * scan this routine deems potentially interesting for the current query.
!  *
!  * We also determine the set of other relids that participate in join
!  * clauses that could be used with each index.    The actually best innerjoin
!  * path will be generated for each outer relation later on, but knowing the
!  * set of potential otherrels allows us to identify equivalent outer relations
!  * and avoid repeated computation.
   *
   * 'rel' is the relation for which we want to generate index paths
   *
--- 159,175 ----
   *
   * There are two basic kinds of index scans.  A "plain" index scan uses
   * only restriction clauses (possibly none at all) in its indexqual,
!  * so it can be applied in any context.  A "parameterized" index scan uses
   * join clauses (plus restriction clauses, if available) in its indexqual.
!  * When joining such a scan to one of the relations supplying the other
!  * variables used in its indexqual, the parameterized scan must appear as
!  * the inner relation of a nestloop join; it can't be used on the outer side,
!  * nor in a merge or hash join.  In that context, values for the other rels'
   * attributes are available and fixed during any one scan of the indexpath.
   *
!  * An IndexPath is generated and submitted to add_path() for each plain or
!  * parameterized index scan this routine deems potentially interesting for
!  * the current query.
   *
   * 'rel' is the relation for which we want to generate index paths
   *
*************** create_index_paths(PlannerInfo *root, Re
*** 178,183 ****
--- 181,188 ----
      List       *indexpaths;
      List       *bitindexpaths;
      ListCell   *l;
+     Index        rti;
+     double        min_rowcount;

      /* Skip the whole mess if no indexes */
      if (rel->indexlist == NIL)
*************** create_index_paths(PlannerInfo *root, Re
*** 191,196 ****
--- 196,203 ----
       * indexes of this rel, and generate the set of all other relids that
       * participate in such join clauses.  We'll use this set later to
       * recognize outer rels that are equivalent for joining purposes.
+      *
+      * XXX index_outer_relids could now be a local variable in this routine
       */
      rel->index_outer_relids = indexable_outerrelids(root, rel);

*************** create_index_paths(PlannerInfo *root, Re
*** 200,206 ****
       */
      indexpaths = find_usable_indexes(root, rel,
                                       rel->baserestrictinfo, NIL,
!                                      true, NULL, SAOP_PER_AM, ST_ANYSCAN);

      /*
       * Submit all the ones that can form plain IndexScan plans to add_path.
--- 207,215 ----
       */
      indexpaths = find_usable_indexes(root, rel,
                                       rel->baserestrictinfo, NIL,
!                                      true,
!                                      NULL, 1.0,
!                                      SAOP_PER_AM, ST_ANYSCAN);

      /*
       * Submit all the ones that can form plain IndexScan plans to add_path.
*************** create_index_paths(PlannerInfo *root, Re
*** 233,239 ****
       */
      indexpaths = generate_bitmap_or_paths(root, rel,
                                            rel->baserestrictinfo, NIL,
!                                           NULL);
      bitindexpaths = list_concat(bitindexpaths, indexpaths);

      /*
--- 242,248 ----
       */
      indexpaths = generate_bitmap_or_paths(root, rel,
                                            rel->baserestrictinfo, NIL,
!                                           NULL, 1.0);
      bitindexpaths = list_concat(bitindexpaths, indexpaths);

      /*
*************** create_index_paths(PlannerInfo *root, Re
*** 243,249 ****
       */
      indexpaths = find_saop_paths(root, rel,
                                   rel->baserestrictinfo, NIL,
!                                  true, NULL);
      bitindexpaths = list_concat(bitindexpaths, indexpaths);

      /*
--- 252,259 ----
       */
      indexpaths = find_saop_paths(root, rel,
                                   rel->baserestrictinfo, NIL,
!                                  true,
!                                  NULL, 1.0);
      bitindexpaths = list_concat(bitindexpaths, indexpaths);

      /*
*************** create_index_paths(PlannerInfo *root, Re
*** 255,264 ****
          Path       *bitmapqual;
          BitmapHeapPath *bpath;

!         bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL);
!         bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL);
          add_path(rel, (Path *) bpath);
      }
  }


--- 265,333 ----
          Path       *bitmapqual;
          BitmapHeapPath *bpath;

!         bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL, 1.0);
!         bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL, 1.0);
          add_path(rel, (Path *) bpath);
      }
+
+     /*
+      * Now consider parameterized indexscans (those using join clauses).
+      *
+      * No need to do anything if there are no potentially useful joinclauses.
+      */
+     if (bms_is_empty(rel->index_outer_relids))
+         return;
+
+     /*
+      * The hard part here is to determine which sets of available join
+      * clauses to use, especially in the presence of ECs that can generate
+      * multiple redundant clauses.  For the moment we consider two cases:
+      *
+      * 1) indexscans with a single other baserel as the source of parameters
+      *
+      * 2) indexscans with all potentially useful other baserels as the
+      * source of parameters.
+      *
+      * This must get improved soon --- in particular, case (2) can easily
+      * generate redundant, poorly-costed plans when there are ECs relating
+      * this rel to two or more others.
+      */
+     min_rowcount = -1;
+     for (rti = 1; rti < root->simple_rel_array_size; rti++)
+     {
+         RelOptInfo *outer_rel = root->simple_rel_array[rti];
+
+         /* there may be empty slots corresponding to non-baserel RTEs */
+         if (outer_rel == NULL)
+             continue;
+
+         Assert(outer_rel->relid == rti);        /* sanity check on array */
+
+         /* ignore RTEs that are "other rels" */
+         if (outer_rel->reloptkind != RELOPT_BASEREL)
+             continue;
+
+         /* can't join to self, of course */
+         if (outer_rel == rel)
+             continue;
+         Assert(outer_rel->relid != rel->relid);
+
+         /* ignore if no potentially useful join clauses */
+         if (!bms_overlap(rel->index_outer_relids, outer_rel->relids))
+             continue;
+
+         /* try to build index paths joining to just this rel */
+         find_parameterized_indexscans(root, rel,
+                                       outer_rel->relids, outer_rel->rows);
+
+         /* remember smallest row count estimate among these rels */
+         if (min_rowcount < 0 || min_rowcount > outer_rel->rows)
+             min_rowcount = outer_rel->rows;
+     }
+
+     /* try to build index paths joining to all other useful rels */
+     find_parameterized_indexscans(root, rel,
+                                   rel->index_outer_relids, min_rowcount);
  }


*************** create_index_paths(PlannerInfo *root, Re
*** 291,311 ****
   * 'outer_clauses' is the list of additional upper-level clauses
   * 'istoplevel' is true if clauses are the rel's top-level restriction list
   *        (outer_clauses must be NIL when this is true)
!  * 'outer_rel' is the outer side of the join if forming an inner indexscan
!  *        (so some of the given clauses are join clauses); NULL if not
   * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
   * 'scantype' indicates whether we need plain or bitmap scan support
   *
!  * Note: check_partial_indexes() must have been run previously.
   *----------
   */
  static List *
  find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
                      List *clauses, List *outer_clauses,
!                     bool istoplevel, RelOptInfo *outer_rel,
                      SaOpControl saop_control, ScanTypeControl scantype)
  {
-     Relids        outer_relids = outer_rel ? outer_rel->relids : NULL;
      bool        possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
      List       *result = NIL;
      List       *all_clauses = NIL;        /* not computed till needed */
--- 360,381 ----
   * 'outer_clauses' is the list of additional upper-level clauses
   * 'istoplevel' is true if clauses are the rel's top-level restriction list
   *        (outer_clauses must be NIL when this is true)
!  * 'outer_relids' lists rels whose Vars can be used as parameters
!  * 'outer_rows' is the number of loop repetitions to expect
   * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
   * 'scantype' indicates whether we need plain or bitmap scan support
   *
!  * Note: outer_clauses and outer_relids/outer_rows refer to two different
!  * concepts of "outer".  Should probably rename...
   *----------
   */
  static List *
  find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
                      List *clauses, List *outer_clauses,
!                     bool istoplevel,
!                     Relids outer_relids, double outer_rows,
                      SaOpControl saop_control, ScanTypeControl scantype)
  {
      bool        possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
      List       *result = NIL;
      List       *all_clauses = NIL;        /* not computed till needed */
*************** find_usable_indexes(PlannerInfo *root, R
*** 426,432 ****
           */
          index_is_ordered = (index->sortopfamily != NULL);
          if (index_is_ordered && possibly_useful_pathkeys &&
!             istoplevel && outer_rel == NULL)
          {
              index_pathkeys = build_index_pathkeys(root, index,
                                                    ForwardScanDirection);
--- 496,502 ----
           */
          index_is_ordered = (index->sortopfamily != NULL);
          if (index_is_ordered && possibly_useful_pathkeys &&
!             istoplevel && outer_relids == NULL)
          {
              index_pathkeys = build_index_pathkeys(root, index,
                                                    ForwardScanDirection);
*************** find_usable_indexes(PlannerInfo *root, R
*** 436,442 ****
              orderbyclausecols = NIL;
          }
          else if (index->amcanorderbyop && possibly_useful_pathkeys &&
!                  istoplevel && outer_rel == NULL && scantype != ST_BITMAPSCAN)
          {
              /* see if we can generate ordering operators for query_pathkeys */
              match_pathkeys_to_index(index, root->query_pathkeys,
--- 506,513 ----
              orderbyclausecols = NIL;
          }
          else if (index->amcanorderbyop && possibly_useful_pathkeys &&
!                  istoplevel && outer_relids == NULL &&
!                  scantype != ST_BITMAPSCAN)
          {
              /* see if we can generate ordering operators for query_pathkeys */
              match_pathkeys_to_index(index, root->query_pathkeys,
*************** find_usable_indexes(PlannerInfo *root, R
*** 479,485 ****
                                        ForwardScanDirection :
                                        NoMovementScanDirection,
                                        index_only_scan,
!                                       outer_rel);
              result = lappend(result, ipath);
          }

--- 550,557 ----
                                        ForwardScanDirection :
                                        NoMovementScanDirection,
                                        index_only_scan,
!                                       outer_relids,
!                                       outer_rows);
              result = lappend(result, ipath);
          }

*************** find_usable_indexes(PlannerInfo *root, R
*** 488,494 ****
           * Again, this is only interesting at top level.
           */
          if (index_is_ordered && possibly_useful_pathkeys &&
!             istoplevel && outer_rel == NULL)
          {
              index_pathkeys = build_index_pathkeys(root, index,
                                                    BackwardScanDirection);
--- 560,566 ----
           * Again, this is only interesting at top level.
           */
          if (index_is_ordered && possibly_useful_pathkeys &&
!             istoplevel && outer_relids == NULL)
          {
              index_pathkeys = build_index_pathkeys(root, index,
                                                    BackwardScanDirection);
*************** find_usable_indexes(PlannerInfo *root, R
*** 504,510 ****
                                            useful_pathkeys,
                                            BackwardScanDirection,
                                            index_only_scan,
!                                           outer_rel);
                  result = lappend(result, ipath);
              }
          }
--- 576,583 ----
                                            useful_pathkeys,
                                            BackwardScanDirection,
                                            index_only_scan,
!                                           outer_relids,
!                                           outer_rows);
                  result = lappend(result, ipath);
              }
          }
*************** find_usable_indexes(PlannerInfo *root, R
*** 525,531 ****
  static List *
  find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
                  List *clauses, List *outer_clauses,
!                 bool istoplevel, RelOptInfo *outer_rel)
  {
      bool        have_saop = false;
      ListCell   *l;
--- 598,605 ----
  static List *
  find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
                  List *clauses, List *outer_clauses,
!                 bool istoplevel,
!                 Relids outer_relids, double outer_rows)
  {
      bool        have_saop = false;
      ListCell   *l;
*************** find_saop_paths(PlannerInfo *root, RelOp
*** 550,556 ****

      return find_usable_indexes(root, rel,
                                 clauses, outer_clauses,
!                                istoplevel, outer_rel,
                                 SAOP_REQUIRE, ST_BITMAPSCAN);
  }

--- 624,630 ----

      return find_usable_indexes(root, rel,
                                 clauses, outer_clauses,
!                                istoplevel, outer_relids, outer_rows,
                                 SAOP_REQUIRE, ST_BITMAPSCAN);
  }

*************** find_saop_paths(PlannerInfo *root, RelOp
*** 563,575 ****
   *
   * outer_clauses is a list of additional clauses that can be assumed true
   * for the purpose of generating indexquals, but are not to be searched for
!  * ORs.  (See find_usable_indexes() for motivation.)  outer_rel is the outer
!  * side when we are considering a nestloop inner indexpath.
   */
  List *
  generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
                           List *clauses, List *outer_clauses,
!                          RelOptInfo *outer_rel)
  {
      List       *result = NIL;
      List       *all_clauses;
--- 637,650 ----
   *
   * outer_clauses is a list of additional clauses that can be assumed true
   * for the purpose of generating indexquals, but are not to be searched for
!  * ORs.  (See find_usable_indexes() for motivation.)  outer_relids is the set
!  * of relids on the outer side when we are considering a parameterized path,
!  * and outer_rows is the loop count to expect.
   */
  List *
  generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
                           List *clauses, List *outer_clauses,
!                          Relids outer_relids, double outer_rows)
  {
      List       *result = NIL;
      List       *all_clauses;
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 612,618 ****
                                                andargs,
                                                all_clauses,
                                                false,
!                                               outer_rel,
                                                SAOP_ALLOW,
                                                ST_BITMAPSCAN);
                  /* Recurse in case there are sub-ORs */
--- 687,694 ----
                                                andargs,
                                                all_clauses,
                                                false,
!                                               outer_relids,
!                                               outer_rows,
                                                SAOP_ALLOW,
                                                ST_BITMAPSCAN);
                  /* Recurse in case there are sub-ORs */
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 620,626 ****
                                        generate_bitmap_or_paths(root, rel,
                                                                 andargs,
                                                                 all_clauses,
!                                                                outer_rel));
              }
              else
              {
--- 696,703 ----
                                        generate_bitmap_or_paths(root, rel,
                                                                 andargs,
                                                                 all_clauses,
!                                                                outer_relids,
!                                                                outer_rows));
              }
              else
              {
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 630,636 ****
                                                list_make1(orarg),
                                                all_clauses,
                                                false,
!                                               outer_rel,
                                                SAOP_ALLOW,
                                                ST_BITMAPSCAN);
              }
--- 707,714 ----
                                                list_make1(orarg),
                                                all_clauses,
                                                false,
!                                               outer_relids,
!                                               outer_rows,
                                                SAOP_ALLOW,
                                                ST_BITMAPSCAN);
              }
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 649,655 ****
               * OK, pick the most promising AND combination, and add it to
               * pathlist.
               */
!             bitmapqual = choose_bitmap_and(root, rel, indlist, outer_rel);
              pathlist = lappend(pathlist, bitmapqual);
          }

--- 727,734 ----
               * OK, pick the most promising AND combination, and add it to
               * pathlist.
               */
!             bitmapqual = choose_bitmap_and(root, rel, indlist,
!                                            outer_relids, outer_rows);
              pathlist = lappend(pathlist, bitmapqual);
          }

*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 681,687 ****
   */
  static Path *
  choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
!                   List *paths, RelOptInfo *outer_rel)
  {
      int            npaths = list_length(paths);
      PathClauseUsage **pathinfoarray;
--- 760,767 ----
   */
  static Path *
  choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
!                   List *paths,
!                   Relids outer_relids, double outer_rows)
  {
      int            npaths = list_length(paths);
      PathClauseUsage **pathinfoarray;
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 729,735 ****
       * reduces the total cost.    Perhaps someday that code will be smarter and
       * we can remove this limitation.  (But note that this also defends
       * against flat-out duplicate input paths, which can happen because
!      * best_inner_indexscan will find the same OR join clauses that
       * create_or_index_quals has pulled OR restriction clauses out of.)
       *
       * For the same reason, we reject AND combinations in which an index
--- 809,815 ----
       * reduces the total cost.    Perhaps someday that code will be smarter and
       * we can remove this limitation.  (But note that this also defends
       * against flat-out duplicate input paths, which can happen because
!      * find_parameterized_indexscans will find the same OR join clauses that
       * create_or_index_quals has pulled OR restriction clauses out of.)
       *
       * For the same reason, we reject AND combinations in which an index
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 807,813 ****

          pathinfo = pathinfoarray[i];
          paths = list_make1(pathinfo->path);
!         costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path, outer_rel);
          qualsofar = list_concat(list_copy(pathinfo->quals),
                                  list_copy(pathinfo->preds));
          clauseidsofar = bms_copy(pathinfo->clauseids);
--- 887,894 ----

          pathinfo = pathinfoarray[i];
          paths = list_make1(pathinfo->path);
!         costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path,
!                                          outer_relids, outer_rows);
          qualsofar = list_concat(list_copy(pathinfo->quals),
                                  list_copy(pathinfo->preds));
          clauseidsofar = bms_copy(pathinfo->clauseids);
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 841,847 ****
              }
              /* tentatively add new path to paths, so we can estimate cost */
              paths = lappend(paths, pathinfo->path);
!             newcost = bitmap_and_cost_est(root, rel, paths, outer_rel);
              if (newcost < costsofar)
              {
                  /* keep new path in paths, update subsidiary variables */
--- 922,929 ----
              }
              /* tentatively add new path to paths, so we can estimate cost */
              paths = lappend(paths, pathinfo->path);
!             newcost = bitmap_and_cost_est(root, rel, paths,
!                                           outer_relids, outer_rows);
              if (newcost < costsofar)
              {
                  /* keep new path in paths, update subsidiary variables */
*************** path_usage_comparator(const void *a, con
*** 914,926 ****
   */
  static Cost
  bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                      Path *ipath, RelOptInfo *outer_rel)
  {
!     Path        bpath;

!     cost_bitmap_heap_scan(&bpath, root, rel, ipath, outer_rel);

!     return bpath.total_cost;
  }

  /*
--- 996,1018 ----
   */
  static Cost
  bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                      Path *ipath,
!                      Relids outer_relids, double outer_rows)
  {
!     BitmapHeapPath bpath;

!     /* Set up a dummy BitmapHeapPath */
!     bpath.path.type = T_BitmapHeapPath;
!     bpath.path.pathtype = T_BitmapHeapScan;
!     bpath.path.parent = rel;
!     bpath.path.required_outer = outer_relids;
!     bpath.path.param_clauses = NIL;    /* not needed for cost estimate */
!     bpath.path.pathkeys = NIL;
!     bpath.bitmapqual = ipath;

!     cost_bitmap_heap_scan((Path *) &bpath, root, rel, ipath, outer_rows);
!
!     return bpath.path.total_cost;
  }

  /*
*************** bitmap_scan_cost_est(PlannerInfo *root,
*** 929,949 ****
   */
  static Cost
  bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                     List *paths, RelOptInfo *outer_rel)
  {
      BitmapAndPath apath;
!     Path        bpath;

      /* Set up a dummy BitmapAndPath */
      apath.path.type = T_BitmapAndPath;
      apath.path.parent = rel;
      apath.bitmapquals = paths;
      cost_bitmap_and_node(&apath, root);

      /* Now we can do cost_bitmap_heap_scan */
!     cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, outer_rel);

!     return bpath.total_cost;
  }


--- 1021,1056 ----
   */
  static Cost
  bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
!                     List *paths,
!                     Relids outer_relids, double outer_rows)
  {
      BitmapAndPath apath;
!     BitmapHeapPath bpath;

      /* Set up a dummy BitmapAndPath */
      apath.path.type = T_BitmapAndPath;
+     apath.path.pathtype = T_BitmapAnd;
      apath.path.parent = rel;
+     apath.path.required_outer = outer_relids;
+     apath.path.param_clauses = NIL;    /* not needed for cost estimate */
+     apath.path.pathkeys = NIL;
      apath.bitmapquals = paths;
+
      cost_bitmap_and_node(&apath, root);

+     /* Set up a dummy BitmapHeapPath */
+     bpath.path.type = T_BitmapHeapPath;
+     bpath.path.pathtype = T_BitmapHeapScan;
+     bpath.path.parent = rel;
+     bpath.path.required_outer = outer_relids;
+     bpath.path.param_clauses = NIL;    /* not needed for cost estimate */
+     bpath.path.pathkeys = NIL;
+     bpath.bitmapqual = (Path *) &apath;
+
      /* Now we can do cost_bitmap_heap_scan */
!     cost_bitmap_heap_scan((Path *) &bpath, root, rel, (Path *) &apath, outer_rows);

!     return bpath.path.total_cost;
  }


*************** match_clauses_to_index(IndexOptInfo *ind
*** 1285,1291 ****
   *      to the caller-specified outer_relids relations (which had better not
   *      include the relation whose index is being tested).  outer_relids should
   *      be NULL when checking simple restriction clauses, and the outer side
!  *      of the join when building a join inner scan.    Other than that, the
   *      only thing we don't like is volatile functions.
   *
   *      Note: in most cases we already know that the clause as a whole uses
--- 1392,1398 ----
   *      to the caller-specified outer_relids relations (which had better not
   *      include the relation whose index is being tested).  outer_relids should
   *      be NULL when checking simple restriction clauses, and the outer side
!  *      of the join when building a parameterized path.  Other than that, the
   *      only thing we don't like is volatile functions.
   *
   *      Note: in most cases we already know that the clause as a whole uses
*************** eclass_matches_any_index(EquivalenceClas
*** 2013,2121 ****


  /*
!  * best_inner_indexscan
!  *      Finds the best available inner indexscans for a nestloop join
!  *      with the given rel on the inside and the given outer_rel outside.
!  *
!  * *cheapest_startup gets the path with least startup cost
!  * *cheapest_total gets the path with least total cost (often the same path)
!  * Both are set to NULL if there are no possible inner indexscans.
!  *
!  * We ignore ordering considerations, since a nestloop's inner scan's order
!  * is uninteresting.  Hence startup cost and total cost are the only figures
!  * of merit to consider.
   *
!  * Note: create_index_paths() must have been run previously for this rel,
!  * else the results will always be NULL.
   */
! void
! best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
!                      RelOptInfo *outer_rel, JoinType jointype,
!                      Path **cheapest_startup, Path **cheapest_total)
  {
-     Relids        outer_relids;
-     bool        isouterjoin;
      List       *clause_list;
-     List       *indexpaths;
      List       *bitindexpaths;
      List       *allindexpaths;
      ListCell   *l;
-     InnerIndexscanInfo *info;
-     MemoryContext oldcontext;
-
-     /* Initialize results for failure returns */
-     *cheapest_startup = *cheapest_total = NULL;
-
-     /*
-      * Nestloop only supports inner, left, semi, and anti joins.
-      */
-     switch (jointype)
-     {
-         case JOIN_INNER:
-         case JOIN_SEMI:
-             isouterjoin = false;
-             break;
-         case JOIN_LEFT:
-         case JOIN_ANTI:
-             isouterjoin = true;
-             break;
-         default:
-             return;
-     }
-
-     /*
-      * If there are no indexable joinclauses for this rel, exit quickly.
-      */
-     if (bms_is_empty(rel->index_outer_relids))
-         return;
-
-     /*
-      * Otherwise, we have to do path selection in the main planning context,
-      * so that any created path can be safely attached to the rel's cache of
-      * best inner paths.  (This is not currently an issue for normal planning,
-      * but it is an issue for GEQO planning.)
-      */
-     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
-
-     /*
-      * Intersect the given outer relids with index_outer_relids to find the
-      * set of outer relids actually relevant for this rel. If there are none,
-      * again we can fail immediately.
-      */
-     outer_relids = bms_intersect(rel->index_outer_relids, outer_rel->relids);
-     if (bms_is_empty(outer_relids))
-     {
-         bms_free(outer_relids);
-         MemoryContextSwitchTo(oldcontext);
-         return;
-     }
-
-     /*
-      * Look to see if we already computed the result for this set of relevant
-      * outerrels.  (We include the isouterjoin status in the cache lookup key
-      * for safety.    In practice I suspect this is not necessary because it
-      * should always be the same for a given combination of rels.)
-      *
-      * NOTE: because we cache on outer_relids rather than outer_rel->relids,
-      * we will report the same paths and hence path cost for joins with
-      * different sets of irrelevant rels on the outside.  Now that cost_index
-      * is sensitive to outer_rel->rows, this is not really right.  However the
-      * error is probably not large.  Is it worth establishing a separate cache
-      * entry for each distinct outer_rel->relids set to get this right?
-      */
-     foreach(l, rel->index_inner_paths)
-     {
-         info = (InnerIndexscanInfo *) lfirst(l);
-         if (bms_equal(info->other_relids, outer_relids) &&
-             info->isouterjoin == isouterjoin)
-         {
-             bms_free(outer_relids);
-             MemoryContextSwitchTo(oldcontext);
-             *cheapest_startup = info->cheapest_startup_innerpath;
-             *cheapest_total = info->cheapest_total_innerpath;
-             return;
-         }
-     }

      /*
       * Find all the relevant restriction and join clauses.
--- 2120,2140 ----


  /*
!  * find_parameterized_indexscans
!  *      Create paths for parameterized indexscans of the given rel
!  *      with the given outer_relids on the outside of the nestloop,
!  *      using outer_rows as the loop count for cost estimates.
   *
!  * The paths are added to the rel's pathlist via add_path().
   */
! static void
! find_parameterized_indexscans(PlannerInfo *root, RelOptInfo *rel,
!                               Relids outer_relids, double outer_rows)
  {
      List       *clause_list;
      List       *bitindexpaths;
      List       *allindexpaths;
      ListCell   *l;

      /*
       * Find all the relevant restriction and join clauses.
*************** best_inner_indexscan(PlannerInfo *root,
*** 2124,2134 ****
       * that could be plain indexscans, ie, they don't require the join context
       * at all.    This may seem redundant, but we need to include those scans in
       * the input given to choose_bitmap_and() to be sure we find optimal AND
!      * combinations of join and non-join scans.  Also, even if the "best inner
!      * indexscan" is just a plain indexscan, it will have a different cost
!      * estimate because of cache effects.
       */
!     clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);

      /*
       * Find all the index paths that are usable for this join, except for
--- 2143,2151 ----
       * that could be plain indexscans, ie, they don't require the join context
       * at all.    This may seem redundant, but we need to include those scans in
       * the input given to choose_bitmap_and() to be sure we find optimal AND
!      * combinations of join and non-join scans.
       */
!     clause_list = find_clauses_for_join(root, rel, outer_relids);

      /*
       * Find all the index paths that are usable for this join, except for
*************** best_inner_indexscan(PlannerInfo *root,
*** 2136,2156 ****
       */
      allindexpaths = find_usable_indexes(root, rel,
                                          clause_list, NIL,
!                                         false, outer_rel,
                                          SAOP_PER_AM,
                                          ST_ANYSCAN);

      /*
!      * Include the ones that are usable as plain indexscans in indexpaths, and
!      * include the ones that are usable as bitmap scans in bitindexpaths.
       */
!     indexpaths = bitindexpaths = NIL;
      foreach(l, allindexpaths)
      {
          IndexPath  *ipath = (IndexPath *) lfirst(l);

          if (ipath->indexinfo->amhasgettuple)
!             indexpaths = lappend(indexpaths, ipath);

          if (ipath->indexinfo->amhasgetbitmap)
              bitindexpaths = lappend(bitindexpaths, ipath);
--- 2153,2174 ----
       */
      allindexpaths = find_usable_indexes(root, rel,
                                          clause_list, NIL,
!                                         false,
!                                         outer_relids, outer_rows,
                                          SAOP_PER_AM,
                                          ST_ANYSCAN);

      /*
!      * Send the ones that are usable as plain indexscans to add_path(), and
!      * remember the ones that are usable as bitmap scans in bitindexpaths.
       */
!     bitindexpaths = NIL;
      foreach(l, allindexpaths)
      {
          IndexPath  *ipath = (IndexPath *) lfirst(l);

          if (ipath->indexinfo->amhasgettuple)
!             add_path(rel, (Path *) ipath);

          if (ipath->indexinfo->amhasgetbitmap)
              bitindexpaths = lappend(bitindexpaths, ipath);
*************** best_inner_indexscan(PlannerInfo *root,
*** 2163,2169 ****
      bitindexpaths = list_concat(bitindexpaths,
                                  generate_bitmap_or_paths(root, rel,
                                                           clause_list, NIL,
!                                                          outer_rel));

      /*
       * Likewise, generate paths using executor-managed ScalarArrayOpExpr
--- 2181,2188 ----
      bitindexpaths = list_concat(bitindexpaths,
                                  generate_bitmap_or_paths(root, rel,
                                                           clause_list, NIL,
!                                                          outer_relids,
!                                                          outer_rows));

      /*
       * Likewise, generate paths using executor-managed ScalarArrayOpExpr
*************** best_inner_indexscan(PlannerInfo *root,
*** 2173,2179 ****
      bitindexpaths = list_concat(bitindexpaths,
                                  find_saop_paths(root, rel,
                                                  clause_list, NIL,
!                                                 false, outer_rel));

      /*
       * If we found anything usable, generate a BitmapHeapPath for the most
--- 2192,2199 ----
      bitindexpaths = list_concat(bitindexpaths,
                                  find_saop_paths(root, rel,
                                                  clause_list, NIL,
!                                                 false,
!                                                 outer_relids, outer_rows));

      /*
       * If we found anything usable, generate a BitmapHeapPath for the most
*************** best_inner_indexscan(PlannerInfo *root,
*** 2184,2221 ****
          Path       *bitmapqual;
          BitmapHeapPath *bpath;

!         bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, outer_rel);
!         bpath = create_bitmap_heap_path(root, rel, bitmapqual, outer_rel);
!         indexpaths = lappend(indexpaths, bpath);
!     }
!
!     /*
!      * Now choose the cheapest members of indexpaths.
!      */
!     if (indexpaths != NIL)
!     {
!         *cheapest_startup = *cheapest_total = (Path *) linitial(indexpaths);
!
!         for_each_cell(l, lnext(list_head(indexpaths)))
!         {
!             Path       *path = (Path *) lfirst(l);
!
!             if (compare_path_costs(path, *cheapest_startup, STARTUP_COST) < 0)
!                 *cheapest_startup = path;
!             if (compare_path_costs(path, *cheapest_total, TOTAL_COST) < 0)
!                 *cheapest_total = path;
!         }
      }
-
-     /* Cache the results --- whether positive or negative */
-     info = makeNode(InnerIndexscanInfo);
-     info->other_relids = outer_relids;
-     info->isouterjoin = isouterjoin;
-     info->cheapest_startup_innerpath = *cheapest_startup;
-     info->cheapest_total_innerpath = *cheapest_total;
-     rel->index_inner_paths = lcons(info, rel->index_inner_paths);
-
-     MemoryContextSwitchTo(oldcontext);
  }

  /*
--- 2204,2215 ----
          Path       *bitmapqual;
          BitmapHeapPath *bpath;

!         bitmapqual = choose_bitmap_and(root, rel, bitindexpaths,
!                                        outer_relids, outer_rows);
!         bpath = create_bitmap_heap_path(root, rel, bitmapqual,
!                                         outer_relids, outer_rows);
!         add_path(rel, (Path *) bpath);
      }
  }

  /*
*************** best_inner_indexscan(PlannerInfo *root,
*** 2230,2236 ****
   */
  static List *
  find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
!                       Relids outer_relids, bool isouterjoin)
  {
      List       *clause_list = NIL;
      Relids        join_relids;
--- 2224,2230 ----
   */
  static List *
  find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
!                       Relids outer_relids)
  {
      List       *clause_list = NIL;
      Relids        join_relids;
*************** find_clauses_for_join(PlannerInfo *root,
*** 2248,2259 ****
      {
          RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

-         /* Can't use pushed-down join clauses in outer join */
-         if (isouterjoin && rinfo->is_pushed_down)
-             continue;
          if (!bms_is_subset(rinfo->required_relids, join_relids))
              continue;

          clause_list = lappend(clause_list, rinfo);
      }

--- 2242,2264 ----
      {
          RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

          if (!bms_is_subset(rinfo->required_relids, join_relids))
              continue;

+         /*
+          * We must ignore clauses for which the target rel is in
+          * nullable_relids; that means there's an outer join below the clause
+          * and so it can't be enforced at the relation scan level.
+          *
+          * Note: unlike create_or_index_quals(), we can accept clauses that
+          * are marked !is_pushed_down (ie they are themselves outer-join
+          * clauses).  This is OK because any path generated with these clauses
+          * could only be used in the inside of a nestloop join, which will be
+          * the nullable side.
+          */
+         if (bms_is_member(rel->relid, rinfo->nullable_relids))
+             continue;
+
          clause_list = lappend(clause_list, rinfo);
      }

*************** find_clauses_for_join(PlannerInfo *root,
*** 2261,2270 ****

      /*
       * Also check to see if any EquivalenceClasses can produce a relevant
!      * joinclause.    Since all such clauses are effectively pushed-down, this
!      * doesn't apply to outer joins.
       */
!     if (!isouterjoin && rel->has_eclass_joins)
          clause_list = list_concat(clause_list,
                                    find_eclass_clauses_for_index_join(root,
                                                                       rel,
--- 2266,2274 ----

      /*
       * Also check to see if any EquivalenceClasses can produce a relevant
!      * joinclause.
       */
!     if (rel->has_eclass_joins)
          clause_list = list_concat(clause_list,
                                    find_eclass_clauses_for_index_join(root,
                                                                       rel,
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 65caeb86c9bd419e3485bbe889f44e559235083a..0353d6e01df39240f055a612e458538af0654843 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** static void hash_inner_and_outer(Planner
*** 34,41 ****
                       RelOptInfo *outerrel, RelOptInfo *innerrel,
                       List *restrictlist,
                       JoinType jointype, SpecialJoinInfo *sjinfo);
- static Path *best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
-                          RelOptInfo *outer_rel, JoinType jointype);
  static List *select_mergejoin_clauses(PlannerInfo *root,
                           RelOptInfo *joinrel,
                           RelOptInfo *outerrel,
--- 34,39 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 367,375 ****
      Path       *inner_cheapest_startup = innerrel->cheapest_startup_path;
      Path       *inner_cheapest_total = innerrel->cheapest_total_path;
      Path       *matpath = NULL;
!     Path       *index_cheapest_startup = NULL;
!     Path       *index_cheapest_total = NULL;
!     ListCell   *l;

      /*
       * Nestloop only supports inner, left, semi, and anti joins.  Also, if we
--- 365,371 ----
      Path       *inner_cheapest_startup = innerrel->cheapest_startup_path;
      Path       *inner_cheapest_total = innerrel->cheapest_total_path;
      Path       *matpath = NULL;
!     ListCell   *lc1;

      /*
       * Nestloop only supports inner, left, semi, and anti joins.  Also, if we
*************** match_unsorted_outer(PlannerInfo *root,
*** 428,455 ****
              !ExecMaterializesOutput(inner_cheapest_total->pathtype))
              matpath = (Path *)
                  create_material_path(innerrel, inner_cheapest_total);
-
-         /*
-          * Get the best innerjoin indexpaths (if any) for this outer rel.
-          * They're the same for all outer paths.
-          */
-         if (innerrel->reloptkind != RELOPT_JOINREL)
-         {
-             if (IsA(inner_cheapest_total, AppendPath))
-                 index_cheapest_total = best_appendrel_indexscan(root,
-                                                                 innerrel,
-                                                                 outerrel,
-                                                                 jointype);
-             else if (innerrel->rtekind == RTE_RELATION)
-                 best_inner_indexscan(root, innerrel, outerrel, jointype,
-                                      &index_cheapest_startup,
-                                      &index_cheapest_total);
-         }
      }

!     foreach(l, outerrel->pathlist)
      {
!         Path       *outerpath = (Path *) lfirst(l);
          List       *merge_pathkeys;
          List       *mergeclauses;
          List       *innersortkeys;
--- 424,434 ----
              !ExecMaterializesOutput(inner_cheapest_total->pathtype))
              matpath = (Path *)
                  create_material_path(innerrel, inner_cheapest_total);
      }

!     foreach(lc1, outerrel->pathlist)
      {
!         Path       *outerpath = (Path *) lfirst(lc1);
          List       *merge_pathkeys;
          List       *mergeclauses;
          List       *innersortkeys;
*************** match_unsorted_outer(PlannerInfo *root,
*** 460,467 ****
          int            sortkeycnt;

          /*
           * If we need to unique-ify the outer path, it's pointless to consider
!          * any but the cheapest outer.
           */
          if (save_jointype == JOIN_UNIQUE_OUTER)
          {
--- 439,452 ----
          int            sortkeycnt;

          /*
+          * We cannot use an outer path that is parameterized by the inner rel.
+          */
+         if (bms_overlap(outerpath->required_outer, innerrel->relids))
+             continue;
+
+         /*
           * If we need to unique-ify the outer path, it's pointless to consider
!          * any but the cheapest outer.  (XXX what about parameterized outers?)
           */
          if (save_jointype == JOIN_UNIQUE_OUTER)
          {
*************** match_unsorted_outer(PlannerInfo *root,
*** 480,493 ****
          merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
                                               outerpath->pathkeys);

!         if (nestjoinOK)
          {
              /*
!              * Always consider a nestloop join with this outer and
!              * cheapest-total-cost inner.  When appropriate, also consider
!              * using the materialized form of the cheapest inner, the
!              * cheapest-startup-cost inner path, and the cheapest innerjoin
!              * indexpaths.
               */
              add_path(joinrel, (Path *)
                       create_nestloop_path(root,
--- 465,475 ----
          merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
                                               outerpath->pathkeys);

!         if (save_jointype == JOIN_UNIQUE_INNER)
          {
              /*
!              * Consider nestloop join, but only with the unique-ified cheapest
!              * inner path
               */
              add_path(joinrel, (Path *)
                       create_nestloop_path(root,
*************** match_unsorted_outer(PlannerInfo *root,
*** 498,503 ****
--- 480,516 ----
                                            inner_cheapest_total,
                                            restrictlist,
                                            merge_pathkeys));
+         }
+         else if (nestjoinOK)
+         {
+             /*
+              * Consider nestloop joins using this outer path and various
+              * available paths for the inner relation.  We always consider the
+              * cheapest-total-cost and cheapest-startup-cost inner paths, as
+              * well as parameterized inner paths (even if they are not
+              * parameterized by this particular outer rel).
+              */
+             ListCell   *lc2;
+
+             foreach(lc2, innerrel->pathlist)
+             {
+                 Path       *innerpath = (Path *) lfirst(lc2);
+
+                 if (innerpath == inner_cheapest_total ||
+                     innerpath == inner_cheapest_startup ||
+                     innerpath->required_outer)
+                     add_path(joinrel, (Path *)
+                              create_nestloop_path(root,
+                                                   joinrel,
+                                                   jointype,
+                                                   sjinfo,
+                                                   outerpath,
+                                                   innerpath,
+                                                   restrictlist,
+                                                   merge_pathkeys));
+             }
+
+             /* Also consider materialized form of the cheapest inner path */
              if (matpath != NULL)
                  add_path(joinrel, (Path *)
                           create_nestloop_path(root,
*************** match_unsorted_outer(PlannerInfo *root,
*** 508,544 ****
                                                matpath,
                                                restrictlist,
                                                merge_pathkeys));
-             if (inner_cheapest_startup != inner_cheapest_total)
-                 add_path(joinrel, (Path *)
-                          create_nestloop_path(root,
-                                               joinrel,
-                                               jointype,
-                                               sjinfo,
-                                               outerpath,
-                                               inner_cheapest_startup,
-                                               restrictlist,
-                                               merge_pathkeys));
-             if (index_cheapest_total != NULL)
-                 add_path(joinrel, (Path *)
-                          create_nestloop_path(root,
-                                               joinrel,
-                                               jointype,
-                                               sjinfo,
-                                               outerpath,
-                                               index_cheapest_total,
-                                               restrictlist,
-                                               merge_pathkeys));
-             if (index_cheapest_startup != NULL &&
-                 index_cheapest_startup != index_cheapest_total)
-                 add_path(joinrel, (Path *)
-                          create_nestloop_path(root,
-                                               joinrel,
-                                               jointype,
-                                               sjinfo,
-                                               outerpath,
-                                               index_cheapest_startup,
-                                               restrictlist,
-                                               merge_pathkeys));
          }

          /* Can't do anything else if outer path needs to be unique'd */
--- 521,526 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 654,659 ****
--- 636,642 ----
              trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
              innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
                                                         trialsortkeys,
+                                                        NULL,
                                                         TOTAL_COST);
              if (innerpath != NULL &&
                  (cheapest_total_inner == NULL ||
*************** match_unsorted_outer(PlannerInfo *root,
*** 690,695 ****
--- 673,679 ----
              /* Same on the basis of cheapest startup cost ... */
              innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
                                                         trialsortkeys,
+                                                        NULL,
                                                         STARTUP_COST);
              if (innerpath != NULL &&
                  (cheapest_startup_inner == NULL ||
*************** hash_inner_and_outer(PlannerInfo *root,
*** 854,928 ****
  }

  /*
-  * best_appendrel_indexscan
-  *      Finds the best available set of inner indexscans for a nestloop join
-  *      with the given append relation on the inside and the given outer_rel
-  *      outside.    Returns an AppendPath comprising the best inner scans, or
-  *      NULL if there are no possible inner indexscans.
-  *
-  * Note that we currently consider only cheapest-total-cost.  It's not
-  * very clear what cheapest-startup-cost might mean for an AppendPath.
-  */
- static Path *
- best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
-                          RelOptInfo *outer_rel, JoinType jointype)
- {
-     int            parentRTindex = rel->relid;
-     List       *append_paths = NIL;
-     bool        found_indexscan = false;
-     ListCell   *l;
-
-     foreach(l, root->append_rel_list)
-     {
-         AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
-         int            childRTindex;
-         RelOptInfo *childrel;
-         Path       *index_cheapest_startup;
-         Path       *index_cheapest_total;
-
-         /* append_rel_list contains all append rels; ignore others */
-         if (appinfo->parent_relid != parentRTindex)
-             continue;
-
-         childRTindex = appinfo->child_relid;
-         childrel = find_base_rel(root, childRTindex);
-         Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
-
-         /*
-          * Check to see if child was rejected by constraint exclusion. If so,
-          * it will have a cheapest_total_path that's a "dummy" path.
-          */
-         if (IS_DUMMY_PATH(childrel->cheapest_total_path))
-             continue;            /* OK, we can ignore it */
-
-         /*
-          * Get the best innerjoin indexpaths (if any) for this child rel.
-          */
-         best_inner_indexscan(root, childrel, outer_rel, jointype,
-                              &index_cheapest_startup, &index_cheapest_total);
-
-         /*
-          * If no luck on an indexpath for this rel, we'll still consider an
-          * Append substituting the cheapest-total inner path.  However we must
-          * find at least one indexpath, else there's not going to be any
-          * improvement over the base path for the appendrel.
-          */
-         if (index_cheapest_total)
-             found_indexscan = true;
-         else
-             index_cheapest_total = childrel->cheapest_total_path;
-
-         append_paths = lappend(append_paths, index_cheapest_total);
-     }
-
-     if (!found_indexscan)
-         return NULL;
-
-     /* Form and return the completed Append path. */
-     return (Path *) create_append_path(rel, append_paths);
- }
-
- /*
   * select_mergejoin_clauses
   *      Select mergejoin clauses that are usable for a particular join.
   *      Returns a list of RestrictInfo nodes for those clauses.
--- 838,843 ----
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index d4cc567892da164fae658ef9baed253f7e2bf0bd..0b6c21dd9c2e7b0fc2a48487a033a5181b0bf85d 100644
*** a/src/backend/optimizer/path/orindxpath.c
--- b/src/backend/optimizer/path/orindxpath.c
*************** create_or_index_quals(PlannerInfo *root,
*** 123,129 ****
              orpaths = generate_bitmap_or_paths(root, rel,
                                                 list_make1(rinfo),
                                                 rel->baserestrictinfo,
!                                                NULL);

              /* Locate the cheapest OR path */
              foreach(k, orpaths)
--- 123,129 ----
              orpaths = generate_bitmap_or_paths(root, rel,
                                                 list_make1(rinfo),
                                                 rel->baserestrictinfo,
!                                                NULL, 1.0);

              /* Locate the cheapest OR path */
              foreach(k, orpaths)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 0ebdead6c84d48baf8f8c0fc93f2775e56ec3a2a..44ac629a9cf4b95e5c5ca7c7ef7c7c350fc8cc53 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** pathkeys_contained_in(List *keys1, List
*** 403,416 ****
  /*
   * get_cheapest_path_for_pathkeys
   *      Find the cheapest path (according to the specified criterion) that
!  *      satisfies the given pathkeys.  Return NULL if no such path.
   *
   * 'paths' is a list of possible paths that all generate the same relation
   * 'pathkeys' represents a required ordering (already canonicalized!)
   * 'cost_criterion' is STARTUP_COST or TOTAL_COST
   */
  Path *
  get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
                                 CostSelector cost_criterion)
  {
      Path       *matched_path = NULL;
--- 403,419 ----
  /*
   * get_cheapest_path_for_pathkeys
   *      Find the cheapest path (according to the specified criterion) that
!  *      satisfies the given pathkeys and parameterization.
!  *      Return NULL if no such path.
   *
   * 'paths' is a list of possible paths that all generate the same relation
   * 'pathkeys' represents a required ordering (already canonicalized!)
+  * 'required_outer' denotes allowable outer relations for parameterized paths
   * 'cost_criterion' is STARTUP_COST or TOTAL_COST
   */
  Path *
  get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
+                                Relids required_outer,
                                 CostSelector cost_criterion)
  {
      Path       *matched_path = NULL;
*************** get_cheapest_path_for_pathkeys(List *pat
*** 428,434 ****
              compare_path_costs(matched_path, path, cost_criterion) <= 0)
              continue;

!         if (pathkeys_contained_in(pathkeys, path->pathkeys))
              matched_path = path;
      }
      return matched_path;
--- 431,438 ----
              compare_path_costs(matched_path, path, cost_criterion) <= 0)
              continue;

!         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
!             bms_is_subset(path->required_outer, required_outer))
              matched_path = path;
      }
      return matched_path;
*************** get_cheapest_fractional_path_for_pathkey
*** 459,464 ****
--- 463,472 ----
      {
          Path       *path = (Path *) lfirst(l);

+         /* XXX for now, consider only unparameterized paths */
+         if (path->required_outer)
+             continue;
+
          /*
           * Since cost comparison is a lot cheaper than pathkey comparison, do
           * that first.
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index e41d2a6eb99a48cf47e2f95e2c4863f58e9098c2..975147f2f820c10fa661261b59c8b67e617690df 100644
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** create_unique_plan(PlannerInfo *root, Un
*** 932,938 ****
          long        numGroups;
          Oid           *groupOperators;

!         numGroups = (long) Min(best_path->rows, (double) LONG_MAX);

          /*
           * Get the hashable equality operators for the Agg node to use.
--- 932,938 ----
          long        numGroups;
          Oid           *groupOperators;

!         numGroups = (long) Min(best_path->path.rows, (double) LONG_MAX);

          /*
           * Get the hashable equality operators for the Agg node to use.
*************** create_unique_plan(PlannerInfo *root, Un
*** 1018,1024 ****
      }

      /* Adjust output size estimate (other fields should be OK already) */
!     plan->plan_rows = best_path->rows;

      return plan;
  }
--- 1018,1024 ----
      }

      /* Adjust output size estimate (other fields should be OK already) */
!     plan->plan_rows = best_path->path.rows;

      return plan;
  }
*************** create_indexscan_plan(PlannerInfo *root,
*** 1112,1118 ****
      fixed_indexorderbys = fix_indexorderby_references(root, best_path);

      /*
!      * If this is an innerjoin scan, the indexclauses will contain join
       * clauses that are not present in scan_clauses (since the passed-in value
       * is just the rel's baserestrictinfo list).  We must add these clauses to
       * scan_clauses to ensure they get checked.  In most cases we will remove
--- 1112,1118 ----
      fixed_indexorderbys = fix_indexorderby_references(root, best_path);

      /*
!      * If this is a parameterized scan, the indexclauses will contain join
       * clauses that are not present in scan_clauses (since the passed-in value
       * is just the rel's baserestrictinfo list).  We must add these clauses to
       * scan_clauses to ensure they get checked.  In most cases we will remove
*************** create_indexscan_plan(PlannerInfo *root,
*** 1122,1128 ****
       * Note: pointer comparison should be enough to determine RestrictInfo
       * matches.
       */
!     if (best_path->isjoininner)
          scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);

      /*
--- 1122,1128 ----
       * Note: pointer comparison should be enough to determine RestrictInfo
       * matches.
       */
!     if (best_path->path.required_outer)
          scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);

      /*
*************** create_indexscan_plan(PlannerInfo *root,
*** 1189,1195 ****
       * it'd break the comparisons to predicates above ... (or would it?  Those
       * wouldn't have outer refs)
       */
!     if (best_path->isjoininner)
      {
          stripped_indexquals = (List *)
              replace_nestloop_params(root, (Node *) stripped_indexquals);
--- 1189,1195 ----
       * it'd break the comparisons to predicates above ... (or would it?  Those
       * wouldn't have outer refs)
       */
!     if (best_path->path.required_outer)
      {
          stripped_indexquals = (List *)
              replace_nestloop_params(root, (Node *) stripped_indexquals);
*************** create_indexscan_plan(PlannerInfo *root,
*** 1221,1228 ****
                                              best_path->indexscandir);

      copy_path_costsize(&scan_plan->plan, &best_path->path);
-     /* use the indexscan-specific rows estimate, not the parent rel's */
-     scan_plan->plan.plan_rows = best_path->rows;

      return scan_plan;
  }
--- 1221,1226 ----
*************** create_bitmap_scan_plan(PlannerInfo *roo
*** 1258,1271 ****
      scan_clauses = extract_actual_clauses(scan_clauses, false);

      /*
!      * If this is a innerjoin scan, the indexclauses will contain join clauses
       * that are not present in scan_clauses (since the passed-in value is just
       * the rel's baserestrictinfo list).  We must add these clauses to
       * scan_clauses to ensure they get checked.  In most cases we will remove
       * the join clauses again below, but if a join clause contains a special
       * operator, we need to make sure it gets into the scan_clauses.
       */
!     if (best_path->isjoininner)
      {
          scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
      }
--- 1256,1269 ----
      scan_clauses = extract_actual_clauses(scan_clauses, false);

      /*
!      * If this is a parameterized scan, the indexclauses will contain join clauses
       * that are not present in scan_clauses (since the passed-in value is just
       * the rel's baserestrictinfo list).  We must add these clauses to
       * scan_clauses to ensure they get checked.  In most cases we will remove
       * the join clauses again below, but if a join clause contains a special
       * operator, we need to make sure it gets into the scan_clauses.
       */
!     if (best_path->path.required_outer)
      {
          scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
      }
*************** create_bitmap_scan_plan(PlannerInfo *roo
*** 1328,1335 ****
                                       baserelid);

      copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
-     /* use the indexscan-specific rows estimate, not the parent rel's */
-     scan_plan->scan.plan.plan_rows = best_path->rows;

      return scan_plan;
  }
--- 1326,1331 ----
*************** create_bitmap_subplan(PlannerInfo *root,
*** 1510,1516 ****
           * Replace outer-relation variables with nestloop params, but only
           * after doing the above comparisons to index predicates.
           */
!         if (ipath->isjoininner)
          {
              *qual = (List *)
                  replace_nestloop_params(root, (Node *) *qual);
--- 1506,1512 ----
           * Replace outer-relation variables with nestloop params, but only
           * after doing the above comparisons to index predicates.
           */
!         if (ipath->path.required_outer)
          {
              *qual = (List *)
                  replace_nestloop_params(root, (Node *) *qual);
*************** create_nestloop_plan(PlannerInfo *root,
*** 1883,1896 ****
      ListCell   *next;

      /*
!      * If the inner path is a nestloop inner indexscan, it might be using some
!      * of the join quals as index quals, in which case we don't have to check
!      * them again at the join node.  Remove any join quals that are redundant.
       */
      joinrestrictclauses =
!         select_nonredundant_join_clauses(root,
!                                          joinrestrictclauses,
!                                          best_path->innerjoinpath);

      /* Sort join qual clauses into best execution order */
      joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
--- 1879,1891 ----
      ListCell   *next;

      /*
!      * If the inner path is parameterized, it might have already used some of
!      * the join quals, in which case we don't have to check them again at the
!      * join node.  Remove any join quals that are redundant.
       */
      joinrestrictclauses =
!         select_nonredundant_join_clauses(joinrestrictclauses,
!                                          best_path->innerjoinpath->param_clauses);

      /* Sort join qual clauses into best execution order */
      joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
*************** copy_path_costsize(Plan *dest, Path *src
*** 2885,2891 ****
      {
          dest->startup_cost = src->startup_cost;
          dest->total_cost = src->total_cost;
!         dest->plan_rows = src->parent->rows;
          dest->plan_width = src->parent->width;
      }
      else
--- 2880,2886 ----
      {
          dest->startup_cost = src->startup_cost;
          dest->total_cost = src->total_cost;
!         dest->plan_rows = src->rows;
          dest->plan_width = src->parent->width;
      }
      else
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index b66a508c22da934e96771c99a0a5010dc6c64177..921262948bb8cc5b42c32170c447a0d8008bea34 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** plan_cluster_use_sort(Oid tableOid, Oid
*** 3297,3303 ****
      /* Estimate the cost of index scan */
      indexScanPath = create_index_path(root, indexInfo,
                                        NIL, NIL, NIL, NIL, NIL,
!                                       ForwardScanDirection, false, NULL);

      return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
  }
--- 3297,3304 ----
      /* Estimate the cost of index scan */
      indexScanPath = create_index_path(root, indexInfo,
                                        NIL, NIL, NIL, NIL, NIL,
!                                       ForwardScanDirection, false,
!                                       NULL, 1.0);

      return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
  }
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0ca161a31dc99a3ee7384f47dde75e3fcd628cb5..ace8ca020b34b1b89a9af1542e34c272b4b3495f 100644
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
***************
*** 23,28 ****
--- 23,29 ----
  #include "optimizer/cost.h"
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
+ #include "optimizer/restrictinfo.h"
  #include "optimizer/tlist.h"
  #include "parser/parsetree.h"
  #include "utils/lsyscache.h"
*************** compare_fractional_path_costs(Path *path
*** 166,171 ****
--- 167,174 ----
   *      Find the minimum-cost paths from among a relation's paths,
   *      and save them in the rel's cheapest-path fields.
   *
+  * Only unparameterized paths are considered candidates.
+  *
   * This is normally called only after we've finished constructing the path
   * list for the rel node.
   *
*************** compare_fractional_path_costs(Path *path
*** 177,199 ****
  void
  set_cheapest(RelOptInfo *parent_rel)
  {
-     List       *pathlist = parent_rel->pathlist;
-     ListCell   *p;
      Path       *cheapest_startup_path;
      Path       *cheapest_total_path;

      Assert(IsA(parent_rel, RelOptInfo));

!     if (pathlist == NIL)
!         elog(ERROR, "could not devise a query plan for the given query");
!
!     cheapest_startup_path = cheapest_total_path = (Path *) linitial(pathlist);

!     for_each_cell(p, lnext(list_head(pathlist)))
      {
          Path       *path = (Path *) lfirst(p);
          int            cmp;

          cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
          if (cmp > 0 ||
              (cmp == 0 &&
--- 180,208 ----
  void
  set_cheapest(RelOptInfo *parent_rel)
  {
      Path       *cheapest_startup_path;
      Path       *cheapest_total_path;
+     ListCell   *p;

      Assert(IsA(parent_rel, RelOptInfo));

!     cheapest_startup_path = cheapest_total_path = NULL;

!     foreach(p, parent_rel->pathlist)
      {
          Path       *path = (Path *) lfirst(p);
          int            cmp;

+         /* We only consider unparameterized paths here */
+         if (path->required_outer)
+             continue;
+
+         if (cheapest_total_path == NULL)
+         {
+             cheapest_startup_path = cheapest_total_path = path;
+             continue;
+         }
+
          cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
          if (cmp > 0 ||
              (cmp == 0 &&
*************** set_cheapest(RelOptInfo *parent_rel)
*** 209,214 ****
--- 218,226 ----
              cheapest_total_path = path;
      }

+     if (cheapest_total_path == NULL)
+         elog(ERROR, "could not devise a query plan for the given query");
+
      parent_rel->cheapest_startup_path = cheapest_startup_path;
      parent_rel->cheapest_total_path = cheapest_total_path;
      parent_rel->cheapest_unique_path = NULL;    /* computed only if needed */
*************** set_cheapest(RelOptInfo *parent_rel)
*** 219,229 ****
   *      Consider a potential implementation path for the specified parent rel,
   *      and add it to the rel's pathlist if it is worthy of consideration.
   *      A path is worthy if it has either a better sort order (better pathkeys)
!  *      or cheaper cost (on either dimension) than any of the existing old paths.
   *
   *      We also remove from the rel's pathlist any old paths that are dominated
!  *      by new_path --- that is, new_path is both cheaper and at least as well
!  *      ordered.
   *
   *      The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
   *      at the front.  No code depends on that for correctness; it's simply
--- 231,242 ----
   *      Consider a potential implementation path for the specified parent rel,
   *      and add it to the rel's pathlist if it is worthy of consideration.
   *      A path is worthy if it has either a better sort order (better pathkeys)
!  *      or cheaper cost (on either dimension) than any of the existing old paths
!  *      that have the same or subset required_outer rels.
   *
   *      We also remove from the rel's pathlist any old paths that are dominated
!  *      by new_path --- that is, new_path is cheaper, at least as well ordered,
!  *      and requires no outer rels not required by old path.
   *
   *      The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
   *      at the front.  No code depends on that for correctness; it's simply
*************** add_path(RelOptInfo *parent_rel, Path *n
*** 287,334 ****
          /*
           * If the two paths compare differently for startup and total cost,
           * then we want to keep both, and we can skip the (much slower)
!          * comparison of pathkeys.    If they compare the same, proceed with the
!          * pathkeys comparison.  Note: this test relies on the fact that
!          * compare_fuzzy_path_costs will only return 0 if both costs are
!          * effectively equal (and, therefore, there's no need to call it twice
!          * in that case).
           */
          if (costcmp == 0 ||
              costcmp == compare_fuzzy_path_costs(new_path, old_path,
                                                  STARTUP_COST))
          {
!             switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
              {
!                 case PATHKEYS_EQUAL:
!                     if (costcmp < 0)
!                         remove_old = true;        /* new dominates old */
!                     else if (costcmp > 0)
!                         accept_new = false;        /* old dominates new */
!                     else
!                     {
!                         /*
!                          * Same pathkeys, and fuzzily the same cost, so keep
!                          * just one --- but we'll do an exact cost comparison
!                          * to decide which.
!                          */
!                         if (compare_path_costs(new_path, old_path,
!                                                TOTAL_COST) < 0)
!                             remove_old = true;    /* new dominates old */
                          else
!                             accept_new = false; /* old equals or dominates new */
!                     }
!                     break;
!                 case PATHKEYS_BETTER1:
!                     if (costcmp <= 0)
!                         remove_old = true;        /* new dominates old */
!                     break;
!                 case PATHKEYS_BETTER2:
!                     if (costcmp >= 0)
!                         accept_new = false;        /* old dominates new */
!                     break;
!                 case PATHKEYS_DIFFERENT:
!                     /* keep both paths, since they have different ordering */
!                     break;
              }
          }

--- 300,369 ----
          /*
           * If the two paths compare differently for startup and total cost,
           * then we want to keep both, and we can skip the (much slower)
!          * comparisons of pathkeys and required_outer rels.  If they compare
!          * the same, proceed with the other comparisons.  Note: this test
!          * relies on the fact that compare_fuzzy_path_costs will only return 0
!          * if both costs are effectively equal (and, therefore, there's no
!          * need to call it twice in that case).
           */
          if (costcmp == 0 ||
              costcmp == compare_fuzzy_path_costs(new_path, old_path,
                                                  STARTUP_COST))
          {
!             BMS_Comparison outercmp;
!
!             /*
!              * Compare required outer rels.  If neither set is a subset of the
!              * other, neither path can dominate the other, so we keep both.
!              */
!             outercmp = bms_subset_compare(new_path->required_outer,
!                                           old_path->required_outer);
!             if (outercmp != BMS_DIFFERENT)
              {
!                 switch (compare_pathkeys(new_path->pathkeys,
!                                          old_path->pathkeys))
!                 {
!                     case PATHKEYS_EQUAL:
!                         if (costcmp < 0)
!                         {
!                             if (outercmp != BMS_SUBSET2)
!                                 remove_old = true; /* new dominates old */
!                         }
!                         else if (costcmp > 0)
!                         {
!                             if (outercmp != BMS_SUBSET1)
!                                 accept_new = false;    /* old dominates new */
!                         }
!                         else if (outercmp == BMS_SUBSET1)
!                             remove_old = true; /* new dominates old */
!                         else if (outercmp == BMS_SUBSET2)
!                             accept_new = false;    /* old dominates new */
                          else
!                         {
!                             /*
!                              * Same pathkeys and outer rels, and fuzzily the
!                              * same cost, so keep just one --- but we'll do an
!                              * exact cost comparison to decide which.
!                              */
!                             if (compare_path_costs(new_path, old_path,
!                                                    TOTAL_COST) < 0)
!                                 remove_old = true;    /* new dominates old */
!                             else
!                                 accept_new = false; /* old equals or dominates new */
!                         }
!                         break;
!                     case PATHKEYS_BETTER1:
!                         if (costcmp <= 0 && outercmp != BMS_SUBSET2)
!                             remove_old = true;        /* new dominates old */
!                         break;
!                     case PATHKEYS_BETTER2:
!                         if (costcmp >= 0 && outercmp != BMS_SUBSET1)
!                             accept_new = false;        /* old dominates new */
!                         break;
!                     case PATHKEYS_DIFFERENT:
!                         /* keep both, since they have different ordering */
!                         break;
!                 }
              }
          }

*************** create_seqscan_path(PlannerInfo *root, R
*** 398,403 ****
--- 433,440 ----

      pathnode->pathtype = T_SeqScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = NIL;    /* seqscan has unordered result */

      cost_seqscan(pathnode, root, rel);
*************** create_seqscan_path(PlannerInfo *root, R
*** 423,430 ****
   *            for an ordered index, or NoMovementScanDirection for
   *            an unordered index.
   * 'indexonly' is true if an index-only scan is wanted.
!  * 'outer_rel' is the outer relation if this is a join inner indexscan path.
!  *            (pathkeys and indexscandir are ignored if so.)    NULL if not.
   *
   * Returns the new path node.
   */
--- 460,468 ----
   *            for an ordered index, or NoMovementScanDirection for
   *            an unordered index.
   * 'indexonly' is true if an index-only scan is wanted.
!  * 'required_outer' is the set of outer relids referenced in indexclauses.
!  * 'loop_count' is the number of repetitions of the indexscan to factor into
!  *        estimates of caching behavior.
   *
   * Returns the new path node.
   */
*************** create_index_path(PlannerInfo *root,
*** 438,465 ****
                    List *pathkeys,
                    ScanDirection indexscandir,
                    bool indexonly,
!                   RelOptInfo *outer_rel)
  {
      IndexPath  *pathnode = makeNode(IndexPath);
      RelOptInfo *rel = index->rel;
      List       *indexquals,
                 *indexqualcols;

-     /*
-      * For a join inner scan, there's no point in marking the path with any
-      * pathkeys, since it will only ever be used as the inner path of a
-      * nestloop, and so its ordering does not matter.  For the same reason we
-      * don't really care what order it's scanned in.  (We could expect the
-      * caller to supply the correct values, but it's easier to force it here.)
-      */
-     if (outer_rel != NULL)
-     {
-         pathkeys = NIL;
-         indexscandir = NoMovementScanDirection;
-     }
-
      pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
      pathnode->path.parent = rel;
      pathnode->path.pathkeys = pathkeys;

      /* Convert clauses to indexquals the executor can handle */
--- 476,509 ----
                    List *pathkeys,
                    ScanDirection indexscandir,
                    bool indexonly,
!                   Relids required_outer,
!                   double loop_count)
  {
      IndexPath  *pathnode = makeNode(IndexPath);
      RelOptInfo *rel = index->rel;
      List       *indexquals,
                 *indexqualcols;

      pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = required_outer;
+     if (required_outer)
+     {
+         /* Identify index clauses that are join clauses */
+         List       *jclauses = NIL;
+         ListCell   *lc;
+
+         foreach(lc, indexclauses)
+         {
+             RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+
+             if (!bms_is_subset(rinfo->required_relids, rel->relids))
+                 jclauses = lappend(jclauses, rinfo);
+         }
+         pathnode->path.param_clauses = jclauses;
+     }
+     else
+         pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = pathkeys;

      /* Convert clauses to indexquals the executor can handle */
*************** create_index_path(PlannerInfo *root,
*** 473,522 ****
      pathnode->indexqualcols = indexqualcols;
      pathnode->indexorderbys = indexorderbys;
      pathnode->indexorderbycols = indexorderbycols;
-
-     pathnode->isjoininner = (outer_rel != NULL);
      pathnode->indexscandir = indexscandir;

!     if (outer_rel != NULL)
!     {
!         /*
!          * We must compute the estimated number of output rows for the
!          * indexscan.  This is less than rel->rows because of the additional
!          * selectivity of the join clauses.  Since indexclauses may contain
!          * both restriction and join clauses, we have to do a set union to get
!          * the full set of clauses that must be considered to compute the
!          * correct selectivity.  (Without the union operation, we might have
!          * some restriction clauses appearing twice, which'd mislead
!          * clauselist_selectivity into double-counting their selectivity.
!          * However, since RestrictInfo nodes aren't copied when linking them
!          * into different lists, it should be sufficient to use pointer
!          * comparison to remove duplicates.)
!          *
!          * Note that we force the clauses to be treated as non-join clauses
!          * during selectivity estimation.
!          */
!         List       *allclauses;
!
!         allclauses = list_union_ptr(rel->baserestrictinfo, indexclauses);
!         pathnode->rows = rel->tuples *
!             clauselist_selectivity(root,
!                                    allclauses,
!                                    rel->relid,    /* do not use 0! */
!                                    JOIN_INNER,
!                                    NULL);
!         /* Like costsize.c, force estimate to be at least one row */
!         pathnode->rows = clamp_row_est(pathnode->rows);
!     }
!     else
!     {
!         /*
!          * The number of rows is the same as the parent rel's estimate, since
!          * this isn't a join inner indexscan.
!          */
!         pathnode->rows = rel->rows;
!     }
!
!     cost_index(pathnode, root, outer_rel);

      return pathnode;
  }
--- 517,525 ----
      pathnode->indexqualcols = indexqualcols;
      pathnode->indexorderbys = indexorderbys;
      pathnode->indexorderbycols = indexorderbycols;
      pathnode->indexscandir = indexscandir;

!     cost_index(pathnode, root, loop_count);

      return pathnode;
  }
*************** create_index_path(PlannerInfo *root,
*** 526,580 ****
   *      Creates a path node for a bitmap scan.
   *
   * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
   *
!  * If this is a join inner indexscan path, 'outer_rel' is the outer relation,
!  * and all the component IndexPaths should have been costed accordingly.
   */
  BitmapHeapPath *
  create_bitmap_heap_path(PlannerInfo *root,
                          RelOptInfo *rel,
                          Path *bitmapqual,
!                         RelOptInfo *outer_rel)
  {
      BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);

      pathnode->path.pathtype = T_BitmapHeapScan;
      pathnode->path.parent = rel;
!     pathnode->path.pathkeys = NIL;        /* always unordered */
!
!     pathnode->bitmapqual = bitmapqual;
!     pathnode->isjoininner = (outer_rel != NULL);
!
!     if (pathnode->isjoininner)
      {
!         /*
!          * We must compute the estimated number of output rows for the
!          * indexscan.  This is less than rel->rows because of the additional
!          * selectivity of the join clauses.  We make use of the selectivity
!          * estimated for the bitmap to do this; this isn't really quite right
!          * since there may be restriction conditions not included in the
!          * bitmap ...
!          */
!         Cost        indexTotalCost;
!         Selectivity indexSelectivity;

!         cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
!         pathnode->rows = rel->tuples * indexSelectivity;
!         if (pathnode->rows > rel->rows)
!             pathnode->rows = rel->rows;
!         /* Like costsize.c, force estimate to be at least one row */
!         pathnode->rows = clamp_row_est(pathnode->rows);
      }
      else
!     {
!         /*
!          * The number of rows is the same as the parent rel's estimate, since
!          * this isn't a join inner indexscan.
!          */
!         pathnode->rows = rel->rows;
!     }

!     cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, outer_rel);

      return pathnode;
  }
--- 529,579 ----
   *      Creates a path node for a bitmap scan.
   *
   * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
+  * 'required_outer' is the set of outer relids referenced in indexclauses.
+  * 'loop_count' is the number of repetitions of the indexscan to factor into
+  *        estimates of caching behavior.
   *
!  * required_outer and loop_count should match the values used when creating
!  * the component IndexPaths.
   */
  BitmapHeapPath *
  create_bitmap_heap_path(PlannerInfo *root,
                          RelOptInfo *rel,
                          Path *bitmapqual,
!                         Relids required_outer,
!                         double loop_count)
  {
      BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);

      pathnode->path.pathtype = T_BitmapHeapScan;
      pathnode->path.parent = rel;
!     pathnode->path.required_outer = required_outer;
!     if (required_outer)
      {
!         /* Identify index clauses that are join clauses */
!         List       *jclauses = NIL;
!         List       *bitmapclauses;
!         ListCell   *lc;

!         bitmapclauses = make_restrictinfo_from_bitmapqual(bitmapqual,
!                                                           true,
!                                                           false);
!         foreach(lc, bitmapclauses)
!         {
!             RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
!
!             if (!bms_is_subset(rinfo->required_relids, rel->relids))
!                 jclauses = lappend(jclauses, rinfo);
!         }
!         pathnode->path.param_clauses = jclauses;
      }
      else
!         pathnode->path.param_clauses = NIL;
!     pathnode->path.pathkeys = NIL;        /* always unordered */

!     pathnode->bitmapqual = bitmapqual;
!
!     cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, loop_count);

      return pathnode;
  }
*************** create_bitmap_and_path(PlannerInfo *root
*** 592,597 ****
--- 591,598 ----

      pathnode->path.pathtype = T_BitmapAnd;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL;
+     pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = NIL;        /* always unordered */

      pathnode->bitmapquals = bitmapquals;
*************** create_bitmap_or_path(PlannerInfo *root,
*** 615,620 ****
--- 616,623 ----

      pathnode->path.pathtype = T_BitmapOr;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL;
+     pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = NIL;        /* always unordered */

      pathnode->bitmapquals = bitmapquals;
*************** create_tidscan_path(PlannerInfo *root, R
*** 636,641 ****
--- 639,646 ----

      pathnode->path.pathtype = T_TidScan;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL;
+     pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = NIL;

      pathnode->tidquals = tidquals;
*************** create_append_path(RelOptInfo *rel, List
*** 660,685 ****

      pathnode->path.pathtype = T_Append;
      pathnode->path.parent = rel;
      pathnode->path.pathkeys = NIL;        /* result is always considered
                                           * unsorted */
      pathnode->subpaths = subpaths;

      /*
!      * Compute cost as sum of subplan costs.  We charge nothing extra for the
!      * Append itself, which perhaps is too optimistic, but since it doesn't do
!      * any selection or projection, it is a pretty cheap node.
       *
!      * If you change this, see also make_append().
       */
      pathnode->path.startup_cost = 0;
      pathnode->path.total_cost = 0;
      foreach(l, subpaths)
      {
          Path       *subpath = (Path *) lfirst(l);

          if (l == list_head(subpaths))    /* first node? */
              pathnode->path.startup_cost = subpath->startup_cost;
          pathnode->path.total_cost += subpath->total_cost;
      }

      return pathnode;
--- 665,712 ----

      pathnode->path.pathtype = T_Append;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL; /* updated below */
+     pathnode->path.param_clauses = NIL;    /* XXX see below */
      pathnode->path.pathkeys = NIL;        /* result is always considered
                                           * unsorted */
      pathnode->subpaths = subpaths;

      /*
!      * We don't bother with inventing a cost_append(), but just do it here.
       *
!      * Compute rows and costs as sums of subplan rows and costs.  We charge
!      * nothing extra for the Append itself, which perhaps is too optimistic,
!      * but since it doesn't do any selection or projection, it is a pretty
!      * cheap node.  If you change this, see also make_append().
!      *
!      * We also compute the correct required_outer set, namely the union of
!      * the input paths' requirements.
!      *
!      * XXX We should also compute a proper param_clauses list, but that
!      * will require identifying which joinclauses are enforced by all the
!      * subplans, as well as locating the original parent RestrictInfo from
!      * which they were generated.  For the moment we punt and leave the list
!      * as NIL.  This will result in uselessly rechecking such joinclauses
!      * at the parameter-supplying nestloop join, which is slightly annoying,
!      * as well as overestimating the sizes of any intermediate joins, which
!      * is significantly more annoying.
       */
+     pathnode->path.rows = 0;
      pathnode->path.startup_cost = 0;
      pathnode->path.total_cost = 0;
      foreach(l, subpaths)
      {
          Path       *subpath = (Path *) lfirst(l);

+         pathnode->path.rows += subpath->rows;
+
          if (l == list_head(subpaths))    /* first node? */
              pathnode->path.startup_cost = subpath->startup_cost;
          pathnode->path.total_cost += subpath->total_cost;
+
+         pathnode->path.required_outer =
+             bms_add_members(pathnode->path.required_outer,
+                             subpath->required_outer);
      }

      return pathnode;
*************** create_merge_append_path(PlannerInfo *ro
*** 703,708 ****
--- 730,737 ----

      pathnode->path.pathtype = T_MergeAppend;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL; /* updated below */
+     pathnode->path.param_clauses = NIL;    /* XXX see below */
      pathnode->path.pathkeys = pathkeys;
      pathnode->subpaths = subpaths;

*************** create_merge_append_path(PlannerInfo *ro
*** 735,747 ****
          }
      }

!     /* Add up all the costs of the input paths */
      input_startup_cost = 0;
      input_total_cost = 0;
      foreach(l, subpaths)
      {
          Path       *subpath = (Path *) lfirst(l);

          if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
          {
              /* Subpath is adequately ordered, we won't need to sort it */
--- 764,785 ----
          }
      }

!     /*
!      * Add up the sizes and costs of the input paths, and also compute the
!      * real required_outer value.
!      *
!      * XXX as in create_append_path(), we should compute param_clauses but
!      * it will require more work.
!      */
!     pathnode->path.rows = 0;
      input_startup_cost = 0;
      input_total_cost = 0;
      foreach(l, subpaths)
      {
          Path       *subpath = (Path *) lfirst(l);

+         pathnode->path.rows += subpath->rows;
+
          if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
          {
              /* Subpath is adequately ordered, we won't need to sort it */
*************** create_merge_append_path(PlannerInfo *ro
*** 765,770 ****
--- 803,812 ----
              input_startup_cost += sort_path.startup_cost;
              input_total_cost += sort_path.total_cost;
          }
+
+         pathnode->path.required_outer =
+             bms_add_members(pathnode->path.required_outer,
+                             subpath->required_outer);
      }

      /* Now we can compute total costs of the MergeAppend */
*************** create_result_path(List *quals)
*** 788,797 ****

      pathnode->path.pathtype = T_Result;
      pathnode->path.parent = NULL;
      pathnode->path.pathkeys = NIL;
      pathnode->quals = quals;

!     /* Ideally should define cost_result(), but I'm too lazy */
      pathnode->path.startup_cost = 0;
      pathnode->path.total_cost = cpu_tuple_cost;

--- 830,842 ----

      pathnode->path.pathtype = T_Result;
      pathnode->path.parent = NULL;
+     pathnode->path.required_outer = NULL;
+     pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = NIL;
      pathnode->quals = quals;

!     /* Hardly worth defining a cost_result() function ... just do it */
!     pathnode->path.rows = 1;
      pathnode->path.startup_cost = 0;
      pathnode->path.total_cost = cpu_tuple_cost;

*************** create_material_path(RelOptInfo *rel, Pa
*** 817,823 ****

      pathnode->path.pathtype = T_Material;
      pathnode->path.parent = rel;
!
      pathnode->path.pathkeys = subpath->pathkeys;

      pathnode->subpath = subpath;
--- 862,869 ----

      pathnode->path.pathtype = T_Material;
      pathnode->path.parent = rel;
!     pathnode->path.required_outer = subpath->required_outer;
!     pathnode->path.param_clauses = subpath->param_clauses;
      pathnode->path.pathkeys = subpath->pathkeys;

      pathnode->subpath = subpath;
*************** create_material_path(RelOptInfo *rel, Pa
*** 825,831 ****
      cost_material(&pathnode->path,
                    subpath->startup_cost,
                    subpath->total_cost,
!                   rel->rows,
                    rel->width);

      return pathnode;
--- 871,877 ----
      cost_material(&pathnode->path,
                    subpath->startup_cost,
                    subpath->total_cost,
!                   subpath->rows,
                    rel->width);

      return pathnode;
*************** create_unique_path(PlannerInfo *root, Re
*** 874,880 ****
      /*
       * We must ensure path struct and subsidiary data are allocated in main
       * planning context; otherwise GEQO memory management causes trouble.
-      * (Compare best_inner_indexscan().)
       */
      oldcontext = MemoryContextSwitchTo(root->planner_cxt);

--- 920,925 ----
*************** create_unique_path(PlannerInfo *root, Re
*** 1026,1031 ****
--- 1071,1078 ----

      pathnode->path.pathtype = T_Unique;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = subpath->required_outer;
+     pathnode->path.param_clauses = subpath->param_clauses;

      /*
       * Assume the output is unsorted, since we don't necessarily have pathkeys
*************** create_unique_path(PlannerInfo *root, Re
*** 1048,1054 ****
                                        uniq_exprs, in_operators))
      {
          pathnode->umethod = UNIQUE_PATH_NOOP;
!         pathnode->rows = rel->rows;
          pathnode->path.startup_cost = subpath->startup_cost;
          pathnode->path.total_cost = subpath->total_cost;
          pathnode->path.pathkeys = subpath->pathkeys;
--- 1095,1101 ----
                                        uniq_exprs, in_operators))
      {
          pathnode->umethod = UNIQUE_PATH_NOOP;
!         pathnode->path.rows = rel->rows;
          pathnode->path.startup_cost = subpath->startup_cost;
          pathnode->path.total_cost = subpath->total_cost;
          pathnode->path.pathkeys = subpath->pathkeys;
*************** create_unique_path(PlannerInfo *root, Re
*** 1081,1087 ****
                                    sub_tlist_colnos, in_operators))
          {
              pathnode->umethod = UNIQUE_PATH_NOOP;
!             pathnode->rows = rel->rows;
              pathnode->path.startup_cost = subpath->startup_cost;
              pathnode->path.total_cost = subpath->total_cost;
              pathnode->path.pathkeys = subpath->pathkeys;
--- 1128,1134 ----
                                    sub_tlist_colnos, in_operators))
          {
              pathnode->umethod = UNIQUE_PATH_NOOP;
!             pathnode->path.rows = rel->rows;
              pathnode->path.startup_cost = subpath->startup_cost;
              pathnode->path.total_cost = subpath->total_cost;
              pathnode->path.pathkeys = subpath->pathkeys;
*************** create_unique_path(PlannerInfo *root, Re
*** 1095,1101 ****
      }

      /* Estimate number of output rows */
!     pathnode->rows = estimate_num_groups(root, uniq_exprs, rel->rows);
      numCols = list_length(uniq_exprs);

      if (all_btree)
--- 1142,1148 ----
      }

      /* Estimate number of output rows */
!     pathnode->path.rows = estimate_num_groups(root, uniq_exprs, rel->rows);
      numCols = list_length(uniq_exprs);

      if (all_btree)
*************** create_unique_path(PlannerInfo *root, Re
*** 1128,1139 ****
           */
          int            hashentrysize = rel->width + 64;

!         if (hashentrysize * pathnode->rows > work_mem * 1024L)
              all_hash = false;    /* don't try to hash */
          else
              cost_agg(&agg_path, root,
                       AGG_HASHED, NULL,
!                      numCols, pathnode->rows,
                       subpath->startup_cost,
                       subpath->total_cost,
                       rel->rows);
--- 1175,1186 ----
           */
          int            hashentrysize = rel->width + 64;

!         if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
              all_hash = false;    /* don't try to hash */
          else
              cost_agg(&agg_path, root,
                       AGG_HASHED, NULL,
!                      numCols, pathnode->path.rows,
                       subpath->startup_cost,
                       subpath->total_cost,
                       rel->rows);
*************** create_subqueryscan_path(RelOptInfo *rel
*** 1366,1371 ****
--- 1413,1420 ----

      pathnode->pathtype = T_SubqueryScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = pathkeys;

      cost_subqueryscan(pathnode, rel);
*************** create_functionscan_path(PlannerInfo *ro
*** 1385,1390 ****
--- 1434,1441 ----

      pathnode->pathtype = T_FunctionScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = NIL;    /* for now, assume unordered result */

      cost_functionscan(pathnode, root, rel);
*************** create_valuesscan_path(PlannerInfo *root
*** 1404,1409 ****
--- 1455,1462 ----

      pathnode->pathtype = T_ValuesScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = NIL;    /* result is always unordered */

      cost_valuesscan(pathnode, root, rel);
*************** create_ctescan_path(PlannerInfo *root, R
*** 1423,1428 ****
--- 1476,1483 ----

      pathnode->pathtype = T_CteScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = NIL;    /* XXX for now, result is always unordered */

      cost_ctescan(pathnode, root, rel);
*************** create_worktablescan_path(PlannerInfo *r
*** 1442,1447 ****
--- 1497,1504 ----

      pathnode->pathtype = T_WorkTableScan;
      pathnode->parent = rel;
+     pathnode->required_outer = NULL;
+     pathnode->param_clauses = NIL;
      pathnode->pathkeys = NIL;    /* result is always unordered */

      /* Cost is the same as for a regular CTE scan */
*************** create_foreignscan_path(PlannerInfo *roo
*** 1465,1470 ****
--- 1522,1529 ----

      pathnode->path.pathtype = T_ForeignScan;
      pathnode->path.parent = rel;
+     pathnode->path.required_outer = NULL;
+     pathnode->path.param_clauses = NIL;
      pathnode->path.pathkeys = NIL;        /* result is always unordered */

      /* Get FDW's callback info */
*************** create_foreignscan_path(PlannerInfo *roo
*** 1479,1484 ****
--- 1538,1544 ----
      pathnode->fdwplan = fdwplan;

      /* use costs estimated by FDW */
+     pathnode->path.rows = rel->rows;
      pathnode->path.startup_cost = fdwplan->startup_cost;
      pathnode->path.total_cost = fdwplan->total_cost;

*************** create_nestloop_path(PlannerInfo *root,
*** 1514,1519 ****
--- 1574,1608 ----

      pathnode->path.pathtype = T_NestLoop;
      pathnode->path.parent = joinrel;
+     /* inner_path can require rels from outer path, but not vice versa */
+     Assert(!bms_overlap(outer_path->required_outer,
+                         inner_path->parent->relids));
+     pathnode->path.required_outer =
+         bms_del_members(bms_union(outer_path->required_outer,
+                                   inner_path->required_outer),
+                         outer_path->parent->relids);
+     /* maintain invariant that required_outer is exactly NULL if empty */
+     if (bms_is_empty(pathnode->path.required_outer))
+         pathnode->path.required_outer = NULL;
+     if (pathnode->path.required_outer)
+     {
+         /* Identify parameter clauses not yet applied here */
+         List       *jclauses;
+         ListCell   *lc;
+
+         /* LHS clauses could not be satisfied here */
+         jclauses = list_copy(outer_path->param_clauses);
+         foreach(lc, inner_path->param_clauses)
+         {
+             RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+
+             if (!bms_is_subset(rinfo->required_relids, joinrel->relids))
+                 jclauses = lappend(jclauses, rinfo);
+         }
+         pathnode->path.param_clauses = jclauses;
+     }
+     else
+         pathnode->path.param_clauses = NIL;
      pathnode->jointype = jointype;
      pathnode->outerjoinpath = outer_path;
      pathnode->innerjoinpath = inner_path;
*************** create_mergejoin_path(PlannerInfo *root,
*** 1570,1575 ****
--- 1659,1674 ----

      pathnode->jpath.path.pathtype = T_MergeJoin;
      pathnode->jpath.path.parent = joinrel;
+     /* neither path can require rels from the other */
+     Assert(!bms_overlap(outer_path->required_outer,
+                         inner_path->parent->relids));
+     Assert(!bms_overlap(inner_path->required_outer,
+                         outer_path->parent->relids));
+     pathnode->jpath.path.required_outer =
+         bms_union(outer_path->required_outer, inner_path->required_outer);
+     pathnode->jpath.path.param_clauses =
+         list_concat(list_copy(outer_path->param_clauses),
+                     inner_path->param_clauses);
      pathnode->jpath.jointype = jointype;
      pathnode->jpath.outerjoinpath = outer_path;
      pathnode->jpath.innerjoinpath = inner_path;
*************** create_hashjoin_path(PlannerInfo *root,
*** 1612,1617 ****
--- 1711,1726 ----

      pathnode->jpath.path.pathtype = T_HashJoin;
      pathnode->jpath.path.parent = joinrel;
+     /* neither path can require rels from the other */
+     Assert(!bms_overlap(outer_path->required_outer,
+                         inner_path->parent->relids));
+     Assert(!bms_overlap(inner_path->required_outer,
+                         outer_path->parent->relids));
+     pathnode->jpath.path.required_outer =
+         bms_union(outer_path->required_outer, inner_path->required_outer);
+     pathnode->jpath.path.param_clauses =
+         list_concat(list_copy(outer_path->param_clauses),
+                     inner_path->param_clauses);
      pathnode->jpath.jointype = jointype;
      pathnode->jpath.outerjoinpath = outer_path;
      pathnode->jpath.innerjoinpath = inner_path;
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index d9c96020f14d650987f2b470da397dfa2ac17cb1..7d03d91f5d3b6f90de576021542fea9b21ca4122 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
*************** static Expr *make_sub_restrictinfos(Expr
*** 33,40 ****
                         bool pseudoconstant,
                         Relids required_relids,
                         Relids nullable_relids);
- static List *select_nonredundant_join_list(List *restrictinfo_list,
-                               List *reference_list);
  static bool join_clause_is_redundant(RestrictInfo *rinfo,
                           List *reference_list);

--- 33,38 ----
*************** extract_actual_join_clauses(List *restri
*** 623,633 ****

  /*
   * select_nonredundant_join_clauses
   *
   * Given a list of RestrictInfo clauses that are to be applied in a join,
!  * select the ones that are not redundant with any clause that's enforced
!  * by the inner_path.  This is used for nestloop joins, wherein any clause
!  * being used in an inner indexscan need not be checked again at the join.
   *
   * "Redundant" means either equal() or derived from the same EquivalenceClass.
   * We have to check the latter because indxpath.c may select different derived
--- 621,634 ----

  /*
   * select_nonredundant_join_clauses
+  *        Select the members of restrictinfo_list that are not redundant with
+  *        any member of reference_list.
   *
   * Given a list of RestrictInfo clauses that are to be applied in a join,
!  * select the ones that are not redundant with any clause that's listed in
!  * reference_list.  This is used, for example, to avoid checking joinclauses
!  * again at a nestloop join when they've already been enforced by a
!  * parameterized inner path.
   *
   * "Redundant" means either equal() or derived from the same EquivalenceClass.
   * We have to check the latter because indxpath.c may select different derived
*************** extract_actual_join_clauses(List *restri
*** 637,714 ****
   * restrictinfo_list; that should have been handled elsewhere.
   */
  List *
! select_nonredundant_join_clauses(PlannerInfo *root,
!                                  List *restrictinfo_list,
!                                  Path *inner_path)
! {
!     if (IsA(inner_path, IndexPath))
!     {
!         /*
!          * Check the index quals to see if any of them are join clauses.
!          *
!          * We can skip this if the index path is an ordinary indexpath and not
!          * a special innerjoin path, since it then wouldn't be using any join
!          * clauses.
!          */
!         IndexPath  *innerpath = (IndexPath *) inner_path;
!
!         if (innerpath->isjoininner)
!             restrictinfo_list =
!                 select_nonredundant_join_list(restrictinfo_list,
!                                               innerpath->indexclauses);
!     }
!     else if (IsA(inner_path, BitmapHeapPath))
!     {
!         /*
!          * Same deal for bitmapped index scans.
!          *
!          * Note: both here and above, we ignore any implicit index
!          * restrictions associated with the use of partial indexes.  This is
!          * OK because we're only trying to prove we can dispense with some
!          * join quals; failing to prove that doesn't result in an incorrect
!          * plan.  It's quite unlikely that a join qual could be proven
!          * redundant by an index predicate anyway.    (Also, if we did manage to
!          * prove it, we'd have to have a special case for update targets; see
!          * notes about EvalPlanQual testing in create_indexscan_plan().)
!          */
!         BitmapHeapPath *innerpath = (BitmapHeapPath *) inner_path;
!
!         if (innerpath->isjoininner)
!         {
!             List       *bitmapclauses;
!
!             bitmapclauses =
!                 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
!                                                   true,
!                                                   false);
!             restrictinfo_list =
!                 select_nonredundant_join_list(restrictinfo_list,
!                                               bitmapclauses);
!         }
!     }
!
!     /*
!      * XXX the inner path of a nestloop could also be an append relation whose
!      * elements use join quals.  However, they might each use different quals;
!      * we could only remove join quals that are enforced by all the appendrel
!      * members.  For the moment we don't bother to try.
!      */
!
!     return restrictinfo_list;
! }
!
! /*
!  * select_nonredundant_join_list
!  *        Select the members of restrictinfo_list that are not redundant with
!  *        any member of reference_list.  See above for more info.
!  */
! static List *
! select_nonredundant_join_list(List *restrictinfo_list,
!                               List *reference_list)
  {
      List       *result = NIL;
      ListCell   *item;

      foreach(item, restrictinfo_list)
      {
          RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
--- 638,653 ----
   * restrictinfo_list; that should have been handled elsewhere.
   */
  List *
! select_nonredundant_join_clauses(List *restrictinfo_list,
!                                  List *reference_list)
  {
      List       *result = NIL;
      ListCell   *item;

+     /* Quick out if nothing could be removed */
+     if (reference_list == NIL)
+         return restrictinfo_list;
+
      foreach(item, restrictinfo_list)
      {
          RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index da638f885aa5c381220f0e53688dd48d52cd86bf..09c9240490218b0525389465d6f4db6d46498cff 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** string_to_bytea_const(const char *str, s
*** 5971,5977 ****
  static void
  genericcostestimate(PlannerInfo *root,
                      IndexPath *path,
!                     RelOptInfo *outer_rel,
                      double numIndexTuples,
                      Cost *indexStartupCost,
                      Cost *indexTotalCost,
--- 5971,5977 ----
  static void
  genericcostestimate(PlannerInfo *root,
                      IndexPath *path,
!                     double loop_count,
                      double numIndexTuples,
                      Cost *indexStartupCost,
                      Cost *indexTotalCost,
*************** genericcostestimate(PlannerInfo *root,
*** 6119,6134 ****
       * Note that we are counting pages not tuples anymore, so we take N = T =
       * index size, as if there were one "tuple" per page.
       */
!     if (outer_rel != NULL && outer_rel->rows > 1)
!     {
!         num_outer_scans = outer_rel->rows;
!         num_scans = num_sa_scans * num_outer_scans;
!     }
!     else
!     {
!         num_outer_scans = 1;
!         num_scans = num_sa_scans;
!     }

      if (num_scans > 1)
      {
--- 6119,6126 ----
       * Note that we are counting pages not tuples anymore, so we take N = T =
       * index size, as if there were one "tuple" per page.
       */
!     num_outer_scans = loop_count;
!     num_scans = num_sa_scans * num_outer_scans;

      if (num_scans > 1)
      {
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6234,6240 ****
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
--- 6226,6232 ----
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     double        loop_count = PG_GETARG_FLOAT8(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6410,6416 ****
          numIndexTuples = rint(numIndexTuples / num_sa_scans);
      }

!     genericcostestimate(root, path, outer_rel,
                          numIndexTuples,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);
--- 6402,6408 ----
          numIndexTuples = rint(numIndexTuples / num_sa_scans);
      }

!     genericcostestimate(root, path, loop_count,
                          numIndexTuples,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);
*************** hashcostestimate(PG_FUNCTION_ARGS)
*** 6527,6539 ****
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, outer_rel, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

--- 6519,6531 ----
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     double        loop_count = PG_GETARG_FLOAT8(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, loop_count, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

*************** gistcostestimate(PG_FUNCTION_ARGS)
*** 6545,6557 ****
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, outer_rel, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

--- 6537,6549 ----
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     double        loop_count = PG_GETARG_FLOAT8(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, loop_count, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

*************** spgcostestimate(PG_FUNCTION_ARGS)
*** 6563,6575 ****
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, outer_rel, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

--- 6555,6567 ----
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     double        loop_count = PG_GETARG_FLOAT8(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
      double       *indexCorrelation = (double *) PG_GETARG_POINTER(6);

!     genericcostestimate(root, path, loop_count, 0.0,
                          indexStartupCost, indexTotalCost,
                          indexSelectivity, indexCorrelation);

*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6884,6890 ****
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
--- 6876,6882 ----
  {
      PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
      IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
!     double        loop_count = PG_GETARG_FLOAT8(2);
      Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
      Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
      Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 7051,7060 ****
      }

      /* Will we have more than one iteration of a nestloop scan? */
!     if (outer_rel != NULL && outer_rel->rows > 1)
!         outer_scans = outer_rel->rows;
!     else
!         outer_scans = 1;

      /*
       * Compute cost to begin scan, first of all, pay attention to pending list.
--- 7043,7049 ----
      }

      /* Will we have more than one iteration of a nestloop scan? */
!     outer_scans = loop_count;

      /*
       * Compute cost to begin scan, first of all, pay attention to pending list.
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 8fdbd72d3525ddde33d24051e228005be4ec9527..bcca70d2b9817ca0d05f2a90e0c898ff0c48b1b6 100644
*** a/src/include/nodes/bitmapset.h
--- b/src/include/nodes/bitmapset.h
*************** typedef struct Bitmapset
*** 36,41 ****
--- 36,50 ----
  } Bitmapset;                    /* VARIABLE LENGTH STRUCT */


+ /* result of bms_subset_compare */
+ typedef enum
+ {
+     BMS_EQUAL,                    /* sets are equal */
+     BMS_SUBSET1,                /* first set is a subset of the second */
+     BMS_SUBSET2,                /* second set is a subset of the first */
+     BMS_DIFFERENT                /* neither set is a subset of the other */
+ } BMS_Comparison;
+
  /* result of bms_membership */
  typedef enum
  {
*************** extern Bitmapset *bms_union(const Bitmap
*** 58,63 ****
--- 67,73 ----
  extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
  extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
  extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
+ extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
  extern bool bms_is_member(int x, const Bitmapset *a);
  extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
  extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 94657d2aaa1aacc4ee04160833298c7af7e585fa..27cbef5e3823099e5a92971e5e6cd95b6beb3587 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct EquivalenceMember
*** 609,615 ****
   * BTGreaterStrategyNumber (for DESC).    We assume that all ordering-capable
   * index types will use btree-compatible strategy numbers.
   */
-
  typedef struct PathKey
  {
      NodeTag        type;
--- 609,614 ----
*************** typedef struct PathKey
*** 625,650 ****
   * simple plan types that we don't need any extra information in the path for.
   * For other path types it is the first component of a larger struct.
   *
!  * Note: "pathtype" is the NodeTag of the Plan node we could build from this
!  * Path.  It is partially redundant with the Path's NodeTag, but allows us
!  * to use the same Path type for multiple Plan types where there is no need
!  * to distinguish the Plan type during path processing.
   */
-
  typedef struct Path
  {
      NodeTag        type;

      NodeTag        pathtype;        /* tag identifying scan/join method */
-
      RelOptInfo *parent;            /* the relation this path can build */
!
      /* estimated execution costs for path (see costsize.c for more info) */
      Cost        startup_cost;    /* cost expended before fetching any tuples */
      Cost        total_cost;        /* total cost (assuming all tuples fetched) */
-
-     List       *pathkeys;        /* sort ordering of path's output */
-     /* pathkeys is a List of PathKey nodes; see above */
  } Path;

  /*----------
--- 624,667 ----
   * simple plan types that we don't need any extra information in the path for.
   * For other path types it is the first component of a larger struct.
   *
!  * "pathtype" is the NodeTag of the Plan node we could build from this Path.
!  * It is partially redundant with the Path's NodeTag, but allows us to use
!  * the same Path type for multiple Plan types when there is no need to
!  * distinguish the Plan type during path processing.
!  *
!  * "required_outer", if not NULL, contains the relids of one or more relations
!  * that must provide parameter values to each scan of this path, because the
!  * path relies on join clauses using those rels. That means this path can only
!  * be joined to those rels by means of nestloop joins with this path on the
!  * inside.  Note: for a normal unparameterized path, required_outer must be
!  * NULL, not an empty-but-not-null Bitmapset.
!  *
!  * "param_clauses" is a List of RestrictInfo nodes, containing the join
!  * clauses used by a parameterized path.  Ideally param_clauses should be NIL
!  * if and only if required_outer is NULL.  XXX for the moment, however, we do
!  * not compute param_clauses for Append and MergeAppend paths, so the list
!  * is inaccurate in those paths and possibly paths above them.
!  *
!  * "pathkeys" is a List of PathKey nodes (see above), describing the sort
!  * ordering of the path's output rows.
!  *
!  * "rows" is the same as parent->rows in simple paths, but in parameterized
!  * paths and UniquePaths it can be less than parent->rows, reflecting the
!  * fact that we've filtered by extra join conditions or removed duplicates.
   */
  typedef struct Path
  {
      NodeTag        type;

      NodeTag        pathtype;        /* tag identifying scan/join method */
      RelOptInfo *parent;            /* the relation this path can build */
!     Relids        required_outer;    /* rels supplying parameters used by path */
!     List       *param_clauses;    /* join clauses that use such parameters */
!     List       *pathkeys;        /* sort ordering of path's output */
!     double        rows;            /* estimated number of result tuples */
      /* estimated execution costs for path (see costsize.c for more info) */
      Cost        startup_cost;    /* cost expended before fetching any tuples */
      Cost        total_cost;        /* total cost (assuming all tuples fetched) */
  } Path;

  /*----------
*************** typedef struct Path
*** 685,696 ****
   * ORDER BY expression is meant to be used with.  (There is no restriction
   * on which index column each ORDER BY can be used with.)
   *
-  * 'isjoininner' is TRUE if the path is a nestloop inner scan (that is,
-  * some of the index conditions are join rather than restriction clauses).
-  * Note that the path costs will be calculated differently from a plain
-  * indexscan in this case, and in addition there's a special 'rows' value
-  * different from the parent RelOptInfo's (see below).
-  *
   * 'indexscandir' is one of:
   *        ForwardScanDirection: forward scan of an ordered index
   *        BackwardScanDirection: backward scan of an ordered index
--- 702,707 ----
*************** typedef struct Path
*** 703,714 ****
   * we need not recompute them when considering using the same index in a
   * bitmap index/heap scan (see BitmapHeapPath).  The costs of the IndexPath
   * itself represent the costs of an IndexScan or IndexOnlyScan plan type.
-  *
-  * 'rows' is the estimated result tuple count for the indexscan.  This
-  * is the same as path.parent->rows for a simple indexscan, but it is
-  * different for a nestloop inner scan, because the additional indexquals
-  * coming from join clauses make the scan more selective than the parent
-  * rel's restrict clauses alone would do.
   *----------
   */
  typedef struct IndexPath
--- 714,719 ----
*************** typedef struct IndexPath
*** 720,730 ****
      List       *indexqualcols;
      List       *indexorderbys;
      List       *indexorderbycols;
-     bool        isjoininner;
      ScanDirection indexscandir;
      Cost        indextotalcost;
      Selectivity indexselectivity;
-     double        rows;            /* estimated number of result tuples */
  } IndexPath;

  /*
--- 725,733 ----
*************** typedef struct IndexPath
*** 743,758 ****
   * always represent the costs to use it as a regular (or index-only)
   * IndexScan.  The costs of a BitmapIndexScan can be computed using the
   * IndexPath's indextotalcost and indexselectivity.
-  *
-  * BitmapHeapPaths can be nestloop inner indexscans.  The isjoininner and
-  * rows fields serve the same purpose as for plain IndexPaths.
   */
  typedef struct BitmapHeapPath
  {
      Path        path;
      Path       *bitmapqual;        /* IndexPath, BitmapAndPath, BitmapOrPath */
-     bool        isjoininner;    /* T if it's a nestloop inner scan */
-     double        rows;            /* estimated number of result tuples */
  } BitmapHeapPath;

  /*
--- 746,756 ----
*************** typedef struct UniquePath
*** 885,891 ****
      UniquePathMethod umethod;
      List       *in_operators;    /* equality operators of the IN clause */
      List       *uniq_exprs;        /* expressions to be made unique */
-     double        rows;            /* estimated number of result tuples */
  } UniquePath;

  /*
--- 883,888 ----
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 1786d5e93607846acf70aab80093163442700a13..3b093dfd9cae9c5ce59a563de127815b40f946d0 100644
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern double index_pages_fetched(double
*** 68,76 ****
                      double index_pages, PlannerInfo *root);
  extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
  extern void cost_index(IndexPath *path, PlannerInfo *root,
!                        RelOptInfo *outer_rel);
  extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
!                       Path *bitmapqual, RelOptInfo *outer_rel);
  extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
  extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root);
  extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
--- 68,76 ----
                      double index_pages, PlannerInfo *root);
  extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
  extern void cost_index(IndexPath *path, PlannerInfo *root,
!                        double loop_count);
  extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
!                       Path *bitmapqual, double loop_count);
  extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
  extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root);
  extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 3bc1b27384c0c6d9d06e13068f8be085b7abb18c..c4ae7a9d556b743a77419f8f080960ddb310b13a 100644
*** a/src/include/optimizer/pathnode.h
--- b/src/include/optimizer/pathnode.h
*************** extern IndexPath *create_index_path(Plan
*** 37,47 ****
                    List *pathkeys,
                    ScanDirection indexscandir,
                    bool indexonly,
!                   RelOptInfo *outer_rel);
  extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
                          RelOptInfo *rel,
                          Path *bitmapqual,
!                         RelOptInfo *outer_rel);
  extern BitmapAndPath *create_bitmap_and_path(PlannerInfo *root,
                         RelOptInfo *rel,
                         List *bitmapquals);
--- 37,49 ----
                    List *pathkeys,
                    ScanDirection indexscandir,
                    bool indexonly,
!                   Relids required_outer,
!                   double loop_count);
  extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
                          RelOptInfo *rel,
                          Path *bitmapqual,
!                         Relids required_outer,
!                         double loop_count);
  extern BitmapAndPath *create_bitmap_and_path(PlannerInfo *root,
                         RelOptInfo *rel,
                         List *bitmapquals);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 76d7b77fc1d782f8812d7308baa1e357db9ca5c6..e3a085fdff13e6ca9c6d4a498522a69171d18b42 100644
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern void debug_print_rel(PlannerInfo
*** 45,54 ****
  extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
  extern List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
                           List *clauses, List *outer_clauses,
!                          RelOptInfo *outer_rel);
! extern void best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
!                      RelOptInfo *outer_rel, JoinType jointype,
!                      Path **cheapest_startup, Path **cheapest_total);
  extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
                                List *restrictlist,
                                List *exprlist, List *oprlist);
--- 45,51 ----
  extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
  extern List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
                           List *clauses, List *outer_clauses,
!                          Relids outer_relids, double outer_rows);
  extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
                                List *restrictlist,
                                List *exprlist, List *oprlist);
*************** extern List *canonicalize_pathkeys(Plann
*** 153,158 ****
--- 150,156 ----
  extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
  extern bool pathkeys_contained_in(List *keys1, List *keys2);
  extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
+                                Relids required_outer,
                                 CostSelector cost_criterion);
  extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
                                            List *pathkeys,
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 157f58e5fa8a4a3d3956750a9fd4e509a5084dfb..34977f9b95cbf5b96502100b5c1b695e74b3a58a 100644
*** a/src/include/optimizer/restrictinfo.h
--- b/src/include/optimizer/restrictinfo.h
*************** extern List *extract_actual_clauses(List
*** 40,47 ****
  extern void extract_actual_join_clauses(List *restrictinfo_list,
                              List **joinquals,
                              List **otherquals);
! extern List *select_nonredundant_join_clauses(PlannerInfo *root,
!                                  List *restrictinfo_list,
!                                  Path *inner_path);

  #endif   /* RESTRICTINFO_H */
--- 40,46 ----
  extern void extract_actual_join_clauses(List *restrictinfo_list,
                              List **joinquals,
                              List **otherquals);
! extern List *select_nonredundant_join_clauses(List *restrictinfo_list,
!                                  List *reference_list);

  #endif   /* RESTRICTINFO_H */