Re: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places

On Sat, 10 Oct 2020 at 15:45, Hou, Zhijie <houzj(dot)fnst(at)cn(dot)fujitsu(dot)com> wrote:
> I found some code places call list_delete_ptr can be replaced by list_delete_xxxcell which can be faster.
>
> diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
> index db54a6b..61ef7c8 100644
> --- a/src/backend/optimizer/path/joinpath.c
> +++ b/src/backend/optimizer/path/joinpath.c
> @@ -1005,8 +1005,8 @@ sort_inner_and_outer(PlannerInfo *root,
> /* Make a pathkey list with this guy first */
> if (l != list_head(all_pathkeys))
> outerkeys = lcons(front_pathkey,
> - list_delete_ptr(list_copy(all_pathkeys),
> - front_pathkey));
> + list_delete_nth_cell(list_copy(all_pathkeys),
> + foreach_current_index(l)));
> else
> outerkeys = all_pathkeys; /* no work at first one... */

That looks ok to me. It would be more optimal if we had a method to
move an element to the front of a list, or to any specified position,
but I can't imagine it's worth making such a function just for that.
So what you have there seems fine.

> diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c
> index fe777c3..d0f15b8 100644
> --- a/src/backend/rewrite/rewriteHandler.c
> +++ b/src/backend/rewrite/rewriteHandler.c
> @@ -650,7 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, int rt_index)
> if (IsA(rtr, RangeTblRef) &&
> rtr->rtindex == rt_index)
> {
> - newjointree = list_delete_ptr(newjointree, rtr);
> + newjointree = list_delete_cell(newjointree, l);

I think you may as well just use newjointree =
foreach_delete_current(newjointree, l);. The comment about why the
list_delete is ok inside a foreach is then irrelevant since
foreach_delete_current() is designed for deleting the current foreach
cell.

Looking around for other places I found two more in equivclass.c.
These two do require an additional moving part to keep track of the
index we want to delete, so they're not quite as clear cut a win to
do. However, I don't think tracking the index makes the code overly
complex, so I'm thinking they're both fine to do. Does anyone think
differently?

Updated patch attached.

David