[PATCH] Fix ScalarArrayOpExpr estimation for GIN indexes

diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
new file mode 100644
index e7af7d4..250d853
*** a/contrib/pg_trgm/expected/pg_trgm.out
--- b/contrib/pg_trgm/expected/pg_trgm.out
*************** explain (costs off)
*** 3486,3491 ****
--- 3486,3501 ----
           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 
  ---
*************** select * from test2 where t ilike 'qua%'
*** 3509,3514 ****
--- 3519,3531 ----
   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;
*************** explain (costs off)
*** 3528,3533 ****
--- 3545,3560 ----
     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 
  ---
*************** select * from test2 where t ilike 'qua%'
*** 3551,3553 ****
--- 3578,3587 ----
   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
new file mode 100644
index ea902f6..ac969e6
*** a/contrib/pg_trgm/sql/pg_trgm.sql
--- b/contrib/pg_trgm/sql/pg_trgm.sql
*************** explain (costs off)
*** 47,56 ****
--- 47,59 ----
    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;
*************** explain (costs off)
*** 58,64 ****
--- 61,70 ----
    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
new file mode 100644
index d06809e..4bca715
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** find_index_column(Node *op, IndexOptInfo
*** 6591,6596 ****
--- 6591,6660 ----
  }
  
  /*
+  * 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)
+ {
+ 	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
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6613,6619 ****
  				numDataPages,
  				numPendingPages,
  				numEntries;
! 	bool		haveFullScan = false;
  	double		partialEntriesInQuals = 0.0;
  	double		searchEntriesInQuals = 0.0;
  	double		exactEntriesInQuals = 0.0;
--- 6677,6683 ----
  				numDataPages,
  				numPendingPages,
  				numEntries;
! 	bool		matchPossible = true;
  	double		partialEntriesInQuals = 0.0;
  	double		searchEntriesInQuals = 0.0;
  	double		exactEntriesInQuals = 0.0;
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6623,6629 ****
  	double		qual_op_cost,
  				qual_arg_cost,
  				spc_random_page_cost,
! 				num_scans;
  	QualCost	index_qual_cost;
  	Relation	indexRel;
  	GinStatsData ginStats;
--- 6687,6694 ----
  	double		qual_op_cost,
  				qual_arg_cost,
  				spc_random_page_cost,
! 				outer_scans,
! 				array_scans = 1.0;
  	QualCost	index_qual_cost;
  	Relation	indexRel;
  	GinStatsData ginStats;
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6721,6739 ****
  		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 ((indexcol = find_index_column(leftop, index)) >= 0)
  		{
--- 6786,6816 ----
  		int			strategy_op;
  		Oid			lefttype,
  					righttype;
  		int			indexcol;
  
  		Assert(IsA(rinfo, RestrictInfo));
  		clause = rinfo->clause;
! 
! 		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)
  		{
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6761,6776 ****
  		if (!IsA(operand, Const))
  		{
  			searchEntriesInQuals++;
  			continue;
  		}
  
  		/* If Const is null, there can be no matches */
  		if (((Const *) operand)->constisnull)
  		{
! 			*indexStartupCost = 0;
! 			*indexTotalCost = 0;
! 			*indexSelectivity = 0;
! 			PG_RETURN_VOID();
  		}
  
  		/*
--- 6838,6855 ----
  		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)
  		{
! 			matchPossible = false;
! 			break;
  		}
  
  		/*
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6800,6856 ****
  				 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)
  		{
! 			/* No match is possible */
! 			*indexStartupCost = 0;
! 			*indexTotalCost = 0;
! 			*indexSelectivity = 0;
! 			PG_RETURN_VOID();
  		}
! 		else
  		{
! 			int32		i;
  
! 			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 */
! 			haveFullScan = true;
  		}
  	}
  
! 	if (haveFullScan || indexQuals == NIL)
  	{
  		/*
  		 * Full index scan will be required.  We treat this as if every key in
--- 6879,6977 ----
  				 get_rel_name(index->indexoid));
  		}
  
! 		if (IsA(rinfo->clause, OpExpr))
  		{
! 			matchPossible =
! 				gin_costestimate_search(extractProcOid,
! 										((Const *) operand)->constvalue,
! 										strategy_op,
! 										numEntries,
! 										&partialEntriesInQuals,
! 										&exactEntriesInQuals,
! 										&searchEntriesInQuals);
! 			if (!matchPossible)
! 				break;
  		}
! 		else if (IsA(rinfo->clause, ScalarArrayOpExpr))
  		{
! 			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++)
  			{
! 				bool		elemMatchPossible;
  
! 				/* NULL can't match anything */
! 				if (elemNulls[i])
! 					continue;
! 
! 				elemMatchPossible =
! 					gin_costestimate_search(extractProcOid,
! 											elemValues[i],
! 											strategy_op,
! 											numEntries,
! 											&partialEntries,
! 											&exactEntries,
! 											&searchEntries);
! 
! 				/* We only count array elements that can return any results */
! 				if (elemMatchPossible)
! 					numPossible++;
  			}
  
! 			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.
! 			 *
! 			 * 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 (!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
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6861,6869 ****
  
  	/* Will we have more than one iteration of a nestloop scan? */
  	if (outer_rel != NULL && outer_rel->rows > 1)
! 		num_scans = outer_rel->rows;
  	else
! 		num_scans = 1;
  
  	/*
  	 * cost to begin scan, first of all, pay attention to pending list.
--- 6982,6997 ----
  
  	/* Will we have more than one iteration of a nestloop scan? */
  	if (outer_rel != NULL && outer_rel->rows > 1)
! 		outer_scans = outer_rel->rows;
  	else
! 		outer_scans = 1;
! 
! 	/*
! 	 * The cost needs to account for all rescans of ScalarArrayOpExprs
! 	 */
! 	partialEntriesInQuals *= array_scans;
! 	exactEntriesInQuals   *= array_scans;
! 	searchEntriesInQuals  *= array_scans;
  
  	/*
  	 * cost to begin scan, first of all, pay attention to pending list.
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6888,6900 ****
  
  	/*
  	 * 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,
  	 * estimate it as proportion
  	 */
  	dataPagesFetched = ceil(numDataPages * partialEntriesInQuals / numEntries);
  
  	/* calculate cache effects */
! 	if (num_scans > 1 || searchEntriesInQuals > 1)
  	{
  		entryPagesFetched = index_pages_fetched(entryPagesFetched,
  												(BlockNumber) numEntryPages,
--- 7016,7028 ----
  
  	/*
  	 * Partial match algorithm reads all data pages before doing actual scan,
! 	 * 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 (outer_scans > 1 || array_scans > 1 || searchEntriesInQuals > 1)
  	{
  		entryPagesFetched = index_pages_fetched(entryPagesFetched,
  												(BlockNumber) numEntryPages,
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6932,6938 ****
  		dataPagesFetched = dataPagesFetchedBySel;
  	}
  
! 	if (num_scans > 1)
  		dataPagesFetched = index_pages_fetched(dataPagesFetched,
  											   (BlockNumber) numDataPages,
  											   numDataPages, root);
--- 7060,7066 ----
  		dataPagesFetched = dataPagesFetchedBySel;
  	}
  
! 	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
new file mode 100644
index e1d7646..9341dbe
*** a/src/test/regress/expected/tsearch.out
--- b/src/test/regress/expected/tsearch.out
*************** SELECT count(*) FROM test_tsvector WHERE
*** 142,147 ****
--- 142,153 ----
     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);
*************** SELECT count(*) FROM test_tsvector WHERE
*** 188,193 ****
--- 194,205 ----
     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
new file mode 100644
index d261da2..9fd1207
*** a/src/test/regress/sql/tsearch.sql
--- b/src/test/regress/sql/tsearch.sql
*************** SELECT count(*) FROM test_tsvector WHERE
*** 60,65 ****
--- 60,66 ----
  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;
  
*************** SELECT count(*) FROM test_tsvector WHERE
*** 76,81 ****
--- 77,83 ----
  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');