diff --git a/contrib/pg_upgrade/function.c b/contrib/pg_upgrade/function.c
index 31255d637dc8a6fd2642650bccfec972401f188f..c76aaeb090bde61c4308807033164946f2aa22cc 100644
*** a/contrib/pg_upgrade/function.c
--- b/contrib/pg_upgrade/function.c
*************** install_support_functions(void)
*** 79,85 ****
  								  "LANGUAGE C STRICT;"));
  		PQclear(executeQueryOrDie(conn,
  								  "CREATE OR REPLACE FUNCTION "
! 			 "		binary_upgrade.add_pg_enum_label(OID, OID, NAME) "
  								  "RETURNS VOID "
  								  "AS '$libdir/pg_upgrade_support' "
  								  "LANGUAGE C STRICT;"));
--- 79,85 ----
  								  "LANGUAGE C STRICT;"));
  		PQclear(executeQueryOrDie(conn,
  								  "CREATE OR REPLACE FUNCTION "
! 			 "		binary_upgrade.set_next_pg_enum_oid(OID) "
  								  "RETURNS VOID "
  								  "AS '$libdir/pg_upgrade_support' "
  								  "LANGUAGE C STRICT;"));
diff --git a/contrib/pg_upgrade_support/pg_upgrade_support.c b/contrib/pg_upgrade_support/pg_upgrade_support.c
index c956be187ac398495944d3f0b8c07ec18a970040..3ec436fe140c2effcc5793e2c39cb6d6949dc975 100644
*** a/contrib/pg_upgrade_support/pg_upgrade_support.c
--- b/contrib/pg_upgrade_support/pg_upgrade_support.c
***************
*** 16,28 ****
  
  /* THIS IS USED ONLY FOR PG >= 9.0 */
  
- /*
-  * Cannot include "catalog/pg_enum.h" here because we might
-  * not be compiling against PG 9.0.
-  */
- extern void EnumValuesCreate(Oid enumTypeOid, List *vals,
- 				 Oid binary_upgrade_next_pg_enum_oid);
- 
  #ifdef PG_MODULE_MAGIC
  PG_MODULE_MAGIC;
  #endif
--- 16,21 ----
*************** extern PGDLLIMPORT Oid binary_upgrade_ne
*** 33,38 ****
--- 26,32 ----
  extern PGDLLIMPORT Oid binary_upgrade_next_heap_relfilenode;
  extern PGDLLIMPORT Oid binary_upgrade_next_toast_relfilenode;
  extern PGDLLIMPORT Oid binary_upgrade_next_index_relfilenode;
+ extern PGDLLIMPORT Oid binary_upgrade_next_pg_enum_oid;
  
  Datum		set_next_pg_type_oid(PG_FUNCTION_ARGS);
  Datum		set_next_pg_type_array_oid(PG_FUNCTION_ARGS);
*************** Datum		set_next_pg_type_toast_oid(PG_FUN
*** 40,46 ****
  Datum		set_next_heap_relfilenode(PG_FUNCTION_ARGS);
  Datum		set_next_toast_relfilenode(PG_FUNCTION_ARGS);
  Datum		set_next_index_relfilenode(PG_FUNCTION_ARGS);
! Datum		add_pg_enum_label(PG_FUNCTION_ARGS);
  
  PG_FUNCTION_INFO_V1(set_next_pg_type_oid);
  PG_FUNCTION_INFO_V1(set_next_pg_type_array_oid);
--- 34,40 ----
  Datum		set_next_heap_relfilenode(PG_FUNCTION_ARGS);
  Datum		set_next_toast_relfilenode(PG_FUNCTION_ARGS);
  Datum		set_next_index_relfilenode(PG_FUNCTION_ARGS);
! Datum		set_next_pg_enum_oid(PG_FUNCTION_ARGS);
  
  PG_FUNCTION_INFO_V1(set_next_pg_type_oid);
  PG_FUNCTION_INFO_V1(set_next_pg_type_array_oid);
*************** PG_FUNCTION_INFO_V1(set_next_pg_type_toa
*** 48,54 ****
  PG_FUNCTION_INFO_V1(set_next_heap_relfilenode);
  PG_FUNCTION_INFO_V1(set_next_toast_relfilenode);
  PG_FUNCTION_INFO_V1(set_next_index_relfilenode);
! PG_FUNCTION_INFO_V1(add_pg_enum_label);
  
  Datum
  set_next_pg_type_oid(PG_FUNCTION_ARGS)
--- 42,48 ----
  PG_FUNCTION_INFO_V1(set_next_heap_relfilenode);
  PG_FUNCTION_INFO_V1(set_next_toast_relfilenode);
  PG_FUNCTION_INFO_V1(set_next_index_relfilenode);
! PG_FUNCTION_INFO_V1(set_next_pg_enum_oid);
  
  Datum
  set_next_pg_type_oid(PG_FUNCTION_ARGS)
*************** set_next_index_relfilenode(PG_FUNCTION_A
*** 111,124 ****
  }
  
  Datum
! add_pg_enum_label(PG_FUNCTION_ARGS)
  {
  	Oid			enumoid = PG_GETARG_OID(0);
- 	Oid			typoid = PG_GETARG_OID(1);
- 	Name		label = PG_GETARG_NAME(2);
  
! 	EnumValuesCreate(typoid, list_make1(makeString(NameStr(*label))),
! 					 enumoid);
  
  	PG_RETURN_VOID();
  }
--- 105,115 ----
  }
  
  Datum
! set_next_pg_enum_oid(PG_FUNCTION_ARGS)
  {
  	Oid			enumoid = PG_GETARG_OID(0);
  
! 	binary_upgrade_next_pg_enum_oid = enumoid;
  
  	PG_RETURN_VOID();
  }
diff --git a/doc/src/sgml/catalogs.sgml b/doc/src/sgml/catalogs.sgml
index b7b48e4fb93c26c421cea5c6fd01a914f9ccc8b5..9a8729b8b3194a780ea4b15dd5cfcd8bff297543 100644
*** a/doc/src/sgml/catalogs.sgml
--- b/doc/src/sgml/catalogs.sgml
***************
*** 2623,2634 ****
  
    <para>
     The <structname>pg_enum</structname> catalog contains entries
!    matching enum types to their associated values and labels. The
     internal representation of a given enum value is actually the OID
!    of its associated row in <structname>pg_enum</structname>.  The
!    OIDs for a particular enum type are guaranteed to be ordered in
!    the way the type should sort, but there is no guarantee about the
!    ordering of OIDs of unrelated enum types.
    </para>
  
    <table>
--- 2623,2631 ----
  
    <para>
     The <structname>pg_enum</structname> catalog contains entries
!    showing the values and labels for each enum type. The
     internal representation of a given enum value is actually the OID
!    of its associated row in <structname>pg_enum</structname>.
    </para>
  
    <table>
***************
*** 2653,2658 ****
--- 2650,2662 ----
       </row>
  
       <row>
+       <entry><structfield>enumsortorder</structfield></entry>
+       <entry><type>float4</type></entry>
+       <entry></entry>
+       <entry>The sort position of this enum value within its enum type</entry>
+      </row>
+ 
+      <row>
        <entry><structfield>enumlabel</structfield></entry>
        <entry><type>name</type></entry>
        <entry></entry>
***************
*** 2661,2666 ****
--- 2665,2690 ----
      </tbody>
     </tgroup>
    </table>
+ 
+   <para>
+    The OIDs for <structname>pg_enum</structname> rows follow a special
+    rule: even-numbered OIDs are guaranteed to be ordered in the same way
+    as the sort ordering of their enum type.  That is, if two even OIDs
+    belong to the same enum type, the smaller OID must have the smaller
+    <structfield>enumsortorder</structfield> value.  Odd-numbered OID values
+    need bear no relationship to the sort order.  This rule allows the
+    enum comparison routines to avoid catalog lookups in many common cases.
+    The routines that create and alter enum types attempt to assign even
+    OIDs to enum values whenever possible.
+   </para>
+ 
+   <para>
+    When an enum type is created, its members are assigned sort-order
+    positions 1..<replaceable>n</>.  But members added later might be given
+    negative or fractional values of <structfield>enumsortorder</structfield>.
+    The only requirement on these values is that they be correctly
+    ordered and unique within each enum type.
+   </para>
   </sect1>
  
  
diff --git a/doc/src/sgml/ref/alter_type.sgml b/doc/src/sgml/ref/alter_type.sgml
index 315922ea8365c482cdd787d1a775e0220ba1625c..b1336e1d0dcd38a2ca572495150b441d192b2fe7 100644
*** a/doc/src/sgml/ref/alter_type.sgml
--- b/doc/src/sgml/ref/alter_type.sgml
*************** PostgreSQL documentation
*** 24,33 ****
   <refsynopsisdiv>
  <synopsis>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> <replaceable class="PARAMETER">action</replaceable> [, ... ]
! ALTER TYPE <replaceable class="PARAMETER">name</replaceable> OWNER TO <replaceable class="PARAMETER">new_owner</replaceable> 
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> RENAME ATTRIBUTE <replaceable class="PARAMETER">attribute_name</replaceable> TO <replaceable class="PARAMETER">new_attribute_name</replaceable>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> RENAME TO <replaceable class="PARAMETER">new_name</replaceable>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> SET SCHEMA <replaceable class="PARAMETER">new_schema</replaceable>
  
  <phrase>where <replaceable class="PARAMETER">action</replaceable> is one of:</phrase>
  
--- 24,34 ----
   <refsynopsisdiv>
  <synopsis>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> <replaceable class="PARAMETER">action</replaceable> [, ... ]
! ALTER TYPE <replaceable class="PARAMETER">name</replaceable> OWNER TO <replaceable class="PARAMETER">new_owner</replaceable>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> RENAME ATTRIBUTE <replaceable class="PARAMETER">attribute_name</replaceable> TO <replaceable class="PARAMETER">new_attribute_name</replaceable>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> RENAME TO <replaceable class="PARAMETER">new_name</replaceable>
  ALTER TYPE <replaceable class="PARAMETER">name</replaceable> SET SCHEMA <replaceable class="PARAMETER">new_schema</replaceable>
+ ALTER TYPE <replaceable class="PARAMETER">name</replaceable> ADD <replaceable class="PARAMETER">new_enum_value</replaceable> [ { BEFORE | AFTER } <replaceable class="PARAMETER">existing_enum_value</replaceable> ]
  
  <phrase>where <replaceable class="PARAMETER">action</replaceable> is one of:</phrase>
  
*************** ALTER TYPE <replaceable class="PARAMETER
*** 103,108 ****
--- 104,121 ----
       </para>
      </listitem>
     </varlistentry>
+ 
+    <varlistentry>
+     <term><literal>ADD [ BEFORE | AFTER ]</literal></term>
+     <listitem>
+      <para>
+       This form adds a new value to an enum type. If the new value's place in
+       the enum's ordering is not specified using <literal>BEFORE</literal> or
+       <literal>AFTER</literal>, then the new item is placed at the end of the
+       list of values.
+      </para>
+     </listitem>
+    </varlistentry>
    </variablelist>
    </para>
  
*************** ALTER TYPE <replaceable class="PARAMETER
*** 181,187 ****
        <term><replaceable class="PARAMETER">new_attribute_name</replaceable></term>
        <listitem>
         <para>
!         The new name of the attribute begin renamed.
         </para>
        </listitem>
       </varlistentry>
--- 194,200 ----
        <term><replaceable class="PARAMETER">new_attribute_name</replaceable></term>
        <listitem>
         <para>
!         The new name of the attribute to be renamed.
         </para>
        </listitem>
       </varlistentry>
*************** ALTER TYPE <replaceable class="PARAMETER
*** 196,206 ****
--- 209,253 ----
        </listitem>
       </varlistentry>
  
+      <varlistentry>
+       <term><replaceable class="PARAMETER">new_enum_value</replaceable></term>
+       <listitem>
+        <para>
+         The new value to be added to an enum type's list of values.
+         Like all enum literals, it needs to be quoted.
+        </para>
+       </listitem>
+      </varlistentry>
+ 
+      <varlistentry>
+       <term><replaceable class="PARAMETER">existing_enum_value</replaceable></term>
+       <listitem>
+        <para>
+         The existing enum value that the new value should be added immediately
+         before or after in the enum type's sort ordering.
+         Like all enum literals, it needs to be quoted.
+        </para>
+       </listitem>
+      </varlistentry>
+ 
      </variablelist>
     </para>
    </refsect1>
  
   <refsect1>
+   <title>Notes</title>
+ 
+   <para>
+    Adding a new enum value will in some cases slow down comparison and
+    sorting of the enum type. This will usually only occur if
+    <literal>BEFORE</literal> or <literal>AFTER</literal> is used to set
+    the new value's sort position somewhere other than at the end
+    of the list.  Optimal performance will be restored if the database is
+    dumped and reloaded, or the enum type is dropped and recreated.
+   </para>
+  </refsect1>
+ 
+  <refsect1>
    <title>Examples</title>
  
    <para>
*************** ALTER TYPE email SET SCHEMA customers;
*** 232,237 ****
--- 279,291 ----
  ALTER TYPE compfoo ADD ATTRIBUTE f3 int;
  </programlisting>
    </para>
+ 
+   <para>
+    To add a new value to an enum type in a particular sort position:
+ <programlisting>
+ ALTER TYPE colors ADD 'orange' AFTER 'red';
+ </programlisting>
+   </para>
   </refsect1>
  
   <refsect1>
diff --git a/src/backend/catalog/pg_enum.c b/src/backend/catalog/pg_enum.c
index d544c1f4773d322b88d5c07bb192d6f136629829..0c384def7b60e17a0c0dc03bce0fc83d23d9389e 100644
*** a/src/backend/catalog/pg_enum.c
--- b/src/backend/catalog/pg_enum.c
***************
*** 15,29 ****
--- 15,38 ----
  
  #include "access/genam.h"
  #include "access/heapam.h"
+ #include "access/xact.h"
  #include "catalog/catalog.h"
  #include "catalog/indexing.h"
  #include "catalog/pg_enum.h"
+ #include "catalog/pg_type.h"
+ #include "storage/lmgr.h"
  #include "utils/builtins.h"
  #include "utils/fmgroids.h"
  #include "utils/rel.h"
+ #include "utils/syscache.h"
  #include "utils/tqual.h"
  
+ 
+ Oid      binary_upgrade_next_pg_enum_oid = InvalidOid;
+ 
+ static void RenumberEnumType(Relation pg_enum, HeapTuple *existing, int nelems);
  static int	oid_cmp(const void *p1, const void *p2);
+ static int	sort_order_cmp(const void *p1, const void *p2);
  
  
  /*
*************** static int	oid_cmp(const void *p1, const
*** 33,43 ****
   * vals is a list of Value strings.
   */
  void
! EnumValuesCreate(Oid enumTypeOid, List *vals,
! 				 Oid binary_upgrade_next_pg_enum_oid)
  {
  	Relation	pg_enum;
- 	TupleDesc	tupDesc;
  	NameData	enumlabel;
  	Oid		   *oids;
  	int			elemno,
--- 42,50 ----
   * vals is a list of Value strings.
   */
  void
! EnumValuesCreate(Oid enumTypeOid, List *vals)
  {
  	Relation	pg_enum;
  	NameData	enumlabel;
  	Oid		   *oids;
  	int			elemno,
*************** EnumValuesCreate(Oid enumTypeOid, List *
*** 50,97 ****
  	num_elems = list_length(vals);
  
  	/*
! 	 * XXX we do not bother to check the list of values for duplicates --- if
  	 * you have any, you'll get a less-than-friendly unique-index violation.
! 	 * Is it worth trying harder?
  	 */
  
  	pg_enum = heap_open(EnumRelationId, RowExclusiveLock);
- 	tupDesc = pg_enum->rd_att;
  
  	/*
! 	 * Allocate oids
  	 */
  	oids = (Oid *) palloc(num_elems * sizeof(Oid));
! 	if (OidIsValid(binary_upgrade_next_pg_enum_oid))
! 	{
! 		if (num_elems != 1)
! 			ereport(ERROR,
! 					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
! 					 errmsg("EnumValuesCreate() can only set a single OID")));
! 		oids[0] = binary_upgrade_next_pg_enum_oid;
! 		binary_upgrade_next_pg_enum_oid = InvalidOid;
! 	}
! 	else
  	{
  		/*
! 		 * While this method does not absolutely guarantee that we generate no
! 		 * duplicate oids (since we haven't entered each oid into the table
! 		 * before allocating the next), trouble could only occur if the oid
! 		 * counter wraps all the way around before we finish. Which seems
! 		 * unlikely.
  		 */
! 		for (elemno = 0; elemno < num_elems; elemno++)
! 		{
! 			/*
! 			 * The pg_enum.oid is stored in user tables.  This oid must be
! 			 * preserved by binary upgrades.
! 			 */
! 			oids[elemno] = GetNewOid(pg_enum);
! 		}
! 		/* sort them, just in case counter wrapped from high to low */
! 		qsort(oids, num_elems, sizeof(Oid), oid_cmp);
  	}
  
  	/* and make the entries */
  	memset(nulls, false, sizeof(nulls));
  
--- 57,98 ----
  	num_elems = list_length(vals);
  
  	/*
! 	 * We do not bother to check the list of values for duplicates --- if
  	 * you have any, you'll get a less-than-friendly unique-index violation.
! 	 * It is probably not worth trying harder.
  	 */
  
  	pg_enum = heap_open(EnumRelationId, RowExclusiveLock);
  
  	/*
! 	 * Allocate OIDs for the enum's members.
! 	 *
! 	 * While this method does not absolutely guarantee that we generate no
! 	 * duplicate OIDs (since we haven't entered each oid into the table
! 	 * before allocating the next), trouble could only occur if the OID
! 	 * counter wraps all the way around before we finish. Which seems
! 	 * unlikely.
  	 */
  	oids = (Oid *) palloc(num_elems * sizeof(Oid));
! 
! 	for (elemno = 0; elemno < num_elems; elemno++)
  	{
  		/*
! 		 * We assign even-numbered OIDs to all the new enum labels.  This
! 		 * tells the comparison functions the OIDs are in the correct sort
! 		 * order and can be compared directly.
  		 */
! 		Oid		new_oid;
! 
! 		do {
! 			new_oid = GetNewOid(pg_enum);
! 		} while (new_oid & 1);
! 		oids[elemno] = new_oid;
  	}
  
+ 	/* sort them, just in case OID counter wrapped from high to low */
+ 	qsort(oids, num_elems, sizeof(Oid), oid_cmp);
+ 
  	/* and make the entries */
  	memset(nulls, false, sizeof(nulls));
  
*************** EnumValuesCreate(Oid enumTypeOid, List *
*** 112,121 ****
  							   NAMEDATALEN - 1)));
  
  		values[Anum_pg_enum_enumtypid - 1] = ObjectIdGetDatum(enumTypeOid);
  		namestrcpy(&enumlabel, lab);
  		values[Anum_pg_enum_enumlabel - 1] = NameGetDatum(&enumlabel);
  
! 		tup = heap_form_tuple(tupDesc, values, nulls);
  		HeapTupleSetOid(tup, oids[elemno]);
  
  		simple_heap_insert(pg_enum, tup);
--- 113,123 ----
  							   NAMEDATALEN - 1)));
  
  		values[Anum_pg_enum_enumtypid - 1] = ObjectIdGetDatum(enumTypeOid);
+ 		values[Anum_pg_enum_enumsortorder - 1] = Float4GetDatum(elemno + 1);
  		namestrcpy(&enumlabel, lab);
  		values[Anum_pg_enum_enumlabel - 1] = NameGetDatum(&enumlabel);
  
! 		tup = heap_form_tuple(RelationGetDescr(pg_enum), values, nulls);
  		HeapTupleSetOid(tup, oids[elemno]);
  
  		simple_heap_insert(pg_enum, tup);
*************** EnumValuesDelete(Oid enumTypeOid)
*** 164,170 ****
  }
  
  
! /* qsort comparison function */
  static int
  oid_cmp(const void *p1, const void *p2)
  {
--- 166,487 ----
  }
  
  
! /*
!  * AddEnumLabel
!  *		Add a new label to the enum set. By default it goes at
!  *		the end, but the user can choose to place it before or
!  *		after any existing set member.
!  */
! void
! AddEnumLabel(Oid enumTypeOid,
! 			 const char *newVal,
! 			 const char *neighbor,
! 			 bool newValIsAfter)
! {
! 	Relation	pg_enum;
! 	Oid			newOid;
! 	Datum		values[Natts_pg_enum];
! 	bool		nulls[Natts_pg_enum];
! 	NameData	enumlabel;
! 	HeapTuple	enum_tup;
! 	float4		newelemorder;
! 	HeapTuple  *existing;
! 	CatCList   *list;
! 	int			nelems;
! 	int			i;
! 
! 	/* check length of new label is ok */
! 	if (strlen(newVal) > (NAMEDATALEN - 1))
! 		ereport(ERROR,
! 				(errcode(ERRCODE_INVALID_NAME),
! 				 errmsg("invalid enum label \"%s\"", newVal),
! 				 errdetail("Labels must be %d characters or less.",
! 						   NAMEDATALEN - 1)));
! 
! 	/*
! 	 * Acquire a lock on the enum type, which we won't release until commit.
! 	 * This ensures that two backends aren't concurrently modifying the same
! 	 * enum type.  Without that, we couldn't be sure to get a consistent
! 	 * view of the enum members via the syscache.  Note that this does not
! 	 * block other backends from inspecting the type; see comments for
! 	 * RenumberEnumType.
! 	 */
! 	LockDatabaseObject(TypeRelationId, enumTypeOid, 0, ExclusiveLock);
! 
! 	pg_enum = heap_open(EnumRelationId, RowExclusiveLock);
! 
! 	/* If we have to renumber the existing members, we restart from here */
! restart:
! 
! 	/* Get the list of existing members of the enum */
! 	list = SearchSysCacheList1(ENUMTYPOIDNAME,
! 							   ObjectIdGetDatum(enumTypeOid));
! 	nelems =  list->n_members;
! 
! 	/* Sort the existing members by enumsortorder */
! 	existing = (HeapTuple *) palloc(nelems * sizeof(HeapTuple));
! 	for (i = 0; i < nelems; i++)
! 		existing[i] = &(list->members[i]->tuple);
! 
! 	qsort(existing, nelems, sizeof(HeapTuple), sort_order_cmp);
! 
! 	if (neighbor == NULL)
! 	{
! 		/*
! 		 * Put the new label at the end of the list.
! 		 * No change to existing tuples is required.
! 		 */
! 		if (nelems > 0)
! 		{
! 			Form_pg_enum en = (Form_pg_enum) GETSTRUCT(existing[nelems - 1]);
! 
! 			newelemorder = en->enumsortorder + 1;
! 		}
! 		else
! 			newelemorder = 1;
! 	}
! 	else
! 	{
! 		/* BEFORE or AFTER was specified */
! 		int				nbr_index;
! 		int				other_nbr_index;
! 		Form_pg_enum	nbr_en;
! 		Form_pg_enum	other_nbr_en;
! 
! 		/* Locate the neighbor element */
! 		for (nbr_index = 0; nbr_index < nelems; nbr_index++)
! 		{
! 			Form_pg_enum en = (Form_pg_enum) GETSTRUCT(existing[nbr_index]);
! 
! 			if (strcmp(NameStr(en->enumlabel), neighbor) == 0)
! 				break;
! 		}
! 		if (nbr_index >= nelems)
! 			ereport(ERROR,
! 					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
! 					 errmsg("\"%s\" is not an existing enum label",
! 							neighbor)));
! 		nbr_en = (Form_pg_enum) GETSTRUCT(existing[nbr_index]);
! 
! 		/*
! 		 * Attempt to assign an appropriate enumsortorder value: one less
! 		 * than the smallest member, one more than the largest member,
! 		 * or halfway between two existing members.
! 		 *
! 		 * In the "halfway" case, because of the finite precision of float4,
! 		 * we might compute a value that's actually equal to one or the
! 		 * other of its neighbors.  In that case we renumber the existing
! 		 * members and try again.
! 		 */
! 		if (newValIsAfter)
! 			other_nbr_index = nbr_index + 1;
! 		else
! 			other_nbr_index = nbr_index - 1;
! 
! 		if (other_nbr_index < 0)
! 			newelemorder = nbr_en->enumsortorder - 1;
! 		else if (other_nbr_index >= nelems)
! 			newelemorder = nbr_en->enumsortorder + 1;
! 		else
! 		{
! 			other_nbr_en = (Form_pg_enum) GETSTRUCT(existing[other_nbr_index]);
! 			newelemorder = (nbr_en->enumsortorder +
! 							other_nbr_en->enumsortorder) / 2;
! 			if (newelemorder == nbr_en->enumsortorder ||
! 				newelemorder == other_nbr_en->enumsortorder)
! 			{
! 				RenumberEnumType(pg_enum, existing, nelems);
! 				/* Clean up and start over */
! 				pfree(existing);
! 				ReleaseCatCacheList(list);
! 				goto restart;
! 			}
! 		}
! 	}
! 
! 	/* Get a new OID for the new label */
! 	if (OidIsValid(binary_upgrade_next_pg_enum_oid))
! 	{
! 		/*
! 		 * In binary upgrades, just add the new label with the predetermined
! 		 * Oid.  It's pg_upgrade's responsibility that the Oid meets
! 		 * requirements.
! 		 */
! 		if (neighbor != NULL)
! 			ereport(ERROR,
! 					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
! 					 errmsg("ALTER TYPE ADD BEFORE/AFTER is incompatible with binary upgrade")));
! 
! 		newOid = binary_upgrade_next_pg_enum_oid;
! 		binary_upgrade_next_pg_enum_oid = InvalidOid;
! 	}
! 	else
! 	{
! 		/*
! 		 * Normal case: we need to allocate a new Oid for the value.
! 		 *
! 		 * We want to give the new element an even-numbered Oid if it's safe,
! 		 * which is to say it compares correctly to all pre-existing even
! 		 * numbered Oids in the enum.  Otherwise, we must give it an odd Oid.
! 		 */
! 		for (;;)
! 		{
! 			bool	sorts_ok;
! 
! 			/* Get a new OID (different from all existing pg_enum tuples) */
! 			newOid = GetNewOid(pg_enum);
! 
! 			/*
! 			 * Detect whether it sorts correctly relative to existing
! 			 * even-numbered labels of the enum.  We can ignore existing
! 			 * labels with odd Oids, since a comparison involving one of
! 			 * those will not take the fast path anyway.
! 			 */
! 			sorts_ok = true;
! 			for (i = 0; i < nelems; i++)
! 			{
! 				HeapTuple	exists_tup = existing[i];
! 				Form_pg_enum exists_en = (Form_pg_enum) GETSTRUCT(exists_tup);
! 				Oid			exists_oid = HeapTupleGetOid(exists_tup);
! 
! 				if (exists_oid & 1)
! 					continue;	/* ignore odd Oids */
! 
! 				if (exists_en->enumsortorder < newelemorder)
! 				{
! 					/* should sort before */
! 					if (exists_oid >= newOid)
! 					{
! 						sorts_ok = false;
! 						break;
! 					}
! 				}
! 				else
! 				{
! 					/* should sort after */
! 					if (exists_oid <= newOid)
! 					{
! 						sorts_ok = false;
! 						break;
! 					}
! 				}
! 			}
! 
! 			if (sorts_ok)
! 			{
! 				/* If it's even and sorts OK, we're done. */
! 				if ((newOid & 1) == 0)
! 					break;
! 
! 				/*
! 				 * If it's odd, and sorts OK, loop back to get another OID
! 				 * and try again.  Probably, the next available even OID
! 				 * will sort correctly too, so it's worth trying.
! 				 */
! 			}
! 			else
! 			{
! 				/*
! 				 * If it's odd, and does not sort correctly, we're done.
! 				 * (Probably, the next available even OID would sort
! 				 * incorrectly too, so no point in trying again.)
! 				 */
! 				if (newOid & 1)
! 					break;
! 
! 				/*
! 				 * If it's even, and does not sort correctly, loop back to get
! 				 * another OID and try again.  (We *must* reject this case.)
! 				 */
! 			}
! 		}
! 	}
! 
! 	/* Done with info about existing members */
! 	pfree(existing);
! 	ReleaseCatCacheList(list);
! 
! 	/* Create the new pg_enum entry */
! 	memset(nulls, false, sizeof(nulls));
! 	values[Anum_pg_enum_enumtypid - 1] = ObjectIdGetDatum(enumTypeOid);
! 	values[Anum_pg_enum_enumsortorder - 1] = Float4GetDatum(newelemorder);
! 	namestrcpy(&enumlabel, newVal);
! 	values[Anum_pg_enum_enumlabel - 1] = NameGetDatum(&enumlabel);
! 	enum_tup = heap_form_tuple(RelationGetDescr(pg_enum), values, nulls);
! 	HeapTupleSetOid(enum_tup, newOid);
! 	simple_heap_insert(pg_enum, enum_tup);
! 	CatalogUpdateIndexes(pg_enum, enum_tup);
! 	heap_freetuple(enum_tup);
! 
! 	heap_close(pg_enum, RowExclusiveLock);
! }
! 
! 
! /*
!  * RenumberEnumType
!  *		Renumber existing enum elements to have sort positions 1..n.
!  *
!  * We avoid doing this unless absolutely necessary; in most installations
!  * it will never happen.  The reason is that updating existing pg_enum
!  * entries creates hazards for other backends that are concurrently reading
!  * pg_enum with SnapshotNow semantics.  A concurrent SnapshotNow scan could
!  * see both old and new versions of an updated row as valid, or neither of
!  * them, if the commit happens between scanning the two versions.  It's
!  * also quite likely for a concurrent scan to see an inconsistent set of
!  * rows (some members updated, some not).
!  *
!  * We can avoid these risks by reading pg_enum with an MVCC snapshot
!  * instead of SnapshotNow, but that forecloses use of the syscaches.
!  * We therefore make the following choices:
!  *
!  * 1. Any code that is interested in the enumsortorder values MUST read
!  * pg_enum with an MVCC snapshot, or else acquire lock on the enum type
!  * to prevent concurrent execution of AddEnumLabel().  The risk of
!  * seeing inconsistent values of enumsortorder is too high otherwise.
!  *
!  * 2. Code that is not examining enumsortorder can use a syscache
!  * (for example, enum_in and enum_out do so).  The worst that can happen
!  * is a transient failure to find any valid value of the row.  This is
!  * judged acceptable in view of the infrequency of use of RenumberEnumType.
!  */
! static void
! RenumberEnumType(Relation pg_enum, HeapTuple *existing, int nelems)
! {
! 	int			i;
! 
! 	/*
! 	 * We should only need to increase existing elements' enumsortorders,
! 	 * never decrease them.  Therefore, work from the end backwards, to avoid
! 	 * unwanted uniqueness violations.
! 	 */
! 	for (i = nelems - 1; i >= 0; i--)
! 	{
! 		HeapTuple	newtup;
! 		Form_pg_enum en;
! 		float4		newsortorder;
! 
! 		newtup = heap_copytuple(existing[i]);
! 		en = (Form_pg_enum) GETSTRUCT(newtup);
! 
! 		newsortorder = i + 1;
! 		if (en->enumsortorder != newsortorder)
! 		{
! 			en->enumsortorder = newsortorder;
! 
! 			simple_heap_update(pg_enum, &newtup->t_self, newtup);
! 
! 			CatalogUpdateIndexes(pg_enum, newtup);
! 		}
! 
! 		heap_freetuple(newtup);
! 	}
! 
! 	/* Make the updates visible */
! 	CommandCounterIncrement();
! }
! 
! 
! /* qsort comparison function for oids */
  static int
  oid_cmp(const void *p1, const void *p2)
  {
*************** oid_cmp(const void *p1, const void *p2)
*** 177,179 ****
--- 494,513 ----
  		return 1;
  	return 0;
  }
+ 
+ /* qsort comparison function for tuples by sort order */
+ static int
+ sort_order_cmp(const void *p1, const void *p2)
+ {
+ 	HeapTuple		v1 = *((const HeapTuple *) p1);
+ 	HeapTuple		v2 = *((const HeapTuple *) p2);
+ 	Form_pg_enum	en1 = (Form_pg_enum) GETSTRUCT(v1);
+ 	Form_pg_enum	en2 = (Form_pg_enum) GETSTRUCT(v2);
+ 
+ 	if (en1->enumsortorder < en2->enumsortorder)
+ 		return -1;
+ 	else if (en1->enumsortorder > en2->enumsortorder)
+ 		return 1;
+ 	else
+ 		return 0;
+ }
diff --git a/src/backend/commands/typecmds.c b/src/backend/commands/typecmds.c
index 46b156e09a30ff264e6cf2e7567a2beb8cda43cb..220be9b443b54143f4ed097a2786f40aaf66e415 100644
*** a/src/backend/commands/typecmds.c
--- b/src/backend/commands/typecmds.c
*************** static Oid	findTypeTypmodinFunction(List
*** 84,90 ****
  static Oid	findTypeTypmodoutFunction(List *procname);
  static Oid	findTypeAnalyzeFunction(List *procname, Oid typeOid);
  static List *get_rels_with_domain(Oid domainOid, LOCKMODE lockmode);
! static void checkDomainOwner(HeapTuple tup, TypeName *typename);
  static char *domainAddConstraint(Oid domainOid, Oid domainNamespace,
  					Oid baseTypeOid,
  					int typMod, Constraint *constr,
--- 84,91 ----
  static Oid	findTypeTypmodoutFunction(List *procname);
  static Oid	findTypeAnalyzeFunction(List *procname, Oid typeOid);
  static List *get_rels_with_domain(Oid domainOid, LOCKMODE lockmode);
! static void checkDomainOwner(HeapTuple tup);
! static void checkEnumOwner(HeapTuple tup);
  static char *domainAddConstraint(Oid domainOid, Oid domainNamespace,
  					Oid baseTypeOid,
  					int typMod, Constraint *constr,
*************** DefineEnum(CreateEnumStmt *stmt)
*** 1150,1156 ****
  				   false);		/* Type NOT NULL */
  
  	/* Enter the enum's values into pg_enum */
! 	EnumValuesCreate(enumTypeOid, stmt->vals, InvalidOid);
  
  	/*
  	 * Create the array type that goes with it.
--- 1151,1157 ----
  				   false);		/* Type NOT NULL */
  
  	/* Enter the enum's values into pg_enum */
! 	EnumValuesCreate(enumTypeOid, stmt->vals);
  
  	/*
  	 * Create the array type that goes with it.
*************** DefineEnum(CreateEnumStmt *stmt)
*** 1191,1196 ****
--- 1192,1251 ----
  	pfree(enumArrayName);
  }
  
+ /*
+  * AlterEnum
+  *		Adds a new label to an existing enum.
+  */
+ void
+ AlterEnum(AlterEnumStmt *stmt)
+ {
+ 	Oid			enum_type_oid;
+ 	TypeName   *typename;
+ 	HeapTuple	tup;
+ 
+ 	/* Make a TypeName so we can use standard type lookup machinery */
+ 	typename = makeTypeNameFromNameList(stmt->typeName);
+ 	enum_type_oid = typenameTypeId(NULL, typename, NULL);
+ 
+ 	tup = SearchSysCache1(TYPEOID, ObjectIdGetDatum(enum_type_oid));
+ 	if (!HeapTupleIsValid(tup))
+ 		elog(ERROR, "cache lookup failed for type %u", enum_type_oid);
+ 
+ 	/* Check it's an enum and check user has permission to ALTER the enum */
+ 	checkEnumOwner(tup);
+ 
+ 	/* Add the new label */
+ 	AddEnumLabel(enum_type_oid, stmt->newVal,
+ 				 stmt->newValNeighbor, stmt->newValIsAfter);
+ 
+ 	ReleaseSysCache(tup);
+ }
+ 
+ 
+ /*
+  * checkEnumOwner
+  *
+  * Check that the type is actually an enum and that the current user
+  * has permission to do ALTER TYPE on it.  Throw an error if not.
+  */
+ static void
+ checkEnumOwner(HeapTuple tup)
+ {
+ 	Form_pg_type typTup = (Form_pg_type) GETSTRUCT(tup);
+ 
+ 	/* Check that this is actually an enum */
+ 	if (typTup->typtype != TYPTYPE_ENUM)
+ 		ereport(ERROR,
+ 				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
+ 				 errmsg("%s is not an enum",
+ 						format_type_be(HeapTupleGetOid(tup)))));
+ 
+ 	/* Permission check: must own type */
+ 	if (!pg_type_ownercheck(HeapTupleGetOid(tup), GetUserId()))
+ 		aclcheck_error(ACLCHECK_NOT_OWNER, ACL_KIND_TYPE,
+ 					   format_type_be(HeapTupleGetOid(tup)));
+ }
+ 
  
  /*
   * Find suitable I/O functions for a type.
*************** AlterDomainDefault(List *names, Node *de
*** 1576,1582 ****
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup, typename);
  
  	/* Setup new tuple */
  	MemSet(new_record, (Datum) 0, sizeof(new_record));
--- 1631,1637 ----
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup);
  
  	/* Setup new tuple */
  	MemSet(new_record, (Datum) 0, sizeof(new_record));
*************** AlterDomainNotNull(List *names, bool not
*** 1702,1708 ****
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup, typename);
  
  	/* Is the domain already set to the desired constraint? */
  	if (typTup->typnotnull == notNull)
--- 1757,1763 ----
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup);
  
  	/* Is the domain already set to the desired constraint? */
  	if (typTup->typnotnull == notNull)
*************** AlterDomainDropConstraint(List *names, c
*** 1801,1807 ****
  		elog(ERROR, "cache lookup failed for type %u", domainoid);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup, typename);
  
  	/* Grab an appropriate lock on the pg_constraint relation */
  	conrel = heap_open(ConstraintRelationId, RowExclusiveLock);
--- 1856,1862 ----
  		elog(ERROR, "cache lookup failed for type %u", domainoid);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup);
  
  	/* Grab an appropriate lock on the pg_constraint relation */
  	conrel = heap_open(ConstraintRelationId, RowExclusiveLock);
*************** AlterDomainAddConstraint(List *names, No
*** 1875,1881 ****
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup, typename);
  
  	if (!IsA(newConstraint, Constraint))
  		elog(ERROR, "unrecognized node type: %d",
--- 1930,1936 ----
  	typTup = (Form_pg_type) GETSTRUCT(tup);
  
  	/* Check it's a domain and check user has permission for ALTER DOMAIN */
! 	checkDomainOwner(tup);
  
  	if (!IsA(newConstraint, Constraint))
  		elog(ERROR, "unrecognized node type: %d",
*************** get_rels_with_domain(Oid domainOid, LOCK
*** 2187,2193 ****
   * has permission to do ALTER DOMAIN on it.  Throw an error if not.
   */
  static void
! checkDomainOwner(HeapTuple tup, TypeName *typename)
  {
  	Form_pg_type typTup = (Form_pg_type) GETSTRUCT(tup);
  
--- 2242,2248 ----
   * has permission to do ALTER DOMAIN on it.  Throw an error if not.
   */
  static void
! checkDomainOwner(HeapTuple tup)
  {
  	Form_pg_type typTup = (Form_pg_type) GETSTRUCT(tup);
  
*************** checkDomainOwner(HeapTuple tup, TypeName
*** 2195,2202 ****
  	if (typTup->typtype != TYPTYPE_DOMAIN)
  		ereport(ERROR,
  				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
! 				 errmsg("\"%s\" is not a domain",
! 						TypeNameToString(typename))));
  
  	/* Permission check: must own type */
  	if (!pg_type_ownercheck(HeapTupleGetOid(tup), GetUserId()))
--- 2250,2257 ----
  	if (typTup->typtype != TYPTYPE_DOMAIN)
  		ereport(ERROR,
  				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
! 				 errmsg("%s is not a domain",
! 						format_type_be(HeapTupleGetOid(tup)))));
  
  	/* Permission check: must own type */
  	if (!pg_type_ownercheck(HeapTupleGetOid(tup), GetUserId()))
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 508d7c70b137fa34f5dc31c00ec8fdf36de21a95..5346c72cd98f341e15b37b6d1ba75168ae5b0058 100644
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copyCreateEnumStmt(CreateEnumStmt *from
*** 2901,2906 ****
--- 2901,2919 ----
  	return newnode;
  }
  
+ static AlterEnumStmt *
+ _copyAlterEnumStmt(AlterEnumStmt *from)
+ {
+ 	AlterEnumStmt *newnode = makeNode(AlterEnumStmt);
+ 
+ 	COPY_NODE_FIELD(typeName);
+ 	COPY_STRING_FIELD(newVal);
+ 	COPY_STRING_FIELD(newValNeighbor);
+ 	COPY_SCALAR_FIELD(newValIsAfter);
+ 
+ 	return newnode;
+ }
+ 
  static ViewStmt *
  _copyViewStmt(ViewStmt *from)
  {
*************** copyObject(void *from)
*** 4064,4069 ****
--- 4077,4085 ----
  		case T_CreateEnumStmt:
  			retval = _copyCreateEnumStmt(from);
  			break;
+ 		case T_AlterEnumStmt:
+ 			retval = _copyAlterEnumStmt(from);
+ 			break;
  		case T_ViewStmt:
  			retval = _copyViewStmt(from);
  			break;
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index 19262aad6691ea8caca2c7a20fa07a2de0b4d59f..7cb2192d94725734405377864c36fc3c0271e2b7 100644
*** a/src/backend/nodes/equalfuncs.c
--- b/src/backend/nodes/equalfuncs.c
*************** _equalCreateEnumStmt(CreateEnumStmt *a, 
*** 1393,1398 ****
--- 1393,1409 ----
  }
  
  static bool
+ _equalAlterEnumStmt(AlterEnumStmt *a, AlterEnumStmt *b)
+ {
+ 	COMPARE_NODE_FIELD(typeName);
+ 	COMPARE_STRING_FIELD(newVal);
+ 	COMPARE_STRING_FIELD(newValNeighbor);
+ 	COMPARE_SCALAR_FIELD(newValIsAfter);
+ 
+ 	return true;
+ }
+ 
+ static bool
  _equalViewStmt(ViewStmt *a, ViewStmt *b)
  {
  	COMPARE_NODE_FIELD(view);
*************** equal(void *a, void *b)
*** 2700,2705 ****
--- 2711,2719 ----
  		case T_CreateEnumStmt:
  			retval = _equalCreateEnumStmt(a, b);
  			break;
+ 		case T_AlterEnumStmt:
+ 			retval = _equalAlterEnumStmt(a, b);
+ 			break;
  		case T_ViewStmt:
  			retval = _equalViewStmt(a, b);
  			break;
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index c4165f0bf074f1be23e4bbdb4608fec2cbd76563..1394b21dec4de7400a466269ba6b36bb6390ce4e 100644
*** a/src/backend/parser/gram.y
--- b/src/backend/parser/gram.y
*************** static RangeVar *makeRangeVarFromAnyName
*** 182,189 ****
  }
  
  %type <node>	stmt schema_stmt
! 		AlterDatabaseStmt AlterDatabaseSetStmt AlterDomainStmt AlterFdwStmt
! 		AlterForeignServerStmt AlterGroupStmt
  		AlterObjectSchemaStmt AlterOwnerStmt AlterSeqStmt AlterTableStmt
  		AlterCompositeTypeStmt AlterUserStmt AlterUserMappingStmt AlterUserSetStmt
  		AlterRoleStmt AlterRoleSetStmt
--- 182,189 ----
  }
  
  %type <node>	stmt schema_stmt
! 		AlterDatabaseStmt AlterDatabaseSetStmt AlterDomainStmt AlterEnumStmt
! 		AlterFdwStmt AlterForeignServerStmt AlterGroupStmt
  		AlterObjectSchemaStmt AlterOwnerStmt AlterSeqStmt AlterTableStmt
  		AlterCompositeTypeStmt AlterUserStmt AlterUserMappingStmt AlterUserSetStmt
  		AlterRoleStmt AlterRoleSetStmt
*************** stmt :
*** 652,657 ****
--- 652,658 ----
  			| AlterDatabaseSetStmt
  			| AlterDefaultPrivilegesStmt
  			| AlterDomainStmt
+ 			| AlterEnumStmt
  			| AlterFdwStmt
  			| AlterForeignServerStmt
  			| AlterFunctionStmt
*************** enum_val_list:	Sconst
*** 3863,3868 ****
--- 3864,3905 ----
  				{ $$ = lappend($1, makeString($3)); }
  		;
  
+ /*****************************************************************************
+  *
+  *	ALTER TYPE enumtype ADD ...
+  *
+  *****************************************************************************/
+ 
+ AlterEnumStmt:
+          ALTER TYPE_P any_name ADD_P Sconst
+ 			 {
+ 				 AlterEnumStmt *n = makeNode(AlterEnumStmt);
+ 				 n->typeName = $3;
+ 				 n->newVal = $5;
+ 				 n->newValNeighbor = NULL;
+ 				 n->newValIsAfter = true;
+ 				 $$ = (Node *) n;
+ 			 }
+ 		 | ALTER TYPE_P any_name ADD_P Sconst BEFORE Sconst
+ 			 {
+ 				 AlterEnumStmt *n = makeNode(AlterEnumStmt);
+ 				 n->typeName = $3;
+ 				 n->newVal = $5;
+ 				 n->newValNeighbor = $7;
+ 				 n->newValIsAfter = false;
+ 				 $$ = (Node *) n;
+ 			 }
+ 		 | ALTER TYPE_P any_name ADD_P Sconst AFTER Sconst
+ 			 {
+ 				 AlterEnumStmt *n = makeNode(AlterEnumStmt);
+ 				 n->typeName = $3;
+ 				 n->newVal = $5;
+ 				 n->newValNeighbor = $7;
+ 				 n->newValIsAfter = true;
+ 				 $$ = (Node *) n;
+ 			 }
+ 		 ;
+ 
  
  /*****************************************************************************
   *
diff --git a/src/backend/tcop/utility.c b/src/backend/tcop/utility.c
index 75cb354ea89db9ce071ab3d781c8daf3280cd5e4..2c8b7aa810ef12101ee0755b28f391f0162ab6e2 100644
*** a/src/backend/tcop/utility.c
--- b/src/backend/tcop/utility.c
*************** check_xact_readonly(Node *parsetree)
*** 190,195 ****
--- 190,196 ----
  		case T_CreateTrigStmt:
  		case T_CompositeTypeStmt:
  		case T_CreateEnumStmt:
+ 		case T_AlterEnumStmt:
  		case T_ViewStmt:
  		case T_DropCastStmt:
  		case T_DropStmt:
*************** standard_ProcessUtility(Node *parsetree,
*** 860,865 ****
--- 861,870 ----
  			DefineEnum((CreateEnumStmt *) parsetree);
  			break;
  
+ 		case T_AlterEnumStmt:	/* ALTER TYPE (enum) */
+ 			AlterEnum((AlterEnumStmt *) parsetree);
+ 			break;
+ 
  		case T_ViewStmt:		/* CREATE VIEW */
  			DefineView((ViewStmt *) parsetree, queryString);
  			break;
*************** CreateCommandTag(Node *parsetree)
*** 1868,1873 ****
--- 1873,1882 ----
  			tag = "CREATE TYPE";
  			break;
  
+ 		case T_AlterEnumStmt:
+ 			tag = "ALTER TYPE";
+ 			break;
+ 
  		case T_ViewStmt:
  			tag = "CREATE VIEW";
  			break;
*************** GetCommandLogLevel(Node *parsetree)
*** 2410,2415 ****
--- 2419,2428 ----
  			lev = LOGSTMT_DDL;
  			break;
  
+ 		case T_AlterEnumStmt:
+ 			lev = LOGSTMT_DDL;
+ 			break;
+ 
  		case T_ViewStmt:
  			lev = LOGSTMT_DDL;
  			break;
diff --git a/src/backend/utils/adt/enum.c b/src/backend/utils/adt/enum.c
index e5747a46bcd341488b26cc739f50dc0f8d14f622..ff9fa498f296ffb9f626a55d58d641931f2c57d2 100644
*** a/src/backend/utils/adt/enum.c
--- b/src/backend/utils/adt/enum.c
***************
*** 15,30 ****
  
  #include "catalog/pg_enum.h"
  #include "fmgr.h"
  #include "utils/array.h"
  #include "utils/builtins.h"
  #include "utils/lsyscache.h"
  #include "utils/syscache.h"
! #include "libpq/pqformat.h"
! #include "miscadmin.h"
  
  
  static ArrayType *enum_range_internal(Oid enumtypoid, Oid lower, Oid upper);
! static int	enum_elem_cmp(const void *left, const void *right);
  
  
  /* Basic I/O support */
--- 15,37 ----
  
  #include "catalog/pg_enum.h"
  #include "fmgr.h"
+ #include "libpq/pqformat.h"
+ #include "miscadmin.h"
  #include "utils/array.h"
  #include "utils/builtins.h"
  #include "utils/lsyscache.h"
  #include "utils/syscache.h"
! #include "utils/typcache.h"
  
  
+ typedef struct
+ {
+ 	Oid			enum_oid;		/* OID of one enum value */
+ 	float4		sort_order;		/* its sort position */
+ } enum_sort;
+ 
  static ArrayType *enum_range_internal(Oid enumtypoid, Oid lower, Oid upper);
! static int	enum_sort_cmp(const void *left, const void *right);
  
  
  /* Basic I/O support */
*************** enum_send(PG_FUNCTION_ARGS)
*** 155,167 ****
  
  /* Comparison functions and related */
  
  Datum
  enum_lt(PG_FUNCTION_ARGS)
  {
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(a < b);
  }
  
  Datum
--- 162,224 ----
  
  /* Comparison functions and related */
  
+ /*
+  * enum_cmp_internal is the common engine for all the visible comparison
+  * functions, except for enum_eq and enum_ne which can just check for OID
+  * equality directly.
+  */
+ static int
+ enum_cmp_internal(Oid arg1, Oid arg2, FunctionCallInfo fcinfo)
+ {
+ 	TypeCacheEntry *tcache;
+ 
+ 	/* Equal OIDs are equal no matter what */
+ 	if (arg1 == arg2)
+ 		return 0;
+ 
+ 	/* Fast path: even-numbered Oids are known to compare correctly */
+ 	if ((arg1 & 1) == 0 && (arg2 & 1) == 0)
+ 	{
+ 		if (arg1 < arg2)
+ 			return -1;
+ 		else
+ 			return 1;
+ 	}
+ 
+ 	/* Locate the typcache entry for the enum type */
+ 	tcache = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+ 	if (tcache == NULL)
+ 	{
+ 		HeapTuple	enum_tup;
+ 		Form_pg_enum en;
+ 		Oid			typeoid;
+ 
+ 		/* Get the OID of the enum type containing arg1 */
+ 		enum_tup = SearchSysCache1(ENUMOID, ObjectIdGetDatum(arg1));
+ 		if (!HeapTupleIsValid(enum_tup))
+ 			ereport(ERROR,
+ 					(errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
+ 					 errmsg("invalid internal value for enum: %u",
+ 							arg1)));
+ 		en = (Form_pg_enum) GETSTRUCT(enum_tup);
+ 		typeoid = en->enumtypid;
+ 		ReleaseSysCache(enum_tup);
+ 		/* Now locate and remember the typcache entry */
+ 		tcache = lookup_type_cache(typeoid, 0);
+ 		fcinfo->flinfo->fn_extra = (void *) tcache;
+ 	}
+ 
+ 	/* The remaining comparison logic is in typcache.c */
+ 	return compare_values_of_enum(tcache, arg1, arg2);
+ }
+ 
  Datum
  enum_lt(PG_FUNCTION_ARGS)
  {
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(enum_cmp_internal(a, b, fcinfo) < 0);
  }
  
  Datum
*************** enum_le(PG_FUNCTION_ARGS)
*** 170,176 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(a <= b);
  }
  
  Datum
--- 227,233 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(enum_cmp_internal(a, b, fcinfo) <= 0);
  }
  
  Datum
*************** enum_ge(PG_FUNCTION_ARGS)
*** 197,203 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(a >= b);
  }
  
  Datum
--- 254,260 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(enum_cmp_internal(a, b, fcinfo) >= 0);
  }
  
  Datum
*************** enum_gt(PG_FUNCTION_ARGS)
*** 206,212 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(a > b);
  }
  
  Datum
--- 263,269 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_BOOL(enum_cmp_internal(a, b, fcinfo) > 0);
  }
  
  Datum
*************** enum_smaller(PG_FUNCTION_ARGS)
*** 215,221 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_OID(a <= b ? a : b);
  }
  
  Datum
--- 272,278 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_OID(enum_cmp_internal(a, b, fcinfo) < 0 ? a : b);
  }
  
  Datum
*************** enum_larger(PG_FUNCTION_ARGS)
*** 224,230 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_OID(a >= b ? a : b);
  }
  
  Datum
--- 281,287 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	PG_RETURN_OID(enum_cmp_internal(a, b, fcinfo) > 0 ? a : b);
  }
  
  Datum
*************** enum_cmp(PG_FUNCTION_ARGS)
*** 233,242 ****
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	if (a > b)
! 		PG_RETURN_INT32(1);
! 	else if (a == b)
  		PG_RETURN_INT32(0);
  	else
  		PG_RETURN_INT32(-1);
  }
--- 290,299 ----
  	Oid			a = PG_GETARG_OID(0);
  	Oid			b = PG_GETARG_OID(1);
  
! 	if (a == b)
  		PG_RETURN_INT32(0);
+ 	else if (enum_cmp_internal(a, b, fcinfo) > 0)
+ 		PG_RETURN_INT32(1);
  	else
  		PG_RETURN_INT32(-1);
  }
*************** enum_first(PG_FUNCTION_ARGS)
*** 248,253 ****
--- 305,311 ----
  {
  	Oid			enumtypoid;
  	Oid			min = InvalidOid;
+ 	float4		min_sort = 0;	/* arbitrary, this value won't be used */
  	CatCList   *list;
  	int			num,
  				i;
*************** enum_first(PG_FUNCTION_ARGS)
*** 267,276 ****
  	num = list->n_members;
  	for (i = 0; i < num; i++)
  	{
! 		Oid			valoid = HeapTupleHeaderGetOid(list->members[i]->tuple.t_data);
  
! 		if (!OidIsValid(min) || valoid < min)
! 			min = valoid;
  	}
  
  	ReleaseCatCacheList(list);
--- 325,338 ----
  	num = list->n_members;
  	for (i = 0; i < num; i++)
  	{
! 		HeapTuple tup = &(list->members[i]->tuple);
! 		Form_pg_enum en = (Form_pg_enum) GETSTRUCT(tup);
  
! 		if (!OidIsValid(min) || en->enumsortorder < min_sort)
! 		{
! 			min = HeapTupleGetOid(tup);
! 			min_sort = en->enumsortorder;
! 		}
  	}
  
  	ReleaseCatCacheList(list);
*************** enum_last(PG_FUNCTION_ARGS)
*** 287,292 ****
--- 349,355 ----
  {
  	Oid			enumtypoid;
  	Oid			max = InvalidOid;
+ 	float4		max_sort = 0;	/* arbitrary, this value won't be used */
  	CatCList   *list;
  	int			num,
  				i;
*************** enum_last(PG_FUNCTION_ARGS)
*** 306,315 ****
  	num = list->n_members;
  	for (i = 0; i < num; i++)
  	{
! 		Oid			valoid = HeapTupleHeaderGetOid(list->members[i]->tuple.t_data);
  
! 		if (!OidIsValid(max) || valoid > max)
! 			max = valoid;
  	}
  
  	ReleaseCatCacheList(list);
--- 369,382 ----
  	num = list->n_members;
  	for (i = 0; i < num; i++)
  	{
! 		HeapTuple tup = &(list->members[i]->tuple);
! 		Form_pg_enum en = (Form_pg_enum) GETSTRUCT(tup);
  
! 		if (!OidIsValid(max) || en->enumsortorder > max_sort)
! 		{
! 			max = HeapTupleGetOid(tup);
! 			max_sort = en->enumsortorder;
! 		}
  	}
  
  	ReleaseCatCacheList(list);
*************** enum_range_internal(Oid enumtypoid, Oid 
*** 382,427 ****
  				i,
  				j;
  	Datum	   *elems;
  
  	list = SearchSysCacheList1(ENUMTYPOIDNAME, ObjectIdGetDatum(enumtypoid));
  	total = list->n_members;
  
  	elems = (Datum *) palloc(total * sizeof(Datum));
  
- 	j = 0;
  	for (i = 0; i < total; i++)
  	{
! 		Oid			val = HeapTupleGetOid(&(list->members[i]->tuple));
  
! 		if ((!OidIsValid(lower) || lower <= val) &&
! 			(!OidIsValid(upper) || val <= upper))
! 			elems[j++] = ObjectIdGetDatum(val);
  	}
  
! 	/* shouldn't need the cache anymore */
  	ReleaseCatCacheList(list);
  
! 	/* sort results into OID order */
! 	qsort(elems, j, sizeof(Datum), enum_elem_cmp);
  
  	/* note this hardwires some details about the representation of Oid */
  	result = construct_array(elems, j, enumtypoid, sizeof(Oid), true, 'i');
  
  	pfree(elems);
  
  	return result;
  }
  
! /* qsort comparison function for Datums that are OIDs */
  static int
! enum_elem_cmp(const void *left, const void *right)
  {
! 	Oid			l = DatumGetObjectId(*((const Datum *) left));
! 	Oid			r = DatumGetObjectId(*((const Datum *) right));
  
! 	if (l < r)
  		return -1;
! 	if (l > r)
  		return 1;
! 	return 0;
  }
--- 449,517 ----
  				i,
  				j;
  	Datum	   *elems;
+ 	enum_sort  *sort_items;
+ 	bool        left_found;
  
+ 	/* collect information about the enum's members using the syscache */
  	list = SearchSysCacheList1(ENUMTYPOIDNAME, ObjectIdGetDatum(enumtypoid));
  	total = list->n_members;
  
  	elems = (Datum *) palloc(total * sizeof(Datum));
+ 	sort_items = (enum_sort *) palloc(total * sizeof(enum_sort));
  
  	for (i = 0; i < total; i++)
  	{
! 		HeapTuple tup = &(list->members[i]->tuple);
! 		Form_pg_enum en = (Form_pg_enum) GETSTRUCT(tup);
  
! 		sort_items[i].enum_oid = HeapTupleGetOid(tup);
! 		sort_items[i].sort_order = en->enumsortorder;
  	}
  
! 	/* shouldn't need the syscache items anymore */
  	ReleaseCatCacheList(list);
  
! 	/* sort results into sort_order sequence */
! 	qsort(sort_items, total, sizeof(enum_sort), enum_sort_cmp);
! 
! 	/* collect the desired OIDs in elems[] */
! 	j = 0;
! 	left_found = !OidIsValid(lower);
! 	for (i = 0; i < total; i++)
! 	{
! 		if (!left_found && lower == sort_items[i].enum_oid)
! 			left_found = true;
! 
! 		if (left_found)
! 			elems[j++] = ObjectIdGetDatum(sort_items[i].enum_oid);
! 
! 		if (OidIsValid(upper) && upper == sort_items[i].enum_oid)
! 			break;
! 	}
  
+ 	/* and build the result array */
  	/* note this hardwires some details about the representation of Oid */
  	result = construct_array(elems, j, enumtypoid, sizeof(Oid), true, 'i');
  
  	pfree(elems);
+ 	pfree(sort_items);
  
  	return result;
  }
  
! /*
!  * qsort comparison using sort order, for range routines
!  */
  static int
! enum_sort_cmp(const void *left, const void *right)
  {
! 	const enum_sort *l = (const enum_sort *) left;
! 	const enum_sort *r = (const enum_sort *) right;
  
! 	if (l->sort_order < r->sort_order)
  		return -1;
! 	else if (l->sort_order > r->sort_order)
  		return 1;
! 	else
! 		return 0;
  }
diff --git a/src/backend/utils/cache/typcache.c b/src/backend/utils/cache/typcache.c
index 200961448903b12cabb11b895629404ca0b3d90a..e683203fd4e24d18a043849f9cd96f757a19faab 100644
*** a/src/backend/utils/cache/typcache.c
--- b/src/backend/utils/cache/typcache.c
***************
*** 45,63 ****
--- 45,83 ----
  #include "access/hash.h"
  #include "access/heapam.h"
  #include "access/nbtree.h"
+ #include "catalog/indexing.h"
+ #include "catalog/pg_enum.h"
  #include "catalog/pg_type.h"
  #include "commands/defrem.h"
  #include "utils/builtins.h"
+ #include "utils/fmgroids.h"
  #include "utils/inval.h"
  #include "utils/lsyscache.h"
  #include "utils/rel.h"
+ #include "utils/snapmgr.h"
  #include "utils/syscache.h"
+ #include "utils/tqual.h"
  #include "utils/typcache.h"
  
  
  /* The main type cache hashtable searched by lookup_type_cache */
  static HTAB *TypeCacheHash = NULL;
  
+ /* Private information to support comparisons of enum values */
+ typedef struct
+ {
+ 	Oid			enum_oid;		/* OID of one enum value */
+ 	float4		sort_order;		/* its sort position */
+ } EnumItem;
+ 
+ typedef struct TypeCacheEnumData
+ {
+ 	Oid			bitmap_base;	/* OID corresponding to bit 0 of bitmapset */
+ 	Bitmapset  *sorted_values;	/* Set of OIDs known to be in order */
+ 	int			num_values;		/* total number of values in enum */
+ 	EnumItem	enum_values[1];	/* VARIABLE LENGTH ARRAY */
+ } TypeCacheEnumData;
+ 
  /*
   * We use a separate table for storing the definitions of non-anonymous
   * record types.  Once defined, a record type will be remembered for the
*************** static int32 RecordCacheArrayLen = 0;	/*
*** 88,93 ****
--- 108,116 ----
  static int32 NextRecordTypmod = 0;		/* number of entries used */
  
  static void TypeCacheRelCallback(Datum arg, Oid relid);
+ static void load_enum_cache_data(TypeCacheEntry *tcache);
+ static EnumItem *find_enumitem(TypeCacheEnumData *enumdata, Oid arg);
+ static int	enum_oid_cmp(const void *left, const void *right);
  
  
  /*
*************** TypeCacheRelCallback(Datum arg, Oid reli
*** 551,553 ****
--- 574,868 ----
  		}
  	}
  }
+ 
+ 
+ /*
+  * compare_values_of_enum
+  *		Compare two members of an enum type.
+  *		Return <0, 0, or >0 according as arg1 <, =, or > arg2.
+  *
+  * Note: currently, the enumData cache is refreshed only if we are asked
+  * to compare an enum value that is not already in the cache.  This is okay
+  * because there is no support for re-ordering existing values, so comparisons
+  * of previously cached values will return the right answer even if other
+  * values have been added since we last loaded the cache.
+  *
+  * Note: the enum logic has a special-case rule about even-numbered versus
+  * odd-numbered OIDs, but we take no account of that rule here; this
+  * routine shouldn't even get called when that rule applies.
+  */
+ int
+ compare_values_of_enum(TypeCacheEntry *tcache, Oid arg1, Oid arg2)
+ {
+ 	TypeCacheEnumData *enumdata;
+ 	EnumItem   *item1;
+ 	EnumItem   *item2;
+ 
+ 	/*
+ 	 * Equal OIDs are certainly equal --- this case was probably handled
+ 	 * by our caller, but we may as well check.
+ 	 */
+ 	if (arg1 == arg2)
+ 		return 0;
+ 
+ 	/* Load up the cache if first time through */
+ 	if (tcache->enumData == NULL)
+ 		load_enum_cache_data(tcache);
+ 	enumdata = tcache->enumData;
+ 
+ 	/*
+ 	 * If both OIDs are known-sorted, we can just compare them directly.
+ 	 * (Note: this coding assumes that OID is no wider than int, else we
+ 	 * would have to do an explicit range-check.)
+ 	 */
+ 	if (bms_is_member(arg1 - enumdata->bitmap_base, enumdata->sorted_values) &&
+ 		bms_is_member(arg2 - enumdata->bitmap_base, enumdata->sorted_values))
+ 	{
+ 		if (arg1 < arg2)
+ 			return -1;
+ 		else
+ 			return 1;
+ 	}
+ 
+ 	/*
+ 	 * Slow path: we have to identify their actual sort-order positions.
+ 	 */
+ 	item1 = find_enumitem(enumdata, arg1);
+ 	item2 = find_enumitem(enumdata, arg2);
+ 
+ 	if (item1 == NULL || item2 == NULL)
+ 	{
+ 		/*
+ 		 * We couldn't find one or both values.  That means the enum has
+ 		 * changed under us, so re-initialize the cache and try again.
+ 		 * We don't bother retrying the known-sorted case in this path.
+ 		 */
+ 		load_enum_cache_data(tcache);
+ 		enumdata = tcache->enumData;
+ 
+ 		item1 = find_enumitem(enumdata, arg1);
+ 		item2 = find_enumitem(enumdata, arg2);
+ 
+ 		/*
+ 		 * If we still can't find the values, complain: we must have
+ 		 * corrupt data.
+ 		 */
+ 		if (item1 == NULL)
+ 			elog(ERROR, "enum value %u not found in cache for enum %s",
+ 				 arg1, format_type_be(tcache->type_id));
+ 		if (item2 == NULL)
+ 			elog(ERROR, "enum value %u not found in cache for enum %s",
+ 				 arg2, format_type_be(tcache->type_id));
+ 	}
+ 
+ 	if (item1->sort_order < item2->sort_order)
+ 		return -1;
+ 	else if (item1->sort_order > item2->sort_order)
+ 		return 1;
+ 	else
+ 		return 0;
+ }
+ 
+ /*
+  * Load (or re-load) the enumData member of the typcache entry.
+  */
+ static void
+ load_enum_cache_data(TypeCacheEntry *tcache)
+ {
+ 	TypeCacheEnumData *enumdata;
+ 	Relation	enum_rel;
+ 	SysScanDesc enum_scan;
+ 	HeapTuple	enum_tuple;
+ 	ScanKeyData skey;
+ 	EnumItem   *items;
+ 	int			numitems;
+ 	int			maxitems;
+ 	Oid			bitmap_base;
+ 	Bitmapset  *bms;
+ 	MemoryContext oldcxt;
+ 	int			i,
+ 				bm_start,
+ 				bm_len,
+ 				start_pos,
+ 				list_end;
+ 
+ 	/* Check that this is actually an enum */
+ 	if (tcache->typtype != TYPTYPE_ENUM)
+ 		ereport(ERROR,
+ 				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
+ 				 errmsg("%s is not an enum",
+ 						format_type_be(tcache->type_id))));
+ 
+ 	/*
+ 	 * Read all the information for members of the enum type.  We collect
+ 	 * the info in working memory in the caller's context, and then transfer
+ 	 * it to permanent memory in CacheMemoryContext.  This minimizes the risk
+ 	 * of leaking memory from CacheMemoryContext in the event of an error
+ 	 * partway through.
+ 	 */
+ 	maxitems = 64;
+ 	items = (EnumItem *) palloc(sizeof(EnumItem) * maxitems);
+ 	numitems = 0;
+ 
+ 	/*
+ 	 * Scan pg_enum for the members of the target enum type.  We use a
+ 	 * current MVCC snapshot, *not* SnapshotNow, so that we see a consistent
+ 	 * set of rows even if someone commits a renumbering of the enum meanwhile.
+ 	 * See comments in catalog/pg_enum.c for more info.
+ 	 */
+ 	ScanKeyInit(&skey,
+ 				Anum_pg_enum_enumtypid,
+ 				BTEqualStrategyNumber, F_OIDEQ,
+ 				ObjectIdGetDatum(tcache->type_id));
+ 
+ 	enum_rel = heap_open(EnumRelationId, AccessShareLock);
+ 	enum_scan = systable_beginscan(enum_rel,
+ 								   EnumTypIdLabelIndexId,
+ 								   true, GetTransactionSnapshot(),
+ 								   1, &skey);
+ 
+ 	while (HeapTupleIsValid(enum_tuple = systable_getnext(enum_scan)))
+ 	{
+ 		Form_pg_enum en = (Form_pg_enum) GETSTRUCT(enum_tuple);
+ 
+ 		if (numitems >= maxitems)
+ 		{
+ 			maxitems *= 2;
+ 			items = (EnumItem *) repalloc(items, sizeof(EnumItem) * maxitems);
+ 		}
+ 		items[numitems].enum_oid = HeapTupleGetOid(enum_tuple);
+ 		items[numitems].sort_order = en->enumsortorder;
+ 		numitems++;
+ 	}
+ 
+ 	systable_endscan(enum_scan);
+ 	heap_close(enum_rel, AccessShareLock);
+ 
+ 	/* Sort the items into OID order */
+ 	qsort(items, numitems, sizeof(EnumItem), enum_oid_cmp);
+ 
+ 	/*
+ 	 * Here, we create a bitmap listing a subset of the enum's OIDs that are
+ 	 * known to be in order and can thus be compared with just OID comparison.
+ 	 *
+ 	 * The point of this is that the enum's initial OIDs were certainly in
+ 	 * order, so there is some subset that can be compared via OID comparison;
+ 	 * and we'd rather not do binary searches unnecessarily.
+ 	 */
+ 
+ 	/* Look for the longest suitable range for the bitmap */
+ 	bm_len = 0;
+ 	bm_start = 0;
+ 
+ 	for (start_pos = 0; start_pos < numitems - 1; start_pos++)
+ 	{
+ 		/*
+ 		 * Identify longest sorted subsequence starting at start_pos
+ 		 */
+ 		Oid		start_oid = items[start_pos].enum_oid;
+ 
+ 		for (list_end = start_pos + 1; list_end < numitems; list_end++)
+ 		{
+ 			/* quit if list_end item is out-of-order */
+ 			if (items[list_end].sort_order <= items[list_end - 1].sort_order)
+ 				break;
+ 			/* quit if bitmap would be too large; cutoff is arbitrary */
+ 			if ((items[list_end].enum_oid - start_oid) >= 1024)
+ 				break;
+ 		}
+ 
+ 		/* Remember it if larger than previous best */
+ 		if ((list_end - start_pos) > bm_len)
+ 		{
+ 			bm_len = list_end - start_pos;
+ 			bm_start = start_pos;
+ 
+ 			/*
+ 			 * If the sequence we've just found is bigger than half the list,
+ 			 *  we won't find one bigger
+ 			 */
+ 			if (bm_len > numitems / 2)
+ 				break;
+ 		}
+ 
+ 		/*
+ 		 * If we stopped at an out-of-order item, there's no point in starting
+ 		 * another scan before that item.
+ 		 */
+ 		if (list_end < numitems &&
+ 			items[list_end].sort_order <= items[list_end - 1].sort_order)
+ 			start_pos = list_end - 1;
+ 	}
+ 
+ 	/* If we found a suitable range for the bitmap, set it up */
+ 	if (bm_len > 1)
+ 	{
+ 		bitmap_base = items[bm_start].enum_oid;
+ 		bms = NULL;
+ 		for (i = 0; i < bm_len; i++)
+ 		{
+ 			Oid		en_oid = items[bm_start + i].enum_oid;
+ 
+ 			bms = bms_add_member(bms, (int) (en_oid - bitmap_base));
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/* This should be an unusual corner case */
+ 		bitmap_base = InvalidOid;
+ 		bms = NULL;
+ 	}
+ 
+ 	/* OK, copy the data into CacheMemoryContext */
+ 	oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
+ 	enumdata = (TypeCacheEnumData *)
+ 		palloc(offsetof(TypeCacheEnumData, enum_values) +
+ 			   numitems * sizeof(EnumItem));
+ 	enumdata->bitmap_base = bitmap_base;
+ 	enumdata->sorted_values = bms_copy(bms);
+ 	enumdata->num_values = numitems;
+ 	memcpy(enumdata->enum_values, items, numitems * sizeof(EnumItem));
+ 	MemoryContextSwitchTo(oldcxt);
+ 
+ 	pfree(items);
+ 	bms_free(bms);
+ 
+ 	/* And link the finished cache struct into the typcache */
+ 	if (tcache->enumData != NULL)
+ 		pfree(tcache->enumData);
+ 	tcache->enumData = enumdata;
+ }
+ 
+ /*
+  * Locate the EnumItem with the given OID, if present
+  */
+ static EnumItem *
+ find_enumitem(TypeCacheEnumData *enumdata, Oid arg)
+ {
+ 	EnumItem	srch;
+ 
+ 	/* On some versions of Solaris, bsearch of zero items dumps core */
+ 	if (enumdata->num_values <= 0)
+ 		return NULL;
+ 
+ 	srch.enum_oid = arg;
+ 	return bsearch(&srch, enumdata->enum_values, enumdata->num_values,
+ 				   sizeof(EnumItem), enum_oid_cmp);
+ }
+ 
+ /*
+  * qsort comparison function for OID-ordered EnumItems
+  */
+ static int
+ enum_oid_cmp(const void *left, const void *right)
+ {
+ 	const EnumItem *l = (const EnumItem *) left;
+ 	const EnumItem *r = (const EnumItem *) right;
+ 
+ 	if (l->enum_oid < r->enum_oid)
+ 		return -1;
+ 	else if (l->enum_oid > r->enum_oid)
+ 		return 1;
+ 	else
+ 		return 0;
+ }
diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index 6a4557b48610f51247209b80ea5b8962f1fea048..55ea6841a443ca0558e526a895cfbf2f484d76ba 100644
*** a/src/bin/pg_dump/pg_dump.c
--- b/src/bin/pg_dump/pg_dump.c
*************** dumpEnumType(Archive *fout, TypeInfo *ty
*** 6657,6670 ****
  	Oid			enum_oid;
  	char	   *label;
  
! 	/* Set proper schema search path so regproc references list correctly */
! 	selectSourceSchema(tyinfo->dobj.namespace->dobj.name);
  
! 	appendPQExpBuffer(query, "SELECT oid, enumlabel "
! 					  "FROM pg_catalog.pg_enum "
! 					  "WHERE enumtypid = '%u'"
! 					  "ORDER BY oid",
! 					  tyinfo->dobj.catId.oid);
  
  	res = PQexec(g_conn, query->data);
  	check_sql_result(res, g_conn, query->data, PGRES_TUPLES_OK);
--- 6657,6677 ----
  	Oid			enum_oid;
  	char	   *label;
  
! 	/* Set proper schema search path */
! 	selectSourceSchema("pg_catalog");
  
! 	if (fout->remoteVersion >= 90100)
! 		appendPQExpBuffer(query, "SELECT oid, enumlabel "
! 						  "FROM pg_catalog.pg_enum "
! 						  "WHERE enumtypid = '%u'"
! 						  "ORDER BY enumsortorder",
! 						  tyinfo->dobj.catId.oid);
! 	else
! 		appendPQExpBuffer(query, "SELECT oid, enumlabel "
! 						  "FROM pg_catalog.pg_enum "
! 						  "WHERE enumtypid = '%u'"
! 						  "ORDER BY oid",
! 						  tyinfo->dobj.catId.oid);
  
  	res = PQexec(g_conn, query->data);
  	check_sql_result(res, g_conn, query->data, PGRES_TUPLES_OK);
*************** dumpEnumType(Archive *fout, TypeInfo *ty
*** 6713,6725 ****
  			if (i == 0)
  				appendPQExpBuffer(q, "\n-- For binary upgrade, must preserve pg_enum oids\n");
  			appendPQExpBuffer(q,
! 			 "SELECT binary_upgrade.add_pg_enum_label('%u'::pg_catalog.oid, "
! 							  "'%u'::pg_catalog.oid, ",
! 							  enum_oid, tyinfo->dobj.catId.oid);
  			appendStringLiteralAH(q, label, fout);
! 			appendPQExpBuffer(q, ");\n");
  		}
- 		appendPQExpBuffer(q, "\n");
  	}
  
  	ArchiveEntry(fout, tyinfo->dobj.catId, tyinfo->dobj.dumpId,
--- 6720,6734 ----
  			if (i == 0)
  				appendPQExpBuffer(q, "\n-- For binary upgrade, must preserve pg_enum oids\n");
  			appendPQExpBuffer(q,
! 							  "SELECT binary_upgrade.set_next_pg_enum_oid('%u'::pg_catalog.oid);\n",
! 							  enum_oid);
! 			appendPQExpBuffer(q, "ALTER TYPE %s.",
! 							  fmtId(tyinfo->dobj.namespace->dobj.name));
! 			appendPQExpBuffer(q, "%s ADD ",
! 							  fmtId(tyinfo->dobj.name));
  			appendStringLiteralAH(q, label, fout);
! 			appendPQExpBuffer(q, ";\n\n");
  		}
  	}
  
  	ArchiveEntry(fout, tyinfo->dobj.catId, tyinfo->dobj.dumpId,
diff --git a/src/bin/psql/describe.c b/src/bin/psql/describe.c
index 57d74e14d75e3556389cff966ab7fc360b97fdbd..b705cb29dd419b207a365ae61801f8a6512da253 100644
*** a/src/bin/psql/describe.c
--- b/src/bin/psql/describe.c
*************** describeTypes(const char *pattern, bool 
*** 473,489 ****
  						  gettext_noop("Internal name"),
  						  gettext_noop("Size"));
  	if (verbose && pset.sversion >= 80300)
  		appendPQExpBuffer(&buf,
  						  "  pg_catalog.array_to_string(\n"
  						  "      ARRAY(\n"
  						  "		     SELECT e.enumlabel\n"
  						  "          FROM pg_catalog.pg_enum e\n"
! 						  "          WHERE e.enumtypid = t.oid\n"
! 						  "          ORDER BY e.oid\n"
  						  "      ),\n"
  						  "      E'\\n'\n"
  						  "  ) AS \"%s\",\n",
  						  gettext_noop("Elements"));
  
  	appendPQExpBuffer(&buf,
  				"  pg_catalog.obj_description(t.oid, 'pg_type') as \"%s\"\n",
--- 473,499 ----
  						  gettext_noop("Internal name"),
  						  gettext_noop("Size"));
  	if (verbose && pset.sversion >= 80300)
+ 	{
  		appendPQExpBuffer(&buf,
  						  "  pg_catalog.array_to_string(\n"
  						  "      ARRAY(\n"
  						  "		     SELECT e.enumlabel\n"
  						  "          FROM pg_catalog.pg_enum e\n"
! 						  "          WHERE e.enumtypid = t.oid\n");
! 
! 		if (pset.sversion >= 90100)
! 			appendPQExpBuffer(&buf,
! 							  "          ORDER BY e.enumsortorder\n");
! 		else
! 			appendPQExpBuffer(&buf,
! 							  "          ORDER BY e.oid\n");
! 
! 		appendPQExpBuffer(&buf,
  						  "      ),\n"
  						  "      E'\\n'\n"
  						  "  ) AS \"%s\",\n",
  						  gettext_noop("Elements"));
+ 	}
  
  	appendPQExpBuffer(&buf,
  				"  pg_catalog.obj_description(t.oid, 'pg_type') as \"%s\"\n",
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index e30a7d7298b489286c2e8cccea45a32de8ceb556..b858d3ee009626cea6258d5da775b307e0e0b995 100644
*** a/src/include/catalog/catversion.h
--- b/src/include/catalog/catversion.h
***************
*** 53,58 ****
   */
  
  /*							yyyymmddN */
! #define CATALOG_VERSION_NO	201010201
  
  #endif
--- 53,58 ----
   */
  
  /*							yyyymmddN */
! #define CATALOG_VERSION_NO	201010241
  
  #endif
diff --git a/src/include/catalog/indexing.h b/src/include/catalog/indexing.h
index b7c9849314eb1dc2f468ea0a3c22fe2e63de2b67..a3839e1e2597e3d5ccfd848c69265eb9057080e7 100644
*** a/src/include/catalog/indexing.h
--- b/src/include/catalog/indexing.h
*************** DECLARE_UNIQUE_INDEX(pg_enum_oid_index, 
*** 147,152 ****
--- 147,154 ----
  #define EnumOidIndexId	3502
  DECLARE_UNIQUE_INDEX(pg_enum_typid_label_index, 3503, on pg_enum using btree(enumtypid oid_ops, enumlabel name_ops));
  #define EnumTypIdLabelIndexId 3503
+ DECLARE_UNIQUE_INDEX(pg_enum_typid_sortorder_index, 3534, on pg_enum using btree(enumtypid oid_ops, enumsortorder float4_ops));
+ #define EnumTypIdSortOrderIndexId 3534
  
  /* This following index is not used for a cache and is not unique */
  DECLARE_INDEX(pg_index_indrelid_index, 2678, on pg_index using btree(indrelid oid_ops));
diff --git a/src/include/catalog/pg_enum.h b/src/include/catalog/pg_enum.h
index 28da42bf54e417047c08b0a94c82e1baad61e37e..cc69eb531c6e558c87b41794543598452b0ec390 100644
*** a/src/include/catalog/pg_enum.h
--- b/src/include/catalog/pg_enum.h
***************
*** 34,39 ****
--- 34,40 ----
  CATALOG(pg_enum,3501)
  {
  	Oid			enumtypid;		/* OID of owning enum type */
+ 	float4		enumsortorder;	/* sort position of this enum value */
  	NameData	enumlabel;		/* text representation of enum value */
  } FormData_pg_enum;
  
*************** typedef FormData_pg_enum *Form_pg_enum;
*** 48,56 ****
   *		compiler constants for pg_enum
   * ----------------
   */
! #define Natts_pg_enum					2
  #define Anum_pg_enum_enumtypid			1
! #define Anum_pg_enum_enumlabel			2
  
  /* ----------------
   *		pg_enum has no initial contents
--- 49,58 ----
   *		compiler constants for pg_enum
   * ----------------
   */
! #define Natts_pg_enum					3
  #define Anum_pg_enum_enumtypid			1
! #define Anum_pg_enum_enumsortorder		2
! #define Anum_pg_enum_enumlabel			3
  
  /* ----------------
   *		pg_enum has no initial contents
*************** typedef FormData_pg_enum *Form_pg_enum;
*** 60,67 ****
  /*
   * prototypes for functions in pg_enum.c
   */
! extern void EnumValuesCreate(Oid enumTypeOid, List *vals,
! 				 Oid binary_upgrade_next_pg_enum_oid);
  extern void EnumValuesDelete(Oid enumTypeOid);
  
  #endif   /* PG_ENUM_H */
--- 62,70 ----
  /*
   * prototypes for functions in pg_enum.c
   */
! extern void EnumValuesCreate(Oid enumTypeOid, List *vals);
  extern void EnumValuesDelete(Oid enumTypeOid);
+ extern void AddEnumLabel(Oid enumTypeOid, const char *newVal,
+ 						 const char *neighbor, bool newValIsAfter);
  
  #endif   /* PG_ENUM_H */
diff --git a/src/include/commands/typecmds.h b/src/include/commands/typecmds.h
index 2bff7e1c2b138481d33aebfd2f03504815f7d02a..4c6e7e164e0a3da23333014e0f9bac9ca5c170df 100644
*** a/src/include/commands/typecmds.h
--- b/src/include/commands/typecmds.h
*************** extern void RemoveTypes(DropStmt *drop);
*** 24,29 ****
--- 24,30 ----
  extern void RemoveTypeById(Oid typeOid);
  extern void DefineDomain(CreateDomainStmt *stmt);
  extern void DefineEnum(CreateEnumStmt *stmt);
+ extern void AlterEnum(AlterEnumStmt *stmt);
  extern Oid	DefineCompositeType(const RangeVar *typevar, List *coldeflist);
  extern Oid	AssignTypeArrayOid(void);
  
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 15dabe31ce39750f35e77ebcaf274ff40df313a0..8e94d9803f702875cd47b85b48b1ebe29ac257b9 100644
*** a/src/include/nodes/nodes.h
--- b/src/include/nodes/nodes.h
*************** typedef enum NodeTag
*** 338,343 ****
--- 338,344 ----
  	T_ReassignOwnedStmt,
  	T_CompositeTypeStmt,
  	T_CreateEnumStmt,
+ 	T_AlterEnumStmt,
  	T_AlterTSDictionaryStmt,
  	T_AlterTSConfigurationStmt,
  	T_CreateFdwStmt,
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index e0bdebd0abe378727fcfb858bae31c503a8df6d0..3cac54b94708e574fc7f53bba4317be8d00b4855 100644
*** a/src/include/nodes/parsenodes.h
--- b/src/include/nodes/parsenodes.h
*************** typedef struct CreateEnumStmt
*** 2193,2198 ****
--- 2193,2210 ----
  	List	   *vals;			/* enum values (list of Value strings) */
  } CreateEnumStmt;
  
+ /* ----------------------
+  *		Alter Type Statement, enum types
+  * ----------------------
+  */
+ typedef struct AlterEnumStmt
+ {
+ 	NodeTag		type;
+ 	List	   *typeName;		/* qualified name (list of Value strings) */
+ 	char	   *newVal;			/* new enum value's name */
+ 	char	   *newValNeighbor;	/* neighboring enum value, if specified */
+ 	bool	    newValIsAfter;	/* place new enum value after neighbor? */
+ } AlterEnumStmt;
  
  /* ----------------------
   *		Create View Statement
diff --git a/src/include/utils/typcache.h b/src/include/utils/typcache.h
index 4065e483e4be6cdfbce1839df2f6ffe19a81aa0c..28b66718b338c9a75276a027b25dc78f7b9fee50 100644
*** a/src/include/utils/typcache.h
--- b/src/include/utils/typcache.h
***************
*** 20,25 ****
--- 20,28 ----
  #include "fmgr.h"
  
  
+ /* TypeCacheEnumData is an opaque struct known only within typcache.c */
+ struct TypeCacheEnumData;
+ 
  typedef struct TypeCacheEntry
  {
  	/* typeId is the hash lookup key and MUST BE FIRST */
*************** typedef struct TypeCacheEntry
*** 63,68 ****
--- 66,77 ----
  	 * reference-counted tupledesc.)
  	 */
  	TupleDesc	tupDesc;
+ 
+ 	/*
+ 	 * Private information about an enum type.  NULL if not enum or
+ 	 * information hasn't been requested.
+ 	 */
+ 	struct TypeCacheEnumData *enumData;
  } TypeCacheEntry;
  
  /* Bit flags to indicate which fields a given caller needs to have set */
*************** extern TupleDesc lookup_rowtype_tupdesc_
*** 86,89 ****
--- 95,100 ----
  
  extern void assign_record_type_typmod(TupleDesc tupDesc);
  
+ extern int	compare_values_of_enum(TypeCacheEntry *tcache, Oid arg1, Oid arg2);
+ 
  #endif   /* TYPCACHE_H */
diff --git a/src/test/regress/expected/enum.out b/src/test/regress/expected/enum.out
index 56240c0e7a2966a9dccd2cd9692bc628c52237ab..23389f41485961ba314022368919fa3687583fe2 100644
*** a/src/test/regress/expected/enum.out
--- b/src/test/regress/expected/enum.out
*************** ERROR:  invalid input value for enum rai
*** 25,30 ****
--- 25,91 ----
  LINE 1: SELECT 'mauve'::rainbow;
                 ^
  --
+ -- adding new values
+ --
+ CREATE TYPE planets AS ENUM ( 'venus', 'earth', 'mars' );
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+  enumlabel | enumsortorder 
+ -----------+---------------
+  venus     |             1
+  earth     |             2
+  mars      |             3
+ (3 rows)
+ 
+ ALTER TYPE planets ADD 'uranus';
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+  enumlabel | enumsortorder 
+ -----------+---------------
+  venus     |             1
+  earth     |             2
+  mars      |             3
+  uranus    |             4
+ (4 rows)
+ 
+ ALTER TYPE planets ADD 'mercury' BEFORE 'venus';
+ ALTER TYPE planets ADD 'saturn' BEFORE 'uranus';
+ ALTER TYPE planets ADD 'jupiter' AFTER 'mars';
+ ALTER TYPE planets ADD 'neptune' AFTER 'uranus';
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+  enumlabel | enumsortorder 
+ -----------+---------------
+  mercury   |             0
+  venus     |             1
+  earth     |             2
+  mars      |             3
+  jupiter   |          3.25
+  saturn    |           3.5
+  uranus    |             4
+  neptune   |             5
+ (8 rows)
+ 
+ select 'mars'::planets > 'mercury' as using_sortorder;
+  using_sortorder 
+ -----------------
+  t
+ (1 row)
+ 
+ -- errors for adding labels
+ ALTER TYPE planets ADD
+   'plutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutopluto';
+ ERROR:  invalid enum label "plutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutopluto"
+ DETAIL:  Labels must be 63 characters or less.
+ ALTER TYPE planets ADD 'pluto' AFTER 'zeus';
+ ERROR:  "zeus" is not an existing enum label
+ --
  -- Basic table creation, row selection
  --
  CREATE TABLE enumtest (col rainbow);
*************** SELECT COUNT(*) FROM pg_type WHERE typna
*** 403,409 ****
  
  SELECT * FROM pg_enum WHERE NOT EXISTS
    (SELECT 1 FROM pg_type WHERE pg_type.oid = enumtypid);
!  enumtypid | enumlabel 
! -----------+-----------
  (0 rows)
  
--- 464,470 ----
  
  SELECT * FROM pg_enum WHERE NOT EXISTS
    (SELECT 1 FROM pg_type WHERE pg_type.oid = enumtypid);
!  enumtypid | enumsortorder | enumlabel 
! -----------+---------------+-----------
  (0 rows)
  
diff --git a/src/test/regress/sql/enum.sql b/src/test/regress/sql/enum.sql
index 387e8e72ed8f8e9af85bd7430f9fbfde369a0e3e..53191125be263c06cb91a6bd3184b0549ca9ea83 100644
*** a/src/test/regress/sql/enum.sql
--- b/src/test/regress/sql/enum.sql
*************** SELECT 'red'::rainbow;
*** 16,21 ****
--- 16,57 ----
  SELECT 'mauve'::rainbow;
  
  --
+ -- adding new values
+ --
+ 
+ CREATE TYPE planets AS ENUM ( 'venus', 'earth', 'mars' );
+ 
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+ 
+ ALTER TYPE planets ADD 'uranus';
+ 
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+ 
+ ALTER TYPE planets ADD 'mercury' BEFORE 'venus';
+ ALTER TYPE planets ADD 'saturn' BEFORE 'uranus';
+ ALTER TYPE planets ADD 'jupiter' AFTER 'mars';
+ ALTER TYPE planets ADD 'neptune' AFTER 'uranus';
+ 
+ SELECT enumlabel, enumsortorder
+ FROM pg_enum
+ WHERE enumtypid = 'planets'::regtype
+ ORDER BY 2;
+ 
+ select 'mars'::planets > 'mercury' as using_sortorder;
+ 
+ -- errors for adding labels
+ ALTER TYPE planets ADD
+   'plutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutoplutopluto';
+ 
+ ALTER TYPE planets ADD 'pluto' AFTER 'zeus';
+ 
+ --
  -- Basic table creation, row selection
  --
  CREATE TABLE enumtest (col rainbow);
