Re: Introduce list_reverse() to make lcons() usage less inefficient - Mailing list pgsql-hackers

From Tom Lane
Subject Re: Introduce list_reverse() to make lcons() usage less inefficient
Date
Msg-id 2449787.1676600375@sss.pgh.pa.us
Whole thread Raw
In response to Re: Introduce list_reverse() to make lcons() usage less inefficient  (Andres Freund <andres@anarazel.de>)
List pgsql-hackers
Andres Freund <andres@anarazel.de> writes:
> On 2023-02-17 11:36:40 +1300, David Rowley wrote:
>> One of those places is in generate_orderedappend_paths() when we find
>> that the required sort order is the same as the reverse of the
>> partition order.  In this case, we build a list of paths for each
>> partition using the lcons() function. Since Lists are now arrays in
>> PostgreSQL, lcons() isn't as efficient as it once was and it must
>> memmove the entire existing contents of the list up one element to
>> make way to prepend the new element. This is effectively quadratic and
>> becomes noticeable with a large number of partitions.

> I have wondered before if we eventually ought to switch to embedded lists for
> some planner structures, including paths. add_path() inserts/deletes at points
> in the middle of the list, which isn't great.

I'm not hugely excited about that, because it presumes that paths appear
in only one list, which isn't true.  We could perhaps privilege
RelOptInfo.pathlist over other cases, but that'd be asymmetrical and
probably bug-inducing.

            regards, tom lane



pgsql-hackers by date:

Previous
From: Andres Freund
Date:
Subject: Re: Make set_ps_display faster and easier to use
Next
From: Thomas Munro
Date:
Subject: Re: Dead code in ps_status.c