PostgreSQL在何处处理 sql查询之五十七

/*
 * add_path
 *      Consider a potential implementation path for the specified parent rel,
 *      and add it to the rel's pathlist if it is worthy of consideration.
 *      A path is worthy if it has a better sort order (better pathkeys) or
 *      cheaper cost (on either dimension), or generates fewer rows, than any
 *      existing path that has the same or superset parameterization rels.
 *
 *      We also remove from the rel's pathlist any old paths that are dominated
 *      by new_path --- that is, new_path is cheaper, at least as well ordered,
 *      generates no more rows, and requires no outer rels not required by the
 *      old path.
 *
 *      In most cases, a path with a superset parameterization will generate
 *      fewer rows (since it has more join clauses to apply), so that those two
 *      figures of merit move in opposite directions; this means that a path of
 *      one parameterization can seldom dominate a path of another.  But such
 *      cases do arise, so we make the full set of checks anyway.
 *
 *      There is one policy decision embedded in this function, along with its
 *      sibling add_path_precheck: we treat all parameterized paths as having
 *      NIL pathkeys, so that they compete only on cost.    This is to reduce
 *      the number of parameterized paths that are kept.    See discussion in
 *      src/backend/optimizer/README.
 *
 *      The pathlist is kept sorted by total_cost, with cheaper paths
 *      at the front.  Within this routine, that's simply a speed hack:
 *      doing it that way makes it more likely that we will reject an inferior
 *      path after a few comparisons, rather than many comparisons.
 *      However, add_path_precheck relies on this ordering to exit early
 *      when possible.
 *
 *      NOTE: discarded Path objects are immediately pfree'd to reduce planner
 *      memory consumption.  We dare not try to free the substructure of a Path,
 *      since much of it may be shared with other Paths or the query tree itself;
 *      but just recycling discarded Path nodes is a very useful savings in
 *      a large join tree.  We can recycle the List nodes of pathlist, too.
 *
 *      BUT: we do not pfree IndexPath objects, since they may be referenced as
 *      children of BitmapHeapPaths as well as being paths in their own right.
 *
 * 'parent_rel' is the relation entry to which the path corresponds.
 * 'new_path' is a potential path for parent_rel.
 *
 * Returns nothing, but modifies parent_rel->pathlist.
 */
void
add_path(RelOptInfo *parent_rel, Path *new_path)
{
    bool        accept_new = true;        /* unless we find a superior old path */
    ListCell   *insert_after = NULL;    /* where to insert new item */
    List       *new_path_pathkeys;
    ListCell   *p1;
    ListCell   *p1_prev;
    ListCell   *p1_next;

    /*
     * This is a convenient place to check for query cancel --- no part of the
     * planner goes very long without calling add_path().
     */
    CHECK_FOR_INTERRUPTS();

    /* Pretend parameterized paths have no pathkeys, per comment above */
    new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys;

    /*
     * Loop to check proposed new path against old paths.  Note it is possible
     * for more than one old path to be tossed out because new_path dominates
     * it.
     *
     * We can't use foreach here because the loop body may delete the current
     * list cell.
     */
    p1_prev = NULL;
    for (p1 = list_head(parent_rel->pathlist); p1 != NULL; p1 = p1_next)
    {
        Path       *old_path = (Path *) lfirst(p1);
        bool        remove_old = false; /* unless new proves superior */
        PathCostComparison costcmp;
        PathKeysComparison keyscmp;
        BMS_Comparison outercmp;

        p1_next = lnext(p1);

        /*
         * Do a fuzzy cost comparison with 1% fuzziness limit.    (XXX does this
         * percentage need to be user-configurable?)
         */
        costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01);

        /*
         * If the two paths compare differently for startup and total cost,
         * then we want to keep both, and we can skip comparing pathkeys and
         * required_outer rels.  If they compare the same, proceed with the
         * other comparisons.  Row count is checked last.  (We make the tests
         * in this order because the cost comparison is most likely to turn
         * out "different", and the pathkeys comparison next most likely.  As
         * explained above, row count very seldom makes a difference, so even
         * though it's cheap to compare there's not much point in checking it
         * earlier.)
         */
        if (costcmp != COSTS_DIFFERENT)
        {
            /* Similarly check to see if either dominates on pathkeys */
            List       *old_path_pathkeys;

            old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
            keyscmp = compare_pathkeys(new_path_pathkeys,
                                       old_path_pathkeys);
            if (keyscmp != PATHKEYS_DIFFERENT)
            {
                switch (costcmp)
                {
                    case COSTS_EQUAL:
                        outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
                                                   PATH_REQ_OUTER(old_path));
                        if (keyscmp == PATHKEYS_BETTER1)
                        {
                            if ((outercmp == BMS_EQUAL ||
                                 outercmp == BMS_SUBSET1) &&
                                new_path->rows <= old_path->rows)
                                remove_old = true;        /* new dominates old */
                        }
                        else if (keyscmp == PATHKEYS_BETTER2)
                        {
                            if ((outercmp == BMS_EQUAL ||
                                 outercmp == BMS_SUBSET2) &&
                                new_path->rows >= old_path->rows)
                                accept_new = false;        /* old dominates new */
                        }
                        else    /* keyscmp == PATHKEYS_EQUAL */
                        {
                            if (outercmp == BMS_EQUAL)
                            {
                                /*
                                 * Same pathkeys and outer rels, and fuzzily
                                 * the same cost, so keep just one; to decide
                                 * which, first check rows and then do a fuzzy
                                 * cost comparison with very small fuzz limit.
                                 * (We used to do an exact cost comparison,
                                 * but that results in annoying
                                 * platform-specific plan variations due to
                                 * roundoff in the cost estimates.)  If things
                                 * are still tied, arbitrarily keep only the
                                 * old path.  Notice that we will keep only
                                 * the old path even if the less-fuzzy
                                 * comparison decides the startup and total
                                 * costs compare differently.
                                 */
                                if (new_path->rows < old_path->rows)
                                    remove_old = true;    /* new dominates old */
                                else if (new_path->rows > old_path->rows)
                                    accept_new = false; /* old dominates new */
                                else if (compare_path_costs_fuzzily(new_path, old_path,
                                              1.0000000001) == COSTS_BETTER1)
                                    remove_old = true;    /* new dominates old */
                                else
                                    accept_new = false; /* old equals or
                                                         * dominates new */
                            }
                            else if (outercmp == BMS_SUBSET1 &&
                                     new_path->rows <= old_path->rows)
                                remove_old = true;        /* new dominates old */
                            else if (outercmp == BMS_SUBSET2 &&
                                     new_path->rows >= old_path->rows)
                                accept_new = false;        /* old dominates new */
                            /* else different parameterizations, keep both */
                        }
                        break;
                    case COSTS_BETTER1:
                        if (keyscmp != PATHKEYS_BETTER2)
                        {
                            outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
                                                   PATH_REQ_OUTER(old_path));
                            if ((outercmp == BMS_EQUAL ||
                                 outercmp == BMS_SUBSET1) &&
                                new_path->rows <= old_path->rows)
                                remove_old = true;        /* new dominates old */
                        }
                        break;
                    case COSTS_BETTER2:
                        if (keyscmp != PATHKEYS_BETTER1)
                        {
                            outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
                                                   PATH_REQ_OUTER(old_path));
                            if ((outercmp == BMS_EQUAL ||
                                 outercmp == BMS_SUBSET2) &&
                                new_path->rows >= old_path->rows)
                                accept_new = false;        /* old dominates new */
                        }
                        break;
                    case COSTS_DIFFERENT:

                        /*
                         * can't get here, but keep this case to keep compiler
                         * quiet
                         */
                        break;
                }
            }
        }

        /*
         * Remove current element from pathlist if dominated by new.
         */
        if (remove_old)
        {
            parent_rel->pathlist = list_delete_cell(parent_rel->pathlist,
                                                    p1, p1_prev);

            /*
             * Delete the data pointed-to by the deleted cell, if possible
             */
            if (!IsA(old_path, IndexPath))
                pfree(old_path);
            /* p1_prev does not advance */
        }
        else
        {
            /* new belongs after this old path if it has cost >= old's */
            if (new_path->total_cost >= old_path->total_cost)
                insert_after = p1;
            /* p1_prev advances */
            p1_prev = p1;
        }

        /*
         * If we found an old path that dominates new_path, we can quit
         * scanning the pathlist; we will not add new_path, and we assume
         * new_path cannot dominate any other elements of the pathlist.
         */
        if (!accept_new)
            break;
    }

    if (accept_new)
    {
        /* Accept the new path: insert it at proper place in pathlist */
        if (insert_after)
            lappend_cell(parent_rel->pathlist, insert_after, new_path);
        else
            parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
    }
    else
    {
        /* Reject and recycle the new path */
        if (!IsA(new_path, IndexPath))
            pfree(new_path);
    }
}

/*
 * set_plain_rel_pathlist
 *      Build access paths for a plain relation (no subquery, no inheritance)
 */
static void
set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
{
    ///fprintf(stderr,"In set_plain_rel_pathlist \n");

    /* Consider sequential scan */
    add_path(rel, create_seqscan_path(root, rel, NULL));

    /* Consider index scans */
    create_index_paths(root, rel);

    /* Consider TID scans */
    create_tidscan_paths(root, rel);

    /* Now find the cheapest of the paths for this rel */
    set_cheapest(rel);
}