gin-scalar-estimates.patch

diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
index e7af7d4..250d853 100644
--- a/contrib/pg_trgm/expected/pg_trgm.out
+++ b/contrib/pg_trgm/expected/pg_trgm.out
@@ -3486,6 +3486,16 @@ explain (costs off)
          Index Cond: (t ~~* '%BCD%'::text)
 (4 rows)
 
+explain (costs off)
+  select * from test2 where t like any ('{%bcd%,qua%}');
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Bitmap Heap Scan on test2
+   Recheck Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[]))
+   ->  Bitmap Index Scan on test2_idx_gin
+         Index Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[]))
+(4 rows)
+
 select * from test2 where t like '%BCD%';
  t 
 ---
@@ -3509,6 +3519,13 @@ select * from test2 where t ilike 'qua%';
  quark
 (1 row)
 
+select * from test2 where t like any ('{%bcd%,qua%}');
+   t    
+--------
+ abcdef
+ quark
+(2 rows)
+
 drop index test2_idx_gin;
 create index test2_idx_gist on test2 using gist (t gist_trgm_ops);
 set enable_seqscan=off;
@@ -3528,6 +3545,16 @@ explain (costs off)
    Index Cond: (t ~~* '%BCD%'::text)
 (2 rows)
 
+explain (costs off)
+  select * from test2 where t like any ('{%bcd%,qua%}');
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Bitmap Heap Scan on test2
+   Recheck Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[]))
+   ->  Bitmap Index Scan on test2_idx_gist
+         Index Cond: (t ~~ ANY ('{%bcd%,qua%}'::text[]))
+(4 rows)
+
 select * from test2 where t like '%BCD%';
  t 
 ---
@@ -3551,3 +3578,10 @@ select * from test2 where t ilike 'qua%';
  quark
 (1 row)
 
+select * from test2 where t like any ('{%bcd%,qua%}');
+   t    
+--------
+ abcdef
+ quark
+(2 rows)
+
diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sql
index ea902f6..ac969e6 100644
--- a/contrib/pg_trgm/sql/pg_trgm.sql
+++ b/contrib/pg_trgm/sql/pg_trgm.sql
@@ -47,10 +47,13 @@ explain (costs off)
   select * from test2 where t like '%BCD%';
 explain (costs off)
   select * from test2 where t ilike '%BCD%';
+explain (costs off)
+  select * from test2 where t like any ('{%bcd%,qua%}');
 select * from test2 where t like '%BCD%';
 select * from test2 where t like '%bcd%';
 select * from test2 where t ilike '%BCD%';
 select * from test2 where t ilike 'qua%';
+select * from test2 where t like any ('{%bcd%,qua%}');
 drop index test2_idx_gin;
 create index test2_idx_gist on test2 using gist (t gist_trgm_ops);
 set enable_seqscan=off;
@@ -58,7 +61,10 @@ explain (costs off)
   select * from test2 where t like '%BCD%';
 explain (costs off)
   select * from test2 where t ilike '%BCD%';
+explain (costs off)
+  select * from test2 where t like any ('{%bcd%,qua%}');
 select * from test2 where t like '%BCD%';
 select * from test2 where t like '%bcd%';
 select * from test2 where t ilike '%BCD%';
 select * from test2 where t ilike 'qua%';
+select * from test2 where t like any ('{%bcd%,qua%}');
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index d06809e..64b732e 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6591,6 +6591,70 @@ find_index_column(Node *op, IndexOptInfo *index)
 }
 
 /*
+ * Estimate gin costs for a single search value. Returns false if no match
+ * is possible, true otherwise. All pointer arguments must be initialized by
+ * the caller.
+ */
+static bool
+gin_costestimate_search(Oid extractProcOid, Datum value, int strategy_op,
+						double numEntries, double *partialEntriesInQuals,
+						double *exactEntriesInQuals,
+						double *searchEntriesInQuals, bool *haveFullScan)
+{
+	int32		nentries = 0;
+	bool	   *partial_matches = NULL;
+	Pointer    *extra_data = NULL;
+	bool	   *nullFlags = NULL;
+	int32		searchMode = GIN_SEARCH_MODE_DEFAULT;
+	int32		i;
+
+	OidFunctionCall7(extractProcOid,
+					 value,
+					 PointerGetDatum(&nentries),
+					 UInt16GetDatum(strategy_op),
+					 PointerGetDatum(&partial_matches),
+					 PointerGetDatum(&extra_data),
+					 PointerGetDatum(&nullFlags),
+					 PointerGetDatum(&searchMode));
+
+	if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
+		return false;
+
+	for (i = 0; i < nentries; i++)
+	{
+		/*
+		 * For partial match we haven't any information to estimate
+		 * number of matched entries in index, so, we just estimate it
+		 * as 100
+		 */
+		if (partial_matches && partial_matches[i])
+			*partialEntriesInQuals += 100;
+		else
+			(*exactEntriesInQuals)++;
+
+		(*searchEntriesInQuals)++;
+	}
+
+	if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
+	{
+		/* Treat "include empty" like an exact-match item */
+		(*exactEntriesInQuals)++;
+		(*searchEntriesInQuals)++;
+	}
+	else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
+	{
+		/*
+		 * It's GIN_SEARCH_MODE_ALL, full index scan will be required.  We
+		 * treat this as if every key in the index had been listed in the
+		 * query; is that reasonable?
+		 */
+		*searchEntriesInQuals += numEntries;
+	}
+
+	return true;
+}
+
+/*
  * GIN has search behavior completely different from other index types
  */
 Datum
@@ -6613,7 +6677,8 @@ gincostestimate(PG_FUNCTION_ARGS)
 				numDataPages,
 				numPendingPages,
 				numEntries;
-	bool		haveFullScan = false;
+	bool		haveFullScan = false,
+				matchPossible = true;
 	double		partialEntriesInQuals = 0.0;
 	double		searchEntriesInQuals = 0.0;
 	double		exactEntriesInQuals = 0.0;
@@ -6623,7 +6688,8 @@ gincostestimate(PG_FUNCTION_ARGS)
 	double		qual_op_cost,
 				qual_arg_cost,
 				spc_random_page_cost,
-				num_scans;
+				outer_scans,
+				array_scans = 1.0;
 	QualCost	index_qual_cost;
 	Relation	indexRel;
 	GinStatsData ginStats;
@@ -6721,19 +6787,31 @@ gincostestimate(PG_FUNCTION_ARGS)
 		int			strategy_op;
 		Oid			lefttype,
 					righttype;
-		int32		nentries = 0;
-		bool	   *partial_matches = NULL;
-		Pointer    *extra_data = NULL;
-		bool	   *nullFlags = NULL;
-		int32		searchMode = GIN_SEARCH_MODE_DEFAULT;
 		int			indexcol;
 
 		Assert(IsA(rinfo, RestrictInfo));
 		clause = rinfo->clause;
-		Assert(IsA(clause, OpExpr));
-		leftop = get_leftop(clause);
-		rightop = get_rightop(clause);
-		clause_op = ((OpExpr *) clause)->opno;
+
+		if (IsA(clause, OpExpr))
+		{
+			leftop = get_leftop(clause);
+			rightop = get_rightop(clause);
+			clause_op = ((OpExpr *) clause)->opno;
+		}
+		else if (IsA(clause, ScalarArrayOpExpr))
+		{
+			ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+
+			leftop = (Node *) linitial(saop->args);
+			rightop = (Node *) lsecond(saop->args);
+			clause_op = saop->opno;
+		}
+		else
+		{
+			elog(ERROR, "unsupported GIN indexqual type: %d",
+				 (int) nodeTag(clause));
+			continue;			/* keep compiler quiet */
+		}
 
 		if ((indexcol = find_index_column(leftop, index)) >= 0)
 		{
@@ -6761,16 +6839,18 @@ gincostestimate(PG_FUNCTION_ARGS)
 		if (!IsA(operand, Const))
 		{
 			searchEntriesInQuals++;
+
+			if (IsA(rinfo->clause, ScalarArrayOpExpr))
+				array_scans *= estimate_array_length(operand);
+
 			continue;
 		}
 
 		/* If Const is null, there can be no matches */
 		if (((Const *) operand)->constisnull)
 		{
-			*indexStartupCost = 0;
-			*indexTotalCost = 0;
-			*indexSelectivity = 0;
-			PG_RETURN_VOID();
+			matchPossible = false;
+			break;
 		}
 
 		/*
@@ -6800,57 +6880,102 @@ gincostestimate(PG_FUNCTION_ARGS)
 				 get_rel_name(index->indexoid));
 		}
 
-		OidFunctionCall7(extractProcOid,
-						 ((Const *) operand)->constvalue,
-						 PointerGetDatum(&nentries),
-						 UInt16GetDatum(strategy_op),
-						 PointerGetDatum(&partial_matches),
-						 PointerGetDatum(&extra_data),
-						 PointerGetDatum(&nullFlags),
-						 PointerGetDatum(&searchMode));
-
-		if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
+		if (IsA(rinfo->clause, OpExpr))
 		{
-			/* No match is possible */
-			*indexStartupCost = 0;
-			*indexTotalCost = 0;
-			*indexSelectivity = 0;
-			PG_RETURN_VOID();
+			matchPossible =
+				gin_costestimate_search(extractProcOid,
+										((Const *) operand)->constvalue,
+										strategy_op,
+										numEntries,
+										&partialEntriesInQuals,
+										&exactEntriesInQuals,
+										&searchEntriesInQuals,
+										&haveFullScan);
+			if (!matchPossible)
+				break;
 		}
-		else
+		else if (IsA(rinfo->clause, ScalarArrayOpExpr))
 		{
-			int32		i;
-
-			for (i = 0; i < nentries; i++)
+			ArrayType  *arrayval;
+			int16		elmlen;
+			bool		elmbyval;
+			char		elmalign;
+			int			numElems;
+			Datum	   *elemValues;
+			bool	   *elemNulls;
+			int			numPossible = 0;
+			int			i;
+			double		partialEntries = 0.0,
+						exactEntries = 0.0,
+						searchEntries = 0.0;
+
+			arrayval = DatumGetArrayTypeP(((Const *) operand)->constvalue);
+			get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
+								 &elmlen, &elmbyval, &elmalign);
+			deconstruct_array(arrayval,
+							  ARR_ELEMTYPE(arrayval),
+							  elmlen, elmbyval, elmalign,
+							  &elemValues, &elemNulls, &numElems);
+
+			for (i = 0; i < numElems; i++)
 			{
-				/*
-				 * For partial match we haven't any information to estimate
-				 * number of matched entries in index, so, we just estimate it
-				 * as 100
-				 */
-				if (partial_matches && partial_matches[i])
-					partialEntriesInQuals += 100;
-				else
-					exactEntriesInQuals++;
+				bool		elemMatchPossible;
+
+				/* NULL can't match anything */
+				if (elemNulls[i])
+					continue;
 
-				searchEntriesInQuals++;
+				elemMatchPossible =
+					gin_costestimate_search(extractProcOid,
+											elemValues[i],
+											strategy_op,
+											numEntries,
+											&partialEntries,
+											&exactEntries,
+											&searchEntries,
+											&haveFullScan);
+
+				/* We only count array elements that can return any results */
+				if (elemMatchPossible)
+					numPossible++;
 			}
-		}
 
-		if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
-		{
-			/* Treat "include empty" like an exact-match item */
-			exactEntriesInQuals++;
-			searchEntriesInQuals++;
-		}
-		else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
-		{
-			/* It's GIN_SEARCH_MODE_ALL */
-			haveFullScan = true;
+			if (numPossible == 0)
+			{
+				/* No useful searches in the array */
+				matchPossible = false;
+				break;
+			}
+
+			/*
+			 * When there are multiple scalar expressions in an index scan,
+			 * the executor repeats the index scan for all possible
+			 * combinations (cartesian product) of input arrays. Instead of
+			 * doing that here, we only do a single pass over input arrays and
+			 * calculate the average entries for each scan. That allows us to
+			 * estimate startup cost too.
+			 *
+			 * Later, we multiply average cost by array_scans (the product of
+			 * effective array lengths)
+			 */
+			partialEntriesInQuals += partialEntries / numPossible;
+			exactEntriesInQuals   += exactEntries / numPossible;
+			searchEntriesInQuals  += searchEntries / numPossible;
+
+			array_scans *= numPossible;
 		}
 	}
 
-	if (haveFullScan || indexQuals == NIL)
+	if (!matchPossible)
+	{
+		/* No match is possible */
+		*indexStartupCost = 0;
+		*indexTotalCost = 0;
+		*indexSelectivity = 0;
+		PG_RETURN_VOID();
+	}
+
+	if (indexQuals == NIL)
 	{
 		/*
 		 * Full index scan will be required.  We treat this as if every key in
@@ -6861,9 +6986,9 @@ gincostestimate(PG_FUNCTION_ARGS)
 
 	/* Will we have more than one iteration of a nestloop scan? */
 	if (outer_rel != NULL && outer_rel->rows > 1)
-		num_scans = outer_rel->rows;
+		outer_scans = outer_rel->rows;
 	else
-		num_scans = 1;
+		outer_scans = 1;
 
 	/*
 	 * cost to begin scan, first of all, pay attention to pending list.
@@ -6888,13 +7013,13 @@ gincostestimate(PG_FUNCTION_ARGS)
 
 	/*
 	 * Partial match algorithm reads all data pages before doing actual scan,
-	 * so it's a startup cost. Again, we havn't any useful stats here, so,
+	 * so it's a startup cost. Again, we haven't any useful stats here, so,
 	 * estimate it as proportion
 	 */
 	dataPagesFetched = ceil(numDataPages * partialEntriesInQuals / numEntries);
 
 	/* calculate cache effects */
-	if (num_scans > 1 || searchEntriesInQuals > 1)
+	if (outer_scans > 1 || array_scans > 1 || searchEntriesInQuals > 1)
 	{
 		entryPagesFetched = index_pages_fetched(entryPagesFetched,
 												(BlockNumber) numEntryPages,
@@ -6910,6 +7035,14 @@ gincostestimate(PG_FUNCTION_ARGS)
 	 */
 	*indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
 
+	/*
+	 * Startup cost was estimated with per-scan averages (first scan), but
+	 * total cost needs to account for all rescans of ScalarArrayOpExprs.
+	 */
+	partialEntriesInQuals *= array_scans;
+	exactEntriesInQuals   *= array_scans;
+	searchEntriesInQuals  *= array_scans;
+
 	/* cost to scan data pages for each exact (non-partial) matched entry */
 	dataPagesFetched = ceil(numDataPages * exactEntriesInQuals / numEntries);
 
@@ -6932,7 +7065,7 @@ gincostestimate(PG_FUNCTION_ARGS)
 		dataPagesFetched = dataPagesFetchedBySel;
 	}
 
-	if (num_scans > 1)
+	if (outer_scans > 1 || array_scans > 1)
 		dataPagesFetched = index_pages_fetched(dataPagesFetched,
 											   (BlockNumber) numDataPages,
 											   numDataPages, root);
diff --git a/src/test/regress/expected/tsearch.out b/src/test/regress/expected/tsearch.out
index e1d7646..9341dbe 100644
--- a/src/test/regress/expected/tsearch.out
+++ b/src/test/regress/expected/tsearch.out
@@ -142,6 +142,12 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*';
    494
 (1 row)
 
+SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}');
+ count 
+-------
+   158
+(1 row)
+
 RESET enable_seqscan;
 DROP INDEX wowidx;
 CREATE INDEX wowidx ON test_tsvector USING gin (a);
@@ -188,6 +194,12 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*';
    494
 (1 row)
 
+SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}');
+ count 
+-------
+   158
+(1 row)
+
 RESET enable_seqscan;
 INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH');
 SELECT * FROM ts_stat('SELECT a FROM test_tsvector') ORDER BY ndoc DESC, nentry DESC, word LIMIT 10;
diff --git a/src/test/regress/sql/tsearch.sql b/src/test/regress/sql/tsearch.sql
index d261da2..9fd1207 100644
--- a/src/test/regress/sql/tsearch.sql
+++ b/src/test/regress/sql/tsearch.sql
@@ -60,6 +60,7 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'eq|yt';
 SELECT count(*) FROM test_tsvector WHERE a @@ '(eq&yt)|(wr&qh)';
 SELECT count(*) FROM test_tsvector WHERE a @@ '(eq|yt)&(wr|qh)';
 SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*';
+SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}');
 
 RESET enable_seqscan;
 
@@ -76,6 +77,7 @@ SELECT count(*) FROM test_tsvector WHERE a @@ 'eq|yt';
 SELECT count(*) FROM test_tsvector WHERE a @@ '(eq&yt)|(wr&qh)';
 SELECT count(*) FROM test_tsvector WHERE a @@ '(eq|yt)&(wr|qh)';
 SELECT count(*) FROM test_tsvector WHERE a @@ 'w:*|q:*';
+SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}');
 
 RESET enable_seqscan;
 INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH');