list_skip_forward_v0.patch

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index dae7a842a1..7f4cc2add8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -68,6 +68,7 @@ static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
 							  Relids relids);
 static void delete_eclass(PlannerInfo *root, EquivalenceClass *ec,
 			  int ec_index);
+static ListCell *list_skip_forward(ListCell *lc, int forward);
 
 
 /*
@@ -1131,7 +1132,8 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 	Bitmapset  *inner_ecs;
 	Bitmapset  *join_ecs;
 	Bitmapset  *matching_ecs;
-	int			i;
+	int			i, last;
+	ListCell   *lc;
 
 	/* If inner rel is a child, extra setup work is needed */
 	if (IS_OTHER_REL(inner_rel))
@@ -1155,12 +1157,18 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 	/* Determine all eclasses in common between inner rels and join rels */
 	matching_ecs = bms_int_members(inner_ecs, join_ecs);
 
+	lc = list_head(root->eq_classes);
+	last = 0;
 	i = -1;
 	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
+		EquivalenceClass *ec;
 		List	   *sublist = NIL;
 
+		lc = list_skip_forward(lc, i - last);
+		last = i;
+		ec = (EquivalenceClass *) lfirst(lc);
+
 		/* ECs containing consts do not need any further enforcement */
 		if (ec->ec_has_const)
 			continue;
@@ -2080,19 +2088,26 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 	Oid			eqop = fkinfo->conpfeqop[colno];
 	List	   *opfamilies = NIL;	/* compute only if needed */
 	Bitmapset  *matching_ecs;
-	int			i;
+	int			i, last;
+	ListCell   *lc;
 
 	/* Determine which eclasses contain members for both of the relations */
 	matching_ecs = bms_intersect(root->simple_rel_array[var1varno]->eclass_indexes,
 								 root->simple_rel_array[var2varno]->eclass_indexes);
 
+	lc = list_head(root->eq_classes);
+	last = 0;
 	i = -1;
 	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
+		EquivalenceClass *ec;
 		bool		item1member = false;
 		bool		item2member = false;
-		ListCell   *lc;
+		ListCell   *lc2;
+
+		lc = list_skip_forward(lc, i - last);
+		last = i;
+		ec = (EquivalenceClass *) lfirst(lc);
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
@@ -2102,9 +2117,9 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 		/* Ensure no corruption of eclass_indexes */
 		Assert(bms_is_member(var1varno, ec->ec_relids));
 		Assert(bms_is_member(var2varno, ec->ec_relids));
-		foreach(lc, ec->ec_members)
+		foreach(lc2, ec->ec_members)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 			Var		   *var;
 
 			if (em->em_is_child)
@@ -2273,7 +2288,8 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	List	   *result = NIL;
 	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
 	Relids		parent_relids;
-	int			i;
+	int			i, last;
+	ListCell   *lc;
 
 	/* Indexes are available only on base or "other" member relations. */
 	Assert(IS_SIMPLE_REL(rel));
@@ -2284,12 +2300,18 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 	else
 		parent_relids = NULL;	/* not used, but keep compiler quiet */
 
+	lc = list_head(root->eq_classes);
+	last = 0;
 	i = -1;
 	while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
 	{
-		EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
+		EquivalenceClass *cur_ec;
 		EquivalenceMember *cur_em;
-		ListCell   *lc;
+		ListCell   *lc2;
+
+		lc = list_skip_forward(lc, i - last);
+		last = i;
+		cur_ec = (EquivalenceClass *) lfirst(lc);
 
 		/*
 		 * Won't generate joinclauses if const or single-member (the latter
@@ -2316,9 +2338,9 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * match.  See also get_eclass_for_sort_expr.)
 		 */
 		cur_em = NULL;
-		foreach(lc, cur_ec->ec_members)
+		foreach(lc2, cur_ec->ec_members)
 		{
-			cur_em = (EquivalenceMember *) lfirst(lc);
+			cur_em = (EquivalenceMember *) lfirst(lc2);
 			if (bms_equal(cur_em->em_relids, rel->relids) &&
 				callback(root, rel, cur_ec, cur_em, callback_arg))
 				break;
@@ -2332,9 +2354,9 @@ generate_implied_equalities_for_column(PlannerInfo *root,
 		 * Found our match.  Scan the other EC members and attempt to generate
 		 * joinclauses.
 		 */
-		foreach(lc, cur_ec->ec_members)
+		foreach(lc2, cur_ec->ec_members)
 		{
-			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc);
+			EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
 			Oid			eq_op;
 			RestrictInfo *rinfo;
 
@@ -2401,7 +2423,8 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 	Bitmapset	   *rel1_ecs;
 	Bitmapset	   *rel2_ecs;
 	Bitmapset	   *matching_ecs;
-	int				i;
+	int				i, last;
+	ListCell	   *lc;
 
 	rel1_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
 	rel2_ecs = get_eclass_indexes_for_relids(root, rel2->relids);
@@ -2409,10 +2432,16 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 
 	/* XXX or can we just return bms_overlap(rel1_ecs, rel2_ecs) ? */
 
+	lc = list_head(root->eq_classes);
+	last = 0;
 	i = -1;
 	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
+		EquivalenceClass *ec;
+
+		lc = list_skip_forward(lc, i - last);
+		last = i;
+		ec = (EquivalenceClass *) lfirst(lc);
 
 		/*
 		 * Won't generate joinclauses if single-member (this test covers the
@@ -2468,18 +2497,24 @@ bool
 has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
 {
 	Bitmapset	   *matched_ecs;
-	int				i;
+	int			i, last;
+	ListCell   *lc;
 
 	if (IS_SIMPLE_REL(rel1))
 		matched_ecs = rel1->eclass_indexes;
 	else
 		matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
 
+	lc = list_head(root->eq_classes);
+	last = 0;
 	i = -1;
 	while ((i = bms_next_member(matched_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
+		EquivalenceClass *ec;
 
+		lc = list_skip_forward(lc, i - last);
+		last = i;
+		ec = (EquivalenceClass *) lfirst(lc);
 		/*
 		 * Won't generate joinclauses if single-member (this test covers the
 		 * volatile case too)
@@ -2716,3 +2751,12 @@ delete_eclass(PlannerInfo *root, EquivalenceClass *ec, int ec_index)
 	ec->ec_derives = NIL;
 	ec->ec_relids = NULL;
 }
+
+/* XXX remove when list_nth is O(1) */
+static ListCell *
+list_skip_forward(ListCell *lc, int forward)
+{
+	while (forward--)
+		lc = lnext(lc);
+	return lc;
+}