sort-support.patch

diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml
index 2832436..5f67624 100644
--- a/doc/src/sgml/xindex.sgml
+++ b/doc/src/sgml/xindex.sgml
@@ -758,7 +758,8 @@ DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
   OPERATOR 3 = ,
   OPERATOR 4 >= ,
   OPERATOR 5 > ,
-  FUNCTION 1 btint4cmp(int4, int4) ;
+  FUNCTION 1 btint4cmp(int4, int4),
+  FUNCTION 2 btint4sortsupport(int4, int4) ;
 
 CREATE OPERATOR CLASS int2_ops
 DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 23f2b61..f95bc9f 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -49,6 +49,7 @@
 #include "postgres.h"
 
 #include "utils/builtins.h"
+#include "utils/sortsupport.h"
 
 
 Datum
@@ -83,6 +84,28 @@ btint4cmp(PG_FUNCTION_ARGS)
 		PG_RETURN_INT32(-1);
 }
 
+static int
+btint4acmp(Datum a, Datum b, SortSupportInfo ss)
+{
+	int32		a1 = Int32GetDatum(a);
+	int32		b1 = Int32GetDatum(b);
+
+	if (a1 > b1)
+		return 1;
+	else if (a1 == b1)
+		return 0;
+	else
+		return -1;
+}
+
+Datum
+btint4sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupportInfo	ss = (SortSupportInfo) PG_GETARG_POINTER(0);
+	ss->extra = btint4acmp;
+	PG_RETURN_VOID();
+}
+
 Datum
 btint8cmp(PG_FUNCTION_ARGS)
 {
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 347d942..b17855e 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -417,13 +417,17 @@ typedef struct xl_btree_newroot
 
 /*
  *	When a new operator class is declared, we require that the user
- *	supply us with an amproc procedure for determining whether, for
- *	two keys a and b, a < b, a = b, or a > b.  This routine must
- *	return < 0, 0, > 0, respectively, in these three cases.  Since we
- *	only have one such proc in amproc, it's number 1.
+ *	supply us with an amproc procedure (BTORDER_PROC) for determining
+ *  whether, for two keys a and b, a < b, a = b, or a > b.  This routine
+ *  must return < 0, 0, > 0, respectively, in these three cases.
+ *
+ *  To facilitate accelerated sorting, an operator class may choose to
+ *  offer a second procedure (BTSORTSUPPORT_PROC).  For full details, see
+ *  src/include/utils/sortsupport.h
  */
 
-#define BTORDER_PROC	1
+#define BTORDER_PROC			1
+#define BTSORTSUPPORT_PROC		2
 
 /*
  *	We need to be able to tell the difference between read and write
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index 8b075d3..ddacdf2 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -117,7 +117,7 @@ typedef FormData_pg_am *Form_pg_am;
  * ----------------
  */
 
-DATA(insert OID = 403 (  btree	5 1 t f t t t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete btvacuumcleanup btcostestimate btoptions ));
+DATA(insert OID = 403 (  btree	5 2 t f t t t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete btvacuumcleanup btcostestimate btoptions ));
 DESCR("b-tree index access method");
 #define BTREE_AM_OID 403
 DATA(insert OID = 405 (  hash	1 1 f f t f f f f f f f f f 23 hashinsert hashbeginscan hashgettuple hashgetbitmap hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbuildempty hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions ));
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index e5d43f7..373191a 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -100,6 +100,7 @@ DATA(insert (	1976   21 21 1 350 ));
 DATA(insert (	1976   21 23 1 2190 ));
 DATA(insert (	1976   21 20 1 2192 ));
 DATA(insert (	1976   23 23 1 351 ));
+DATA(insert (	1976   23 23 2 324 ));
 DATA(insert (	1976   23 20 1 2188 ));
 DATA(insert (	1976   23 21 1 2191 ));
 DATA(insert (	1976   20 20 1 842 ));
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 28e53b7..e062b80 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -568,6 +568,8 @@ DATA(insert OID = 350 (  btint2cmp		   PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 23
 DESCR("less-equal-greater");
 DATA(insert OID = 351 (  btint4cmp		   PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 23 "23 23" _null_ _null_ _null_ _null_ btint4cmp _null_ _null_ _null_ ));
 DESCR("less-equal-greater");
+DATA(insert OID = 324 (  btint4sortsupport PGNSP PGUID 12 1 0 0 0 f f f t f i 1 0 2278 "2281" _null_ _null_ _null_ _null_ btint4sortsupport _null_ _null_ _null_ ));
+DESCR("sort support");
 DATA(insert OID = 842 (  btint8cmp		   PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 23 "20 20" _null_ _null_ _null_ _null_ btint8cmp _null_ _null_ _null_ ));
 DESCR("less-equal-greater");
 DATA(insert OID = 354 (  btfloat4cmp	   PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 23 "700 700" _null_ _null_ _null_ _null_ btfloat4cmp _null_ _null_ _null_ ));
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 47a1412..565e455 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -304,6 +304,13 @@ extern Datum btcharcmp(PG_FUNCTION_ARGS);
 extern Datum btnamecmp(PG_FUNCTION_ARGS);
 extern Datum bttextcmp(PG_FUNCTION_ARGS);
 
+/*
+ *		Per-opclass sort support functions for new btrees.  Like the
+ *		functions above, these are stored in pg_amproc and defined in
+ *		access/nbtree/nbtcompare.c
+ */
+extern Datum btint4sortsupport(PG_FUNCTION_ARGS);
+
 /* float.c */
 extern PGDLLIMPORT int extra_float_digits;
 
diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h
new file mode 100644
index 0000000..a925ce1
--- /dev/null
+++ b/src/include/utils/sortsupport.h
@@ -0,0 +1,43 @@
+/*-------------------------------------------------------------------------
+ *
+ * sortsupport.h
+ *	  Framework for accelerated sorting.
+ *
+ * Sorting can be performed by repeatedly invoking an SQL-callable
+ * comparison function on the value to be compared; this module provides
+ * a way to avoid some of the function call overhead inherent in that
+ * interface.  A btree opclass may choose to offer a BTSORTSUPPORT_PROC,
+ * taking a single argument of type internal and returning void.
+ *
+ * This function will be called during sort setup and should initialize
+ * the extra and comparator functions of the SortSupportInfo structure
+ * that will be passed as an argument, using info_cxt for any required
+ * memory allocations.  The relevant collation OID will be initialized
+ * prior to invoking this function.
+ *
+ * After initialization, the comparator function will be called directly
+ * for each comparison, eliminating the overhead of the FunctionCallInfo
+ * interface.
+ *
+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/sortsupport.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef SORTSUPPORT_H
+#define SORTSUPPORT_H
+
+typedef struct SortSupportInfoData *SortSupportInfo;
+
+typedef struct SortSupportInfoData
+{
+	MemoryContext	info_cxt;
+	void		   *extra;
+	Oid				collation;
+
+	int	(*comparator)(Datum a, Datum b, SortSupportInfo info);
+} SortSupportInfoData;
+
+#endif   /* SORTSUPPORT_H */
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index b915134..1c8a634 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -1186,40 +1186,28 @@ WHERE p1.amprocfamily = p3.oid AND p3.opfmethod = p2.oid AND
 
 -- Detect missing pg_amproc entries: should have as many support functions
 -- as AM expects for each datatype combination supported by the opfamily.
--- GiST/GIN are special cases because each has an optional support function.
+-- btree/GiST/GIN each allow an optional support function
 SELECT p1.amname, p2.opfname, p3.amproclefttype, p3.amprocrighttype
 FROM pg_am AS p1, pg_opfamily AS p2, pg_amproc AS p3
 WHERE p2.opfmethod = p1.oid AND p3.amprocfamily = p2.oid AND
-    p1.amname <> 'gist' AND p1.amname <> 'gin' AND
-    p1.amsupport != (SELECT count(*) FROM pg_amproc AS p4
-                     WHERE p4.amprocfamily = p2.oid AND
-                           p4.amproclefttype = p3.amproclefttype AND
-                           p4.amprocrighttype = p3.amprocrighttype);
- amname | opfname | amproclefttype | amprocrighttype 
---------+---------+----------------+-----------------
-(0 rows)
-
--- Similar check for GiST/GIN, allowing one optional proc
-SELECT p1.amname, p2.opfname, p3.amproclefttype, p3.amprocrighttype
-FROM pg_am AS p1, pg_opfamily AS p2, pg_amproc AS p3
-WHERE p2.opfmethod = p1.oid AND p3.amprocfamily = p2.oid AND
-    (p1.amname = 'gist' OR p1.amname = 'gin') AND
-    (SELECT count(*) FROM pg_amproc AS p4
-     WHERE p4.amprocfamily = p2.oid AND
-           p4.amproclefttype = p3.amproclefttype AND
-           p4.amprocrighttype = p3.amprocrighttype)
-      NOT IN (p1.amsupport, p1.amsupport - 1);
+    p1.amsupport - (SELECT count(*) FROM pg_amproc AS p4
+		WHERE p4.amprocfamily = p2.oid AND
+              p4.amproclefttype = p3.amproclefttype AND
+              p4.amprocrighttype = p3.amprocrighttype)
+	NOT BETWEEN 0 AND
+		CASE WHEN p1.amname IN ('gin', 'gist', 'btree') THEN 1 ELSE 0 END;
  amname | opfname | amproclefttype | amprocrighttype 
 --------+---------+----------------+-----------------
 (0 rows)
 
 -- Also, check if there are any pg_opclass entries that don't seem to have
--- pg_amproc support.  Again, GiST/GIN have to be checked specially.
+-- pg_amproc support.  Again, opclasses with an optional support proc have to be
+-- checked specially.
 SELECT amname, opcname, count(*)
 FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
      LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
          amproclefttype = amprocrighttype AND amproclefttype = opcintype
-WHERE am.amname <> 'gist' AND am.amname <> 'gin'
+WHERE am.amname <> 'gist' AND am.amname <> 'gin' AND am.amname <> 'btree'
 GROUP BY amname, amsupport, opcname, amprocfamily
 HAVING count(*) != amsupport OR amprocfamily IS NULL;
  amname | opcname | count 
@@ -1230,7 +1218,7 @@ SELECT amname, opcname, count(*)
 FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
      LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
          amproclefttype = amprocrighttype AND amproclefttype = opcintype
-WHERE am.amname = 'gist' OR am.amname = 'gin'
+WHERE am.amname = 'gist' OR am.amname = 'gin' OR am.amname = 'btree'
 GROUP BY amname, amsupport, opcname, amprocfamily
 HAVING (count(*) != amsupport AND count(*) != amsupport - 1)
     OR amprocfamily IS NULL;
@@ -1261,19 +1249,20 @@ WHERE p1.amprocfamily = p3.oid AND p4.amprocfamily = p6.oid AND
 (0 rows)
 
 -- For btree, though, we can do better since we know the support routines
--- must be of the form cmp(lefttype, righttype) returns int4.
+-- must be of the form cmp(lefttype, righttype) returns int4 or sortsupport(internal).
 SELECT p1.amprocfamily, p1.amprocnum,
 	p2.oid, p2.proname,
 	p3.opfname
 FROM pg_amproc AS p1, pg_proc AS p2, pg_opfamily AS p3
 WHERE p3.opfmethod = (SELECT oid FROM pg_am WHERE amname = 'btree')
     AND p1.amprocfamily = p3.oid AND p1.amproc = p2.oid AND
-    (amprocnum != 1
-     OR proretset
-     OR prorettype != 'int4'::regtype
-     OR pronargs != 2
-     OR proargtypes[0] != amproclefttype
-     OR proargtypes[1] != amprocrighttype);
+    (CASE WHEN amprocnum = 1
+          THEN prorettype != 'int4'::regtype OR pronargs != 2
+               OR proargtypes[0] != amproclefttype
+               OR proargtypes[1] != amprocrighttype
+          WHEN amprocnum = 2
+          THEN prorettype != 'void'::regtype OR pronargs != 1
+               OR proargtypes[0] != 'internal'::regtype END);
  amprocfamily | amprocnum | oid | proname | opfname 
 --------------+-----------+-----+---------+---------
 (0 rows)
diff --git a/src/test/regress/sql/opr_sanity.sql b/src/test/regress/sql/opr_sanity.sql
index b0d1430..1146008 100644
--- a/src/test/regress/sql/opr_sanity.sql
+++ b/src/test/regress/sql/opr_sanity.sql
@@ -926,37 +926,27 @@ WHERE p1.amprocfamily = p3.oid AND p3.opfmethod = p2.oid AND
 
 -- Detect missing pg_amproc entries: should have as many support functions
 -- as AM expects for each datatype combination supported by the opfamily.
--- GiST/GIN are special cases because each has an optional support function.
+-- btree/GiST/GIN each allow an optional support function
 
 SELECT p1.amname, p2.opfname, p3.amproclefttype, p3.amprocrighttype
 FROM pg_am AS p1, pg_opfamily AS p2, pg_amproc AS p3
 WHERE p2.opfmethod = p1.oid AND p3.amprocfamily = p2.oid AND
-    p1.amname <> 'gist' AND p1.amname <> 'gin' AND
-    p1.amsupport != (SELECT count(*) FROM pg_amproc AS p4
-                     WHERE p4.amprocfamily = p2.oid AND
-                           p4.amproclefttype = p3.amproclefttype AND
-                           p4.amprocrighttype = p3.amprocrighttype);
-
--- Similar check for GiST/GIN, allowing one optional proc
-
-SELECT p1.amname, p2.opfname, p3.amproclefttype, p3.amprocrighttype
-FROM pg_am AS p1, pg_opfamily AS p2, pg_amproc AS p3
-WHERE p2.opfmethod = p1.oid AND p3.amprocfamily = p2.oid AND
-    (p1.amname = 'gist' OR p1.amname = 'gin') AND
-    (SELECT count(*) FROM pg_amproc AS p4
-     WHERE p4.amprocfamily = p2.oid AND
-           p4.amproclefttype = p3.amproclefttype AND
-           p4.amprocrighttype = p3.amprocrighttype)
-      NOT IN (p1.amsupport, p1.amsupport - 1);
+    p1.amsupport - (SELECT count(*) FROM pg_amproc AS p4
+		WHERE p4.amprocfamily = p2.oid AND
+              p4.amproclefttype = p3.amproclefttype AND
+              p4.amprocrighttype = p3.amprocrighttype)
+	NOT BETWEEN 0 AND
+		CASE WHEN p1.amname IN ('gin', 'gist', 'btree') THEN 1 ELSE 0 END;
 
 -- Also, check if there are any pg_opclass entries that don't seem to have
--- pg_amproc support.  Again, GiST/GIN have to be checked specially.
+-- pg_amproc support.  Again, opclasses with an optional support proc have to be
+-- checked specially.
 
 SELECT amname, opcname, count(*)
 FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
      LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
          amproclefttype = amprocrighttype AND amproclefttype = opcintype
-WHERE am.amname <> 'gist' AND am.amname <> 'gin'
+WHERE am.amname <> 'gist' AND am.amname <> 'gin' AND am.amname <> 'btree'
 GROUP BY amname, amsupport, opcname, amprocfamily
 HAVING count(*) != amsupport OR amprocfamily IS NULL;
 
@@ -964,7 +954,7 @@ SELECT amname, opcname, count(*)
 FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
      LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
          amproclefttype = amprocrighttype AND amproclefttype = opcintype
-WHERE am.amname = 'gist' OR am.amname = 'gin'
+WHERE am.amname = 'gist' OR am.amname = 'gin' OR am.amname = 'btree'
 GROUP BY amname, amsupport, opcname, amprocfamily
 HAVING (count(*) != amsupport AND count(*) != amsupport - 1)
     OR amprocfamily IS NULL;
@@ -990,7 +980,7 @@ WHERE p1.amprocfamily = p3.oid AND p4.amprocfamily = p6.oid AND
     (p2.proretset OR p5.proretset OR p2.pronargs != p5.pronargs);
 
 -- For btree, though, we can do better since we know the support routines
--- must be of the form cmp(lefttype, righttype) returns int4.
+-- must be of the form cmp(lefttype, righttype) returns int4 or sortsupport(internal).
 
 SELECT p1.amprocfamily, p1.amprocnum,
 	p2.oid, p2.proname,
@@ -998,12 +988,13 @@ SELECT p1.amprocfamily, p1.amprocnum,
 FROM pg_amproc AS p1, pg_proc AS p2, pg_opfamily AS p3
 WHERE p3.opfmethod = (SELECT oid FROM pg_am WHERE amname = 'btree')
     AND p1.amprocfamily = p3.oid AND p1.amproc = p2.oid AND
-    (amprocnum != 1
-     OR proretset
-     OR prorettype != 'int4'::regtype
-     OR pronargs != 2
-     OR proargtypes[0] != amproclefttype
-     OR proargtypes[1] != amprocrighttype);
+    (CASE WHEN amprocnum = 1
+          THEN prorettype != 'int4'::regtype OR pronargs != 2
+               OR proargtypes[0] != amproclefttype
+               OR proargtypes[1] != amprocrighttype
+          WHEN amprocnum = 2
+          THEN prorettype != 'void'::regtype OR pronargs != 1
+               OR proargtypes[0] != 'internal'::regtype END);
 
 -- For hash we can also do a little better: the support routines must be
 -- of the form hash(lefttype) returns int4.  There are several cases where