Reordering DISTINCT keys to match input path's pathkeys

Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
path's pathkeys, which can help reduce cost by avoiding unnecessary
re-sort, or allowing us to use incremental-sort to save efforts. For
instance,

create table t (a int, b int);
create index on t (a, b);

explain (costs off) select distinct b, a from t limit 10;
QUERY PLAN
--------------------------------------------------
Limit
-> Unique
-> Index Only Scan using t_a_b_idx on t
(3 rows)

Please note that the parser has ensured that the DISTINCT pathkeys
matches the order of ORDER BY clauses. So there is no need to do this
part again.

In principle, we can perform such reordering for DISTINCT ON too, but we
need to make sure that the resulting pathkeys matches initial ORDER BY
keys, which seems not trivial. So it doesn't seem worth the effort.

Attached is a patch for this optimization. Any thoughts?

Thanks
Richard

On Tue, 2024-01-23 at 13:55 +0800, Richard Guo wrote:
> Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
> the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
> path's pathkeys, which can help reduce cost by avoiding unnecessary
> re-sort, or allowing us to use incremental-sort to save efforts.
>
> Attached is a patch for this optimization.  Any thoughts?

I didn't scrutinize the code, but that sounds like a fine optimization.

Yours,
Laurenz Albe

On Tue, 23 Jan 2024 at 18:56, Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
>
> Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
> the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
> path's pathkeys, which can help reduce cost by avoiding unnecessary
> re-sort, or allowing us to use incremental-sort to save efforts. For
> instance,

I've not caught up on the specifics of 0452b461b, but I just wanted to
highlight that there was some work done in [1] in this area. It seems
Ankit didn't ever add that to a CF, so that might explain why it's
been lost.

Anyway, just pointing it out as there may be useful code or discussion
in the corresponding threads.

David

[1] https://postgr.es/m/da9425ae-8ff7-33d9-23b3-2a3eb605e106%40gmail.com

On Tue, Jan 23, 2024 at 5:03 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> I've not caught up on the specifics of 0452b461b, but I just wanted to
> highlight that there was some work done in [1] in this area. It seems
> Ankit didn't ever add that to a CF, so that might explain why it's
> been lost.
>
> Anyway, just pointing it out as there may be useful code or discussion
> in the corresponding threads.

Thanks for pointing it out. I looked at the patch there and noticed
several problems with it.

* That patch is incomplete and does not work as expected. It at least
needs to modify truncate_useless_pathkeys() to account for DISTINCT
clause (I think this has been mentioned in that thread).

* That patch would not consider the origin DISTINCT pathkeys if it could
do some reordering, which is not great and can generate inefficient
plans. For instance (after fixing the first problem)

create table t (a int, b int);
create index on t(a);

set enable_hashagg to off;
set enable_incremental_sort to off;
set enable_seqscan to off;

explain (costs off) select distinct b, a from t order by b, a;
QUERY PLAN
-------------------------------------------------
Sort
Sort Key: b, a
-> Unique
-> Sort
Sort Key: a, b
-> Index Scan using t_a_idx on t
(6 rows)

Using DISTINCT pathkeys {b, a} is more efficient for this plan, because
only one Sort would be required. But that patch is not able to do that,
because it does not consider the origin DISTINCT pathkeys after
reordering.

Thanks
Richard

cfbot reminds that this patch does not apply any more. So I've rebased
it on master, and also adjusted the test cases a bit.

Thanks
Richard

On Mon, Feb 5, 2024 at 11:18 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> cfbot reminds that this patch does not apply any more. So I've rebased
> it on master, and also adjusted the test cases a bit.

This patch does not apply any more, so here is a new rebase, with some
tweaks to the comments.

Thanks
Richard

On 6/7/24 16:46, Richard Guo wrote:
> On Mon, Feb 5, 2024 at 11:18 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
>> cfbot reminds that this patch does not apply any more. So I've rebased
>> it on master, and also adjusted the test cases a bit.
>
> This patch does not apply any more, so here is a new rebase, with some
> tweaks to the comments.
This patch needs a minor rebase again.
After skimming the code, I want to say that it looks good. But maybe to
avoid one more *_reordering GUC - it would be better to cover all path
key reorderings under a single GUC.

--
regards, Andrei Lepikhov

On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
> On 6/7/24 16:46, Richard Guo wrote:
> > This patch does not apply any more, so here is a new rebase, with some
> > tweaks to the comments.

> This patch needs a minor rebase again.
> After skimming the code, I want to say that it looks good. But maybe to
> avoid one more *_reordering GUC - it would be better to cover all path
> key reorderings under a single GUC.

Thanks for reviewing this patch. After some consideration, I think
it's not too complex to also apply this optimization to DISTINCT ON.
The parser already ensures that the DISTINCT ON expressions match the
initial ORDER BY expressions; we just need to ensure that the
resulting pathkey list from the reordering matches the original
distinctClause pathkeys, while leaving the remaining pathkeys
unchanged in order. Please see attached.

I'm not sure about merging these two 'reordering' GUCs into one.
While they may look similar, they apply to very different scenarios.
However, I'm open to other suggestions.

Thanks
Richard

On 11/13/24 13:49, Richard Guo wrote:
> On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
>> On 6/7/24 16:46, Richard Guo wrote:
>>> This patch does not apply any more, so here is a new rebase, with some
>>> tweaks to the comments.
>
>> This patch needs a minor rebase again.
>> After skimming the code, I want to say that it looks good. But maybe to
>> avoid one more *_reordering GUC - it would be better to cover all path
>> key reorderings under a single GUC.
>
> Thanks for reviewing this patch. After some consideration, I think
> it's not too complex to also apply this optimization to DISTINCT ON.
> The parser already ensures that the DISTINCT ON expressions match the
> initial ORDER BY expressions; we just need to ensure that the
> resulting pathkey list from the reordering matches the original
> distinctClause pathkeys, while leaving the remaining pathkeys
> unchanged in order. Please see attached.
Thanks, I'll discover it later.
BTW have you ever thought about one more, cost-based reordering strategy?
For now, we can reorder GROUP-BY and distinct clauses according to two
orderings: 1) ORDER-BY order and 2) order derived from the underlying
query tree.
In thread [1], I try to add one more strategy that minimises the number
of comparison operator calls. It seems that it would work the same way
with the DISTINCT statement. Do you think it make sense in general and
can be a possible direction of improvement for the current patch?

>
> I'm not sure about merging these two 'reordering' GUCs into one.
> While they may look similar, they apply to very different scenarios.
> However, I'm open to other suggestions.
Sure, they enable different optimisations. But, they enable highly
specialised optimisations. Having two GUCs looks too expensive.
Moreover, this stuff is cost-based and should work automatically. So, I
treat these GUCs as mostly debugging or last-chance stuff used to
disable features during severe slowdowns or bugs. It might make sense to
group them into a single 'Clause Reordering' parameter.

[1]
https://www.postgresql.org/message-id/flat/8742aaa8-9519-4a1f-91bd-364aec65f5cf%40gmail.com

--
regards, Andrei Lepikhov

On Wed, Nov 13, 2024 at 7:36 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
> On 11/13/24 13:49, Richard Guo wrote:
> > Thanks for reviewing this patch. After some consideration, I think
> > it's not too complex to also apply this optimization to DISTINCT ON.
> > The parser already ensures that the DISTINCT ON expressions match the
> > initial ORDER BY expressions; we just need to ensure that the
> > resulting pathkey list from the reordering matches the original
> > distinctClause pathkeys, while leaving the remaining pathkeys
> > unchanged in order. Please see attached.

> BTW have you ever thought about one more, cost-based reordering strategy?
> For now, we can reorder GROUP-BY and distinct clauses according to two
> orderings: 1) ORDER-BY order and 2) order derived from the underlying
> query tree.
> In thread [1], I try to add one more strategy that minimises the number
> of comparison operator calls. It seems that it would work the same way
> with the DISTINCT statement. Do you think it make sense in general and
> can be a possible direction of improvement for the current patch?

I haven’t had a chance to follow that thread. From a quick look at
that patch, it seems to improve the general costing logic for sorting.
If that’s the case, I think it would be beneficial in the areas where
we use cost_sort(), including in this patch.

> > I'm not sure about merging these two 'reordering' GUCs into one.
> > While they may look similar, they apply to very different scenarios.
> > However, I'm open to other suggestions.
> Sure, they enable different optimisations. But, they enable highly
> specialised optimisations. Having two GUCs looks too expensive.
> Moreover, this stuff is cost-based and should work automatically. So, I
> treat these GUCs as mostly debugging or last-chance stuff used to
> disable features during severe slowdowns or bugs. It might make sense to
> group them into a single 'Clause Reordering' parameter.

I don't want to argue too much about this, but the two types of
optimizations are quite different in terms of implementation details.
For example, with DISTINCT ON, one key requirement is ensuring that
the resulting pathkey list matches the original distinctClause
pathkeys, and this logic doesn’t exist in the GROUP BY reordering
code. If these GUCs are mainly for debugging, I think it's better to
keep them separate so that we can debug each optimization individually.

Thanks
Richard

On 11/14/24 08:09, Richard Guo wrote:
> On Wed, Nov 13, 2024 at 7:36 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
>> On 11/13/24 13:49, Richard Guo wrote:
>> In thread [1], I try to add one more strategy that minimises the number
>> of comparison operator calls. It seems that it would work the same way
>> with the DISTINCT statement. Do you think it make sense in general and
>> can be a possible direction of improvement for the current patch?
>
> I haven’t had a chance to follow that thread. From a quick look at
> that patch, it seems to improve the general costing logic for sorting.
> If that’s the case, I think it would be beneficial in the areas where
> we use cost_sort(), including in this patch.
Yes, the core of the discussion is cost calculation. It is a base for
the final patch that adds a grouping strategy, according to which it may
be profitable to put the column with max distinct value at the first
position to make sorting less expensive. I think it makes sense to do
the same in this DISTINCT feature, too (as a further improvement, of
course).

>> disable features during severe slowdowns or bugs. It might make sense to
>> group them into a single 'Clause Reordering' parameter.
> code. If these GUCs are mainly for debugging, I think it's better to
> keep them separate so that we can debug each optimization individually.
Ok.
See minor changes I propose in the attachment.

--
regards, Andrei Lepikhov

On 11/13/24 13:49, Richard Guo wrote:
> On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
>> On 6/7/24 16:46, Richard Guo wrote:
> I'm not sure about merging these two 'reordering' GUCs into one.
> While they may look similar, they apply to very different scenarios.
> However, I'm open to other suggestions.
I finally have passed through the code. It generally looks OK. Let me
only write a few words on tests.
I wonder if it would be possible to print only three rows instead of 10
to prove the DISTINCT's correctness.
Also, to stabilise tests with parallel workers, I would recommend
setting max_parallel_workers_per_gather into 1 and enabling
debug_parallel_query.

--
regards, Andrei Lepikhov

On Fri, Nov 22, 2024 at 5:40 PM Andrei Lepikhov <lepihov(at)gmail(dot)com> wrote:
> I wonder if it would be possible to print only three rows instead of 10
> to prove the DISTINCT's correctness.

There are ten distinct values in the 'distinct_tbl' test table, so
I think it’d better to print all of them to verify correctness.

> Also, to stabilise tests with parallel workers, I would recommend
> setting max_parallel_workers_per_gather into 1 and enabling
> debug_parallel_query.

Since we're testing sort-based DISTINCT, the results will always be
well-ordered, so they should be pretty stable as is.

I've applied some of the changes you suggested in your previous email
and pushed the updated patch. Thank you for your review.

Thanks
Richard

On Tue, Nov 26, 2024 at 9:43 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> I've applied some of the changes you suggested in your previous email
> and pushed the updated patch. Thank you for your review.

Ah, the buildfarm is complaining. I shouldn't create tables with the
same name in two test files. Fixing ...

Thanks
Richard

Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> I've applied some of the changes you suggested in your previous email
> and pushed the updated patch. Thank you for your review.

The buildfarm's not too happy. It looks like this patch decided
to use the name "distinct_tbl" in a test script that runs in
parallel with another one already using "distinct_tbl".

regards, tom lane

On Tue, Nov 26, 2024 at 10:12 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> > I've applied some of the changes you suggested in your previous email
> > and pushed the updated patch. Thank you for your review.
>
> The buildfarm's not too happy. It looks like this patch decided
> to use the name "distinct_tbl" in a test script that runs in
> parallel with another one already using "distinct_tbl".

Exactly. I shouldn't create tables with the same name in two test
files. Will push a fix shortly.

Thanks
Richard

On Tue, Nov 26, 2024 at 10:22 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> On Tue, Nov 26, 2024 at 10:12 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> > > I've applied some of the changes you suggested in your previous email
> > > and pushed the updated patch. Thank you for your review.

> > The buildfarm's not too happy. It looks like this patch decided
> > to use the name "distinct_tbl" in a test script that runs in
> > parallel with another one already using "distinct_tbl".

> Exactly. I shouldn't create tables with the same name in two test
> files. Will push a fix shortly.

Fixed.

Thanks
Richard