diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index 2fd1a96269..db97bd254d 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -1186,14 +1186,34 @@ Thus the join above the partial aggregate node receives fewer input rows, and so the number of outer-to-inner pairs of tuples to be checked can be significantly lower, which can in turn lead to considerably lower join cost. -Note that there's often no GROUP BY expression to be used for the partial -aggregation, so we use equivalence classes to derive grouping expression: in -the example above, the grouping key "b.j" was derived from "a.i". - -Also note that in this case the partial aggregate uses the "b.j" as grouping -column although the column does not appear in the query target list. The point -is that "b.j" is needed to evaluate the join condition, and there's no other -way for the partial aggregate to emit its values. +Note that the GROUP BY expression might not be useful for the partial +aggregate. In the example above, the aggregate avg(b.y) references table "b", +but the GROUP BY expression mentions "a". However, the equivalence class {a.i, +b.j} allows us to use the b.j column as a grouping key for the partial +aggregation of the "b" table. The equivalence class mechanism is suitable +because it's designed to derive join clauses, and at the same time the join +clauses determine the choice of grouping columns of the partial aggregate: the +only way for the partial aggregate to provide upper join(s) with input values +is to have the join input expression(s) in the grouping key: besides grouping +columns, the partial aggregate can only produce the transient states of the +aggregate functions, but aggregate functions cannot be referenced by the JOIN +clauses. + +Regarding correctness, join node considers the output of the partial aggregate +to be equivalent to the output of a plain (non-aggregated) relation scan. That +is, a group (i.e. a row of the partial aggregate output) matches the other +side of the join if and only if each row of the non-aggregate relation +does. In other words, all rows belonging to the same group have the same value +of the join columns (As mentioned above, a join cannot reference other output +expressions of the partial aggregate than the grouping expressions.). + +However, there's a restriction from the aggregate's perspective: the aggregate +cannot be pushed down if any column referenced by either grouping expression +or aggregate function can be set to NULL by an outer join above the relation +to which we want to apply the partiall aggregation. The point is that those +NULL values would not appear on the input of the pushed-down aggregate, so it could +either put the rows into groups in a different way than the aggregate at the +top of the plan, or it could compute wrong values of the aggregate functions. Besides base relation, the aggregation can also be pushed down to join: diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 32b3dedc71..50f0cf8365 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -197,8 +197,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) * Now that the sizes are known, we can estimate the sizes of the grouped * relations. */ - if (root->grouped_var_list) - setup_base_grouped_rels(root); + setup_base_grouped_rels(root); /* * We should now have size estimates for every actual table involved in @@ -341,7 +340,7 @@ set_base_rel_sizes(PlannerInfo *root) } /* - * setup_based_grouped_rels + * setup_base_grouped_rels * For each "plain" relation build a grouped relation if aggregate pushdown * is possible and if this relation is suitable for partial aggregation. */ @@ -350,6 +349,11 @@ setup_base_grouped_rels(PlannerInfo *root) { Index rti; + /* If there are no grouping expressions, no aggregate push-down. */ + if (!root->grouped_var_list) + return; + + for (rti = 1; rti < root->simple_rel_array_size; rti++) { RelOptInfo *brel = root->simple_rel_array[rti]; @@ -362,6 +366,10 @@ setup_base_grouped_rels(PlannerInfo *root) Assert(brel->relid == rti); /* sanity check on array */ + /* ignore RTEs that are "other rels" */ + if (brel->reloptkind != RELOPT_BASEREL) + continue; + /* * The aggregate push-down feature only makes sense if there are * multiple base rels in the query. @@ -369,16 +377,13 @@ setup_base_grouped_rels(PlannerInfo *root) if (!bms_nonempty_difference(root->all_baserels, brel->relids)) continue; - /* ignore RTEs that are "other rels" */ - if (brel->reloptkind != RELOPT_BASEREL) + rel_grouped = build_simple_grouped_rel(root, brel->relid, &agg_info); + /* Couldn't any aggregate be pushed down to this relation? */ + if (!rel_grouped) continue; - rel_grouped = build_simple_grouped_rel(root, brel->relid, &agg_info); - if (rel_grouped) - { - /* Make the relation available for joining. */ - add_grouped_rel(root, rel_grouped, agg_info); - } + /* Make the relation available for joining. */ + add_grouped_rel(root, rel_grouped, agg_info); } } @@ -554,21 +559,8 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, } else { - RelOptInfo *rel_grouped; - RelAggInfo *agg_info; - /* Plain relation */ set_plain_rel_pathlist(root, rel, rte); - - /* Add paths to the grouped relation if one exists. */ - rel_grouped = find_grouped_rel(root, rel->relids, - &agg_info); - if (rel_grouped) - { - generate_grouping_paths(root, rel_grouped, rel, - agg_info); - set_cheapest(rel_grouped); - } } break; case RTE_SUBQUERY: @@ -836,6 +828,8 @@ static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { Relids required_outer; + RelOptInfo *rel_grouped; + RelAggInfo *agg_info; /* * We don't support pushing join clauses into the quals of a seqscan, but @@ -856,6 +850,14 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* Consider TID scans */ create_tidscan_paths(root, rel); + + /* Add paths to the grouped relation if one exists. */ + rel_grouped = find_grouped_rel(root, rel->relids, &agg_info); + if (!rel_grouped) + return; + + generate_grouping_paths(root, rel_grouped, rel, agg_info); + set_cheapest(rel_grouped); } /* @@ -3428,14 +3430,19 @@ add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, else elog(ERROR, "unexpected strategy %d", aggstrategy); + /* + * Bail out if we failed to create a suitable aggregated path. This can + * happen e.g. then the path does not support hashing (for AGG_HASHED), + * or when the input path is not sorted. + */ + if (agg_path == NULL) + return; + /* Add the grouped path to the list of grouped base paths. */ - if (agg_path != NULL) - { - if (!partial) - add_path(rel, (Path *) agg_path); - else - add_partial_path(rel, (Path *) agg_path); - } + if (!partial) + add_path(rel, (Path *) agg_path); + else + add_partial_path(rel, (Path *) agg_path); } /* @@ -3579,7 +3586,6 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) for (lev = 2; lev <= levels_needed; lev++) { - RelOptInfo *rel_grouped; ListCell *lc; /* @@ -3601,6 +3607,8 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) */ foreach(lc, root->join_rel_level[lev]) { + RelOptInfo *rel_grouped; + rel = (RelOptInfo *) lfirst(lc); /* Create paths for partitionwise joins. */ diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index b34ad90d08..4688f561f0 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -4999,6 +4999,7 @@ set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel) 0, JOIN_INNER, NULL); + rel->rows = clamp_row_est(nrows); cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root); diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 8e913c92d8..8dc39765f2 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -355,7 +355,8 @@ create_aggregate_grouped_var_infos(PlannerInfo *root) Assert(root->grouped_var_list == NIL); tlist_exprs = pull_var_clause((Node *) root->processed_tlist, - PVC_INCLUDE_AGGREGATES); + PVC_INCLUDE_AGGREGATES | + PVC_RECURSE_WINDOWFUNCS); /* * Although GroupingFunc is related to root->parse->groupingSets, this diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 0ada3ba3eb..3292b4b419 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -6847,6 +6847,12 @@ create_partial_grouping_paths(PlannerInfo *root, * push-down. */ partially_grouped_rel = find_grouped_rel(root, input_rel->relids, NULL); + + /* + * If the relation already exists, it must have been created by aggregate + * pushdown. We can't check how exactly it got created, but we can at + * least check that aggregate pushdown is enabled. + */ Assert(enable_agg_pushdown || partially_grouped_rel == NULL); /* @@ -6871,17 +6877,25 @@ create_partial_grouping_paths(PlannerInfo *root, /* * If we can't partially aggregate partial paths, and we can't partially * aggregate non-partial paths, then don't bother creating the new - * RelOptInfo at all, unless the caller specified force_rel_creation. + * RelOptInfo at all, unless the caller specified force_rel_creation. However */ if (cheapest_total_path == NULL && cheapest_partial_path == NULL && - !force_rel_creation && - partially_grouped_rel == NULL) - return NULL; + !force_rel_creation) + { + /* + * If partially_grouped_rel exists, it should contain paths generated + * by the aggregate push-down feature, so the caller is interested in + * it. + */ + return partially_grouped_rel; + } /* * Build a new upper relation to represent the result of partially - * aggregating the rows from the input relation. + * aggregating the rows from the input relation. The relation may already + * exist due to aggregate pushdown, in which case we don't need to create + * it. */ if (partially_grouped_rel == NULL) partially_grouped_rel = fetch_upper_rel(root, @@ -6903,6 +6917,11 @@ create_partial_grouping_paths(PlannerInfo *root, * * If the target was already created for the sake of aggregate push-down, * it should be compatible with what we'd create here. + * + * XXX If fetch_upper_rel() had to create a new relation (i.e. aggregate + * push-down generated no paths), it created an empty target. Should we + * change the convention and have it assign NULL to reltarget instead? Or + * should we introduce a function like is_pathtarget_empty()? */ if (partially_grouped_rel->reltarget->exprs == NIL) partially_grouped_rel->reltarget = diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 7025ebf94b..2627e2f252 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -3163,6 +3163,9 @@ create_agg_path(PlannerInfo *root, } /* + * create_agg_sorted_path + * Creates a pathnode performing sorted aggregation/grouping + * * Apply AGG_SORTED aggregation path to subpath if it's suitably sorted. * * NULL is returned if sorting of subpath output is not suitable. @@ -3176,45 +3179,32 @@ create_agg_sorted_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, AggClauseCosts agg_costs; PathTarget *target; double dNumGroups; - ListCell *lc1; - List *key_subset = NIL; AggPath *result = NULL; aggsplit = AGGSPLIT_INITIAL_SERIAL; agg_exprs = agg_info->agg_exprs; target = agg_info->target; - if (subpath->pathkeys == NIL) - return NULL; - - if (!grouping_is_sortable(root->parse->groupClause)) + /* group_pathkeys are necessary to evaluate the sorting. */ + if (agg_info->group_pathkeys == NIL) return NULL; /* - * Find all query pathkeys that our relation does affect. + * The input path must be sorted in a specific way, but if it's not sorted + * at all, it's not useful for AGG_SORTED. */ - 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 (subpath->pathkeys == NIL) + return NULL; - if (key_subset == NIL) + /* Are the grouping clauses suitable for sorted aggregation? */ + if (!grouping_is_sortable(agg_info->group_clauses)) return NULL; - /* Check if AGG_SORTED is useful for the whole query. */ - if (!pathkeys_contained_in(key_subset, subpath->pathkeys)) + /* + * Is the input path sorted enough for this grouping? TODO Consider using + * incremental sort if the sorting is "almost sufficient". + */ + if (!pathkeys_contained_in(agg_info->group_pathkeys, subpath->pathkeys)) return NULL; MemSet(&agg_costs, 0, sizeof(AggClauseCosts)); @@ -3231,7 +3221,7 @@ create_agg_sorted_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, result = create_agg_path(root, rel, subpath, target, AGG_SORTED, aggsplit, agg_info->group_clauses, - NIL, + NIL, /* qual for HAVING clause */ &agg_costs, dNumGroups); @@ -3254,7 +3244,6 @@ create_agg_hashed_path(PlannerInfo *root, RelOptInfo *rel, AggClauseCosts agg_costs; PathTarget *target; double dNumGroups; - double hashaggtablesize; Query *parse = root->parse; AggPath *result = NULL; @@ -3279,25 +3268,18 @@ create_agg_hashed_path(PlannerInfo *root, RelOptInfo *rel, dNumGroups = estimate_num_groups(root, agg_info->group_exprs, subpath->rows, NULL, NULL); - hashaggtablesize = estimate_hashagg_tablesize(root, subpath, - &agg_costs, - dNumGroups); - - if (hashaggtablesize < work_mem * 1024L) - { - /* - * qual is NIL because the HAVING clause cannot be evaluated until - * the final value of the aggregate is known. - */ - result = create_agg_path(root, rel, subpath, - target, - AGG_HASHED, - aggsplit, - agg_info->group_clauses, - NIL, - &agg_costs, - dNumGroups); - } + /* + * qual is NIL because the HAVING clause cannot be evaluated until the + * final value of the aggregate is known. + */ + result = create_agg_path(root, rel, subpath, + target, + AGG_HASHED, + aggsplit, + agg_info->group_clauses, + NIL, /* qual for HAVING clause */ + &agg_costs, + dNumGroups); } return result; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index ce2e267e91..fcec58f10a 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -2330,15 +2330,16 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) List *grp_exprs_extra = NIL; List *group_clauses_final; int i; + bool pk_found, pk_missing; /* * The function shouldn't have been called if there's no opportunity for - * aggregation push-down. + * aggregate push-down. */ Assert(root->grouped_var_list != NIL); /* - * The current implementation of aggregation push-down cannot handle + * The current implementation of aggregate push-down cannot handle * PlaceHolderVar (PHV). * * If we knew that the PHV should be evaluated in this target (and of @@ -2608,11 +2609,13 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) */ i = 0; result = makeNode(RelAggInfo); + pk_missing = false; foreach(lc, target->exprs) { Index sortgroupref = 0; SortGroupClause *cl; Expr *texpr; + ListCell *lc2; texpr = (Expr *) lfirst(lc); @@ -2631,9 +2634,9 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) /* * 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. + * other reason to be there than 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; @@ -2654,6 +2657,52 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) */ result->group_exprs = list_append_unique(result->group_exprs, texpr); + + /* + * Try to find PathKey for the expression, but don't if we already saw + * an expression w/o the PathKey. + */ + if (pk_missing) + continue; + + pk_found = false; + foreach(lc2, root->group_pathkeys) + { + PathKey *pkey = lfirst_node(PathKey, lc2); + EquivalenceClass *ec = pkey->pk_eclass; + ListCell *lc3; + + foreach(lc3, ec->ec_members) + { + EquivalenceMember *em = lfirst_node(EquivalenceMember, lc3); + + if (equal(texpr, em->em_expr)) + { + result->group_pathkeys = lappend(result->group_pathkeys, + pkey); + pk_found = true; + break; + } + } + if (pk_found) + break; + } + + /* + * If no PathKey was found, the expression was probably generated out + * of grp_exprs_extra. If we don't have a single PathKey, + * group_pathkeys is not useful, so clear it. + */ + if (!pk_found) + { + list_free(result->group_pathkeys); + result->group_pathkeys = NIL; + /* + * Do not spend cycles looking for the PathKey for other + * expressions. + */ + pk_missing = true; + } } /* diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample index 89f944d83a..310c5ff774 100644 --- a/src/backend/utils/misc/postgresql.conf.sample +++ b/src/backend/utils/misc/postgresql.conf.sample @@ -389,6 +389,7 @@ #enable_seqscan = on #enable_sort = on #enable_tidscan = on +#enable_agg_pushdown = on # - Planner Cost Constants - diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 07459c423f..38e105b6de 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1065,8 +1065,9 @@ typedef struct RelOptInfo * actually just a workspace for users of the structure, i.e. not initialized * when instance of the structure is created. * - * "group_clauses" and "group_exprs" are lists of SortGroupClause and the - * corresponding grouping expressions respectively. + * "group_clauses", "group_exprs" and "group_pathkeys" are lists of + * SortGroupClause, the corresponding grouping expressions and PathKey + * respectively. * * "agg_exprs" is a list of Aggref nodes for the aggregation of the relation's * paths. @@ -1090,6 +1091,7 @@ typedef struct RelAggInfo List *group_clauses; List *group_exprs; + List *group_pathkeys; List *agg_exprs; /* Aggref expressions. */ diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out index 442f7f9b41..da67f3a901 100644 --- a/src/test/regress/expected/sysviews.out +++ b/src/test/regress/expected/sysviews.out @@ -111,7 +111,7 @@ select count(*) = 0 as ok from pg_stat_wal_receiver; select name, setting from pg_settings where name like 'enable%'; name | setting --------------------------------+--------- - enable_agg_pushdown | off + enable_agg_pushdown | on enable_async_append | on enable_bitmapscan | on enable_gathermerge | on