pgpa_walker.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * pgpa_walker.c
 *    Main entrypoints for analyzing a plan to generate an advice string
 *
 * Copyright (c) 2016-2026, PostgreSQL Global Development Group
 *
 *    contrib/pg_plan_advice/pgpa_walker.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"
 
#include "pgpa_join.h"
#include "pgpa_planner.h"
#include "pgpa_scan.h"
#include "pgpa_walker.h"
 
#include "nodes/plannodes.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"
 
static void pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
                                  bool within_join_problem,
                                  pgpa_join_unroller *join_unroller,
                                  List *active_query_features,
                                  bool beneath_any_gather);
static Bitmapset *pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
                                             pgpa_unrolled_join *ujoin);
 
static pgpa_query_feature *pgpa_add_feature(pgpa_plan_walker_context *walker,
                                            pgpa_qf_type type,
                                            Plan *plan);
 
static void pgpa_qf_add_rti(List *active_query_features, Index rti);
static void pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids);
static void pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan,
                                  List *rtable);
 
static bool pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
                                           Index rtable_length,
                                           pgpa_identifier *rt_identifiers,
                                           pgpa_advice_target *target,
                                           bool toplevel);
static bool pgpa_walker_join_order_matches_member(pgpa_join_member *member,
                                                  Index rtable_length,
                                                  pgpa_identifier *rt_identifiers,
                                                  pgpa_advice_target *target);
static pgpa_scan *pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
                                        pgpa_scan_strategy strategy,
                                        Bitmapset *relids);
static bool pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget,
                                                  Plan *plan);
static bool pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
                                         pgpa_qf_type type,
                                         Bitmapset *relids);
static bool pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
                                      pgpa_join_strategy strategy,
                                      Bitmapset *relids);
static bool pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
                                           Bitmapset *relids);
static void pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
                                               List *proots,
                                               List **chosen_proots,
                                               List **discarded_proots);
 
/*
 * Top-level entrypoint for the plan tree walk.
 *
 * Populates walker based on a traversal of the Plan trees in pstmt.
 *
 * proots is the list of pgpa_planner_info objects that were generated
 * during planning.
 */
void
pgpa_plan_walker(pgpa_plan_walker_context *walker, PlannedStmt *pstmt,
                 List *proots)
{
    ListCell   *lc;
    List       *sj_unique_rtis = NULL;
    List       *sj_nonunique_qfs = NULL;
    List       *chosen_proots;
    List       *discarded_proots;
 
    /* Initialization. */
    memset(walker, 0, sizeof(pgpa_plan_walker_context));
    walker->pstmt = pstmt;
 
    /* Walk the main plan tree. */
    pgpa_walk_recursively(walker, pstmt->planTree, false, NULL, NIL, false);
 
    /* Main plan tree walk won't reach subplans, so walk those. */
    foreach(lc, pstmt->subplans)
    {
        Plan       *plan = lfirst(lc);
 
        if (plan != NULL)
            pgpa_walk_recursively(walker, plan, false, NULL, NIL, false);
    }
 
    /* Adjust RTIs from sj_unique_rels for the flattened range table. */
    foreach_ptr(pgpa_planner_info, proot, proots)
    {
        /* If there are no sj_unique_rels for this proot, we can skip it. */
        if (proot->sj_unique_rels == NIL)
            continue;
 
        /* If this is a subplan, find the range table offset. */
        if (!proot->has_rtoffset)
            elog(ERROR, "no rtoffset for plan %s", proot->plan_name);
 
        /* Offset each relid set by the proot's rtoffset. */
        foreach_node(Bitmapset, relids, proot->sj_unique_rels)
        {
            int         rtindex = -1;
            Bitmapset  *flat_relids = NULL;
 
            while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
                flat_relids = bms_add_member(flat_relids,
                                             rtindex + proot->rtoffset);
 
            sj_unique_rtis = lappend(sj_unique_rtis, flat_relids);
        }
    }
 
    /*
     * Remove any non-unique semijoin query features for which making the rel
     * unique wasn't considered.
     */
    foreach_ptr(pgpa_query_feature, qf,
                walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE])
    {
        if (list_member(sj_unique_rtis, qf->relids))
            sj_nonunique_qfs = lappend(sj_nonunique_qfs, qf);
    }
    walker->query_features[PGPAQF_SEMIJOIN_NON_UNIQUE] = sj_nonunique_qfs;
 
    /*
     * If we find any cases where analysis of the Plan tree shows that the
     * semijoin was made unique but this possibility was never observed to be
     * considered during planning, then we have a bug somewhere.
     */
    foreach_ptr(pgpa_query_feature, qf,
                walker->query_features[PGPAQF_SEMIJOIN_UNIQUE])
    {
        if (!list_member(sj_unique_rtis, qf->relids))
        {
            StringInfoData buf;
 
            initStringInfo(&buf);
            outBitmapset(&buf, qf->relids);
            elog(ERROR,
                 "unique semijoin found for relids %s but not observed during planning",
                 buf.data);
        }
    }
 
    /*
     * It's possible for a Gather or Gather Merge query feature to find no
     * RTIs when partitionwise aggregation is in use. We shouldn't emit
     * something like GATHER_MERGE(()), so instead emit nothing. This means
     * that we won't advise either GATHER or GATHER_MERGE or NO_GATHER in such
     * cases, which might be something we want to improve in the future.
     *
     * (Should the Partial Aggregates in such a case be created in an
     * UPPERREL_GROUP_AGG with a non-empty relid set? Right now that doesn't
     * happen, but it seems like it would make life easier for us if it did.)
     */
    for (int t = 0; t < NUM_PGPA_QF_TYPES; ++t)
    {
        List       *query_features = NIL;
 
        foreach_ptr(pgpa_query_feature, qf, walker->query_features[t])
        {
            if (qf->relids != NULL)
                query_features = lappend(query_features, qf);
            else
                Assert(t == PGPAQF_GATHER || t == PGPAQF_GATHER_MERGE);
        }
 
        walker->query_features[t] = query_features;
    }
 
    /* Classify alternative subplans. */
    pgpa_classify_alternative_subplans(walker, proots,
                                       &chosen_proots, &discarded_proots);
 
    /*
     * Figure out which of the discarded alternatives have a non-discarded
     * alternative. Those are the ones for which we want to emit DO_NOT_SCAN
     * advice. (If every alternative was discarded, then there's no point.)
     */
    foreach_ptr(pgpa_planner_info, discarded_proot, discarded_proots)
    {
        bool        some_alternative_chosen = false;
 
        foreach_ptr(pgpa_planner_info, chosen_proot, chosen_proots)
        {
            if (strings_equal_or_both_null(discarded_proot->alternative_plan_name,
                                           chosen_proot->alternative_plan_name))
            {
                some_alternative_chosen = true;
                break;
            }
        }
 
        if (some_alternative_chosen)
        {
            for (int rti = 1; rti <= discarded_proot->rid_array_size; rti++)
            {
                pgpa_identifier *rid = &discarded_proot->rid_array[rti - 1];
 
                if (rid->alias_name != NULL)
                    walker->do_not_scan_identifiers =
                        lappend(walker->do_not_scan_identifiers, rid);
            }
        }
    }
}
 
/*
 * Main workhorse for the plan tree walk.
 *
 * If within_join_problem is true, we encountered a join at some higher level
 * of the tree walk and haven't yet descended out of the portion of the plan
 * tree that is part of that same join problem. We're no longer in the same
 * join problem if (1) we cross into a different subquery or (2) we descend
 * through an Append or MergeAppend node, below which any further joins would
 * be partitionwise joins planned separately from the outer join problem.
 *
 * If join_unroller != NULL, the join unroller code expects us to find a join
 * that should be unrolled into that object. This implies that we're within a
 * join problem, but the reverse is not true: when we've traversed all the
 * joins but are still looking for the scan that is the leaf of the join tree,
 * join_unroller will be NULL but within_join_problem will be true.
 *
 * Each element of active_query_features corresponds to some item of advice
 * that needs to enumerate all the relations it affects. We add RTIs we find
 * during tree traversal to each of these query features.
 *
 * If beneath_any_gather == true, some higher level of the tree traversal found
 * a Gather or Gather Merge node.
 */
static void
pgpa_walk_recursively(pgpa_plan_walker_context *walker, Plan *plan,
                      bool within_join_problem,
                      pgpa_join_unroller *join_unroller,
                      List *active_query_features,
                      bool beneath_any_gather)
{
    pgpa_join_unroller *outer_join_unroller = NULL;
    pgpa_join_unroller *inner_join_unroller = NULL;
    bool        join_unroller_toplevel = false;
    ListCell   *lc;
    List       *extraplans = NIL;
    List       *elided_nodes = NIL;
 
    Assert(within_join_problem || join_unroller == NULL);
 
    /*
     * Check the future_query_features list to see whether this was previously
     * identified as a plan node that needs to be treated as a query feature.
     * We must do this before handling elided nodes, because if there's an
     * elided node associated with a future query feature, the RTIs associated
     * with the elided node should be the only ones attributed to the query
     * feature.
     */
    foreach_ptr(pgpa_query_feature, qf, walker->future_query_features)
    {
        if (qf->plan == plan)
        {
            active_query_features = list_copy(active_query_features);
            active_query_features = lappend(active_query_features, qf);
            walker->future_query_features =
                list_delete_ptr(walker->future_query_features, qf);
            break;
        }
    }
 
    /*
     * Find all elided nodes for this Plan node.
     */
    foreach_node(ElidedNode, n, walker->pstmt->elidedNodes)
    {
        if (n->plan_node_id == plan->plan_node_id)
            elided_nodes = lappend(elided_nodes, n);
    }
 
    /* If we found any elided_nodes, handle them. */
    if (elided_nodes != NIL)
    {
        int         num_elided_nodes = list_length(elided_nodes);
        ElidedNode *last_elided_node;
 
        /*
         * RTIs for the final -- and thus logically uppermost -- elided node
         * should be collected for query features passed down by the caller.
         * However, elided nodes act as barriers to query features, which
         * means that (1) the remaining elided nodes, if any, should be
         * ignored for purposes of query features and (2) the list of active
         * query features should be reset to empty so that we do not add RTIs
         * from the plan node that is logically beneath the elided node to the
         * query features passed down from the caller.
         */
        last_elided_node = list_nth(elided_nodes, num_elided_nodes - 1);
        pgpa_qf_add_rtis(active_query_features,
                         pgpa_filter_out_join_relids(last_elided_node->relids,
                                                     walker->pstmt->rtable));
        active_query_features = NIL;
 
        /*
         * If we're within a join problem, the join_unroller is responsible
         * for building the scan for the final elided node, so throw it out.
         */
        if (within_join_problem)
            elided_nodes = list_truncate(elided_nodes, num_elided_nodes - 1);
 
        /* Build scans for all (or the remaining) elided nodes. */
        foreach_node(ElidedNode, elided_node, elided_nodes)
        {
            (void) pgpa_build_scan(walker, plan, elided_node,
                                   beneath_any_gather, within_join_problem);
        }
 
        /*
         * If there were any elided nodes, then everything beneath those nodes
         * is not part of the same join problem.
         *
         * In more detail, if an Append or MergeAppend was elided, then a
         * partitionwise join was chosen and only a single child survived; if
         * a SubqueryScan was elided, the subquery was planned without
         * flattening it into the parent.
         */
        within_join_problem = false;
        join_unroller = NULL;
    }
 
    /*
     * If this is a Gather or Gather Merge node, directly add it to the list
     * of currently-active query features. We must do this after handling
     * elided nodes, since the Gather or Gather Merge node occurs logically
     * beneath any associated elided nodes.
     *
     * Exception: We disregard any single_copy Gather nodes. These are created
     * by debug_parallel_query, and having them affect the plan advice is
     * counterproductive, as the result will be to advise the use of a real
     * Gather node, rather than a single copy one.
     */
    if (IsA(plan, Gather) && !((Gather *) plan)->single_copy)
    {
        active_query_features =
            lappend(list_copy(active_query_features),
                    pgpa_add_feature(walker, PGPAQF_GATHER, plan));
        beneath_any_gather = true;
    }
    else if (IsA(plan, GatherMerge))
    {
        active_query_features =
            lappend(list_copy(active_query_features),
                    pgpa_add_feature(walker, PGPAQF_GATHER_MERGE, plan));
        beneath_any_gather = true;
    }
 
    /*
     * If we're within a join problem, the join unroller is responsible for
     * building any required scan for this node. If not, we do it here.
     */
    if (!within_join_problem)
        (void) pgpa_build_scan(walker, plan, NULL, beneath_any_gather, false);
 
    /*
     * If this join needs to be unrolled but there's no join unroller already
     * available, create one.
     */
    if (join_unroller == NULL && pgpa_is_join(plan))
    {
        join_unroller = pgpa_create_join_unroller();
        join_unroller_toplevel = true;
        within_join_problem = true;
    }
 
    /*
     * If this join is to be unrolled, pgpa_unroll_join() will return the join
     * unroller object that should be passed down when we recurse into the
     * outer and inner sides of the plan.
     */
    if (join_unroller != NULL)
        pgpa_unroll_join(walker, plan, beneath_any_gather, join_unroller,
                         &outer_join_unroller, &inner_join_unroller);
 
    /* Add RTIs from the plan node to all active query features. */
    pgpa_qf_add_plan_rtis(active_query_features, plan, walker->pstmt->rtable);
 
    /*
     * Recurse into the outer and inner subtrees.
     *
     * As an exception, if this is a ForeignScan, don't recurse. postgres_fdw
     * sometimes stores an EPQ recheck plan in plan->lefttree, but that's
     * going to mention the same set of relations as the ForeignScan itself,
     * and we have no way to emit advice targeting the EPQ case vs. the
     * non-EPQ case. Moreover, it's not entirely clear what other FDWs might
     * do with the left and right subtrees. Maybe some better handling is
     * needed here, but for now, we just punt.
     */
    if (!IsA(plan, ForeignScan))
    {
        if (plan->lefttree != NULL)
            pgpa_walk_recursively(walker, plan->lefttree, within_join_problem,
                                  outer_join_unroller, active_query_features,
                                  beneath_any_gather);
        if (plan->righttree != NULL)
            pgpa_walk_recursively(walker, plan->righttree, within_join_problem,
                                  inner_join_unroller, active_query_features,
                                  beneath_any_gather);
    }
 
    /*
     * If we created a join unroller up above, then it's also our join to use
     * it to build the final pgpa_unrolled_join, and to destroy the object.
     */
    if (join_unroller_toplevel)
    {
        pgpa_unrolled_join *ujoin;
 
        ujoin = pgpa_build_unrolled_join(walker, join_unroller);
        walker->toplevel_unrolled_joins =
            lappend(walker->toplevel_unrolled_joins, ujoin);
        pgpa_destroy_join_unroller(join_unroller);
        (void) pgpa_process_unrolled_join(walker, ujoin);
    }
 
    /*
     * Some plan types can have additional children. Nodes like Append that
     * can have any number of children store them in a List; a SubqueryScan
     * just has a field for a single additional Plan.
     */
    switch (nodeTag(plan))
    {
        case T_Append:
            {
                Append     *aplan = (Append *) plan;
 
                extraplans = aplan->appendplans;
            }
            break;
        case T_MergeAppend:
            {
                MergeAppend *maplan = (MergeAppend *) plan;
 
                extraplans = maplan->mergeplans;
            }
            break;
        case T_BitmapAnd:
            extraplans = ((BitmapAnd *) plan)->bitmapplans;
            break;
        case T_BitmapOr:
            extraplans = ((BitmapOr *) plan)->bitmapplans;
            break;
        case T_SubqueryScan:
 
            /*
             * We don't pass down active_query_features across here, because
             * those are specific to a subquery level.
             */
            pgpa_walk_recursively(walker, ((SubqueryScan *) plan)->subplan,
                                  0, NULL, NIL, beneath_any_gather);
            break;
        case T_CustomScan:
            extraplans = ((CustomScan *) plan)->custom_plans;
            break;
        default:
            break;
    }
 
    /* If we found a list of extra children, iterate over it. */
    foreach(lc, extraplans)
    {
        Plan       *subplan = lfirst(lc);
 
        pgpa_walk_recursively(walker, subplan, false, NULL, NIL,
                              beneath_any_gather);
    }
}
 
/*
 * Perform final processing of a newly-constructed pgpa_unrolled_join. This
 * only needs to be called for toplevel pgpa_unrolled_join objects, since it
 * recurses to sub-joins as needed.
 *
 * Our goal is to add the set of inner relids to the relevant join_strategies
 * list, and to do the same for any sub-joins. To that end, the return value
 * is the set of relids found beneath the join, but it is expected that
 * the toplevel caller will ignore this.
 */
static Bitmapset *
pgpa_process_unrolled_join(pgpa_plan_walker_context *walker,
                           pgpa_unrolled_join *ujoin)
{
    Bitmapset  *all_relids = bms_copy(ujoin->outer.scan->relids);
 
    /* If this fails, we didn't unroll properly. */
    Assert(ujoin->outer.unrolled_join == NULL);
 
    for (int k = 0; k < ujoin->ninner; ++k)
    {
        pgpa_join_member *member = &ujoin->inner[k];
        Bitmapset  *relids;
 
        if (member->unrolled_join != NULL)
            relids = pgpa_process_unrolled_join(walker,
                                                member->unrolled_join);
        else
        {
            Assert(member->scan != NULL);
            relids = member->scan->relids;
        }
        walker->join_strategies[ujoin->strategy[k]] =
            lappend(walker->join_strategies[ujoin->strategy[k]], relids);
        all_relids = bms_add_members(all_relids, relids);
    }
 
    return all_relids;
}
 
/*
 * Arrange for the given plan node to be treated as a query feature when the
 * tree walk reaches it.
 *
 * Make sure to only use this for nodes that the tree walk can't have reached
 * yet!
 */
void
pgpa_add_future_feature(pgpa_plan_walker_context *walker,
                        pgpa_qf_type type, Plan *plan)
{
    pgpa_query_feature *qf = pgpa_add_feature(walker, type, plan);
 
    walker->future_query_features =
        lappend(walker->future_query_features, qf);
}
 
/*
 * Return the last of any elided nodes associated with this plan node ID.
 *
 * The last elided node is the one that would have been uppermost in the plan
 * tree had it not been removed during setrefs processing.
 */
ElidedNode *
pgpa_last_elided_node(PlannedStmt *pstmt, Plan *plan)
{
    ElidedNode *elided_node = NULL;
 
    foreach_node(ElidedNode, n, pstmt->elidedNodes)
    {
        if (n->plan_node_id == plan->plan_node_id)
            elided_node = n;
    }
 
    return elided_node;
}
 
/*
 * Certain plan nodes can refer to a set of RTIs. Extract and return the set.
 */
Bitmapset *
pgpa_relids(Plan *plan)
{
    if (IsA(plan, Result))
        return ((Result *) plan)->relids;
    else if (IsA(plan, ForeignScan))
        return ((ForeignScan *) plan)->fs_relids;
    else if (IsA(plan, Append))
        return ((Append *) plan)->apprelids;
    else if (IsA(plan, MergeAppend))
        return ((MergeAppend *) plan)->apprelids;
 
    return NULL;
}
 
/*
 * Extract the scanned RTI from a plan node.
 *
 * Returns 0 if there isn't one.
 */
Index
pgpa_scanrelid(Plan *plan)
{
    switch (nodeTag(plan))
    {
        case T_SeqScan:
        case T_SampleScan:
        case T_BitmapHeapScan:
        case T_TidScan:
        case T_TidRangeScan:
        case T_SubqueryScan:
        case T_FunctionScan:
        case T_TableFuncScan:
        case T_ValuesScan:
        case T_CteScan:
        case T_NamedTuplestoreScan:
        case T_WorkTableScan:
        case T_ForeignScan:
        case T_CustomScan:
        case T_IndexScan:
        case T_IndexOnlyScan:
            return ((Scan *) plan)->scanrelid;
        default:
            return 0;
    }
}
 
/*
 * Construct a new Bitmapset containing non-RTE_JOIN members of 'relids'.
 */
Bitmapset *
pgpa_filter_out_join_relids(Bitmapset *relids, List *rtable)
{
    int         rti = -1;
    Bitmapset  *result = NULL;
 
    while ((rti = bms_next_member(relids, rti)) >= 0)
    {
        RangeTblEntry *rte = rt_fetch(rti, rtable);
 
        if (rte->rtekind != RTE_JOIN)
            result = bms_add_member(result, rti);
    }
 
    return result;
}
 
/*
 * Create a pgpa_query_feature and add it to the list of all query features
 * for this plan.
 */
static pgpa_query_feature *
pgpa_add_feature(pgpa_plan_walker_context *walker,
                 pgpa_qf_type type, Plan *plan)
{
    pgpa_query_feature *qf = palloc0_object(pgpa_query_feature);
 
    qf->type = type;
    qf->plan = plan;
 
    walker->query_features[qf->type] =
        lappend(walker->query_features[qf->type], qf);
 
    return qf;
}
 
/*
 * Add a single RTI to each active query feature.
 */
static void
pgpa_qf_add_rti(List *active_query_features, Index rti)
{
    foreach_ptr(pgpa_query_feature, qf, active_query_features)
    {
        qf->relids = bms_add_member(qf->relids, rti);
    }
}
 
/*
 * Add a set of RTIs to each active query feature.
 */
static void
pgpa_qf_add_rtis(List *active_query_features, Bitmapset *relids)
{
    foreach_ptr(pgpa_query_feature, qf, active_query_features)
    {
        qf->relids = bms_add_members(qf->relids, relids);
    }
}
 
/*
 * Add RTIs directly contained in a plan node to each active query feature,
 * but filter out any join RTIs, since advice doesn't mention those.
 */
static void
pgpa_qf_add_plan_rtis(List *active_query_features, Plan *plan, List *rtable)
{
    Bitmapset  *relids;
    Index       rti;
 
    if ((relids = pgpa_relids(plan)) != NULL)
    {
        relids = pgpa_filter_out_join_relids(relids, rtable);
        pgpa_qf_add_rtis(active_query_features, relids);
    }
    else if ((rti = pgpa_scanrelid(plan)) != 0)
        pgpa_qf_add_rti(active_query_features, rti);
}
 
/*
 * If we generated plan advice using the provided walker object and array
 * of identifiers, would we generate the specified tag/target combination?
 *
 * If yes, the plan conforms to the advice; if no, it does not. Note that
 * we have no way of knowing whether the planner was forced to emit a plan
 * that conformed to the advice or just happened to do so.
 */
bool
pgpa_walker_would_advise(pgpa_plan_walker_context *walker,
                         pgpa_identifier *rt_identifiers,
                         pgpa_advice_tag_type tag,
                         pgpa_advice_target *target)
{
    Index       rtable_length = list_length(walker->pstmt->rtable);
    Bitmapset  *relids = NULL;
 
    if (tag == PGPA_TAG_JOIN_ORDER)
    {
        foreach_ptr(pgpa_unrolled_join, ujoin, walker->toplevel_unrolled_joins)
        {
            if (pgpa_walker_join_order_matches(ujoin, rtable_length,
                                               rt_identifiers, target, true))
                return true;
        }
 
        return false;
    }
 
    /*
     * DO_NOT_SCAN advice targets rels that may not be in the flat range table
     * (e.g. MinMaxAgg losers), so pgpa_compute_rti_from_identifier won't work
     * here. Instead, check directly against the do_not_scan_identifiers list.
     */
    if (tag == PGPA_TAG_DO_NOT_SCAN)
    {
        if (target->ttype != PGPA_TARGET_IDENTIFIER)
            return false;
        foreach_ptr(pgpa_identifier, rid, walker->do_not_scan_identifiers)
        {
            if (strcmp(rid->alias_name, target->rid.alias_name) == 0 &&
                rid->occurrence == target->rid.occurrence &&
                strings_equal_or_both_null(rid->partnsp,
                                           target->rid.partnsp) &&
                strings_equal_or_both_null(rid->partrel,
                                           target->rid.partrel) &&
                strings_equal_or_both_null(rid->plan_name,
                                           target->rid.plan_name))
                return true;
        }
        return false;
    }
 
    if (target->ttype == PGPA_TARGET_IDENTIFIER)
    {
        Index       rti;
 
        rti = pgpa_compute_rti_from_identifier(rtable_length, rt_identifiers,
                                               &target->rid);
        if (rti == 0)
            return false;
        relids = bms_make_singleton(rti);
    }
    else
    {
        Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
        foreach_ptr(pgpa_advice_target, child_target, target->children)
        {
            Index       rti;
 
            Assert(child_target->ttype == PGPA_TARGET_IDENTIFIER);
            rti = pgpa_compute_rti_from_identifier(rtable_length,
                                                   rt_identifiers,
                                                   &child_target->rid);
            if (rti == 0)
                return false;
            relids = bms_add_member(relids, rti);
        }
    }
 
    switch (tag)
    {
        case PGPA_TAG_JOIN_ORDER:
            /* should have been handled above */
            pg_unreachable();
            break;
        case PGPA_TAG_DO_NOT_SCAN:
            /* should have been handled above */
            pg_unreachable();
            break;
        case PGPA_TAG_BITMAP_HEAP_SCAN:
            return pgpa_walker_find_scan(walker,
                                         PGPA_SCAN_BITMAP_HEAP,
                                         relids) != NULL;
        case PGPA_TAG_FOREIGN_JOIN:
            return pgpa_walker_find_scan(walker,
                                         PGPA_SCAN_FOREIGN,
                                         relids) != NULL;
        case PGPA_TAG_INDEX_ONLY_SCAN:
            {
                pgpa_scan  *scan;
 
                scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX_ONLY,
                                             relids);
                if (scan == NULL)
                    return false;
 
                return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
            }
        case PGPA_TAG_INDEX_SCAN:
            {
                pgpa_scan  *scan;
 
                scan = pgpa_walker_find_scan(walker, PGPA_SCAN_INDEX,
                                             relids);
                if (scan == NULL)
                    return false;
 
                return pgpa_walker_index_target_matches_plan(target->itarget, scan->plan);
            }
        case PGPA_TAG_PARTITIONWISE:
            return pgpa_walker_find_scan(walker,
                                         PGPA_SCAN_PARTITIONWISE,
                                         relids) != NULL;
        case PGPA_TAG_SEQ_SCAN:
            return pgpa_walker_find_scan(walker,
                                         PGPA_SCAN_SEQ,
                                         relids) != NULL;
        case PGPA_TAG_TID_SCAN:
            return pgpa_walker_find_scan(walker,
                                         PGPA_SCAN_TID,
                                         relids) != NULL;
        case PGPA_TAG_GATHER:
            return pgpa_walker_contains_feature(walker,
                                                PGPAQF_GATHER,
                                                relids);
        case PGPA_TAG_GATHER_MERGE:
            return pgpa_walker_contains_feature(walker,
                                                PGPAQF_GATHER_MERGE,
                                                relids);
        case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
            return pgpa_walker_contains_feature(walker,
                                                PGPAQF_SEMIJOIN_NON_UNIQUE,
                                                relids);
        case PGPA_TAG_SEMIJOIN_UNIQUE:
            return pgpa_walker_contains_feature(walker,
                                                PGPAQF_SEMIJOIN_UNIQUE,
                                                relids);
        case PGPA_TAG_HASH_JOIN:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_HASH_JOIN,
                                             relids);
        case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_MERGE_JOIN_MATERIALIZE,
                                             relids);
        case PGPA_TAG_MERGE_JOIN_PLAIN:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_MERGE_JOIN_PLAIN,
                                             relids);
        case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_NESTED_LOOP_MATERIALIZE,
                                             relids);
        case PGPA_TAG_NESTED_LOOP_MEMOIZE:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_NESTED_LOOP_MEMOIZE,
                                             relids);
        case PGPA_TAG_NESTED_LOOP_PLAIN:
            return pgpa_walker_contains_join(walker,
                                             JSTRAT_NESTED_LOOP_PLAIN,
                                             relids);
        case PGPA_TAG_NO_GATHER:
            return pgpa_walker_contains_no_gather(walker, relids);
    }
 
    /* should not get here */
    return false;
}
 
/*
 * Does the index target match the Plan?
 *
 * Should only be called when we know that itarget mandates an Index Scan or
 * Index Only Scan and this corresponds to the type of Plan. Here, our job is
 * just to check whether it's the same index.
 */
static bool
pgpa_walker_index_target_matches_plan(pgpa_index_target *itarget, Plan *plan)
{
    Oid         indexoid = InvalidOid;
 
    /* Retrieve the index OID from the plan. */
    if (IsA(plan, IndexScan))
        indexoid = ((IndexScan *) plan)->indexid;
    else if (IsA(plan, IndexOnlyScan))
        indexoid = ((IndexOnlyScan *) plan)->indexid;
    else
        elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan));
 
    /* Check whether schema name matches, if specified in index target. */
    if (itarget->indnamespace != NULL)
    {
        Oid         nspoid = get_rel_namespace(indexoid);
        char       *relnamespace = get_namespace_name_or_temp(nspoid);
 
        if (strcmp(itarget->indnamespace, relnamespace) != 0)
            return false;
    }
 
    /* Check whether relation name matches. */
    return (strcmp(itarget->indname, get_rel_name(indexoid)) == 0);
}
 
/*
 * Does an unrolled join match the join order specified by an advice target?
 */
static bool
pgpa_walker_join_order_matches(pgpa_unrolled_join *ujoin,
                               Index rtable_length,
                               pgpa_identifier *rt_identifiers,
                               pgpa_advice_target *target,
                               bool toplevel)
{
    int         nchildren = list_length(target->children);
 
    Assert(target->ttype == PGPA_TARGET_ORDERED_LIST);
 
    /* At toplevel, we allow a prefix match. */
    if (toplevel)
    {
        if (nchildren > ujoin->ninner + 1)
            return false;
    }
    else
    {
        if (nchildren != ujoin->ninner + 1)
            return false;
    }
 
    /* Outermost rel must match. */
    if (!pgpa_walker_join_order_matches_member(&ujoin->outer,
                                               rtable_length,
                                               rt_identifiers,
                                               linitial(target->children)))
        return false;
 
    /* Each inner rel must match. */
    for (int n = 0; n < nchildren - 1; ++n)
    {
        pgpa_advice_target *child_target = list_nth(target->children, n + 1);
 
        if (!pgpa_walker_join_order_matches_member(&ujoin->inner[n],
                                                   rtable_length,
                                                   rt_identifiers,
                                                   child_target))
            return false;
    }
 
    return true;
}
 
/*
 * Does one member of an unrolled join match an advice target?
 */
static bool
pgpa_walker_join_order_matches_member(pgpa_join_member *member,
                                      Index rtable_length,
                                      pgpa_identifier *rt_identifiers,
                                      pgpa_advice_target *target)
{
    Bitmapset  *relids = NULL;
 
    if (member->unrolled_join != NULL)
    {
        if (target->ttype != PGPA_TARGET_ORDERED_LIST)
            return false;
        return pgpa_walker_join_order_matches(member->unrolled_join,
                                              rtable_length,
                                              rt_identifiers,
                                              target,
                                              false);
    }
 
    Assert(member->scan != NULL);
    switch (target->ttype)
    {
        case PGPA_TARGET_ORDERED_LIST:
            /* Could only match an unrolled join */
            return false;
 
        case PGPA_TARGET_UNORDERED_LIST:
            {
                foreach_ptr(pgpa_advice_target, child_target, target->children)
                {
                    Index       rti;
 
                    rti = pgpa_compute_rti_from_identifier(rtable_length,
                                                           rt_identifiers,
                                                           &child_target->rid);
                    if (rti == 0)
                        return false;
                    relids = bms_add_member(relids, rti);
                }
                break;
            }
 
        case PGPA_TARGET_IDENTIFIER:
            {
                Index       rti;
 
                rti = pgpa_compute_rti_from_identifier(rtable_length,
                                                       rt_identifiers,
                                                       &target->rid);
                if (rti == 0)
                    return false;
                relids = bms_make_singleton(rti);
                break;
            }
    }
 
    return bms_equal(member->scan->relids, relids);
}
 
/*
 * Find the scan where the walker says that the given scan strategy should be
 * used for the given relid set, if one exists.
 *
 * Returns the pgpa_scan object, or NULL if none was found.
 */
static pgpa_scan *
pgpa_walker_find_scan(pgpa_plan_walker_context *walker,
                      pgpa_scan_strategy strategy,
                      Bitmapset *relids)
{
    List       *scans = walker->scans[strategy];
 
    foreach_ptr(pgpa_scan, scan, scans)
    {
        if (bms_equal(scan->relids, relids))
            return scan;
    }
 
    return NULL;
}
 
/*
 * Does this walker say that the given query feature applies to the given
 * relid set?
 */
static bool
pgpa_walker_contains_feature(pgpa_plan_walker_context *walker,
                             pgpa_qf_type type,
                             Bitmapset *relids)
{
    List       *query_features = walker->query_features[type];
 
    foreach_ptr(pgpa_query_feature, qf, query_features)
    {
        if (bms_equal(qf->relids, relids))
            return true;
    }
 
    return false;
}
 
/*
 * Does the walker say that the given join strategy should be used for the
 * given relid set?
 */
static bool
pgpa_walker_contains_join(pgpa_plan_walker_context *walker,
                          pgpa_join_strategy strategy,
                          Bitmapset *relids)
{
    List       *join_strategies = walker->join_strategies[strategy];
 
    foreach_ptr(Bitmapset, jsrelids, join_strategies)
    {
        if (bms_equal(jsrelids, relids))
            return true;
    }
 
    return false;
}
 
/*
 * Does the walker say that the given relids should be marked as NO_GATHER?
 */
static bool
pgpa_walker_contains_no_gather(pgpa_plan_walker_context *walker,
                               Bitmapset *relids)
{
    return bms_is_subset(relids, walker->no_gather_scans);
}
 
/*
 * Classify alternative subplans as chosen or discarded.
 */
static void
pgpa_classify_alternative_subplans(pgpa_plan_walker_context *walker,
                                   List *proots,
                                   List **chosen_proots,
                                   List **discarded_proots)
{
    Bitmapset  *all_scan_rtis = NULL;
 
    /* Initialize both output lists to empty. */
    *chosen_proots = NIL;
    *discarded_proots = NIL;
 
    /* Collect all scan RTIs. */
    for (int s = 0; s < NUM_PGPA_SCAN_STRATEGY; s++)
        foreach_ptr(pgpa_scan, scan, walker->scans[s])
            all_scan_rtis = bms_add_members(all_scan_rtis, scan->relids);
 
    /* Now classify each subplan. */
    foreach_ptr(pgpa_planner_info, proot, proots)
    {
        bool        chosen = false;
 
        /*
         * We're only interested in classifying subplans for which there are
         * alternatives.
         */
        if (!proot->is_alternative_plan)
            continue;
 
        /*
         * A subplan has been chosen if any of its scan RTIs appear in the
         * final plan. This cannot be the case if it has no RT offset.
         */
        if (proot->has_rtoffset)
        {
            for (int rti = 1; rti <= proot->rid_array_size; rti++)
            {
                if (proot->rid_array[rti - 1].alias_name != NULL &&
                    bms_is_member(proot->rtoffset + rti, all_scan_rtis))
                {
                    chosen = true;
                    break;
                }
            }
        }
 
        /* Add it to the correct list. */
        if (chosen)
            *chosen_proots = lappend(*chosen_proots, proot);
        else
            *discarded_proots = lappend(*discarded_proots, proot);
    }
}