Re: Introduce list_reverse() to make lcons() usage less inefficient

Hi,

On 2023-02-17 11:36:40 +1300, David Rowley wrote:
> While working on [1] to make improvements in the query planner around
> the speed to find EquivalenceMembers in an EquivalenceClass, because
> that patch does have a large impact in terms of performance
> improvements, some performance tests with that patch started to
> highlight some other places that bottleneck the planner's performance.
>
> 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.

> One way we could solve that is to just lappend() the new item and then
> just reverse the order of the list only when we need to.

That's not generally the same as lcons() ing, but I guess it's fine here,
because we build the lists from scratch, so the reversing actually yields the
correct result.

But wouldn't an even cheaper way here be to iterate over the children in
reverse order when match_partition_order_desc? We can do that efficiently
now. Looks like we don't have a readymade helper for it, but it'd be easy
enough to add or open code.

Greetings,

Andres Freund