diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 7fcac81e2e..5752eba563 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -665,7 +665,7 @@ postgresGetForeignRelSize(PlannerInfo *root, } /* Estimate baserel size as best we can with local statistics. */ - set_baserel_size_estimates(root, baserel); + set_baserel_size_estimates(root, baserel, NULL); /* Fill in basically-bogus cost estimates for use later. */ estimate_path_cost_size(root, baserel, NIL, NIL, @@ -2068,7 +2068,10 @@ postgresPlanDirectModify(PlannerInfo *root, /* Safe to fetch data about the target foreign rel */ if (fscan->scan.scanrelid == 0) { - foreignrel = find_join_rel(root, fscan->fs_relids); + RelOptInfoSet *foreignrelset; + + foreignrelset = find_join_rel(root, fscan->fs_relids); + foreignrel = foreignrelset->rel_plain; /* We should have a rel for this foreign join. */ Assert(foreignrel); } diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index b44ead269f..eabea5dce1 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -2198,8 +2198,8 @@ _copyOnConflictExpr(const OnConflictExpr *from) /* **************************************************************** * pathnodes.h copy functions * - * We don't support copying RelOptInfo, IndexOptInfo, or Path nodes. - * There are some subsidiary structs that are useful to copy, though. + * We don't support copying RelOptInfo, IndexOptInfo, RelAggInfo or Path + * nodes. There are some subsidiary structs that are useful to copy, though. * **************************************************************** */ @@ -2340,6 +2340,20 @@ _copyPlaceHolderInfo(const PlaceHolderInfo *from) return newnode; } +static GroupedVarInfo * +_copyGroupedVarInfo(const GroupedVarInfo *from) +{ + GroupedVarInfo *newnode = makeNode(GroupedVarInfo); + + COPY_NODE_FIELD(gvexpr); + COPY_NODE_FIELD(agg_partial); + COPY_SCALAR_FIELD(sortgroupref); + COPY_SCALAR_FIELD(gv_eval_at); + COPY_SCALAR_FIELD(derived); + + return newnode; +} + /* **************************************************************** * parsenodes.h copy functions * **************************************************************** @@ -5108,6 +5122,9 @@ copyObjectImpl(const void *from) case T_PlaceHolderInfo: retval = _copyPlaceHolderInfo(from); break; + case T_GroupedVarInfo: + retval = _copyGroupedVarInfo(from); + break; /* * VALUE NODES diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index f97cf37f1f..a859d60f43 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -2198,6 +2198,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(append_rel_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); @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) 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"); @@ -2415,6 +2417,22 @@ _outParamPathInfo(StringInfo str, const ParamPathInfo *node) WRITE_NODE_FIELD(ppi_clauses); } +/* + * Note we do NOT print plain_rel, else we'd be in infinite recursion. + */ +static void +_outRelAggInfo(StringInfo str, const RelAggInfo *node) +{ + WRITE_NODE_TYPE("RELAGGINFO"); + + WRITE_NODE_FIELD(target); + WRITE_NODE_FIELD(input); + WRITE_FLOAT_FIELD(input_rows, "%.0f"); + WRITE_NODE_FIELD(group_clauses); + WRITE_NODE_FIELD(group_exprs); + WRITE_NODE_FIELD(agg_exprs); +} + static void _outRestrictInfo(StringInfo str, const RestrictInfo *node) { @@ -2503,6 +2521,18 @@ _outPlaceHolderInfo(StringInfo str, const PlaceHolderInfo *node) } static void +_outGroupedVarInfo(StringInfo str, const GroupedVarInfo *node) +{ + WRITE_NODE_TYPE("GROUPEDVARINFO"); + + WRITE_NODE_FIELD(gvexpr); + WRITE_NODE_FIELD(agg_partial); + WRITE_UINT_FIELD(sortgroupref); + WRITE_BITMAPSET_FIELD(gv_eval_at); + WRITE_BOOL_FIELD(derived); +} + +static void _outMinMaxAggInfo(StringInfo str, const MinMaxAggInfo *node) { WRITE_NODE_TYPE("MINMAXAGGINFO"); @@ -4041,6 +4071,9 @@ outNode(StringInfo str, const void *obj) case T_ParamPathInfo: _outParamPathInfo(str, obj); break; + case T_RelAggInfo: + _outRelAggInfo(str, obj); + break; case T_RestrictInfo: _outRestrictInfo(str, obj); break; @@ -4056,6 +4089,9 @@ outNode(StringInfo str, const void *obj) 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/optimizer/README b/src/backend/optimizer/README index 89ce373d5e..4633fb8768 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -1127,3 +1127,90 @@ breaking down aggregation or grouping over a partitioned relation into aggregation or grouping over its partitions is called partitionwise aggregation. Especially when the partition keys match the GROUP BY clause, this can be significantly faster than the regular method. + +Aggregate push-down +------------------- + +The obvious way to evaluate aggregates is to evaluate the FROM clause of the +SQL query (this is what query_planner does) and use the resuing paths as the +input of Agg node. However, if the groups are large enough, it may be more +efficient to apply the partial aggregation to the output of base relation +scan, and finalize it when we have all relations of the query joined: + + EXPLAIN + SELECT a.i, avg(b.u) + FROM a JOIN b ON b.j = a.i + GROUP BY a.i; + + Finalize HashAggregate + Group Key: a.i + -> Nested Loop + -> Partial HashAggregate + Group Key: b.j + -> Seq Scan on b + -> Index Only Scan using a_pkey on a + Index Cond: (i = b.j) + +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". + +Furthermore, extra grouping columns can be added to the partial Agg node if a +join clause above that node references a column which is not in the query +GROUP BY clause and which could not be derived using equivalence class. + + EXPLAIN + SELECT a.i, avg(b.u) + FROM a JOIN b ON b.j = a.x + GROUP BY a.i; + + Finalize HashAggregate + Group Key: a.i + -> Hash Join + Hash Cond: (a.x = b.j) + -> Seq Scan on a + -> Hash + -> Partial HashAggregate + Group Key: b.j + -> Seq Scan on b + +Here the partial aggregate uses "b.j" as grouping column although it's not in +the same equivalence class as "a.i". Note that no column of the {a.x, b.j} +equivalence class is used as a key for the final aggregation. + +Besides base relation, the aggregation can also be pushed down to join: + + EXPLAIN + SELECT a.i, avg(b.u + c.v) + FROM a JOIN b ON b.j = a.i + JOIN c ON c.k = a.i + WHERE b.j = c.k GROUP BY a.i; + + Finalize HashAggregate + Group Key: a.i + -> Hash Join + Hash Cond: (b.j = a.i) + -> Partial HashAggregate + Group Key: b.j + -> Hash Join + Hash Cond: (b.j = c.k) + -> Seq Scan on b + -> Hash + -> Seq Scan on c + -> Hash + -> Seq Scan on a + +Whether the Agg node is created out of base relation or out of join, it's +added to a separate RelOptInfo that we call "grouped relation". Grouped +relation can be joined to a non-grouped relation, which results in a grouped +relation too. Join of two grouped relations does not seem to be very useful +and is currently not supported. + +If query_planner produces a grouped relation that contains valid paths, these +are simply added to the UPPERREL_PARTIAL_GROUP_AGG relation. Further +processing of these paths then does not differ from processing of other +partially grouped paths. diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index e07bab831e..4beac45fdf 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -182,13 +182,15 @@ gimme_tree(PlannerInfo *root, Gene *tour, int num_gene) for (rel_count = 0; rel_count < num_gene; rel_count++) { int cur_rel_index; + RelOptInfoSet *cur_relset; RelOptInfo *cur_rel; Clump *cur_clump; /* Get the next input relation */ cur_rel_index = (int) tour[rel_count]; - cur_rel = (RelOptInfo *) list_nth(private->initial_rels, - cur_rel_index - 1); + cur_relset = (RelOptInfoSet *) list_nth(private->initial_rels, + cur_rel_index - 1); + cur_rel = cur_relset->rel_plain; /* Make it into a single-rel clump */ cur_clump = (Clump *) palloc(sizeof(Clump)); @@ -251,16 +253,24 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, desirable_join(root, old_clump->joinrel, new_clump->joinrel)) { RelOptInfo *joinrel; + RelOptInfoSet *oldset, + *newset; /* * Construct a RelOptInfo representing the join of these two input * relations. Note that we expect the joinrel not to exist in * root->join_rel_list yet, and so the paths constructed for it * will only include the ones we want. + * + * TODO Consider using make_join_rel_common() (possibly renamed) + * here instead of wrapping the joinrels into RelOptInfoSet. */ - joinrel = make_join_rel(root, - old_clump->joinrel, - new_clump->joinrel); + oldset = makeNode(RelOptInfoSet); + oldset->rel_plain = old_clump->joinrel; + newset = makeNode(RelOptInfoSet); + newset->rel_plain = new_clump->joinrel; + + joinrel = make_join_rel(root, oldset, newset); /* Keep searching if join order is not valid */ if (joinrel) diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c index dc51829dec..b4a4f4ff27 100644 --- a/src/backend/optimizer/geqo/geqo_main.c +++ b/src/backend/optimizer/geqo/geqo_main.c @@ -63,7 +63,7 @@ static int gimme_number_generations(int pool_size); * similar to a constrained Traveling Salesman Problem (TSP) */ -RelOptInfo * +RelOptInfoSet * geqo(PlannerInfo *root, int number_of_rels, List *initial_rels) { GeqoPrivateData private; @@ -74,6 +74,7 @@ geqo(PlannerInfo *root, int number_of_rels, List *initial_rels) Pool *pool; int pool_size, number_generations; + RelOptInfoSet *result; #ifdef GEQO_DEBUG int status_interval; @@ -296,7 +297,9 @@ geqo(PlannerInfo *root, int number_of_rels, List *initial_rels) /* ... clear root pointer to our private storage */ root->join_search_private = NULL; - return best_rel; + result = makeNode(RelOptInfoSet); + result->rel_plain = best_rel; + return result; } diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 55b871c02c..7f3ac0a6de 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -59,6 +59,7 @@ typedef struct pushdown_safety_info /* 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; @@ -74,16 +75,18 @@ 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); + Index rti, RangeTblEntry *rte, RelAggInfo *agg_info); static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, - Index rti, RangeTblEntry *rte); + Index rti, RangeTblEntry *rte, + RelOptInfo *rel_grouped, RelAggInfo *agg_info); static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, - RangeTblEntry *rte); + RangeTblEntry *rte, RelAggInfo *agg_info); static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel); static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, - RangeTblEntry *rte); + RangeTblEntry *rte, RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static void set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, @@ -118,10 +121,11 @@ static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, static void set_namedtuplestore_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_result_pathlist(PlannerInfo *root, RelOptInfo *rel, - RangeTblEntry *rte); + RangeTblEntry *rte); static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); -static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist); +static RelOptInfoSet *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, @@ -148,10 +152,10 @@ static bool apply_child_basequals(PlannerInfo *root, RelOptInfo *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 * +RelOptInfoSet * make_one_rel(PlannerInfo *root, List *joinlist) { - RelOptInfo *rel; + RelOptInfoSet *rel; Index rti; double total_pages; @@ -229,7 +233,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) /* * The result should join all and only the query's base rels. */ - Assert(bms_equal(rel->relids, root->all_baserels)); + Assert(bms_equal(rel->rel_plain->relids, root->all_baserels)); return rel; } @@ -320,7 +324,7 @@ set_base_rel_sizes(PlannerInfo *root) if (root->glob->parallelModeOK) set_rel_consider_parallel(root, rel, rte); - set_rel_size(root, rel, rti, rte); + set_rel_size(root, rel, rti, rte, NULL); } } @@ -349,18 +353,29 @@ set_base_rel_pathlists(PlannerInfo *root) if (rel->reloptkind != RELOPT_BASEREL) continue; - set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]); + set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti], + NULL, NULL); } } /* * set_rel_size * Set size estimates for a base relation + * + * If "agg_info" is passed, it means that "rel" is a grouped relation for + * which "agg_info" provides the information needed for size estimate. */ static void set_rel_size(PlannerInfo *root, RelOptInfo *rel, - Index rti, RangeTblEntry *rte) + Index rti, RangeTblEntry *rte, RelAggInfo *agg_info) { + bool grouped = agg_info != NULL; + + /* + * Aggregate push-down is currently used only for relations. + */ + Assert(!grouped || rte->rtekind == RTE_RELATION); + if (rel->reloptkind == RELOPT_BASEREL && relation_excluded_by_constraints(root, rel, rte)) { @@ -379,7 +394,13 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel, } else if (rte->inh) { - /* It's an "append relation", process accordingly */ + /* + * It's an "append relation", process accordingly. + * + * The aggregate push-down feature currently does not support grouped + * append relation. + */ + Assert(!grouped); set_append_rel_size(root, rel, rti, rte); } else @@ -389,7 +410,12 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel, case RTE_RELATION: if (rte->relkind == RELKIND_FOREIGN_TABLE) { - /* Foreign table */ + /* + * Foreign table + * + * Grouped foreign table is not supported. + */ + Assert(!grouped); set_foreign_size(root, rel, rte); } else if (rte->relkind == RELKIND_PARTITIONED_TABLE) @@ -397,18 +423,27 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel, /* * A partitioned table without any partitions is marked as * a dummy rel. + * + * Grouped partitioned table is not supported. */ + Assert(!grouped); + set_dummy_rel_pathlist(rel); } else if (rte->tablesample != NULL) { - /* Sampled relation */ + /* + * Sampled relation + * + * Grouped tablesample rel is not supported. + */ + Assert(!grouped); set_tablesample_rel_size(root, rel, rte); } else { /* Plain relation */ - set_plain_rel_size(root, rel, rte); + set_plain_rel_size(root, rel, rte, agg_info); } break; case RTE_SUBQUERY: @@ -464,18 +499,49 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel, /* * set_rel_pathlist * Build access paths for a base relation + * + * If "rel_grouped" is passed, apply partial aggregation to each path and add + * the path to this relation instead of "rel". "rel_agg_input" describes the + * aggregation input. "agg_info" must be passed in such a case too. */ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, - Index rti, RangeTblEntry *rte) + Index rti, RangeTblEntry *rte, RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { + bool grouped = rel_grouped != NULL; + + /* + * Aggregate push-down is currently implemented for RTE_RELATION only. + */ + Assert(!grouped || rte->rtekind == RTE_RELATION); + + if (grouped) + { + /* + * Do not apply AggPath if this is the only relation of the query: + * create_grouping_paths() will do so anyway. + */ + if (bms_equal(rel->relids, root->all_baserels)) + { + set_dummy_rel_pathlist(rel_grouped); + return; + } + } + if (IS_DUMMY_REL(rel)) { /* We already proved the relation empty, so nothing more to do */ } else if (rte->inh) { - /* It's an "append relation", process accordingly */ + /* + * It's an "append relation", process accordingly. + * + * The aggregate push-down feature currently does not support append + * relation. + */ + Assert(!grouped); set_append_rel_pathlist(root, rel, rti, rte); } else @@ -485,18 +551,29 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, case RTE_RELATION: if (rte->relkind == RELKIND_FOREIGN_TABLE) { - /* Foreign table */ + /* + * Foreign table + * + * Aggregate push-down not supported. + */ + Assert(!grouped); set_foreign_pathlist(root, rel, rte); } else if (rte->tablesample != NULL) { - /* Sampled relation */ + /* + * Sampled relation. + * + * Aggregate push-down not supported. + */ + Assert(!grouped); set_tablesample_rel_pathlist(root, rel, rte); } else { /* Plain relation */ - set_plain_rel_pathlist(root, rel, rte); + set_plain_rel_pathlist(root, rel, rte, rel_grouped, + agg_info); } break; case RTE_SUBQUERY: @@ -541,9 +618,12 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, * Also, if this is the topmost scan/join rel (that is, the only baserel), * we postpone this until the final scan/join targelist is available (see * grouping_planner). + * + * Note on aggregation push-down: parallel paths are not supported so far. */ if (rel->reloptkind == RELOPT_BASEREL && - bms_membership(root->all_baserels) != BMS_SINGLETON) + bms_membership(root->all_baserels) != BMS_SINGLETON && + !grouped) generate_gather_paths(root, rel, false); /* @@ -552,10 +632,24 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, * add_path(), or delete or modify paths added by the core code. */ if (set_rel_pathlist_hook) - (*set_rel_pathlist_hook) (root, rel, rti, rte); + (*set_rel_pathlist_hook) (root, rel, rti, rte, rel_grouped, + agg_info); + + /* + * The grouped relation is not guaranteed to have any paths. If the + * pathlist is empty, there's no point in calling set_cheapest(). + */ + if (rel_grouped && rel_grouped->pathlist == NIL) + { + set_dummy_rel_pathlist(rel_grouped); + return; + } /* Now find the cheapest of the paths for this rel */ - set_cheapest(rel); + if (!grouped) + set_cheapest(rel); + else + set_cheapest(rel_grouped); #ifdef OPTIMIZER_DEBUG debug_print_rel(root, rel); @@ -565,9 +659,13 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* * set_plain_rel_size * Set size estimates for a plain relation (no subquery, no inheritance) + * + * If "agg_info" is passed, it means that "rel" is a grouped relation for + * which "agg_info" provides the information needed for size estimate. */ static void -set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte, + RelAggInfo *agg_info) { /* * Test any partial indexes of rel for applicability. We must do this @@ -576,7 +674,7 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) check_index_predicates(root, rel); /* Mark rel with estimated output rows, width, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, agg_info); } /* @@ -757,11 +855,19 @@ set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel, /* * set_plain_rel_pathlist * Build access paths for a plain relation (no subquery, no inheritance) + * + * If "rel_grouped" is passed, apply partial aggregation to each path and add + * the path to this relation instead of "rel". "rel_agg_input" describes the + * aggregation input. "agg_info" must be passed in such a case too. */ static void -set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte, RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { Relids required_outer; + Path *seq_path; + bool grouped = rel_grouped != NULL; /* * We don't support pushing join clauses into the quals of a seqscan, but @@ -770,18 +876,38 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) */ required_outer = rel->lateral_relids; - /* Consider sequential scan */ - add_path(rel, create_seqscan_path(root, rel, required_outer, 0)); + /* Consider sequential scan. */ + seq_path = create_seqscan_path(root, rel, required_outer, 0, rel_grouped, + agg_info); + + if (!grouped) + add_path(rel, seq_path); + + /* + * It's probably not good idea to repeat hashed aggregation with different + * parameters, so check if there are no parameters. + */ + else if (required_outer == NULL) + { + /* + * Only AGG_HASHED is suitable here as it does not expect the input + * set to be sorted. + */ + add_grouped_path(root, rel_grouped, seq_path, AGG_HASHED, agg_info); + } /* If appropriate, consider parallel sequential scan */ - if (rel->consider_parallel && required_outer == NULL) + if (rel->consider_parallel && required_outer == NULL && !grouped) create_plain_partial_paths(root, rel); - /* Consider index scans */ - create_index_paths(root, rel); + /* + * Consider index scans, possibly including the grouped paths. + */ + create_index_paths(root, rel, rel_grouped, agg_info); /* Consider TID scans */ - create_tidscan_paths(root, rel); + if (!grouped) + create_tidscan_paths(root, rel); } /* @@ -793,15 +919,55 @@ 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); + 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)); + add_partial_path(rel, create_seqscan_path(root, rel, NULL, + parallel_workers, NULL, NULL)); +} + +/* + * Apply aggregation to a subpath and add the AggPath to the pathlist. + * + * The return value tells whether the path was added to the pathlist. + * + * XXX Pass the plain rel and fetch the grouped from rel->grouped? How about + * subroutines then? + */ +bool +add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, + AggStrategy aggstrategy, RelAggInfo *agg_info) +{ + Path *agg_path; + + /* + * 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); + + if (aggstrategy == AGG_HASHED) + agg_path = (Path *) create_agg_hashed_path(root, subpath, + agg_info); + else if (aggstrategy == AGG_SORTED) + agg_path = (Path *) create_agg_sorted_path(root, subpath, + agg_info); + else + elog(ERROR, "unexpected strategy %d", aggstrategy); + + /* Add the grouped path to the list of grouped base paths. */ + if (agg_path != NULL) + { + add_path(rel, (Path *) agg_path); + + return true; + } + + return false; } /* @@ -841,7 +1007,7 @@ set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) rel->tuples = tuples; /* Mark rel with estimated output rows, width, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -1130,7 +1296,7 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel, /* * Compute the child's size. */ - set_rel_size(root, childrel, childRTindex, childRTE); + set_rel_size(root, childrel, childRTindex, childRTE, NULL); /* * It is possible that constraint exclusion detected a contradiction @@ -1279,7 +1445,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* * Compute the child's access paths. */ - set_rel_pathlist(root, childrel, childRTindex, childRTE); + set_rel_pathlist(root, childrel, childRTindex, childRTE, NULL, NULL); /* * If child is dummy, ignore it. @@ -2569,7 +2735,7 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows) * See comments for deconstruct_jointree() for definition of the joinlist * data structure. */ -static RelOptInfo * +static RelOptInfoSet * make_rel_from_joinlist(PlannerInfo *root, List *joinlist) { int levels_needed; @@ -2595,13 +2761,35 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist) foreach(jl, joinlist) { Node *jlnode = (Node *) lfirst(jl); - RelOptInfo *thisrel; + RelOptInfoSet *thisrel; if (IsA(jlnode, RangeTblRef)) { - int varno = ((RangeTblRef *) jlnode)->rtindex; + RangeTblRef *rtref = castNode(RangeTblRef, jlnode); + int varno = rtref->rtindex; + RangeTblEntry *rte = root->simple_rte_array[varno]; + RelOptInfo *rel_grouped; + + thisrel = makeNode(RelOptInfoSet); + thisrel->rel_plain = find_base_rel(root, varno); - thisrel = find_base_rel(root, varno); + /* + * Create the grouped counterpart of rel_plain if possible. + */ + build_simple_grouped_rel(root, thisrel); + rel_grouped = thisrel->rel_grouped; + + /* + * If succeeded, do what should already have been done for the + * plain relation. + */ + if (rel_grouped) + { + set_rel_size(root, rel_grouped, varno, rte, + thisrel->agg_info); + set_rel_pathlist(root, thisrel->rel_plain, varno, rte, + rel_grouped, thisrel->agg_info); + } } else if (IsA(jlnode, List)) { @@ -2623,7 +2811,7 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist) /* * Single joinlist node, so we're done. */ - return (RelOptInfo *) linitial(initial_rels); + return (RelOptInfoSet *) linitial(initial_rels); } else { @@ -2637,11 +2825,19 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist) root->initial_rels = initial_rels; if (join_search_hook) - return (*join_search_hook) (root, levels_needed, initial_rels); + return (*join_search_hook) (root, levels_needed, + initial_rels); else if (enable_geqo && levels_needed >= geqo_threshold) + { + /* + * TODO Teach GEQO about grouped relations. Don't forget that + * pathlist can be NIL before set_cheapest() gets called. + */ return geqo(root, levels_needed, initial_rels); + } else - return standard_join_search(root, levels_needed, initial_rels); + return standard_join_search(root, levels_needed, + initial_rels); } } @@ -2674,11 +2870,11 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist) * 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 * +RelOptInfoSet * standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) { int lev; - RelOptInfo *rel; + RelOptInfoSet *result; /* * This function cannot be invoked recursively within any one planning @@ -2720,13 +2916,20 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) * * After that, we're done creating paths for the joinrel, so run * set_cheapest(). + * + * Neither partitionwise join nor parallel processing is supported for + * grouped relations so far. */ foreach(lc, root->join_rel_level[lev]) { - rel = (RelOptInfo *) lfirst(lc); + RelOptInfoSet *rel_set; + RelOptInfo *rel_plain; + + rel_set = (RelOptInfoSet *) lfirst(lc); + rel_plain = rel_set->rel_plain; /* Create paths for partitionwise joins. */ - generate_partitionwise_join_paths(root, rel); + generate_partitionwise_join_paths(root, rel_plain); /* * Except for the topmost scan/join rel, consider gathering @@ -2734,10 +2937,33 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) * once we know the final targetlist (see grouping_planner). */ if (lev < levels_needed) - generate_gather_paths(root, rel, false); + generate_gather_paths(root, rel_plain, false); /* Find and save the cheapest paths for this rel */ - set_cheapest(rel); + set_cheapest(rel_plain); + + if (rel_set->rel_grouped) + { + RelOptInfo *rel_grouped; + + rel_grouped = rel_set->rel_grouped; + + /* Partial paths not supported yet. */ + Assert(rel_grouped->partial_pathlist == NIL); + + if (rel_grouped->pathlist != NIL) + set_cheapest(rel_grouped); + else + { + /* + * When checking whether the grouped relation can supply + * any input paths to join, test for existence of the + * relation will be easier than a test of pathlist. + */ + pfree(rel_grouped); + rel_set->rel_grouped = NULL; + } + } #ifdef OPTIMIZER_DEBUG debug_print_rel(root, rel); @@ -2752,11 +2978,11 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) 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]); + result = (RelOptInfoSet *) linitial(root->join_rel_level[levels_needed]); root->join_rel_level = NULL; - return rel; + return result; } /***************************************************************************** diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index f1baa36886..5c8a009d09 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -2329,13 +2329,23 @@ cost_group(Path *path, PlannerInfo *root, /* * estimate_join_rows * Set rows of a join path according to its parent relation or according - * to parameters. + * to parameters. If agg_info is passed, the join path is grouped. */ static void -estimate_join_rows(PlannerInfo *root, Path *path) +estimate_join_rows(PlannerInfo *root, Path *path, RelAggInfo *agg_info) { if (path->param_info) + { path->rows = path->param_info->ppi_rows; + if (agg_info) + { + double nrows; + + nrows = estimate_num_groups(root, agg_info->group_exprs, + path->rows, NULL); + path->rows = clamp_row_est(nrows); + } + } else path->rows = path->parent->rows; } @@ -2461,7 +2471,7 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path, inner_path_rows = 1; /* Mark the path with the correct row estimate */ - estimate_join_rows(root, (Path *) path); + estimate_join_rows(root, (Path *) path, extra->agg_info); /* For partial paths, scale row estimate. */ if (path->path.parallel_workers > 0) @@ -2904,7 +2914,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, inner_path_rows = 1; /* Mark the path with the correct row estimate */ - estimate_join_rows(root, (Path *) path); + estimate_join_rows(root, (Path *) path, extra->agg_info); /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) @@ -3331,7 +3341,7 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path, ListCell *hcl; /* Mark the path with the correct row estimate */ - estimate_join_rows(root, (Path *) path); + estimate_join_rows(root, (Path *) path, extra->agg_info); /* For partial paths, scale row estimate. */ if (path->jpath.path.parallel_workers > 0) @@ -4336,27 +4346,59 @@ approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals) * restriction clauses). * width: the estimated average output tuple width in bytes. * baserestrictcost: estimated cost of evaluating baserestrictinfo clauses. + * + * If "agg_info" is passed, it means that "rel" is a grouped relation for + * which "agg_info" provides the information needed for size estimate. */ void -set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel) +set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel, + RelAggInfo *agg_info) { double nrows; + bool grouped = agg_info != NULL; /* Should only be applied to base relations */ Assert(rel->relid > 0); - nrows = rel->tuples * - clauselist_selectivity(root, - rel->baserestrictinfo, - 0, - JOIN_INNER, - NULL); + if (!grouped) + { + nrows = rel->tuples * + clauselist_selectivity(root, + rel->baserestrictinfo, + 0, + JOIN_INNER, + NULL); + rel->rows = clamp_row_est(nrows); + } - rel->rows = clamp_row_est(nrows); + /* + * Only set the estimate for grouped base rel if aggregation can take + * place. (Aggregation is the only way to build grouped base relation.) + */ + else if (!bms_equal(rel->relids, root->all_baserels)) + { + /* + * Grouping essentially changes the number of rows. + */ + nrows = estimate_num_groups(root, + agg_info->group_exprs, + agg_info->input_rows, + NULL); + rel->rows = clamp_row_est(nrows); + } cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root); - set_rel_width(root, rel); + /* + * 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 } /* @@ -4920,7 +4962,7 @@ set_subquery_size_estimates(PlannerInfo *root, RelOptInfo *rel) } /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -4958,7 +5000,7 @@ set_function_size_estimates(PlannerInfo *root, RelOptInfo *rel) } /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -4980,7 +5022,7 @@ set_tablefunc_size_estimates(PlannerInfo *root, RelOptInfo *rel) rel->tuples = 100; /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -5011,7 +5053,7 @@ set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel) rel->tuples = list_length(rte->values_lists); /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -5049,7 +5091,7 @@ set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, double cte_rows) } /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -5082,7 +5124,7 @@ set_namedtuplestore_size_estimates(PlannerInfo *root, RelOptInfo *rel) rel->tuples = 1000; /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -5105,7 +5147,7 @@ set_result_size_estimates(PlannerInfo *root, RelOptInfo *rel) rel->tuples = 1; /* Now estimate number of output rows, etc */ - set_baserel_size_estimates(root, rel); + set_baserel_size_estimates(root, rel, NULL); } /* @@ -5329,11 +5371,11 @@ set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target) foreach(lc, target->exprs) { Node *node = (Node *) lfirst(lc); + int32 item_width; if (IsA(node, Var)) { Var *var = (Var *) node; - int32 item_width; /* We should not see any upper-level Vars here */ Assert(var->varlevelsup == 0); @@ -5364,6 +5406,20 @@ set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target) Assert(item_width > 0); tuple_width += item_width; } + else if (IsA(node, Aggref)) + { + /* + * If the target is evaluated by AggPath, it'll care of cost + * estimate. If the target is above AggPath (typically target of a + * join relation that contains grouped relation), the cost of + * Aggref should not be accounted for again. + * + * On the other hand, width is always needed. + */ + item_width = get_typavgwidth(exprType(node), exprTypmod(node)); + Assert(item_width > 0); + tuple_width += item_width; + } else { /* diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 3454f12912..0452d415fb 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -65,7 +65,6 @@ static bool reconsider_outer_join_clause(PlannerInfo *root, static bool reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo); - /* * process_equivalence * The given clause has a mergejoinable operator and can be applied without @@ -2511,3 +2510,137 @@ is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist) 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. Return NULL if + * translation is not possible or needed. + * + * Note: Currently we only translate Var expressions. This is subject to + * change as the aggregate push-down feature gets enhanced. + */ +GroupedVarInfo * +translate_expression_to_rels(PlannerInfo *root, GroupedVarInfo *gvi, + Index relid) +{ + Var *var; + ListCell *l1; + bool found_orig = false; + Var *var_translated = NULL; + GroupedVarInfo *result; + + /* Can't do anything w/o equivalence classes. */ + if (root->eq_classes == NIL) + return NULL; + + var = castNode(Var, gvi->gvexpr); + + /* + * Do we need to translate the var? + */ + if (var->varno == relid) + return NULL; + + /* + * Find the replacement var. + */ + foreach(l1, root->eq_classes) + { + EquivalenceClass *ec = lfirst_node(EquivalenceClass, l1); + ListCell *l2; + + /* TODO 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. + */ + foreach(l2, ec->ec_members) + { + EquivalenceMember *em = lfirst_node(EquivalenceMember, l2); + Var *ec_var; + + /* + * The grouping expressions derived here are used to evaluate + * possibility to push aggregation down to RELOPT_BASEREL or + * RELOPT_JOINREL relations, and to construct reltargets for the + * grouped rels. We're not interested at the moment whether the + * relations do have children. + */ + if (em->em_is_child) + continue; + + if (!IsA(em->em_expr, Var)) + continue; + + ec_var = castNode(Var, em->em_expr); + if (equal(ec_var, var)) + found_orig = true; + else if (ec_var->varno == relid) + var_translated = ec_var; + + if (found_orig && var_translated) + { + /* + * The replacement Var must have the same data type, otherwise + * the values are not guaranteed to be grouped in the same way + * as values of the original Var. + */ + if (ec_var->vartype != var->vartype) + return NULL; + + break; + } + } + + if (found_orig) + { + /* + * The same expression probably does not exist in multiple ECs. + */ + if (var_translated == NULL) + { + /* + * Failed to translate the expression. + */ + return NULL; + } + else + { + /* Success. */ + break; + } + } + else + { + /* + * Vars of the requested relid can be in the next ECs too. + */ + var_translated = NULL; + } + } + + if (!found_orig) + return NULL; + + result = makeNode(GroupedVarInfo); + memcpy(result, gvi, sizeof(GroupedVarInfo)); + + /* + * translate_expression_to_rels_mutator updates gv_eval_at. + */ + result->gv_eval_at = bms_make_singleton(relid); + result->gvexpr = (Expr *) var_translated; + result->derived = true; + + return result; +} diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 7e1a3908f1..c4080b0587 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -77,13 +77,14 @@ typedef struct 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, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, - List **bitindexpaths); + List **bitindexpaths, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static void consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, @@ -92,7 +93,9 @@ static void consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, List **bitindexpaths, List *indexjoinclauses, int considered_clauses, - List **considered_relids); + List **considered_relids, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static void get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, @@ -100,19 +103,24 @@ static void get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexClauseSet *eclauseset, List **bitindexpaths, Relids relids, - List **considered_relids); + List **considered_relids, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static bool eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids, List *indexjoinclauses); static bool bms_equal_any(Relids relids, List *relids_list); static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, - List **bitindexpaths); + List **bitindexpaths, RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static List *build_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, bool useful_predicate, ScanTypeControl scantype, bool *skip_nonnative_saop, - bool *skip_lower_saop); + bool *skip_lower_saop, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); static List *build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses); static List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, @@ -216,6 +224,10 @@ static Const *string_to_const(const char *str, Oid datatype); * * 'rel' is the relation for which we want to generate index paths * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. + * * Note: check_index_predicates() must have been run previously for this rel. * * Note: in cases involving LATERAL references in the relation's tlist, it's @@ -228,7 +240,8 @@ static Const *string_to_const(const char *str, Oid datatype); * as meaning "unparameterized so far as the indexquals are concerned". */ void -create_index_paths(PlannerInfo *root, RelOptInfo *rel) +create_index_paths(PlannerInfo *root, RelOptInfo *rel, RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { List *indexpaths; List *bitindexpaths; @@ -238,6 +251,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) IndexClauseSet jclauseset; IndexClauseSet eclauseset; ListCell *lc; + bool grouped = rel_grouped != NULL; /* Skip the whole mess if no indexes */ if (rel->indexlist == NIL) @@ -273,8 +287,8 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) * 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); + get_index_paths(root, rel, index, &rclauseset, &bitindexpaths, + rel_grouped, agg_info); /* * Identify the join clauses that can match the index. For the moment @@ -303,15 +317,24 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) &rclauseset, &jclauseset, &eclauseset, - &bitjoinpaths); + &bitjoinpaths, + rel_grouped, + agg_info); } /* + * It does not seem too efficient to aggregate the individual paths and + * then AND them together. + */ + if (grouped) + 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); + indexpaths = generate_bitmap_or_paths(root, rel, rel->baserestrictinfo, + NIL); bitindexpaths = list_concat(bitindexpaths, indexpaths); /* @@ -433,6 +456,10 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) * 'jclauseset' is the collection of indexable simple join clauses * 'eclauseset' is the collection of indexable clauses from EquivalenceClasses * '*bitindexpaths' is the list to add bitmap paths to + * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. */ static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, @@ -440,7 +467,9 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, - List **bitindexpaths) + List **bitindexpaths, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { int considered_clauses = 0; List *considered_relids = NIL; @@ -476,7 +505,9 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, bitindexpaths, jclauseset->indexclauses[indexcol], considered_clauses, - &considered_relids); + &considered_relids, + rel_grouped, + agg_info); /* Consider each applicable eclass join clause */ considered_clauses += list_length(eclauseset->indexclauses[indexcol]); consider_index_join_outer_rels(root, rel, index, @@ -484,7 +515,9 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, bitindexpaths, eclauseset->indexclauses[indexcol], considered_clauses, - &considered_relids); + &considered_relids, + rel_grouped, + agg_info); } } @@ -499,6 +532,10 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, * 'indexjoinclauses' is a list of RestrictInfos for join clauses * 'considered_clauses' is the total number of clauses considered (so far) * '*considered_relids' is a list of all relids sets already considered + * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. */ static void consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, @@ -509,7 +546,9 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, List **bitindexpaths, List *indexjoinclauses, int considered_clauses, - List **considered_relids) + List **considered_relids, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { ListCell *lc; @@ -576,7 +615,9 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, rclauseset, jclauseset, eclauseset, bitindexpaths, bms_union(clause_relids, oldrelids), - considered_relids); + considered_relids, + rel_grouped, + agg_info); } /* Also try this set of relids by itself */ @@ -584,7 +625,9 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, rclauseset, jclauseset, eclauseset, bitindexpaths, clause_relids, - considered_relids); + considered_relids, + rel_grouped, + agg_info); } } @@ -600,6 +643,10 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, * 'bitindexpaths', 'considered_relids' as above * 'relids' is the current set of relids to consider (the target rel plus * one or more outer rels) + * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. */ static void get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, @@ -609,7 +656,9 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexClauseSet *eclauseset, List **bitindexpaths, Relids relids, - List **considered_relids) + List **considered_relids, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { IndexClauseSet clauseset; int indexcol; @@ -666,7 +715,8 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, Assert(clauseset.nonempty); /* Build index path(s) using the collected set of clauses */ - get_index_paths(root, rel, index, &clauseset, bitindexpaths); + get_index_paths(root, rel, index, &clauseset, bitindexpaths, + rel_grouped, agg_info); /* * Remember we considered paths for this set of relids. We use lcons not @@ -716,7 +766,6 @@ bms_equal_any(Relids relids, List *relids_list) return false; } - /* * get_index_paths * Given an index and a set of index clauses for it, construct IndexPaths. @@ -731,16 +780,23 @@ bms_equal_any(Relids relids, List *relids_list) * paths, and then make a separate attempt to include them in bitmap paths. * Furthermore, we should consider excluding lower-order ScalarArrayOpExpr * quals so as to create ordered paths. + * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. */ static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, - List **bitindexpaths) + List **bitindexpaths, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { List *indexpaths; bool skip_nonnative_saop = false; bool skip_lower_saop = false; ListCell *lc; + bool grouped = rel_grouped != NULL; /* * Build simple index paths using the clauses. Allow ScalarArrayOpExpr @@ -753,7 +809,40 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel, index->predOK, ST_ANYSCAN, &skip_nonnative_saop, - &skip_lower_saop); + &skip_lower_saop, + rel_grouped, + agg_info); + + /* + * If the relation is grouped, apply the partial aggregation. + * + * Only AGG_SORTED strategy is used, so we ignore bitmap paths, as well as + * indexes that can only produce them. + */ + if (grouped && index->amhasgettuple) + { + foreach(lc, indexpaths) + { + IndexPath *ipath = (IndexPath *) lfirst(lc); + Path *subpath = &ipath->path; + + if (subpath->pathkeys != NIL) + { + AggPath *agg_path; + + agg_path = create_agg_sorted_path(root, + subpath, + agg_info); + if (agg_path) + add_path(rel_grouped, (Path *) agg_path); + } + } + + /* + * Nothing more to do for grouped relation. + */ + return; + } /* * If we skipped any lower-order ScalarArrayOpExprs on an index with an AM @@ -768,7 +857,9 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel, index->predOK, ST_ANYSCAN, &skip_nonnative_saop, - NULL)); + NULL, + rel_grouped, + agg_info)); } /* @@ -808,7 +899,9 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel, false, ST_BITMAPSCAN, NULL, - NULL); + NULL, + rel_grouped, + agg_info); *bitindexpaths = list_concat(*bitindexpaths, indexpaths); } } @@ -852,7 +945,15 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel, * '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 + * 'skip_lower_saop' indicates whether to accept non-first-column SAOP. + * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. + * + * XXX When enabling the aggregate push-down for partial paths, we'll need the + * function to return the aggregation input paths in a separate list instead + * of calling add_partial_path() on them immediately. */ static List * build_index_paths(PlannerInfo *root, RelOptInfo *rel, @@ -860,7 +961,9 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, bool useful_predicate, ScanTypeControl scantype, bool *skip_nonnative_saop, - bool *skip_lower_saop) + bool *skip_lower_saop, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { List *result = NIL; IndexPath *ipath; @@ -877,6 +980,12 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, bool index_is_ordered; bool index_only_scan; int indexcol; + bool include_partial; + + /* + * Grouped partial paths are not supported yet. + */ + include_partial = rel_grouped == NULL; /* * Check that index supports the desired scan type(s) @@ -1046,14 +1155,16 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_only_scan, outer_relids, loop_count, - false); + false, + rel_grouped, + agg_info); result = lappend(result, ipath); /* * If appropriate, consider parallel index scan. We don't allow * parallel index scan for bitmap index scans. */ - if (index->amcanparallel && + if (include_partial && index->amcanparallel && rel->consider_parallel && outer_relids == NULL && scantype != ST_BITMAPSCAN) { @@ -1069,7 +1180,9 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_only_scan, outer_relids, loop_count, - true); + true, + rel_grouped, + agg_info); /* * if, after costing the path, we find that it's not worth using @@ -1103,11 +1216,13 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_only_scan, outer_relids, loop_count, - false); + false, + rel_grouped, + agg_info); result = lappend(result, ipath); /* If appropriate, consider parallel index scan */ - if (index->amcanparallel && + if (include_partial && index->amcanparallel && rel->consider_parallel && outer_relids == NULL && scantype != ST_BITMAPSCAN) { @@ -1121,7 +1236,9 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_only_scan, outer_relids, loop_count, - true); + true, + rel_grouped, + agg_info); /* * if, after costing the path, we find that it's not worth @@ -1243,6 +1360,8 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel, useful_predicate, ST_BITMAPSCAN, NULL, + NULL, + NULL, NULL); result = list_concat(result, indexpaths); } diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index d8ff4bf432..f99d6b98a9 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -120,7 +120,9 @@ add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, - List *restrictlist) + List *restrictlist, + RelAggInfo *agg_info, + RelOptInfo *rel_agg_input) { JoinPathExtraData extra; bool mergejoin_allowed = true; @@ -143,6 +145,8 @@ add_paths_to_joinrel(PlannerInfo *root, extra.mergeclause_list = NIL; extra.sjinfo = sjinfo; extra.param_source_rels = NULL; + extra.agg_info = agg_info; + extra.rel_agg_input = rel_agg_input; /* * See if the inner relation is provably unique for this outer rel. @@ -376,6 +380,8 @@ try_nestloop_path(PlannerInfo *root, Relids outerrelids; Relids inner_paramrels = PATH_REQ_OUTER(inner_path); Relids outer_paramrels = PATH_REQ_OUTER(outer_path); + bool do_aggregate = extra->rel_agg_input != NULL; + bool success = false; /* * Paths are parameterized by top-level parents, so run parameterization @@ -422,10 +428,37 @@ try_nestloop_path(PlannerInfo *root, 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 join output should be aggregated, the precheck is skipped + * because it makes little sense to compare the new join path to existing, + * already aggregated paths. Since we don't have row count estimate yet, + * it's hard to involve AggPath in the precheck. + */ + if ((!do_aggregate && + add_path_precheck(joinrel, + workspace.startup_cost, workspace.total_cost, + pathkeys, required_outer)) || + do_aggregate) { + PathTarget *target; + Path *path; + RelOptInfo *parent_rel; + + if (!do_aggregate) + { + target = joinrel->reltarget; + parent_rel = joinrel; + } + else + { + /* + * If the join output is subject to aggregation, the path must + * generate aggregation input. + */ + target = extra->agg_info->input; + parent_rel = extra->rel_agg_input; + } + /* * If the inner path is parameterized, it is parameterized by the * topmost parent of the outer rel, not the outer rel itself. Fix @@ -447,21 +480,57 @@ try_nestloop_path(PlannerInfo *root, } } - add_path(joinrel, (Path *) - create_nestloop_path(root, - joinrel, - jointype, - &workspace, - extra, - outer_path, - inner_path, - extra->restrictlist, - pathkeys, - required_outer)); + path = (Path *) create_nestloop_path(root, + parent_rel, + target, + jointype, + &workspace, + extra, + outer_path, + inner_path, + extra->restrictlist, + pathkeys, + required_outer); + + if (!do_aggregate) + { + add_path(joinrel, path); + success = true; + } + else + { + /* + * Non-grouped rel had to be passed to create_nestloop_path() so + * that row estimate reflects the aggregation input data, however + * even the aggregation input path should eventually be owned by + * the grouped joinrel. + */ + path->parent = joinrel; + + /* + * Try both AGG_HASHED and AGG_SORTED 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 = add_grouped_path(root, joinrel, path, + AGG_HASHED, extra->agg_info); + + /* + * Don't try AGG_SORTED if add_grouped_path() would reject it + * anyway. + */ + if (pathkeys != NIL) + success = success || + add_grouped_path(root, joinrel, path, AGG_SORTED, + extra->agg_info); + } } - else + + if (!success) { - /* Waste no memory when we reject a path here */ + /* Waste no memory when we reject path(s) here */ bms_free(required_outer); } } @@ -538,6 +607,7 @@ try_partial_nestloop_path(PlannerInfo *root, add_partial_path(joinrel, (Path *) create_nestloop_path(root, joinrel, + joinrel->reltarget, jointype, &workspace, extra, @@ -568,8 +638,11 @@ try_mergejoin_path(PlannerInfo *root, { Relids required_outer; JoinCostWorkspace workspace; + bool grouped = extra->agg_info != NULL; + bool do_aggregate = extra->rel_agg_input != NULL; + bool success = false; - if (is_partial) + if (!grouped && is_partial) { try_partial_mergejoin_path(root, joinrel, @@ -617,26 +690,73 @@ try_mergejoin_path(PlannerInfo *root, outersortkeys, innersortkeys, extra); - if (add_path_precheck(joinrel, - workspace.startup_cost, workspace.total_cost, - pathkeys, required_outer)) + /* + * See comments in try_nestloop_path(). + */ + if ((!do_aggregate && + add_path_precheck(joinrel, + workspace.startup_cost, workspace.total_cost, + pathkeys, required_outer)) || + do_aggregate) { - add_path(joinrel, (Path *) - create_mergejoin_path(root, - joinrel, - jointype, - &workspace, - extra, - outer_path, - inner_path, - extra->restrictlist, - pathkeys, - required_outer, - mergeclauses, - outersortkeys, - innersortkeys)); + PathTarget *target; + Path *path; + RelOptInfo *parent_rel; + + if (!do_aggregate) + { + target = joinrel->reltarget; + parent_rel = joinrel; + } + else + { + target = extra->agg_info->input; + parent_rel = extra->rel_agg_input; + } + + path = (Path *) create_mergejoin_path(root, + parent_rel, + 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 + { + /* See comment in try_nestloop_path() */ + path->parent = joinrel; + + if (required_outer == NULL) + success = add_grouped_path(root, + joinrel, + path, + AGG_HASHED, + extra->agg_info); + + if (pathkeys != NIL) + success = success || + add_grouped_path(root, + joinrel, + path, + AGG_SORTED, + extra->agg_info); + } } - else + + if (!success) { /* Waste no memory when we reject a path here */ bms_free(required_outer); @@ -700,6 +820,7 @@ try_partial_mergejoin_path(PlannerInfo *root, add_partial_path(joinrel, (Path *) create_mergejoin_path(root, joinrel, + joinrel->reltarget, jointype, &workspace, extra, @@ -729,6 +850,9 @@ try_hashjoin_path(PlannerInfo *root, { Relids required_outer; JoinCostWorkspace workspace; + bool grouped = extra->agg_info != NULL; + bool do_aggregate = extra->rel_agg_input != NULL; + bool success = false; /* * Check to see if proposed path is still parameterized, and reject if the @@ -745,30 +869,79 @@ try_hashjoin_path(PlannerInfo *root, } /* + * 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 && grouped) + 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 (add_path_precheck(joinrel, - workspace.startup_cost, workspace.total_cost, - NIL, required_outer)) + + /* + * See comments in try_nestloop_path(). + */ + if ((!do_aggregate && + add_path_precheck(joinrel, + workspace.startup_cost, workspace.total_cost, + NIL, required_outer)) || + do_aggregate) { - add_path(joinrel, (Path *) - create_hashjoin_path(root, - joinrel, - jointype, - &workspace, - extra, - outer_path, - inner_path, - false, /* parallel_hash */ - extra->restrictlist, - required_outer, - hashclauses)); + PathTarget *target; + Path *path = NULL; + RelOptInfo *parent_rel; + + if (!do_aggregate) + { + target = joinrel->reltarget; + parent_rel = joinrel; + } + else + { + target = extra->agg_info->input; + parent_rel = extra->rel_agg_input; + } + + path = (Path *) create_hashjoin_path(root, + parent_rel, + 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 + { + /* See comment in try_nestloop_path() */ + path->parent = joinrel; + + /* + * As the hashjoin path is not sorted, only try AGG_HASHED. + */ + if (add_grouped_path(root, joinrel, path, AGG_HASHED, + extra->agg_info)) + success = true; + } } - else + + if (!success) { /* Waste no memory when we reject a path here */ bms_free(required_outer); @@ -824,6 +997,7 @@ try_partial_hashjoin_path(PlannerInfo *root, add_partial_path(joinrel, (Path *) create_hashjoin_path(root, joinrel, + joinrel->reltarget, jointype, &workspace, extra, @@ -892,6 +1066,7 @@ sort_inner_and_outer(PlannerInfo *root, Path *cheapest_safe_inner = NULL; List *all_pathkeys; ListCell *l; + bool grouped = extra->agg_info != NULL; /* * We only consider the cheapest-total-cost input paths, since we are @@ -1051,7 +1226,7 @@ sort_inner_and_outer(PlannerInfo *root, * If we have partial outer and parallel safe inner path then try * partial mergejoin path. */ - if (cheapest_partial_outer && cheapest_safe_inner) + if (!grouped && cheapest_partial_outer && cheapest_safe_inner) try_partial_mergejoin_path(root, joinrel, cheapest_partial_outer, @@ -1341,6 +1516,7 @@ match_unsorted_outer(PlannerInfo *root, Path *inner_cheapest_total = innerrel->cheapest_total_path; Path *matpath = NULL; ListCell *lc1; + bool grouped = extra->agg_info != NULL; /* * Nestloop only supports inner, left, semi, and anti joins. Also, if we @@ -1516,7 +1692,8 @@ match_unsorted_outer(PlannerInfo *root, * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT, * because they can produce false null extended rows. */ - if (joinrel->consider_parallel && + if (!grouped && + joinrel->consider_parallel && save_jointype != JOIN_UNIQUE_OUTER && save_jointype != JOIN_FULL && save_jointype != JOIN_RIGHT && diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index fc9eb95f5a..8014f10ac3 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -24,24 +24,33 @@ #include "partitioning/partbounds.h" #include "utils/lsyscache.h" #include "utils/memutils.h" +#include "utils/selfuncs.h" static void make_rels_by_clause_joins(PlannerInfo *root, - RelOptInfo *old_rel, + RelOptInfoSet *old_relset, ListCell *other_rels); static void make_rels_by_clauseless_joins(PlannerInfo *root, - RelOptInfo *old_rel, + RelOptInfoSet *old_relset, ListCell *other_rels); +static void set_grouped_joinrel_target(PlannerInfo *root, RelOptInfo *joinrel, + 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_false(List *restrictlist, RelOptInfo *joinrel, bool only_pushed_down); -static RelOptInfo *make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); +static RelOptInfo *make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, + RelAggInfo *agg_info, RelOptInfo *rel_agg_input); +static void make_join_rel_common_grouped(PlannerInfo *root, RelOptInfoSet *relset1, + RelOptInfoSet *relset2, + RelAggInfo *agg_info); static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, - SpecialJoinInfo *sjinfo, List *restrictlist); + SpecialJoinInfo *sjinfo, List *restrictlist, + RelAggInfo *agg_info, + RelOptInfo *rel_agg_input); static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, @@ -54,7 +63,6 @@ static SpecialJoinInfo *build_child_join_sjinfo(PlannerInfo *root, static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op); - /* * join_search_one_level * Consider ways to produce join relations containing exactly 'level' @@ -89,7 +97,15 @@ join_search_one_level(PlannerInfo *root, int level) */ foreach(r, joinrels[level - 1]) { - RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); + RelOptInfoSet *old_relset = (RelOptInfoSet *) lfirst(r); + RelOptInfo *old_rel; + + /* + * Both rel_plain and rel_grouped should have the same clauses, so it + * does not matter which one we use here. The only difference is that + * rel_grouped is not guaranteed to exist, so use rel_plain. + */ + old_rel = old_relset->rel_plain; if (old_rel->joininfo != NIL || old_rel->has_eclass_joins || has_join_restriction(root, old_rel)) @@ -115,7 +131,7 @@ join_search_one_level(PlannerInfo *root, int level) other_rels = list_head(joinrels[1]); make_rels_by_clause_joins(root, - old_rel, + old_relset, other_rels); } else @@ -133,7 +149,7 @@ join_search_one_level(PlannerInfo *root, int level) * avoid the duplicated effort. */ make_rels_by_clauseless_joins(root, - old_rel, + old_relset, list_head(joinrels[1])); } } @@ -159,7 +175,8 @@ join_search_one_level(PlannerInfo *root, int level) foreach(r, joinrels[k]) { - RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); + RelOptInfoSet *old_relset = (RelOptInfoSet *) lfirst(r); + RelOptInfo *old_rel = old_relset->rel_plain; ListCell *other_rels; ListCell *r2; @@ -179,7 +196,8 @@ join_search_one_level(PlannerInfo *root, int level) for_each_cell(r2, other_rels) { - RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2); + RelOptInfoSet *new_relset = (RelOptInfoSet *) lfirst(r2); + RelOptInfo *new_rel = new_relset->rel_plain; if (!bms_overlap(old_rel->relids, new_rel->relids)) { @@ -191,7 +209,7 @@ join_search_one_level(PlannerInfo *root, int level) if (have_relevant_joinclause(root, old_rel, new_rel) || have_join_order_restriction(root, old_rel, new_rel)) { - (void) make_join_rel(root, old_rel, new_rel); + (void) make_join_rel(root, old_relset, new_relset); } } } @@ -225,10 +243,10 @@ join_search_one_level(PlannerInfo *root, int level) */ foreach(r, joinrels[level - 1]) { - RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); + RelOptInfoSet *old_relset = (RelOptInfoSet *) lfirst(r); make_rels_by_clauseless_joins(root, - old_rel, + old_relset, list_head(joinrels[1])); } @@ -274,25 +292,31 @@ join_search_one_level(PlannerInfo *root, int level) * 'other_rels': the first cell in a linked list containing the other * rels to be considered for joining * + * 'rel_plain' is what we use of RelOptInfoSet because it's guaranteed to + * exists. However the test should have the same result if we used the + * corresponding 'rel_grouped'. + * * Currently, this is only used with initial rels in other_rels, but it * will work for joining to joinrels too. */ static void make_rels_by_clause_joins(PlannerInfo *root, - RelOptInfo *old_rel, + RelOptInfoSet *old_relset, ListCell *other_rels) { ListCell *l; for_each_cell(l, other_rels) { - RelOptInfo *other_rel = (RelOptInfo *) lfirst(l); + RelOptInfo *old_rel = old_relset->rel_plain; + RelOptInfoSet *other_relset = (RelOptInfoSet *) lfirst(l); + RelOptInfo *other_rel = other_relset->rel_plain; if (!bms_overlap(old_rel->relids, other_rel->relids) && (have_relevant_joinclause(root, old_rel, other_rel) || have_join_order_restriction(root, old_rel, other_rel))) { - (void) make_join_rel(root, old_rel, other_rel); + (void) make_join_rel(root, old_relset, other_relset); } } } @@ -308,27 +332,62 @@ make_rels_by_clause_joins(PlannerInfo *root, * 'other_rels': the first cell of a linked list containing the * other rels to be considered for joining * + * 'rel_plain' is what we use of RelOptInfoSet because it's guaranteed to + * exists. However the test should have the same result if we used the + * corresponding 'rel_grouped'. + * * Currently, this is only used with initial rels in other_rels, but it would * work for joining to joinrels too. */ static void make_rels_by_clauseless_joins(PlannerInfo *root, - RelOptInfo *old_rel, + RelOptInfoSet *old_relset, ListCell *other_rels) { ListCell *l; for_each_cell(l, other_rels) { - RelOptInfo *other_rel = (RelOptInfo *) lfirst(l); + RelOptInfo *old_rel = old_relset->rel_plain; + RelOptInfoSet *other_relset = (RelOptInfoSet *) lfirst(l); + RelOptInfo *other_rel = other_relset->rel_plain; if (!bms_overlap(other_rel->relids, old_rel->relids)) { - (void) make_join_rel(root, old_rel, other_rel); + (void) make_join_rel(root, old_relset, other_relset); } } } +/* + * Set joinrel's reltarget according to agg_info and estimate the number of + * rows. + */ +static void +set_grouped_joinrel_target(PlannerInfo *root, RelOptInfo *joinrel, + RelAggInfo *agg_info) +{ + Assert(agg_info != NULL); + + /* + * build_join_rel() does not create the target for grouped relation. + */ + Assert(joinrel->reltarget == NULL); + + joinrel->reltarget = agg_info->target; + + /* + * Grouping essentially changes the number of rows. + * + * XXX We do not distinguish whether two plain rels are joined and the + * result is aggregated, or the 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, agg_info->group_exprs, + agg_info->input_rows, NULL); +} /* * join_is_legal @@ -661,9 +720,18 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, /* * make_join_rel_common * The workhorse of make_join_rel(). + * + * 'agg_info' contains the reltarget of grouped relation and everything we + * need to aggregate the join result. If NULL, then the join relation + * should not be grouped. + * + * 'rel_agg_input' describes the AggPath input relation if the join output + * should be aggregated. If NULL is passed, do not aggregate the join + * output. */ static RelOptInfo * -make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) +make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, + RelAggInfo *agg_info, RelOptInfo *rel_agg_input) { Relids joinrelids; SpecialJoinInfo *sjinfo; @@ -671,10 +739,15 @@ make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) SpecialJoinInfo sjinfo_data; RelOptInfo *joinrel; List *restrictlist; + bool grouped = agg_info != NULL; + bool do_aggregate = rel_agg_input != 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); @@ -724,7 +797,18 @@ make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) * goes with this particular joining. */ joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo, - &restrictlist); + &restrictlist, agg_info); + + if (grouped) + { + /* + * Make sure the grouped joinrel has reltarget initialized. Caller + * should supply the target for grouped relation, so build_join_rel() + * should have omitted its creation. + */ + if (joinrel->reltarget == NULL) + set_grouped_joinrel_target(root, joinrel, agg_info); + } /* * If we've already proven this join is empty, we needn't consider any @@ -738,13 +822,72 @@ make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) /* Add paths to the join relation. */ populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); bms_free(joinrelids); return joinrel; } +static void +make_join_rel_common_grouped(PlannerInfo *root, RelOptInfoSet *relset1, + RelOptInfoSet *relset2, + RelAggInfo *agg_info) +{ + RelOptInfo *rel1_grouped = NULL; + RelOptInfo *rel2_grouped = NULL; + bool rel1_grouped_useful = false; + bool rel2_grouped_useful = false; + + /* + * Retrieve the grouped relations. + * + * Dummy rel may indicates a join relation that is 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). + */ + if (relset1->rel_grouped) + rel1_grouped = relset1->rel_grouped; + if (relset2->rel_grouped) + rel2_grouped = relset2->rel_grouped; + + rel1_grouped_useful = rel1_grouped != NULL && !IS_DUMMY_REL(rel1_grouped); + rel2_grouped_useful = rel2_grouped != NULL && !IS_DUMMY_REL(rel2_grouped); + + /* + * Nothing to do? + */ + if (!rel1_grouped_useful && !rel2_grouped_useful) + return; + + /* + * At maximum one input rel can be grouped (here we don't care if any rel + * is eventually dummy, the existence of grouped rel indicates that + * aggregates can be pushed down to it). 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 && rel2_grouped) + return; + + if (rel1_grouped_useful) + make_join_rel_common(root, rel1_grouped, relset2->rel_plain, agg_info, + NULL); + else if (rel2_grouped_useful) + make_join_rel_common(root, relset1->rel_plain, rel2_grouped, agg_info, + NULL); +} + /* * make_join_rel * Find or create a join RelOptInfo that represents the join of @@ -753,14 +896,101 @@ make_join_rel_common(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) * (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. + * In addition to creating an ordinary join relation, try to create a + * grouped one. There are two strategies to achieve that: join a grouped + * relation to plain one, or join two plain relations and apply partial + * aggregation to the result. + * + * 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. Besides that, NULL is also returned if caller is + * interested in a grouped relation but there's no useful grouped input + * relation. + * + * Only the plain relation is returned. + * + * TODO geqo is the only caller interested in the result. We'll need to return + * RelOptInfoSet if geqo adopts the aggregate pushdown technique. */ RelOptInfo * -make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) +make_join_rel(PlannerInfo *root, RelOptInfoSet *relset1, + RelOptInfoSet *relset2) { - return make_join_rel_common(root, rel1, rel2); + Relids joinrelids; + RelAggInfo *agg_info; + RelOptInfoSet *joinrelset; + RelOptInfo *joinrel_plain; + RelOptInfo *rel1 = relset1->rel_plain; + RelOptInfo *rel2 = relset2->rel_plain; + + /* 1) form the plain join. */ + joinrel_plain = make_join_rel_common(root, rel1, rel2, NULL, NULL); + + if (joinrel_plain == NULL) + return joinrel_plain; + + /* + * We're done if there are no grouping expressions nor aggregates. + */ + if (root->grouped_var_list == NIL) + return joinrel_plain; + + /* + * If the same grouped joinrel was already formed, just with the base rels + * divided between rel1 and rel2 in a different way, we should already + * have the matching agg_info. + */ + joinrelids = bms_union(rel1->relids, rel2->relids); + joinrelset = find_join_rel(root, joinrelids); + + /* + * At the moment we know that non-grouped join exists, so the containing + * joinrelset should have been fetched. + */ + Assert(joinrelset != NULL); + + if (joinrelset->rel_grouped != NULL) + { + /* + * The same agg_info should be used for all the rels consisting of + * exactly joinrelids. + */ + agg_info = joinrelset->agg_info; + } + else + { + /* + * agg_info must be created from scratch. + */ + agg_info = create_rel_agg_info(root, joinrel_plain); + + /* + * The number of aggregate input rows is simply the number of rows of + * the non-grouped relation, which should have been estimated by now. + */ + if (agg_info != NULL) + agg_info->input_rows = joinrel_plain->rows; + } + + /* + * Cannot we build grouped join? + */ + if (agg_info == NULL) + return joinrel_plain; + + /* + * 2) join two plain rels and aggregate the join paths. Aggregate + * push-down only makes sense if the join is not the final one. + */ + if (bms_nonempty_difference(root->all_baserels, joinrelids)) + make_join_rel_common(root, rel1, rel2, agg_info, joinrel_plain); + + /* + * 3) combine plain and grouped relations. + */ + make_join_rel_common_grouped(root, relset1, relset2, agg_info); + + return joinrel_plain; } /* @@ -773,8 +1003,11 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, - SpecialJoinInfo *sjinfo, List *restrictlist) + SpecialJoinInfo *sjinfo, List *restrictlist, + RelAggInfo *agg_info, RelOptInfo *rel_agg_input) { + bool grouped = agg_info != NULL; + /* * Consider paths using each rel as both outer and inner. Depending on * the join type, a provably empty outer or inner rel might mean the join @@ -804,10 +1037,10 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_INNER, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_INNER, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); break; case JOIN_LEFT: if (is_dummy_rel(rel1) || @@ -821,10 +1054,10 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_LEFT, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_RIGHT, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); break; case JOIN_FULL: if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) || @@ -835,10 +1068,10 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_FULL, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_FULL, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); /* * If there are join quals that aren't mergeable or hashable, we @@ -871,7 +1104,7 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_SEMI, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); } /* @@ -894,10 +1127,10 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, } add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_UNIQUE_INNER, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); add_paths_to_joinrel(root, joinrel, rel2, rel1, JOIN_UNIQUE_OUTER, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); } break; case JOIN_ANTI: @@ -912,7 +1145,7 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, mark_dummy_rel(rel2); add_paths_to_joinrel(root, joinrel, rel1, rel2, JOIN_ANTI, sjinfo, - restrictlist); + restrictlist, agg_info, rel_agg_input); break; default: /* other values not expected here */ @@ -920,8 +1153,16 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, break; } - /* Apply partitionwise join technique, if possible. */ - try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist); + /* + * The aggregate push-down feature currently does not support + * partition-wise aggregation. + */ + if (grouped) + return; + + /* Apply partition-wise join technique, if possible. */ + try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, + restrictlist); } @@ -1121,7 +1362,8 @@ has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel) foreach(lc, root->initial_rels) { - RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc); + RelOptInfoSet *relset2 = lfirst_node(RelOptInfoSet, lc); + RelOptInfo *rel2 = relset2->rel_plain; /* ignore rels that are already in "rel" */ if (bms_overlap(rel->relids, rel2->relids)) @@ -1452,7 +1694,7 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, populate_joinrel_with_paths(root, child_rel1, child_rel2, child_joinrel, child_sjinfo, - child_restrictlist); + child_restrictlist, NULL, NULL); } } diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 1b4f7db649..d22de6a909 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -901,6 +901,18 @@ use_physical_tlist(PlannerInfo *root, Path *path, int flags) } } + /* + * If aggregate was pushed down, the target can contain aggregates. The + * original target must be preserved then. + */ + foreach(lc, path->pathtarget->exprs) + { + Expr *expr = (Expr *) lfirst(lc); + + if (IsA(expr, Aggref)) + return false; + } + return true; } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index d6ffa7869d..d7008b33b9 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -47,6 +47,8 @@ typedef struct PostponedQual } PostponedQual; +static void create_aggregate_grouped_var_infos(PlannerInfo *root); +static void create_grouping_expr_grouped_var_infos(PlannerInfo *root); static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex); static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode, @@ -97,10 +99,9 @@ static void check_hashjoinable(RestrictInfo *restrictinfo); * 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.) + * 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) @@ -242,6 +243,261 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars, } } +/* + * Add GroupedVarInfo to grouped_var_list for each aggregate as well as for + * each possible grouping expression. + * + * root->group_pathkeys must be setup before this function is called. + */ +extern void +setup_aggregate_pushdown(PlannerInfo *root) +{ + ListCell *lc; + + /* + * Isn't user interested in the aggregate push-down feature? + */ + if (!enable_agg_pushdown) + return; + + /* The feature can only be applied to grouped aggregation. */ + 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; + + /* 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); + + /* Isn't there any useful grouping expression for aggregate push-down? */ + 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; + } +} + +/* + * 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 | + PVC_INCLUDE_WINDOWFUNCS); + + /* + * 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. + * + * Note that the contained aggregates will be pushed down, but the + * containing HAVING clause must be ignored until the aggregation is + * finalized. + */ + 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; + + foreach(lc, tlist_exprs) + { + Expr *expr = (Expr *) lfirst(lc); + Aggref *aggref; + ListCell *lc2; + GroupedVarInfo *gvi; + bool exists; + + /* + * tlist_exprs may also contain Vars or WindowFuncs, but we only need + * Aggrefs. + */ + if (IsA(expr, Var) ||IsA(expr, WindowFunc)) + continue; + + aggref = castNode(Aggref, expr); + + /* TODO Think if (some of) these can be handled. */ + if (aggref->aggvariadic || + aggref->aggdirectargs || aggref->aggorder || + aggref->aggdistinct) + { + /* + * Aggregation push-down 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; + } + + /* 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->gvexpr = (Expr *) copyObject(aggref); + + /* 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; + + 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; + + Assert(sortgroupref > 0); + + /* + * Non-zero sortgroupref does not necessarily imply grouping + * expression: data can also be sorted by aggregate. + */ + if (IsA(te->expr, Aggref)) + continue; + + /* + * The aggregate push-down feature currently supports only plain Vars + * as grouping expressions. + */ + if (!IsA(te->expr, Var)) + { + root->grouped_var_list = NIL; + return; + } + + exprs = lappend(exprs, te->expr); + sortgrouprefs = lappend_int(sortgrouprefs, sortgroupref); + } + + /* + * Construct GroupedVarInfo for each expression. + */ + forboth(l1, exprs, l2, sortgrouprefs) + { + Var *var = lfirst_node(Var, l1); + int sortgroupref = lfirst_int(l2); + GroupedVarInfo *gvi = makeNode(GroupedVarInfo); + + gvi->gvexpr = (Expr *) copyObject(var); + gvi->sortgroupref = sortgroupref; + + /* Find out where the expression should be evaluated. */ + gvi->gv_eval_at = bms_make_singleton(var->varno); + + root->grouped_var_list = lappend(root->grouped_var_list, gvi); + } +} /***************************************************************************** * diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 86617099df..1f2f5b0832 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -349,6 +349,7 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo, List *tlist; NullTest *ntest; SortGroupClause *sortcl; + RelOptInfoSet *final_relset; RelOptInfo *final_rel; Path *sorted_path; Cost path_cost; @@ -442,7 +443,8 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo, subroot->tuple_fraction = 1.0; subroot->limit_tuples = 1.0; - final_rel = query_planner(subroot, tlist, minmax_qp_callback, NULL); + final_relset = query_planner(subroot, tlist, minmax_qp_callback, NULL); + final_rel = final_relset->rel_plain; /* * 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 index 3cedd01c98..ad5b18eb61 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -53,13 +53,14 @@ * qp_callback once we have completed merging the query's equivalence classes. * (We cannot construct canonical pathkeys until that's done.) */ -RelOptInfo * +RelOptInfoSet * query_planner(PlannerInfo *root, List *tlist, query_pathkeys_callback qp_callback, void *qp_extra) { Query *parse = root->parse; List *joinlist; RelOptInfo *final_rel; + RelOptInfoSet *final_relset; /* * Init planner lists to empty. @@ -77,6 +78,7 @@ query_planner(PlannerInfo *root, List *tlist, 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; @@ -147,7 +149,10 @@ query_planner(PlannerInfo *root, List *tlist, */ (*qp_callback) (root, qp_extra); - return final_rel; + final_relset = makeNode(RelOptInfoSet); + final_relset->rel_plain = final_rel; + + return final_relset; } } } @@ -260,14 +265,25 @@ query_planner(PlannerInfo *root, List *tlist, 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. + * + * The base relations should be fully initialized now, so that we have + * enough info to decide whether grouping is possible. + */ + setup_aggregate_pushdown(root); + + /* * Ready to do the primary planning. */ - final_rel = make_one_rel(root, joinlist); + final_relset = make_one_rel(root, joinlist); + final_rel = final_relset->rel_plain; /* 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; + return final_relset; } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 0614f31be4..fcfac56564 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -149,7 +149,7 @@ static double get_number_of_groups(PlannerInfo *root, grouping_sets_data *gd, List *target_list); static RelOptInfo *create_grouping_paths(PlannerInfo *root, - RelOptInfo *input_rel, + RelOptInfoSet *input_relset, PathTarget *target, bool target_parallel_safe, const AggClauseCosts *agg_costs, @@ -162,7 +162,7 @@ static RelOptInfo *make_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, PathTarget *target, bool target_parallel_safe, Node *havingQual); static void create_ordinary_grouping_paths(PlannerInfo *root, - RelOptInfo *input_rel, + RelOptInfoSet *input_relset, RelOptInfo *grouped_rel, const AggClauseCosts *agg_costs, grouping_sets_data *gd, @@ -630,6 +630,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse, memset(root->upper_rels, 0, sizeof(root->upper_rels)); memset(root->upper_targets, 0, sizeof(root->upper_targets)); root->processed_tlist = NIL; + root->max_sortgroupref = 0; root->grouping_map = NULL; root->minmax_aggs = NIL; root->qual_security_level = 0; @@ -1683,6 +1684,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, List *final_targets; List *final_targets_contain_srfs; bool final_target_parallel_safe; + RelOptInfoSet *current_relset; RelOptInfo *current_rel; RelOptInfo *final_rel; ListCell *lc; @@ -1902,8 +1904,9 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, * We also generate (in standard_qp_callback) pathkey representations * of the query's sort clause, distinct clause, etc. */ - current_rel = query_planner(root, tlist, - standard_qp_callback, &qp_extra); + current_relset = query_planner(root, tlist, + standard_qp_callback, &qp_extra); + current_rel = current_relset->rel_plain; /* * Convert the query's result tlist into PathTarget format. @@ -2043,7 +2046,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, if (have_grouping) { current_rel = create_grouping_paths(root, - current_rel, + current_relset, grouping_target, grouping_target_parallel_safe, &agg_costs, @@ -3674,13 +3677,14 @@ get_number_of_groups(PlannerInfo *root, */ static RelOptInfo * create_grouping_paths(PlannerInfo *root, - RelOptInfo *input_rel, + RelOptInfoSet *input_relset, PathTarget *target, bool target_parallel_safe, const AggClauseCosts *agg_costs, grouping_sets_data *gd) { Query *parse = root->parse; + RelOptInfo *input_rel = input_relset->rel_plain; RelOptInfo *grouped_rel; RelOptInfo *partially_grouped_rel; @@ -3765,7 +3769,7 @@ create_grouping_paths(PlannerInfo *root, else extra.patype = PARTITIONWISE_AGGREGATE_NONE; - create_ordinary_grouping_paths(root, input_rel, grouped_rel, + create_ordinary_grouping_paths(root, input_relset, grouped_rel, agg_costs, gd, &extra, &partially_grouped_rel); } @@ -3921,13 +3925,14 @@ create_degenerate_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, * function creates, or to NULL if it doesn't create one. */ static void -create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, +create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfoSet *input_relset, RelOptInfo *grouped_rel, const AggClauseCosts *agg_costs, grouping_sets_data *gd, GroupPathExtraData *extra, RelOptInfo **partially_grouped_rel_p) { + RelOptInfo *input_rel = input_relset->rel_plain; Path *cheapest_path = input_rel->cheapest_total_path; RelOptInfo *partially_grouped_rel = NULL; double dNumGroups; @@ -3971,13 +3976,25 @@ create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, if ((extra->flags & GROUPING_CAN_PARTIAL_AGG) != 0) { bool force_rel_creation; + RelOptInfo *input_rel_grouped = input_relset->rel_grouped; + bool have_agg_pushdown_paths; /* - * If we're doing partitionwise aggregation at this level, force - * creation of a partially_grouped_rel so we can add partitionwise - * paths to it. + * Check if the aggregate push-down feature succeeded to generate any + * paths. Dummy relation can appear here because grouped paths are not + * guaranteed to exist for a relation. */ - force_rel_creation = (patype == PARTITIONWISE_AGGREGATE_PARTIAL); + have_agg_pushdown_paths = input_rel_grouped != NULL && + input_rel_grouped->pathlist != NIL && + !IS_DUMMY_REL(input_rel_grouped); + + /* + * If we're doing partitionwise aggregation at this level or if + * aggregate push-down succeeded to create some paths, force creation + * of a partially_grouped_rel so we can add the related paths to it. + */ + force_rel_creation = patype == PARTITIONWISE_AGGREGATE_PARTIAL || + have_agg_pushdown_paths; partially_grouped_rel = create_partial_grouping_paths(root, @@ -3986,6 +4003,23 @@ create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, gd, extra, force_rel_creation); + + /* + * No further processing is needed for paths provided by the aggregate + * push-down feature. Simply add them to the partially grouped + * relation. + */ + if (have_agg_pushdown_paths) + { + ListCell *lc; + + foreach(lc, input_rel_grouped->pathlist) + { + Path *path = (Path *) lfirst(lc); + + add_path(partially_grouped_rel, path); + } + } } /* Set out parameter. */ @@ -4010,10 +4044,14 @@ create_ordinary_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel, /* Gather any partially grouped partial paths. */ if (partially_grouped_rel && partially_grouped_rel->partial_pathlist) - { gather_grouping_paths(root, partially_grouped_rel); + + /* + * The non-partial paths can come either from the Gather above or from + * aggregate push-down. + */ + if (partially_grouped_rel && partially_grouped_rel->pathlist) set_cheapest(partially_grouped_rel); - } /* * Estimate number of groups. @@ -6092,7 +6130,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple); /* Estimate the cost of seq scan + sort */ - seqScanPath = create_seqscan_path(root, rel, NULL, 0); + seqScanPath = create_seqscan_path(root, rel, NULL, 0, NULL, NULL); cost_sort(&seqScanAndSortPath, root, NIL, seqScanPath->total_cost, rel->tuples, rel->reltarget->width, comparisonCost, maintenance_work_mem, -1.0); @@ -6101,7 +6139,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) indexScanPath = create_index_path(root, indexInfo, NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, - NULL, 1.0, false); + NULL, 1.0, false, NULL, NULL); return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost); } @@ -7114,6 +7152,7 @@ create_partitionwise_grouping_paths(PlannerInfo *root, for (cnt_parts = 0; cnt_parts < nparts; cnt_parts++) { RelOptInfo *child_input_rel = input_rel->part_rels[cnt_parts]; + RelOptInfoSet *child_input_relset; PathTarget *child_target = copy_pathtarget(target); AppendRelInfo **appinfos; int nappinfos; @@ -7172,12 +7211,17 @@ create_partitionwise_grouping_paths(PlannerInfo *root, continue; } + child_input_relset = makeNode(RelOptInfoSet); + child_input_relset->rel_plain = child_input_rel; + /* Create grouping paths for this child relation. */ - create_ordinary_grouping_paths(root, child_input_rel, + create_ordinary_grouping_paths(root, child_input_relset, child_grouped_rel, agg_costs, gd, &child_extra, &child_partially_grouped_rel); + pfree(child_input_relset); + if (child_partially_grouped_rel) { partially_grouped_live_children = diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 0213a37670..d618007929 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -2300,6 +2300,39 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) /* No referent found for Var */ elog(ERROR, "variable not found in subplan target lists"); } + if (IsA(node, Aggref)) + { + Aggref *aggref = castNode(Aggref, node); + + /* + * The upper plan targetlist can contain Aggref whose value has + * already been evaluated by the subplan. However this can only happen + * with specific value of aggsplit. + */ + if (aggref->aggsplit == AGGSPLIT_INITIAL_SERIAL) + { + /* See if the Aggref has bubbled up from a lower plan node */ + if (context->outer_itlist && context->outer_itlist->has_non_vars) + { + newvar = search_indexed_tlist_for_non_var((Expr *) node, + context->outer_itlist, + OUTER_VAR); + if (newvar) + return (Node *) newvar; + } + if (context->inner_itlist && context->inner_itlist->has_non_vars) + { + newvar = search_indexed_tlist_for_non_var((Expr *) node, + context->inner_itlist, + INNER_VAR); + if (newvar) + return (Node *) newvar; + } + } + + /* No referent found for Aggref */ + elog(ERROR, "Aggref not found in subplan target lists"); + } if (IsA(node, PlaceHolderVar)) { PlaceHolderVar *phv = (PlaceHolderVar *) node; diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index aebe162713..9886c18bbd 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -891,6 +891,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, memset(subroot->upper_rels, 0, sizeof(subroot->upper_rels)); memset(subroot->upper_targets, 0, sizeof(subroot->upper_targets)); subroot->processed_tlist = NIL; + root->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 index b57de6b4c6..50bdf69b2e 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -17,6 +17,8 @@ #include #include "miscadmin.h" +#include "access/sysattr.h" +#include "catalog/pg_constraint.h" #include "foreign/fdwapi.h" #include "nodes/extensible.h" #include "nodes/nodeFuncs.h" @@ -58,7 +60,6 @@ static List *reparameterize_pathlist_by_child(PlannerInfo *root, List *pathlist, RelOptInfo *child_rel); - /***************************************************************************** * MISC. PATH UTILITIES *****************************************************************************/ @@ -953,13 +954,15 @@ add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, */ Path * create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, - Relids required_outer, int parallel_workers) + Relids required_outer, int parallel_workers, + RelOptInfo *rel_grouped, RelAggInfo *agg_info) { Path *pathnode = makeNode(Path); pathnode->pathtype = T_SeqScan; - pathnode->parent = rel; - pathnode->pathtarget = rel->reltarget; + pathnode->parent = rel_grouped == NULL ? rel : rel_grouped; + pathnode->pathtarget = rel_grouped == NULL ? rel->reltarget : + agg_info->input; pathnode->param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->parallel_aware = parallel_workers > 0 ? true : false; @@ -1019,6 +1022,10 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer * estimates of caching behavior. * 'partial_path' is true if constructing a parallel index scan path. * + * If 'rel_grouped' is passed, apply partial aggregation to each path and add + * the path to this relation instead of 'rel'. 'rel_agg_input' describes the + * aggregation input. 'agg_info' must be passed in such a case too. + * * Returns the new path node. */ IndexPath * @@ -1033,7 +1040,9 @@ create_index_path(PlannerInfo *root, bool indexonly, Relids required_outer, double loop_count, - bool partial_path) + bool partial_path, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info) { IndexPath *pathnode = makeNode(IndexPath); RelOptInfo *rel = index->rel; @@ -1041,8 +1050,9 @@ create_index_path(PlannerInfo *root, *indexqualcols; pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan; - pathnode->path.parent = rel; - pathnode->path.pathtarget = rel->reltarget; + pathnode->path.parent = rel_grouped == NULL ? rel : rel_grouped; + pathnode->path.pathtarget = rel_grouped == NULL ? rel->reltarget : + agg_info->input; pathnode->path.param_info = get_baserel_parampathinfo(root, rel, required_outer); pathnode->path.parallel_aware = false; @@ -1186,8 +1196,8 @@ create_bitmap_or_path(PlannerInfo *root, * Creates a path corresponding to a scan by TID, returning the pathnode. */ TidPath * -create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, - Relids required_outer) +create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, + List *tidquals, Relids required_outer) { TidPath *pathnode = makeNode(TidPath); @@ -1342,7 +1352,8 @@ append_startup_cost_compare(const void *a, const void *b) /* * create_merge_append_path * Creates a path corresponding to a MergeAppend plan, returning the - * pathnode. + * 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, @@ -1533,7 +1544,9 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, MemoryContext oldcontext; int numCols; - /* Caller made a mistake if subpath isn't cheapest_total ... */ + /* + * 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 */ @@ -2180,6 +2193,7 @@ calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path) * 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 @@ -2194,6 +2208,7 @@ calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path) NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -2234,7 +2249,7 @@ create_nestloop_path(PlannerInfo *root, pathnode->path.pathtype = T_NestLoop; pathnode->path.parent = joinrel; - pathnode->path.pathtarget = joinrel->reltarget; + pathnode->path.pathtarget = target; pathnode->path.param_info = get_joinrel_parampathinfo(root, joinrel, @@ -2266,6 +2281,7 @@ create_nestloop_path(PlannerInfo *root, * 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 @@ -2282,6 +2298,7 @@ create_nestloop_path(PlannerInfo *root, MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -2298,7 +2315,7 @@ create_mergejoin_path(PlannerInfo *root, pathnode->jpath.path.pathtype = T_MergeJoin; pathnode->jpath.path.parent = joinrel; - pathnode->jpath.path.pathtarget = joinrel->reltarget; + pathnode->jpath.path.pathtarget = target; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, @@ -2334,6 +2351,7 @@ create_mergejoin_path(PlannerInfo *root, * 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 @@ -2348,6 +2366,7 @@ create_mergejoin_path(PlannerInfo *root, HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -2362,7 +2381,7 @@ create_hashjoin_path(PlannerInfo *root, pathnode->jpath.path.pathtype = T_HashJoin; pathnode->jpath.path.parent = joinrel; - pathnode->jpath.path.pathtarget = joinrel->reltarget; + pathnode->jpath.path.pathtarget = target; pathnode->jpath.path.param_info = get_joinrel_parampathinfo(root, joinrel, @@ -2444,8 +2463,8 @@ create_projection_path(PlannerInfo *root, * 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)) + if ((is_projection_capable_path(subpath) || + equal(oldtarget->exprs, target->exprs))) { /* No separate Result node needed */ pathnode->dummypp = true; @@ -2830,8 +2849,7 @@ create_agg_path(PlannerInfo *root, 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.param_info = subpath->param_info; pathnode->path.parallel_aware = false; pathnode->path.parallel_safe = rel->consider_parallel && subpath->parallel_safe; @@ -2864,6 +2882,152 @@ create_agg_path(PlannerInfo *root, } /* + * Apply AGG_SORTED aggregation path to subpath if it's suitably sorted. + * + * NULL is returned if sorting of subpath output is not suitable. + */ +AggPath * +create_agg_sorted_path(PlannerInfo *root, Path *subpath, + RelAggInfo *agg_info) +{ + RelOptInfo *rel; + Node *agg_exprs; + AggSplit aggsplit; + AggClauseCosts agg_costs; + PathTarget *target; + double dNumGroups; + ListCell *lc1; + List *key_subset = NIL; + AggPath *result = NULL; + + rel = subpath->parent; + aggsplit = AGGSPLIT_INITIAL_SERIAL; + agg_exprs = (Node *) agg_info->agg_exprs; + target = agg_info->target; + + if (subpath->pathkeys == NIL) + return NULL; + + if (!grouping_is_sortable(root->parse->groupClause)) + return NULL; + + /* + * 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)); + get_agg_clause_costs(root, (Node *) agg_exprs, aggsplit, &agg_costs); + + Assert(agg_info->group_exprs != NIL); + dNumGroups = estimate_num_groups(root, agg_info->group_exprs, + subpath->rows, NULL); + + /* + * 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_SORTED, aggsplit, + agg_info->group_clauses, + NIL, + &agg_costs, + dNumGroups); + + return result; +} + +/* + * Apply AGG_HASHED aggregation to subpath. + * + * Arguments have the same meaning as those of create_agg_sorted_path. + */ +AggPath * +create_agg_hashed_path(PlannerInfo *root, Path *subpath, + RelAggInfo *agg_info) +{ + RelOptInfo *rel; + bool can_hash; + Node *agg_exprs; + AggSplit aggsplit; + AggClauseCosts agg_costs; + PathTarget *target; + double dNumGroups; + Size hashaggtablesize; + Query *parse = root->parse; + AggPath *result = NULL; + + rel = subpath->parent; + aggsplit = AGGSPLIT_INITIAL_SERIAL; + agg_exprs = (Node *) agg_info->agg_exprs; + target = agg_info->target; + + MemSet(&agg_costs, 0, sizeof(AggClauseCosts)); + get_agg_clause_costs(root, agg_exprs, aggsplit, &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, + subpath->rows, NULL); + + hashaggtablesize = estimate_hashagg_tablesize(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); + + /* + * 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 * @@ -3548,7 +3712,8 @@ reparameterize_path(PlannerInfo *root, Path *path, switch (path->pathtype) { case T_SeqScan: - return create_seqscan_path(root, rel, required_outer, 0); + return create_seqscan_path(root, rel, required_outer, 0, NULL, + NULL); case T_SampleScan: return (Path *) create_samplescan_path(root, rel, required_outer); case T_IndexScan: diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index f04c6b76f4..c54964ce64 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -17,16 +17,21 @@ #include #include "miscadmin.h" +#include "catalog/pg_class.h" +#include "catalog/pg_constraint.h" #include "optimizer/appendinfo.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" +#include "optimizer/optimizer.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/placeholder.h" #include "optimizer/plancat.h" +#include "optimizer/planner.h" #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" #include "optimizer/tlist.h" +#include "parser/parse_oper.h" #include "partitioning/partbounds.h" #include "utils/hsearch.h" @@ -34,7 +39,7 @@ typedef struct JoinHashEntry { Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; + RelOptInfoSet *join_relset; } JoinHashEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, @@ -54,7 +59,7 @@ static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, 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 add_join_rel(PlannerInfo *root, RelOptInfoSet *joinrelset); static void build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, List *restrictlist, JoinType jointype); @@ -63,6 +68,9 @@ static void build_child_join_reltarget(PlannerInfo *root, RelOptInfo *childrel, int nappinfos, AppendRelInfo **appinfos); +static bool init_grouping_targets(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, PathTarget *agg_input, + List *gvis, List **group_exprs_extra_p); /* @@ -323,6 +331,97 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent) } /* + * build_simple_grouped_rel + * Construct a new RelOptInfo for a grouped base relation out of an + * existing non-grouped relation. + */ +void +build_simple_grouped_rel(PlannerInfo *root, RelOptInfoSet *relset) +{ + RangeTblEntry *rte; + RelOptInfo *rel_plain, + *rel_grouped; + RelAggInfo *agg_info; + + /* Isn't there any grouping expression to be pushed down? */ + if (root->grouped_var_list == NIL) + return; + + rel_plain = relset->rel_plain; + + /* + * Not all RTE kinds are supported when grouping is considered. + * + * TODO Consider relaxing some of these restrictions. + */ + rte = root->simple_rte_array[rel_plain->relid]; + if (rte->rtekind != RTE_RELATION || + rte->relkind == RELKIND_FOREIGN_TABLE || + rte->tablesample != NULL) + return;; + + /* + * Grouped append relation is not supported yet. + */ + if (rte->inh) + return; + + /* + * Currently we do not support child relations ("other rels"). + */ + if (rel_plain->reloptkind != RELOPT_BASEREL) + return; + + /* + * Prepare the information we need for aggregation of the rel contents. + */ + agg_info = create_rel_agg_info(root, relset->rel_plain); + if (agg_info == NULL) + return; + + /* + * TODO Consider if 1) a flat copy is o.k., 2) it's safer in terms of + * adding new fields to RelOptInfo) to copy everything and then reset some + * fields, or to zero the structure and copy individual fields. + */ + rel_grouped = makeNode(RelOptInfo); + memcpy(rel_grouped, rel_plain, sizeof(RelOptInfo)); + + /* + * Note on consider_startup: while the AGG_HASHED strategy needs the whole + * relation, AGG_SORTED does not. Therefore we do not force + * consider_startup to false. + */ + + /* + * Set the appropriate target for grouped paths. + * + * The aggregation paths will get their input target from agg_info, so + * store it too. + */ + rel_grouped->reltarget = agg_info->target; + + /* + * Grouped paths must not be mixed with the plain ones. + */ + rel_grouped->pathlist = NIL; + rel_grouped->partial_pathlist = NIL; + rel_grouped->cheapest_startup_path = NULL; + rel_grouped->cheapest_total_path = NULL; + rel_grouped->cheapest_unique_path = NULL; + rel_grouped->cheapest_parameterized_paths = NIL; + + relset->rel_grouped = rel_grouped; + + /* + * The number of aggregation input rows is simply the number of rows of + * the non-grouped relation, which should have been estimated by now. + */ + agg_info->input_rows = rel_plain->rows; + relset->agg_info = agg_info; +} + +/* * find_base_rel * Find a base or other relation entry, which must already exist. */ @@ -371,16 +470,16 @@ build_join_rel_hash(PlannerInfo *root) /* Insert all the already-existing joinrels */ foreach(l, root->join_rel_list) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + RelOptInfoSet *relset = (RelOptInfoSet *) lfirst(l); JoinHashEntry *hentry; bool found; hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), + &(relset->rel_plain->relids), HASH_ENTER, &found); Assert(!found); - hentry->join_rel = rel; + hentry->join_relset = relset; } root->join_rel_hash = hashtab; @@ -391,7 +490,7 @@ build_join_rel_hash(PlannerInfo *root) * Returns relation entry corresponding to 'relids' (a set of RT indexes), * or NULL if none exists. This is for join relations. */ -RelOptInfo * +RelOptInfoSet * find_join_rel(PlannerInfo *root, Relids relids) { /* @@ -419,7 +518,13 @@ find_join_rel(PlannerInfo *root, Relids relids) HASH_FIND, NULL); if (hentry) - return hentry->join_rel; + { + RelOptInfoSet *result = hentry->join_relset;; + + /* The plain relation should always be there. */ + Assert(result->rel_plain != NULL); + return result; + } } else { @@ -427,10 +532,10 @@ find_join_rel(PlannerInfo *root, Relids relids) foreach(l, root->join_rel_list) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + RelOptInfoSet *result = (RelOptInfoSet *) lfirst(l); - if (bms_equal(rel->relids, relids)) - return rel; + if (bms_equal(result->rel_plain->relids, relids)) + return result; } } @@ -493,23 +598,26 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, * PlannerInfo. Also add it to the auxiliary hashtable if there is one. */ static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +add_join_rel(PlannerInfo *root, RelOptInfoSet *joinrelset) { - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); + /* + * GEQO requires us to append the new joinrel to the end of the list! + */ + root->join_rel_list = lappend(root->join_rel_list, joinrelset); /* store it into the auxiliary hashtable if there is one. */ if (root->join_rel_hash) { JoinHashEntry *hentry; bool found; + Relids relids = joinrelset->rel_plain->relids; hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), + &relids, HASH_ENTER, &found); Assert(!found); - hentry->join_rel = joinrel; + hentry->join_relset = joinrelset; } } @@ -525,6 +633,8 @@ add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr * receives the list of RestrictInfo nodes that apply to this * particular pair of joinable relations. + * 'agg_info' contains information needed for the join to form grouped + * paths. If NULL, the join is not grouped. * * restrictlist_ptr makes the routine's API a little grotty, but it saves * duplicated calculation of the restrictlist... @@ -535,10 +645,20 @@ build_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, - List **restrictlist_ptr) + List **restrictlist_ptr, + RelAggInfo *agg_info) { + RelOptInfoSet *joinrelset; + bool new_set = false; RelOptInfo *joinrel; List *restrictlist; + bool grouped = agg_info != NULL; + bool create_target; + + /* + * Target for grouped relation will be supplied by caller. + */ + create_target = !grouped; /* This function should be used only for join between parents. */ Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel)); @@ -546,7 +666,19 @@ build_join_rel(PlannerInfo *root, /* * See if we already have a joinrel for this set of base rels. */ - joinrel = find_join_rel(root, joinrelids); + joinrelset = find_join_rel(root, joinrelids); + if (joinrelset == NULL) + { + /* + * The plain joinrel should be the first one to be added to the set. + */ + Assert(!grouped); + + joinrelset = makeNode(RelOptInfoSet); + new_set = true; + } + + joinrel = !grouped ? joinrelset->rel_plain : joinrelset->rel_grouped; if (joinrel) { @@ -573,7 +705,7 @@ build_join_rel(PlannerInfo *root, joinrel->consider_startup = (root->tuple_fraction > 0); joinrel->consider_param_startup = false; joinrel->consider_parallel = false; - joinrel->reltarget = create_empty_pathtarget(); + joinrel->reltarget = NULL; joinrel->pathlist = NIL; joinrel->ppilist = NIL; joinrel->partial_pathlist = NIL; @@ -638,9 +770,13 @@ build_join_rel(PlannerInfo *root, * 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); + 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 @@ -676,45 +812,68 @@ build_join_rel(PlannerInfo *root, sjinfo->jointype); /* - * Set estimates of the joinrel's size. + * Assign the joinrel to the set. */ - set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, - sjinfo, restrictlist); + if (!grouped) + joinrelset->rel_plain = joinrel; + else + { + joinrelset->rel_grouped = joinrel; + joinrelset->agg_info = agg_info; + } - /* - * 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; + if (new_set) + { + /* Add the joinrelset to the PlannerInfo. */ + add_join_rel(root, joinrelset); - /* Add the joinrel to the PlannerInfo. */ - add_join_rel(root, joinrel); + /* + * Also, if dynamic-programming join search is active, add the new + * joinrelset to the appropriate sublist. Note: you might think the + * Assert on number 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(joinrelids)); + root->join_rel_level[root->join_cur_level] = + lappend(root->join_rel_level[root->join_cur_level], + joinrelset); + } + } /* - * Also, if dynamic-programming join search is active, add the new joinrel - * to the appropriate sublist. Note: you might think the Assert on number - * of members should be for equality, but some of the level 1 rels might - * have been joinrels already, so we can only assert <=. + * Set estimates of the joinrel's size. + * + * XXX set_joinrel_size_estimates() 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 (root->join_rel_level) + if (create_target) { - 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); + 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; } return joinrel; @@ -741,6 +900,7 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, JoinType jointype) { RelOptInfo *joinrel = makeNode(RelOptInfo); + RelOptInfoSet *joinrelset = makeNode(RelOptInfoSet); AppendRelInfo **appinfos; int nappinfos; @@ -852,7 +1012,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, Assert(!find_join_rel(root, joinrel->relids)); /* Add the relation to the PlannerInfo. */ - add_join_rel(root, joinrel); + joinrelset->rel_plain = joinrel; + add_join_rel(root, joinrelset); return joinrel; } @@ -1749,3 +1910,626 @@ build_child_join_reltarget(PlannerInfo *root, childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple; childrel->reltarget->width = parentrel->reltarget->width; } + +/* + * 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; + bool found_other_rel_agg; + ListCell *lc; + RelAggInfo *result; + PathTarget *agg_input; + PathTarget *target = NULL; + List *grp_exprs_extra = NIL; + List *group_clauses_final; + int i; + + /* + * The function shouldn't have been called if there's no opportunity for + * aggregation push-down. + */ + Assert(root->grouped_var_list != NIL); + + result = makeNode(RelAggInfo); + + /* + * 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 Aggref argument), we'd just let + * init_grouping_targets add that Aggref. On the other hand, if we knew + * that the PHV is evaluated below the current rel, we could ignore it + * because the referencing Aggref would take care of propagation of the + * value to upper joins. + * + * 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_other_rel_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. + */ + if (IsA(gvi->gvexpr, Var)) + continue; + + /* + * Currently, GroupedVarInfo only handles Vars and Aggrefs. + */ + Assert(IsA(gvi->gvexpr, Aggref)); + + /* We only derive grouped expressions using ECs, not aggregates */ + Assert(!gvi->derived); + + gvi->agg_partial = (Aggref *) copyObject(gvi->gvexpr); + mark_partial_aggref(gvi->agg_partial, AGGSPLIT_INITIAL_SERIAL); + + /* + * Accept the aggregate. + */ + aggregates = lappend(aggregates, gvi); + } + else if (IsA(gvi->gvexpr, Aggref)) + { + /* + * Remember that there is at least one aggregate expression that + * needs something else than this rel. + */ + found_other_rel_agg = true; + + /* + * This condition effectively terminates creation of the + * RelAggInfo, so there's no reason to check the next + * GroupedVarInfo. + */ + break; + } + } + + /* + * 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 relations other than the + * current one. + * + * If the aggregate needs the current rel plus anything else, then 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. + * + * If the aggregate does not even need the current rel, then neither the + * current rel nor anything else should be grouped because we do not + * support join of two grouped relations. + */ + if (found_other_rel_agg) + { + list_free(gvis); + return NULL; + } + + /* + * Create target for grouped paths as well as one for the input paths of + * the aggregation paths. + */ + target = create_empty_pathtarget(); + agg_input = create_empty_pathtarget(); + + /* + * Cannot suitable targets for the aggregation push-down be derived? + */ + if (!init_grouping_targets(root, rel, target, agg_input, gvis, + &grp_exprs_extra)) + { + list_free(gvis); + return NULL; + } + + list_free(gvis); + + /* + * Aggregation push-down makes no sense w/o grouping expressions. + */ + if ((list_length(target->exprs) + list_length(grp_exprs_extra)) == 0) + return NULL; + + group_clauses_final = root->parse->groupClause; + + /* + * If the aggregation target should have extra grouping expressions (in + * order to emit input vars for join conditions), add them now. This step + * includes assignment of tleSortGroupRef's which we can generate now. + */ + if (list_length(grp_exprs_extra) > 0) + { + Index sortgroupref; + + /* + * We'll have to add some clauses, but query group clause must be + * preserved. + */ + group_clauses_final = list_copy(group_clauses_final); + + /* + * 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); + + /* + * Initialize the SortGroupClause. + * + * As the final aggregation will not use this grouping expression, + * we don't care whether sortop is < or >. The value of + * nulls_first should not matter for the same reason. + */ + cl->tleSortGroupRef = ++sortgroupref; + get_sort_group_operators(var->vartype, + false, true, false, + &cl->sortop, &cl->eqop, NULL, + &cl->hashable); + group_clauses_final = lappend(group_clauses_final, cl); + add_column_to_pathtarget(target, (Expr *) var, + cl->tleSortGroupRef); + + /* + * The aggregation input target must emit this var too. + */ + add_column_to_pathtarget(agg_input, (Expr *) var, + cl->tleSortGroupRef); + } + } + + /* + * Add aggregates to the grouping target. + */ + add_aggregates_to_target(root, target, aggregates); + + /* + * 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, Aggref)) + { + /* + * Once we see Aggref, no grouping expressions should follow. + */ + 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; + + /* + * group_clause_final contains the "local" clauses, so this search + * should succeed. + */ + cl = get_sortgroupref_clause(sortgroupref, group_clauses_final); + + 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); + } + + /* + * Since neither target nor agg_input is supposed to be identical to the + * source reltarget, compute the width and cost again. + * + * target does not yet contain aggregates, but these will be accounted by + * AggPath. + */ + set_pathtarget_cost_width(root, target); + set_pathtarget_cost_width(root, agg_input); + + result->target = target; + result->input = agg_input; + + /* Finally collect the aggregates. */ + while (lc != NULL) + { + Aggref *aggref = lfirst_node(Aggref, lc); + + /* + * Partial aggregation is what the grouped paths should do. + */ + result->agg_exprs = lappend(result->agg_exprs, aggref); + lc = lnext(lc); + } + + /* + * The "input_rows" field should be set by caller. + */ + return result; +} + +/* + * Initialize target for grouped paths (target) as well as a target for paths + * that generate input for aggregation (agg_input). + * + * group_exprs_extra_p receives a list of Var nodes for which we need to + * construct SortGroupClause. Those vars will then be used as additional + * grouping expressions, for the sake of join clauses. + * + * gvis a list of GroupedVarInfo's possibly useful for rel. + * + * Return true iff the targets could be initialized. + */ +static bool +init_grouping_targets(PlannerInfo *root, RelOptInfo *rel, + PathTarget *target, PathTarget *agg_input, + List *gvis, List **group_exprs_extra_p) +{ + ListCell *lc1, + *lc2; + List *unresolved = NIL; + List *unresolved_sortgrouprefs = NIL; + + foreach(lc1, rel->reltarget->exprs) + { + Var *tvar; + bool is_grouping; + Index sortgroupref = 0; + bool derived = false; + bool needed_by_aggregate; + + /* + * Given that PlaceHolderVar currently prevents us from doing + * aggregation push-down, the source target cannot contain anything + * more complex than a Var. + */ + tvar = lfirst_node(Var, lc1); + + is_grouping = is_grouping_expression(gvis, (Expr *) tvar, + &sortgroupref, &derived); + + /* + * Derived grouping expressions should not be referenced by the query + * targetlist, so let them fall into vars_unresolved. It'll be checked + * later if the current targetlist needs them. For example, we should + * not automatically use Var as a grouping expression if the only + * reason for it to be in the plain relation target is that it's + * referenced by aggregate argument, and it happens to be in the same + * EC as any grouping expression. + */ + if (is_grouping && !derived) + { + Assert(sortgroupref > 0); + + /* + * It's o.k. to use the target expression for grouping. + */ + add_column_to_pathtarget(target, (Expr *) tvar, sortgroupref); + + /* + * As for agg_input, add the original expression but set + * sortgroupref in addition. + */ + add_column_to_pathtarget(agg_input, (Expr *) tvar, sortgroupref); + + /* Process the next expression. */ + continue; + } + + /* + * Is this Var needed in the query targetlist for anything else than + * aggregate input? + */ + needed_by_aggregate = false; + foreach(lc2, root->grouped_var_list) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, lc2); + ListCell *lc3; + List *vars; + + if (!IsA(gvi->gvexpr, Aggref)) + continue; + + if (!bms_is_member(tvar->varno, gvi->gv_eval_at)) + continue; + + /* + * XXX Consider some sort of caching. + */ + vars = pull_var_clause((Node *) gvi->gvexpr, PVC_RECURSE_AGGREGATES); + foreach(lc3, vars) + { + Var *var = lfirst_node(Var, lc3); + + if (equal(var, tvar)) + { + needed_by_aggregate = true; + break; + } + } + list_free(vars); + if (needed_by_aggregate) + break; + } + + if (needed_by_aggregate) + { + bool found = false; + + foreach(lc2, root->processed_tlist) + { + TargetEntry *te = lfirst_node(TargetEntry, lc2); + + if (IsA(te->expr, Aggref)) + continue; + + if (equal(te->expr, tvar)) + { + found = true; + break; + } + } + + /* + * If it's only Aggref input, add it to the aggregation input + * target and that's it. + */ + if (!found) + { + add_new_column_to_pathtarget(agg_input, (Expr *) tvar); + continue; + } + } + + /* + * Further investigation involves dependency check, for which we need + * to have all the (plain-var) grouping expressions gathered. + */ + unresolved = lappend(unresolved, tvar); + unresolved_sortgrouprefs = lappend_int(unresolved_sortgrouprefs, + sortgroupref); + } + + /* + * Check for other possible reasons for the var to be in the plain target. + */ + forboth(lc1, unresolved, lc2, unresolved_sortgrouprefs) + { + Var *var = lfirst_node(Var, lc1); + Index sortgroupref = lfirst_int(lc2); + RangeTblEntry *rte; + List *deps = NIL; + Relids relids_subtract; + int ndx; + RelOptInfo *baserel; + + rte = root->simple_rte_array[var->varno]; + + /* + * Check if the Var can be in the grouping key even though it's not + * mentioned by the GROUP BY clause (and could not be derived using + * ECs). + */ + if (sortgroupref == 0 && + check_functional_grouping(rte->relid, var->varno, + var->varlevelsup, + target->exprs, &deps)) + { + /* + * 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. + */ + add_new_column_to_pathtarget(target, (Expr *) var); + add_new_column_to_pathtarget(agg_input, (Expr *) var); + + /* + * The var may or may not be present in generic grouping + * expression(s) in addition, but this is handled elsewhere. + */ + 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 aggregation is pushed down, the aggregates in the + * query targetlist 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 a join involving this relation. That + * case includes variable that is referenced by a generic grouping + * expression. + * + * The only way to bring this var to the aggregation output is to + * add it to the grouping expressions too. + */ + if (sortgroupref > 0) + { + /* + * The var could be recognized as a potentially useful + * grouping expression at the top of the loop, so we can add + * it to the grouping target, as well as to the agg_input. + */ + add_column_to_pathtarget(target, (Expr *) var, sortgroupref); + add_column_to_pathtarget(agg_input, (Expr *) var, sortgroupref); + } + else + { + /* + * 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_agg, 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 by a generic grouping + * expression but not referenced by any join. + * + * create_rel_agg_info() should add this variable to "agg_input" + * target and also add the whole generic expression to "target", + * but that's subject to future enhancement of the aggregate + * push-down feature. + */ + return false; + } + } + + return true; +} diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c index 14d1c67a94..bf820fe66c 100644 --- a/src/backend/optimizer/util/tlist.c +++ b/src/backend/optimizer/util/tlist.c @@ -427,7 +427,6 @@ get_sortgrouplist_exprs(List *sgClauses, List *targetList) return result; } - /***************************************************************************** * Functions to extract data from a list of SortGroupClauses * @@ -802,6 +801,62 @@ apply_pathtarget_labeling_to_tlist(List *tlist, PathTarget *target) } /* + * For each aggregate grouping expression or aggregate to the grouped target. + * + * Caller passes the expressions in the form of GroupedVarInfos so that we + * don't have to look for gvid. + */ +void +add_aggregates_to_target(PlannerInfo *root, PathTarget *target, + List *expressions) +{ + ListCell *lc; + + /* Create the vars and add them to the target. */ + foreach(lc, expressions) + { + GroupedVarInfo *gvi; + + gvi = lfirst_node(GroupedVarInfo, lc); + add_column_to_pathtarget(target, (Expr *) gvi->agg_partial, + gvi->sortgroupref); + } +} + +/* + * Find out if expr can be used as grouping expression in reltarget. + * + * sortgroupref and is_derived reflect the ->sortgroupref and ->derived fields + * of the corresponding GroupedVarInfo. + */ +bool +is_grouping_expression(List *gvis, Expr *expr, Index *sortgroupref, + bool *is_derived) +{ + ListCell *lc; + + foreach(lc, gvis) + { + GroupedVarInfo *gvi = lfirst_node(GroupedVarInfo, lc); + + if (IsA(gvi->gvexpr, Aggref)) + continue; + + if (equal(gvi->gvexpr, expr)) + { + Assert(gvi->sortgroupref > 0); + + *sortgroupref = gvi->sortgroupref; + *is_derived = gvi->derived; + return true; + } + } + + /* The expression cannot be used as grouping key. */ + return false; +} + +/* * split_pathtarget_at_srfs * Split given PathTarget into multiple levels to position SRFs safely * diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 67e268cc7a..0cc56f8b66 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -4884,8 +4884,12 @@ examine_variable(PlannerInfo *root, Node *node, int varRelid, case BMS_MULTIPLE: if (varRelid == 0) { + RelOptInfoSet *relset; + /* treat it as a variable of a join relation */ - vardata->rel = find_join_rel(root, varnos); + relset = find_join_rel(root, varnos); + if (relset) + vardata->rel = relset->rel_plain; node = basenode; /* strip any relabeling */ } else if (bms_is_member(varRelid, varnos)) @@ -5743,7 +5747,13 @@ find_join_input_rel(PlannerInfo *root, Relids relids) rel = find_base_rel(root, bms_singleton_member(relids)); break; case BMS_MULTIPLE: - rel = find_join_rel(root, relids); + { + RelOptInfoSet *relset; + + relset = find_join_rel(root, relids); + if (relset) + rel = relset->rel_plain; + } break; } diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c index 8681ada33a..52b1204345 100644 --- a/src/backend/utils/misc/guc.c +++ b/src/backend/utils/misc/guc.c @@ -1007,6 +1007,15 @@ static struct config_bool ConfigureNamesBool[] = 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 index e215ad4978..96fa16c2d3 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -223,6 +223,8 @@ typedef enum NodeTag T_IndexOptInfo, T_ForeignKeyOptInfo, T_ParamPathInfo, + T_RelAggInfo, + T_RelOptInfoSet, T_Path, T_IndexPath, T_BitmapHeapPath, @@ -266,6 +268,7 @@ typedef enum NodeTag T_SpecialJoinInfo, T_AppendRelInfo, T_PlaceHolderInfo, + T_GroupedVarInfo, T_MinMaxAggInfo, T_PlannerParamItem, T_RollupData, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index d3c477a542..60b059ad05 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -284,6 +284,8 @@ struct PlannerInfo 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() */ @@ -296,7 +298,7 @@ struct PlannerInfo List *part_schemes; /* Canonicalised partition schemes used in the * query. */ - List *initial_rels; /* RelOptInfos we are now trying to join */ + List *initial_rels; /* RelOptInfoSets we are now trying to join */ /* Use fetch_upper_rel() to get any particular upper rel */ List *upper_rels[UPPERREL_FINAL + 1]; /* upper-rel RelOptInfos */ @@ -310,6 +312,12 @@ struct PlannerInfo */ 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 */ @@ -734,6 +742,82 @@ typedef struct RelOptInfo (rel)->part_rels && (rel)->partexprs && (rel)->nullable_partexprs) /* + * RelAggInfo + * + * RelOptInfo needs information contained here if its paths should be + * aggregated. + * + * "target" will be used as pathtarget for aggregation if "explicit + * aggregation" is applied to base relation or join. The same target will also + * --- if the relation is a join --- be used to joinin grouped path to a + * non-grouped one. + * + * These targets contain plain-Var grouping expressions and Aggrefs which. + * Once Aggref is evaluated, its value is passed to the upper paths w/o being + * evaluated again. + * + * Note: There's a convention that Aggref expressions are supposed to follow + * the other expressions of the target. Iterations of ->exprs may rely on this + * arrangement. + * + * "input" contains Vars used either as grouping expressions or aggregate + * arguments. Paths providing the aggregation plan with input data should use + * this target. + * + * "input_rows" is the estimated number of input rows for AggPath. It's + * 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. + * + * "agg_exprs" is a list of Aggref nodes for the aggregation of the relation's + * paths. + */ +typedef struct RelAggInfo +{ + NodeTag type; + + struct PathTarget *target; /* Target for grouped paths.. */ + + struct PathTarget *input; /* pathtarget of paths that generate input for + * aggregation paths. */ + double input_rows; + + List *group_clauses; + List *group_exprs; + + List *agg_exprs; /* Aggref expressions. */ +} RelAggInfo; + +/* + * RelOptInfoSet + * + * Structure to use where RelOptInfo for other UpperRelationKind than + * UPPERREL_FINAL may be needed. Currently we only need UPPERREL_FINAL + * and UPPERREL_PARTIAL_GROUP_AGG. + * + * rel_plain should always be initialized. Code paths that do not + * distinguish between plain and grouped relation use rel_plain, + * e.g. has_legal_joinclause(). + * + * agg_info is initialized iff rel_grouped is. + * + * XXX Is RelOptInfoPair more appropriate name? + */ +typedef struct RelOptInfoSet +{ + NodeTag type; + + RelOptInfo *rel_plain; /* UPPERREL_FINAL */ + RelOptInfo *rel_grouped; /* UPPERREL_PARTIAL_GROUP_AGG */ + + RelAggInfo *agg_info; /* Information needed to create rel_grouped + * and its paths. It seems just convenient to + * store it here. */ +} RelOptInfoSet; + +/* * IndexOptInfo * Per-index information for planning/optimization * @@ -2214,6 +2298,26 @@ typedef struct PlaceHolderInfo } PlaceHolderInfo; /* + * GroupedVarInfo exists for each expression that can be used as an aggregate + * or grouping expression evaluated below a join. + */ +typedef struct GroupedVarInfo +{ + NodeTag type; + + 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. */ + bool derived; /* derived from another GroupedVarInfo using + * equeivalence classes? */ +} 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. @@ -2320,6 +2424,11 @@ typedef struct SemiAntiJoinFactors * sjinfo is extra info about special joins for selectivity estimation * semifactors is as shown above (only valid for SEMI/ANTI/inner_unique joins) * param_source_rels are OK targets for parameterization of result paths + * agg_info passes information necessary for joins to produce partially + * grouped data. + * rel_agg_input describes the AggPath input relation if the join output + * should be aggregated. If NULL is passed, do not aggregate the join + * output. */ typedef struct JoinPathExtraData { @@ -2329,6 +2438,8 @@ typedef struct JoinPathExtraData SpecialJoinInfo *sjinfo; SemiAntiJoinFactors semifactors; Relids param_source_rels; + RelAggInfo *agg_info; + RelOptInfo *rel_agg_input; } JoinPathExtraData; /* diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h index 23073c0402..25ab90e7f2 100644 --- a/src/include/optimizer/clauses.h +++ b/src/include/optimizer/clauses.h @@ -56,4 +56,6 @@ extern void CommuteRowCompareExpr(RowCompareExpr *clause); 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 index ac6de0f6be..b9757c31fd 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -64,6 +64,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate; extern PGDLLIMPORT bool enable_parallel_append; extern PGDLLIMPORT bool enable_parallel_hash; extern PGDLLIMPORT bool enable_partition_pruning; +extern PGDLLIMPORT bool enable_agg_pushdown; extern PGDLLIMPORT int constraint_exclusion; extern double index_pages_fetched(double tuples_fetched, BlockNumber pages, @@ -171,7 +172,8 @@ extern void compute_semi_anti_join_factors(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors); -extern void set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel); +extern void set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel, + RelAggInfo *agg_info); extern double get_parameterized_baserel_size(PlannerInfo *root, RelOptInfo *rel, List *param_clauses); diff --git a/src/include/optimizer/geqo.h b/src/include/optimizer/geqo.h index 5b3327665e..8a4054b59a 100644 --- a/src/include/optimizer/geqo.h +++ b/src/include/optimizer/geqo.h @@ -78,7 +78,7 @@ typedef struct /* routines in geqo_main.c */ -extern RelOptInfo *geqo(PlannerInfo *root, +extern RelOptInfoSet *geqo(PlannerInfo *root, int number_of_rels, List *initial_rels); /* routines in geqo_eval.c */ diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index d0c8f99d0a..88b460ee58 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -35,7 +35,8 @@ extern bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys); extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, - Relids required_outer, int parallel_workers); + Relids required_outer, int parallel_workers, + RelOptInfo *rel_grouped, RelAggInfo *agg_info); extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer); extern IndexPath *create_index_path(PlannerInfo *root, @@ -49,7 +50,9 @@ extern IndexPath *create_index_path(PlannerInfo *root, bool indexonly, Relids required_outer, double loop_count, - bool partial_path); + bool partial_path, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, @@ -127,6 +130,7 @@ extern Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_pat extern NestPath *create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -138,6 +142,7 @@ extern NestPath *create_nestloop_path(PlannerInfo *root, extern MergePath *create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -152,6 +157,7 @@ extern MergePath *create_mergejoin_path(PlannerInfo *root, extern HashPath *create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, + PathTarget *target, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, @@ -200,6 +206,12 @@ extern AggPath *create_agg_path(PlannerInfo *root, List *qual, const AggClauseCosts *aggcosts, double numGroups); +extern AggPath *create_agg_sorted_path(PlannerInfo *root, + Path *subpath, + RelAggInfo *agg_info); +extern AggPath *create_agg_hashed_path(PlannerInfo *root, + Path *subpath, + RelAggInfo *agg_info); extern GroupingSetsPath *create_groupingsets_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, @@ -267,14 +279,16 @@ extern void setup_simple_rel_arrays(PlannerInfo *root); extern void setup_append_rel_array(PlannerInfo *root); extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent); +extern void build_simple_grouped_rel(PlannerInfo *root, RelOptInfoSet *rel); extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid); -extern RelOptInfo *find_join_rel(PlannerInfo *root, Relids relids); +extern RelOptInfoSet *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); + List **restrictlist_ptr, + RelAggInfo *agg_info); extern Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, @@ -300,5 +314,5 @@ extern RelOptInfo *build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, SpecialJoinInfo *sjinfo, JoinType jointype); - +extern RelAggInfo *create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel); #endif /* PATHNODE_H */ diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 1b02b3b889..ad9439439d 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -21,6 +21,7 @@ * 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; @@ -29,7 +30,9 @@ extern PGDLLIMPORT int min_parallel_index_scan_size; typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, - RangeTblEntry *rte); + RangeTblEntry *rte, + RelOptInfo *rel_grouped, + RelAggInfo *agg_info); extern PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook; /* Hook for plugins to get control in add_paths_to_joinrel() */ @@ -42,19 +45,24 @@ typedef void (*set_join_pathlist_hook_type) (PlannerInfo *root, 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); +typedef RelOptInfoSet *(*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 RelOptInfoSet *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, +extern RelOptInfoSet *standard_join_search(PlannerInfo *root, + int levels_needed, List *initial_rels); extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows); + +extern bool add_grouped_path(PlannerInfo *root, RelOptInfo *rel, + Path *subpath, AggStrategy aggstrategy, + RelAggInfo *agg_info); 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, @@ -70,7 +78,8 @@ extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel); * indxpath.c * routines to generate index paths */ -extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel); +extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel, + RelOptInfo *rel_grouped, RelAggInfo *agg_info); extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist); @@ -101,7 +110,9 @@ extern void create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel); extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, - List *restrictlist); + List *restrictlist, + RelAggInfo *agg_info, + RelOptInfo *rel_agg_input); /* * joinrels.c @@ -109,7 +120,7 @@ extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, */ extern void join_search_one_level(PlannerInfo *root, int level); extern RelOptInfo *make_join_rel(PlannerInfo *root, - RelOptInfo *rel1, RelOptInfo *rel2); + RelOptInfoSet *relset1, RelOptInfoSet *relset2); extern bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); extern bool have_dangerous_phv(PlannerInfo *root, diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 3bbdb5e2f7..75e48185a3 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -27,7 +27,7 @@ typedef void (*query_pathkeys_callback) (PlannerInfo *root, void *extra); /* * prototypes for plan/planmain.c */ -extern RelOptInfo *query_planner(PlannerInfo *root, List *tlist, +extern RelOptInfoSet *query_planner(PlannerInfo *root, List *tlist, query_pathkeys_callback qp_callback, void *qp_extra); /* @@ -68,6 +68,7 @@ extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode); 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 setup_aggregate_pushdown(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 index 58db79203b..fa927cd6f4 100644 --- a/src/include/optimizer/tlist.h +++ b/src/include/optimizer/tlist.h @@ -49,6 +49,13 @@ extern void split_pathtarget_at_srfs(PlannerInfo *root, 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 void add_aggregates_to_target(PlannerInfo *root, PathTarget *target, + List *expressions); +extern bool is_grouping_expression(List *gvis, Expr *expr, + Index *sortgroupref, bool *is_derived); + /* 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/test/regress/parallel_schedule b/src/test/regress/parallel_schedule index 4051a4ad4e..22058b1f91 100644 --- a/src/test/regress/parallel_schedule +++ b/src/test/regress/parallel_schedule @@ -104,6 +104,9 @@ test: rules psql_crosstab amutils 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 index ac1ea622d6..bc1ed68a9e 100644 --- a/src/test/regress/serial_schedule +++ b/src/test/regress/serial_schedule @@ -136,6 +136,7 @@ test: rules test: psql_crosstab test: select_parallel test: write_parallel +test: agg_pushdown test: publication test: subscription test: amutils diff --git a/src/test/regress/expected/agg_pushdown.out b/src/test/regress/expected/agg_pushdown.out new file mode 100644 index 0000000000..b3a97f86d6 --- /dev/null +++ b/src/test/regress/expected/agg_pushdown.out @@ -0,0 +1,217 @@ +BEGIN; +CREATE TABLE agg_pushdown_parent ( + i int primary key, + x int); +CREATE TABLE agg_pushdown_child1 ( + j int, + parent int references agg_pushdown_parent, + v double precision, + PRIMARY KEY (j, parent)); +CREATE INDEX ON agg_pushdown_child1(parent); +CREATE TABLE agg_pushdown_child2 ( + k int, + parent int references agg_pushdown_parent, + v double precision, + PRIMARY KEY (k, parent));; +INSERT INTO agg_pushdown_parent(i, x) +SELECT n, n +FROM generate_series(0, 7) AS s(n); +INSERT INTO agg_pushdown_child1(j, parent, v) +SELECT 128 * i + n, i, random() +FROM generate_series(0, 127) AS s(n), agg_pushdown_parent; +INSERT INTO agg_pushdown_child2(k, parent, v) +SELECT 128 * i + n, i, random() +FROM generate_series(0, 127) AS s(n), agg_pushdown_parent; +COMMIT; +ANALYZE; +SET enable_agg_pushdown TO on; +SET enable_nestloop TO on; +SET enable_hashjoin TO off; +SET enable_mergejoin TO off; +-- Perform scan of a table, aggregate the result, join it to the other table +-- and finalize the aggregation. +-- +-- In addition, check that functionally dependent column "c.x" can be +-- referenced by SELECT although GROUP BY references "p.i". +EXPLAIN (COSTS off) +SELECT p.x, 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 + -> Sort + Sort Key: p.i + -> Nested Loop + -> Partial HashAggregate + Group Key: c1.parent + -> Seq Scan on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) +(10 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) 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 + -> 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 + -> Seq Scan on agg_pushdown_child1 c1 +(11 rows) + +-- The same for merge join. +SET enable_hashjoin TO off; +SET enable_mergejoin 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 GroupAggregate + Group Key: p.i + -> Merge Join + Merge Cond: (p.i = c1.parent) + -> Sort + Sort Key: p.i + -> Seq Scan on agg_pushdown_parent p + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: c1.parent + -> Seq Scan on agg_pushdown_child1 c1 +(12 rows) + +SET enable_nestloop TO on; +SET enable_hashjoin TO on; +-- Scan index on agg_pushdown_child1(parent) column and 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; +-- Join "c1" to "p.x" column, i.e. one that is not in the GROUP BY clause. The +-- planner should still use "c1.parent" as grouping expression for partial +-- aggregation, although it's not in the same equivalence class as the GROUP +-- BY expression ("p.i"). The reason to use "c1.parent" for partial +-- aggregation is that this is the only way for "c1" to provide the join +-- expression with input data. +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.x GROUP BY p.i; + QUERY PLAN +------------------------------------------------------------------ + Finalize GroupAggregate + Group Key: p.i + -> Sort + Sort Key: p.i + -> Hash Join + Hash Cond: (p.x = c1.parent) + -> Seq Scan on agg_pushdown_parent p + -> Hash + -> Partial HashAggregate + Group Key: c1.parent + -> Seq Scan on agg_pushdown_child1 c1 +(11 rows) + +-- Perform nestloop join between agg_pushdown_child1 and agg_pushdown_child2 +-- and 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) AND (parent = c1.parent)) + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) +(13 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) AND (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 +(13 rows) + diff --git a/src/test/regress/sql/agg_pushdown.sql b/src/test/regress/sql/agg_pushdown.sql new file mode 100644 index 0000000000..6cf2ed9c20 --- /dev/null +++ b/src/test/regress/sql/agg_pushdown.sql @@ -0,0 +1,117 @@ +BEGIN; + +CREATE TABLE agg_pushdown_parent ( + i int primary key, + x int); + +CREATE TABLE agg_pushdown_child1 ( + j int, + parent int references agg_pushdown_parent, + v double precision, + PRIMARY KEY (j, parent)); + +CREATE INDEX ON agg_pushdown_child1(parent); + +CREATE TABLE agg_pushdown_child2 ( + k int, + parent int references agg_pushdown_parent, + v double precision, + PRIMARY KEY (k, parent));; + +INSERT INTO agg_pushdown_parent(i, x) +SELECT n, n +FROM generate_series(0, 7) AS s(n); + +INSERT INTO agg_pushdown_child1(j, parent, v) +SELECT 128 * i + n, i, random() +FROM generate_series(0, 127) AS s(n), agg_pushdown_parent; + +INSERT INTO agg_pushdown_child2(k, parent, v) +SELECT 128 * i + n, i, random() +FROM generate_series(0, 127) AS s(n), agg_pushdown_parent; + +COMMIT; +ANALYZE; + +SET enable_agg_pushdown TO on; + +SET enable_nestloop TO on; +SET enable_hashjoin TO off; +SET enable_mergejoin TO off; + +-- Perform scan of a table, aggregate the result, join it to the other table +-- and finalize the aggregation. +-- +-- In addition, check that functionally dependent column "c.x" can be +-- referenced by SELECT although GROUP BY references "p.i". +EXPLAIN (COSTS off) +SELECT p.x, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 +AS c1 ON c1.parent = p.i 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) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 +AS c1 ON c1.parent = p.i GROUP BY p.i; + +-- The same for merge join. +SET enable_hashjoin TO off; +SET enable_mergejoin 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_nestloop TO on; +SET enable_hashjoin TO on; + +-- Scan index on agg_pushdown_child1(parent) column and 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; + +-- Join "c1" to "p.x" column, i.e. one that is not in the GROUP BY clause. The +-- planner should still use "c1.parent" as grouping expression for partial +-- aggregation, although it's not in the same equivalence class as the GROUP +-- BY expression ("p.i"). The reason to use "c1.parent" for partial +-- aggregation is that this is the only way for "c1" to provide the join +-- expression with input data. +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.x GROUP BY p.i; + +-- Perform nestloop join between agg_pushdown_child1 and agg_pushdown_child2 +-- and 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;