relnode.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * relnode.c
 *    Relation-node lookup/construction routines
 *
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/optimizer/util/relnode.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/plancat.h"
#include "optimizer/restrictinfo.h"
#include "utils/hsearch.h"


typedef struct JoinHashEntry
{
    Relids      join_relids;    /* hash key --- MUST BE FIRST */
    RelOptInfo *join_rel;
} JoinHashEntry;

static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
                    RelOptInfo *input_rel);
static List *build_joinrel_restrictlist(PlannerInfo *root,
                           RelOptInfo *joinrel,
                           RelOptInfo *outer_rel,
                           RelOptInfo *inner_rel);
static void build_joinrel_joinlist(RelOptInfo *joinrel,
                       RelOptInfo *outer_rel,
                       RelOptInfo *inner_rel);
static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
                              List *joininfo_list,
                              List *new_restrictlist);
static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
                          List *joininfo_list,
                          List *new_joininfo);


/*
 * setup_simple_rel_arrays
 *    Prepare the arrays we use for quickly accessing base relations.
 */
void
setup_simple_rel_arrays(PlannerInfo *root)
{
    Index       rti;
    ListCell   *lc;

    /* Arrays are accessed using RT indexes (1..N) */
    root->simple_rel_array_size = list_length(root->parse->rtable) + 1;

    /* simple_rel_array is initialized to all NULLs */
    root->simple_rel_array = (RelOptInfo **)
        palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));

    /* simple_rte_array is an array equivalent of the rtable list */
    root->simple_rte_array = (RangeTblEntry **)
        palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
    rti = 1;
    foreach(lc, root->parse->rtable)
    {
        RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);

        root->simple_rte_array[rti++] = rte;
    }
}

/*
 * build_simple_rel
 *    Construct a new RelOptInfo for a base relation or 'other' relation.
 */
RelOptInfo *
build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
{
    RelOptInfo *rel;
    RangeTblEntry *rte;

    /* Rel should not exist already */
    Assert(relid > 0 && relid < root->simple_rel_array_size);
    if (root->simple_rel_array[relid] != NULL)
        elog(ERROR, "rel %d already exists", relid);

    /* Fetch RTE for relation */
    rte = root->simple_rte_array[relid];
    Assert(rte != NULL);

    rel = makeNode(RelOptInfo);
    rel->reloptkind = reloptkind;
    rel->relids = bms_make_singleton(relid);
    rel->rows = 0;
    rel->width = 0;
    /* cheap startup cost is interesting iff not all tuples to be retrieved */
    rel->consider_startup = (root->tuple_fraction > 0);
    rel->reltargetlist = NIL;
    rel->pathlist = NIL;
    rel->ppilist = NIL;
    rel->cheapest_startup_path = NULL;
    rel->cheapest_total_path = NULL;
    rel->cheapest_unique_path = NULL;
    rel->cheapest_parameterized_paths = NIL;
    rel->relid = relid;
    rel->rtekind = rte->rtekind;
    /* min_attr, max_attr, attr_needed, attr_widths are set below */
    rel->lateral_vars = NIL;
    rel->lateral_relids = NULL;
    rel->indexlist = NIL;
    rel->pages = 0;
    rel->tuples = 0;
    rel->allvisfrac = 0;
    rel->subplan = NULL;
    rel->subroot = NULL;
    rel->subplan_params = NIL;
    rel->fdwroutine = NULL;
    rel->fdw_private = NULL;
    rel->baserestrictinfo = NIL;
    rel->baserestrictcost.startup = 0;
    rel->baserestrictcost.per_tuple = 0;
    rel->joininfo = NIL;
    rel->has_eclass_joins = false;

    /* Check type of rtable entry */
    switch (rte->rtekind)
    {
        case RTE_RELATION:
            /* Table --- retrieve statistics from the system catalogs */
            get_relation_info(root, rte->relid, rte->inh, rel);
            break;
        case RTE_SUBQUERY:
        case RTE_FUNCTION:
        case RTE_VALUES:
        case RTE_CTE:

            /*
             * Subquery, function, or values list --- set up attr range and
             * arrays
             *
             * Note: 0 is included in range to support whole-row Vars
             */
            rel->min_attr = 0;
            rel->max_attr = list_length(rte->eref->colnames);
            rel->attr_needed = (Relids *)
                palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
            rel->attr_widths = (int32 *)
                palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
            break;
        default:
            elog(ERROR, "unrecognized RTE kind: %d",
                 (int) rte->rtekind);
            break;
    }

    /* Save the finished struct in the query's simple_rel_array */
    root->simple_rel_array[relid] = rel;

    /*
     * If this rel is an appendrel parent, recurse to build "other rel"
     * RelOptInfos for its children.  They are "other rels" because they are
     * not in the main join tree, but we will need RelOptInfos to plan access
     * to them.
     */
    if (rte->inh)
    {
        ListCell   *l;

        foreach(l, root->append_rel_list)
        {
            AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);

            /* append_rel_list contains all append rels; ignore others */
            if (appinfo->parent_relid != relid)
                continue;

            (void) build_simple_rel(root, appinfo->child_relid,
                                    RELOPT_OTHER_MEMBER_REL);
        }
    }

    return rel;
}

/*
 * find_base_rel
 *    Find a base or other relation entry, which must already exist.
 */
RelOptInfo *
find_base_rel(PlannerInfo *root, int relid)
{
    RelOptInfo *rel;

    Assert(relid > 0);

    if (relid < root->simple_rel_array_size)
    {
        rel = root->simple_rel_array[relid];
        if (rel)
            return rel;
    }

    elog(ERROR, "no relation entry for relid %d", relid);

    return NULL;                /* keep compiler quiet */
}

/*
 * build_join_rel_hash
 *    Construct the auxiliary hash table for join relations.
 */
static void
build_join_rel_hash(PlannerInfo *root)
{
    HTAB       *hashtab;
    HASHCTL     hash_ctl;
    ListCell   *l;

    /* Create the hash table */
    MemSet(&hash_ctl, 0, sizeof(hash_ctl));
    hash_ctl.keysize = sizeof(Relids);
    hash_ctl.entrysize = sizeof(JoinHashEntry);
    hash_ctl.hash = bitmap_hash;
    hash_ctl.match = bitmap_match;
    hash_ctl.hcxt = CurrentMemoryContext;
    hashtab = hash_create("JoinRelHashTable",
                          256L,
                          &hash_ctl,
                    HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

    /* Insert all the already-existing joinrels */
    foreach(l, root->join_rel_list)
    {
        RelOptInfo *rel = (RelOptInfo *) lfirst(l);
        JoinHashEntry *hentry;
        bool        found;

        hentry = (JoinHashEntry *) hash_search(hashtab,
                                               &(rel->relids),
                                               HASH_ENTER,
                                               &found);
        Assert(!found);
        hentry->join_rel = rel;
    }

    root->join_rel_hash = hashtab;
}

/*
 * find_join_rel
 *    Returns relation entry corresponding to 'relids' (a set of RT indexes),
 *    or NULL if none exists.  This is for join relations.
 */
RelOptInfo *
find_join_rel(PlannerInfo *root, Relids relids)
{
    /*
     * Switch to using hash lookup when list grows "too long".  The threshold
     * is arbitrary and is known only here.
     */
    if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
        build_join_rel_hash(root);

    /*
     * Use either hashtable lookup or linear search, as appropriate.
     *
     * Note: the seemingly redundant hashkey variable is used to avoid taking
     * the address of relids; unless the compiler is exceedingly smart, doing
     * so would force relids out of a register and thus probably slow down the
     * list-search case.
     */
    if (root->join_rel_hash)
    {
        Relids      hashkey = relids;
        JoinHashEntry *hentry;

        hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
                                               &hashkey,
                                               HASH_FIND,
                                               NULL);
        if (hentry)
            return hentry->join_rel;
    }
    else
    {
        ListCell   *l;

        foreach(l, root->join_rel_list)
        {
            RelOptInfo *rel = (RelOptInfo *) lfirst(l);

            if (bms_equal(rel->relids, relids))
                return rel;
        }
    }

    return NULL;
}

/*
 * build_join_rel
 *    Returns relation entry corresponding to the union of two given rels,
 *    creating a new relation entry if none already exists.
 *
 * 'joinrelids' is the Relids set that uniquely identifies the join
 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 *      joined
 * 'sjinfo': join context info
 * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 *      receives the list of RestrictInfo nodes that apply to this
 *      particular pair of joinable relations.
 *
 * restrictlist_ptr makes the routine's API a little grotty, but it saves
 * duplicated calculation of the restrictlist...
 */
RelOptInfo *
build_join_rel(PlannerInfo *root,
               Relids joinrelids,
               RelOptInfo *outer_rel,
               RelOptInfo *inner_rel,
               SpecialJoinInfo *sjinfo,
               List **restrictlist_ptr)
{
    RelOptInfo *joinrel;
    List       *restrictlist;

    /*
     * See if we already have a joinrel for this set of base rels.
     */
    joinrel = find_join_rel(root, joinrelids);

    if (joinrel)
    {
        /*
         * Yes, so we only need to figure the restrictlist for this particular
         * pair of component relations.
         */
        if (restrictlist_ptr)
            *restrictlist_ptr = build_joinrel_restrictlist(root,
                                                           joinrel,
                                                           outer_rel,
                                                           inner_rel);
        return joinrel;
    }

    /*
     * Nope, so make one.
     */
    joinrel = makeNode(RelOptInfo);
    joinrel->reloptkind = RELOPT_JOINREL;
    joinrel->relids = bms_copy(joinrelids);
    joinrel->rows = 0;
    joinrel->width = 0;
    /* cheap startup cost is interesting iff not all tuples to be retrieved */
    joinrel->consider_startup = (root->tuple_fraction > 0);
    joinrel->reltargetlist = NIL;
    joinrel->pathlist = NIL;
    joinrel->ppilist = NIL;
    joinrel->cheapest_startup_path = NULL;
    joinrel->cheapest_total_path = NULL;
    joinrel->cheapest_unique_path = NULL;
    joinrel->cheapest_parameterized_paths = NIL;
    joinrel->relid = 0;         /* indicates not a baserel */
    joinrel->rtekind = RTE_JOIN;
    joinrel->min_attr = 0;
    joinrel->max_attr = 0;
    joinrel->attr_needed = NULL;
    joinrel->attr_widths = NULL;
    joinrel->lateral_vars = NIL;
    joinrel->lateral_relids = NULL;
    joinrel->indexlist = NIL;
    joinrel->pages = 0;
    joinrel->tuples = 0;
    joinrel->allvisfrac = 0;
    joinrel->subplan = NULL;
    joinrel->subroot = NULL;
    joinrel->subplan_params = NIL;
    joinrel->fdwroutine = NULL;
    joinrel->fdw_private = NULL;
    joinrel->baserestrictinfo = NIL;
    joinrel->baserestrictcost.startup = 0;
    joinrel->baserestrictcost.per_tuple = 0;
    joinrel->joininfo = NIL;
    joinrel->has_eclass_joins = false;

    /*
     * Create a new tlist containing just the vars that need to be output from
     * this join (ie, are needed for higher joinclauses or final output).
     *
     * NOTE: the tlist order for a join rel will depend on which pair of outer
     * and inner rels we first try to build it from.  But the contents should
     * be the same regardless.
     */
    build_joinrel_tlist(root, joinrel, outer_rel);
    build_joinrel_tlist(root, joinrel, inner_rel);
    add_placeholders_to_joinrel(root, joinrel);

    /*
     * Construct restrict and join clause lists for the new joinrel. (The
     * caller might or might not need the restrictlist, but I need it anyway
     * for set_joinrel_size_estimates().)
     */
    restrictlist = build_joinrel_restrictlist(root, joinrel,
                                              outer_rel, inner_rel);
    if (restrictlist_ptr)
        *restrictlist_ptr = restrictlist;
    build_joinrel_joinlist(joinrel, outer_rel, inner_rel);

    /*
     * This is also the right place to check whether the joinrel has any
     * pending EquivalenceClass joins.
     */
    joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);

    /*
     * Set estimates of the joinrel's size.
     */
    set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
                               sjinfo, restrictlist);

    /*
     * Add the joinrel to the query's joinrel list, and store it into the
     * auxiliary hashtable if there is one.  NB: GEQO requires us to append
     * the new joinrel to the end of the list!
     */
    root->join_rel_list = lappend(root->join_rel_list, joinrel);

    if (root->join_rel_hash)
    {
        JoinHashEntry *hentry;
        bool        found;

        hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
                                               &(joinrel->relids),
                                               HASH_ENTER,
                                               &found);
        Assert(!found);
        hentry->join_rel = joinrel;
    }

    /*
     * Also, if dynamic-programming join search is active, add the new joinrel
     * to the appropriate sublist.  Note: you might think the Assert on number
     * of members should be for equality, but some of the level 1 rels might
     * have been joinrels already, so we can only assert <=.
     */
    if (root->join_rel_level)
    {
        Assert(root->join_cur_level > 0);
        Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
        root->join_rel_level[root->join_cur_level] =
            lappend(root->join_rel_level[root->join_cur_level], joinrel);
    }

    return joinrel;
}

/*
 * build_joinrel_tlist
 *    Builds a join relation's target list from an input relation.
 *    (This is invoked twice to handle the two input relations.)
 *
 * The join's targetlist includes all Vars of its member relations that
 * will still be needed above the join.  This subroutine adds all such
 * Vars from the specified input rel's tlist to the join rel's tlist.
 *
 * We also compute the expected width of the join's output, making use
 * of data that was cached at the baserel level by set_rel_width().
 */
static void
build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
                    RelOptInfo *input_rel)
{
    Relids      relids = joinrel->relids;
    ListCell   *vars;

    foreach(vars, input_rel->reltargetlist)
    {
        Var        *var = (Var *) lfirst(vars);
        RelOptInfo *baserel;
        int         ndx;

        /*
         * Ignore PlaceHolderVars in the input tlists; we'll make our own
         * decisions about whether to copy them.
         */
        if (IsA(var, PlaceHolderVar))
            continue;

        /*
         * Otherwise, anything in a baserel or joinrel targetlist ought to be
         * a Var.  (More general cases can only appear in appendrel child
         * rels, which will never be seen here.)
         */
        if (!IsA(var, Var))
            elog(ERROR, "unexpected node type in reltargetlist: %d",
                 (int) nodeTag(var));

        /* Get the Var's original base rel */
        baserel = find_base_rel(root, var->varno);

        /* Is it still needed above this joinrel? */
        ndx = var->varattno - baserel->min_attr;
        if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
        {
            /* Yup, add it to the output */
            joinrel->reltargetlist = lappend(joinrel->reltargetlist, var);
            joinrel->width += baserel->attr_widths[ndx];
        }
    }
}

/*
 * build_joinrel_restrictlist
 * build_joinrel_joinlist
 *    These routines build lists of restriction and join clauses for a
 *    join relation from the joininfo lists of the relations it joins.
 *
 *    These routines are separate because the restriction list must be
 *    built afresh for each pair of input sub-relations we consider, whereas
 *    the join list need only be computed once for any join RelOptInfo.
 *    The join list is fully determined by the set of rels making up the
 *    joinrel, so we should get the same results (up to ordering) from any
 *    candidate pair of sub-relations.  But the restriction list is whatever
 *    is not handled in the sub-relations, so it depends on which
 *    sub-relations are considered.
 *
 *    If a join clause from an input relation refers to base rels still not
 *    present in the joinrel, then it is still a join clause for the joinrel;
 *    we put it into the joininfo list for the joinrel.  Otherwise,
 *    the clause is now a restrict clause for the joined relation, and we
 *    return it to the caller of build_joinrel_restrictlist() to be stored in
 *    join paths made from this pair of sub-relations.  (It will not need to
 *    be considered further up the join tree.)
 *
 *    In many case we will find the same RestrictInfos in both input
 *    relations' joinlists, so be careful to eliminate duplicates.
 *    Pointer equality should be a sufficient test for dups, since all
 *    the various joinlist entries ultimately refer to RestrictInfos
 *    pushed into them by distribute_restrictinfo_to_rels().
 *
 * 'joinrel' is a join relation node
 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 *      to form joinrel.
 *
 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 * whereas build_joinrel_joinlist() stores its results in the joinrel's
 * joininfo list.  One or the other must accept each given clause!
 *
 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 * up to the join relation.  I believe this is no longer necessary, because
 * RestrictInfo nodes are no longer context-dependent.  Instead, just include
 * the original nodes in the lists made for the join relation.
 */
static List *
build_joinrel_restrictlist(PlannerInfo *root,
                           RelOptInfo *joinrel,
                           RelOptInfo *outer_rel,
                           RelOptInfo *inner_rel)
{
    List       *result;

    /*
     * Collect all the clauses that syntactically belong at this level,
     * eliminating any duplicates (important since we will see many of the
     * same clauses arriving from both input relations).
     */
    result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
    result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);

    /*
     * Add on any clauses derived from EquivalenceClasses.  These cannot be
     * redundant with the clauses in the joininfo lists, so don't bother
     * checking.
     */
    result = list_concat(result,
                         generate_join_implied_equalities(root,
                                                          joinrel->relids,
                                                          outer_rel->relids,
                                                          inner_rel));

    return result;
}

static void
build_joinrel_joinlist(RelOptInfo *joinrel,
                       RelOptInfo *outer_rel,
                       RelOptInfo *inner_rel)
{
    List       *result;

    /*
     * Collect all the clauses that syntactically belong above this level,
     * eliminating any duplicates (important since we will see many of the
     * same clauses arriving from both input relations).
     */
    result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
    result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);

    joinrel->joininfo = result;
}

static List *
subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
                              List *joininfo_list,
                              List *new_restrictlist)
{
    ListCell   *l;

    foreach(l, joininfo_list)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

        if (bms_is_subset(rinfo->required_relids, joinrel->relids))
        {
            /*
             * This clause becomes a restriction clause for the joinrel, since
             * it refers to no outside rels.  Add it to the list, being
             * careful to eliminate duplicates. (Since RestrictInfo nodes in
             * different joinlists will have been multiply-linked rather than
             * copied, pointer equality should be a sufficient test.)
             */
            new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
        }
        else
        {
            /*
             * This clause is still a join clause at this level, so we ignore
             * it in this routine.
             */
        }
    }

    return new_restrictlist;
}

static List *
subbuild_joinrel_joinlist(RelOptInfo *joinrel,
                          List *joininfo_list,
                          List *new_joininfo)
{
    ListCell   *l;

    foreach(l, joininfo_list)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

        if (bms_is_subset(rinfo->required_relids, joinrel->relids))
        {
            /*
             * This clause becomes a restriction clause for the joinrel, since
             * it refers to no outside rels.  So we can ignore it in this
             * routine.
             */
        }
        else
        {
            /*
             * This clause is still a join clause at this level, so add it to
             * the new joininfo list, being careful to eliminate duplicates.
             * (Since RestrictInfo nodes in different joinlists will have been
             * multiply-linked rather than copied, pointer equality should be
             * a sufficient test.)
             */
            new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
        }
    }

    return new_joininfo;
}


/*
 * find_childrel_appendrelinfo
 *      Get the AppendRelInfo associated with an appendrel child rel.
 *
 * This search could be eliminated by storing a link in child RelOptInfos,
 * but for now it doesn't seem performance-critical.
 */
AppendRelInfo *
find_childrel_appendrelinfo(PlannerInfo *root, RelOptInfo *rel)
{
    Index       relid = rel->relid;
    ListCell   *lc;

    /* Should only be called on child rels */
    Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);

    foreach(lc, root->append_rel_list)
    {
        AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);

        if (appinfo->child_relid == relid)
            return appinfo;
    }
    /* should have found the entry ... */
    elog(ERROR, "child rel %d not found in append_rel_list", relid);
    return NULL;                /* not reached */
}


/*
 * get_baserel_parampathinfo
 *      Get the ParamPathInfo for a parameterized path for a base relation,
 *      constructing one if we don't have one already.
 *
 * This centralizes estimating the rowcounts for parameterized paths.
 * We need to cache those to be sure we use the same rowcount for all paths
 * of the same parameterization for a given rel.  This is also a convenient
 * place to determine which movable join clauses the parameterized path will
 * be responsible for evaluating.
 */
ParamPathInfo *
get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
                          Relids required_outer)
{
    ParamPathInfo *ppi;
    Relids      joinrelids;
    List       *pclauses;
    double      rows;
    ListCell   *lc;

    /* Unparameterized paths have no ParamPathInfo */
    if (bms_is_empty(required_outer))
        return NULL;

    Assert(!bms_overlap(baserel->relids, required_outer));

    /* If we already have a PPI for this parameterization, just return it */
    foreach(lc, baserel->ppilist)
    {
        ppi = (ParamPathInfo *) lfirst(lc);
        if (bms_equal(ppi->ppi_req_outer, required_outer))
            return ppi;
    }

    /*
     * Identify all joinclauses that are movable to this base rel given this
     * parameterization.
     */
    joinrelids = bms_union(baserel->relids, required_outer);
    pclauses = NIL;
    foreach(lc, baserel->joininfo)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

        if (join_clause_is_movable_into(rinfo,
                                        baserel->relids,
                                        joinrelids))
            pclauses = lappend(pclauses, rinfo);
    }

    /*
     * Add in joinclauses generated by EquivalenceClasses, too.  (These
     * necessarily satisfy join_clause_is_movable_into.)
     */
    pclauses = list_concat(pclauses,
                           generate_join_implied_equalities(root,
                                                            joinrelids,
                                                            required_outer,
                                                            baserel));

    /* Estimate the number of rows returned by the parameterized scan */
    rows = get_parameterized_baserel_size(root, baserel, pclauses);

    /* And now we can build the ParamPathInfo */
    ppi = makeNode(ParamPathInfo);
    ppi->ppi_req_outer = required_outer;
    ppi->ppi_rows = rows;
    ppi->ppi_clauses = pclauses;
    baserel->ppilist = lappend(baserel->ppilist, ppi);

    return ppi;
}

/*
 * get_joinrel_parampathinfo
 *      Get the ParamPathInfo for a parameterized path for a join relation,
 *      constructing one if we don't have one already.
 *
 * This centralizes estimating the rowcounts for parameterized paths.
 * We need to cache those to be sure we use the same rowcount for all paths
 * of the same parameterization for a given rel.  This is also a convenient
 * place to determine which movable join clauses the parameterized path will
 * be responsible for evaluating.
 *
 * outer_path and inner_path are a pair of input paths that can be used to
 * construct the join, and restrict_clauses is the list of regular join
 * clauses (including clauses derived from EquivalenceClasses) that must be
 * applied at the join node when using these inputs.
 *
 * Unlike the situation for base rels, the set of movable join clauses to be
 * enforced at a join varies with the selected pair of input paths, so we
 * must calculate that and pass it back, even if we already have a matching
 * ParamPathInfo.  We handle this by adding any clauses moved down to this
 * join to *restrict_clauses, which is an in/out parameter.  (The addition
 * is done in such a way as to not modify the passed-in List structure.)
 *
 * Note: when considering a nestloop join, the caller must have removed from
 * restrict_clauses any movable clauses that are themselves scheduled to be
 * pushed into the right-hand path.  We do not do that here since it's
 * unnecessary for other join types.
 */
ParamPathInfo *
get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
                          Path *outer_path,
                          Path *inner_path,
                          SpecialJoinInfo *sjinfo,
                          Relids required_outer,
                          List **restrict_clauses)
{
    ParamPathInfo *ppi;
    Relids      join_and_req;
    Relids      outer_and_req;
    Relids      inner_and_req;
    List       *pclauses;
    List       *eclauses;
    double      rows;
    ListCell   *lc;

    /* Unparameterized paths have no ParamPathInfo or extra join clauses */
    if (bms_is_empty(required_outer))
        return NULL;

    Assert(!bms_overlap(joinrel->relids, required_outer));

    /*
     * Identify all joinclauses that are movable to this join rel given this
     * parameterization.  These are the clauses that are movable into this
     * join, but not movable into either input path.  Treat an unparameterized
     * input path as not accepting parameterized clauses (because it won't,
     * per the shortcut exit above), even though the joinclause movement rules
     * might allow the same clauses to be moved into a parameterized path for
     * that rel.
     */
    join_and_req = bms_union(joinrel->relids, required_outer);
    if (outer_path->param_info)
        outer_and_req = bms_union(outer_path->parent->relids,
                                  PATH_REQ_OUTER(outer_path));
    else
        outer_and_req = NULL;   /* outer path does not accept parameters */
    if (inner_path->param_info)
        inner_and_req = bms_union(inner_path->parent->relids,
                                  PATH_REQ_OUTER(inner_path));
    else
        inner_and_req = NULL;   /* inner path does not accept parameters */

    pclauses = NIL;
    foreach(lc, joinrel->joininfo)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

        if (join_clause_is_movable_into(rinfo,
                                        joinrel->relids,
                                        join_and_req) &&
            !join_clause_is_movable_into(rinfo,
                                         outer_path->parent->relids,
                                         outer_and_req) &&
            !join_clause_is_movable_into(rinfo,
                                         inner_path->parent->relids,
                                         inner_and_req))
            pclauses = lappend(pclauses, rinfo);
    }

    /* Consider joinclauses generated by EquivalenceClasses, too */
    eclauses = generate_join_implied_equalities(root,
                                                join_and_req,
                                                required_outer,
                                                joinrel);
    /* We only want ones that aren't movable to lower levels */
    foreach(lc, eclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

        Assert(join_clause_is_movable_into(rinfo,
                                           joinrel->relids,
                                           join_and_req));
        if (!join_clause_is_movable_into(rinfo,
                                         outer_path->parent->relids,
                                         outer_and_req) &&
            !join_clause_is_movable_into(rinfo,
                                         inner_path->parent->relids,
                                         inner_and_req))
            pclauses = lappend(pclauses, rinfo);
    }

    /*
     * Now, attach the identified moved-down clauses to the caller's
     * restrict_clauses list.  By using list_concat in this order, we leave
     * the original list structure of restrict_clauses undamaged.
     */
    *restrict_clauses = list_concat(pclauses, *restrict_clauses);

    /* If we already have a PPI for this parameterization, just return it */
    foreach(lc, joinrel->ppilist)
    {
        ppi = (ParamPathInfo *) lfirst(lc);
        if (bms_equal(ppi->ppi_req_outer, required_outer))
            return ppi;
    }

    /* Estimate the number of rows returned by the parameterized join */
    rows = get_parameterized_joinrel_size(root, joinrel,
                                          outer_path->rows,
                                          inner_path->rows,
                                          sjinfo,
                                          *restrict_clauses);

    /*
     * And now we can build the ParamPathInfo.  No point in saving the
     * input-pair-dependent clause list, though.
     *
     * Note: in GEQO mode, we'll be called in a temporary memory context, but
     * the joinrel structure is there too, so no problem.
     */
    ppi = makeNode(ParamPathInfo);
    ppi->ppi_req_outer = required_outer;
    ppi->ppi_rows = rows;
    ppi->ppi_clauses = NIL;
    joinrel->ppilist = lappend(joinrel->ppilist, ppi);

    return ppi;
}

/*
 * get_appendrel_parampathinfo
 *      Get the ParamPathInfo for a parameterized path for an append relation.
 *
 * For an append relation, the rowcount estimate will just be the sum of
 * the estimates for its children.  However, we still need a ParamPathInfo
 * to flag the fact that the path requires parameters.  So this just creates
 * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
 * the Append node isn't responsible for checking quals).
 */
ParamPathInfo *
get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
{
    ParamPathInfo *ppi;
    ListCell   *lc;

    /* Unparameterized paths have no ParamPathInfo */
    if (bms_is_empty(required_outer))
        return NULL;

    Assert(!bms_overlap(appendrel->relids, required_outer));

    /* If we already have a PPI for this parameterization, just return it */
    foreach(lc, appendrel->ppilist)
    {
        ppi = (ParamPathInfo *) lfirst(lc);
        if (bms_equal(ppi->ppi_req_outer, required_outer))
            return ppi;
    }

    /* Else build the ParamPathInfo */
    ppi = makeNode(ParamPathInfo);
    ppi->ppi_req_outer = required_outer;
    ppi->ppi_rows = 0;
    ppi->ppi_clauses = NIL;
    appendrel->ppilist = lappend(appendrel->ppilist, ppi);

    return ppi;
}