choose-bitmap-and.patch

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index f295558..da5a98e 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1371,7 +1371,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 {
 	int			npaths = list_length(paths);
 	PathClauseUsage **pathinfoarray;
-	PathClauseUsage *pathinfo;
+	PathClauseUsage *pathinfo = NULL;
 	List	   *clauselist;
 	List	   *bestpaths = NIL;
 	Cost		bestcost = 0;
@@ -1431,6 +1431,10 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 	 * regular qual clauses too, to have a more intelligent, but much more
 	 * expensive, check for redundancy --- but in most cases simple equality
 	 * seems to suffice.)
+	 *
+	 * It is too slow to compare paths by clause usage if there are too many
+	 * clauses, so in that case we skip the above algorithm and just return
+	 * the cheapest input path.
 	 */
 
 	/*
@@ -1447,6 +1451,14 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 		Path	   *ipath = (Path *) lfirst(l);
 
 		pathinfo = classify_index_clause_usage(ipath, &clauselist);
+
+		/*
+		 * There are too many clauses to classify efficiently, switch
+		 * to a simpler algorithm.
+		 */
+		if (pathinfo == NULL)
+			break;
+
 		for (i = 0; i < npaths; i++)
 		{
 			if (bms_equal(pathinfo->clauseids, pathinfoarray[i]->clauseids))
@@ -1476,6 +1488,27 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 	if (npaths == 1)
 		return pathinfoarray[0]->path;
 
+	/*
+	 * If there are too many different clauses to classify efficiently,
+	 * just return the cheapest input path.
+	 */
+	if (pathinfo == NULL)
+	{
+		Path *bestPath = NULL;
+		Cost bestCost = 0.;
+		foreach(l, paths)
+		{
+			Path *path = (Path *) lfirst(l);
+			Cost cost = bitmap_and_cost_est(root, rel, list_make1(path));
+			if (bestPath == NULL || cost < bestCost)
+			{
+				bestCost = cost;
+				bestPath = path;
+			}
+		}
+		return bestPath;
+	}
+
 	/* Sort the surviving paths by index access cost */
 	qsort(pathinfoarray, npaths, sizeof(PathClauseUsage *),
 		  path_usage_comparator);
@@ -1695,6 +1728,17 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
  * *clauselist is used and expanded as needed to identify all the distinct
  * clauses seen across successive calls.  Caller must initialize it to NIL
  * before first call of a set.
+ *
+ * We use linear search in list to find clauses in clauselist, so the time
+ * to classify the clauses grows quadratically with their number. To control
+ * the run time, this function returns NULL after clauselist length reaches
+ * some threshold, so that the caller can switch to a simpler algorithm.
+ *
+ * It could be possible to use a tree or a hash table instead of list to
+ * allows faster lookups, but we don't have comparison or hash function for
+ * the nodes. The nodeToString() is not suitable because the equality of string
+ * representation is not the same ad nodes being equal(). The string includes
+ * some fields that are ignored by equal(), such as token location.
  */
 static PathClauseUsage *
 classify_index_clause_usage(Path *path, List **clauselist)
@@ -1711,6 +1755,13 @@ classify_index_clause_usage(Path *path, List **clauselist)
 	result->preds = NIL;
 	find_indexpath_quals(path, &result->quals, &result->preds);
 
+	/* Bail out if there are too many clauses to classify efficiently */
+	if (list_length(result->quals) + list_length(result->preds)
+		+ list_length(*clauselist) > 1000)
+	{
+		return NULL;
+	}
+
 	/* Build up a bitmapset representing the quals and preds */
 	clauseids = NULL;
 	foreach(lc, result->quals)