*** /dev/null
--- b/contrib/intarray/_int_sel.c
***************
*** 0 ****
--- 1,373 ----
+ /*-------------------------------------------------------------------------
+  *
+  * ts_selfuncs.c
+  *	  Selectivity estimation functions for text search operators.
+  *
+  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+  *
+  *
+  * IDENTIFICATION
+  *	  src/backend/tsearch/ts_selfuncs.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "_int.h"
+ 
+ #include "catalog/pg_statistic.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/nodes.h"
+ #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
+ #include "utils/syscache.h"
+ 
+ 
+ /*
+  * The default text search selectivity is chosen to be small enough to
+  * encourage indexscans for typical table densities.  See selfuncs.h and
+  * DEFAULT_EQ_SEL for details.
+  */
+ #define DEFAULT_INTARRAY_MATCH_SEL 0.005
+ 
+ /* lookup table type for binary searching through MCELEMs */
+ typedef struct
+ {
+ 	int			value;
+ 	float4		frequency;
+ } IntFreq;
+ 
+ static Selectivity query_intsel(VariableStatData *vardata, Datum constval);
+ static Selectivity mcelem_query_int_selec(QUERYTYPE *query,
+ 					 Datum *mcelem, int nmcelem,
+ 					 float4 *numbers, int nnumbers);
+ static Selectivity query_int_opr_selec(ITEM *item,
+ 				  IntFreq *lookup, int length, float4 minfreq);
+ static int	compare_value_intfreq(const void *e1, const void *e2);
+ 
+ PG_FUNCTION_INFO_V1(intarraymatchsel);
+ Datum
+ intarraymatchsel(PG_FUNCTION_ARGS);
+ 
+ PG_FUNCTION_INFO_V1(intarrayjoinsel);
+ Datum
+ intarrayjoinsel(PG_FUNCTION_ARGS);
+ 
+ 
+ #define query_int_opr_selec_no_stats(query) \
+ 	query_int_opr_selec(GETQUERY(query) + query->size - 1, NULL, 0, 0)
+ 
+ /*
+  *	tsmatchsel -- Selectivity of "@@"
+  *
+  * restriction selectivity function for tsvector @@ tsquery and
+  * tsquery @@ tsvector
+  */
+ Datum
+ intarraymatchsel(PG_FUNCTION_ARGS)
+ {
+ 	PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
+ 
+ #ifdef NOT_USED
+ 	Oid			operator = PG_GETARG_OID(1);
+ #endif
+ 	List	   *args = (List *) PG_GETARG_POINTER(2);
+ 	int			varRelid = PG_GETARG_INT32(3);
+ 	VariableStatData vardata;
+ 	Node	   *other;
+ 	bool		varonleft;
+ 	Selectivity selec;
+ 
+ 	elog(NOTICE, "%d", gettype("query_int"));
+ 
+ 	/*
+ 	 * If expression is not variable = something or something = variable, then
+ 	 * punt and return a default estimate.
+ 	 */
+ 	if (!get_restriction_variable(root, args, varRelid,
+ 								  &vardata, &other, &varonleft))
+ 		PG_RETURN_FLOAT8(DEFAULT_INTARRAY_MATCH_SEL);
+ 
+ 	/*
+ 	 * Can't do anything useful if the something is not a constant, either.
+ 	 */
+ 	if (!IsA(other, Const))
+ 	{
+ 		ReleaseVariableStats(vardata);
+ 		PG_RETURN_FLOAT8(DEFAULT_INTARRAY_MATCH_SEL);
+ 	}
+ 
+ 	/*
+ 	 * The "@@" operator is strict, so we can cope with NULL right away
+ 	 */
+ 	if (((Const *) other)->constisnull)
+ 	{
+ 		ReleaseVariableStats(vardata);
+ 		PG_RETURN_FLOAT8(0.0);
+ 	}
+ 
+ 	/*
+ 	 * OK, there's a Var and a Const we're dealing with here.  We need the
+ 	 * Const to be a TSQuery, else we can't do anything useful.  We have to
+ 	 * check this because the Var might be the TSQuery not the TSVector.
+ 	 */
+ 	if (((Const *) other)->consttype == 24924)
+ 	{
+ 		/* tsvector @@ tsquery or the other way around */
+ 		Assert(vardata.vartype == INT4ARRAYOID);
+ 
+ 		selec = query_intsel(&vardata, ((Const *) other)->constvalue);
+ 	}
+ 	else
+ 	{
+ 		/* If we can't see the query structure, must punt */
+ 		selec = DEFAULT_INTARRAY_MATCH_SEL;
+ 	}
+ 
+ 	ReleaseVariableStats(vardata);
+ 
+ 	CLAMP_PROBABILITY(selec);
+ 
+ 	PG_RETURN_FLOAT8((float8) selec);
+ }
+ 
+ 
+ /*
+  *	tsmatchjoinsel -- join selectivity of "@@"
+  *
+  * join selectivity function for tsvector @@ tsquery and tsquery @@ tsvector
+  */
+ Datum
+ intarrayjoinsel(PG_FUNCTION_ARGS)
+ {
+ 	/* for the moment we just punt */
+ 	PG_RETURN_FLOAT8(DEFAULT_INTARRAY_MATCH_SEL);
+ }
+ 
+ 
+ /*
+  * @@ selectivity for tsvector var vs tsquery constant
+  */
+ static Selectivity
+ query_intsel(VariableStatData *vardata, Datum constval)
+ {
+ 	Selectivity selec;
+ 	QUERYTYPE	*query;
+ 
+ 	/* The caller made sure the const is a TSQuery, so get it now */
+ 	query = DatumGetQueryTypeP(constval);
+ 
+ 	/* Empty query matches nothing */
+ 	if (query->size == 0)
+ 		return (Selectivity) 0.0;
+ 
+ 	if (HeapTupleIsValid(vardata->statsTuple))
+ 	{
+ 		Form_pg_statistic stats;
+ 		Datum	   *values;
+ 		int			nvalues;
+ 		float4	   *numbers;
+ 		int			nnumbers;
+ 
+ 		stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
+ 
+ 		/* MCELEM will be an array of TEXT elements for a tsvector column */
+ 		if (get_attstatsslot(vardata->statsTuple,
+ 							 INT4OID, -1,
+ 							 STATISTIC_KIND_MCELEM, InvalidOid,
+ 							 NULL,
+ 							 &values, &nvalues,
+ 							 &numbers, &nnumbers))
+ 		{
+ 			/*
+ 			 * There is a most-common-elements slot for the tsvector Var, so
+ 			 * use that.
+ 			 */
+ 			selec = mcelem_query_int_selec(query, values, nvalues,
+ 										 numbers, nnumbers);
+ 			free_attstatsslot(INT4OID, values, nvalues, numbers, nnumbers);
+ 		}
+ 		else
+ 		{
+ 			/* No most-common-elements info, so do without */
+ 			selec = query_int_opr_selec_no_stats(query);
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/* No stats at all, so do without */
+ 		selec = query_int_opr_selec_no_stats(query);
+ 	}
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * Extract data from the pg_statistic arrays into useful format.
+  */
+ static Selectivity
+ mcelem_query_int_selec(QUERYTYPE *query, Datum *mcelem, int nmcelem,
+ 					 float4 *numbers, int nnumbers)
+ {
+ 	float4		minfreq;
+ 	IntFreq    *lookup;
+ 	Selectivity selec;
+ 	int			i;
+ 
+ 	/*
+ 	 * There should be two more Numbers than Values, because the last two
+ 	 * cells are taken for minimal and maximal frequency.  Punt if not.
+ 	 */
+ 	if (nnumbers != nmcelem + 2)
+ 		return query_int_opr_selec_no_stats(query);
+ 
+ 	/*
+ 	 * Transpose the data into a single array so we can use bsearch().
+ 	 */
+ 	lookup = (IntFreq *) palloc(sizeof(IntFreq) * nmcelem);
+ 	for (i = 0; i < nmcelem; i++)
+ 	{
+ 		/*
+ 		 * The text Datums came from an array, so it cannot be compressed or
+ 		 * stored out-of-line -- it's safe to use VARSIZE_ANY*.
+ 		 */
+ 		Assert(!VARATT_IS_COMPRESSED(mcelem[i]) && !VARATT_IS_EXTERNAL(mcelem[i]));
+ 		lookup[i].value = DatumGetInt32(mcelem[i]);
+ 		lookup[i].frequency = numbers[i];
+ 	}
+ 
+ 	/*
+ 	 * Grab the lowest frequency. compute_tsvector_stats() stored it for us in
+ 	 * the one before the last cell of the Numbers array. See ts_typanalyze.c
+ 	 */
+ 	minfreq = numbers[nnumbers - 2];
+ 
+ 	selec = query_int_opr_selec(GETQUERY(query) + query->size - 1, lookup,
+ 							  nmcelem, minfreq);
+ 
+ 	pfree(lookup);
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * Traverse the tsquery in preorder, calculating selectivity as:
+  *
+  *	 selec(left_oper) * selec(right_oper) in AND nodes,
+  *
+  *	 selec(left_oper) + selec(right_oper) -
+  *		selec(left_oper) * selec(right_oper) in OR nodes,
+  *
+  *	 1 - select(oper) in NOT nodes
+  *
+  *	 histogram-based estimation in prefix VAL nodes
+  *
+  *	 freq[val] in exact VAL nodes, if the value is in MCELEM
+  *	 min(freq[MCELEM]) / 2 in VAL nodes, if it is not
+  *
+  * The MCELEM array is already sorted (see ts_typanalyze.c), so we can use
+  * binary search for determining freq[MCELEM].
+  *
+  * If we don't have stats for the tsvector, we still use this logic,
+  * except we use default estimates for VAL nodes.  This case is signaled
+  * by lookup == NULL.
+  */
+ static Selectivity
+ query_int_opr_selec(ITEM *item,
+ 				  IntFreq *lookup, int length, float4 minfreq)
+ {
+ 	Selectivity selec;
+ 
+ 	/* since this function recurses, it could be driven to stack overflow */
+ 	check_stack_depth();
+ 
+ 	if (item->type == VAL)
+ 	{
+ 		IntFreq *searchres;
+ 		/* If no stats for the variable, use DEFAULT_TS_MATCH_SEL */
+ 		if (lookup == NULL)
+ 			return (Selectivity) DEFAULT_INTARRAY_MATCH_SEL;
+ 
+ 		searchres = (IntFreq *) bsearch(&item->val, lookup, sizeof(item->val),
+ 										 sizeof(IntFreq),
+ 										 compare_value_intfreq);
+ 
+ 		if (searchres)
+ 		{
+ 			/*
+ 			 * The element is in MCELEM.  Return precise selectivity (or
+ 			 * at least as precise as ANALYZE could find out).
+ 			 */
+ 			selec = searchres->frequency;
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * The element is not in MCELEM.  Punt, but assume that the
+ 			 * selectivity cannot be more than minfreq / 2.
+ 			 */
+ 			selec = Min(DEFAULT_INTARRAY_MATCH_SEL, minfreq / 2);
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/* Current TSQuery node is an operator */
+ 		Selectivity s1,
+ 					s2;
+ 
+ 		switch (item->val)
+ 		{
+ 			case (int4) '!':
+ 				selec = 1.0 - query_int_opr_selec(item - 1,
+ 												lookup, length, minfreq);
+ 				break;
+ 
+ 			case (int4) '&':
+ 				s1 = query_int_opr_selec(item - 1,
+ 									   lookup, length, minfreq);
+ 				s2 = query_int_opr_selec(item + item->left,
+ 									   lookup, length, minfreq);
+ 				selec = s1 * s2;
+ 				break;
+ 
+ 			case (int4) '|':
+ 				s1 = query_int_opr_selec(item - 1,
+ 									   lookup, length, minfreq);
+ 				s2 = query_int_opr_selec(item + item->left,
+ 									   lookup, length, minfreq);
+ 				selec = s1 + s2 - s1 * s2;
+ 				break;
+ 
+ 			default:
+ 				elog(ERROR, "unrecognized operator: %d", item->val);
+ 				selec = 0;			/* keep compiler quiet */
+ 				break;
+ 		}
+ 	}
+ 
+ 	/* Clamp intermediate results to stay sane despite roundoff error */
+ 	CLAMP_PROBABILITY(selec);
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * bsearch() comparator for a lexeme (non-NULL terminated string with length)
+  * and a TextFreq. Use length, then byte-for-byte comparison, because that's
+  * how ANALYZE code sorted data before storing it in a statistic tuple.
+  * See ts_typanalyze.c for details.
+  */
+ static int
+ compare_value_intfreq(const void *e1, const void *e2)
+ {
+ 	const int4 *key = (const int4 *) e1;
+ 	const IntFreq *t = (const IntFreq *) e2;
+ 
+ 	if (*key > t->value)
+ 		return 1;
+ 	else if (*key < t->value)
+ 		return -1;
+ 	else
+ 		return 0;
+ }
*** a/doc/src/sgml/catalogs.sgml
--- b/doc/src/sgml/catalogs.sgml
***************
*** 8007,8014 ****
        <entry>
         A list of the most common values in the column. (Null if
         no values seem to be more common than any others.)
!        For some data types such as <type>tsvector</>, this is a list of
!        the most common element values rather than values of the type itself.
        </entry>
       </row>
  
--- 8007,8015 ----
        <entry>
         A list of the most common values in the column. (Null if
         no values seem to be more common than any others.)
!        For some data types such as <type>arrays</> and <type>tsvector</>,
!        this is a list of the most common element values rather than values of
!        the type itself.
        </entry>
       </row>
  
***************
*** 8020,8028 ****
         A list of the frequencies of the most common values or elements,
         i.e., number of occurrences of each divided by total number of rows.
         (Null when <structfield>most_common_vals</structfield> is.)
!        For some data types such as <type>tsvector</>, it can also store some
!        additional information, making it longer than the
!        <structfield>most_common_vals</> array.
        </entry>
       </row>
  
--- 8021,8029 ----
         A list of the frequencies of the most common values or elements,
         i.e., number of occurrences of each divided by total number of rows.
         (Null when <structfield>most_common_vals</structfield> is.)
!        For some data types such as <type>arrays</> and <type>tsvector</>,
!        it can also store some additional information, making it longer than
!        the <structfield>most_common_vals</> array.
        </entry>
       </row>
  
***************
*** 8038,8043 ****
--- 8039,8045 ----
         does not have a <literal>&lt;</> operator or if the
         <structfield>most_common_vals</> list accounts for the entire
         population.)
+        For <type>arrays</>, it holds histogram bounds of array lengths. 
        </entry>
       </row>
  
*** a/src/backend/catalog/heap.c
--- b/src/backend/catalog/heap.c
***************
*** 49,54 ****
--- 49,55 ----
  #include "catalog/pg_namespace.h"
  #include "catalog/pg_statistic.h"
  #include "catalog/pg_tablespace.h"
+ #include "catalog/pg_proc.h"
  #include "catalog/pg_type.h"
  #include "catalog/pg_type_fn.h"
  #include "catalog/storage.h"
***************
*** 1169,1175 **** heap_create_with_catalog(const char *relname,
  				   F_ARRAY_SEND,	/* array send (bin) proc */
  				   InvalidOid,	/* typmodin procedure - none */
  				   InvalidOid,	/* typmodout procedure - none */
! 				   InvalidOid,	/* analyze procedure - default */
  				   new_type_oid,	/* array element type - the rowtype */
  				   true,		/* yes, this is an array type */
  				   InvalidOid,	/* this has no array type */
--- 1170,1176 ----
  				   F_ARRAY_SEND,	/* array send (bin) proc */
  				   InvalidOid,	/* typmodin procedure - none */
  				   InvalidOid,	/* typmodout procedure - none */
! 				   ArrayTypanalyzeOid,	/* analyze procedure - default */
  				   new_type_oid,	/* array element type - the rowtype */
  				   true,		/* yes, this is an array type */
  				   InvalidOid,	/* this has no array type */
*** a/src/backend/commands/typecmds.c
--- b/src/backend/commands/typecmds.c
***************
*** 43,48 ****
--- 43,49 ----
  #include "catalog/pg_depend.h"
  #include "catalog/pg_enum.h"
  #include "catalog/pg_namespace.h"
+ #include "catalog/pg_proc.h"
  #include "catalog/pg_type.h"
  #include "catalog/pg_type_fn.h"
  #include "commands/defrem.h"
***************
*** 598,604 **** DefineType(List *names, List *parameters)
  			   F_ARRAY_SEND,	/* send procedure */
  			   typmodinOid,		/* typmodin procedure */
  			   typmodoutOid,	/* typmodout procedure */
! 			   InvalidOid,		/* analyze procedure - default */
  			   typoid,			/* element type ID */
  			   true,			/* yes this is an array type */
  			   InvalidOid,		/* no further array type */
--- 599,605 ----
  			   F_ARRAY_SEND,	/* send procedure */
  			   typmodinOid,		/* typmodin procedure */
  			   typmodoutOid,	/* typmodout procedure */
! 			   ArrayTypanalyzeOid,		/* analyze procedure - default */
  			   typoid,			/* element type ID */
  			   true,			/* yes this is an array type */
  			   InvalidOid,		/* no further array type */
***************
*** 1206,1212 **** DefineEnum(CreateEnumStmt *stmt)
  			   F_ARRAY_SEND,	/* send procedure */
  			   InvalidOid,		/* typmodin procedure - none */
  			   InvalidOid,		/* typmodout procedure - none */
! 			   InvalidOid,		/* analyze procedure - default */
  			   enumTypeOid,		/* element type ID */
  			   true,			/* yes this is an array type */
  			   InvalidOid,		/* no further array type */
--- 1207,1213 ----
  			   F_ARRAY_SEND,	/* send procedure */
  			   InvalidOid,		/* typmodin procedure - none */
  			   InvalidOid,		/* typmodout procedure - none */
! 			   ArrayTypanalyzeOid,		/* analyze procedure - default */
  			   enumTypeOid,		/* element type ID */
  			   true,			/* yes this is an array type */
  			   InvalidOid,		/* no further array type */
*** a/src/backend/utils/adt/Makefile
--- b/src/backend/utils/adt/Makefile
***************
*** 15,21 **** override CFLAGS+= -mieee
  endif
  endif
  
! OBJS = acl.o arrayfuncs.o array_userfuncs.o arrayutils.o bool.o \
  	cash.o char.o date.o datetime.o datum.o domains.o \
  	enum.o float.o format_type.o \
  	geo_ops.o geo_selfuncs.o int.o int8.o like.o lockfuncs.o \
--- 15,22 ----
  endif
  endif
  
! OBJS = acl.o arrayfuncs.o array_userfuncs.o arrayutils.o \
! 	array_sel.o array_typanalyze.o bool.o \
  	cash.o char.o date.o datetime.o datum.o domains.o \
  	enum.o float.o format_type.o \
  	geo_ops.o geo_selfuncs.o int.o int8.o like.o lockfuncs.o \
*** /dev/null
--- b/src/backend/utils/adt/array_sel.c
***************
*** 0 ****
--- 1,863 ----
+ /*-------------------------------------------------------------------------
+  *
+  * array_sel.c
+  *	  Functions for selectivity estimation of array operators.
+  *
+  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+  *
+  *
+  * IDENTIFICATION
+  *	  src/backend/tsearch/array_sel.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ 
+ #include "postgres.h"
+ #include "access/hash.h"
+ #include "catalog/pg_operator.h"
+ #include "commands/vacuum.h"
+ #include "utils/builtins.h"
+ #include "utils/typcache.h"
+ #include "utils/array.h"
+ #include "catalog/pg_am.h"
+ #include "catalog/pg_collation.h"
+ #include "commands/defrem.h"
+ #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
+ 
+ /* Default selectivity constant */
+ #define DEFAULT_CONT_SEL 0.005
+ 
+ /* Macro for selectivity estimation to be used if we have no statistics */
+ #define array_selec_no_stats(array,nitems,op) mcelem_array_selec(array, nitems, typentry, NULL, 0, NULL, 0, NULL, 0, op)
+ 
+ Datum arraysel(PG_FUNCTION_ARGS);
+ 
+ static Selectivity calc_arraysel(VariableStatData *vardata, Datum constval, 
+ 	Oid operator);
+ static Selectivity
+ mcelem_array_selec(ArrayType *array, int nitems, TypeCacheEntry *typentry, 
+ 	Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, 
+ 	Datum *hist, int nhist, Oid operator);
+ static int element_compare(const void *key1, const void *key2);
+ bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index);
+ static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, 
+ 	int nmcelem, float4 *numbers, Datum *array_data, int nitems, Oid operator);
+ static float calc_hist(Datum *hist, int nhist, float *hist_part, int n);
+ static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem, 
+ 	float4 *numbers, Datum *array_data, int nitems, Datum *hist, int nhist, 
+ 	Oid operator);
+ static float *calc_distr(float *p, int n, int m);
+ 
+ /* Compare function of element data type */
+ static FunctionCallInfoData cmpfunc;
+ 
+ /*
+  * selectivity for "const = ANY(column)" and "const = ALL(column)"
+  */
+ Selectivity
+ calc_scalararraysel(VariableStatData *vardata, Datum constval, bool orClause)
+ {
+ 	Oid elemtype;
+ 	Selectivity	selec;
+ 	TypeCacheEntry *typentry;
+ 	Datum	   *hist;
+ 	int			nhist;
+ 
+ 	elemtype = get_base_element_type(vardata->vartype);
+ 
+ 	/* Get default comparison function */
+ 	typentry = lookup_type_cache(elemtype,
+ 		TYPECACHE_CMP_PROC | TYPECACHE_CMP_PROC_FINFO );
+ 	InitFunctionCallInfoData(cmpfunc, &typentry->cmp_proc_finfo, 2, 
+ 		DEFAULT_COLLATION_OID, NULL, NULL);
+ 
+ 	if (HeapTupleIsValid(vardata->statsTuple))
+ 	{
+ 		Form_pg_statistic stats;
+ 		Datum	   *values;
+ 		int			nvalues;
+ 		float4	   *numbers;
+ 		int			nnumbers;
+ 
+ 		stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
+ 
+ 		/* MCELEM will be an array of same type as element */
+ 		if (get_attstatsslot(vardata->statsTuple,
+ 							 elemtype, vardata->atttypmod,
+ 							 STATISTIC_KIND_MCELEM, InvalidOid,
+ 							 NULL,
+ 							 &values, &nvalues,
+ 							 &numbers, &nnumbers))
+ 		{
+ 			/* For const = ALL(column) get lengths histogram */
+ 			if (!orClause
+ 				|| !get_attstatsslot(vardata->statsTuple,
+ 							 INT4OID, -1,
+ 							 STATISTIC_KIND_HISTOGRAM, InvalidOid,
+ 							 NULL,
+ 							 &hist, &nhist,
+ 							 NULL, NULL))
+ 			{
+ 				hist = NULL;
+ 				nhist = 0;
+ 			}
+ 			/*
+ 			 * There is a most-common-elements slot for the array Var, so
+ 			 * use that.
+ 			 */
+ 			if (orClause)
+ 				selec = mcelem_array_contain_overlap_selec(values, nvalues, 
+ 					numbers, &constval, 1, OID_ARRAY_CONTAIN_OP);
+ 			else
+ 				selec = mcelem_array_contained_selec(values, nvalues, numbers, 
+ 					&constval, 1, hist, nhist, OID_ARRAY_CONTAINED_OP);
+ 			free_attstatsslot(elemtype, values, nvalues, numbers, nnumbers);
+ 		}
+ 		else
+ 		{
+ 			/* No most-common-elements info, so do without */
+ 			selec = mcelem_array_contain_overlap_selec(NULL, 0, NULL, &constval, 
+ 				1, OID_ARRAY_CONTAIN_OP);
+ 		}
+ 
+ 		/*
+ 		 * MCE stats count only non-null rows, so adjust for null rows.
+ 		 */
+ 		selec *= (1.0 - stats->stanullfrac);
+ 	}
+ 	else
+ 	{
+ 		/* No stats at all, so do without */
+ 		selec = mcelem_array_contain_overlap_selec(NULL, 0, NULL, &constval, 
+ 			1, OID_ARRAY_CONTAIN_OP);
+ 		/* we assume no nulls here, so no stanullfrac correction */
+ 	}
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * arraysel -- restriction selectivity for "array && array" and "array <@ array"
+  */
+ Datum
+ arraysel(PG_FUNCTION_ARGS)
+ {
+ 	PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
+ 
+ 	Oid			operator = PG_GETARG_OID(1);
+ 	List	   *args = (List *) PG_GETARG_POINTER(2);
+ 	int			varRelid = PG_GETARG_INT32(3);
+ 	VariableStatData vardata;
+ 	Node	   *other;
+ 	bool		varonleft;
+ 	Selectivity selec;
+ 	Oid			element_typeid;
+ 
+ 	/*
+ 	 * If expression is not variable = something or something = variable, then
+ 	 * punt and return a default estimate.
+ 	 */
+ 	if (!get_restriction_variable(root, args, varRelid,
+ 								  &vardata, &other, &varonleft))
+ 		PG_RETURN_FLOAT8(DEFAULT_CONT_SEL);
+ 
+ 	/*
+ 	 * Can't do anything useful if the something is not a constant, either.
+ 	 */
+ 	if (!IsA(other, Const))
+ 	{
+ 		ReleaseVariableStats(vardata);
+ 		PG_RETURN_FLOAT8(DEFAULT_CONT_SEL);
+ 	}
+ 
+ 	/*
+ 	 * The "&&", "@>" and "<@" operators is strict, so we can cope with NULL
+ 	 * right away.
+ 	 */
+ 	if (((Const *) other)->constisnull)
+ 	{
+ 		ReleaseVariableStats(vardata);
+ 		PG_RETURN_FLOAT8(0.0);
+ 	}
+ 
+ 	if (!varonleft && operator == OID_ARRAY_CONTAIN_OP)
+ 		operator = OID_ARRAY_CONTAINED_OP;
+ 
+ 	/*
+ 	 * OK, there's a Var and a Const we're dealing with here.  We need the
+ 	 * Const to be a array with same element type as column, else we can't do
+ 	 * anything useful.
+ 	 */
+ 	element_typeid = get_base_element_type(((Const *) other)->consttype);
+ 	if (element_typeid != InvalidOid &&
+ 		element_typeid == get_base_element_type(vardata.vartype))
+ 	{
+ 		selec = calc_arraysel(&vardata, ((Const *) other)->constvalue, operator);
+ 	}
+ 	else
+ 	{
+ 		/* If we can't see the query structure, must punt */
+ 		selec = DEFAULT_CONT_SEL;
+ 	}
+ 
+ 	ReleaseVariableStats(vardata);
+ 
+ 	CLAMP_PROBABILITY(selec);
+ 
+ 	PG_RETURN_FLOAT8((float8) selec);
+ }
+ 
+ /*
+  * selectivity for "column @> const", "column && const" and "column <@ const"
+  */
+ static Selectivity
+ calc_arraysel(VariableStatData *vardata, Datum constval, Oid operator)
+ {
+ 	Selectivity	selec;
+ 	ArrayType  *array;
+ 	int			ndims;
+ 	int		   *dims;
+ 	int			nitems;
+ 	TypeCacheEntry *typentry;
+ 
+ 	/* The caller made sure the const is a array with same element type, so get it now */
+ 	array = DatumGetArrayTypeP(constval);
+ 	ndims = ARR_NDIM(array);
+ 	dims = ARR_DIMS(array);
+ 	nitems = ArrayGetNItems(ndims, dims);
+ 
+ 	/* Get default comparison functio */
+ 	typentry = lookup_type_cache(array->elemtype,
+ 		TYPECACHE_CMP_PROC | TYPECACHE_CMP_PROC_FINFO );
+ 	InitFunctionCallInfoData(cmpfunc, &typentry->cmp_proc_finfo, 2, DEFAULT_COLLATION_OID, NULL, NULL);
+ 
+ 	if (HeapTupleIsValid(vardata->statsTuple))
+ 	{
+ 		Form_pg_statistic stats;
+ 		Datum	   *values;
+ 		int			nvalues;
+ 		Datum	   *hist;
+ 		int			nhist;
+ 		float4	   *numbers;
+ 		int			nnumbers;
+ 
+ 		stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
+ 
+ 		/* MCELEM will be an array of same type as column */
+ 		if (get_attstatsslot(vardata->statsTuple,
+ 							 array->elemtype, vardata->atttypmod,
+ 							 STATISTIC_KIND_MCELEM, InvalidOid,
+ 							 NULL,
+ 							 &values, &nvalues,
+ 							 &numbers, &nnumbers))
+ 		{
+ 			/*
+ 			 * For "array <@ const" case we also need array lengths histogram.
+ 			 */
+ 			if (operator != OID_ARRAY_CONTAINED_OP
+ 				|| !get_attstatsslot(vardata->statsTuple,
+ 							 INT4OID, -1,
+ 							 STATISTIC_KIND_HISTOGRAM, InvalidOid,
+ 							 NULL,
+ 							 &hist, &nhist,
+ 							 NULL, NULL))
+ 			{
+ 				hist = NULL;
+ 				nhist = 0;
+ 			}
+ 			/*
+ 			 * There is a most-common-elements slot for the array Var, so
+ 			 * use that.
+ 			 */
+ 			selec = mcelem_array_selec(array, nitems, typentry, values, nvalues,
+ 				numbers, nnumbers, hist, nhist, operator);
+ 			free_attstatsslot(array->elemtype, values, nvalues, numbers, nnumbers);
+ 		}
+ 		else
+ 		{
+ 			/* No most-common-elements info, so do without */
+ 			selec = array_selec_no_stats(array, nitems, operator);
+ 		}
+ 
+ 		/*
+ 		 * MCE stats count only non-null rows, so adjust for null rows.
+ 		 */
+ 		selec *= (1.0 - stats->stanullfrac);
+ 	}
+ 	else
+ 	{
+ 		/* No stats at all, so do without */
+ 		selec = array_selec_no_stats(array, nitems, operator);
+ 		/* we assume no nulls here, so no stanullfrac correction */
+ 	}
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * find_next_mcelem finds first mcelem that greater or equal to given value 
+  * starting from *index. It saves found position into *index and returns true
+  * if found mcelem is equal to value.
+  */
+ bool
+ find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index)
+ {
+ 	int l = *index, r = nmcelem - 1, i, res;
+ 	while (l <= r)
+ 	{
+ 		i = (l + r)/2;
+ 		res = element_compare(&mcelem[i], &value);
+ 		if (res == 0)
+ 		{
+ 			*index = i;
+ 			return true;
+ 		}
+ 		else if (res < 0)
+ 		{
+ 			l = i + 1;
+ 		}
+ 		else
+ 		{
+ 			r = i - 1;
+ 		}
+ 	}
+ 	*index = l;
+ 	return false;
+ }
+ 
+ /*
+  * Array selectivity estimation based on most common elements statistics.
+  */
+ static Selectivity
+ mcelem_array_selec(ArrayType *array, int nitems, TypeCacheEntry *typentry, 
+ 	Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *hist, 
+ 	int nhist, Oid operator)
+ {
+ 	int			i;
+ 	char	   *ptr;
+ 	bits8	   *bitmap;
+ 	int			bitmask;
+ 	Datum	   *array_data;
+ 	bool		null_present;
+ 	int			nonnull_nitems;
+ 
+ 	/*
+ 	 * There should be three more Numbers than Values, because the last three
+ 	 * cells are taken for nulls, minimal and maximal frequency.  Punt if not.
+ 	 */
+ 	if (nnumbers != nmcelem + 4)
+ 		mcelem = NULL;
+ 
+ 	if (!mcelem)
+ 		nmcelem = 0;
+ 
+ 	/*
+ 	 * Prepare constant array data for sorting. Sorting allows to find unique
+ 	 * elements and do merge with most common elements in single loop.
+ 	 */
+ 	array_data = (Datum *)palloc(sizeof(Datum) * nitems);
+ 	bitmap = ARR_NULLBITMAP(array);
+ 	ptr = ARR_DATA_PTR(array);
+ 	bitmask = 1;
+ 	nonnull_nitems = 0;
+ 	null_present = false;
+ 	for (i = 0; i < nitems; i++)
+ 	{
+ 		if (bitmap && (*bitmap & bitmask) == 0)
+ 		{
+ 			/* Store information about null element presence into flag */
+ 			null_present = true;
+ 		}
+ 		else
+ 		{
+ 			/* Extract array data */
+ 			array_data[nonnull_nitems] = fetch_att(ptr, typentry->typbyval,
+ 												   typentry->typlen);
+ 			ptr = att_addlength_pointer(ptr, typentry->typlen, ptr);
+ 			ptr = (char *) att_align_nominal(ptr, typentry->typalign);
+ 			nonnull_nitems++;
+ 		}
+ 		/* Adjust bitmask and bitmap pointer */
+ 		bitmask <<= 1;
+ 		if (bitmask == 0x100)
+ 		{
+ 			if (bitmap)
+ 				bitmap++;
+ 			bitmask = 1;
+ 		}
+ 	}
+ 
+ 	/* Query "column @> '{smth., null}'" match nothing */
+ 	if (null_present && operator == OID_ARRAY_CONTAIN_OP)
+ 		return 0.0;
+ 
+ 	/* Sort extracted array elements using default comparison function */
+ 	qsort(array_data, nonnull_nitems, sizeof(Datum), element_compare);
+ 
+ 	/* "column @> const" and "column && const" cases */
+ 	if (operator == OID_ARRAY_CONTAIN_OP || operator == OID_ARRAY_OVERLAP_OP)
+ 		return mcelem_array_contain_overlap_selec(mcelem, nmcelem, numbers,
+ 			array_data, nonnull_nitems, operator);
+ 	/* "column <@ const" case */
+ 	if (operator == OID_ARRAY_CONTAINED_OP)
+ 		return mcelem_array_contained_selec(mcelem, nmcelem, numbers,
+ 			array_data, nonnull_nitems, hist, nhist, operator);
+ 	return DEFAULT_CONT_SEL;
+ }
+ 
+ /*
+  * Fast function for floor value of 2 based logarithm calculation.
+  */
+ static int
+ floor_log2(uint32 n)
+ {
+ 	int pos = 0;
+ 	if (n == 0)
+ 		return -1;
+ 	if (n >= 1<<16)
+ 	{
+ 		n >>= 16;
+ 		pos += 16;
+ 	}
+ 	if (n >= 1<<8)
+ 	{
+ 		n >>= 8;
+ 		pos += 8;
+ 	}
+ 	if (n >= 1<<4)
+ 	{
+ 		n >>= 4;
+ 		pos += 4;
+ 	}
+ 	if (n >= 1<<2)
+ 	{
+ 		n >>= 2;
+ 		pos += 2;
+ 	}
+ 	if (n >= 1<<1)
+ 	{
+ 		pos += 1;
+ 	}
+ 	return pos;
+ }
+ 
+ /*
+  * Array selectivity estimation based on most common elements statistics for
+  * "column @> const" and "column && const" cases.
+  */
+ static Selectivity
+ mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem,
+ 	float4 *numbers, Datum *array_data, int nitems, Oid operator)
+ {
+ 	Selectivity	selec, elem_selec;
+ 	int	mcelem_index, i;
+ 	bool use_bsearch;
+ 	float4		minfreq;
+ 
+ 	if (mcelem)
+ 	{
+ 		/*
+ 		 * Grab the lowest frequency. compute_array_stats() stored it for us
+ 		 * in the one before the last cell of the Numbers array.
+ 		 * See array_typanalyze.c
+ 		 */
+ 		minfreq = numbers[nmcelem + 1];
+ 	}else{
+ 		/*
+ 		 * Without statistics set minfreq so that minfreq/2 = DEFAULT_CONT_SEL
+ 		 */
+ 		minfreq = 2 * DEFAULT_CONT_SEL;
+ 	}
+ 	
+ 	/*
+ 	 * Decide whether it is faster to use binary search or not.
+ 	 */
+ 	if (nitems * floor_log2((unsigned int)nmcelem) < nmcelem + nitems)
+ 		use_bsearch = true;
+ 	else
+ 		use_bsearch = false;
+ 
+ 	if (operator == OID_ARRAY_CONTAIN_OP)
+ 	{
+ 		/*
+ 		 * Initial selectivity for "column @> const" query is 1.0, and it will
+ 		 * be decreased with each element of constant array.
+ 		 */
+ 		selec = 1.0;
+ 	}
+ 	else
+ 	{
+ 		/*
+ 		 * Initial selectivity for "column && const" query is 0.0, and it will
+ 		 * be increased with each element of constant array.
+ 		 */
+ 		selec = 0.0;
+ 	}
+ 	mcelem_index = 0;
+ 	for (i = 0; i < nitems; i++)
+ 	{
+ 		bool found = false;
+ 		/* Comparison with previous value in order to guarantee uniquness */
+ 		if (i > 0)
+ 		{
+ 			if (!element_compare(&array_data[i-1], &array_data[i]))
+ 				continue;
+ 		}
+ 
+ 
+ 		/* Find frequency of corresponding most common element */
+ 		if (use_bsearch)
+ 		{
+ 			found = find_next_mcelem(mcelem, nmcelem, array_data[i], &mcelem_index);
+ 		}
+ 		else
+ 		{
+ 			while (mcelem_index < nmcelem)
+ 			{
+ 				int cmp = element_compare(&mcelem[mcelem_index], &array_data[i]);
+ 				if (cmp < 0)
+ 				{
+ 					mcelem_index++;
+ 				}
+ 				else
+ 				{
+ 					/* mcelem is found */
+ 					if (cmp == 0)
+ 					{
+ 						found = true;
+ 					}
+ 					break;
+ 				}
+ 			}
+ 		}
+ 		
+ 		if (found)
+ 		{
+ 			/*
+ 			 * MCELEM is found, use it's frequency.
+ 			 */
+ 			elem_selec = numbers[mcelem_index];
+ 			mcelem_index++;
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * The element is not in MCELEM.  Punt, but assume that the
+ 			 * selectivity cannot be more than minfreq / 2.
+ 			 */
+ 			elem_selec = Min(DEFAULT_CONT_SEL, minfreq / 2);
+ 		}
+ 		/*
+ 		 * Adjust general selectivity using current element selectivity using
+ 		 * assumption of element occurence independence.
+ 		 */
+ 		if (operator == OID_ARRAY_CONTAIN_OP)
+ 			selec *= elem_selec;
+ 		else
+ 			selec = selec + elem_selec - selec * elem_selec;
+ 	}
+ 
+ 	/* Clamp intermediate results to stay sane despite roundoff error */
+ 	CLAMP_PROBABILITY(selec);
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * Calculate first n lengths probabilities by histogram. We assume that any
+  * interval between a and b histogram values gives 1 / ((b - a + 1) * (nhist - 1))
+  * probability to values between a and b and half of that to a and b.
+  * Returns total probability that length is less of equal to n.
+  */
+ static float
+ calc_hist(Datum *hist, int nhist, float *hist_part, int n)
+ {
+ 	int k, i = 0, prev_interval = 0, next_interval = 0;
+ 	float frac, total = 0.0f;
+ 	/* 
+ 	 * frac is a probability contribution by each interval between histogram 
+ 	 * values. We have nhist - 1 intervals. Contribution of one will be
+ 	 * 1 / (nhist - 1).
+ 	 */
+ 	frac = 1.0f / ((float)(nhist - 1));
+ 	for (k = 0; k <= n; k++)
+ 	{
+ 		int count = 0;
+ 		
+ 		/* Count occurences of k length in histogram. */
+ 		while (i < nhist && DatumGetInt32(hist[i]) <= k)
+ 		{
+ 			if (DatumGetInt32(hist[i]) == k)
+ 				count++;
+ 			i++;
+ 		}
+ 
+ 		if (count > 0)
+ 		{
+ 			float val;
+ 			
+ 			/* Find length between current histogram value and the next one */
+ 			if (i < nhist)
+ 				next_interval = DatumGetInt32(hist[i + 1]) - 
+ 								DatumGetInt32(hist[i]);
+ 			else
+ 				next_interval = 0;
+ 			
+ 			/*
+ 			 * count - 1 of intervals are inside of k value. It gives
+ 			 * (count - 1) * frac probability. Also, take care about intervals
+ 			 * that have start or end here. 
+ 			 */
+ 			val = (float)(count - 1);
+ 			if (next_interval > 0)
+ 				val += 0.5f / ((float)next_interval);
+ 			if (prev_interval > 0)
+ 				val += 0.5f / ((float)prev_interval);
+ 			hist_part[k] = frac * val;
+ 			prev_interval = next_interval;
+ 		}
+ 		else
+ 		{
+ 			/* 
+ 			 * If k value isn't present in histogram then only interval that
+ 			 * goes along k value contribute to it's probability.
+ 			 */
+ 			if (prev_interval == 0)
+ 				hist_part[k] = 0.0f;
+ 			else
+ 				hist_part[k] = frac / ((float) prev_interval);
+ 		}
+ 		/* Accumulate total probability. */
+ 		total += hist_part[k];
+ 	}
+ 	return total;
+ }
+ 
+ /*
+  * Let be n independent events with probabilities p. This function calculates
+  * probabilities of exact k of events occurence for k in [0;m].
+  * Imagine matrix M of (n + 1) x (m + 1) size. Element M[i,j] denotes
+  * probability that exact j of first i events occurs. Obviously M[0,0] = 1. 
+  * Each next event increase total number of occured events if it occurs and 
+  * leave last value of that number if it doesn't occur. So, by the law of
+  * total probability: M[i,j] = M[i - 1, j] * (1 - p[i]) + M[i - 1, j - 1] * p[i]
+  * for i > 0, j > 0. M[i,0] = M[i - 1, 0] * (1 - p[i]) for i > 0.
+  */
+ static float *
+ calc_distr(float *p, int n, int m)
+ {
+ 	float *row, *prev_row, *tmp;
+ 	int i, j;
+ 	
+ 	/*
+ 	 * Since we need to return only the last row of the matrix and we can use 
+ 	 * only current and previous row in calculation, we can allocate the only
+ 	 * memory for two rows.
+ 	 */
+ 	row = (float *)palloc(2 * (m + 1) * sizeof(float));
+ 	prev_row = row + (m + 1);
+ 
+ 	/* M[0,0] = 1 */
+ 	row[0] = 1.0f;
+ 	for (i = 1; i <= n; i++)
+ 	{
+ 		float t = p[i - 1];
+ 		/* Swap rows */
+ 		tmp = row;
+ 		row = prev_row;
+ 		prev_row = tmp;
+ 		/* Calculate next row */
+ 		for (j = 0; j <= i && j <= m; j++)
+ 		{
+ 			float val = 0.0f;
+ 			if (j < i)
+ 				val += prev_row[j] * (1.0f - t);
+ 			if (j > 0)
+ 				val += prev_row[j - 1] * t;
+ 			row[j] = val;
+ 
+ 		}
+ 	}	
+ 	return row;
+ }
+ 
+ /*
+  * Array selectivity estimation based on most common elements statistics for
+  * "column <@ const" case.
+  */
+ static Selectivity
+ mcelem_array_contained_selec(Datum *mcelem, int nmcelem, float4 *numbers, 
+ 	Datum *array_data, int nitems, Datum *hist, int nhist, Oid operator)
+ {
+ 	int	mcelem_index, i;
+ 	float selec, minfreq, default_freq, nullelem_freq;
+ 	float *dist, *mcelem_dist, *hist_part;
+ 	float avg_length, mult, rest;
+ 	float *elem_selec;
+ 	
+ 	/*
+ 	 * elem_selec is array of frequences estimate of elements in constant.
+ 	 */	
+ 	elem_selec = (float *)palloc(sizeof(float) * nitems);
+ 
+ 	if (mcelem)
+ 	{
+ 		/*
+ 		 * Grab the lowest frequency. compute_array_stats() stored it for us
+ 		 * in the one before the last cell of the Numbers array.
+ 		 * See array_typanalyze.c
+ 		 */
+ 		nullelem_freq = numbers[nmcelem];
+ 		minfreq = numbers[nmcelem + 1];
+ 		avg_length = numbers[nmcelem + 3];
+ 	}else{
+ 		/*
+ 		 * Without statistics set minfreq so that minfreq/2 = DEFAULT_CONT_SEL
+ 		 */
+ 		nullelem_freq = 0.0f;
+ 		minfreq = 2 * DEFAULT_CONT_SEL;
+ 		avg_length = 10.0f;
+ 	}
+ 	
+ 	/*
+ 	 * Rest is a average length of elements which aren't present in mcelem.
+ 	 */
+ 	rest = avg_length;
+ 
+ 	default_freq = Min(DEFAULT_CONT_SEL, minfreq / 2);
+ 
+ 	mcelem_index = 0;
+ 	
+ 	/*
+ 	 * mult is the multiplier that presents estimate of probability that each
+ 	 * mcelem which is not present in constant doesn't occur. 
+ 	 */
+ 	mult = 1.0f;
+ 	
+ 	for (i = 0; i < nitems; i++)
+ 	{
+ 		bool found = false;
+ 		/* Comparison with previous value in order to guarantee uniquness */
+ 		if (i > 0)
+ 		{
+ 			if (!element_compare(&array_data[i - 1], &array_data[i]))
+ 				continue;
+ 		}
+ 		
+ 		/*
+ 		 * Iterate over mcelem until find mcelem that is greater or equal
+ 		 * to element of constant. Simultaneously taking care about rest and
+ 		 * mult. If that mcelem is found then fill corresponding elem_selec.
+ 		 */
+ 		while (mcelem_index < nmcelem)
+ 		{
+ 			int cmp = element_compare(&mcelem[mcelem_index], &array_data[i]);
+ 			if (cmp < 0)
+ 			{
+ 				mult *= (1.0f - numbers[mcelem_index]);
+ 				rest -= numbers[mcelem_index];
+ 				mcelem_index++;
+ 			}
+ 			else
+ 			{
+ 				/* mcelem is found */
+ 				if (cmp == 0)
+ 				{
+ 					elem_selec[i] = numbers[mcelem_index];
+ 					rest -= numbers[mcelem_index];
+ 					found = true;
+ 				}
+ 				break;
+ 			}
+ 		}
+ 
+ 		if (found)
+ 		{
+ 			mcelem_index++;
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * The element is not in MCELEM.  Punt, but assume that the
+ 			 * selectivity cannot be more than minfreq / 2.
+ 			 */
+ 			elem_selec[i] = Min(DEFAULT_CONT_SEL, minfreq / 2);
+ 		}
+ 	}
+ 	
+ 	/*
+ 	 * Taking into account rest of mcelem in rest and mult calculation.
+ 	 */	
+ 	while (mcelem_index < nmcelem)
+ 	{
+ 		mult *= (1.0f - numbers[mcelem_index]);
+ 		rest -= numbers[mcelem_index];
+ 		mcelem_index++;
+ 	}
+ 	
+ 	
+ 	if (nhist > 0)	
+ 	{
+ 		/*
+ 		 * If we have histogram then calculate probabilities of lengths for
+ 		 * mcelems and constant elements from assumption of independent elements
+ 		 * occurence.
+ 		 */
+ 		dist = calc_distr(elem_selec, nitems, nitems);
+ 		mcelem_dist = calc_distr(numbers, nmcelem, nitems);
+ 
+ 		hist_part = (float *)palloc((nitems + 1) * sizeof(float));
+ 		calc_hist(hist, nhist, hist_part, nitems);
+ 		
+ 		selec = 0.0f;
+ 
+ 		for (i = 0; i <= nitems; i++)
+ 		{
+ 			/*
+ 			 * mult * dist[i] / mcelem_dist[i] gives us probability probability
+ 			 * of qual matching from assumption of independent element occurence
+ 			 * with condition that length = i.
+ 			 */
+ 			if (hist_part[i] > 0)
+ 				selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/*
+ 		 * We don't have histogram. So use more rough estimate.
+ 		 */
+ 		selec = mult;
+ 	}
+ 	
+ 	/*
+ 	 * We should take care about elements which aren't in mcelem... somehow...
+ 	 */
+ 	selec *= exp(-rest);
+ 	
+ 	/* Take into account occurence of NULL element. */
+ 	selec *= (1.0f - nullelem_freq);
+ 
+ 	CLAMP_PROBABILITY(selec);
+ 
+ 	return selec;
+ }
+ 
+ /*
+  * Comparison function for elements. Based on default comparison function for
+  * array element data type.
+  */
+ static int
+ element_compare(const void *key1, const void *key2)
+ {
+ 	const Datum *d1 = (const Datum *) key1;
+ 	const Datum *d2 = (const Datum *) key2;
+ 
+ 	cmpfunc.arg[0] = *d1;
+ 	cmpfunc.arg[1] = *d2;
+ 	cmpfunc.argnull[0] = false;
+ 	cmpfunc.argnull[1] = false;
+ 	cmpfunc.isnull = false;
+ 	return DatumGetInt32(FunctionCallInvoke(&cmpfunc));
+ }
*** /dev/null
--- b/src/backend/utils/adt/array_typanalyze.c
***************
*** 0 ****
--- 1,726 ----
+ /*-------------------------------------------------------------------------
+  *
+  * array_typanalyze.c
+  *	  functions for gathering statistics from array columns
+  *
+  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+  *
+  *
+  * IDENTIFICATION
+  *	  src/backend/tsearch/array_typanalyze.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ 
+ #include "postgres.h"
+ #include "access/hash.h"
+ #include "catalog/pg_operator.h"
+ #include "commands/vacuum.h"
+ #include "utils/builtins.h"
+ #include "utils/hsearch.h"
+ #include "utils/typcache.h"
+ #include "utils/array.h"
+ #include "catalog/pg_am.h"
+ #include "catalog/pg_collation.h"
+ #include "commands/defrem.h"
+ #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
+ 
+ #define ARRAY_ANALYZE_CHECK_OID(x) \
+ 	if (!OidIsValid(x)) \
+ 	{ \
+ 		elog(INFO, "Can't collect statistics on %d array type. Array statistics collection requires default hash and btree opclasses for element type.", stats->attrtypid); \
+ 		stats->stats_valid = false; \
+ 		return; \
+ 	}
+ 
+ /* Element data type information for working with elements hash */
+ typedef struct
+ {
+ 	FunctionCallInfoData cmp, eq, hash;
+ 	bool typbyval;
+ } ElementTypeInfo;
+ 
+ static ElementTypeInfo element_type_info;
+ 
+ /* A hash table entry for the Lossy Counting algorithm */
+ typedef struct
+ {
+ 	Datum		key;			/* This is 'e' from the LC algorithm. */
+ 	bool		occurence;		/* Flag for unique counting */
+ 	int			frequency;		/* This is 'f'. */
+ 	int			delta;			/* And this is 'delta'. */
+ } TrackItem;
+ 
+ typedef struct
+ {
+ 	int length;
+ 	int frequency;
+ } LengthItem;
+ 
+ Datum array_typanalyze(PG_FUNCTION_ARGS);
+ static void compute_array_stats(VacAttrStats *stats, 
+ 	AnalyzeAttrFetchFunc fetchfunc,	int samplerows,	double totalrows);
+ static void prune_element_hashtable(HTAB *elements_tab, int b_current);
+ static uint32 element_hash(const void *key, Size keysize);
+ static int element_match(const void *key1, const void *key2, Size keysize);
+ static int element_compare(const void *key1, const void *key2);
+ static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
+ static int trackitem_compare_element(const void *e1, const void *e2);
+ static int lengthitem_compare_element(const void *e1, const void *e2);
+ 
+ /*
+  *	array_typanalyze -- a custom typanalyze function for array columns
+  */
+ Datum
+ array_typanalyze(PG_FUNCTION_ARGS)
+ {
+ 	VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
+ 	Form_pg_attribute attr = stats->attr;
+ 
+ 	/* If the attstattarget column is negative, use the default value */
+ 	/* NB: it is okay to scribble on stats->attr since it's a copy */
+ 	if (attr->attstattarget < 0)
+ 		attr->attstattarget = default_statistics_target;
+ 
+ 	stats->compute_stats = compute_array_stats;
+ 	/* see comment about the choice of minrows in commands/analyze.c */
+ 	stats->minrows = 300 * attr->attstattarget;
+ 
+ 	PG_RETURN_BOOL(true);
+ }
+ 
+ /*
+  *	compute_array_stats() -- compute statistics for a array column
+  *
+  *	This function uses the same lossy counting algorithm for array element
+  *	frequencies statistics as compute_tsvector_stats do for ts_vectors. 
+  *	See compute_tsvector_stats for detailed comments on this algorithm.
+  *	In spite of ts_vector array elements may be not unique in array. That's why
+  *	this function takes additional care about uniqueness of counting.
+  *	This function also collects histogram of array lengths distribution.
+  */
+ static void
+ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
+ 					int samplerows, double totalrows)
+ {
+ 	int			num_mcelem;
+ 	int			null_cnt = 0;
+ 	
+ 	/* We should count not only null array values, but also null array elements */
+ 	int			null_elem_cnt = 0.0;
+ 	
+ 	double		total_width = 0.0;
+ 	double		total_length = 0.0;
+ 
+ 	/* This is D from the LC algorithm. */
+ 	HTAB	   *elements_tab;
+ 	HASHCTL		elem_hash_ctl;
+ 	HASH_SEQ_STATUS scan_status;
+ 
+ 	/* This is the current bucket number from the LC algorithm */
+ 	int			b_current;
+ 
+ 	/* This is 'w' from the LC algorithm */
+ 	int			bucket_width;
+ 	int			array_no,
+ 				element_no;
+ 	Datum		hash_key;
+ 	TrackItem  *item;
+ 
+ 	int			lengths_count;
+ 	int			length_index;
+ 	int			slot_idx = 0;
+ 	HTAB	   *length_tab;
+ 	HASHCTL		length_hash_ctl;
+ 	LengthItem *length_item;
+ 	LengthItem *sorted_length_tab;
+ 
+ 	/*
+ 	 * Most part of array operators, which selectivity is estimated by
+ 	 * this statistics, takes care only one occurence of element in array.
+ 	 * That's why we should take care about count element occurence only
+ 	 * once per array. To clean occurence flag for each array by iterating
+ 	 * over all hash table can be too expensive. That's why we store pointers
+ 	 * to hash items contain elements which occur in last array.
+ 	 */
+ 	TrackItem **occurences = NULL;
+ 	int			occurences_count = 0,
+ 				occurence_index;
+ 
+ 	TypeCacheEntry *typentry;
+ 	Oid         hash_opclass,
+ 				hash_opfamily,
+ 				element_typeid,
+ 				hash_oroc;
+ 	FmgrInfo	hash_func_info;
+ 
+ 	/* Gathering all necessary information about element data type. */
+ 
+ 	element_typeid = stats->attrtype->typelem;
+ 
+ 	if (!OidIsValid(element_typeid))
+ 		elog(ERROR, "array_typanalyze was invoked with %d non-array type", stats->attrtypid);
+ 
+ 	typentry = lookup_type_cache(element_typeid, TYPECACHE_EQ_OPR |
+ 		TYPECACHE_CMP_PROC | TYPECACHE_EQ_OPR_FINFO | TYPECACHE_CMP_PROC_FINFO );
+ 	ARRAY_ANALYZE_CHECK_OID(typentry->cmp_proc);
+ 	ARRAY_ANALYZE_CHECK_OID(typentry->eq_opr);
+ 
+ 	hash_opclass = GetDefaultOpClass(element_typeid, HASH_AM_OID);
+ 	ARRAY_ANALYZE_CHECK_OID(hash_opclass);
+ 
+ 	hash_opfamily = get_opclass_family(hash_opclass);
+ 	ARRAY_ANALYZE_CHECK_OID(hash_opfamily);
+ 
+ 	hash_oroc = get_opfamily_proc(hash_opfamily, element_typeid,
+ 		element_typeid,  HASHPROC);
+ 	ARRAY_ANALYZE_CHECK_OID(hash_oroc);
+ 
+ 	fmgr_info(hash_oroc, &hash_func_info);
+ 
+ 	InitFunctionCallInfoData(element_type_info.cmp, &typentry->cmp_proc_finfo, 2, DEFAULT_COLLATION_OID, NULL, NULL);
+ 	InitFunctionCallInfoData(element_type_info.eq, &typentry->eq_opr_finfo, 2, DEFAULT_COLLATION_OID, NULL, NULL);
+ 	InitFunctionCallInfoData(element_type_info.hash, &hash_func_info, 1, DEFAULT_COLLATION_OID, NULL, NULL);
+ 	element_type_info.typbyval = typentry->typbyval;
+ 
+ 	/*
+ 	 * We want statistics_target * 10 elements in the MCELEM array.	This
+ 	 * multiplier is pretty arbitrary, but is meant to reflect the fact that
+ 	 * the number of individual elements tracked in pg_statistic ought to
+ 	 * be more than the number of values for a simple scalar column.
+ 	 */
+ 	num_mcelem = stats->attr->attstattarget * 10;
+ 
+ 	/*
+ 	 * We set bucket width equal to (num_mcelem + 10) / 0.007 as per the
+ 	 * comment above.
+ 	 */
+ 	bucket_width = (num_mcelem + 10) * 1000 / 7;
+ 
+ 	/*
+ 	 * Create the hashtable. It will be in local memory, so we don't need to
+ 	 * worry about overflowing the initial size. Also we don't need to pay any
+ 	 * attention to locking and memory management.
+ 	 */
+ 	MemSet(&elem_hash_ctl, 0, sizeof(elem_hash_ctl));
+ 	elem_hash_ctl.keysize = sizeof(Datum);
+ 	elem_hash_ctl.entrysize = sizeof(TrackItem);
+ 	elem_hash_ctl.hash = element_hash;
+ 	elem_hash_ctl.match = element_match;
+ 	elem_hash_ctl.hcxt = CurrentMemoryContext;
+ 	elements_tab = hash_create("Analyzed elements table",
+ 							  bucket_width * 7,
+ 							  &elem_hash_ctl,
+ 					HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
+ 	
+ 	/*
+ 	 * hashtable for arrays lengths.
+ 	 */
+ 	MemSet(&length_hash_ctl, 0, sizeof(length_hash_ctl));
+ 	length_hash_ctl.keysize = sizeof(int);
+ 	length_hash_ctl.entrysize = sizeof(LengthItem);
+ 	length_hash_ctl.hcxt = CurrentMemoryContext;
+ 	length_tab = hash_create("Array length table",
+ 							  64,
+ 							  &length_hash_ctl,
+ 					HASH_ELEM | HASH_CONTEXT);
+ 
+ 	/* Initialize counters. */
+ 	b_current = 1;
+ 	element_no = 0;
+ 
+ 	/* Loop over the arrays. */
+ 	for (array_no = 0; array_no < samplerows; array_no++)
+ 	{
+ 		Datum		value;
+ 		bool		isnull;
+ 		bool		null_present;
+ 		ArrayType  *array;
+ 		char	   *ptr;
+ 		bits8	   *bitmap;
+ 		int			bitmask;
+ 		int			j;
+ 		int			ndims;
+ 		int		   *dims;
+ 		int			nitems;
+ 		bool		length_found;
+ 
+ 		vacuum_delay_point();
+ 
+ 		value = fetchfunc(stats, array_no, &isnull);
+ 
+ 		/*
+ 		 * Check for null/nonnull.
+ 		 */
+ 		if (isnull)
+ 		{
+ 			null_cnt++;
+ 			continue;
+ 		}
+ 
+ 		/*
+ 		 * Add up widths for average-width calculation.  Since it's a
+ 		 * array, we know it's varlena.  As in the regular
+ 		 * compute_minimal_stats function, we use the toasted width for this
+ 		 * calculation.
+ 		 */
+ 		total_width += VARSIZE_ANY(DatumGetPointer(value));
+ 
+ 		/*
+ 		 * Now detoast the array if needed.
+ 		 */
+ 		array = DatumGetArrayTypeP(value);
+ 		ptr = ARR_DATA_PTR(array);
+ 		bitmap = ARR_NULLBITMAP(array);
+ 		bitmask = 1;
+ 		ndims = ARR_NDIM(array);
+ 		dims = ARR_DIMS(array);
+ 		nitems = ArrayGetNItems(ndims, dims);
+ 
+ 		/*
+ 		 * Check if we have enough of memory to store element occurences in
+ 		 * one array.
+ 		 */
+ 		if (nitems > occurences_count)
+ 		{
+ 			occurences_count = 2 * nitems;
+ 			if (occurences)
+ 				occurences = (TrackItem **)repalloc(occurences,
+ 					sizeof(TrackItem *)*occurences_count);
+ 			else
+ 				occurences = (TrackItem **)palloc(
+ 					sizeof(TrackItem *)*occurences_count);
+ 		}
+ 		occurence_index = 0;
+ 
+ 		null_present = false;
+ 
+ 		/*
+ 		 * We loop through the elements in the array and add them to our
+ 		 * tracking hashtable.	Note: the hashtable entries will point into
+ 		 * the (detoasted) array value, therefore we cannot free that
+ 		 * storage until we're done.
+ 		 */
+ 		for (j = 0; j < nitems; j++)
+ 		{
+ 			bool		found;
+ 			bool		isnull;
+ 
+ 			/* Get elements, checking for NULL */
+ 			if (bitmap && (*bitmap & bitmask) == 0)
+ 			{
+ 				hash_key = (Datum) 0;
+ 				isnull = true;
+ 				null_present = true;
+ 			}
+ 			else
+ 			{
+ 				/* Get element value */
+ 				hash_key = fetch_att(ptr, typentry->typbyval, typentry->typlen);
+ 				isnull = false;
+ 				/*
+ 				 * We should allocate memory for element if it isn't passing
+ 				 * by value, because array will be freed after that loop.
+ 				 */
+ 				if (!typentry->typbyval)
+ 				{
+ 					Datum tmp;
+ 					int length;
+ 					length = (typentry->typlen == -1) ?
+ 						VARSIZE(hash_key) : typentry->typlen;
+ 					tmp = (Datum)MemoryContextAlloc(stats->anl_context, length);
+ 					memcpy((void *)tmp, (void *)hash_key, length);
+ 					hash_key = tmp;
+ 				}
+ 				ptr = att_addlength_pointer(ptr, typentry->typlen, ptr);
+ 				ptr = (char *) att_align_nominal(ptr, typentry->typalign);
+ 			}
+ 
+ 			/* Advance bitmap pointers if any */
+ 			bitmask <<= 1;
+ 			if (bitmask == 0x100)
+ 			{
+ 				if (bitmap)
+ 					bitmap++;
+ 				bitmask = 1;
+ 			}
+ 
+ 			/* No null element processing other then flag setting here */
+ 			if (isnull) continue;
+ 
+ 			/* Lookup current element in hashtable, adding it if new */
+ 			item = (TrackItem *) hash_search(elements_tab,
+ 											 (const void *) &hash_key,
+ 											 HASH_ENTER, &found);
+ 
+ 			if (found)
+ 			{
+ 				/* 
+ 				 * The element is already on the tracking list. If it is the
+ 				 * first occurence in array then update element frequency.
+ 				 */
+ 				if (!item->occurence)
+ 				{
+ 					item->frequency++;
+ 					item->occurence = true;
+ 					occurences[occurence_index++] = item;
+ 				}
+ 			}
+ 			else
+ 			{
+ 				/* Initialize new tracking list element */
+ 				item->frequency = 1;
+ 				item->delta = b_current - 1;
+ 				item->occurence = true;
+ 				occurences[occurence_index++] = item;
+ 			}
+ 
+ 			/* element_no is the number of elements processed (ie N) */
+ 			element_no++;
+ 
+ 			/* We prune the D structure after processing each bucket */
+ 			if (element_no % bucket_width == 0)
+ 			{
+ 				prune_element_hashtable(elements_tab, b_current);
+ 				b_current++;
+ 			}
+ 		}
+ 		/* Count null element only once per array */
+ 		if (null_present)
+ 			null_elem_cnt++;
+ 		
+ 		/* Update frequency of particular array length. */
+ 		length_item = (LengthItem *) hash_search(length_tab,
+ 											 &occurence_index,
+ 											 HASH_ENTER, &length_found);
+ 		if (length_found)
+ 		{
+ 			length_item->frequency++;
+ 		}
+ 		else
+ 		{
+ 			length_item->length = occurence_index;
+ 			length_item->frequency = 1;
+ 		}
+ 		total_length += occurence_index;
+ 		
+ 		/* When we end processing of particular array we should clean occurence flag */
+ 		for (j = 0; j < occurence_index; j++)
+ 			occurences[j]->occurence = false;
+ 
+ 		/* We should free memory from array if it was copied during detoast. */
+ 		if ((Datum)array != value)
+ 			pfree((void *)array);
+ 	}
+ 	
+ 	/* Fill histogram of arrays lengths. */
+ 	lengths_count = hash_get_num_entries(length_tab);
+ 	if (lengths_count > 0)
+ 	{
+ 		int			num_hist = stats->attr->attstattarget;
+ 		int			delta;
+ 		int			frac;
+ 		int			i;
+ 		Datum	   *hist_values;
+ 		
+ 		/* Copy lengths statistics from hashtab to array and sort them. */		
+ 		length_index = 0;
+ 		sorted_length_tab = (LengthItem *)palloc(sizeof(LengthItem) * lengths_count);
+ 		hash_seq_init(&scan_status, length_tab);
+ 		while ((length_item = (LengthItem *) hash_seq_search(&scan_status)) != NULL)
+ 		{
+ 			memcpy(&sorted_length_tab[length_index], length_item, 
+ 				   sizeof(LengthItem));
+ 			length_index++;
+ 		}
+ 		qsort(sorted_length_tab, lengths_count, sizeof(LengthItem),
+ 			  lengthitem_compare_element);
+ 
+ 		/* Histogram should be stored in anl_context. */
+ 		hist_values = (Datum *)MemoryContextAlloc(stats->anl_context, 
+ 												  sizeof(Datum) * num_hist);
+ 		/* Fill histogram by hashtab. */
+ 		delta = samplerows - null_cnt - 1;
+ 		length_index = 0;
+ 		frac = sorted_length_tab[0].frequency * (num_hist - 1);
+ 		for (i = 0; i < num_hist; i++)
+ 		{
+ 			hist_values[i] = Int32GetDatum(sorted_length_tab[length_index].length);
+ 			frac -= delta;
+ 			while (frac <= 0)
+ 			{
+ 				length_index++;
+ 				frac += sorted_length_tab[length_index].frequency * (num_hist - 1);
+ 			}
+ 		}
+ 		
+ 		stats->stakind[slot_idx] = STATISTIC_KIND_HISTOGRAM;
+ 		stats->staop[slot_idx] = Int4EqualOperator;
+ 		stats->stavalues[slot_idx] = hist_values;
+ 		stats->numvalues[slot_idx] = num_hist;
+ 		/* We are storing values of element type */
+ 		stats->statypid[slot_idx] = INT4OID;
+ 		stats->statyplen[slot_idx] = 4;
+ 		stats->statypbyval[slot_idx] = true;
+ 		stats->statypalign[slot_idx] = 'i';
+ 		slot_idx++;
+ 	}
+ 
+ 	/* We can only compute real stats if we found some non-null values. */
+ 	if (null_cnt < samplerows)
+ 	{
+ 		int			nonnull_cnt = samplerows - null_cnt;
+ 		int			i;
+ 		TrackItem **sort_table;
+ 		int			track_len;
+ 		int			cutoff_freq;
+ 		int			minfreq,
+ 					maxfreq;
+ 
+ 		stats->stats_valid = true;
+ 		/* Do the simple null-frac and average width stats */
+ 		stats->stanullfrac = (double) null_cnt / (double) samplerows;
+ 		stats->stawidth = total_width / (double) nonnull_cnt;
+ 
+ 		/* Assume it's a unique column (see notes above) */
+ 		stats->stadistinct = -1.0;
+ 
+ 		/*
+ 		 * Construct an array of the interesting hashtable items, that is,
+ 		 * those meeting the cutoff frequency (s - epsilon)*N.	Also identify
+ 		 * the minimum and maximum frequencies among these items.
+ 		 *
+ 		 * Since epsilon = s/10 and bucket_width = 1/epsilon, the cutoff
+ 		 * frequency is 9*N / bucket_width.
+ 		 */
+ 		cutoff_freq = 9 * element_no / bucket_width;
+ 
+ 		i = hash_get_num_entries(elements_tab);	/* surely enough space */
+ 		sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * i);
+ 
+ 		hash_seq_init(&scan_status, elements_tab);
+ 		track_len = 0;
+ 		minfreq = element_no;
+ 		maxfreq = 0;
+ 		while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
+ 		{
+ 			if (item->frequency > cutoff_freq)
+ 			{
+ 				sort_table[track_len++] = item;
+ 				minfreq = Min(minfreq, item->frequency);
+ 				maxfreq = Max(maxfreq, item->frequency);
+ 			}
+ 		}
+ 		Assert(track_len <= i);
+ 
+ 		/* emit some statistics for debug purposes */
+ 		elog(DEBUG3, "array: target # mces = %d, bucket width = %d, "
+ 			 "# elements = %d, hashtable size = %d, usable entries = %d",
+ 			 num_mcelem, bucket_width, element_no, i, track_len);
+ 
+ 		/*
+ 		 * If we obtained more elements than we really want, get rid of those
+ 		 * with least frequencies.	The easiest way is to qsort the array into
+ 		 * descending frequency order and truncate the array.
+ 		 */
+ 		if (num_mcelem < track_len)
+ 		{
+ 			qsort(sort_table, track_len, sizeof(TrackItem *),
+ 				  trackitem_compare_frequencies_desc);
+ 			/* reset minfreq to the smallest frequency we're keeping */
+ 			minfreq = sort_table[num_mcelem - 1]->frequency;
+ 		}
+ 		else
+ 			num_mcelem = track_len;
+ 
+ 		/* Generate MCELEM slot entry */
+ 		if (num_mcelem > 0)
+ 		{
+ 			MemoryContext old_context;
+ 			Datum	   *mcelem_values;
+ 			float4	   *mcelem_freqs;
+ 
+ 			/*
+ 			 * We want to store statistics sorted on the element value using
+ 			 * default comparison function for element type. This allow s
+ 			 * faster searching in selectivity estimation functions.
+ 			 */
+ 			qsort(sort_table, num_mcelem, sizeof(TrackItem *),
+ 				  trackitem_compare_element);
+ 
+ 			/* Must copy the target values into anl_context */
+ 			old_context = MemoryContextSwitchTo(stats->anl_context);
+ 
+ 			/*
+ 			 * We sorted statistics on the element value, but we want to be
+ 			 * able to find out the minimal and maximal frequency without
+ 			 * going through all the values. Also we want to keep frequency
+ 			 * of null element, because it's valuable for selectivity 
+ 			 * estimation. We keep those three extra frequencies in three extra
+ 			 * cells in mcelem_freqs.
+ 			 */
+ 			mcelem_values = (Datum *) palloc(num_mcelem * sizeof(Datum));
+ 			mcelem_freqs = (float4 *) palloc((num_mcelem + 3) * sizeof(float4));
+ 
+ 			/*
+ 			 * See comments above about use of nonnull_cnt as the divisor for
+ 			 * the final frequency estimates.
+ 			 */
+ 			for (i = 0; i < num_mcelem; i++)
+ 			{
+ 				TrackItem  *item = sort_table[i];
+ 
+ 				mcelem_values[i] = item->key;
+ 				mcelem_freqs[i] = (double) item->frequency / (double) nonnull_cnt;
+ 			}
+ 			mcelem_freqs[i++] = (double) null_elem_cnt / (double) nonnull_cnt;
+ 			mcelem_freqs[i++] = (double) minfreq / (double) nonnull_cnt;
+ 			mcelem_freqs[i++] = (double) maxfreq / (double) nonnull_cnt;
+ 			mcelem_freqs[i++] = (double) total_length / (double) nonnull_cnt;
+ 			MemoryContextSwitchTo(old_context);
+ 
+ 			stats->stakind[slot_idx] = STATISTIC_KIND_MCELEM;
+ 			stats->staop[slot_idx] = typentry->eq_opr;
+ 			stats->stanumbers[slot_idx] = mcelem_freqs;
+ 			/* See above comment about three extra frequency fields */
+ 			stats->numnumbers[slot_idx] = num_mcelem + 4;
+ 			stats->stavalues[slot_idx] = mcelem_values;
+ 			stats->numvalues[slot_idx] = num_mcelem;
+ 			/* We are storing values of element type */
+ 			stats->statypid[slot_idx] = element_typeid;
+ 			stats->statyplen[slot_idx] = typentry->typlen;
+ 			stats->statypbyval[slot_idx] = typentry->typbyval;
+ 			stats->statypalign[slot_idx] = typentry->typalign;
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/* We found only nulls; assume the column is entirely null */
+ 		stats->stats_valid = true;
+ 		stats->stanullfrac = 1.0;
+ 		stats->stawidth = 0;	/* "unknown" */
+ 		stats->stadistinct = 0.0;		/* "unknown" */
+ 	}
+ 
+ 	/*
+ 	 * We don't need to bother cleaning up any of our temporary palloc's. The
+ 	 * hashtable should also go away, as it used a child memory context.
+ 	 */
+ }
+ 
+ /*
+  *	A function to prune the D structure from the Lossy Counting algorithm.
+  *	Consult compute_tsvector_stats() for wider explanation.
+  */
+ static void
+ prune_element_hashtable(HTAB *elements_tab, int b_current)
+ {
+ 	HASH_SEQ_STATUS scan_status;
+ 	TrackItem  *item;
+ 
+ 	hash_seq_init(&scan_status, elements_tab);
+ 	while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
+ 	{
+ 		if (item->frequency + item->delta <= b_current)
+ 		{
+ 			Datum value = item->key;
+ 			if (hash_search(elements_tab, (const void *) &item,
+ 							HASH_REMOVE, NULL) == NULL)
+ 				elog(ERROR, "hash table corrupted");
+ 			/* We should free memory if element is not passed by value */
+ 			if (!element_type_info.typbyval)
+ 				pfree((void *)value);
+ 		}
+ 	}
+ }
+ 
+ /*
+  * Hash functions for elements. Based on default hash opclass.
+  */
+ static uint32
+ element_hash(const void *key, Size keysize)
+ {
+ 	const Datum *l = (const Datum *) key;
+ 
+ 	element_type_info.hash.arg[0] = *l;
+ 	element_type_info.hash.argnull[0] =false;
+ 	element_type_info.hash.isnull = false;
+ 	return DatumGetInt32(FunctionCallInvoke(&element_type_info.hash));
+ }
+ 
+ /*
+  * Matching function for elements, to be used in hashtable lookups.
+  */
+ static int
+ element_match(const void *key1, const void *key2, Size keysize)
+ {
+ 	const Datum *d1 = (const Datum *) key1;
+ 	const Datum *d2 = (const Datum *) key2;
+ 
+ 	element_type_info.eq.arg[0] = *d1;
+ 	element_type_info.eq.arg[1] = *d2;
+ 	element_type_info.eq.argnull[0] = false;
+ 	element_type_info.eq.argnull[1] = false;
+ 	element_type_info.eq.isnull = false;
+ 	return !DatumGetInt32(FunctionCallInvoke(&element_type_info.eq));
+ }
+ 
+ /*
+  * Comparison function for elements, based of default comparison function
+  * for element data type.
+  */
+ static int
+ element_compare(const void *key1, const void *key2)
+ {
+ 	const Datum *d1 = (const Datum *) key1;
+ 	const Datum *d2 = (const Datum *) key2;
+ 
+ 	element_type_info.cmp.arg[0] = *d1;
+ 	element_type_info.cmp.arg[1] = *d2;
+ 	element_type_info.cmp.argnull[0] = false;
+ 	element_type_info.cmp.argnull[1] = false;
+ 	element_type_info.cmp.isnull = false;
+ 	return DatumGetInt32(FunctionCallInvoke(&element_type_info.cmp));
+ }
+ 
+ /*
+  *	qsort() comparator for sorting TrackItems on frequencies (descending sort)
+  */
+ static int
+ trackitem_compare_frequencies_desc(const void *e1, const void *e2)
+ {
+ 	const TrackItem *const * t1 = (const TrackItem *const *) e1;
+ 	const TrackItem *const * t2 = (const TrackItem *const *) e2;
+ 
+ 	return (*t2)->frequency - (*t1)->frequency;
+ }
+ 
+ /*
+  *	qsort() comparator for sorting TrackItems on elements
+  */
+ static int
+ trackitem_compare_element(const void *e1, const void *e2)
+ {
+ 	const TrackItem *const * t1 = (const TrackItem *const *) e1;
+ 	const TrackItem *const * t2 = (const TrackItem *const *) e2;
+ 
+ 	return element_compare(&(*t1)->key, &(*t2)->key);
+ }
+ 
+ /*
+  *	qsort() comparator for sorting LengthItems on elements
+  */
+ static int
+ lengthitem_compare_element(const void *e1, const void *e2)
+ {
+ 	const LengthItem *t1 = (const LengthItem *) e1;
+ 	const LengthItem *t2 = (const LengthItem *) e2;
+ 
+ 	if (t1->length < t2->length)
+ 		return -1;
+ 	else if (t1->length == t2->length)
+ 		return 0;
+ 	else
+ 		return 1;
+ }
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
***************
*** 1697,1702 **** scalararraysel(PlannerInfo *root,
--- 1697,1724 ----
  	RegProcedure oprsel;
  	FmgrInfo	oprselproc;
  	Selectivity s1;
+ 	bool		varonleft;
+ 	Node	   *other;
+ 	VariableStatData vardata;
+ 
+ 	if (get_restriction_variable(root, clause->args, varRelid,
+ 								  &vardata, &other, &varonleft))
+ 	{
+ 		Oid elemtype;
+ 		elemtype = get_base_element_type(vardata.vartype);
+ 		if (elemtype != InvalidOid && IsA(other, Const))
+ 		{
+ 			if (((Const *) other)->constisnull)
+ 			{
+ 				ReleaseVariableStats(vardata);
+ 				return (Selectivity) 0.0;
+ 			}
+ 			s1 = calc_scalararraysel(&vardata, ((Const *) other)->constvalue, useOr);
+ 			ReleaseVariableStats(vardata);
+ 			return s1;
+ 		}
+ 		ReleaseVariableStats(vardata);
+ 	}
  
  	/*
  	 * First, look up the underlying operator's selectivity estimator. Punt if
*** a/src/include/catalog/pg_operator.h
--- b/src/include/catalog/pg_operator.h
***************
*** 128,133 **** DATA(insert OID =  95 ( "<"		   PGNSP PGUID b f f	21	21	16 520 524 int2lt scalar
--- 128,134 ----
  DESCR("less than");
  DATA(insert OID =  96 ( "="		   PGNSP PGUID b t t	23	23	16	96 518 int4eq eqsel eqjoinsel ));
  DESCR("equal");
+ #define Int4EqualOperator	98
  DATA(insert OID =  97 ( "<"		   PGNSP PGUID b f f	23	23	16 521 525 int4lt scalarltsel scalarltjoinsel ));
  DESCR("less than");
  DATA(insert OID =  98 ( "="		   PGNSP PGUID b t t	25	25	16	98 531 texteq eqsel eqjoinsel ));
***************
*** 1513,1524 **** DATA(insert OID = 2590 (  "|&>"    PGNSP PGUID b f f 718 718	16	 0	 0 circle_ove
  DESCR("overlaps or is above");
  
  /* overlap/contains/contained for arrays */
! DATA(insert OID = 2750 (  "&&"	   PGNSP PGUID b f f 2277 2277	16 2750  0 arrayoverlap areasel areajoinsel ));
  DESCR("overlaps");
! DATA(insert OID = 2751 (  "@>"	   PGNSP PGUID b f f 2277 2277	16 2752  0 arraycontains contsel contjoinsel ));
  DESCR("contains");
! DATA(insert OID = 2752 (  "<@"	   PGNSP PGUID b f f 2277 2277	16 2751  0 arraycontained contsel contjoinsel ));
  DESCR("is contained by");
  
  /* capturing operators to preserve pre-8.3 behavior of text concatenation */
  DATA(insert OID = 2779 (  "||"	   PGNSP PGUID b f f 25 2776	25	 0 0 textanycat - - ));
--- 1514,1528 ----
  DESCR("overlaps or is above");
  
  /* overlap/contains/contained for arrays */
! DATA(insert OID = 2750 (  "&&"	   PGNSP PGUID b f f 2277 2277	16 2750  0 arrayoverlap arraysel areajoinsel ));
  DESCR("overlaps");
! #define OID_ARRAY_OVERLAP_OP	2750
! DATA(insert OID = 2751 (  "@>"	   PGNSP PGUID b f f 2277 2277	16 2752  0 arraycontains arraysel contjoinsel ));
  DESCR("contains");
! #define OID_ARRAY_CONTAIN_OP	2751
! DATA(insert OID = 2752 (  "<@"	   PGNSP PGUID b f f 2277 2277	16 2751  0 arraycontained arraysel contjoinsel ));
  DESCR("is contained by");
+ #define OID_ARRAY_CONTAINED_OP	2752
  
  /* capturing operators to preserve pre-8.3 behavior of text concatenation */
  DATA(insert OID = 2779 (  "||"	   PGNSP PGUID b f f 25 2776	25	 0 0 textanycat - - ));
*** a/src/include/catalog/pg_proc.h
--- b/src/include/catalog/pg_proc.h
***************
*** 845,850 **** DATA(insert OID = 2334 (  array_agg_finalfn   PGNSP PGUID 12 1 0 0 f f f f f i 1
--- 845,855 ----
  DESCR("aggregate final function");
  DATA(insert OID = 2335 (  array_agg		   PGNSP PGUID 12 1 0 0 t f f f f i 1 0 2277 "2283" _null_ _null_ _null_ _null_ aggregate_dummy _null_ _null_ _null_ ));
  DESCR("concatenate aggregate input into an array");
+ DATA(insert OID = 3816 (  array_typanalyze PGNSP PGUID 12 1 0 0 f f f t f s 1 0 16 "2281" _null_ _null_ _null_ _null_ array_typanalyze _null_ _null_ _null_ ));
+ DESCR("array statistics collector");
+ #define ArrayTypanalyzeOid 3816
+ DATA(insert OID = 3817 (  arraysel		   PGNSP PGUID 12 1 0 0 f f f t f s 4 0 701 "2281 26 2281 23" _null_ _null_ _null_ _null_ arraysel _null_ _null_ _null_ ));
+ DESCR("array selectivity estimation functions");
  
  DATA(insert OID = 760 (  smgrin			   PGNSP PGUID 12 1 0 0 f f f t f s 1 0 210 "2275" _null_ _null_ _null_ _null_	smgrin _null_ _null_ _null_ ));
  DESCR("I/O");
*** a/src/include/catalog/pg_type.h
--- b/src/include/catalog/pg_type.h
***************
*** 431,466 **** DESCR("network IP address/netmask, network address");
  /* OIDS 900 - 999 */
  
  /* OIDS 1000 - 1099 */
! DATA(insert OID = 1000 (  _bool		 PGNSP PGUID -1 f b A f t \054 0	16 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1001 (  _bytea	 PGNSP PGUID -1 f b A f t \054 0	17 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1002 (  _char		 PGNSP PGUID -1 f b A f t \054 0	18 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1003 (  _name		 PGNSP PGUID -1 f b A f t \054 0	19 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1005 (  _int2		 PGNSP PGUID -1 f b A f t \054 0	21 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1006 (  _int2vector PGNSP PGUID -1 f b A f t \054 0	22 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1007 (  _int4		 PGNSP PGUID -1 f b A f t \054 0	23 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
  #define INT4ARRAYOID		1007
! DATA(insert OID = 1008 (  _regproc	 PGNSP PGUID -1 f b A f t \054 0	24 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1009 (  _text		 PGNSP PGUID -1 f b A f t \054 0	25 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 100 _null_ _null_ ));
  #define TEXTARRAYOID		1009
! DATA(insert OID = 1028 (  _oid		 PGNSP PGUID -1 f b A f t \054 0	26 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1010 (  _tid		 PGNSP PGUID -1 f b A f t \054 0	27 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1011 (  _xid		 PGNSP PGUID -1 f b A f t \054 0	28 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1012 (  _cid		 PGNSP PGUID -1 f b A f t \054 0	29 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1013 (  _oidvector PGNSP PGUID -1 f b A f t \054 0	30 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1014 (  _bpchar	 PGNSP PGUID -1 f b A f t \054 0 1042 0 array_in array_out array_recv array_send bpchartypmodin bpchartypmodout - i x f 0 -1 0 100 _null_ _null_ ));
! DATA(insert OID = 1015 (  _varchar	 PGNSP PGUID -1 f b A f t \054 0 1043 0 array_in array_out array_recv array_send varchartypmodin varchartypmodout - i x f 0 -1 0 100 _null_ _null_ ));
! DATA(insert OID = 1016 (  _int8		 PGNSP PGUID -1 f b A f t \054 0	20 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1017 (  _point	 PGNSP PGUID -1 f b A f t \054 0 600 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1018 (  _lseg		 PGNSP PGUID -1 f b A f t \054 0 601 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1019 (  _path		 PGNSP PGUID -1 f b A f t \054 0 602 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1020 (  _box		 PGNSP PGUID -1 f b A f t \073 0 603 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1021 (  _float4	 PGNSP PGUID -1 f b A f t \054 0 700 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
  #define FLOAT4ARRAYOID 1021
! DATA(insert OID = 1022 (  _float8	 PGNSP PGUID -1 f b A f t \054 0 701 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1023 (  _abstime	 PGNSP PGUID -1 f b A f t \054 0 702 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1024 (  _reltime	 PGNSP PGUID -1 f b A f t \054 0 703 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1025 (  _tinterval PGNSP PGUID -1 f b A f t \054 0 704 0 array_in array_out array_recv array_send - - - i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1027 (  _polygon	 PGNSP PGUID -1 f b A f t \054 0 604 0 array_in array_out array_recv array_send - - - d x f 0 -1 0 0 _null_ _null_ ));
  DATA(insert OID = 1033 (  aclitem	 PGNSP PGUID 12 f b U f t \054 0 0 1034 aclitemin aclitemout - - - - - i p f 0 -1 0 0 _null_ _null_ ));
  DESCR("access control list");
  #define ACLITEMOID		1033
--- 431,466 ----
  /* OIDS 900 - 999 */
  
  /* OIDS 1000 - 1099 */
! DATA(insert OID = 1000 (  _bool		 PGNSP PGUID -1 f b A f t \054 0	16 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1001 (  _bytea	 PGNSP PGUID -1 f b A f t \054 0	17 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1002 (  _char		 PGNSP PGUID -1 f b A f t \054 0	18 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1003 (  _name		 PGNSP PGUID -1 f b A f t \054 0	19 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1005 (  _int2		 PGNSP PGUID -1 f b A f t \054 0	21 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1006 (  _int2vector PGNSP PGUID -1 f b A f t \054 0	22 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1007 (  _int4		 PGNSP PGUID -1 f b A f t \054 0	23 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
  #define INT4ARRAYOID		1007
! DATA(insert OID = 1008 (  _regproc	 PGNSP PGUID -1 f b A f t \054 0	24 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1009 (  _text		 PGNSP PGUID -1 f b A f t \054 0	25 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 100 _null_ _null_ ));
  #define TEXTARRAYOID		1009
! DATA(insert OID = 1028 (  _oid		 PGNSP PGUID -1 f b A f t \054 0	26 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1010 (  _tid		 PGNSP PGUID -1 f b A f t \054 0	27 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1011 (  _xid		 PGNSP PGUID -1 f b A f t \054 0	28 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1012 (  _cid		 PGNSP PGUID -1 f b A f t \054 0	29 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1013 (  _oidvector PGNSP PGUID -1 f b A f t \054 0	30 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1014 (  _bpchar	 PGNSP PGUID -1 f b A f t \054 0 1042 0 array_in array_out array_recv array_send bpchartypmodin bpchartypmodout array_typanalyze i x f 0 -1 0 100 _null_ _null_ ));
! DATA(insert OID = 1015 (  _varchar	 PGNSP PGUID -1 f b A f t \054 0 1043 0 array_in array_out array_recv array_send varchartypmodin varchartypmodout array_typanalyze i x f 0 -1 0 100 _null_ _null_ ));
! DATA(insert OID = 1016 (  _int8		 PGNSP PGUID -1 f b A f t \054 0	20 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1017 (  _point	 PGNSP PGUID -1 f b A f t \054 0 600 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1018 (  _lseg		 PGNSP PGUID -1 f b A f t \054 0 601 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1019 (  _path		 PGNSP PGUID -1 f b A f t \054 0 602 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1020 (  _box		 PGNSP PGUID -1 f b A f t \073 0 603 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1021 (  _float4	 PGNSP PGUID -1 f b A f t \054 0 700 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
  #define FLOAT4ARRAYOID 1021
! DATA(insert OID = 1022 (  _float8	 PGNSP PGUID -1 f b A f t \054 0 701 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1023 (  _abstime	 PGNSP PGUID -1 f b A f t \054 0 702 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1024 (  _reltime	 PGNSP PGUID -1 f b A f t \054 0 703 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1025 (  _tinterval PGNSP PGUID -1 f b A f t \054 0 704 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ ));
! DATA(insert OID = 1027 (  _polygon	 PGNSP PGUID -1 f b A f t \054 0 604 0 array_in array_out array_recv array_send - - array_typanalyze d x f 0 -1 0 0 _null_ _null_ ));
  DATA(insert OID = 1033 (  aclitem	 PGNSP PGUID 12 f b U f t \054 0 0 1034 aclitemin aclitemout - - - - - i p f 0 -1 0 0 _null_ _null_ ));
  DESCR("access control list");
  #define ACLITEMOID		1033
*** a/src/include/utils/selfuncs.h
--- b/src/include/utils/selfuncs.h
***************
*** 164,169 **** extern Datum icregexnejoinsel(PG_FUNCTION_ARGS);
--- 164,171 ----
  extern Datum nlikejoinsel(PG_FUNCTION_ARGS);
  extern Datum icnlikejoinsel(PG_FUNCTION_ARGS);
  
+ extern Selectivity calc_scalararraysel(VariableStatData *vardata, Datum constval,
+             bool orClause);
  extern Selectivity booltestsel(PlannerInfo *root, BoolTestType booltesttype,
  			Node *arg, int varRelid,
  			JoinType jointype, SpecialJoinInfo *sjinfo);
*** a/src/test/regress/expected/arrays.out
--- b/src/test/regress/expected/arrays.out
***************
*** 421,426 **** SELECT 0 || ARRAY[1,2] || 3 AS "{0,1,2,3}";
--- 421,427 ----
   {0,1,2,3}
  (1 row)
  
+ ANALYZE array_op_test;
  SELECT * FROM array_op_test WHERE i @> '{32}' ORDER BY seqno;
   seqno |                i                |                                                                 t                                                                  
  -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------
*** a/src/test/regress/sql/arrays.sql
--- b/src/test/regress/sql/arrays.sql
***************
*** 196,201 **** SELECT ARRAY[[1,2],[3,4]] || ARRAY[5,6] AS "{{1,2},{3,4},{5,6}}";
--- 196,203 ----
  SELECT ARRAY[0,0] || ARRAY[1,1] || ARRAY[2,2] AS "{0,0,1,1,2,2}";
  SELECT 0 || ARRAY[1,2] || 3 AS "{0,1,2,3}";
  
+ ANALYZE array_op_test;
+ 
  SELECT * FROM array_op_test WHERE i @> '{32}' ORDER BY seqno;
  SELECT * FROM array_op_test WHERE i && '{32}' ORDER BY seqno;
  SELECT * FROM array_op_test WHERE i @> '{17}' ORDER BY seqno;
