createplan.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * createplan.c
 *    Routines to create the desired plan for processing a query.
 *    Planning is complete, we just need to convert the selected
 *    Path into a Plan.
 *
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/optimizer/plan/createplan.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <limits.h>
#include <math.h>

#include "access/skey.h"
#include "catalog/pg_class.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/plancat.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
#include "optimizer/predtest.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/subselect.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/parse_clause.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"


static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path);
static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
static List *build_relation_tlist(RelOptInfo *rel);
static bool use_physical_tlist(PlannerInfo *root, RelOptInfo *rel);
static void disuse_physical_tlist(Plan *plan, Path *path);
static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
                    List *tlist, List *scan_clauses);
static Scan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
                      List *tlist, List *scan_clauses, bool indexonly);
static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
                        BitmapHeapPath *best_path,
                        List *tlist, List *scan_clauses);
static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
                      List **qual, List **indexqual, List **indexECs);
static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
                    List *tlist, List *scan_clauses);
static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
                         List *tlist, List *scan_clauses);
static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
                         List *tlist, List *scan_clauses);
static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
                       List *tlist, List *scan_clauses);
static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
                    List *tlist, List *scan_clauses);
static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
                          List *tlist, List *scan_clauses);
static ForeignScan *create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
                        List *tlist, List *scan_clauses);
static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
                     Plan *outer_plan, Plan *inner_plan);
static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
                      Plan *outer_plan, Plan *inner_plan);
static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
                     Plan *outer_plan, Plan *inner_plan);
static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
static void process_subquery_nestloop_params(PlannerInfo *root,
                                 List *subplan_params);
static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path);
static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
static List *get_switched_clauses(List *clauses, Relids outerrelids);
static List *order_qual_clauses(PlannerInfo *root, List *clauses);
static void copy_path_costsize(Plan *dest, Path *src);
static void copy_plan_costsize(Plan *dest, Plan *src);
static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
               Oid indexid, List *indexqual, List *indexqualorig,
               List *indexorderby, List *indexorderbyorig,
               ScanDirection indexscandir);
static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
                   Index scanrelid, Oid indexid,
                   List *indexqual, List *indexorderby,
                   List *indextlist,
                   ScanDirection indexscandir);
static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
                      List *indexqual,
                      List *indexqualorig);
static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
                     List *qpqual,
                     Plan *lefttree,
                     List *bitmapqualorig,
                     Index scanrelid);
static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
             List *tidquals);
static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
                  Index scanrelid, Node *funcexpr, List *funccolnames,
                  List *funccoltypes, List *funccoltypmods,
                  List *funccolcollations);
static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
                Index scanrelid, List *values_lists);
static CteScan *make_ctescan(List *qptlist, List *qpqual,
             Index scanrelid, int ctePlanId, int cteParam);
static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
                   Index scanrelid, int wtParam);
static BitmapAnd *make_bitmap_and(List *bitmapplans);
static BitmapOr *make_bitmap_or(List *bitmapplans);
static NestLoop *make_nestloop(List *tlist,
              List *joinclauses, List *otherclauses, List *nestParams,
              Plan *lefttree, Plan *righttree,
              JoinType jointype);
static HashJoin *make_hashjoin(List *tlist,
              List *joinclauses, List *otherclauses,
              List *hashclauses,
              Plan *lefttree, Plan *righttree,
              JoinType jointype);
static Hash *make_hash(Plan *lefttree,
          Oid skewTable,
          AttrNumber skewColumn,
          bool skewInherit,
          Oid skewColType,
          int32 skewColTypmod);
static MergeJoin *make_mergejoin(List *tlist,
               List *joinclauses, List *otherclauses,
               List *mergeclauses,
               Oid *mergefamilies,
               Oid *mergecollations,
               int *mergestrategies,
               bool *mergenullsfirst,
               Plan *lefttree, Plan *righttree,
               JoinType jointype);
static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
          AttrNumber *sortColIdx, Oid *sortOperators,
          Oid *collations, bool *nullsFirst,
          double limit_tuples);
static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
                           Plan *lefttree, List *pathkeys,
                           Relids relids,
                           const AttrNumber *reqColIdx,
                           bool adjust_tlist_in_place,
                           int *p_numsortkeys,
                           AttrNumber **p_sortColIdx,
                           Oid **p_sortOperators,
                           Oid **p_collations,
                           bool **p_nullsFirst);
static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
                       TargetEntry *tle,
                       Relids relids);
static Material *make_material(Plan *lefttree);


/*
 * create_plan
 *    Creates the access plan for a query by recursively processing the
 *    desired tree of pathnodes, starting at the node 'best_path'.  For
 *    every pathnode found, we create a corresponding plan node containing
 *    appropriate id, target list, and qualification information.
 *
 *    The tlists and quals in the plan tree are still in planner format,
 *    ie, Vars still correspond to the parser's numbering.  This will be
 *    fixed later by setrefs.c.
 *
 *    best_path is the best access path
 *
 *    Returns a Plan tree.
 */
Plan *
create_plan(PlannerInfo *root, Path *best_path)
{
    Plan       *plan;

    /* plan_params should not be in use in current query level */
    Assert(root->plan_params == NIL);

    /* Initialize this module's private workspace in PlannerInfo */
    root->curOuterRels = NULL;
    root->curOuterParams = NIL;

    /* Recursively process the path tree */
    plan = create_plan_recurse(root, best_path);

    /* Check we successfully assigned all NestLoopParams to plan nodes */
    if (root->curOuterParams != NIL)
        elog(ERROR, "failed to assign all NestLoopParams to plan nodes");

    /*
     * Reset plan_params to ensure param IDs used for nestloop params are not
     * re-used later
     */
    root->plan_params = NIL;

    return plan;
}

/*
 * create_plan_recurse
 *    Recursive guts of create_plan().
 */
static Plan *
create_plan_recurse(PlannerInfo *root, Path *best_path)
{
    Plan       *plan;

    switch (best_path->pathtype)
    {
        case T_SeqScan:
        case T_IndexScan:
        case T_IndexOnlyScan:
        case T_BitmapHeapScan:
        case T_TidScan:
        case T_SubqueryScan:
        case T_FunctionScan:
        case T_ValuesScan:
        case T_CteScan:
        case T_WorkTableScan:
        case T_ForeignScan:
            plan = create_scan_plan(root, best_path);
            break;
        case T_HashJoin:
        case T_MergeJoin:
        case T_NestLoop:
            plan = create_join_plan(root,
                                    (JoinPath *) best_path);
            break;
        case T_Append:
            plan = create_append_plan(root,
                                      (AppendPath *) best_path);
            break;
        case T_MergeAppend:
            plan = create_merge_append_plan(root,
                                            (MergeAppendPath *) best_path);
            break;
        case T_Result:
            plan = (Plan *) create_result_plan(root,
                                               (ResultPath *) best_path);
            break;
        case T_Material:
            plan = (Plan *) create_material_plan(root,
                                                 (MaterialPath *) best_path);
            break;
        case T_Unique:
            plan = create_unique_plan(root,
                                      (UniquePath *) best_path);
            break;
        default:
            elog(ERROR, "unrecognized node type: %d",
                 (int) best_path->pathtype);
            plan = NULL;        /* keep compiler quiet */
            break;
    }

    return plan;
}

/*
 * create_scan_plan
 *   Create a scan plan for the parent relation of 'best_path'.
 */
static Plan *
create_scan_plan(PlannerInfo *root, Path *best_path)
{
    RelOptInfo *rel = best_path->parent;
    List       *tlist;
    List       *scan_clauses;
    Plan       *plan;

    /*
     * For table scans, rather than using the relation targetlist (which is
     * only those Vars actually needed by the query), we prefer to generate a
     * tlist containing all Vars in order.  This will allow the executor to
     * optimize away projection of the table tuples, if possible.  (Note that
     * planner.c may replace the tlist we generate here, forcing projection to
     * occur.)
     */
    if (use_physical_tlist(root, rel))
    {
        if (best_path->pathtype == T_IndexOnlyScan)
        {
            /* For index-only scan, the preferred tlist is the index's */
            tlist = copyObject(((IndexPath *) best_path)->indexinfo->indextlist);
        }
        else
        {
            tlist = build_physical_tlist(root, rel);
            /* if fail because of dropped cols, use regular method */
            if (tlist == NIL)
                tlist = build_relation_tlist(rel);
        }
    }
    else
    {
        tlist = build_relation_tlist(rel);

        /*
         * If it's a parameterized otherrel, there might be lateral references
         * in the tlist, which need to be replaced with Params.  This cannot
         * happen for regular baserels, though.  Note use_physical_tlist()
         * always fails for otherrels, so we don't need to check this above.
         */
        if (rel->reloptkind != RELOPT_BASEREL && best_path->param_info)
            tlist = (List *) replace_nestloop_params(root, (Node *) tlist);
    }

    /*
     * Extract the relevant restriction clauses from the parent relation. The
     * executor must apply all these restrictions during the scan, except for
     * pseudoconstants which we'll take care of below.
     */
    scan_clauses = rel->baserestrictinfo;

    /*
     * If this is a parameterized scan, we also need to enforce all the join
     * clauses available from the outer relation(s).
     *
     * For paranoia's sake, don't modify the stored baserestrictinfo list.
     */
    if (best_path->param_info)
        scan_clauses = list_concat(list_copy(scan_clauses),
                                   best_path->param_info->ppi_clauses);

    switch (best_path->pathtype)
    {
        case T_SeqScan:
            plan = (Plan *) create_seqscan_plan(root,
                                                best_path,
                                                tlist,
                                                scan_clauses);
            break;

        case T_IndexScan:
            plan = (Plan *) create_indexscan_plan(root,
                                                  (IndexPath *) best_path,
                                                  tlist,
                                                  scan_clauses,
                                                  false);
            break;

        case T_IndexOnlyScan:
            plan = (Plan *) create_indexscan_plan(root,
                                                  (IndexPath *) best_path,
                                                  tlist,
                                                  scan_clauses,
                                                  true);
            break;

        case T_BitmapHeapScan:
            plan = (Plan *) create_bitmap_scan_plan(root,
                                                (BitmapHeapPath *) best_path,
                                                    tlist,
                                                    scan_clauses);
            break;

        case T_TidScan:
            plan = (Plan *) create_tidscan_plan(root,
                                                (TidPath *) best_path,
                                                tlist,
                                                scan_clauses);
            break;

        case T_SubqueryScan:
            plan = (Plan *) create_subqueryscan_plan(root,
                                                     best_path,
                                                     tlist,
                                                     scan_clauses);
            break;

        case T_FunctionScan:
            plan = (Plan *) create_functionscan_plan(root,
                                                     best_path,
                                                     tlist,
                                                     scan_clauses);
            break;

        case T_ValuesScan:
            plan = (Plan *) create_valuesscan_plan(root,
                                                   best_path,
                                                   tlist,
                                                   scan_clauses);
            break;

        case T_CteScan:
            plan = (Plan *) create_ctescan_plan(root,
                                                best_path,
                                                tlist,
                                                scan_clauses);
            break;

        case T_WorkTableScan:
            plan = (Plan *) create_worktablescan_plan(root,
                                                      best_path,
                                                      tlist,
                                                      scan_clauses);
            break;

        case T_ForeignScan:
            plan = (Plan *) create_foreignscan_plan(root,
                                                    (ForeignPath *) best_path,
                                                    tlist,
                                                    scan_clauses);
            break;

        default:
            elog(ERROR, "unrecognized node type: %d",
                 (int) best_path->pathtype);
            plan = NULL;        /* keep compiler quiet */
            break;
    }

    /*
     * If there are any pseudoconstant clauses attached to this node, insert a
     * gating Result node that evaluates the pseudoconstants as one-time
     * quals.
     */
    if (root->hasPseudoConstantQuals)
        plan = create_gating_plan(root, plan, scan_clauses);

    return plan;
}

/*
 * Build a target list (ie, a list of TargetEntry) for a relation.
 */
static List *
build_relation_tlist(RelOptInfo *rel)
{
    List       *tlist = NIL;
    int         resno = 1;
    ListCell   *v;

    foreach(v, rel->reltargetlist)
    {
        /* Do we really need to copy here?  Not sure */
        Node       *node = (Node *) copyObject(lfirst(v));

        tlist = lappend(tlist, makeTargetEntry((Expr *) node,
                                               resno,
                                               NULL,
                                               false));
        resno++;
    }
    return tlist;
}

/*
 * use_physical_tlist
 *      Decide whether to use a tlist matching relation structure,
 *      rather than only those Vars actually referenced.
 */
static bool
use_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
{
    int         i;
    ListCell   *lc;

    /*
     * We can do this for real relation scans, subquery scans, function scans,
     * values scans, and CTE scans (but not for, eg, joins).
     */
    if (rel->rtekind != RTE_RELATION &&
        rel->rtekind != RTE_SUBQUERY &&
        rel->rtekind != RTE_FUNCTION &&
        rel->rtekind != RTE_VALUES &&
        rel->rtekind != RTE_CTE)
        return false;

    /*
     * Can't do it with inheritance cases either (mainly because Append
     * doesn't project).
     */
    if (rel->reloptkind != RELOPT_BASEREL)
        return false;

    /*
     * Can't do it if any system columns or whole-row Vars are requested.
     * (This could possibly be fixed but would take some fragile assumptions
     * in setrefs.c, I think.)
     */
    for (i = rel->min_attr; i <= 0; i++)
    {
        if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
            return false;
    }

    /*
     * Can't do it if the rel is required to emit any placeholder expressions,
     * either.
     */
    foreach(lc, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);

        if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
            bms_is_subset(phinfo->ph_eval_at, rel->relids))
            return false;
    }

    return true;
}

/*
 * disuse_physical_tlist
 *      Switch a plan node back to emitting only Vars actually referenced.
 *
 * If the plan node immediately above a scan would prefer to get only
 * needed Vars and not a physical tlist, it must call this routine to
 * undo the decision made by use_physical_tlist().  Currently, Hash, Sort,
 * and Material nodes want this, so they don't have to store useless columns.
 */
static void
disuse_physical_tlist(Plan *plan, Path *path)
{
    /* Only need to undo it for path types handled by create_scan_plan() */
    switch (path->pathtype)
    {
        case T_SeqScan:
        case T_IndexScan:
        case T_IndexOnlyScan:
        case T_BitmapHeapScan:
        case T_TidScan:
        case T_SubqueryScan:
        case T_FunctionScan:
        case T_ValuesScan:
        case T_CteScan:
        case T_WorkTableScan:
        case T_ForeignScan:
            plan->targetlist = build_relation_tlist(path->parent);
            break;
        default:
            break;
    }
}

/*
 * create_gating_plan
 *    Deal with pseudoconstant qual clauses
 *
 * If the node's quals list includes any pseudoconstant quals, put them
 * into a gating Result node atop the already-built plan.  Otherwise,
 * return the plan as-is.
 *
 * Note that we don't change cost or size estimates when doing gating.
 * The costs of qual eval were already folded into the plan's startup cost.
 * Leaving the size alone amounts to assuming that the gating qual will
 * succeed, which is the conservative estimate for planning upper queries.
 * We certainly don't want to assume the output size is zero (unless the
 * gating qual is actually constant FALSE, and that case is dealt with in
 * clausesel.c).  Interpolating between the two cases is silly, because
 * it doesn't reflect what will really happen at runtime, and besides which
 * in most cases we have only a very bad idea of the probability of the gating
 * qual being true.
 */
static Plan *
create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
{
    List       *pseudoconstants;

    /* Sort into desirable execution order while still in RestrictInfo form */
    quals = order_qual_clauses(root, quals);

    /* Pull out any pseudoconstant quals from the RestrictInfo list */
    pseudoconstants = extract_actual_clauses(quals, true);

    if (!pseudoconstants)
        return plan;

    return (Plan *) make_result(root,
                                plan->targetlist,
                                (Node *) pseudoconstants,
                                plan);
}

/*
 * create_join_plan
 *    Create a join plan for 'best_path' and (recursively) plans for its
 *    inner and outer paths.
 */
static Plan *
create_join_plan(PlannerInfo *root, JoinPath *best_path)
{
    Plan       *outer_plan;
    Plan       *inner_plan;
    Plan       *plan;
    Relids      saveOuterRels = root->curOuterRels;

    outer_plan = create_plan_recurse(root, best_path->outerjoinpath);

    /* For a nestloop, include outer relids in curOuterRels for inner side */
    if (best_path->path.pathtype == T_NestLoop)
        root->curOuterRels = bms_union(root->curOuterRels,
                                   best_path->outerjoinpath->parent->relids);

    inner_plan = create_plan_recurse(root, best_path->innerjoinpath);

    switch (best_path->path.pathtype)
    {
        case T_MergeJoin:
            plan = (Plan *) create_mergejoin_plan(root,
                                                  (MergePath *) best_path,
                                                  outer_plan,
                                                  inner_plan);
            break;
        case T_HashJoin:
            plan = (Plan *) create_hashjoin_plan(root,
                                                 (HashPath *) best_path,
                                                 outer_plan,
                                                 inner_plan);
            break;
        case T_NestLoop:
            /* Restore curOuterRels */
            bms_free(root->curOuterRels);
            root->curOuterRels = saveOuterRels;

            plan = (Plan *) create_nestloop_plan(root,
                                                 (NestPath *) best_path,
                                                 outer_plan,
                                                 inner_plan);
            break;
        default:
            elog(ERROR, "unrecognized node type: %d",
                 (int) best_path->path.pathtype);
            plan = NULL;        /* keep compiler quiet */
            break;
    }

    /*
     * If there are any pseudoconstant clauses attached to this node, insert a
     * gating Result node that evaluates the pseudoconstants as one-time
     * quals.
     */
    if (root->hasPseudoConstantQuals)
        plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);

#ifdef NOT_USED

    /*
     * * Expensive function pullups may have pulled local predicates * into
     * this path node.  Put them in the qpqual of the plan node. * JMH,
     * 6/15/92
     */
    if (get_loc_restrictinfo(best_path) != NIL)
        set_qpqual((Plan) plan,
                   list_concat(get_qpqual((Plan) plan),
                       get_actual_clauses(get_loc_restrictinfo(best_path))));
#endif

    return plan;
}

/*
 * create_append_plan
 *    Create an Append plan for 'best_path' and (recursively) plans
 *    for its subpaths.
 *
 *    Returns a Plan node.
 */
static Plan *
create_append_plan(PlannerInfo *root, AppendPath *best_path)
{
    Append     *plan;
    RelOptInfo *rel = best_path->path.parent;
    List       *tlist = build_relation_tlist(rel);
    List       *subplans = NIL;
    ListCell   *subpaths;

    /*
     * The subpaths list could be empty, if every child was proven empty by
     * constraint exclusion.  In that case generate a dummy plan that returns
     * no rows.
     *
     * Note that an AppendPath with no members is also generated in certain
     * cases where there was no appending construct at all, but we know the
     * relation is empty (see set_dummy_rel_pathlist).
     */
    if (best_path->subpaths == NIL)
    {
        /*
         * If this is a dummy path for a subquery, we have to wrap the
         * subquery's original plan in a SubqueryScan so that setrefs.c will
         * do the right things.  (In particular, it must pull up the
         * subquery's rangetable so that the executor will apply permissions
         * checks to those rels at runtime.)
         */
        if (rel->rtekind == RTE_SUBQUERY)
        {
            Assert(is_dummy_plan(rel->subplan));
            return (Plan *) make_subqueryscan(tlist,
                                              NIL,
                                              rel->relid,
                                              rel->subplan);
        }
        else
        {
            /* Generate a Result plan with constant-FALSE gating qual */
            return (Plan *) make_result(root,
                                        tlist,
                                     (Node *) list_make1(makeBoolConst(false,
                                                                     false)),
                                        NULL);
        }
    }

    /* Build the plan for each child */
    foreach(subpaths, best_path->subpaths)
    {
        Path       *subpath = (Path *) lfirst(subpaths);

        subplans = lappend(subplans, create_plan_recurse(root, subpath));
    }

    /*
     * XXX ideally, if there's just one child, we'd not bother to generate an
     * Append node but just return the single child.  At the moment this does
     * not work because the varno of the child scan plan won't match the
     * parent-rel Vars it'll be asked to emit.
     */

    plan = make_append(subplans, tlist);

    return (Plan *) plan;
}

/*
 * create_merge_append_plan
 *    Create a MergeAppend plan for 'best_path' and (recursively) plans
 *    for its subpaths.
 *
 *    Returns a Plan node.
 */
static Plan *
create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
{
    MergeAppend *node = makeNode(MergeAppend);
    Plan       *plan = &node->plan;
    List       *tlist = build_relation_tlist(best_path->path.parent);
    List       *pathkeys = best_path->path.pathkeys;
    List       *subplans = NIL;
    ListCell   *subpaths;

    /*
     * We don't have the actual creation of the MergeAppend node split out
     * into a separate make_xxx function.  This is because we want to run
     * prepare_sort_from_pathkeys on it before we do so on the individual
     * child plans, to make cross-checking the sort info easier.
     */
    copy_path_costsize(plan, (Path *) best_path);
    plan->targetlist = tlist;
    plan->qual = NIL;
    plan->lefttree = NULL;
    plan->righttree = NULL;

    /* Compute sort column info, and adjust MergeAppend's tlist as needed */
    (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
                                      NULL,
                                      NULL,
                                      true,
                                      &node->numCols,
                                      &node->sortColIdx,
                                      &node->sortOperators,
                                      &node->collations,
                                      &node->nullsFirst);

    /*
     * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
     * even to subplans that don't need an explicit sort, to make sure they
     * are returning the same sort key columns the MergeAppend expects.
     */
    foreach(subpaths, best_path->subpaths)
    {
        Path       *subpath = (Path *) lfirst(subpaths);
        Plan       *subplan;
        int         numsortkeys;
        AttrNumber *sortColIdx;
        Oid        *sortOperators;
        Oid        *collations;
        bool       *nullsFirst;

        /* Build the child plan */
        subplan = create_plan_recurse(root, subpath);

        /* Compute sort column info, and adjust subplan's tlist as needed */
        subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
                                             subpath->parent->relids,
                                             node->sortColIdx,
                                             false,
                                             &numsortkeys,
                                             &sortColIdx,
                                             &sortOperators,
                                             &collations,
                                             &nullsFirst);

        /*
         * Check that we got the same sort key information.  We just Assert
         * that the sortops match, since those depend only on the pathkeys;
         * but it seems like a good idea to check the sort column numbers
         * explicitly, to ensure the tlists really do match up.
         */
        Assert(numsortkeys == node->numCols);
        if (memcmp(sortColIdx, node->sortColIdx,
                   numsortkeys * sizeof(AttrNumber)) != 0)
            elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
        Assert(memcmp(sortOperators, node->sortOperators,
                      numsortkeys * sizeof(Oid)) == 0);
        Assert(memcmp(collations, node->collations,
                      numsortkeys * sizeof(Oid)) == 0);
        Assert(memcmp(nullsFirst, node->nullsFirst,
                      numsortkeys * sizeof(bool)) == 0);

        /* Now, insert a Sort node if subplan isn't sufficiently ordered */
        if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
            subplan = (Plan *) make_sort(root, subplan, numsortkeys,
                                         sortColIdx, sortOperators,
                                         collations, nullsFirst,
                                         best_path->limit_tuples);

        subplans = lappend(subplans, subplan);
    }

    node->mergeplans = subplans;

    return (Plan *) node;
}

/*
 * create_result_plan
 *    Create a Result plan for 'best_path'.
 *    This is only used for the case of a query with an empty jointree.
 *
 *    Returns a Plan node.
 */
static Result *
create_result_plan(PlannerInfo *root, ResultPath *best_path)
{
    List       *tlist;
    List       *quals;

    /* The tlist will be installed later, since we have no RelOptInfo */
    Assert(best_path->path.parent == NULL);
    tlist = NIL;

    /* best_path->quals is just bare clauses */

    quals = order_qual_clauses(root, best_path->quals);

    return make_result(root, tlist, (Node *) quals, NULL);
}

/*
 * create_material_plan
 *    Create a Material plan for 'best_path' and (recursively) plans
 *    for its subpaths.
 *
 *    Returns a Plan node.
 */
static Material *
create_material_plan(PlannerInfo *root, MaterialPath *best_path)
{
    Material   *plan;
    Plan       *subplan;

    subplan = create_plan_recurse(root, best_path->subpath);

    /* We don't want any excess columns in the materialized tuples */
    disuse_physical_tlist(subplan, best_path->subpath);

    plan = make_material(subplan);

    copy_path_costsize(&plan->plan, (Path *) best_path);

    return plan;
}

/*
 * create_unique_plan
 *    Create a Unique plan for 'best_path' and (recursively) plans
 *    for its subpaths.
 *
 *    Returns a Plan node.
 */
static Plan *
create_unique_plan(PlannerInfo *root, UniquePath *best_path)
{
    Plan       *plan;
    Plan       *subplan;
    List       *in_operators;
    List       *uniq_exprs;
    List       *newtlist;
    int         nextresno;
    bool        newitems;
    int         numGroupCols;
    AttrNumber *groupColIdx;
    int         groupColPos;
    ListCell   *l;

    subplan = create_plan_recurse(root, best_path->subpath);

    /* Done if we don't need to do any actual unique-ifying */
    if (best_path->umethod == UNIQUE_PATH_NOOP)
        return subplan;

    /*
     * As constructed, the subplan has a "flat" tlist containing just the Vars
     * needed here and at upper levels.  The values we are supposed to
     * unique-ify may be expressions in these variables.  We have to add any
     * such expressions to the subplan's tlist.
     *
     * The subplan may have a "physical" tlist if it is a simple scan plan. If
     * we're going to sort, this should be reduced to the regular tlist, so
     * that we don't sort more data than we need to.  For hashing, the tlist
     * should be left as-is if we don't need to add any expressions; but if we
     * do have to add expressions, then a projection step will be needed at
     * runtime anyway, so we may as well remove unneeded items. Therefore
     * newtlist starts from build_relation_tlist() not just a copy of the
     * subplan's tlist; and we don't install it into the subplan unless we are
     * sorting or stuff has to be added.
     */
    in_operators = best_path->in_operators;
    uniq_exprs = best_path->uniq_exprs;

    /* initialize modified subplan tlist as just the "required" vars */
    newtlist = build_relation_tlist(best_path->path.parent);
    nextresno = list_length(newtlist) + 1;
    newitems = false;

    foreach(l, uniq_exprs)
    {
        Node       *uniqexpr = lfirst(l);
        TargetEntry *tle;

        tle = tlist_member(uniqexpr, newtlist);
        if (!tle)
        {
            tle = makeTargetEntry((Expr *) uniqexpr,
                                  nextresno,
                                  NULL,
                                  false);
            newtlist = lappend(newtlist, tle);
            nextresno++;
            newitems = true;
        }
    }

    if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
    {
        /*
         * If the top plan node can't do projections and its existing target
         * list isn't already what we need, we need to add a Result node to
         * help it along.
         */
        if (!is_projection_capable_plan(subplan) &&
            !tlist_same_exprs(newtlist, subplan->targetlist))
            subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
        else
            subplan->targetlist = newtlist;
    }

    /*
     * Build control information showing which subplan output columns are to
     * be examined by the grouping step.  Unfortunately we can't merge this
     * with the previous loop, since we didn't then know which version of the
     * subplan tlist we'd end up using.
     */
    newtlist = subplan->targetlist;
    numGroupCols = list_length(uniq_exprs);
    groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));

    groupColPos = 0;
    foreach(l, uniq_exprs)
    {
        Node       *uniqexpr = lfirst(l);
        TargetEntry *tle;

        tle = tlist_member(uniqexpr, newtlist);
        if (!tle)               /* shouldn't happen */
            elog(ERROR, "failed to find unique expression in subplan tlist");
        groupColIdx[groupColPos++] = tle->resno;
    }

    if (best_path->umethod == UNIQUE_PATH_HASH)
    {
        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.
         * Normally these are the same as the IN clause operators, but if
         * those are cross-type operators then the equality operators are the
         * ones for the IN clause operators' RHS datatype.
         */
        groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
        groupColPos = 0;
        foreach(l, in_operators)
        {
            Oid         in_oper = lfirst_oid(l);
            Oid         eq_oper;

            if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
                elog(ERROR, "could not find compatible hash operator for operator %u",
                     in_oper);
            groupOperators[groupColPos++] = eq_oper;
        }

        /*
         * Since the Agg node is going to project anyway, we can give it the
         * minimum output tlist, without any stuff we might have added to the
         * subplan tlist.
         */
        plan = (Plan *) make_agg(root,
                                 build_relation_tlist(best_path->path.parent),
                                 NIL,
                                 AGG_HASHED,
                                 NULL,
                                 numGroupCols,
                                 groupColIdx,
                                 groupOperators,
                                 numGroups,
                                 subplan);
    }
    else
    {
        List       *sortList = NIL;

        /* Create an ORDER BY list to sort the input compatibly */
        groupColPos = 0;
        foreach(l, in_operators)
        {
            Oid         in_oper = lfirst_oid(l);
            Oid         sortop;
            Oid         eqop;
            TargetEntry *tle;
            SortGroupClause *sortcl;

            sortop = get_ordering_op_for_equality_op(in_oper, false);
            if (!OidIsValid(sortop))    /* shouldn't happen */
                elog(ERROR, "could not find ordering operator for equality operator %u",
                     in_oper);

            /*
             * The Unique node will need equality operators.  Normally these
             * are the same as the IN clause operators, but if those are
             * cross-type operators then the equality operators are the ones
             * for the IN clause operators' RHS datatype.
             */
            eqop = get_equality_op_for_ordering_op(sortop, NULL);
            if (!OidIsValid(eqop))      /* shouldn't happen */
                elog(ERROR, "could not find equality operator for ordering operator %u",
                     sortop);

            tle = get_tle_by_resno(subplan->targetlist,
                                   groupColIdx[groupColPos]);
            Assert(tle != NULL);

            sortcl = makeNode(SortGroupClause);
            sortcl->tleSortGroupRef = assignSortGroupRef(tle,
                                                         subplan->targetlist);
            sortcl->eqop = eqop;
            sortcl->sortop = sortop;
            sortcl->nulls_first = false;
            sortcl->hashable = false;   /* no need to make this accurate */
            sortList = lappend(sortList, sortcl);
            groupColPos++;
        }
        plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
        plan = (Plan *) make_unique(plan, sortList);
    }

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

    return plan;
}


/*****************************************************************************
 *
 *  BASE-RELATION SCAN METHODS
 *
 *****************************************************************************/


/*
 * create_seqscan_plan
 *   Returns a seqscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static SeqScan *
create_seqscan_plan(PlannerInfo *root, Path *best_path,
                    List *tlist, List *scan_clauses)
{
    SeqScan    *scan_plan;
    Index       scan_relid = best_path->parent->relid;

    /* it should be a base rel... */
    Assert(scan_relid > 0);
    Assert(best_path->parent->rtekind == RTE_RELATION);

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
    }

    scan_plan = make_seqscan(tlist,
                             scan_clauses,
                             scan_relid);

    copy_path_costsize(&scan_plan->plan, best_path);

    return scan_plan;
}

/*
 * create_indexscan_plan
 *    Returns an indexscan plan for the base relation scanned by 'best_path'
 *    with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 *
 * We use this for both plain IndexScans and IndexOnlyScans, because the
 * qual preprocessing work is the same for both.  Note that the caller tells
 * us which to build --- we don't look at best_path->path.pathtype, because
 * create_bitmap_subplan needs to be able to override the prior decision.
 */
static Scan *
create_indexscan_plan(PlannerInfo *root,
                      IndexPath *best_path,
                      List *tlist,
                      List *scan_clauses,
                      bool indexonly)
{
    Scan       *scan_plan;
    List       *indexquals = best_path->indexquals;
    List       *indexorderbys = best_path->indexorderbys;
    Index       baserelid = best_path->path.parent->relid;
    Oid         indexoid = best_path->indexinfo->indexoid;
    List       *qpqual;
    List       *stripped_indexquals;
    List       *fixed_indexquals;
    List       *fixed_indexorderbys;
    ListCell   *l;

    /* it should be a base rel... */
    Assert(baserelid > 0);
    Assert(best_path->path.parent->rtekind == RTE_RELATION);

    /*
     * Build "stripped" indexquals structure (no RestrictInfos) to pass to
     * executor as indexqualorig
     */
    stripped_indexquals = get_actual_clauses(indexquals);

    /*
     * The executor needs a copy with the indexkey on the left of each clause
     * and with index Vars substituted for table ones.
     */
    fixed_indexquals = fix_indexqual_references(root, best_path);

    /*
     * Likewise fix up index attr references in the ORDER BY expressions.
     */
    fixed_indexorderbys = fix_indexorderby_references(root, best_path);

    /*
     * The qpqual list must contain all restrictions not automatically handled
     * by the index, other than pseudoconstant clauses which will be handled
     * by a separate gating plan node.  All the predicates in the indexquals
     * will be checked (either by the index itself, or by nodeIndexscan.c),
     * but if there are any "special" operators involved then they must be
     * included in qpqual.  The upshot is that qpqual must contain
     * scan_clauses minus whatever appears in indexquals.
     *
     * In normal cases simple pointer equality checks will be enough to spot
     * duplicate RestrictInfos, so we try that first.
     *
     * Another common case is that a scan_clauses entry is generated from the
     * same EquivalenceClass as some indexqual, and is therefore redundant
     * with it, though not equal.  (This happens when indxpath.c prefers a
     * different derived equality than what generate_join_implied_equalities
     * picked for a parameterized scan's ppi_clauses.)
     *
     * In some situations (particularly with OR'd index conditions) we may
     * have scan_clauses that are not equal to, but are logically implied by,
     * the index quals; so we also try a predicate_implied_by() check to see
     * if we can discard quals that way.  (predicate_implied_by assumes its
     * first input contains only immutable functions, so we have to check
     * that.)
     *
     * We can also discard quals that are implied by a partial index's
     * predicate, but only in a plain SELECT; when scanning a target relation
     * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
     * plan so that they'll be properly rechecked by EvalPlanQual testing.
     */
    qpqual = NIL;
    foreach(l, scan_clauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

        Assert(IsA(rinfo, RestrictInfo));
        if (rinfo->pseudoconstant)
            continue;           /* we may drop pseudoconstants here */
        if (list_member_ptr(indexquals, rinfo))
            continue;           /* simple duplicate */
        if (is_redundant_derived_clause(rinfo, indexquals))
            continue;           /* derived from same EquivalenceClass */
        if (!contain_mutable_functions((Node *) rinfo->clause))
        {
            List       *clausel = list_make1(rinfo->clause);

            if (predicate_implied_by(clausel, indexquals))
                continue;       /* provably implied by indexquals */
            if (best_path->indexinfo->indpred)
            {
                if (baserelid != root->parse->resultRelation &&
                    get_parse_rowmark(root->parse, baserelid) == NULL)
                    if (predicate_implied_by(clausel,
                                             best_path->indexinfo->indpred))
                        continue;       /* implied by index predicate */
            }
        }
        qpqual = lappend(qpqual, rinfo);
    }

    /* Sort clauses into best execution order */
    qpqual = order_qual_clauses(root, qpqual);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    qpqual = extract_actual_clauses(qpqual, false);

    /*
     * We have to replace any outer-relation variables with nestloop params in
     * the indexqualorig, qpqual, and indexorderbyorig expressions.  A bit
     * annoying to have to do this separately from the processing in
     * fix_indexqual_references --- rethink this when generalizing the inner
     * indexscan support.  But note we can't really do this earlier because
     * it'd break the comparisons to predicates above ... (or would it?  Those
     * wouldn't have outer refs)
     */
    if (best_path->path.param_info)
    {
        stripped_indexquals = (List *)
            replace_nestloop_params(root, (Node *) stripped_indexquals);
        qpqual = (List *)
            replace_nestloop_params(root, (Node *) qpqual);
        indexorderbys = (List *)
            replace_nestloop_params(root, (Node *) indexorderbys);
    }

    /* Finally ready to build the plan node */
    if (indexonly)
        scan_plan = (Scan *) make_indexonlyscan(tlist,
                                                qpqual,
                                                baserelid,
                                                indexoid,
                                                fixed_indexquals,
                                                fixed_indexorderbys,
                                            best_path->indexinfo->indextlist,
                                                best_path->indexscandir);
    else
        scan_plan = (Scan *) make_indexscan(tlist,
                                            qpqual,
                                            baserelid,
                                            indexoid,
                                            fixed_indexquals,
                                            stripped_indexquals,
                                            fixed_indexorderbys,
                                            indexorderbys,
                                            best_path->indexscandir);

    copy_path_costsize(&scan_plan->plan, &best_path->path);

    return scan_plan;
}

/*
 * create_bitmap_scan_plan
 *    Returns a bitmap scan plan for the base relation scanned by 'best_path'
 *    with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static BitmapHeapScan *
create_bitmap_scan_plan(PlannerInfo *root,
                        BitmapHeapPath *best_path,
                        List *tlist,
                        List *scan_clauses)
{
    Index       baserelid = best_path->path.parent->relid;
    Plan       *bitmapqualplan;
    List       *bitmapqualorig;
    List       *indexquals;
    List       *indexECs;
    List       *qpqual;
    ListCell   *l;
    BitmapHeapScan *scan_plan;

    /* it should be a base rel... */
    Assert(baserelid > 0);
    Assert(best_path->path.parent->rtekind == RTE_RELATION);

    /* Process the bitmapqual tree into a Plan tree and qual lists */
    bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
                                           &bitmapqualorig, &indexquals,
                                           &indexECs);

    /*
     * The qpqual list must contain all restrictions not automatically handled
     * by the index, other than pseudoconstant clauses which will be handled
     * by a separate gating plan node.  All the predicates in the indexquals
     * will be checked (either by the index itself, or by
     * nodeBitmapHeapscan.c), but if there are any "special" operators
     * involved then they must be added to qpqual.  The upshot is that qpqual
     * must contain scan_clauses minus whatever appears in indexquals.
     *
     * This loop is similar to the comparable code in create_indexscan_plan(),
     * but with some differences because it has to compare the scan clauses to
     * stripped (no RestrictInfos) indexquals.  See comments there for more
     * info.
     *
     * In normal cases simple equal() checks will be enough to spot duplicate
     * clauses, so we try that first.  We next see if the scan clause is
     * redundant with any top-level indexqual by virtue of being generated
     * from the same EC.  After that, try predicate_implied_by().
     *
     * Unlike create_indexscan_plan(), we need take no special thought here
     * for partial index predicates; this is because the predicate conditions
     * are already listed in bitmapqualorig and indexquals.  Bitmap scans have
     * to do it that way because predicate conditions need to be rechecked if
     * the scan becomes lossy, so they have to be included in bitmapqualorig.
     */
    qpqual = NIL;
    foreach(l, scan_clauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
        Node       *clause = (Node *) rinfo->clause;

        Assert(IsA(rinfo, RestrictInfo));
        if (rinfo->pseudoconstant)
            continue;           /* we may drop pseudoconstants here */
        if (list_member(indexquals, clause))
            continue;           /* simple duplicate */
        if (rinfo->parent_ec && list_member_ptr(indexECs, rinfo->parent_ec))
            continue;           /* derived from same EquivalenceClass */
        if (!contain_mutable_functions(clause))
        {
            List       *clausel = list_make1(clause);

            if (predicate_implied_by(clausel, indexquals))
                continue;       /* provably implied by indexquals */
        }
        qpqual = lappend(qpqual, rinfo);
    }

    /* Sort clauses into best execution order */
    qpqual = order_qual_clauses(root, qpqual);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    qpqual = extract_actual_clauses(qpqual, false);

    /*
     * When dealing with special operators, we will at this point have
     * duplicate clauses in qpqual and bitmapqualorig.  We may as well drop
     * 'em from bitmapqualorig, since there's no point in making the tests
     * twice.
     */
    bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);

    /*
     * We have to replace any outer-relation variables with nestloop params in
     * the qpqual and bitmapqualorig expressions.  (This was already done for
     * expressions attached to plan nodes in the bitmapqualplan tree.)
     */
    if (best_path->path.param_info)
    {
        qpqual = (List *)
            replace_nestloop_params(root, (Node *) qpqual);
        bitmapqualorig = (List *)
            replace_nestloop_params(root, (Node *) bitmapqualorig);
    }

    /* Finally ready to build the plan node */
    scan_plan = make_bitmap_heapscan(tlist,
                                     qpqual,
                                     bitmapqualplan,
                                     bitmapqualorig,
                                     baserelid);

    copy_path_costsize(&scan_plan->scan.plan, &best_path->path);

    return scan_plan;
}

/*
 * Given a bitmapqual tree, generate the Plan tree that implements it
 *
 * As byproducts, we also return in *qual and *indexqual the qual lists
 * (in implicit-AND form, without RestrictInfos) describing the original index
 * conditions and the generated indexqual conditions.  (These are the same in
 * simple cases, but when special index operators are involved, the former
 * list includes the special conditions while the latter includes the actual
 * indexable conditions derived from them.)  Both lists include partial-index
 * predicates, because we have to recheck predicates as well as index
 * conditions if the bitmap scan becomes lossy.
 *
 * In addition, we return a list of EquivalenceClass pointers for all the
 * top-level indexquals that were possibly-redundantly derived from ECs.
 * This allows removal of scan_clauses that are redundant with such quals.
 * (We do not attempt to detect such redundancies for quals that are within
 * OR subtrees.  This could be done in a less hacky way if we returned the
 * indexquals in RestrictInfo form, but that would be slower and still pretty
 * messy, since we'd have to build new RestrictInfos in many cases.)
 *
 * Note: if you find yourself changing this, you probably need to change
 * make_restrictinfo_from_bitmapqual too.
 */
static Plan *
create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
                      List **qual, List **indexqual, List **indexECs)
{
    Plan       *plan;

    if (IsA(bitmapqual, BitmapAndPath))
    {
        BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
        List       *subplans = NIL;
        List       *subquals = NIL;
        List       *subindexquals = NIL;
        List       *subindexECs = NIL;
        ListCell   *l;

        /*
         * There may well be redundant quals among the subplans, since a
         * top-level WHERE qual might have gotten used to form several
         * different index quals.  We don't try exceedingly hard to eliminate
         * redundancies, but we do eliminate obvious duplicates by using
         * list_concat_unique.
         */
        foreach(l, apath->bitmapquals)
        {
            Plan       *subplan;
            List       *subqual;
            List       *subindexqual;
            List       *subindexEC;

            subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
                                            &subqual, &subindexqual,
                                            &subindexEC);
            subplans = lappend(subplans, subplan);
            subquals = list_concat_unique(subquals, subqual);
            subindexquals = list_concat_unique(subindexquals, subindexqual);
            /* Duplicates in indexECs aren't worth getting rid of */
            subindexECs = list_concat(subindexECs, subindexEC);
        }
        plan = (Plan *) make_bitmap_and(subplans);
        plan->startup_cost = apath->path.startup_cost;
        plan->total_cost = apath->path.total_cost;
        plan->plan_rows =
            clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
        plan->plan_width = 0;   /* meaningless */
        *qual = subquals;
        *indexqual = subindexquals;
        *indexECs = subindexECs;
    }
    else if (IsA(bitmapqual, BitmapOrPath))
    {
        BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
        List       *subplans = NIL;
        List       *subquals = NIL;
        List       *subindexquals = NIL;
        bool        const_true_subqual = false;
        bool        const_true_subindexqual = false;
        ListCell   *l;

        /*
         * Here, we only detect qual-free subplans.  A qual-free subplan would
         * cause us to generate "... OR true ..."  which we may as well reduce
         * to just "true".  We do not try to eliminate redundant subclauses
         * because (a) it's not as likely as in the AND case, and (b) we might
         * well be working with hundreds or even thousands of OR conditions,
         * perhaps from a long IN list.  The performance of list_append_unique
         * would be unacceptable.
         */
        foreach(l, opath->bitmapquals)
        {
            Plan       *subplan;
            List       *subqual;
            List       *subindexqual;
            List       *subindexEC;

            subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
                                            &subqual, &subindexqual,
                                            &subindexEC);
            subplans = lappend(subplans, subplan);
            if (subqual == NIL)
                const_true_subqual = true;
            else if (!const_true_subqual)
                subquals = lappend(subquals,
                                   make_ands_explicit(subqual));
            if (subindexqual == NIL)
                const_true_subindexqual = true;
            else if (!const_true_subindexqual)
                subindexquals = lappend(subindexquals,
                                        make_ands_explicit(subindexqual));
        }

        /*
         * In the presence of ScalarArrayOpExpr quals, we might have built
         * BitmapOrPaths with just one subpath; don't add an OR step.
         */
        if (list_length(subplans) == 1)
        {
            plan = (Plan *) linitial(subplans);
        }
        else
        {
            plan = (Plan *) make_bitmap_or(subplans);
            plan->startup_cost = opath->path.startup_cost;
            plan->total_cost = opath->path.total_cost;
            plan->plan_rows =
                clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
            plan->plan_width = 0;       /* meaningless */
        }

        /*
         * If there were constant-TRUE subquals, the OR reduces to constant
         * TRUE.  Also, avoid generating one-element ORs, which could happen
         * due to redundancy elimination or ScalarArrayOpExpr quals.
         */
        if (const_true_subqual)
            *qual = NIL;
        else if (list_length(subquals) <= 1)
            *qual = subquals;
        else
            *qual = list_make1(make_orclause(subquals));
        if (const_true_subindexqual)
            *indexqual = NIL;
        else if (list_length(subindexquals) <= 1)
            *indexqual = subindexquals;
        else
            *indexqual = list_make1(make_orclause(subindexquals));
        *indexECs = NIL;
    }
    else if (IsA(bitmapqual, IndexPath))
    {
        IndexPath  *ipath = (IndexPath *) bitmapqual;
        IndexScan  *iscan;
        List       *subindexECs;
        ListCell   *l;

        /* Use the regular indexscan plan build machinery... */
        iscan = (IndexScan *) create_indexscan_plan(root, ipath,
                                                    NIL, NIL, false);
        Assert(IsA(iscan, IndexScan));
        /* then convert to a bitmap indexscan */
        plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
                                              iscan->indexid,
                                              iscan->indexqual,
                                              iscan->indexqualorig);
        plan->startup_cost = 0.0;
        plan->total_cost = ipath->indextotalcost;
        plan->plan_rows =
            clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
        plan->plan_width = 0;   /* meaningless */
        *qual = get_actual_clauses(ipath->indexclauses);
        *indexqual = get_actual_clauses(ipath->indexquals);
        foreach(l, ipath->indexinfo->indpred)
        {
            Expr       *pred = (Expr *) lfirst(l);

            /*
             * We know that the index predicate must have been implied by the
             * query condition as a whole, but it may or may not be implied by
             * the conditions that got pushed into the bitmapqual.  Avoid
             * generating redundant conditions.
             */
            if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
            {
                *qual = lappend(*qual, pred);
                *indexqual = lappend(*indexqual, pred);
            }
        }
        subindexECs = NIL;
        foreach(l, ipath->indexquals)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

            if (rinfo->parent_ec)
                subindexECs = lappend(subindexECs, rinfo->parent_ec);
        }
        *indexECs = subindexECs;
    }
    else
    {
        elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
        plan = NULL;            /* keep compiler quiet */
    }

    return plan;
}

/*
 * create_tidscan_plan
 *   Returns a tidscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static TidScan *
create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
                    List *tlist, List *scan_clauses)
{
    TidScan    *scan_plan;
    Index       scan_relid = best_path->path.parent->relid;
    List       *tidquals = best_path->tidquals;
    List       *ortidquals;

    /* it should be a base rel... */
    Assert(scan_relid > 0);
    Assert(best_path->path.parent->rtekind == RTE_RELATION);

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->path.param_info)
    {
        tidquals = (List *)
            replace_nestloop_params(root, (Node *) tidquals);
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
    }

    /*
     * Remove any clauses that are TID quals.  This is a bit tricky since the
     * tidquals list has implicit OR semantics.
     */
    ortidquals = tidquals;
    if (list_length(ortidquals) > 1)
        ortidquals = list_make1(make_orclause(ortidquals));
    scan_clauses = list_difference(scan_clauses, ortidquals);

    scan_plan = make_tidscan(tlist,
                             scan_clauses,
                             scan_relid,
                             tidquals);

    copy_path_costsize(&scan_plan->scan.plan, &best_path->path);

    return scan_plan;
}

/*
 * create_subqueryscan_plan
 *   Returns a subqueryscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static SubqueryScan *
create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
                         List *tlist, List *scan_clauses)
{
    SubqueryScan *scan_plan;
    Index       scan_relid = best_path->parent->relid;

    /* it should be a subquery base rel... */
    Assert(scan_relid > 0);
    Assert(best_path->parent->rtekind == RTE_SUBQUERY);

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
        process_subquery_nestloop_params(root,
                                         best_path->parent->subplan_params);
    }

    scan_plan = make_subqueryscan(tlist,
                                  scan_clauses,
                                  scan_relid,
                                  best_path->parent->subplan);

    copy_path_costsize(&scan_plan->scan.plan, best_path);

    return scan_plan;
}

/*
 * create_functionscan_plan
 *   Returns a functionscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static FunctionScan *
create_functionscan_plan(PlannerInfo *root, Path *best_path,
                         List *tlist, List *scan_clauses)
{
    FunctionScan *scan_plan;
    Index       scan_relid = best_path->parent->relid;
    RangeTblEntry *rte;
    Node       *funcexpr;

    /* it should be a function base rel... */
    Assert(scan_relid > 0);
    rte = planner_rt_fetch(scan_relid, root);
    Assert(rte->rtekind == RTE_FUNCTION);
    funcexpr = rte->funcexpr;

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
        /* The func expression itself could contain nestloop params, too */
        funcexpr = replace_nestloop_params(root, funcexpr);
    }

    scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
                                  funcexpr,
                                  rte->eref->colnames,
                                  rte->funccoltypes,
                                  rte->funccoltypmods,
                                  rte->funccolcollations);

    copy_path_costsize(&scan_plan->scan.plan, best_path);

    return scan_plan;
}

/*
 * create_valuesscan_plan
 *   Returns a valuesscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static ValuesScan *
create_valuesscan_plan(PlannerInfo *root, Path *best_path,
                       List *tlist, List *scan_clauses)
{
    ValuesScan *scan_plan;
    Index       scan_relid = best_path->parent->relid;
    RangeTblEntry *rte;
    List       *values_lists;

    /* it should be a values base rel... */
    Assert(scan_relid > 0);
    rte = planner_rt_fetch(scan_relid, root);
    Assert(rte->rtekind == RTE_VALUES);
    values_lists = rte->values_lists;

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
        /* The values lists could contain nestloop params, too */
        values_lists = (List *)
            replace_nestloop_params(root, (Node *) values_lists);
    }

    scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
                                values_lists);

    copy_path_costsize(&scan_plan->scan.plan, best_path);

    return scan_plan;
}

/*
 * create_ctescan_plan
 *   Returns a ctescan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static CteScan *
create_ctescan_plan(PlannerInfo *root, Path *best_path,
                    List *tlist, List *scan_clauses)
{
    CteScan    *scan_plan;
    Index       scan_relid = best_path->parent->relid;
    RangeTblEntry *rte;
    SubPlan    *ctesplan = NULL;
    int         plan_id;
    int         cte_param_id;
    PlannerInfo *cteroot;
    Index       levelsup;
    int         ndx;
    ListCell   *lc;

    Assert(scan_relid > 0);
    rte = planner_rt_fetch(scan_relid, root);
    Assert(rte->rtekind == RTE_CTE);
    Assert(!rte->self_reference);

    /*
     * Find the referenced CTE, and locate the SubPlan previously made for it.
     */
    levelsup = rte->ctelevelsup;
    cteroot = root;
    while (levelsup-- > 0)
    {
        cteroot = cteroot->parent_root;
        if (!cteroot)           /* shouldn't happen */
            elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
    }

    /*
     * Note: cte_plan_ids can be shorter than cteList, if we are still working
     * on planning the CTEs (ie, this is a side-reference from another CTE).
     * So we mustn't use forboth here.
     */
    ndx = 0;
    foreach(lc, cteroot->parse->cteList)
    {
        CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);

        if (strcmp(cte->ctename, rte->ctename) == 0)
            break;
        ndx++;
    }
    if (lc == NULL)             /* shouldn't happen */
        elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
    if (ndx >= list_length(cteroot->cte_plan_ids))
        elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
    plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
    Assert(plan_id > 0);
    foreach(lc, cteroot->init_plans)
    {
        ctesplan = (SubPlan *) lfirst(lc);
        if (ctesplan->plan_id == plan_id)
            break;
    }
    if (lc == NULL)             /* shouldn't happen */
        elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);

    /*
     * We need the CTE param ID, which is the sole member of the SubPlan's
     * setParam list.
     */
    cte_param_id = linitial_int(ctesplan->setParam);

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
    }

    scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
                             plan_id, cte_param_id);

    copy_path_costsize(&scan_plan->scan.plan, best_path);

    return scan_plan;
}

/*
 * create_worktablescan_plan
 *   Returns a worktablescan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static WorkTableScan *
create_worktablescan_plan(PlannerInfo *root, Path *best_path,
                          List *tlist, List *scan_clauses)
{
    WorkTableScan *scan_plan;
    Index       scan_relid = best_path->parent->relid;
    RangeTblEntry *rte;
    Index       levelsup;
    PlannerInfo *cteroot;

    Assert(scan_relid > 0);
    rte = planner_rt_fetch(scan_relid, root);
    Assert(rte->rtekind == RTE_CTE);
    Assert(rte->self_reference);

    /*
     * We need to find the worktable param ID, which is in the plan level
     * that's processing the recursive UNION, which is one level *below* where
     * the CTE comes from.
     */
    levelsup = rte->ctelevelsup;
    if (levelsup == 0)          /* shouldn't happen */
        elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
    levelsup--;
    cteroot = root;
    while (levelsup-- > 0)
    {
        cteroot = cteroot->parent_root;
        if (!cteroot)           /* shouldn't happen */
            elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
    }
    if (cteroot->wt_param_id < 0)       /* shouldn't happen */
        elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);

    /* Sort clauses into best execution order */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
    scan_clauses = extract_actual_clauses(scan_clauses, false);

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->param_info)
    {
        scan_clauses = (List *)
            replace_nestloop_params(root, (Node *) scan_clauses);
    }

    scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
                                   cteroot->wt_param_id);

    copy_path_costsize(&scan_plan->scan.plan, best_path);

    return scan_plan;
}

/*
 * create_foreignscan_plan
 *   Returns a foreignscan plan for the base relation scanned by 'best_path'
 *   with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 */
static ForeignScan *
create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
                        List *tlist, List *scan_clauses)
{
    ForeignScan *scan_plan;
    RelOptInfo *rel = best_path->path.parent;
    Index       scan_relid = rel->relid;
    RangeTblEntry *rte;
    int         i;

    /* it should be a base rel... */
    Assert(scan_relid > 0);
    Assert(rel->rtekind == RTE_RELATION);
    rte = planner_rt_fetch(scan_relid, root);
    Assert(rte->rtekind == RTE_RELATION);

    /*
     * Sort clauses into best execution order.  We do this first since the FDW
     * might have more info than we do and wish to adjust the ordering.
     */
    scan_clauses = order_qual_clauses(root, scan_clauses);

    /*
     * Let the FDW perform its processing on the restriction clauses and
     * generate the plan node.  Note that the FDW might remove restriction
     * clauses that it intends to execute remotely, or even add more (if it
     * has selected some join clauses for remote use but also wants them
     * rechecked locally).
     */
    scan_plan = rel->fdwroutine->GetForeignPlan(root, rel, rte->relid,
                                                best_path,
                                                tlist, scan_clauses);

    /* Copy cost data from Path to Plan; no need to make FDW do this */
    copy_path_costsize(&scan_plan->scan.plan, &best_path->path);

    /*
     * Replace any outer-relation variables with nestloop params in the qual
     * and fdw_exprs expressions.  We do this last so that the FDW doesn't
     * have to be involved.  (Note that parts of fdw_exprs could have come
     * from join clauses, so doing this beforehand on the scan_clauses
     * wouldn't work.)
     */
    if (best_path->path.param_info)
    {
        scan_plan->scan.plan.qual = (List *)
            replace_nestloop_params(root, (Node *) scan_plan->scan.plan.qual);
        scan_plan->fdw_exprs = (List *)
            replace_nestloop_params(root, (Node *) scan_plan->fdw_exprs);
    }

    /*
     * Detect whether any system columns are requested from rel.  This is a
     * bit of a kluge and might go away someday, so we intentionally leave it
     * out of the API presented to FDWs.
     */
    scan_plan->fsSystemCol = false;
    for (i = rel->min_attr; i < 0; i++)
    {
        if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
        {
            scan_plan->fsSystemCol = true;
            break;
        }
    }

    return scan_plan;
}


/*****************************************************************************
 *
 *  JOIN METHODS
 *
 *****************************************************************************/

static NestLoop *
create_nestloop_plan(PlannerInfo *root,
                     NestPath *best_path,
                     Plan *outer_plan,
                     Plan *inner_plan)
{
    NestLoop   *join_plan;
    List       *tlist = build_relation_tlist(best_path->path.parent);
    List       *joinrestrictclauses = best_path->joinrestrictinfo;
    List       *joinclauses;
    List       *otherclauses;
    Relids      outerrelids;
    List       *nestParams;
    ListCell   *cell;
    ListCell   *prev;
    ListCell   *next;

    /* Sort join qual clauses into best execution order */
    joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);

    /* Get the join qual clauses (in plain expression form) */
    /* Any pseudoconstant clauses are ignored here */
    if (IS_OUTER_JOIN(best_path->jointype))
    {
        extract_actual_join_clauses(joinrestrictclauses,
                                    &joinclauses, &otherclauses);
    }
    else
    {
        /* We can treat all clauses alike for an inner join */
        joinclauses = extract_actual_clauses(joinrestrictclauses, false);
        otherclauses = NIL;
    }

    /* Replace any outer-relation variables with nestloop params */
    if (best_path->path.param_info)
    {
        joinclauses = (List *)
            replace_nestloop_params(root, (Node *) joinclauses);
        otherclauses = (List *)
            replace_nestloop_params(root, (Node *) otherclauses);
    }

    /*
     * Identify any nestloop parameters that should be supplied by this join
     * node, and move them from root->curOuterParams to the nestParams list.
     */
    outerrelids = best_path->outerjoinpath->parent->relids;
    nestParams = NIL;
    prev = NULL;
    for (cell = list_head(root->curOuterParams); cell; cell = next)
    {
        NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);

        next = lnext(cell);
        if (IsA(nlp->paramval, Var) &&
            bms_is_member(nlp->paramval->varno, outerrelids))
        {
            root->curOuterParams = list_delete_cell(root->curOuterParams,
                                                    cell, prev);
            nestParams = lappend(nestParams, nlp);
        }
        else if (IsA(nlp->paramval, PlaceHolderVar) &&
                 bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
                             outerrelids) &&
                 bms_is_subset(find_placeholder_info(root,
                                            (PlaceHolderVar *) nlp->paramval,
                                                     false)->ph_eval_at,
                               outerrelids))
        {
            root->curOuterParams = list_delete_cell(root->curOuterParams,
                                                    cell, prev);
            nestParams = lappend(nestParams, nlp);
        }
        else
            prev = cell;
    }

    join_plan = make_nestloop(tlist,
                              joinclauses,
                              otherclauses,
                              nestParams,
                              outer_plan,
                              inner_plan,
                              best_path->jointype);

    copy_path_costsize(&join_plan->join.plan, &best_path->path);

    return join_plan;
}

static MergeJoin *
create_mergejoin_plan(PlannerInfo *root,
                      MergePath *best_path,
                      Plan *outer_plan,
                      Plan *inner_plan)
{
    List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
    List       *joinclauses;
    List       *otherclauses;
    List       *mergeclauses;
    List       *outerpathkeys;
    List       *innerpathkeys;
    int         nClauses;
    Oid        *mergefamilies;
    Oid        *mergecollations;
    int        *mergestrategies;
    bool       *mergenullsfirst;
    MergeJoin  *join_plan;
    int         i;
    ListCell   *lc;
    ListCell   *lop;
    ListCell   *lip;

    /* Sort join qual clauses into best execution order */
    /* NB: do NOT reorder the mergeclauses */
    joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);

    /* Get the join qual clauses (in plain expression form) */
    /* Any pseudoconstant clauses are ignored here */
    if (IS_OUTER_JOIN(best_path->jpath.jointype))
    {
        extract_actual_join_clauses(joinclauses,
                                    &joinclauses, &otherclauses);
    }
    else
    {
        /* We can treat all clauses alike for an inner join */
        joinclauses = extract_actual_clauses(joinclauses, false);
        otherclauses = NIL;
    }

    /*
     * Remove the mergeclauses from the list of join qual clauses, leaving the
     * list of quals that must be checked as qpquals.
     */
    mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
    joinclauses = list_difference(joinclauses, mergeclauses);

    /*
     * Replace any outer-relation variables with nestloop params.  There
     * should not be any in the mergeclauses.
     */
    if (best_path->jpath.path.param_info)
    {
        joinclauses = (List *)
            replace_nestloop_params(root, (Node *) joinclauses);
        otherclauses = (List *)
            replace_nestloop_params(root, (Node *) otherclauses);
    }

    /*
     * Rearrange mergeclauses, if needed, so that the outer variable is always
     * on the left; mark the mergeclause restrictinfos with correct
     * outer_is_left status.
     */
    mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
                             best_path->jpath.outerjoinpath->parent->relids);

    /*
     * Create explicit sort nodes for the outer and inner paths if necessary.
     * Make sure there are no excess columns in the inputs if sorting.
     */
    if (best_path->outersortkeys)
    {
        disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
        outer_plan = (Plan *)
            make_sort_from_pathkeys(root,
                                    outer_plan,
                                    best_path->outersortkeys,
                                    -1.0);
        outerpathkeys = best_path->outersortkeys;
    }
    else
        outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;

    if (best_path->innersortkeys)
    {
        disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
        inner_plan = (Plan *)
            make_sort_from_pathkeys(root,
                                    inner_plan,
                                    best_path->innersortkeys,
                                    -1.0);
        innerpathkeys = best_path->innersortkeys;
    }
    else
        innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;

    /*
     * If specified, add a materialize node to shield the inner plan from the
     * need to handle mark/restore.
     */
    if (best_path->materialize_inner)
    {
        Plan       *matplan = (Plan *) make_material(inner_plan);

        /*
         * We assume the materialize will not spill to disk, and therefore
         * charge just cpu_operator_cost per tuple.  (Keep this estimate in
         * sync with final_cost_mergejoin.)
         */
        copy_plan_costsize(matplan, inner_plan);
        matplan->total_cost += cpu_operator_cost * matplan->plan_rows;

        inner_plan = matplan;
    }

    /*
     * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
     * executor.  The information is in the pathkeys for the two inputs, but
     * we need to be careful about the possibility of mergeclauses sharing a
     * pathkey (compare find_mergeclauses_for_pathkeys()).
     */
    nClauses = list_length(mergeclauses);
    Assert(nClauses == list_length(best_path->path_mergeclauses));
    mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
    mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
    mergestrategies = (int *) palloc(nClauses * sizeof(int));
    mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));

    lop = list_head(outerpathkeys);
    lip = list_head(innerpathkeys);
    i = 0;
    foreach(lc, best_path->path_mergeclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
        EquivalenceClass *oeclass;
        EquivalenceClass *ieclass;
        PathKey    *opathkey;
        PathKey    *ipathkey;
        EquivalenceClass *opeclass;
        EquivalenceClass *ipeclass;
        ListCell   *l2;

        /* fetch outer/inner eclass from mergeclause */
        Assert(IsA(rinfo, RestrictInfo));
        if (rinfo->outer_is_left)
        {
            oeclass = rinfo->left_ec;
            ieclass = rinfo->right_ec;
        }
        else
        {
            oeclass = rinfo->right_ec;
            ieclass = rinfo->left_ec;
        }
        Assert(oeclass != NULL);
        Assert(ieclass != NULL);

        /*
         * For debugging purposes, we check that the eclasses match the paths'
         * pathkeys.  In typical cases the merge clauses are one-to-one with
         * the pathkeys, but when dealing with partially redundant query
         * conditions, we might have clauses that re-reference earlier path
         * keys.  The case that we need to reject is where a pathkey is
         * entirely skipped over.
         *
         * lop and lip reference the first as-yet-unused pathkey elements;
         * it's okay to match them, or any element before them.  If they're
         * NULL then we have found all pathkey elements to be used.
         */
        if (lop)
        {
            opathkey = (PathKey *) lfirst(lop);
            opeclass = opathkey->pk_eclass;
            if (oeclass == opeclass)
            {
                /* fast path for typical case */
                lop = lnext(lop);
            }
            else
            {
                /* redundant clauses ... must match something before lop */
                foreach(l2, outerpathkeys)
                {
                    if (l2 == lop)
                        break;
                    opathkey = (PathKey *) lfirst(l2);
                    opeclass = opathkey->pk_eclass;
                    if (oeclass == opeclass)
                        break;
                }
                if (oeclass != opeclass)
                    elog(ERROR, "outer pathkeys do not match mergeclauses");
            }
        }
        else
        {
            /* redundant clauses ... must match some already-used pathkey */
            opathkey = NULL;
            opeclass = NULL;
            foreach(l2, outerpathkeys)
            {
                opathkey = (PathKey *) lfirst(l2);
                opeclass = opathkey->pk_eclass;
                if (oeclass == opeclass)
                    break;
            }
            if (l2 == NULL)
                elog(ERROR, "outer pathkeys do not match mergeclauses");
        }

        if (lip)
        {
            ipathkey = (PathKey *) lfirst(lip);
            ipeclass = ipathkey->pk_eclass;
            if (ieclass == ipeclass)
            {
                /* fast path for typical case */
                lip = lnext(lip);
            }
            else
            {
                /* redundant clauses ... must match something before lip */
                foreach(l2, innerpathkeys)
                {
                    if (l2 == lip)
                        break;
                    ipathkey = (PathKey *) lfirst(l2);
                    ipeclass = ipathkey->pk_eclass;
                    if (ieclass == ipeclass)
                        break;
                }
                if (ieclass != ipeclass)
                    elog(ERROR, "inner pathkeys do not match mergeclauses");
            }
        }
        else
        {
            /* redundant clauses ... must match some already-used pathkey */
            ipathkey = NULL;
            ipeclass = NULL;
            foreach(l2, innerpathkeys)
            {
                ipathkey = (PathKey *) lfirst(l2);
                ipeclass = ipathkey->pk_eclass;
                if (ieclass == ipeclass)
                    break;
            }
            if (l2 == NULL)
                elog(ERROR, "inner pathkeys do not match mergeclauses");
        }

        /* pathkeys should match each other too (more debugging) */
        if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
            opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
            opathkey->pk_strategy != ipathkey->pk_strategy ||
            opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
            elog(ERROR, "left and right pathkeys do not match in mergejoin");

        /* OK, save info for executor */
        mergefamilies[i] = opathkey->pk_opfamily;
        mergecollations[i] = opathkey->pk_eclass->ec_collation;
        mergestrategies[i] = opathkey->pk_strategy;
        mergenullsfirst[i] = opathkey->pk_nulls_first;
        i++;
    }

    /*
     * Note: it is not an error if we have additional pathkey elements (i.e.,
     * lop or lip isn't NULL here).  The input paths might be better-sorted
     * than we need for the current mergejoin.
     */

    /*
     * Now we can build the mergejoin node.
     */
    join_plan = make_mergejoin(tlist,
                               joinclauses,
                               otherclauses,
                               mergeclauses,
                               mergefamilies,
                               mergecollations,
                               mergestrategies,
                               mergenullsfirst,
                               outer_plan,
                               inner_plan,
                               best_path->jpath.jointype);

    /* Costs of sort and material steps are included in path cost already */
    copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);

    return join_plan;
}

static HashJoin *
create_hashjoin_plan(PlannerInfo *root,
                     HashPath *best_path,
                     Plan *outer_plan,
                     Plan *inner_plan)
{
    List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
    List       *joinclauses;
    List       *otherclauses;
    List       *hashclauses;
    Oid         skewTable = InvalidOid;
    AttrNumber  skewColumn = InvalidAttrNumber;
    bool        skewInherit = false;
    Oid         skewColType = InvalidOid;
    int32       skewColTypmod = -1;
    HashJoin   *join_plan;
    Hash       *hash_plan;

    /* Sort join qual clauses into best execution order */
    joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
    /* There's no point in sorting the hash clauses ... */

    /* Get the join qual clauses (in plain expression form) */
    /* Any pseudoconstant clauses are ignored here */
    if (IS_OUTER_JOIN(best_path->jpath.jointype))
    {
        extract_actual_join_clauses(joinclauses,
                                    &joinclauses, &otherclauses);
    }
    else
    {
        /* We can treat all clauses alike for an inner join */
        joinclauses = extract_actual_clauses(joinclauses, false);
        otherclauses = NIL;
    }

    /*
     * Remove the hashclauses from the list of join qual clauses, leaving the
     * list of quals that must be checked as qpquals.
     */
    hashclauses = get_actual_clauses(best_path->path_hashclauses);
    joinclauses = list_difference(joinclauses, hashclauses);

    /*
     * Replace any outer-relation variables with nestloop params.  There
     * should not be any in the hashclauses.
     */
    if (best_path->jpath.path.param_info)
    {
        joinclauses = (List *)
            replace_nestloop_params(root, (Node *) joinclauses);
        otherclauses = (List *)
            replace_nestloop_params(root, (Node *) otherclauses);
    }

    /*
     * Rearrange hashclauses, if needed, so that the outer variable is always
     * on the left.
     */
    hashclauses = get_switched_clauses(best_path->path_hashclauses,
                             best_path->jpath.outerjoinpath->parent->relids);

    /* We don't want any excess columns in the hashed tuples */
    disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);

    /* If we expect batching, suppress excess columns in outer tuples too */
    if (best_path->num_batches > 1)
        disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);

    /*
     * If there is a single join clause and we can identify the outer variable
     * as a simple column reference, supply its identity for possible use in
     * skew optimization.  (Note: in principle we could do skew optimization
     * with multiple join clauses, but we'd have to be able to determine the
     * most common combinations of outer values, which we don't currently have
     * enough stats for.)
     */
    if (list_length(hashclauses) == 1)
    {
        OpExpr     *clause = (OpExpr *) linitial(hashclauses);
        Node       *node;

        Assert(is_opclause(clause));
        node = (Node *) linitial(clause->args);
        if (IsA(node, RelabelType))
            node = (Node *) ((RelabelType *) node)->arg;
        if (IsA(node, Var))
        {
            Var        *var = (Var *) node;
            RangeTblEntry *rte;

            rte = root->simple_rte_array[var->varno];
            if (rte->rtekind == RTE_RELATION)
            {
                skewTable = rte->relid;
                skewColumn = var->varattno;
                skewInherit = rte->inh;
                skewColType = var->vartype;
                skewColTypmod = var->vartypmod;
            }
        }
    }

    /*
     * Build the hash node and hash join node.
     */
    hash_plan = make_hash(inner_plan,
                          skewTable,
                          skewColumn,
                          skewInherit,
                          skewColType,
                          skewColTypmod);
    join_plan = make_hashjoin(tlist,
                              joinclauses,
                              otherclauses,
                              hashclauses,
                              outer_plan,
                              (Plan *) hash_plan,
                              best_path->jpath.jointype);

    copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);

    return join_plan;
}


/*****************************************************************************
 *
 *  SUPPORTING ROUTINES
 *
 *****************************************************************************/

/*
 * replace_nestloop_params
 *    Replace outer-relation Vars and PlaceHolderVars in the given expression
 *    with nestloop Params
 *
 * All Vars and PlaceHolderVars belonging to the relation(s) identified by
 * root->curOuterRels are replaced by Params, and entries are added to
 * root->curOuterParams if not already present.
 */
static Node *
replace_nestloop_params(PlannerInfo *root, Node *expr)
{
    /* No setup needed for tree walk, so away we go */
    return replace_nestloop_params_mutator(expr, root);
}

static Node *
replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
{
    if (node == NULL)
        return NULL;
    if (IsA(node, Var))
    {
        Var        *var = (Var *) node;
        Param      *param;
        NestLoopParam *nlp;
        ListCell   *lc;

        /* Upper-level Vars should be long gone at this point */
        Assert(var->varlevelsup == 0);
        /* If not to be replaced, we can just return the Var unmodified */
        if (!bms_is_member(var->varno, root->curOuterRels))
            return node;
        /* Create a Param representing the Var */
        param = assign_nestloop_param_var(root, var);
        /* Is this param already listed in root->curOuterParams? */
        foreach(lc, root->curOuterParams)
        {
            nlp = (NestLoopParam *) lfirst(lc);
            if (nlp->paramno == param->paramid)
            {
                Assert(equal(var, nlp->paramval));
                /* Present, so we can just return the Param */
                return (Node *) param;
            }
        }
        /* No, so add it */
        nlp = makeNode(NestLoopParam);
        nlp->paramno = param->paramid;
        nlp->paramval = var;
        root->curOuterParams = lappend(root->curOuterParams, nlp);
        /* And return the replacement Param */
        return (Node *) param;
    }
    if (IsA(node, PlaceHolderVar))
    {
        PlaceHolderVar *phv = (PlaceHolderVar *) node;
        Param      *param;
        NestLoopParam *nlp;
        ListCell   *lc;

        /* Upper-level PlaceHolderVars should be long gone at this point */
        Assert(phv->phlevelsup == 0);

        /*
         * If not to be replaced, just return the PlaceHolderVar unmodified.
         * We use bms_overlap as a cheap/quick test to see if the PHV might be
         * evaluated in the outer rels, and then grab its PlaceHolderInfo to
         * tell for sure.
         */
        if (!bms_overlap(phv->phrels, root->curOuterRels))
            return node;
        if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
                           root->curOuterRels))
            return node;
        /* Create a Param representing the PlaceHolderVar */
        param = assign_nestloop_param_placeholdervar(root, phv);
        /* Is this param already listed in root->curOuterParams? */
        foreach(lc, root->curOuterParams)
        {
            nlp = (NestLoopParam *) lfirst(lc);
            if (nlp->paramno == param->paramid)
            {
                Assert(equal(phv, nlp->paramval));
                /* Present, so we can just return the Param */
                return (Node *) param;
            }
        }
        /* No, so add it */
        nlp = makeNode(NestLoopParam);
        nlp->paramno = param->paramid;
        nlp->paramval = (Var *) phv;
        root->curOuterParams = lappend(root->curOuterParams, nlp);
        /* And return the replacement Param */
        return (Node *) param;
    }
    return expression_tree_mutator(node,
                                   replace_nestloop_params_mutator,
                                   (void *) root);
}

/*
 * process_subquery_nestloop_params
 *    Handle params of a parameterized subquery that need to be fed
 *    from an outer nestloop.
 *
 * Currently, that would be *all* params that a subquery in FROM has demanded
 * from the current query level, since they must be LATERAL references.
 *
 * The subplan's references to the outer variables are already represented
 * as PARAM_EXEC Params, so we need not modify the subplan here.  What we
 * do need to do is add entries to root->curOuterParams to signal the parent
 * nestloop plan node that it must provide these values.
 */
static void
process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
{
    ListCell   *ppl;

    foreach(ppl, subplan_params)
    {
        PlannerParamItem *pitem = (PlannerParamItem *) lfirst(ppl);

        if (IsA(pitem->item, Var))
        {
            Var        *var = (Var *) pitem->item;
            NestLoopParam *nlp;
            ListCell   *lc;

            /* If not from a nestloop outer rel, complain */
            if (!bms_is_member(var->varno, root->curOuterRels))
                elog(ERROR, "non-LATERAL parameter required by subquery");
            /* Is this param already listed in root->curOuterParams? */
            foreach(lc, root->curOuterParams)
            {
                nlp = (NestLoopParam *) lfirst(lc);
                if (nlp->paramno == pitem->paramId)
                {
                    Assert(equal(var, nlp->paramval));
                    /* Present, so nothing to do */
                    break;
                }
            }
            if (lc == NULL)
            {
                /* No, so add it */
                nlp = makeNode(NestLoopParam);
                nlp->paramno = pitem->paramId;
                nlp->paramval = copyObject(var);
                root->curOuterParams = lappend(root->curOuterParams, nlp);
            }
        }
        else if (IsA(pitem->item, PlaceHolderVar))
        {
            PlaceHolderVar *phv = (PlaceHolderVar *) pitem->item;
            NestLoopParam *nlp;
            ListCell   *lc;

            /* If not from a nestloop outer rel, complain */
            if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
                               root->curOuterRels))
                elog(ERROR, "non-LATERAL parameter required by subquery");
            /* Is this param already listed in root->curOuterParams? */
            foreach(lc, root->curOuterParams)
            {
                nlp = (NestLoopParam *) lfirst(lc);
                if (nlp->paramno == pitem->paramId)
                {
                    Assert(equal(phv, nlp->paramval));
                    /* Present, so nothing to do */
                    break;
                }
            }
            if (lc == NULL)
            {
                /* No, so add it */
                nlp = makeNode(NestLoopParam);
                nlp->paramno = pitem->paramId;
                nlp->paramval = copyObject(phv);
                root->curOuterParams = lappend(root->curOuterParams, nlp);
            }
        }
        else
            elog(ERROR, "unexpected type of subquery parameter");
    }
}

/*
 * fix_indexqual_references
 *    Adjust indexqual clauses to the form the executor's indexqual
 *    machinery needs.
 *
 * We have four tasks here:
 *  * Remove RestrictInfo nodes from the input clauses.
 *  * Replace any outer-relation Var or PHV nodes with nestloop Params.
 *    (XXX eventually, that responsibility should go elsewhere?)
 *  * Index keys must be represented by Var nodes with varattno set to the
 *    index's attribute number, not the attribute number in the original rel.
 *  * If the index key is on the right, commute the clause to put it on the
 *    left.
 *
 * The result is a modified copy of the path's indexquals list --- the
 * original is not changed.  Note also that the copy shares no substructure
 * with the original; this is needed in case there is a subplan in it (we need
 * two separate copies of the subplan tree, or things will go awry).
 */
static List *
fix_indexqual_references(PlannerInfo *root, IndexPath *index_path)
{
    IndexOptInfo *index = index_path->indexinfo;
    List       *fixed_indexquals;
    ListCell   *lcc,
               *lci;

    fixed_indexquals = NIL;

    forboth(lcc, index_path->indexquals, lci, index_path->indexqualcols)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
        int         indexcol = lfirst_int(lci);
        Node       *clause;

        Assert(IsA(rinfo, RestrictInfo));

        /*
         * Replace any outer-relation variables with nestloop params.
         *
         * This also makes a copy of the clause, so it's safe to modify it
         * in-place below.
         */
        clause = replace_nestloop_params(root, (Node *) rinfo->clause);

        if (IsA(clause, OpExpr))
        {
            OpExpr     *op = (OpExpr *) clause;

            if (list_length(op->args) != 2)
                elog(ERROR, "indexqual clause is not binary opclause");

            /*
             * Check to see if the indexkey is on the right; if so, commute
             * the clause.  The indexkey should be the side that refers to
             * (only) the base relation.
             */
            if (!bms_equal(rinfo->left_relids, index->rel->relids))
                CommuteOpExpr(op);

            /*
             * Now replace the indexkey expression with an index Var.
             */
            linitial(op->args) = fix_indexqual_operand(linitial(op->args),
                                                       index,
                                                       indexcol);
        }
        else if (IsA(clause, RowCompareExpr))
        {
            RowCompareExpr *rc = (RowCompareExpr *) clause;
            Expr       *newrc;
            List       *indexcolnos;
            bool        var_on_left;
            ListCell   *lca,
                       *lcai;

            /*
             * Re-discover which index columns are used in the rowcompare.
             */
            newrc = adjust_rowcompare_for_index(rc,
                                                index,
                                                indexcol,
                                                &indexcolnos,
                                                &var_on_left);

            /*
             * Trouble if adjust_rowcompare_for_index thought the
             * RowCompareExpr didn't match the index as-is; the clause should
             * have gone through that routine already.
             */
            if (newrc != (Expr *) rc)
                elog(ERROR, "inconsistent results from adjust_rowcompare_for_index");

            /*
             * Check to see if the indexkey is on the right; if so, commute
             * the clause.
             */
            if (!var_on_left)
                CommuteRowCompareExpr(rc);

            /*
             * Now replace the indexkey expressions with index Vars.
             */
            Assert(list_length(rc->largs) == list_length(indexcolnos));
            forboth(lca, rc->largs, lcai, indexcolnos)
            {
                lfirst(lca) = fix_indexqual_operand(lfirst(lca),
                                                    index,
                                                    lfirst_int(lcai));
            }
        }
        else if (IsA(clause, ScalarArrayOpExpr))
        {
            ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;

            /* Never need to commute... */

            /* Replace the indexkey expression with an index Var. */
            linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
                                                         index,
                                                         indexcol);
        }
        else if (IsA(clause, NullTest))
        {
            NullTest   *nt = (NullTest *) clause;

            /* Replace the indexkey expression with an index Var. */
            nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
                                                     index,
                                                     indexcol);
        }
        else
            elog(ERROR, "unsupported indexqual type: %d",
                 (int) nodeTag(clause));

        fixed_indexquals = lappend(fixed_indexquals, clause);
    }

    return fixed_indexquals;
}

/*
 * fix_indexorderby_references
 *    Adjust indexorderby clauses to the form the executor's index
 *    machinery needs.
 *
 * This is a simplified version of fix_indexqual_references.  The input does
 * not have RestrictInfo nodes, and we assume that indxpath.c already
 * commuted the clauses to put the index keys on the left.  Also, we don't
 * bother to support any cases except simple OpExprs, since nothing else
 * is allowed for ordering operators.
 */
static List *
fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path)
{
    IndexOptInfo *index = index_path->indexinfo;
    List       *fixed_indexorderbys;
    ListCell   *lcc,
               *lci;

    fixed_indexorderbys = NIL;

    forboth(lcc, index_path->indexorderbys, lci, index_path->indexorderbycols)
    {
        Node       *clause = (Node *) lfirst(lcc);
        int         indexcol = lfirst_int(lci);

        /*
         * Replace any outer-relation variables with nestloop params.
         *
         * This also makes a copy of the clause, so it's safe to modify it
         * in-place below.
         */
        clause = replace_nestloop_params(root, clause);

        if (IsA(clause, OpExpr))
        {
            OpExpr     *op = (OpExpr *) clause;

            if (list_length(op->args) != 2)
                elog(ERROR, "indexorderby clause is not binary opclause");

            /*
             * Now replace the indexkey expression with an index Var.
             */
            linitial(op->args) = fix_indexqual_operand(linitial(op->args),
                                                       index,
                                                       indexcol);
        }
        else
            elog(ERROR, "unsupported indexorderby type: %d",
                 (int) nodeTag(clause));

        fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
    }

    return fixed_indexorderbys;
}

/*
 * fix_indexqual_operand
 *    Convert an indexqual expression to a Var referencing the index column.
 *
 * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
 * equal to the index's attribute number (index column position).
 *
 * Most of the code here is just for sanity cross-checking that the given
 * expression actually matches the index column it's claimed to.
 */
static Node *
fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol)
{
    Var        *result;
    int         pos;
    ListCell   *indexpr_item;

    /*
     * Remove any binary-compatible relabeling of the indexkey
     */
    if (IsA(node, RelabelType))
        node = (Node *) ((RelabelType *) node)->arg;

    Assert(indexcol >= 0 && indexcol < index->ncolumns);

    if (index->indexkeys[indexcol] != 0)
    {
        /* It's a simple index column */
        if (IsA(node, Var) &&
            ((Var *) node)->varno == index->rel->relid &&
            ((Var *) node)->varattno == index->indexkeys[indexcol])
        {
            result = (Var *) copyObject(node);
            result->varno = INDEX_VAR;
            result->varattno = indexcol + 1;
            return (Node *) result;
        }
        else
            elog(ERROR, "index key does not match expected index column");
    }

    /* It's an index expression, so find and cross-check the expression */
    indexpr_item = list_head(index->indexprs);
    for (pos = 0; pos < index->ncolumns; pos++)
    {
        if (index->indexkeys[pos] == 0)
        {
            if (indexpr_item == NULL)
                elog(ERROR, "too few entries in indexprs list");
            if (pos == indexcol)
            {
                Node       *indexkey;

                indexkey = (Node *) lfirst(indexpr_item);
                if (indexkey && IsA(indexkey, RelabelType))
                    indexkey = (Node *) ((RelabelType *) indexkey)->arg;
                if (equal(node, indexkey))
                {
                    result = makeVar(INDEX_VAR, indexcol + 1,
                                     exprType(lfirst(indexpr_item)), -1,
                                     exprCollation(lfirst(indexpr_item)),
                                     0);
                    return (Node *) result;
                }
                else
                    elog(ERROR, "index key does not match expected index column");
            }
            indexpr_item = lnext(indexpr_item);
        }
    }

    /* Ooops... */
    elog(ERROR, "index key does not match expected index column");
    return NULL;                /* keep compiler quiet */
}

/*
 * get_switched_clauses
 *    Given a list of merge or hash joinclauses (as RestrictInfo nodes),
 *    extract the bare clauses, and rearrange the elements within the
 *    clauses, if needed, so the outer join variable is on the left and
 *    the inner is on the right.  The original clause data structure is not
 *    touched; a modified list is returned.  We do, however, set the transient
 *    outer_is_left field in each RestrictInfo to show which side was which.
 */
static List *
get_switched_clauses(List *clauses, Relids outerrelids)
{
    List       *t_list = NIL;
    ListCell   *l;

    foreach(l, clauses)
    {
        RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
        OpExpr     *clause = (OpExpr *) restrictinfo->clause;

        Assert(is_opclause(clause));
        if (bms_is_subset(restrictinfo->right_relids, outerrelids))
        {
            /*
             * Duplicate just enough of the structure to allow commuting the
             * clause without changing the original list.  Could use
             * copyObject, but a complete deep copy is overkill.
             */
            OpExpr     *temp = makeNode(OpExpr);

            temp->opno = clause->opno;
            temp->opfuncid = InvalidOid;
            temp->opresulttype = clause->opresulttype;
            temp->opretset = clause->opretset;
            temp->opcollid = clause->opcollid;
            temp->inputcollid = clause->inputcollid;
            temp->args = list_copy(clause->args);
            temp->location = clause->location;
            /* Commute it --- note this modifies the temp node in-place. */
            CommuteOpExpr(temp);
            t_list = lappend(t_list, temp);
            restrictinfo->outer_is_left = false;
        }
        else
        {
            Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
            t_list = lappend(t_list, clause);
            restrictinfo->outer_is_left = true;
        }
    }
    return t_list;
}

/*
 * order_qual_clauses
 *      Given a list of qual clauses that will all be evaluated at the same
 *      plan node, sort the list into the order we want to check the quals
 *      in at runtime.
 *
 * Ideally the order should be driven by a combination of execution cost and
 * selectivity, but it's not immediately clear how to account for both,
 * and given the uncertainty of the estimates the reliability of the decisions
 * would be doubtful anyway.  So we just order by estimated per-tuple cost,
 * being careful not to change the order when (as is often the case) the
 * estimates are identical.
 *
 * Although this will work on either bare clauses or RestrictInfos, it's
 * much faster to apply it to RestrictInfos, since it can re-use cost
 * information that is cached in RestrictInfos.
 *
 * Note: some callers pass lists that contain entries that will later be
 * removed; this is the easiest way to let this routine see RestrictInfos
 * instead of bare clauses.  It's OK because we only sort by cost, but
 * a cost/selectivity combination would likely do the wrong thing.
 */
static List *
order_qual_clauses(PlannerInfo *root, List *clauses)
{
    typedef struct
    {
        Node       *clause;
        Cost        cost;
    } QualItem;
    int         nitems = list_length(clauses);
    QualItem   *items;
    ListCell   *lc;
    int         i;
    List       *result;

    /* No need to work hard for 0 or 1 clause */
    if (nitems <= 1)
        return clauses;

    /*
     * Collect the items and costs into an array.  This is to avoid repeated
     * cost_qual_eval work if the inputs aren't RestrictInfos.
     */
    items = (QualItem *) palloc(nitems * sizeof(QualItem));
    i = 0;
    foreach(lc, clauses)
    {
        Node       *clause = (Node *) lfirst(lc);
        QualCost    qcost;

        cost_qual_eval_node(&qcost, clause, root);
        items[i].clause = clause;
        items[i].cost = qcost.per_tuple;
        i++;
    }

    /*
     * Sort.  We don't use qsort() because it's not guaranteed stable for
     * equal keys.  The expected number of entries is small enough that a
     * simple insertion sort should be good enough.
     */
    for (i = 1; i < nitems; i++)
    {
        QualItem    newitem = items[i];
        int         j;

        /* insert newitem into the already-sorted subarray */
        for (j = i; j > 0; j--)
        {
            if (newitem.cost >= items[j - 1].cost)
                break;
            items[j] = items[j - 1];
        }
        items[j] = newitem;
    }

    /* Convert back to a list */
    result = NIL;
    for (i = 0; i < nitems; i++)
        result = lappend(result, items[i].clause);

    return result;
}

/*
 * Copy cost and size info from a Path node to the Plan node created from it.
 * The executor usually won't use this info, but it's needed by EXPLAIN.
 */
static void
copy_path_costsize(Plan *dest, Path *src)
{
    if (src)
    {
        dest->startup_cost = src->startup_cost;
        dest->total_cost = src->total_cost;
        dest->plan_rows = src->rows;
        dest->plan_width = src->parent->width;
    }
    else
    {
        dest->startup_cost = 0;
        dest->total_cost = 0;
        dest->plan_rows = 0;
        dest->plan_width = 0;
    }
}

/*
 * Copy cost and size info from a lower plan node to an inserted node.
 * (Most callers alter the info after copying it.)
 */
static void
copy_plan_costsize(Plan *dest, Plan *src)
{
    if (src)
    {
        dest->startup_cost = src->startup_cost;
        dest->total_cost = src->total_cost;
        dest->plan_rows = src->plan_rows;
        dest->plan_width = src->plan_width;
    }
    else
    {
        dest->startup_cost = 0;
        dest->total_cost = 0;
        dest->plan_rows = 0;
        dest->plan_width = 0;
    }
}


/*****************************************************************************
 *
 *  PLAN NODE BUILDING ROUTINES
 *
 * Some of these are exported because they are called to build plan nodes
 * in contexts where we're not deriving the plan node from a path node.
 *
 *****************************************************************************/

static SeqScan *
make_seqscan(List *qptlist,
             List *qpqual,
             Index scanrelid)
{
    SeqScan    *node = makeNode(SeqScan);
    Plan       *plan = &node->plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scanrelid = scanrelid;

    return node;
}

static IndexScan *
make_indexscan(List *qptlist,
               List *qpqual,
               Index scanrelid,
               Oid indexid,
               List *indexqual,
               List *indexqualorig,
               List *indexorderby,
               List *indexorderbyorig,
               ScanDirection indexscandir)
{
    IndexScan  *node = makeNode(IndexScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->indexid = indexid;
    node->indexqual = indexqual;
    node->indexqualorig = indexqualorig;
    node->indexorderby = indexorderby;
    node->indexorderbyorig = indexorderbyorig;
    node->indexorderdir = indexscandir;

    return node;
}

static IndexOnlyScan *
make_indexonlyscan(List *qptlist,
                   List *qpqual,
                   Index scanrelid,
                   Oid indexid,
                   List *indexqual,
                   List *indexorderby,
                   List *indextlist,
                   ScanDirection indexscandir)
{
    IndexOnlyScan *node = makeNode(IndexOnlyScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->indexid = indexid;
    node->indexqual = indexqual;
    node->indexorderby = indexorderby;
    node->indextlist = indextlist;
    node->indexorderdir = indexscandir;

    return node;
}

static BitmapIndexScan *
make_bitmap_indexscan(Index scanrelid,
                      Oid indexid,
                      List *indexqual,
                      List *indexqualorig)
{
    BitmapIndexScan *node = makeNode(BitmapIndexScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = NIL;     /* not used */
    plan->qual = NIL;           /* not used */
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->indexid = indexid;
    node->indexqual = indexqual;
    node->indexqualorig = indexqualorig;

    return node;
}

static BitmapHeapScan *
make_bitmap_heapscan(List *qptlist,
                     List *qpqual,
                     Plan *lefttree,
                     List *bitmapqualorig,
                     Index scanrelid)
{
    BitmapHeapScan *node = makeNode(BitmapHeapScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = lefttree;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->bitmapqualorig = bitmapqualorig;

    return node;
}

static TidScan *
make_tidscan(List *qptlist,
             List *qpqual,
             Index scanrelid,
             List *tidquals)
{
    TidScan    *node = makeNode(TidScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->tidquals = tidquals;

    return node;
}

SubqueryScan *
make_subqueryscan(List *qptlist,
                  List *qpqual,
                  Index scanrelid,
                  Plan *subplan)
{
    SubqueryScan *node = makeNode(SubqueryScan);
    Plan       *plan = &node->scan.plan;

    /*
     * Cost is figured here for the convenience of prepunion.c.  Note this is
     * only correct for the case where qpqual is empty; otherwise caller
     * should overwrite cost with a better estimate.
     */
    copy_plan_costsize(plan, subplan);
    plan->total_cost += cpu_tuple_cost * subplan->plan_rows;

    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->subplan = subplan;

    return node;
}

static FunctionScan *
make_functionscan(List *qptlist,
                  List *qpqual,
                  Index scanrelid,
                  Node *funcexpr,
                  List *funccolnames,
                  List *funccoltypes,
                  List *funccoltypmods,
                  List *funccolcollations)
{
    FunctionScan *node = makeNode(FunctionScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->funcexpr = funcexpr;
    node->funccolnames = funccolnames;
    node->funccoltypes = funccoltypes;
    node->funccoltypmods = funccoltypmods;
    node->funccolcollations = funccolcollations;

    return node;
}

static ValuesScan *
make_valuesscan(List *qptlist,
                List *qpqual,
                Index scanrelid,
                List *values_lists)
{
    ValuesScan *node = makeNode(ValuesScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->values_lists = values_lists;

    return node;
}

static CteScan *
make_ctescan(List *qptlist,
             List *qpqual,
             Index scanrelid,
             int ctePlanId,
             int cteParam)
{
    CteScan    *node = makeNode(CteScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->ctePlanId = ctePlanId;
    node->cteParam = cteParam;

    return node;
}

static WorkTableScan *
make_worktablescan(List *qptlist,
                   List *qpqual,
                   Index scanrelid,
                   int wtParam)
{
    WorkTableScan *node = makeNode(WorkTableScan);
    Plan       *plan = &node->scan.plan;

    /* cost should be inserted by caller */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->wtParam = wtParam;

    return node;
}

ForeignScan *
make_foreignscan(List *qptlist,
                 List *qpqual,
                 Index scanrelid,
                 List *fdw_exprs,
                 List *fdw_private)
{
    ForeignScan *node = makeNode(ForeignScan);
    Plan       *plan = &node->scan.plan;

    /* cost will be filled in by create_foreignscan_plan */
    plan->targetlist = qptlist;
    plan->qual = qpqual;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->scan.scanrelid = scanrelid;
    node->fdw_exprs = fdw_exprs;
    node->fdw_private = fdw_private;
    /* fsSystemCol will be filled in by create_foreignscan_plan */
    node->fsSystemCol = false;

    return node;
}

Append *
make_append(List *appendplans, List *tlist)
{
    Append     *node = makeNode(Append);
    Plan       *plan = &node->plan;
    double      total_size;
    ListCell   *subnode;

    /*
     * 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 create_append_path().  Also, the size
     * calculations should match set_append_rel_pathlist().  It'd be better
     * not to duplicate all this logic, but some callers of this function
     * aren't working from an appendrel or AppendPath, so there's noplace to
     * copy the data from.
     */
    plan->startup_cost = 0;
    plan->total_cost = 0;
    plan->plan_rows = 0;
    total_size = 0;
    foreach(subnode, appendplans)
    {
        Plan       *subplan = (Plan *) lfirst(subnode);

        if (subnode == list_head(appendplans))  /* first node? */
            plan->startup_cost = subplan->startup_cost;
        plan->total_cost += subplan->total_cost;
        plan->plan_rows += subplan->plan_rows;
        total_size += subplan->plan_width * subplan->plan_rows;
    }
    if (plan->plan_rows > 0)
        plan->plan_width = rint(total_size / plan->plan_rows);
    else
        plan->plan_width = 0;

    plan->targetlist = tlist;
    plan->qual = NIL;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->appendplans = appendplans;

    return node;
}

RecursiveUnion *
make_recursive_union(List *tlist,
                     Plan *lefttree,
                     Plan *righttree,
                     int wtParam,
                     List *distinctList,
                     long numGroups)
{
    RecursiveUnion *node = makeNode(RecursiveUnion);
    Plan       *plan = &node->plan;
    int         numCols = list_length(distinctList);

    cost_recursive_union(plan, lefttree, righttree);

    plan->targetlist = tlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = righttree;
    node->wtParam = wtParam;

    /*
     * convert SortGroupClause list into arrays of attr indexes and equality
     * operators, as wanted by executor
     */
    node->numCols = numCols;
    if (numCols > 0)
    {
        int         keyno = 0;
        AttrNumber *dupColIdx;
        Oid        *dupOperators;
        ListCell   *slitem;

        dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
        dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);

        foreach(slitem, distinctList)
        {
            SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
            TargetEntry *tle = get_sortgroupclause_tle(sortcl,
                                                       plan->targetlist);

            dupColIdx[keyno] = tle->resno;
            dupOperators[keyno] = sortcl->eqop;
            Assert(OidIsValid(dupOperators[keyno]));
            keyno++;
        }
        node->dupColIdx = dupColIdx;
        node->dupOperators = dupOperators;
    }
    node->numGroups = numGroups;

    return node;
}

static BitmapAnd *
make_bitmap_and(List *bitmapplans)
{
    BitmapAnd  *node = makeNode(BitmapAnd);
    Plan       *plan = &node->plan;

    /* cost should be inserted by caller */
    plan->targetlist = NIL;
    plan->qual = NIL;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->bitmapplans = bitmapplans;

    return node;
}

static BitmapOr *
make_bitmap_or(List *bitmapplans)
{
    BitmapOr   *node = makeNode(BitmapOr);
    Plan       *plan = &node->plan;

    /* cost should be inserted by caller */
    plan->targetlist = NIL;
    plan->qual = NIL;
    plan->lefttree = NULL;
    plan->righttree = NULL;
    node->bitmapplans = bitmapplans;

    return node;
}

static NestLoop *
make_nestloop(List *tlist,
              List *joinclauses,
              List *otherclauses,
              List *nestParams,
              Plan *lefttree,
              Plan *righttree,
              JoinType jointype)
{
    NestLoop   *node = makeNode(NestLoop);
    Plan       *plan = &node->join.plan;

    /* cost should be inserted by caller */
    plan->targetlist = tlist;
    plan->qual = otherclauses;
    plan->lefttree = lefttree;
    plan->righttree = righttree;
    node->join.jointype = jointype;
    node->join.joinqual = joinclauses;
    node->nestParams = nestParams;

    return node;
}

static HashJoin *
make_hashjoin(List *tlist,
              List *joinclauses,
              List *otherclauses,
              List *hashclauses,
              Plan *lefttree,
              Plan *righttree,
              JoinType jointype)
{
    HashJoin   *node = makeNode(HashJoin);
    Plan       *plan = &node->join.plan;

    /* cost should be inserted by caller */
    plan->targetlist = tlist;
    plan->qual = otherclauses;
    plan->lefttree = lefttree;
    plan->righttree = righttree;
    node->hashclauses = hashclauses;
    node->join.jointype = jointype;
    node->join.joinqual = joinclauses;

    return node;
}

static Hash *
make_hash(Plan *lefttree,
          Oid skewTable,
          AttrNumber skewColumn,
          bool skewInherit,
          Oid skewColType,
          int32 skewColTypmod)
{
    Hash       *node = makeNode(Hash);
    Plan       *plan = &node->plan;

    copy_plan_costsize(plan, lefttree);

    /*
     * For plausibility, make startup & total costs equal total cost of input
     * plan; this only affects EXPLAIN display not decisions.
     */
    plan->startup_cost = plan->total_cost;
    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    node->skewTable = skewTable;
    node->skewColumn = skewColumn;
    node->skewInherit = skewInherit;
    node->skewColType = skewColType;
    node->skewColTypmod = skewColTypmod;

    return node;
}

static MergeJoin *
make_mergejoin(List *tlist,
               List *joinclauses,
               List *otherclauses,
               List *mergeclauses,
               Oid *mergefamilies,
               Oid *mergecollations,
               int *mergestrategies,
               bool *mergenullsfirst,
               Plan *lefttree,
               Plan *righttree,
               JoinType jointype)
{
    MergeJoin  *node = makeNode(MergeJoin);
    Plan       *plan = &node->join.plan;

    /* cost should be inserted by caller */
    plan->targetlist = tlist;
    plan->qual = otherclauses;
    plan->lefttree = lefttree;
    plan->righttree = righttree;
    node->mergeclauses = mergeclauses;
    node->mergeFamilies = mergefamilies;
    node->mergeCollations = mergecollations;
    node->mergeStrategies = mergestrategies;
    node->mergeNullsFirst = mergenullsfirst;
    node->join.jointype = jointype;
    node->join.joinqual = joinclauses;

    return node;
}

/*
 * make_sort --- basic routine to build a Sort plan node
 *
 * Caller must have built the sortColIdx, sortOperators, collations, and
 * nullsFirst arrays already.
 * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
 */
static Sort *
make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
          AttrNumber *sortColIdx, Oid *sortOperators,
          Oid *collations, bool *nullsFirst,
          double limit_tuples)
{
    Sort       *node = makeNode(Sort);
    Plan       *plan = &node->plan;
    Path        sort_path;      /* dummy for result of cost_sort */

    copy_plan_costsize(plan, lefttree); /* only care about copying size */
    cost_sort(&sort_path, root, NIL,
              lefttree->total_cost,
              lefttree->plan_rows,
              lefttree->plan_width,
              0.0,
              work_mem,
              limit_tuples);
    plan->startup_cost = sort_path.startup_cost;
    plan->total_cost = sort_path.total_cost;
    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;
    node->numCols = numCols;
    node->sortColIdx = sortColIdx;
    node->sortOperators = sortOperators;
    node->collations = collations;
    node->nullsFirst = nullsFirst;

    return node;
}

/*
 * prepare_sort_from_pathkeys
 *    Prepare to sort according to given pathkeys
 *
 * This is used to set up for both Sort and MergeAppend nodes.  It calculates
 * the executor's representation of the sort key information, and adjusts the
 * plan targetlist if needed to add resjunk sort columns.
 *
 * Input parameters:
 *    'lefttree' is the plan node which yields input tuples
 *    'pathkeys' is the list of pathkeys by which the result is to be sorted
 *    'relids' identifies the child relation being sorted, if any
 *    'reqColIdx' is NULL or an array of required sort key column numbers
 *    'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place
 *
 * We must convert the pathkey information into arrays of sort key column
 * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
 * which is the representation the executor wants.  These are returned into
 * the output parameters *p_numsortkeys etc.
 *
 * When looking for matches to an EquivalenceClass's members, we will only
 * consider child EC members if they match 'relids'.  This protects against
 * possible incorrect matches to child expressions that contain no Vars.
 *
 * If reqColIdx isn't NULL then it contains sort key column numbers that
 * we should match.  This is used when making child plans for a MergeAppend;
 * it's an error if we can't match the columns.
 *
 * If the pathkeys include expressions that aren't simple Vars, we will
 * usually need to add resjunk items to the input plan's targetlist to
 * compute these expressions, since the Sort/MergeAppend node itself won't
 * do any such calculations.  If the input plan type isn't one that can do
 * projections, this means adding a Result node just to do the projection.
 * However, the caller can pass adjust_tlist_in_place = TRUE to force the
 * lefttree tlist to be modified in-place regardless of whether the node type
 * can project --- we use this for fixing the tlist of MergeAppend itself.
 *
 * Returns the node which is to be the input to the Sort (either lefttree,
 * or a Result stacked atop lefttree).
 */
static Plan *
prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
                           Relids relids,
                           const AttrNumber *reqColIdx,
                           bool adjust_tlist_in_place,
                           int *p_numsortkeys,
                           AttrNumber **p_sortColIdx,
                           Oid **p_sortOperators,
                           Oid **p_collations,
                           bool **p_nullsFirst)
{
    List       *tlist = lefttree->targetlist;
    ListCell   *i;
    int         numsortkeys;
    AttrNumber *sortColIdx;
    Oid        *sortOperators;
    Oid        *collations;
    bool       *nullsFirst;

    /*
     * We will need at most list_length(pathkeys) sort columns; possibly less
     */
    numsortkeys = list_length(pathkeys);
    sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
    sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
    collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
    nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));

    numsortkeys = 0;

    foreach(i, pathkeys)
    {
        PathKey    *pathkey = (PathKey *) lfirst(i);
        EquivalenceClass *ec = pathkey->pk_eclass;
        EquivalenceMember *em;
        TargetEntry *tle = NULL;
        Oid         pk_datatype = InvalidOid;
        Oid         sortop;
        ListCell   *j;

        if (ec->ec_has_volatile)
        {
            /*
             * If the pathkey's EquivalenceClass is volatile, then it must
             * have come from an ORDER BY clause, and we have to match it to
             * that same targetlist entry.
             */
            if (ec->ec_sortref == 0)    /* can't happen */
                elog(ERROR, "volatile EquivalenceClass has no sortref");
            tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
            Assert(tle);
            Assert(list_length(ec->ec_members) == 1);
            pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
        }
        else if (reqColIdx != NULL)
        {
            /*
             * If we are given a sort column number to match, only consider
             * the single TLE at that position.  It's possible that there is
             * no such TLE, in which case fall through and generate a resjunk
             * targetentry (we assume this must have happened in the parent
             * plan as well).  If there is a TLE but it doesn't match the
             * pathkey's EC, we do the same, which is probably the wrong thing
             * but we'll leave it to caller to complain about the mismatch.
             */
            tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
            if (tle)
            {
                em = find_ec_member_for_tle(ec, tle, relids);
                if (em)
                {
                    /* found expr at right place in tlist */
                    pk_datatype = em->em_datatype;
                }
                else
                    tle = NULL;
            }
        }
        else
        {
            /*
             * Otherwise, we can sort by any non-constant expression listed in
             * the pathkey's EquivalenceClass.  For now, we take the first
             * tlist item found in the EC. If there's no match, we'll generate
             * a resjunk entry using the first EC member that is an expression
             * in the input's vars.  (The non-const restriction only matters
             * if the EC is below_outer_join; but if it isn't, it won't
             * contain consts anyway, else we'd have discarded the pathkey as
             * redundant.)
             *
             * XXX if we have a choice, is there any way of figuring out which
             * might be cheapest to execute?  (For example, int4lt is likely
             * much cheaper to execute than numericlt, but both might appear
             * in the same equivalence class...)  Not clear that we ever will
             * have an interesting choice in practice, so it may not matter.
             */
            foreach(j, tlist)
            {
                tle = (TargetEntry *) lfirst(j);
                em = find_ec_member_for_tle(ec, tle, relids);
                if (em)
                {
                    /* found expr already in tlist */
                    pk_datatype = em->em_datatype;
                    break;
                }
                tle = NULL;
            }
        }

        if (!tle)
        {
            /*
             * No matching tlist item; look for a computable expression. Note
             * that we treat Aggrefs as if they were variables; this is
             * necessary when attempting to sort the output from an Agg node
             * for use in a WindowFunc (since grouping_planner will have
             * treated the Aggrefs as variables, too).
             */
            Expr       *sortexpr = NULL;

            foreach(j, ec->ec_members)
            {
                EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
                List       *exprvars;
                ListCell   *k;

                /*
                 * We shouldn't be trying to sort by an equivalence class that
                 * contains a constant, so no need to consider such cases any
                 * further.
                 */
                if (em->em_is_const)
                    continue;

                /*
                 * Ignore child members unless they match the rel being
                 * sorted.
                 */
                if (em->em_is_child &&
                    !bms_equal(em->em_relids, relids))
                    continue;

                sortexpr = em->em_expr;
                exprvars = pull_var_clause((Node *) sortexpr,
                                           PVC_INCLUDE_AGGREGATES,
                                           PVC_INCLUDE_PLACEHOLDERS);
                foreach(k, exprvars)
                {
                    if (!tlist_member_ignore_relabel(lfirst(k), tlist))
                        break;
                }
                list_free(exprvars);
                if (!k)
                {
                    pk_datatype = em->em_datatype;
                    break;      /* found usable expression */
                }
            }
            if (!j)
                elog(ERROR, "could not find pathkey item to sort");

            /*
             * Do we need to insert a Result node?
             */
            if (!adjust_tlist_in_place &&
                !is_projection_capable_plan(lefttree))
            {
                /* copy needed so we don't modify input's tlist below */
                tlist = copyObject(tlist);
                lefttree = (Plan *) make_result(root, tlist, NULL,
                                                lefttree);
            }

            /* Don't bother testing is_projection_capable_plan again */
            adjust_tlist_in_place = true;

            /*
             * Add resjunk entry to input's tlist
             */
            tle = makeTargetEntry(sortexpr,
                                  list_length(tlist) + 1,
                                  NULL,
                                  true);
            tlist = lappend(tlist, tle);
            lefttree->targetlist = tlist;       /* just in case NIL before */
        }

        /*
         * Look up the correct sort operator from the PathKey's slightly
         * abstracted representation.
         */
        sortop = get_opfamily_member(pathkey->pk_opfamily,
                                     pk_datatype,
                                     pk_datatype,
                                     pathkey->pk_strategy);
        if (!OidIsValid(sortop))    /* should not happen */
            elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
                 pathkey->pk_strategy, pk_datatype, pk_datatype,
                 pathkey->pk_opfamily);

        /* Add the column to the sort arrays */
        sortColIdx[numsortkeys] = tle->resno;
        sortOperators[numsortkeys] = sortop;
        collations[numsortkeys] = ec->ec_collation;
        nullsFirst[numsortkeys] = pathkey->pk_nulls_first;
        numsortkeys++;
    }

    /* Return results */
    *p_numsortkeys = numsortkeys;
    *p_sortColIdx = sortColIdx;
    *p_sortOperators = sortOperators;
    *p_collations = collations;
    *p_nullsFirst = nullsFirst;

    return lefttree;
}

/*
 * find_ec_member_for_tle
 *      Locate an EquivalenceClass member matching the given TLE, if any
 *
 * Child EC members are ignored unless they match 'relids'.
 */
static EquivalenceMember *
find_ec_member_for_tle(EquivalenceClass *ec,
                       TargetEntry *tle,
                       Relids relids)
{
    Expr       *tlexpr;
    ListCell   *lc;

    /* We ignore binary-compatible relabeling on both ends */
    tlexpr = tle->expr;
    while (tlexpr && IsA(tlexpr, RelabelType))
        tlexpr = ((RelabelType *) tlexpr)->arg;

    foreach(lc, ec->ec_members)
    {
        EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
        Expr       *emexpr;

        /*
         * We shouldn't be trying to sort by an equivalence class that
         * contains a constant, so no need to consider such cases any further.
         */
        if (em->em_is_const)
            continue;

        /*
         * Ignore child members unless they match the rel being sorted.
         */
        if (em->em_is_child &&
            !bms_equal(em->em_relids, relids))
            continue;

        /* Match if same expression (after stripping relabel) */
        emexpr = em->em_expr;
        while (emexpr && IsA(emexpr, RelabelType))
            emexpr = ((RelabelType *) emexpr)->arg;

        if (equal(emexpr, tlexpr))
            return em;
    }

    return NULL;
}

/*
 * make_sort_from_pathkeys
 *    Create sort plan to sort according to given pathkeys
 *
 *    'lefttree' is the node which yields input tuples
 *    'pathkeys' is the list of pathkeys by which the result is to be sorted
 *    'limit_tuples' is the bound on the number of output tuples;
 *              -1 if no bound
 */
Sort *
make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
                        double limit_tuples)
{
    int         numsortkeys;
    AttrNumber *sortColIdx;
    Oid        *sortOperators;
    Oid        *collations;
    bool       *nullsFirst;

    /* Compute sort column info, and adjust lefttree as needed */
    lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
                                          NULL,
                                          NULL,
                                          false,
                                          &numsortkeys,
                                          &sortColIdx,
                                          &sortOperators,
                                          &collations,
                                          &nullsFirst);

    /* Now build the Sort node */
    return make_sort(root, lefttree, numsortkeys,
                     sortColIdx, sortOperators, collations,
                     nullsFirst, limit_tuples);
}

/*
 * make_sort_from_sortclauses
 *    Create sort plan to sort according to given sortclauses
 *
 *    'sortcls' is a list of SortGroupClauses
 *    'lefttree' is the node which yields input tuples
 */
Sort *
make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
{
    List       *sub_tlist = lefttree->targetlist;
    ListCell   *l;
    int         numsortkeys;
    AttrNumber *sortColIdx;
    Oid        *sortOperators;
    Oid        *collations;
    bool       *nullsFirst;

    /* Convert list-ish representation to arrays wanted by executor */
    numsortkeys = list_length(sortcls);
    sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
    sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
    collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
    nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));

    numsortkeys = 0;
    foreach(l, sortcls)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
        TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);

        sortColIdx[numsortkeys] = tle->resno;
        sortOperators[numsortkeys] = sortcl->sortop;
        collations[numsortkeys] = exprCollation((Node *) tle->expr);
        nullsFirst[numsortkeys] = sortcl->nulls_first;
        numsortkeys++;
    }

    return make_sort(root, lefttree, numsortkeys,
                     sortColIdx, sortOperators, collations,
                     nullsFirst, -1.0);
}

/*
 * make_sort_from_groupcols
 *    Create sort plan to sort based on grouping columns
 *
 * 'groupcls' is the list of SortGroupClauses
 * 'grpColIdx' gives the column numbers to use
 *
 * This might look like it could be merged with make_sort_from_sortclauses,
 * but presently we *must* use the grpColIdx[] array to locate sort columns,
 * because the child plan's tlist is not marked with ressortgroupref info
 * appropriate to the grouping node.  So, only the sort ordering info
 * is used from the SortGroupClause entries.
 */
Sort *
make_sort_from_groupcols(PlannerInfo *root,
                         List *groupcls,
                         AttrNumber *grpColIdx,
                         Plan *lefttree)
{
    List       *sub_tlist = lefttree->targetlist;
    ListCell   *l;
    int         numsortkeys;
    AttrNumber *sortColIdx;
    Oid        *sortOperators;
    Oid        *collations;
    bool       *nullsFirst;

    /* Convert list-ish representation to arrays wanted by executor */
    numsortkeys = list_length(groupcls);
    sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
    sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
    collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
    nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));

    numsortkeys = 0;
    foreach(l, groupcls)
    {
        SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
        TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[numsortkeys]);

        sortColIdx[numsortkeys] = tle->resno;
        sortOperators[numsortkeys] = grpcl->sortop;
        collations[numsortkeys] = exprCollation((Node *) tle->expr);
        nullsFirst[numsortkeys] = grpcl->nulls_first;
        numsortkeys++;
    }

    return make_sort(root, lefttree, numsortkeys,
                     sortColIdx, sortOperators, collations,
                     nullsFirst, -1.0);
}

static Material *
make_material(Plan *lefttree)
{
    Material   *node = makeNode(Material);
    Plan       *plan = &node->plan;

    /* cost should be inserted by caller */
    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    return node;
}

/*
 * materialize_finished_plan: stick a Material node atop a completed plan
 *
 * There are a couple of places where we want to attach a Material node
 * after completion of subquery_planner().  This currently requires hackery.
 * Since subquery_planner has already run SS_finalize_plan on the subplan
 * tree, we have to kluge up parameter lists for the Material node.
 * Possibly this could be fixed by postponing SS_finalize_plan processing
 * until setrefs.c is run?
 */
Plan *
materialize_finished_plan(Plan *subplan)
{
    Plan       *matplan;
    Path        matpath;        /* dummy for result of cost_material */

    matplan = (Plan *) make_material(subplan);

    /* Set cost data */
    cost_material(&matpath,
                  subplan->startup_cost,
                  subplan->total_cost,
                  subplan->plan_rows,
                  subplan->plan_width);
    matplan->startup_cost = matpath.startup_cost;
    matplan->total_cost = matpath.total_cost;
    matplan->plan_rows = subplan->plan_rows;
    matplan->plan_width = subplan->plan_width;

    /* parameter kluge --- see comments above */
    matplan->extParam = bms_copy(subplan->extParam);
    matplan->allParam = bms_copy(subplan->allParam);

    return matplan;
}

Agg *
make_agg(PlannerInfo *root, List *tlist, List *qual,
         AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
         int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
         long numGroups,
         Plan *lefttree)
{
    Agg        *node = makeNode(Agg);
    Plan       *plan = &node->plan;
    Path        agg_path;       /* dummy for result of cost_agg */
    QualCost    qual_cost;

    node->aggstrategy = aggstrategy;
    node->numCols = numGroupCols;
    node->grpColIdx = grpColIdx;
    node->grpOperators = grpOperators;
    node->numGroups = numGroups;

    copy_plan_costsize(plan, lefttree); /* only care about copying size */
    cost_agg(&agg_path, root,
             aggstrategy, aggcosts,
             numGroupCols, numGroups,
             lefttree->startup_cost,
             lefttree->total_cost,
             lefttree->plan_rows);
    plan->startup_cost = agg_path.startup_cost;
    plan->total_cost = agg_path.total_cost;

    /*
     * We will produce a single output tuple if not grouping, and a tuple per
     * group otherwise.
     */
    if (aggstrategy == AGG_PLAIN)
        plan->plan_rows = 1;
    else
        plan->plan_rows = numGroups;

    /*
     * We also need to account for the cost of evaluation of the qual (ie, the
     * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
     * anything for Aggref nodes; this is okay since they are really
     * comparable to Vars.
     *
     * See notes in add_tlist_costs_to_plan about why only make_agg,
     * make_windowagg and make_group worry about tlist eval cost.
     */
    if (qual)
    {
        cost_qual_eval(&qual_cost, qual, root);
        plan->startup_cost += qual_cost.startup;
        plan->total_cost += qual_cost.startup;
        plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
    }
    add_tlist_costs_to_plan(root, plan, tlist);

    plan->qual = qual;
    plan->targetlist = tlist;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    return node;
}

WindowAgg *
make_windowagg(PlannerInfo *root, List *tlist,
               List *windowFuncs, Index winref,
               int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
               int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
               int frameOptions, Node *startOffset, Node *endOffset,
               Plan *lefttree)
{
    WindowAgg  *node = makeNode(WindowAgg);
    Plan       *plan = &node->plan;
    Path        windowagg_path; /* dummy for result of cost_windowagg */

    node->winref = winref;
    node->partNumCols = partNumCols;
    node->partColIdx = partColIdx;
    node->partOperators = partOperators;
    node->ordNumCols = ordNumCols;
    node->ordColIdx = ordColIdx;
    node->ordOperators = ordOperators;
    node->frameOptions = frameOptions;
    node->startOffset = startOffset;
    node->endOffset = endOffset;

    copy_plan_costsize(plan, lefttree); /* only care about copying size */
    cost_windowagg(&windowagg_path, root,
                   windowFuncs, partNumCols, ordNumCols,
                   lefttree->startup_cost,
                   lefttree->total_cost,
                   lefttree->plan_rows);
    plan->startup_cost = windowagg_path.startup_cost;
    plan->total_cost = windowagg_path.total_cost;

    /*
     * We also need to account for the cost of evaluation of the tlist.
     *
     * See notes in add_tlist_costs_to_plan about why only make_agg,
     * make_windowagg and make_group worry about tlist eval cost.
     */
    add_tlist_costs_to_plan(root, plan, tlist);

    plan->targetlist = tlist;
    plan->lefttree = lefttree;
    plan->righttree = NULL;
    /* WindowAgg nodes never have a qual clause */
    plan->qual = NIL;

    return node;
}

Group *
make_group(PlannerInfo *root,
           List *tlist,
           List *qual,
           int numGroupCols,
           AttrNumber *grpColIdx,
           Oid *grpOperators,
           double numGroups,
           Plan *lefttree)
{
    Group      *node = makeNode(Group);
    Plan       *plan = &node->plan;
    Path        group_path;     /* dummy for result of cost_group */
    QualCost    qual_cost;

    node->numCols = numGroupCols;
    node->grpColIdx = grpColIdx;
    node->grpOperators = grpOperators;

    copy_plan_costsize(plan, lefttree); /* only care about copying size */
    cost_group(&group_path, root,
               numGroupCols, numGroups,
               lefttree->startup_cost,
               lefttree->total_cost,
               lefttree->plan_rows);
    plan->startup_cost = group_path.startup_cost;
    plan->total_cost = group_path.total_cost;

    /* One output tuple per estimated result group */
    plan->plan_rows = numGroups;

    /*
     * We also need to account for the cost of evaluation of the qual (ie, the
     * HAVING clause) and the tlist.
     *
     * XXX this double-counts the cost of evaluation of any expressions used
     * for grouping, since in reality those will have been evaluated at a
     * lower plan level and will only be copied by the Group node. Worth
     * fixing?
     *
     * See notes in add_tlist_costs_to_plan about why only make_agg,
     * make_windowagg and make_group worry about tlist eval cost.
     */
    if (qual)
    {
        cost_qual_eval(&qual_cost, qual, root);
        plan->startup_cost += qual_cost.startup;
        plan->total_cost += qual_cost.startup;
        plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
    }
    add_tlist_costs_to_plan(root, plan, tlist);

    plan->qual = qual;
    plan->targetlist = tlist;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    return node;
}

/*
 * distinctList is a list of SortGroupClauses, identifying the targetlist items
 * that should be considered by the Unique filter.  The input path must
 * already be sorted accordingly.
 */
Unique *
make_unique(Plan *lefttree, List *distinctList)
{
    Unique     *node = makeNode(Unique);
    Plan       *plan = &node->plan;
    int         numCols = list_length(distinctList);
    int         keyno = 0;
    AttrNumber *uniqColIdx;
    Oid        *uniqOperators;
    ListCell   *slitem;

    copy_plan_costsize(plan, lefttree);

    /*
     * Charge one cpu_operator_cost per comparison per input tuple. We assume
     * all columns get compared at most of the tuples.  (XXX probably this is
     * an overestimate.)
     */
    plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;

    /*
     * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
     * we assume the filter removes nothing.  The caller must alter this if he
     * has a better idea.
     */

    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    /*
     * convert SortGroupClause list into arrays of attr indexes and equality
     * operators, as wanted by executor
     */
    Assert(numCols > 0);
    uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
    uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);

    foreach(slitem, distinctList)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
        TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);

        uniqColIdx[keyno] = tle->resno;
        uniqOperators[keyno] = sortcl->eqop;
        Assert(OidIsValid(uniqOperators[keyno]));
        keyno++;
    }

    node->numCols = numCols;
    node->uniqColIdx = uniqColIdx;
    node->uniqOperators = uniqOperators;

    return node;
}

/*
 * distinctList is a list of SortGroupClauses, identifying the targetlist
 * items that should be considered by the SetOp filter.  The input path must
 * already be sorted accordingly.
 */
SetOp *
make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
           List *distinctList, AttrNumber flagColIdx, int firstFlag,
           long numGroups, double outputRows)
{
    SetOp      *node = makeNode(SetOp);
    Plan       *plan = &node->plan;
    int         numCols = list_length(distinctList);
    int         keyno = 0;
    AttrNumber *dupColIdx;
    Oid        *dupOperators;
    ListCell   *slitem;

    copy_plan_costsize(plan, lefttree);
    plan->plan_rows = outputRows;

    /*
     * Charge one cpu_operator_cost per comparison per input tuple. We assume
     * all columns get compared at most of the tuples.
     */
    plan->total_cost += cpu_operator_cost * lefttree->plan_rows * numCols;

    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    /*
     * convert SortGroupClause list into arrays of attr indexes and equality
     * operators, as wanted by executor
     */
    Assert(numCols > 0);
    dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
    dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);

    foreach(slitem, distinctList)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
        TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);

        dupColIdx[keyno] = tle->resno;
        dupOperators[keyno] = sortcl->eqop;
        Assert(OidIsValid(dupOperators[keyno]));
        keyno++;
    }

    node->cmd = cmd;
    node->strategy = strategy;
    node->numCols = numCols;
    node->dupColIdx = dupColIdx;
    node->dupOperators = dupOperators;
    node->flagColIdx = flagColIdx;
    node->firstFlag = firstFlag;
    node->numGroups = numGroups;

    return node;
}

/*
 * make_lockrows
 *    Build a LockRows plan node
 */
LockRows *
make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
{
    LockRows   *node = makeNode(LockRows);
    Plan       *plan = &node->plan;

    copy_plan_costsize(plan, lefttree);

    /* charge cpu_tuple_cost to reflect locking costs (underestimate?) */
    plan->total_cost += cpu_tuple_cost * plan->plan_rows;

    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    node->rowMarks = rowMarks;
    node->epqParam = epqParam;

    return node;
}

/*
 * Note: offset_est and count_est are passed in to save having to repeat
 * work already done to estimate the values of the limitOffset and limitCount
 * expressions.  Their values are as returned by preprocess_limit (0 means
 * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
 * with that function!
 */
Limit *
make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
           int64 offset_est, int64 count_est)
{
    Limit      *node = makeNode(Limit);
    Plan       *plan = &node->plan;

    copy_plan_costsize(plan, lefttree);

    /*
     * Adjust the output rows count and costs according to the offset/limit.
     * This is only a cosmetic issue if we are at top level, but if we are
     * building a subquery then it's important to report correct info to the
     * outer planner.
     *
     * When the offset or count couldn't be estimated, use 10% of the
     * estimated number of rows emitted from the subplan.
     */
    if (offset_est != 0)
    {
        double      offset_rows;

        if (offset_est > 0)
            offset_rows = (double) offset_est;
        else
            offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
        if (offset_rows > plan->plan_rows)
            offset_rows = plan->plan_rows;
        if (plan->plan_rows > 0)
            plan->startup_cost +=
                (plan->total_cost - plan->startup_cost)
                * offset_rows / plan->plan_rows;
        plan->plan_rows -= offset_rows;
        if (plan->plan_rows < 1)
            plan->plan_rows = 1;
    }

    if (count_est != 0)
    {
        double      count_rows;

        if (count_est > 0)
            count_rows = (double) count_est;
        else
            count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
        if (count_rows > plan->plan_rows)
            count_rows = plan->plan_rows;
        if (plan->plan_rows > 0)
            plan->total_cost = plan->startup_cost +
                (plan->total_cost - plan->startup_cost)
                * count_rows / plan->plan_rows;
        plan->plan_rows = count_rows;
        if (plan->plan_rows < 1)
            plan->plan_rows = 1;
    }

    plan->targetlist = lefttree->targetlist;
    plan->qual = NIL;
    plan->lefttree = lefttree;
    plan->righttree = NULL;

    node->limitOffset = limitOffset;
    node->limitCount = limitCount;

    return node;
}

/*
 * make_result
 *    Build a Result plan node
 *
 * If we have a subplan, assume that any evaluation costs for the gating qual
 * were already factored into the subplan's startup cost, and just copy the
 * subplan cost.  If there's no subplan, we should include the qual eval
 * cost.  In either case, tlist eval cost is not to be included here.
 */
Result *
make_result(PlannerInfo *root,
            List *tlist,
            Node *resconstantqual,
            Plan *subplan)
{
    Result     *node = makeNode(Result);
    Plan       *plan = &node->plan;

    if (subplan)
        copy_plan_costsize(plan, subplan);
    else
    {
        plan->startup_cost = 0;
        plan->total_cost = cpu_tuple_cost;
        plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
        plan->plan_width = 0;   /* XXX is it worth being smarter? */
        if (resconstantqual)
        {
            QualCost    qual_cost;

            cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
            /* resconstantqual is evaluated once at startup */
            plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
            plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
        }
    }

    plan->targetlist = tlist;
    plan->qual = NIL;
    plan->lefttree = subplan;
    plan->righttree = NULL;
    node->resconstantqual = resconstantqual;

    return node;
}

/*
 * make_modifytable
 *    Build a ModifyTable plan node
 *
 * Currently, we don't charge anything extra for the actual table modification
 * work, nor for the RETURNING expressions if any.  It would only be window
 * dressing, since these are always top-level nodes and there is no way for
 * the costs to change any higher-level planning choices.  But we might want
 * to make it look better sometime.
 */
ModifyTable *
make_modifytable(PlannerInfo *root,
                 CmdType operation, bool canSetTag,
                 List *resultRelations,
                 List *subplans, List *returningLists,
                 List *rowMarks, int epqParam)
{
    ModifyTable *node = makeNode(ModifyTable);
    Plan       *plan = &node->plan;
    double      total_size;
    List       *fdw_private_list;
    ListCell   *subnode;
    ListCell   *lc;
    int         i;

    Assert(list_length(resultRelations) == list_length(subplans));
    Assert(returningLists == NIL ||
           list_length(resultRelations) == list_length(returningLists));

    /*
     * Compute cost as sum of subplan costs.
     */
    plan->startup_cost = 0;
    plan->total_cost = 0;
    plan->plan_rows = 0;
    total_size = 0;
    foreach(subnode, subplans)
    {
        Plan       *subplan = (Plan *) lfirst(subnode);

        if (subnode == list_head(subplans))     /* first node? */
            plan->startup_cost = subplan->startup_cost;
        plan->total_cost += subplan->total_cost;
        plan->plan_rows += subplan->plan_rows;
        total_size += subplan->plan_width * subplan->plan_rows;
    }
    if (plan->plan_rows > 0)
        plan->plan_width = rint(total_size / plan->plan_rows);
    else
        plan->plan_width = 0;

    node->plan.lefttree = NULL;
    node->plan.righttree = NULL;
    node->plan.qual = NIL;
    /* setrefs.c will fill in the targetlist, if needed */
    node->plan.targetlist = NIL;

    node->operation = operation;
    node->canSetTag = canSetTag;
    node->resultRelations = resultRelations;
    node->resultRelIndex = -1;  /* will be set correctly in setrefs.c */
    node->plans = subplans;
    node->returningLists = returningLists;
    node->rowMarks = rowMarks;
    node->epqParam = epqParam;

    /*
     * For each result relation that is a foreign table, allow the FDW to
     * construct private plan data, and accumulate it all into a list.
     */
    fdw_private_list = NIL;
    i = 0;
    foreach(lc, resultRelations)
    {
        Index       rti = lfirst_int(lc);
        FdwRoutine *fdwroutine;
        List       *fdw_private;

        /*
         * If possible, we want to get the FdwRoutine from our RelOptInfo for
         * the table.  But sometimes we don't have a RelOptInfo and must get
         * it the hard way.  (In INSERT, the target relation is not scanned,
         * so it's not a baserel; and there are also corner cases for
         * updatable views where the target rel isn't a baserel.)
         */
        if (rti < root->simple_rel_array_size &&
            root->simple_rel_array[rti] != NULL)
        {
            RelOptInfo *resultRel = root->simple_rel_array[rti];

            fdwroutine = resultRel->fdwroutine;
        }
        else
        {
            RangeTblEntry *rte = planner_rt_fetch(rti, root);

            Assert(rte->rtekind == RTE_RELATION);
            if (rte->relkind == RELKIND_FOREIGN_TABLE)
                fdwroutine = GetFdwRoutineByRelId(rte->relid);
            else
                fdwroutine = NULL;
        }

        if (fdwroutine != NULL &&
            fdwroutine->PlanForeignModify != NULL)
            fdw_private = fdwroutine->PlanForeignModify(root, node, rti, i);
        else
            fdw_private = NIL;
        fdw_private_list = lappend(fdw_private_list, fdw_private);
        i++;
    }
    node->fdwPrivLists = fdw_private_list;

    return node;
}

/*
 * is_projection_capable_plan
 *      Check whether a given Plan node is able to do projection.
 */
bool
is_projection_capable_plan(Plan *plan)
{
    /* Most plan types can project, so just list the ones that can't */
    switch (nodeTag(plan))
    {
        case T_Hash:
        case T_Material:
        case T_Sort:
        case T_Unique:
        case T_SetOp:
        case T_LockRows:
        case T_Limit:
        case T_ModifyTable:
        case T_Append:
        case T_MergeAppend:
        case T_RecursiveUnion:
            return false;
        default:
            break;
    }
    return true;
}