Обсуждение: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places

Hi

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... */

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);


Best regards,
houzj

The following review has been posted through the commitfest application:
make installcheck-world:  tested, passed
Implements feature:       not tested
Spec compliant:           not tested
Documentation:            not tested

Patch applies cleanly on master & 13 and installcheck-world runs on 13 & master. Seem to follow the new style of using
morethe expressive macro's for the list interface, so looks good to me. 

The new status of this patch is: Ready for Committer

On Sat, 10 Oct 2020 at 15:45, Hou, Zhijie <houzj.fnst@cn.fujitsu.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

> > 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.
> 
Thanks for reviewing the patch!
And after checking the code again and I found two more places which can be improved.

1.
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -1702,7 +1702,7 @@ transformMultiAssignRef(ParseState *pstate, MultiAssignRef *maref)
          */
         if (maref->colno == maref->ncolumns)
             pstate->p_multiassign_exprs =
-                list_delete_ptr(pstate->p_multiassign_exprs, tle);
+                list_delete_last(pstate->p_multiassign_exprs);

Based on the logic above in function transformMultiAssignRef,
I found 'tle' is always the last one in list ' pstate->p_multiassign_exprs ' ,
So list_delete_last seems can be used here.


2.

+            nameEl_idx = foreach_current_index(option);
         }
     }
 
@@ -405,7 +407,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column,
         }
         sname = rv->relname;
         /* Remove the SEQUENCE NAME item from seqoptions */
-        seqoptions = list_delete_ptr(seqoptions, nameEl);
+        seqoptions = list_delete_nth_cell(seqoptions, nameEl_idx);

Add a new var ' nameEl_idx ' to catch the index.

Best regards,
houzj

On Fri, 16 Oct 2020 at 16:42, Hou, Zhijie <houzj.fnst@cn.fujitsu.com> wrote:
> And after checking the code again and I found two more places which can be improved.
>
> 1.
> --- a/src/backend/parser/parse_expr.c
> +++ b/src/backend/parser/parse_expr.c
> @@ -1702,7 +1702,7 @@ transformMultiAssignRef(ParseState *pstate, MultiAssignRef *maref)
>                  */
>                 if (maref->colno == maref->ncolumns)
>                         pstate->p_multiassign_exprs =
> -                               list_delete_ptr(pstate->p_multiassign_exprs, tle);
> +                               list_delete_last(pstate->p_multiassign_exprs);
>
> Based on the logic above in function transformMultiAssignRef,
> I found 'tle' is always the last one in list ' pstate->p_multiassign_exprs ' ,
> So list_delete_last seems can be used here.


Yeah. After a bit of looking I agree.  There's a similar assumption
there already with:

/*
* Second or later column in a multiassignment.  Re-fetch the
* transformed SubLink or RowExpr, which we assume is still the last
* entry in p_multiassign_exprs.
*/
Assert(pstate->p_multiassign_exprs != NIL);
tle = (TargetEntry *) llast(pstate->p_multiassign_exprs);

> 2.
>
> +                       nameEl_idx = foreach_current_index(option);
>                 }
>         }
>
> @@ -405,7 +407,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column,
>                 }
>                 sname = rv->relname;
>                 /* Remove the SEQUENCE NAME item from seqoptions */
> -               seqoptions = list_delete_ptr(seqoptions, nameEl);
> +               seqoptions = list_delete_nth_cell(seqoptions, nameEl_idx);
>
> Add a new var ' nameEl_idx ' to catch the index.

Yeah. That looks fine too.

Pushed.

David