Why don't we consider explicit Incremental Sort?

From: Richard Guo <guofenglinux(at)gmail(dot)com>
To: PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Why don't we consider explicit Incremental Sort?
Date: 2024-09-09 09:39:24
Message-ID: CAMbWs49x425QrX7h=Ux05WEnt8GS757H-jOP3_xsX5t1FoUsZw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

While looking at label_sort_with_costsize() due to another issue, I
noticed that we build explicit Sort nodes but not explicit Incremental
Sort nodes. I wonder why this is the case. It seems to me that
Incremental Sorts are preferable in some cases. For example:

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

set enable_seqscan to off;

explain (costs off)
select * from t t1 join t t2 on t1.a = t2.a and t1.b = t2.b;
QUERY PLAN
-------------------------------------------------
Merge Join
Merge Cond: ((t1.a = t2.a) AND (t1.b = t2.b))
-> Sort
Sort Key: t1.a, t1.b
-> Index Scan using t_a_idx on t t1
-> Sort
Sort Key: t2.a, t2.b
-> Index Scan using t_a_idx on t t2
(8 rows)

For the outer path of a mergejoin, I think we can leverage Incremental
Sort to save effort. For the inner path, though, we cannot do this
because Incremental Sort does not support mark/restore.

It could be argued that what if a mergejoin with an Incremental Sort
as the outer path is selected as the inner path of another mergejoin?
Well, I don't think this is a problem, because mergejoin itself does
not support mark/restore either, and we will add a Material node on
top of it anyway in this case (see final_cost_mergejoin).

label_sort_with_costsize is also called in create_append_plan,
create_merge_append_plan and create_unique_plan. In these cases, we
may also consider using Incremental Sort. But I haven't looked into
these cases.

Any thoughts?

Thanks
Richard

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Nisha Moond 2024-09-09 09:45:22 Re: Conflict Detection and Resolution
Previous Message Shubham Khanna 2024-09-09 09:38:19 Re: Pgoutput not capturing the generated columns