Add an in-core GiST index opclass for inet/cidr types.

This operator class can accelerate subnet/supernet tests as well as
btree-equivalent ordered comparisons.  It also handles a new network
operator inet && inet (overlaps, a/k/a "is supernet or subnet of"),
which is expected to be useful in exclusion constraints.

Ideally this opclass would be the default for GiST with inet/cidr data,
but we can't mark it that way until we figure out how to do a more or
less graceful transition from the current situation, in which the
really-completely-bogus inet/cidr opclasses in contrib/btree_gist are
marked as default.  Having the opclass in core and not default is better
than not having it at all, though.

While at it, add new documentation sections to allow us to officially
document GiST/GIN/SP-GiST opclasses, something there was never a clear
place to do before.  I filled these in with some simple tables listing
the existing opclasses and the operators they support, but there's
certainly scope to put more information there.

Emre Hasegeli, reviewed by Andreas Karlsson, further hacking by me

9 files changed, 110 insertions, 5 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 4b3357ccd97..fe6144e2d34 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201404081
+#define CATALOG_VERSION_NO	201404082
 
 #endif
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index 26231135570..8efd3be3c66 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -818,4 +818,19 @@ DATA(insert (	3474   3831 3831 8 s	3892 4000 0 ));
 DATA(insert (	3474   3831 2283 16 s	3889 4000 0 ));
 DATA(insert (	3474   3831 3831 18 s	3882 4000 0 ));
 
+/*
+ * GiST inet_ops
+ */
+DATA(insert (	3550	869 869 3 s		3552 783 0 ));
+DATA(insert (	3550	869 869 18 s	1201 783 0 ));
+DATA(insert (	3550	869 869 19 s	1202 783 0 ));
+DATA(insert (	3550	869 869 20 s	1203 783 0 ));
+DATA(insert (	3550	869 869 21 s	1204 783 0 ));
+DATA(insert (	3550	869 869 22 s	1205 783 0 ));
+DATA(insert (	3550	869 869 23 s	1206 783 0 ));
+DATA(insert (	3550	869 869 24 s	931 783 0 ));
+DATA(insert (	3550	869 869 25 s	932 783 0 ));
+DATA(insert (	3550	869 869 26 s	933 783 0 ));
+DATA(insert (	3550	869 869 27 s	934 783 0 ));
+
 #endif   /* PG_AMOP_H */
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index b28dd563a8c..198b126964f 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -399,6 +399,13 @@ DATA(insert (	4037   3802 3802 2 3485 ));
 DATA(insert (	4037   3802 3802 3 3486 ));
 DATA(insert (	4037   3802 3802 4 3487 ));
 DATA(insert (	4037   3802 3802 6 3489 ));
+DATA(insert (	3550   869	869  1 3553 ));
+DATA(insert (	3550   869	869  2 3554 ));
+DATA(insert (	3550   869	869  3 3555 ));
+DATA(insert (	3550   869	869  4 3556 ));
+DATA(insert (	3550   869	869  5 3557 ));
+DATA(insert (	3550   869	869  6 3558 ));
+DATA(insert (	3550   869	869  7 3559 ));
 
 /* sp-gist */
 DATA(insert (	3474   3831 3831 1 3469 ));
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index 63a40a8412c..49b24108de9 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -112,6 +112,7 @@ DATA(insert OID = 3123 ( 403	float8_ops	PGNSP PGUID 1970  701 t 0 ));
 DATA(insert (	405		float8_ops			PGNSP PGUID 1971  701 t 0 ));
 DATA(insert (	403		inet_ops			PGNSP PGUID 1974  869 t 0 ));
 DATA(insert (	405		inet_ops			PGNSP PGUID 1975  869 t 0 ));
+DATA(insert (	783		inet_ops			PGNSP PGUID 3550  869 f 0 ));
 DATA(insert OID = 1979 ( 403	int2_ops	PGNSP PGUID 1976   21 t 0 ));
 #define INT2_BTREE_OPS_OID 1979
 DATA(insert (	405		int2_ops			PGNSP PGUID 1977   21 t 0 ));
diff --git a/src/include/catalog/pg_operator.h b/src/include/catalog/pg_operator.h
index ac09034f3d0..f280af441c2 100644
--- a/src/include/catalog/pg_operator.h
+++ b/src/include/catalog/pg_operator.h
@@ -1140,18 +1140,20 @@ DATA(insert OID = 1205 (  ">"	   PGNSP PGUID b f f 869 869	 16 1203 1204 network
 DESCR("greater than");
 DATA(insert OID = 1206 (  ">="	   PGNSP PGUID b f f 869 869	 16 1204 1203 network_ge scalargtsel scalargtjoinsel ));
 DESCR("greater than or equal");
-DATA(insert OID = 931  (  "<<"	   PGNSP PGUID b f f 869 869	 16 933		0 network_sub - - ));
+DATA(insert OID = 931  (  "<<"	   PGNSP PGUID b f f 869 869	 16 933		0 network_sub networksel networkjoinsel ));
 DESCR("is subnet");
 #define OID_INET_SUB_OP				  931
-DATA(insert OID = 932  (  "<<="    PGNSP PGUID b f f 869 869	 16 934		0 network_subeq - - ));
+DATA(insert OID = 932  (  "<<="    PGNSP PGUID b f f 869 869	 16 934		0 network_subeq networksel networkjoinsel ));
 DESCR("is subnet or equal");
 #define OID_INET_SUBEQ_OP				932
-DATA(insert OID = 933  (  ">>"	   PGNSP PGUID b f f 869 869	 16 931		0 network_sup - - ));
+DATA(insert OID = 933  (  ">>"	   PGNSP PGUID b f f 869 869	 16 931		0 network_sup networksel networkjoinsel ));
 DESCR("is supernet");
 #define OID_INET_SUP_OP				  933
-DATA(insert OID = 934  (  ">>="    PGNSP PGUID b f f 869 869	 16 932		0 network_supeq - - ));
+DATA(insert OID = 934  (  ">>="    PGNSP PGUID b f f 869 869	 16 932		0 network_supeq networksel networkjoinsel ));
 DESCR("is supernet or equal");
 #define OID_INET_SUPEQ_OP				934
+DATA(insert OID = 3552	(  "&&"    PGNSP PGUID b f f 869 869	 16 3552	0 network_overlap networksel networkjoinsel ));
+DESCR("overlaps (is subnet or supernet)");
 
 DATA(insert OID = 2634 (  "~"	   PGNSP PGUID l f f	  0 869 869 0 0 inetnot - - ));
 DESCR("bitwise not");
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index 775be86c1af..9e8f4ac5b63 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -78,6 +78,7 @@ DATA(insert OID = 1971 (	405		float_ops		PGNSP PGUID ));
 DATA(insert OID = 1974 (	403		network_ops		PGNSP PGUID ));
 #define NETWORK_BTREE_FAM_OID 1974
 DATA(insert OID = 1975 (	405		network_ops		PGNSP PGUID ));
+DATA(insert OID = 3550 (	783		network_ops		PGNSP PGUID ));
 DATA(insert OID = 1976 (	403		integer_ops		PGNSP PGUID ));
 #define INTEGER_BTREE_FAM_OID 1976
 DATA(insert OID = 1977 (	405		integer_ops		PGNSP PGUID ));
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 21c17a08ed4..7b9c5870fac 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -2120,6 +2120,7 @@ DATA(insert OID = 927 (  network_sub		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 1
 DATA(insert OID = 928 (  network_subeq		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "869 869" _null_ _null_ _null_ _null_	network_subeq _null_ _null_ _null_ ));
 DATA(insert OID = 929 (  network_sup		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "869 869" _null_ _null_ _null_ _null_	network_sup _null_ _null_ _null_ ));
 DATA(insert OID = 930 (  network_supeq		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "869 869" _null_ _null_ _null_ _null_	network_supeq _null_ _null_ _null_ ));
+DATA(insert OID = 3551 (  network_overlap	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "869 869" _null_ _null_ _null_ _null_	network_overlap _null_ _null_ _null_ ));
 
 /* inet/cidr functions */
 DATA(insert OID = 598 (  abbrev				PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 25 "869" _null_ _null_ _null_ _null_	inet_abbrev _null_ _null_ _null_ ));
@@ -2166,6 +2167,28 @@ DATA(insert OID = 2631 (  int8pl_inet		PGNSP PGUID 14 1 0 0 0 f f f f t f i 2 0
 DATA(insert OID = 2632 (  inetmi_int8		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 869 "869 20" _null_ _null_ _null_ _null_	inetmi_int8 _null_ _null_ _null_ ));
 DATA(insert OID = 2633 (  inetmi			PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 20 "869 869" _null_ _null_ _null_ _null_	inetmi _null_ _null_ _null_ ));
 
+/* GiST support for inet and cidr */
+DATA(insert OID = 3553 (  inet_gist_consistent	PGNSP PGUID 12 1 0 0 0 f f f f t f i 5 0 16 "2281 869 23 26 2281" _null_ _null_ _null_ _null_ inet_gist_consistent _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3554 (  inet_gist_union		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ inet_gist_union _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3555 (  inet_gist_compress	PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ inet_gist_compress _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3556 (  inet_gist_decompress	PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ inet_gist_decompress _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3557 (  inet_gist_penalty		PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "2281 2281 2281" _null_ _null_ _null_ _null_ inet_gist_penalty _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3558 (  inet_gist_picksplit	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ inet_gist_picksplit _null_ _null_ _null_ ));
+DESCR("GiST support");
+DATA(insert OID = 3559 (  inet_gist_same		PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "869 869 2281" _null_ _null_ _null_ _null_ inet_gist_same _null_ _null_ _null_ ));
+DESCR("GiST support");
+
+/* Selectivity estimation for inet and cidr */
+DATA(insert OID = 3560 (  networksel		   PGNSP PGUID 12 1 0 0 0 f f f f t f s 4 0 701 "2281 26 2281 23" _null_ _null_ _null_ _null_	networksel _null_ _null_ _null_ ));
+DESCR("restriction selectivity for network operators");
+DATA(insert OID = 3561 (  networkjoinsel	   PGNSP PGUID 12 1 0 0 0 f f f f t f s 5 0 701 "2281 26 2281 21 2281" _null_ _null_ _null_ _null_	networkjoinsel _null_ _null_ _null_ ));
+DESCR("join selectivity for network operators");
+
 DATA(insert OID = 1690 ( time_mi_time		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 1186 "1083 1083" _null_ _null_ _null_ _null_	time_mi_time _null_ _null_ _null_ ));
 
 DATA(insert OID = 1691 (  boolle			PGNSP PGUID 12 1 0 0 0 f f f t t f i 2 0 16 "16 16" _null_ _null_ _null_ _null_ boolle _null_ _null_ _null_ ));
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 720c8318011..5907cb13fd3 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -906,6 +906,7 @@ extern Datum network_sub(PG_FUNCTION_ARGS);
 extern Datum network_subeq(PG_FUNCTION_ARGS);
 extern Datum network_sup(PG_FUNCTION_ARGS);
 extern Datum network_supeq(PG_FUNCTION_ARGS);
+extern Datum network_overlap(PG_FUNCTION_ARGS);
 extern Datum network_network(PG_FUNCTION_ARGS);
 extern Datum network_netmask(PG_FUNCTION_ARGS);
 extern Datum network_hostmask(PG_FUNCTION_ARGS);
diff --git a/src/include/utils/inet.h b/src/include/utils/inet.h
index 330f32de8f1..bd31c7169a1 100644
--- a/src/include/utils/inet.h
+++ b/src/include/utils/inet.h
@@ -53,6 +53,38 @@ typedef struct
 	inet_struct inet_data;
 } inet;
 
+/*
+ *	Access macros.	We use VARDATA_ANY so that we can process short-header
+ *	varlena values without detoasting them.  This requires a trick:
+ *	VARDATA_ANY assumes the varlena header is already filled in, which is
+ *	not the case when constructing a new value (until SET_INET_VARSIZE is
+ *	called, which we typically can't do till the end).  Therefore, we
+ *	always initialize the newly-allocated value to zeroes (using palloc0).
+ *	A zero length word will look like the not-1-byte case to VARDATA_ANY,
+ *	and so we correctly construct an uncompressed value.
+ *
+ *	Note that ip_addrsize(), ip_maxbits(), and SET_INET_VARSIZE() require
+ *	the family field to be set correctly.
+ */
+#define ip_family(inetptr) \
+	(((inet_struct *) VARDATA_ANY(inetptr))->family)
+
+#define ip_bits(inetptr) \
+	(((inet_struct *) VARDATA_ANY(inetptr))->bits)
+
+#define ip_addr(inetptr) \
+	(((inet_struct *) VARDATA_ANY(inetptr))->ipaddr)
+
+#define ip_addrsize(inetptr) \
+	(ip_family(inetptr) == PGSQL_AF_INET ? 4 : 16)
+
+#define ip_maxbits(inetptr) \
+	(ip_family(inetptr) == PGSQL_AF_INET ? 32 : 128)
+
+#define SET_INET_VARSIZE(dst) \
+	SET_VARSIZE(dst, VARHDRSZ + offsetof(inet_struct, ipaddr) + \
+				ip_addrsize(dst))
+
 
 /*
  *	This is the internal storage format for MAC addresses:
@@ -82,4 +114,27 @@ typedef struct macaddr
 #define PG_GETARG_MACADDR_P(n) DatumGetMacaddrP(PG_GETARG_DATUM(n))
 #define PG_RETURN_MACADDR_P(x) return MacaddrPGetDatum(x)
 
+/*
+ * Support functions in network.c
+ */
+extern int	bitncmp(const unsigned char *l, const unsigned char *r, int n);
+extern int	bitncommon(const unsigned char *l, const unsigned char *r, int n);
+
+/*
+ * GiST support functions in network_gist.c
+ */
+extern Datum inet_gist_consistent(PG_FUNCTION_ARGS);
+extern Datum inet_gist_union(PG_FUNCTION_ARGS);
+extern Datum inet_gist_compress(PG_FUNCTION_ARGS);
+extern Datum inet_gist_decompress(PG_FUNCTION_ARGS);
+extern Datum inet_gist_penalty(PG_FUNCTION_ARGS);
+extern Datum inet_gist_picksplit(PG_FUNCTION_ARGS);
+extern Datum inet_gist_same(PG_FUNCTION_ARGS);
+
+/*
+ * Estimation functions in network_selfuncs.c
+ */
+extern Datum networksel(PG_FUNCTION_ARGS);
+extern Datum networkjoinsel(PG_FUNCTION_ARGS);
+
 #endif   /* INET_H */