Represent Lists as expansible arrays, not chains of cons-cells.

Originally, Postgres Lists were a more or less exact reimplementation of
Lisp lists, which consist of chains of separately-allocated cons cells,
each having a value and a next-cell link.  We'd hacked that once before
(commit d0b4399d8) to add a separate List header, but the data was still
in cons cells.  That makes some operations -- notably list_nth() -- O(N),
and it's bulky because of the next-cell pointers and per-cell palloc
overhead, and it's very cache-unfriendly if the cons cells end up
scattered around rather than being adjacent.

In this rewrite, we still have List headers, but the data is in a
resizable array of values, with no next-cell links.  Now we need at
most two palloc's per List, and often only one, since we can allocate
some values in the same palloc call as the List header.  (Of course,
extending an existing List may require repalloc's to enlarge the array.
But this involves just O(log N) allocations not O(N).)

Of course this is not without downsides.  The key difficulty is that
addition or deletion of a list entry may now cause other entries to
move, which it did not before.

For example, that breaks foreach() and sister macros, which historically
used a pointer to the current cons-cell as loop state.  We can repair
those macros transparently by making their actual loop state be an
integer list index; the exposed "ListCell *" pointer is no longer state
carried across loop iterations, but is just a derived value.  (In
practice, modern compilers can optimize things back to having just one
loop state value, at least for simple cases with inline loop bodies.)
In principle, this is a semantics change for cases where the loop body
inserts or deletes list entries ahead of the current loop index; but
I found no such cases in the Postgres code.

The change is not at all transparent for code that doesn't use foreach()
but chases lists "by hand" using lnext().  The largest share of such
code in the backend is in loops that were maintaining "prev" and "next"
variables in addition to the current-cell pointer, in order to delete
list cells efficiently using list_delete_cell().  However, we no longer
need a previous-cell pointer to delete a list cell efficiently.  Keeping
a next-cell pointer doesn't work, as explained above, but we can improve
matters by changing such code to use a regular foreach() loop and then
using the new macro foreach_delete_current() to delete the current cell.
(This macro knows how to update the associated foreach loop's state so
that no cells will be missed in the traversal.)

There remains a nontrivial risk of code assuming that a ListCell *
pointer will remain good over an operation that could now move the list
contents.  To help catch such errors, list.c can be compiled with a new
define symbol DEBUG_LIST_MEMORY_USAGE that forcibly moves list contents
whenever that could possibly happen.  This makes list operations
significantly more expensive so it's not normally turned on (though it
is on by default if USE_VALGRIND is on).

There are two notable API differences from the previous code:

* lnext() now requires the List's header pointer in addition to the
current cell's address.

* list_delete_cell() no longer requires a previous-cell argument.

These changes are somewhat unfortunate, but on the other hand code using
either function needs inspection to see if it is assuming anything
it shouldn't, so it's not all bad.

Programmers should be aware of these significant performance changes:

* list_nth() and related functions are now O(1); so there's no
major access-speed difference between a list and an array.

* Inserting or deleting a list element now takes time proportional to
the distance to the end of the list, due to moving the array elements.
(However, it typically *doesn't* require palloc or pfree, so except in
long lists it's probably still faster than before.)  Notably, lcons()
used to be about the same cost as lappend(), but that's no longer true
if the list is long.  Code that uses lcons() and list_delete_first()
to maintain a stack might usefully be rewritten to push and pop at the
end of the list rather than the beginning.

* There are now list_insert_nth...() and list_delete_nth...() functions
that add or remove a list cell identified by index.  These have the
data-movement penalty explained above, but there's no search penalty.

* list_concat() and variants now copy the second list's data into
storage belonging to the first list, so there is no longer any
sharing of cells between the input lists.  The second argument is
now declared "const List *" to reflect that it isn't changed.

This patch just does the minimum needed to get the new implementation
in place and fix bugs exposed by the regression tests.  As suggested
by the foregoing, there's a fair amount of followup work remaining to
do.

Also, the ENABLE_LIST_COMPAT macros are finally removed in this
commit.  Code using those should have been gone a dozen years ago.

Patch by me; thanks to David Rowley, Jesper Pedersen, and others
for review.

Discussion: https://postgr.es/m/11587.1550975080@sss.pgh.pa.us

20 files changed, 145 insertions, 205 deletions

diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c
index 6c69c1c1478..8a44ac8530d 100644
--- a/src/backend/optimizer/geqo/geqo_eval.c
+++ b/src/backend/optimizer/geqo/geqo_eval.c
@@ -238,11 +238,9 @@ static List *
 merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
 			bool force)
 {
-	ListCell   *prev;
 	ListCell   *lc;
 
 	/* Look for a clump that new_clump can join to */
-	prev = NULL;
 	foreach(lc, clumps)
 	{
 		Clump	   *old_clump = (Clump *) lfirst(lc);
@@ -286,7 +284,7 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
 				pfree(new_clump);
 
 				/* Remove old_clump from list */
-				clumps = list_delete_cell(clumps, lc, prev);
+				clumps = foreach_delete_current(clumps, lc);
 
 				/*
 				 * Recursively try to merge the enlarged old_clump with
@@ -296,7 +294,6 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
 				return merge_clump(root, clumps, old_clump, num_gene, force);
 			}
 		}
-		prev = lc;
 	}
 
 	/*
@@ -315,7 +312,7 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
 	/* Else search for the place to insert it */
 	for (;;)
 	{
-		ListCell   *nxt = lnext(lc);
+		ListCell   *nxt = lnext(clumps, lc);
 
 		if (nxt == NULL || new_clump->size > ((Clump *) lfirst(nxt))->size)
 			break;				/* it belongs after 'lc', before 'nxt' */
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b7723481b0e..e9ee32b7f43 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -3204,7 +3204,7 @@ compare_tlist_datatypes(List *tlist, List *colTypes,
 			elog(ERROR, "wrong number of tlist entries");
 		if (exprType((Node *) tle->expr) != lfirst_oid(colType))
 			safetyInfo->unsafeColumns[tle->resno] = true;
-		colType = lnext(colType);
+		colType = lnext(colTypes, colType);
 	}
 	if (colType != NULL)
 		elog(ERROR, "wrong number of tlist entries");
@@ -3761,7 +3761,7 @@ print_restrictclauses(PlannerInfo *root, List *clauses)
 		RestrictInfo *c = lfirst(l);
 
 		print_expr((Node *) c->clause, root->parse->rtable);
-		if (lnext(l))
+		if (lnext(clauses, l))
 			printf(", ");
 	}
 }
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index a2a9b1f7be6..3a9a994733b 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1838,7 +1838,7 @@ append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
 	 * For each of the remaining subpaths, add its cost to the array element
 	 * with minimum cost.
 	 */
-	for_each_cell(l, cell)
+	for_each_cell(l, subpaths, cell)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
 		int			i;
@@ -4724,8 +4724,6 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
 		bool		ref_is_outer;
 		List	   *removedlist;
 		ListCell   *cell;
-		ListCell   *prev;
-		ListCell   *next;
 
 		/*
 		 * This FK is not relevant unless it connects a baserel on one side of
@@ -4766,14 +4764,12 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
 			worklist = list_copy(worklist);
 
 		removedlist = NIL;
-		prev = NULL;
-		for (cell = list_head(worklist); cell; cell = next)
+		foreach(cell, worklist)
 		{
 			RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 			bool		remove_it = false;
 			int			i;
 
-			next = lnext(cell);
 			/* Drop this clause if it matches any column of the FK */
 			for (i = 0; i < fkinfo->nkeys; i++)
 			{
@@ -4813,11 +4809,9 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
 			}
 			if (remove_it)
 			{
-				worklist = list_delete_cell(worklist, cell, prev);
+				worklist = foreach_delete_current(worklist, cell);
 				removedlist = lappend(removedlist, rinfo);
 			}
-			else
-				prev = cell;
 		}
 
 		/*
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 688d9b07075..78d076b13cd 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1573,8 +1573,6 @@ reconsider_outer_join_clauses(PlannerInfo *root)
 {
 	bool		found;
 	ListCell   *cell;
-	ListCell   *prev;
-	ListCell   *next;
 
 	/* Outer loop repeats until we find no more deductions */
 	do
@@ -1582,72 +1580,60 @@ reconsider_outer_join_clauses(PlannerInfo *root)
 		found = false;
 
 		/* Process the LEFT JOIN clauses */
-		prev = NULL;
-		for (cell = list_head(root->left_join_clauses); cell; cell = next)
+		foreach(cell, root->left_join_clauses)
 		{
 			RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
-			next = lnext(cell);
 			if (reconsider_outer_join_clause(root, rinfo, true))
 			{
 				found = true;
 				/* remove it from the list */
 				root->left_join_clauses =
-					list_delete_cell(root->left_join_clauses, cell, prev);
+					foreach_delete_current(root->left_join_clauses, cell);
 				/* we throw it back anyway (see notes above) */
 				/* but the thrown-back clause has no extra selectivity */
 				rinfo->norm_selec = 2.0;
 				rinfo->outer_selec = 1.0;
 				distribute_restrictinfo_to_rels(root, rinfo);
 			}
-			else
-				prev = cell;
 		}
 
 		/* Process the RIGHT JOIN clauses */
-		prev = NULL;
-		for (cell = list_head(root->right_join_clauses); cell; cell = next)
+		foreach(cell, root->right_join_clauses)
 		{
 			RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
-			next = lnext(cell);
 			if (reconsider_outer_join_clause(root, rinfo, false))
 			{
 				found = true;
 				/* remove it from the list */
 				root->right_join_clauses =
-					list_delete_cell(root->right_join_clauses, cell, prev);
+					foreach_delete_current(root->right_join_clauses, cell);
 				/* we throw it back anyway (see notes above) */
 				/* but the thrown-back clause has no extra selectivity */
 				rinfo->norm_selec = 2.0;
 				rinfo->outer_selec = 1.0;
 				distribute_restrictinfo_to_rels(root, rinfo);
 			}
-			else
-				prev = cell;
 		}
 
 		/* Process the FULL JOIN clauses */
-		prev = NULL;
-		for (cell = list_head(root->full_join_clauses); cell; cell = next)
+		foreach(cell, root->full_join_clauses)
 		{
 			RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
-			next = lnext(cell);
 			if (reconsider_full_join_clause(root, rinfo))
 			{
 				found = true;
 				/* remove it from the list */
 				root->full_join_clauses =
-					list_delete_cell(root->full_join_clauses, cell, prev);
+					foreach_delete_current(root->full_join_clauses, cell);
 				/* we throw it back anyway (see notes above) */
 				/* but the thrown-back clause has no extra selectivity */
 				rinfo->norm_selec = 2.0;
 				rinfo->outer_selec = 1.0;
 				distribute_restrictinfo_to_rels(root, rinfo);
 			}
-			else
-				prev = cell;
 		}
 	} while (found);
 
@@ -2123,7 +2109,7 @@ add_child_rel_equivalences(PlannerInfo *root,
 	foreach(lc1, root->eq_classes)
 	{
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-		ListCell   *lc2;
+		int			num_members;
 
 		/*
 		 * If this EC contains a volatile expression, then generating child
@@ -2140,9 +2126,15 @@ add_child_rel_equivalences(PlannerInfo *root,
 		if (!bms_is_subset(child_rel->top_parent_relids, cur_ec->ec_relids))
 			continue;
 
-		foreach(lc2, cur_ec->ec_members)
+		/*
+		 * We don't use foreach() here because there's no point in scanning
+		 * newly-added child members, so we can stop after the last
+		 * pre-existing EC member.
+		 */
+		num_members = list_length(cur_ec->ec_members);
+		for (int pos = 0; pos < num_members; pos++)
 		{
-			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
 
 			if (cur_em->em_is_const)
 				continue;		/* ignore consts here */
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c208e9bfb0b..5f339fdfde7 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -520,7 +520,7 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
 		IndexClause *iclause = (IndexClause *) lfirst(lc);
 		Relids		clause_relids = iclause->rinfo->clause_relids;
 		EquivalenceClass *parent_ec = iclause->rinfo->parent_ec;
-		ListCell   *lc2;
+		int			num_considered_relids;
 
 		/* If we already tried its relids set, no need to do so again */
 		if (bms_equal_any(clause_relids, *considered_relids))
@@ -533,15 +533,16 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
 		 * exponential growth of planning time when there are many clauses,
 		 * limit the number of relid sets accepted to 10 * considered_clauses.
 		 *
-		 * Note: get_join_index_paths adds entries to *considered_relids, but
-		 * it prepends them to the list, so that we won't visit new entries
-		 * during the inner foreach loop.  No real harm would be done if we
-		 * did, since the subset check would reject them; but it would waste
-		 * some cycles.
+		 * Note: get_join_index_paths appends entries to *considered_relids,
+		 * but we do not need to visit such newly-added entries within this
+		 * loop, so we don't use foreach() here.  No real harm would be done
+		 * if we did visit them, since the subset check would reject them; but
+		 * it would waste some cycles.
 		 */
-		foreach(lc2, *considered_relids)
+		num_considered_relids = list_length(*considered_relids);
+		for (int pos = 0; pos < num_considered_relids; pos++)
 		{
-			Relids		oldrelids = (Relids) lfirst(lc2);
+			Relids		oldrelids = (Relids) list_nth(*considered_relids, pos);
 
 			/*
 			 * If either is a subset of the other, no new set is possible.
@@ -671,10 +672,9 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel,
 	get_index_paths(root, rel, index, &clauseset, bitindexpaths);
 
 	/*
-	 * Remember we considered paths for this set of relids.  We use lcons not
-	 * lappend to avoid confusing the loop in consider_index_join_outer_rels.
+	 * Remember we considered paths for this set of relids.
 	 */
-	*considered_relids = lcons(relids, *considered_relids);
+	*considered_relids = lappend(*considered_relids, relids);
 }
 
 /*
@@ -1502,7 +1502,6 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 		Cost		costsofar;
 		List	   *qualsofar;
 		Bitmapset  *clauseidsofar;
-		ListCell   *lastcell;
 
 		pathinfo = pathinfoarray[i];
 		paths = list_make1(pathinfo->path);
@@ -1510,7 +1509,6 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 		qualsofar = list_concat(list_copy(pathinfo->quals),
 								list_copy(pathinfo->preds));
 		clauseidsofar = bms_copy(pathinfo->clauseids);
-		lastcell = list_head(paths);	/* for quick deletions */
 
 		for (j = i + 1; j < npaths; j++)
 		{
@@ -1551,14 +1549,12 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 										list_copy(pathinfo->preds));
 				clauseidsofar = bms_add_members(clauseidsofar,
 												pathinfo->clauseids);
-				lastcell = lnext(lastcell);
 			}
 			else
 			{
 				/* reject new path, remove it from paths list */
-				paths = list_delete_cell(paths, lnext(lastcell), lastcell);
+				paths = list_truncate(paths, list_length(paths) - 1);
 			}
-			Assert(lnext(lastcell) == NULL);
 		}
 
 		/* Keep the cheapest AND-group (or singleton) */
@@ -2970,10 +2966,6 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo,
 	List	   *new_ops;
 	List	   *var_args;
 	List	   *non_var_args;
-	ListCell   *vargs_cell;
-	ListCell   *nargs_cell;
-	ListCell   *opnos_cell;
-	ListCell   *collids_cell;
 
 	iclause->rinfo = rinfo;
 	iclause->indexcol = indexcol;
@@ -3010,18 +3002,14 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo,
 	 * indexed relation.
 	 */
 	matching_cols = 1;
-	vargs_cell = lnext(list_head(var_args));
-	nargs_cell = lnext(list_head(non_var_args));
-	opnos_cell = lnext(list_head(clause->opnos));
-	collids_cell = lnext(list_head(clause->inputcollids));
 
-	while (vargs_cell != NULL)
+	while (matching_cols < list_length(var_args))
 	{
-		Node	   *varop = (Node *) lfirst(vargs_cell);
-		Node	   *constop = (Node *) lfirst(nargs_cell);
+		Node	   *varop = (Node *) list_nth(var_args, matching_cols);
+		Node	   *constop = (Node *) list_nth(non_var_args, matching_cols);
 		int			i;
 
-		expr_op = lfirst_oid(opnos_cell);
+		expr_op = list_nth_oid(clause->opnos, matching_cols);
 		if (!var_on_left)
 		{
 			/* indexkey is on right, so commute the operator */
@@ -3043,7 +3031,8 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo,
 				get_op_opfamily_strategy(expr_op,
 										 index->opfamily[i]) == op_strategy &&
 				IndexCollMatchesExprColl(index->indexcollations[i],
-										 lfirst_oid(collids_cell)))
+										 list_nth_oid(clause->inputcollids,
+													  matching_cols)))
 				break;
 		}
 		if (i >= index->nkeycolumns)
@@ -3064,10 +3053,6 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo,
 
 		/* This column matches, keep scanning */
 		matching_cols++;
-		vargs_cell = lnext(vargs_cell);
-		nargs_cell = lnext(nargs_cell);
-		opnos_cell = lnext(opnos_cell);
-		collids_cell = lnext(collids_cell);
 	}
 
 	/* Result is non-lossy if all columns are usable as index quals */
@@ -3866,7 +3851,7 @@ match_index_to_operand(Node *operand,
 			{
 				if (indexpr_item == NULL)
 					elog(ERROR, "wrong number of index expressions");
-				indexpr_item = lnext(indexpr_item);
+				indexpr_item = lnext(index->indexprs, indexpr_item);
 			}
 		}
 		if (indexpr_item == NULL)
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 43c3b7ea489..6a480ab7644 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -26,10 +26,11 @@
 
 static void make_rels_by_clause_joins(PlannerInfo *root,
 									  RelOptInfo *old_rel,
+									  List *other_rels_list,
 									  ListCell *other_rels);
 static void make_rels_by_clauseless_joins(PlannerInfo *root,
 										  RelOptInfo *old_rel,
-										  ListCell *other_rels);
+										  List *other_rels);
 static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
 static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
 static bool restriction_is_constant_false(List *restrictlist,
@@ -101,15 +102,23 @@ join_search_one_level(PlannerInfo *root, int level)
 			 * to each initial rel they don't already include but have a join
 			 * clause or restriction with.
 			 */
+			List	   *other_rels_list;
 			ListCell   *other_rels;
 
 			if (level == 2)		/* consider remaining initial rels */
-				other_rels = lnext(r);
+			{
+				other_rels_list = joinrels[level - 1];
+				other_rels = lnext(other_rels_list, r);
+			}
 			else				/* consider all initial rels */
-				other_rels = list_head(joinrels[1]);
+			{
+				other_rels_list = joinrels[1];
+				other_rels = list_head(other_rels_list);
+			}
 
 			make_rels_by_clause_joins(root,
 									  old_rel,
+									  other_rels_list,
 									  other_rels);
 		}
 		else
@@ -128,7 +137,7 @@ join_search_one_level(PlannerInfo *root, int level)
 			 */
 			make_rels_by_clauseless_joins(root,
 										  old_rel,
-										  list_head(joinrels[1]));
+										  joinrels[1]);
 		}
 	}
 
@@ -154,6 +163,7 @@ join_search_one_level(PlannerInfo *root, int level)
 		foreach(r, joinrels[k])
 		{
 			RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
+			List	   *other_rels_list;
 			ListCell   *other_rels;
 			ListCell   *r2;
 
@@ -167,11 +177,18 @@ join_search_one_level(PlannerInfo *root, int level)
 				continue;
 
 			if (k == other_level)
-				other_rels = lnext(r);	/* only consider remaining rels */
+			{
+				/* only consider remaining rels */
+				other_rels_list = joinrels[k];
+				other_rels = lnext(other_rels_list, r);
+			}
 			else
-				other_rels = list_head(joinrels[other_level]);
+			{
+				other_rels_list = joinrels[other_level];
+				other_rels = list_head(other_rels_list);
+			}
 
-			for_each_cell(r2, other_rels)
+			for_each_cell(r2, other_rels_list, other_rels)
 			{
 				RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
 
@@ -223,7 +240,7 @@ join_search_one_level(PlannerInfo *root, int level)
 
 			make_rels_by_clauseless_joins(root,
 										  old_rel,
-										  list_head(joinrels[1]));
+										  joinrels[1]);
 		}
 
 		/*----------
@@ -265,8 +282,9 @@ join_search_one_level(PlannerInfo *root, int level)
  * automatically ensures that each new joinrel is only added to the list once.
  *
  * 'old_rel' is the relation entry for the relation to be joined
- * 'other_rels': the first cell in a linked list containing the other
+ * 'other_rels_list': a list containing the other
  * rels to be considered for joining
+ * 'other_rels': the first cell to be considered
  *
  * Currently, this is only used with initial rels in other_rels, but it
  * will work for joining to joinrels too.
@@ -274,11 +292,12 @@ join_search_one_level(PlannerInfo *root, int level)
 static void
 make_rels_by_clause_joins(PlannerInfo *root,
 						  RelOptInfo *old_rel,
+						  List *other_rels_list,
 						  ListCell *other_rels)
 {
 	ListCell   *l;
 
-	for_each_cell(l, other_rels)
+	for_each_cell(l, other_rels_list, other_rels)
 	{
 		RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 
@@ -299,8 +318,7 @@ make_rels_by_clause_joins(PlannerInfo *root,
  *	  The join rels are returned in root->join_rel_level[join_cur_level].
  *
  * 'old_rel' is the relation entry for the relation to be joined
- * 'other_rels': the first cell of a linked list containing the
- * other rels to be considered for joining
+ * 'other_rels': a list containing the other rels to be considered for joining
  *
  * Currently, this is only used with initial rels in other_rels, but it would
  * work for joining to joinrels too.
@@ -308,11 +326,11 @@ make_rels_by_clause_joins(PlannerInfo *root,
 static void
 make_rels_by_clauseless_joins(PlannerInfo *root,
 							  RelOptInfo *old_rel,
-							  ListCell *other_rels)
+							  List *other_rels)
 {
 	ListCell   *l;
 
-	for_each_cell(l, other_rels)
+	foreach(l, other_rels)
 	{
 		RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 08b50616128..202a4b9db82 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1529,7 +1529,7 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
 			if (!lop)
 				elog(ERROR, "too few pathkeys for mergeclauses");
 			opathkey = (PathKey *) lfirst(lop);
-			lop = lnext(lop);
+			lop = lnext(outer_pathkeys, lop);
 			lastoeclass = opathkey->pk_eclass;
 			if (oeclass != lastoeclass)
 				elog(ERROR, "outer pathkeys do not match mergeclause");
@@ -1609,7 +1609,7 @@ trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
 	lip = list_head(pathkeys);
 	pathkey = (PathKey *) lfirst(lip);
 	pathkey_ec = pathkey->pk_eclass;
-	lip = lnext(lip);
+	lip = lnext(pathkeys, lip);
 	matched_pathkey = false;
 
 	/* Scan mergeclauses to see how many we can use */
@@ -1636,7 +1636,7 @@ trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
 				break;
 			pathkey = (PathKey *) lfirst(lip);
 			pathkey_ec = pathkey->pk_eclass;
-			lip = lnext(lip);
+			lip = lnext(pathkeys, lip);
 			matched_pathkey = false;
 		}
 
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 32695db367b..d19ff4138e5 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -96,17 +96,16 @@ restart:
 
 		/*
 		 * We can delete this SpecialJoinInfo from the list too, since it's no
-		 * longer of interest.
+		 * longer of interest.  (Since we'll restart the foreach loop
+		 * immediately, we don't bother with foreach_delete_current.)
 		 */
-		root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+		root->join_info_list = list_delete_cell(root->join_info_list, lc);
 
 		/*
 		 * Restart the scan.  This is necessary to ensure we find all
 		 * removable joins independently of ordering of the join_info_list
 		 * (note that removal of attr_needed bits may make a join appear
-		 * removable that did not before).  Also, since we just deleted the
-		 * current list cell, we'd have to have some kluge to continue the
-		 * list scan anyway.
+		 * removable that did not before).
 		 */
 		goto restart;
 	}
@@ -316,7 +315,6 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	List	   *joininfos;
 	Index		rti;
 	ListCell   *l;
-	ListCell   *nextl;
 
 	/*
 	 * Mark the rel as "dead" to show it is no longer part of the join tree.
@@ -383,16 +381,15 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	 * remove or just update the PHV.  There is no corresponding test in
 	 * join_is_removable because it doesn't need to distinguish those cases.
 	 */
-	for (l = list_head(root->placeholder_list); l != NULL; l = nextl)
+	foreach(l, root->placeholder_list)
 	{
 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
 
-		nextl = lnext(l);
 		Assert(!bms_is_member(relid, phinfo->ph_lateral));
 		if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
 			bms_is_member(relid, phinfo->ph_eval_at))
-			root->placeholder_list = list_delete_ptr(root->placeholder_list,
-													 phinfo);
+			root->placeholder_list = foreach_delete_current(root->placeholder_list,
+															l);
 		else
 		{
 			phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
@@ -511,13 +508,11 @@ void
 reduce_unique_semijoins(PlannerInfo *root)
 {
 	ListCell   *lc;
-	ListCell   *next;
 
 	/*
-	 * Scan the join_info_list to find semijoins.  We can't use foreach
-	 * because we may delete the current cell.
+	 * Scan the join_info_list to find semijoins.
 	 */
-	for (lc = list_head(root->join_info_list); lc != NULL; lc = next)
+	foreach(lc, root->join_info_list)
 	{
 		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
 		int			innerrelid;
@@ -525,8 +520,6 @@ reduce_unique_semijoins(PlannerInfo *root)
 		Relids		joinrelids;
 		List	   *restrictlist;
 
-		next = lnext(lc);
-
 		/*
 		 * Must be a non-delaying semijoin to a single baserel, else we aren't
 		 * going to be able to do anything with it.  (It's probably not
@@ -572,7 +565,7 @@ reduce_unique_semijoins(PlannerInfo *root)
 			continue;
 
 		/* OK, remove the SpecialJoinInfo from the list. */
-		root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+		root->join_info_list = foreach_delete_current(root->join_info_list, lc);
 	}
 }
 
@@ -897,7 +890,7 @@ query_is_distinct_for(Query *query, List *colnos, List *opids)
 				/* non-resjunk columns should have grouping clauses */
 				Assert(lg != NULL);
 				sgc = (SortGroupClause *) lfirst(lg);
-				lg = lnext(lg);
+				lg = lnext(topop->groupClauses, lg);
 
 				opid = distinct_col_search(tle->resno, colnos, opids);
 				if (!OidIsValid(opid) ||
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 12fba56285d..c6b8553a083 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2211,10 +2211,9 @@ create_groupingsets_plan(PlannerInfo *root, GroupingSetsPath *best_path)
 	chain = NIL;
 	if (list_length(rollups) > 1)
 	{
-		ListCell   *lc2 = lnext(list_head(rollups));
 		bool		is_first_sort = ((RollupData *) linitial(rollups))->is_hashed;
 
-		for_each_cell(lc, lc2)
+		for_each_cell(lc, rollups, list_second_cell(rollups))
 		{
 			RollupData *rollup = lfirst(lc);
 			AttrNumber *new_grpColIdx;
@@ -4261,7 +4260,7 @@ create_mergejoin_plan(PlannerInfo *root,
 				elog(ERROR, "outer pathkeys do not match mergeclauses");
 			opathkey = (PathKey *) lfirst(lop);
 			opeclass = opathkey->pk_eclass;
-			lop = lnext(lop);
+			lop = lnext(outerpathkeys, lop);
 			if (oeclass != opeclass)
 				elog(ERROR, "outer pathkeys do not match mergeclauses");
 		}
@@ -4288,7 +4287,7 @@ create_mergejoin_plan(PlannerInfo *root,
 			if (ieclass == ipeclass)
 			{
 				/* successful first match to this inner pathkey */
-				lip = lnext(lip);
+				lip = lnext(innerpathkeys, lip);
 				first_inner_match = true;
 			}
 		}
@@ -4820,7 +4819,7 @@ fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol)
 				else
 					elog(ERROR, "index key does not match expected index column");
 			}
-			indexpr_item = lnext(indexpr_item);
+			indexpr_item = lnext(index->indexprs, indexpr_item);
 		}
 	}
 
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 401299e5420..ca3b7f29e18 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3351,7 +3351,7 @@ extract_rollup_sets(List *groupingSets)
 	while (lc1 && lfirst(lc1) == NIL)
 	{
 		++num_empty;
-		lc1 = lnext(lc1);
+		lc1 = lnext(groupingSets, lc1);
 	}
 
 	/* bail out now if it turns out that all we had were empty sets. */
@@ -3385,7 +3385,7 @@ extract_rollup_sets(List *groupingSets)
 	j = 0;
 	i = 1;
 
-	for_each_cell(lc, lc1)
+	for_each_cell(lc, groupingSets, lc1)
 	{
 		List	   *candidate = (List *) lfirst(lc);
 		Bitmapset  *candidate_set = NULL;
@@ -4243,7 +4243,7 @@ consider_groupingsets_paths(PlannerInfo *root,
 		{
 			unhashed_rollup = lfirst_node(RollupData, l_start);
 			exclude_groups = unhashed_rollup->numGroups;
-			l_start = lnext(l_start);
+			l_start = lnext(gd->rollups, l_start);
 		}
 
 		hashsize = estimate_hashagg_tablesize(path,
@@ -4264,7 +4264,7 @@ consider_groupingsets_paths(PlannerInfo *root,
 		 */
 		sets_data = list_copy(gd->unsortable_sets);
 
-		for_each_cell(lc, l_start)
+		for_each_cell(lc, gd->rollups, l_start)
 		{
 			RollupData *rollup = lfirst_node(RollupData, lc);
 
@@ -4425,7 +4425,7 @@ consider_groupingsets_paths(PlannerInfo *root,
 			 * below, must use the same condition.
 			 */
 			i = 0;
-			for_each_cell(lc, lnext(list_head(gd->rollups)))
+			for_each_cell(lc, gd->rollups, list_second_cell(gd->rollups))
 			{
 				RollupData *rollup = lfirst_node(RollupData, lc);
 
@@ -4459,7 +4459,7 @@ consider_groupingsets_paths(PlannerInfo *root,
 				rollups = list_make1(linitial(gd->rollups));
 
 				i = 0;
-				for_each_cell(lc, lnext(list_head(gd->rollups)))
+				for_each_cell(lc, gd->rollups, list_second_cell(gd->rollups))
 				{
 					RollupData *rollup = lfirst_node(RollupData, lc);
 
@@ -4672,7 +4672,7 @@ create_one_window_path(PlannerInfo *root,
 											 -1.0);
 		}
 
-		if (lnext(l))
+		if (lnext(activeWindows, l))
 		{
 			/*
 			 * Add the current WindowFuncs to the output target for this
@@ -5333,7 +5333,7 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
 
 		Assert(orig_tlist_item != NULL);
 		orig_tle = lfirst_node(TargetEntry, orig_tlist_item);
-		orig_tlist_item = lnext(orig_tlist_item);
+		orig_tlist_item = lnext(orig_tlist, orig_tlist_item);
 		if (orig_tle->resjunk)	/* should not happen */
 			elog(ERROR, "resjunk output columns are not implemented");
 		Assert(new_tle->resno == orig_tle->resno);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index efd0fbc21c5..48b62a55de8 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -567,7 +567,7 @@ build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
 		{
 			ptr += sprintf(ptr, "$%d%s",
 						   lfirst_int(lc),
-						   lnext(lc) ? "," : ")");
+						   lnext(splan->setParam, lc) ? "," : ")");
 		}
 	}
 
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 67eeba938db..e20bee0b330 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -2791,8 +2791,6 @@ void
 remove_useless_result_rtes(PlannerInfo *root)
 {
 	ListCell   *cell;
-	ListCell   *prev;
-	ListCell   *next;
 
 	/* Top level of jointree must always be a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
@@ -2813,16 +2811,12 @@ remove_useless_result_rtes(PlannerInfo *root)
 	 * RTE_RESULT RTE; otherwise we'll generate a whole-row Var for the
 	 * RTE_RESULT, which the executor has no support for.
 	 */
-	prev = NULL;
-	for (cell = list_head(root->rowMarks); cell; cell = next)
+	foreach(cell, root->rowMarks)
 	{
 		PlanRowMark *rc = (PlanRowMark *) lfirst(cell);
 
-		next = lnext(cell);
 		if (rt_fetch(rc->rti, root->parse->rtable)->rtekind == RTE_RESULT)
-			root->rowMarks = list_delete_cell(root->rowMarks, cell, prev);
-		else
-			prev = cell;
+			root->rowMarks = foreach_delete_current(root->rowMarks, cell);
 	}
 }
 
@@ -2845,17 +2839,14 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
 		FromExpr   *f = (FromExpr *) jtnode;
 		Relids		result_relids = NULL;
 		ListCell   *cell;
-		ListCell   *prev;
-		ListCell   *next;
 
 		/*
 		 * We can drop RTE_RESULT rels from the fromlist so long as at least
 		 * one child remains, since joining to a one-row table changes
 		 * nothing.  The easiest way to mechanize this rule is to modify the
-		 * list in-place, using list_delete_cell.
+		 * list in-place.
 		 */
-		prev = NULL;
-		for (cell = list_head(f->fromlist); cell; cell = next)
+		foreach(cell, f->fromlist)
 		{
 			Node	   *child = (Node *) lfirst(cell);
 			int			varno;
@@ -2864,7 +2855,6 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
 			child = remove_useless_results_recurse(root, child);
 			/* ... and stick it back into the tree */
 			lfirst(cell) = child;
-			next = lnext(cell);
 
 			/*
 			 * If it's an RTE_RESULT with at least one sibling, we can drop
@@ -2874,11 +2864,9 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode)
 			if (list_length(f->fromlist) > 1 &&
 				(varno = get_result_relid(root, child)) != 0)
 			{
-				f->fromlist = list_delete_cell(f->fromlist, cell, prev);
+				f->fromlist = foreach_delete_current(f->fromlist, cell);
 				result_relids = bms_add_member(result_relids, varno);
 			}
-			else
-				prev = cell;
 		}
 
 		/*
diff --git a/src/backend/optimizer/prep/preptlist.c b/src/backend/optimizer/prep/preptlist.c
index 05172ff0234..792ae393d97 100644
--- a/src/backend/optimizer/prep/preptlist.c
+++ b/src/backend/optimizer/prep/preptlist.c
@@ -285,7 +285,7 @@ expand_targetlist(List *tlist, int command_type,
 			if (!old_tle->resjunk && old_tle->resno == attrno)
 			{
 				new_tle = old_tle;
-				tlist_item = lnext(tlist_item);
+				tlist_item = lnext(tlist, tlist_item);
 			}
 		}
 
@@ -410,7 +410,7 @@ expand_targetlist(List *tlist, int command_type,
 		}
 		new_tlist = lappend(new_tlist, old_tle);
 		attrno++;
-		tlist_item = lnext(tlist_item);
+		tlist_item = lnext(tlist, tlist_item);
 	}
 
 	return new_tlist;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index cd9d49c1f79..61120778516 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -1310,7 +1310,7 @@ generate_append_tlist(List *colTypes, List *colCollations,
 				/* types disagree, so force typmod to -1 */
 				colTypmods[colindex] = -1;
 			}
-			curColType = lnext(curColType);
+			curColType = lnext(colTypes, curColType);
 			colindex++;
 		}
 		Assert(curColType == NULL);
@@ -1410,7 +1410,7 @@ generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
 		/* non-resjunk columns should have grouping clauses */
 		Assert(lg != NULL);
 		sgc = (SortGroupClause *) lfirst(lg);
-		lg = lnext(lg);
+		lg = lnext(grouplist, lg);
 		Assert(sgc->tleSortGroupRef == 0);
 
 		sgc->tleSortGroupRef = tle->ressortgroupref;
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index d78f4e64c1b..f0e789f37e6 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -5255,7 +5255,7 @@ tlist_matches_coltypelist(List *tlist, List *coltypelist)
 			return false;		/* too many tlist items */
 
 		coltype = lfirst_oid(clistitem);
-		clistitem = lnext(clistitem);
+		clistitem = lnext(coltypelist, clistitem);
 
 		if (exprType((Node *) tle->expr) != coltype)
 			return false;		/* column type mismatch */
diff --git a/src/backend/optimizer/util/paramassign.c b/src/backend/optimizer/util/paramassign.c
index 838587c2b8d..536d80a2756 100644
--- a/src/backend/optimizer/util/paramassign.c
+++ b/src/backend/optimizer/util/paramassign.c
@@ -510,17 +510,12 @@ identify_current_nestloop_params(PlannerInfo *root, Relids leftrelids)
 {
 	List	   *result;
 	ListCell   *cell;
-	ListCell   *prev;
-	ListCell   *next;
 
 	result = NIL;
-	prev = NULL;
-	for (cell = list_head(root->curOuterParams); cell; cell = next)
+	foreach(cell, root->curOuterParams)
 	{
 		NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
 
-		next = lnext(cell);
-
 		/*
 		 * We are looking for Vars and PHVs that can be supplied by the
 		 * lefthand rels.  The "bms_overlap" test is just an optimization to
@@ -529,8 +524,8 @@ identify_current_nestloop_params(PlannerInfo *root, Relids leftrelids)
 		if (IsA(nlp->paramval, Var) &&
 			bms_is_member(nlp->paramval->varno, leftrelids))
 		{
-			root->curOuterParams = list_delete_cell(root->curOuterParams,
-													cell, prev);
+			root->curOuterParams = foreach_delete_current(root->curOuterParams,
+														  cell);
 			result = lappend(result, nlp);
 		}
 		else if (IsA(nlp->paramval, PlaceHolderVar) &&
@@ -541,12 +536,10 @@ identify_current_nestloop_params(PlannerInfo *root, Relids leftrelids)
 													 false)->ph_eval_at,
 							   leftrelids))
 		{
-			root->curOuterParams = list_delete_cell(root->curOuterParams,
-													cell, prev);
+			root->curOuterParams = foreach_delete_current(root->curOuterParams,
+														  cell);
 			result = lappend(result, nlp);
 		}
-		else
-			prev = cell;
 	}
 	return result;
 }
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d884d2bb000..67254c2fd91 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -423,11 +423,9 @@ void
 add_path(RelOptInfo *parent_rel, Path *new_path)
 {
 	bool		accept_new = true;	/* unless we find a superior old path */
-	ListCell   *insert_after = NULL;	/* where to insert new item */
+	int			insert_at = 0;	/* where to insert new item */
 	List	   *new_path_pathkeys;
 	ListCell   *p1;
-	ListCell   *p1_prev;
-	ListCell   *p1_next;
 
 	/*
 	 * This is a convenient place to check for query cancel --- no part of the
@@ -442,12 +440,8 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 	 * Loop to check proposed new path against old paths.  Note it is possible
 	 * for more than one old path to be tossed out because new_path dominates
 	 * it.
-	 *
-	 * We can't use foreach here because the loop body may delete the current
-	 * list cell.
 	 */
-	p1_prev = NULL;
-	for (p1 = list_head(parent_rel->pathlist); p1 != NULL; p1 = p1_next)
+	foreach(p1, parent_rel->pathlist)
 	{
 		Path	   *old_path = (Path *) lfirst(p1);
 		bool		remove_old = false; /* unless new proves superior */
@@ -455,8 +449,6 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		PathKeysComparison keyscmp;
 		BMS_Comparison outercmp;
 
-		p1_next = lnext(p1);
-
 		/*
 		 * Do a fuzzy cost comparison with standard fuzziness limit.
 		 */
@@ -593,23 +585,20 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		 */
 		if (remove_old)
 		{
-			parent_rel->pathlist = list_delete_cell(parent_rel->pathlist,
-													p1, p1_prev);
+			parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist,
+														  p1);
 
 			/*
 			 * Delete the data pointed-to by the deleted cell, if possible
 			 */
 			if (!IsA(old_path, IndexPath))
 				pfree(old_path);
-			/* p1_prev does not advance */
 		}
 		else
 		{
 			/* new belongs after this old path if it has cost >= old's */
 			if (new_path->total_cost >= old_path->total_cost)
-				insert_after = p1;
-			/* p1_prev advances */
-			p1_prev = p1;
+				insert_at = foreach_current_index(p1) + 1;
 		}
 
 		/*
@@ -624,10 +613,8 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 	if (accept_new)
 	{
 		/* Accept the new path: insert it at proper place in pathlist */
-		if (insert_after)
-			lappend_cell(parent_rel->pathlist, insert_after, new_path);
-		else
-			parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
+		parent_rel->pathlist =
+			list_insert_nth(parent_rel->pathlist, insert_at, new_path);
 	}
 	else
 	{
@@ -763,10 +750,8 @@ void
 add_partial_path(RelOptInfo *parent_rel, Path *new_path)
 {
 	bool		accept_new = true;	/* unless we find a superior old path */
-	ListCell   *insert_after = NULL;	/* where to insert new item */
+	int			insert_at = 0;	/* where to insert new item */
 	ListCell   *p1;
-	ListCell   *p1_prev;
-	ListCell   *p1_next;
 
 	/* Check for query cancel. */
 	CHECK_FOR_INTERRUPTS();
@@ -781,16 +766,12 @@ add_partial_path(RelOptInfo *parent_rel, Path *new_path)
 	 * As in add_path, throw out any paths which are dominated by the new
 	 * path, but throw out the new path if some existing path dominates it.
 	 */
-	p1_prev = NULL;
-	for (p1 = list_head(parent_rel->partial_pathlist); p1 != NULL;
-		 p1 = p1_next)
+	foreach(p1, parent_rel->partial_pathlist)
 	{
 		Path	   *old_path = (Path *) lfirst(p1);
 		bool		remove_old = false; /* unless new proves superior */
 		PathKeysComparison keyscmp;
 
-		p1_next = lnext(p1);
-
 		/* Compare pathkeys. */
 		keyscmp = compare_pathkeys(new_path->pathkeys, old_path->pathkeys);
 
@@ -841,17 +822,14 @@ add_partial_path(RelOptInfo *parent_rel, Path *new_path)
 		if (remove_old)
 		{
 			parent_rel->partial_pathlist =
-				list_delete_cell(parent_rel->partial_pathlist, p1, p1_prev);
+				foreach_delete_current(parent_rel->partial_pathlist, p1);
 			pfree(old_path);
-			/* p1_prev does not advance */
 		}
 		else
 		{
 			/* new belongs after this old path if it has cost >= old's */
 			if (new_path->total_cost >= old_path->total_cost)
-				insert_after = p1;
-			/* p1_prev advances */
-			p1_prev = p1;
+				insert_at = foreach_current_index(p1) + 1;
 		}
 
 		/*
@@ -866,11 +844,8 @@ add_partial_path(RelOptInfo *parent_rel, Path *new_path)
 	if (accept_new)
 	{
 		/* Accept the new path: insert it at proper place */
-		if (insert_after)
-			lappend_cell(parent_rel->partial_pathlist, insert_after, new_path);
-		else
-			parent_rel->partial_pathlist =
-				lcons(new_path, parent_rel->partial_pathlist);
+		parent_rel->partial_pathlist =
+			list_insert_nth(parent_rel->partial_pathlist, insert_at, new_path);
 	}
 	else
 	{
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 40f497660d1..6ea625a148c 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -1742,7 +1742,7 @@ build_index_tlist(PlannerInfo *root, IndexOptInfo *index,
 			if (indexpr_item == NULL)
 				elog(ERROR, "wrong number of index expressions");
 			indexvar = (Expr *) lfirst(indexpr_item);
-			indexpr_item = lnext(indexpr_item);
+			indexpr_item = lnext(index->indexprs, indexpr_item);
 		}
 
 		tlist = lappend(tlist,
@@ -2301,7 +2301,7 @@ set_baserel_partition_key_exprs(Relation relation,
 			/* Re-stamp the expression with given varno. */
 			partexpr = (Expr *) copyObject(lfirst(lc));
 			ChangeVarNodes((Node *) partexpr, 1, varno, 0);
-			lc = lnext(lc);
+			lc = lnext(partkey->partexprs, lc);
 		}
 
 		partexprs[cnt] = list_make1(partexpr);
diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index b81eba72191..08a160fff60 100644
--- a/src/backend/optimizer/util/predtest.c
+++ b/src/backend/optimizer/util/predtest.c
@@ -59,6 +59,7 @@ typedef struct PredIterInfoData
 {
 	/* node-type-specific iteration state */
 	void	   *state;
+	List	   *state_list;
 	/* initialize to do the iteration */
 	void		(*startup_fn) (Node *clause, PredIterInfo info);
 	/* next-component iteration function */
@@ -905,7 +906,8 @@ predicate_classify(Node *clause, PredIterInfo info)
 static void
 list_startup_fn(Node *clause, PredIterInfo info)
 {
-	info->state = (void *) list_head((List *) clause);
+	info->state_list = (List *) clause;
+	info->state = (void *) list_head(info->state_list);
 }
 
 static Node *
@@ -917,7 +919,7 @@ list_next_fn(PredIterInfo info)
 	if (l == NULL)
 		return NULL;
 	n = lfirst(l);
-	info->state = (void *) lnext(l);
+	info->state = (void *) lnext(info->state_list, l);
 	return n;
 }
 
@@ -934,7 +936,8 @@ list_cleanup_fn(PredIterInfo info)
 static void
 boolexpr_startup_fn(Node *clause, PredIterInfo info)
 {
-	info->state = (void *) list_head(((BoolExpr *) clause)->args);
+	info->state_list = ((BoolExpr *) clause)->args;
+	info->state = (void *) list_head(info->state_list);
 }
 
 /*
@@ -1057,6 +1060,7 @@ arrayexpr_startup_fn(Node *clause, PredIterInfo info)
 
 	/* Initialize iteration variable to first member of ArrayExpr */
 	arrayexpr = (ArrayExpr *) lsecond(saop->args);
+	info->state_list = arrayexpr->elements;
 	state->next = list_head(arrayexpr->elements);
 }
 
@@ -1068,7 +1072,7 @@ arrayexpr_next_fn(PredIterInfo info)
 	if (state->next == NULL)
 		return NULL;
 	lsecond(state->opexpr.args) = lfirst(state->next);
-	state->next = lnext(state->next);
+	state->next = lnext(info->state_list, state->next);
 	return (Node *) &(state->opexpr);
 }
 
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index 41402821a15..7ccb10e4e1b 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -287,7 +287,7 @@ tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
 				return false;	/* tlist longer than colTypes */
 			if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
 				return false;
-			curColType = lnext(curColType);
+			curColType = lnext(colTypes, curColType);
 		}
 	}
 	if (curColType != NULL)
@@ -321,7 +321,7 @@ tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
 				return false;	/* tlist longer than colCollations */
 			if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
 				return false;
-			curColColl = lnext(curColColl);
+			curColColl = lnext(colCollations, curColColl);
 		}
 	}
 	if (curColColl != NULL)
@@ -1022,7 +1022,7 @@ split_pathtarget_at_srfs(PlannerInfo *root,
 		List	   *level_srfs = (List *) lfirst(lc1);
 		PathTarget *ntarget;
 
-		if (lnext(lc1) == NULL)
+		if (lnext(context.level_srfs, lc1) == NULL)
 		{
 			ntarget = target;
 		}
@@ -1037,13 +1037,15 @@ split_pathtarget_at_srfs(PlannerInfo *root,
 			 * later levels.
 			 */
 			add_sp_items_to_pathtarget(ntarget, level_srfs);
-			for_each_cell(lc, lnext(lc2))
+			for_each_cell(lc, context.level_input_vars,
+						  lnext(context.level_input_vars, lc2))
 			{
 				List	   *input_vars = (List *) lfirst(lc);
 
 				add_sp_items_to_pathtarget(ntarget, input_vars);
 			}
-			for_each_cell(lc, lnext(lc3))
+			for_each_cell(lc, context.level_input_srfs,
+						  lnext(context.level_input_srfs, lc3))
 			{
 				List	   *input_srfs = (List *) lfirst(lc);
 				ListCell   *lcx;