Concurrency for GiST

- full concurrency for insert/update/select/vacuum:
        - select and vacuum never locks more than one page simultaneously
        - select (gettuple) hasn't any lock across it's calls
        - insert never locks more than two page simultaneously:
                - during search of leaf to insert it locks only one page
                  simultaneously
                - while walk upward to the root it locked only parent (may be
                  non-direct parent) and child. One of them X-lock, another may
                  be S- or X-lock
- 'vacuum full' locks index
- improve gistgetmulti
- simplify XLOG records

Fix bug in index_beginscan_internal: LockRelation may clean
  rd_aminfo structure, so move GET_REL_PROCEDURE after LockRelation

5 files changed, 136 insertions, 105 deletions

diff --git a/src/include/access/gist.h b/src/include/access/gist.h
index bf9c1c712b..ee060e83c2 100644
--- a/src/include/access/gist.h
+++ b/src/include/access/gist.h
@@ -9,7 +9,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/gist.h,v 1.47 2005/06/20 10:29:36 teodor Exp $
+ * $PostgreSQL: pgsql/src/include/access/gist.h,v 1.48 2005/06/27 12:45:22 teodor Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,8 @@
 #include "storage/bufpage.h"
 #include "storage/off.h"
 #include "utils/rel.h"
+#include "access/xlog.h"
+#include "access/xlogdefs.h"
 
 /*
  * amproc indexes for GiST indexes.
@@ -39,9 +41,22 @@
 #define F_DELETED		(1 << 1)
 #define F_TUPLES_DELETED	(1 << 2)
 
+typedef XLogRecPtr GistNSN;
+
 typedef struct GISTPageOpaqueData
 {
-	uint32		flags;
+	uint8		flags;
+
+   /* number page to which current one is splitted in last split */
+	uint8		nsplited;
+
+   /* level of page, 0 - leaf */
+	uint16		level;
+	BlockNumber	rightlink;
+
+   /* the only meaning - change this value if
+      page split. */
+	GistNSN		nsn;
 } GISTPageOpaqueData;
 
 typedef GISTPageOpaqueData *GISTPageOpaque;
@@ -90,18 +105,20 @@ typedef struct GISTENTRY
 	bool		leafkey;
 } GISTENTRY;
 
-#define GistPageIsLeaf(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags & F_LEAF)
+#define	GistPageGetOpaque(page)	( (GISTPageOpaque) PageGetSpecialPointer(page) )
+
+#define GistPageIsLeaf(page)	( GistPageGetOpaque(page)->flags & F_LEAF)
 #define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
-#define GistPageSetLeaf(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags |= F_LEAF)
-#define GistPageSetNonLeaf(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags &= ~F_LEAF)
+#define GistPageSetLeaf(page)	( GistPageGetOpaque(page)->flags |= F_LEAF)
+#define GistPageSetNonLeaf(page) 	( GistPageGetOpaque(page)->flags &= ~F_LEAF)
 
-#define GistPageIsDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags & F_DELETED)
-#define GistPageSetDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags |= F_DELETED)
-#define GistPageSetNonDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags &= ~F_DELETED)
+#define GistPageIsDeleted(page)	( GistPageGetOpaque(page)->flags & F_DELETED)
+#define GistPageSetDeleted(page)	( GistPageGetOpaque(page)->flags |= F_DELETED)
+#define GistPageSetNonDeleted(page)	( GistPageGetOpaque(page)->flags &= ~F_DELETED)
 
-#define GistTuplesDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags & F_TUPLES_DELETED)
-#define GistMarkTuplesDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags |= F_TUPLES_DELETED)
-#define GistClearTuplesDeleted(page)	(((GISTPageOpaque) PageGetSpecialPointer(page))->flags &= ~F_TUPLES_DELETED)
+#define GistTuplesDeleted(page)	( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
+#define GistMarkTuplesDeleted(page)	( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
+#define GistClearTuplesDeleted(page)	( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
 
 /*
  * Vector of GISTENTRY structs; user-defined methods union and pick
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
index 54bf195759..6ea4dccb68 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/gist_private.h,v 1.5 2005/06/20 15:22:38 teodor Exp $
+ * $PostgreSQL: pgsql/src/include/access/gist_private.h,v 1.6 2005/06/27 12:45:22 teodor Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,7 +20,13 @@
 #include "access/xlogdefs.h"
 #include "fmgr.h"
 
+#define GIST_UNLOCK	BUFFER_LOCK_UNLOCK
+#define GIST_SHARE	BUFFER_LOCK_SHARE
+#define GIST_EXCLUSIVE	BUFFER_LOCK_EXCLUSIVE
+
+
 /*
+ * XXX old comment!!!
  * When we descend a tree, we keep a stack of parent pointers. This
  * allows us to follow a chain of internal node points until we reach
  * a leaf node, and then back up the stack to re-examine the internal
@@ -31,12 +37,15 @@
  * the node's page that we stopped at (i.e. we followed the child
  * pointer located at the specified offset).
  */
-typedef struct GISTSTACK
+typedef struct GISTSearchStack
 {
-	struct GISTSTACK *parent;
-	OffsetNumber offset;
+	struct GISTSearchStack *next;
 	BlockNumber block;
-} GISTSTACK;
+	/* to identify page changed */
+	GistNSN		lsn;
+	/* to recognize split occured */
+	GistNSN		parentlsn;
+} GISTSearchStack;
 
 typedef struct GISTSTATE
 {
@@ -57,8 +66,8 @@ typedef struct GISTSTATE
  */
 typedef struct GISTScanOpaqueData
 {
-	GISTSTACK			*stack;
-	GISTSTACK			*markstk;
+	GISTSearchStack			*stack;
+	GISTSearchStack			*markstk;
 	uint16				 flags;
 	GISTSTATE			*giststate;
 	MemoryContext		 tempCxt;
@@ -68,6 +77,71 @@ typedef struct GISTScanOpaqueData
 
 typedef GISTScanOpaqueData *GISTScanOpaque;
 
+/* XLog stuff */
+extern	const XLogRecPtr	XLogRecPtrForTemp;
+
+#define	XLOG_GIST_ENTRY_UPDATE	0x00
+#define	XLOG_GIST_ENTRY_DELETE	0x10
+#define XLOG_GIST_NEW_ROOT	0x20
+
+typedef struct gistxlogEntryUpdate {
+	RelFileNode	node;
+	BlockNumber	blkno;
+
+	uint16		ntodelete;
+	bool		isemptypage;	
+
+	/* 
+	 * It used to identify completeness of insert.
+         * Sets to leaf itup 
+         */ 
+	ItemPointerData	key;
+
+	/* follow:
+	 * 1. todelete OffsetNumbers 
+	 * 2. tuples to insert
+         */ 
+} gistxlogEntryUpdate;
+
+#define XLOG_GIST_PAGE_SPLIT	0x30
+
+typedef struct gistxlogPageSplit {
+	RelFileNode	node;
+	BlockNumber	origblkno; /*splitted page*/
+	uint16		npage;
+
+	/* see comments on gistxlogEntryUpdate */
+	ItemPointerData	key;
+ 
+	/* follow:
+	 * 1. gistxlogPage and array of IndexTupleData per page
+         */ 
+} gistxlogPageSplit;
+
+#define XLOG_GIST_INSERT_COMPLETE  0x40
+
+typedef struct gistxlogPage {
+	BlockNumber	blkno;
+	int		num;
+} gistxlogPage;	
+
+#define	XLOG_GIST_CREATE_INDEX	0x50
+
+typedef struct gistxlogInsertComplete {
+	RelFileNode	node;
+	/* follows ItemPointerData key to clean */
+} gistxlogInsertComplete;
+
+/* SplitedPageLayout - gistSplit function result */
+typedef struct SplitedPageLayout {
+        gistxlogPage    block;
+        IndexTupleData  *list;
+	int		lenlist;
+        Buffer          buffer; /* to write after all proceed */
+
+        struct SplitedPageLayout *next;
+} SplitedPageLayout;
+
 /*
  * GISTInsertStack used for locking buffers and transfer arguments during
  * insertion
@@ -78,16 +152,25 @@ typedef struct GISTInsertStack {
 	BlockNumber	blkno;	 
 	Buffer		buffer;
 	Page		page;
+
+	/* log sequence number from page->lsn to
+           recognize page update  and compare it with page's nsn 
+	  to recognize page split*/
+	GistNSN		lsn;
 	
 	/* child's offset */
 	OffsetNumber	childoffnum;
 
-	/* pointer to parent */
+	/* pointer to parent and child */
 	struct GISTInsertStack	*parent;
+	struct GISTInsertStack	*child;
 
-	bool todelete;
+	/* for gistFindPath */
+	struct GISTInsertStack	*next;
 } GISTInsertStack;
 
+#define XLogRecPtrIsInvalid( r )	( (r).xlogid == 0 && (r).xrecoff == 0 )
+
 typedef struct {
 	Relation	r;
 	IndexTuple      *itup; /* in/out, points to compressed entry */
@@ -97,10 +180,6 @@ typedef struct {
 
 	/* pointer to heap tuple */
 	ItemPointerData	key;
-
-	/* path to stroe in XLog */
-	BlockNumber	*path;
-	int 		pathlen; 
 } GISTInsertState;
 
 /*
@@ -124,7 +203,7 @@ typedef struct {
  * constants tell us what sort of operation changed the index.
  */
 #define GISTOP_DEL		0
-#define GISTOP_SPLIT	1
+/* #define GISTOP_SPLIT	1 */
 
 #define ATTSIZE(datum, tupdesc, i, isnull) \
         ( \
@@ -132,64 +211,6 @@ typedef struct {
                    att_addlength(0, (tupdesc)->attrs[(i)-1]->attlen, (datum)) \
         ) 
 
-/* XLog stuff */
-#define	XLOG_GIST_ENTRY_UPDATE	0x00
-#define	XLOG_GIST_ENTRY_DELETE	0x10
-#define XLOG_GIST_NEW_ROOT	0x20
-
-typedef struct gistxlogEntryUpdate {
-	RelFileNode	node;
-	BlockNumber	blkno;
-
-	uint16		ntodelete;
-	uint16		pathlen;
-	bool		isemptypage;	
-
-	/* 
-	 * It used to identify completeness of insert.
-         * Sets to leaf itup 
-         */ 
-	ItemPointerData	key;
-
-	/* follow:
-	 * 1. path to root (BlockNumber)
-	 * 2. todelete OffsetNumbers 
-	 * 3. tuples to insert
-         */ 
-} gistxlogEntryUpdate;
-
-#define XLOG_GIST_PAGE_SPLIT	0x30
-
-typedef struct gistxlogPageSplit {
-	RelFileNode	node;
-	BlockNumber	origblkno; /*splitted page*/
-	uint16		pathlen;
-	uint16		npage;
-
-	/* see comments on gistxlogEntryUpdate */
-	ItemPointerData	key;
- 
-	/* follow:
-	 * 1. path to root (BlockNumber) 
-	 * 2. gistxlogPage and array of IndexTupleData per page
-         */ 
-} gistxlogPageSplit;
-
-typedef struct gistxlogPage {
-	BlockNumber	blkno;
-	int		num;
-} gistxlogPage;	
-
-
-#define XLOG_GIST_INSERT_COMPLETE  0x40
-
-typedef struct gistxlogInsertComplete {
-	RelFileNode	node;
-	/* follows ItemPointerData key to clean */
-} gistxlogInsertComplete;
-
-#define	XLOG_GIST_CREATE_INDEX	0x50
-
 /*
  * mark tuples on inner pages during recovery
  */
@@ -206,20 +227,14 @@ extern Datum gistinsert(PG_FUNCTION_ARGS);
 extern MemoryContext createTempGistContext(void);
 extern void initGISTstate(GISTSTATE *giststate, Relation index);
 extern void freeGISTstate(GISTSTATE *giststate);
-extern void gistnewroot(Relation r, IndexTuple *itup, int len, ItemPointer key);
 extern void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate);
+extern void gistnewroot(Relation r, Buffer buffer, IndexTuple *itup, int len, ItemPointer key);
 
-typedef struct SplitedPageLayout {
-        gistxlogPage    block;
-        IndexTupleData  *list;
-	int		lenlist;
-        Buffer          buffer; /* to write after all proceed */
-
-        struct SplitedPageLayout *next;
-} SplitedPageLayout;
-
-IndexTuple * gistSplit(Relation r, Buffer buffer, IndexTuple *itup,
+extern IndexTuple * gistSplit(Relation r, Buffer buffer, IndexTuple *itup,
                   int *len, SplitedPageLayout    **dist, GISTSTATE *giststate);
+
+extern GISTInsertStack* gistFindPath( Relation r, BlockNumber child, 
+	Buffer  (*myReadBuffer)(bool, Relation, BlockNumber) );
 /* gistxlog.c */
 extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
 extern void gist_desc(char *buf, uint8 xl_info, char *rec);
@@ -229,12 +244,10 @@ extern IndexTuple gist_form_invalid_tuple(BlockNumber blkno);
 
 extern XLogRecData* formUpdateRdata(RelFileNode node, BlockNumber blkno,
                 OffsetNumber *todelete, int ntodelete, bool emptypage,
-                IndexTuple *itup, int ituplen, ItemPointer key,
-                BlockNumber *path, int pathlen);
+                IndexTuple *itup, int ituplen, ItemPointer key);
 
 extern XLogRecData* formSplitRdata(RelFileNode node, BlockNumber blkno,
-                ItemPointer key,
-                BlockNumber *path, int pathlen, SplitedPageLayout *dist );
+                ItemPointer key, SplitedPageLayout *dist);
 
 extern XLogRecPtr gistxlogInsertCompletion(RelFileNode node, ItemPointerData *keys, int len);
 
@@ -243,7 +256,7 @@ extern Datum gistgettuple(PG_FUNCTION_ARGS);
 extern Datum gistgetmulti(PG_FUNCTION_ARGS);
 
 /* gistutil.c */
-extern	Buffer	gistReadBuffer(Relation r, BlockNumber blkno);
+extern	Buffer	gistNewBuffer(Relation r);
 extern OffsetNumber gistfillbuffer(Relation r, Page page, IndexTuple *itup,
                                 int len, OffsetNumber off);
 extern bool gistnospace(Page page, IndexTuple *itvec, int len);
diff --git a/src/include/access/gistscan.h b/src/include/access/gistscan.h
index 12a7a0ea73..8920f023fa 100644
--- a/src/include/access/gistscan.h
+++ b/src/include/access/gistscan.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/gistscan.h,v 1.26 2004/12/31 22:03:21 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/access/gistscan.h,v 1.27 2005/06/27 12:45:22 teodor Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -15,13 +15,14 @@
 #define GISTSCAN_H
 
 #include "access/relscan.h"
+#include "access/xlogdefs.h"
 
 extern Datum gistbeginscan(PG_FUNCTION_ARGS);
 extern Datum gistrescan(PG_FUNCTION_ARGS);
 extern Datum gistmarkpos(PG_FUNCTION_ARGS);
 extern Datum gistrestrpos(PG_FUNCTION_ARGS);
 extern Datum gistendscan(PG_FUNCTION_ARGS);
-extern void gistadjscans(Relation r, int op, BlockNumber blkno, OffsetNumber offnum);
+extern void gistadjscans(Relation r, int op, BlockNumber blkno, OffsetNumber offnum, XLogRecPtr newlsn, XLogRecPtr oldlsn);
 extern void ReleaseResources_gist(void);
 
 #endif   /* GISTSCAN_H */
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index ab1b6c0a5d..1e5c7ce0fa 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.281 2005/06/24 20:53:31 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.282 2005/06/27 12:45:22 teodor Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	200506241
+#define CATALOG_VERSION_NO	200506271
 
 #endif
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index b5ecdd9c73..0f05c48c84 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.36 2005/06/24 20:53:31 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.37 2005/06/27 12:45:23 teodor Exp $
  *
  * NOTES
  *		the genbki.sh script reads this file and generates .bki
@@ -112,7 +112,7 @@ DESCR("b-tree index access method");
 DATA(insert OID = 405 (  hash	1 1 0 f f f f t hashinsert hashbeginscan hashgettuple hashgetmulti hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbulkdelete - hashcostestimate ));
 DESCR("hash index access method");
 #define HASH_AM_OID 405
-DATA(insert OID = 783 (  gist	100 7 0 f t f f f gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate ));
+DATA(insert OID = 783 (  gist	100 7 0 f t f f t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate ));
 DESCR("GiST index access method");
 #define GIST_AM_OID 783