multiset-20101115.patch

diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index 1394b21..57d012e 100644
*** a/src/backend/parser/gram.y
--- b/src/backend/parser/gram.y
*************** static RangeVar *makeRangeVarFromAnyName
*** 463,469 ****
   */
  
  /* ordinary key words in alphabetical order */
! %token <keyword> ABORT_P ABSOLUTE_P ACCESS ACTION ADD_P ADMIN AFTER
  	AGGREGATE ALL ALSO ALTER ALWAYS ANALYSE ANALYZE AND ANY ARRAY AS ASC
  	ASSERTION ASSIGNMENT ASYMMETRIC AT ATTRIBUTE AUTHORIZATION
  
--- 463,469 ----
   */
  
  /* ordinary key words in alphabetical order */
! %token <keyword> A ABORT_P ABSOLUTE_P ACCESS ACTION ADD_P ADMIN AFTER
  	AGGREGATE ALL ALSO ALTER ALWAYS ANALYSE ANALYZE AND ANY ARRAY AS ASC
  	ASSERTION ASSIGNMENT ASYMMETRIC AT ATTRIBUTE AUTHORIZATION
  
*************** static RangeVar *makeRangeVarFromAnyName
*** 506,512 ****
  	LEAST LEFT LEVEL LIKE LIMIT LISTEN LOAD LOCAL LOCALTIME LOCALTIMESTAMP
  	LOCATION LOCK_P LOGIN_P
  
! 	MAPPING MATCH MAXVALUE MINUTE_P MINVALUE MODE MONTH_P MOVE
  
  	NAME_P NAMES NATIONAL NATURAL NCHAR NEXT NO NOCREATEDB
  	NOCREATEROLE NOCREATEUSER NOINHERIT NOLOGIN_P NONE NOSUPERUSER
--- 506,512 ----
  	LEAST LEFT LEVEL LIKE LIMIT LISTEN LOAD LOCAL LOCALTIME LOCALTIMESTAMP
  	LOCATION LOCK_P LOGIN_P
  
! 	MAPPING MATCH MAXVALUE MEMBER MINUTE_P MINVALUE MODE MONTH_P MOVE MULTISET
  
  	NAME_P NAMES NATIONAL NATURAL NCHAR NEXT NO NOCREATEDB
  	NOCREATEROLE NOCREATEUSER NOINHERIT NOLOGIN_P NONE NOSUPERUSER
*************** static RangeVar *makeRangeVarFromAnyName
*** 528,534 ****
  	SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE SEQUENCES
  	SERIALIZABLE SERVER SESSION SESSION_USER SET SETOF SHARE
  	SHOW SIMILAR SIMPLE SMALLINT SOME STABLE STANDALONE_P START STATEMENT
! 	STATISTICS STDIN STDOUT STORAGE STRICT_P STRIP_P SUBSTRING SUPERUSER_P
  	SYMMETRIC SYSID SYSTEM_P
  
  	TABLE TABLES TABLESPACE TEMP TEMPLATE TEMPORARY TEXT_P THEN TIME TIMESTAMP
--- 528,534 ----
  	SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE SEQUENCES
  	SERIALIZABLE SERVER SESSION SESSION_USER SET SETOF SHARE
  	SHOW SIMILAR SIMPLE SMALLINT SOME STABLE STANDALONE_P START STATEMENT
! 	STATISTICS STDIN STDOUT STORAGE STRICT_P STRIP_P SUB SUBSTRING SUPERUSER_P
  	SYMMETRIC SYSID SYSTEM_P
  
  	TABLE TABLES TABLESPACE TEMP TEMPLATE TEMPORARY TEXT_P THEN TIME TIMESTAMP
*************** static RangeVar *makeRangeVarFromAnyName
*** 598,603 ****
--- 598,604 ----
  %nonassoc	NOTNULL
  %nonassoc	ISNULL
  %nonassoc	IS NULL_P TRUE_P FALSE_P UNKNOWN /* sets precedence for IS NULL, etc */
+ %nonassoc	MEMBER MULTISET SUB
  %left		'+' '-'
  %left		'*' '/' '%'
  %left		'^'
*************** a_expr:		c_expr									{ $$ = $1; }
*** 9358,9363 ****
--- 9359,9426 ----
  														 list_make1($1), @2),
  											 @2);
  				}
+ 			| a_expr MEMBER OF a_expr				%prec MEMBER
+ 				{
+ 					$$ = (Node *) makeA_Expr(AEXPR_OP_ANY,
+ 							list_make1(makeString("=")), $1, $4, @2);
+ 				}
+ 			| a_expr SUB MULTISET OF a_expr			%prec SUB
+ 				{
+ 					$$ = (Node *) makeA_Expr(AEXPR_OP,
+ 						list_make1(makeString("<@")), $1, $5, @2);
+ 				}
+ 			| a_expr IS A SET
+ 				{
+ 					FuncCall *n = makeNode(FuncCall);
+ 					n->funcname = SystemFuncName("multiset_is_a_set");
+ 					n->args = list_make1($1);
+ 					n->agg_order = NIL;
+ 					n->agg_star = FALSE;
+ 					n->agg_distinct = FALSE;
+ 					n->func_variadic = FALSE;
+ 					n->over = NULL;
+ 					n->location = @1;
+ 					$$ = (Node *)n;
+ 				}
+ 			| a_expr MULTISET UNION opt_all a_expr
+ 				{
+ 					FuncCall *n = makeNode(FuncCall);
+ 					n->funcname = SystemFuncName("multiset_union");
+ 					n->args = list_make3($1, $5, makeBoolAConst($4, -1));
+ 					n->agg_order = NIL;
+ 					n->agg_star = FALSE;
+ 					n->agg_distinct = FALSE;
+ 					n->func_variadic = FALSE;
+ 					n->over = NULL;
+ 					n->location = @1;
+ 					$$ = (Node *)n;
+ 				}
+ 			| a_expr MULTISET INTERSECT opt_all a_expr
+ 				{
+ 					FuncCall *n = makeNode(FuncCall);
+ 					n->funcname = SystemFuncName("multiset_intersect");
+ 					n->args = list_make3($1, $5, makeBoolAConst($4, -1));
+ 					n->agg_order = NIL;
+ 					n->agg_star = FALSE;
+ 					n->agg_distinct = FALSE;
+ 					n->func_variadic = FALSE;
+ 					n->over = NULL;
+ 					n->location = @1;
+ 					$$ = (Node *)n;
+ 				}
+ 			| a_expr MULTISET EXCEPT opt_all a_expr
+ 				{
+ 					FuncCall *n = makeNode(FuncCall);
+ 					n->funcname = SystemFuncName("multiset_except");
+ 					n->args = list_make3($1, $5, makeBoolAConst($4, -1));
+ 					n->agg_order = NIL;
+ 					n->agg_star = FALSE;
+ 					n->agg_distinct = FALSE;
+ 					n->func_variadic = FALSE;
+ 					n->over = NULL;
+ 					n->location = @1;
+ 					$$ = (Node *)n;
+ 				}
  		;
  
  /*
*************** ColLabel:	IDENT									{ $$ = $1; }
*** 11073,11079 ****
  /* "Unreserved" keywords --- available for use as any kind of name.
   */
  unreserved_keyword:
! 			  ABORT_P
  			| ABSOLUTE_P
  			| ACCESS
  			| ACTION
--- 11136,11143 ----
  /* "Unreserved" keywords --- available for use as any kind of name.
   */
  unreserved_keyword:
! 			  A
! 			| ABORT_P
  			| ABSOLUTE_P
  			| ACCESS
  			| ACTION
*************** unreserved_keyword:
*** 11200,11210 ****
--- 11264,11276 ----
  			| MAPPING
  			| MATCH
  			| MAXVALUE
+ 			| MEMBER
  			| MINUTE_P
  			| MINVALUE
  			| MODE
  			| MONTH_P
  			| MOVE
+ 			| MULTISET
  			| NAME_P
  			| NAMES
  			| NEXT
*************** unreserved_keyword:
*** 11290,11295 ****
--- 11356,11362 ----
  			| STORAGE
  			| STRICT_P
  			| STRIP_P
+ 			| SUB
  			| SUPERUSER_P
  			| SYSID
  			| SYSTEM_P
diff --git a/src/backend/utils/adt/array_userfuncs.c b/src/backend/utils/adt/array_userfuncs.c
index d7ec310..fddee6b 100644
*** a/src/backend/utils/adt/array_userfuncs.c
--- b/src/backend/utils/adt/array_userfuncs.c
***************
*** 15,21 ****
--- 15,25 ----
  #include "utils/array.h"
  #include "utils/builtins.h"
  #include "utils/lsyscache.h"
+ #include "utils/typcache.h"
+ 
  
+ static void check_concatinatable(Oid element_type1, Oid element_type2);
+ static void check_comparable(Oid element_type1, Oid element_type2);
  
  /*-----------------------------------------------------------------------------
   * array_push :
*************** array_push(PG_FUNCTION_ARGS)
*** 165,173 ****
--- 169,231 ----
   *		push an (n-1)D array onto the end of an nD array
   *----------------------------------------------------------------------------
   */
+ static Datum
+ array_cat_internal(PG_FUNCTION_ARGS, bool flatten);
  Datum
  array_cat(PG_FUNCTION_ARGS)
  {
+ 	return array_cat_internal(fcinfo, false);
+ }
+ 
+ /*
+  * flatten multi-dimensional array into one-dimensional
+  */
+ static ArrayType *
+ flatten_array(ArrayType *array)
+ {
+ 	ArrayType  *result;
+ 	int			ndims = ARR_NDIM(array);
+ 	int32		dataoffset;
+ 	int			ndatabytes,
+ 				nbytes;
+ 	int			nitems;
+ 
+ 	if (ndims <= 1)
+ 		return array;
+ 
+ 	nitems = ArrayGetNItems(ndims, ARR_DIMS(array));
+ 	ndatabytes = ARR_SIZE(array) - ARR_DATA_OFFSET(array);
+ 	if (ARR_HASNULL(array))
+ 	{
+ 		dataoffset = ARR_OVERHEAD_WITHNULLS(1, nitems);
+ 		nbytes = ndatabytes + dataoffset;
+ 	}
+ 	else
+ 	{
+ 		dataoffset = 0;			/* marker for no null bitmap */
+ 		nbytes = ndatabytes + ARR_OVERHEAD_NONULLS(1);
+ 	}
+ 
+ 	result = (ArrayType *) palloc(nbytes);
+ 	SET_VARSIZE(result, nbytes);
+ 	result->ndim = 1;
+ 	result->dataoffset = dataoffset;
+ 	result->elemtype = ARR_ELEMTYPE(array);
+ 	ARR_DIMS(result)[0] = nitems;
+ 	ARR_LBOUND(result)[0] = 1;
+ 	/* data area is arg1 then arg2 */
+ 	memcpy(ARR_DATA_PTR(result), ARR_DATA_PTR(array), ndatabytes);
+ 	/* handle the null bitmap if needed */
+ 	if (ARR_HASNULL(result))
+ 		array_bitmap_copy(ARR_NULLBITMAP(result), 0,
+ 						  ARR_NULLBITMAP(array), 0, nitems);
+ 
+ 	return result;
+ }
+ 
+ static Datum
+ array_cat_internal(PG_FUNCTION_ARGS, bool flatten)
+ {
  	ArrayType  *v1,
  			   *v2;
  	ArrayType  *result;
*************** array_cat(PG_FUNCTION_ARGS)
*** 203,213 ****
--- 261,275 ----
  		if (PG_ARGISNULL(1))
  			PG_RETURN_NULL();
  		result = PG_GETARG_ARRAYTYPE_P(1);
+ 		if (flatten)
+ 			result = flatten_array(result);
  		PG_RETURN_ARRAYTYPE_P(result);
  	}
  	if (PG_ARGISNULL(1))
  	{
  		result = PG_GETARG_ARRAYTYPE_P(0);
+ 		if (flatten)
+ 			result = flatten_array(result);
  		PG_RETURN_ARRAYTYPE_P(result);
  	}
  
*************** array_cat(PG_FUNCTION_ARGS)
*** 218,231 ****
  	element_type2 = ARR_ELEMTYPE(v2);
  
  	/* Check we have matching element types */
! 	if (element_type1 != element_type2)
! 		ereport(ERROR,
! 				(errcode(ERRCODE_DATATYPE_MISMATCH),
! 				 errmsg("cannot concatenate incompatible arrays"),
! 				 errdetail("Arrays with element types %s and %s are not "
! 						   "compatible for concatenation.",
! 						   format_type_be(element_type1),
! 						   format_type_be(element_type2))));
  
  	/* OK, use it */
  	element_type = element_type1;
--- 280,286 ----
  	element_type2 = ARR_ELEMTYPE(v2);
  
  	/* Check we have matching element types */
! 	check_concatinatable(element_type1, element_type2);
  
  	/* OK, use it */
  	element_type = element_type1;
*************** array_cat(PG_FUNCTION_ARGS)
*** 249,261 ****
  	 * if both are empty, return the first one
  	 */
  	if (ndims1 == 0 && ndims2 > 0)
  		PG_RETURN_ARRAYTYPE_P(v2);
  
  	if (ndims2 == 0)
  		PG_RETURN_ARRAYTYPE_P(v1);
  
  	/* the rest fall under rule 3, 4, or 5 */
! 	if (ndims1 != ndims2 &&
  		ndims1 != ndims2 - 1 &&
  		ndims1 != ndims2 + 1)
  		ereport(ERROR,
--- 304,325 ----
  	 * if both are empty, return the first one
  	 */
  	if (ndims1 == 0 && ndims2 > 0)
+ 	{
+ 		if (flatten)
+ 			v2 = flatten_array(v2);
  		PG_RETURN_ARRAYTYPE_P(v2);
+ 	}
  
  	if (ndims2 == 0)
+ 	{
+ 		if (flatten)
+ 			v1 = flatten_array(v1);
  		PG_RETURN_ARRAYTYPE_P(v1);
+ 	}
  
  	/* the rest fall under rule 3, 4, or 5 */
! 	if (!flatten &&
! 		ndims1 != ndims2 &&
  		ndims1 != ndims2 - 1 &&
  		ndims1 != ndims2 + 1)
  		ereport(ERROR,
*************** array_cat(PG_FUNCTION_ARGS)
*** 279,285 ****
  	ndatabytes1 = ARR_SIZE(v1) - ARR_DATA_OFFSET(v1);
  	ndatabytes2 = ARR_SIZE(v2) - ARR_DATA_OFFSET(v2);
  
! 	if (ndims1 == ndims2)
  	{
  		/*
  		 * resulting array is made up of the elements (possibly arrays
--- 343,358 ----
  	ndatabytes1 = ARR_SIZE(v1) - ARR_DATA_OFFSET(v1);
  	ndatabytes2 = ARR_SIZE(v2) - ARR_DATA_OFFSET(v2);
  
! 	if (flatten)
! 	{
! 		ndims = 1;
! 		dims = (int *) palloc(sizeof(int));
! 		lbs = (int *) palloc(sizeof(int));
! 		lbs = (int *) palloc(1 * sizeof(int));
! 		dims[0] = nitems1 + nitems2;
! 		lbs[0] = 1;
! 	}
! 	else if (ndims1 == ndims2)
  	{
  		/*
  		 * resulting array is made up of the elements (possibly arrays
*************** array_agg_finalfn(PG_FUNCTION_ARGS)
*** 544,546 ****
--- 617,1293 ----
  
  	PG_RETURN_DATUM(result);
  }
+ 
+ /*
+  * array_cardinality :
+  *		returns the number of elements in the array.
+  */
+ Datum
+ array_cardinality(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v = PG_GETARG_ARRAYTYPE_P(0);
+ 	int			nitems;
+ 
+ 	nitems = ArrayGetNItems(ARR_NDIM(v), ARR_DIMS(v));
+ 
+ 	PG_RETURN_INT32(nitems);
+ }
+ 
+ /*
+  * trim_array :
+  *		remove elements at end of the array. Multi-dimensional array is
+  *		flattened into one-dimensional array.
+  */
+ Datum
+ trim_array(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v = PG_GETARG_ARRAYTYPE_P(0);
+ 	int32		ntrimmed = PG_GETARG_INT32(1);
+ 	Oid			elmtype;
+ 	int16		elmlen;
+ 	bool		elmbyval;
+ 	char		elmalign;
+ 	Datum	   *elems;
+ 	bool	   *nulls;
+ 	ArrayType  *result;
+ 	int			nitems;
+ 
+ 	if (ntrimmed < 0)
+ 		ereport(ERROR,
+ 				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ 				 errmsg("number of trimmed elements must not be negative")));
+ 
+ 	elmtype = ARR_ELEMTYPE(v);
+ 	get_typlenbyvalalign(elmtype, &elmlen, &elmbyval, &elmalign);
+ 	deconstruct_array(v, elmtype, elmlen, elmbyval, elmalign,
+ 					  &elems, &nulls, &nitems);
+ 
+ 	if (nitems <= ntrimmed)
+ 		result = construct_empty_array(elmtype);
+ 	else
+ 	{
+ 		int		dims = nitems - ntrimmed;
+ 		int		lbs = 1;
+ 
+ 		result = construct_md_array(elems, nulls, 1, &dims, &lbs,
+ 									elmtype, elmlen, elmbyval, elmalign);
+ 	}
+ 
+ 	PG_RETURN_ARRAYTYPE_P(result);
+ }
+ 
+ Datum
+ array_element(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v = PG_GETARG_ARRAYTYPE_P(0);
+ 	Oid			elmtype;
+ 	int16		elmlen;
+ 	bool		elmbyval;
+ 	char		elmalign;
+ 	Datum	   *elems;
+ 	bool	   *nulls;
+ 	int			nitems;
+ 
+ 	elmtype = ARR_ELEMTYPE(v);
+ 	get_typlenbyvalalign(elmtype, &elmlen, &elmbyval, &elmalign);
+ 	deconstruct_array(v, elmtype, elmlen, elmbyval, elmalign,
+ 					  &elems, &nulls, &nitems);
+ 	if (nitems > 1)
+ 		elog(ERROR, "array has %d elements", nitems);
+ 	if (nitems < 1 || nulls[0])
+ 		PG_RETURN_NULL();
+ 	PG_RETURN_DATUM(elems[0]);
+ }
+ 
+ /*
+  * Find TypeCacheEntry with comparison functions for element_type.
+  * We arrange to look up the compare functions only once per series of
+  * calls, assuming the element type doesn't change underneath us.
+  */
+ static TypeCacheEntry *
+ get_type_cache(FunctionCallInfo fcinfo, Oid element_type)
+ {
+ 	TypeCacheEntry *type;
+ 
+ 	type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 	if (type == NULL ||
+ 		type->type_id != element_type)
+ 	{
+ 		type = lookup_type_cache(element_type,
+ 					TYPECACHE_EQ_OPR_FINFO | TYPECACHE_CMP_PROC_FINFO);
+ 		if (!OidIsValid(type->eq_opr_finfo.fn_oid) ||
+ 			!OidIsValid(type->cmp_proc_finfo.fn_oid))
+ 			ereport(ERROR,
+ 					(errcode(ERRCODE_UNDEFINED_FUNCTION),
+ 			   errmsg("could not identify comparison functions for type %s",
+ 					  format_type_be(element_type))));
+ 		fcinfo->flinfo->fn_extra = type;
+ 	}
+ 
+ 	return type;
+ }
+ 
+ static int
+ compare_element(const void *a, const void *b, void *arg)
+ {
+ 	FunctionCallInfo fn = (FunctionCallInfo) arg;
+ 
+ 	fn->arg[0] = *(const Datum *) a;
+ 	fn->arg[1] = *(const Datum *) b;
+ 	fn->argnull[0] = false;
+ 	fn->argnull[1] = false;
+ 	fn->isnull = false;
+ 	return DatumGetInt32(FunctionCallInvoke(fn));
+ }
+ 
+ /*
+  * Sort values and move nulls to the end.
+  * Returns number of non-null elements.
+  */
+ static int
+ sort_elements(TypeCacheEntry *type, Datum *values, bool *nulls, int nitems)
+ {
+ 	int			nonnulls,
+ 				i;
+ 	FunctionCallInfoData fn;
+ 
+ 	/* move nulls to end of the array */
+ 	for (i = nonnulls = 0; i < nitems; i++)
+ 	{
+ 		if (!nulls[i])
+ 		{
+ 			values[nonnulls] = values[i];
+ 			nulls[nonnulls] = false;
+ 			nonnulls++;
+ 		}
+ 	}
+ 	for (i = nonnulls; i < nitems; i++)
+ 		nulls[i] = true;
+ 
+ 	/* sort non-null values */
+ 	InitFunctionCallInfoData(fn, &type->cmp_proc_finfo, 2, NULL, NULL);
+ 	qsort_arg(values, nonnulls, sizeof(Datum), compare_element, &fn);
+ 
+ 	return nonnulls;
+ }
+ 
+ /*
+  * Remove duplicated values in already sorted elements.
+  * Returns the number of distinct elements.
+  */
+ static int
+ unique_elements(TypeCacheEntry *type, Datum *values, bool *nulls,
+ 				int nitems, int nonnulls)
+ {
+ 	int		i,
+ 			n;
+ 	FunctionCallInfoData fn;
+ 
+ 	InitFunctionCallInfoData(fn, &type->eq_opr_finfo, 2, NULL, NULL);
+ 
+ 	for (i = n = 1; i < nonnulls; i++)
+ 	{
+ 		fn.arg[0] = values[i - 1];
+ 		fn.arg[1] = values[i];
+ 		fn.argnull[0] = false;
+ 		fn.argnull[1] = false;
+ 		fn.isnull = false;
+ 		if (!DatumGetBool(FunctionCallInvoke(&fn)))
+ 			values[n++] = values[i];
+ 	}
+ 	if (nonnulls < nitems)
+ 		nulls[n++] = true;
+ 
+ 	return n;
+ }
+ 
+ static void
+ deconstruct_and_sort(FunctionCallInfo fcinfo, ArrayType *array, bool unique,
+ 					 Datum **sorted_values, bool **sorted_nulls, int *nitems)
+ {
+ 	Oid			element_type = ARR_ELEMTYPE(array);
+ 	Datum	   *values;
+ 	bool	   *nulls;
+ 	int			len,
+ 				nonnulls;
+ 	TypeCacheEntry *type;
+ 
+ 	type = get_type_cache(fcinfo, element_type);
+ 	deconstruct_array(array,
+ 					  element_type,
+ 					  type->typlen,
+ 					  type->typbyval,
+ 					  type->typalign,
+ 					  &values, &nulls, &len);
+ 
+ 	nonnulls = sort_elements(type, values, nulls, len);
+ 	if (unique)
+ 		len = unique_elements(type, values, nulls, len, nonnulls);
+ 
+ 	*sorted_values = values;
+ 	*sorted_nulls = nulls;
+ 	*nitems = len;
+ }
+ 
+ static ArrayType *
+ array_to_set(FunctionCallInfo fcinfo, ArrayType *array)
+ {
+ 	Datum	   *values;
+ 	bool	   *nulls;
+ 	int			nitems;
+ 	int			lbs = 1;
+ 	Oid			element_type = ARR_ELEMTYPE(array);
+ 	TypeCacheEntry *type;
+ 
+ 	deconstruct_and_sort(fcinfo, array, true, &values, &nulls, &nitems);
+ 	type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 
+ 	return construct_md_array(values, nulls, 1, &nitems, &lbs, element_type,
+ 				type->typlen, type->typbyval, type->typalign);
+ }
+ 
+ Datum
+ multiset_is_a_set(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
+ 	bool		result = true;
+ 	Datum	   *values;
+ 	bool	   *nulls;
+ 	int			nitems;
+ 	int			i;
+ 	TypeCacheEntry *type;
+ 	FunctionCallInfoData fn;
+ 
+ 	deconstruct_and_sort(fcinfo, array, false, &values, &nulls, &nitems);
+ 	type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 	InitFunctionCallInfoData(fn, &type->eq_opr_finfo, 2, NULL, NULL);
+ 
+ 	/* compare for each adjacent */
+ 	for (i = 1; i < nitems; i++)
+ 	{
+ 		/* some nulls at end of the array are allowed */
+ 		if (nulls[i])
+ 			break;
+ 
+ 		fn.arg[0] = values[i - 1];
+ 		fn.arg[1] = values[i];
+ 		fn.argnull[0] = false;
+ 		fn.argnull[1] = false;
+ 		fn.isnull = false;
+ 		if (DatumGetBool(FunctionCallInvoke(&fn)))
+ 		{
+ 			result = false;
+ 			break;
+ 		}
+ 	}
+ 
+ 	/* Avoid leaking memory when handed toasted input. */
+ 	PG_FREE_IF_COPY(array, 0);
+ 
+ 	PG_RETURN_BOOL(result);
+ }
+ 
+ Datum
+ multiset_union(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v1,
+ 			   *v2;
+ 	bool		all = PG_GETARG_BOOL(2);
+ 	ArrayType  *result;
+ 	Datum	   *values,
+ 			   *values1,
+ 			   *values2;
+ 	bool	   *nulls,
+ 			   *nulls1,
+ 			   *nulls2;
+ 	int			nitems,
+ 				nitems1,
+ 				nitems2,
+ 				nonnulls;
+ 	Oid			element_type1,
+ 				element_type2;
+ 	int			lbs = 1;
+ 	TypeCacheEntry *type;
+ 
+ 	if (PG_ARGISNULL(0) && PG_ARGISNULL(1))
+ 		PG_RETURN_NULL();
+ 
+ 	/* fast path for UNION ALL */
+ 	if (all)
+ 		return array_cat_internal(fcinfo, true);
+ 
+ 	/* Concatenating a null array is a no-op, just return the other input */
+ 	if (PG_ARGISNULL(0))
+ 	{
+ 		v2 = PG_GETARG_ARRAYTYPE_P(1);
+ 		result = array_to_set(fcinfo, v2);
+ 		PG_FREE_IF_COPY(v2, 1);
+ 		PG_RETURN_ARRAYTYPE_P(result);
+ 	}
+ 	if (PG_ARGISNULL(1))
+ 	{
+ 		v1 = PG_GETARG_ARRAYTYPE_P(0);
+ 		result = array_to_set(fcinfo, v1);
+ 		PG_FREE_IF_COPY(v1, 0);
+ 		PG_RETURN_ARRAYTYPE_P(result);
+ 	}
+ 
+ 	v1 = PG_GETARG_ARRAYTYPE_P(0);
+ 	v2 = PG_GETARG_ARRAYTYPE_P(1);
+ 	element_type1 = ARR_ELEMTYPE(v1);
+ 	element_type2 = ARR_ELEMTYPE(v2);
+ 
+ 	check_concatinatable(element_type1, element_type2);
+ 	type = get_type_cache(fcinfo, element_type1);
+ 	deconstruct_array(v1,
+ 					  element_type1,
+ 					  type->typlen,
+ 					  type->typbyval,
+ 					  type->typalign,
+ 					  &values1, &nulls1, &nitems1);
+ 	deconstruct_array(v2,
+ 					  element_type2,
+ 					  type->typlen,
+ 					  type->typbyval,
+ 					  type->typalign,
+ 					  &values2, &nulls2, &nitems2);
+ 
+ 	nitems = nitems1 + nitems2;
+ 	values = (Datum *) palloc(sizeof(Datum) * nitems);
+ 	nulls = (bool *) palloc(sizeof(bool) * nitems);
+ 
+ 	memcpy(values, values1, sizeof(Datum) * nitems1);
+ 	memcpy(values + nitems1, values2, sizeof(Datum) * nitems2);
+ 	memcpy(nulls, nulls1, sizeof(bool) * nitems1);
+ 	memcpy(nulls + nitems1, nulls2, sizeof(bool) * nitems2);
+ 
+ 	nonnulls = sort_elements(type, values, nulls, nitems);
+ 	nitems = unique_elements(type, values, nulls, nitems, nonnulls);
+ 	result = construct_md_array(values, nulls, 1, &nitems, &lbs,
+ 								element_type1,
+ 								type->typlen,
+ 								type->typbyval,
+ 								type->typalign);
+ 
+ 	/* Avoid leaking memory when handed toasted input. */
+ 	PG_FREE_IF_COPY(v1, 0);
+ 	PG_FREE_IF_COPY(v2, 1);
+ 
+ 	PG_RETURN_ARRAYTYPE_P(result);
+ }
+ 
+ static int
+ intersect_internal(TypeCacheEntry *type,
+ 				   Datum *values1, bool *nulls1, int nitems1,
+ 				   Datum *values2, bool *nulls2, int nitems2)
+ {
+ 	int			n1,
+ 				n2,
+ 				n;
+ 	FunctionCallInfoData fn;
+ 
+ 	InitFunctionCallInfoData(fn, &type->cmp_proc_finfo, 2, NULL, NULL);
+ 
+ 	/* add non-nulls */
+ 	for (n = n1 = n2 = 0;
+ 		 n1 < nitems1 && !nulls1[n1] &&
+ 		 n2 < nitems2 && !nulls2[n2];)
+ 	{
+ 		int		r;
+ 
+ 		fn.arg[0] = values1[n1];
+ 		fn.arg[1] = values2[n2];
+ 		fn.argnull[0] = false;
+ 		fn.argnull[1] = false;
+ 		fn.isnull = false;
+ 		r = DatumGetInt32(FunctionCallInvoke(&fn));
+ 
+ 		if (r == 0)
+ 			values1[n++] = values1[n1];
+ 		if (r <= 0)
+ 			n1++;
+ 		if (r >= 0)
+ 			n2++;
+ 	}
+ 
+ 	/* skip non-nulls */
+ 	for (; n1 < nitems1 && !nulls1[n1]; n1++) {}
+ 	for (; n2 < nitems2 && !nulls2[n2]; n2++) {}
+ 
+ 	/* add nulls */
+ 	for (; n1 < nitems1 && n2 < nitems2; n1++, n2++, n++)
+ 		nulls1[n] = true;
+ 
+ 	return n;
+ }
+ 
+ Datum
+ multiset_intersect(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v1 = PG_GETARG_ARRAYTYPE_P(0);
+ 	ArrayType  *v2 = PG_GETARG_ARRAYTYPE_P(1);
+ 	bool		all = PG_GETARG_BOOL(2);
+ 
+ 	ArrayType  *result;
+ 	Oid			element_type = ARR_ELEMTYPE(v1);
+ 	Datum	   *values1,
+ 			   *values2;
+ 	bool	   *nulls1,
+ 			   *nulls2;
+ 	int			nitems1,
+ 				nitems2;
+ 	int			lbs = 1;
+ 	TypeCacheEntry *type;
+ 
+ 	check_comparable(element_type, ARR_ELEMTYPE(v2));
+ 	deconstruct_and_sort(fcinfo, v1, !all, &values1, &nulls1, &nitems1);
+ 	deconstruct_and_sort(fcinfo, v2, !all, &values2, &nulls2, &nitems2);
+ 	type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 
+ 	nitems1 = intersect_internal(type,
+ 								 values1, nulls1, nitems1,
+ 								 values2, nulls2, nitems2);
+ 	result = construct_md_array(values1, nulls1, 1, &nitems1, &lbs,
+ 								element_type, type->typlen,
+ 								type->typbyval, type->typalign);
+ 
+ 	/* Avoid leaking memory when handed toasted input. */
+ 	PG_FREE_IF_COPY(v1, 0);
+ 	PG_FREE_IF_COPY(v2, 1);
+ 
+ 	PG_RETURN_ARRAYTYPE_P(result);
+ }
+ 
+ Datum
+ multiset_except(PG_FUNCTION_ARGS)
+ {
+ 	ArrayType  *v1;
+ 	ArrayType  *v2;
+ 	bool		all;
+ 	ArrayType  *result;
+ 	Oid			element_type;
+ 	Datum	   *values1,
+ 			   *values2;
+ 	bool	   *nulls1,
+ 			   *nulls2;
+ 	int			nitems1,
+ 				nitems2;
+ 	int			n1,
+ 				n2,
+ 				n;
+ 	int			lbs = 1;
+ 	TypeCacheEntry *type;
+ 	FunctionCallInfoData fn;
+ 
+ 	if (PG_ARGISNULL(0))
+ 		PG_RETURN_NULL();
+ 
+ 	v1 = PG_GETARG_ARRAYTYPE_P(0);
+ 	all = PG_GETARG_BOOL(2);
+ 	element_type = ARR_ELEMTYPE(v1);
+ 
+ 	/* fast path for except null */
+ 	if (PG_ARGISNULL(1))
+ 	{
+ 		if (all)
+ 			PG_RETURN_ARRAYTYPE_P(flatten_array(v1));
+ 
+ 		deconstruct_and_sort(fcinfo, v1, false, &values1, &nulls1, &nitems1);
+ 		type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 
+ 		result = construct_md_array(values1, nulls1, 1, &nitems1, &lbs,
+ 									element_type, type->typlen,
+ 									type->typbyval, type->typalign);
+ 
+ 		/* Avoid leaking memory when handed toasted input. */
+ 		PG_FREE_IF_COPY(v1, 0);
+ 
+ 		PG_RETURN_ARRAYTYPE_P(result);
+ 	}
+ 
+ 	v2 = PG_GETARG_ARRAYTYPE_P(1);
+ 
+ 	check_concatinatable(element_type, ARR_ELEMTYPE(v2));
+ 	deconstruct_and_sort(fcinfo, v1, !all, &values1, &nulls1, &nitems1);
+ 	deconstruct_and_sort(fcinfo, v2, !all, &values2, &nulls2, &nitems2);
+ 	type = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 	InitFunctionCallInfoData(fn, &type->cmp_proc_finfo, 2, NULL, NULL);
+ 
+ 	/* add non-nulls */
+ 	for (n = n1 = n2 = 0;
+ 		 n1 < nitems1 && !nulls1[n1] &&
+ 		 n2 < nitems2 && !nulls2[n2];)
+ 	{
+ 		int		r;
+ 
+ 		fn.arg[0] = values1[n1];
+ 		fn.arg[1] = values2[n2];
+ 		fn.argnull[0] = false;
+ 		fn.argnull[1] = false;
+ 		fn.isnull = false;
+ 		r = DatumGetInt32(FunctionCallInvoke(&fn));
+ 
+ 		if (r < 0)
+ 			values1[n++] = values1[n1++];
+ 		else if (r == 0)
+ 			n1++;
+ 		else
+ 			n2++;
+ 	}
+ 	for (; n1 < nitems1 && !nulls1[n1]; n1++, n++)
+ 		values1[n] = values1[n1];
+ 
+ 	/* add nulls */
+ 	if (n1 < nitems1 && nulls1[n1])
+ 	{
+ 		for (; n2 < nitems2 && !nulls2[n2]; n2++) {}
+ 		for (; n1 < nitems1 - (nitems2 - n2); n1++, n++)
+ 			nulls1[n] = true;
+ 	}
+ 
+ 	result = construct_md_array(values1, nulls1, 1, &n, &lbs, element_type,
+ 								type->typlen, type->typbyval, type->typalign);
+ 
+ 	/* Avoid leaking memory when handed toasted input. */
+ 	PG_FREE_IF_COPY(v1, 0);
+ 	PG_FREE_IF_COPY(v2, 1);
+ 
+ 	PG_RETURN_ARRAYTYPE_P(result);
+ }
+ 
+ Datum
+ fusion_transfn(PG_FUNCTION_ARGS)
+ {
+ 	MemoryContext		aggcontext;
+ 	ArrayBuildState	   *state;
+ 
+ 	if (!AggCheckCallContext(fcinfo, &aggcontext))
+ 	{
+ 		/* cannot be called directly because of internal-type argument */
+ 		elog(ERROR, "fusion_transfn called in non-aggregate context");
+ 	}
+ 
+ 	state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
+ 	if (!PG_ARGISNULL(1))
+ 	{
+ 		ArrayType  *v = PG_GETARG_ARRAYTYPE_P(1);
+ 		Oid			elmtype;
+ 		int16		elmlen;
+ 		bool		elmbyval;
+ 		char		elmalign;
+ 		Datum	   *elems;
+ 		bool	   *nulls;
+ 		int			nitems;
+ 		int			i;
+ 
+ 		elmtype = ARR_ELEMTYPE(v);
+ 		get_typlenbyvalalign(elmtype, &elmlen, &elmbyval, &elmalign);
+ 		deconstruct_array(v, elmtype, elmlen, elmbyval, elmalign,
+ 						  &elems, &nulls, &nitems);
+ 		for (i = 0; i < nitems; i++)
+ 			state = accumArrayResult(state, elems[i], nulls[i],
+ 									 elmtype, aggcontext);
+ 	}
+ 
+ 	PG_RETURN_POINTER(state);
+ }
+ 
+ typedef struct IntersectionState
+ {
+ 	Oid		element_type;
+ 	int		nitems;
+ 	Datum  *values;
+ 	bool   *nulls;
+ } IntersectionState;
+ 
+ Datum
+ intersection_transfn(PG_FUNCTION_ARGS)
+ {
+ 	MemoryContext		aggcontext;
+ 	IntersectionState  *state;
+ 
+ 	if (!AggCheckCallContext(fcinfo, &aggcontext))
+ 	{
+ 		/* cannot be called directly because of internal-type argument */
+ 		elog(ERROR, "intersection_transfn called in non-aggregate context");
+ 	}
+ 
+ 	state = PG_ARGISNULL(0) ? NULL : (IntersectionState *) PG_GETARG_POINTER(0);
+ 	if (!PG_ARGISNULL(1))
+ 	{
+ 		ArrayType  *v = PG_GETARG_ARRAYTYPE_P(1);
+ 
+ 		if (state == NULL)
+ 		{
+ 			MemoryContext	oldcontext;
+ 
+ 			oldcontext = MemoryContextSwitchTo(aggcontext);
+ 			state = (IntersectionState *) palloc(sizeof(IntersectionState));
+ 			state->element_type = ARR_ELEMTYPE(v);
+ 			deconstruct_and_sort(fcinfo, v, false,
+ 				&state->values, &state->nulls, &state->nitems);
+ 			MemoryContextSwitchTo(oldcontext);
+ 		}
+ 		else
+ 		{
+ 			Datum	   *values;
+ 			bool	   *nulls;
+ 			int			nitems;
+ 
+ 			check_concatinatable(state->element_type, ARR_ELEMTYPE(v));
+ 			deconstruct_and_sort(fcinfo, v, false, &values, &nulls, &nitems);
+ 			state->nitems = intersect_internal(
+ 				(TypeCacheEntry *) fcinfo->flinfo->fn_extra,
+ 				state->values, state->nulls, state->nitems,
+ 				values, nulls, nitems);
+ 		}
+ 	}
+ 
+ 	PG_RETURN_POINTER(state);
+ }
+ 
+ Datum
+ intersection_finalfn(PG_FUNCTION_ARGS)
+ {
+ 	IntersectionState  *state;
+ 	ArrayType		   *result;
+ 	int					lbs = 1;
+ 	TypeCacheEntry	   *type;
+ 
+ 	state = PG_ARGISNULL(0) ? NULL : (IntersectionState *) PG_GETARG_POINTER(0);
+ 	if (state == NULL)
+ 		PG_RETURN_NULL();
+ 
+ 	type = get_type_cache(fcinfo, state->element_type);
+ 	result = construct_md_array(state->values, state->nulls,
+ 								1, &state->nitems, &lbs, state->element_type,
+ 								type->typlen, type->typbyval, type->typalign);
+ 
+ 	PG_RETURN_ARRAYTYPE_P(result);
+ }
+ 
+ static void
+ check_concatinatable(Oid element_type1, Oid element_type2)
+ {
+ 	if (element_type1 != element_type2)
+ 		ereport(ERROR,
+ 				(errcode(ERRCODE_DATATYPE_MISMATCH),
+ 				 errmsg("cannot concatenate incompatible arrays"),
+ 				 errdetail("Arrays with element types %s and %s are not "
+ 						   "compatible for concatenation.",
+ 						   format_type_be(element_type1),
+ 						   format_type_be(element_type2))));
+ }
+ 
+ static void
+ check_comparable(Oid element_type1, Oid element_type2)
+ {
+ 	if (element_type1 != element_type2)
+ 		ereport(ERROR,
+ 				(errcode(ERRCODE_DATATYPE_MISMATCH),
+ 				 errmsg("cannot compare incompatible arrays"),
+ 				 errdetail("Arrays with element types %s and %s are not "
+ 						   "compatible for comparison.",
+ 						   format_type_be(element_type1),
+ 						   format_type_be(element_type2))));
+ }
diff --git a/src/include/catalog/pg_aggregate.h b/src/include/catalog/pg_aggregate.h
index 5ac3492..003dd52 100644
*** a/src/include/catalog/pg_aggregate.h
--- b/src/include/catalog/pg_aggregate.h
*************** DATA(insert ( 2901 xmlconcat2	  -					0	
*** 222,227 ****
--- 222,230 ----
  
  /* array */
  DATA(insert ( 2335	array_agg_transfn	array_agg_finalfn		0	2281	_null_ ));
+ DATA(insert ( 3070	array_agg_transfn	array_agg_finalfn		0	2281	_null_ ));
+ DATA(insert ( 3072	fusion_transfn		array_agg_finalfn		0	2281	_null_ ));
+ DATA(insert ( 3075	intersection_transfn intersection_finalfn	0	2281	_null_ ));
  
  /* text */
  DATA(insert ( 3538	string_agg_transfn	string_agg_finalfn		0	2281	_null_ ));
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 4f444ae..c0cf41b 100644
*** a/src/include/catalog/pg_proc.h
--- b/src/include/catalog/pg_proc.h
*************** DATA(insert OID = 2334 (  array_agg_fina
*** 1058,1063 ****
--- 1058,1089 ----
  DESCR("array_agg 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 = 3063 (  cardinality	   PGNSP PGUID 12 1 0 0 f f f t f i 1 0 23 "2277" _null_ _null_ _null_ _null_ array_cardinality _null_ _null_ _null_ ));
+ DESCR("number of elements in array");
+ DATA(insert OID = 3064 (  trim_array	   PGNSP PGUID 12 1 0 0 f f f t f i 2 0 2277 "2277 23" _null_ _null_ _null_ _null_ trim_array _null_ _null_ _null_ ));
+ DESCR("remove elements end of array");
+ DATA(insert OID = 3065 (  element		   PGNSP PGUID 12 1 0 0 f f f t f i 1 0 2283 "2277" _null_ _null_ _null_ _null_ array_element _null_ _null_ _null_ ));
+ DESCR("element of array");
+ DATA(insert OID = 3066 (  multiset_is_a_set PGNSP PGUID 12 1 0 0 f f f t f i 1 0 16 "2277" _null_ _null_ _null_ _null_ multiset_is_a_set _null_ _null_ _null_ ));
+ DESCR("no duplicated elements?");
+ DATA(insert OID = 3067 (  multiset_union PGNSP PGUID 12 1 0 0 f f f f f i 3 0 2277 "2277 2277 16" _null_ _null_ _null_ _null_ multiset_union _null_ _null_ _null_ ));
+ DESCR("concatenate two arrays");
+ DATA(insert OID = 3068 (  multiset_intersect PGNSP PGUID 12 1 0 0 f f f t f i 3 0 2277 "2277 2277 16" _null_ _null_ _null_ _null_ multiset_intersect _null_ _null_ _null_ ));
+ DESCR("intersection of two arrays");
+ DATA(insert OID = 3069 (  multiset_except PGNSP PGUID 12 1 0 0 f f f f f i 3 0 2277 "2277 2277 16" _null_ _null_ _null_ _null_ multiset_except _null_ _null_ _null_ ));
+ DESCR("exception of two arrays");
+ DATA(insert OID = 3070 (  collect		   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 = 3071 (  fusion_transfn   PGNSP PGUID 12 1 0 0 f f f f f i 2 0 2281 "2281 2277" _null_ _null_ _null_ _null_ fusion_transfn _null_ _null_ _null_ ));
+ DESCR("fusion transition function");
+ DATA(insert OID = 3072 (  fusion		   PGNSP PGUID 12 1 0 0 t f f f f i 1 0 2277 "2277" _null_ _null_ _null_ _null_ aggregate_dummy _null_ _null_ _null_ ));
+ DESCR("concatenate aggregate input into an array");
+ DATA(insert OID = 3073 (  intersection_transfn PGNSP PGUID 12 1 0 0 f f f f f i 2 0 2281 "2281 2277" _null_ _null_ _null_ _null_ intersection_transfn _null_ _null_ _null_ ));
+ DESCR("intersection transition function");
+ DATA(insert OID = 3074 (  intersection_finalfn PGNSP PGUID 12 1 0 0 f f f f f i 1 0 2277 "2281" _null_ _null_ _null_ _null_ intersection_finalfn _null_ _null_ _null_ ));
+ DESCR("intersection final function");
+ DATA(insert OID = 3075 (  intersection	   PGNSP PGUID 12 1 0 0 t f f f f i 1 0 2277 "2277" _null_ _null_ _null_ _null_ aggregate_dummy _null_ _null_ _null_ ));
+ DESCR("intersection of all inputs");
  
  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");
diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h
index 2c44cf7..bcfdedd 100644
*** a/src/include/parser/kwlist.h
--- b/src/include/parser/kwlist.h
***************
*** 26,31 ****
--- 26,32 ----
   */
  
  /* name, value, category */
+ PG_KEYWORD("a", A, UNRESERVED_KEYWORD)
  PG_KEYWORD("abort", ABORT_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("absolute", ABSOLUTE_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("access", ACCESS, UNRESERVED_KEYWORD)
*************** PG_KEYWORD("login", LOGIN_P, UNRESERVED_
*** 232,242 ****
--- 233,245 ----
  PG_KEYWORD("mapping", MAPPING, UNRESERVED_KEYWORD)
  PG_KEYWORD("match", MATCH, UNRESERVED_KEYWORD)
  PG_KEYWORD("maxvalue", MAXVALUE, UNRESERVED_KEYWORD)
+ PG_KEYWORD("member", MEMBER, UNRESERVED_KEYWORD)
  PG_KEYWORD("minute", MINUTE_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("minvalue", MINVALUE, UNRESERVED_KEYWORD)
  PG_KEYWORD("mode", MODE, UNRESERVED_KEYWORD)
  PG_KEYWORD("month", MONTH_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("move", MOVE, UNRESERVED_KEYWORD)
+ PG_KEYWORD("multiset", MULTISET, UNRESERVED_KEYWORD)
  PG_KEYWORD("name", NAME_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("names", NAMES, UNRESERVED_KEYWORD)
  PG_KEYWORD("national", NATIONAL, COL_NAME_KEYWORD)
*************** PG_KEYWORD("stdout", STDOUT, UNRESERVED_
*** 356,361 ****
--- 359,365 ----
  PG_KEYWORD("storage", STORAGE, UNRESERVED_KEYWORD)
  PG_KEYWORD("strict", STRICT_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("strip", STRIP_P, UNRESERVED_KEYWORD)
+ PG_KEYWORD("sub", SUB, UNRESERVED_KEYWORD)
  PG_KEYWORD("substring", SUBSTRING, COL_NAME_KEYWORD)
  PG_KEYWORD("superuser", SUPERUSER_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("symmetric", SYMMETRIC, RESERVED_KEYWORD)
diff --git a/src/include/utils/array.h b/src/include/utils/array.h
index dba9c3d..daff9cc 100644
*** a/src/include/utils/array.h
--- b/src/include/utils/array.h
*************** extern ArrayType *create_singleton_array
*** 280,284 ****
--- 280,294 ----
  
  extern Datum array_agg_transfn(PG_FUNCTION_ARGS);
  extern Datum array_agg_finalfn(PG_FUNCTION_ARGS);
+ extern Datum array_cardinality(PG_FUNCTION_ARGS);
+ extern Datum trim_array(PG_FUNCTION_ARGS);
+ extern Datum array_element(PG_FUNCTION_ARGS);
+ extern Datum multiset_is_a_set(PG_FUNCTION_ARGS);
+ extern Datum multiset_union(PG_FUNCTION_ARGS);
+ extern Datum multiset_intersect(PG_FUNCTION_ARGS);
+ extern Datum multiset_except(PG_FUNCTION_ARGS);
+ extern Datum fusion_transfn(PG_FUNCTION_ARGS);
+ extern Datum intersection_transfn(PG_FUNCTION_ARGS);
+ extern Datum intersection_finalfn(PG_FUNCTION_ARGS);
  
  #endif   /* ARRAY_H */
diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out
index eff5f88..31965ee 100644
*** a/src/test/regress/expected/arrays.out
--- b/src/test/regress/expected/arrays.out
*************** select * from t1;
*** 1286,1288 ****
--- 1286,1398 ----
   [5:5]={"(42,43)"}
  (1 row)
  
+ -- MULTISET support
+ SELECT cardinality(ARRAY[1, 2, 3]);
+  cardinality 
+ -------------
+            3
+ (1 row)
+ 
+ SELECT trim_array(ARRAY[1, 2, 3], 2);
+  trim_array 
+ ------------
+  {1}
+ (1 row)
+ 
+ SELECT element(NULL::integer[]);
+  element 
+ ---------
+         
+ (1 row)
+ 
+ SELECT element(ARRAY[1]);
+  element 
+ ---------
+        1
+ (1 row)
+ 
+ SELECT element(ARRAY[1, 2]);
+ ERROR:  array has 2 elements
+ SELECT 'B' MEMBER OF ARRAY['A', 'B', 'C'];
+  ?column? 
+ ----------
+  t
+ (1 row)
+ 
+ SELECT 3 MEMBER OF ARRAY[1, 2];
+  ?column? 
+ ----------
+  f
+ (1 row)
+ 
+ SELECT ARRAY[1, 2] SUB MULTISET OF ARRAY[3, 2, 1];
+  ?column? 
+ ----------
+  t
+ (1 row)
+ 
+ SELECT ARRAY['A', 'B', 'C'] SUB MULTISET OF ARRAY['A', 'B', 'D'];
+  ?column? 
+ ----------
+  f
+ (1 row)
+ 
+ SELECT ARRAY[1, 2, 3] IS A SET;
+  multiset_is_a_set 
+ -------------------
+  t
+ (1 row)
+ 
+ SELECT ARRAY['A', 'A', 'B'] IS A SET;
+  multiset_is_a_set 
+ -------------------
+  f
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET UNION ALL ARRAY[2, NULL];
+       multiset_union      
+ --------------------------
+  {2,NULL,1,2,NULL,2,NULL}
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET UNION ARRAY[2, NULL];
+  multiset_union 
+ ----------------
+  {1,2,NULL}
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET INTERSECT ALL ARRAY[2, NULL];
+  multiset_intersect 
+ --------------------
+  {2,NULL}
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET INTERSECT ARRAY[2, NULL];
+  multiset_intersect 
+ --------------------
+  {2,NULL}
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET EXCEPT ALL ARRAY[2, NULL];
+  multiset_except 
+ -----------------
+  {1,NULL}
+ (1 row)
+ 
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET EXCEPT ARRAY[2, NULL];
+  multiset_except 
+ -----------------
+  {1}
+ (1 row)
+ 
+ SELECT collect(s), fusion(a), intersection(a)
+   FROM (VALUES
+   ('A', ARRAY[1, 2, 3, 2, 2]),
+   ('B', ARRAY[1, 2, 4, 2]),
+   ('C', ARRAY[3, 2, 2, 1])
+ ) AS t(s, a);
+  collect |           fusion            | intersection 
+ ---------+-----------------------------+--------------
+  {A,B,C} | {1,2,3,2,2,1,2,4,2,3,2,2,1} | {1,2,2}
+ (1 row)
+ 
diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql
index a75b8c4..c477c4c 100644
*** a/src/test/regress/sql/arrays.sql
--- b/src/test/regress/sql/arrays.sql
*************** insert into t1 (f1[5].q1) values(42);
*** 426,428 ****
--- 426,454 ----
  select * from t1;
  update t1 set f1[5].q2 = 43;
  select * from t1;
+ 
+ -- MULTISET support
+ 
+ SELECT cardinality(ARRAY[1, 2, 3]);
+ SELECT trim_array(ARRAY[1, 2, 3], 2);
+ SELECT element(NULL::integer[]);
+ SELECT element(ARRAY[1]);
+ SELECT element(ARRAY[1, 2]);
+ SELECT 'B' MEMBER OF ARRAY['A', 'B', 'C'];
+ SELECT 3 MEMBER OF ARRAY[1, 2];
+ SELECT ARRAY[1, 2] SUB MULTISET OF ARRAY[3, 2, 1];
+ SELECT ARRAY['A', 'B', 'C'] SUB MULTISET OF ARRAY['A', 'B', 'D'];
+ SELECT ARRAY[1, 2, 3] IS A SET;
+ SELECT ARRAY['A', 'A', 'B'] IS A SET;
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET UNION ALL ARRAY[2, NULL];
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET UNION ARRAY[2, NULL];
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET INTERSECT ALL ARRAY[2, NULL];
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET INTERSECT ARRAY[2, NULL];
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET EXCEPT ALL ARRAY[2, NULL];
+ SELECT ARRAY[2, NULL, 1, 2, NULL] MULTISET EXCEPT ARRAY[2, NULL];
+ SELECT collect(s), fusion(a), intersection(a)
+   FROM (VALUES
+   ('A', ARRAY[1, 2, 3, 2, 2]),
+   ('B', ARRAY[1, 2, 4, 2]),
+   ('C', ARRAY[3, 2, 2, 1])
+ ) AS t(s, a);