From 4bc0c6d0ef14006b2dea8db871ba0e4a247bec71 Mon Sep 17 00:00:00 2001
From: Alexander Kuzmenkov <36882414+akuzm@users.noreply.github.com>
Date: Wed, 22 Jan 2025 16:33:40 +0100
Subject: [PATCH v1] Fix quadratic equivalence member search for partitioned
 tables

Currently the find_ec_member_matching_expr() uses a linear search. When
creating ordered paths for a partitioned table, the total time taken by
this linear search becomes effectively quadratic in the number of
partitions, which starts seriously affecting the planning performance
after we hit 1k partitions. Ideally, ec_members should be a hash table,
but as a quick fix, we can make use of the fact that this search usually
looks up the either the same EM as before, or the next one, and start
the search from the previous position. This speeds up the common case.
---
 src/backend/optimizer/path/equivclass.c | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 7cafaca33c..9d8fb5e40d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -764,16 +764,26 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
 							 Expr *expr,
 							 Relids relids)
 {
-	ListCell   *lc;
-
 	/* We ignore binary-compatible relabeling on both ends */
 	while (expr && IsA(expr, RelabelType))
 		expr = ((RelabelType *) expr)->arg;
 
-	foreach(lc, ec->ec_members)
+	/*
+	 * When creating ordered paths for a partitioned table, the total time taken
+	 * by this linear search becomes effectively quadratic in the number of
+	 * partitions, which starts seriously affecting the planning performance
+	 * after we hit 1k partitions. Ideally, ec_members should be a hash table,
+	 * but as a quick fix, we can make use of the fact that this search usually
+	 * looks up the either the same EM as before, or the next one, and start the
+	 * search from the previous position. This speeds up the common case.
+	 */
+	static int previous_em_found_at = 0;
+	int n = list_length(ec->ec_members);
+	for(int search_offset = 0; search_offset < n; search_offset++)
 	{
-		EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
-		Expr	   *emexpr;
+		const int current_position = (search_offset + previous_em_found_at) % n;
+		EquivalenceMember *em = list_nth_node(EquivalenceMember, ec->ec_members,
+			current_position);
 
 		/*
 		 * We shouldn't be trying to sort by an equivalence class that
@@ -792,12 +802,15 @@ find_ec_member_matching_expr(EquivalenceClass *ec,
 		/*
 		 * Match if same expression (after stripping relabel).
 		 */
-		emexpr = em->em_expr;
+		Expr *emexpr = em->em_expr;
 		while (emexpr && IsA(emexpr, RelabelType))
 			emexpr = ((RelabelType *) emexpr)->arg;
 
 		if (equal(emexpr, expr))
+		{
+			previous_em_found_at = current_position;
 			return em;
+		}
 	}
 
 	return NULL;
-- 
2.34.1