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
Attachments:
0001-Use-list_delete_xxxcell-instead-of-list_delete_ptr.patchapplication/octet-stream; name=0001-Use-list_delete_xxxcell-instead-of-list_delete_ptr.patchDownload
From 5935a26ffaefde5876d226d6d582491724c4433e Mon Sep 17 00:00:00 2001
From: root <root@localhost.localdomain>
Date: Fri, 9 Oct 2020 22:04:24 -0400
Subject: [PATCH] Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N)
---
src/backend/optimizer/path/joinpath.c | 4 ++--
src/backend/rewrite/rewriteHandler.c | 2 +-
2 files changed, 3 insertions(+), 3 deletions(-)
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);
/*
* foreach is safe because we exit loop after list_delete...
--
1.8.3.1
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 more the 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
Attachments:
optimize_a_few_list_delete_ptr_calls.patchtext/plain; charset=US-ASCII; name=optimize_a_few_list_delete_ptr_calls.patchDownload
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 823422edad..690b753369 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -137,6 +137,7 @@ process_equivalence(PlannerInfo *root,
EquivalenceMember *em1,
*em2;
ListCell *lc1;
+ int ec2_idx;
/* Should not already be marked as having generated an eclass */
Assert(restrictinfo->left_ec == NULL);
@@ -258,6 +259,7 @@ process_equivalence(PlannerInfo *root,
*/
ec1 = ec2 = NULL;
em1 = em2 = NULL;
+ ec2_idx = -1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
@@ -311,6 +313,7 @@ process_equivalence(PlannerInfo *root,
equal(item2, cur_em->em_expr))
{
ec2 = cur_ec;
+ ec2_idx = foreach_current_index(lc1);
em2 = cur_em;
if (ec1)
break;
@@ -371,7 +374,7 @@ process_equivalence(PlannerInfo *root,
ec1->ec_max_security = Max(ec1->ec_max_security,
ec2->ec_max_security);
ec2->ec_merged = ec1;
- root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
+ root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
ec2->ec_sources = NIL;
@@ -1964,6 +1967,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
bool matchleft;
bool matchright;
ListCell *lc2;
+ int coal_idx = -1;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2008,6 +2012,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
if (equal(leftvar, cfirst) && equal(rightvar, csecond))
{
+ coal_idx = foreach_current_index(lc2);
match = true;
break;
}
@@ -2072,7 +2077,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
*/
if (matchleft && matchright)
{
- cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
+ cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
return true;
}
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index db54a6ba2e..4a35903b29 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 fe777c3103..1faaafab08 100644
--- a/src/backend/rewrite/rewriteHandler.c
+++ b/src/backend/rewrite/rewriteHandler.c
@@ -650,11 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, int rt_index)
if (IsA(rtr, RangeTblRef) &&
rtr->rtindex == rt_index)
{
- newjointree = list_delete_ptr(newjointree, rtr);
-
- /*
- * foreach is safe because we exit loop after list_delete...
- */
+ newjointree = foreach_delete_current(newjointree, l);
break;
}
}
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 atfirst 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
Attachments:
0001-optimize-a-few-list_delete_ptr-calls.patchapplication/octet-stream; name=0001-optimize-a-few-list_delete_ptr-calls.patchDownload
From 2ed7c58eec2f27018023c6a7d6cbdd4cd31333be Mon Sep 17 00:00:00 2001
From: root <root@localhost.localdomain>
Date: Thu, 15 Oct 2020 23:40:10 -0400
Subject: [PATCH] optimize a few list_delete_ptr calls
---
src/backend/optimizer/path/equivclass.c | 9 +++++++--
src/backend/optimizer/path/joinpath.c | 4 ++--
src/backend/parser/parse_expr.c | 2 +-
src/backend/parser/parse_utilcmd.c | 4 +++-
src/backend/rewrite/rewriteHandler.c | 6 +-----
5 files changed, 14 insertions(+), 11 deletions(-)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b68a5a0..3ec84a0 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -137,6 +137,7 @@ process_equivalence(PlannerInfo *root,
EquivalenceMember *em1,
*em2;
ListCell *lc1;
+ int ec2_idx;
/* Should not already be marked as having generated an eclass */
Assert(restrictinfo->left_ec == NULL);
@@ -258,6 +259,7 @@ process_equivalence(PlannerInfo *root,
*/
ec1 = ec2 = NULL;
em1 = em2 = NULL;
+ ec2_idx = -1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
@@ -311,6 +313,7 @@ process_equivalence(PlannerInfo *root,
equal(item2, cur_em->em_expr))
{
ec2 = cur_ec;
+ ec2_idx = foreach_current_index(lc1);
em2 = cur_em;
if (ec1)
break;
@@ -371,7 +374,7 @@ process_equivalence(PlannerInfo *root,
ec1->ec_max_security = Max(ec1->ec_max_security,
ec2->ec_max_security);
ec2->ec_merged = ec1;
- root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
+ root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
ec2->ec_sources = NIL;
@@ -1964,6 +1967,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
bool matchleft;
bool matchright;
ListCell *lc2;
+ int coal_idx = -1;
/* Ignore EC unless it contains pseudoconstants */
if (!cur_ec->ec_has_const)
@@ -2008,6 +2012,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
if (equal(leftvar, cfirst) && equal(rightvar, csecond))
{
+ coal_idx = foreach_current_index(lc2);
match = true;
break;
}
@@ -2072,7 +2077,7 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
*/
if (matchleft && matchright)
{
- cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
+ cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx);
return true;
}
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index db54a6b..4a35903 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/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index d24420c..030fd73 100644
--- 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);
return result;
}
diff --git a/src/backend/parser/parse_utilcmd.c b/src/backend/parser/parse_utilcmd.c
index ec94437..91ba2cd 100644
--- a/src/backend/parser/parse_utilcmd.c
+++ b/src/backend/parser/parse_utilcmd.c
@@ -360,6 +360,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column,
CreateSeqStmt *seqstmt;
AlterSeqStmt *altseqstmt;
List *attnamelist;
+ int nameEl_idx = -1;
/*
* Determine namespace and name to use for the sequence.
@@ -386,6 +387,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column,
(errcode(ERRCODE_SYNTAX_ERROR),
errmsg("conflicting or redundant options")));
nameEl = defel;
+ 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);
}
else
{
diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c
index fe777c3..1faaafa 100644
--- a/src/backend/rewrite/rewriteHandler.c
+++ b/src/backend/rewrite/rewriteHandler.c
@@ -650,11 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, int rt_index)
if (IsA(rtr, RangeTblRef) &&
rtr->rtindex == rt_index)
{
- newjointree = list_delete_ptr(newjointree, rtr);
-
- /*
- * foreach is safe because we exit loop after list_delete...
- */
+ newjointree = foreach_delete_current(newjointree, l);
break;
}
}
--
1.8.3.1
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