Add SP-GiST (space-partitioned GiST) index access method.

SP-GiST is comparable to GiST in flexibility, but supports non-balanced
partitioned search structures rather than balanced trees.  As described at
PGCon 2011, this new indexing structure can beat GiST in both index build
time and query speed for search problems that it is well matched to.

There are a number of areas that could still use improvement, but at this
point the code seems committable.

Teodor Sigaev and Oleg Bartunov, with considerable revisions by Tom Lane

14 files changed, 965 insertions, 7 deletions

diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index 290f0edaefa..ee5d71e4d71 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -24,6 +24,10 @@
  * Note: GIN does not include a page ID word as do the other index types.
  * This is OK because the opaque data is only 8 bytes and so can be reliably
  * distinguished by size.  Revisit this if the size ever increases.
+ * Further note: as of 9.2, SP-GiST also uses 8-byte special space.  This is
+ * still OK, as long as GIN isn't using all of the high-order bits in its
+ * flags word, because that way the flags word cannot match the page ID used
+ * by SP-GiST.
  */
 typedef struct GinPageOpaqueData
 {
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 14f50345bbf..10b2f9ea4db 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -42,8 +42,9 @@ typedef enum relopt_kind
 	RELOPT_KIND_GIST = (1 << 5),
 	RELOPT_KIND_ATTRIBUTE = (1 << 6),
 	RELOPT_KIND_TABLESPACE = (1 << 7),
+	RELOPT_KIND_SPGIST = (1 << 8),
 	/* if you add a new kind, make sure you update "last_default" too */
-	RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_TABLESPACE,
+	RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_SPGIST,
 	/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
 	RELOPT_KIND_MAX = (1 << 30)
 } relopt_kind;
diff --git a/src/include/access/rmgr.h b/src/include/access/rmgr.h
index 83abba359a5..e4844fe96c9 100644
--- a/src/include/access/rmgr.h
+++ b/src/include/access/rmgr.h
@@ -32,6 +32,8 @@ typedef uint8 RmgrId;
 #define RM_GIN_ID				13
 #define RM_GIST_ID				14
 #define RM_SEQ_ID				15
-#define RM_MAX_ID				RM_SEQ_ID
+#define RM_SPGIST_ID			16
+
+#define RM_MAX_ID				RM_SPGIST_ID
 
 #endif   /* RMGR_H */
diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h
new file mode 100644
index 00000000000..aa655a31402
--- /dev/null
+++ b/src/include/access/spgist.h
@@ -0,0 +1,199 @@
+/*-------------------------------------------------------------------------
+ *
+ * spgist.h
+ *	  Public header file for SP-GiST access method.
+ *
+ *
+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/access/spgist.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef SPGIST_H
+#define SPGIST_H
+
+#include "access/skey.h"
+#include "access/xlog.h"
+#include "fmgr.h"
+
+
+/* reloption parameters */
+#define SPGIST_MIN_FILLFACTOR			10
+#define SPGIST_DEFAULT_FILLFACTOR		80
+
+/* SPGiST opclass support function numbers */
+#define SPGIST_CONFIG_PROC				1
+#define SPGIST_CHOOSE_PROC				2
+#define SPGIST_PICKSPLIT_PROC			3
+#define SPGIST_INNER_CONSISTENT_PROC	4
+#define SPGIST_LEAF_CONSISTENT_PROC		5
+#define SPGISTNProc						5
+
+/*
+ * Argument structs for spg_config method
+ */
+typedef struct spgConfigIn
+{
+	Oid			attType;		/* Data type to be indexed */
+} spgConfigIn;
+
+typedef struct spgConfigOut
+{
+	Oid			prefixType;		/* Data type of inner-tuple prefixes */
+	Oid			labelType;		/* Data type of inner-tuple node labels */
+	bool		longValuesOK;	/* Opclass can cope with values > 1 page */
+} spgConfigOut;
+
+/*
+ * Argument structs for spg_choose method
+ */
+typedef struct spgChooseIn
+{
+	Datum		datum;			/* original datum to be indexed */
+	Datum		leafDatum;		/* current datum to be stored at leaf */
+	int			level;			/* current level (counting from zero) */
+
+	/* Data from current inner tuple */
+	bool		allTheSame;		/* tuple is marked all-the-same? */
+	bool		hasPrefix;		/* tuple has a prefix? */
+	Datum		prefixDatum;	/* if so, the prefix value */
+	int			nNodes;			/* number of nodes in the inner tuple */
+	Datum	   *nodeLabels;		/* node label values (NULL if none) */
+} spgChooseIn;
+
+typedef enum spgChooseResultType
+{
+	spgMatchNode = 1,			/* descend into existing node */
+	spgAddNode,					/* add a node to the inner tuple */
+	spgSplitTuple				/* split inner tuple (change its prefix) */
+} spgChooseResultType;
+
+typedef struct spgChooseOut
+{
+	spgChooseResultType resultType;		/* action code, see above */
+	union
+	{
+		struct					/* results for spgMatchNode */
+		{
+			int			nodeN;		/* descend to this node (index from 0) */
+			int			levelAdd;	/* increment level by this much */
+			Datum		restDatum;	/* new leaf datum */
+		}			matchNode;
+		struct					/* results for spgAddNode */
+		{
+			Datum		nodeLabel;	/* new node's label */
+			int			nodeN;		/* where to insert it (index from 0) */
+		}			addNode;
+		struct					/* results for spgSplitTuple */
+		{
+			/* Info to form new inner tuple with one node */
+			bool		prefixHasPrefix;	/* tuple should have a prefix? */
+			Datum		prefixPrefixDatum;	/* if so, its value */
+			Datum		nodeLabel;			/* node's label */
+
+			/* Info to form new lower-level inner tuple with all old nodes */
+			bool		postfixHasPrefix;	/* tuple should have a prefix? */
+			Datum		postfixPrefixDatum;	/* if so, its value */
+		}			splitTuple;
+	}			result;
+} spgChooseOut;
+
+/*
+ * Argument structs for spg_picksplit method
+ */
+typedef struct spgPickSplitIn
+{
+	int			nTuples;		/* number of leaf tuples */
+	Datum	   *datums;			/* their datums (array of length nTuples) */
+	int			level;			/* current level (counting from zero) */
+} spgPickSplitIn;
+
+typedef struct spgPickSplitOut
+{
+	bool		hasPrefix;		/* new inner tuple should have a prefix? */
+	Datum		prefixDatum;	/* if so, its value */
+
+	int			nNodes;			/* number of nodes for new inner tuple */
+	Datum	   *nodeLabels;		/* their labels (or NULL for no labels) */
+
+	int		   *mapTuplesToNodes;	/* node index for each leaf tuple */
+	Datum	   *leafTupleDatums;	/* datum to store in each new leaf tuple */
+} spgPickSplitOut;
+
+/*
+ * Argument structs for spg_inner_consistent method
+ */
+typedef struct spgInnerConsistentIn
+{
+	StrategyNumber strategy;	/* operator strategy number */
+	Datum		query;			/* operator's RHS value */
+
+	Datum		reconstructedValue;		/* value reconstructed at parent */
+	int			level;			/* current level (counting from zero) */
+
+	/* Data from current inner tuple */
+	bool		allTheSame;		/* tuple is marked all-the-same? */
+	bool		hasPrefix;		/* tuple has a prefix? */
+	Datum		prefixDatum;	/* if so, the prefix value */
+	int			nNodes;			/* number of nodes in the inner tuple */
+	Datum	   *nodeLabels;		/* node label values (NULL if none) */
+} spgInnerConsistentIn;
+
+typedef struct spgInnerConsistentOut
+{
+	int			nNodes;			/* number of child nodes to be visited */
+	int		   *nodeNumbers;	/* their indexes in the node array */
+	int		   *levelAdds;		/* increment level by this much for each */
+	Datum	   *reconstructedValues;	/* associated reconstructed values */
+} spgInnerConsistentOut;
+
+/*
+ * Argument structs for spg_leaf_consistent method
+ */
+typedef struct spgLeafConsistentIn
+{
+	StrategyNumber strategy;	/* operator strategy number */
+	Datum		query;			/* operator's RHS value */
+
+	Datum		reconstructedValue;		/* value reconstructed at parent */
+	int			level;			/* current level (counting from zero) */
+
+	Datum		leafDatum;		/* datum in leaf tuple */
+} spgLeafConsistentIn;
+
+typedef struct spgLeafConsistentOut
+{
+	bool		recheck;		/* set true if operator must be rechecked */
+} spgLeafConsistentOut;
+
+
+/* spginsert.c */
+extern Datum spgbuild(PG_FUNCTION_ARGS);
+extern Datum spgbuildempty(PG_FUNCTION_ARGS);
+extern Datum spginsert(PG_FUNCTION_ARGS);
+
+/* spgscan.c */
+extern Datum spgbeginscan(PG_FUNCTION_ARGS);
+extern Datum spgendscan(PG_FUNCTION_ARGS);
+extern Datum spgrescan(PG_FUNCTION_ARGS);
+extern Datum spgmarkpos(PG_FUNCTION_ARGS);
+extern Datum spgrestrpos(PG_FUNCTION_ARGS);
+extern Datum spggetbitmap(PG_FUNCTION_ARGS);
+extern Datum spggettuple(PG_FUNCTION_ARGS);
+
+/* spgutils.c */
+extern Datum spgoptions(PG_FUNCTION_ARGS);
+
+/* spgvacuum.c */
+extern Datum spgbulkdelete(PG_FUNCTION_ARGS);
+extern Datum spgvacuumcleanup(PG_FUNCTION_ARGS);
+
+/* spgxlog.c */
+extern void spg_redo(XLogRecPtr lsn, XLogRecord *record);
+extern void spg_desc(StringInfo buf, uint8 xl_info, char *rec);
+extern void spg_xlog_startup(void);
+extern void spg_xlog_cleanup(void);
+
+#endif   /* SPGIST_H */
diff --git a/src/include/access/spgist_private.h b/src/include/access/spgist_private.h
new file mode 100644
index 00000000000..5c57799f09c
--- /dev/null
+++ b/src/include/access/spgist_private.h
@@ -0,0 +1,609 @@
+/*-------------------------------------------------------------------------
+ *
+ * spgist_private.h
+ *	  Private declarations for SP-GiST access method.
+ *
+ *
+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/access/spgist_private.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef SPGIST_PRIVATE_H
+#define SPGIST_PRIVATE_H
+
+#include "access/itup.h"
+#include "access/spgist.h"
+#include "nodes/tidbitmap.h"
+#include "utils/rel.h"
+
+
+/* Page numbers of fixed-location pages */
+#define SPGIST_METAPAGE_BLKNO	 (0)
+#define SPGIST_HEAD_BLKNO		 (1)
+
+/*
+ * Contents of page special space on SPGiST index pages
+ */
+typedef struct SpGistPageOpaqueData
+{
+	uint16		flags;			/* see bit definitions below */
+	uint16		nRedirection;	/* number of redirection tuples on page */
+	uint16		nPlaceholder;	/* number of placeholder tuples on page */
+	/* note there's no count of either LIVE or DEAD tuples ... */
+	uint16		spgist_page_id;	/* for identification of SP-GiST indexes */
+} SpGistPageOpaqueData;
+
+typedef SpGistPageOpaqueData *SpGistPageOpaque;
+
+/* Flag bits in page special space */
+#define SPGIST_META			(1<<0)
+#define SPGIST_DELETED		(1<<1)
+#define SPGIST_LEAF			(1<<2)
+
+#define SpGistPageGetOpaque(page) ((SpGistPageOpaque) PageGetSpecialPointer(page))
+#define SpGistPageIsMeta(page) (SpGistPageGetOpaque(page)->flags & SPGIST_META)
+#define SpGistPageIsDeleted(page) (SpGistPageGetOpaque(page)->flags & SPGIST_DELETED)
+#define SpGistPageSetDeleted(page) (SpGistPageGetOpaque(page)->flags |= SPGIST_DELETED)
+#define SpGistPageSetNonDeleted(page) (SpGistPageGetOpaque(page)->flags &= ~SPGIST_DELETED)
+#define SpGistPageIsLeaf(page) (SpGistPageGetOpaque(page)->flags & SPGIST_LEAF)
+#define SpGistPageSetLeaf(page) (SpGistPageGetOpaque(page)->flags |= SPGIST_LEAF)
+#define SpGistPageSetInner(page) (SpGistPageGetOpaque(page)->flags &= ~SPGIST_LEAF)
+
+/*
+ * The page ID is for the convenience of pg_filedump and similar utilities,
+ * which otherwise would have a hard time telling pages of different index
+ * types apart.  It should be the last 2 bytes on the page.  This is more or
+ * less "free" due to alignment considerations.
+ */
+#define SPGIST_PAGE_ID		0xFF82
+
+/*
+ * Each backend keeps a cache of last-used page info in its index->rd_amcache
+ * area.  This is initialized from, and occasionally written back to,
+ * shared storage in the index metapage.
+ */
+typedef struct SpGistLastUsedPage
+{
+	BlockNumber blkno;			/* block number of described page */
+	int			freeSpace;		/* its free space (could be obsolete!) */
+} SpGistLastUsedPage;
+
+typedef struct SpGistCache
+{
+	SpGistLastUsedPage innerPage[3];	/* one per triple-parity group */
+	SpGistLastUsedPage leafPage;
+} SpGistCache;
+
+/*
+ * metapage
+ */
+typedef struct SpGistMetaPageData
+{
+	uint32		magicNumber;	/* for identity cross-check */
+	SpGistCache lastUsedPages;	/* shared storage of last-used info */
+} SpGistMetaPageData;
+
+#define SPGIST_MAGIC_NUMBER (0xBA0BABED)
+
+#define SpGistPageGetMeta(p) \
+	((SpGistMetaPageData *) PageGetContents(p))
+
+/*
+ * Private state of index AM.  SpGistState is common to both insert and
+ * search code; SpGistScanOpaque is for searches only.
+ */
+
+/* Per-datatype info needed in SpGistState */
+typedef struct SpGistTypeDesc
+{
+	Oid			type;
+	bool		attbyval;
+	int16		attlen;
+} SpGistTypeDesc;
+
+typedef struct SpGistState
+{
+	spgConfigOut config;		/* filled in by opclass config method */
+
+	SpGistTypeDesc attType;			/* type of input data and leaf values */
+	SpGistTypeDesc attPrefixType;	/* type of inner-tuple prefix values */
+	SpGistTypeDesc attLabelType;	/* type of node label values */
+
+	/* lookup data for the opclass support functions, except config */
+	FmgrInfo	chooseFn;
+	FmgrInfo	picksplitFn;
+	FmgrInfo	innerConsistentFn;
+	FmgrInfo	leafConsistentFn;
+
+	char	   *deadTupleStorage;	/* workspace for spgFormDeadTuple */
+
+	TransactionId myXid;		/* XID to use when creating a redirect tuple */
+	bool		isBuild;		/* true if doing index build */
+} SpGistState;
+
+/*
+ * Private state of an index scan
+ */
+typedef struct SpGistScanOpaqueData
+{
+	SpGistState state;			/* see above */
+	MemoryContext tempCxt;		/* short-lived memory context */
+
+	/* Index quals for scan (copied from IndexScanDesc for convenience) */
+	int			numberOfKeys;	/* number of index qualifier conditions */
+	ScanKey		keyData;		/* array of index qualifier descriptors */
+
+	/* Stack of yet-to-be-visited pages */
+	List	   *scanStack;		/* List of ScanStackEntrys */
+
+	/* These fields are only used in amgetbitmap scans: */
+	TIDBitmap  *tbm;			/* bitmap being filled */
+	int64		ntids;			/* number of TIDs passed to bitmap */
+
+	/* These fields are only used in amgettuple scans: */
+	int			nPtrs;			/* number of TIDs found on current page */
+	int			iPtr;			/* index for scanning through same */
+	ItemPointerData heapPtrs[MaxIndexTuplesPerPage]; /* TIDs from cur page */
+	bool		recheck[MaxIndexTuplesPerPage];		/* their recheck flags */
+
+	/*
+	 * Note: using MaxIndexTuplesPerPage above is a bit hokey since
+	 * SpGistLeafTuples aren't exactly IndexTuples; however, they are
+	 * larger, so this is safe.
+	 */
+} SpGistScanOpaqueData;
+
+typedef SpGistScanOpaqueData *SpGistScanOpaque;
+
+
+/*
+ * SPGiST tuple types.  Note: inner, leaf, and dead tuple structs
+ * must have the same tupstate field in the same position!  Real inner and
+ * leaf tuples always have tupstate = LIVE; if the state is something else,
+ * use the SpGistDeadTuple struct to inspect the tuple.
+ */
+
+/* values of tupstate (see README for more info) */
+#define SPGIST_LIVE			0	/* normal live tuple (either inner or leaf) */
+#define SPGIST_REDIRECT		1	/* temporary redirection placeholder */
+#define SPGIST_DEAD			2	/* dead, cannot be removed because of links */
+#define SPGIST_PLACEHOLDER	3	/* placeholder, used to preserve offsets */
+
+/*
+ * SPGiST inner tuple: list of "nodes" that subdivide a set of tuples
+ *
+ * Inner tuple layout:
+ * header/optional prefix/array of nodes, which are SpGistNodeTuples
+ *
+ * size and prefixSize must be multiples of MAXALIGN
+ */
+typedef struct SpGistInnerTupleData
+{
+	unsigned int tupstate:2,	/* LIVE/REDIRECT/DEAD/PLACEHOLDER */
+				allTheSame:1,	/* all nodes in tuple are equivalent */
+				nNodes:13,		/* number of nodes within inner tuple */
+				prefixSize:16;	/* size of prefix, or 0 if none */
+	uint16		size;			/* total size of inner tuple */
+	/* On most machines there will be a couple of wasted bytes here */
+	/* prefix datum follows, then nodes */
+} SpGistInnerTupleData;
+
+typedef SpGistInnerTupleData *SpGistInnerTuple;
+
+/* these must match largest values that fit in bit fields declared above */
+#define SGITMAXNNODES		0x1FFF
+#define SGITMAXPREFIXSIZE	0xFFFF
+#define SGITMAXSIZE			0xFFFF
+
+#define SGITHDRSZ			MAXALIGN(sizeof(SpGistInnerTupleData))
+#define _SGITDATA(x)		(((char *) (x)) + SGITHDRSZ)
+#define SGITDATAPTR(x)		((x)->prefixSize ? _SGITDATA(x) : NULL)
+#define SGITDATUM(x, s)		((x)->prefixSize ? \
+							 ((s)->attPrefixType.attbyval ? \
+							  *(Datum *) _SGITDATA(x) : \
+							  PointerGetDatum(_SGITDATA(x))) \
+							 : (Datum) 0)
+#define SGITNODEPTR(x)		((SpGistNodeTuple) (_SGITDATA(x) + (x)->prefixSize))
+
+/* Macro for iterating through the nodes of an inner tuple */
+#define SGITITERATE(x, i, nt)	\
+	for ((i) = 0, (nt) = SGITNODEPTR(x); \
+		 (i) < (x)->nNodes; \
+		 (i)++, (nt) = (SpGistNodeTuple) (((char *) (nt)) + IndexTupleSize(nt)))
+
+/*
+ * SPGiST node tuple: one node within an inner tuple
+ *
+ * Node tuples use the same header as ordinary Postgres IndexTuples, but
+ * we do not use a null bitmap, because we know there is only one column
+ * so the INDEX_NULL_MASK bit suffices.  Also, pass-by-value datums are
+ * stored as a full Datum, the same convention as for inner tuple prefixes
+ * and leaf tuple datums.
+ */
+
+typedef IndexTupleData SpGistNodeTupleData;
+
+typedef SpGistNodeTupleData *SpGistNodeTuple;
+
+#define SGNTHDRSZ			MAXALIGN(sizeof(SpGistNodeTupleData))
+#define SGNTDATAPTR(x)		(((char *) (x)) + SGNTHDRSZ)
+#define SGNTDATUM(x, s)		((s)->attLabelType.attbyval ? \
+							 *(Datum *) SGNTDATAPTR(x) : \
+							 PointerGetDatum(SGNTDATAPTR(x)))
+
+/*
+ * SPGiST leaf tuple: carries a datum and a heap tuple TID
+ *
+ * In the simplest case, the datum is the same as the indexed value; but
+ * it could also be a suffix or some other sort of delta that permits
+ * reconstruction given knowledge of the prefix path traversed to get here.
+ *
+ * The size field is wider than could possibly be needed for an on-disk leaf
+ * tuple, but this allows us to form leaf tuples even when the datum is too
+ * wide to be stored immediately, and it costs nothing because of alignment
+ * considerations.
+ *
+ * Normally, nextOffset links to the next tuple belonging to the same parent
+ * node (which must be on the same page).  But when the root page is a leaf
+ * page, we don't chain its tuples, so nextOffset is always 0 on the root.
+ *
+ * size must be a multiple of MAXALIGN
+ */
+typedef struct SpGistLeafTupleData
+{
+	unsigned int tupstate:2,	/* LIVE/REDIRECT/DEAD/PLACEHOLDER */
+				size:30;		/* large enough for any palloc'able value */
+	OffsetNumber nextOffset;	/* next tuple in chain, or InvalidOffset */
+	ItemPointerData heapPtr;	/* TID of represented heap tuple */
+	/* leaf datum follows */
+} SpGistLeafTupleData;
+
+typedef SpGistLeafTupleData *SpGistLeafTuple;
+
+#define SGLTHDRSZ			MAXALIGN(sizeof(SpGistLeafTupleData))
+#define SGLTDATAPTR(x)		(((char *) (x)) + SGLTHDRSZ)
+#define SGLTDATUM(x, s)		((s)->attType.attbyval ? \
+							 *(Datum *) SGLTDATAPTR(x) : \
+							 PointerGetDatum(SGLTDATAPTR(x)))
+
+/*
+ * SPGiST dead tuple: declaration for examining non-live tuples
+ *
+ * The tupstate field of this struct must match those of regular inner and
+ * leaf tuples, and its size field must match a leaf tuple's.
+ * Also, the pointer field must be in the same place as a leaf tuple's heapPtr
+ * field, to satisfy some Asserts that we make when replacing a leaf tuple
+ * with a dead tuple.
+ * We don't use nextOffset, but it's needed to align the pointer field.
+ * pointer and xid are only valid when tupstate = REDIRECT.
+ */
+typedef struct SpGistDeadTupleData
+{
+	unsigned int tupstate:2,	/* LIVE/REDIRECT/DEAD/PLACEHOLDER */
+				size:30;
+	OffsetNumber nextOffset;	/* not used in dead tuples */
+	ItemPointerData pointer;	/* redirection inside index */
+	TransactionId xid;			/* ID of xact that inserted this tuple */
+} SpGistDeadTupleData;
+
+typedef SpGistDeadTupleData *SpGistDeadTuple;
+
+#define SGDTSIZE		MAXALIGN(sizeof(SpGistDeadTupleData))
+
+/*
+ * Macros for doing free-space calculations.  Note that when adding up the
+ * space needed for tuples, we always consider each tuple to need the tuple's
+ * size plus sizeof(ItemIdData) (for the line pointer).  This works correctly
+ * so long as tuple sizes are always maxaligned.
+ */
+
+/* Page capacity after allowing for fixed header and special space */
+#define SPGIST_PAGE_CAPACITY  \
+	MAXALIGN_DOWN(BLCKSZ - \
+				  SizeOfPageHeaderData - \
+				  MAXALIGN(sizeof(SpGistPageOpaqueData)))
+
+/*
+ * Compute free space on page, assuming that up to n placeholders can be
+ * recycled if present (n should be the number of tuples to be inserted)
+ */
+#define SpGistPageGetFreeSpace(p, n) \
+	(PageGetExactFreeSpace(p) + \
+	 Min(SpGistPageGetOpaque(p)->nPlaceholder, n) * \
+	 (SGDTSIZE + sizeof(ItemIdData)))
+
+/*
+ * XLOG stuff
+ *
+ * ACCEPT_RDATA_* can only use fixed-length rdata arrays, because of lengthof
+ */
+
+#define ACCEPT_RDATA_DATA(p, s, i)  \
+	do { \
+		Assert((i) < lengthof(rdata)); \
+		rdata[i].data = (char *) (p); \
+		rdata[i].len = (s); \
+		rdata[i].buffer = InvalidBuffer; \
+		rdata[i].buffer_std = true; \
+		rdata[i].next = NULL; \
+		if ((i) > 0) \
+			rdata[(i) - 1].next = rdata + (i); \
+	} while(0)
+
+#define ACCEPT_RDATA_BUFFER(b, i)  \
+	do { \
+		Assert((i) < lengthof(rdata)); \
+		rdata[i].data = NULL; \
+		rdata[i].len = 0; \
+		rdata[i].buffer = (b); \
+		rdata[i].buffer_std = true; \
+		rdata[i].next = NULL; \
+		if ((i) > 0) \
+			rdata[(i) - 1].next = rdata + (i); \
+	} while(0)
+
+
+/* XLOG record types for SPGiST */
+#define XLOG_SPGIST_CREATE_INDEX	0x00
+#define XLOG_SPGIST_ADD_LEAF		0x10
+#define XLOG_SPGIST_MOVE_LEAFS		0x20
+#define XLOG_SPGIST_ADD_NODE		0x30
+#define XLOG_SPGIST_SPLIT_TUPLE		0x40
+#define XLOG_SPGIST_PICKSPLIT		0x50
+#define XLOG_SPGIST_VACUUM_LEAF		0x60
+#define XLOG_SPGIST_VACUUM_ROOT		0x70
+#define XLOG_SPGIST_VACUUM_REDIRECT	0x80
+
+/*
+ * Some redo functions need an SpGistState, although only a few of its fields
+ * need to be valid.  spgxlogState carries the required info in xlog records.
+ * (See fillFakeState in spgxlog.c for more comments.)
+ */
+typedef struct spgxlogState
+{
+	TransactionId myXid;
+	bool		isBuild;
+} spgxlogState;
+
+#define STORE_STATE(s, d)  \
+	do { \
+		(d).myXid = (s)->myXid; \
+		(d).isBuild = (s)->isBuild; \
+	} while(0)
+
+
+typedef struct spgxlogAddLeaf
+{
+	RelFileNode node;
+
+	BlockNumber blknoLeaf;		/* destination page for leaf tuple */
+	bool		newPage;		/* init dest page? */
+	OffsetNumber offnumLeaf;	/* offset where leaf tuple gets placed */
+	OffsetNumber offnumHeadLeaf; /* offset of head tuple in chain, if any */
+
+	BlockNumber blknoParent;	/* where the parent downlink is, if any */
+	OffsetNumber offnumParent;
+	uint16		nodeI;
+
+	/*
+	 * new leaf tuple follows, on an intalign boundary (replay only needs to
+	 * fetch its size field, so that should be enough alignment)
+	 */
+} spgxlogAddLeaf;
+
+typedef struct spgxlogMoveLeafs
+{
+	RelFileNode node;
+
+	BlockNumber blknoSrc;		/* source leaf page */
+	BlockNumber blknoDst;		/* destination leaf page */
+	uint16		nMoves;			/* number of tuples moved from source page */
+	bool		newPage;		/* init dest page? */
+	bool		replaceDead;	/* are we replacing a DEAD source tuple? */
+
+	BlockNumber blknoParent;	/* where the parent downlink is */
+	OffsetNumber offnumParent;
+	uint16		nodeI;
+
+	spgxlogState stateSrc;
+
+	/*----------
+	 * data follows:
+	 *		array of deleted tuple numbers, length nMoves
+	 *		array of inserted tuple numbers, length nMoves + 1 or 1
+	 *		list of leaf tuples, length nMoves + 1 or 1 (must be maxaligned)
+	 * the tuple number arrays are padded to maxalign boundaries so that the
+	 * leaf tuples will be suitably aligned
+	 *
+	 * Note: if replaceDead is true then there is only one inserted tuple
+	 * number and only one leaf tuple in the data, because we are not copying
+	 * the dead tuple from the source
+	 *
+	 * Buffer references in the rdata array are:
+	 *		Src page
+	 *		Dest page
+	 *		Parent page
+	 *----------
+	 */
+} spgxlogMoveLeafs;
+
+typedef struct spgxlogAddNode
+{
+	RelFileNode node;
+
+	BlockNumber blkno;			/* block number of original inner tuple */
+	OffsetNumber offnum;		/* offset of original inner tuple */
+
+	BlockNumber blknoParent;	/* where parent downlink is, if updated */
+	OffsetNumber offnumParent;
+	uint16		nodeI;
+
+	BlockNumber blknoNew;		/* where new tuple goes, if not same place */
+	OffsetNumber offnumNew;
+	bool		newPage;		/* init new page? */
+
+	spgxlogState stateSrc;
+
+	/*
+	 * updated inner tuple follows, on an intalign boundary (replay only needs
+	 * to fetch its size field, so that should be enough alignment)
+	 */
+} spgxlogAddNode;
+
+typedef struct spgxlogSplitTuple
+{
+	RelFileNode node;
+
+	BlockNumber blknoPrefix;	/* where the prefix tuple goes */
+	OffsetNumber offnumPrefix;
+
+	BlockNumber blknoPostfix;	/* where the postfix tuple goes */
+	OffsetNumber offnumPostfix;
+	bool		newPage;		/* need to init that page? */
+
+	/*
+	 * new prefix inner tuple follows, then new postfix inner tuple, on
+	 * intalign boundaries (replay only needs to fetch size fields, so that
+	 * should be enough alignment)
+	 */
+} spgxlogSplitTuple;
+
+typedef struct spgxlogPickSplit
+{
+	RelFileNode node;
+
+	BlockNumber blknoSrc;		/* original leaf page */
+	BlockNumber blknoDest;		/* other leaf page, if any */
+	uint16		nDelete;		/* n to delete from Src */
+	uint16		nInsert;		/* n to insert on Src and/or Dest */
+	bool		initSrc;		/* re-init the Src page? */
+	bool		initDest;		/* re-init the Dest page? */
+
+	BlockNumber blknoInner;		/* where to put new inner tuple */
+	OffsetNumber offnumInner;
+	bool		initInner;		/* re-init the Inner page? */
+
+	BlockNumber blknoParent;	/* where the parent downlink is, if any */
+	OffsetNumber offnumParent;
+	uint16		nodeI;
+
+	spgxlogState stateSrc;
+
+	/*----------
+	 * data follows:
+	 *		new inner tuple (assumed to have a maxaligned length)
+	 *		array of deleted tuple numbers, length nDelete
+	 *		array of inserted tuple numbers, length nInsert
+	 *		array of page selector bytes for inserted tuples, length nInsert
+	 *		list of leaf tuples, length nInsert (must be maxaligned)
+	 * the tuple number and page selector arrays are padded to maxalign
+	 * boundaries so that the leaf tuples will be suitably aligned
+	 *
+	 * Buffer references in the rdata array are:
+	 *		Src page (only if not root and not being init'd)
+	 *		Dest page (if used and not being init'd)
+	 *		Inner page (only if not being init'd)
+	 *		Parent page (if any; could be same as Inner)
+	 *----------
+	 */
+} spgxlogPickSplit;
+
+typedef struct spgxlogVacuumLeaf
+{
+	RelFileNode node;
+
+	BlockNumber blkno;			/* block number to clean */
+	uint16		nDead;			/* number of tuples to become DEAD */
+	uint16		nPlaceholder;	/* number of tuples to become PLACEHOLDER */
+	uint16		nMove;			/* number of tuples to move */
+	uint16		nChain;			/* number of tuples to re-chain */
+
+	spgxlogState stateSrc;
+
+	/*----------
+	 * data follows:
+	 *		tuple numbers to become DEAD
+	 *		tuple numbers to become PLACEHOLDER
+	 *		tuple numbers to move from (and replace with PLACEHOLDER)
+	 *		tuple numbers to move to (replacing what is there)
+	 *		tuple numbers to update nextOffset links of
+	 *		tuple numbers to insert in nextOffset links
+	 *----------
+	 */
+} spgxlogVacuumLeaf;
+
+typedef struct spgxlogVacuumRoot
+{
+	/* vacuum root page when it is a leaf */
+	RelFileNode node;
+
+	uint16		nDelete;		/* number of tuples to delete */
+
+	spgxlogState stateSrc;
+
+	/* offsets of tuples to delete follow */
+} spgxlogVacuumRoot;
+
+typedef struct spgxlogVacuumRedirect
+{
+	RelFileNode node;
+
+	BlockNumber blkno;			/* block number to clean */
+	uint16		nToPlaceholder;	/* number of redirects to make placeholders */
+	OffsetNumber firstPlaceholder;		/* first placeholder tuple to remove */
+
+	/* offsets of redirect tuples to make placeholders follow */
+} spgxlogVacuumRedirect;
+
+/*
+ * The "flags" argument for SpGistGetBuffer should be either GBUF_LEAF to
+ * get a leaf page, or GBUF_INNER_PARITY(blockNumber) to get an inner
+ * page in the same triple-parity group as the specified block number.
+ * (Typically, this should be GBUF_INNER_PARITY(parentBlockNumber + 1)
+ * to follow the rule described in spgist/README.)
+ */
+#define GBUF_PARITY_MASK		0x03
+#define GBUF_LEAF				0x04
+#define GBUF_INNER_PARITY(x)	((x) % 3)
+
+/* spgutils.c */
+extern void initSpGistState(SpGistState *state, Relation index);
+extern Buffer SpGistNewBuffer(Relation index);
+extern void SpGistUpdateMetaPage(Relation index);
+extern Buffer SpGistGetBuffer(Relation index, int flags,
+							  int needSpace, bool *isNew);
+extern void SpGistSetLastUsedPage(Relation index, Buffer buffer);
+extern void SpGistInitPage(Page page, uint16 f);
+extern void SpGistInitBuffer(Buffer b, uint16 f);
+extern void SpGistInitMetapage(Page page);
+extern unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum);
+extern SpGistLeafTuple spgFormLeafTuple(SpGistState *state,
+										ItemPointer heapPtr, Datum datum);
+extern SpGistNodeTuple spgFormNodeTuple(SpGistState *state,
+										Datum label, bool isnull);
+extern SpGistInnerTuple spgFormInnerTuple(SpGistState *state,
+										  bool hasPrefix, Datum prefix,
+										  int nNodes, SpGistNodeTuple *nodes);
+extern SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate,
+				 BlockNumber blkno, OffsetNumber offnum);
+extern Datum *spgExtractNodeLabels(SpGistState *state,
+								   SpGistInnerTuple innerTuple);
+extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page,
+					 Item item, Size size,
+					 OffsetNumber *startOffset,
+					 bool errorOK);
+
+/* spgdoinsert.c */
+extern void updateNodeLink(SpGistInnerTuple tup, int nodeN,
+						   BlockNumber blkno, OffsetNumber offset);
+extern void spgPageIndexMultiDelete(SpGistState *state, Page page,
+						OffsetNumber *itemnos, int nitems,
+						int firststate, int reststate,
+						BlockNumber blkno, OffsetNumber offnum);
+extern void spgdoinsert(Relation index, SpGistState *state,
+						ItemPointer heapPtr, Datum datum);
+
+#endif   /* SPGIST_PRIVATE_H */
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 14e177dc482..eb343545915 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201112071
+#define CATALOG_VERSION_NO	201112171
 
 #endif
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index ddacdf274c4..6fdd1d5b052 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -117,17 +117,20 @@ typedef FormData_pg_am *Form_pg_am;
  * ----------------
  */
 
-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 ));
+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 ));
+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 ));
 DESCR("hash index access method");
 #define HASH_AM_OID 405
-DATA(insert OID = 783 (  gist	0 8 f t f f t f t f t t t f 0 gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbuildempty gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
+DATA(insert OID = 783 (  gist		0 8 f t f f t f t f t t t f 0 gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbuildempty gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
 DESCR("GiST index access method");
 #define GIST_AM_OID 783
-DATA(insert OID = 2742 (  gin	0 5 f f f f t f t f f t f f 0 gininsert ginbeginscan - gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbuildempty ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
+DATA(insert OID = 2742 (  gin		0 5 f f f f t f t f f t f f 0 gininsert ginbeginscan - gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbuildempty ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
 DESCR("GIN index access method");
 #define GIN_AM_OID 2742
+DATA(insert OID = 4000 (  spgist	0 5 f f f f f f f f f f f f 0 spginsert spgbeginscan spggettuple spggetbitmap spgrescan spgendscan spgmarkpos spgrestrpos spgbuild spgbuildempty spgbulkdelete spgvacuumcleanup spgcostestimate spgoptions ));
+DESCR("SP-GiST index access method");
+#define SPGIST_AM_OID 4000
 
 #endif   /* PG_AM_H */
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index 1e8c9a289f9..cb394e03e40 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -737,4 +737,37 @@ DATA(insert (	3919   3831 3831 8 s	3892 783 0 ));
 DATA(insert (	3919   3831 2283 16 s	3889 783 0 ));
 DATA(insert (	3919   3831 3831 18 s	3882 783 0 ));
 
+/*
+ * SP-GiST quad_point_ops
+ */
+DATA(insert (	4015   600 600 11 s 506 4000 0 ));
+DATA(insert (	4015   600 600 1 s	507 4000 0 ));
+DATA(insert (	4015   600 600 5 s	508 4000 0 ));
+DATA(insert (	4015   600 600 10 s 509 4000 0 ));
+DATA(insert (	4015   600 600 6 s	510 4000 0 ));
+DATA(insert (	4015   600 603 8 s	511 4000 0 ));
+
+/*
+ * SP-GiST kd_point_ops
+ */
+DATA(insert (	4016   600 600 11 s 506 4000 0 ));
+DATA(insert (	4016   600 600 1 s	507 4000 0 ));
+DATA(insert (	4016   600 600 5 s	508 4000 0 ));
+DATA(insert (	4016   600 600 10 s 509 4000 0 ));
+DATA(insert (	4016   600 600 6 s	510 4000 0 ));
+DATA(insert (	4016   600 603 8 s	511 4000 0 ));
+
+/*
+ * SP-GiST text_ops
+ */
+DATA(insert (	4017   25 25 1 s	2314 4000 0 ));
+DATA(insert (	4017   25 25 2 s	2315 4000 0 ));
+DATA(insert (	4017   25 25 3 s	98	4000 0 ));
+DATA(insert (	4017   25 25 4 s	2317 4000 0 ));
+DATA(insert (	4017   25 25 5 s	2318 4000 0 ));
+DATA(insert (	4017   25 25 11 s	664 4000 0 ));
+DATA(insert (	4017   25 25 12 s	665 4000 0 ));
+DATA(insert (	4017   25 25 14 s	667 4000 0 ));
+DATA(insert (	4017   25 25 15 s	666 4000 0 ));
+
 #endif   /* PG_AMOP_H */
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index 8571dd08709..a4c49efed83 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -356,4 +356,22 @@ DATA(insert (	3919   3831 3831 5 3879 ));
 DATA(insert (	3919   3831 3831 6 3880 ));
 DATA(insert (	3919   3831 3831 7 3881 ));
 
+
+/* sp-gist */
+DATA(insert (	4015   600 600 1 4018 ));
+DATA(insert (	4015   600 600 2 4019 ));
+DATA(insert (	4015   600 600 3 4020 ));
+DATA(insert (	4015   600 600 4 4021 ));
+DATA(insert (	4015   600 600 5 4022 ));
+DATA(insert (	4016   600 600 1 4023 ));
+DATA(insert (	4016   600 600 2 4024 ));
+DATA(insert (	4016   600 600 3 4025 ));
+DATA(insert (	4016   600 600 4 4026 ));
+DATA(insert (	4016   600 600 5 4022 ));
+DATA(insert (	4017   25 25 1 4027 ));
+DATA(insert (	4017   25 25 2 4028 ));
+DATA(insert (	4017   25 25 3 4029 ));
+DATA(insert (	4017   25 25 4 4030 ));
+DATA(insert (	4017   25 25 5 4031 ));
+
 #endif   /* PG_AMPROC_H */
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index eecd3b63c50..c692ae4311b 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -223,5 +223,8 @@ DATA(insert (	783		tsquery_ops			PGNSP PGUID 3702  3615 t 20 ));
 DATA(insert (	403		range_ops			PGNSP PGUID 3901  3831 t 0 ));
 DATA(insert (	405		range_ops			PGNSP PGUID 3903  3831 t 0 ));
 DATA(insert (	783		range_ops			PGNSP PGUID 3919  3831 t 0 ));
+DATA(insert (	4000	quad_point_ops		PGNSP PGUID 4015  600 t 0 ));
+DATA(insert (	4000	kd_point_ops		PGNSP PGUID 4016  600 f 0 ));
+DATA(insert (	4000	text_ops			PGNSP PGUID 4017  25 t 0 ));
 
 #endif   /* PG_OPCLASS_H */
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index 5ea949bec6b..009000ffcff 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -142,5 +142,8 @@ DATA(insert OID = 3702 (	783		tsquery_ops		PGNSP PGUID ));
 DATA(insert OID = 3901 (	403		range_ops		PGNSP PGUID ));
 DATA(insert OID = 3903 (	405		range_ops		PGNSP PGUID ));
 DATA(insert OID = 3919 (	783		range_ops		PGNSP PGUID ));
+DATA(insert OID = 4015 (	4000	quad_point_ops	PGNSP PGUID ));
+DATA(insert OID = 4016 (	4000	kd_point_ops	PGNSP PGUID ));
+DATA(insert OID = 4017 (	4000	text_ops		PGNSP PGUID ));
 
 #endif   /* PG_OPFAMILY_H */
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 924cb1f601c..6da3b421ae3 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -4481,6 +4481,68 @@ DESCR("int8range constructor");
 DATA(insert OID = 3946 (  int8range	PGNSP PGUID 12 1 0 0 0 f f f f f i 3 0 3926 "20 20 25" _null_ _null_ _null_ _null_ range_constructor3 _null_ _null_ _null_ ));
 DESCR("int8range constructor");
 
+/* spgist support functions */
+DATA(insert OID = 4001 (  spggettuple	   PGNSP PGUID 12 1 0 0 0 f f f t f v 2 0 16 "2281 2281" _null_ _null_ _null_ _null_	spggettuple _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4002 (  spggetbitmap	   PGNSP PGUID 12 1 0 0 0 f f f t f v 2 0 20 "2281 2281" _null_ _null_ _null_ _null_	spggetbitmap _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4003 (  spginsert		   PGNSP PGUID 12 1 0 0 0 f f f t f v 6 0 16 "2281 2281 2281 2281 2281 2281" _null_ _null_ _null_ _null_	spginsert _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4004 (  spgbeginscan	   PGNSP PGUID 12 1 0 0 0 f f f t f v 3 0 2281 "2281 2281 2281" _null_ _null_ _null_ _null_	spgbeginscan _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4005 (  spgrescan		   PGNSP PGUID 12 1 0 0 0 f f f t f v 5 0 2278 "2281 2281 2281 2281 2281" _null_ _null_ _null_ _null_ spgrescan _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4006 (  spgendscan	   PGNSP PGUID 12 1 0 0 0 f f f t f v 1 0 2278 "2281" _null_ _null_ _null_ _null_ spgendscan _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4007 (  spgmarkpos	   PGNSP PGUID 12 1 0 0 0 f f f t f v 1 0 2278 "2281" _null_ _null_ _null_ _null_ spgmarkpos _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4008 (  spgrestrpos	   PGNSP PGUID 12 1 0 0 0 f f f t f v 1 0 2278 "2281" _null_ _null_ _null_ _null_ spgrestrpos _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4009 (  spgbuild		   PGNSP PGUID 12 1 0 0 0 f f f t f v 3 0 2281 "2281 2281 2281" _null_ _null_ _null_ _null_ spgbuild _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4010 (  spgbuildempty    PGNSP PGUID 12 1 0 0 0 f f f t f v 1 0 2278 "2281" _null_ _null_ _null_ _null_ spgbuildempty _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4011 (  spgbulkdelete    PGNSP PGUID 12 1 0 0 0 f f f t f v 4 0 2281 "2281 2281 2281 2281" _null_ _null_ _null_ _null_ spgbulkdelete _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4012 (  spgvacuumcleanup   PGNSP PGUID 12 1 0 0 0 f f f t f v 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ spgvacuumcleanup _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4013 (  spgcostestimate  PGNSP PGUID 12 1 0 0 0 f f f t f v 9 0 2278 "2281 2281 2281 2281 2281 2281 2281 2281 2281" _null_ _null_ _null_ _null_ spgcostestimate _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+DATA(insert OID = 4014 (  spgoptions	   PGNSP PGUID 12 1 0 0 0 f f f t f s 2 0 17 "1009 16" _null_ _null_ _null_ _null_  spgoptions _null_ _null_ _null_ ));
+DESCR("spgist(internal)");
+
+/* spgist opclasses */
+DATA(insert OID = 4018 (  spg_quad_config	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_quad_config _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over point");
+DATA(insert OID = 4019 (  spg_quad_choose	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_quad_choose _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over point");
+DATA(insert OID = 4020 (  spg_quad_picksplit	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_quad_picksplit _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over point");
+DATA(insert OID = 4021 (  spg_quad_inner_consistent	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_quad_inner_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over point");
+DATA(insert OID = 4022 (  spg_quad_leaf_consistent	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_  spg_quad_leaf_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree and k-d tree over point");
+
+DATA(insert OID = 4023 (  spg_kd_config	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_kd_config _null_ _null_ _null_ ));
+DESCR("SP-GiST support for k-d tree over point");
+DATA(insert OID = 4024 (  spg_kd_choose	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_kd_choose _null_ _null_ _null_ ));
+DESCR("SP-GiST support for k-d tree over point");
+DATA(insert OID = 4025 (  spg_kd_picksplit	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_kd_picksplit _null_ _null_ _null_ ));
+DESCR("SP-GiST support for k-d tree over point");
+DATA(insert OID = 4026 (  spg_kd_inner_consistent	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_kd_inner_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for k-d tree over point");
+
+DATA(insert OID = 4027 (  spg_text_config	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_text_config _null_ _null_ _null_ ));
+DESCR("SP-GiST support for suffix tree over text");
+DATA(insert OID = 4028 (  spg_text_choose	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_text_choose _null_ _null_ _null_ ));
+DESCR("SP-GiST support for suffix tree over text");
+DATA(insert OID = 4029 (  spg_text_picksplit	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_text_picksplit _null_ _null_ _null_ ));
+DESCR("SP-GiST support for suffix tree over text");
+DATA(insert OID = 4030 (  spg_text_inner_consistent	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_text_inner_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for suffix tree over text");
+DATA(insert OID = 4031 (  spg_text_leaf_consistent	PGNSP PGUID 12 1 0 0 0 f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_  spg_text_leaf_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for suffix tree over text");
+
 
 /*
  * Symbolic values for provolatile column: these indicate whether the result
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 994dc5368b1..9c5af5960fd 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -1080,6 +1080,26 @@ extern Datum window_first_value(PG_FUNCTION_ARGS);
 extern Datum window_last_value(PG_FUNCTION_ARGS);
 extern Datum window_nth_value(PG_FUNCTION_ARGS);
 
+/* access/spgist/spgquadtreeproc.c */
+extern Datum spg_quad_config(PG_FUNCTION_ARGS);
+extern Datum spg_quad_choose(PG_FUNCTION_ARGS);
+extern Datum spg_quad_picksplit(PG_FUNCTION_ARGS);
+extern Datum spg_quad_inner_consistent(PG_FUNCTION_ARGS);
+extern Datum spg_quad_leaf_consistent(PG_FUNCTION_ARGS);
+
+/* access/spgist/spgkdtreeproc.c */
+extern Datum spg_kd_config(PG_FUNCTION_ARGS);
+extern Datum spg_kd_choose(PG_FUNCTION_ARGS);
+extern Datum spg_kd_picksplit(PG_FUNCTION_ARGS);
+extern Datum spg_kd_inner_consistent(PG_FUNCTION_ARGS);
+
+/* access/spgist/spgtextproc.c */
+extern Datum spg_text_config(PG_FUNCTION_ARGS);
+extern Datum spg_text_choose(PG_FUNCTION_ARGS);
+extern Datum spg_text_picksplit(PG_FUNCTION_ARGS);
+extern Datum spg_text_inner_consistent(PG_FUNCTION_ARGS);
+extern Datum spg_text_leaf_consistent(PG_FUNCTION_ARGS);
+
 /* access/gin/ginarrayproc.c */
 extern Datum ginarrayextract(PG_FUNCTION_ARGS);
 extern Datum ginarrayextract_2args(PG_FUNCTION_ARGS);
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 32d14b60290..6afcbf47537 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -194,6 +194,7 @@ extern Selectivity estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey,
 extern Datum btcostestimate(PG_FUNCTION_ARGS);
 extern Datum hashcostestimate(PG_FUNCTION_ARGS);
 extern Datum gistcostestimate(PG_FUNCTION_ARGS);
+extern Datum spgcostestimate(PG_FUNCTION_ARGS);
 extern Datum gincostestimate(PG_FUNCTION_ARGS);
 
 #endif   /* SELFUNCS_H */