Header And Logo

PostgreSQL
| The world's most advanced open source database.

Functions

planmain.c File Reference

#include "postgres.h"
#include "miscadmin.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
#include "utils/selfuncs.h"
Include dependency graph for planmain.c:

Go to the source code of this file.

Functions

void query_planner (PlannerInfo *root, List *tlist, double tuple_fraction, double limit_tuples, query_pathkeys_callback qp_callback, void *qp_extra, Path **cheapest_path, Path **sorted_path, double *num_groups)

Function Documentation

void query_planner ( PlannerInfo root,
List tlist,
double  tuple_fraction,
double  limit_tuples,
query_pathkeys_callback  qp_callback,
void *  qp_extra,
Path **  cheapest_path,
Path **  sorted_path,
double *  num_groups 
)

Definition at line 81 of file planmain.c.

References add_base_rels_to_query(), add_placeholders_to_base_rels(), Assert, build_base_rel_tlists(), PlannerInfo::canon_pathkeys, RelOptInfo::cheapest_total_path, compare_fractional_path_costs(), cost_sort(), create_lateral_join_info(), create_result_path(), deconstruct_jointree(), Query::distinctClause, elog, ERROR, estimate_num_groups(), find_lateral_references(), find_placeholders_in_jointree(), fix_placeholder_input_needed_levels(), FromExpr::fromlist, PlannerInfo::full_join_clauses, generate_base_implied_equalities(), get_cheapest_fractional_path_for_pathkeys(), get_sortgrouplist_exprs(), Query::groupClause, Query::hasAggs, PlannerInfo::initial_rels, PlannerInfo::join_cur_level, PlannerInfo::join_info_list, PlannerInfo::join_rel_hash, PlannerInfo::join_rel_level, PlannerInfo::join_rel_list, Query::jointree, PlannerInfo::lateral_info_list, PlannerInfo::left_join_clauses, PlannerInfo::limit_tuples, make_one_rel(), NIL, NULL, RelOptInfo::pages, Path::param_info, PlannerInfo::parse, parse(), Path::pathkeys, pathkeys_contained_in(), RelOptInfo::pathlist, PlannerInfo::placeholder_list, FromExpr::quals, reconsider_outer_join_clauses(), RelOptInfo::relid, RELOPT_BASEREL, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, remove_useless_joins(), PlannerInfo::right_join_clauses, RelOptInfo::rows, setup_simple_rel_arrays(), Path::startup_cost, Query::targetList, Path::total_cost, PlannerInfo::tuple_fraction, RelOptInfo::width, and work_mem.

Referenced by build_minmax_path(), and grouping_planner().

{
    Query      *parse = root->parse;
    List       *joinlist;
    RelOptInfo *final_rel;
    Path       *cheapestpath;
    Path       *sortedpath;
    Index       rti;
    double      total_pages;

    /* Make tuple_fraction, limit_tuples accessible to lower-level routines */
    root->tuple_fraction = tuple_fraction;
    root->limit_tuples = limit_tuples;

    *num_groups = 1;            /* default result */

    /*
     * If the query has an empty join tree, then it's something easy like
     * "SELECT 2+2;" or "INSERT ... VALUES()".  Fall through quickly.
     */
    if (parse->jointree->fromlist == NIL)
    {
        /* We need a trivial path result */
        *cheapest_path = (Path *)
            create_result_path((List *) parse->jointree->quals);
        *sorted_path = NULL;

        /*
         * We still are required to call qp_callback, in case it's something
         * like "SELECT 2+2 ORDER BY 1".
         */
        root->canon_pathkeys = NIL;
        (*qp_callback) (root, qp_extra);
        return;
    }

    /*
     * Init planner lists to empty.
     *
     * NOTE: append_rel_list was set up by subquery_planner, so do not touch
     * here; eq_classes and minmax_aggs may contain data already, too.
     */
    root->join_rel_list = NIL;
    root->join_rel_hash = NULL;
    root->join_rel_level = NULL;
    root->join_cur_level = 0;
    root->canon_pathkeys = NIL;
    root->left_join_clauses = NIL;
    root->right_join_clauses = NIL;
    root->full_join_clauses = NIL;
    root->join_info_list = NIL;
    root->lateral_info_list = NIL;
    root->placeholder_list = NIL;
    root->initial_rels = NIL;

    /*
     * Make a flattened version of the rangetable for faster access (this is
     * OK because the rangetable won't change any more), and set up an empty
     * array for indexing base relations.
     */
    setup_simple_rel_arrays(root);

    /*
     * Construct RelOptInfo nodes for all base relations in query, and
     * indirectly for all appendrel member relations ("other rels").  This
     * will give us a RelOptInfo for every "simple" (non-join) rel involved in
     * the query.
     *
     * Note: the reason we find the rels by searching the jointree and
     * appendrel list, rather than just scanning the rangetable, is that the
     * rangetable may contain RTEs for rels not actively part of the query,
     * for example views.  We don't want to make RelOptInfos for them.
     */
    add_base_rels_to_query(root, (Node *) parse->jointree);

    /*
     * Examine the targetlist and join tree, adding entries to baserel
     * targetlists for all referenced Vars, and generating PlaceHolderInfo
     * entries for all referenced PlaceHolderVars.  Restrict and join clauses
     * are added to appropriate lists belonging to the mentioned relations. We
     * also build EquivalenceClasses for provably equivalent expressions. The
     * SpecialJoinInfo list is also built to hold information about join order
     * restrictions.  Finally, we form a target joinlist for make_one_rel() to
     * work from.
     */
    build_base_rel_tlists(root, tlist);

    find_placeholders_in_jointree(root);

    find_lateral_references(root);

    joinlist = deconstruct_jointree(root);

    /*
     * Create the LateralJoinInfo list now that we have finalized
     * PlaceHolderVar eval levels.
     */
    create_lateral_join_info(root);

    /*
     * Reconsider any postponed outer-join quals now that we have built up
     * equivalence classes.  (This could result in further additions or
     * mergings of classes.)
     */
    reconsider_outer_join_clauses(root);

    /*
     * If we formed any equivalence classes, generate additional restriction
     * clauses as appropriate.  (Implied join clauses are formed on-the-fly
     * later.)
     */
    generate_base_implied_equalities(root);

    /*
     * We have completed merging equivalence sets, so it's now possible to
     * generate pathkeys in canonical form; so compute query_pathkeys and
     * other pathkeys fields in PlannerInfo.
     */
    (*qp_callback) (root, qp_extra);

    /*
     * Examine any "placeholder" expressions generated during subquery pullup.
     * Make sure that the Vars they need are marked as needed at the relevant
     * join level.  This must be done before join removal because it might
     * cause Vars or placeholders to be needed above a join when they weren't
     * so marked before.
     */
    fix_placeholder_input_needed_levels(root);

    /*
     * Remove any useless outer joins.  Ideally this would be done during
     * jointree preprocessing, but the necessary information isn't available
     * until we've built baserel data structures and classified qual clauses.
     */
    joinlist = remove_useless_joins(root, joinlist);

    /*
     * Now distribute "placeholders" to base rels as needed.  This has to be
     * done after join removal because removal could change whether a
     * placeholder is evaluatable at a base rel.
     */
    add_placeholders_to_base_rels(root);

    /*
     * We should now have size estimates for every actual table involved in
     * the query, and we also know which if any have been deleted from the
     * query by join removal; so we can compute total_table_pages.
     *
     * Note that appendrels are not double-counted here, even though we don't
     * bother to distinguish RelOptInfos for appendrel parents, because the
     * parents will still have size zero.
     *
     * XXX if a table is self-joined, we will count it once per appearance,
     * which perhaps is the wrong thing ... but that's not completely clear,
     * and detecting self-joins here is difficult, so ignore it for now.
     */
    total_pages = 0;
    for (rti = 1; rti < root->simple_rel_array_size; rti++)
    {
        RelOptInfo *brel = root->simple_rel_array[rti];

        if (brel == NULL)
            continue;

        Assert(brel->relid == rti);     /* sanity check on array */

        if (brel->reloptkind == RELOPT_BASEREL ||
            brel->reloptkind == RELOPT_OTHER_MEMBER_REL)
            total_pages += (double) brel->pages;
    }
    root->total_table_pages = total_pages;

    /*
     * Ready to do the primary planning.
     */
    final_rel = make_one_rel(root, joinlist);

    if (!final_rel || !final_rel->cheapest_total_path ||
        final_rel->cheapest_total_path->param_info != NULL)
        elog(ERROR, "failed to construct the join relation");

    /*
     * If there's grouping going on, estimate the number of result groups. We
     * couldn't do this any earlier because it depends on relation size
     * estimates that were set up above.
     *
     * Then convert tuple_fraction to fractional form if it is absolute, and
     * adjust it based on the knowledge that grouping_planner will be doing
     * grouping or aggregation work with our result.
     *
     * This introduces some undesirable coupling between this code and
     * grouping_planner, but the alternatives seem even uglier; we couldn't
     * pass back completed paths without making these decisions here.
     */
    if (parse->groupClause)
    {
        List       *groupExprs;

        groupExprs = get_sortgrouplist_exprs(parse->groupClause,
                                             parse->targetList);
        *num_groups = estimate_num_groups(root,
                                          groupExprs,
                                          final_rel->rows);

        /*
         * In GROUP BY mode, an absolute LIMIT is relative to the number of
         * groups not the number of tuples.  If the caller gave us a fraction,
         * keep it as-is.  (In both cases, we are effectively assuming that
         * all the groups are about the same size.)
         */
        if (tuple_fraction >= 1.0)
            tuple_fraction /= *num_groups;

        /*
         * If both GROUP BY and ORDER BY are specified, we will need two
         * levels of sort --- and, therefore, certainly need to read all the
         * tuples --- unless ORDER BY is a subset of GROUP BY.  Likewise if we
         * have both DISTINCT and GROUP BY, or if we have a window
         * specification not compatible with the GROUP BY.
         */
        if (!pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys) ||
            !pathkeys_contained_in(root->distinct_pathkeys, root->group_pathkeys) ||
         !pathkeys_contained_in(root->window_pathkeys, root->group_pathkeys))
            tuple_fraction = 0.0;

        /* In any case, limit_tuples shouldn't be specified here */
        Assert(limit_tuples < 0);
    }
    else if (parse->hasAggs || root->hasHavingQual)
    {
        /*
         * Ungrouped aggregate will certainly want to read all the tuples, and
         * it will deliver a single result row (so leave *num_groups 1).
         */
        tuple_fraction = 0.0;

        /* limit_tuples shouldn't be specified here */
        Assert(limit_tuples < 0);
    }
    else if (parse->distinctClause)
    {
        /*
         * Since there was no grouping or aggregation, it's reasonable to
         * assume the UNIQUE filter has effects comparable to GROUP BY. Return
         * the estimated number of output rows for use by caller. (If DISTINCT
         * is used with grouping, we ignore its effects for rowcount
         * estimation purposes; this amounts to assuming the grouped rows are
         * distinct already.)
         */
        List       *distinctExprs;

        distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
                                                parse->targetList);
        *num_groups = estimate_num_groups(root,
                                          distinctExprs,
                                          final_rel->rows);

        /*
         * Adjust tuple_fraction the same way as for GROUP BY, too.
         */
        if (tuple_fraction >= 1.0)
            tuple_fraction /= *num_groups;

        /* limit_tuples shouldn't be specified here */
        Assert(limit_tuples < 0);
    }
    else
    {
        /*
         * Plain non-grouped, non-aggregated query: an absolute tuple fraction
         * can be divided by the number of tuples.
         */
        if (tuple_fraction >= 1.0)
            tuple_fraction /= final_rel->rows;
    }

    /*
     * Pick out the cheapest-total path and the cheapest presorted path for
     * the requested pathkeys (if there is one).  We should take the tuple
     * fraction into account when selecting the cheapest presorted path, but
     * not when selecting the cheapest-total path, since if we have to sort
     * then we'll have to fetch all the tuples.  (But there's a special case:
     * if query_pathkeys is NIL, meaning order doesn't matter, then the
     * "cheapest presorted" path will be the cheapest overall for the tuple
     * fraction.)
     *
     * The cheapest-total path is also the one to use if grouping_planner
     * decides to use hashed aggregation, so we return it separately even if
     * this routine thinks the presorted path is the winner.
     */
    cheapestpath = final_rel->cheapest_total_path;

    sortedpath =
        get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
                                                  root->query_pathkeys,
                                                  NULL,
                                                  tuple_fraction);

    /* Don't return same path in both guises; just wastes effort */
    if (sortedpath == cheapestpath)
        sortedpath = NULL;

    /*
     * Forget about the presorted path if it would be cheaper to sort the
     * cheapest-total path.  Here we need consider only the behavior at the
     * tuple fraction point.
     */
    if (sortedpath)
    {
        Path        sort_path;  /* dummy for result of cost_sort */

        if (root->query_pathkeys == NIL ||
            pathkeys_contained_in(root->query_pathkeys,
                                  cheapestpath->pathkeys))
        {
            /* No sort needed for cheapest path */
            sort_path.startup_cost = cheapestpath->startup_cost;
            sort_path.total_cost = cheapestpath->total_cost;
        }
        else
        {
            /* Figure cost for sorting */
            cost_sort(&sort_path, root, root->query_pathkeys,
                      cheapestpath->total_cost,
                      final_rel->rows, final_rel->width,
                      0.0, work_mem, limit_tuples);
        }

        if (compare_fractional_path_costs(sortedpath, &sort_path,
                                          tuple_fraction) > 0)
        {
            /* Presorted path is a loser */
            sortedpath = NULL;
        }
    }

    *cheapest_path = cheapestpath;
    *sorted_path = sortedpath;
}