Header And Logo

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

Functions

planagg.c File Reference

#include "postgres.h"
#include "access/htup_details.h"
#include "catalog/pg_aggregate.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
#include "optimizer/subselect.h"
#include "parser/parsetree.h"
#include "parser/parse_clause.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
Include dependency graph for planagg.c:

Go to the source code of this file.

Functions

static bool find_minmax_aggs_walker (Node *node, List **context)
static bool build_minmax_path (PlannerInfo *root, MinMaxAggInfo *mminfo, Oid eqop, Oid sortop, bool nulls_first)
static void minmax_qp_callback (PlannerInfo *root, void *extra)
static void make_agg_subplan (PlannerInfo *root, MinMaxAggInfo *mminfo)
static Nodereplace_aggs_with_params_mutator (Node *node, PlannerInfo *root)
static Oid fetch_agg_sort_op (Oid aggfnoid)
void preprocess_minmax_aggregates (PlannerInfo *root, List *tlist)
Planoptimize_minmax_aggregates (PlannerInfo *root, List *tlist, const AggClauseCosts *aggcosts, Path *best_path)

Function Documentation

static bool build_minmax_path ( PlannerInfo root,
MinMaxAggInfo mminfo,
Oid  eqop,
Oid  sortop,
bool  nulls_first 
) [static]

Definition at line 374 of file planagg.c.

References NullTest::arg, NullTest::argisrow, Assert, assignSortGroupRef(), copyObject(), Query::distinctClause, SortGroupClause::eqop, Query::hasAggs, Query::hasDistinctOn, SortGroupClause::hashable, PlannerInfo::hasHavingQual, Query::havingQual, PlannerInfo::init_plans, Int64GetDatum(), INT8OID, InvalidOid, PlannerInfo::join_info_list, Query::jointree, PlannerInfo::lateral_info_list, lcons(), Query::limitCount, Query::limitOffset, list_copy(), list_make1, list_member(), makeConst(), makeNode, makeTargetEntry(), minmax_qp_callback(), NIL, NULL, SortGroupClause::nulls_first, NullTest::nulltesttype, palloc(), Path::parent, PlannerInfo::parse, MinMaxAggInfo::path, MinMaxAggInfo::pathcost, Path::pathkeys, pathkeys_contained_in(), PlannerInfo::placeholder_list, pstrdup(), FromExpr::quals, query_planner(), RelOptInfo::rows, PlannerInfo::sort_pathkeys, Query::sortClause, SortGroupClause::sortop, Path::startup_cost, MinMaxAggInfo::subroot, MinMaxAggInfo::target, Query::targetList, SortGroupClause::tleSortGroupRef, and Path::total_cost.

Referenced by preprocess_minmax_aggregates().

{
    PlannerInfo *subroot;
    Query      *parse;
    TargetEntry *tle;
    NullTest   *ntest;
    SortGroupClause *sortcl;
    Path       *cheapest_path;
    Path       *sorted_path;
    double      dNumGroups;
    Cost        path_cost;
    double      path_fraction;

    /*----------
     * Generate modified query of the form
     *      (SELECT col FROM tab
     *       WHERE col IS NOT NULL AND existing-quals
     *       ORDER BY col ASC/DESC
     *       LIMIT 1)
     *----------
     */
    subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
    memcpy(subroot, root, sizeof(PlannerInfo));
    subroot->parse = parse = (Query *) copyObject(root->parse);
    /* make sure subroot planning won't change root->init_plans contents */
    subroot->init_plans = list_copy(root->init_plans);
    /* There shouldn't be any OJ or LATERAL info to translate, as yet */
    Assert(subroot->join_info_list == NIL);
    Assert(subroot->lateral_info_list == NIL);
    /* and we haven't created PlaceHolderInfos, either */
    Assert(subroot->placeholder_list == NIL);

    /* single tlist entry that is the aggregate target */
    tle = makeTargetEntry(copyObject(mminfo->target),
                          (AttrNumber) 1,
                          pstrdup("agg_target"),
                          false);
    parse->targetList = list_make1(tle);

    /* No HAVING, no DISTINCT, no aggregates anymore */
    parse->havingQual = NULL;
    subroot->hasHavingQual = false;
    parse->distinctClause = NIL;
    parse->hasDistinctOn = false;
    parse->hasAggs = false;

    /* Build "target IS NOT NULL" expression */
    ntest = makeNode(NullTest);
    ntest->nulltesttype = IS_NOT_NULL;
    ntest->arg = copyObject(mminfo->target);
    /* we checked it wasn't a rowtype in find_minmax_aggs_walker */
    ntest->argisrow = false;

    /* User might have had that in WHERE already */
    if (!list_member((List *) parse->jointree->quals, ntest))
        parse->jointree->quals = (Node *)
            lcons(ntest, (List *) parse->jointree->quals);

    /* Build suitable ORDER BY clause */
    sortcl = makeNode(SortGroupClause);
    sortcl->tleSortGroupRef = assignSortGroupRef(tle, parse->targetList);
    sortcl->eqop = eqop;
    sortcl->sortop = sortop;
    sortcl->nulls_first = nulls_first;
    sortcl->hashable = false;   /* no need to make this accurate */
    parse->sortClause = list_make1(sortcl);

    /* set up expressions for LIMIT 1 */
    parse->limitOffset = NULL;
    parse->limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
                                           sizeof(int64),
                                           Int64GetDatum(1), false,
                                           FLOAT8PASSBYVAL);

    /*
     * Generate the best paths for this query, telling query_planner that we
     * have LIMIT 1.
     */
    query_planner(subroot, parse->targetList, 1.0, 1.0,
                  minmax_qp_callback, NULL,
                  &cheapest_path, &sorted_path, &dNumGroups);

    /*
     * Fail if no presorted path.  However, if query_planner determines that
     * the presorted path is also the cheapest, it will set sorted_path to
     * NULL ... don't be fooled.  (This is kind of a pain here, but it
     * simplifies life for grouping_planner, so leave it be.)
     */
    if (!sorted_path)
    {
        if (cheapest_path &&
            pathkeys_contained_in(subroot->sort_pathkeys,
                                  cheapest_path->pathkeys))
            sorted_path = cheapest_path;
        else
            return false;
    }

    /*
     * Determine cost to get just the first row of the presorted path.
     *
     * Note: cost calculation here should match
     * compare_fractional_path_costs().
     */
    if (sorted_path->parent->rows > 1.0)
        path_fraction = 1.0 / sorted_path->parent->rows;
    else
        path_fraction = 1.0;

    path_cost = sorted_path->startup_cost +
        path_fraction * (sorted_path->total_cost - sorted_path->startup_cost);

    /* Save state for further processing */
    mminfo->subroot = subroot;
    mminfo->path = sorted_path;
    mminfo->pathcost = path_cost;

    return true;
}

static Oid fetch_agg_sort_op ( Oid  aggfnoid  )  [static]

Definition at line 590 of file planagg.c.

References AGGFNOID, GETSTRUCT, HeapTupleIsValid, ObjectIdGetDatum, ReleaseSysCache(), and SearchSysCache1.

Referenced by find_minmax_aggs_walker().

{
    HeapTuple   aggTuple;
    Form_pg_aggregate aggform;
    Oid         aggsortop;

    /* fetch aggregate entry from pg_aggregate */
    aggTuple = SearchSysCache1(AGGFNOID, ObjectIdGetDatum(aggfnoid));
    if (!HeapTupleIsValid(aggTuple))
        return InvalidOid;
    aggform = (Form_pg_aggregate) GETSTRUCT(aggTuple);
    aggsortop = aggform->aggsortop;
    ReleaseSysCache(aggTuple);

    return aggsortop;
}

static bool find_minmax_aggs_walker ( Node node,
List **  context 
) [static]

Definition at line 304 of file planagg.c.

References MinMaxAggInfo::aggfnoid, Aggref::aggfnoid, Aggref::agglevelsup, Aggref::aggorder, MinMaxAggInfo::aggsortop, Aggref::args, Assert, contain_mutable_functions(), equal(), TargetEntry::expr, expression_tree_walker(), exprType(), fetch_agg_sort_op(), IsA, lappend(), lfirst, linitial, list_length(), makeNode, NIL, NULL, OidIsValid, MinMaxAggInfo::param, MinMaxAggInfo::path, MinMaxAggInfo::pathcost, MinMaxAggInfo::subroot, MinMaxAggInfo::target, and type_is_rowtype().

Referenced by preprocess_minmax_aggregates().

{
    if (node == NULL)
        return false;
    if (IsA(node, Aggref))
    {
        Aggref     *aggref = (Aggref *) node;
        Oid         aggsortop;
        TargetEntry *curTarget;
        MinMaxAggInfo *mminfo;
        ListCell   *l;

        Assert(aggref->agglevelsup == 0);
        if (list_length(aggref->args) != 1 || aggref->aggorder != NIL)
            return true;        /* it couldn't be MIN/MAX */
        /* note: we do not care if DISTINCT is mentioned ... */
        curTarget = (TargetEntry *) linitial(aggref->args);

        aggsortop = fetch_agg_sort_op(aggref->aggfnoid);
        if (!OidIsValid(aggsortop))
            return true;        /* not a MIN/MAX aggregate */

        if (contain_mutable_functions((Node *) curTarget->expr))
            return true;        /* not potentially indexable */

        if (type_is_rowtype(exprType((Node *) curTarget->expr)))
            return true;        /* IS NOT NULL would have weird semantics */

        /*
         * Check whether it's already in the list, and add it if not.
         */
        foreach(l, *context)
        {
            mminfo = (MinMaxAggInfo *) lfirst(l);
            if (mminfo->aggfnoid == aggref->aggfnoid &&
                equal(mminfo->target, curTarget->expr))
                return false;
        }

        mminfo = makeNode(MinMaxAggInfo);
        mminfo->aggfnoid = aggref->aggfnoid;
        mminfo->aggsortop = aggsortop;
        mminfo->target = curTarget->expr;
        mminfo->subroot = NULL; /* don't compute path yet */
        mminfo->path = NULL;
        mminfo->pathcost = 0;
        mminfo->param = NULL;

        *context = lappend(*context, mminfo);

        /*
         * We need not recurse into the argument, since it can't contain any
         * aggregates.
         */
        return false;
    }
    Assert(!IsA(node, SubLink));
    return expression_tree_walker(node, find_minmax_aggs_walker,
                                  (void *) context);
}

static void make_agg_subplan ( PlannerInfo root,
MinMaxAggInfo mminfo 
) [static]

Definition at line 517 of file planagg.c.

References create_plan(), exprCollation(), exprType(), PlannerInfo::init_plans, Query::limitCount, Query::limitOffset, list_concat_unique_ptr(), make_limit(), MinMaxAggInfo::param, PlannerInfo::parse, MinMaxAggInfo::path, SS_make_initplan_from_plan(), MinMaxAggInfo::subroot, MinMaxAggInfo::target, Query::targetList, and Plan::targetlist.

Referenced by optimize_minmax_aggregates().

{
    PlannerInfo *subroot = mminfo->subroot;
    Query      *subparse = subroot->parse;
    Plan       *plan;

    /*
     * Generate the plan for the subquery. We already have a Path, but we have
     * to convert it to a Plan and attach a LIMIT node above it.
     */
    plan = create_plan(subroot, mminfo->path);

    plan->targetlist = subparse->targetList;

    plan = (Plan *) make_limit(plan,
                               subparse->limitOffset,
                               subparse->limitCount,
                               0, 1);

    /*
     * Convert the plan into an InitPlan, and make a Param for its result.
     */
    mminfo->param =
        SS_make_initplan_from_plan(subroot, plan,
                                   exprType((Node *) mminfo->target),
                                   -1,
                                   exprCollation((Node *) mminfo->target));

    /*
     * Make sure the initplan gets into the outer PlannerInfo, along with any
     * other initplans generated by the sub-planning run.  We had to include
     * the outer PlannerInfo's pre-existing initplans into the inner one's
     * init_plans list earlier, so make sure we don't put back any duplicate
     * entries.
     */
    root->init_plans = list_concat_unique_ptr(root->init_plans,
                                              subroot->init_plans);
}

static void minmax_qp_callback ( PlannerInfo root,
void *  extra 
) [static]
Plan* optimize_minmax_aggregates ( PlannerInfo root,
List tlist,
const AggClauseCosts aggcosts,
Path best_path 
)

Definition at line 203 of file planagg.c.

References add_tlist_costs_to_plan(), AGG_PLAIN, cost_agg(), Query::havingQual, lfirst, make_agg_subplan(), make_result(), PlannerInfo::minmax_aggs, mutate_eclass_expressions(), NIL, NULL, Path::parent, PlannerInfo::parse, parse(), MinMaxAggInfo::pathcost, replace_aggs_with_params_mutator(), RelOptInfo::rows, Path::startup_cost, and Path::total_cost.

Referenced by grouping_planner().

{
    Query      *parse = root->parse;
    Cost        total_cost;
    Path        agg_p;
    Plan       *plan;
    Node       *hqual;
    ListCell   *lc;

    /* Nothing to do if preprocess_minmax_aggs rejected the query */
    if (root->minmax_aggs == NIL)
        return NULL;

    /*
     * Now we have enough info to compare costs against the generic aggregate
     * implementation.
     *
     * Note that we don't include evaluation cost of the tlist here; this is
     * OK since it isn't included in best_path's cost either, and should be
     * the same in either case.
     */
    total_cost = 0;
    foreach(lc, root->minmax_aggs)
    {
        MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);

        total_cost += mminfo->pathcost;
    }

    cost_agg(&agg_p, root, AGG_PLAIN, aggcosts,
             0, 0,
             best_path->startup_cost, best_path->total_cost,
             best_path->parent->rows);

    if (total_cost > agg_p.total_cost)
        return NULL;            /* too expensive */

    /*
     * OK, we are going to generate an optimized plan.
     *
     * First, generate a subplan and output Param node for each agg.
     */
    foreach(lc, root->minmax_aggs)
    {
        MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);

        make_agg_subplan(root, mminfo);
    }

    /*
     * Modify the targetlist and HAVING qual to reference subquery outputs
     */
    tlist = (List *) replace_aggs_with_params_mutator((Node *) tlist, root);
    hqual = replace_aggs_with_params_mutator(parse->havingQual, root);

    /*
     * We have to replace Aggrefs with Params in equivalence classes too, else
     * ORDER BY or DISTINCT on an optimized aggregate will fail.  We don't
     * need to process child eclass members though, since they aren't of
     * interest anymore --- and replace_aggs_with_params_mutator isn't able
     * to handle Aggrefs containing translated child Vars, anyway.
     *
     * Note: at some point it might become necessary to mutate other data
     * structures too, such as the query's sortClause or distinctClause. Right
     * now, those won't be examined after this point.
     */
    mutate_eclass_expressions(root,
                              replace_aggs_with_params_mutator,
                              (void *) root,
                              false);

    /*
     * Generate the output plan --- basically just a Result
     */
    plan = (Plan *) make_result(root, tlist, hqual, NULL);

    /* Account for evaluation cost of the tlist (make_result did the rest) */
    add_tlist_costs_to_plan(root, plan, tlist);

    return plan;
}

void preprocess_minmax_aggregates ( PlannerInfo root,
List tlist 
)

Definition at line 69 of file planagg.c.

References MinMaxAggInfo::aggsortop, Assert, build_minmax_path(), elog, ERROR, find_minmax_aggs_walker(), FromExpr::fromlist, get_equality_op_for_ordering_op(), Query::groupClause, Query::hasAggs, Query::hasWindowFuncs, Query::havingQual, RangeTblEntry::inh, IsA, Query::jointree, lfirst, linitial, list_length(), PlannerInfo::minmax_aggs, NIL, OidIsValid, PlannerInfo::parse, parse(), planner_rt_fetch, Query::rowMarks, RTE_RELATION, RTE_SUBQUERY, RangeTblEntry::rtekind, RangeTblRef::rtindex, and Query::setOperations.

Referenced by grouping_planner().

{
    Query      *parse = root->parse;
    FromExpr   *jtnode;
    RangeTblRef *rtr;
    RangeTblEntry *rte;
    List       *aggs_list;
    ListCell   *lc;

    /* minmax_aggs list should be empty at this point */
    Assert(root->minmax_aggs == NIL);

    /* Nothing to do if query has no aggregates */
    if (!parse->hasAggs)
        return;

    Assert(!parse->setOperations);      /* shouldn't get here if a setop */
    Assert(parse->rowMarks == NIL);     /* nor if FOR UPDATE */

    /*
     * Reject unoptimizable cases.
     *
     * We don't handle GROUP BY or windowing, because our current
     * implementations of grouping require looking at all the rows anyway, and
     * so there's not much point in optimizing MIN/MAX.  (Note: relaxing this
     * would likely require some restructuring in grouping_planner(), since it
     * performs assorted processing related to these features between calling
     * preprocess_minmax_aggregates and optimize_minmax_aggregates.)
     */
    if (parse->groupClause || parse->hasWindowFuncs)
        return;

    /*
     * We also restrict the query to reference exactly one table, since join
     * conditions can't be handled reasonably.  (We could perhaps handle a
     * query containing cartesian-product joins, but it hardly seems worth the
     * trouble.)  However, the single table could be buried in several levels
     * of FromExpr due to subqueries.  Note the "single" table could be an
     * inheritance parent, too, including the case of a UNION ALL subquery
     * that's been flattened to an appendrel.
     */
    jtnode = parse->jointree;
    while (IsA(jtnode, FromExpr))
    {
        if (list_length(jtnode->fromlist) != 1)
            return;
        jtnode = linitial(jtnode->fromlist);
    }
    if (!IsA(jtnode, RangeTblRef))
        return;
    rtr = (RangeTblRef *) jtnode;
    rte = planner_rt_fetch(rtr->rtindex, root);
    if (rte->rtekind == RTE_RELATION)
         /* ordinary relation, ok */ ;
    else if (rte->rtekind == RTE_SUBQUERY && rte->inh)
         /* flattened UNION ALL subquery, ok */ ;
    else
        return;

    /*
     * Scan the tlist and HAVING qual to find all the aggregates and verify
     * all are MIN/MAX aggregates.  Stop as soon as we find one that isn't.
     */
    aggs_list = NIL;
    if (find_minmax_aggs_walker((Node *) tlist, &aggs_list))
        return;
    if (find_minmax_aggs_walker(parse->havingQual, &aggs_list))
        return;

    /*
     * OK, there is at least the possibility of performing the optimization.
     * Build an access path for each aggregate.  (We must do this now because
     * we need to call query_planner with a pristine copy of the current query
     * tree; it'll be too late when optimize_minmax_aggregates gets called.)
     * If any of the aggregates prove to be non-indexable, give up; there is
     * no point in optimizing just some of them.
     */
    foreach(lc, aggs_list)
    {
        MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);
        Oid         eqop;
        bool        reverse;

        /*
         * We'll need the equality operator that goes with the aggregate's
         * ordering operator.
         */
        eqop = get_equality_op_for_ordering_op(mminfo->aggsortop, &reverse);
        if (!OidIsValid(eqop))  /* shouldn't happen */
            elog(ERROR, "could not find equality operator for ordering operator %u",
                 mminfo->aggsortop);

        /*
         * We can use either an ordering that gives NULLS FIRST or one that
         * gives NULLS LAST; furthermore there's unlikely to be much
         * performance difference between them, so it doesn't seem worth
         * costing out both ways if we get a hit on the first one.  NULLS
         * FIRST is more likely to be available if the operator is a
         * reverse-sort operator, so try that first if reverse.
         */
        if (build_minmax_path(root, mminfo, eqop, mminfo->aggsortop, reverse))
            continue;
        if (build_minmax_path(root, mminfo, eqop, mminfo->aggsortop, !reverse))
            continue;

        /* No indexable path for this aggregate, so fail */
        return;
    }

    /*
     * We're done until path generation is complete.  Save info for later.
     * (Setting root->minmax_aggs non-NIL signals we succeeded in making index
     * access paths for all the aggregates.)
     */
    root->minmax_aggs = aggs_list;
}

static Node * replace_aggs_with_params_mutator ( Node node,
PlannerInfo root 
) [static]

Definition at line 560 of file planagg.c.

References Aggref::aggfnoid, MinMaxAggInfo::aggfnoid, Aggref::args, Assert, elog, equal(), ERROR, TargetEntry::expr, expression_tree_mutator(), IsA, lfirst, linitial, PlannerInfo::minmax_aggs, NULL, MinMaxAggInfo::param, and MinMaxAggInfo::target.

Referenced by optimize_minmax_aggregates().

{
    if (node == NULL)
        return NULL;
    if (IsA(node, Aggref))
    {
        Aggref     *aggref = (Aggref *) node;
        TargetEntry *curTarget = (TargetEntry *) linitial(aggref->args);
        ListCell   *lc;

        foreach(lc, root->minmax_aggs)
        {
            MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);

            if (mminfo->aggfnoid == aggref->aggfnoid &&
                equal(mminfo->target, curTarget->expr))
                return (Node *) mminfo->param;
        }
        elog(ERROR, "failed to re-find MinMaxAggInfo record");
    }
    Assert(!IsA(node, SubLink));
    return expression_tree_mutator(node, replace_aggs_with_params_mutator,
                                   (void *) root);
}