Hi,
I take a look at the patch today. Attached is the v12 and a separate
patch with some comment tweaks and review comments.
1) I see the patch results in some plan changes in postgres_fdw. I
assume it's somehow related to the sort costing changes, but I find it a
bit suspicious. Why should the plan change from this:
Foreign Scan
Remote SQL: ... ORDER BY ... OFFSET 100 LIMIT 10;
to
Limit
Foreign Scan
Remote SQL: ... ORDER BY ...
But even if this is due to changes to order by costing, postponing the
limit seems like a net loss - the sort happens before the limit, and by
postponing the limit after foreign scan we need to transfer 100 more
rows. So what's causing this?
The difference in plan cost seems fairly substantial (old: 196.52, new:
241.94). But maybe that's OK and expected.
2) I wonder how much more expensive (in terms of CPU) is the new sort
costing code. It's iterative, and it's calling functions to calculate
number of groups etc. I wonder what's the impact simple queries?
3) It's not clear to me why we need "fake var" protection? Why would the
estimate_num_groups() fail for that?
4) In one of the places a comment says DEFAULT_NUM_DISTINCT is not used
because we're dealing with multiple columns. That makes sense, but maybe
we should use DEFAULT_NUM_DISTINCT at least to limit the range. That is,
with N columns we should restrict the nGroups estimate by:
min = DEFAULT_NUM_DISTINCT
max = Min(pow(DEFAULT_NUM_DISTINCT, ncolumns), tuples)
Also, it's not clear what's the logic behind the formula:
nGroups = ceil(2.0 + sqrt(tuples) *
list_length(pathkeyExprs) / list_length(pathkeys));
A comment explaining that would be helpful.
5) The compute_cpu_sort_cost comment includes two references (in a quite
mixed-up way), and then there's another reference in the code. I suggest
we list all of them in the function comment.
6) There's a bunch of magic values (various multipliers etc.). It's not
clear which values are meant to be equal, etc. Let's introduce nicer
constants with reasonable names.
7) The comment at get_cheapest_group_keys_order is a bit misleading,
because it talks about "uniqueness" - but that's not what we're looking
at here (I mean, is the column unique or not). We're looking at number
of distinct values in the column, which is a different thing. Also, it'd
be good to roughly explain what get_cheapest_group_keys_order does - how
it calculates the order (permutations up to 4 values, etc.).
8) The comment at compute_cpu_sort_cost should also explain basics of
the algorithm. I tried doing something like that, but I'm not sure I got
all the details right and it probably needs further improvements.
9) The main concern I have is still about the changes in planner.c, and
I think I've already shared it before. The code takes the grouping
pathkeys, and just reshuffles them to what it believes is a better order
(cheaper, ...). That is, there's on input pathkey list, and it gets
transformed into another pathkey list. The problem is that even if this
optimizes the sort, it may work against some optimization in the upper
part of the plan.
Imagine a query that does something like this:
SELECT a, b, count(*) FROM (
SELECT DISTINCT a, b, c, d FROM x
) GROUP BY a, b;
Now, from the costing perspective, it may be cheaper to do the inner
grouping by "c, d, a, b" for example. But that works directly against
the second grouping, which would benefit from having the input sorted by
"a, b". How exactly would this behaves depends on the number of distinct
values in the columns, how expensive the comparisons are for each
column, and so on. But you get the idea.
I admit I haven't managed to construct a reasonably query that'd be
significantly harmed by this, but I haven't spent a lot of time on it.
I'm pretty sure I used this trick in the past, when doing aggregations
on large data sets, where it was much better to "pipe" the data through
multiple GroupAggregate nodes.
For this reason I think the code generating paths should work a bit like
get_useful_pathkeys_for_relation and generate_useful_gather_paths.
* group_keys_reorder_by_pathkeys should not produce just one list of
pathkeys, but multiple interesting options. At the moment it should
produce at least the input grouping pathkeys (as specified in the
query), and the "optimal" pathkeys (by lowest cost).
* the places calling group_keys_reorder_by_pathkeys should loop on the
result, and generate separate path for each option.
I'd guess in the future we'll "peek forward" in the plan and see if
there are other interesting pathkeys (that's the expectation for
get_useful_pathkeys_for_relation).
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
>From 0d8a7ddc441a3b26a498f6d3d4805fe5d305ebfc Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.von...@postgresql.org>
Date: Tue, 9 Mar 2021 18:44:23 +0100
Subject: [PATCH 1/2] v12
---
.../postgres_fdw/expected/postgres_fdw.out | 199 +++++++---
src/backend/optimizer/path/costsize.c | 333 +++++++++++++++--
src/backend/optimizer/path/equivclass.c | 13 +-
src/backend/optimizer/path/pathkeys.c | 347 ++++++++++++++++++
src/backend/optimizer/plan/planner.c | 124 +++++--
src/backend/optimizer/util/pathnode.c | 2 +-
src/backend/utils/adt/selfuncs.c | 35 +-
src/backend/utils/misc/guc.c | 29 ++
src/include/optimizer/cost.h | 4 +-
src/include/optimizer/paths.h | 13 +
src/include/utils/selfuncs.h | 3 +
src/test/modules/unsafe_tests/Makefile | 2 +-
src/test/regress/expected/aggregates.out | 240 +++++++++++-
.../regress/expected/incremental_sort.out | 2 +-
src/test/regress/expected/join.out | 51 ++-
.../regress/expected/partition_aggregate.out | 136 ++++---
src/test/regress/expected/partition_join.out | 79 ++--
src/test/regress/expected/union.out | 60 ++-
src/test/regress/sql/aggregates.sql | 99 +++++
src/test/regress/sql/incremental_sort.sql | 2 +-
20 files changed, 1472 insertions(+), 301 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 0649b6b81c..5209d89b32 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -1077,13 +1077,15 @@ ANALYZE ft5;
-- join two tables
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10;
- QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1, t1.c3
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3 FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint
-(4 rows)
+ -> Foreign Scan
+ Output: t1.c1, t2.c1, t1.c3
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3 FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST
+(6 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10;
c1 | c1
@@ -1103,13 +1105,15 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t
-- join three tables
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c2, t3.c3 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) JOIN ft4 t3 ON (t3.c1 = t1.c1) ORDER BY t1.c3, t1.c1 OFFSET 10 LIMIT 10;
- QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c2, t3.c3, t1.c3
- Relations: ((public.ft1 t1) INNER JOIN (public.ft2 t2)) INNER JOIN (public.ft4 t3)
- Remote SQL: SELECT r1."C 1", r2.c2, r4.c3, r1.c3 FROM (("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) INNER JOIN "S 1"."T 3" r4 ON (((r1."C 1" = r4.c1)))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 10::bigint
-(4 rows)
+ -> Foreign Scan
+ Output: t1.c1, t2.c2, t3.c3, t1.c3
+ Relations: ((public.ft1 t1) INNER JOIN (public.ft2 t2)) INNER JOIN (public.ft4 t3)
+ Remote SQL: SELECT r1."C 1", r2.c2, r4.c3, r1.c3 FROM (("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) INNER JOIN "S 1"."T 3" r4 ON (((r1."C 1" = r4.c1)))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST
+(6 rows)
SELECT t1.c1, t2.c2, t3.c3 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) JOIN ft4 t3 ON (t3.c1 = t1.c1) ORDER BY t1.c3, t1.c1 OFFSET 10 LIMIT 10;
c1 | c2 | c3
@@ -1716,13 +1720,33 @@ ALTER SERVER loopback OPTIONS (ADD extensions 'postgres_fdw');
-- tests whole-row reference for row marks
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR UPDATE OF t1;
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint FOR UPDATE OF r1
-(4 rows)
+ -> LockRows
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Foreign Scan
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST FOR UPDATE OF r1
+ -> Result
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Sort
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Sort Key: t1.c3, t1.c1
+ -> Hash Join
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Hash Cond: (t1.c1 = t2.c1)
+ -> Foreign Scan on public.ft1 t1
+ Output: t1.c1, t1.c3, t1.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR UPDATE
+ -> Hash
+ Output: t2.c1, t2.*
+ -> Foreign Scan on public.ft2 t2
+ Output: t2.c1, t2.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1"
+(24 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR UPDATE OF t1;
c1 | c1
@@ -1741,13 +1765,33 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR UPDATE;
- QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint FOR UPDATE OF r1 FOR UPDATE OF r2
-(4 rows)
+ -> LockRows
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Foreign Scan
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST FOR UPDATE OF r1 FOR UPDATE OF r2
+ -> Result
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Sort
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Sort Key: t1.c3, t1.c1
+ -> Hash Join
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Hash Cond: (t1.c1 = t2.c1)
+ -> Foreign Scan on public.ft1 t1
+ Output: t1.c1, t1.c3, t1.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR UPDATE
+ -> Hash
+ Output: t2.c1, t2.*
+ -> Foreign Scan on public.ft2 t2
+ Output: t2.c1, t2.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR UPDATE
+(24 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR UPDATE;
c1 | c1
@@ -1767,13 +1811,33 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t
-- join two tables with FOR SHARE clause
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR SHARE OF t1;
- QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint FOR SHARE OF r1
-(4 rows)
+ -> LockRows
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Foreign Scan
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST FOR SHARE OF r1
+ -> Result
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Sort
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Sort Key: t1.c3, t1.c1
+ -> Hash Join
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Hash Cond: (t1.c1 = t2.c1)
+ -> Foreign Scan on public.ft1 t1
+ Output: t1.c1, t1.c3, t1.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR SHARE
+ -> Hash
+ Output: t2.c1, t2.*
+ -> Foreign Scan on public.ft2 t2
+ Output: t2.c1, t2.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1"
+(24 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR SHARE OF t1;
c1 | c1
@@ -1792,13 +1856,33 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR SHARE;
- QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint FOR SHARE OF r1 FOR SHARE OF r2
-(4 rows)
+ -> LockRows
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Foreign Scan
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1", r1.c3, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST FOR SHARE OF r1 FOR SHARE OF r2
+ -> Result
+ Output: t1.c1, t2.c1, t1.c3, t1.*, t2.*
+ -> Sort
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Sort Key: t1.c3, t1.c1
+ -> Hash Join
+ Output: t1.c1, t1.c3, t1.*, t2.c1, t2.*
+ Hash Cond: (t1.c1 = t2.c1)
+ -> Foreign Scan on public.ft1 t1
+ Output: t1.c1, t1.c3, t1.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR SHARE
+ -> Hash
+ Output: t2.c1, t2.*
+ -> Foreign Scan on public.ft2 t2
+ Output: t2.c1, t2.*
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" FOR SHARE
+(24 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10 FOR SHARE;
c1 | c1
@@ -1852,13 +1936,15 @@ WITH t (c1_1, c1_3, c2_1) AS MATERIALIZED (SELECT t1.c1, t1.c3, t2.c1 FROM ft1 t
-- ctid with whole-row reference
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.ctid, t1, t2, t1.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t1.c1 OFFSET 100 LIMIT 10;
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.ctid, t1.*, t2.*, t1.c1, t1.c3
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r1."C 1", r1.c3 FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint
-(4 rows)
+ -> Foreign Scan
+ Output: t1.ctid, t1.*, t2.*, t1.c1, t1.c3
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r1."C 1", r1.c3 FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")))) ORDER BY r1.c3 ASC NULLS LAST, r1."C 1" ASC NULLS LAST
+(6 rows)
-- SEMI JOIN, not pushed down
EXPLAIN (VERBOSE, COSTS OFF)
@@ -1929,13 +2015,15 @@ SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2
-- CROSS JOIN can be pushed down
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
- QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
Output: t1.c1, t2.c1
- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
- Remote SQL: SELECT r1."C 1", r2."C 1" FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS LAST, r2."C 1" ASC NULLS LAST LIMIT 10::bigint OFFSET 100::bigint
-(4 rows)
+ -> Foreign Scan
+ Output: t1.c1, t2.c1
+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
+ Remote SQL: SELECT r1."C 1", r2."C 1" FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS LAST, r2."C 1" ASC NULLS LAST
+(6 rows)
SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
c1 | c1
@@ -2639,16 +2727,13 @@ select c2 * (random() <= 1)::int as c2 from ft2 group by c2 * (random() <= 1)::i
-- GROUP BY clause in various forms, cardinal, alias and constant expression
explain (verbose, costs off)
select count(c2) w, c2 x, 5 y, 7.0 z from ft1 group by 2, y, 9.0::int order by 2;
- QUERY PLAN
----------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------
+ Foreign Scan
Output: (count(c2)), c2, 5, 7.0, 9
- Sort Key: ft1.c2
- -> Foreign Scan
- Output: (count(c2)), c2, 5, 7.0, 9
- Relations: Aggregate on (public.ft1)
- Remote SQL: SELECT count(c2), c2, 5, 7.0, 9 FROM "S 1"."T 1" GROUP BY 2, 3, 5
-(7 rows)
+ Relations: Aggregate on (public.ft1)
+ Remote SQL: SELECT count(c2), c2, 5, 7.0, 9 FROM "S 1"."T 1" GROUP BY 2, 3, 5 ORDER BY c2 ASC NULLS LAST
+(4 rows)
select count(c2) w, c2 x, 5 y, 7.0 z from ft1 group by 2, y, 9.0::int order by 2;
w | x | y | z
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index a25b674a19..1639258aaf 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1751,6 +1751,289 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
rterm->pathtarget->width);
}
+/*
+ * is_fake_var
+ * Workaround for generate_append_tlist() which generates fake Vars with
+ * varno == 0, that will cause a fail of estimate_num_group() call
+ */
+static bool
+is_fake_var(Expr *expr)
+{
+ if (IsA(expr, RelabelType))
+ expr = (Expr *) ((RelabelType *) expr)->arg;
+
+ return (IsA(expr, Var) && ((Var *) expr)->varno == 0);
+}
+
+/*
+ * get_width_cost_multiplier
+ * Returns relative complexity of comparing two values based on it's width.
+ * The idea behind - long values have more expensive comparison. Return value is
+ * in cpu_operator_cost unit.
+ */
+static double
+get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
+{
+ double width = -1.0; /* fake value */
+
+ if (IsA(expr, RelabelType))
+ expr = (Expr *) ((RelabelType *) expr)->arg;
+
+ /* Try to find actual stat in corresponding relation */
+ if (IsA(expr, Var))
+ {
+ Var *var = (Var *) expr;
+
+ if (var->varno > 0 && var->varno < root->simple_rel_array_size)
+ {
+ RelOptInfo *rel = root->simple_rel_array[var->varno];
+
+ if (rel != NULL &&
+ var->varattno >= rel->min_attr &&
+ var->varattno <= rel->max_attr)
+ {
+ int ndx = var->varattno - rel->min_attr;
+
+ if (rel->attr_widths[ndx] > 0)
+ width = rel->attr_widths[ndx];
+ }
+ }
+ }
+
+ /* Didn't find any actual stats, use estimation by type */
+ if (width < 0.0)
+ {
+ Node *node = (Node*) expr;
+
+ width = get_typavgwidth(exprType(node), exprTypmod(node));
+ }
+
+ /*
+ * Any value in pgsql is passed by Datum type, so any operation with value
+ * could not be cheaper than operation with Datum type
+ */
+ if (width <= sizeof(Datum))
+ return 1.0;
+
+ /*
+ * Seems, cost of comparision is not directly proportional to args width,
+ * because comparing args could be differ width (we known only average over
+ * column) and difference often could be defined only by looking on first
+ * bytes. So, use log16(width) as estimation.
+ */
+ return 1.0 + 0.125 * LOG2(width / sizeof(Datum));
+}
+
+/*
+ * compute_cpu_sort_cost
+ * compute CPU cost of sort (i.e. in-memory)
+ *
+ * NOTE: some callers currently pass NIL for pathkeys because they
+ * can't conveniently supply the sort keys. In this case, it will fallback to
+ * simple comparison cost estimate.
+ *
+ * Estimation algorithm is based on ideas from course Algorithms,
+ * Robert Sedgewick, Kevin Wayne, https://algs4.cs.princeton.edu/home/ and paper
+ * "Quicksort Is Optimal For Many Equal Keys", Sebastian Wild,
+ * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017.
+ *
+ * In term of that papers, let N - number of tuples, Xi - number of tuples with
+ * key Ki, then estimation is:
+ * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi))
+ * In our case all Xi are the same because now we don't have an estimation of
+ * group sizes, we have only estimation of number of groups. In this case,
+ * formula becomes: N * log(NumberOfGroups). Next, to support correct estimation
+ * of multi-column sort we need separately compute each column, so, let k is a
+ * column number, Gk - number of groups defined by k columns:
+ * N * sum( Fk * log(Gk) )
+ * Fk is a function costs (including width) for k columns.
+ */
+
+static Cost
+compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
+ Cost comparison_cost, double tuples, double output_tuples,
+ bool heapSort)
+{
+ Cost per_tuple_cost = 0.0;
+ ListCell *lc;
+ List *pathkeyExprs = NIL;
+ double tuplesPerPrevGroup = tuples;
+ double totalFuncCost = 1.0;
+ bool has_fake_var = false;
+ int i = 0;
+ Oid prev_datatype = InvalidOid;
+ Cost funcCost = 0.;
+ List *cache_varinfos = NIL;
+
+ /* fallback if pathkeys is unknown */
+ if (list_length(pathkeys) == 0)
+ {
+ /*
+ * If we'll use a bounded heap-sort keeping just K tuples in memory, for
+ * a total number of tuple comparisons of N log2 K; but the constant
+ * factor is a bit higher than for quicksort. Tweak it so that the
+ * cost curve is continuous at the crossover point.
+ */
+ output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
+ per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
+
+ /* add cost provided by caller */
+ per_tuple_cost += comparison_cost;
+
+ return per_tuple_cost * tuples;
+ }
+
+ /*
+ * Computing total cost of sorting takes into account:
+ * - per column comparison function cost
+ * - we try to compute needed number of comparison per column
+ */
+
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey*)lfirst(lc);
+ EquivalenceMember *em;
+ double nGroups,
+ correctedNGroups;
+
+ /*
+ * We believe than equivalence members aren't very different, so, to
+ * estimate cost we take just first member
+ */
+ em = (EquivalenceMember *) linitial(pathkey->pk_eclass->ec_members);
+
+ if (em->em_datatype != InvalidOid)
+ {
+ /* do not lookup funcCost if data type is the same as previous */
+ if (prev_datatype != em->em_datatype)
+ {
+ Oid sortop;
+ QualCost cost;
+
+ sortop = get_opfamily_member(pathkey->pk_opfamily,
+ em->em_datatype, em->em_datatype,
+ pathkey->pk_strategy);
+
+ cost.startup = 0;
+ cost.per_tuple = 0;
+ add_function_cost(root, get_opcode(sortop), NULL, &cost);
+ /* we need procost, not product of procost and cpu_operator_cost */
+ funcCost = cost.per_tuple / cpu_operator_cost;
+ prev_datatype = em->em_datatype;
+ }
+ }
+ else
+ funcCost = 1.0; /* fallback */
+
+ /* Try to take into account actual width fee */
+ funcCost *= get_width_cost_multiplier(root, em->em_expr);
+
+ totalFuncCost += funcCost;
+
+ /* remeber if we have a fake var in pathkeys */
+ has_fake_var |= is_fake_var(em->em_expr);
+ pathkeyExprs = lappend(pathkeyExprs, em->em_expr);
+
+ /*
+ * Prevent call estimate_num_groups() with fake Var. Note,
+ * pathkeyExprs contains only previous columns
+ */
+ if (has_fake_var == false)
+ /*
+ * Recursively compute number of group in group from previous step
+ */
+ nGroups = estimate_num_groups_incremental(root, pathkeyExprs,
+ tuplesPerPrevGroup, NULL,
+ &cache_varinfos,
+ list_length(pathkeyExprs) - 1);
+ else if (tuples > 4.0)
+ /*
+ * Use geometric mean as estimation if there is no any stats.
+ * Don't use DEFAULT_NUM_DISTINCT because it used for only one
+ * column while here we try to estimate number of groups over
+ * set of columns.
+ */
+ nGroups = ceil(2.0 + sqrt(tuples) *
+ list_length(pathkeyExprs) / list_length(pathkeys));
+ else
+ nGroups = tuples;
+
+ /*
+ * Presorted keys aren't participated in comparison but still checked
+ * by qsort comparator.
+ */
+ if (i >= nPresortedKeys)
+ {
+ if (heapSort)
+ {
+ if (tuplesPerPrevGroup < output_tuples)
+ /* comparing only inside output_tuples */
+ correctedNGroups =
+ ceil(2.0 * output_tuples / (tuplesPerPrevGroup / nGroups));
+ else
+ /* two groups - in output and out */
+ correctedNGroups = 2.0;
+ }
+ else
+ correctedNGroups = nGroups;
+
+ if (correctedNGroups <= 1.0)
+ correctedNGroups = 2.0;
+ else
+ correctedNGroups = ceil(correctedNGroups);
+ per_tuple_cost += totalFuncCost * LOG2(correctedNGroups);
+ }
+
+ i++;
+
+ /*
+ * Real-world distribution isn't uniform but now we don't have a way to
+ * determine that, so, add multiplier to get closer to worst case.
+ */
+ tuplesPerPrevGroup = ceil(1.5 * tuplesPerPrevGroup / nGroups);
+
+ /*
+ * We could skip all followed columns for cost estimation, because we
+ * believe that tuples are unique by set ot previous columns
+ */
+ if (tuplesPerPrevGroup <= 1.0)
+ break;
+ }
+
+ list_free(pathkeyExprs);
+
+ /* per_tuple_cost is in cpu_operator_cost units */
+ per_tuple_cost *= cpu_operator_cost;
+
+ /*
+ * Accordingly to "Introduction to algorithms", Thomas H. Cormen, Charles E.
+ * Leiserson, Ronald L. Rivest, ISBN 0-07-013143-0, quicksort estimation
+ * formula has additional term proportional to number of tuples (See Chapter
+ * 8.2 and Theorem 4.1). It has meaning with low number of tuples,
+ * approximately less that 1e4. Of course, it could be implemented as
+ * additional multiplier under logarithm, but use more complicated formula
+ * which takes into account number of unique tuples and it isn't clear how
+ * to combine multiplier with groups. Estimate it as 10 in cpu_operator_cost
+ * unit.
+ */
+ per_tuple_cost += 10 * cpu_operator_cost;
+
+ per_tuple_cost += comparison_cost;
+
+ return tuples * per_tuple_cost;
+}
+
+/*
+ * simple wrapper just to estimate best sort path
+ */
+Cost
+cost_sort_estimate(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
+ double tuples)
+{
+ return compute_cpu_sort_cost(root, pathkeys, nPresortedKeys,
+ 0, tuples, tuples, false);
+}
+
/*
* cost_tuplesort
* Determines and returns the cost of sorting a relation using tuplesort,
@@ -1767,7 +2050,7 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
* number of initial runs formed and M is the merge order used by tuplesort.c.
* Since the average initial run should be about sort_mem, we have
* disk traffic = 2 * relsize * ceil(logM(p / sort_mem))
- * cpu = comparison_cost * t * log2(t)
+ * and cpu cost (computed by compute_cpu_sort_cost()).
*
* If the sort is bounded (i.e., only the first k result tuples are needed)
* and k tuples can fit into sort_mem, we use a heap method that keeps only
@@ -1786,9 +2069,11 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
* 'comparison_cost' is the extra cost per comparison, if any
* 'sort_mem' is the number of kilobytes of work memory allowed for the sort
* 'limit_tuples' is the bound on the number of output tuples; -1 if no bound
+ * 'startup_cost' is expected to be 0 at input. If there is "input cost" it should
+ * be added by caller later.
*/
static void
-cost_tuplesort(Cost *startup_cost, Cost *run_cost,
+cost_tuplesort(PlannerInfo *root, List *pathkeys, Cost *startup_cost, Cost *run_cost,
double tuples, int width,
Cost comparison_cost, int sort_mem,
double limit_tuples)
@@ -1805,9 +2090,6 @@ cost_tuplesort(Cost *startup_cost, Cost *run_cost,
if (tuples < 2.0)
tuples = 2.0;
- /* Include the default cost-per-comparison */
- comparison_cost += 2.0 * cpu_operator_cost;
-
/* Do we have a useful LIMIT? */
if (limit_tuples > 0 && limit_tuples < tuples)
{
@@ -1831,12 +2113,10 @@ cost_tuplesort(Cost *startup_cost, Cost *run_cost,
double log_runs;
double npageaccesses;
- /*
- * CPU costs
- *
- * Assume about N log2 N comparisons
- */
- *startup_cost = comparison_cost * tuples * LOG2(tuples);
+ /* CPU costs */
+ *startup_cost = compute_cpu_sort_cost(root, pathkeys, 0,
+ comparison_cost, tuples,
+ tuples, false);
/* Disk costs */
@@ -1852,18 +2132,17 @@ cost_tuplesort(Cost *startup_cost, Cost *run_cost,
}
else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
{
- /*
- * We'll use a bounded heap-sort keeping just K tuples in memory, for
- * a total number of tuple comparisons of N log2 K; but the constant
- * factor is a bit higher than for quicksort. Tweak it so that the
- * cost curve is continuous at the crossover point.
- */
- *startup_cost = comparison_cost * tuples * LOG2(2.0 * output_tuples);
+ /* We'll use a bounded heap-sort keeping just K tuples in memory. */
+ *startup_cost = compute_cpu_sort_cost(root, pathkeys, 0,
+ comparison_cost, tuples,
+ output_tuples, true);
}
else
{
/* We'll use plain quicksort on all the input tuples */
- *startup_cost = comparison_cost * tuples * LOG2(tuples);
+ *startup_cost = compute_cpu_sort_cost(root, pathkeys, 0,
+ comparison_cost, tuples,
+ tuples, false);
}
/*
@@ -1896,8 +2175,8 @@ cost_incremental_sort(Path *path,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples)
{
- Cost startup_cost = 0,
- run_cost = 0,
+ Cost startup_cost,
+ run_cost,
input_run_cost = input_total_cost - input_startup_cost;
double group_tuples,
input_groups;
@@ -1981,7 +2260,7 @@ cost_incremental_sort(Path *path,
* pessimistic about incremental sort performance and increase its average
* group size by half.
*/
- cost_tuplesort(&group_startup_cost, &group_run_cost,
+ cost_tuplesort(root, pathkeys, &group_startup_cost, &group_run_cost,
1.5 * group_tuples, width, comparison_cost, sort_mem,
limit_tuples);
@@ -1989,7 +2268,7 @@ cost_incremental_sort(Path *path,
* Startup cost of incremental sort is the startup cost of its first group
* plus the cost of its input.
*/
- startup_cost += group_startup_cost
+ startup_cost = group_startup_cost
+ input_startup_cost + group_input_run_cost;
/*
@@ -1998,7 +2277,7 @@ cost_incremental_sort(Path *path,
* group, plus the total cost to process the remaining groups, plus the
* remaining cost of input.
*/
- run_cost += group_run_cost
+ run_cost = group_run_cost
+ (group_run_cost + group_startup_cost) * (input_groups - 1)
+ group_input_run_cost * (input_groups - 1);
@@ -2038,7 +2317,7 @@ cost_sort(Path *path, PlannerInfo *root,
Cost startup_cost;
Cost run_cost;
- cost_tuplesort(&startup_cost, &run_cost,
+ cost_tuplesort(root, pathkeys, &startup_cost, &run_cost,
tuples, width,
comparison_cost, sort_mem,
limit_tuples);
@@ -2136,7 +2415,7 @@ append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
* Determines and returns the cost of an Append node.
*/
void
-cost_append(AppendPath *apath)
+cost_append(AppendPath *apath, PlannerInfo *root)
{
ListCell *l;
@@ -2204,7 +2483,7 @@ cost_append(AppendPath *apath)
* any child.
*/
cost_sort(&sort_path,
- NULL, /* doesn't currently need root */
+ root,
pathkeys,
subpath->total_cost,
subpath->rows,
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0188c1e9a1..9e3e02a0a8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -680,7 +680,18 @@ get_eclass_for_sort_expr(PlannerInfo *root,
if (opcintype == cur_em->em_datatype &&
equal(expr, cur_em->em_expr))
- return cur_ec; /* Match! */
+ {
+ /*
+ * Match!
+ *
+ * Copy sortref if it wasn't set yet, it's possible if ec was
+ * constructed from WHERE clause, ie it doesn't have target
+ * reference at all
+ */
+ if (cur_ec->ec_sortref == 0 && sortref > 0)
+ cur_ec->ec_sortref = sortref;
+ return cur_ec;
+ }
}
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index bd9a176d7d..7beb32488a 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -17,16 +17,19 @@
*/
#include "postgres.h"
+#include "miscadmin.h"
#include "access/stratnum.h"
#include "catalog/pg_opfamily.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
+#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "partitioning/partbounds.h"
#include "utils/lsyscache.h"
+#include "utils/selfuncs.h"
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
@@ -334,6 +337,312 @@ pathkeys_contained_in(List *keys1, List *keys2)
return false;
}
+/************************<DEBUG PART>*************************************/
+bool debug_group_by_reorder_by_pathkeys = true;
+bool debug_group_by_match_order_by = true;
+bool debug_cheapest_group_by = true;
+/************************</DEBUG PART>************************************/
+
+/*
+ * Reorder GROUP BY pathkeys and clauses to match order of pathkeys. Function
+ * returns new lists, original GROUP BY lists stay untouched.
+ */
+int
+group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
+ List **group_clauses)
+{
+ List *new_group_pathkeys= NIL,
+ *new_group_clauses = NIL;
+ ListCell *key;
+ int n;
+
+ if (debug_group_by_reorder_by_pathkeys == false)
+ return 0;
+
+ if (pathkeys == NIL || *group_pathkeys == NIL)
+ return 0;
+
+ /*
+ * For each pathkey it tries to find corresponding GROUP BY pathkey and
+ * clause.
+ */
+ foreach(key, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(key);
+ SortGroupClause *sgc;
+
+ /*
+ * Pathkey should use the same allocated struct, so, equiality of
+ * pointers is enough
+ */
+ if (!list_member_ptr(*group_pathkeys, pathkey))
+ break;
+
+ new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
+
+ sgc = get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
+ *group_clauses);
+ new_group_clauses = lappend(new_group_clauses, sgc);
+ }
+
+ n = list_length(new_group_pathkeys);
+
+ /*
+ * Just append the rest of pathkeys and clauses
+ */
+ *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
+ *group_pathkeys);
+ *group_clauses = list_concat_unique_ptr(new_group_clauses,
+ *group_clauses);
+
+ return n;
+}
+
+typedef struct MutatorState {
+ List *elemsList;
+ ListCell **elemCells;
+ void **elems;
+ int *positions;
+ int mutatorNColumns;
+ int count;
+} MutatorState;
+
+static void
+initMutator(MutatorState *state, List *elems, int start, int end)
+{
+ int i;
+ int n = end - start;
+ ListCell *lc;
+
+ memset(state, 0, sizeof(*state));
+
+ state->mutatorNColumns = n;
+
+ state->elemsList = list_copy(elems);
+
+ state->elems = palloc(sizeof(void*) * n);
+ state->elemCells = palloc(sizeof(ListCell*) * n);
+ state->positions = palloc(sizeof(int) * n);
+
+ i = 0;
+ for_each_cell(lc, state->elemsList, list_nth_cell(state->elemsList, start))
+ {
+ state->elemCells[i] = lc;
+ state->elems[i] = lfirst(lc);
+ state->positions[i] = i + 1;
+ i++;
+ if (i >= n)
+ break;
+ }
+}
+
+static void
+swap(int *a, int i, int j)
+{
+ int s = a[i];
+
+ a[i] = a[j];
+ a[j] = s;
+}
+
+static bool
+getNextSet(int *a, int n)
+{
+ int j, k, l, r;
+
+ j = n - 2;
+ while (j >= 0 && a[j] >= a[j + 1])
+ j--;
+ if (j < 0)
+ return false;
+
+ k = n - 1;
+ while (k >= 0 && a[j] >= a[k])
+ k--;
+ swap(a, j, k);
+
+ l = j + 1;
+ r = n - 1;
+ while (l < r)
+ swap(a, l++, r--);
+
+
+ return true;
+}
+
+static List*
+doMutator(MutatorState *state)
+{
+ int i;
+
+ state->count++;
+
+ /* first set is original set */
+ if (state->count == 1)
+ return state->elemsList;
+
+ if (getNextSet(state->positions, state->mutatorNColumns) == false)
+ {
+ pfree(state->elems);
+ pfree(state->elemCells);
+ pfree(state->positions);
+ list_free(state->elemsList);
+
+ return NIL;
+ }
+
+ for(i=0; i<state->mutatorNColumns; i++)
+ lfirst(state->elemCells[i]) =
+ (void*) state->elems[ state->positions[i] - 1 ];
+
+ return state->elemsList;
+}
+
+typedef struct {
+ Cost cost;
+ PathKey *pathkey;
+} PathkeySortCost;
+
+static int
+pathkey_sort_cost_comparator(const void *_a, const void *_b)
+{
+ const PathkeySortCost *a = (PathkeySortCost *) _a;
+ const PathkeySortCost *b = (PathkeySortCost *) _b;
+
+ if (a->cost < b->cost)
+ return -1;
+ else if (a->cost == b->cost)
+ return 0;
+ return 1;
+}
+/*
+ * Order tail of list of group pathkeys by uniqueness descendetly. It allows to
+ * speedup sorting. Returns newly allocated lists, old ones stay untouched.
+ * n_preordered defines a head of list which order should be prevented.
+ */
+void
+get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
+ List **group_pathkeys, List **group_clauses,
+ int n_preordered)
+{
+ List *new_group_pathkeys = NIL,
+ *new_group_clauses = NIL,
+ *var_group_pathkeys;
+
+ ListCell *cell;
+ MutatorState mstate;
+ double cheapest_sort_cost = -1.0;
+
+ int nFreeKeys;
+ int nToPermute;
+ int i;
+
+ if (list_length(*group_pathkeys) - n_preordered < 2)
+ return; /* nothing to do */
+
+ /*
+ * Will try to match ORDER BY pathkeys in hope that one sort is cheaper than
+ * two
+ */
+ if (debug_group_by_match_order_by &&
+ n_preordered == 0 && root->sort_pathkeys)
+ {
+ bool _save_debug_group_by_reorder_by_pathkeys =
+ debug_group_by_reorder_by_pathkeys; /* DEBUG ONLY, to be removed */
+
+ debug_group_by_reorder_by_pathkeys = true;
+ n_preordered = group_keys_reorder_by_pathkeys(root->sort_pathkeys,
+ group_pathkeys,
+ group_clauses);
+ debug_group_by_reorder_by_pathkeys = _save_debug_group_by_reorder_by_pathkeys;
+
+ if (list_length(*group_pathkeys) - n_preordered < 2)
+ return; /* nothing to do */
+ }
+
+ /*
+ * Try all permutations of at most 4 cheapeast pathkeys.
+ */
+ nFreeKeys = list_length(*group_pathkeys) - n_preordered;
+ nToPermute = 4;
+ if (nFreeKeys > nToPermute)
+ {
+ /*
+ * Sort the remaining pathkeys cheapest first.
+ */
+ PathkeySortCost *costs = palloc(sizeof(*costs) * nFreeKeys);
+ cell = list_nth_cell(*group_pathkeys, n_preordered);
+ for (i = 0; cell != NULL; i++, (cell = lnext(*group_pathkeys, cell)))
+ {
+ List *to_cost = list_make1(lfirst(cell));
+
+ Assert(i < nFreeKeys);
+
+ costs[i].pathkey = lfirst(cell);
+ costs[i].cost = cost_sort_estimate(root, to_cost, 0, nrows);
+
+ pfree(to_cost);
+ }
+ qsort(costs, nFreeKeys, sizeof(*costs), pathkey_sort_cost_comparator);
+
+ /* Construct the sorted list. First, the preordered pathkeys. */
+ new_group_pathkeys = list_truncate(list_copy(*group_pathkeys), n_preordered);
+
+ /* The rest, ordered by increasing cost */
+ for (i = 0; i < nFreeKeys; i++)
+ new_group_pathkeys = lappend(new_group_pathkeys, costs[i].pathkey);
+
+ pfree(costs);
+ }
+ else
+ {
+ /*
+ * Since v13 list_free() can clean list elements so for original list not to be modified it should be copied to
+ * a new one which can then be cleaned safely if needed.
+ */
+ new_group_pathkeys = list_copy(*group_pathkeys);
+ nToPermute = nFreeKeys;
+ }
+
+ if (!debug_cheapest_group_by)
+ return;
+
+ initMutator(&mstate, new_group_pathkeys, n_preordered, n_preordered + nToPermute);
+
+ while((var_group_pathkeys = doMutator(&mstate)) != NIL)
+ {
+ Cost cost;
+
+ cost = cost_sort_estimate(root, var_group_pathkeys, n_preordered, nrows);
+
+ if (cost < cheapest_sort_cost || cheapest_sort_cost < 0)
+ {
+ list_free(new_group_pathkeys);
+ new_group_pathkeys = list_copy(var_group_pathkeys);
+ cheapest_sort_cost = cost;
+ }
+ }
+
+ /*
+ * repeat order of pathkeys for clauses
+ */
+ foreach(cell, new_group_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(cell);
+
+ new_group_clauses = lappend(new_group_clauses,
+ get_sortgroupref_clause(pathkey->pk_eclass->ec_sortref,
+ *group_clauses));
+ }
+
+ /* Just append the rest GROUP BY clauses */
+ new_group_clauses = list_concat_unique_ptr(new_group_clauses,
+ *group_clauses);
+
+ *group_pathkeys = new_group_pathkeys;
+ *group_clauses = new_group_clauses;
+}
+
/*
* pathkeys_count_contained_in
* Same as pathkeys_contained_in, but also sets length of longest
@@ -1862,6 +2171,39 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
return n_common_pathkeys;
}
+/*
+ * pathkeys_useful_for_grouping
+ * Count the number of pathkeys that are useful for grouping (instead of
+ * explicit sort)
+ *
+ * Group pathkeys could be reordered, so we don't bother about actual order in
+ * pathkeys
+ */
+static int
+pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
+{
+ ListCell *key;
+ int n = 0;
+
+ if (root->group_pathkeys == NIL)
+ return 0; /* no special ordering requested */
+
+ if (pathkeys == NIL)
+ return 0; /* unordered path */
+
+ foreach(key, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(key);
+
+ if (!list_member_ptr(root->group_pathkeys, pathkey))
+ break;
+
+ n++;
+ }
+
+ return n;
+}
+
/*
* truncate_useless_pathkeys
* Shorten the given pathkey list to just the useful pathkeys.
@@ -1876,6 +2218,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
@@ -1911,6 +2256,8 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
{
if (rel->joininfo != NIL || rel->has_eclass_joins)
return true; /* might be able to use pathkeys for merging */
+ if (root->group_pathkeys != NIL)
+ return true; /* might be able to use pathkeys for grouping */
if (root->query_pathkeys != NIL)
return true; /* might be able to use them for ordering */
return false; /* definitely useless */
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 545b56bcaf..6e82d5ddac 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6517,21 +6517,49 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
Path *path = (Path *) lfirst(lc);
Path *path_original = path;
bool is_sorted;
- int presorted_keys;
+ int presorted_keys = 0;
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
- path->pathkeys,
- &presorted_keys);
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups = 0;
+
+ if (parse->groupingSets)
+ {
+ /*
+ * prevent group pathkey reordering, just check the same
+ * order paths pathkeys and group pathkeys
+ */
+ is_sorted = pathkeys_count_contained_in(group_pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+ }
+ else
+ {
+ n_preordered_groups =
+ group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = (n_preordered_groups == list_length(group_pathkeys));
+ }
if (path == cheapest_path || is_sorted)
{
/* Sort the cheapest-total path if it isn't already sorted */
if (!is_sorted)
+ {
+ if (!parse->groupingSets)
+ get_cheapest_group_keys_order(root,
+ path->rows,
+ &group_pathkeys,
+ &group_clauses,
+ n_preordered_groups);
+
path = (Path *) create_sort_path(root,
grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
+ }
/* Now decide what to stick atop it */
if (parse->groupingSets)
@@ -6551,14 +6579,14 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_SIMPLE,
- parse->groupClause,
+ group_clauses,
havingQual,
agg_costs,
dNumGroups));
}
- else if (parse->groupClause)
+ else if (group_clauses)
{
/*
* We have GROUP BY without aggregation or grouping sets.
@@ -6568,7 +6596,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
create_group_path(root,
grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
havingQual,
dNumGroups));
}
@@ -6664,11 +6692,18 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
Path *path = (Path *) lfirst(lc);
Path *path_original = path;
bool is_sorted;
- int presorted_keys;
+ int presorted_keys = 0;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
+ is_sorted = pathkeys_count_contained_in(group_pathkeys,
path->pathkeys,
&presorted_keys);
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = is_sorted || (n_preordered_groups == list_length(group_pathkeys));
/*
* Insert a Sort node, if required. But there's no point in
@@ -6678,10 +6713,15 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
if (path != partially_grouped_rel->cheapest_total_path)
continue;
+ get_cheapest_group_keys_order(root,
+ path->rows,
+ &group_pathkeys,
+ &group_clauses,
+ n_preordered_groups);
path = (Path *) create_sort_path(root,
grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
}
@@ -6691,9 +6731,9 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_FINAL_DESERIAL,
- parse->groupClause,
+ group_clauses,
havingQual,
agg_final_costs,
dNumGroups));
@@ -6702,7 +6742,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
create_group_path(root,
grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
havingQual,
dNumGroups));
@@ -6959,18 +6999,32 @@ create_partial_grouping_paths(PlannerInfo *root,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
+
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = (n_preordered_groups == list_length(group_pathkeys)) ||
+ pathkeys_contained_in(group_pathkeys, path->pathkeys);
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
if (path == cheapest_total_path || is_sorted)
{
/* Sort the cheapest partial path, if it isn't already */
if (!is_sorted)
+ {
+ get_cheapest_group_keys_order(root,
+ path->rows,
+ &group_pathkeys,
+ &group_clauses,
+ n_preordered_groups);
path = (Path *) create_sort_path(root,
partially_grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
+ }
if (parse->hasAggs)
add_path(partially_grouped_rel, (Path *)
@@ -6978,9 +7032,9 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
+ group_clauses,
NIL,
agg_partial_costs,
dNumPartialGroups));
@@ -6989,7 +7043,7 @@ create_partial_grouping_paths(PlannerInfo *root,
create_group_path(root,
partially_grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
NIL,
dNumPartialGroups));
}
@@ -7062,21 +7116,37 @@ create_partial_grouping_paths(PlannerInfo *root,
Path *path = (Path *) lfirst(lc);
Path *path_original = path;
bool is_sorted;
- int presorted_keys;
+ int presorted_keys = 0;
+ List *group_pathkeys = root->group_pathkeys,
+ *group_clauses = parse->groupClause;
+ int n_preordered_groups;
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
+ is_sorted = pathkeys_count_contained_in(group_pathkeys,
path->pathkeys,
&presorted_keys);
+ n_preordered_groups = group_keys_reorder_by_pathkeys(path->pathkeys,
+ &group_pathkeys,
+ &group_clauses);
+ is_sorted = is_sorted || (n_preordered_groups == list_length(group_pathkeys));
+
if (path == cheapest_partial_path || is_sorted)
{
+
/* Sort the cheapest partial path, if it isn't already */
if (!is_sorted)
+ {
+ get_cheapest_group_keys_order(root,
+ path->rows,
+ &group_pathkeys,
+ &group_clauses,
+ n_preordered_groups);
path = (Path *) create_sort_path(root,
partially_grouped_rel,
path,
- root->group_pathkeys,
+ group_pathkeys,
-1.0);
+ }
if (parse->hasAggs)
add_partial_path(partially_grouped_rel, (Path *)
@@ -7084,9 +7154,9 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ group_clauses ? AGG_SORTED : AGG_PLAIN,
AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
+ group_clauses,
NIL,
agg_partial_costs,
dNumPartialPartialGroups));
@@ -7095,7 +7165,7 @@ create_partial_grouping_paths(PlannerInfo *root,
create_group_path(root,
partially_grouped_rel,
path,
- parse->groupClause,
+ group_clauses,
NIL,
dNumPartialPartialGroups));
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 69b83071cf..0bfb638abc 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1342,7 +1342,7 @@ create_append_path(PlannerInfo *root,
pathnode->path.pathkeys = child->pathkeys;
}
else
- cost_append(pathnode);
+ cost_append(pathnode, root);
/* If the caller provided a row estimate, override the computed value. */
if (rows >= 0)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 52314d3aa1..80fc597630 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3292,7 +3292,10 @@ add_unique_group_var(PlannerInfo *root, List *varinfos,
}
/*
- * estimate_num_groups - Estimate number of groups in a grouped query
+ * estimate_num_groups/estimate_num_groups_incremental
+ * - Estimate number of groups in a grouped query.
+ * _incremental variant is performance optimization for
+ * case of adding one-by-one column
*
* Given a query having a GROUP BY clause, estimate how many groups there
* will be --- ie, the number of distinct combinations of the GROUP BY
@@ -3360,11 +3363,20 @@ double
estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
List **pgset)
{
- List *varinfos = NIL;
+ return estimate_num_groups_incremental(root, groupExprs,
+ input_rows, pgset, NULL, 0);
+}
+
+double
+estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs,
+ double input_rows,
+ List **pgset, List **cache_varinfos, int prevNExprs)
+{
+ List *varinfos = (cache_varinfos) ? *cache_varinfos : NIL;
double srf_multiplier = 1.0;
double numdistinct;
ListCell *l;
- int i;
+ int i, j;
/*
* We don't ever want to return an estimate of zero groups, as that tends
@@ -3391,7 +3403,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
*/
numdistinct = 1.0;
- i = 0;
+ i = j = 0;
foreach(l, groupExprs)
{
Node *groupexpr = (Node *) lfirst(l);
@@ -3400,6 +3412,14 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
List *varshere;
ListCell *l2;
+ /* was done on previous call */
+ if (cache_varinfos && j++ < prevNExprs)
+ {
+ if (pgset)
+ i++; /* to keep in sync with lines below */
+ continue;
+ }
+
/* is expression in this grouping set? */
if (pgset && !list_member_int(*pgset, i++))
continue;
@@ -3461,7 +3481,11 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
if (varshere == NIL)
{
if (contain_volatile_functions(groupexpr))
+ {
+ if (cache_varinfos)
+ *cache_varinfos = varinfos;
return input_rows;
+ }
continue;
}
@@ -3478,6 +3502,9 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
}
}
+ if (cache_varinfos)
+ *cache_varinfos = varinfos;
+
/*
* If now no Vars, we must have an all-constant or all-boolean GROUP BY
* list.
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 3fd1a5fbe2..c6d8c37d74 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -2049,6 +2049,35 @@ static struct config_bool ConfigureNamesBool[] =
NULL, NULL, NULL
},
+/************************<DEBUG OPT GROUP BY>*********************************/
+ {
+ {"debug_group_by_reorder_by_pathkeys", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("enable reorder GROUP BY by pathkeys"),
+ NULL
+ },
+ &debug_group_by_reorder_by_pathkeys,
+ true,
+ NULL, NULL, NULL
+ },
+ {
+ {"debug_enable_group_by_match_order_by", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("enable matching GROUP BY by ORDER BY."),
+ NULL
+ },
+ &debug_group_by_match_order_by,
+ true,
+ NULL, NULL, NULL
+ },
+ {
+ {"debug_enable_cheapest_group_by", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("find a cheapest order of columns in GROUP BY."),
+ NULL
+ },
+ &debug_cheapest_group_by,
+ true,
+ NULL, NULL, NULL
+ },
+/************************</DEBUG OPT GROUP BY>********************************/
/* End-of-list marker */
{
{NULL, 0, 0, NULL, NULL}, NULL, false, NULL, NULL, NULL
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 1be93be098..baf6ee79b4 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -110,7 +110,9 @@ extern void cost_incremental_sort(Path *path,
Cost input_startup_cost, Cost input_total_cost,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples);
-extern void cost_append(AppendPath *path);
+extern Cost cost_sort_estimate(PlannerInfo *root, List *pathkeys,
+ int nPresortedKeys, double tuples);
+extern void cost_append(AppendPath *path, PlannerInfo *root);
extern void cost_merge_append(Path *path, PlannerInfo *root,
List *pathkeys, int n_streams,
Cost input_startup_cost, Cost input_total_cost,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 035d3e1206..a43898c929 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -196,6 +196,19 @@ typedef enum
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
extern bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common);
+extern int group_keys_reorder_by_pathkeys(List *pathkeys,
+ List **group_pathkeys,
+ List **group_clauses);
+/************************<DEBUG OPT GROUP BY>*********************************/
+extern bool debug_group_by_reorder_by_pathkeys;
+extern bool debug_group_by_match_order_by;
+extern bool debug_cheapest_group_by;
+/************************</DEBUG OPT GROUP BY>********************************/
+extern void get_cheapest_group_keys_order(PlannerInfo *root,
+ double nrows,
+ List **group_pathkeys,
+ List **group_clauses,
+ int n_preordered);
extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
CostSelector cost_criterion,
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index f9be539602..03e25011b9 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -198,6 +198,9 @@ extern void mergejoinscansel(PlannerInfo *root, Node *clause,
extern double estimate_num_groups(PlannerInfo *root, List *groupExprs,
double input_rows, List **pgset);
+extern double estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs,
+ double input_rows, List **pgset,
+ List **cache_varinfos, int prevNExprs);
extern void estimate_hash_bucket_stats(PlannerInfo *root,
Node *hashkey, double nbuckets,
diff --git a/src/test/modules/unsafe_tests/Makefile b/src/test/modules/unsafe_tests/Makefile
index 3ecf5fcfc5..2cf710eb2c 100644
--- a/src/test/modules/unsafe_tests/Makefile
+++ b/src/test/modules/unsafe_tests/Makefile
@@ -1,6 +1,6 @@
# src/test/modules/unsafe_tests/Makefile
-REGRESS = rolenames alter_system_table
+REGRESS = alter_system_table
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 2c818d9253..a970ef45a1 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1200,7 +1200,8 @@ explain (costs off)
select distinct min(f1), max(f1) from minmaxtest;
QUERY PLAN
---------------------------------------------------------------------------------------------
- Unique
+ HashAggregate
+ Group Key: $0, $1
InitPlan 1 (returns $0)
-> Limit
-> Merge Append
@@ -1223,10 +1224,8 @@ explain (costs off)
-> Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest_8
Index Cond: (f1 IS NOT NULL)
-> Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest_9
- -> Sort
- Sort Key: ($0), ($1)
- -> Result
-(26 rows)
+ -> Result
+(25 rows)
select distinct min(f1), max(f1) from minmaxtest;
min | max
@@ -2408,6 +2407,237 @@ SELECT balk(hundred) FROM tenk1;
(1 row)
ROLLBACK;
+-- GROUP BY optimization by reorder columns
+SELECT
+ i AS id,
+ i/2 AS p,
+ format('%60s', i%2) AS v,
+ i/4 AS c,
+ i/8 AS d,
+ (random() * (10000/8))::int as e --the same as d but no correlation with p
+ INTO btg
+FROM
+ generate_series(1, 10000) i;
+VACUUM btg;
+ANALYZE btg;
+-- GROUP BY optimization by reorder columns by frequency
+SET enable_hashagg=off;
+SET max_parallel_workers= 0;
+SET max_parallel_workers_per_gather = 0;
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Sort
+ Sort Key: p, v
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Sort
+ Sort Key: p, v
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, c, v
+ -> Sort
+ Sort Key: p, c, v
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: v, p, c
+ -> Sort
+ Sort Key: v, p, c
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c;
+ QUERY PLAN
+------------------------------
+ GroupAggregate
+ Group Key: p, d, c, v
+ -> Sort
+ Sort Key: p, d, c, v
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c;
+ QUERY PLAN
+------------------------------
+ GroupAggregate
+ Group Key: v, p, d, c
+ -> Sort
+ Sort Key: v, p, d, c
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c;
+ QUERY PLAN
+------------------------------
+ GroupAggregate
+ Group Key: p, v, d, c
+ -> Sort
+ Sort Key: p, v, d, c
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, d, e
+ -> Sort
+ Sort Key: p, d, e
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, e, d
+ -> Sort
+ Sort Key: p, e, d
+ -> Seq Scan on btg
+(5 rows)
+
+CREATE STATISTICS btg_dep ON d, e, p FROM btg;
+ANALYZE btg;
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, d, e
+ -> Sort
+ Sort Key: p, d, e
+ -> Seq Scan on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+ QUERY PLAN
+-----------------------------
+ GroupAggregate
+ Group Key: p, e, d
+ -> Sort
+ Sort Key: p, e, d
+ -> Seq Scan on btg
+(5 rows)
+
+-- GROUP BY optimization by reorder columns by index scan
+CREATE INDEX ON btg(p, v);
+SET enable_seqscan=off;
+SET enable_bitmapscan=off;
+VACUUM btg;
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v;
+ QUERY PLAN
+------------------------------------------------
+ GroupAggregate
+ Group Key: p, v
+ -> Index Only Scan using btg_p_v_idx on btg
+(3 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c
+ -> Sort
+ Sort Key: p, v, c
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c
+ -> Sort
+ Sort Key: p, v, c
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c, d
+ -> Sort
+ Sort Key: p, v, c, d
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v;
+ QUERY PLAN
+-------------------------------------------------
+ GroupAggregate
+ Group Key: p, v, c, d
+ -> Sort
+ Sort Key: p, v, c, d
+ -> Index Scan using btg_p_v_idx on btg
+(5 rows)
+
+DROP TABLE btg;
+RESET enable_hashagg;
+RESET max_parallel_workers;
+RESET max_parallel_workers_per_gather;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
-- Secondly test the case of a parallel aggregate combiner function
-- returning NULL. For that use normal transition function, but a
-- combiner function returning NULL.
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 68ca321163..859db97ca4 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1437,7 +1437,7 @@ set parallel_setup_cost = 0;
set parallel_tuple_cost = 0;
set max_parallel_workers_per_gather = 2;
create table t (a int, b int, c int);
-insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i);
+insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i);
create index on t (a);
analyze t;
set enable_incremental_sort = off;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 5c7528c029..2e9617351d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -1932,8 +1932,8 @@ USING (name);
------+----+----
bb | 12 | 13
cc | 22 | 23
- dd | | 33
ee | 42 |
+ dd | | 33
(4 rows)
-- Cases with non-nullable expressions in subquery results;
@@ -1967,8 +1967,8 @@ NATURAL FULL JOIN
------+------+------+------+------
bb | 12 | 2 | 13 | 3
cc | 22 | 2 | 23 | 3
- dd | | | 33 | 3
ee | 42 | 2 | |
+ dd | | | 33 | 3
(4 rows)
SELECT * FROM
@@ -4534,18 +4534,20 @@ select d.* from d left join (select * from b group by b.id, b.c_id) s
explain (costs off)
select d.* from d left join (select distinct * from b) s
on d.a = s.id;
- QUERY PLAN
---------------------------------------
- Merge Right Join
- Merge Cond: (b.id = d.a)
- -> Unique
- -> Sort
- Sort Key: b.id, b.c_id
- -> Seq Scan on b
+ QUERY PLAN
+---------------------------------------------
+ Merge Left Join
+ Merge Cond: (d.a = s.id)
-> Sort
Sort Key: d.a
-> Seq Scan on d
-(9 rows)
+ -> Sort
+ Sort Key: s.id
+ -> Subquery Scan on s
+ -> HashAggregate
+ Group Key: b.id, b.c_id
+ -> Seq Scan on b
+(11 rows)
-- check join removal works when uniqueness of the join condition is enforced
-- by a UNION
@@ -6213,44 +6215,39 @@ select * from j1 natural join j2;
explain (verbose, costs off)
select * from j1
inner join (select distinct id from j3) j3 on j1.id = j3.id;
- QUERY PLAN
------------------------------------------
+ QUERY PLAN
+-----------------------------------
Nested Loop
Output: j1.id, j3.id
Inner Unique: true
Join Filter: (j1.id = j3.id)
- -> Unique
+ -> HashAggregate
Output: j3.id
- -> Sort
+ Group Key: j3.id
+ -> Seq Scan on public.j3
Output: j3.id
- Sort Key: j3.id
- -> Seq Scan on public.j3
- Output: j3.id
-> Seq Scan on public.j1
Output: j1.id
-(13 rows)
+(11 rows)
-- ensure group by clause allows the inner to become unique
explain (verbose, costs off)
select * from j1
inner join (select id from j3 group by id) j3 on j1.id = j3.id;
- QUERY PLAN
------------------------------------------
+ QUERY PLAN
+-----------------------------------
Nested Loop
Output: j1.id, j3.id
Inner Unique: true
Join Filter: (j1.id = j3.id)
- -> Group
+ -> HashAggregate
Output: j3.id
Group Key: j3.id
- -> Sort
+ -> Seq Scan on public.j3
Output: j3.id
- Sort Key: j3.id
- -> Seq Scan on public.j3
- Output: j3.id
-> Seq Scan on public.j1
Output: j1.id
-(14 rows)
+(11 rows)
drop table j1;
drop table j2;
diff --git a/src/test/regress/expected/partition_aggregate.out b/src/test/regress/expected/partition_aggregate.out
index dfa4b036b5..a08a3825ff 100644
--- a/src/test/regress/expected/partition_aggregate.out
+++ b/src/test/regress/expected/partition_aggregate.out
@@ -952,32 +952,30 @@ SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HA
--------------------------------------------------------------------------------------
Sort
Sort Key: pagg_tab_ml.a, (sum(pagg_tab_ml.b)), (array_agg(DISTINCT pagg_tab_ml.c))
- -> Gather
- Workers Planned: 2
- -> Parallel Append
- -> GroupAggregate
- Group Key: pagg_tab_ml.a
- Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml.a
- -> Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
- -> GroupAggregate
- Group Key: pagg_tab_ml_5.a
- Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml_5.a
- -> Append
- -> Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
- -> Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
- -> GroupAggregate
- Group Key: pagg_tab_ml_2.a
- Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml_2.a
- -> Append
- -> Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
- -> Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
-(27 rows)
+ -> Append
+ -> GroupAggregate
+ Group Key: pagg_tab_ml.a
+ Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml.a
+ -> Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
+ -> GroupAggregate
+ Group Key: pagg_tab_ml_2.a
+ Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml_2.a
+ -> Append
+ -> Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
+ -> Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
+ -> GroupAggregate
+ Group Key: pagg_tab_ml_5.a
+ Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml_5.a
+ -> Append
+ -> Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
+ -> Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
+(25 rows)
SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3 ORDER BY 1, 2, 3;
a | sum | array_agg | count
@@ -996,34 +994,32 @@ SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HA
-- Without ORDER BY clause, to test Gather at top-most path
EXPLAIN (COSTS OFF)
SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3;
- QUERY PLAN
----------------------------------------------------------------------------
- Gather
- Workers Planned: 2
- -> Parallel Append
- -> GroupAggregate
- Group Key: pagg_tab_ml.a
- Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml.a
- -> Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
- -> GroupAggregate
- Group Key: pagg_tab_ml_5.a
- Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml_5.a
- -> Append
- -> Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
- -> Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
- -> GroupAggregate
- Group Key: pagg_tab_ml_2.a
- Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
- -> Sort
- Sort Key: pagg_tab_ml_2.a
- -> Append
- -> Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
- -> Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
-(25 rows)
+ QUERY PLAN
+---------------------------------------------------------------------
+ Append
+ -> GroupAggregate
+ Group Key: pagg_tab_ml.a
+ Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml.a
+ -> Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
+ -> GroupAggregate
+ Group Key: pagg_tab_ml_2.a
+ Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml_2.a
+ -> Append
+ -> Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
+ -> Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
+ -> GroupAggregate
+ Group Key: pagg_tab_ml_5.a
+ Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
+ -> Sort
+ Sort Key: pagg_tab_ml_5.a
+ -> Append
+ -> Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
+ -> Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
+(23 rows)
-- Full aggregation at level 1 as GROUP BY clause matches with PARTITION KEY
-- for level 1 only. For subpartitions, GROUP BY clause does not match with
@@ -1379,28 +1375,26 @@ SELECT x, sum(y), avg(y), count(*) FROM pagg_tab_para GROUP BY x HAVING avg(y) <
-- When GROUP BY clause does not match; partial aggregation is performed for each partition.
EXPLAIN (COSTS OFF)
SELECT y, sum(x), avg(x), count(*) FROM pagg_tab_para GROUP BY y HAVING avg(x) < 12 ORDER BY 1, 2, 3;
- QUERY PLAN
--------------------------------------------------------------------------------------------
+ QUERY PLAN
+-------------------------------------------------------------------------------------
Sort
Sort Key: pagg_tab_para.y, (sum(pagg_tab_para.x)), (avg(pagg_tab_para.x))
- -> Finalize GroupAggregate
+ -> Finalize HashAggregate
Group Key: pagg_tab_para.y
Filter: (avg(pagg_tab_para.x) < '12'::numeric)
- -> Gather Merge
+ -> Gather
Workers Planned: 2
- -> Sort
- Sort Key: pagg_tab_para.y
- -> Parallel Append
- -> Partial HashAggregate
- Group Key: pagg_tab_para.y
- -> Parallel Seq Scan on pagg_tab_para_p1 pagg_tab_para
- -> Partial HashAggregate
- Group Key: pagg_tab_para_1.y
- -> Parallel Seq Scan on pagg_tab_para_p2 pagg_tab_para_1
- -> Partial HashAggregate
- Group Key: pagg_tab_para_2.y
- -> Parallel Seq Scan on pagg_tab_para_p3 pagg_tab_para_2
-(19 rows)
+ -> Parallel Append
+ -> Partial HashAggregate
+ Group Key: pagg_tab_para.y
+ -> Parallel Seq Scan on pagg_tab_para_p1 pagg_tab_para
+ -> Partial HashAggregate
+ Group Key: pagg_tab_para_1.y
+ -> Parallel Seq Scan on pagg_tab_para_p2 pagg_tab_para_1
+ -> Partial HashAggregate
+ Group Key: pagg_tab_para_2.y
+ -> Parallel Seq Scan on pagg_tab_para_p3 pagg_tab_para_2
+(17 rows)
SELECT y, sum(x), avg(x), count(*) FROM pagg_tab_para GROUP BY y HAVING avg(x) < 12 ORDER BY 1, 2, 3;
y | sum | avg | count
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 0057f41caa..e3fdfb3e31 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -466,52 +466,41 @@ EXPLAIN (COSTS OFF)
SELECT a, b FROM prt1 FULL JOIN prt2 p2(b,a,c) USING(a,b)
WHERE a BETWEEN 490 AND 510
GROUP BY 1, 2 ORDER BY 1, 2;
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------
Group
Group Key: (COALESCE(prt1.a, p2.a)), (COALESCE(prt1.b, p2.b))
- -> Merge Append
+ -> Sort
Sort Key: (COALESCE(prt1.a, p2.a)), (COALESCE(prt1.b, p2.b))
- -> Group
- Group Key: (COALESCE(prt1.a, p2.a)), (COALESCE(prt1.b, p2.b))
- -> Sort
- Sort Key: (COALESCE(prt1.a, p2.a)), (COALESCE(prt1.b, p2.b))
- -> Merge Full Join
- Merge Cond: ((prt1.a = p2.a) AND (prt1.b = p2.b))
- Filter: ((COALESCE(prt1.a, p2.a) >= 490) AND (COALESCE(prt1.a, p2.a) <= 510))
- -> Sort
- Sort Key: prt1.a, prt1.b
- -> Seq Scan on prt1_p1 prt1
- -> Sort
- Sort Key: p2.a, p2.b
- -> Seq Scan on prt2_p1 p2
- -> Group
- Group Key: (COALESCE(prt1_1.a, p2_1.a)), (COALESCE(prt1_1.b, p2_1.b))
- -> Sort
- Sort Key: (COALESCE(prt1_1.a, p2_1.a)), (COALESCE(prt1_1.b, p2_1.b))
- -> Merge Full Join
- Merge Cond: ((prt1_1.a = p2_1.a) AND (prt1_1.b = p2_1.b))
- Filter: ((COALESCE(prt1_1.a, p2_1.a) >= 490) AND (COALESCE(prt1_1.a, p2_1.a) <= 510))
- -> Sort
- Sort Key: prt1_1.a, prt1_1.b
- -> Seq Scan on prt1_p2 prt1_1
- -> Sort
- Sort Key: p2_1.a, p2_1.b
- -> Seq Scan on prt2_p2 p2_1
- -> Group
- Group Key: (COALESCE(prt1_2.a, p2_2.a)), (COALESCE(prt1_2.b, p2_2.b))
- -> Sort
- Sort Key: (COALESCE(prt1_2.a, p2_2.a)), (COALESCE(prt1_2.b, p2_2.b))
- -> Merge Full Join
- Merge Cond: ((prt1_2.a = p2_2.a) AND (prt1_2.b = p2_2.b))
- Filter: ((COALESCE(prt1_2.a, p2_2.a) >= 490) AND (COALESCE(prt1_2.a, p2_2.a) <= 510))
- -> Sort
- Sort Key: prt1_2.a, prt1_2.b
- -> Seq Scan on prt1_p3 prt1_2
- -> Sort
- Sort Key: p2_2.a, p2_2.b
- -> Seq Scan on prt2_p3 p2_2
-(43 rows)
+ -> Append
+ -> Merge Full Join
+ Merge Cond: ((prt1_1.a = p2_1.a) AND (prt1_1.b = p2_1.b))
+ Filter: ((COALESCE(prt1_1.a, p2_1.a) >= 490) AND (COALESCE(prt1_1.a, p2_1.a) <= 510))
+ -> Sort
+ Sort Key: prt1_1.a, prt1_1.b
+ -> Seq Scan on prt1_p1 prt1_1
+ -> Sort
+ Sort Key: p2_1.a, p2_1.b
+ -> Seq Scan on prt2_p1 p2_1
+ -> Merge Full Join
+ Merge Cond: ((prt1_2.a = p2_2.a) AND (prt1_2.b = p2_2.b))
+ Filter: ((COALESCE(prt1_2.a, p2_2.a) >= 490) AND (COALESCE(prt1_2.a, p2_2.a) <= 510))
+ -> Sort
+ Sort Key: prt1_2.a, prt1_2.b
+ -> Seq Scan on prt1_p2 prt1_2
+ -> Sort
+ Sort Key: p2_2.a, p2_2.b
+ -> Seq Scan on prt2_p2 p2_2
+ -> Merge Full Join
+ Merge Cond: ((prt1_3.b = p2_3.b) AND (prt1_3.a = p2_3.a))
+ Filter: ((COALESCE(prt1_3.a, p2_3.a) >= 490) AND (COALESCE(prt1_3.a, p2_3.a) <= 510))
+ -> Sort
+ Sort Key: prt1_3.b, prt1_3.a
+ -> Seq Scan on prt1_p3 prt1_3
+ -> Sort
+ Sort Key: p2_3.b, p2_3.a
+ -> Seq Scan on prt2_p3 p2_3
+(32 rows)
SELECT a, b FROM prt1 FULL JOIN prt2 p2(b,a,c) USING(a,b)
WHERE a BETWEEN 490 AND 510
@@ -1339,7 +1328,7 @@ SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, pl
QUERY PLAN
--------------------------------------------------------------------------------
GroupAggregate
- Group Key: t1.c, t2.c, t3.c
+ Group Key: t1.c, t3.c, t2.c
-> Sort
Sort Key: t1.c, t3.c
-> Append
@@ -1483,7 +1472,7 @@ SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, ph
QUERY PLAN
--------------------------------------------------------------------------------
GroupAggregate
- Group Key: t1.c, t2.c, t3.c
+ Group Key: t1.c, t3.c, t2.c
-> Sort
Sort Key: t1.c, t3.c
-> Append
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 75f78db8f5..63b52c065f 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -1291,24 +1291,22 @@ select distinct q1 from
union all
select distinct * from int8_tbl i82) ss
where q2 = q2;
- QUERY PLAN
-----------------------------------------------------------
- Unique
- -> Merge Append
- Sort Key: "*SELECT* 1".q1
+ QUERY PLAN
+----------------------------------------------------
+ HashAggregate
+ Group Key: "*SELECT* 1".q1
+ -> Append
-> Subquery Scan on "*SELECT* 1"
- -> Unique
- -> Sort
- Sort Key: i81.q1, i81.q2
- -> Seq Scan on int8_tbl i81
- Filter: (q2 IS NOT NULL)
+ -> HashAggregate
+ Group Key: i81.q1, i81.q2
+ -> Seq Scan on int8_tbl i81
+ Filter: (q2 IS NOT NULL)
-> Subquery Scan on "*SELECT* 2"
- -> Unique
- -> Sort
- Sort Key: i82.q1, i82.q2
- -> Seq Scan on int8_tbl i82
- Filter: (q2 IS NOT NULL)
-(15 rows)
+ -> HashAggregate
+ Group Key: i82.q1, i82.q2
+ -> Seq Scan on int8_tbl i82
+ Filter: (q2 IS NOT NULL)
+(13 rows)
select distinct q1 from
(select distinct * from int8_tbl i81
@@ -1327,24 +1325,22 @@ select distinct q1 from
union all
select distinct * from int8_tbl i82) ss
where -q1 = q2;
- QUERY PLAN
---------------------------------------------------------
- Unique
- -> Merge Append
- Sort Key: "*SELECT* 1".q1
+ QUERY PLAN
+--------------------------------------------------
+ HashAggregate
+ Group Key: "*SELECT* 1".q1
+ -> Append
-> Subquery Scan on "*SELECT* 1"
- -> Unique
- -> Sort
- Sort Key: i81.q1, i81.q2
- -> Seq Scan on int8_tbl i81
- Filter: ((- q1) = q2)
+ -> HashAggregate
+ Group Key: i81.q1, i81.q2
+ -> Seq Scan on int8_tbl i81
+ Filter: ((- q1) = q2)
-> Subquery Scan on "*SELECT* 2"
- -> Unique
- -> Sort
- Sort Key: i82.q1, i82.q2
- -> Seq Scan on int8_tbl i82
- Filter: ((- q1) = q2)
-(15 rows)
+ -> HashAggregate
+ Group Key: i82.q1, i82.q2
+ -> Seq Scan on int8_tbl i82
+ Filter: ((- q1) = q2)
+(13 rows)
select distinct q1 from
(select distinct * from int8_tbl i81
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index f9579af19a..cb6434b096 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -999,6 +999,105 @@ SELECT balk(hundred) FROM tenk1;
ROLLBACK;
+-- GROUP BY optimization by reorder columns
+
+SELECT
+ i AS id,
+ i/2 AS p,
+ format('%60s', i%2) AS v,
+ i/4 AS c,
+ i/8 AS d,
+ (random() * (10000/8))::int as e --the same as d but no correlation with p
+ INTO btg
+FROM
+ generate_series(1, 10000) i;
+
+VACUUM btg;
+ANALYZE btg;
+
+-- GROUP BY optimization by reorder columns by frequency
+
+SET enable_hashagg=off;
+SET max_parallel_workers= 0;
+SET max_parallel_workers_per_gather = 0;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+
+CREATE STATISTICS btg_dep ON d, e, p FROM btg;
+ANALYZE btg;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, d, e;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, e, d;
+
+
+-- GROUP BY optimization by reorder columns by index scan
+
+CREATE INDEX ON btg(p, v);
+SET enable_seqscan=off;
+SET enable_bitmapscan=off;
+VACUUM btg;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d;
+
+EXPLAIN (COSTS off)
+SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v;
+
+DROP TABLE btg;
+
+RESET enable_hashagg;
+RESET max_parallel_workers;
+RESET max_parallel_workers_per_gather;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+
+
-- Secondly test the case of a parallel aggregate combiner function
-- returning NULL. For that use normal transition function, but a
-- combiner function returning NULL.
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 81429164d4..40e5d30f84 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -213,7 +213,7 @@ set parallel_tuple_cost = 0;
set max_parallel_workers_per_gather = 2;
create table t (a int, b int, c int);
-insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i);
+insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i);
create index on t (a);
analyze t;
--
2.29.2
>From 9a43cf0fb74e242f56c9d290c5544743b4b7375d Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.von...@postgresql.org>
Date: Tue, 9 Mar 2021 21:09:14 +0100
Subject: [PATCH 2/2] review
---
src/backend/optimizer/path/costsize.c | 77 ++++++++++++++++++++-------
src/backend/optimizer/path/pathkeys.c | 14 ++++-
2 files changed, 69 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 1639258aaf..f55a4f20e5 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1755,6 +1755,8 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
* is_fake_var
* Workaround for generate_append_tlist() which generates fake Vars with
* varno == 0, that will cause a fail of estimate_num_group() call
+ *
+ * XXX Ummm, why would estimate_num_group fail with this?
*/
static bool
is_fake_var(Expr *expr)
@@ -1828,27 +1830,53 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
* compute_cpu_sort_cost
* compute CPU cost of sort (i.e. in-memory)
*
+ * The main thing we need to calculate to estimate sort CPU costs is the number
+ * of calls to the comparator functions. The difficulty is that for multi-column
+ * sorts there may be different data types involved (for some of which the calls
+ * may be much more expensive). Furthermore, the columns may have very different
+ * number of distinct values - the higher the number, the fewer comparisons will
+ * be needed for the following columns.
+ *
+ * The algoritm is incremental - we add pathkeys one by one, and at each step we
+ * estimate the number of necessary comparisons (based on the number of distinct
+ * groups in the current pathkey prefix and the new pathkey), and the comparison
+ * costs (which is data type specific).
+ *
+ * Estimation of the number of comparisons is based on ideas from two sources:
+ *
+ * 1) "Algorithms" (course), Robert Sedgewick, Kevin Wayne [https://algs4.cs.princeton.edu/home/]
+ *
+ * 2) "Quicksort Is Optimal For Many Equal Keys" (paper), Sebastian Wild,
+ * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017. [https://arxiv.org/abs/1608.04906]
+ *
+ * In term of that paper, let N - number of tuples, Xi - number of tuples with
+ * key Ki, then the estimate of number of comparisons is:
+ *
+ * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi))
+ *
+ * In our case all Xi are the same because now we don't have any estimation of
+ * group sizes, we have only know the estimate of number of groups (distinct
+ * values). In that case, formula becomes:
+ *
+ * N * log(NumberOfGroups)
+ *
+ * For multi-column sorts we need to estimate the number of comparisons for
+ * each individual column - for example with columns (c1, c2, ..., ck) we
+ * can estimate that number of comparions on ck is roughly
+ *
+ * ncomparisons(c1, c2, ..., ck) / ncomparisons(c1, c2, ..., c(k-1))
+ *
+ * Let k be a column number, Gk - number of groups defined by k columns, and Fk
+ * the cost of the comparison is
+ *
+ * N * sum( Fk * log(Gk) )
+ *
+ * Note: We also consider column witdth, not just the comparator cost.
+ *
* NOTE: some callers currently pass NIL for pathkeys because they
* can't conveniently supply the sort keys. In this case, it will fallback to
* simple comparison cost estimate.
- *
- * Estimation algorithm is based on ideas from course Algorithms,
- * Robert Sedgewick, Kevin Wayne, https://algs4.cs.princeton.edu/home/ and paper
- * "Quicksort Is Optimal For Many Equal Keys", Sebastian Wild,
- * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017.
- *
- * In term of that papers, let N - number of tuples, Xi - number of tuples with
- * key Ki, then estimation is:
- * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi))
- * In our case all Xi are the same because now we don't have an estimation of
- * group sizes, we have only estimation of number of groups. In this case,
- * formula becomes: N * log(NumberOfGroups). Next, to support correct estimation
- * of multi-column sort we need separately compute each column, so, let k is a
- * column number, Gk - number of groups defined by k columns:
- * N * sum( Fk * log(Gk) )
- * Fk is a function costs (including width) for k columns.
*/
-
static Cost
compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
Cost comparison_cost, double tuples, double output_tuples,
@@ -1862,7 +1890,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
bool has_fake_var = false;
int i = 0;
Oid prev_datatype = InvalidOid;
- Cost funcCost = 0.;
+ Cost funcCost = 0.0;
List *cache_varinfos = NIL;
/* fallback if pathkeys is unknown */
@@ -1873,6 +1901,10 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
* a total number of tuple comparisons of N log2 K; but the constant
* factor is a bit higher than for quicksort. Tweak it so that the
* cost curve is continuous at the crossover point.
+ *
+ * XXX I suppose the "quicksort factor" references to 1.5 at the end
+ * of this function, but I'm not sure. I suggest we introduce some simple
+ * constants for that, instead of magic values.
*/
output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
@@ -1888,7 +1920,6 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
* - per column comparison function cost
* - we try to compute needed number of comparison per column
*/
-
foreach(lc, pathkeys)
{
PathKey *pathkey = (PathKey*)lfirst(lc);
@@ -1952,6 +1983,11 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
* Don't use DEFAULT_NUM_DISTINCT because it used for only one
* column while here we try to estimate number of groups over
* set of columns.
+ *
+ * XXX Perhaps this should use DEFAULT_NUM_DISTINCT at least to
+ * limit the calculated values, somehow?
+ *
+ * XXX What's the logic of the following formula?
*/
nGroups = ceil(2.0 + sqrt(tuples) *
list_length(pathkeyExprs) / list_length(pathkeys));
@@ -1968,6 +2004,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
{
if (tuplesPerPrevGroup < output_tuples)
/* comparing only inside output_tuples */
+ /* XXX why not to use the same multiplier (1.5)? */
correctedNGroups =
ceil(2.0 * output_tuples / (tuplesPerPrevGroup / nGroups));
else
@@ -1993,7 +2030,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
tuplesPerPrevGroup = ceil(1.5 * tuplesPerPrevGroup / nGroups);
/*
- * We could skip all followed columns for cost estimation, because we
+ * We could skip all following columns for cost estimation, because we
* believe that tuples are unique by set ot previous columns
*/
if (tuplesPerPrevGroup <= 1.0)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 7beb32488a..b092c3e055 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -515,10 +515,19 @@ pathkey_sort_cost_comparator(const void *_a, const void *_b)
return 0;
return 1;
}
+
/*
* Order tail of list of group pathkeys by uniqueness descendetly. It allows to
* speedup sorting. Returns newly allocated lists, old ones stay untouched.
* n_preordered defines a head of list which order should be prevented.
+ *
+ * XXX But we're not generating this only based on uniqueness (that's a bad
+ * term anyway, because we're using ndistinct estimates, not uniqueness).
+ * We're also using the comparator cost to calculate the expected sort cost,
+ * and optimize that.
+ *
+ * XXX This should explain how we generate the values - all permutations for
+ * up to 4 values, etc.
*/
void
get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
@@ -597,8 +606,9 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
else
{
/*
- * Since v13 list_free() can clean list elements so for original list not to be modified it should be copied to
- * a new one which can then be cleaned safely if needed.
+ * Since v13 list_free() can clean list elements so for original list
+ * not to be modified it should be copied to a new one which can then
+ * be cleaned safely if needed.
*/
new_group_pathkeys = list_copy(*group_pathkeys);
nToPermute = nFreeKeys;
--
2.29.2
