Replace "amgetmulti" AM functions with "amgetbitmap", in which the whole

indexscan always occurs in one call, and the results are returned in a
TIDBitmap instead of a limited-size array of TIDs.  This should improve
speed a little by reducing AM entry/exit overhead, and it is necessary
infrastructure if we are ever to support bitmap indexes.

In an only slightly related change, add support for TIDBitmaps to preserve
(somewhat lossily) the knowledge that particular TIDs reported by an index
need to have their quals rechecked when the heap is visited.  This facility
is not really used yet; we'll need to extend the forced-recheck feature to
plain indexscans before it's useful, and that hasn't been coded yet.
The intent is to use it to clean up 8.3's horrid @@@ kluge for text search
with weighted queries.  There might be other uses in future, but that one
alone is sufficient reason.

Heikki Linnakangas, with some adjustments by me.

9 files changed, 168 insertions, 189 deletions

diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 31464ab2bc3..4fb5ee556c5 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -8,13 +8,15 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *			$PostgreSQL: pgsql/src/backend/access/gin/ginget.c,v 1.10 2008/01/01 19:45:46 momjian Exp $
+ *			$PostgreSQL: pgsql/src/backend/access/gin/ginget.c,v 1.11 2008/04/10 22:25:25 tgl Exp $
  *-------------------------------------------------------------------------
  */
 
 #include "postgres.h"
+
 #include "access/gin.h"
 #include "catalog/index.h"
+#include "miscadmin.h"
 #include "utils/memutils.h"
 
 static bool
@@ -476,34 +478,37 @@ scanGetItem(IndexScanDesc scan, ItemPointerData *item)
 #define GinIsVoidRes(s)		( ((GinScanOpaque) scan->opaque)->isVoidRes == true )
 
 Datum
-gingetmulti(PG_FUNCTION_ARGS)
+gingetbitmap(PG_FUNCTION_ARGS)
 {
 	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
-	ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
-	int32		max_tids = PG_GETARG_INT32(2);
-	int32	   *returned_tids = (int32 *) PG_GETARG_POINTER(3);
+	TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
+	int64		ntids;
 
 	if (GinIsNewKey(scan))
 		newScanKey(scan);
 
-	*returned_tids = 0;
-
 	if (GinIsVoidRes(scan))
-		PG_RETURN_BOOL(false);
+		PG_RETURN_INT64(0);
 
 	startScan(scan);
 
-	do
+	ntids = 0;
+	for (;;)
 	{
-		if (scanGetItem(scan, tids + *returned_tids))
-			(*returned_tids)++;
-		else
+		ItemPointerData iptr;
+
+		CHECK_FOR_INTERRUPTS();
+
+		if (!scanGetItem(scan, &iptr))
 			break;
-	} while (*returned_tids < max_tids);
+
+		tbm_add_tuples(tbm, &iptr, 1, false);
+		ntids++;
+	}
 
 	stopScan(scan);
 
-	PG_RETURN_BOOL(*returned_tids == max_tids);
+	PG_RETURN_INT64(ntids);
 }
 
 Datum
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 22a7d0ceae6..4533ff8c85f 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.69 2008/01/01 19:45:46 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.70 2008/04/10 22:25:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,13 +16,16 @@
 
 #include "access/gist_private.h"
 #include "executor/execdebug.h"
+#include "miscadmin.h"
 #include "pgstat.h"
 #include "utils/memutils.h"
 
 
 static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n,
 			 ScanDirection dir);
-static int	gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples);
+static int64 gistnext(IndexScanDesc scan, ScanDirection dir,
+					  ItemPointer tid, TIDBitmap *tbm,
+					  bool ignore_killed_tuples);
 static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan,
 				  OffsetNumber offset);
 
@@ -114,32 +117,37 @@ gistgettuple(PG_FUNCTION_ARGS)
 	 * tuples, continue looping until we find a non-killed tuple that matches
 	 * the search key.
 	 */
-	res = (gistnext(scan, dir, &tid, 1, scan->ignore_killed_tuples)) ? true : false;
+	res = (gistnext(scan, dir, &tid, NULL, scan->ignore_killed_tuples) > 0) ? true : false;
 
 	PG_RETURN_BOOL(res);
 }
 
 Datum
-gistgetmulti(PG_FUNCTION_ARGS)
+gistgetbitmap(PG_FUNCTION_ARGS)
 {
 	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
-	ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
-	int32		max_tids = PG_GETARG_INT32(2);
-	int32	   *returned_tids = (int32 *) PG_GETARG_POINTER(3);
+	TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
+	int64	   ntids;
 
-	*returned_tids = gistnext(scan, ForwardScanDirection, tids, max_tids, false);
+	ntids = gistnext(scan, ForwardScanDirection, NULL, tbm, false);
 
-	PG_RETURN_BOOL(*returned_tids == max_tids);
+	PG_RETURN_INT64(ntids);
 }
 
 /*
- * Fetch a tuples that matchs the search key; this can be invoked
- * either to fetch the first such tuple or subsequent matching
- * tuples. Returns true iff a matching tuple was found.
+ * Fetch tuple(s) that match the search key; this can be invoked
+ * either to fetch the first such tuple or subsequent matching tuples.
+ *
+ * This function is used by both gistgettuple and gistgetbitmap. When
+ * invoked from gistgettuple, tbm is null and the next matching tuple
+ * is returned in *tid. When invoked from getbitmap, tid is null and
+ * all matching tuples are added to tbm. In both cases, the function
+ * result is the number of returned tuples.
  */
-static int
-gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
-		 int maxtids, bool ignore_killed_tuples)
+static int64
+gistnext(IndexScanDesc scan, ScanDirection dir,
+		 ItemPointer tid, TIDBitmap *tbm,
+		 bool ignore_killed_tuples)
 {
 	Page		p;
 	OffsetNumber n;
@@ -148,7 +156,7 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
 	IndexTuple	it;
 	GISTPageOpaque opaque;
 	bool		resetoffset = false;
-	int			ntids = 0;
+	int64		ntids = 0;
 
 	so = (GISTScanOpaque) scan->opaque;
 
@@ -174,6 +182,8 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
 
 	for (;;)
 	{
+		CHECK_FOR_INTERRUPTS();
+
 		/* First of all, we need lock buffer */
 		Assert(so->curbuf != InvalidBuffer);
 		LockBuffer(so->curbuf, GIST_SHARE);
@@ -285,20 +295,21 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
 				 * return success. Note that we keep "curbuf" pinned so that
 				 * we can efficiently resume the index scan later.
 				 */
-
 				ItemPointerSet(&(so->curpos),
 							   BufferGetBlockNumber(so->curbuf), n);
 
 				if (!(ignore_killed_tuples && ItemIdIsDead(PageGetItemId(p, n))))
 				{
 					it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
-					tids[ntids] = scan->xs_ctup.t_self = it->t_tid;
 					ntids++;
-
-					if (ntids == maxtids)
+					if (tbm != NULL)
+						tbm_add_tuples(tbm, &it->t_tid, 1, false);
+					else 
 					{
+						*tid = scan->xs_ctup.t_self = it->t_tid;
+
 						LockBuffer(so->curbuf, GIST_UNLOCK);
-						return ntids;
+						return ntids; /* always 1 */
 					}
 				}
 			}
@@ -308,7 +319,6 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
 				 * We've found an entry in an internal node whose key is
 				 * consistent with the search key, so push it to stack
 				 */
-
 				stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack));
 
 				it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
@@ -318,7 +328,6 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
 
 				stk->next = so->stack->next;
 				so->stack->next = stk;
-
 			}
 
 			if (ScanDirectionIsBackward(dir))
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c
index 01da35ec9f2..c090cfef8bb 100644
--- a/src/backend/access/hash/hash.c
+++ b/src/backend/access/hash/hash.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/hash/hash.c,v 1.100 2008/03/16 23:15:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/hash/hash.c,v 1.101 2008/04/10 22:25:25 tgl Exp $
  *
  * NOTES
  *	  This file contains only the public interface routines.
@@ -22,6 +22,7 @@
 #include "access/hash.h"
 #include "catalog/index.h"
 #include "commands/vacuum.h"
+#include "miscadmin.h"
 #include "optimizer/cost.h"
 #include "optimizer/plancat.h"
 
@@ -275,72 +276,51 @@ hashgettuple(PG_FUNCTION_ARGS)
 
 
 /*
- *	hashgetmulti() -- get multiple tuples at once
- *
- * This is a somewhat generic implementation: it avoids lock reacquisition
- * overhead, but there's no smarts about picking especially good stopping
- * points such as index page boundaries.
+ *	hashgetbitmap() -- get all tuples at once
  */
 Datum
-hashgetmulti(PG_FUNCTION_ARGS)
+hashgetbitmap(PG_FUNCTION_ARGS)
 {
 	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
-	ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
-	int32		max_tids = PG_GETARG_INT32(2);
-	int32	   *returned_tids = (int32 *) PG_GETARG_POINTER(3);
+	TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
 	HashScanOpaque so = (HashScanOpaque) scan->opaque;
-	Relation	rel = scan->indexRelation;
-	bool		res = true;
-	int32		ntids = 0;
+	bool		res;
+	int64		ntids = 0;
 
-	/*
-	 * We hold pin but not lock on current buffer while outside the hash AM.
-	 * Reacquire the read lock here.
-	 */
-	if (BufferIsValid(so->hashso_curbuf))
-		_hash_chgbufaccess(rel, so->hashso_curbuf, HASH_NOLOCK, HASH_READ);
+	res = _hash_first(scan, ForwardScanDirection);
 
-	while (ntids < max_tids)
+	while (res)
 	{
-		/*
-		 * Start scan, or advance to next tuple.
-		 */
-		if (ItemPointerIsValid(&(so->hashso_curpos)))
-			res = _hash_next(scan, ForwardScanDirection);
-		else
-			res = _hash_first(scan, ForwardScanDirection);
+		bool	add_tuple;
+
+		CHECK_FOR_INTERRUPTS();
 
 		/*
 		 * Skip killed tuples if asked to.
 		 */
 		if (scan->ignore_killed_tuples)
 		{
-			while (res)
-			{
-				Page		page;
-				OffsetNumber offnum;
-
-				offnum = ItemPointerGetOffsetNumber(&(so->hashso_curpos));
-				page = BufferGetPage(so->hashso_curbuf);
-				if (!ItemIdIsDead(PageGetItemId(page, offnum)))
-					break;
-				res = _hash_next(scan, ForwardScanDirection);
-			}
+			Page		page;
+			OffsetNumber offnum;
+
+			offnum = ItemPointerGetOffsetNumber(&(so->hashso_curpos));
+			page = BufferGetPage(so->hashso_curbuf);
+			add_tuple = !ItemIdIsDead(PageGetItemId(page, offnum));
 		}
+		else
+			add_tuple = true;
 
-		if (!res)
-			break;
 		/* Save tuple ID, and continue scanning */
-		tids[ntids] = scan->xs_ctup.t_self;
-		ntids++;
-	}
+		if (add_tuple) 
+		{
+			tbm_add_tuples(tbm, &scan->xs_ctup.t_self, 1, false);
+			ntids++;
+		}
 
-	/* Release read lock on current buffer, but keep it pinned */
-	if (BufferIsValid(so->hashso_curbuf))
-		_hash_chgbufaccess(rel, so->hashso_curbuf, HASH_READ, HASH_NOLOCK);
+		res = _hash_next(scan, ForwardScanDirection);
+	}
 
-	*returned_tids = ntids;
-	PG_RETURN_BOOL(res);
+	PG_RETURN_INT64(ntids);
 }
 
 
diff --git a/src/backend/access/index/genam.c b/src/backend/access/index/genam.c
index a4395cb240e..8877938322d 100644
--- a/src/backend/access/index/genam.c
+++ b/src/backend/access/index/genam.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/index/genam.c,v 1.65 2008/03/26 21:10:37 alvherre Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/index/genam.c,v 1.66 2008/04/10 22:25:25 tgl Exp $
  *
  * NOTES
  *	  many of the old access method routines have been turned into
@@ -88,7 +88,6 @@ RelationGetIndexScan(Relation indexRelation,
 	else
 		scan->keyData = NULL;
 
-	scan->is_multiscan = false; /* caller may change this */
 	scan->kill_prior_tuple = false;
 	scan->ignore_killed_tuples = true;	/* default setting */
 
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index c4739aa1cd1..d59f1529db1 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -8,20 +8,20 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.104 2008/03/26 21:10:37 alvherre Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.105 2008/04/10 22:25:25 tgl Exp $
  *
  * INTERFACE ROUTINES
  *		index_open		- open an index relation by relation OID
  *		index_close		- close an index relation
  *		index_beginscan - start a scan of an index with amgettuple
- *		index_beginscan_multi - start a scan of an index with amgetmulti
+ *		index_beginscan_bitmap - start a scan of an index with amgetbitmap
  *		index_rescan	- restart a scan of an index
  *		index_endscan	- end a scan
  *		index_insert	- insert an index tuple into a relation
  *		index_markpos	- mark a scan position
  *		index_restrpos	- restore a scan position
  *		index_getnext	- get the next tuple from a scan
- *		index_getmulti	- get multiple tuples from a scan
+ *		index_getbitmap	- get all tuples from a scan
  *		index_bulk_delete	- bulk deletion of index tuples
  *		index_vacuum_cleanup	- post-deletion cleanup of an index
  *		index_getprocid - get a support procedure OID
@@ -227,7 +227,6 @@ index_beginscan(Relation heapRelation,
 	 * Save additional parameters into the scandesc.  Everything else was set
 	 * up by RelationGetIndexScan.
 	 */
-	scan->is_multiscan = false;
 	scan->heapRelation = heapRelation;
 	scan->xs_snapshot = snapshot;
 
@@ -235,15 +234,15 @@ index_beginscan(Relation heapRelation,
 }
 
 /*
- * index_beginscan_multi - start a scan of an index with amgetmulti
+ * index_beginscan_bitmap - start a scan of an index with amgetbitmap
  *
  * As above, caller had better be holding some lock on the parent heap
  * relation, even though it's not explicitly mentioned here.
  */
 IndexScanDesc
-index_beginscan_multi(Relation indexRelation,
-					  Snapshot snapshot,
-					  int nkeys, ScanKey key)
+index_beginscan_bitmap(Relation indexRelation,
+					   Snapshot snapshot,
+					   int nkeys, ScanKey key)
 {
 	IndexScanDesc scan;
 
@@ -253,7 +252,6 @@ index_beginscan_multi(Relation indexRelation,
 	 * Save additional parameters into the scandesc.  Everything else was set
 	 * up by RelationGetIndexScan.
 	 */
-	scan->is_multiscan = true;
 	scan->xs_snapshot = snapshot;
 
 	return scan;
@@ -676,44 +674,39 @@ index_getnext_indexitem(IndexScanDesc scan,
 }
 
 /* ----------------
- *		index_getmulti - get multiple tuples from an index scan
+ *		index_getbitmap - get all tuples at once from an index scan
  *
- * Collects the TIDs of multiple heap tuples satisfying the scan keys.
+ * Adds the TIDs of all heap tuples satisfying the scan keys to a bitmap.
  * Since there's no interlock between the index scan and the eventual heap
  * access, this is only safe to use with MVCC-based snapshots: the heap
  * item slot could have been replaced by a newer tuple by the time we get
  * to it.
  *
- * A TRUE result indicates more calls should occur; a FALSE result says the
- * scan is done.  *returned_tids could be zero or nonzero in either case.
+ * Returns the number of matching tuples found.
  * ----------------
  */
-bool
-index_getmulti(IndexScanDesc scan,
-			   ItemPointer tids, int32 max_tids,
-			   int32 *returned_tids)
+int64
+index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap)
 {
 	FmgrInfo   *procedure;
-	bool		found;
+	int64		ntids;
 
 	SCAN_CHECKS;
-	GET_SCAN_PROCEDURE(amgetmulti);
+	GET_SCAN_PROCEDURE(amgetbitmap);
 
 	/* just make sure this is false... */
 	scan->kill_prior_tuple = false;
 
 	/*
-	 * have the am's getmulti proc do all the work.
+	 * have the am's getbitmap proc do all the work.
 	 */
-	found = DatumGetBool(FunctionCall4(procedure,
-									   PointerGetDatum(scan),
-									   PointerGetDatum(tids),
-									   Int32GetDatum(max_tids),
-									   PointerGetDatum(returned_tids)));
+	ntids = DatumGetInt64(FunctionCall2(procedure,
+										PointerGetDatum(scan),
+										PointerGetDatum(bitmap)));
 
-	pgstat_count_index_tuples(scan->indexRelation, *returned_tids);
+	pgstat_count_index_tuples(scan->indexRelation, ntids);
 
-	return found;
+	return ntids;
 }
 
 /* ----------------
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 5cfa8f315d7..d96348ace46 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -12,7 +12,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.156 2008/01/01 19:45:46 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.157 2008/04/10 22:25:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -22,6 +22,7 @@
 #include "access/nbtree.h"
 #include "catalog/index.h"
 #include "commands/vacuum.h"
+#include "miscadmin.h"
 #include "storage/freespace.h"
 #include "storage/lmgr.h"
 #include "utils/memutils.h"
@@ -278,42 +279,29 @@ btgettuple(PG_FUNCTION_ARGS)
 }
 
 /*
- * btgetmulti() -- get multiple tuples at once
- *
- * In the current implementation there seems no strong reason to stop at
- * index page boundaries; we just press on until we fill the caller's buffer
- * or run out of matches.
+ * btgetbitmap() -- gets all matching tuples, and adds them to a bitmap
  */
 Datum
-btgetmulti(PG_FUNCTION_ARGS)
+btgetbitmap(PG_FUNCTION_ARGS)
 {
 	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
-	ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
-	int32		max_tids = PG_GETARG_INT32(2);
-	int32	   *returned_tids = (int32 *) PG_GETARG_POINTER(3);
+	TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
-	bool		res = true;
-	int32		ntids = 0;
-
-	if (max_tids <= 0)			/* behave correctly in boundary case */
-		PG_RETURN_BOOL(true);
+	int64		ntids = 0;
+	ItemPointer heapTid;
 
-	/* If we haven't started the scan yet, fetch the first page & tuple. */
-	if (!BTScanPosIsValid(so->currPos))
+	/* Fetch the first page & tuple. */
+	if (!_bt_first(scan, ForwardScanDirection))
 	{
-		res = _bt_first(scan, ForwardScanDirection);
-		if (!res)
-		{
-			/* empty scan */
-			*returned_tids = ntids;
-			PG_RETURN_BOOL(res);
-		}
-		/* Save tuple ID, and continue scanning */
-		tids[ntids] = scan->xs_ctup.t_self;
-		ntids++;
+		/* empty scan */
+		PG_RETURN_INT64(0);
 	}
+	/* Save tuple ID, and continue scanning */
+	heapTid = &scan->xs_ctup.t_self;
+	tbm_add_tuples(tbm, heapTid, 1, false);
+	ntids++;
 
-	while (ntids < max_tids)
+	for (;;)
 	{
 		/*
 		 * Advance to next tuple within page.  This is the same as the easy
@@ -321,19 +309,20 @@ btgetmulti(PG_FUNCTION_ARGS)
 		 */
 		if (++so->currPos.itemIndex > so->currPos.lastItem)
 		{
+			CHECK_FOR_INTERRUPTS();
+
 			/* let _bt_next do the heavy lifting */
-			res = _bt_next(scan, ForwardScanDirection);
-			if (!res)
+			if (!_bt_next(scan, ForwardScanDirection))
 				break;
 		}
 
 		/* Save tuple ID, and continue scanning */
-		tids[ntids] = so->currPos.items[so->currPos.itemIndex].heapTid;
+		heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid;
+		tbm_add_tuples(tbm, heapTid, 1, false);
 		ntids++;
 	}
 
-	*returned_tids = ntids;
-	PG_RETURN_BOOL(res);
+	PG_RETURN_INT64(ntids);
 }
 
 /*
diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c
index 998ef91097d..3908892bc2a 100644
--- a/src/backend/executor/nodeBitmapHeapscan.c
+++ b/src/backend/executor/nodeBitmapHeapscan.c
@@ -21,7 +21,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapHeapscan.c,v 1.25 2008/03/26 21:10:38 alvherre Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapHeapscan.c,v 1.26 2008/04/10 22:25:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -206,7 +206,7 @@ BitmapHeapNext(BitmapHeapScanState *node)
 		 * If we are using lossy info, we have to recheck the qual conditions
 		 * at every tuple.
 		 */
-		if (tbmres->ntuples < 0)
+		if (tbmres->recheck)
 		{
 			econtext->ecxt_scantuple = slot;
 			ResetExprContext(econtext);
diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c
index fd56e862df6..a2b2700723c 100644
--- a/src/backend/executor/nodeBitmapIndexscan.c
+++ b/src/backend/executor/nodeBitmapIndexscan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.25 2008/01/01 19:45:49 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.26 2008/04/10 22:25:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -37,11 +37,8 @@
 Node *
 MultiExecBitmapIndexScan(BitmapIndexScanState *node)
 {
-#define MAX_TIDS	1024
 	TIDBitmap  *tbm;
 	IndexScanDesc scandesc;
-	ItemPointerData tids[MAX_TIDS];
-	int32		ntids;
 	double		nTuples = 0;
 	bool		doscan;
 
@@ -91,23 +88,14 @@ MultiExecBitmapIndexScan(BitmapIndexScanState *node)
 	 */
 	while (doscan)
 	{
-		bool		more = index_getmulti(scandesc, tids, MAX_TIDS, &ntids);
-
-		if (ntids > 0)
-		{
-			tbm_add_tuples(tbm, tids, ntids);
-			nTuples += ntids;
-		}
+		nTuples += (double) index_getbitmap(scandesc, tbm);
 
 		CHECK_FOR_INTERRUPTS();
 
-		if (!more)
-		{
-			doscan = ExecIndexAdvanceArrayKeys(node->biss_ArrayKeys,
-											   node->biss_NumArrayKeys);
-			if (doscan)			/* reset index scan */
-				index_rescan(node->biss_ScanDesc, node->biss_ScanKeys);
-		}
+		doscan = ExecIndexAdvanceArrayKeys(node->biss_ArrayKeys,
+										   node->biss_NumArrayKeys);
+		if (doscan)			/* reset index scan */
+			index_rescan(node->biss_ScanDesc, node->biss_ScanKeys);
 	}
 
 	/* must provide our own instrumentation support */
@@ -321,10 +309,10 @@ ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate, int eflags)
 	 * Initialize scan descriptor.
 	 */
 	indexstate->biss_ScanDesc =
-		index_beginscan_multi(indexstate->biss_RelationDesc,
-							  estate->es_snapshot,
-							  indexstate->biss_NumScanKeys,
-							  indexstate->biss_ScanKeys);
+		index_beginscan_bitmap(indexstate->biss_RelationDesc,
+							   estate->es_snapshot,
+							   indexstate->biss_NumScanKeys,
+							   indexstate->biss_ScanKeys);
 
 	/*
 	 * all done.
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index 18a260675a4..37a2b4bfae7 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -19,11 +19,20 @@
  * of lossiness.  In theory we could fall back to page ranges at some
  * point, but for now that seems useless complexity.
  *
+ * We also support the notion of candidate matches, or rechecking.  This
+ * means we know that a search need visit only some tuples on a page,
+ * but we are not certain that all of those tuples are real matches.
+ * So the eventual heap scan must recheck the quals for these tuples only,
+ * rather than rechecking the quals for all tuples on the page as in the
+ * lossy-bitmap case.  Rechecking can be specified when TIDs are inserted
+ * into a bitmap, and it can also happen internally when we AND a lossy
+ * and a non-lossy page.
+ *
  *
  * Copyright (c) 2003-2008, PostgreSQL Global Development Group
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/tidbitmap.c,v 1.14 2008/01/01 19:45:50 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/tidbitmap.c,v 1.15 2008/04/10 22:25:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -81,11 +90,16 @@
  * have exact storage for the first page of a chunk if we are using
  * lossy storage for any page in the chunk's range, since the same
  * hashtable entry has to serve both purposes.
+ *
+ * recheck is used only on exact pages --- it indicates that although
+ * only the stated tuples need be checked, the full index qual condition
+ * must be checked for each (ie, these are candidate matches).
  */
 typedef struct PagetableEntry
 {
 	BlockNumber blockno;		/* page number (hashtable key) */
 	bool		ischunk;		/* T = lossy storage, F = exact */
+	bool		recheck;		/* should the tuples be rechecked? */
 	bitmapword	words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
 } PagetableEntry;
 
@@ -244,9 +258,13 @@ tbm_free(TIDBitmap *tbm)
 
 /*
  * tbm_add_tuples - add some tuple IDs to a TIDBitmap
+ *
+ * If recheck is true, then the recheck flag will be set in the
+ * TBMIterateResult when any of these tuples are reported out.
  */
 void
-tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids)
+tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids,
+			   bool recheck)
 {
 	int			i;
 
@@ -280,6 +298,7 @@ tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids)
 			bitnum = BITNUM(off - 1);
 		}
 		page->words[wordnum] |= ((bitmapword) 1 << bitnum);
+		page->recheck |= recheck;
 
 		if (tbm->nentries > tbm->maxentries)
 			tbm_lossify(tbm);
@@ -360,6 +379,7 @@ tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
 			/* Both pages are exact, merge at the bit level */
 			for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
 				apage->words[wordnum] |= bpage->words[wordnum];
+			apage->recheck |= bpage->recheck;
 		}
 	}
 
@@ -471,22 +491,12 @@ tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
 	else if (tbm_page_is_lossy(b, apage->blockno))
 	{
 		/*
-		 * When the page is lossy in b, we have to mark it lossy in a too. We
-		 * know that no bits need be set in bitmap a, but we do not know which
-		 * ones should be cleared, and we have no API for "at most these
-		 * tuples need be checked".  (Perhaps it's worth adding that?)
-		 */
-		tbm_mark_page_lossy(a, apage->blockno);
-
-		/*
-		 * Note: tbm_mark_page_lossy will have removed apage from a, and may
-		 * have inserted a new lossy chunk instead.  We can continue the same
-		 * seq_search scan at the caller level, because it does not matter
-		 * whether we visit such a new chunk or not: it will have only the bit
-		 * for apage->blockno set, which is correct.
-		 *
-		 * We must return false here since apage was already deleted.
+		 * Some of the tuples in 'a' might not satisfy the quals for 'b',
+		 * but because the page 'b' is lossy, we don't know which ones. 
+		 * Therefore we mark 'a' as requiring rechecks, to indicate that
+		 * at most those tuples set in 'a' are matches.
 		 */
+		apage->recheck = true;
 		return false;
 	}
 	else
@@ -504,7 +514,9 @@ tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
 				if (apage->words[wordnum] != 0)
 					candelete = false;
 			}
+			apage->recheck |= bpage->recheck;
 		}
+		/* If there is no matching b page, we can just delete the a page */
 		return candelete;
 	}
 }
@@ -585,7 +597,9 @@ tbm_begin_iterate(TIDBitmap *tbm)
  * order.  If result->ntuples < 0, then the bitmap is "lossy" and failed to
  * remember the exact tuples to look at on this page --- the caller must
  * examine all tuples on the page and check if they meet the intended
- * condition.
+ * condition.  If result->recheck is true, only the indicated tuples need
+ * be examined, but the condition must be rechecked anyway.  (For ease of
+ * testing, recheck is always set true when ntuples < 0.)
  */
 TBMIterateResult *
 tbm_iterate(TIDBitmap *tbm)
@@ -638,6 +652,7 @@ tbm_iterate(TIDBitmap *tbm)
 			/* Return a lossy page indicator from the chunk */
 			output->blockno = chunk_blockno;
 			output->ntuples = -1;
+			output->recheck = true;
 			tbm->schunkbit++;
 			return output;
 		}
@@ -676,6 +691,7 @@ tbm_iterate(TIDBitmap *tbm)
 		}
 		output->blockno = page->blockno;
 		output->ntuples = ntuples;
+		output->recheck = page->recheck;
 		tbm->spageptr++;
 		return output;
 	}