Rewrite btree index scans to work a page at a time in all cases (both

btgettuple and btgetmulti).  This eliminates the problem of "re-finding" the
exact stopping point, since the stopping point is effectively always a page
boundary, and index items are never moved across pre-existing page boundaries.
A small penalty is that the keys_are_unique optimization is effectively
disabled (and, therefore, is removed in this patch), causing us to apply
_bt_checkkeys() to at least one more tuple than necessary when looking up a
unique key.  However, the advantages for non-unique cases seem great enough to
accept this tradeoff.  Aside from simplifying and (sometimes) speeding up the
indexscan code, this will allow us to reimplement btbulkdelete as a largely
sequential scan instead of index-order traversal, thereby significantly
reducing the cost of VACUUM.  Those changes will come in a separate patch.

Original patch by Heikki Linnakangas, rework by Tom Lane.

1 files changed, 4 insertions, 85 deletions

diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index b54364acb6d..900b34263d8 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.92 2006/05/02 22:25:10 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.93 2006/05/07 01:21:30 tgl Exp $
  *
  * INTERFACE ROUTINES
  *		index_open		- open an index relation by relation OID
@@ -362,10 +362,6 @@ index_rescan(IndexScanDesc scan, ScanKey key)
 	}
 
 	scan->kill_prior_tuple = false;		/* for safety */
-	scan->keys_are_unique = false;		/* may be set by index AM */
-	scan->got_tuple = false;
-	scan->unique_tuple_pos = 0;
-	scan->unique_tuple_mark = 0;
 
 	FunctionCall2(procedure,
 				  PointerGetDatum(scan),
@@ -417,8 +413,6 @@ index_markpos(IndexScanDesc scan)
 	SCAN_CHECKS;
 	GET_SCAN_PROCEDURE(ammarkpos);
 
-	scan->unique_tuple_mark = scan->unique_tuple_pos;
-
 	FunctionCall1(procedure, PointerGetDatum(scan));
 }
 
@@ -440,13 +434,6 @@ index_restrpos(IndexScanDesc scan)
 
 	scan->kill_prior_tuple = false;		/* for safety */
 
-	/*
-	 * We do not reset got_tuple; so if the scan is actually being
-	 * short-circuited by index_getnext, the effective position restoration is
-	 * done by restoring unique_tuple_pos.
-	 */
-	scan->unique_tuple_pos = scan->unique_tuple_mark;
-
 	FunctionCall1(procedure, PointerGetDatum(scan));
 }
 
@@ -456,8 +443,7 @@ index_restrpos(IndexScanDesc scan)
  * The result is the next heap tuple satisfying the scan keys and the
  * snapshot, or NULL if no more matching tuples exist.	On success,
  * the buffer containing the heap tuple is pinned (the pin will be dropped
- * at the next index_getnext or index_endscan).  The index TID corresponding
- * to the heap tuple can be obtained if needed from scan->currentItemData.
+ * at the next index_getnext or index_endscan).
  * ----------------
  */
 HeapTuple
@@ -469,65 +455,6 @@ index_getnext(IndexScanDesc scan, ScanDirection direction)
 	SCAN_CHECKS;
 	GET_SCAN_PROCEDURE(amgettuple);
 
-	/*
-	 * If we already got a tuple and it must be unique, there's no need to
-	 * make the index AM look through any additional tuples.  (This can save a
-	 * useful amount of work in scenarios where there are many dead tuples due
-	 * to heavy update activity.)
-	 *
-	 * To do this we must keep track of the logical scan position
-	 * (before/on/after tuple).  Also, we have to be sure to release scan
-	 * resources before returning NULL; if we fail to do so then a multi-index
-	 * scan can easily run the system out of free buffers.	We can release
-	 * index-level resources fairly cheaply by calling index_rescan.  This
-	 * means there are two persistent states as far as the index AM is
-	 * concerned: on-tuple and rescanned.  If we are actually asked to
-	 * re-fetch the single tuple, we have to go through a fresh indexscan
-	 * startup, which penalizes that (infrequent) case.
-	 */
-	if (scan->keys_are_unique && scan->got_tuple)
-	{
-		int			new_tuple_pos = scan->unique_tuple_pos;
-
-		if (ScanDirectionIsForward(direction))
-		{
-			if (new_tuple_pos <= 0)
-				new_tuple_pos++;
-		}
-		else
-		{
-			if (new_tuple_pos >= 0)
-				new_tuple_pos--;
-		}
-		if (new_tuple_pos == 0)
-		{
-			/*
-			 * We are moving onto the unique tuple from having been off it. We
-			 * just fall through and let the index AM do the work. Note we
-			 * should get the right answer regardless of scan direction.
-			 */
-			scan->unique_tuple_pos = 0; /* need to update position */
-		}
-		else
-		{
-			/*
-			 * Moving off the tuple; must do amrescan to release index-level
-			 * pins before we return NULL.	Since index_rescan will reset my
-			 * state, must save and restore...
-			 */
-			int			unique_tuple_mark = scan->unique_tuple_mark;
-
-			index_rescan(scan, NULL /* no change to key */ );
-
-			scan->keys_are_unique = true;
-			scan->got_tuple = true;
-			scan->unique_tuple_pos = new_tuple_pos;
-			scan->unique_tuple_mark = unique_tuple_mark;
-
-			return NULL;
-		}
-	}
-
 	/* just make sure this is false... */
 	scan->kill_prior_tuple = false;
 
@@ -588,14 +515,6 @@ index_getnext(IndexScanDesc scan, ScanDirection direction)
 	}
 
 	/* Success exit */
-	scan->got_tuple = true;
-
-	/*
-	 * If we just fetched a known-unique tuple, then subsequent calls will go
-	 * through the short-circuit code above.  unique_tuple_pos has been
-	 * initialized to 0, which is the correct state ("on row").
-	 */
-
 	return heapTuple;
 }
 
@@ -608,8 +527,8 @@ index_getnext(IndexScanDesc scan, ScanDirection direction)
  * (which most callers of this routine will probably want to suppress by
  * setting scan->ignore_killed_tuples = false).
  *
- * On success (TRUE return), the found index TID is in scan->currentItemData,
- * and its heap TID is in scan->xs_ctup.t_self.  scan->xs_cbuf is untouched.
+ * On success (TRUE return), the heap TID of the found index entry is in
+ * scan->xs_ctup.t_self.  scan->xs_cbuf is untouched.
  * ----------------
  */
 bool