I wrote:
> * Look at places using lcons/list_delete_first to maintain FIFO lists.
> The patch makes these O(N^2) for long lists. If we can reverse the list
> order and use lappend/list_truncate instead, it'd be better. Possibly in
> some places the list ordering is critical enough to make this impractical,
> but I suspect it's an easy win in most.
Attached are two patches that touch all the places where it seemed like
an easy win to stop using lcons and/or list_delete_first.
0001 adds list_delete_last() as a mirror image to list_delete_first(),
and changes all the places where it seemed 100% safe to do so (ie,
there's no behavioral change because the list order is demonstrably
immaterial).
0002 changes some additional places where it's maybe a bit less safe,
ie there's a potential for user-visible behavioral change because
processing will occur in a different order. In particular, the proposed
change in execExpr.c causes aggregates and window functions that are in
the same plan node to be executed in a different order than before ---
but it seems to me that this order is saner. (Note the change in the
expected regression results, in a test that's intentionally sensitive to
the execution order.) And anyway when did we guarantee anything about
that?
I refrained from changing lcons to lappend in get_relation_info, because
that demonstrably causes the planner to change its choices when two
indexes look equally attractive, and probably people would complain
about that. I think that the other changes proposed in 0002 are pretty
harmless --- for example, in get_tables_to_cluster the order depends
initially on the results of a seqscan of pg_index, so anybody who's
expecting stability is in for rude surprises anyhow. Also, the proposed
changes in plancat.c, parse_agg.c, selfuncs.c almost certainly have no
user-visible effect, but maybe there could be changes at the
roundoff-error level due to processing estimates in a different order?
There are a bunch of places that are using list_delete_first to remove
the next-to-process entry from a List used as a queue. In principle,
we could invert the order of those queues and then use list_delete_last,
but I thought this would probably be too confusing: it's natural to
think of the front of the list as being the head of the queue. I doubt
that any of those queues get long enough for it to be a serious
performance problem to leave them as-is.
(Actually, I doubt that any of these changes will really move the
performance needle in the real world. It's more a case of wanting
the code to present good examples not bad ones.)
Thoughts? Anybody want to object to any of the changes in 0002?
regards, tom lane
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index dfb51f6..169bf6f 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1323,8 +1323,6 @@ static void
gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
{
- ListCell *lc;
- List *reversed;
GISTPageSplitInfo *right;
GISTPageSplitInfo *left;
IndexTuple tuples[2];
@@ -1339,14 +1337,6 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
* left. Finally insert the downlink for the last new page and update the
* downlink for the original page as one operation.
*/
-
- /* for convenience, create a copy of the list in reverse order */
- reversed = NIL;
- foreach(lc, splitinfo)
- {
- reversed = lcons(lfirst(lc), reversed);
- }
-
LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
gistFindCorrectParent(state->r, stack);
@@ -1354,10 +1344,10 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
* insert downlinks for the siblings from right to left, until there are
* only two siblings left.
*/
- while (list_length(reversed) > 2)
+ for (int pos = list_length(splitinfo) - 1; pos > 1; pos--)
{
- right = (GISTPageSplitInfo *) linitial(reversed);
- left = (GISTPageSplitInfo *) lsecond(reversed);
+ right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
+ left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
if (gistinserttuples(state, stack->parent, giststate,
&right->downlink, 1,
@@ -1371,11 +1361,10 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
gistFindCorrectParent(state->r, stack);
}
/* gistinserttuples() released the lock on right->buf. */
- reversed = list_delete_first(reversed);
}
- right = (GISTPageSplitInfo *) linitial(reversed);
- left = (GISTPageSplitInfo *) lsecond(reversed);
+ right = (GISTPageSplitInfo *) lsecond(splitinfo);
+ left = (GISTPageSplitInfo *) linitial(splitinfo);
/*
* Finally insert downlink for the remaining right page and update the
diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index 6c3ff76..032fab9 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -633,7 +633,7 @@ CheckAttributeType(const char *attname,
errmsg("composite type %s cannot be made a member of itself",
format_type_be(atttypid))));
- containing_rowtypes = lcons_oid(atttypid, containing_rowtypes);
+ containing_rowtypes = lappend_oid(containing_rowtypes, atttypid);
relation = relation_open(get_typ_typrelid(atttypid), AccessShareLock);
@@ -653,7 +653,7 @@ CheckAttributeType(const char *attname,
relation_close(relation, AccessShareLock);
- containing_rowtypes = list_delete_first(containing_rowtypes);
+ containing_rowtypes = list_delete_last(containing_rowtypes);
}
else if (OidIsValid((att_typelem = get_element_type(atttypid))))
{
diff --git a/src/backend/commands/lockcmds.c b/src/backend/commands/lockcmds.c
index 417d595..bae3b38 100644
--- a/src/backend/commands/lockcmds.c
+++ b/src/backend/commands/lockcmds.c
@@ -281,11 +281,11 @@ LockViewRecurse(Oid reloid, LOCKMODE lockmode, bool nowait, List *ancestor_views
context.nowait = nowait;
context.viewowner = view->rd_rel->relowner;
context.viewoid = reloid;
- context.ancestor_views = lcons_oid(reloid, ancestor_views);
+ context.ancestor_views = lappend_oid(ancestor_views, reloid);
LockViewRecurse_walker((Node *) viewquery, &context);
- ancestor_views = list_delete_oid(ancestor_views, reloid);
+ (void) list_delete_last(context.ancestor_views);
table_close(view, NoLock);
}
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 0c0ddd5..fc1c4df 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -14480,6 +14480,11 @@ register_on_commit_action(Oid relid, OnCommitAction action)
oc->creating_subid = GetCurrentSubTransactionId();
oc->deleting_subid = InvalidSubTransactionId;
+ /*
+ * We use lcons() here so that ON COMMIT actions are processed in reverse
+ * order of registration. That might not be essential but it seems
+ * reasonable.
+ */
on_commits = lcons(oc, on_commits);
MemoryContextSwitchTo(oldcxt);
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 5584fa8..9163464 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -827,6 +827,30 @@ list_delete_first(List *list)
}
/*
+ * Delete the last element of the list.
+ *
+ * This is the opposite of list_delete_first(), but is noticeably cheaper
+ * with a long list, since no data need be moved.
+ */
+List *
+list_delete_last(List *list)
+{
+ check_list_invariants(list);
+
+ if (list == NIL)
+ return NIL; /* would an error be better? */
+
+ /* list_truncate won't free list if it goes to empty, but this should */
+ if (list_length(list) <= 1)
+ {
+ list_free(list);
+ return NIL;
+ }
+
+ return list_truncate(list, list_length(list) - 1);
+}
+
+/*
* Generate the union of two lists. This is calculated by copying
* list1 via list_copy(), then adding to it all the members of list2
* that aren't already in list1.
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index f0e789f..99dbf8d 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -881,11 +881,9 @@ is_parallel_safe(PlannerInfo *root, Node *node)
foreach(l, proot->init_plans)
{
SubPlan *initsubplan = (SubPlan *) lfirst(l);
- ListCell *l2;
- foreach(l2, initsubplan->setParam)
- context.safe_param_ids = lcons_int(lfirst_int(l2),
- context.safe_param_ids);
+ context.safe_param_ids = list_concat(context.safe_param_ids,
+ initsubplan->setParam);
}
}
@@ -1015,6 +1013,7 @@ max_parallel_hazard_walker(Node *node, max_parallel_hazard_context *context)
context->safe_param_ids);
if (max_parallel_hazard_walker(subplan->testexpr, context))
return true; /* no need to restore safe_param_ids */
+ list_free(context->safe_param_ids);
context->safe_param_ids = save_safe_param_ids;
/* we must also check args, but no special Param treatment there */
if (max_parallel_hazard_walker((Node *) subplan->args, context))
@@ -4185,8 +4184,8 @@ add_function_defaults(List *args, HeapTuple func_tuple)
ndelete = nargsprovided + list_length(defaults) - funcform->pronargs;
if (ndelete < 0)
elog(ERROR, "not enough default arguments");
- while (ndelete-- > 0)
- defaults = list_delete_first(defaults);
+ if (ndelete > 0)
+ defaults = list_copy_tail(defaults, ndelete);
/* And form the combined argument list, not modifying the input list */
return list_concat(list_copy(args), defaults);
@@ -4701,9 +4700,9 @@ inline_function(Oid funcid, Oid result_type, Oid result_collid,
* Recursively try to simplify the modified expression. Here we must add
* the current function to the context list of active functions.
*/
- context->active_fns = lcons_oid(funcid, context->active_fns);
+ context->active_fns = lappend_oid(context->active_fns, funcid);
newexpr = eval_const_expressions_mutator(newexpr, context);
- context->active_fns = list_delete_first(context->active_fns);
+ context->active_fns = list_delete_last(context->active_fns);
error_context_stack = sqlerrcontext.previous;
diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c
index 5b047d1..93b6784 100644
--- a/src/backend/rewrite/rewriteHandler.c
+++ b/src/backend/rewrite/rewriteHandler.c
@@ -1973,7 +1973,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
errmsg("infinite recursion detected in rules for relation \"%s\"",
RelationGetRelationName(rel))));
- activeRIRs = lcons_oid(RelationGetRelid(rel), activeRIRs);
+ activeRIRs = lappend_oid(activeRIRs, RelationGetRelid(rel));
foreach(l, locks)
{
@@ -1986,7 +1986,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
activeRIRs);
}
- activeRIRs = list_delete_first(activeRIRs);
+ activeRIRs = list_delete_last(activeRIRs);
}
}
@@ -2059,7 +2059,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
errmsg("infinite recursion detected in policy for relation \"%s\"",
RelationGetRelationName(rel))));
- activeRIRs = lcons_oid(RelationGetRelid(rel), activeRIRs);
+ activeRIRs = lappend_oid(activeRIRs, RelationGetRelid(rel));
/*
* get_row_security_policies just passed back securityQuals
@@ -2084,7 +2084,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
expression_tree_walker((Node *) withCheckOptions,
fireRIRonSubLink, (void *) activeRIRs);
- activeRIRs = list_delete_first(activeRIRs);
+ activeRIRs = list_delete_last(activeRIRs);
}
/*
@@ -3711,7 +3711,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events)
rev = (rewrite_event *) palloc(sizeof(rewrite_event));
rev->relation = RelationGetRelid(rt_entry_relation);
rev->event = event;
- rewrite_events = lcons(rev, rewrite_events);
+ rewrite_events = lappend(rewrite_events, rev);
foreach(n, product_queries)
{
@@ -3722,7 +3722,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events)
rewritten = list_concat(rewritten, newstuff);
}
- rewrite_events = list_delete_first(rewrite_events);
+ rewrite_events = list_delete_last(rewrite_events);
}
/*
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 71dc4dc..1463408 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -531,6 +531,7 @@ extern List *list_delete_ptr(List *list, void *datum);
extern List *list_delete_int(List *list, int datum);
extern List *list_delete_oid(List *list, Oid datum);
extern List *list_delete_first(List *list);
+extern List *list_delete_last(List *list);
extern List *list_delete_nth_cell(List *list, int n);
extern List *list_delete_cell(List *list, ListCell *cell);
diff --git a/src/backend/commands/cluster.c b/src/backend/commands/cluster.c
index ebaec4f..cedb4ee 100644
--- a/src/backend/commands/cluster.c
+++ b/src/backend/commands/cluster.c
@@ -1566,7 +1566,7 @@ get_tables_to_cluster(MemoryContext cluster_context)
rvtc = (RelToCluster *) palloc(sizeof(RelToCluster));
rvtc->tableOid = index->indrelid;
rvtc->indexOid = index->indexrelid;
- rvs = lcons(rvtc, rvs);
+ rvs = lappend(rvs, rvtc);
MemoryContextSwitchTo(old_context);
}
diff --git a/src/backend/commands/typecmds.c b/src/backend/commands/typecmds.c
index e9c8873..89887b8 100644
--- a/src/backend/commands/typecmds.c
+++ b/src/backend/commands/typecmds.c
@@ -2999,7 +2999,7 @@ get_rels_with_domain(Oid domainOid, LOCKMODE lockmode)
rtc->rel = rel;
rtc->natts = 0;
rtc->atts = (int *) palloc(sizeof(int) * RelationGetNumberOfAttributes(rel));
- result = lcons(rtc, result);
+ result = lappend(result, rtc);
}
/*
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index e4e0575..6d09f2a 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -786,7 +786,7 @@ ExecInitExprRec(Expr *node, ExprState *state,
{
AggState *aggstate = (AggState *) state->parent;
- aggstate->aggs = lcons(astate, aggstate->aggs);
+ aggstate->aggs = lappend(aggstate->aggs, astate);
aggstate->numaggs++;
}
else
@@ -834,7 +834,7 @@ ExecInitExprRec(Expr *node, ExprState *state,
WindowAggState *winstate = (WindowAggState *) state->parent;
int nfuncs;
- winstate->funcs = lcons(wfstate, winstate->funcs);
+ winstate->funcs = lappend(winstate->funcs, wfstate);
nfuncs = ++winstate->numfuncs;
if (wfunc->winagg)
winstate->numaggs++;
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 6ea625a..98e9948 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -419,6 +419,13 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
index_close(indexRelation, NoLock);
+ /*
+ * We've historically used lcons() here. It'd make more sense to
+ * use lappend(), but that causes the planner to change behavior
+ * in cases where two indexes seem equally attractive. For now,
+ * stick with lcons() --- few tables should have so many indexes
+ * that the O(N^2) behavior of lcons() is really a problem.
+ */
indexinfos = lcons(info, indexinfos);
}
@@ -1339,7 +1346,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
info->kind = STATS_EXT_NDISTINCT;
info->keys = bms_copy(keys);
- stainfos = lcons(info, stainfos);
+ stainfos = lappend(stainfos, info);
}
if (statext_is_kind_built(dtup, STATS_EXT_DEPENDENCIES))
@@ -1351,7 +1358,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
info->kind = STATS_EXT_DEPENDENCIES;
info->keys = bms_copy(keys);
- stainfos = lcons(info, stainfos);
+ stainfos = lappend(stainfos, info);
}
if (statext_is_kind_built(dtup, STATS_EXT_MCV))
@@ -1363,7 +1370,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
info->kind = STATS_EXT_MCV;
info->keys = bms_copy(keys);
- stainfos = lcons(info, stainfos);
+ stainfos = lappend(stainfos, info);
}
ReleaseSysCache(htup);
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index 19e3164..354030e 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -1132,7 +1132,7 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
if (expr == NULL)
continue; /* probably cannot happen */
- groupClauses = lcons(expr, groupClauses);
+ groupClauses = lappend(groupClauses, expr);
}
/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 66449b8..7eba59e 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3201,7 +3201,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
* Split the list of varinfos in two - one for the current rel, one
* for remaining Vars on other rels.
*/
- relvarinfos = lcons(varinfo1, relvarinfos);
+ relvarinfos = lappend(relvarinfos, varinfo1);
for_each_cell(l, varinfos, list_second_cell(varinfos))
{
GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
@@ -3209,12 +3209,12 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
if (varinfo2->rel == varinfo1->rel)
{
/* varinfos on current rel */
- relvarinfos = lcons(varinfo2, relvarinfos);
+ relvarinfos = lappend(relvarinfos, varinfo2);
}
else
{
/* not time to process varinfo2 yet */
- newvarinfos = lcons(varinfo2, newvarinfos);
+ newvarinfos = lappend(newvarinfos, varinfo2);
}
}
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index ef8eec3..be4ddf8 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2030,10 +2030,10 @@ NOTICE: avg_transfn called with 3
-- this should not share the state due to different input columns.
select my_avg(one),my_sum(two) from (values(1,2),(3,4)) t(one,two);
-NOTICE: avg_transfn called with 2
NOTICE: avg_transfn called with 1
-NOTICE: avg_transfn called with 4
+NOTICE: avg_transfn called with 2
NOTICE: avg_transfn called with 3
+NOTICE: avg_transfn called with 4
my_avg | my_sum
--------+--------
2 | 6
