Horton

Re: POC: GROUP BY optimization

jian he <jian.universality@gmail.com>

View thread
From: jian he <jian.universality@gmail.com>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Andrei Lepikhov <a.lepikhov@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>, Richard Guo <guofenglinux@gmail.com>, Pavel Borisov <pashkin.elfe@gmail.com>, vignesh C <vignesh21@gmail.com>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>, Tomas Vondra <tomas.vondra@enterprisedb.com>, Teodor Sigaev <teodor@sigaev.ru>, David Rowley <dgrowleyml@gmail.com>, "a.rybakina" <a.rybakina@postgrespro.ru>
Date: 2024-04-29T02:50:00Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Restore preprocess_groupclause()

  2. Rename PathKeyInfo to GroupByOrdering

  3. Add invariants check to get_useful_group_keys_orderings()

  4. Fix asymmetry in setting EquivalenceClass.ec_sortref

  5. Multiple revisions to the GROUP BY reordering tests

  6. Get rid of pg_class usage in SJE regression tests

  7. Rename index "abc" in aggregates.sql

  8. Explore alternative orderings of group-by pathkeys during optimization.

  9. Generalize the common code of adding sort before processing of grouping

  10. Fix out-dated comment in preprocess_groupclause()

  11. Force parallelism in partition_aggregate

  12. Optimize order of GROUP BY keys

On Wed, Apr 24, 2024 at 2:25 PM jian he <jian.universality@gmail.com> wrote:
>
> hi.
> I found an interesting case.
>
> CREATE TABLE t1 AS
>   SELECT (i % 10)::numeric AS x,(i % 10)::int8 AS y,'abc' || i % 10 AS
> z, i::int4 AS w
>   FROM generate_series(1, 100) AS i;
> CREATE INDEX t1_x_y_idx ON t1 (x, y);
> ANALYZE t1;
> SET enable_hashagg = off;
> SET enable_seqscan = off;
>
> EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,y,w;
> EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,w,y,z;
> EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,w,y;
> EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,w,z,y;
> the above part will use:
>   ->  Incremental Sort
>          Sort Key: x, $, $, $
>          Presorted Key: x
>          ->  Index Scan using t1_x_y_idx on t1

We can make these cases also `Presorted Key: x, y`.

in
`if (path->pathkeys && !pathkeys_contained_in(path->pathkeys,
root->group_pathkeys))` branch
we can simple do
-                       infos = lappend(infos, info);
+                       infos = lcons(info, infos);

similar to what we did at plancat.c (search lcons).

get_useful_group_keys_orderings returns a  list of PathKeyInfo,
then the caller function just iterates each element.
so for the caller, order of the returned list element from
get_useful_group_keys_orderings
does not matter.

for path Incremental Sort:
function make_ordered_path will return the same cost for different
numbers of  presorted keys.

for example:
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,y,w;
make_ordered_path cost is same for:
`info->pathkeys: x,y,z,w`
`info->pathkeys:x,z,y,w`

if we arrange `info->pathkeys: x,y,z,w` before `info->pathkeys:x,z,y,w`
in get_useful_group_keys_orderings.
then with the same cost, we will choose the first one
(`info->pathkeys: x,y,z,w`),
if we use IncrementalSort, then we use `Presorted Key: x, y`.