[PATCH] Teach planner to further optimize sort in distinct

Hi, this is extension of `teach planner to evaluate multiple windows in
the optimal order` work applied to distinct operation.

Based on discussions before
(https://www.postgresql.org/message-id/flat/CAApHDvr7rSCVXzGfVa1L9pLpkKj6-s8NynK8o%2B98X9sKjejnQQ%40mail.gmail.com#e01327a3053d9281c40f281ef7105b42)
,

> All I imagine you need to do for it
> is to invent a function in pathkeys.c which is along the lines of what
> pathkeys_count_contained_in() does, but returns a List of pathkeys
> which are in keys1 but not in keys2 and NIL if keys2 has a pathkey
> that does not exist as a pathkey in keys1. In
> create_final_distinct_paths(), you can then perform an incremental
> sort on any input_path which has a non-empty return list and in
> create_incremental_sort_path(), you'll pass presorted_keys as the
> number of pathkeys in the path, and the required pathkeys the
> input_path->pathkeys + the pathkeys returned from the new function.

There is bit confusion in wording here:

"returns a List of pathkeys
which are in keys1 but not in keys2 and NIL if keys2 has a pathkey
that does not exist as a pathkey in keys1."

You mean extract common keys without ordering right?

Example: keys1 = (a,b,c), keys2 = (b,a)

returns (a,b)

and

keys1 = (a,b,c), keys = (d)

returns = ()

which translates to

needed_pathkeys = (a,b,c) = key2

input_pathkeys = (b,a) key1

returns (b,a) = common_keys

new needed_pathkeys = unique(common_keys + old needed_pathkeys)

=> new needed_pathkeys = (b,a,c)

The new needed_pathkeys matches input_pathkeys.

This is what I implemented in the patch.

The patched version yields the following plans:

set enable_hashagg=0;
set enable_seqscan=0;

explain (costs off) select distinct relname,relkind,count(*) over
(partition by
relkind) from pg_Class;
                       QUERY PLAN
---------------------------------------------------------
 Unique
   ->  Incremental Sort
         Sort Key: relkind, relname, (count(*) OVER (?))
         Presorted Key: relkind
         ->  WindowAgg
               ->  Sort
                     Sort Key: relkind
                     ->  Seq Scan on pg_class
(8 rows)

explain (costs off) select distinct a, b, count(*) over (partition by b,
a) from abcd;
                       QUERY PLAN
--------------------------------------------------------
 Unique
   ->  Incremental Sort
         Sort Key: b, a, (count(*) OVER (?))
         Presorted Key: b, a
         ->  WindowAgg
               ->  Incremental Sort
                     Sort Key: b, a
                     Presorted Key: b
                     ->  Index Scan using b_idx on abcd
(9 rows)

explain (costs off) select distinct a, b, count(*) over (partition by c,
d) from abcd;
                       QUERY PLAN
--------------------------------------------------------
 Unique
   ->  Sort
         Sort Key: a, b, (count(*) OVER (?))
         ->  WindowAgg
               ->  Incremental Sort
                     Sort Key: c, d
                     Presorted Key: c
                     ->  Index Scan using c_idx on abcd
(8 rows)

Issue with index path still remains as pathkeys get purged by
truncate_useless_pathkeys

and hence are not available in create_final_distinct_paths for the above
optimizations.

I have attached a patch for the reference.

Thanks,

Ankit