Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hnWXJ-0001en-QK for pgsql-hackers@arkaria.postgresql.org; Tue, 16 Jul 2019 23:07:06 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hnWXI-0001ko-NA for pgsql-hackers@arkaria.postgresql.org; Tue, 16 Jul 2019 23:07:04 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hnWXI-0001kh-Cj for pgsql-hackers@lists.postgresql.org; Tue, 16 Jul 2019 23:07:04 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hnWXF-0001Wm-94 for pgsql-hackers@lists.postgresql.org; Tue, 16 Jul 2019 23:07:04 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.4/8.14.4) with ESMTP id x6GN6pRo021273; Tue, 16 Jul 2019 19:06:51 -0400 From: Tom Lane To: David Rowley cc: Jesper Pedersen , Andres Freund , Robert Haas , PostgreSQL Hackers Subject: Re: POC: converting Lists into arrays In-reply-to: <2305.1562181615@sss.pgh.pa.us> References: <481.1551390571@sss.pgh.pa.us> <24783.1551568303@sss.pgh.pa.us> <20190303043424.itzy3ge52xrkpmpr@alap3.anarazel.de> <437.1551637744@sss.pgh.pa.us> <12684.1551723095@sss.pgh.pa.us> <20190304190612.vgqqsowzkrh22623@alap3.anarazel.de> <26464.1551734920@sss.pgh.pa.us> <20190304221101.hdg4vj5fo4eewh3b@alap3.anarazel.de> <20190304235402.nod3gbotk2qtd4nh@alap3.anarazel.de> <1131.1551746172@sss.pgh.pa.us> <14626.1558745627@sss.pgh.pa.us> <29297.1558799327@sss.pgh.pa.us> <25178.1562006685@sss.pgh.pa.us> <25258.1562023641@sss.pgh.pa.us> <2305.1562181615@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Wed, 03 Jul 2019 15:20:15 -0400" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <21115.1563318167.0@sss.pgh.pa.us> Date: Tue, 16 Jul 2019 19:06:51 -0400 Message-ID: <21272.1563318411@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <21115.1563318167.1@sss.pgh.pa.us> 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 ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="0001-safe-lcons-changes.patch"; charset="us-ascii" Content-ID: <21115.1563318167.2@sss.pgh.pa.us> Content-Description: 0001-safe-lcons-changes.patch Content-Transfer-Encoding: quoted-printable 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, GISTInsertS= tack *stack, * left. Finally insert the downlink for the last new page and update th= e * downlink for the original page as one operation. */ - - /* for convenience, create a copy of the list in reverse order */ - reversed =3D NIL; - foreach(lc, splitinfo) - { - reversed =3D lcons(lfirst(lc), reversed); - } - LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE); gistFindCorrectParent(state->r, stack); = @@ -1354,10 +1344,10 @@ gistfinishsplit(GISTInsertState *state, GISTInsert= Stack *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 =3D list_length(splitinfo) - 1; pos > 1; pos--) { - right =3D (GISTPageSplitInfo *) linitial(reversed); - left =3D (GISTPageSplitInfo *) lsecond(reversed); + right =3D (GISTPageSplitInfo *) list_nth(splitinfo, pos); + left =3D (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1); = if (gistinserttuples(state, stack->parent, giststate, &right->downlink, 1, @@ -1371,11 +1361,10 @@ gistfinishsplit(GISTInsertState *state, GISTInsert= Stack *stack, gistFindCorrectParent(state->r, stack); } /* gistinserttuples() released the lock on right->buf. */ - reversed =3D list_delete_first(reversed); } = - right =3D (GISTPageSplitInfo *) linitial(reversed); - left =3D (GISTPageSplitInfo *) lsecond(reversed); + right =3D (GISTPageSplitInfo *) lsecond(splitinfo); + left =3D (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 =3D lcons_oid(atttypid, containing_rowtypes); + containing_rowtypes =3D lappend_oid(containing_rowtypes, atttypid); = relation =3D relation_open(get_typ_typrelid(atttypid), AccessShareLock)= ; = @@ -653,7 +653,7 @@ CheckAttributeType(const char *attname, = relation_close(relation, AccessShareLock); = - containing_rowtypes =3D list_delete_first(containing_rowtypes); + containing_rowtypes =3D list_delete_last(containing_rowtypes); } else if (OidIsValid((att_typelem =3D get_element_type(atttypid)))) { diff --git a/src/backend/commands/lockcmds.c b/src/backend/commands/lockcm= ds.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 =3D nowait; context.viewowner =3D view->rd_rel->relowner; context.viewoid =3D reloid; - context.ancestor_views =3D lcons_oid(reloid, ancestor_views); + context.ancestor_views =3D lappend_oid(ancestor_views, reloid); = LockViewRecurse_walker((Node *) viewquery, &context); = - ancestor_views =3D 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/table= cmds.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, OnCommitActi= on action) oc->creating_subid =3D GetCurrentSubTransactionId(); oc->deleting_subid =3D InvalidSubTransactionId; = + /* + * We use lcons() here so that ON COMMIT actions are processed in revers= e + * order of registration. That might not be essential but it seems + * reasonable. + */ on_commits =3D 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 =3D=3D 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) <=3D 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 =3D (SubPlan *) lfirst(l); - ListCell *l2; = - foreach(l2, initsubplan->setParam) - context.safe_param_ids =3D lcons_int(lfirst_int(l2), - context.safe_param_ids); + context.safe_param_ids =3D 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 =3D 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_tup= le) ndelete =3D nargsprovided + list_length(defaults) - funcform->pronargs; if (ndelete < 0) elog(ERROR, "not enough default arguments"); - while (ndelete-- > 0) - defaults =3D list_delete_first(defaults); + if (ndelete > 0) + defaults =3D 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 res= ult_collid, * Recursively try to simplify the modified expression. Here we must ad= d * the current function to the context list of active functions. */ - context->active_fns =3D lcons_oid(funcid, context->active_fns); + context->active_fns =3D lappend_oid(context->active_fns, funcid); newexpr =3D eval_const_expressions_mutator(newexpr, context); - context->active_fns =3D list_delete_first(context->active_fns); + context->active_fns =3D list_delete_last(context->active_fns); = error_context_stack =3D sqlerrcontext.previous; = diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/re= writeHandler.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 =3D lcons_oid(RelationGetRelid(rel), activeRIRs); + activeRIRs =3D lappend_oid(activeRIRs, RelationGetRelid(rel)); = foreach(l, locks) { @@ -1986,7 +1986,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs) activeRIRs); } = - activeRIRs =3D list_delete_first(activeRIRs); + activeRIRs =3D 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 =3D lcons_oid(RelationGetRelid(rel), activeRIRs); + activeRIRs =3D 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 =3D list_delete_first(activeRIRs); + activeRIRs =3D list_delete_last(activeRIRs); } = /* @@ -3711,7 +3711,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events) rev =3D (rewrite_event *) palloc(sizeof(rewrite_event)); rev->relation =3D RelationGetRelid(rt_entry_relation); rev->event =3D event; - rewrite_events =3D lcons(rev, rewrite_events); + rewrite_events =3D lappend(rewrite_events, rev); = foreach(n, product_queries) { @@ -3722,7 +3722,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events) rewritten =3D list_concat(rewritten, newstuff); } = - rewrite_events =3D list_delete_first(rewrite_events); + rewrite_events =3D 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); = ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="0002-less-safe-lcons-changes.patch"; charset="us-ascii" Content-ID: <21115.1563318167.3@sss.pgh.pa.us> Content-Description: 0002-less-safe-lcons-changes.patch Content-Transfer-Encoding: quoted-printable 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 =3D (RelToCluster *) palloc(sizeof(RelToCluster)); rvtc->tableOid =3D index->indrelid; rvtc->indexOid =3D index->indexrelid; - rvs =3D lcons(rvtc, rvs); + rvs =3D lappend(rvs, rvtc); = MemoryContextSwitchTo(old_context); } diff --git a/src/backend/commands/typecmds.c b/src/backend/commands/typecm= ds.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 lockmod= e) rtc->rel =3D rel; rtc->natts =3D 0; rtc->atts =3D (int *) palloc(sizeof(int) * RelationGetNumberOfAttribut= es(rel)); - result =3D lcons(rtc, result); + result =3D lappend(result, rtc); } = /* diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execEx= pr.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 =3D (AggState *) state->parent; = - aggstate->aggs =3D lcons(astate, aggstate->aggs); + aggstate->aggs =3D lappend(aggstate->aggs, astate); aggstate->numaggs++; } else @@ -834,7 +834,7 @@ ExecInitExprRec(Expr *node, ExprState *state, WindowAggState *winstate =3D (WindowAggState *) state->parent; int nfuncs; = - winstate->funcs =3D lcons(wfstate, winstate->funcs); + winstate->funcs =3D lappend(winstate->funcs, wfstate); nfuncs =3D ++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 relationObje= ctId, 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 =3D lcons(info, indexinfos); } = @@ -1339,7 +1346,7 @@ get_relation_statistics(RelOptInfo *rel, Relation re= lation) info->kind =3D STATS_EXT_NDISTINCT; info->keys =3D bms_copy(keys); = - stainfos =3D lcons(info, stainfos); + stainfos =3D lappend(stainfos, info); } = if (statext_is_kind_built(dtup, STATS_EXT_DEPENDENCIES)) @@ -1351,7 +1358,7 @@ get_relation_statistics(RelOptInfo *rel, Relation re= lation) info->kind =3D STATS_EXT_DEPENDENCIES; info->keys =3D bms_copy(keys); = - stainfos =3D lcons(info, stainfos); + stainfos =3D lappend(stainfos, info); } = if (statext_is_kind_built(dtup, STATS_EXT_MCV)) @@ -1363,7 +1370,7 @@ get_relation_statistics(RelOptInfo *rel, Relation re= lation) info->kind =3D STATS_EXT_MCV; info->keys =3D bms_copy(keys); = - stainfos =3D lcons(info, stainfos); + stainfos =3D 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 =3D=3D NULL) continue; /* probably cannot happen */ = - groupClauses =3D lcons(expr, groupClauses); + groupClauses =3D lappend(groupClauses, expr); } = /* diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/self= uncs.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 *groupEx= prs, double input_rows, * Split the list of varinfos in two - one for the current rel, one * for remaining Vars on other rels. */ - relvarinfos =3D lcons(varinfo1, relvarinfos); + relvarinfos =3D lappend(relvarinfos, varinfo1); for_each_cell(l, varinfos, list_second_cell(varinfos)) { GroupVarInfo *varinfo2 =3D (GroupVarInfo *) lfirst(l); @@ -3209,12 +3209,12 @@ estimate_num_groups(PlannerInfo *root, List *group= Exprs, double input_rows, if (varinfo2->rel =3D=3D varinfo1->rel) { /* varinfos on current rel */ - relvarinfos =3D lcons(varinfo2, relvarinfos); + relvarinfos =3D lappend(relvarinfos, varinfo2); } else { /* not time to process varinfo2 yet */ - newvarinfos =3D lcons(varinfo2, newvarinfos); + newvarinfos =3D lappend(newvarinfos, varinfo2); } } = diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/e= xpected/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 ------- =_aaaaaaaaaa0--