Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1er4Be-000721-QH for pgsql-hackers@arkaria.postgresql.org; Wed, 28 Feb 2018 16:02:35 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1er4Bd-0001T2-MX for pgsql-hackers@arkaria.postgresql.org; Wed, 28 Feb 2018 16:02:33 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1er4Bd-0001Ss-6U for pgsql-hackers@lists.postgresql.org; Wed, 28 Feb 2018 16:02:33 +0000 Received: from mx2.mailbox.org ([80.241.60.215]) by magus.postgresql.org with esmtps (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1er4BL-0003iY-DP for pgsql-hackers@postgresql.org; Wed, 28 Feb 2018 16:02:32 +0000 Received: from smtp2.mailbox.org (smtp2.mailbox.org [80.241.60.241]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx2.mailbox.org (Postfix) with ESMTPS id 9968640F4E; Wed, 28 Feb 2018 17:02:13 +0100 (CET) X-Virus-Scanned: amavisd-new at heinlein-support.de Received: from smtp2.mailbox.org ([80.241.60.241]) by hefe.heinlein-support.de (hefe.heinlein-support.de [91.198.250.172]) (amavisd-new, port 10030) with ESMTP id BLqq8wW2IxbY; Wed, 28 Feb 2018 17:01:57 +0100 (CET) From: Antonin Houska To: Robert Haas cc: "pgsql-hackers@postgresql.org" Subject: Re: [HACKERS] WIP: Aggregation push-down In-reply-to: References: <9666.1491295317@localhost> <8160.1493369169@localhost> <29613.1502983342@localhost> <14577.1509723225@localhost> <18007.1513957437@localhost> Comments: In-reply-to Robert Haas message dated "Mon, 15 Jan 2018 16:15:42 -0500." MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Date: Wed, 28 Feb 2018 17:02:43 +0100 Message-ID: <31585.1519833763@localhost> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Robert Haas wrote: > On Fri, Dec 22, 2017 at 10:43 AM, Antonin Houska wrote: > > Michael Paquier wrote: > >> On Sat, Nov 4, 2017 at 12:33 AM, Antonin Houska wrote: > >> > I'm not about to add any other features now. Implementation of the m= issing > >> > parts (see the TODO comments in the code) is the next step. But what= I'd > >> > appreciate most is a feedback on the design. Thanks. > >> > >> I am getting a conflict after applying patch 5 but this did not get > >> any reviews so moved to next CF with waiting on author as status. > > > > Attached is the next version. > translate_expression_to_rels() looks unsafe. Equivalence members are > known to be equal under the semantics of the relevant operator class, > but that doesn't mean that one can be freely substituted for another. > For example: >=20 > rhaas=3D# create table one (a numeric); > CREATE TABLE > rhaas=3D# create table two (a numeric); > CREATE TABLE > rhaas=3D# insert into one values ('0'); > INSERT 0 1 > rhaas=3D# insert into two values ('0.00'); > INSERT 0 1 > rhaas=3D# select one.a, count(*) from one, two where one.a =3D two.a grou= p by 1; > a | count > ---+------- > 0 | 1 > (1 row) >=20 > rhaas=3D# select two.a, count(*) from one, two where one.a =3D two.a grou= p by 1; > a | count > ------+------- > 0.00 | 1 > (1 row) >=20 > There are, admittedly, a large number of data types for which such a > substitution would work just fine. numeric will not, citext will not, > but many others are fine. Regrettably, we have no framework in the > system for identifying equality operators which actually test identity > versus some looser notion of equality. Cross-type operators are a > problem, too; if we have foo.x =3D bar.y in the query, one might be int4 > and the other int8, for example, but they can still belong to the same > equivalence class. >=20 > Concretely, in your test query "SELECT p.i, avg(c1.v) FROM > agg_pushdown_parent AS p JOIN agg_pushdown_child1 AS c1 ON c1.parent =3D > p.i GROUP BY p.i" you assume that it's OK to do a Partial > HashAggregate over c1.parent rather than p.i. This will be false if, > say, c1.parent is of type citext and p.i is of type text; this will > get grouped together that shouldn't. It will also be false if the > grouping expression is something like GROUP BY length(p.i::text), > because one value could be '0'::numeric and the other '0.00'::numeric. > I can't think of a reason why it would be false if the grouping > expressions are both simple Vars of the same underlying data type, but > I'm a little nervous that I might be wrong even about that case. > Maybe you've handled all of this somehow, but it's not obvious to me > that it has been considered. These problems are still being investigated, see [1] > Another thing I noticed is that the GroupedPathInfo looks a bit like a > stripped-down RelOptInfo, in that for example it has both a pathlist > and a partial_pathlist. I'm inclined to think that we should build new > RelOptInfos instead. As you have it, there are an awful lot of things > that seem to know about the grouped/ungrouped distinction, many of > which are quite low-level functions like add_path(), > add_paths_to_append_rel(), try_nestloop_path(), etc. I think that > some of this would go away if you had separate RelOptInfos instead of > GroupedPathInfo. I've reworked the patch so that separate RelOptInfo is used for grouped relation. The attached patch is only the core part. Neither postgres_fdw changes nor the part that tries to avoid the final aggregation is included here. I'll add these when the patch does not seem to need another major rew= ork. [1] https://www.postgresql.org/message-id/CA+Tgmoa5Pp-DBJg=3DW8Xj8Czf-32Pfx= PgxwFPkA6qN2w_wPX8bg@mail.gmail.com --=20 Antonin Houska Cybertec Sch=C3=B6nig & Sch=C3=B6nig GmbH Gr=C3=B6hrm=C3=BChlgasse 26, A-2700 Wiener Neustadt Web: https://www.cybertec-postgresql.com --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=agg_pushdown_v6.diff diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c new file mode 100644 index db5fcaf..813249a *** a/src/backend/executor/execExpr.c --- b/src/backend/executor/execExpr.c *************** ExecInitExprRec(Expr *node, ExprState *s *** 794,799 **** --- 794,840 ---- break; } + case T_GroupedVar: + + /* + * If GroupedVar appears in targetlist of Agg node, it can + * represent either Aggref or grouping expression. + */ + if (state->parent && (IsA(state->parent, AggState))) + { + GroupedVar *gvar = (GroupedVar *) node; + + /* + * The only reason to execute GroupedVar is to generate either + * aggregate transient state or grouping expression value. So + * any contained Aggref must be partial. + * + * (The purpose of propagating GroupedVars to upper plan nodes + * is just to transfer the value, no execution takes place + * there.) + */ + if (IsA(gvar->gvexpr, Aggref)) + + ExecInitExprRec((Expr *) gvar->agg_partial, state, + resv, resnull); + else + ExecInitExprRec((Expr *) gvar->gvexpr, state, + resv, resnull); + break; + } + else + { + /* + * set_plan_refs should have replaced GroupedVar in the + * targetlist with an ordinary Var. + * + * XXX Should we error out here? There's at least one legal + * case here which we'd have to check: a Result plan with no + * outer plan which represents an empty Append plan. + */ + break; + } + case T_GroupingFunc: { GroupingFunc *grp_node = (GroupingFunc *) node; diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c new file mode 100644 index 266a3ef..dca0653 *** a/src/backend/nodes/copyfuncs.c --- b/src/backend/nodes/copyfuncs.c *************** _copyAggref(const Aggref *from) *** 1367,1372 **** --- 1367,1373 ---- COPY_SCALAR_FIELD(aggcollid); COPY_SCALAR_FIELD(inputcollid); COPY_SCALAR_FIELD(aggtranstype); + COPY_SCALAR_FIELD(aggcombinefn); COPY_NODE_FIELD(aggargtypes); COPY_NODE_FIELD(aggdirectargs); COPY_NODE_FIELD(args); *************** _copyPlaceHolderVar(const PlaceHolderVar *** 2219,2224 **** --- 2220,2241 ---- } /* + * _copyGroupedVar + */ + static GroupedVar * + _copyGroupedVar(const GroupedVar *from) + { + GroupedVar *newnode = makeNode(GroupedVar); + + COPY_NODE_FIELD(gvexpr); + COPY_NODE_FIELD(agg_partial); + COPY_SCALAR_FIELD(sortgroupref); + COPY_SCALAR_FIELD(gvid); + + return newnode; + } + + /* * _copySpecialJoinInfo */ static SpecialJoinInfo * *************** _copyPlaceHolderInfo(const PlaceHolderIn *** 2292,2297 **** --- 2309,2329 ---- return newnode; } + static GroupedVarInfo * + _copyGroupedVarInfo(const GroupedVarInfo *from) + { + GroupedVarInfo *newnode = makeNode(GroupedVarInfo); + + COPY_SCALAR_FIELD(gvid); + COPY_NODE_FIELD(gvexpr); + COPY_NODE_FIELD(agg_partial); + COPY_SCALAR_FIELD(sortgroupref); + COPY_SCALAR_FIELD(gv_eval_at); + COPY_SCALAR_FIELD(gv_width); + + return newnode; + } + /* **************************************************************** * parsenodes.h copy functions * **************************************************************** *************** copyObjectImpl(const void *from) *** 5034,5039 **** --- 5066,5074 ---- case T_PlaceHolderVar: retval = _copyPlaceHolderVar(from); break; + case T_GroupedVar: + retval = _copyGroupedVar(from); + break; case T_SpecialJoinInfo: retval = _copySpecialJoinInfo(from); break; *************** copyObjectImpl(const void *from) *** 5046,5051 **** --- 5081,5089 ---- case T_PlaceHolderInfo: retval = _copyPlaceHolderInfo(from); break; + case T_GroupedVarInfo: + retval = _copyGroupedVarInfo(from); + break; /* * VALUE NODES diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c new file mode 100644 index bbffc87..fb26311 *** a/src/backend/nodes/equalfuncs.c --- b/src/backend/nodes/equalfuncs.c *************** _equalPlaceHolderVar(const PlaceHolderVa *** 873,878 **** --- 873,886 ---- } static bool + _equalGroupedVar(const GroupedVar *a, const GroupedVar *b) + { + COMPARE_SCALAR_FIELD(gvid); + + return true; + } + + static bool _equalSpecialJoinInfo(const SpecialJoinInfo *a, const SpecialJoinInfo *b) { COMPARE_BITMAPSET_FIELD(min_lefthand); *************** equal(const void *a, const void *b) *** 3179,3184 **** --- 3187,3195 ---- case T_PlaceHolderVar: retval = _equalPlaceHolderVar(a, b); break; + case T_GroupedVar: + retval = _equalGroupedVar(a, b); + break; case T_SpecialJoinInfo: retval = _equalSpecialJoinInfo(a, b); break; diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c new file mode 100644 index 6c76c41..d34b26b *** a/src/backend/nodes/nodeFuncs.c --- b/src/backend/nodes/nodeFuncs.c *************** exprType(const Node *expr) *** 259,264 **** --- 259,270 ---- case T_PlaceHolderVar: type = exprType((Node *) ((const PlaceHolderVar *) expr)->phexpr); break; + case T_GroupedVar: + if (IsA(((const GroupedVar *) expr)->gvexpr, Aggref)) + type = exprType((Node *) ((const GroupedVar *) expr)->agg_partial); + else + type = exprType((Node *) ((const GroupedVar *) expr)->gvexpr); + break; default: elog(ERROR, "unrecognized node type: %d", (int) nodeTag(expr)); type = InvalidOid; /* keep compiler quiet */ *************** exprTypmod(const Node *expr) *** 492,497 **** --- 498,508 ---- return ((const SetToDefault *) expr)->typeMod; case T_PlaceHolderVar: return exprTypmod((Node *) ((const PlaceHolderVar *) expr)->phexpr); + case T_GroupedVar: + if (IsA(((const GroupedVar *) expr)->gvexpr, Aggref)) + return exprTypmod((Node *) ((const GroupedVar *) expr)->agg_partial); + else + return exprTypmod((Node *) ((const GroupedVar *) expr)->gvexpr); default: break; } *************** exprCollation(const Node *expr) *** 903,908 **** --- 914,925 ---- case T_PlaceHolderVar: coll = exprCollation((Node *) ((const PlaceHolderVar *) expr)->phexpr); break; + case T_GroupedVar: + if (IsA(((const GroupedVar *) expr)->gvexpr, Aggref)) + coll = exprCollation((Node *) ((const GroupedVar *) expr)->agg_partial); + else + coll = exprCollation((Node *) ((const GroupedVar *) expr)->gvexpr); + break; default: elog(ERROR, "unrecognized node type: %d", (int) nodeTag(expr)); coll = InvalidOid; /* keep compiler quiet */ *************** expression_tree_walker(Node *node, *** 2176,2181 **** --- 2193,2200 ---- break; case T_PlaceHolderVar: return walker(((PlaceHolderVar *) node)->phexpr, context); + case T_GroupedVar: + return walker(((GroupedVar *) node)->gvexpr, context); case T_InferenceElem: return walker(((InferenceElem *) node)->expr, context); case T_AppendRelInfo: *************** expression_tree_mutator(Node *node, *** 2968,2973 **** --- 2987,3002 ---- return (Node *) newnode; } break; + case T_GroupedVar: + { + GroupedVar *gv = (GroupedVar *) node; + GroupedVar *newnode; + + FLATCOPY(newnode, gv, GroupedVar); + MUTATE(newnode->gvexpr, gv->gvexpr, Expr *); + MUTATE(newnode->agg_partial, gv->agg_partial, Aggref *); + return (Node *) newnode; + } case T_InferenceElem: { InferenceElem *inferenceelemdexpr = (InferenceElem *) node; diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c new file mode 100644 index 011d2a3..37d2fb0 *** a/src/backend/nodes/outfuncs.c --- b/src/backend/nodes/outfuncs.c *************** _outAggref(StringInfo str, const Aggref *** 1142,1147 **** --- 1142,1148 ---- WRITE_OID_FIELD(aggcollid); WRITE_OID_FIELD(inputcollid); WRITE_OID_FIELD(aggtranstype); + WRITE_OID_FIELD(aggcombinefn); WRITE_NODE_FIELD(aggargtypes); WRITE_NODE_FIELD(aggdirectargs); WRITE_NODE_FIELD(args); *************** _outPlannerInfo(StringInfo str, const Pl *** 2218,2223 **** --- 2219,2225 ---- WRITE_BITMAPSET_FIELD(all_baserels); WRITE_BITMAPSET_FIELD(nullable_baserels); WRITE_NODE_FIELD(join_rel_list); + WRITE_NODE_FIELD(join_grouped_rel_list); WRITE_INT_FIELD(join_cur_level); WRITE_NODE_FIELD(init_plans); WRITE_NODE_FIELD(cte_plan_ids); *************** _outPlannerInfo(StringInfo str, const Pl *** 2232,2237 **** --- 2234,2240 ---- WRITE_NODE_FIELD(pcinfo_list); WRITE_NODE_FIELD(rowMarks); WRITE_NODE_FIELD(placeholder_list); + WRITE_NODE_FIELD(grouped_var_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); WRITE_NODE_FIELD(group_pathkeys); *************** _outPlannerInfo(StringInfo str, const Pl *** 2239,2244 **** --- 2242,2248 ---- WRITE_NODE_FIELD(distinct_pathkeys); WRITE_NODE_FIELD(sort_pathkeys); WRITE_NODE_FIELD(processed_tlist); + WRITE_INT_FIELD(max_sortgroupref); WRITE_NODE_FIELD(minmax_aggs); WRITE_FLOAT_FIELD(total_table_pages, "%.0f"); WRITE_FLOAT_FIELD(tuple_fraction, "%.4f"); *************** _outRelOptInfo(StringInfo str, const Rel *** 2278,2283 **** --- 2282,2288 ---- WRITE_NODE_FIELD(cheapest_parameterized_paths); WRITE_BITMAPSET_FIELD(direct_lateral_relids); WRITE_BITMAPSET_FIELD(lateral_relids); + WRITE_NODE_FIELD(agg_info); WRITE_UINT_FIELD(relid); WRITE_OID_FIELD(reltablespace); WRITE_ENUM_FIELD(rtekind, RTEKind); *************** _outParamPathInfo(StringInfo str, const *** 2454,2459 **** --- 2459,2476 ---- } static void + _outRelAggInfo(StringInfo str, const RelAggInfo *node) + { + WRITE_NODE_TYPE("RELAGGINFO"); + + WRITE_NODE_FIELD(target); + WRITE_NODE_FIELD(input); + WRITE_NODE_FIELD(group_clauses); + WRITE_NODE_FIELD(group_exprs); + WRITE_NODE_FIELD(agg_exprs); + } + + static void _outRestrictInfo(StringInfo str, const RestrictInfo *node) { WRITE_NODE_TYPE("RESTRICTINFO"); *************** _outPlaceHolderVar(StringInfo str, const *** 2497,2502 **** --- 2514,2530 ---- } static void + _outGroupedVar(StringInfo str, const GroupedVar *node) + { + WRITE_NODE_TYPE("GROUPEDVAR"); + + WRITE_NODE_FIELD(gvexpr); + WRITE_NODE_FIELD(agg_partial); + WRITE_UINT_FIELD(sortgroupref); + WRITE_UINT_FIELD(gvid); + } + + static void _outSpecialJoinInfo(StringInfo str, const SpecialJoinInfo *node) { WRITE_NODE_TYPE("SPECIALJOININFO"); *************** _outPlaceHolderInfo(StringInfo str, cons *** 2551,2556 **** --- 2579,2597 ---- } static void + _outGroupedVarInfo(StringInfo str, const GroupedVarInfo *node) + { + WRITE_NODE_TYPE("GROUPEDVARINFO"); + + WRITE_UINT_FIELD(gvid); + WRITE_NODE_FIELD(gvexpr); + WRITE_NODE_FIELD(agg_partial); + WRITE_UINT_FIELD(sortgroupref); + WRITE_BITMAPSET_FIELD(gv_eval_at); + WRITE_INT_FIELD(gv_width); + } + + static void _outMinMaxAggInfo(StringInfo str, const MinMaxAggInfo *node) { WRITE_NODE_TYPE("MINMAXAGGINFO"); *************** outNode(StringInfo str, const void *obj) *** 4060,4071 **** --- 4101,4118 ---- case T_ParamPathInfo: _outParamPathInfo(str, obj); break; + case T_RelAggInfo: + _outRelAggInfo(str, obj); + break; case T_RestrictInfo: _outRestrictInfo(str, obj); break; case T_PlaceHolderVar: _outPlaceHolderVar(str, obj); break; + case T_GroupedVar: + _outGroupedVar(str, obj); + break; case T_SpecialJoinInfo: _outSpecialJoinInfo(str, obj); break; *************** outNode(StringInfo str, const void *obj) *** 4078,4083 **** --- 4125,4133 ---- case T_PlaceHolderInfo: _outPlaceHolderInfo(str, obj); break; + case T_GroupedVarInfo: + _outGroupedVarInfo(str, obj); + break; case T_MinMaxAggInfo: _outMinMaxAggInfo(str, obj); break; diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c new file mode 100644 index 068db35..f5dceb0 *** a/src/backend/nodes/readfuncs.c --- b/src/backend/nodes/readfuncs.c *************** _readVar(void) *** 534,539 **** --- 534,555 ---- } /* + * _readGroupedVar + */ + static GroupedVar * + _readGroupedVar(void) + { + READ_LOCALS(GroupedVar); + + READ_NODE_FIELD(gvexpr); + READ_NODE_FIELD(agg_partial); + READ_UINT_FIELD(sortgroupref); + READ_UINT_FIELD(gvid); + + READ_DONE(); + } + + /* * _readConst */ static Const * *************** _readAggref(void) *** 589,594 **** --- 605,611 ---- READ_OID_FIELD(aggcollid); READ_OID_FIELD(inputcollid); READ_OID_FIELD(aggtranstype); + READ_OID_FIELD(aggcombinefn); READ_NODE_FIELD(aggargtypes); READ_NODE_FIELD(aggdirectargs); READ_NODE_FIELD(args); *************** parseNodeString(void) *** 2483,2488 **** --- 2500,2507 ---- return_value = _readTableFunc(); else if (MATCH("VAR", 3)) return_value = _readVar(); + else if (MATCH("GROUPEDVAR", 10)) + return_value = _readGroupedVar(); else if (MATCH("CONST", 5)) return_value = _readConst(); else if (MATCH("PARAM", 5)) diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c new file mode 100644 index 0be2a73..ecff708 *** a/src/backend/optimizer/geqo/geqo_eval.c --- b/src/backend/optimizer/geqo/geqo_eval.c *************** merge_clump(PlannerInfo *root, List *clu *** 249,254 **** --- 249,255 ---- if (force || desirable_join(root, old_clump->joinrel, new_clump->joinrel)) { + JoinSearchResult *joinrels; RelOptInfo *joinrel; /* *************** merge_clump(PlannerInfo *root, List *clu *** 257,265 **** * root->join_rel_list yet, and so the paths constructed for it * will only include the ones we want. */ ! joinrel = make_join_rel(root, ! old_clump->joinrel, ! new_clump->joinrel); /* Keep searching if join order is not valid */ if (joinrel) --- 258,267 ---- * root->join_rel_list yet, and so the paths constructed for it * will only include the ones we want. */ ! joinrels = make_join_rel(root, ! old_clump->joinrel, ! new_clump->joinrel); ! joinrel = joinrels->plain; /* Keep searching if join order is not valid */ if (joinrel) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c new file mode 100644 index 1c792a0..be61d30 *** a/src/backend/optimizer/path/allpaths.c --- b/src/backend/optimizer/path/allpaths.c *************** typedef struct pushdown_safety_info *** 57,62 **** --- 57,63 ---- /* These parameters are set by GUC */ bool enable_geqo = false; /* just in case GUC doesn't set it */ + bool enable_agg_pushdown; int geqo_threshold; int min_parallel_table_scan_size; int min_parallel_index_scan_size; *************** set_rel_pathlist_hook_type set_rel_pathl *** 68,76 **** join_search_hook_type join_search_hook = NULL; ! static void set_base_rel_consider_startup(PlannerInfo *root); ! static void set_base_rel_sizes(PlannerInfo *root); ! static void set_base_rel_pathlists(PlannerInfo *root); static void set_rel_size(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, --- 69,77 ---- join_search_hook_type join_search_hook = NULL; ! static void set_base_rel_consider_startup(PlannerInfo *root, bool grouped); ! static void set_base_rel_sizes(PlannerInfo *root, bool grouped); ! static void set_base_rel_pathlists(PlannerInfo *root, bool grouped); static void set_rel_size(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, *************** static void set_namedtuplestore_pathlist *** 117,123 **** RangeTblEntry *rte); static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); ! static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist); static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery, pushdown_safety_info *safetyInfo); static bool recurse_pushdown_safe(Node *setOp, Query *topquery, --- 118,125 ---- RangeTblEntry *rte); static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); ! static JoinSearchResult *make_rel_from_joinlist(PlannerInfo *root, ! List *joinlist); static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery, pushdown_safety_info *safetyInfo); static bool recurse_pushdown_safe(Node *setOp, Query *topquery, *************** static void add_paths_to_append_rel(Plan *** 141,152 **** /* * make_one_rel * Finds all possible access paths for executing a query, returning a ! * single rel that represents the join of all base rels in the query. */ ! RelOptInfo * make_one_rel(PlannerInfo *root, List *joinlist) { ! RelOptInfo *rel; Index rti; /* --- 143,155 ---- /* * make_one_rel * Finds all possible access paths for executing a query, returning a ! * single rel that represents the join of all base rels in the query. If ! * possible, also return a join that contains partial aggregate(s). */ ! JoinSearchResult * make_one_rel(PlannerInfo *root, List *joinlist) { ! JoinSearchResult *rels; Index rti; /* *************** make_one_rel(PlannerInfo *root, List *jo *** 170,196 **** root->all_baserels = bms_add_member(root->all_baserels, brel->relid); } ! /* Mark base rels as to whether we care about fast-start plans */ ! set_base_rel_consider_startup(root); /* ! * Compute size estimates and consider_parallel flags for each base rel, ! * then generate access paths. */ ! set_base_rel_sizes(root); ! set_base_rel_pathlists(root); /* * Generate access paths for the entire join tree. */ ! rel = make_rel_from_joinlist(root, joinlist); /* * The result should join all and only the query's base rels. */ ! Assert(bms_equal(rel->relids, root->all_baserels)); ! return rel; } /* --- 173,215 ---- root->all_baserels = bms_add_member(root->all_baserels, brel->relid); } ! /* ! * Mark base rels as to whether we care about fast-start plans. XXX We ! * deliberately do not mark grouped rels --- see the comment on ! * consider_startup in build_simple_rel(). ! */ ! set_base_rel_consider_startup(root, false); /* ! * As for grouped relations, paths differ substantially by the ! * AggStrategy. Paths that use AGG_HASHED should not be parameterized ! * (because creation of hashtable would have to be repeated for different ! * parameters) but paths using AGG_SORTED can be. The latter seem to ! * justify calling the function for grouped relations too. */ ! set_base_rel_consider_startup(root, true); ! ! /* ! * Compute size estimates and consider_parallel flags for each plain and ! * each grouped base rel, then generate access paths. ! */ ! set_base_rel_sizes(root, false); ! set_base_rel_pathlists(root, false); ! ! set_base_rel_sizes(root, true); ! set_base_rel_pathlists(root, true); /* * Generate access paths for the entire join tree. */ ! rels = make_rel_from_joinlist(root, joinlist); /* * The result should join all and only the query's base rels. */ ! Assert(rels->plain && bms_equal(rels->plain->relids, root->all_baserels)); ! return rels; } /* *************** make_one_rel(PlannerInfo *root, List *jo *** 204,210 **** * be better to move it here. */ static void ! set_base_rel_consider_startup(PlannerInfo *root) { /* * Since parameterized paths can only be used on the inside of a nestloop --- 223,229 ---- * be better to move it here. */ static void ! set_base_rel_consider_startup(PlannerInfo *root, bool grouped) { /* * Since parameterized paths can only be used on the inside of a nestloop *************** set_base_rel_consider_startup(PlannerInf *** 229,237 **** if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) && bms_get_singleton_member(sjinfo->syn_righthand, &varno)) { ! RelOptInfo *rel = find_base_rel(root, varno); ! rel->consider_param_startup = true; } } } --- 248,262 ---- if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) && bms_get_singleton_member(sjinfo->syn_righthand, &varno)) { ! RelOptInfo *rel = !grouped ? find_base_rel(root, varno) : ! find_grouped_base_rel(root, varno); ! if (rel != NULL) ! rel->consider_param_startup = true; ! #ifdef USE_ASSERT_CHECKING ! else ! Assert(grouped); ! #endif /* USE_ASSERT_CHECKING */ } } } *************** set_base_rel_consider_startup(PlannerInf *** 247,262 **** * generate paths. */ static void ! set_base_rel_sizes(PlannerInfo *root) { Index rti; for (rti = 1; rti < root->simple_rel_array_size; rti++) { ! RelOptInfo *rel = root->simple_rel_array[rti]; RangeTblEntry *rte; ! /* there may be empty slots corresponding to non-baserel RTEs */ if (rel == NULL) continue; --- 272,294 ---- * generate paths. */ static void ! set_base_rel_sizes(PlannerInfo *root, bool grouped) { Index rti; + RelOptInfo **rel_array; + + rel_array = !grouped ? root->simple_rel_array : + root->simple_grouped_rel_array; for (rti = 1; rti < root->simple_rel_array_size; rti++) { ! RelOptInfo *rel = rel_array[rti]; RangeTblEntry *rte; ! /* ! * There may be empty slots corresponding to non-baserel RTEs, or to ! * baserel which cannot be grouped. ! */ if (rel == NULL) continue; *************** set_base_rel_sizes(PlannerInfo *root) *** 290,304 **** * Each useful path is attached to its relation's 'pathlist' field. */ static void ! set_base_rel_pathlists(PlannerInfo *root) { Index rti; for (rti = 1; rti < root->simple_rel_array_size; rti++) { ! RelOptInfo *rel = root->simple_rel_array[rti]; ! /* there may be empty slots corresponding to non-baserel RTEs */ if (rel == NULL) continue; --- 322,343 ---- * Each useful path is attached to its relation's 'pathlist' field. */ static void ! set_base_rel_pathlists(PlannerInfo *root, bool grouped) { Index rti; + RelOptInfo **rel_array; + + rel_array = !grouped ? root->simple_rel_array : + root->simple_grouped_rel_array; for (rti = 1; rti < root->simple_rel_array_size; rti++) { ! RelOptInfo *rel = rel_array[rti]; ! /* ! * There may be empty slots corresponding to non-baserel RTEs, or to ! * baserel which cannot be grouped. ! */ if (rel == NULL) continue; *************** static void *** 320,325 **** --- 359,372 ---- set_rel_size(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte) { + bool grouped = rel->agg_info != NULL; + + /* + * build_simple_rel() should not have created rels that do not match this + * condition. + */ + Assert(!grouped || rte->rtekind == RTE_RELATION); + if (rel->reloptkind == RELOPT_BASEREL && relation_excluded_by_constraints(root, rel, rte)) { *************** set_rel_size(PlannerInfo *root, RelOptIn *** 349,354 **** --- 396,403 ---- if (rte->relkind == RELKIND_FOREIGN_TABLE) { /* Foreign table */ + /* Not supported yet, see build_simple_rel(). */ + Assert(!grouped); set_foreign_size(root, rel, rte); } else if (rte->relkind == RELKIND_PARTITIONED_TABLE) *************** set_rel_size(PlannerInfo *root, RelOptIn *** 362,367 **** --- 411,418 ---- else if (rte->tablesample != NULL) { /* Sampled relation */ + /* Not supported yet, see build_simple_rel(). */ + Assert(!grouped); set_tablesample_rel_size(root, rel, rte); } else *************** static void *** 423,428 **** --- 474,487 ---- set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte) { + bool grouped = rel->agg_info != NULL; + + /* + * build_simple_rel() should not have created rels that do not match this + * condition. + */ + Assert(!grouped || rte->rtekind == RTE_RELATION); + if (IS_DUMMY_REL(rel)) { /* We already proved the relation empty, so nothing more to do */ *************** set_rel_pathlist(PlannerInfo *root, RelO *** 440,450 **** --- 499,513 ---- if (rte->relkind == RELKIND_FOREIGN_TABLE) { /* Foreign table */ + /* Not supported yet, see build_simple_rel(). */ + Assert(!grouped); set_foreign_pathlist(root, rel, rte); } else if (rte->tablesample != NULL) { /* Sampled relation */ + /* Not supported yet, see build_simple_rel(). */ + Assert(!grouped); set_tablesample_rel_pathlist(root, rel, rte); } else *************** static void *** 689,694 **** --- 752,759 ---- set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { Relids required_outer; + Path *seq_path; + bool grouped = rel->agg_info != NULL; /* * We don't support pushing join clauses into the quals of a seqscan, but *************** set_plain_rel_pathlist(PlannerInfo *root *** 697,714 **** */ required_outer = rel->lateral_relids; ! /* Consider sequential scan */ ! add_path(rel, create_seqscan_path(root, rel, required_outer, 0)); ! /* If appropriate, consider parallel sequential scan */ if (rel->consider_parallel && required_outer == NULL) create_plain_partial_paths(root, rel); ! /* Consider index scans */ create_index_paths(root, rel); /* Consider TID scans */ ! create_tidscan_paths(root, rel); } /* --- 762,796 ---- */ required_outer = rel->lateral_relids; ! /* Consider sequential scan, both plain and grouped. */ ! seq_path = create_seqscan_path(root, rel, required_outer, 0); ! /* ! * It's probably not good idea to repeat hashed aggregation with different ! * parameters, so check if there are no parameters. ! */ ! if (!grouped) ! add_path(rel, seq_path); ! else if (required_outer == NULL) ! { ! /* ! * Only AGG_HASHED is suitable here as it does not expect the input ! * set to be sorted. ! */ ! create_grouped_path(root, rel, seq_path, false, false, AGG_HASHED); ! } ! ! /* If appropriate, consider parallel sequential scan (plain or grouped) */ if (rel->consider_parallel && required_outer == NULL) create_plain_partial_paths(root, rel); ! /* ! * Consider index scans. ! */ create_index_paths(root, rel); /* Consider TID scans */ ! create_tidscan_paths(root, rel, grouped); } /* *************** static void *** 719,734 **** create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel) { int parallel_workers; ! parallel_workers = compute_parallel_worker(rel, rel->pages, -1, ! max_parallel_workers_per_gather); /* If any limit was set to zero, the user doesn't want a parallel scan. */ if (parallel_workers <= 0) return; /* Add an unordered partial path based on a parallel sequential scan. */ ! add_partial_path(rel, create_seqscan_path(root, rel, NULL, parallel_workers)); } /* --- 801,907 ---- create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel) { int parallel_workers; + Path *path; + bool grouped = rel->agg_info != NULL; ! parallel_workers = compute_parallel_worker(rel, rel->pages, -1, max_parallel_workers_per_gather); /* If any limit was set to zero, the user doesn't want a parallel scan. */ if (parallel_workers <= 0) return; /* Add an unordered partial path based on a parallel sequential scan. */ ! path = create_seqscan_path(root, rel, NULL, parallel_workers); ! ! if (!grouped) ! add_partial_path(rel, path); ! else ! { ! /* ! * Do partial aggregation at base relation level if the relation is ! * eligible for it. Only AGG_HASHED is suitable here as it does not ! * expect the input set to be sorted. ! */ ! create_grouped_path(root, rel, path, false, true, AGG_HASHED); ! } ! } ! ! /* ! * Apply partial aggregation to a subpath and add the AggPath to the pathlist. ! * ! * "precheck" tells whether the aggregation path should first be checked using ! * add_path_precheck() / add_partial_path_precheck(). ! * ! * If "partial" is true, the aggregation path is considered partial in terms ! * of parallel execution. ! * ! * The return value tells whether the path was added to the pathlist. ! */ ! bool ! create_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, ! bool precheck, bool partial, AggStrategy aggstrategy) ! { ! Path *agg_path; ! RelAggInfo *agg_info = rel->agg_info; ! ! Assert(agg_info != NULL); ! ! /* ! * If the AggPath should be partial, the subpath must be too, and ! * therefore the subpath is essentially parallel_safe. ! */ ! Assert(subpath->parallel_safe || !partial); ! ! /* ! * Repeated creation of hash table does not sound like a good idea. Caller ! * should avoid asking us to do so. ! */ ! Assert(subpath->param_info == NULL || aggstrategy != AGG_HASHED); ! ! /* ! * Note that "partial" in the following function names refers to 2-stage ! * aggregation, not to parallel processing. ! */ ! if (aggstrategy == AGG_HASHED) ! agg_path = (Path *) create_partial_agg_hashed_path(root, subpath, ! subpath->rows); ! else if (aggstrategy == AGG_SORTED) ! agg_path = (Path *) create_partial_agg_sorted_path(root, subpath, ! true, ! subpath->rows); ! else ! elog(ERROR, "unexpected strategy %d", aggstrategy); ! ! /* Add the grouped path to the list of grouped base paths. */ ! if (agg_path != NULL) ! { ! if (precheck) ! { ! List *pathkeys; ! ! /* AGG_HASH is not supposed to generate sorted output. */ ! pathkeys = aggstrategy == AGG_SORTED ? subpath->pathkeys : NIL; ! ! if (!partial && ! !add_path_precheck(rel, agg_path->startup_cost, ! agg_path->total_cost, pathkeys, NULL)) ! return false; ! ! if (partial && ! !add_partial_path_precheck(rel, agg_path->total_cost, ! pathkeys)) ! return false; ! } ! ! if (!partial) ! add_path(rel, (Path *) agg_path); ! else ! add_partial_path(rel, (Path *) agg_path); ! ! return true; ! } ! ! return false; } /* *************** set_append_rel_size(PlannerInfo *root, R *** 869,874 **** --- 1042,1048 ---- double *parent_attrsizes; int nattrs; ListCell *l; + bool grouped = rel->agg_info != NULL; /* Guard against stack overflow due to overly deep inheritance tree. */ check_stack_depth(); *************** set_append_rel_size(PlannerInfo *root, R *** 919,925 **** * The child rel's RelOptInfo was already created during * add_base_rels_to_query. */ ! childrel = find_base_rel(root, childRTindex); Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL); if (rel->part_scheme) --- 1093,1100 ---- * The child rel's RelOptInfo was already created during * add_base_rels_to_query. */ ! childrel = !grouped ? find_base_rel(root, childRTindex) : ! find_grouped_base_rel(root, childRTindex); Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL); if (rel->part_scheme) *************** set_append_rel_size(PlannerInfo *root, R *** 929,938 **** /* * We need attr_needed data for building targetlist of a join * relation representing join between matching partitions for ! * partitionwise join. A given attribute of a child will be ! * needed in the same highest joinrel where the corresponding ! * attribute of parent is needed. Hence it suffices to use the ! * same Relids set for parent and child. */ for (attno = rel->min_attr; attno <= rel->max_attr; attno++) { --- 1104,1113 ---- /* * We need attr_needed data for building targetlist of a join * relation representing join between matching partitions for ! * partitionwise join. A given attribute of a child will be needed ! * in the same highest joinrel where the corresponding attribute ! * of parent is needed. Hence it suffices to use the same Relids ! * set for parent and child. */ for (attno = rel->min_attr; attno <= rel->max_attr; attno++) { *************** set_append_rel_size(PlannerInfo *root, R *** 982,991 **** * PlaceHolderVars.) XXX we do not bother to update the cost or width * fields of childrel->reltarget; not clear if that would be useful. */ ! childrel->reltarget->exprs = (List *) ! adjust_appendrel_attrs(root, ! (Node *) rel->reltarget->exprs, ! 1, &appinfo); /* * We have to make child entries in the EquivalenceClass data --- 1157,1190 ---- * PlaceHolderVars.) XXX we do not bother to update the cost or width * fields of childrel->reltarget; not clear if that would be useful. */ ! if (grouped) ! { ! /* ! * Special attention is needed in the grouped case. ! * ! * build_simple_rel() didn't create empty target because it's ! * better to start with copying one from the parent rel. ! */ ! Assert(childrel->reltarget == NULL && childrel->agg_info == NULL); ! Assert(rel->reltarget != NULL && rel->agg_info != NULL); ! ! /* ! * Translate the targets and grouping expressions so they match ! * this child. ! */ ! childrel->agg_info = translate_rel_agg_info(root, rel->agg_info, ! &appinfo, 1); ! ! /* ! * The relation paths will generate input for partial aggregation. ! */ ! childrel->reltarget = childrel->agg_info->input; ! } ! else ! childrel->reltarget->exprs = (List *) ! adjust_appendrel_attrs(root, ! (Node *) rel->reltarget->exprs, ! 1, &appinfo); /* * We have to make child entries in the EquivalenceClass data *************** set_append_rel_size(PlannerInfo *root, R *** 1140,1145 **** --- 1339,1364 ---- 1, &appinfo); /* + * We have to make child entries in the EquivalenceClass data + * structures as well. This is needed either if the parent + * participates in some eclass joins (because we will want to consider + * inner-indexscan joins on the individual children) or if the parent + * has useful pathkeys (because we should try to build MergeAppend + * paths that produce those sort orderings). + */ + if (rel->has_eclass_joins || has_useful_pathkeys(root, rel)) + add_child_rel_equivalences(root, appinfo, rel, childrel); + childrel->has_eclass_joins = rel->has_eclass_joins; + + /* + * Note: we could compute appropriate attr_needed data for the child's + * variables, by transforming the parent's attr_needed through the + * translated_vars mapping. However, currently there's no need + * because attr_needed is only examined for base relations not + * otherrels. So we just leave the child's attr_needed empty. + */ + + /* * If parallelism is allowable for this query in general, see whether * it's allowable for this childrel in particular. But if we've * already decided the appendrel is not parallel-safe as a whole, *************** set_append_rel_pathlist(PlannerInfo *roo *** 1263,1268 **** --- 1482,1488 ---- int parentRTindex = rti; List *live_childrels = NIL; ListCell *l; + bool grouped = rel->agg_info != NULL; /* * Generate access paths for each member relation, and remember the *************** set_append_rel_pathlist(PlannerInfo *roo *** 1282,1288 **** /* Re-locate the child RTE and RelOptInfo */ childRTindex = appinfo->child_relid; childRTE = root->simple_rte_array[childRTindex]; ! childrel = root->simple_rel_array[childRTindex]; /* * If set_append_rel_size() decided the parent appendrel was --- 1502,1510 ---- /* Re-locate the child RTE and RelOptInfo */ childRTindex = appinfo->child_relid; childRTE = root->simple_rte_array[childRTindex]; ! childrel = !grouped ? ! find_base_rel(root, childRTindex) : ! find_grouped_base_rel(root, childRTindex); /* * If set_append_rel_size() decided the parent appendrel was *************** generate_mergeappend_paths(PlannerInfo * *** 1732,1737 **** --- 1954,1960 ---- List *partitioned_rels) { ListCell *lcp; + PathTarget *target = NULL; foreach(lcp, all_child_pathkeys) { *************** generate_mergeappend_paths(PlannerInfo * *** 1740,1762 **** List *total_subpaths = NIL; bool startup_neq_total = false; ListCell *lcr; /* Select the child paths for this ordering... */ foreach(lcr, live_childrels) { RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr); Path *cheapest_startup, *cheapest_total; /* Locate the right paths, if they are available. */ cheapest_startup = ! get_cheapest_path_for_pathkeys(childrel->pathlist, pathkeys, NULL, STARTUP_COST, false); cheapest_total = ! get_cheapest_path_for_pathkeys(childrel->pathlist, pathkeys, NULL, TOTAL_COST, --- 1963,1987 ---- List *total_subpaths = NIL; bool startup_neq_total = false; ListCell *lcr; + Path *path; /* Select the child paths for this ordering... */ foreach(lcr, live_childrels) { RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr); + List *pathlist = childrel->pathlist; Path *cheapest_startup, *cheapest_total; /* Locate the right paths, if they are available. */ cheapest_startup = ! get_cheapest_path_for_pathkeys(pathlist, pathkeys, NULL, STARTUP_COST, false); cheapest_total = ! get_cheapest_path_for_pathkeys(pathlist, pathkeys, NULL, TOTAL_COST, *************** generate_mergeappend_paths(PlannerInfo * *** 1789,1807 **** } /* ... and build the MergeAppend paths */ ! add_path(rel, (Path *) create_merge_append_path(root, ! rel, ! startup_subpaths, ! pathkeys, ! NULL, ! partitioned_rels)); if (startup_neq_total) ! add_path(rel, (Path *) create_merge_append_path(root, ! rel, ! total_subpaths, ! pathkeys, ! NULL, ! partitioned_rels)); } } --- 2014,2041 ---- } /* ... and build the MergeAppend paths */ ! path = (Path *) create_merge_append_path(root, ! rel, ! target, ! startup_subpaths, ! pathkeys, ! NULL, ! partitioned_rels); ! ! add_path(rel, path); ! if (startup_neq_total) ! { ! path = (Path *) create_merge_append_path(root, ! rel, ! target, ! total_subpaths, ! pathkeys, ! NULL, ! partitioned_rels); ! add_path(rel, path); ! } ! } } *************** generate_gather_paths(PlannerInfo *root, *** 2508,2518 **** * See comments for deconstruct_jointree() for definition of the joinlist * data structure. */ ! static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist) { int levels_needed; ! List *initial_rels; ListCell *jl; /* --- 2742,2753 ---- * See comments for deconstruct_jointree() for definition of the joinlist * data structure. */ ! static JoinSearchResult * make_rel_from_joinlist(PlannerInfo *root, List *joinlist) { int levels_needed; ! List *initial_rels, ! *initial_rels_grouped; ListCell *jl; /* *************** make_rel_from_joinlist(PlannerInfo *root *** 2531,2568 **** * sub-joinlists. */ initial_rels = NIL; foreach(jl, joinlist) { Node *jlnode = (Node *) lfirst(jl); ! RelOptInfo *thisrel; if (IsA(jlnode, RangeTblRef)) { int varno = ((RangeTblRef *) jlnode)->rtindex; thisrel = find_base_rel(root, varno); } else if (IsA(jlnode, List)) { /* Recurse to handle subproblem */ ! thisrel = make_rel_from_joinlist(root, (List *) jlnode); } else { elog(ERROR, "unrecognized joinlist node type: %d", (int) nodeTag(jlnode)); thisrel = NULL; /* keep compiler quiet */ } initial_rels = lappend(initial_rels, thisrel); } if (levels_needed == 1) { /* * Single joinlist node, so we're done. */ ! return (RelOptInfo *) linitial(initial_rels); } else { --- 2766,2817 ---- * sub-joinlists. */ initial_rels = NIL; + initial_rels_grouped = NIL; foreach(jl, joinlist) { Node *jlnode = (Node *) lfirst(jl); ! RelOptInfo *thisrel, ! *thisrel_grouped; if (IsA(jlnode, RangeTblRef)) { int varno = ((RangeTblRef *) jlnode)->rtindex; thisrel = find_base_rel(root, varno); + thisrel_grouped = find_grouped_base_rel(root, varno); } else if (IsA(jlnode, List)) { + JoinSearchResult *rels; + /* Recurse to handle subproblem */ ! rels = make_rel_from_joinlist(root, (List *) jlnode); ! thisrel = rels->plain; ! thisrel_grouped = rels->grouped; } else { elog(ERROR, "unrecognized joinlist node type: %d", (int) nodeTag(jlnode)); thisrel = NULL; /* keep compiler quiet */ + thisrel_grouped = NULL; } initial_rels = lappend(initial_rels, thisrel); + initial_rels_grouped = lappend(initial_rels_grouped, thisrel_grouped); } if (levels_needed == 1) { + JoinSearchResult *result; + /* * Single joinlist node, so we're done. */ ! result = (JoinSearchResult *) palloc(sizeof(JoinSearchResult)); ! result->plain = (RelOptInfo *) linitial(initial_rels); ! result->grouped = (RelOptInfo *) linitial(initial_rels_grouped); ! return result; } else { *************** make_rel_from_joinlist(PlannerInfo *root *** 2576,2586 **** root->initial_rels = initial_rels; if (join_search_hook) ! return (*join_search_hook) (root, levels_needed, initial_rels); else if (enable_geqo && levels_needed >= geqo_threshold) ! return geqo(root, levels_needed, initial_rels); else ! return standard_join_search(root, levels_needed, initial_rels); } } --- 2825,2849 ---- root->initial_rels = initial_rels; if (join_search_hook) ! return (*join_search_hook) (root, levels_needed, ! initial_rels, ! initial_rels_grouped); else if (enable_geqo && levels_needed >= geqo_threshold) ! { ! JoinSearchResult *result; ! ! /* ! * TODO Teach GEQO about grouped relations. Don't forget that ! * pathlist can be NIL before set_cheapest() gets called. ! */ ! result = (JoinSearchResult *) palloc0(sizeof(JoinSearchResult)); ! result->plain = geqo(root, levels_needed, initial_rels); ! return result; ! } else ! return standard_join_search(root, levels_needed, ! initial_rels, ! initial_rels_grouped); } } *************** make_rel_from_joinlist(PlannerInfo *root *** 2596,2601 **** --- 2859,2868 ---- * jointree item. These are the components to be joined together. * Note that levels_needed == list_length(initial_rels). * + * 'initial_rels_grouped' is a list where i-th position is either RelOptInfo + * representing i-th item of 'initial_rels' grouped or NULL if there's no + * such grouped relation. + * * Returns the final level of join relations, i.e., the relation that is * the result of joining all the original relations together. * At least one implementation path must be provided for this relation and *************** make_rel_from_joinlist(PlannerInfo *root *** 2613,2629 **** * than one join-order search, you'll probably need to save and restore the * original states of those data structures. See geqo_eval() for an example. */ ! RelOptInfo * ! standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) { int lev; ! RelOptInfo *rel; /* * This function cannot be invoked recursively within any one planning ! * problem, so join_rel_level[] can't be in use already. */ Assert(root->join_rel_level == NULL); /* * We employ a simple "dynamic programming" algorithm: we first find all --- 2880,2901 ---- * than one join-order search, you'll probably need to save and restore the * original states of those data structures. See geqo_eval() for an example. */ ! JoinSearchResult * ! standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels, ! List *initial_rels_grouped) { int lev; ! Size levels_size; ! List *top_list; ! JoinSearchResult *result; /* * This function cannot be invoked recursively within any one planning ! * problem, so join_rel_level[] / join_grouped_rel_level[] can't be in use ! * already. */ Assert(root->join_rel_level == NULL); + Assert(root->join_grouped_rel_level == NULL); /* * We employ a simple "dynamic programming" algorithm: we first find all *************** standard_join_search(PlannerInfo *root, *** 2636,2671 **** * set root->join_rel_level[1] to represent all the single-jointree-item * relations. */ ! root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *)); ! root->join_rel_level[1] = initial_rels; for (lev = 2; lev <= levels_needed; lev++) { ListCell *lc; /* * Determine all possible pairs of relations to be joined at this * level, and build paths for making each one from every available * pair of lower-level relations. */ join_search_one_level(root, lev); /* ! * Run generate_partitionwise_join_paths() and ! * generate_gather_paths() for each just-processed joinrel. We could ! * not do this earlier because both regular and partial paths can get ! * added to a particular joinrel at multiple times within ! * join_search_one_level. * * After that, we're done creating paths for the joinrel, so run * set_cheapest(). */ ! foreach(lc, root->join_rel_level[lev]) { ! rel = (RelOptInfo *) lfirst(lc); ! /* Create paths for partitionwise joins. */ generate_partitionwise_join_paths(root, rel); /* Create GatherPaths for any useful partial paths for rel */ --- 2908,2952 ---- * set root->join_rel_level[1] to represent all the single-jointree-item * relations. */ ! levels_size = (levels_needed + 1) * sizeof(List *); ! root->join_rel_level = (List **) palloc0(levels_size); root->join_rel_level[1] = initial_rels; + root->join_grouped_rel_level = (List **) palloc0(levels_size); + root->join_grouped_rel_level[1] = initial_rels_grouped; for (lev = 2; lev <= levels_needed; lev++) { + List *levels; ListCell *lc; /* * Determine all possible pairs of relations to be joined at this * level, and build paths for making each one from every available * pair of lower-level relations. + * + * This step includes creation of grouped relations. */ join_search_one_level(root, lev); /* ! * Run generate_partitionwise_join_paths() and generate_gather_paths() ! * for each just-processed joinrel. We could not do this earlier ! * because both regular and partial paths can get added to a ! * particular joinrel at multiple times within join_search_one_level. * * After that, we're done creating paths for the joinrel, so run * set_cheapest(). + * + * This processing makes no difference betweend plain and grouped + * rels, so process them in the same loop. */ ! levels = list_concat(list_copy(root->join_rel_level[lev]), ! root->join_grouped_rel_level[lev]); ! foreach(lc, levels) { ! RelOptInfo *rel = lfirst_node(RelOptInfo, lc); ! /* Create paths for partition-wise joins. */ generate_partitionwise_join_paths(root, rel); /* Create GatherPaths for any useful partial paths for rel */ *************** standard_join_search(PlannerInfo *root, *** 2681,2697 **** } /* ! * We should have a single rel at the final level. */ ! if (root->join_rel_level[levels_needed] == NIL) elog(ERROR, "failed to build any %d-way joins", levels_needed); ! Assert(list_length(root->join_rel_level[levels_needed]) == 1); ! rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]); root->join_rel_level = NULL; ! return rel; } /***************************************************************************** --- 2962,2989 ---- } /* ! * We should have a single plain rel at the final level. */ ! if ((top_list = root->join_rel_level[levels_needed]) == NIL) elog(ERROR, "failed to build any %d-way joins", levels_needed); ! Assert(list_length(top_list) == 1); ! result = (JoinSearchResult *) palloc0(sizeof(JoinSearchResult)); ! result->plain = linitial_node(RelOptInfo, top_list); ! ! /* ! * Grouped relation might have been created too. ! */ ! if ((top_list = root->join_grouped_rel_level[levels_needed]) != NIL) ! { ! Assert(list_length(top_list) == 1); ! result->grouped = linitial_node(RelOptInfo, top_list); ! } root->join_rel_level = NULL; + root->join_grouped_rel_level = NULL; ! return result; } /***************************************************************************** *************** create_partial_bitmap_paths(PlannerInfo *** 3311,3316 **** --- 3603,3609 ---- { int parallel_workers; double pages_fetched; + Path *bmhpath; /* Compute heap pages for bitmap heap scan */ pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0, *************** create_partial_bitmap_paths(PlannerInfo *** 3322,3329 **** if (parallel_workers <= 0) return; ! add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel, ! bitmapqual, rel->lateral_relids, 1.0, parallel_workers)); } /* --- 3615,3635 ---- if (parallel_workers <= 0) return; ! bmhpath = (Path *) create_bitmap_heap_path(root, rel, bitmapqual, ! rel->lateral_relids, 1.0, ! parallel_workers); ! ! if (rel->agg_info == NULL) ! add_partial_path(rel, bmhpath); ! else ! { ! /* ! * Only AGG_HASHED is suitable here as it does not expect the input ! * set to be sorted. ! */ ! create_grouped_path(root, rel, (Path *) bmhpath, false, true, ! AGG_HASHED); ! } } /* diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c new file mode 100644 index d8db0b2..14146bd *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *************** *** 91,96 **** --- 91,97 ---- #include "optimizer/plancat.h" #include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" + #include "optimizer/var.h" #include "parser/parsetree.h" #include "utils/lsyscache.h" #include "utils/selfuncs.h" *************** cost_bitmap_tree_node(Path *path, Cost * *** 1065,1070 **** --- 1066,1082 ---- *cost = path->total_cost; *selec = ((BitmapOrPath *) path)->bitmapselectivity; } + else if (IsA(path, AggPath)) + { + /* + * If partial aggregation was already applied, use only the input + * path. + * + * TODO Take the aggregation into account, both cost and its effect on + * selectivity (i.e. how it reduces the number of rows). + */ + cost_bitmap_tree_node(((AggPath *) path)->subpath, cost, selec); + } else { elog(ERROR, "unrecognized node type: %d", nodeTag(path)); *************** cost_group(Path *path, PlannerInfo *root *** 2287,2292 **** --- 2299,2330 ---- path->total_cost = total_cost; } + static void + estimate_join_rows(PlannerInfo *root, Path *path, RelAggInfo *agg_info) + { + bool grouped = agg_info != NULL; + + if (path->param_info) + { + double nrows; + + path->rows = path->param_info->ppi_rows; + if (grouped) + { + nrows = estimate_num_groups(root, agg_info->group_exprs, + path->rows, NULL); + path->rows = clamp_row_est(nrows); + } + } + else + { + if (!grouped) + path->rows = path->parent->rows; + else + path->rows = agg_info->rows; + } + } + /* * initial_cost_nestloop * Preliminary estimate of the cost of a nestloop join path. *************** final_cost_nestloop(PlannerInfo *root, N *** 2408,2417 **** inner_path_rows = 1; /* Mark the path with the correct row estimate */ ! if (path->path.param_info) ! path->path.rows = path->path.param_info->ppi_rows; ! else ! path->path.rows = path->path.parent->rows; /* For partial paths, scale row estimate. */ if (path->path.parallel_workers > 0) --- 2446,2452 ---- inner_path_rows = 1; /* Mark the path with the correct row estimate */ ! estimate_join_rows(root, (Path *) path, path->path.parent->agg_info); /* For partial paths, scale row estimate. */ if (path->path.parallel_workers > 0) *************** final_cost_mergejoin(PlannerInfo *root, *** 2854,2863 **** inner_path_rows = 1; /* Mark the path with the correct row estimate */ ! if (path->jpath.path.param_info) ! path->jpath.path.rows = path->jpath.path.param_info->ppi_rows; ! else ! path->jpath.path.rows = path->jpath.path.parent->rows; /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) --- 2889,2896 ---- inner_path_rows = 1; /* Mark the path with the correct row estimate */ ! estimate_join_rows(root, (Path *) path, ! path->jpath.path.parent->agg_info); /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) *************** final_cost_hashjoin(PlannerInfo *root, H *** 3277,3286 **** ListCell *hcl; /* Mark the path with the correct row estimate */ ! if (path->jpath.path.param_info) ! path->jpath.path.rows = path->jpath.path.param_info->ppi_rows; ! else ! path->jpath.path.rows = path->jpath.path.parent->rows; /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) --- 3310,3317 ---- ListCell *hcl; /* Mark the path with the correct row estimate */ ! estimate_join_rows(root, (Path *) path, ! path->jpath.path.parent->agg_info); /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) *************** cost_qual_eval_walker(Node *node, cost_q *** 3803,3810 **** * estimated execution cost given by pg_proc.procost (remember to multiply * this by cpu_operator_cost). * ! * Vars and Consts are charged zero, and so are boolean operators (AND, ! * OR, NOT). Simplistic, but a lot better than no model at all. * * Should we try to account for the possibility of short-circuit * evaluation of AND/OR? Probably *not*, because that would make the --- 3834,3842 ---- * estimated execution cost given by pg_proc.procost (remember to multiply * this by cpu_operator_cost). * ! * Vars, GroupedVars and Consts are charged zero, and so are boolean ! * operators (AND, OR, NOT). Simplistic, but a lot better than no model at ! * all. * * Should we try to account for the possibility of short-circuit * evaluation of AND/OR? Probably *not*, because that would make the *************** approx_tuple_count(PlannerInfo *root, Jo *** 4283,4293 **** --- 4315,4327 ---- * restriction clauses). * width: the estimated average output tuple width in bytes. * baserestrictcost: estimated cost of evaluating baserestrictinfo clauses. + * grouped: will partial aggregation be applied to each path? */ void set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel) { double nrows; + bool grouped = rel->agg_info != NULL; /* Should only be applied to base relations */ Assert(rel->relid > 0); *************** set_baserel_size_estimates(PlannerInfo * *** 4298,4309 **** 0, JOIN_INNER, NULL); - rel->rows = clamp_row_est(nrows); cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root); ! set_rel_width(root, rel); } /* --- 4332,4362 ---- 0, JOIN_INNER, NULL); rel->rows = clamp_row_est(nrows); + /* + * Grouping essentially changes the number of rows. + */ + if (grouped) + { + nrows = estimate_num_groups(root, + rel->agg_info->group_exprs, nrows, + NULL); + rel->agg_info->rows = clamp_row_est(nrows); + } + cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root); ! /* ! * The grouped target should have the cost and width set immediately on ! * creation, see create_rel_agg_info(). ! */ ! if (!grouped) ! set_rel_width(root, rel); ! #ifdef USE_ASSERT_CHECKING ! else ! Assert(rel->reltarget->width > 0); ! #endif } /* *************** set_pathtarget_cost_width(PlannerInfo *r *** 5285,5290 **** --- 5338,5358 ---- Assert(item_width > 0); tuple_width += item_width; } + else if (IsA(node, GroupedVar)) + { + GroupedVar *gvar = (GroupedVar *) node; + GroupedVarInfo *gvinfo; + + gvinfo = find_grouped_var_info(root, gvar); + tuple_width += gvinfo->gv_width; + + /* + * Only AggPath can evaluate GroupedVar, whether it's an aggregate + * or generic grouping expression. In the other cases the + * GroupedVar we see here only bubbled up from a lower AggPath, so + * it does not add any cost to the path that owns this target. + */ + } else { /* diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c new file mode 100644 index 70a925c..6c0a33f *** a/src/backend/optimizer/path/equivclass.c --- b/src/backend/optimizer/path/equivclass.c *************** static bool reconsider_outer_join_clause *** 65,70 **** --- 65,83 ---- static bool reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo); + typedef struct translate_expr_context + { + Var **keys; /* Dictionary keys. */ + Var **values; /* Dictionary values */ + int nitems; /* Number of dictionary items. */ + Relids *gv_eval_at_p; /* See GroupedVarInfo. */ + Index relid; /* Translate into this relid. */ + } translate_expr_context; + + static Node *translate_expression_to_rels_mutator(Node *node, + translate_expr_context *context); + static int var_dictionary_comparator(const void *a, const void *b); + /* * process_equivalence *************** is_redundant_derived_clause(RestrictInfo *** 2510,2512 **** --- 2523,2844 ---- return false; } + + /* + * translate_expression_to_rels + * If the appropriate equivalence classes exist, replace vars in + * gvi->gvexpr with vars whose varno is equal to relid. + */ + GroupedVarInfo * + translate_expression_to_rels(PlannerInfo *root, GroupedVarInfo *gvi, + Index relid) + { + List *vars; + ListCell *l1; + int i, + j; + int nkeys, + nkeys_resolved; + Var **keys, + **values, + **keys_tmp; + Var *key, + *key_prev; + translate_expr_context context; + GroupedVarInfo *result; + + /* Can't do anything w/o equivalence classes. */ + if (root->eq_classes == NIL) + return NULL; + + /* + * Before actually trying to modify the expression tree, find out if all + * vars can be translated. + */ + vars = pull_var_clause((Node *) gvi->gvexpr, PVC_RECURSE_AGGREGATES); + + /* No vars to translate? */ + if (vars == NIL) + return NULL; + + /* + * Search for individual replacement vars as well as the actual expression + * translation will be more efficient if we use a dictionary with the keys + * (i.e. the "source vars") unique and sorted. + */ + nkeys = list_length(vars); + keys = (Var **) palloc(nkeys * sizeof(Var *)); + i = 0; + foreach(l1, vars) + { + key = lfirst_node(Var, l1); + keys[i++] = key; + } + + /* + * Sort the keys by varno. varattno decides where varnos are equal. + */ + if (nkeys > 1) + pg_qsort(keys, nkeys, sizeof(Var *), var_dictionary_comparator); + + /* + * Pick unique values and get rid of the vars that need no translation. + */ + keys_tmp = (Var **) palloc(nkeys * sizeof(Var *)); + key_prev = NULL; + j = 0; + for (i = 0; i < nkeys; i++) + { + key = keys[i]; + + if ((key_prev == NULL || (key->varno != key_prev->varno && + key->varattno != key_prev->varattno)) && + key->varno != relid) + keys_tmp[j++] = key; + + key_prev = key; + } + pfree(keys); + keys = keys_tmp; + nkeys = j; + + /* + * Is there actually nothing to be translated? + */ + if (nkeys == 0) + { + pfree(keys); + return NULL; + } + + nkeys_resolved = 0; + + /* + * Find the replacement vars. + */ + values = (Var **) palloc0(nkeys * sizeof(Var *)); + foreach(l1, root->eq_classes) + { + EquivalenceClass *ec = lfirst_node(EquivalenceClass, l1); + Relids ec_var_relids; + Var **ec_vars; + int ec_nvars; + ListCell *l2; + + /* TODO Re-check if any other EC kind should be ignored. */ + if (ec->ec_has_volatile || ec->ec_below_outer_join || ec->ec_broken) + continue; + + /* Single-element EC can hardly help in translations. */ + if (list_length(ec->ec_members) == 1) + continue; + + /* + * Collect all vars of this EC and their varnos. + * + * ec->ec_relids does not help because we're only interested in a + * subset of EC members. + */ + ec_vars = (Var **) palloc(list_length(ec->ec_members) * sizeof(Var *)); + ec_nvars = 0; + ec_var_relids = NULL; + foreach(l2, ec->ec_members) + { + EquivalenceMember *em = lfirst_node(EquivalenceMember, l2); + Var *ec_var; + + if (!IsA(em->em_expr, Var)) + continue; + + ec_var = castNode(Var, em->em_expr); + ec_vars[ec_nvars++] = ec_var; + ec_var_relids = bms_add_member(ec_var_relids, ec_var->varno); + } + + /* + * At least two vars are needed so that the EC is usable for + * translation. + */ + if (ec_nvars <= 1) + { + pfree(ec_vars); + bms_free(ec_var_relids); + continue; + } + + /* + * Now check where this EC can help. + */ + for (i = 0; i < nkeys; i++) + { + Relids ec_rest; + bool relid_ok, + key_found; + Var *key = keys[i]; + Var *value = values[i]; + + /* Skip this item if it's already resolved. */ + if (value != NULL) + continue; + + /* + * Can't translate if the EC does not mention key->varno. + */ + if (!bms_is_member(key->varno, ec_var_relids)) + continue; + + /* + * Besides key, at least one EC member must belong to the relation + * we're translating our expression to. + */ + ec_rest = bms_copy(ec_var_relids); + ec_rest = bms_del_member(ec_rest, key->varno); + relid_ok = bms_is_member(relid, ec_rest); + bms_free(ec_rest); + if (!relid_ok) + continue; + + /* + * The preliminary checks passed, so try to find the exact vars. + */ + key_found = false; + for (j = 0; j < ec_nvars; j++) + { + Var *ec_var = ec_vars[j]; + + if (!key_found && key->varno == ec_var->varno && + key->varattno == ec_var->varattno) + key_found = true; + + /* + * + * Is this Var useful for our dictionary? + * + * XXX Shouldn't ec_var be copied? + */ + if (value == NULL && ec_var->varno == relid) + value = ec_var; + + if (key_found && value != NULL) + break; + } + + if (key_found && value != NULL) + { + values[i] = value; + nkeys_resolved++; + + if (nkeys_resolved == nkeys) + break; + } + } + + pfree(ec_vars); + bms_free(ec_var_relids); + + /* Don't need to check the remaining ECs? */ + if (nkeys_resolved == nkeys) + break; + } + + /* Couldn't compose usable dictionary? */ + if (nkeys_resolved < nkeys) + { + pfree(keys); + pfree(values); + return NULL; + } + + result = makeNode(GroupedVarInfo); + memcpy(result, gvi, sizeof(GroupedVarInfo)); + + /* + * translate_expression_to_rels_mutator updates gv_eval_at. + */ + result->gv_eval_at = bms_copy(result->gv_eval_at); + + /* The dictionary is ready, so perform the translation. */ + context.keys = keys; + context.values = values; + context.nitems = nkeys; + context.gv_eval_at_p = &result->gv_eval_at; + context.relid = relid; + result->gvexpr = (Expr *) + translate_expression_to_rels_mutator((Node *) gvi->gvexpr, &context); + + pfree(keys); + pfree(values); + return result; + } + + static Node * + translate_expression_to_rels_mutator(Node *node, + translate_expr_context *context) + { + if (node == NULL) + return NULL; + + if (IsA(node, Var)) + { + Var *var = castNode(Var, node); + Var **key_p; + Var *value; + int index; + + /* + * Simply return the existing variable if already belongs to the + * relation we're adjusting the expression to. + */ + if (var->varno == context->relid) + return (Node *) var; + + key_p = bsearch(&var, context->keys, context->nitems, sizeof(Var *), + var_dictionary_comparator); + + /* We shouldn't have omitted any var from the dictionary. */ + Assert(key_p != NULL); + + index = key_p - context->keys; + Assert(index >= 0 && index < context->nitems); + value = context->values[index]; + + /* All values should be present in the dictionary. */ + Assert(value != NULL); + + /* Update gv_eval_at accordingly. */ + bms_del_member(*context->gv_eval_at_p, var->varno); + *context->gv_eval_at_p = bms_add_member(*context->gv_eval_at_p, + value->varno); + + return (Node *) value; + } + + return expression_tree_mutator(node, translate_expression_to_rels_mutator, + (void *) context); + } + + static int + var_dictionary_comparator(const void *a, const void *b) + { + Var **var1_p, + **var2_p; + Var *var1, + *var2; + + var1_p = (Var **) a; + var1 = castNode(Var, *var1_p); + var2_p = (Var **) b; + var2 = castNode(Var, *var2_p); + + if (var1->varno < var2->varno) + return -1; + else if (var1->varno > var2->varno) + return 1; + + if (var1->varattno < var2->varattno) + return -1; + else if (var1->varattno > var2->varattno) + return 1; + + return 0; + } diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c new file mode 100644 index 7fc7080..1e05faf *** a/src/backend/optimizer/path/indxpath.c --- b/src/backend/optimizer/path/indxpath.c *************** *** 32,37 **** --- 32,38 ---- #include "optimizer/predtest.h" #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" + #include "optimizer/tlist.h" #include "optimizer/var.h" #include "utils/builtins.h" #include "utils/bytea.h" *************** typedef struct *** 78,84 **** int indexcol; /* index column we want to match to */ } ec_member_matches_arg; - static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, --- 79,84 ---- *************** static Const *string_to_const(const char *** 227,232 **** --- 227,234 ---- * index quals ... but for now, it doesn't seem worth troubling over. * In particular, comments below about "unparameterized" paths should be read * as meaning "unparameterized so far as the indexquals are concerned". + * + * If agg_info is passed, grouped paths are generated too. */ void create_index_paths(PlannerInfo *root, RelOptInfo *rel) *************** create_index_paths(PlannerInfo *root, Re *** 274,281 **** * non-parameterized paths. Plain paths go directly to add_path(), * bitmap paths are added to bitindexpaths to be handled below. */ ! get_index_paths(root, rel, index, &rclauseset, ! &bitindexpaths); /* * Identify the join clauses that can match the index. For the moment --- 276,282 ---- * non-parameterized paths. Plain paths go directly to add_path(), * bitmap paths are added to bitindexpaths to be handled below. */ ! get_index_paths(root, rel, index, &rclauseset, &bitindexpaths); /* * Identify the join clauses that can match the index. For the moment *************** create_index_paths(PlannerInfo *root, Re *** 307,318 **** &bitjoinpaths); } /* * Generate BitmapOrPaths for any suitable OR-clauses present in the * restriction list. Add these to bitindexpaths. */ ! indexpaths = generate_bitmap_or_paths(root, rel, ! rel->baserestrictinfo, NIL); bitindexpaths = list_concat(bitindexpaths, indexpaths); /* --- 308,328 ---- &bitjoinpaths); } + + /* + * Bitmap paths are currently not aggregated: AggPath does not accept the + * TID bitmap as input, and even if it did, it'd seem weird to aggregate + * the individual paths and then AND them together. + */ + if (rel->agg_info != NULL) + return; + /* * Generate BitmapOrPaths for any suitable OR-clauses present in the * restriction list. Add these to bitindexpaths. */ ! indexpaths = generate_bitmap_or_paths(root, rel, rel->baserestrictinfo, ! NIL); bitindexpaths = list_concat(bitindexpaths, indexpaths); /* *************** bms_equal_any(Relids relids, List *relid *** 717,723 **** return false; } - /* * get_index_paths * Given an index and a set of index clauses for it, construct IndexPaths. --- 727,732 ---- *************** get_index_paths(PlannerInfo *root, RelOp *** 748,753 **** --- 757,766 ---- * clauses only if the index AM supports them natively, and skip any such * clauses for index columns after the first (so that we produce ordered * paths if possible). + * + * These paths are good candidates for AGG_SORTED, so pass the output + * lists for this strategy. AGG_HASHED should be applied to paths with no + * pathkeys. */ indexpaths = build_index_paths(root, rel, index, clauses, *************** get_index_paths(PlannerInfo *root, RelOp *** 760,765 **** --- 773,781 ---- * If we skipped any lower-order ScalarArrayOpExprs on an index with an AM * that supports them, then try again including those clauses. This will * produce paths with more selectivity but no ordering. + * + * As for the grouping paths, only AGG_HASHED is considered due to the + * missing ordering. */ if (skip_lower_saop) { *************** get_index_paths(PlannerInfo *root, RelOp *** 801,806 **** --- 817,825 ---- * If there were ScalarArrayOpExpr clauses that the index can't handle * natively, generate bitmap scan paths relying on executor-managed * ScalarArrayOpExpr. + * + * As for grouping, only AGG_HASHED is possible here. Again, because + * there's no ordering. */ if (skip_nonnative_saop) { *************** get_index_paths(PlannerInfo *root, RelOp *** 847,859 **** * NULL, we do not ignore non-first ScalarArrayOpExpr clauses, but they will * result in considering the scan's output to be unordered. * * 'rel' is the index's heap relation * 'index' is the index for which we want to generate paths * 'clauses' is the collection of indexable clauses (RestrictInfo nodes) * 'useful_predicate' indicates whether the index has a useful predicate * 'scantype' indicates whether we need plain or bitmap scan support * 'skip_nonnative_saop' indicates whether to accept SAOP if index AM doesn't ! * 'skip_lower_saop' indicates whether to accept non-first-column SAOP */ static List * build_index_paths(PlannerInfo *root, RelOptInfo *rel, --- 866,883 ---- * NULL, we do not ignore non-first ScalarArrayOpExpr clauses, but they will * result in considering the scan's output to be unordered. * + * If 'agg_info' is passed, 'agg_sorted' and / or 'agg_hashed' must be passed + * too. In that case AGG_SORTED and / or AGG_HASHED aggregation is applied to + * the index path (as long as the index path is appropriate) and the resulting + * grouped path is stored here. + * * 'rel' is the index's heap relation * 'index' is the index for which we want to generate paths * 'clauses' is the collection of indexable clauses (RestrictInfo nodes) * 'useful_predicate' indicates whether the index has a useful predicate * 'scantype' indicates whether we need plain or bitmap scan support * 'skip_nonnative_saop' indicates whether to accept SAOP if index AM doesn't ! * 'skip_lower_saop' indicates whether to accept non-first-column SAOP. */ static List * build_index_paths(PlannerInfo *root, RelOptInfo *rel, *************** build_index_paths(PlannerInfo *root, Rel *** 878,883 **** --- 902,913 ---- bool index_is_ordered; bool index_only_scan; int indexcol; + bool grouped; + bool can_agg_sorted, + can_agg_hashed; + AggPath *agg_path; + + grouped = rel->agg_info != NULL; /* * Check that index supports the desired scan type(s) *************** build_index_paths(PlannerInfo *root, Rel *** 1031,1037 **** --- 1061,1072 ---- * in the current clauses, OR the index ordering is potentially useful for * later merging or final output ordering, OR the index has a useful * predicate, OR an index-only scan is possible. + * + * This is where grouped path start to be considered. */ + can_agg_sorted = true; + can_agg_hashed = true; + if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { *************** build_index_paths(PlannerInfo *root, Rel *** 1048,1054 **** outer_relids, loop_count, false); ! result = lappend(result, ipath); /* * If appropriate, consider parallel index scan. We don't allow --- 1083,1145 ---- outer_relids, loop_count, false); ! ! if (!grouped) ! result = lappend(result, ipath); ! else ! { ! /* ! * Try to create the grouped paths if caller is interested in ! * them. ! */ ! if (useful_pathkeys != NIL) ! { ! agg_path = create_partial_agg_sorted_path(root, ! (Path *) ipath, ! true, ! ipath->path.rows); ! ! if (agg_path != NULL) ! result = lappend(result, agg_path); ! else ! { ! /* ! * If ipath could not be used as a source for AGG_SORTED ! * partial aggregation, it probably does not have the ! * appropriate pathkeys. Avoid trying to apply AGG_SORTED ! * to the next index paths because those will have the ! * same pathkeys. ! */ ! can_agg_sorted = false; ! } ! } ! else ! can_agg_sorted = false; ! ! /* ! * Hashed aggregation should not be parameterized: the cost of ! * repeated creation of the hashtable (for different parameter ! * values) is probably not worth. ! */ ! if (outer_relids != NULL) ! { ! agg_path = create_partial_agg_hashed_path(root, ! (Path *) ipath, ! ipath->path.rows); ! ! if (agg_path != NULL) ! result = lappend(result, agg_path); ! else ! { ! /* ! * If ipath could not be used as a source for AGG_HASHED, ! * we should not expect any other path of the same index ! * to succeed. Avoid wasting the effort next time. ! */ ! can_agg_hashed = false; ! } ! } ! } /* * If appropriate, consider parallel index scan. We don't allow *************** build_index_paths(PlannerInfo *root, Rel *** 1077,1083 **** * parallel workers, just free it. */ if (ipath->path.parallel_workers > 0) ! add_partial_path(rel, (Path *) ipath); else pfree(ipath); } --- 1168,1213 ---- * parallel workers, just free it. */ if (ipath->path.parallel_workers > 0) ! { ! if (!grouped) ! add_partial_path(rel, (Path *) ipath); ! else ! { ! if (useful_pathkeys != NIL && can_agg_sorted) ! { ! /* ! * No need to check the pathkeys again. ! */ ! agg_path = create_partial_agg_sorted_path(root, ! (Path *) ipath, ! false, ! ipath->path.rows); ! ! /* ! * If create_agg_sorted_path succeeded once, it should ! * always do. ! */ ! Assert(agg_path != NULL); ! ! add_partial_path(rel, (Path *) agg_path); ! } ! ! if (can_agg_hashed && outer_relids == NULL) ! { ! agg_path = create_partial_agg_hashed_path(root, ! (Path *) ipath, ! ipath->path.rows); ! ! /* ! * If create_agg_hashed_path succeeded once, it should ! * always do. ! */ ! Assert(agg_path != NULL); ! ! add_partial_path(rel, (Path *) agg_path); ! } ! } ! } else pfree(ipath); } *************** build_index_paths(PlannerInfo *root, Rel *** 1105,1111 **** outer_relids, loop_count, false); ! result = lappend(result, ipath); /* If appropriate, consider parallel index scan */ if (index->amcanparallel && --- 1235,1266 ---- outer_relids, loop_count, false); ! ! if (!grouped) ! result = lappend(result, ipath); ! else ! { ! /* ! * As the input set ordering does not matter to AGG_HASHED, ! * only AGG_SORTED makes sense here. (The AGG_HASHED path we'd ! * create here should already exist.) ! * ! * The existing value of can_agg_sorted is not up-to-date for ! * the new pathkeys. ! */ ! can_agg_sorted = true; ! ! /* pathkeys are new, so check them. */ ! agg_path = create_partial_agg_sorted_path(root, ! (Path *) ipath, ! true, ! ipath->path.rows); ! ! if (agg_path != NULL) ! result = lappend(result, agg_path); ! else ! can_agg_sorted = false; ! } /* If appropriate, consider parallel index scan */ if (index->amcanparallel && *************** build_index_paths(PlannerInfo *root, Rel *** 1129,1135 **** * using parallel workers, just free it. */ if (ipath->path.parallel_workers > 0) ! add_partial_path(rel, (Path *) ipath); else pfree(ipath); } --- 1284,1309 ---- * using parallel workers, just free it. */ if (ipath->path.parallel_workers > 0) ! { ! if (!grouped) ! add_partial_path(rel, (Path *) ipath); ! else ! { ! if (can_agg_sorted) ! { ! /* ! * The non-partial path above should have been ! * created, so no need to check pathkeys. ! */ ! agg_path = create_partial_agg_sorted_path(root, ! (Path *) ipath, ! false, ! ipath->path.rows); ! Assert(agg_path != NULL); ! add_partial_path(rel, (Path *) agg_path); ! } ! } ! } else pfree(ipath); } *************** build_index_paths(PlannerInfo *root, Rel *** 1164,1169 **** --- 1338,1344 ---- * 'rel' is the relation for which we want to generate index paths * 'clauses' is the current list of clauses (RestrictInfo nodes) * 'other_clauses' is the list of additional upper-level clauses + * 'agg_info' indicates that grouped paths should be added to 'agg_hashed'. */ static List * build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel, *************** build_paths_for_OR(PlannerInfo *root, Re *** 1237,1243 **** match_clauses_to_index(index, other_clauses, &clauseset); /* ! * Construct paths if possible. */ indexpaths = build_index_paths(root, rel, index, &clauseset, --- 1412,1419 ---- match_clauses_to_index(index, other_clauses, &clauseset); /* ! * Construct paths if possible. Forbid partial aggregation even if the ! * relation is grouped --- it'll be applied to the bitmap heap path. */ indexpaths = build_index_paths(root, rel, index, &clauseset, diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c new file mode 100644 index 688f440..0cc6268 *** a/src/backend/optimizer/path/joinpath.c --- b/src/backend/optimizer/path/joinpath.c *************** static void try_partial_mergejoin_path(P *** 48,76 **** List *outersortkeys, List *innersortkeys, JoinType jointype, ! JoinPathExtraData *extra); static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra); static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra); static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra); static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, ! Path *inner_cheapest_total); static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra); static List *select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, --- 48,82 ---- List *outersortkeys, List *innersortkeys, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate); static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra, ! bool do_aggregate); static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra, ! bool do_aggregate); static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate); static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, ! Path *inner_cheapest_total, ! bool do_aggregate); static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, ! JoinType jointype, JoinPathExtraData *extra, ! bool do_aggregate); static List *select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, *************** static void generate_mergejoin_paths(Pla *** 87,93 **** bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, ! bool is_partial); /* --- 93,100 ---- bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, ! bool is_partial, ! bool do_aggregate); /* *************** static void generate_mergejoin_paths(Pla *** 112,117 **** --- 119,127 ---- * however. Path cost estimation code may need to recognize that it's * dealing with such a case --- the combination of nominal jointype INNER * with sjinfo->jointype == JOIN_SEMI indicates that. + * + * agg_info is passed iff partial aggregation should be applied to the join + * path. */ void add_paths_to_joinrel(PlannerInfo *root, *************** add_paths_to_joinrel(PlannerInfo *root, *** 120,126 **** RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, ! List *restrictlist) { JoinPathExtraData extra; bool mergejoin_allowed = true; --- 130,137 ---- RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, ! List *restrictlist, ! bool do_aggregate) { JoinPathExtraData extra; bool mergejoin_allowed = true; *************** add_paths_to_joinrel(PlannerInfo *root, *** 265,271 **** */ if (mergejoin_allowed) sort_inner_and_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra); /* * 2. Consider paths where the outer relation need not be explicitly --- 276,282 ---- */ if (mergejoin_allowed) sort_inner_and_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra, do_aggregate); /* * 2. Consider paths where the outer relation need not be explicitly *************** add_paths_to_joinrel(PlannerInfo *root, *** 276,282 **** */ if (mergejoin_allowed) match_unsorted_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra); #ifdef NOT_USED --- 287,293 ---- */ if (mergejoin_allowed) match_unsorted_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra, do_aggregate); #ifdef NOT_USED *************** add_paths_to_joinrel(PlannerInfo *root, *** 303,309 **** */ if (enable_hashjoin || jointype == JOIN_FULL) hash_inner_and_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra); /* * 5. If inner and outer relations are foreign tables (or joins) belonging --- 314,320 ---- */ if (enable_hashjoin || jointype == JOIN_FULL) hash_inner_and_outer(root, joinrel, outerrel, innerrel, ! jointype, &extra, do_aggregate); /* * 5. If inner and outer relations are foreign tables (or joins) belonging *************** try_nestloop_path(PlannerInfo *root, *** 364,370 **** Path *inner_path, List *pathkeys, JoinType jointype, ! JoinPathExtraData *extra) { Relids required_outer; JoinCostWorkspace workspace; --- 375,382 ---- Path *inner_path, List *pathkeys, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { Relids required_outer; JoinCostWorkspace workspace; *************** try_nestloop_path(PlannerInfo *root, *** 374,379 **** --- 386,392 ---- Relids outerrelids; Relids inner_paramrels = PATH_REQ_OUTER(inner_path); Relids outer_paramrels = PATH_REQ_OUTER(outer_path); + bool success = false; /* * Paths are parameterized by top-level parents, so run parameterization *************** try_nestloop_path(PlannerInfo *root, *** 420,429 **** initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); ! if (add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! pathkeys, required_outer)) { /* * If the inner path is parameterized, it is parameterized by the * topmost parent of the outer rel, not the outer rel itself. Fix --- 433,463 ---- initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); ! /* ! * If the join output should be (partially) aggregated, the precheck ! * includes the aggregation and is postponed to create_grouped_path(). ! */ ! if ((!do_aggregate && ! add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! pathkeys, required_outer)) || ! do_aggregate) { + Path *path; + PathTarget *target; + + /* + * If the join output is subject to partial aggregation, the path must + * have the appropriate target. + */ + if (!do_aggregate) + target = joinrel->reltarget; + else + { + Assert(joinrel->agg_info != NULL); + target = joinrel->agg_info->input; + } + /* * If the inner path is parameterized, it is parameterized by the * topmost parent of the outer rel, not the outer rel itself. Fix *************** try_nestloop_path(PlannerInfo *root, *** 445,465 **** } } ! add_path(joinrel, (Path *) ! create_nestloop_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! required_outer)); } ! else { ! /* Waste no memory when we reject a path here */ bms_free(required_outer); } } --- 479,534 ---- } } ! path = (Path *) create_nestloop_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! required_outer); ! if (!do_aggregate) ! { ! add_path(joinrel, path); ! success = true; ! } ! else ! { ! /* ! * Try both AGG_HASHED and AGG_SORTED partial aggregation. ! * ! * AGG_HASHED should not be parameterized because we don't want to ! * create the hashtable again for each set of parameters. ! */ ! if (required_outer == NULL) ! success = create_grouped_path(root, ! joinrel, ! path, ! true, ! false, ! AGG_HASHED); ! ! /* ! * Don't try AGG_SORTED if create_grouped_path() would reject it ! * anyway. ! */ ! if (pathkeys != NIL) ! success = success || ! create_grouped_path(root, ! joinrel, ! path, ! true, ! false, ! AGG_SORTED); ! } } ! ! if (!success) { ! /* Waste no memory when we reject path(s) here */ bms_free(required_outer); } } *************** try_partial_nestloop_path(PlannerInfo *r *** 476,484 **** Path *inner_path, List *pathkeys, JoinType jointype, ! JoinPathExtraData *extra) { JoinCostWorkspace workspace; /* * If the inner path is parameterized, the parameterization must be fully --- 545,556 ---- Path *inner_path, List *pathkeys, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinCostWorkspace workspace; + Path *path; + PathTarget *target; /* * If the inner path is parameterized, the parameterization must be fully *************** try_partial_nestloop_path(PlannerInfo *r *** 513,519 **** */ initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); ! if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys)) return; /* --- 585,597 ---- */ initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); ! ! /* ! * If the join output should be (partially) aggregated, the precheck ! * includes the aggregation and is postponed to create_grouped_path(). ! */ ! if (!do_aggregate && ! !add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys)) return; /* *************** try_partial_nestloop_path(PlannerInfo *r *** 532,549 **** return; } /* Might be good enough to be worth trying, so let's try it. */ ! add_partial_path(joinrel, (Path *) ! create_nestloop_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! NULL)); } /* --- 610,663 ---- return; } + /* + * If the join output is subject to partial aggregation, the path must + * have the appropriate target. + */ + if (!do_aggregate) + target = joinrel->reltarget; + else + { + Assert(joinrel->agg_info != NULL); + target = joinrel->agg_info->input; + } + /* Might be good enough to be worth trying, so let's try it. */ ! path = (Path *) create_nestloop_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! NULL); ! ! if (!do_aggregate) ! add_partial_path(joinrel, path); ! else ! { ! create_grouped_path(root, ! joinrel, ! path, ! true, ! true, ! AGG_HASHED); ! ! /* ! * Don't try AGG_SORTED if create_grouped_path() would reject it ! * anyway. ! */ ! if (pathkeys != NIL) ! create_grouped_path(root, ! joinrel, ! path, ! true, ! true, ! AGG_SORTED); ! } } /* *************** try_mergejoin_path(PlannerInfo *root, *** 562,571 **** List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, ! bool is_partial) { Relids required_outer; JoinCostWorkspace workspace; if (is_partial) { --- 676,687 ---- List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, ! bool is_partial, ! bool do_aggregate) { Relids required_outer; JoinCostWorkspace workspace; + bool success = false; if (is_partial) { *************** try_mergejoin_path(PlannerInfo *root, *** 578,584 **** outersortkeys, innersortkeys, jointype, ! extra); return; } --- 694,701 ---- outersortkeys, innersortkeys, jointype, ! extra, ! do_aggregate); return; } *************** try_mergejoin_path(PlannerInfo *root, *** 615,640 **** outersortkeys, innersortkeys, extra); ! if (add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! pathkeys, required_outer)) { ! add_path(joinrel, (Path *) ! create_mergejoin_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! required_outer, ! mergeclauses, ! outersortkeys, ! innersortkeys)); } ! else { /* Waste no memory when we reject a path here */ bms_free(required_outer); --- 732,799 ---- outersortkeys, innersortkeys, extra); ! if ((!do_aggregate && ! add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! pathkeys, required_outer)) || ! do_aggregate) { ! Path *path; ! PathTarget *target; ! ! /* ! * If the join output is subject to partial aggregation, the path must ! * have the appropriate target. ! */ ! if (!do_aggregate) ! target = joinrel->reltarget; ! else ! { ! Assert(joinrel->agg_info != NULL); ! target = joinrel->agg_info->input; ! } ! ! path = (Path *) create_mergejoin_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! required_outer, ! mergeclauses, ! outersortkeys, ! innersortkeys); ! if (!do_aggregate) ! { ! add_path(joinrel, path); ! success = true; ! } ! else ! { ! if (required_outer == NULL) ! success = create_grouped_path(root, ! joinrel, ! path, ! true, ! false, ! AGG_HASHED); ! ! if (pathkeys != NIL) ! success = success || ! create_grouped_path(root, ! joinrel, ! path, ! true, ! false, ! AGG_SORTED); ! } } ! ! if (!success) { /* Waste no memory when we reject a path here */ bms_free(required_outer); *************** try_partial_mergejoin_path(PlannerInfo * *** 656,664 **** List *outersortkeys, List *innersortkeys, JoinType jointype, ! JoinPathExtraData *extra) { JoinCostWorkspace workspace; /* * See comments in try_partial_hashjoin_path(). --- 815,826 ---- List *outersortkeys, List *innersortkeys, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinCostWorkspace workspace; + Path *path; + PathTarget *target; /* * See comments in try_partial_hashjoin_path(). *************** try_partial_mergejoin_path(PlannerInfo * *** 691,714 **** outersortkeys, innersortkeys, extra); ! if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys)) return; /* Might be good enough to be worth trying, so let's try it. */ ! add_partial_path(joinrel, (Path *) ! create_mergejoin_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! NULL, ! mergeclauses, ! outersortkeys, ! innersortkeys)); } /* --- 853,909 ---- outersortkeys, innersortkeys, extra); ! if (!do_aggregate && ! !add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys)) return; + /* + * If the join output is subject to partial aggregation, the path must + * have the appropriate target. + */ + if (!do_aggregate) + target = joinrel->reltarget; + else + { + Assert(joinrel->agg_info != NULL); + target = joinrel->agg_info->input; + } + /* Might be good enough to be worth trying, so let's try it. */ ! path = (Path *) create_mergejoin_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! extra->restrictlist, ! pathkeys, ! NULL, ! mergeclauses, ! outersortkeys, ! innersortkeys); ! ! if (!do_aggregate) ! add_partial_path(joinrel, path); ! else ! { ! create_grouped_path(root, ! joinrel, ! path, ! true, ! true, ! AGG_HASHED); ! ! if (pathkeys != NIL) ! create_grouped_path(root, ! joinrel, ! path, ! true, ! true, ! AGG_SORTED); ! } } /* *************** try_hashjoin_path(PlannerInfo *root, *** 723,732 **** Path *inner_path, List *hashclauses, JoinType jointype, ! JoinPathExtraData *extra) { Relids required_outer; JoinCostWorkspace workspace; /* * Check to see if proposed path is still parameterized, and reject if the --- 918,930 ---- Path *inner_path, List *hashclauses, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { Relids required_outer; JoinCostWorkspace workspace; + Path *path = NULL; + bool success = false; /* * Check to see if proposed path is still parameterized, and reject if the *************** try_hashjoin_path(PlannerInfo *root, *** 743,772 **** } /* * See comments in try_nestloop_path(). Also note that hashjoin paths * never have any output pathkeys, per comments in create_hashjoin_path. */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, false); ! if (add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! NIL, required_outer)) { ! add_path(joinrel, (Path *) ! create_hashjoin_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! false, /* parallel_hash */ ! extra->restrictlist, ! required_outer, ! hashclauses)); } ! else { /* Waste no memory when we reject a path here */ bms_free(required_outer); --- 941,1020 ---- } /* + * Parameterized execution of grouped path would mean repeated hashing of + * the output of the hashjoin output, so forget about AGG_HASHED if there + * are any parameters. And AGG_SORTED makes no sense because the hash join + * output is not sorted. + */ + if (required_outer && joinrel->agg_info) + return; + + /* * See comments in try_nestloop_path(). Also note that hashjoin paths * never have any output pathkeys, per comments in create_hashjoin_path. */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, false); ! /* ! * If the join output should be (partially) aggregated, the precheck ! * includes the aggregation and is postponed to create_grouped_path(). ! */ ! if ((!do_aggregate && ! add_path_precheck(joinrel, ! workspace.startup_cost, workspace.total_cost, ! NIL, required_outer)) || ! do_aggregate) { ! PathTarget *target; ! ! /* ! * If the join output is subject to partial aggregation, the path must ! * have the appropriate target. ! */ ! if (!do_aggregate) ! target = joinrel->reltarget; ! else ! { ! Assert(joinrel->agg_info != NULL); ! target = joinrel->agg_info->input; ! } ! ! path = (Path *) create_hashjoin_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! false, /* parallel_hash */ ! extra->restrictlist, ! required_outer, ! hashclauses); ! ! if (!do_aggregate) ! { ! add_path(joinrel, path); ! success = true; ! } ! else ! { ! ! /* ! * As the hashjoin path is not sorted, only try AGG_HASHED. ! */ ! if (create_grouped_path(root, ! joinrel, ! path, ! true, ! false, ! AGG_HASHED)) ! success = true; ! } } ! ! if (!success) { /* Waste no memory when we reject a path here */ bms_free(required_outer); *************** try_partial_hashjoin_path(PlannerInfo *r *** 790,798 **** List *hashclauses, JoinType jointype, JoinPathExtraData *extra, ! bool parallel_hash) { JoinCostWorkspace workspace; /* * If the inner path is parameterized, the parameterization must be fully --- 1038,1049 ---- List *hashclauses, JoinType jointype, JoinPathExtraData *extra, ! bool parallel_hash, ! bool do_aggregate) { JoinCostWorkspace workspace; + Path *path; + PathTarget *target; /* * If the inner path is parameterized, the parameterization must be fully *************** try_partial_hashjoin_path(PlannerInfo *r *** 815,836 **** */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, true); ! if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL)) return; ! /* Might be good enough to be worth trying, so let's try it. */ ! add_partial_path(joinrel, (Path *) ! create_hashjoin_path(root, ! joinrel, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! parallel_hash, ! extra->restrictlist, ! NULL, ! hashclauses)); } /* --- 1066,1118 ---- */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, true); ! ! /* ! * If the join output should be (partially) aggregated, the precheck ! * includes the aggregation and is postponed to create_grouped_path(). ! */ ! if (!do_aggregate && ! !add_partial_path_precheck(joinrel, workspace.total_cost, NIL)) return; ! /* ! * If the join output is subject to partial aggregation, the path must ! * have the appropriate target. ! */ ! if (!do_aggregate) ! target = joinrel->reltarget; ! else ! { ! Assert(joinrel->agg_info != NULL); ! target = joinrel->agg_info->input; ! } ! ! path = (Path *) create_hashjoin_path(root, ! joinrel, ! target, ! jointype, ! &workspace, ! extra, ! outer_path, ! inner_path, ! parallel_hash, ! extra->restrictlist, ! NULL, ! hashclauses); ! if (!do_aggregate) ! add_partial_path(joinrel, path); ! else ! { ! /* ! * Only AGG_HASHED is useful, see comments in try_hashjoin_path(). ! */ ! create_grouped_path(root, ! joinrel, ! path, ! true, ! true, ! AGG_HASHED); ! } } /* *************** clause_sides_match_join(RestrictInfo *ri *** 874,879 **** --- 1156,1162 ---- * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values + * 'agg_info' tells if/how to apply partial aggregation to the output. */ static void sort_inner_and_outer(PlannerInfo *root, *************** sort_inner_and_outer(PlannerInfo *root, *** 881,887 **** RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra) { JoinType save_jointype = jointype; Path *outer_path; --- 1164,1171 ---- RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinType save_jointype = jointype; Path *outer_path; *************** sort_inner_and_outer(PlannerInfo *root, *** 1043,1049 **** innerkeys, jointype, extra, ! false); /* * If we have partial outer and parallel safe inner path then try --- 1327,1334 ---- innerkeys, jointype, extra, ! false, ! do_aggregate); /* * If we have partial outer and parallel safe inner path then try *************** sort_inner_and_outer(PlannerInfo *root, *** 1059,1065 **** outerkeys, innerkeys, jointype, ! extra); } } --- 1344,1351 ---- outerkeys, innerkeys, jointype, ! extra, ! do_aggregate); } } *************** generate_mergejoin_paths(PlannerInfo *ro *** 1087,1093 **** bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, ! bool is_partial) { List *mergeclauses; List *innersortkeys; --- 1373,1380 ---- bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, ! bool is_partial, ! bool do_aggregate) { List *mergeclauses; List *innersortkeys; *************** generate_mergejoin_paths(PlannerInfo *ro *** 1148,1154 **** innersortkeys, jointype, extra, ! is_partial); /* Can't do anything else if inner path needs to be unique'd */ if (save_jointype == JOIN_UNIQUE_INNER) --- 1435,1442 ---- innersortkeys, jointype, extra, ! is_partial, ! do_aggregate); /* Can't do anything else if inner path needs to be unique'd */ if (save_jointype == JOIN_UNIQUE_INNER) *************** generate_mergejoin_paths(PlannerInfo *ro *** 1245,1251 **** NIL, jointype, extra, ! is_partial); cheapest_total_inner = innerpath; } /* Same on the basis of cheapest startup cost ... */ --- 1533,1540 ---- NIL, jointype, extra, ! is_partial, ! do_aggregate); cheapest_total_inner = innerpath; } /* Same on the basis of cheapest startup cost ... */ *************** generate_mergejoin_paths(PlannerInfo *ro *** 1289,1295 **** NIL, jointype, extra, ! is_partial); } cheapest_startup_inner = innerpath; } --- 1578,1585 ---- NIL, jointype, extra, ! is_partial, ! do_aggregate); } cheapest_startup_inner = innerpath; } *************** match_unsorted_outer(PlannerInfo *root, *** 1331,1337 **** RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra) { JoinType save_jointype = jointype; bool nestjoinOK; --- 1621,1628 ---- RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinType save_jointype = jointype; bool nestjoinOK; *************** match_unsorted_outer(PlannerInfo *root, *** 1454,1460 **** inner_cheapest_total, merge_pathkeys, jointype, ! extra); } else if (nestjoinOK) { --- 1745,1752 ---- inner_cheapest_total, merge_pathkeys, jointype, ! extra, ! do_aggregate); } else if (nestjoinOK) { *************** match_unsorted_outer(PlannerInfo *root, *** 1476,1482 **** innerpath, merge_pathkeys, jointype, ! extra); } /* Also consider materialized form of the cheapest inner path */ --- 1768,1775 ---- innerpath, merge_pathkeys, jointype, ! extra, ! do_aggregate); } /* Also consider materialized form of the cheapest inner path */ *************** match_unsorted_outer(PlannerInfo *root, *** 1487,1493 **** matpath, merge_pathkeys, jointype, ! extra); } /* Can't do anything else if outer path needs to be unique'd */ --- 1780,1787 ---- matpath, merge_pathkeys, jointype, ! extra, ! do_aggregate); } /* Can't do anything else if outer path needs to be unique'd */ *************** match_unsorted_outer(PlannerInfo *root, *** 1502,1508 **** generate_mergejoin_paths(root, joinrel, innerrel, outerpath, save_jointype, extra, useallclauses, inner_cheapest_total, merge_pathkeys, ! false); } /* --- 1796,1802 ---- generate_mergejoin_paths(root, joinrel, innerrel, outerpath, save_jointype, extra, useallclauses, inner_cheapest_total, merge_pathkeys, ! false, do_aggregate); } /* *************** match_unsorted_outer(PlannerInfo *root, *** 1523,1529 **** { if (nestjoinOK) consider_parallel_nestloop(root, joinrel, outerrel, innerrel, ! save_jointype, extra); /* * If inner_cheapest_total is NULL or non parallel-safe then find the --- 1817,1823 ---- { if (nestjoinOK) consider_parallel_nestloop(root, joinrel, outerrel, innerrel, ! save_jointype, extra, do_aggregate); /* * If inner_cheapest_total is NULL or non parallel-safe then find the *************** match_unsorted_outer(PlannerInfo *root, *** 1543,1549 **** if (inner_cheapest_total) consider_parallel_mergejoin(root, joinrel, outerrel, innerrel, save_jointype, extra, ! inner_cheapest_total); } } --- 1837,1844 ---- if (inner_cheapest_total) consider_parallel_mergejoin(root, joinrel, outerrel, innerrel, save_jointype, extra, ! inner_cheapest_total, ! do_aggregate); } } *************** consider_parallel_mergejoin(PlannerInfo *** 1566,1572 **** RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, ! Path *inner_cheapest_total) { ListCell *lc1; --- 1861,1868 ---- RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, ! Path *inner_cheapest_total, ! bool do_aggregate) { ListCell *lc1; *************** consider_parallel_mergejoin(PlannerInfo *** 1584,1590 **** generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype, extra, false, inner_cheapest_total, ! merge_pathkeys, true); } } --- 1880,1886 ---- generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype, extra, false, inner_cheapest_total, ! merge_pathkeys, true, do_aggregate); } } *************** consider_parallel_nestloop(PlannerInfo * *** 1605,1611 **** RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra) { JoinType save_jointype = jointype; ListCell *lc1; --- 1901,1908 ---- RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinType save_jointype = jointype; ListCell *lc1; *************** consider_parallel_nestloop(PlannerInfo * *** 1655,1661 **** } try_partial_nestloop_path(root, joinrel, outerpath, innerpath, ! pathkeys, jointype, extra); } } } --- 1952,1959 ---- } try_partial_nestloop_path(root, joinrel, outerpath, innerpath, ! pathkeys, jointype, extra, ! do_aggregate); } } } *************** consider_parallel_nestloop(PlannerInfo * *** 1670,1675 **** --- 1968,1974 ---- * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values + * 'agg_info' tells if/how to apply partial aggregation to the output. */ static void hash_inner_and_outer(PlannerInfo *root, *************** hash_inner_and_outer(PlannerInfo *root, *** 1677,1683 **** RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra) { JoinType save_jointype = jointype; bool isouterjoin = IS_OUTER_JOIN(jointype); --- 1976,1983 ---- RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, ! JoinPathExtraData *extra, ! bool do_aggregate) { JoinType save_jointype = jointype; bool isouterjoin = IS_OUTER_JOIN(jointype); *************** hash_inner_and_outer(PlannerInfo *root, *** 1752,1758 **** cheapest_total_inner, hashclauses, jointype, ! extra); /* no possibility of cheap startup here */ } else if (jointype == JOIN_UNIQUE_INNER) --- 2052,2059 ---- cheapest_total_inner, hashclauses, jointype, ! extra, ! do_aggregate); /* no possibility of cheap startup here */ } else if (jointype == JOIN_UNIQUE_INNER) *************** hash_inner_and_outer(PlannerInfo *root, *** 1768,1774 **** cheapest_total_inner, hashclauses, jointype, ! extra); if (cheapest_startup_outer != NULL && cheapest_startup_outer != cheapest_total_outer) try_hashjoin_path(root, --- 2069,2076 ---- cheapest_total_inner, hashclauses, jointype, ! extra, ! do_aggregate); if (cheapest_startup_outer != NULL && cheapest_startup_outer != cheapest_total_outer) try_hashjoin_path(root, *************** hash_inner_and_outer(PlannerInfo *root, *** 1777,1783 **** cheapest_total_inner, hashclauses, jointype, ! extra); } else { --- 2079,2086 ---- cheapest_total_inner, hashclauses, jointype, ! extra, ! do_aggregate); } else { *************** hash_inner_and_outer(PlannerInfo *root, *** 1798,1804 **** cheapest_total_inner, hashclauses, jointype, ! extra); foreach(lc1, outerrel->cheapest_parameterized_paths) { --- 2101,2108 ---- cheapest_total_inner, hashclauses, jointype, ! extra, ! do_aggregate); foreach(lc1, outerrel->cheapest_parameterized_paths) { *************** hash_inner_and_outer(PlannerInfo *root, *** 1832,1838 **** innerpath, hashclauses, jointype, ! extra); } } } --- 2136,2143 ---- innerpath, hashclauses, jointype, ! extra, ! do_aggregate); } } } *************** hash_inner_and_outer(PlannerInfo *root, *** 1875,1881 **** cheapest_partial_outer, cheapest_partial_inner, hashclauses, jointype, extra, ! true /* parallel_hash */ ); } /* --- 2180,2187 ---- cheapest_partial_outer, cheapest_partial_inner, hashclauses, jointype, extra, ! true /* parallel_hash */ , ! do_aggregate); } /* *************** hash_inner_and_outer(PlannerInfo *root, *** 1896,1902 **** cheapest_partial_outer, cheapest_safe_inner, hashclauses, jointype, extra, ! false /* parallel_hash */ ); } } } --- 2202,2209 ---- cheapest_partial_outer, cheapest_safe_inner, hashclauses, jointype, extra, ! false /* parallel_hash */ , ! do_aggregate); } } } diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c new file mode 100644 index 3f1c1b3..59273c4 *** a/src/backend/optimizer/path/joinrels.c --- b/src/backend/optimizer/path/joinrels.c *************** *** 17,28 **** --- 17,31 ---- #include "miscadmin.h" #include "catalog/partition.h" #include "optimizer/clauses.h" + #include "optimizer/cost.h" #include "optimizer/joininfo.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/prep.h" + #include "optimizer/tlist.h" #include "utils/lsyscache.h" #include "utils/memutils.h" + #include "utils/selfuncs.h" static void make_rels_by_clause_joins(PlannerInfo *root, *************** static void make_rels_by_clause_joins(Pl *** 31,36 **** --- 34,43 ---- static void make_rels_by_clauseless_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels); + static void set_grouped_joinrel_target(PlannerInfo *root, RelOptInfo *joinrel, + RelOptInfo *rel1, RelOptInfo *rel2, + SpecialJoinInfo *sjinfo, List *restrictlist, + RelAggInfo *agg_info); static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel); static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel); static bool is_dummy_rel(RelOptInfo *rel); *************** static bool restriction_is_constant_fals *** 38,48 **** bool only_pushed_down); static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, ! SpecialJoinInfo *sjinfo, List *restrictlist); ! static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, ! List *parent_restrictlist); static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op); --- 45,57 ---- bool only_pushed_down); static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, ! SpecialJoinInfo *sjinfo, List *restrictlist, ! bool do_aggregate); ! static void try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, ! List *parent_restrictlist, ! bool do_aggregate); static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op); *************** join_search_one_level(PlannerInfo *root, *** 69,74 **** --- 78,92 ---- Assert(joinrels[level] == NIL); + /* + * Subroutines will eventually call make_join_rel() with both input rels + * from the joinrels list, i.e. both non-grouped. In addition to joining + * these, make_join_rel() will try to combine each of these with grouped + * rel and also apply partial aggregation. All the grouped joins will be + * added to root->join_grouped_rel_level[level]. + */ + Assert(root->join_grouped_rel_level[level] == NIL); + /* Set join_cur_level so that new joinrels are added to proper list */ root->join_cur_level = level; *************** make_rels_by_clauseless_joins(PlannerInf *** 321,326 **** --- 339,392 ---- } } + /* + * Set joinrel's reltarget according to agg_info and estimate the number of + * rows. + */ + static void + set_grouped_joinrel_target(PlannerInfo *root, RelOptInfo *joinrel, + RelOptInfo *rel1, RelOptInfo *rel2, + SpecialJoinInfo *sjinfo, List *restrictlist, + RelAggInfo *agg_info) + { + Assert(agg_info != NULL); + + /* + * build_join_rel() / build_child_join_rel() does not create the target + * for grouped relation. + */ + Assert(joinrel->reltarget == NULL); + Assert(joinrel->agg_info == NULL); + + /* + * The output will actually be grouped, i.e. partially aggregated. No + * additional processing needed. + */ + joinrel->reltarget = copy_pathtarget(agg_info->target); + + /* + * The rest of agg_info will be needed at aggregation time. + */ + joinrel->agg_info = agg_info; + + /* + * Now that we have the target, compute the estimates. + */ + set_joinrel_size_estimates(root, joinrel, rel1, rel2, sjinfo, + restrictlist); + + /* + * Grouping essentially changes the number of rows. + * + * XXX We do not distinguish whether two plain rels are joined and the + * result is partially aggregated, or the partial aggregation has been + * already applied to one of the input rels. Is this worth extra effort, + * e.g. maintaining a separate RelOptInfo for each case (one difficulty + * that would introduce is construction of AppendPath)? + */ + joinrel->rows = estimate_num_groups(root, joinrel->agg_info->group_exprs, + joinrel->rows, NULL); + } /* * join_is_legal *************** join_is_legal(PlannerInfo *root, RelOptI *** 659,670 **** * (The join rel may already contain paths generated from other * pairs of rels that add up to the same set of base rels.) * ! * NB: will return NULL if attempted join is not valid. This can happen ! * when working with outer joins, or with IN or EXISTS clauses that have been ! * turned into joins. */ ! RelOptInfo * ! make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) { Relids joinrelids; SpecialJoinInfo *sjinfo; --- 725,745 ---- * (The join rel may already contain paths generated from other * pairs of rels that add up to the same set of base rels.) * ! * 'agg_info' contains the reltarget of grouped relation and everything we ! * need to perform partial aggregation. If NULL, then the join relation ! * should not be grouped. ! * ! * 'do_aggregate' tells that two non-grouped rels should be grouped and ! * partial aggregation should be applied to all their paths. ! * ! * NB: will return NULL if attempted join is not valid. This can happen when ! * working with outer joins, or with IN or EXISTS clauses that have been ! * turned into joins. NULL is also returned if caller is interested in a ! * grouped relation but there's no useful grouped input relation. */ ! static RelOptInfo * ! make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, ! RelAggInfo *agg_info, bool do_aggregate) { Relids joinrelids; SpecialJoinInfo *sjinfo; *************** make_join_rel(PlannerInfo *root, RelOptI *** 672,681 **** --- 747,760 ---- SpecialJoinInfo sjinfo_data; RelOptInfo *joinrel; List *restrictlist; + bool grouped = agg_info != NULL; /* We should never try to join two overlapping sets of rels. */ Assert(!bms_overlap(rel1->relids, rel2->relids)); + /* do_aggregate implies the output to be grouped. */ + Assert(!do_aggregate || grouped); + /* Construct Relids set that identifies the joinrel. */ joinrelids = bms_union(rel1->relids, rel2->relids); *************** make_join_rel(PlannerInfo *root, RelOptI *** 725,731 **** * goes with this particular joining. */ joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo, ! &restrictlist); /* * If we've already proven this join is empty, we needn't consider any --- 804,829 ---- * goes with this particular joining. */ joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo, ! &restrictlist, grouped); ! ! /* ! * Make sure the joinrel has reltarget initialized. Caller should supply ! * the target for group relation, so build_join_rel() should have omitted ! * its creation. ! * ! * The target can already be there if we were already called with ! * grouped=true. ! */ ! if (grouped && joinrel->reltarget == NULL) ! { ! set_grouped_joinrel_target(root, joinrel, rel1, rel2, sjinfo, ! restrictlist, agg_info); ! ! if (rel1->consider_parallel && rel2->consider_parallel && ! is_parallel_safe(root, (Node *) restrictlist) && ! is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) ! joinrel->consider_parallel = true; ! } /* * If we've already proven this join is empty, we needn't consider any *************** make_join_rel(PlannerInfo *root, RelOptI *** 739,745 **** /* Add paths to the join relation. */ populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo, ! restrictlist); bms_free(joinrelids); --- 837,843 ---- /* Add paths to the join relation. */ populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo, ! restrictlist, do_aggregate); bms_free(joinrelids); *************** make_join_rel(PlannerInfo *root, RelOptI *** 747,752 **** --- 845,988 ---- } /* + * Front-end to make_join_rel_common(). Generates plain (non-grouped) join and + * then uses all the possible strategies to generate the grouped one. + */ + JoinSearchResult * + make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) + { + Relids joinrelids; + RelAggInfo *agg_info; + RelOptInfo *rel1_grouped, + *rel2_grouped, + *joinrel; + double nrows_plain; + JoinSearchResult *result; + bool rel1_grouped_useful, + rel2_grouped_useful; + + result = (JoinSearchResult *) palloc0(sizeof(JoinSearchResult)); + + /* 1) form the plain join. */ + result->plain = make_join_rel_common(root, rel1, rel2, NULL, false); + + if (result->plain == NULL) + return result; + + nrows_plain = result->plain->rows; + + /* + * We're done if there are no grouping expressions nor aggregates. + */ + if (root->grouped_var_list == NIL) + return result; + + /* + * If the same joinrel was already formed, just with the base rels divided + * between rel1 and rel2 in a different way, we might already have the + * matching agg_info. + */ + joinrelids = bms_union(rel1->relids, rel2->relids); + joinrel = find_join_rel(root, joinrelids, true); + if (joinrel != NULL && joinrel->agg_info != NULL) + agg_info = joinrel->agg_info; + else + { + double nrows; + + /* + * agg_info must be created from scratch. + */ + agg_info = create_rel_agg_info(root, result->plain); + + /* + * Grouping essentially changes the number of rows. + */ + if (agg_info != NULL) + { + nrows = estimate_num_groups(root, + agg_info->group_exprs, + nrows_plain, + NULL); + agg_info->rows = clamp_row_est(nrows); + } + } + + /* + * Cannot we build grouped join? + */ + if (agg_info == NULL) + return result; + + /* + * 2) join two plain rels and aggregate the join paths. + */ + result->grouped = make_join_rel_common(root, rel1, rel2, agg_info, true); + + /* + * Retrieve the grouped relations. + * + * Dummy rel indicates join relation able to generate grouped paths as + * such (i.e. it has valid agg_info), but for which the path actually + * could not be created (e.g. only AGG_HASHED strategy was possible but + * work_mem was not sufficient for hash table). + */ + rel1_grouped = IS_JOIN_REL(rel1) ? + find_join_rel(root, rel1->relids, true) : + find_grouped_base_rel(root, rel1->relid); + rel1_grouped_useful = rel1_grouped != NULL && !IS_DUMMY_REL(rel1_grouped); + + rel2_grouped = IS_JOIN_REL(rel2) ? + find_join_rel(root, rel2->relids, true) : + find_grouped_base_rel(root, rel2->relid); + rel2_grouped_useful = rel2_grouped != NULL && !IS_DUMMY_REL(rel2_grouped); + + /* + * Nothing else to do? + */ + if (!rel1_grouped_useful && !rel2_grouped_useful) + return result; + + /* + * 3) combine plain and grouped relation. + * + * At maximum one input rel can be grouped. If both were grouped, then + * grouping of one side would change the occurrence of the other side's + * aggregate transient states on the input of the final aggregation. This + * can be handled by adjusting the transient states, but it's not worth + * the effort because it's hard to find a use case for this kind of join. + * + * XXX If the join of two grouped rels is implemented someday, note that + * both rels can have aggregates, so it'd be hard to join grouped rel to + * non-grouped here: 1) such a "mixed join" would require a special + * target, 2) both AGGSPLIT_FINAL_DESERIAL and AGGSPLIT_SIMPLE aggregates + * could appear in the target of the final aggregation node, originating + * from the grouped and the non-grouped input rel respectively. + */ + if (rel1_grouped_useful && rel2_grouped_useful) + return result; + + /* + * 4) join grouped relation to plain one. The same target we used for + * aggregation above should be applicable to either case here. + */ + if (rel1_grouped_useful) + joinrel = make_join_rel_common(root, rel1_grouped, rel2, agg_info, + false); + else if (rel2_grouped_useful) + joinrel = make_join_rel_common(root, rel1, rel2_grouped, agg_info, + false); + + /* + * We expect make_join_rel_common() to return the same joinrel it did in + * the 2) case. + */ + Assert(joinrel && result->grouped); + + return result; + } + + /* * populate_joinrel_with_paths * Add paths to the given joinrel for given pair of joining relations. The * SpecialJoinInfo provides details about the join and the restrictlist *************** make_join_rel(PlannerInfo *root, RelOptI *** 756,762 **** static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, ! SpecialJoinInfo *sjinfo, List *restrictlist) { /* * Consider paths using each rel as both outer and inner. Depending on --- 992,999 ---- static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, ! SpecialJoinInfo *sjinfo, List *restrictlist, ! bool do_aggregate) { /* * Consider paths using each rel as both outer and inner. Depending on *************** populate_joinrel_with_paths(PlannerInfo *** 787,796 **** } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_INNER, sjinfo, ! restrictlist); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_INNER, sjinfo, ! restrictlist); break; case JOIN_LEFT: if (is_dummy_rel(rel1) || --- 1024,1033 ---- } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_INNER, sjinfo, ! restrictlist, do_aggregate); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_INNER, sjinfo, ! restrictlist, do_aggregate); break; case JOIN_LEFT: if (is_dummy_rel(rel1) || *************** populate_joinrel_with_paths(PlannerInfo *** 804,813 **** mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_LEFT, sjinfo, ! restrictlist); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_RIGHT, sjinfo, ! restrictlist); break; case JOIN_FULL: if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) || --- 1041,1050 ---- mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_LEFT, sjinfo, ! restrictlist, do_aggregate); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_RIGHT, sjinfo, ! restrictlist, do_aggregate); break; case JOIN_FULL: if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) || *************** populate_joinrel_with_paths(PlannerInfo *** 818,827 **** } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_FULL, sjinfo, ! restrictlist); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_FULL, sjinfo, ! restrictlist); /* * If there are join quals that aren't mergeable or hashable, we --- 1055,1064 ---- } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_FULL, sjinfo, ! restrictlist, do_aggregate); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_FULL, sjinfo, ! restrictlist, do_aggregate); /* * If there are join quals that aren't mergeable or hashable, we *************** populate_joinrel_with_paths(PlannerInfo *** 854,860 **** } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_SEMI, sjinfo, ! restrictlist); } /* --- 1091,1097 ---- } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_SEMI, sjinfo, ! restrictlist, do_aggregate); } /* *************** populate_joinrel_with_paths(PlannerInfo *** 877,886 **** } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_INNER, sjinfo, ! restrictlist); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_OUTER, sjinfo, ! restrictlist); } break; case JOIN_ANTI: --- 1114,1123 ---- } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_INNER, sjinfo, ! restrictlist, do_aggregate); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_OUTER, sjinfo, ! restrictlist, do_aggregate); } break; case JOIN_ANTI: *************** populate_joinrel_with_paths(PlannerInfo *** 895,901 **** mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_ANTI, sjinfo, ! restrictlist); break; default: /* other values not expected here */ --- 1132,1138 ---- mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_ANTI, sjinfo, ! restrictlist, do_aggregate); break; default: /* other values not expected here */ *************** populate_joinrel_with_paths(PlannerInfo *** 903,910 **** break; } ! /* Apply partitionwise join technique, if possible. */ ! try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist); } --- 1140,1148 ---- break; } ! /* Apply partition-wise join technique, if possible. */ ! try_partition_wise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist, ! do_aggregate); } *************** restriction_is_constant_false(List *rest *** 1304,1315 **** * obtained by translating the respective parent join structures. */ static void ! try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, ! List *parent_restrictlist) { int nparts; int cnt_parts; /* Guard against stack overflow due to overly deep partition hierarchy. */ check_stack_depth(); --- 1542,1554 ---- * obtained by translating the respective parent join structures. */ static void ! try_partition_wise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, ! List *parent_restrictlist, bool do_aggregate) { int nparts; int cnt_parts; + bool grouped = joinrel->agg_info != NULL; /* Guard against stack overflow due to overly deep partition hierarchy. */ check_stack_depth(); *************** try_partitionwise_join(PlannerInfo *root *** 1334,1341 **** joinrel->part_scheme == rel2->part_scheme); /* ! * Since we allow partitionwise join only when the partition bounds of ! * the joining relations exactly match, the partition bounds of the join * should match those of the joining relations. */ Assert(partition_bounds_equal(joinrel->part_scheme->partnatts, --- 1573,1580 ---- joinrel->part_scheme == rel2->part_scheme); /* ! * Since we allow partitionwise join only when the partition bounds of the ! * joining relations exactly match, the partition bounds of the join * should match those of the joining relations. */ Assert(partition_bounds_equal(joinrel->part_scheme->partnatts, *************** try_partitionwise_join(PlannerInfo *root *** 1386,1392 **** (List *) adjust_appendrel_attrs(root, (Node *) parent_restrictlist, nappinfos, appinfos); - pfree(appinfos); child_joinrel = joinrel->part_rels[cnt_parts]; if (!child_joinrel) --- 1625,1630 ---- *************** try_partitionwise_join(PlannerInfo *root *** 1394,1408 **** child_joinrel = build_child_join_rel(root, child_rel1, child_rel2, joinrel, child_restrictlist, child_sjinfo, ! child_sjinfo->jointype); joinrel->part_rels[cnt_parts] = child_joinrel; } Assert(bms_equal(child_joinrel->relids, child_joinrelids)); populate_joinrel_with_paths(root, child_rel1, child_rel2, child_joinrel, child_sjinfo, ! child_restrictlist); } } --- 1632,1678 ---- child_joinrel = build_child_join_rel(root, child_rel1, child_rel2, joinrel, child_restrictlist, child_sjinfo, ! child_sjinfo->jointype, ! grouped); ! ! if (grouped) ! { ! RelAggInfo *child_agg_info; ! ! /* ! * Make sure the child_joinrel has reltarget initialized. ! * ! * Although build_child_join_rel() creates reltarget for each ! * child join from scratch as opposed to translating the ! * parent reltarget (XXX set_append_rel_size() uses the ! * translation --- is this inconsistency justified?), we just ! * translate the parent reltarget here. Per-child call of ! * create_rel_agg_info() would introduce too much duplicate ! * work because it needs the *parent* target as a source and ! * that one is identical for all the child joins ! */ ! child_agg_info = translate_rel_agg_info(root, ! joinrel->agg_info, ! appinfos, nappinfos); ! ! /* ! * Make sure the child joinrel has reltarget initialized. ! */ ! set_grouped_joinrel_target(root, child_joinrel, rel1, rel2, ! child_sjinfo, child_restrictlist, ! child_agg_info); ! } ! joinrel->part_rels[cnt_parts] = child_joinrel; } + pfree(appinfos); Assert(bms_equal(child_joinrel->relids, child_joinrelids)); populate_joinrel_with_paths(root, child_rel1, child_rel2, child_joinrel, child_sjinfo, ! child_restrictlist, ! do_aggregate); } } diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c new file mode 100644 index 3bb5b8d..bb0f814 *** a/src/backend/optimizer/path/tidpath.c --- b/src/backend/optimizer/path/tidpath.c *************** TidQualFromBaseRestrictinfo(RelOptInfo * *** 250,259 **** * Candidate paths are added to the rel's pathlist (using add_path). */ void ! create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel) { Relids required_outer; List *tidquals; /* * We don't support pushing join clauses into the quals of a tidscan, but --- 250,260 ---- * Candidate paths are added to the rel's pathlist (using add_path). */ void ! create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel, bool grouped) { Relids required_outer; List *tidquals; + Path *tidpath; /* * We don't support pushing join clauses into the quals of a tidscan, but *************** create_tidscan_paths(PlannerInfo *root, *** 263,270 **** required_outer = rel->lateral_relids; tidquals = TidQualFromBaseRestrictinfo(rel); ! if (tidquals) ! add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals, ! required_outer)); } --- 264,283 ---- required_outer = rel->lateral_relids; tidquals = TidQualFromBaseRestrictinfo(rel); + if (!tidquals) + return; ! tidpath = (Path *) create_tidscan_path(root, rel, tidquals, ! required_outer); ! ! if (!grouped) ! add_path(rel, tidpath); ! else if (required_outer == NULL) ! { ! /* ! * Only AGG_HASHED is suitable here as it does not expect the input ! * set to be sorted. ! */ ! create_grouped_path(root, rel, tidpath, false, false, AGG_HASHED); ! } } diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c new file mode 100644 index 9ae1bf3..bc405bf *** a/src/backend/optimizer/plan/createplan.c --- b/src/backend/optimizer/plan/createplan.c *************** use_physical_tlist(PlannerInfo *root, Pa *** 815,820 **** --- 815,826 ---- return false; /* + * Grouped relation's target list contains GroupedVars. + */ + if (rel->agg_info != NULL) + return false; + + /* * If a bitmap scan's tlist is empty, keep it as-is. This may allow the * executor to skip heap page fetches, and in any case, the benefit of * using a physical tlist instead would be minimal. *************** create_projection_plan(PlannerInfo *root *** 1593,1600 **** * creation, but that would add expense to creating Paths we might end up * not using.) */ ! if (is_projection_capable_path(best_path->subpath) || ! tlist_same_exprs(tlist, subplan->targetlist)) { /* Don't need a separate Result, just assign tlist to subplan */ plan = subplan; --- 1599,1607 ---- * creation, but that would add expense to creating Paths we might end up * not using.) */ ! if (!best_path->force_result && ! (is_projection_capable_path(best_path->subpath) || ! tlist_same_exprs(tlist, subplan->targetlist))) { /* Don't need a separate Result, just assign tlist to subplan */ plan = subplan; *************** find_ec_member_for_tle(EquivalenceClass *** 5827,5832 **** --- 5834,5854 ---- while (tlexpr && IsA(tlexpr, RelabelType)) tlexpr = ((RelabelType *) tlexpr)->arg; + /* + * GroupedVar can contain either non-Var grouping expression or aggregate. + * The grouping expression might be useful for sorting, however aggregates + * shouldn't currently appear among pathkeys. + */ + if (IsA(tlexpr, GroupedVar)) + { + GroupedVar *gvar = castNode(GroupedVar, tlexpr); + + if (!IsA(gvar->gvexpr, Aggref)) + tlexpr = gvar->gvexpr; + else + return NULL; + } + foreach(lc, ec->ec_members) { EquivalenceMember *em = (EquivalenceMember *) lfirst(lc); diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c new file mode 100644 index a436b53..5d66785 *** a/src/backend/optimizer/plan/initsplan.c --- b/src/backend/optimizer/plan/initsplan.c *************** *** 14,19 **** --- 14,20 ---- */ #include "postgres.h" + #include "access/sysattr.h" #include "catalog/pg_type.h" #include "catalog/pg_class.h" #include "nodes/nodeFuncs.h" *************** *** 27,32 **** --- 28,34 ---- #include "optimizer/planner.h" #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" + #include "optimizer/tlist.h" #include "optimizer/var.h" #include "parser/analyze.h" #include "rewrite/rewriteManip.h" *************** typedef struct PostponedQual *** 46,51 **** --- 48,56 ---- } PostponedQual; + static void create_aggregate_grouped_var_infos(PlannerInfo *root); + static void create_grouping_expr_grouped_var_infos(PlannerInfo *root); + static RelOptInfo *copy_simple_rel(PlannerInfo *root, RelOptInfo *rel); static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex); static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode, *************** static void check_hashjoinable(RestrictI *** 96,105 **** * jtnode. Internally, the function recurses through the jointree. * * At the end of this process, there should be one baserel RelOptInfo for ! * every non-join RTE that is used in the query. Therefore, this routine ! * is the only place that should call build_simple_rel with reloptkind ! * RELOPT_BASEREL. (Note: build_simple_rel recurses internally to build ! * "other rel" RelOptInfos for the members of any appendrels we find here.) */ void add_base_rels_to_query(PlannerInfo *root, Node *jtnode) --- 101,109 ---- * jtnode. Internally, the function recurses through the jointree. * * At the end of this process, there should be one baserel RelOptInfo for ! * every non-grouped non-join RTE that is used in the query. (Note: ! * build_simple_rel recurses internally to build "other rel" RelOptInfos for ! * the members of any appendrels we find here.) */ void add_base_rels_to_query(PlannerInfo *root, Node *jtnode) *************** add_vars_to_targetlist(PlannerInfo *root *** 241,246 **** --- 245,701 ---- } } + /* + * Add GroupedVarInfo to grouped_var_list for each aggregate as well as for + * each possible grouping expression and setup RelOptInfo for each base or + * 'other' relation that can product grouped paths. + * + * Note that targets of the 'other' relations are not set here --- + * set_append_rel_size() will create them by translating the targets of the + * base rel. + * + * root->group_pathkeys must be setup before this function is called. + */ + extern void + add_grouped_base_rels_to_query(PlannerInfo *root) + { + int i; + ListCell *lc; + + /* + * Isn't user interested in the aggregate push-down feature? + */ + if (!enable_agg_pushdown) + return; + + /* No grouping in the query? */ + if (!root->parse->groupClause) + return; + + /* + * Grouping sets require multiple different groupings but the base + * relation can only generate one. + */ + if (root->parse->groupingSets) + return; + + /* + * SRF is not allowed in the aggregate argument and we don't even want it + * in the GROUP BY clause, so forbid it in general. It needs to be + * analyzed if evaluation of a GROUP BY clause containing SRF below the + * query targetlist would be correct. Currently it does not seem to be an + * important use case. + */ + if (root->parse->hasTargetSRFs) + return; + + /* + * TODO Consider if this is a real limitation. + */ + if (root->parse->hasWindowFuncs) + return; + + /* Create GroupedVarInfo per (distinct) aggregate. */ + create_aggregate_grouped_var_infos(root); + + /* Isn't there any aggregate to be pushed down? */ + if (root->grouped_var_list == NIL) + return; + + /* Create GroupedVarInfo per grouping expression. */ + create_grouping_expr_grouped_var_infos(root); + + /* + * Are all the aggregates AGGSPLIT_SIMPLE? + */ + if (root->grouped_var_list == NIL) + return; + + /* + * Now that we know that grouping can be pushed down, search for the + * maximum sortgroupref. The base relations may need it if extra grouping + * expressions get added to them. + */ + Assert(root->max_sortgroupref == 0); + foreach(lc, root->processed_tlist) + { + TargetEntry *te = lfirst_node(TargetEntry, lc); + + if (te->ressortgroupref > root->max_sortgroupref) + root->max_sortgroupref = te->ressortgroupref; + } + + /* Process the individual base relations. */ + for (i = 1; i < root->simple_rel_array_size; i++) + { + RelOptInfo *rel = root->simple_rel_array[i]; + RangeTblEntry *rte; + RelOptInfo *rel_grouped; + RelAggInfo *agg_info; + + /* NULL should mean a join relation. */ + if (rel == NULL) + continue; + + /* + * Not all RTE kinds are supported when grouping is considered. + * + * TODO Consider relaxing some of these restrictions. + */ + rte = root->simple_rte_array[rel->relid]; + if (rte->rtekind != RTE_RELATION || + rte->relkind == RELKIND_FOREIGN_TABLE || + rte->tablesample != NULL) + return; + + /* + * Grouped "other member rels" should not be created until we know + * whether the parent can be grouped. + */ + if (rel->reloptkind != RELOPT_BASEREL) + continue; + + /* + * Retrieve the information we need for aggregation of the rel + * contents. + */ + agg_info = create_rel_agg_info(root, rel); + if (agg_info == NULL) + continue; + + /* + * Create the grouped counterpart of "rel". + */ + rel_grouped = copy_simple_rel(root, rel); + + /* + * Assign it the aggregation-specific info. + * + * The aggregation paths will get their input target from agg_info, so + * store it too. + */ + rel_grouped->reltarget = agg_info->target; + rel_grouped->agg_info = agg_info; + } + } + + /* + * Create GroupedVarInfo for each distinct aggregate. + * + * If any aggregate is not suitable, set root->grouped_var_list to NIL and + * return. + */ + static void + create_aggregate_grouped_var_infos(PlannerInfo *root) + { + List *tlist_exprs; + ListCell *lc; + + Assert(root->grouped_var_list == NIL); + + tlist_exprs = pull_var_clause((Node *) root->processed_tlist, + PVC_INCLUDE_AGGREGATES); + + /* + * Although GroupingFunc is related to root->parse->groupingSets, this + * field does not necessarily reflect its presence. + */ + foreach(lc, tlist_exprs) + { + Expr *expr = (Expr *) lfirst(lc); + + if (IsA(expr, GroupingFunc)) + return; + } + + /* + * Aggregates within the HAVING clause need to be processed in the same + * way as those in the main targetlist. + */ + if (root->parse->havingQual != NULL) + { + List *having_exprs; + + having_exprs = pull_var_clause((Node *) root->parse->havingQual, + PVC_INCLUDE_AGGREGATES); + if (having_exprs != NIL) + tlist_exprs = list_concat(tlist_exprs, having_exprs); + } + + if (tlist_exprs == NIL) + return; + + /* tlist_exprs may also contain Vars, but we only need Aggrefs. */ + foreach(lc, tlist_exprs) + { + Expr *expr = (Expr *) lfirst(lc); + Aggref *aggref; + ListCell *lc2; + GroupedVarInfo *gvi; + bool exists; + + if (IsA(expr, Var)) + continue; + + aggref = castNode(Aggref, expr); + + /* TODO Think if (some of) these can be handled. */ + if (aggref->aggvariadic || + aggref->aggdirectargs || aggref->aggorder || + aggref->aggdistinct || aggref->aggfilter) + { + /* + * Partial aggregation is not useful if at least one aggregate + * cannot be evaluated below the top-level join. + * + * XXX Is it worth freeing the GroupedVarInfos and their subtrees? + */ + root->grouped_var_list = NIL; + break; + } + + /* + * Aggregation push-down does not work w/o aggcombinefn. This field is + * not mandatory, so check if this particular aggregate can handle + * partial aggregation. + */ + if (!OidIsValid(aggref->aggcombinefn)) + { + root->grouped_var_list = NIL; + break; + } + + /* Does GroupedVarInfo for this aggregate already exist? */ + exists = false; + foreach(lc2, root->grouped_var_list) + { + gvi = lfirst_node(GroupedVarInfo, lc2); + + if (equal(expr, gvi->gvexpr)) + { + exists = true; + break; + } + } + + /* Construct a new GroupedVarInfo if does not exist yet. */ + if (!exists) + { + Relids relids; + + gvi = makeNode(GroupedVarInfo); + gvi->gvid = list_length(root->grouped_var_list); + gvi->gvexpr = (Expr *) copyObject(aggref); + gvi->agg_partial = copyObject(aggref); + mark_partial_aggref(gvi->agg_partial, AGGSPLIT_INITIAL_SERIAL); + + /* Find out where the aggregate should be evaluated. */ + relids = pull_varnos((Node *) aggref); + if (!bms_is_empty(relids)) + gvi->gv_eval_at = relids; + else + gvi->gv_eval_at = NULL; + + /* + * The transient state is what appears in the target. + */ + gvi->gv_width = + get_typavgwidth(exprType((Node *) gvi->agg_partial), + exprTypmod((Node *) gvi->agg_partial)); + + root->grouped_var_list = lappend(root->grouped_var_list, gvi); + } + } + + list_free(tlist_exprs); + } + + /* + * Create GroupedVarInfo for each expression usable as grouping key. + * + * In addition to the expressions of the query targetlist, group_pathkeys is + * also considered the source of grouping expressions. That increases the + * chance to get the relation output grouped. + */ + static void + create_grouping_expr_grouped_var_infos(PlannerInfo *root) + { + ListCell *l1, + *l2; + List *exprs = NIL; + List *sortgrouprefs = NIL; + + /* + * Make sure GroupedVarInfo exists for each expression usable as grouping + * key. + */ + foreach(l1, root->parse->groupClause) + { + SortGroupClause *sgClause; + TargetEntry *te; + Index sortgroupref; + + sgClause = lfirst_node(SortGroupClause, l1); + te = get_sortgroupclause_tle(sgClause, root->processed_tlist); + sortgroupref = te->ressortgroupref; + + if (sortgroupref == 0) + continue; + + /* + * Non-zero sortgroupref does not necessarily imply grouping + * expression: data can also be sorted by aggregate. + */ + if (IsA(te->expr, Aggref)) + continue; + + exprs = lappend(exprs, te->expr); + sortgrouprefs = lappend_int(sortgrouprefs, sortgroupref); + } + + /* + * Construct GroupedVarInfo for each expression. + */ + forboth(l1, exprs, l2, sortgrouprefs) + { + Expr *expr = (Expr *) lfirst(l1); + int sortgroupref = lfirst_int(l2); + GroupedVarInfo *gvi = makeNode(GroupedVarInfo); + + gvi->gvid = list_length(root->grouped_var_list); + gvi->gvexpr = (Expr *) copyObject(expr); + gvi->sortgroupref = sortgroupref; + + /* Find out where the expression should be evaluated. */ + gvi->gv_eval_at = pull_varnos((Node *) expr); + + /* + * As a special case, Var can be present in the non-grouped target, so + * set_rel_widths() could take care of the width computation. However + * the Var might not be propagated high enough in the join tree, so + * set_rel_width() might miss it. Handle it manually. + */ + if (IsA(expr, Var)) + { + Var *var = castNode(Var, expr); + RelOptInfo *rel = root->simple_rel_array[var->varno]; + Oid reloid = rel->relid; + + if (reloid != InvalidOid && var->varattno > 0) + { + int32 width = get_attavgwidth(reloid, var->varattno); + + if (width > 0) + { + gvi->gv_width += width; + continue; + } + } + } + + /* + * In general we should not expect any statistics to exist for an + * expression just because it's a grouping expression. So use the type + * information to get the width estimate. + */ + gvi->gv_width = get_typavgwidth(exprType((Node *) gvi->gvexpr), + exprTypmod((Node *) gvi->gvexpr)); + + root->grouped_var_list = lappend(root->grouped_var_list, gvi); + } + } + + /* + * Take a flat copy of already initialized RelOptInfo and process child rels + * recursively. + * + * Flat copy ensures that we do not miss any information that the non-grouped + * rel already contains. XXX Do we need to copy any Node field? + */ + static RelOptInfo * + copy_simple_rel(PlannerInfo *root, RelOptInfo *rel) + { + Index relid = rel->relid; + RangeTblEntry *rte; + ListCell *l; + List *indexlist = NIL; + RelOptInfo *result; + + result = makeNode(RelOptInfo); + memcpy(result, rel, sizeof(RelOptInfo)); + root->simple_grouped_rel_array[relid] = result; + + /* + * The target for grouped paths will be initialized later. + */ + result->reltarget = NULL; + + /* + * Make sure that index paths have access to the parent rel's agg_info, + * which is used to indicate that the rel should produce grouped paths. + */ + foreach(l, result->indexlist) + { + IndexOptInfo *src, + *dst; + + src = lfirst_node(IndexOptInfo, l); + dst = makeNode(IndexOptInfo); + memcpy(dst, src, sizeof(IndexOptInfo)); + + dst->rel = result; + indexlist = lappend(indexlist, dst); + } + result->indexlist = indexlist; + + /* + * This is very similar to child rel processing in build_simple_rel(). + */ + rte = root->simple_rte_array[relid]; + if (rte->inh) + { + int nparts = rel->nparts; + int cnt_parts = 0; + + if (nparts > 0) + result->part_rels = (RelOptInfo **) + palloc(sizeof(RelOptInfo *) * nparts); + + foreach(l, root->append_rel_list) + { + AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l); + RelOptInfo *childrel; + + /* append_rel_list contains all append rels; ignore others */ + if (appinfo->parent_relid != relid) + continue; + + /* + * The non-grouped child rel must already exist. + */ + childrel = root->simple_rel_array[appinfo->child_relid]; + Assert(childrel != NULL); + + /* + * Create the copy. + */ + childrel = copy_simple_rel(root, childrel); + + /* Nothing more to do for an unpartitioned table. */ + if (!rel->part_scheme) + continue; + + Assert(cnt_parts < nparts); + result->part_rels[cnt_parts] = childrel; + cnt_parts++; + } + + /* We should have seen all the child partitions. */ + Assert(cnt_parts == nparts); + } + + return result; + } /***************************************************************************** * diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c new file mode 100644 index 95cbffb..7a25f22 *** a/src/backend/optimizer/plan/planagg.c --- b/src/backend/optimizer/plan/planagg.c *************** build_minmax_path(PlannerInfo *root, Min *** 441,447 **** subroot->tuple_fraction = 1.0; subroot->limit_tuples = 1.0; ! final_rel = query_planner(subroot, tlist, minmax_qp_callback, NULL); /* * Since we didn't go through subquery_planner() to handle the subquery, --- 441,447 ---- subroot->tuple_fraction = 1.0; subroot->limit_tuples = 1.0; ! final_rel = query_planner(subroot, tlist, minmax_qp_callback, NULL, NULL); /* * Since we didn't go through subquery_planner() to handle the subquery, diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c new file mode 100644 index 7a34abc..ba16454 *** a/src/backend/optimizer/plan/planmain.c --- b/src/backend/optimizer/plan/planmain.c *************** *** 43,48 **** --- 43,50 ---- * (this is NOT necessarily root->parse->targetList!) * qp_callback is a function to compute query_pathkeys once it's safe to do so * qp_extra is optional extra data to pass to qp_callback + * *partially_grouped receives relation that contains partial aggregate + * anywhere in the join tree. * * Note: the PlannerInfo node also includes a query_pathkeys field, which * tells query_planner the sort order that is desired in the final output *************** *** 52,62 **** */ RelOptInfo * query_planner(PlannerInfo *root, List *tlist, ! query_pathkeys_callback qp_callback, void *qp_extra) { Query *parse = root->parse; List *joinlist; ! RelOptInfo *final_rel; Index rti; double total_pages; --- 54,66 ---- */ RelOptInfo * query_planner(PlannerInfo *root, List *tlist, ! query_pathkeys_callback qp_callback, void *qp_extra, ! RelOptInfo **partially_grouped) { Query *parse = root->parse; List *joinlist; ! JoinSearchResult *final_rels; ! RelOptInfo *plain_rel; Index rti; double total_pages; *************** query_planner(PlannerInfo *root, List *t *** 66,73 **** */ if (parse->jointree->fromlist == NIL) { /* We need a dummy joinrel to describe the empty set of baserels */ ! final_rel = build_empty_join_rel(root); /* * If query allows parallelism in general, check whether the quals are --- 70,82 ---- */ if (parse->jointree->fromlist == NIL) { + JoinSearchResult *final_rels; + RelOptInfo *final_rel; + + final_rels = (JoinSearchResult *) palloc0(sizeof(JoinSearchResult)); + /* We need a dummy joinrel to describe the empty set of baserels */ ! final_rels->plain = final_rel = build_empty_join_rel(root); /* * If query allows parallelism in general, check whether the quals are *************** query_planner(PlannerInfo *root, List *t *** 106,111 **** --- 115,122 ---- */ root->join_rel_list = NIL; root->join_rel_hash = NULL; + root->join_grouped_rel_list = NIL; + root->join_grouped_rel_hash = NULL; root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; *************** query_planner(PlannerInfo *root, List *t *** 114,119 **** --- 125,131 ---- root->full_join_clauses = NIL; root->join_info_list = NIL; root->placeholder_list = NIL; + root->grouped_var_list = NIL; root->fkey_list = NIL; root->initial_rels = NIL; *************** query_planner(PlannerInfo *root, List *t *** 226,231 **** --- 238,253 ---- extract_restriction_or_clauses(root); /* + * If the query result can be grouped, check if any grouping can be + * performed below the top-level join. If so, setup root->grouped_var_list + * and create RelOptInfo for base relations capable to do the grouping. + * + * The base relations should be fully initialized now, so that we have + * enough info to decide whether grouping is possible. + */ + add_grouped_base_rels_to_query(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. *************** query_planner(PlannerInfo *root, List *t *** 256,267 **** /* * Ready to do the primary planning. */ ! final_rel = make_one_rel(root, joinlist); /* Check that we got at least one usable path */ ! if (!final_rel || !final_rel->cheapest_total_path || ! final_rel->cheapest_total_path->param_info != NULL) elog(ERROR, "failed to construct the join relation"); ! return final_rel; } --- 278,292 ---- /* * Ready to do the primary planning. */ ! final_rels = make_one_rel(root, joinlist); ! plain_rel = final_rels->plain; ! if (partially_grouped != NULL) ! *partially_grouped = final_rels->grouped; /* Check that we got at least one usable path */ ! if (!plain_rel || !plain_rel->cheapest_total_path || ! plain_rel->cheapest_total_path->param_info != NULL) elog(ERROR, "failed to construct the join relation"); ! return plain_rel; } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c new file mode 100644 index de1257d..f1a21c0 *** a/src/backend/optimizer/plan/planner.c --- b/src/backend/optimizer/plan/planner.c *************** static void standard_qp_callback(Planner *** 131,141 **** static double get_number_of_groups(PlannerInfo *root, double path_rows, grouping_sets_data *gd); - static Size estimate_hashagg_tablesize(Path *path, - const AggClauseCosts *agg_costs, - double dNumGroups); static RelOptInfo *create_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, PathTarget *target, const AggClauseCosts *agg_costs, grouping_sets_data *gd); --- 131,139 ---- static double get_number_of_groups(PlannerInfo *root, double path_rows, grouping_sets_data *gd); static RelOptInfo *create_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, + RelOptInfo *partially_grouped_input_rel, PathTarget *target, const AggClauseCosts *agg_costs, grouping_sets_data *gd); *************** static void add_paths_to_partial_groupin *** 200,205 **** --- 198,205 ---- grouping_sets_data *gd, bool can_sort, bool can_hash); + static void gather_partial_grouping_rel_paths(PlannerInfo *root, + RelOptInfo *partially_grouped_rel); static bool can_parallel_agg(PlannerInfo *root, RelOptInfo *input_rel, RelOptInfo *grouped_rel, const AggClauseCosts *agg_costs); *************** grouping_planner(PlannerInfo *root, bool *** 1688,1693 **** --- 1688,1694 ---- List *activeWindows = NIL; grouping_sets_data *gset_data = NULL; standard_qp_extra qp_extra; + RelOptInfo *partially_grouped = NULL; /* A recursive query should always have setOperations */ Assert(!root->hasRecursion); *************** grouping_planner(PlannerInfo *root, bool *** 1795,1801 **** * of the query's sort clause, distinct clause, etc. */ current_rel = query_planner(root, tlist, ! standard_qp_callback, &qp_extra); /* * Convert the query's result tlist into PathTarget format. --- 1796,1803 ---- * of the query's sort clause, distinct clause, etc. */ current_rel = query_planner(root, tlist, ! standard_qp_callback, &qp_extra, ! &partially_grouped); /* * Convert the query's result tlist into PathTarget format. *************** grouping_planner(PlannerInfo *root, bool *** 1983,1988 **** --- 1985,1991 ---- { current_rel = create_grouping_paths(root, current_rel, + partially_grouped, grouping_target, &agg_costs, gset_data); *************** get_number_of_groups(PlannerInfo *root, *** 3561,3600 **** } /* - * estimate_hashagg_tablesize - * estimate the number of bytes that a hash aggregate hashtable will - * require based on the agg_costs, path width and dNumGroups. - * - * XXX this may be over-estimating the size now that hashagg knows to omit - * unneeded columns from the hashtable. Also for mixed-mode grouping sets, - * grouping columns not in the hashed set are counted here even though hashagg - * won't store them. Is this a problem? - */ - static Size - estimate_hashagg_tablesize(Path *path, const AggClauseCosts *agg_costs, - double dNumGroups) - { - Size hashentrysize; - - /* Estimate per-hash-entry space at tuple width... */ - hashentrysize = MAXALIGN(path->pathtarget->width) + - MAXALIGN(SizeofMinimalTupleHeader); - - /* plus space for pass-by-ref transition values... */ - hashentrysize += agg_costs->transitionSpace; - /* plus the per-hash-entry overhead */ - hashentrysize += hash_agg_entry_size(agg_costs->numAggs); - - /* - * Note that this disregards the effect of fill-factor and growth policy - * of the hash-table. That's probably ok, given default the default - * fill-factor is relatively high. It'd be hard to meaningfully factor in - * "double-in-size" growth policies here. - */ - return hashentrysize * dNumGroups; - } - - /* * create_grouping_paths * * Build a new upperrel containing Paths for grouping and/or aggregation. --- 3564,3569 ---- *************** estimate_hashagg_tablesize(Path *path, c *** 3605,3610 **** --- 3574,3580 ---- * is, they need a Gather and then a FinalizeAggregate. * * input_rel: contains the source-data Paths + * partially_grouped_input_rel: contains Paths with aggregation pushed down. * target: the pathtarget for the result Paths to compute * agg_costs: cost info about all aggregates in query (in AGGSPLIT_SIMPLE mode) * rollup_lists: list of grouping sets, or NIL if not doing grouping sets *************** estimate_hashagg_tablesize(Path *path, c *** 3622,3627 **** --- 3592,3598 ---- static RelOptInfo * create_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, + RelOptInfo *partially_grouped_input_rel, PathTarget *target, const AggClauseCosts *agg_costs, grouping_sets_data *gd) *************** create_grouping_paths(PlannerInfo *root, *** 3824,3837 **** get_agg_clause_costs(root, (Node *) partial_grouping_target->exprs, AGGSPLIT_INITIAL_SERIAL, &agg_partial_costs); - - /* final phase */ - get_agg_clause_costs(root, (Node *) target->exprs, - AGGSPLIT_FINAL_DESERIAL, - &agg_final_costs); - get_agg_clause_costs(root, parse->havingQual, - AGGSPLIT_FINAL_DESERIAL, - &agg_final_costs); } add_paths_to_partial_grouping_rel(root, input_rel, --- 3795,3800 ---- *************** create_grouping_paths(PlannerInfo *root, *** 3840,3845 **** --- 3803,3862 ---- gd, can_sort, can_hash); } + /* + * Paths generated due to aggregation push-down are passed in a separate + * relation. Unlike "partially grouped_rel", reltarget of which contains + * Aggrefs, this relation's reltarget contains GroupedVars. + */ + if (partially_grouped_input_rel) + { + ListCell *lc; + + Assert(enable_agg_pushdown); + + /* + * Aggregation push-down could have produced partial paths as well. + * These are already aggregated, so only apply Gather / GatherMerge to + * them. + */ + gather_partial_grouping_rel_paths(root, partially_grouped_input_rel); + + /* + * If non-partial paths were generated above, and / or the aggregate + * push-down resulted in non-partial paths, just add them all to + * partially_grouped_rel for common processing. + * + * The only difference is that the paths we add here have GroupedVars + * in their pathtarget, while ones already contained in the pathlist + * of partially_grouped_rel (i.e. the paths resulting from parallel + * processing) have Aggrefs. This difference will be handled later by + * set_upper_references(). + */ + foreach(lc, partially_grouped_input_rel->pathlist) + { + Path *path = (Path *) lfirst(lc); + + add_path(partially_grouped_rel, path); + } + } + + /* + * Prepare for the final aggregation if it's expected to take place. + */ + if (partially_grouped_rel->pathlist) + { + /* Choose the best path(s) */ + set_cheapest(partially_grouped_rel); + + /* final phase */ + get_agg_clause_costs(root, (Node *) target->exprs, + AGGSPLIT_FINAL_DESERIAL, + &agg_final_costs); + get_agg_clause_costs(root, parse->havingQual, + AGGSPLIT_FINAL_DESERIAL, + &agg_final_costs); + } + /* Build final grouping paths */ add_paths_to_grouping_rel(root, input_rel, grouped_rel, target, partially_grouped_rel, agg_costs, *************** add_paths_to_partial_grouping_rel(Planne *** 6334,6339 **** --- 6351,6375 ---- * Try adding Gather or Gather Merge to partial paths to produce * non-partial paths. */ + gather_partial_grouping_rel_paths(root, partially_grouped_rel); + } + + /* + * Apply Gather or GatherMerge to partial paths of partially_grouped_rel. The + * input paths should already be partially aggregated. + */ + static void + gather_partial_grouping_rel_paths(PlannerInfo *root, + RelOptInfo *partially_grouped_rel) + { + Path *cheapest_partial_path; + + /* If there are no partial paths, there's nothing to do here. */ + if (partially_grouped_rel->partial_pathlist == NIL) + return; + + cheapest_partial_path = linitial(partially_grouped_rel->partial_pathlist); + generate_gather_paths(root, partially_grouped_rel, true); /* Get cheapest partial path from partially_grouped_rel */ diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c new file mode 100644 index 4617d12..f385792 *** a/src/backend/optimizer/plan/setrefs.c --- b/src/backend/optimizer/plan/setrefs.c *************** typedef struct *** 40,45 **** --- 40,46 ---- List *tlist; /* underlying target list */ int num_vars; /* number of plain Var tlist entries */ bool has_ph_vars; /* are there PlaceHolderVar entries? */ + bool has_grp_vars; /* are there GroupedVar entries? */ bool has_non_vars; /* are there other entries? */ bool has_conv_whole_rows; /* are there ConvertRowtypeExpr * entries encapsulating a whole-row *************** set_upper_references(PlannerInfo *root, *** 1739,1747 **** --- 1740,1802 ---- indexed_tlist *subplan_itlist; List *output_targetlist; ListCell *l; + List *sub_tlist_save = NIL; + + if (root->grouped_var_list != NIL) + { + if (IsA(plan, Agg)) + { + Agg *agg = (Agg *) plan; + + if (agg->aggsplit == AGGSPLIT_FINAL_DESERIAL) + { + /* + * convert_combining_aggrefs could have replaced some vars + * with Aggref expressions representing the partial + * aggregation. We need to restore the same Aggrefs in the + * subplan targetlist, but this would break the subplan if + * it's something else than the partial aggregation (i.e. the + * partial aggregation takes place lower in the plan tree). So + * we'll eventually need to restore the current + * subplan->targetlist. + */ + if (!IsA(subplan, Agg)) + sub_tlist_save = subplan->targetlist; + #ifdef USE_ASSERT_CHECKING + else + Assert(((Agg *) subplan)->aggsplit == AGGSPLIT_INITIAL_SERIAL); + #endif /* USE_ASSERT_CHECKING */ + + /* + * Restore the aggregate expressions that we might have + * removed when planning for aggregation at base relation + * level. + */ + subplan->targetlist = + replace_grouped_vars_with_aggrefs(root, subplan->targetlist); + } + else if (agg->aggsplit == AGGSPLIT_INITIAL_SERIAL) + { + /* + * Partial aggregation node can have GroupedVar's on the input + * if those represent generic (non-Var) grouping expressions. + * Unlike above, the restored expressions should stay there. + */ + subplan->targetlist = + replace_grouped_vars_with_aggrefs(root, subplan->targetlist); + } + } + } subplan_itlist = build_tlist_index(subplan->targetlist); + /* + * The replacement of GroupVars by Aggrefs was only needed for the index + * build. + */ + if (sub_tlist_save != NIL) + subplan->targetlist = sub_tlist_save; + output_targetlist = NIL; foreach(l, plan->targetlist) { *************** build_tlist_index(List *tlist) *** 1996,2001 **** --- 2051,2057 ---- itlist->tlist = tlist; itlist->has_ph_vars = false; + itlist->has_grp_vars = false; itlist->has_non_vars = false; itlist->has_conv_whole_rows = false; *************** build_tlist_index(List *tlist) *** 2016,2021 **** --- 2072,2079 ---- } else if (tle->expr && IsA(tle->expr, PlaceHolderVar)) itlist->has_ph_vars = true; + else if (tle->expr && IsA(tle->expr, GroupedVar)) + itlist->has_grp_vars = true; else if (is_converted_whole_row_reference((Node *) tle->expr)) itlist->has_conv_whole_rows = true; else *************** fix_join_expr_mutator(Node *node, fix_jo *** 2299,2304 **** --- 2357,2387 ---- /* No referent found for Var */ elog(ERROR, "variable not found in subplan target lists"); } + if (IsA(node, GroupedVar)) + { + GroupedVar *gvar = (GroupedVar *) node; + + /* See if the GroupedVar has bubbled up from a lower plan node */ + if (context->outer_itlist && context->outer_itlist->has_grp_vars) + { + newvar = search_indexed_tlist_for_non_var((Expr *) gvar, + context->outer_itlist, + OUTER_VAR); + if (newvar) + return (Node *) newvar; + } + if (context->inner_itlist && context->inner_itlist->has_grp_vars) + { + newvar = search_indexed_tlist_for_non_var((Expr *) gvar, + context->inner_itlist, + INNER_VAR); + if (newvar) + return (Node *) newvar; + } + + /* No referent found for GroupedVar */ + elog(ERROR, "grouped variable not found in subplan target lists"); + } if (IsA(node, PlaceHolderVar)) { PlaceHolderVar *phv = (PlaceHolderVar *) node; *************** fix_upper_expr_mutator(Node *node, fix_u *** 2461,2467 **** /* If no match, just fall through to process it normally */ } /* Try matching more complex expressions too, if tlist has any */ ! if (context->subplan_itlist->has_non_vars || (context->subplan_itlist->has_conv_whole_rows && is_converted_whole_row_reference(node))) { --- 2544,2551 ---- /* If no match, just fall through to process it normally */ } /* Try matching more complex expressions too, if tlist has any */ ! if (context->subplan_itlist->has_grp_vars || ! context->subplan_itlist->has_non_vars || (context->subplan_itlist->has_conv_whole_rows && is_converted_whole_row_reference(node))) { diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c new file mode 100644 index 45d82da..d52f229 *** a/src/backend/optimizer/prep/prepjointree.c --- b/src/backend/optimizer/prep/prepjointree.c *************** pull_up_simple_subquery(PlannerInfo *roo *** 911,916 **** --- 911,917 ---- memset(subroot->upper_rels, 0, sizeof(subroot->upper_rels)); memset(subroot->upper_targets, 0, sizeof(subroot->upper_targets)); subroot->processed_tlist = NIL; + subroot->max_sortgroupref = 0; subroot->grouping_map = NULL; subroot->minmax_aggs = NIL; subroot->qual_security_level = 0; diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c new file mode 100644 index fe3b458..835623b *** a/src/backend/optimizer/util/pathnode.c --- b/src/backend/optimizer/util/pathnode.c *************** *** 27,32 **** --- 27,33 ---- #include "optimizer/planmain.h" #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" + /* TODO Remove this if create_grouped_path ends up in another module. */ #include "optimizer/tlist.h" #include "optimizer/var.h" #include "parser/parsetree.h" *************** static List *reparameterize_pathlist_by_ *** 57,63 **** List *pathlist, RelOptInfo *child_rel); - /***************************************************************************** * MISC. PATH UTILITIES *****************************************************************************/ --- 58,63 ---- *************** compare_path_costs_fuzzily(Path *path1, *** 243,248 **** --- 243,249 ---- void set_cheapest(RelOptInfo *parent_rel) { + bool grouped = parent_rel->agg_info != NULL; Path *cheapest_startup_path; Path *cheapest_total_path; Path *best_param_path; *************** set_cheapest(RelOptInfo *parent_rel) *** 252,258 **** Assert(IsA(parent_rel, RelOptInfo)); if (parent_rel->pathlist == NIL) ! elog(ERROR, "could not devise a query plan for the given query"); cheapest_startup_path = cheapest_total_path = best_param_path = NULL; parameterized_paths = NIL; --- 253,273 ---- Assert(IsA(parent_rel, RelOptInfo)); if (parent_rel->pathlist == NIL) ! { ! if (!grouped) ! elog(ERROR, "could not devise a query plan for the given query"); ! else ! { ! /* ! * Creation of grouped paths is not guaranteed. ! */ ! if (IS_SIMPLE_REL(parent_rel) || IS_JOIN_REL(parent_rel)) ! mark_dummy_rel(parent_rel); ! else ! Assert(false); ! return; ! } ! } cheapest_startup_path = cheapest_total_path = best_param_path = NULL; parameterized_paths = NIL; *************** create_seqscan_path(PlannerInfo *root, R *** 949,958 **** Relids required_outer, int parallel_workers) { Path *pathnode = makeNode(Path); pathnode->pathtype = T_SeqScan; pathnode->parent = rel; ! pathnode->pathtarget = rel->reltarget; pathnode->param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->parallel_aware = parallel_workers > 0 ? true : false; --- 964,978 ---- Relids required_outer, int parallel_workers) { Path *pathnode = makeNode(Path); + bool grouped = rel->agg_info != NULL; pathnode->pathtype = T_SeqScan; pathnode->parent = rel; ! /* For grouped relation only generate the aggregation input. */ ! if (!grouped) ! pathnode->pathtarget = rel->reltarget; ! else ! pathnode->pathtarget = rel->agg_info->input; pathnode->param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->parallel_aware = parallel_workers > 0 ? true : false; *************** create_index_path(PlannerInfo *root, *** 1032,1041 **** RelOptInfo *rel = index->rel; List *indexquals, *indexqualcols; pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan; pathnode->path.parent = rel; ! pathnode->path.pathtarget = rel->reltarget; pathnode->path.param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->path.parallel_aware = false; --- 1052,1066 ---- RelOptInfo *rel = index->rel; List *indexquals, *indexqualcols; + bool grouped = rel->agg_info != NULL; pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan; pathnode->path.parent = rel; ! /* For grouped relation only generate the aggregation input. */ ! if (!grouped) ! pathnode->path.pathtarget = rel->reltarget; ! else ! pathnode->path.pathtarget = rel->agg_info->input; pathnode->path.param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->path.parallel_aware = false; *************** create_tidscan_path(PlannerInfo *root, R *** 1183,1192 **** Relids required_outer) { TidPath *pathnode = makeNode(TidPath); pathnode->path.pathtype = T_TidScan; pathnode->path.parent = rel; ! pathnode->path.pathtarget = rel->reltarget; pathnode->path.param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->path.parallel_aware = false; --- 1208,1222 ---- Relids required_outer) { TidPath *pathnode = makeNode(TidPath); + bool grouped = rel->agg_info != NULL; pathnode->path.pathtype = T_TidScan; pathnode->path.parent = rel; ! /* For grouped relation only generate the aggregation input. */ ! if (!grouped) ! pathnode->path.pathtarget = rel->reltarget; ! else ! pathnode->path.pathtarget = rel->agg_info->input; pathnode->path.param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->path.parallel_aware = false; *************** create_append_path(RelOptInfo *rel, *** 1218,1229 **** { AppendPath *pathnode = makeNode(AppendPath); ListCell *l; Assert(!parallel_aware || parallel_workers > 0); pathnode->path.pathtype = T_Append; pathnode->path.parent = rel; ! pathnode->path.pathtarget = rel->reltarget; pathnode->path.param_info = get_appendrel_parampathinfo(rel, required_outer); pathnode->path.parallel_aware = parallel_aware; --- 1248,1261 ---- { AppendPath *pathnode = makeNode(AppendPath); ListCell *l; + bool grouped = rel->agg_info != NULL; Assert(!parallel_aware || parallel_workers > 0); pathnode->path.pathtype = T_Append; pathnode->path.parent = rel; ! pathnode->path.pathtarget = !grouped ? rel->reltarget : ! rel->agg_info->target; pathnode->path.param_info = get_appendrel_parampathinfo(rel, required_outer); pathnode->path.parallel_aware = parallel_aware; *************** append_startup_cost_compare(const void * *** 1317,1327 **** /* * create_merge_append_path * Creates a path corresponding to a MergeAppend plan, returning the ! * pathnode. */ MergeAppendPath * create_merge_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *pathkeys, Relids required_outer, --- 1349,1361 ---- /* * create_merge_append_path * Creates a path corresponding to a MergeAppend plan, returning the ! * pathnode. target can be supplied by caller. If NULL is passed, the field ! * is set to rel->reltarget. */ MergeAppendPath * create_merge_append_path(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, List *subpaths, List *pathkeys, Relids required_outer, *************** create_merge_append_path(PlannerInfo *ro *** 1334,1340 **** pathnode->path.pathtype = T_MergeAppend; pathnode->path.parent = rel; ! pathnode->path.pathtarget = rel->reltarget; pathnode->path.param_info = get_appendrel_parampathinfo(rel, required_outer); pathnode->path.parallel_aware = false; --- 1368,1374 ---- pathnode->path.pathtype = T_MergeAppend; pathnode->path.parent = rel; ! pathnode->path.pathtarget = target ? target : rel->reltarget; pathnode->path.param_info = get_appendrel_parampathinfo(rel, required_outer); pathnode->path.parallel_aware = false; *************** create_unique_path(PlannerInfo *root, Re *** 1504,1510 **** MemoryContext oldcontext; int numCols; ! /* Caller made a mistake if subpath isn't cheapest_total ... */ Assert(subpath == rel->cheapest_total_path); Assert(subpath->parent == rel); /* ... or if SpecialJoinInfo is the wrong one */ --- 1538,1546 ---- MemoryContext oldcontext; int numCols; ! /* ! * Caller made a mistake if subpath isn't cheapest_total. ! */ Assert(subpath == rel->cheapest_total_path); Assert(subpath->parent == rel); /* ... or if SpecialJoinInfo is the wrong one */ *************** calc_non_nestloop_required_outer(Path *o *** 2125,2130 **** --- 2161,2167 ---- * relations. * * 'joinrel' is the join relation. + * 'target' is the join path target * 'jointype' is the type of join required * 'workspace' is the result from initial_cost_nestloop * 'extra' contains various information about the join *************** calc_non_nestloop_required_outer(Path *o *** 2139,2144 **** --- 2176,2182 ---- NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** create_nestloop_path(PlannerInfo *root, *** 2179,2185 **** pathnode->path.pathtype = T_NestLoop; pathnode->path.parent = joinrel; ! pathnode->path.pathtarget = joinrel->reltarget; pathnode->path.param_info = get_joinrel_parampathinfo(root, joinrel, --- 2217,2223 ---- pathnode->path.pathtype = T_NestLoop; pathnode->path.parent = joinrel; ! pathnode->path.pathtarget = target; pathnode->path.param_info = get_joinrel_parampathinfo(root, joinrel, *************** create_nestloop_path(PlannerInfo *root, *** 2211,2216 **** --- 2249,2255 ---- * two relations * * 'joinrel' is the join relation + * 'target' is the join path target * 'jointype' is the type of join required * 'workspace' is the result from initial_cost_mergejoin * 'extra' contains various information about the join *************** create_nestloop_path(PlannerInfo *root, *** 2227,2232 **** --- 2266,2272 ---- MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** create_mergejoin_path(PlannerInfo *root, *** 2243,2249 **** pathnode->jpath.path.pathtype = T_MergeJoin; pathnode->jpath.path.parent = joinrel; ! pathnode->jpath.path.pathtarget = joinrel->reltarget; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, --- 2283,2289 ---- pathnode->jpath.path.pathtype = T_MergeJoin; pathnode->jpath.path.parent = joinrel; ! pathnode->jpath.path.pathtarget = target; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, *************** create_mergejoin_path(PlannerInfo *root, *** 2279,2284 **** --- 2319,2325 ---- * Creates a pathnode corresponding to a hash join between two relations. * * 'joinrel' is the join relation + * 'target' is the join path target * 'jointype' is the type of join required * 'workspace' is the result from initial_cost_hashjoin * 'extra' contains various information about the join *************** create_mergejoin_path(PlannerInfo *root, *** 2293,2298 **** --- 2334,2340 ---- HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** create_hashjoin_path(PlannerInfo *root, *** 2307,2313 **** pathnode->jpath.path.pathtype = T_HashJoin; pathnode->jpath.path.parent = joinrel; ! pathnode->jpath.path.pathtarget = joinrel->reltarget; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, --- 2349,2355 ---- pathnode->jpath.path.pathtype = T_HashJoin; pathnode->jpath.path.parent = joinrel; ! pathnode->jpath.path.pathtarget = target; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, *************** create_projection_path(PlannerInfo *root *** 2389,2396 **** * Note: in the latter case, create_projection_plan has to recheck our * conclusion; see comments therein. */ ! if (is_projection_capable_path(subpath) || ! equal(oldtarget->exprs, target->exprs)) { /* No separate Result node needed */ pathnode->dummypp = true; --- 2431,2438 ---- * Note: in the latter case, create_projection_plan has to recheck our * conclusion; see comments therein. */ ! if ((is_projection_capable_path(subpath) || ! equal(oldtarget->exprs, target->exprs))) { /* No separate Result node needed */ pathnode->dummypp = true; *************** create_agg_path(PlannerInfo *root, *** 2775,2782 **** pathnode->path.pathtype = T_Agg; pathnode->path.parent = rel; pathnode->path.pathtarget = target; ! /* For now, assume we are above any joins, so no parameterization */ ! pathnode->path.param_info = NULL; pathnode->path.parallel_aware = false; pathnode->path.parallel_safe = rel->consider_parallel && subpath->parallel_safe; --- 2817,2823 ---- pathnode->path.pathtype = T_Agg; pathnode->path.parent = rel; pathnode->path.pathtarget = target; ! pathnode->path.param_info = subpath->param_info; pathnode->path.parallel_aware = false; pathnode->path.parallel_safe = rel->consider_parallel && subpath->parallel_safe; *************** create_agg_path(PlannerInfo *root, *** 2809,2814 **** --- 2850,3004 ---- } /* + * Apply partial AGG_SORTED aggregation path to subpath if it's suitably + * sorted. + * + * check_pathkeys can be passed FALSE if the function was already called for + * given index --- since the target should not change, we can skip the check + * of sorting during subsequent calls. + * + * agg_info contains both aggregate and grouping expressions. + * + * NULL is returned if sorting of subpath output is not suitable. + */ + AggPath * + create_partial_agg_sorted_path(PlannerInfo *root, Path *subpath, + bool check_pathkeys, double input_rows) + { + RelOptInfo *rel; + AggClauseCosts agg_costs; + double dNumGroups; + AggPath *result = NULL; + RelAggInfo *agg_info; + + rel = subpath->parent; + agg_info = rel->agg_info; + Assert(agg_info != NULL); + + if (subpath->pathkeys == NIL) + return NULL; + + if (!grouping_is_sortable(root->parse->groupClause)) + return NULL; + + if (check_pathkeys) + { + ListCell *lc1; + List *key_subset = NIL; + + /* + * Find all query pathkeys that our relation does affect. + */ + foreach(lc1, root->group_pathkeys) + { + PathKey *gkey = castNode(PathKey, lfirst(lc1)); + ListCell *lc2; + + foreach(lc2, subpath->pathkeys) + { + PathKey *skey = castNode(PathKey, lfirst(lc2)); + + if (skey == gkey) + { + key_subset = lappend(key_subset, gkey); + break; + } + } + } + + if (key_subset == NIL) + return NULL; + + /* Check if AGG_SORTED is useful for the whole query. */ + if (!pathkeys_contained_in(key_subset, subpath->pathkeys)) + return NULL; + } + + MemSet(&agg_costs, 0, sizeof(AggClauseCosts)); + Assert(agg_info->agg_exprs != NIL); + get_agg_clause_costs(root, (Node *) agg_info->agg_exprs, + AGGSPLIT_INITIAL_SERIAL, &agg_costs); + + Assert(agg_info->group_exprs != NIL); + dNumGroups = estimate_num_groups(root, agg_info->group_exprs, + input_rows, NULL); + + Assert(agg_info->group_clauses != NIL); + result = create_agg_path(root, rel, subpath, agg_info->target, + AGG_SORTED, AGGSPLIT_INITIAL_SERIAL, + agg_info->group_clauses, NIL, &agg_costs, dNumGroups); + + return result; + } + + /* + * Apply partial AGG_HASHED aggregation to subpath. + * + * Arguments have the same meaning as those of create_agg_sorted_path. + */ + AggPath * + create_partial_agg_hashed_path(PlannerInfo *root, Path *subpath, + double input_rows) + { + RelOptInfo *rel; + bool can_hash; + AggClauseCosts agg_costs; + double dNumGroups; + Size hashaggtablesize; + Query *parse = root->parse; + AggPath *result = NULL; + RelAggInfo *agg_info; + + rel = subpath->parent; + agg_info = rel->agg_info; + Assert(agg_info != NULL); + + MemSet(&agg_costs, 0, sizeof(AggClauseCosts)); + Assert(agg_info->agg_exprs != NIL); + get_agg_clause_costs(root, (Node *) agg_info->agg_exprs, + AGGSPLIT_INITIAL_SERIAL, &agg_costs); + + can_hash = (parse->groupClause != NIL && + parse->groupingSets == NIL && + agg_costs.numOrderedAggs == 0 && + grouping_is_hashable(parse->groupClause)); + + if (can_hash) + { + Assert(agg_info->group_exprs != NIL); + dNumGroups = estimate_num_groups(root, agg_info->group_exprs, + input_rows, NULL); + + hashaggtablesize = estimate_hashagg_tablesize(subpath, &agg_costs, + dNumGroups); + + if (hashaggtablesize < work_mem * 1024L) + { + /* + * Create the partial aggregation path. + */ + Assert(agg_info->group_clauses != NIL); + + result = create_agg_path(root, rel, subpath, + agg_info->target, + AGG_HASHED, + AGGSPLIT_INITIAL_SERIAL, + agg_info->group_clauses, NIL, + &agg_costs, + dNumGroups); + + /* + * The agg path should require no fewer parameters than the plain + * one. + */ + result->path.param_info = subpath->param_info; + } + } + + return result; + } + + /* * create_groupingsets_path * Creates a pathnode that represents performing GROUPING SETS aggregation * diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c new file mode 100644 index da8f0f9..6eaba9f *** a/src/backend/optimizer/util/relnode.c --- b/src/backend/optimizer/util/relnode.c *************** *** 17,22 **** --- 17,23 ---- #include #include "miscadmin.h" + #include "catalog/pg_constraint_fn.h" #include "catalog/partition.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" *************** *** 27,32 **** --- 28,35 ---- #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" #include "optimizer/tlist.h" + #include "optimizer/var.h" + #include "parser/parse_oper.h" #include "utils/hsearch.h" *************** static List *subbuild_joinrel_joinlist(R *** 53,62 **** List *new_joininfo); static void set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); ! static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel); static void build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, List *restrictlist, JoinType jointype); /* --- 56,69 ---- List *new_joininfo); static void set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); ! static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel, ! bool grouped); static void build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, List *restrictlist, JoinType jointype); + static void init_grouping_targets(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, PathTarget *agg_input, + List *gvis, List **group_exprs_extra_p); /* *************** setup_simple_rel_arrays(PlannerInfo *roo *** 72,80 **** /* 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 **) --- 79,92 ---- /* Arrays are accessed using RT indexes (1..N) */ root->simple_rel_array_size = list_length(root->parse->rtable) + 1; ! /* ! * simple_rel_array / simple_grouped_rel_array are both initialized to all ! * NULLs ! */ root->simple_rel_array = (RelOptInfo **) palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *)); + root->simple_grouped_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 **) *************** build_simple_rel(PlannerInfo *root, int *** 111,117 **** rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL; rel->relids = bms_make_singleton(relid); rel->rows = 0; ! /* cheap startup cost is interesting iff not all tuples to be retrieved */ rel->consider_startup = (root->tuple_fraction > 0); rel->consider_param_startup = false; /* might get changed later */ rel->consider_parallel = false; /* might get changed later */ --- 123,136 ---- rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL; rel->relids = bms_make_singleton(relid); rel->rows = 0; ! ! /* ! * Cheap startup cost is interesting iff not all tuples to be retrieved. ! * XXX As for grouped relation, the startup cost might be interesting for ! * AGG_SORTED (if it can produce the ordering that matches ! * root->query_pathkeys) but not in general (other kinds of aggregation ! * need the whole relation). Yet it seems worth trying. ! */ rel->consider_startup = (root->tuple_fraction > 0); rel->consider_param_startup = false; /* might get changed later */ rel->consider_parallel = false; /* might get changed later */ *************** build_simple_rel(PlannerInfo *root, int *** 125,130 **** --- 144,150 ---- rel->cheapest_parameterized_paths = NIL; rel->direct_lateral_relids = NULL; rel->lateral_relids = NULL; + rel->agg_info = NULL; rel->relid = relid; rel->rtekind = rte->rtekind; /* min_attr, max_attr, attr_needed, attr_widths are set below */ *************** find_base_rel(PlannerInfo *root, int rel *** 293,306 **** } /* * 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 */ --- 313,349 ---- } /* + * find_grouped_base_rel + * Find a grouped base or other relation entry, which does not have to + * exist. + */ + RelOptInfo * + find_grouped_base_rel(PlannerInfo *root, int relid) + { + RelOptInfo *rel; + + Assert(relid > 0); + + if (relid < root->simple_rel_array_size) + { + rel = root->simple_grouped_rel_array[relid]; + if (rel) + return rel; + } + + return NULL; + } + + /* * build_join_rel_hash * Construct the auxiliary hash table for join relations. */ static void ! build_join_rel_hash(PlannerInfo *root, bool grouped) { HTAB *hashtab; HASHCTL hash_ctl; + List *join_rel_list; ListCell *l; /* Create the hash table */ *************** build_join_rel_hash(PlannerInfo *root) *** 316,322 **** 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; --- 359,367 ---- HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ ! join_rel_list = !grouped ? root->join_rel_list : ! root->join_grouped_rel_list; ! foreach(l, join_rel_list) { RelOptInfo *rel = (RelOptInfo *) lfirst(l); JoinHashEntry *hentry; *************** build_join_rel_hash(PlannerInfo *root) *** 330,336 **** hentry->join_rel = rel; } ! root->join_rel_hash = hashtab; } /* --- 375,384 ---- hentry->join_rel = rel; } ! if (!grouped) ! root->join_rel_hash = hashtab; ! else ! root->join_grouped_rel_hash = hashtab; } /* *************** build_join_rel_hash(PlannerInfo *root) *** 339,352 **** * 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. --- 387,419 ---- * or NULL if none exists. This is for join relations. */ RelOptInfo * ! find_join_rel(PlannerInfo *root, Relids relids, bool grouped) { + HTAB *join_rel_hash; + List *join_rel_list; + + if (!grouped) + { + join_rel_hash = root->join_rel_hash; + join_rel_list = root->join_rel_list; + } + else + { + join_rel_hash = root->join_grouped_rel_hash; + join_rel_list = root->join_grouped_rel_list; + } + /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ ! if (!join_rel_hash && list_length(join_rel_list) > 32) ! { ! build_join_rel_hash(root, grouped); ! ! join_rel_hash = !grouped ? root->join_rel_hash : ! root->join_grouped_rel_hash; ! } /* * Use either hashtable lookup or linear search, as appropriate. *************** find_join_rel(PlannerInfo *root, Relids *** 356,367 **** * 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); --- 423,434 ---- * so would force relids out of a register and thus probably slow down the * list-search case. */ ! if (join_rel_hash) { Relids hashkey = relids; JoinHashEntry *hentry; ! hentry = (JoinHashEntry *) hash_search(join_rel_hash, &hashkey, HASH_FIND, NULL); *************** find_join_rel(PlannerInfo *root, Relids *** 372,378 **** { ListCell *l; ! foreach(l, root->join_rel_list) { RelOptInfo *rel = (RelOptInfo *) lfirst(l); --- 439,445 ---- { ListCell *l; ! foreach(l, join_rel_list) { RelOptInfo *rel = (RelOptInfo *) lfirst(l); *************** set_foreign_rel_properties(RelOptInfo *j *** 440,457 **** * PlannerInfo. Also add it to the auxiliary hashtable if there is one. */ static void ! add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) { ! /* GEQO requires us to append the new joinrel to the end of the list! */ ! root->join_rel_list = lappend(root->join_rel_list, joinrel); /* store it into the auxiliary hashtable if there is one. */ ! if (root->join_rel_hash) { JoinHashEntry *hentry; bool found; ! hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, &(joinrel->relids), HASH_ENTER, &found); --- 507,537 ---- * PlannerInfo. Also add it to the auxiliary hashtable if there is one. */ static void ! add_join_rel(PlannerInfo *root, RelOptInfo *joinrel, bool grouped) { ! HTAB *join_rel_hash; ! ! if (!grouped) ! { ! /* ! * GEQO requires us to append the new joinrel to the end of the list! ! */ ! root->join_rel_list = lappend(root->join_rel_list, joinrel); ! } ! else ! root->join_grouped_rel_list = lappend(root->join_grouped_rel_list, ! joinrel); ! ! join_rel_hash = !grouped ? root->join_rel_hash : ! root->join_grouped_rel_hash; /* store it into the auxiliary hashtable if there is one. */ ! if (join_rel_hash) { JoinHashEntry *hentry; bool found; ! hentry = (JoinHashEntry *) hash_search(join_rel_hash, &(joinrel->relids), HASH_ENTER, &found); *************** add_join_rel(PlannerInfo *root, RelOptIn *** 472,477 **** --- 552,559 ---- * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr * receives the list of RestrictInfo nodes that apply to this * particular pair of joinable relations. + * 'grouped': does the join contain partial aggregate? (If it does, then + * caller is responsible for setup of reltarget.) * * restrictlist_ptr makes the routine's API a little grotty, but it saves * duplicated calculation of the restrictlist... *************** build_join_rel(PlannerInfo *root, *** 482,491 **** RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, ! List **restrictlist_ptr) { RelOptInfo *joinrel; List *restrictlist; /* This function should be used only for join between parents. */ Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel)); --- 564,575 ---- RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, ! List **restrictlist_ptr, ! bool grouped) { RelOptInfo *joinrel; List *restrictlist; + bool create_target = !grouped; /* This function should be used only for join between parents. */ Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel)); *************** build_join_rel(PlannerInfo *root, *** 493,499 **** /* * See if we already have a joinrel for this set of base rels. */ ! joinrel = find_join_rel(root, joinrelids); if (joinrel) { --- 577,583 ---- /* * See if we already have a joinrel for this set of base rels. */ ! joinrel = find_join_rel(root, joinrelids, grouped); if (joinrel) { *************** build_join_rel(PlannerInfo *root, *** 516,526 **** joinrel->reloptkind = RELOPT_JOINREL; joinrel->relids = bms_copy(joinrelids); joinrel->rows = 0; ! /* cheap startup cost is interesting iff not all tuples to be retrieved */ joinrel->consider_startup = (root->tuple_fraction > 0); joinrel->consider_param_startup = false; joinrel->consider_parallel = false; ! joinrel->reltarget = create_empty_pathtarget(); joinrel->pathlist = NIL; joinrel->ppilist = NIL; joinrel->partial_pathlist = NIL; --- 600,610 ---- joinrel->reloptkind = RELOPT_JOINREL; joinrel->relids = bms_copy(joinrelids); joinrel->rows = 0; ! /* See the comment in build_simple_rel(). */ joinrel->consider_startup = (root->tuple_fraction > 0); joinrel->consider_param_startup = false; joinrel->consider_parallel = false; ! joinrel->reltarget = NULL; joinrel->pathlist = NIL; joinrel->ppilist = NIL; joinrel->partial_pathlist = NIL; *************** build_join_rel(PlannerInfo *root, *** 534,539 **** --- 618,624 ---- inner_rel->direct_lateral_relids); joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids, outer_rel, inner_rel); + joinrel->agg_info = NULL; joinrel->relid = 0; /* indicates not a baserel */ joinrel->rtekind = RTE_JOIN; joinrel->min_attr = 0; *************** build_join_rel(PlannerInfo *root, *** 582,590 **** * 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, outer_rel, inner_rel); /* * add_placeholders_to_joinrel also took care of adding the ph_lateral --- 667,679 ---- * and inner rels we first try to build it from. But the contents should * be the same regardless. */ ! if (create_target) ! { ! joinrel->reltarget = create_empty_pathtarget(); ! build_joinrel_tlist(root, joinrel, outer_rel); ! build_joinrel_tlist(root, joinrel, inner_rel); ! add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel); ! } /* * add_placeholders_to_joinrel also took care of adding the ph_lateral *************** build_join_rel(PlannerInfo *root, *** 621,651 **** /* * Set estimates of the joinrel's size. - */ - set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, - sjinfo, restrictlist); - - /* - * Set the consider_parallel flag if this joinrel could potentially be - * scanned within a parallel worker. If this flag is false for either - * inner_rel or outer_rel, then it must be false for the joinrel also. - * Even if both are true, there might be parallel-restricted expressions - * in the targetlist or quals. * ! * Note that if there are more than two rels in this relation, they could ! * be divided between inner_rel and outer_rel in any arbitrary way. We ! * assume this doesn't matter, because we should hit all the same baserels ! * and joinclauses while building up to this joinrel no matter which we ! * take; therefore, we should make the same decision here however we get ! * here. */ ! if (inner_rel->consider_parallel && outer_rel->consider_parallel && ! is_parallel_safe(root, (Node *) restrictlist) && ! is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) ! joinrel->consider_parallel = true; /* Add the joinrel to the PlannerInfo. */ ! add_join_rel(root, joinrel); /* * Also, if dynamic-programming join search is active, add the new joinrel --- 710,747 ---- /* * Set estimates of the joinrel's size. * ! * XXX The function claims to need reltarget but it does not seem to ! * actually use it. Should we call it unconditionally so that callers of ! * build_join_rel() do not have to care? */ ! if (create_target) ! { ! set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, ! sjinfo, restrictlist); ! ! /* ! * Set the consider_parallel flag if this joinrel could potentially be ! * scanned within a parallel worker. If this flag is false for either ! * inner_rel or outer_rel, then it must be false for the joinrel also. ! * Even if both are true, there might be parallel-restricted ! * expressions in the targetlist or quals. ! * ! * Note that if there are more than two rels in this relation, they ! * could be divided between inner_rel and outer_rel in any arbitrary ! * way. We assume this doesn't matter, because we should hit all the ! * same baserels and joinclauses while building up to this joinrel no ! * matter which we take; therefore, we should make the same decision ! * here however we get here. ! */ ! if (inner_rel->consider_parallel && outer_rel->consider_parallel && ! is_parallel_safe(root, (Node *) restrictlist) && ! is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) ! joinrel->consider_parallel = true; ! } /* Add the joinrel to the PlannerInfo. */ ! add_join_rel(root, joinrel, grouped); /* * Also, if dynamic-programming join search is active, add the new joinrel *************** build_join_rel(PlannerInfo *root, *** 653,664 **** * 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; --- 749,766 ---- * of members should be for equality, but some of the level 1 rels might * have been joinrels already, so we can only assert <=. */ ! if ((!grouped && root->join_rel_level) || ! (grouped && root->join_grouped_rel_level)) { Assert(root->join_cur_level > 0); Assert(root->join_cur_level <= bms_num_members(joinrel->relids)); ! if (!grouped) ! root->join_rel_level[root->join_cur_level] = ! lappend(root->join_rel_level[root->join_cur_level], joinrel); ! else ! root->join_grouped_rel_level[root->join_cur_level] = ! lappend(root->join_grouped_rel_level[root->join_cur_level], ! joinrel); } return joinrel; *************** build_join_rel(PlannerInfo *root, *** 677,692 **** * 'restrictlist': list of RestrictInfo nodes that apply to this particular * pair of joinable relations * 'jointype' is the join type (inner, left, full, etc) */ RelOptInfo * build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, SpecialJoinInfo *sjinfo, ! JoinType jointype) { RelOptInfo *joinrel = makeNode(RelOptInfo); AppendRelInfo **appinfos; int nappinfos; /* Only joins between "other" relations land here. */ Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel)); --- 779,797 ---- * 'restrictlist': list of RestrictInfo nodes that apply to this particular * pair of joinable relations * 'jointype' is the join type (inner, left, full, etc) + * 'grouped': does the join contain partial aggregate? (If it does, then + * caller is responsible for setup of reltarget.) */ RelOptInfo * build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, SpecialJoinInfo *sjinfo, ! JoinType jointype, bool grouped) { RelOptInfo *joinrel = makeNode(RelOptInfo); AppendRelInfo **appinfos; int nappinfos; + bool create_target = !grouped; /* Only joins between "other" relations land here. */ Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel)); *************** build_child_join_rel(PlannerInfo *root, *** 694,704 **** joinrel->reloptkind = RELOPT_OTHER_JOINREL; joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids); joinrel->rows = 0; ! /* cheap startup cost is interesting iff not all tuples to be retrieved */ joinrel->consider_startup = (root->tuple_fraction > 0); joinrel->consider_param_startup = false; joinrel->consider_parallel = false; ! joinrel->reltarget = create_empty_pathtarget(); joinrel->pathlist = NIL; joinrel->ppilist = NIL; joinrel->partial_pathlist = NIL; --- 799,809 ---- joinrel->reloptkind = RELOPT_OTHER_JOINREL; joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids); joinrel->rows = 0; ! /* See the comment in build_simple_rel(). */ joinrel->consider_startup = (root->tuple_fraction > 0); joinrel->consider_param_startup = false; joinrel->consider_parallel = false; ! joinrel->reltarget = NULL; joinrel->pathlist = NIL; joinrel->ppilist = NIL; joinrel->partial_pathlist = NIL; *************** build_child_join_rel(PlannerInfo *root, *** 708,713 **** --- 813,819 ---- joinrel->cheapest_parameterized_paths = NIL; joinrel->direct_lateral_relids = NULL; joinrel->lateral_relids = NULL; + joinrel->agg_info = NULL; joinrel->relid = 0; /* indicates not a baserel */ joinrel->rtekind = RTE_JOIN; joinrel->min_attr = 0; *************** build_child_join_rel(PlannerInfo *root, *** 744,754 **** /* Compute information relevant to foreign relations. */ set_foreign_rel_properties(joinrel, outer_rel, inner_rel); ! /* Build targetlist */ ! build_joinrel_tlist(root, joinrel, outer_rel); ! build_joinrel_tlist(root, joinrel, inner_rel); ! /* Add placeholder variables. */ ! add_placeholders_to_child_joinrel(root, joinrel, parent_joinrel); /* Construct joininfo list. */ appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos); --- 850,864 ---- /* Compute information relevant to foreign relations. */ set_foreign_rel_properties(joinrel, outer_rel, inner_rel); ! if (create_target) ! { ! /* Build targetlist */ ! joinrel->reltarget = create_empty_pathtarget(); ! build_joinrel_tlist(root, joinrel, outer_rel); ! build_joinrel_tlist(root, joinrel, inner_rel); ! /* Add placeholder variables. */ ! add_placeholders_to_child_joinrel(root, joinrel, parent_joinrel); ! } /* Construct joininfo list. */ appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos); *************** build_child_join_rel(PlannerInfo *root, *** 756,762 **** (Node *) parent_joinrel->joininfo, nappinfos, appinfos); - pfree(appinfos); /* * Lateral relids referred in child join will be same as that referred in --- 866,871 ---- *************** build_child_join_rel(PlannerInfo *root, *** 783,796 **** /* Set estimates of the child-joinrel's size. */ ! set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, ! sjinfo, restrictlist); /* We build the join only once. */ ! Assert(!find_join_rel(root, joinrel->relids)); /* Add the relation to the PlannerInfo. */ ! add_join_rel(root, joinrel); return joinrel; } --- 892,909 ---- /* Set estimates of the child-joinrel's size. */ ! /* XXX See the corresponding comment in build_join_rel(). */ ! if (create_target) ! set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, ! sjinfo, restrictlist); /* We build the join only once. */ ! Assert(!find_join_rel(root, joinrel->relids, grouped)); /* Add the relation to the PlannerInfo. */ ! add_join_rel(root, joinrel, grouped); ! ! pfree(appinfos); return joinrel; } *************** build_joinrel_partition_info(RelOptInfo *** 1751,1753 **** --- 1864,2471 ---- joinrel->nullable_partexprs[cnt] = nullable_partexpr; } } + + /* + * Check if the relation can produce grouped paths and return the information + * it'll need for it. The passed relation is the non-grouped one which has the + * reltarget already constructed. + */ + RelAggInfo * + create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) + { + List *gvis; + List *aggregates = NIL; + List *grp_exprs = NIL; + bool found_higher_agg; + ListCell *lc; + RelAggInfo *result; + PathTarget *target, + *agg_input; + List *grp_exprs_extra = NIL; + int i; + List *sortgroupclauses = NIL; + + /* + * The function shouldn't have been called if there's no opportunity for + * aggregation push-down. + */ + Assert(root->grouped_var_list != NIL); + + /* + * The source relation has nothing to do with grouping. + */ + Assert(rel->agg_info == NULL); + + /* + * The current implementation of aggregation push-down cannot handle + * PlaceHolderVar (PHV). + * + * If we knew that the PHV should be evaluated in this target (and of + * course, if its expression matched some grouping expression or Aggref + * argument), we'd just let init_grouping_targets create GroupedVar for + * the corresponding expression (phexpr). On the other hand, if we knew + * that the PHV is evaluated below the current rel, we'd ignore it because + * the referencing GroupedVar would take care of propagation of the value + * to upper joins. (PHV whose ph_eval_at is above the current rel make the + * aggregation push-down impossible in any case because the partial + * aggregation would receive wrong input if we ignored the ph_eval_at.) + * + * The problem is that the same PHV can be evaluated in the target of the + * current rel or in that of lower rel --- depending on the input paths. + * For example, consider rel->relids = {A, B, C} and if ph_eval_at = {B, + * C}. Path "A JOIN (B JOIN C)" implies that the PHV is evaluated by the + * "(B JOIN C)", while path "(A JOIN B) JOIN C" evaluates the PHV itself. + */ + foreach(lc, rel->reltarget->exprs) + { + Expr *expr = lfirst(lc); + + if (IsA(expr, PlaceHolderVar)) + return NULL; + } + + if (IS_SIMPLE_REL(rel)) + { + RangeTblEntry *rte = root->simple_rte_array[rel->relid];; + + /* + * rtekind != RTE_RELATION case is not supported yet. + */ + if (rte->rtekind != RTE_RELATION) + return NULL; + } + + /* Caller should only pass base relations or joins. */ + Assert(rel->reloptkind == RELOPT_BASEREL || + rel->reloptkind == RELOPT_JOINREL); + + /* + * If any outer join can set the attribute value to NULL, the Agg plan + * would receive different input at the base rel level. + * + * XXX For RELOPT_JOINREL, do not return if all the joins that can set any + * entry of the grouped target (do we need to postpone this check until + * the grouped target is available, and init_grouping_targets take care?) + * of this rel to NULL are provably below rel. (It's ok if rel is one of + * these joins.) + */ + if (bms_overlap(rel->relids, root->nullable_baserels)) + return NULL; + + /* + * Use equivalence classes to generate additional grouping expressions for + * the current rel. Without these we might not be able to apply + * aggregation to the relation result set. + * + * It's important that create_grouping_expr_grouped_var_infos has + * processed the explicit grouping columns by now. If the grouping clause + * contains multiple expressions belonging to the same EC, the original + * (i.e. not derived) one should be preferred when we build grouping + * target for a relation. Otherwise we have a problem when trying to match + * target entries to grouping clauses during plan creation, see + * get_grouping_expression(). + */ + gvis = list_copy(root->grouped_var_list); + foreach(lc, root->grouped_var_list) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, lc); + int relid = -1; + + /* Only interested in grouping expressions. */ + if (IsA(gvi->gvexpr, Aggref)) + continue; + + while ((relid = bms_next_member(rel->relids, relid)) >= 0) + { + GroupedVarInfo *gvi_trans; + + gvi_trans = translate_expression_to_rels(root, gvi, relid); + if (gvi_trans != NULL) + gvis = lappend(gvis, gvi_trans); + } + } + + /* + * Check if some aggregates or grouping expressions can be evaluated in + * this relation's target, and collect all vars referenced by these + * aggregates / grouping expressions; + */ + found_higher_agg = false; + foreach(lc, gvis) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, lc); + + /* + * The subset includes gv_eval_at uninitialized, which includes + * Aggref.aggstar. + */ + if (bms_is_subset(gvi->gv_eval_at, rel->relids)) + { + /* + * init_grouping_targets will handle plain Var grouping + * expressions because it needs to look them up in + * grouped_var_list anyway. + * + * XXX A plain Var could actually be handled w/o GroupedVar, but + * thus init_grouping_targets would have to spend extra effort + * looking for the EC-related vars, instead of relying on + * create_grouping_expr_grouped_var_infos. (Processing of + * particular expression would look different, so we could hardly + * reuse the same piece of code.) + */ + if (IsA(gvi->gvexpr, Var)) + continue; + + /* + * Accept the aggregate / grouping expression. + * + * (GroupedVarInfo is more convenient for the next processing than + * Aggref, see add_aggregates_to_grouped_target.) + */ + if (IsA(gvi->gvexpr, Aggref)) + aggregates = lappend(aggregates, gvi); + else + grp_exprs = lappend(grp_exprs, gvi); + } + else if (bms_overlap(gvi->gv_eval_at, rel->relids) && + IsA(gvi->gvexpr, Aggref)) + { + /* + * Remember that there is at least one aggregate expression that + * needs more than this rel. + */ + found_higher_agg = true; + } + } + + /* + * Grouping makes little sense w/o aggregate function and w/o grouping + * expressions. + */ + if (aggregates == NIL) + { + list_free(gvis); + return NULL; + } + + /* + * Give up if some other aggregate(s) need multiple relations including + * the current one. The problem is that grouping of the current relation + * could make some input variables unavailable for the "higher aggregate", + * and it'd also decrease the number of input rows the "higher aggregate" + * receives. + * + * In contrast, grp_exprs is only supposed to contain generic grouping + * expression, so it can be NIL so far. If all the grouping keys are just + * plain Vars, init_grouping_targets will take care of them. + */ + if (found_higher_agg) + { + list_free(gvis); + return NULL; + } + + /* + * Create target for grouped paths as well as one for the input paths of + * the partial aggregation paths. + */ + target = create_empty_pathtarget(); + agg_input = create_empty_pathtarget(); + init_grouping_targets(root, rel, target, agg_input, gvis, + &grp_exprs_extra); + list_free(gvis); + + /* + * Add (non-Var) grouping expressions (in the form of GroupedVar) to + * target_agg. + * + * Follow the convention that the grouping expressions should precede + * aggregates. + */ + add_grouped_vars_to_target(root, target, grp_exprs); + + /* + * Partial aggregation makes no sense w/o grouping expressions. + */ + if (list_length(target->exprs) == 0) + return NULL; + + /* + * If the aggregation target should have extra grouping expressions, add + * them now. This step includes assignment of tleSortGroupRef's which we + * can generate now (the "ordinary" grouping expression are present in the + * target by now). + */ + if (list_length(grp_exprs_extra) > 0) + { + Index sortgroupref; + + /* + * Always start at root->max_sortgroupref. The extra grouping + * expressions aren't used during the final aggregation, so the + * sortgroupref values don't need to be unique across the query. Thus + * we don't have to increase root->max_sortgroupref, which makes + * recognition of the extra grouping expressions pretty easy. + */ + sortgroupref = root->max_sortgroupref; + + /* + * Generate the SortGroupClause's and add the expressions to the + * target. + */ + foreach(lc, grp_exprs_extra) + { + Var *var = lfirst_node(Var, lc); + SortGroupClause *cl = makeNode(SortGroupClause); + int i = 0; + ListCell *lc2; + + /* + * TODO Verify that these fields are sufficient for this special + * SortGroupClause. + */ + cl->tleSortGroupRef = ++sortgroupref; + get_sort_group_operators(var->vartype, + false, true, false, + NULL, &cl->eqop, NULL, + &cl->hashable); + sortgroupclauses = lappend(sortgroupclauses, cl); + add_column_to_pathtarget(target, (Expr *) var, + cl->tleSortGroupRef); + + /* + * The aggregation input target must emit this var too. It can + * already be there, so avoid adding it again. + */ + foreach(lc2, agg_input->exprs) + { + Expr *expr = (Expr *) lfirst(lc2); + + if (equal(expr, var)) + { + /* + * The fact that the var is in agg_input does not imply + * that it has sortgroupref set. For example, the reason + * that it's there can be that a generic grouping + * expression references it, so grouping by the var alone + * hasn't been considered so far. + */ + if (agg_input->sortgrouprefs == NULL) + { + agg_input->sortgrouprefs = (Index *) + palloc0(list_length(agg_input->exprs) * + sizeof(Index)); + } + if (agg_input->sortgrouprefs[i] == 0) + agg_input->sortgrouprefs[i] = cl->tleSortGroupRef; + + break; + } + + i++; + } + if (lc2 != NULL) + continue; + + /* + * Add the var if it's not in the target yet. + */ + add_column_to_pathtarget(agg_input, (Expr *) var, + cl->tleSortGroupRef); + } + } + + /* + * Add aggregates (in the form of GroupedVar) to the grouping target. + */ + add_grouped_vars_to_target(root, target, aggregates); + + /* + * Make sure that the paths generating input data for partial aggregation + * include non-Var grouping expressions. + */ + add_grouped_vars_to_target(root, agg_input, grp_exprs); + + /* + * Since neither target nor agg_input is supposed to be identical to the + * source reltarget, compute the width and cost again. + */ + set_pathtarget_cost_width(root, target); + set_pathtarget_cost_width(root, agg_input); + + result = makeNode(RelAggInfo); + result->target = target; + result->input = agg_input; + + /* + * Build a list of grouping expressions and a list of the corresponding + * SortGroupClauses. + */ + i = 0; + foreach(lc, target->exprs) + { + Index sortgroupref = 0; + SortGroupClause *cl; + Expr *texpr; + + texpr = (Expr *) lfirst(lc); + + if (IsA(texpr, GroupedVar) && + IsA(((GroupedVar *) texpr)->gvexpr, Aggref)) + { + /* + * texpr should represent the first aggregate in the targetlist. + */ + break; + } + + /* + * Find the clause by sortgroupref. + */ + sortgroupref = target->sortgrouprefs[i++]; + + /* + * Besides being an aggregate, the target expression should have no + * other reason then being a column of a relation functionally + * dependent on the GROUP BY clause. So it's not actually a grouping + * column. + */ + if (sortgroupref == 0) + continue; + + cl = get_sortgroupref_clause_noerr(sortgroupref, + root->parse->groupClause); + + /* + * If query does not have this clause, it must be target-specific. + */ + if (cl == NULL) + cl = get_sortgroupref_clause(sortgroupref, sortgroupclauses); + + result->group_clauses = list_append_unique(result->group_clauses, + cl); + + /* + * Add only unique clauses because of joins (both sides of a join can + * point at the same grouping clause). XXX Is it worth adding a bool + * argument indicating that we're dealing with join right now? + */ + result->group_exprs = list_append_unique(result->group_exprs, + texpr); + } + + /* Finally collect the aggregates. */ + while (lc != NULL) + { + GroupedVar *gvar = castNode(GroupedVar, lfirst(lc)); + + /* + * Aggregate GroupedVarInfo should always point to the partial + * aggregate. + */ + Assert(gvar->agg_partial != NULL); + result->agg_exprs = lappend(result->agg_exprs, gvar->agg_partial); + lc = lnext(lc); + } + + return result; + } + + /* + * Initialize target for grouped paths (target) as well as a target for paths + * that generate input for partial aggregation (agg_input). + * + * gvis a list of GroupedVarInfo's possibly useful for rel. + * + * The *group_exprs_extra_p list may receive additional grouping expressions + * that the query does not have. These can make the aggregation of base + * relation / join less efficient, but can allow for join of the grouped + * relation that wouldn't be possible otherwise. + */ + static void + init_grouping_targets(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, PathTarget *agg_input, + List *gvis, List **group_exprs_extra_p) + { + ListCell *lc; + List *vars_unresolved = NIL; + + foreach(lc, rel->reltarget->exprs) + { + Var *tvar; + GroupedVar *gvar; + + /* + * Given that PlaceHolderVar currently prevents us from doing + * aggregation push-down, the source target cannot contain anything + * more complex than a Var. (As for generic grouping expressions, + * add_grouped_vars_to_target will retrieve them from the query + * targetlist and add them to "target" outside this function.) + */ + tvar = lfirst_node(Var, lc); + + gvar = get_grouping_expression(gvis, (Expr *) tvar); + if (gvar != NULL) + { + /* + * It's o.k. to use the target expression for grouping. + * + * The actual Var is added to the target. If we used the + * containing GroupedVar, references from various clauses (e.g. + * join quals) wouldn't work. + */ + add_column_to_pathtarget(target, gvar->gvexpr, + gvar->sortgroupref); + + /* + * As for agg_input, add the original expression but set + * sortgroupref in addition. + */ + add_column_to_pathtarget(agg_input, gvar->gvexpr, + gvar->sortgroupref); + + /* Process the next expression. */ + continue; + } + + /* + * Further investigation involves dependency check, for which we need + * to have all the plain-var grouping expressions gathered. So far + * only store the var in a list. + */ + vars_unresolved = lappend(vars_unresolved, tvar); + } + + /* + * Check for other possible reasons for the var to be in the plain target. + */ + foreach(lc, vars_unresolved) + { + Var *var; + RangeTblEntry *rte; + List *deps = NIL; + Relids relids_subtract; + int ndx; + RelOptInfo *baserel; + + var = lfirst_node(Var, lc); + rte = root->simple_rte_array[var->varno]; + + /* + * Dependent var is almost the same as one that has sortgroupref. + */ + if (check_functional_grouping(rte->relid, var->varno, + var->varlevelsup, + target->exprs, &deps)) + { + + Index sortgroupref = 0; + + add_column_to_pathtarget(target, (Expr *) var, sortgroupref); + + /* + * The var shouldn't be actually used as a grouping key (instead, + * the one this depends on will be), so sortgroupref should not be + * important. But once we have it ... + */ + add_column_to_pathtarget(agg_input, (Expr *) var, sortgroupref); + + /* + * The var may or may not be present in generic grouping + * expression(s) or aggregate arguments, but we already have it in + * the targets, so don't care. + */ + continue; + } + + /* + * Isn't the expression needed by joins above the current rel? + * + * The relids we're not interested in do include 0, which is the + * top-level targetlist. The only reason for relids to contain 0 + * should be that arg_var is referenced either by aggregate or by + * grouping expression, but right now we're interested in the *other* + * reasons. (As soon as GroupedVars are installed, the top level + * aggregates / grouping expressions no longer need direct reference + * to arg_var anyway.) + */ + relids_subtract = bms_copy(rel->relids); + bms_add_member(relids_subtract, 0); + + baserel = find_base_rel(root, var->varno); + ndx = var->varattno - baserel->min_attr; + if (bms_nonempty_difference(baserel->attr_needed[ndx], + relids_subtract)) + { + /* + * The variable is needed by upper join. This includes one that is + * referenced by a generic grouping expression but couldn't be + * recognized as grouping expression on its own at the top of the + * loop. + * + * The only way to bring this var to the aggregation output is to + * add it to the grouping expressions too. + * + * Since root->parse->groupClause is not supposed to contain this + * expression, we need to construct special SortGroupClause. Its + * tleSortGroupRef needs to be unique within "target", so postpone + * creation of the SortGroupRefs until we're done with the + * iteration of rel->reltarget->exprs. + */ + *group_exprs_extra_p = lappend(*group_exprs_extra_p, var); + } + else + { + /* + * As long as the query is semantically correct, arriving here + * means that the var is referenced either by aggregate argument + * or by generic grouping expression. The per-relation aggregation + * target should not contain it, as it only provides input for the + * final aggregation. + */ + } + + /* + * The var is not suitable for grouping, but agg_input ought to stay + * complete. + */ + add_column_to_pathtarget(agg_input, (Expr *) var, 0); + } + } + + + /* + * Translate RelAggInfo of parent relation so it matches given child relation. + */ + RelAggInfo * + translate_rel_agg_info(PlannerInfo *root, RelAggInfo *parent, + AppendRelInfo **appinfos, int nappinfos) + { + RelAggInfo *result; + + result = makeNode(RelAggInfo); + + result->target = copy_pathtarget(parent->target); + result->target->exprs = (List *) + adjust_appendrel_attrs(root, + (Node *) result->target->exprs, + nappinfos, appinfos); + + result->input = copy_pathtarget(parent->input); + result->input->exprs = (List *) + adjust_appendrel_attrs(root, + (Node *) result->input->exprs, + nappinfos, appinfos); + + result->group_clauses = parent->group_clauses; + + result->group_exprs = (List *) + adjust_appendrel_attrs(root, + (Node *) parent->group_exprs, + nappinfos, appinfos); + result->agg_exprs = (List *) + adjust_appendrel_attrs(root, + (Node *) parent->agg_exprs, + nappinfos, appinfos); + return result; + } diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c new file mode 100644 index 32160d5..6d74323 *** a/src/backend/optimizer/util/tlist.c --- b/src/backend/optimizer/util/tlist.c *************** get_sortgrouplist_exprs(List *sgClauses, *** 408,414 **** return result; } - /***************************************************************************** * Functions to extract data from a list of SortGroupClauses * --- 408,413 ---- *************** apply_pathtarget_labeling_to_tlist(List *** 783,788 **** --- 782,900 ---- } /* + * Replace each GroupedVar in the source targetlist with the original + * expression --- either Aggref or a non-Var grouping expression. + * + * Even if the query targetlist has the Aggref wrapped in a generic + * expression, any subplan should emit the corresponding GroupedVar + * alone. (Aggregate finalization is needed before the aggregate result can be + * used for any purposes and that happens at the top level of the query.) + * Therefore we do not have to recurse into the target expressions here. + */ + List * + replace_grouped_vars_with_aggrefs(PlannerInfo *root, List *src) + { + List *result = NIL; + ListCell *l; + + foreach(l, src) + { + TargetEntry *te, + *te_new; + Expr *expr_new = NULL; + + te = lfirst_node(TargetEntry, l); + + if (IsA(te->expr, GroupedVar)) + { + GroupedVar *gvar; + + gvar = castNode(GroupedVar, te->expr); + if (IsA(gvar->gvexpr, Aggref)) + { + /* + * Partial aggregate should appear in the targetlist so that + * it looks as if convert_combining_aggrefs arranged it. + */ + expr_new = (Expr *) gvar->agg_partial; + } + else + expr_new = gvar->gvexpr; + } + + if (expr_new != NULL) + { + te_new = flatCopyTargetEntry(te); + te_new->expr = (Expr *) expr_new; + } + else + te_new = te; + result = lappend(result, te_new); + } + + return result; + } + + /* + * For each aggregate add GroupedVar to the grouped target. + * + * Caller passes the aggregates in the form of GroupedVarInfos so that we + * don't have to look for gvid. + */ + void + add_grouped_vars_to_target(PlannerInfo *root, PathTarget *target, + List *expressions) + { + ListCell *lc; + + /* Create the vars and add them to the target. */ + foreach(lc, expressions) + { + GroupedVarInfo *gvi; + GroupedVar *gvar; + + gvi = lfirst_node(GroupedVarInfo, lc); + gvar = makeNode(GroupedVar); + gvar->gvid = gvi->gvid; + gvar->gvexpr = gvi->gvexpr; + gvar->agg_partial = gvi->agg_partial; + add_column_to_pathtarget(target, (Expr *) gvar, gvi->sortgroupref); + } + } + + /* + * Return GroupedVar containing the passed-in expression if one exists, or + * NULL if the expression cannot be used as grouping key. + */ + GroupedVar * + get_grouping_expression(List *gvis, Expr *expr) + { + ListCell *lc; + + foreach(lc, gvis) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, lc); + + if (IsA(gvi->gvexpr, Aggref)) + continue; + + if (equal(gvi->gvexpr, expr)) + { + GroupedVar *result = makeNode(GroupedVar); + + Assert(gvi->sortgroupref > 0); + result->gvexpr = gvi->gvexpr; + result->gvid = gvi->gvid; + result->sortgroupref = gvi->sortgroupref; + return result; + } + } + + /* The expression cannot be used as grouping key. */ + return NULL; + } + + /* * split_pathtarget_at_srfs * Split given PathTarget into multiple levels to position SRFs safely * diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c new file mode 100644 index b16b1e4..459dc30 *** a/src/backend/optimizer/util/var.c --- b/src/backend/optimizer/util/var.c *************** alias_relid_set(PlannerInfo *root, Relid *** 840,842 **** --- 840,864 ---- } return result; } + + /* + * Return GroupedVarInfo for given GroupedVar. + * + * XXX Consider better location of this routine. + */ + GroupedVarInfo * + find_grouped_var_info(PlannerInfo *root, GroupedVar *gvar) + { + ListCell *l; + + foreach(l, root->grouped_var_list) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, l); + + if (gvi->gvid == gvar->gvid) + return gvi; + } + + elog(ERROR, "GroupedVarInfo not found"); + return NULL; /* keep compiler quiet */ + } diff --git a/src/backend/parser/parse_func.c b/src/backend/parser/parse_func.c new file mode 100644 index 2a4ac09..267c0b9 *** a/src/backend/parser/parse_func.c --- b/src/backend/parser/parse_func.c *************** ParseFuncOrColumn(ParseState *pstate, Li *** 98,103 **** --- 98,104 ---- Oid vatype; FuncDetailCode fdresult; char aggkind = 0; + Oid aggcombinefn = InvalidOid; ParseCallbackState pcbstate; /* *************** ParseFuncOrColumn(ParseState *pstate, Li *** 350,355 **** --- 351,357 ---- elog(ERROR, "cache lookup failed for aggregate %u", funcid); classForm = (Form_pg_aggregate) GETSTRUCT(tup); aggkind = classForm->aggkind; + aggcombinefn = classForm->aggcombinefn; catDirectArgs = classForm->aggnumdirectargs; ReleaseSysCache(tup); *************** ParseFuncOrColumn(ParseState *pstate, Li *** 695,700 **** --- 697,703 ---- aggref->aggstar = agg_star; aggref->aggvariadic = func_variadic; aggref->aggkind = aggkind; + aggref->aggcombinefn = aggcombinefn; /* agglevelsup will be set by transformAggregateCall */ aggref->aggsplit = AGGSPLIT_SIMPLE; /* planner might change this */ aggref->location = location; diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c new file mode 100644 index 3697466..4b49d32 *** a/src/backend/utils/adt/ruleutils.c --- b/src/backend/utils/adt/ruleutils.c *************** get_rule_expr(Node *node, deparse_contex *** 7686,7691 **** --- 7686,7708 ---- get_agg_expr((Aggref *) node, context, (Aggref *) node); break; + case T_GroupedVar: + { + GroupedVar *gvar = castNode(GroupedVar, node); + Expr *expr = gvar->gvexpr; + + if (IsA(expr, Aggref)) + get_agg_expr(gvar->agg_partial, context, (Aggref *) gvar->gvexpr); + else if (IsA(expr, Var)) + (void) get_variable((Var *) expr, 0, false, context); + else + { + Assert(IsA(gvar->gvexpr, OpExpr)); + get_oper_expr((OpExpr *) expr, context); + } + break; + } + case T_GroupingFunc: { GroupingFunc *gexpr = (GroupingFunc *) node; *************** get_agg_combine_expr(Node *node, deparse *** 9171,9180 **** Aggref *aggref; Aggref *original_aggref = private; ! if (!IsA(node, Aggref)) elog(ERROR, "combining Aggref does not point to an Aggref"); - aggref = (Aggref *) node; get_agg_expr(aggref, context, original_aggref); } --- 9188,9205 ---- Aggref *aggref; Aggref *original_aggref = private; ! if (IsA(node, Aggref)) ! aggref = (Aggref *) node; ! else if (IsA(node, GroupedVar)) ! { ! GroupedVar *gvar = castNode(GroupedVar, node); ! ! aggref = gvar->agg_partial; ! original_aggref = castNode(Aggref, gvar->gvexpr); ! } ! else elog(ERROR, "combining Aggref does not point to an Aggref"); get_agg_expr(aggref, context, original_aggref); } diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c new file mode 100644 index fcc8323..72e14e5 *** a/src/backend/utils/adt/selfuncs.c --- b/src/backend/utils/adt/selfuncs.c *************** *** 114,119 **** --- 114,120 ---- #include "catalog/pg_statistic_ext.h" #include "catalog/pg_type.h" #include "executor/executor.h" + #include "executor/nodeAgg.h" #include "mb/pg_wchar.h" #include "miscadmin.h" #include "nodes/makefuncs.h" *************** estimate_hash_bucket_stats(PlannerInfo * *** 3863,3868 **** --- 3864,3902 ---- ReleaseVariableStats(vardata); } + /* + * estimate_hashagg_tablesize + * estimate the number of bytes that a hash aggregate hashtable will + * require based on the agg_costs, path width and dNumGroups. + * + * XXX this may be over-estimating the size now that hashagg knows to omit + * unneeded columns from the hashtable. Also for mixed-mode grouping sets, + * grouping columns not in the hashed set are counted here even though hashagg + * won't store them. Is this a problem? + */ + Size + estimate_hashagg_tablesize(Path *path, const AggClauseCosts *agg_costs, + double dNumGroups) + { + Size hashentrysize; + + /* Estimate per-hash-entry space at tuple width... */ + hashentrysize = MAXALIGN(path->pathtarget->width) + + MAXALIGN(SizeofMinimalTupleHeader); + + /* plus space for pass-by-ref transition values... */ + hashentrysize += agg_costs->transitionSpace; + /* plus the per-hash-entry overhead */ + hashentrysize += hash_agg_entry_size(agg_costs->numAggs); + + /* + * Note that this disregards the effect of fill-factor and growth policy + * of the hash-table. That's probably ok, given default the default + * fill-factor is relatively high. It'd be hard to meaningfully factor in + * "double-in-size" growth policies here. + */ + return hashentrysize * dNumGroups; + } /*------------------------------------------------------------------------- * *************** examine_variable(PlannerInfo *root, Node *** 4793,4799 **** if (varRelid == 0) { /* treat it as a variable of a join relation */ ! vardata->rel = find_join_rel(root, varnos); node = basenode; /* strip any relabeling */ } else if (bms_is_member(varRelid, varnos)) --- 4827,4833 ---- if (varRelid == 0) { /* treat it as a variable of a join relation */ ! vardata->rel = find_join_rel(root, varnos, false); node = basenode; /* strip any relabeling */ } else if (bms_is_member(varRelid, varnos)) *************** find_join_input_rel(PlannerInfo *root, R *** 5651,5657 **** rel = find_base_rel(root, bms_singleton_member(relids)); break; case BMS_MULTIPLE: ! rel = find_join_rel(root, relids); break; } --- 5685,5691 ---- rel = find_base_rel(root, bms_singleton_member(relids)); break; case BMS_MULTIPLE: ! rel = find_join_rel(root, relids, false); break; } diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c new file mode 100644 index 1db7845..0caa05e *** a/src/backend/utils/misc/guc.c --- b/src/backend/utils/misc/guc.c *************** static struct config_bool ConfigureNames *** 923,928 **** --- 923,937 ---- NULL, NULL, NULL }, { + {"enable_agg_pushdown", PGC_USERSET, QUERY_TUNING_METHOD, + gettext_noop("Enables aggregation push-down."), + NULL + }, + &enable_agg_pushdown, + false, + NULL, NULL, NULL + }, + { {"enable_parallel_append", PGC_USERSET, QUERY_TUNING_METHOD, gettext_noop("Enables the planner's use of parallel append plans."), NULL diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h new file mode 100644 index 74b094a..2914fc8 *** a/src/include/nodes/nodes.h --- b/src/include/nodes/nodes.h *************** typedef enum NodeTag *** 218,223 **** --- 218,224 ---- T_IndexOptInfo, T_ForeignKeyOptInfo, T_ParamPathInfo, + T_RelAggInfo, T_Path, T_IndexPath, T_BitmapHeapPath, *************** typedef enum NodeTag *** 258,267 **** --- 259,270 ---- T_PathTarget, T_RestrictInfo, T_PlaceHolderVar, + T_GroupedVar, T_SpecialJoinInfo, T_AppendRelInfo, T_PartitionedChildRelInfo, T_PlaceHolderInfo, + T_GroupedVarInfo, T_MinMaxAggInfo, T_PlannerParamItem, T_RollupData, diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h new file mode 100644 index 1b4b0d7..6af31f2 *** a/src/include/nodes/primnodes.h --- b/src/include/nodes/primnodes.h *************** typedef struct Aggref *** 296,301 **** --- 296,302 ---- Oid aggcollid; /* OID of collation of result */ Oid inputcollid; /* OID of collation that function should use */ Oid aggtranstype; /* type Oid of aggregate's transition value */ + Oid aggcombinefn; /* combine function (see pg_aggregate.h) */ List *aggargtypes; /* type Oids of direct and aggregated args */ List *aggdirectargs; /* direct arguments, if an ordered-set agg */ List *args; /* aggregated arguments and sort expressions */ *************** typedef struct Aggref *** 306,311 **** --- 307,313 ---- bool aggvariadic; /* true if variadic arguments have been * combined into an array last argument */ char aggkind; /* aggregate kind (see pg_aggregate.h) */ + Index agglevelsup; /* > 0 if agg belongs to outer query */ AggSplit aggsplit; /* expected agg-splitting mode of parent Agg */ int location; /* token location, or -1 if unknown */ diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h new file mode 100644 index db8de2d..1f10816 *** a/src/include/nodes/relation.h --- b/src/include/nodes/relation.h *************** typedef struct PlannerInfo *** 179,185 **** * unreferenced view RTE; or if the RelOptInfo hasn't been made yet. */ struct RelOptInfo **simple_rel_array; /* All 1-rel RelOptInfos */ ! int simple_rel_array_size; /* allocated size of array */ /* * simple_rte_array is the same length as simple_rel_array and holds --- 179,193 ---- * unreferenced view RTE; or if the RelOptInfo hasn't been made yet. */ struct RelOptInfo **simple_rel_array; /* All 1-rel RelOptInfos */ ! ! /* ! * The same like simple_rel_array, but for grouped rels. In addition to ! * the meanings explained above, NULL can also mean that the relation ! * cannot be grouped alone, regardless its kind. ! */ ! struct RelOptInfo **simple_grouped_rel_array; /* The same for grouped ! * rels. */ ! int simple_rel_array_size; /* allocated size of the arrays above */ /* * simple_rte_array is the same length as simple_rel_array and holds *************** typedef struct PlannerInfo *** 217,222 **** --- 225,234 ---- List *join_rel_list; /* list of join-relation RelOptInfos */ struct HTAB *join_rel_hash; /* optional hashtable for join relations */ + /* The same for grouped joins. */ + List *join_grouped_rel_list; + struct HTAB *join_grouped_rel_hash; + /* * When doing a dynamic-programming-style join search, join_rel_level[k] * is a list of all join-relation RelOptInfos of level k, and *************** typedef struct PlannerInfo *** 225,230 **** --- 237,244 ---- * join_rel_level is NULL if not in use. */ List **join_rel_level; /* lists of join-relation RelOptInfos */ + List **join_grouped_rel_level; /* lists of grouped join-relation + * RelOptInfos */ int join_cur_level; /* index of list being extended */ List *init_plans; /* init SubPlans for query */ *************** typedef struct PlannerInfo *** 259,264 **** --- 273,280 ---- List *placeholder_list; /* list of PlaceHolderInfos */ + List *grouped_var_list; /* List of GroupedVarInfos. */ + List *fkey_list; /* list of ForeignKeyOptInfos */ List *query_pathkeys; /* desired pathkeys for query_planner() */ *************** typedef struct PlannerInfo *** 285,290 **** --- 301,312 ---- */ List *processed_tlist; + /* + * The maximum ressortgroupref among target entries in processed_list. + * Useful when adding extra grouping expressions for partial aggregation. + */ + int max_sortgroupref; + /* Fields filled during create_plan() for use in setrefs.c */ AttrNumber *grouping_map; /* for GroupingFunc fixup */ List *minmax_aggs; /* List of MinMaxAggInfos */ *************** typedef struct PartitionSchemeData *Part *** 440,445 **** --- 462,469 ---- * direct_lateral_relids - rels this rel has direct LATERAL references to * lateral_relids - required outer rels for LATERAL, as a Relids set * (includes both direct and indirect lateral references) + * gpi - GroupedPathInfo if the relation can produce grouped paths, NULL + * otherwise. * * If the relation is a base relation it will have these fields set: * *************** typedef struct RelOptInfo *** 611,616 **** --- 635,643 ---- Relids direct_lateral_relids; /* rels directly laterally referenced */ Relids lateral_relids; /* minimum parameterization of rel */ + /* Information needed to apply partial aggregation to this rel's paths. */ + struct RelAggInfo *agg_info; + /* information about a base rel (not set for join rels!) */ Index relid; Oid reltablespace; /* containing tablespace */ *************** typedef struct ParamPathInfo *** 1009,1014 **** --- 1036,1088 ---- List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; + /* + * RelAggInfo + * + * RelOptInfo needs information contained here if its paths should be + * partially aggregated. + * + * "target" will be used as pathtarget of grouped paths produced by "explicit + * aggregation" of a relation, but also --- if the relation is a join --- by + * joining grouped path to a non-grouped one. + * + * The target contains plain-Var grouping expressions, generic grouping + * expressions wrapped in GroupedVar structure, or Aggrefs which are also + * wrapped in GroupedVar. Once GroupedVar is evaluated, its value is passed to + * the upper paths w/o being evaluated again. If final aggregation appears to + * be necessary above the final join, the contained Aggrefs are supposed to + * provide the final aggregation plan with input values, i.e. the aggregate + * transient state. + * + * Note: There's a convention that GroupedVars that contain Aggref expressions + * are supposed to follow the other expressions of the target. Iterations of + * target->exprs may rely on this arrangement. + * + * "input" contains Vars used either as grouping expressions or aggregate + * arguments, plus grouping expressions which are not plain vars. Paths + * providing the partial aggregation plan with input data should use this + * target. + * + * "group_clauses" and "group_exprs" are lists of SortGroupClause and the + * corresponding grouping expressions respectively. "agg_exprs" is a list of + * Aggref nodes to be evaluated by the relation. + * + * "rows" is the estimated number of result tuples produced by grouped paths. + */ + typedef struct RelAggInfo + { + NodeTag type; + + PathTarget *target; /* target of grouped paths. */ + PathTarget *input; /* pathtarget of paths that generate input for + * the partial aggregation. */ + + List *group_clauses; + List *group_exprs; + List *agg_exprs; + + double rows; + } RelAggInfo; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other *************** typedef struct HashPath *** 1486,1497 **** --- 1560,1575 ---- * ProjectionPath node, which is marked dummy to indicate that we intend to * assign the work to the input plan node. The estimated cost for the * ProjectionPath node will account for whether a Result will be used or not. + * + * force_result field tells that the Result node must be used for some reason + * even though the subpath could normally handle the projection. */ typedef struct ProjectionPath { Path path; Path *subpath; /* path representing input source */ bool dummypp; /* true if no separate Result is needed */ + bool force_result; /* Is Result node required? */ } ProjectionPath; /* *************** typedef struct PlaceHolderVar *** 1957,1962 **** --- 2035,2065 ---- Index phlevelsup; /* > 0 if PHV belongs to outer query */ } PlaceHolderVar; + + /* + * Similar to the concept of PlaceHolderVar, we treat aggregates and grouping + * columns as special variables if grouping is possible below the top-level + * join. Likewise, the variable is evaluated below the query targetlist (in + * particular, in the targetlist of AGGSPLIT_INITIAL_SERIAL aggregation node + * which has base relation or a join as the input) and bubbles up through the + * join tree until it reaches AGGSPLIT_FINAL_DESERIAL aggregation node. + * + * gvexpr is either Aggref or a generic (non-Var) grouping expression. (If a + * simple Var, we don't replace it with GroupedVar.) + * + * agg_partial also points to the corresponding field of GroupedVarInfo if + * gvexpr is Aggref. + */ + typedef struct GroupedVar + { + Expr xpr; + Expr *gvexpr; /* the represented expression */ + Aggref *agg_partial; /* partial aggregate if gvexpr is aggregate */ + Index sortgroupref; /* SortGroupClause.tleSortGroupRef if gvexpr + * is grouping expression. */ + Index gvid; /* GroupedVarInfo */ + } GroupedVar; + /* * "Special join" info. * *************** typedef struct PartitionedChildRelInfo *** 2131,2138 **** Index parent_relid; List *child_rels; ! bool part_cols_updated; /* is the partition key of any of ! * the partitioned tables updated? */ } PartitionedChildRelInfo; /* --- 2234,2241 ---- Index parent_relid; List *child_rels; ! bool part_cols_updated; /* is the partition key of any of the ! * partitioned tables updated? */ } PartitionedChildRelInfo; /* *************** typedef struct PlaceHolderInfo *** 2174,2179 **** --- 2277,2301 ---- } PlaceHolderInfo; /* + * Likewise, GroupedVarInfo exists for each distinct GroupedVar. + */ + typedef struct GroupedVarInfo + { + NodeTag type; + + Index gvid; /* GroupedVar.gvid */ + Expr *gvexpr; /* the represented expression. */ + Aggref *agg_partial; /* if gvexpr is aggregate, agg_partial is the + * corresponding partial aggregate */ + Index sortgroupref; /* If gvexpr is a grouping expression, this is + * the tleSortGroupRef of the corresponding + * SortGroupClause. */ + Relids gv_eval_at; /* lowest level we can evaluate the expression + * at or NULL if it can happen anywhere. */ + int32 gv_width; /* estimated width of the expression */ + } GroupedVarInfo; + + /* * This struct describes one potentially index-optimizable MIN/MAX aggregate * function. MinMaxAggPath contains a list of these, and if we accept that * path, the list is stored into root->minmax_aggs for use during setrefs.c. diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h new file mode 100644 index ba4fa4b..6901f10 *** a/src/include/optimizer/clauses.h --- b/src/include/optimizer/clauses.h *************** extern Node *estimate_expression_value(P *** 84,88 **** extern Query *inline_set_returning_function(PlannerInfo *root, RangeTblEntry *rte); ! #endif /* CLAUSES_H */ --- 84,89 ---- extern Query *inline_set_returning_function(PlannerInfo *root, RangeTblEntry *rte); ! extern GroupedVarInfo *translate_expression_to_rels(PlannerInfo *root, ! GroupedVarInfo *gvi, Index relid); #endif /* CLAUSES_H */ diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h new file mode 100644 index 132e355..9d56761 *** a/src/include/optimizer/cost.h --- b/src/include/optimizer/cost.h *************** extern PGDLLIMPORT double parallel_tuple *** 54,60 **** extern PGDLLIMPORT double parallel_setup_cost; extern PGDLLIMPORT int effective_cache_size; extern PGDLLIMPORT Cost disable_cost; ! extern PGDLLIMPORT int max_parallel_workers_per_gather; extern PGDLLIMPORT bool enable_seqscan; extern PGDLLIMPORT bool enable_indexscan; extern PGDLLIMPORT bool enable_indexonlyscan; --- 54,60 ---- extern PGDLLIMPORT double parallel_setup_cost; extern PGDLLIMPORT int effective_cache_size; extern PGDLLIMPORT Cost disable_cost; ! extern PGDLLIMPORT int max_parallel_workers_per_gather; extern PGDLLIMPORT bool enable_seqscan; extern PGDLLIMPORT bool enable_indexscan; extern PGDLLIMPORT bool enable_indexonlyscan; *************** extern PGDLLIMPORT bool enable_gathermer *** 70,76 **** extern PGDLLIMPORT bool enable_partitionwise_join; extern PGDLLIMPORT bool enable_parallel_append; extern PGDLLIMPORT bool enable_parallel_hash; ! extern PGDLLIMPORT int constraint_exclusion; extern double clamp_row_est(double nrows); extern double index_pages_fetched(double tuples_fetched, BlockNumber pages, --- 70,77 ---- extern PGDLLIMPORT bool enable_partitionwise_join; extern PGDLLIMPORT bool enable_parallel_append; extern PGDLLIMPORT bool enable_parallel_hash; ! extern PGDLLIMPORT bool enable_agg_pushdown; ! extern PGDLLIMPORT int constraint_exclusion; extern double clamp_row_est(double nrows); extern double index_pages_fetched(double tuples_fetched, BlockNumber pages, diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h new file mode 100644 index ef7173f..8cafd54 *** a/src/include/optimizer/pathnode.h --- b/src/include/optimizer/pathnode.h *************** extern AppendPath *create_append_path(Re *** 71,76 **** --- 71,77 ---- List *partitioned_rels, double rows); extern MergeAppendPath *create_merge_append_path(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, List *subpaths, List *pathkeys, Relids required_outer, *************** extern Relids calc_non_nestloop_required *** 123,128 **** --- 124,130 ---- extern NestPath *create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** extern NestPath *create_nestloop_path(Pl *** 134,139 **** --- 136,142 ---- extern MergePath *create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** extern MergePath *create_mergejoin_path( *** 148,153 **** --- 151,157 ---- extern HashPath *create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, *************** extern AggPath *create_agg_path(PlannerI *** 197,202 **** --- 201,213 ---- List *qual, const AggClauseCosts *aggcosts, double numGroups); + extern AggPath *create_partial_agg_sorted_path(PlannerInfo *root, + Path *subpath, + bool check_pathkeys, + double input_rows); + extern AggPath *create_partial_agg_hashed_path(PlannerInfo *root, + Path *subpath, + double input_rows); extern GroupingSetsPath *create_groupingsets_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, *************** extern void setup_simple_rel_arrays(Plan *** 266,278 **** extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent); extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid); ! extern RelOptInfo *find_join_rel(PlannerInfo *root, Relids relids); extern RelOptInfo *build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, ! List **restrictlist_ptr); extern Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, --- 277,292 ---- extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent); extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid); ! extern RelOptInfo *find_grouped_base_rel(PlannerInfo *root, int relid); ! extern RelOptInfo *find_join_rel(PlannerInfo *root, Relids relids, ! bool grouped); extern RelOptInfo *build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, ! List **restrictlist_ptr, ! bool grouped); extern Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, *************** extern ParamPathInfo *find_param_path_in *** 300,305 **** extern RelOptInfo *build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, ! SpecialJoinInfo *sjinfo, JoinType jointype); ! #endif /* PATHNODE_H */ --- 314,324 ---- extern RelOptInfo *build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, ! SpecialJoinInfo *sjinfo, JoinType jointype, ! bool grouped); ! extern RelAggInfo *create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel); ! extern RelAggInfo *translate_rel_agg_info(PlannerInfo *root, ! RelAggInfo *agg_info, ! AppendRelInfo **appinfos, ! int nappinfos); #endif /* PATHNODE_H */ diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h new file mode 100644 index 94f9bb2..8352899 *** a/src/include/optimizer/paths.h --- b/src/include/optimizer/paths.h *************** *** 21,29 **** * allpaths.c */ extern PGDLLIMPORT bool enable_geqo; ! extern PGDLLIMPORT int geqo_threshold; ! extern PGDLLIMPORT int min_parallel_table_scan_size; ! extern PGDLLIMPORT int min_parallel_index_scan_size; /* Hook for plugins to get control in set_rel_pathlist() */ typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root, --- 21,30 ---- * allpaths.c */ extern PGDLLIMPORT bool enable_geqo; ! extern PGDLLIMPORT bool enable_agg_pushdown; ! extern PGDLLIMPORT int geqo_threshold; ! extern PGDLLIMPORT int min_parallel_table_scan_size; ! extern PGDLLIMPORT int min_parallel_index_scan_size; /* Hook for plugins to get control in set_rel_pathlist() */ typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root, *************** typedef void (*set_join_pathlist_hook_ty *** 41,66 **** JoinPathExtraData *extra); extern PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook; /* Hook for plugins to replace standard_join_search() */ ! typedef RelOptInfo *(*join_search_hook_type) (PlannerInfo *root, ! int levels_needed, ! List *initial_rels); extern PGDLLIMPORT join_search_hook_type join_search_hook; ! extern RelOptInfo *make_one_rel(PlannerInfo *root, List *joinlist); extern void set_dummy_rel_pathlist(RelOptInfo *rel); ! extern RelOptInfo *standard_join_search(PlannerInfo *root, int levels_needed, ! List *initial_rels); extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows); extern int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers); extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual); extern void generate_partitionwise_join_paths(PlannerInfo *root, ! RelOptInfo *rel); #ifdef OPTIMIZER_DEBUG extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel); --- 42,89 ---- JoinPathExtraData *extra); extern PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook; + /* + * Result of standard_join_search() or join_search_hook(). + * + * 'plain' is a join of two plain (non-grouped) relation. + * + * 'grouped' is either a join of one plain relation to one grouped, or a join + * of two plain relations whose (the join relation's) paths have all been + * subject to partial aggregation. + */ + typedef struct JoinSearchResult + { + RelOptInfo *plain; + RelOptInfo *grouped; + } JoinSearchResult; + /* Hook for plugins to replace standard_join_search() */ ! typedef JoinSearchResult *(*join_search_hook_type) (PlannerInfo *root, ! int levels_needed, ! List *initial_rels, ! List *initial_rels_grouped); extern PGDLLIMPORT join_search_hook_type join_search_hook; ! extern JoinSearchResult *make_one_rel(PlannerInfo *root, List *joinlist); extern void set_dummy_rel_pathlist(RelOptInfo *rel); ! extern JoinSearchResult *standard_join_search(PlannerInfo *root, ! int levels_needed, ! List *initial_rels, ! List *initial_rels_grouped); extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows); + + extern bool create_grouped_path(PlannerInfo *root, RelOptInfo *rel, + Path *subpath, bool precheck, + bool partial, AggStrategy aggstrategy); extern int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers); extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual); extern void generate_partitionwise_join_paths(PlannerInfo *root, ! RelOptInfo *rel); #ifdef OPTIMIZER_DEBUG extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel); *************** extern Expr *adjust_rowcompare_for_index *** 92,98 **** * tidpath.h * routines to generate tid paths */ ! extern void create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel); /* * joinpath.c --- 115,122 ---- * tidpath.h * routines to generate tid paths */ ! extern void create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel, ! bool grouped); /* * joinpath.c *************** extern void create_tidscan_paths(Planner *** 101,114 **** extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, ! List *restrictlist); /* * joinrels.c * routines to determine which relations to join */ extern void join_search_one_level(PlannerInfo *root, int level); ! extern RelOptInfo *make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); extern bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); --- 125,138 ---- extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, ! List *restrictlist, bool do_aggregate); /* * joinrels.c * routines to determine which relations to join */ extern void join_search_one_level(PlannerInfo *root, int level); ! extern JoinSearchResult *make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); extern bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h new file mode 100644 index 7132c88..2bd1135 *** a/src/include/optimizer/planmain.h --- b/src/include/optimizer/planmain.h *************** typedef void (*query_pathkeys_callback) *** 38,44 **** * prototypes for plan/planmain.c */ extern RelOptInfo *query_planner(PlannerInfo *root, List *tlist, ! query_pathkeys_callback qp_callback, void *qp_extra); /* * prototypes for plan/planagg.c --- 38,45 ---- * prototypes for plan/planmain.c */ extern RelOptInfo *query_planner(PlannerInfo *root, List *tlist, ! query_pathkeys_callback qp_callback, void *qp_extra, ! RelOptInfo **partially_grouped); /* * prototypes for plan/planagg.c *************** extern void add_base_rels_to_query(Plann *** 76,81 **** --- 77,84 ---- extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist); extern void add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed, bool create_new_ph); + extern void add_grouped_base_rels_to_query(PlannerInfo *root); + extern void add_grouped_vars_to_rels(PlannerInfo *root); extern void find_lateral_references(PlannerInfo *root); extern void create_lateral_join_info(PlannerInfo *root); extern List *deconstruct_jointree(PlannerInfo *root); diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h new file mode 100644 index 9fa52e1..68c32e1 *** a/src/include/optimizer/tlist.h --- b/src/include/optimizer/tlist.h *************** *** 16,22 **** #include "nodes/relation.h" - extern TargetEntry *tlist_member(Expr *node, List *targetlist); extern TargetEntry *tlist_member_ignore_relabel(Expr *node, List *targetlist); --- 16,21 ---- *************** extern Node *get_sortgroupclause_expr(So *** 41,47 **** List *targetList); extern List *get_sortgrouplist_exprs(List *sgClauses, List *targetList); - extern SortGroupClause *get_sortgroupref_clause(Index sortref, List *clauses); extern SortGroupClause *get_sortgroupref_clause_noerr(Index sortref, --- 40,45 ---- *************** extern void split_pathtarget_at_srfs(Pla *** 65,70 **** --- 63,75 ---- PathTarget *target, PathTarget *input_target, List **targets, List **targets_contain_srfs); + /* TODO Find the best location (position and in some cases even file) for the + * following ones. */ + extern List *replace_grouped_vars_with_aggrefs(PlannerInfo *root, List *src); + extern void add_grouped_vars_to_target(PlannerInfo *root, PathTarget *target, + List *expressions); + extern GroupedVar *get_grouping_expression(List *gvis, Expr *expr); + /* Convenience macro to get a PathTarget with valid cost/width fields */ #define create_pathtarget(root, tlist) \ set_pathtarget_cost_width(root, make_pathtarget_from_tlist(tlist)) diff --git a/src/include/optimizer/var.h b/src/include/optimizer/var.h new file mode 100644 index 43c53b5..5a795c3 *** a/src/include/optimizer/var.h --- b/src/include/optimizer/var.h *************** extern bool contain_vars_of_level(Node * *** 36,40 **** --- 36,42 ---- extern int locate_var_of_level(Node *node, int levelsup); extern List *pull_var_clause(Node *node, int flags); extern Node *flatten_join_alias_vars(PlannerInfo *root, Node *node); + extern GroupedVarInfo *find_grouped_var_info(PlannerInfo *root, + GroupedVar *gvar); #endif /* VAR_H */ diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h new file mode 100644 index 299c9f8..e033a90 *** a/src/include/utils/selfuncs.h --- b/src/include/utils/selfuncs.h *************** extern void estimate_hash_bucket_stats(P *** 210,215 **** --- 210,219 ---- Node *hashkey, double nbuckets, Selectivity *mcv_freq, Selectivity *bucketsize_frac); + extern Size estimate_hashagg_tablesize(Path *path, + const AggClauseCosts *agg_costs, + double dNumGroups); + extern List *deconstruct_indexquals(IndexPath *path); extern void genericcostestimate(PlannerInfo *root, IndexPath *path, diff --git a/src/test/regress/expected/agg_pushdown.out b/src/test/regress/expected/agg_pushdown.out new file mode 100644 index ...09b380d *** a/src/test/regress/expected/agg_pushdown.out --- b/src/test/regress/expected/agg_pushdown.out *************** *** 0 **** --- 1,316 ---- + BEGIN; + CREATE TABLE agg_pushdown_parent ( + i int primary key); + CREATE TABLE agg_pushdown_child1 ( + j int primary key, + parent int references agg_pushdown_parent, + v double precision); + CREATE INDEX ON agg_pushdown_child1(parent); + CREATE TABLE agg_pushdown_child2 ( + k int primary key, + parent int references agg_pushdown_parent, + v double precision); + INSERT INTO agg_pushdown_parent(i) + SELECT n + FROM generate_series(0, 7) AS s(n); + INSERT INTO agg_pushdown_child1(j, parent, v) + SELECT 64 * i + n, i, random() + FROM generate_series(0, 63) AS s(n), agg_pushdown_parent; + INSERT INTO agg_pushdown_child2(k, parent, v) + SELECT 64 * i + n, i, random() + FROM generate_series(0, 63) AS s(n), agg_pushdown_parent; + ANALYZE; + SET enable_agg_pushdown TO on; + -- Perform scan of a table and partially aggregate the result. + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + QUERY PLAN + ------------------------------------------------------------ + Finalize HashAggregate + Group Key: p.i + -> Hash Join + Hash Cond: (p.i = c1.parent) + -> Seq Scan on agg_pushdown_parent p + -> Hash + -> Partial HashAggregate + Group Key: c1.parent + -> Seq Scan on agg_pushdown_child1 c1 + (9 rows) + + -- Scan index on agg_pushdown_child1(parent) column and partially aggregate + -- the result using AGG_SORTED strategy. + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + QUERY PLAN + --------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Nested Loop + -> Partial GroupAggregate + Group Key: c1.parent + -> Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) + (8 rows) + + SET enable_seqscan TO on; + -- Perform nestloop join between agg_pushdown_child1 and agg_pushdown_child2 + -- and partially aggregate the result. + SET enable_nestloop TO on; + SET enable_hashjoin TO off; + SET enable_mergejoin TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + --------------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Sort + Sort Key: p.i + -> Nested Loop + -> Partial HashAggregate + Group Key: c1.parent + -> Nested Loop + -> Seq Scan on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + Index Cond: (k = c1.j) + Filter: (c1.parent = parent) + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) + (14 rows) + + -- The same for hash join. + SET enable_nestloop TO off; + SET enable_hashjoin TO on; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + ---------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Sort + Sort Key: p.i + -> Hash Join + Hash Cond: (p.i = c1.parent) + -> Seq Scan on agg_pushdown_parent p + -> Hash + -> Partial HashAggregate + Group Key: c1.parent + -> Hash Join + Hash Cond: ((c1.parent = c2.parent) AND (c1.j = c2.k)) + -> Seq Scan on agg_pushdown_child1 c1 + -> Hash + -> Seq Scan on agg_pushdown_child2 c2 + (15 rows) + + -- The same for merge join. + SET enable_hashjoin TO off; + SET enable_mergejoin TO on; + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + --------------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: c1.parent + -> Merge Join + Merge Cond: (c1.j = c2.k) + Join Filter: (c1.parent = c2.parent) + -> Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + (14 rows) + + -- Generic grouping expression. + EXPLAIN (COSTS off) + SELECT p.i / 2, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i / 2; + QUERY PLAN + --------------------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: (((c1.parent / 2))) + -> Sort + Sort Key: (((c1.parent / 2))) + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: (c1.parent / 2), c1.parent, c2.parent + -> Merge Join + Merge Cond: (c1.j = c2.k) + Join Filter: (c1.parent = c2.parent) + -> Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + (16 rows) + + -- The same tests for parallel plans. + RESET ALL; + SET parallel_setup_cost TO 0; + SET parallel_tuple_cost TO 0; + SET min_parallel_table_scan_size TO 0; + SET min_parallel_index_scan_size TO 0; + SET max_parallel_workers_per_gather TO 4; + SET enable_agg_pushdown TO on; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + QUERY PLAN + --------------------------------------------------------------------- + Finalize HashAggregate + Group Key: p.i + -> Gather + Workers Planned: 2 + -> Parallel Hash Join + Hash Cond: (c1.parent = p.i) + -> Partial HashAggregate + Group Key: c1.parent + -> Parallel Seq Scan on agg_pushdown_child1 c1 + -> Parallel Hash + -> Parallel Seq Scan on agg_pushdown_parent p + (11 rows) + + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + QUERY PLAN + ------------------------------------------------------------------------------------------------------------ + Finalize GroupAggregate + Group Key: p.i + -> Gather Merge + Workers Planned: 2 + -> Nested Loop + -> Partial GroupAggregate + Group Key: c1.parent + -> Parallel Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) + (10 rows) + + SET enable_seqscan TO on; + SET enable_nestloop TO on; + SET enable_hashjoin TO off; + SET enable_mergejoin TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + --------------------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Gather Merge + Workers Planned: 2 + -> Sort + Sort Key: p.i + -> Nested Loop + -> Partial HashAggregate + Group Key: c1.parent + -> Nested Loop + -> Parallel Seq Scan on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + Index Cond: (k = c1.j) + Filter: (c1.parent = parent) + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) + (16 rows) + + SET enable_nestloop TO off; + SET enable_hashjoin TO on; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + ---------------------------------------------------------------------------------------------- + Finalize GroupAggregate + Group Key: p.i + -> Sort + Sort Key: p.i + -> Gather + Workers Planned: 1 + -> Parallel Hash Join + Hash Cond: (p.i = c1.parent) + -> Parallel Seq Scan on agg_pushdown_parent p + -> Parallel Hash + -> Partial HashAggregate + Group Key: c1.parent + -> Parallel Hash Join + Hash Cond: ((c1.parent = c2.parent) AND (c1.j = c2.k)) + -> Parallel Seq Scan on agg_pushdown_child1 c1 + -> Parallel Hash + -> Parallel Seq Scan on agg_pushdown_child2 c2 + (17 rows) + + SET enable_hashjoin TO off; + SET enable_mergejoin TO on; + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + QUERY PLAN + ------------------------------------------------------------------------------------------------------------------ + Finalize GroupAggregate + Group Key: p.i + -> Gather Merge + Workers Planned: 2 + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: c1.parent + -> Merge Join + Merge Cond: (c1.j = c2.k) + Join Filter: (c1.parent = c2.parent) + -> Parallel Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + (16 rows) + + EXPLAIN (COSTS off) + SELECT p.i / 2, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i / 2; + QUERY PLAN + ------------------------------------------------------------------------------------------------------------------------ + Finalize GroupAggregate + Group Key: (((c1.parent / 2))) + -> Sort + Sort Key: (((c1.parent / 2))) + -> Gather + Workers Planned: 2 + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: (c1.parent / 2), c1.parent, c2.parent + -> Merge Join + Merge Cond: (c1.j = c2.k) + Join Filter: (c1.parent = c2.parent) + -> Parallel Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + (18 rows) + + ROLLBACK; diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out new file mode 100644 index 759f7d9..68d0407 *** a/src/test/regress/expected/sysviews.out --- b/src/test/regress/expected/sysviews.out *************** select count(*) >= 0 as ok from pg_prepa *** 72,77 **** --- 72,78 ---- select name, setting from pg_settings where name like 'enable%'; name | setting ---------------------------+--------- + enable_agg_pushdown | off enable_bitmapscan | on enable_gathermerge | on enable_hashagg | on *************** select name, setting from pg_settings wh *** 87,93 **** enable_seqscan | on enable_sort | on enable_tidscan | on ! (15 rows) -- Test that the pg_timezone_names and pg_timezone_abbrevs views are -- more-or-less working. We can't test their contents in any great detail --- 88,94 ---- enable_seqscan | on enable_sort | on enable_tidscan | on ! (16 rows) -- Test that the pg_timezone_names and pg_timezone_abbrevs views are -- more-or-less working. We can't test their contents in any great detail diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule new file mode 100644 index ad9434f..611aeb4 *** a/src/test/regress/parallel_schedule --- b/src/test/regress/parallel_schedule *************** test: rules psql_crosstab amutils *** 98,103 **** --- 98,106 ---- test: select_parallel test: write_parallel + # this one runs parallel workers too + test: agg_pushdown + # no relation related tests can be put in this group test: publication subscription diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule new file mode 100644 index 27cd498..fe8108e *** a/src/test/regress/serial_schedule --- b/src/test/regress/serial_schedule *************** test: rules *** 137,142 **** --- 137,143 ---- test: psql_crosstab test: select_parallel test: write_parallel + test: agg_pushdown test: publication test: subscription test: amutils diff --git a/src/test/regress/sql/agg_pushdown.sql b/src/test/regress/sql/agg_pushdown.sql new file mode 100644 index ...05e2f55 *** a/src/test/regress/sql/agg_pushdown.sql --- b/src/test/regress/sql/agg_pushdown.sql *************** *** 0 **** --- 1,137 ---- + BEGIN; + + CREATE TABLE agg_pushdown_parent ( + i int primary key); + + CREATE TABLE agg_pushdown_child1 ( + j int primary key, + parent int references agg_pushdown_parent, + v double precision); + + CREATE INDEX ON agg_pushdown_child1(parent); + + CREATE TABLE agg_pushdown_child2 ( + k int primary key, + parent int references agg_pushdown_parent, + v double precision); + + INSERT INTO agg_pushdown_parent(i) + SELECT n + FROM generate_series(0, 7) AS s(n); + + INSERT INTO agg_pushdown_child1(j, parent, v) + SELECT 64 * i + n, i, random() + FROM generate_series(0, 63) AS s(n), agg_pushdown_parent; + + INSERT INTO agg_pushdown_child2(k, parent, v) + SELECT 64 * i + n, i, random() + FROM generate_series(0, 63) AS s(n), agg_pushdown_parent; + + ANALYZE; + + SET enable_agg_pushdown TO on; + + -- Perform scan of a table and partially aggregate the result. + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + + -- Scan index on agg_pushdown_child1(parent) column and partially aggregate + -- the result using AGG_SORTED strategy. + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + + SET enable_seqscan TO on; + + -- Perform nestloop join between agg_pushdown_child1 and agg_pushdown_child2 + -- and partially aggregate the result. + SET enable_nestloop TO on; + SET enable_hashjoin TO off; + SET enable_mergejoin TO off; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + -- The same for hash join. + SET enable_nestloop TO off; + SET enable_hashjoin TO on; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + -- The same for merge join. + SET enable_hashjoin TO off; + SET enable_mergejoin TO on; + SET enable_seqscan TO off; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + -- Generic grouping expression. + EXPLAIN (COSTS off) + SELECT p.i / 2, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i / 2; + + -- The same tests for parallel plans. + RESET ALL; + + SET parallel_setup_cost TO 0; + SET parallel_tuple_cost TO 0; + SET min_parallel_table_scan_size TO 0; + SET min_parallel_index_scan_size TO 0; + SET max_parallel_workers_per_gather TO 4; + + SET enable_agg_pushdown TO on; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + + SET enable_seqscan TO off; + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 + AS c1 ON c1.parent = p.i GROUP BY p.i; + + SET enable_seqscan TO on; + + SET enable_nestloop TO on; + SET enable_hashjoin TO off; + SET enable_mergejoin TO off; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + SET enable_nestloop TO off; + SET enable_hashjoin TO on; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + SET enable_hashjoin TO off; + SET enable_mergejoin TO on; + SET enable_seqscan TO off; + + EXPLAIN (COSTS off) + SELECT p.i, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; + + EXPLAIN (COSTS off) + SELECT p.i / 2, avg(c1.v + c2.v) FROM agg_pushdown_parent AS p JOIN + agg_pushdown_child1 AS c1 ON c1.parent = p.i JOIN agg_pushdown_child2 AS c2 ON + c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i / 2; + + ROLLBACK; --=-=-=--