public inbox for [email protected]help / color / mirror / Atom feed
Re: random() function documentation 5+ messages / 4 participants [nested] [flat]
* Re: random() function documentation @ 2022-04-11 19:19 Tom Lane <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Tom Lane @ 2022-04-11 19:19 UTC (permalink / raw) To: Dagfinn Ilmari Mannsåker <[email protected]>; +Cc: [email protected] =?utf-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <[email protected]> writes: > Tom Lane <[email protected]> writes: >> How about we just say "uses a linear-feedback shift register algorithm"? > That works for me. Nice and simple, and not overly specific. Should we > perhaps also add a warning that the same seed is not guaranteed to > produce the same sequence across different (major?) versions? I wouldn't bother, on the grounds that then we'd need such disclaimers in a whole lot of places. Others might see it differently though. regards, tom lane ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: random() function documentation @ 2022-04-12 00:18 Dean Rasheed <[email protected]> parent: Tom Lane <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Dean Rasheed @ 2022-04-12 00:18 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; PostgreSQL Hackers <[email protected]> On Mon, 11 Apr 2022 at 20:20, Tom Lane <[email protected]> wrote: > > >> How about we just say "uses a linear-feedback shift register algorithm"? I think it'd be sufficient to just say that it's a deterministic pseudorandom number generator. I don't see much value in documenting the internal algorithm used. > > Should we > > perhaps also add a warning that the same seed is not guaranteed to > > produce the same sequence across different (major?) versions? > > I wouldn't bother, on the grounds that then we'd need such disclaimers > in a whole lot of places. Others might see it differently though. Agreed, though I think when the release notes are written, they ought to warn that the sequence will change with this release. Regards, Dean ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: random() function documentation @ 2022-04-12 08:19 Fabien COELHO <[email protected]> parent: Dean Rasheed <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Fabien COELHO @ 2022-04-12 08:19 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Tom Lane <[email protected]>; =?ISO-8859-15?Q?Dagfinn_Ilmari_Manns=E5ker?= <[email protected]>; PostgreSQL Hackers <[email protected]> >>>> How about we just say "uses a linear-feedback shift register algorithm"? > > I think it'd be sufficient to just say that it's a deterministic > pseudorandom number generator. I don't see much value in documenting > the internal algorithm used. Hmmm… I'm not so sure. ISTM that people interested in using the random user-facing variants (only random?) could like a pointer on the algorithm to check for the expected quality of the produced pseudo-random stream? See attached. >>> Should we perhaps also add a warning that the same seed is not >>> guaranteed to produce the same sequence across different (major?) >>> versions? >> >> I wouldn't bother, on the grounds that then we'd need such disclaimers >> in a whole lot of places. Others might see it differently though. > > Agreed, Agreed. > though I think when the release notes are written, they ought > to warn that the sequence will change with this release. Yes. -- Fabien. Attachments: [text/x-diff] random-algo.patch (1.0K, ../../alpine.DEB.2.22.394.2204120950260.1378296@pseudo/2-random-algo.patch) download | inline diff: diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml index 0a5c402640..7492454592 100644 --- a/doc/src/sgml/func.sgml +++ b/doc/src/sgml/func.sgml @@ -1832,10 +1832,11 @@ repeat('Pg', 4) <returnvalue>PgPgPgPg</returnvalue> </table> <para> - The <function>random()</function> function uses a simple linear - congruential algorithm. It is fast but not suitable for cryptographic - applications; see the <xref linkend="pgcrypto"/> module for a more - secure alternative. + The <function>random()</function> function uses + <ulink url="https://en.wikipedia.org/wiki/Xoroshiro128%2B">xoroshiro128**</ulink>, a + linear feedback shift register algorithm. + It is fast but not suitable for cryptographic applications; + see the <xref linkend="pgcrypto"/> module for a more secure alternative. If <function>setseed()</function> is called, the series of results of subsequent <function>random()</function> calls in the current session can be repeated by re-issuing <function>setseed()</function> with the same ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: random() function documentation @ 2022-04-12 15:03 Tom Lane <[email protected]> parent: Fabien COELHO <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Tom Lane @ 2022-04-12 15:03 UTC (permalink / raw) To: Fabien COELHO <[email protected]>; +Cc: Dean Rasheed <[email protected]>; =?ISO-8859-15?Q?Dagfinn_Ilmari_Manns=E5ker?= <[email protected]>; PostgreSQL Hackers <[email protected]> Fabien COELHO <[email protected]> writes: >>> How about we just say "uses a linear-feedback shift register algorithm"? >> I think it'd be sufficient to just say that it's a deterministic >> pseudorandom number generator. I don't see much value in documenting >> the internal algorithm used. > Hmmm… I'm not so sure. ISTM that people interested in using the random > user-facing variants (only random?) could like a pointer on the algorithm > to check for the expected quality of the produced pseudo-random stream? > See attached. I don't want to get that specific. We were not specific before and there has been no call for such detail in the docs. (Unlike closed-source software, anybody who really wants algorithmic details can find all they want to know in the source code.) It would just amount to another thing to forget to update next time someone changes the algorithm ... which is a consideration that leads me to favor Dean's phrasing. regards, tom lane ^ permalink raw reply [nested|flat] 5+ messages in thread
* [PATCH 3/3] Use also partial paths as the input for grouped paths. @ 2022-11-17 09:41 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2022-11-17 09:41 UTC (permalink / raw) --- src/backend/optimizer/path/allpaths.c | 44 +++++- src/backend/optimizer/util/relnode.c | 46 +++--- src/test/regress/expected/agg_pushdown.out | 156 +++++++++++++++++++++ src/test/regress/sql/agg_pushdown.sql | 65 +++++++++ 4 files changed, 281 insertions(+), 30 deletions(-) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 6638311ead..50f0cf8365 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -130,7 +130,7 @@ static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, AggStrategy aggstrategy, - RelAggInfo *agg_info); + RelAggInfo *agg_info, bool partial); static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist); static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery, pushdown_safety_info *safetyInfo); @@ -3343,6 +3343,7 @@ generate_grouping_paths(PlannerInfo *root, RelOptInfo *rel_grouped, RelOptInfo *rel_plain, RelAggInfo *agg_info) { ListCell *lc; + Path *path; if (IS_DUMMY_REL(rel_plain)) { @@ -3352,7 +3353,7 @@ generate_grouping_paths(PlannerInfo *root, RelOptInfo *rel_grouped, foreach(lc, rel_plain->pathlist) { - Path *path = (Path *) lfirst(lc); + path = (Path *) lfirst(lc); /* * Since the path originates from the non-grouped relation which is @@ -3366,7 +3367,8 @@ generate_grouping_paths(PlannerInfo *root, RelOptInfo *rel_grouped, * add_grouped_path() will check whether the path has suitable * pathkeys. */ - add_grouped_path(root, rel_grouped, path, AGG_SORTED, agg_info); + add_grouped_path(root, rel_grouped, path, AGG_SORTED, agg_info, + false); /* * Repeated creation of hash table (for new parameter values) should @@ -3374,12 +3376,38 @@ generate_grouping_paths(PlannerInfo *root, RelOptInfo *rel_grouped, * efficiency. */ if (path->param_info == NULL) - add_grouped_path(root, rel_grouped, path, AGG_HASHED, agg_info); + add_grouped_path(root, rel_grouped, path, AGG_HASHED, agg_info, + false); } /* Could not generate any grouped paths? */ if (rel_grouped->pathlist == NIL) + { mark_dummy_rel(rel_grouped); + return; + } + + /* + * Almost the same for partial paths. + * + * The difference is that parameterized paths are never created, see + * add_partial_path() for explanation. + */ + foreach(lc, rel_plain->partial_pathlist) + { + path = (Path *) lfirst(lc); + + if (path->param_info != NULL) + continue; + + path = (Path *) create_projection_path(root, rel_grouped, path, + agg_info->agg_input); + + add_grouped_path(root, rel_grouped, path, AGG_SORTED, agg_info, + true); + add_grouped_path(root, rel_grouped, path, AGG_HASHED, agg_info, + true); + } } /* @@ -3387,7 +3415,8 @@ generate_grouping_paths(PlannerInfo *root, RelOptInfo *rel_grouped, */ static void add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, - AggStrategy aggstrategy, RelAggInfo *agg_info) + AggStrategy aggstrategy, RelAggInfo *agg_info, + bool partial) { Path *agg_path; @@ -3410,7 +3439,10 @@ add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, return; /* Add the grouped path to the list of grouped base paths. */ - add_path(rel, (Path *) agg_path); + if (!partial) + add_path(rel, (Path *) agg_path); + else + add_partial_path(rel, (Path *) agg_path); } /* diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 556f25bece..17aa8804ff 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -948,33 +948,12 @@ build_join_rel(PlannerInfo *root, build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist, sjinfo->jointype); + /* + * Set estimates of the joinrel's size. + */ if (!grouped) - { - /* - * Set estimates of the joinrel's size. - */ set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, sjinfo, restrictlist); - - /* - * Set the consider_parallel flag if this joinrel could potentially be - * scanned within a parallel worker. If this flag is false for either - * inner_rel or outer_rel, then it must be false for the joinrel also. - * Even if both are true, there might be parallel-restricted - * expressions in the targetlist or quals. - * - * Note that if there are more than two rels in this relation, they - * could be divided between inner_rel and outer_rel in any arbitrary - * way. We assume this doesn't matter, because we should hit all the - * same baserels and joinclauses while building up to this joinrel no - * matter which we take; therefore, we should make the same decision - * here however we get here. - */ - if (inner_rel->consider_parallel && outer_rel->consider_parallel && - is_parallel_safe(root, (Node *) restrictlist) && - is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) - joinrel->consider_parallel = true; - } else { /* @@ -990,6 +969,25 @@ build_join_rel(PlannerInfo *root, agg_info->input_rows, NULL, NULL); } + /* + * Set the consider_parallel flag if this joinrel could potentially be + * scanned within a parallel worker. If this flag is false for either + * inner_rel or outer_rel, then it must be false for the joinrel also. + * Even if both are true, there might be parallel-restricted expressions + * in the targetlist or quals. + * + * Note that if there are more than two rels in this relation, they could + * be divided between inner_rel and outer_rel in any arbitrary way. We + * assume this doesn't matter, because we should hit all the same baserels + * and joinclauses while building up to this joinrel no matter which we + * take; therefore, we should make the same decision here however we get + * here. + */ + if (inner_rel->consider_parallel && outer_rel->consider_parallel && + is_parallel_safe(root, (Node *) restrictlist) && + is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) + joinrel->consider_parallel = true; + /* Add the joinrel to the PlannerInfo. */ if (!grouped) add_join_rel(root, joinrel); diff --git a/src/test/regress/expected/agg_pushdown.out b/src/test/regress/expected/agg_pushdown.out index 03a5ccf571..66d36d122e 100644 --- a/src/test/regress/expected/agg_pushdown.out +++ b/src/test/regress/expected/agg_pushdown.out @@ -214,3 +214,159 @@ c2.parent = p.i WHERE c1.j = c2.k GROUP BY p.i; -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p (13 rows) +-- Most of the tests above with parallel query processing enforced. +SET min_parallel_index_scan_size = 0; +SET min_parallel_table_scan_size = 0; +SET parallel_setup_cost = 0; +SET parallel_tuple_cost = 0; +-- Partially aggregate a single relation. +-- +-- Nestloop join. +SET enable_nestloop TO on; +SET enable_hashjoin TO off; +SET enable_mergejoin TO off; +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 + -> Gather Merge + Workers Planned: 1 + -> Nested Loop + -> Partial GroupAggregate + Group Key: c1.parent + -> Parallel Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p + Index Cond: (i = c1.parent) +(10 rows) + +-- 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 + -> Gather + Workers Planned: 1 + -> Parallel Hash Join + Hash Cond: (c1.parent = p.i) + -> Partial GroupAggregate + Group Key: c1.parent + -> Parallel Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Parallel Hash + -> Parallel Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p +(13 rows) + +-- 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 + -> Gather Merge + Workers Planned: 1 + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Partial GroupAggregate + Group Key: c1.parent + -> Parallel Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p +(10 rows) + +SET enable_nestloop TO on; +SET enable_hashjoin TO on; +-- 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 + -> Gather Merge + Workers Planned: 2 + -> Sort + Sort Key: p.i + -> Nested Loop + -> Partial HashAggregate + Group Key: c1.parent + -> Nested Loop + -> Parallel Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + Index 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) +(15 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 + -> Gather Merge + Workers Planned: 1 + -> Sort + Sort Key: p.i + -> Parallel Hash Join + Hash Cond: (c1.parent = p.i) + -> Partial HashAggregate + Group Key: c1.parent + -> Parallel Hash Join + Hash Cond: ((c1.parent = c2.parent) AND (c1.j = c2.k)) + -> Parallel Index Scan using agg_pushdown_child1_parent_idx on agg_pushdown_child1 c1 + -> Parallel Hash + -> Parallel Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Parallel Hash + -> Parallel Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p +(17 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 + -> Gather Merge + Workers Planned: 2 + -> Merge Join + Merge Cond: (c1.parent = p.i) + -> Sort + Sort Key: c1.parent + -> Partial HashAggregate + Group Key: c1.parent + -> Merge Join + Merge Cond: ((c1.j = c2.k) AND (c1.parent = c2.parent)) + -> Parallel Index Scan using agg_pushdown_child1_pkey on agg_pushdown_child1 c1 + -> Index Scan using agg_pushdown_child2_pkey on agg_pushdown_child2 c2 + -> Index Only Scan using agg_pushdown_parent_pkey on agg_pushdown_parent p +(15 rows) + diff --git a/src/test/regress/sql/agg_pushdown.sql b/src/test/regress/sql/agg_pushdown.sql index 0a4614592b..49ba6dd67c 100644 --- a/src/test/regress/sql/agg_pushdown.sql +++ b/src/test/regress/sql/agg_pushdown.sql @@ -113,3 +113,68 @@ 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; + +-- Most of the tests above with parallel query processing enforced. +SET min_parallel_index_scan_size = 0; +SET min_parallel_table_scan_size = 0; +SET parallel_setup_cost = 0; +SET parallel_tuple_cost = 0; + +-- Partially aggregate a single relation. +-- +-- Nestloop join. +SET enable_nestloop TO on; +SET enable_hashjoin TO off; +SET enable_mergejoin TO off; +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; + +-- 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; + +-- 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; + +-- 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; -- 2.31.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=v21-fixes.patch diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index 2fd1a96269..db97bd254d 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -1186,14 +1186,34 @@ Thus the join above the partial aggregate node receives fewer input rows, and so the number of outer-to-inner pairs of tuples to be checked can be significantly lower, which can in turn lead to considerably lower join cost. -Note that there's often no GROUP BY expression to be used for the partial -aggregation, so we use equivalence classes to derive grouping expression: in -the example above, the grouping key "b.j" was derived from "a.i". - -Also note that in this case the partial aggregate uses the "b.j" as grouping -column although the column does not appear in the query target list. The point -is that "b.j" is needed to evaluate the join condition, and there's no other -way for the partial aggregate to emit its values. +Note that the GROUP BY expression might not be useful for the partial +aggregate. In the example above, the aggregate avg(b.y) references table "b", +but the GROUP BY expression mentions "a". However, the equivalence class {a.i, +b.j} allows us to use the b.j column as a grouping key for the partial +aggregation of the "b" table. The equivalence class mechanism is suitable +because it's designed to derive join clauses, and at the same time the join +clauses determine the choice of grouping columns of the partial aggregate: the +only way for the partial aggregate to provide upper join(s) with input values +is to have the join input expression(s) in the grouping key: besides grouping +columns, the partial aggregate can only produce the transient states of the +aggregate functions, but aggregate functions cannot be referenced by the JOIN +clauses. + +Regarding correctness, join node considers the output of the partial aggregate +to be equivalent to the output of a plain (non-aggregated) relation scan. That +is, a group (i.e. a row of the partial aggregate output) matches the other +side of the join if and only if each row of the non-aggregate relation +does. In other words, all rows belonging to the same group have the same value +of the join columns (As mentioned above, a join cannot reference other output +expressions of the partial aggregate than the grouping expressions.). + +However, there's a restriction from the aggregate's perspective: the aggregate +cannot be pushed down if any column referenced by either grouping expression +or aggregate function can be set to NULL by an outer join above the relation +to which we want to apply the partiall aggregation. The point is that those +NULL values would not appear on the input of the pushed-down aggregate, so it could +either put the rows into groups in a different way than the aggregate at the +top of the plan, or it could compute wrong values of the aggregate functions. Besides base relation, the aggregation can also be pushed down to join: diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 32b3dedc71..50f0cf8365 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -197,8 +197,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) * Now that the sizes are known, we can estimate the sizes of the grouped * relations. */ - if (root->grouped_var_list) - setup_base_grouped_rels(root); + setup_base_grouped_rels(root); /* * We should now have size estimates for every actual table involved in @@ -341,7 +340,7 @@ set_base_rel_sizes(PlannerInfo *root) } /* - * setup_based_grouped_rels + * setup_base_grouped_rels * For each "plain" relation build a grouped relation if aggregate pushdown * is possible and if this relation is suitable for partial aggregation. */ @@ -350,6 +349,11 @@ setup_base_grouped_rels(PlannerInfo *root) { Index rti; + /* If there are no grouping expressions, no aggregate push-down. */ + if (!root->grouped_var_list) + return; + + for (rti = 1; rti < root->simple_rel_array_size; rti++) { RelOptInfo *brel = root->simple_rel_array[rti]; @@ -362,6 +366,10 @@ setup_base_grouped_rels(PlannerInfo *root) Assert(brel->relid == rti); /* sanity check on array */ + /* ignore RTEs that are "other rels" */ + if (brel->reloptkind != RELOPT_BASEREL) + continue; + /* * The aggregate push-down feature only makes sense if there are * multiple base rels in the query. @@ -369,16 +377,13 @@ setup_base_grouped_rels(PlannerInfo *root) if (!bms_nonempty_difference(root->all_baserels, brel->relids)) continue; - /* ignore RTEs that are "other rels" */ - if (brel->reloptkind != RELOPT_BASEREL) + rel_grouped = build_simple_grouped_rel(root, brel->relid, &agg_info); + /* Couldn't any aggregate be pushed down to this relation? */ + if (!rel_grouped) continue; - rel_grouped = build_simple_grouped_rel(root, brel->relid, &agg_info); - if (rel_grouped) - { - /* Make the relation available for joining. */ - add_grouped_rel(root, rel_grouped, agg_info); - } + /* Make the relation available for joining. */ + add_grouped_rel(root, rel_grouped, agg_info); } } @@ -554,21 +559,8 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, } else { - RelOptInfo *rel_grouped; - RelAggInfo *agg_info; - /* Plain relation */ set_plain_rel_pathlist(root, rel, rte); - - /* Add paths to the grouped relation if one exists. */ - rel_grouped = find_grouped_rel(root, rel->relids, - &agg_info); - if (rel_grouped) - { - generate_grouping_paths(root, rel_grouped, rel, - agg_info); - set_cheapest(rel_grouped); - } } break; case RTE_SUBQUERY: @@ -836,6 +828,8 @@ static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { Relids required_outer; + RelOptInfo *rel_grouped; + RelAggInfo *agg_info; /* * We don't support pushing join clauses into the quals of a seqscan, but @@ -856,6 +850,14 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* Consider TID scans */ create_tidscan_paths(root, rel); + + /* Add paths to the grouped relation if one exists. */ + rel_grouped = find_grouped_rel(root, rel->relids, &agg_info); + if (!rel_grouped) + return; + + generate_grouping_paths(root, rel_grouped, rel, agg_info); + set_cheapest(rel_grouped); } /* @@ -3428,14 +3430,19 @@ add_grouped_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, else elog(ERROR, "unexpected strategy %d", aggstrategy); + /* + * Bail out if we failed to create a suitable aggregated path. This can + * happen e.g. then the path does not support hashing (for AGG_HASHED), + * or when the input path is not sorted. + */ + if (agg_path == NULL) + return; + /* Add the grouped path to the list of grouped base paths. */ - if (agg_path != NULL) - { - if (!partial) - add_path(rel, (Path *) agg_path); - else - add_partial_path(rel, (Path *) agg_path); - } + if (!partial) + add_path(rel, (Path *) agg_path); + else + add_partial_path(rel, (Path *) agg_path); } /* @@ -3579,7 +3586,6 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) for (lev = 2; lev <= levels_needed; lev++) { - RelOptInfo *rel_grouped; ListCell *lc; /* @@ -3601,6 +3607,8 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) */ foreach(lc, root->join_rel_level[lev]) { + RelOptInfo *rel_grouped; + rel = (RelOptInfo *) lfirst(lc); /* Create paths for partitionwise joins. */ diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index b34ad90d08..4688f561f0 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -4999,6 +4999,7 @@ set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel) 0, JOIN_INNER, NULL); + rel->rows = clamp_row_est(nrows); cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root); diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 8e913c92d8..8dc39765f2 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -355,7 +355,8 @@ create_aggregate_grouped_var_infos(PlannerInfo *root) Assert(root->grouped_var_list == NIL); tlist_exprs = pull_var_clause((Node *) root->processed_tlist, - PVC_INCLUDE_AGGREGATES); + PVC_INCLUDE_AGGREGATES | + PVC_RECURSE_WINDOWFUNCS); /* * Although GroupingFunc is related to root->parse->groupingSets, this diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 0ada3ba3eb..3292b4b419 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -6847,6 +6847,12 @@ create_partial_grouping_paths(PlannerInfo *root, * push-down. */ partially_grouped_rel = find_grouped_rel(root, input_rel->relids, NULL); + + /* + * If the relation already exists, it must have been created by aggregate + * pushdown. We can't check how exactly it got created, but we can at + * least check that aggregate pushdown is enabled. + */ Assert(enable_agg_pushdown || partially_grouped_rel == NULL); /* @@ -6871,17 +6877,25 @@ create_partial_grouping_paths(PlannerInfo *root, /* * If we can't partially aggregate partial paths, and we can't partially * aggregate non-partial paths, then don't bother creating the new - * RelOptInfo at all, unless the caller specified force_rel_creation. + * RelOptInfo at all, unless the caller specified force_rel_creation. However */ if (cheapest_total_path == NULL && cheapest_partial_path == NULL && - !force_rel_creation && - partially_grouped_rel == NULL) - return NULL; + !force_rel_creation) + { + /* + * If partially_grouped_rel exists, it should contain paths generated + * by the aggregate push-down feature, so the caller is interested in + * it. + */ + return partially_grouped_rel; + } /* * Build a new upper relation to represent the result of partially - * aggregating the rows from the input relation. + * aggregating the rows from the input relation. The relation may already + * exist due to aggregate pushdown, in which case we don't need to create + * it. */ if (partially_grouped_rel == NULL) partially_grouped_rel = fetch_upper_rel(root, @@ -6903,6 +6917,11 @@ create_partial_grouping_paths(PlannerInfo *root, * * If the target was already created for the sake of aggregate push-down, * it should be compatible with what we'd create here. + * + * XXX If fetch_upper_rel() had to create a new relation (i.e. aggregate + * push-down generated no paths), it created an empty target. Should we + * change the convention and have it assign NULL to reltarget instead? Or + * should we introduce a function like is_pathtarget_empty()? */ if (partially_grouped_rel->reltarget->exprs == NIL) partially_grouped_rel->reltarget = diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 7025ebf94b..2627e2f252 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -3163,6 +3163,9 @@ create_agg_path(PlannerInfo *root, } /* + * create_agg_sorted_path + * Creates a pathnode performing sorted aggregation/grouping + * * Apply AGG_SORTED aggregation path to subpath if it's suitably sorted. * * NULL is returned if sorting of subpath output is not suitable. @@ -3176,45 +3179,32 @@ create_agg_sorted_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, AggClauseCosts agg_costs; PathTarget *target; double dNumGroups; - ListCell *lc1; - List *key_subset = NIL; AggPath *result = NULL; aggsplit = AGGSPLIT_INITIAL_SERIAL; agg_exprs = agg_info->agg_exprs; target = agg_info->target; - if (subpath->pathkeys == NIL) - return NULL; - - if (!grouping_is_sortable(root->parse->groupClause)) + /* group_pathkeys are necessary to evaluate the sorting. */ + if (agg_info->group_pathkeys == NIL) return NULL; /* - * Find all query pathkeys that our relation does affect. + * The input path must be sorted in a specific way, but if it's not sorted + * at all, it's not useful for AGG_SORTED. */ - foreach(lc1, root->group_pathkeys) - { - PathKey *gkey = castNode(PathKey, lfirst(lc1)); - ListCell *lc2; - - foreach(lc2, subpath->pathkeys) - { - PathKey *skey = castNode(PathKey, lfirst(lc2)); - - if (skey == gkey) - { - key_subset = lappend(key_subset, gkey); - break; - } - } - } + if (subpath->pathkeys == NIL) + return NULL; - if (key_subset == NIL) + /* Are the grouping clauses suitable for sorted aggregation? */ + if (!grouping_is_sortable(agg_info->group_clauses)) return NULL; - /* Check if AGG_SORTED is useful for the whole query. */ - if (!pathkeys_contained_in(key_subset, subpath->pathkeys)) + /* + * Is the input path sorted enough for this grouping? TODO Consider using + * incremental sort if the sorting is "almost sufficient". + */ + if (!pathkeys_contained_in(agg_info->group_pathkeys, subpath->pathkeys)) return NULL; MemSet(&agg_costs, 0, sizeof(AggClauseCosts)); @@ -3231,7 +3221,7 @@ create_agg_sorted_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, result = create_agg_path(root, rel, subpath, target, AGG_SORTED, aggsplit, agg_info->group_clauses, - NIL, + NIL, /* qual for HAVING clause */ &agg_costs, dNumGroups); @@ -3254,7 +3244,6 @@ create_agg_hashed_path(PlannerInfo *root, RelOptInfo *rel, AggClauseCosts agg_costs; PathTarget *target; double dNumGroups; - double hashaggtablesize; Query *parse = root->parse; AggPath *result = NULL; @@ -3279,25 +3268,18 @@ create_agg_hashed_path(PlannerInfo *root, RelOptInfo *rel, dNumGroups = estimate_num_groups(root, agg_info->group_exprs, subpath->rows, NULL, NULL); - hashaggtablesize = estimate_hashagg_tablesize(root, subpath, - &agg_costs, - dNumGroups); - - if (hashaggtablesize < work_mem * 1024L) - { - /* - * qual is NIL because the HAVING clause cannot be evaluated until - * the final value of the aggregate is known. - */ - result = create_agg_path(root, rel, subpath, - target, - AGG_HASHED, - aggsplit, - agg_info->group_clauses, - NIL, - &agg_costs, - dNumGroups); - } + /* + * qual is NIL because the HAVING clause cannot be evaluated until the + * final value of the aggregate is known. + */ + result = create_agg_path(root, rel, subpath, + target, + AGG_HASHED, + aggsplit, + agg_info->group_clauses, + NIL, /* qual for HAVING clause */ + &agg_costs, + dNumGroups); } return result; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index ce2e267e91..fcec58f10a 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -2330,15 +2330,16 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) List *grp_exprs_extra = NIL; List *group_clauses_final; int i; + bool pk_found, pk_missing; /* * The function shouldn't have been called if there's no opportunity for - * aggregation push-down. + * aggregate push-down. */ Assert(root->grouped_var_list != NIL); /* - * The current implementation of aggregation push-down cannot handle + * The current implementation of aggregate push-down cannot handle * PlaceHolderVar (PHV). * * If we knew that the PHV should be evaluated in this target (and of @@ -2608,11 +2609,13 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) */ i = 0; result = makeNode(RelAggInfo); + pk_missing = false; foreach(lc, target->exprs) { Index sortgroupref = 0; SortGroupClause *cl; Expr *texpr; + ListCell *lc2; texpr = (Expr *) lfirst(lc); @@ -2631,9 +2634,9 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) /* * Besides being an aggregate, the target expression should have no - * other reason then being a column of a relation functionally - * dependent on the GROUP BY clause. So it's not actually a grouping - * column. + * other reason to be there than being a column of a relation + * functionally dependent on the GROUP BY clause. So it's not actually + * a grouping column. */ if (sortgroupref == 0) continue; @@ -2654,6 +2657,52 @@ create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel) */ result->group_exprs = list_append_unique(result->group_exprs, texpr); + + /* + * Try to find PathKey for the expression, but don't if we already saw + * an expression w/o the PathKey. + */ + if (pk_missing) + continue; + + pk_found = false; + foreach(lc2, root->group_pathkeys) + { + PathKey *pkey = lfirst_node(PathKey, lc2); + EquivalenceClass *ec = pkey->pk_eclass; + ListCell *lc3; + + foreach(lc3, ec->ec_members) + { + EquivalenceMember *em = lfirst_node(EquivalenceMember, lc3); + + if (equal(texpr, em->em_expr)) + { + result->group_pathkeys = lappend(result->group_pathkeys, + pkey); + pk_found = true; + break; + } + } + if (pk_found) + break; + } + + /* + * If no PathKey was found, the expression was probably generated out + * of grp_exprs_extra. If we don't have a single PathKey, + * group_pathkeys is not useful, so clear it. + */ + if (!pk_found) + { + list_free(result->group_pathkeys); + result->group_pathkeys = NIL; + /* + * Do not spend cycles looking for the PathKey for other + * expressions. + */ + pk_missing = true; + } } /* diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample index 89f944d83a..310c5ff774 100644 --- a/src/backend/utils/misc/postgresql.conf.sample +++ b/src/backend/utils/misc/postgresql.conf.sample @@ -389,6 +389,7 @@ #enable_seqscan = on #enable_sort = on #enable_tidscan = on +#enable_agg_pushdown = on # - Planner Cost Constants - diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 07459c423f..38e105b6de 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1065,8 +1065,9 @@ typedef struct RelOptInfo * actually just a workspace for users of the structure, i.e. not initialized * when instance of the structure is created. * - * "group_clauses" and "group_exprs" are lists of SortGroupClause and the - * corresponding grouping expressions respectively. + * "group_clauses", "group_exprs" and "group_pathkeys" are lists of + * SortGroupClause, the corresponding grouping expressions and PathKey + * respectively. * * "agg_exprs" is a list of Aggref nodes for the aggregation of the relation's * paths. @@ -1090,6 +1091,7 @@ typedef struct RelAggInfo List *group_clauses; List *group_exprs; + List *group_pathkeys; List *agg_exprs; /* Aggref expressions. */ diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out index 442f7f9b41..da67f3a901 100644 --- a/src/test/regress/expected/sysviews.out +++ b/src/test/regress/expected/sysviews.out @@ -111,7 +111,7 @@ select count(*) = 0 as ok from pg_stat_wal_receiver; select name, setting from pg_settings where name like 'enable%'; name | setting --------------------------------+--------- - enable_agg_pushdown | off + enable_agg_pushdown | on enable_async_append | on enable_bitmapscan | on enable_gathermerge | on --=-=-=-- ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2022-11-17 09:41 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2022-04-11 19:19 Re: random() function documentation Tom Lane <[email protected]> 2022-04-12 00:18 ` Dean Rasheed <[email protected]> 2022-04-12 08:19 ` Fabien COELHO <[email protected]> 2022-04-12 15:03 ` Tom Lane <[email protected]> 2022-11-17 09:41 [PATCH 3/3] Use also partial paths as the input for grouped paths. Antonin Houska <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox