Create executor and planner-backend support for decoupled heap and index

scans, using in-memory tuple ID bitmaps as the intermediary.  The planner
frontend (path creation and cost estimation) is not there yet, so none
of this code can be executed.  I have tested it using some hacked planner
code that is far too ugly to see the light of day, however.  Committing
now so that the bulk of the infrastructure changes go in before the tree
drifts under me.

7 files changed, 1532 insertions, 4 deletions

diff --git a/src/backend/executor/Makefile b/src/backend/executor/Makefile
index 7c0bc25352c..e9caf7d8373 100644
--- a/src/backend/executor/Makefile
+++ b/src/backend/executor/Makefile
@@ -4,7 +4,7 @@
 #    Makefile for executor
 #
 # IDENTIFICATION
-#    $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.22 2003/11/29 19:51:48 pgsql Exp $
+#    $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.23 2005/04/19 22:35:11 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -14,7 +14,9 @@ include $(top_builddir)/src/Makefile.global
 
 OBJS = execAmi.o execGrouping.o execJunk.o execMain.o \
        execProcnode.o execQual.o execScan.o execTuples.o \
-       execUtils.o functions.o instrument.o nodeAppend.o nodeAgg.o nodeHash.o \
+       execUtils.o functions.o instrument.o nodeAppend.o nodeAgg.o \
+       nodeBitmapAnd.o nodeBitmapOr.o \
+       nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \
        nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \
        nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeSeqscan.o \
        nodeSetOp.o nodeSort.o nodeUnique.o nodeLimit.o nodeGroup.o \
diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c
index 008768c3942..ddcd37ae286 100644
--- a/src/backend/executor/execAmi.c
+++ b/src/backend/executor/execAmi.c
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- *	$PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.82 2004/12/31 21:59:45 pgsql Exp $
+ *	$PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.83 2005/04/19 22:35:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,10 @@
 #include "executor/instrument.h"
 #include "executor/nodeAgg.h"
 #include "executor/nodeAppend.h"
+#include "executor/nodeBitmapAnd.h"
+#include "executor/nodeBitmapHeapscan.h"
+#include "executor/nodeBitmapIndexscan.h"
+#include "executor/nodeBitmapOr.h"
 #include "executor/nodeFunctionscan.h"
 #include "executor/nodeGroup.h"
 #include "executor/nodeGroup.h"
@@ -107,6 +111,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt)
 			ExecReScanAppend((AppendState *) node, exprCtxt);
 			break;
 
+		case T_BitmapAndState:
+			ExecReScanBitmapAnd((BitmapAndState *) node, exprCtxt);
+			break;
+
+		case T_BitmapOrState:
+			ExecReScanBitmapOr((BitmapOrState *) node, exprCtxt);
+			break;
+
 		case T_SeqScanState:
 			ExecSeqReScan((SeqScanState *) node, exprCtxt);
 			break;
@@ -115,6 +127,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt)
 			ExecIndexReScan((IndexScanState *) node, exprCtxt);
 			break;
 
+		case T_BitmapIndexScanState:
+			ExecBitmapIndexReScan((BitmapIndexScanState *) node, exprCtxt);
+			break;
+
+		case T_BitmapHeapScanState:
+			ExecBitmapHeapReScan((BitmapHeapScanState *) node, exprCtxt);
+			break;
+
 		case T_TidScanState:
 			ExecTidReScan((TidScanState *) node, exprCtxt);
 			break;
@@ -380,6 +400,7 @@ ExecMayReturnRawTuples(PlanState *node)
 			/* Table scan nodes */
 		case T_SeqScanState:
 		case T_IndexScanState:
+		case T_BitmapHeapScanState:
 		case T_TidScanState:
 		case T_SubqueryScanState:
 		case T_FunctionScanState:
diff --git a/src/backend/executor/execProcnode.c b/src/backend/executor/execProcnode.c
index 555668e7799..28f67a2562f 100644
--- a/src/backend/executor/execProcnode.c
+++ b/src/backend/executor/execProcnode.c
@@ -12,7 +12,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.49 2005/04/16 20:07:35 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.50 2005/04/19 22:35:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -81,6 +81,10 @@
 #include "executor/instrument.h"
 #include "executor/nodeAgg.h"
 #include "executor/nodeAppend.h"
+#include "executor/nodeBitmapAnd.h"
+#include "executor/nodeBitmapHeapscan.h"
+#include "executor/nodeBitmapIndexscan.h"
+#include "executor/nodeBitmapOr.h"
 #include "executor/nodeFunctionscan.h"
 #include "executor/nodeGroup.h"
 #include "executor/nodeHash.h"
@@ -140,6 +144,14 @@ ExecInitNode(Plan *node, EState *estate)
 			result = (PlanState *) ExecInitAppend((Append *) node, estate);
 			break;
 
+		case T_BitmapAnd:
+			result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node, estate);
+			break;
+
+		case T_BitmapOr:
+			result = (PlanState *) ExecInitBitmapOr((BitmapOr *) node, estate);
+			break;
+
 			/*
 			 * scan nodes
 			 */
@@ -151,6 +163,14 @@ ExecInitNode(Plan *node, EState *estate)
 			result = (PlanState *) ExecInitIndexScan((IndexScan *) node, estate);
 			break;
 
+		case T_BitmapIndexScan:
+			result = (PlanState *) ExecInitBitmapIndexScan((BitmapIndexScan *) node, estate);
+			break;
+
+		case T_BitmapHeapScan:
+			result = (PlanState *) ExecInitBitmapHeapScan((BitmapHeapScan *) node, estate);
+			break;
+
 		case T_TidScan:
 			result = (PlanState *) ExecInitTidScan((TidScan *) node, estate);
 			break;
@@ -290,6 +310,10 @@ ExecProcNode(PlanState *node)
 			result = ExecAppend((AppendState *) node);
 			break;
 
+			/* BitmapAndState does not yield tuples */
+
+			/* BitmapOrState does not yield tuples */
+
 			/*
 			 * scan nodes
 			 */
@@ -301,6 +325,12 @@ ExecProcNode(PlanState *node)
 			result = ExecIndexScan((IndexScanState *) node);
 			break;
 
+			/* BitmapIndexScanState does not yield tuples */
+
+		case T_BitmapHeapScanState:
+			result = ExecBitmapHeapScan((BitmapHeapScanState *) node);
+			break;
+
 		case T_TidScanState:
 			result = ExecTidScan((TidScanState *) node);
 			break;
@@ -409,6 +439,18 @@ MultiExecProcNode(PlanState *node)
 			result = MultiExecHash((HashState *) node);
 			break;
 
+		case T_BitmapIndexScanState:
+			result = MultiExecBitmapIndexScan((BitmapIndexScanState *) node);
+			break;
+
+		case T_BitmapAndState:
+			result = MultiExecBitmapAnd((BitmapAndState *) node);
+			break;
+
+		case T_BitmapOrState:
+			result = MultiExecBitmapOr((BitmapOrState *) node);
+			break;
+
 		default:
 			elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
 			result = NULL;
@@ -442,6 +484,12 @@ ExecCountSlotsNode(Plan *node)
 		case T_Append:
 			return ExecCountSlotsAppend((Append *) node);
 
+		case T_BitmapAnd:
+			return ExecCountSlotsBitmapAnd((BitmapAnd *) node);
+
+		case T_BitmapOr:
+			return ExecCountSlotsBitmapOr((BitmapOr *) node);
+
 			/*
 			 * scan nodes
 			 */
@@ -451,6 +499,12 @@ ExecCountSlotsNode(Plan *node)
 		case T_IndexScan:
 			return ExecCountSlotsIndexScan((IndexScan *) node);
 
+		case T_BitmapIndexScan:
+			return ExecCountSlotsBitmapIndexScan((BitmapIndexScan *) node);
+
+		case T_BitmapHeapScan:
+			return ExecCountSlotsBitmapHeapScan((BitmapHeapScan *) node);
+
 		case T_TidScan:
 			return ExecCountSlotsTidScan((TidScan *) node);
 
@@ -554,6 +608,14 @@ ExecEndNode(PlanState *node)
 			ExecEndAppend((AppendState *) node);
 			break;
 
+		case T_BitmapAndState:
+			ExecEndBitmapAnd((BitmapAndState *) node);
+			break;
+
+		case T_BitmapOrState:
+			ExecEndBitmapOr((BitmapOrState *) node);
+			break;
+
 			/*
 			 * scan nodes
 			 */
@@ -565,6 +627,14 @@ ExecEndNode(PlanState *node)
 			ExecEndIndexScan((IndexScanState *) node);
 			break;
 
+		case T_BitmapIndexScanState:
+			ExecEndBitmapIndexScan((BitmapIndexScanState *) node);
+			break;
+
+		case T_BitmapHeapScanState:
+			ExecEndBitmapHeapScan((BitmapHeapScanState *) node);
+			break;
+
 		case T_TidScanState:
 			ExecEndTidScan((TidScanState *) node);
 			break;
diff --git a/src/backend/executor/nodeBitmapAnd.c b/src/backend/executor/nodeBitmapAnd.c
new file mode 100644
index 00000000000..4af1624012b
--- /dev/null
+++ b/src/backend/executor/nodeBitmapAnd.c
@@ -0,0 +1,208 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapAnd.c
+ *	  routines to handle BitmapAnd nodes.
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapAnd.c,v 1.1 2005/04/19 22:35:12 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+/* INTERFACE ROUTINES
+ *		ExecInitBitmapAnd	- initialize the BitmapAnd node
+ *		MultiExecBitmapAnd	- retrieve the result bitmap from the node
+ *		ExecEndBitmapAnd	- shut down the BitmapAnd node
+ *		ExecReScanBitmapAnd	- rescan the BitmapAnd node
+ *
+ *	 NOTES
+ *		BitmapAnd nodes don't make use of their left and right
+ *		subtrees, rather they maintain a list of subplans,
+ *		much like Append nodes.  The logic is much simpler than
+ *		Append, however, since we needn't cope with forward/backward
+ *		execution.
+ */
+
+#include "postgres.h"
+
+#include "executor/execdebug.h"
+#include "executor/instrument.h"
+#include "executor/nodeBitmapAnd.h"
+
+
+/* ----------------------------------------------------------------
+ *		ExecInitBitmapAnd
+ *
+ *		Begin all of the subscans of the BitmapAnd node.
+ * ----------------------------------------------------------------
+ */
+BitmapAndState *
+ExecInitBitmapAnd(BitmapAnd *node, EState *estate)
+{
+	BitmapAndState *bitmapandstate = makeNode(BitmapAndState);
+	PlanState **bitmapplanstates;
+	int			nplans;
+	int			i;
+	Plan	   *initNode;
+
+	CXT1_printf("ExecInitBitmapAnd: context is %d\n", CurrentMemoryContext);
+
+	/*
+	 * Set up empty vector of subplan states
+	 */
+	nplans = list_length(node->bitmapplans);
+
+	bitmapplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *));
+
+	/*
+	 * create new BitmapAndState for our BitmapAnd node
+	 */
+	bitmapandstate->ps.plan = (Plan *) node;
+	bitmapandstate->ps.state = estate;
+	bitmapandstate->bitmapplans = bitmapplanstates;
+	bitmapandstate->nplans = nplans;
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * BitmapAnd plans don't have expression contexts because they never call
+	 * ExecQual or ExecProject.  They don't need any tuple slots either.
+	 */
+
+#define BITMAPAND_NSLOTS 0
+
+	/*
+	 * call ExecInitNode on each of the plans to be executed and save the
+	 * results into the array "bitmapplanstates".
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		initNode = (Plan *) list_nth(node->bitmapplans, i);
+		bitmapplanstates[i] = ExecInitNode(initNode, estate);
+	}
+
+	return bitmapandstate;
+}
+
+int
+ExecCountSlotsBitmapAnd(BitmapAnd *node)
+{
+	ListCell   *plan;
+	int			nSlots = 0;
+
+	foreach(plan, node->bitmapplans)
+		nSlots += ExecCountSlotsNode((Plan *) lfirst(plan));
+	return nSlots + BITMAPAND_NSLOTS;
+}
+
+/* ----------------------------------------------------------------
+ *	   MultiExecBitmapAnd
+ * ----------------------------------------------------------------
+ */
+Node *
+MultiExecBitmapAnd(BitmapAndState *node)
+{
+	PlanState **bitmapplans;
+	int			nplans;
+	int			i;
+	TIDBitmap  *result = NULL;
+
+	/* must provide our own instrumentation support */
+	if (node->ps.instrument)
+		InstrStartNode(node->ps.instrument);
+
+	/*
+	 * get information from the node
+	 */
+	bitmapplans = node->bitmapplans;
+	nplans = node->nplans;
+
+	/*
+	 * Scan all the subplans and AND their result bitmaps
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		PlanState  *subnode = bitmapplans[i];
+		TIDBitmap  *subresult;
+
+		subresult = (TIDBitmap *) MultiExecProcNode(subnode);
+
+		if (!subresult || !IsA(subresult, TIDBitmap))
+			elog(ERROR, "unrecognized result from subplan");
+
+		if (result == NULL)
+			result = subresult;			/* first subplan */
+		else
+		{
+			tbm_intersect(result, subresult);
+			tbm_free(subresult);
+		}
+	}
+
+	if (result == NULL)
+		elog(ERROR, "BitmapAnd doesn't support zero inputs");
+
+	/* must provide our own instrumentation support */
+	if (node->ps.instrument)
+		InstrStopNodeMulti(node->ps.instrument, 0 /* XXX */);
+
+	return (Node *) result;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndBitmapAnd
+ *
+ *		Shuts down the subscans of the BitmapAnd node.
+ *
+ *		Returns nothing of interest.
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndBitmapAnd(BitmapAndState *node)
+{
+	PlanState **bitmapplans;
+	int			nplans;
+	int			i;
+
+	/*
+	 * get information from the node
+	 */
+	bitmapplans = node->bitmapplans;
+	nplans = node->nplans;
+
+	/*
+	 * shut down each of the subscans (that we've initialized)
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		if (bitmapplans[i])
+			ExecEndNode(bitmapplans[i]);
+	}
+}
+
+void
+ExecReScanBitmapAnd(BitmapAndState *node, ExprContext *exprCtxt)
+{
+	int			i;
+
+	for (i = 0; i < node->nplans; i++)
+	{
+		PlanState  *subnode = node->bitmapplans[i];
+
+		/*
+		 * ExecReScan doesn't know about my subplans, so I have to do
+		 * changed-parameter signaling myself.
+		 */
+		if (node->ps.chgParam != NULL)
+			UpdateChangedParamSet(subnode, node->ps.chgParam);
+
+		/*
+		 * Always rescan the inputs immediately, to ensure we can pass down
+		 * any outer tuple that might be used in index quals.
+		 */
+		ExecReScan(subnode, exprCtxt);
+	}
+}
diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c
new file mode 100644
index 00000000000..141e29dd293
--- /dev/null
+++ b/src/backend/executor/nodeBitmapHeapscan.c
@@ -0,0 +1,499 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapHeapscan.c
+ *	  Routines to support bitmapped scans of relations
+ *
+ * NOTE: it is critical that this plan type only be used with MVCC-compliant
+ * snapshots (ie, regular snapshots, not SnapshotNow or one of the other
+ * special snapshots).  The reason is that since index and heap scans are
+ * decoupled, there can be no assurance that the index tuple prompting a
+ * visit to a particular heap TID still exists when the visit is made.
+ * Therefore the tuple might not exist anymore either (which is OK because
+ * heap_fetch will cope) --- but worse, the tuple slot could have been
+ * re-used for a newer tuple.  With an MVCC snapshot the newer tuple is
+ * certain to fail the time qual and so it will not be mistakenly returned.
+ * With SnapshotNow we might return a tuple that doesn't meet the required
+ * index qual conditions.
+ *
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapHeapscan.c,v 1.1 2005/04/19 22:35:12 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+/*
+ * INTERFACE ROUTINES
+ *		ExecBitmapHeapScan			scans a relation using bitmap info
+ *		ExecBitmapHeapNext			workhorse for above
+ *		ExecInitBitmapHeapScan		creates and initializes state info.
+ *		ExecBitmapHeapReScan		prepares to rescan the plan.
+ *		ExecEndBitmapHeapScan		releases all storage.
+ */
+#include "postgres.h"
+
+#include "access/heapam.h"
+#include "executor/execdebug.h"
+#include "executor/nodeBitmapHeapscan.h"
+#include "parser/parsetree.h"
+
+
+static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node);
+
+
+/* ----------------------------------------------------------------
+ *		BitmapHeapNext
+ *
+ *		Retrieve next tuple from the BitmapHeapScan node's currentRelation
+ * ----------------------------------------------------------------
+ */
+static TupleTableSlot *
+BitmapHeapNext(BitmapHeapScanState *node)
+{
+	EState	   *estate;
+	ExprContext *econtext;
+	HeapScanDesc scandesc;
+	Index		scanrelid;
+	TIDBitmap  *tbm;
+	TBMIterateResult *tbmres;
+	OffsetNumber targoffset;
+	TupleTableSlot *slot;
+
+	/*
+	 * extract necessary information from index scan node
+	 */
+	estate = node->ss.ps.state;
+	econtext = node->ss.ps.ps_ExprContext;
+	slot = node->ss.ss_ScanTupleSlot;
+	scandesc = node->ss.ss_currentScanDesc;
+	scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid;
+	tbm = node->tbm;
+	tbmres = node->tbmres;
+
+	/*
+	 * Clear any reference to the previously returned tuple.  The idea
+	 * here is to not have the tuple slot be the last holder of a pin on
+	 * that tuple's buffer; if it is, we'll need a separate visit to the
+	 * bufmgr to release the buffer.  By clearing here, we get to have the
+	 * release done by ReleaseAndReadBuffer, below.
+	 */
+	ExecClearTuple(slot);
+
+	/*
+	 * Check if we are evaluating PlanQual for tuple of this relation.
+	 * Additional checking is not good, but no other way for now. We could
+	 * introduce new nodes for this case and handle IndexScan --> NewNode
+	 * switching in Init/ReScan plan...
+	 */
+	if (estate->es_evTuple != NULL &&
+		estate->es_evTuple[scanrelid - 1] != NULL)
+	{
+		if (estate->es_evTupleNull[scanrelid - 1])
+			return slot;		/* return empty slot */
+
+		ExecStoreTuple(estate->es_evTuple[scanrelid - 1],
+					   slot, InvalidBuffer, false);
+
+		/* Does the tuple meet the original qual conditions? */
+		econtext->ecxt_scantuple = slot;
+
+		ResetExprContext(econtext);
+
+		if (!ExecQual(node->bitmapqualorig, econtext, false))
+			ExecClearTuple(slot);	/* would not be returned by scan */
+
+		/* Flag for the next call that no more tuples */
+		estate->es_evTupleNull[scanrelid - 1] = true;
+
+		return slot;
+	}
+
+	/*
+	 * If we haven't yet performed the underlying index scan, do it,
+	 * and prepare the bitmap to be iterated over.
+	 */
+	if (tbm == NULL)
+	{
+		tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
+
+		if (!tbm || !IsA(tbm, TIDBitmap))
+			elog(ERROR, "unrecognized result from subplan");
+
+		node->tbm = tbm;
+		node->tbmres = tbmres = NULL;
+
+		tbm_begin_iterate(tbm);
+	}
+
+	for (;;)
+	{
+		/*
+		 * Get next page of results if needed
+		 */
+		if (tbmres == NULL)
+		{
+			node->tbmres = tbmres = tbm_iterate(tbm);
+			if (tbmres == NULL)
+			{
+				/* no more entries in the bitmap */
+				break;
+			}
+
+			/*
+			 * Ignore any claimed entries past what we think is the end of
+			 * the relation.  (This is probably not necessary given that we
+			 * got AccessShareLock before performing any of the indexscans,
+			 * but let's be safe.)
+			 */
+			if (tbmres->blockno >= scandesc->rs_nblocks)
+			{
+				node->tbmres = tbmres = NULL;
+				continue;
+			}
+
+			/*
+			 * Acquire pin on the current heap page.  We'll hold the pin
+			 * until done looking at the page.  We trade in any pin we
+			 * held before.
+			 */
+			scandesc->rs_cbuf = ReleaseAndReadBuffer(scandesc->rs_cbuf,
+													 scandesc->rs_rd,
+													 tbmres->blockno);
+
+			/*
+			 * Determine how many entries we need to look at on this page.
+			 * If the bitmap is lossy then we need to look at each physical
+			 * item pointer; otherwise we just look through the offsets
+			 * listed in tbmres.
+			 */
+			if (tbmres->ntuples >= 0)
+			{
+				/* non-lossy case */
+				node->minslot = 0;
+				node->maxslot = tbmres->ntuples - 1;
+			}
+			else
+			{
+				/* lossy case */
+				Page	dp;
+
+				LockBuffer(scandesc->rs_cbuf, BUFFER_LOCK_SHARE);
+				dp = (Page) BufferGetPage(scandesc->rs_cbuf);
+
+				node->minslot = FirstOffsetNumber;
+				node->maxslot = PageGetMaxOffsetNumber(dp);
+
+				LockBuffer(scandesc->rs_cbuf, BUFFER_LOCK_UNLOCK);
+			}
+
+			/*
+			 * Set curslot to first slot to examine
+			 */
+			node->curslot = node->minslot;
+		}
+		else
+		{
+			/*
+			 * Continuing in previously obtained page; advance curslot
+			 */
+			node->curslot++;
+		}
+
+		/*
+		 * Out of range?  If so, nothing more to look at on this page
+		 */
+		if (node->curslot < node->minslot || node->curslot > node->maxslot)
+		{
+			node->tbmres = tbmres = NULL;
+			continue;
+		}
+
+		/*
+		 * Okay to try to fetch the tuple
+		 */
+		if (tbmres->ntuples >= 0)
+		{
+			/* non-lossy case */
+			targoffset = tbmres->offsets[node->curslot];
+		}
+		else
+		{
+			/* lossy case */
+			targoffset = (OffsetNumber) node->curslot;
+		}
+
+		ItemPointerSet(&scandesc->rs_ctup.t_self, tbmres->blockno, targoffset);
+
+		/*
+		 * Fetch the heap tuple and see if it matches the snapshot.
+		 * We use heap_release_fetch to avoid useless bufmgr traffic.
+		 */
+		if (heap_release_fetch(scandesc->rs_rd,
+							   scandesc->rs_snapshot,
+							   &scandesc->rs_ctup,
+							   &scandesc->rs_cbuf,
+							   true,
+							   &scandesc->rs_pgstat_info))
+		{
+			/*
+			 * Set up the result slot to point to this tuple.
+			 * Note that the slot acquires a pin on the buffer.
+			 */
+			ExecStoreTuple(&scandesc->rs_ctup,
+						   slot,
+						   scandesc->rs_cbuf,
+						   false);
+
+			/*
+			 * If we are using lossy info, we have to recheck the qual
+			 * conditions at every tuple.
+			 */
+			if (tbmres->ntuples < 0)
+			{
+				econtext->ecxt_scantuple = slot;
+				ResetExprContext(econtext);
+
+				if (!ExecQual(node->bitmapqualorig, econtext, false))
+				{
+					/* Fails recheck, so drop it and loop back for another */
+					ExecClearTuple(slot);
+					continue;
+				}
+			}
+
+			/* OK to return this tuple */
+			return slot;
+		}
+
+		/*
+		 * Failed the snap, so loop back and try again.
+		 */
+	}
+
+	/*
+	 * if we get here it means we are at the end of the scan..
+	 */
+	return ExecClearTuple(slot);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecBitmapHeapScan(node)
+ * ----------------------------------------------------------------
+ */
+TupleTableSlot *
+ExecBitmapHeapScan(BitmapHeapScanState *node)
+{
+	/*
+	 * use BitmapHeapNext as access method
+	 */
+	return ExecScan(&node->ss, (ExecScanAccessMtd) BitmapHeapNext);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecBitmapHeapReScan(node)
+ * ----------------------------------------------------------------
+ */
+void
+ExecBitmapHeapReScan(BitmapHeapScanState *node, ExprContext *exprCtxt)
+{
+	EState	   *estate;
+	Index		scanrelid;
+
+	estate = node->ss.ps.state;
+	scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid;
+
+	/*
+	 * If we are being passed an outer tuple, link it into the "regular"
+	 * per-tuple econtext for possible qual eval.
+	 */
+	if (exprCtxt != NULL)
+	{
+		ExprContext *stdecontext;
+
+		stdecontext = node->ss.ps.ps_ExprContext;
+		stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
+	}
+
+	/* If this is re-scanning of PlanQual ... */
+	if (estate->es_evTuple != NULL &&
+		estate->es_evTuple[scanrelid - 1] != NULL)
+	{
+		estate->es_evTupleNull[scanrelid - 1] = false;
+	}
+
+	/* rescan to release any page pin */
+	heap_rescan(node->ss.ss_currentScanDesc, NULL);
+
+	if (node->tbm)
+		tbm_free(node->tbm);
+	node->tbm = NULL;
+	node->tbmres = NULL;
+
+	/*
+	 * Always rescan the input immediately, to ensure we can pass down
+	 * any outer tuple that might be used in index quals.
+	 */
+	ExecReScan(outerPlanState(node), exprCtxt);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndBitmapHeapScan
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndBitmapHeapScan(BitmapHeapScanState *node)
+{
+	Relation	relation;
+	HeapScanDesc scanDesc;
+
+	/*
+	 * extract information from the node
+	 */
+	relation = node->ss.ss_currentRelation;
+	scanDesc = node->ss.ss_currentScanDesc;
+
+	/*
+	 * Free the exprcontext
+	 */
+	ExecFreeExprContext(&node->ss.ps);
+
+	/*
+	 * clear out tuple table slots
+	 */
+	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
+	ExecClearTuple(node->ss.ss_ScanTupleSlot);
+
+	/*
+	 * close down subplans
+	 */
+	ExecEndNode(outerPlanState(node));
+
+	/*
+	 * release bitmap if any
+	 */
+	if (node->tbm)
+		tbm_free(node->tbm);
+
+	/*
+	 * close heap scan
+	 */
+	heap_endscan(scanDesc);
+
+	/*
+	 * close the heap relation.
+	 *
+	 * Currently, we do not release the AccessShareLock acquired by
+	 * ExecInitBitmapHeapScan.  This lock should be held till end of
+	 * transaction. (There is a faction that considers this too much
+	 * locking, however.)
+	 */
+	heap_close(relation, NoLock);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecInitBitmapHeapScan
+ *
+ *		Initializes the scan's state information.
+ * ----------------------------------------------------------------
+ */
+BitmapHeapScanState *
+ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate)
+{
+	BitmapHeapScanState *scanstate;
+	RangeTblEntry *rtentry;
+	Index		relid;
+	Oid			reloid;
+	Relation	currentRelation;
+
+	/*
+	 * create state structure
+	 */
+	scanstate = makeNode(BitmapHeapScanState);
+	scanstate->ss.ps.plan = (Plan *) node;
+	scanstate->ss.ps.state = estate;
+
+	scanstate->tbm = NULL;
+	scanstate->tbmres = NULL;
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * create expression context for node
+	 */
+	ExecAssignExprContext(estate, &scanstate->ss.ps);
+
+	/*
+	 * initialize child expressions
+	 */
+	scanstate->ss.ps.targetlist = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.targetlist,
+					 (PlanState *) scanstate);
+	scanstate->ss.ps.qual = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.qual,
+					 (PlanState *) scanstate);
+	scanstate->bitmapqualorig = (List *)
+		ExecInitExpr((Expr *) node->bitmapqualorig,
+					 (PlanState *) scanstate);
+
+	/*
+	 * initialize child nodes
+	 */
+	outerPlanState(scanstate) = ExecInitNode(outerPlan(node), estate);
+
+#define BITMAPHEAPSCAN_NSLOTS 2
+
+	/*
+	 * tuple table initialization
+	 */
+	ExecInitResultTupleSlot(estate, &scanstate->ss.ps);
+	ExecInitScanTupleSlot(estate, &scanstate->ss);
+
+	CXT1_printf("ExecInitBitmapHeapScan: context is %d\n", CurrentMemoryContext);
+
+	/*
+	 * open the base relation and acquire AccessShareLock on it.
+	 */
+	relid = node->scan.scanrelid;
+	rtentry = rt_fetch(relid, estate->es_range_table);
+	reloid = rtentry->relid;
+
+	currentRelation = heap_open(reloid, AccessShareLock);
+
+	scanstate->ss.ss_currentRelation = currentRelation;
+
+	/*
+	 * Even though we aren't going to do a conventional seqscan, it is
+	 * useful to create a HeapScanDesc --- this checks the relation size
+	 * and sets up statistical infrastructure for us.
+	 */
+	scanstate->ss.ss_currentScanDesc = heap_beginscan(currentRelation,
+													  estate->es_snapshot,
+													  0,
+													  NULL);
+
+	/*
+	 * get the scan type from the relation descriptor.
+	 */
+	ExecAssignScanType(&scanstate->ss, RelationGetDescr(currentRelation), false);
+
+	/*
+	 * Initialize result tuple type and projection info.
+	 */
+	ExecAssignResultTypeFromTL(&scanstate->ss.ps);
+	ExecAssignScanProjectionInfo(&scanstate->ss);
+
+	/*
+	 * all done.
+	 */
+	return scanstate;
+}
+
+int
+ExecCountSlotsBitmapHeapScan(BitmapHeapScan *node)
+{
+	return ExecCountSlotsNode(outerPlan((Plan *) node)) +
+		ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPHEAPSCAN_NSLOTS;
+}
diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c
new file mode 100644
index 00000000000..3ed03eb7cb8
--- /dev/null
+++ b/src/backend/executor/nodeBitmapIndexscan.c
@@ -0,0 +1,519 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapIndexscan.c
+ *	  Routines to support bitmapped index scans of relations
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.1 2005/04/19 22:35:12 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+/*
+ * INTERFACE ROUTINES
+ *		MultiExecBitmapIndexScan	scans a relation using index.
+ *		ExecInitBitmapIndexScan		creates and initializes state info.
+ *		ExecBitmapIndexReScan		prepares to rescan the plan.
+ *		ExecEndBitmapIndexScan		releases all storage.
+ */
+#include "postgres.h"
+
+#include "access/genam.h"
+#include "access/heapam.h"
+#include "executor/execdebug.h"
+#include "executor/instrument.h"
+#include "executor/nodeBitmapIndexscan.h"
+#include "miscadmin.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/clauses.h"
+#include "parser/parsetree.h"
+
+
+/* ----------------------------------------------------------------
+ *		MultiExecBitmapIndexScan(node)
+ * ----------------------------------------------------------------
+ */
+Node *
+MultiExecBitmapIndexScan(BitmapIndexScanState *node)
+{
+#define MAX_TIDS	1024
+	TIDBitmap  *tbm;
+	IndexScanDesc scandesc;
+	ItemPointerData tids[MAX_TIDS];
+	int32		ntids;
+	double		nTuples = 0;
+
+	/* must provide our own instrumentation support */
+	if (node->ss.ps.instrument)
+		InstrStartNode(node->ss.ps.instrument);
+
+	/*
+	 * If we have runtime keys and they've not already been set up, do it
+	 * now.
+	 */
+	if (node->biss_RuntimeKeyInfo && !node->biss_RuntimeKeysReady)
+		ExecReScan((PlanState *) node, NULL);
+
+	/*
+	 * extract necessary information from index scan node
+	 */
+	scandesc = node->biss_ScanDesc;
+
+	/*
+	 * Prepare result bitmap
+	 */
+	tbm = tbm_create(work_mem * 1024L);
+
+	/*
+	 * Get TIDs from index and insert into bitmap
+	 */
+	for (;;)
+	{
+		bool	more = index_getmulti(scandesc, tids, MAX_TIDS, &ntids);
+
+		if (ntids > 0)
+		{
+			tbm_add_tuples(tbm, tids, ntids);
+			nTuples += ntids;
+		}
+
+		if (!more)
+			break;
+
+		CHECK_FOR_INTERRUPTS();
+	}
+
+	/* must provide our own instrumentation support */
+	if (node->ss.ps.instrument)
+		InstrStopNodeMulti(node->ss.ps.instrument, nTuples);
+
+	return (Node *) tbm;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecBitmapIndexReScan(node)
+ *
+ *		Recalculates the value of the scan keys whose value depends on
+ *		information known at runtime and rescans the indexed relation.
+ *		Updating the scan key was formerly done separately in
+ *		ExecUpdateIndexScanKeys. Integrating it into ReScan makes
+ *		rescans of indices and relations/general streams more uniform.
+ *
+ * ----------------------------------------------------------------
+ */
+void
+ExecBitmapIndexReScan(BitmapIndexScanState *node, ExprContext *exprCtxt)
+{
+	ExprContext *econtext;
+	ExprState **runtimeKeyInfo;
+	Index		scanrelid;
+
+	econtext = node->biss_RuntimeContext;		/* context for runtime
+												 * keys */
+	runtimeKeyInfo = node->biss_RuntimeKeyInfo;
+	scanrelid = ((BitmapIndexScan *) node->ss.ps.plan)->scan.scanrelid;
+
+	if (econtext)
+	{
+		/*
+		 * If we are being passed an outer tuple, save it for runtime key
+		 * calc.  We also need to link it into the "regular" per-tuple
+		 * econtext.
+		 */
+		if (exprCtxt != NULL)
+		{
+			ExprContext *stdecontext;
+
+			econtext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
+			stdecontext = node->ss.ps.ps_ExprContext;
+			stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
+		}
+
+		/*
+		 * Reset the runtime-key context so we don't leak memory as each
+		 * outer tuple is scanned.	Note this assumes that we will
+		 * recalculate *all* runtime keys on each call.
+		 */
+		ResetExprContext(econtext);
+	}
+
+	/*
+	 * If we are doing runtime key calculations (ie, the index keys depend
+	 * on data from an outer scan), compute the new key values
+	 */
+	if (runtimeKeyInfo)
+	{
+		int			n_keys;
+		ScanKey		scan_keys;
+		ExprState **run_keys;
+		int			j;
+
+		n_keys = node->biss_NumScanKeys;
+		scan_keys = node->biss_ScanKeys;
+		run_keys = runtimeKeyInfo;
+
+		for (j = 0; j < n_keys; j++)
+		{
+			/*
+			 * If we have a run-time key, then extract the run-time
+			 * expression and evaluate it with respect to the current
+			 * outer tuple.  We then stick the result into the scan
+			 * key.
+			 *
+			 * Note: the result of the eval could be a pass-by-ref value
+			 * that's stored in the outer scan's tuple, not in
+			 * econtext->ecxt_per_tuple_memory.  We assume that the
+			 * outer tuple will stay put throughout our scan.  If this
+			 * is wrong, we could copy the result into our context
+			 * explicitly, but I think that's not necessary...
+			 */
+			if (run_keys[j] != NULL)
+			{
+				Datum		scanvalue;
+				bool		isNull;
+
+				scanvalue = ExecEvalExprSwitchContext(run_keys[j],
+													  econtext,
+													  &isNull,
+													  NULL);
+				scan_keys[j].sk_argument = scanvalue;
+				if (isNull)
+					scan_keys[j].sk_flags |= SK_ISNULL;
+				else
+					scan_keys[j].sk_flags &= ~SK_ISNULL;
+			}
+		}
+
+		node->biss_RuntimeKeysReady = true;
+	}
+
+	index_rescan(node->biss_ScanDesc, node->biss_ScanKeys);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndBitmapIndexScan
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndBitmapIndexScan(BitmapIndexScanState *node)
+{
+	Relation	relation;
+
+	/*
+	 * extract information from the node
+	 */
+	relation = node->ss.ss_currentRelation;
+
+	/*
+	 * Free the exprcontext(s)
+	 */
+	ExecFreeExprContext(&node->ss.ps);
+	if (node->biss_RuntimeContext)
+		FreeExprContext(node->biss_RuntimeContext);
+
+	/*
+	 * close the index relation
+	 */
+	if (node->biss_ScanDesc != NULL)
+		index_endscan(node->biss_ScanDesc);
+
+	if (node->biss_RelationDesc != NULL)
+		index_close(node->biss_RelationDesc);
+
+	/*
+	 * close the heap relation.
+	 *
+	 * Currently, we do not release the AccessShareLock acquired by
+	 * ExecInitBitmapIndexScan.  This lock should be held till end of
+	 * transaction. (There is a faction that considers this too much
+	 * locking, however.)
+	 */
+	heap_close(relation, NoLock);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecInitBitmapIndexScan
+ *
+ *		Initializes the index scan's state information, creates
+ *		scan keys, and opens the base and index relations.
+ *
+ *		Note: index scans have 2 sets of state information because
+ *			  we have to keep track of the base relation and the
+ *			  index relations.
+ *
+ * old comments
+ *		Creates the run-time state information for the node and
+ *		sets the relation id to contain relevant descriptors.
+ *
+ *		Parameters:
+ *		  node: BitmapIndexNode node produced by the planner.
+ *		  estate: the execution state initialized in InitPlan.
+ * ----------------------------------------------------------------
+ */
+BitmapIndexScanState *
+ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate)
+{
+	BitmapIndexScanState *indexstate;
+	ExprState **runtimeKeyInfo;
+	bool		have_runtime_keys;
+	RangeTblEntry *rtentry;
+	Index		relid;
+	Oid			reloid;
+	Relation	currentRelation;
+
+	/*
+	 * create state structure
+	 */
+	indexstate = makeNode(BitmapIndexScanState);
+	indexstate->ss.ps.plan = (Plan *) node;
+	indexstate->ss.ps.state = estate;
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * create expression context for node
+	 */
+	ExecAssignExprContext(estate, &indexstate->ss.ps);
+
+	/*
+	 * initialize child expressions
+	 *
+	 * We don't need to initialize targetlist or qual since neither are used.
+	 *
+	 * Note: we don't initialize all of the indxqual expression, only the
+	 * sub-parts corresponding to runtime keys (see below).
+	 */
+
+#define BITMAPINDEXSCAN_NSLOTS 0
+
+	/*
+	 * Initialize index-specific scan state
+	 */
+	indexstate->biss_ScanKeys = NULL;
+	indexstate->biss_NumScanKeys = 0;
+	indexstate->biss_RuntimeKeyInfo = NULL;
+	indexstate->biss_RuntimeContext = NULL;
+	indexstate->biss_RuntimeKeysReady = false;
+	indexstate->biss_RelationDesc = NULL;
+	indexstate->biss_ScanDesc = NULL;
+
+	CXT1_printf("ExecInitBitmapIndexScan: context is %d\n", CurrentMemoryContext);
+
+	/*
+	 * initialize space for runtime key info (may not be needed)
+	 */
+	have_runtime_keys = false;
+
+	/*
+	 * build the index scan keys from the index qualification
+	 */
+	{
+		List	   *quals;
+		List	   *strategies;
+		List	   *subtypes;
+		ListCell   *qual_cell;
+		ListCell   *strategy_cell;
+		ListCell   *subtype_cell;
+		int			n_keys;
+		ScanKey		scan_keys;
+		ExprState **run_keys;
+		int			j;
+
+		quals = node->indxqual;
+		strategies = node->indxstrategy;
+		subtypes = node->indxsubtype;
+		n_keys = list_length(quals);
+		scan_keys = (n_keys <= 0) ? NULL :
+			(ScanKey) palloc(n_keys * sizeof(ScanKeyData));
+		run_keys = (n_keys <= 0) ? NULL :
+			(ExprState **) palloc(n_keys * sizeof(ExprState *));
+
+		/*
+		 * for each opclause in the given qual, convert each qual's
+		 * opclause into a single scan key
+		 */
+		qual_cell = list_head(quals);
+		strategy_cell = list_head(strategies);
+		subtype_cell = list_head(subtypes);
+		for (j = 0; j < n_keys; j++)
+		{
+			OpExpr	   *clause; /* one clause of index qual */
+			Expr	   *leftop; /* expr on lhs of operator */
+			Expr	   *rightop;	/* expr on rhs ... */
+			int			flags = 0;
+			AttrNumber	varattno;		/* att number used in scan */
+			StrategyNumber strategy;	/* op's strategy number */
+			Oid			subtype;	/* op's strategy subtype */
+			RegProcedure opfuncid;		/* operator proc id used in scan */
+			Datum		scanvalue;		/* value used in scan (if const) */
+
+			/*
+			 * extract clause information from the qualification
+			 */
+			clause = (OpExpr *) lfirst(qual_cell);
+			qual_cell = lnext(qual_cell);
+			strategy = lfirst_int(strategy_cell);
+			strategy_cell = lnext(strategy_cell);
+			subtype = lfirst_oid(subtype_cell);
+			subtype_cell = lnext(subtype_cell);
+
+			if (!IsA(clause, OpExpr))
+				elog(ERROR, "indxqual is not an OpExpr");
+
+			opfuncid = clause->opfuncid;
+
+			/*
+			 * Here we figure out the contents of the index qual. The
+			 * usual case is (var op const) which means we form a scan key
+			 * for the attribute listed in the var node and use the value
+			 * of the const as comparison data.
+			 *
+			 * If we don't have a const node, it means our scan key is a
+			 * function of information obtained during the execution of
+			 * the plan, in which case we need to recalculate the index
+			 * scan key at run time.  Hence, we set have_runtime_keys to
+			 * true and place the appropriate subexpression in run_keys.
+			 * The corresponding scan key values are recomputed at run
+			 * time.
+			 */
+			run_keys[j] = NULL;
+
+			/*
+			 * determine information in leftop
+			 */
+			leftop = (Expr *) get_leftop((Expr *) clause);
+
+			if (leftop && IsA(leftop, RelabelType))
+				leftop = ((RelabelType *) leftop)->arg;
+
+			Assert(leftop != NULL);
+
+			if (!(IsA(leftop, Var) &&
+				  var_is_rel((Var *) leftop)))
+				elog(ERROR, "indxqual doesn't have key on left side");
+
+			varattno = ((Var *) leftop)->varattno;
+
+			/*
+			 * now determine information in rightop
+			 */
+			rightop = (Expr *) get_rightop((Expr *) clause);
+
+			if (rightop && IsA(rightop, RelabelType))
+				rightop = ((RelabelType *) rightop)->arg;
+
+			Assert(rightop != NULL);
+
+			if (IsA(rightop, Const))
+			{
+				/*
+				 * if the rightop is a const node then it means it
+				 * identifies the value to place in our scan key.
+				 */
+				scanvalue = ((Const *) rightop)->constvalue;
+				if (((Const *) rightop)->constisnull)
+					flags |= SK_ISNULL;
+			}
+			else
+			{
+				/*
+				 * otherwise, the rightop contains an expression evaluable
+				 * at runtime to figure out the value to place in our scan
+				 * key.
+				 */
+				have_runtime_keys = true;
+				run_keys[j] = ExecInitExpr(rightop, (PlanState *) indexstate);
+				scanvalue = (Datum) 0;
+			}
+
+			/*
+			 * initialize the scan key's fields appropriately
+			 */
+			ScanKeyEntryInitialize(&scan_keys[j],
+								   flags,
+								   varattno,	/* attribute number to
+												 * scan */
+								   strategy,	/* op's strategy */
+								   subtype,		/* strategy subtype */
+								   opfuncid,	/* reg proc to use */
+								   scanvalue);	/* constant */
+		}
+
+		/*
+		 * store the key information into the node.
+		 */
+		indexstate->biss_NumScanKeys = n_keys;
+		indexstate->biss_ScanKeys = scan_keys;
+		runtimeKeyInfo = run_keys;
+	}
+
+
+	/*
+	 * If all of our keys have the form (var op const), then we have no
+	 * runtime keys so we store NULL in the runtime key info. Otherwise
+	 * runtime key info contains an array of pointers (one for each index)
+	 * to arrays of flags (one for each key) which indicate that the qual
+	 * needs to be evaluated at runtime. -cim 10/24/89
+	 *
+	 * If we do have runtime keys, we need an ExprContext to evaluate them;
+	 * the node's standard context won't do because we want to reset that
+	 * context for every tuple.  So, build another context just like the
+	 * other one... -tgl 7/11/00
+	 */
+	if (have_runtime_keys)
+	{
+		ExprContext *stdecontext = indexstate->ss.ps.ps_ExprContext;
+
+		ExecAssignExprContext(estate, &indexstate->ss.ps);
+		indexstate->biss_RuntimeKeyInfo = runtimeKeyInfo;
+		indexstate->biss_RuntimeContext = indexstate->ss.ps.ps_ExprContext;
+		indexstate->ss.ps.ps_ExprContext = stdecontext;
+	}
+	else
+	{
+		indexstate->biss_RuntimeKeyInfo = NULL;
+		indexstate->biss_RuntimeContext = NULL;
+		/* Get rid of the speculatively-allocated flag array, too */
+		pfree(runtimeKeyInfo);
+	}
+
+	/*
+	 * open the base relation and acquire AccessShareLock on it.
+	 */
+	relid = node->scan.scanrelid;
+	rtentry = rt_fetch(relid, estate->es_range_table);
+	reloid = rtentry->relid;
+
+	currentRelation = heap_open(reloid, AccessShareLock);
+
+	indexstate->ss.ss_currentRelation = currentRelation;
+	indexstate->ss.ss_currentScanDesc = NULL;	/* no heap scan here */
+
+	/*
+	 * open the index relation and initialize relation and scan
+	 * descriptors.  Note we acquire no locks here; the index machinery
+	 * does its own locks and unlocks.	(We rely on having AccessShareLock
+	 * on the parent table to ensure the index won't go away!)
+	 */
+	indexstate->biss_RelationDesc = index_open(node->indxid);
+	indexstate->biss_ScanDesc =
+		index_beginscan_multi(indexstate->biss_RelationDesc,
+							  estate->es_snapshot,
+							  indexstate->biss_NumScanKeys,
+							  indexstate->biss_ScanKeys);
+
+	/*
+	 * all done.
+	 */
+	return indexstate;
+}
+
+int
+ExecCountSlotsBitmapIndexScan(BitmapIndexScan *node)
+{
+	return ExecCountSlotsNode(outerPlan((Plan *) node)) +
+		ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPINDEXSCAN_NSLOTS;
+}
diff --git a/src/backend/executor/nodeBitmapOr.c b/src/backend/executor/nodeBitmapOr.c
new file mode 100644
index 00000000000..f4ef17223c8
--- /dev/null
+++ b/src/backend/executor/nodeBitmapOr.c
@@ -0,0 +1,209 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapOr.c
+ *	  routines to handle BitmapOr nodes.
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeBitmapOr.c,v 1.1 2005/04/19 22:35:12 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+/* INTERFACE ROUTINES
+ *		ExecInitBitmapOr	- initialize the BitmapOr node
+ *		MultiExecBitmapOr	- retrieve the result bitmap from the node
+ *		ExecEndBitmapOr		- shut down the BitmapOr node
+ *		ExecReScanBitmapOr	- rescan the BitmapOr node
+ *
+ *	 NOTES
+ *		BitmapOr nodes don't make use of their left and right
+ *		subtrees, rather they maintain a list of subplans,
+ *		much like Append nodes.  The logic is much simpler than
+ *		Append, however, since we needn't cope with forward/backward
+ *		execution.
+ */
+
+#include "postgres.h"
+
+#include "executor/execdebug.h"
+#include "executor/instrument.h"
+#include "executor/nodeBitmapOr.h"
+
+
+/* ----------------------------------------------------------------
+ *		ExecInitBitmapOr
+ *
+ *		Begin all of the subscans of the BitmapOr node.
+ * ----------------------------------------------------------------
+ */
+BitmapOrState *
+ExecInitBitmapOr(BitmapOr *node, EState *estate)
+{
+	BitmapOrState *bitmaporstate = makeNode(BitmapOrState);
+	PlanState **bitmapplanstates;
+	int			nplans;
+	int			i;
+	Plan	   *initNode;
+
+	CXT1_printf("ExecInitBitmapOr: context is %d\n", CurrentMemoryContext);
+
+	/*
+	 * Set up empty vector of subplan states
+	 */
+	nplans = list_length(node->bitmapplans);
+
+	bitmapplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *));
+
+	/*
+	 * create new BitmapOrState for our BitmapOr node
+	 */
+	bitmaporstate->ps.plan = (Plan *) node;
+	bitmaporstate->ps.state = estate;
+	bitmaporstate->bitmapplans = bitmapplanstates;
+	bitmaporstate->nplans = nplans;
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * BitmapOr plans don't have expression contexts because they never call
+	 * ExecQual or ExecProject.  They don't need any tuple slots either.
+	 */
+
+#define BITMAPOR_NSLOTS 0
+
+	/*
+	 * call ExecInitNode on each of the plans to be executed and save the
+	 * results into the array "bitmapplanstates".
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		initNode = (Plan *) list_nth(node->bitmapplans, i);
+		bitmapplanstates[i] = ExecInitNode(initNode, estate);
+	}
+
+	return bitmaporstate;
+}
+
+int
+ExecCountSlotsBitmapOr(BitmapOr *node)
+{
+	ListCell   *plan;
+	int			nSlots = 0;
+
+	foreach(plan, node->bitmapplans)
+		nSlots += ExecCountSlotsNode((Plan *) lfirst(plan));
+	return nSlots + BITMAPOR_NSLOTS;
+}
+
+/* ----------------------------------------------------------------
+ *	   MultiExecBitmapOr
+ * ----------------------------------------------------------------
+ */
+Node *
+MultiExecBitmapOr(BitmapOrState *node)
+{
+	PlanState **bitmapplans;
+	int			nplans;
+	int			i;
+	TIDBitmap  *result = NULL;
+
+	/* must provide our own instrumentation support */
+	if (node->ps.instrument)
+		InstrStartNode(node->ps.instrument);
+
+	/*
+	 * get information from the node
+	 */
+	bitmapplans = node->bitmapplans;
+	nplans = node->nplans;
+
+	/*
+	 * Scan all the subplans and OR their result bitmaps
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		PlanState  *subnode = bitmapplans[i];
+		TIDBitmap  *subresult;
+
+		subresult = (TIDBitmap *) MultiExecProcNode(subnode);
+
+		if (!subresult || !IsA(subresult, TIDBitmap))
+			elog(ERROR, "unrecognized result from subplan");
+
+		if (result == NULL)
+			result = subresult;			/* first subplan */
+		else
+		{
+			tbm_union(result, subresult);
+			tbm_free(subresult);
+		}
+	}
+
+	/* We could return an empty result set here? */
+	if (result == NULL)
+		elog(ERROR, "BitmapOr doesn't support zero inputs");
+
+	/* must provide our own instrumentation support */
+	if (node->ps.instrument)
+		InstrStopNodeMulti(node->ps.instrument, 0 /* XXX */);
+
+	return (Node *) result;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndBitmapOr
+ *
+ *		Shuts down the subscans of the BitmapOr node.
+ *
+ *		Returns nothing of interest.
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndBitmapOr(BitmapOrState *node)
+{
+	PlanState **bitmapplans;
+	int			nplans;
+	int			i;
+
+	/*
+	 * get information from the node
+	 */
+	bitmapplans = node->bitmapplans;
+	nplans = node->nplans;
+
+	/*
+	 * shut down each of the subscans (that we've initialized)
+	 */
+	for (i = 0; i < nplans; i++)
+	{
+		if (bitmapplans[i])
+			ExecEndNode(bitmapplans[i]);
+	}
+}
+
+void
+ExecReScanBitmapOr(BitmapOrState *node, ExprContext *exprCtxt)
+{
+	int			i;
+
+	for (i = 0; i < node->nplans; i++)
+	{
+		PlanState  *subnode = node->bitmapplans[i];
+
+		/*
+		 * ExecReScan doesn't know about my subplans, so I have to do
+		 * changed-parameter signaling myself.
+		 */
+		if (node->ps.chgParam != NULL)
+			UpdateChangedParamSet(subnode, node->ps.chgParam);
+
+		/*
+		 * Always rescan the inputs immediately, to ensure we can pass down
+		 * any outer tuple that might be used in index quals.
+		 */
+		ExecReScan(subnode, exprCtxt);
+	}
+}