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.

11 files changed, 288 insertions, 10 deletions

diff --git a/src/include/executor/nodeBitmapAnd.h b/src/include/executor/nodeBitmapAnd.h
new file mode 100644
index 0000000000..320fc71ab7
--- /dev/null
+++ b/src/include/executor/nodeBitmapAnd.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapAnd.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeBitmapAnd.h,v 1.1 2005/04/19 22:35:17 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEBITMAPAND_H
+#define NODEBITMAPAND_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsBitmapAnd(BitmapAnd *node);
+extern BitmapAndState *ExecInitBitmapAnd(BitmapAnd *node, EState *estate);
+extern Node *MultiExecBitmapAnd(BitmapAndState *node);
+extern void ExecEndBitmapAnd(BitmapAndState *node);
+extern void ExecReScanBitmapAnd(BitmapAndState *node, ExprContext *exprCtxt);
+
+#endif   /* NODEBITMAPAND_H */
diff --git a/src/include/executor/nodeBitmapHeapscan.h b/src/include/executor/nodeBitmapHeapscan.h
new file mode 100644
index 0000000000..48c4b6ad79
--- /dev/null
+++ b/src/include/executor/nodeBitmapHeapscan.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapHeapscan.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeBitmapHeapscan.h,v 1.1 2005/04/19 22:35:17 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEBITMAPHEAPSCAN_H
+#define NODEBITMAPHEAPSCAN_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsBitmapHeapScan(BitmapHeapScan *node);
+extern BitmapHeapScanState *ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate);
+extern TupleTableSlot *ExecBitmapHeapScan(BitmapHeapScanState *node);
+extern void ExecEndBitmapHeapScan(BitmapHeapScanState *node);
+extern void ExecBitmapHeapReScan(BitmapHeapScanState *node, ExprContext *exprCtxt);
+
+#endif   /* NODEBITMAPHEAPSCAN_H */
diff --git a/src/include/executor/nodeBitmapIndexscan.h b/src/include/executor/nodeBitmapIndexscan.h
new file mode 100644
index 0000000000..7ca5553abb
--- /dev/null
+++ b/src/include/executor/nodeBitmapIndexscan.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapIndexscan.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeBitmapIndexscan.h,v 1.1 2005/04/19 22:35:17 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEBITMAPINDEXSCAN_H
+#define NODEBITMAPINDEXSCAN_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsBitmapIndexScan(BitmapIndexScan *node);
+extern BitmapIndexScanState *ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate);
+extern Node *MultiExecBitmapIndexScan(BitmapIndexScanState *node);
+extern void ExecEndBitmapIndexScan(BitmapIndexScanState *node);
+extern void ExecBitmapIndexReScan(BitmapIndexScanState *node, ExprContext *exprCtxt);
+
+#endif   /* NODEBITMAPINDEXSCAN_H */
diff --git a/src/include/executor/nodeBitmapOr.h b/src/include/executor/nodeBitmapOr.h
new file mode 100644
index 0000000000..927231a708
--- /dev/null
+++ b/src/include/executor/nodeBitmapOr.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeBitmapOr.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeBitmapOr.h,v 1.1 2005/04/19 22:35:17 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEBITMAPOR_H
+#define NODEBITMAPOR_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsBitmapOr(BitmapOr *node);
+extern BitmapOrState *ExecInitBitmapOr(BitmapOr *node, EState *estate);
+extern Node *MultiExecBitmapOr(BitmapOrState *node);
+extern void ExecEndBitmapOr(BitmapOrState *node);
+extern void ExecReScanBitmapOr(BitmapOrState *node, ExprContext *exprCtxt);
+
+#endif   /* NODEBITMAPOR_H */
diff --git a/src/include/executor/nodeIndexscan.h b/src/include/executor/nodeIndexscan.h
index e4e3026038..530ac5117b 100644
--- a/src/include/executor/nodeIndexscan.h
+++ b/src/include/executor/nodeIndexscan.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/executor/nodeIndexscan.h,v 1.21 2004/12/31 22:03:29 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/executor/nodeIndexscan.h,v 1.22 2005/04/19 22:35:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -24,6 +24,4 @@ extern void ExecIndexMarkPos(IndexScanState *node);
 extern void ExecIndexRestrPos(IndexScanState *node);
 extern void ExecIndexReScan(IndexScanState *node, ExprContext *exprCtxt);
 
-extern void ExecUpdateIndexScanKeys(IndexScanState *node, ExprContext *econtext);
-
 #endif   /* NODEINDEXSCAN_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index da82daaac9..a5176c2f95 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.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/nodes/execnodes.h,v 1.125 2005/03/25 21:58:00 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.126 2005/04/19 22:35:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,6 +20,7 @@
 #include "nodes/bitmapset.h"
 #include "nodes/params.h"
 #include "nodes/plannodes.h"
+#include "nodes/tidbitmap.h"
 #include "utils/hsearch.h"
 #include "utils/tuplestore.h"
 
@@ -803,6 +804,28 @@ typedef struct AppendState
 	int			as_lastplan;
 } AppendState;
 
+/* ----------------
+ *	 BitmapAndState information
+ * ----------------
+ */
+typedef struct BitmapAndState
+{
+	PlanState	ps;				/* its first field is NodeTag */
+	PlanState **bitmapplans;	/* array of PlanStates for my inputs */
+	int			nplans;			/* number of input plans */
+} BitmapAndState;
+
+/* ----------------
+ *	 BitmapOrState information
+ * ----------------
+ */
+typedef struct BitmapOrState
+{
+	PlanState	ps;				/* its first field is NodeTag */
+	PlanState **bitmapplans;	/* array of PlanStates for my inputs */
+	int			nplans;			/* number of input plans */
+} BitmapOrState;
+
 /* ----------------------------------------------------------------
  *				 Scan State Information
  * ----------------------------------------------------------------
@@ -876,6 +899,53 @@ typedef struct IndexScanState
 } IndexScanState;
 
 /* ----------------
+ *	 BitmapIndexScanState information
+ *
+ *		ScanKeys		   Skey structures to scan index rel
+ *		NumScanKeys		   number of Skey structs
+ *		RuntimeKeyInfo	   array of exprstates for Skeys
+ *						   that will be evaluated at runtime
+ *		RuntimeContext	   expr context for evaling runtime Skeys
+ *		RuntimeKeysReady   true if runtime Skeys have been computed
+ *		RelationDesc	   relation descriptor
+ *		ScanDesc		   scan descriptor
+ * ----------------
+ */
+typedef struct BitmapIndexScanState
+{
+	ScanState	ss;				/* its first field is NodeTag */
+	ScanKey		biss_ScanKeys;
+	int			biss_NumScanKeys;
+	ExprState **biss_RuntimeKeyInfo;
+	ExprContext *biss_RuntimeContext;
+	bool		biss_RuntimeKeysReady;
+	Relation	biss_RelationDesc;
+	IndexScanDesc biss_ScanDesc;
+} BitmapIndexScanState;
+
+/* ----------------
+ *	 BitmapHeapScanState information
+ *
+ *		bitmapqualorig	   execution state for bitmapqualorig expressions
+ *		tbm				   bitmap obtained from child index scan(s)
+ *		tbmres			   current-page data
+ *		curslot			   current tbmres index or tuple offset on page
+ *		minslot			   lowest tbmres index or tuple offset to try
+ *		maxslot			   highest tbmres index or tuple offset to try
+ * ----------------
+ */
+typedef struct BitmapHeapScanState
+{
+	ScanState	ss;				/* its first field is NodeTag */
+	List	   *bitmapqualorig;
+	TIDBitmap  *tbm;
+	TBMIterateResult *tbmres;
+	int			curslot;
+	int			minslot;
+	int			maxslot;
+} BitmapHeapScanState;
+
+/* ----------------
  *	 TidScanState information
  *
  *		NumTids		   number of tids in this scan
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 3c5528546a..32df3bff0e 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.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/nodes/nodes.h,v 1.166 2005/04/17 22:24:02 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.167 2005/04/19 22:35:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -44,9 +44,13 @@ typedef enum NodeTag
 	T_Plan = 100,
 	T_Result,
 	T_Append,
+	T_BitmapAnd,
+	T_BitmapOr,
 	T_Scan,
 	T_SeqScan,
 	T_IndexScan,
+	T_BitmapIndexScan,
+	T_BitmapHeapScan,
 	T_TidScan,
 	T_SubqueryScan,
 	T_FunctionScan,
@@ -71,9 +75,13 @@ typedef enum NodeTag
 	T_PlanState = 200,
 	T_ResultState,
 	T_AppendState,
+	T_BitmapAndState,
+	T_BitmapOrState,
 	T_ScanState,
 	T_SeqScanState,
 	T_IndexScanState,
+	T_BitmapIndexScanState,
+	T_BitmapHeapScanState,
 	T_TidScanState,
 	T_SubqueryScanState,
 	T_FunctionScanState,
@@ -161,6 +169,7 @@ typedef enum NodeTag
 	T_IndexOptInfo,
 	T_Path,
 	T_IndexPath,
+	T_BitmapHeapPath,
 	T_NestPath,
 	T_MergePath,
 	T_HashPath,
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 50eb59cc65..4ab8473e56 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.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/nodes/plannodes.h,v 1.77 2004/12/31 22:03:34 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.78 2005/04/19 22:35:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -134,6 +134,34 @@ typedef struct Append
 	bool		isTarget;
 } Append;
 
+/* ----------------
+ *	 BitmapAnd node -
+ *		Generate the intersection of the results of sub-plans.
+ *
+ * The subplans must be of types that yield tuple bitmaps.  The targetlist
+ * and qual fields of the plan are unused and are always NIL.
+ * ----------------
+ */
+typedef struct BitmapAnd
+{
+	Plan		plan;
+	List	   *bitmapplans;
+} BitmapAnd;
+
+/* ----------------
+ *	 BitmapOr node -
+ *		Generate the union of the results of sub-plans.
+ *
+ * The subplans must be of types that yield tuple bitmaps.  The targetlist
+ * and qual fields of the plan are unused and are always NIL.
+ * ----------------
+ */
+typedef struct BitmapOr
+{
+	Plan		plan;
+	List	   *bitmapplans;
+} BitmapOr;
+
 /*
  * ==========
  * Scan nodes
@@ -156,6 +184,8 @@ typedef Scan SeqScan;
  *
  * Note: this can actually represent N indexscans, all on the same table
  * but potentially using different indexes, put together with OR semantics.
+ * (XXX that extension should probably go away, because bitmapindexscan will
+ * largely eliminate the need for it.)
  * ----------------
  */
 typedef struct IndexScan
@@ -171,7 +201,46 @@ typedef struct IndexScan
 } IndexScan;
 
 /* ----------------
- *				tid scan node
+ *		bitmap index scan node
+ *
+ * BitmapIndexScan delivers a bitmap of potential tuple locations;
+ * it does not access the heap itself.  The bitmap is used by an
+ * ancestor BitmapHeapScan node, possibly after passing through
+ * intermediate BitmapAnd and/or BitmapOr nodes to combine it with
+ * the results of other BitmapIndexScans.
+ *
+ * In a BitmapIndexScan plan node, the targetlist and qual fields are
+ * not used and are always NIL.  The indxqualorig field is useless at
+ * run time too, but is saved for the benefit of EXPLAIN.
+ * ----------------
+ */
+typedef struct BitmapIndexScan
+{
+	Scan		scan;
+	Oid			indxid;			/* OID of index to scan */
+	List	   *indxqual;		/* list of index quals */
+	List	   *indxqualorig;	/* list of original forms of index quals */
+	List	   *indxstrategy;	/* list of strategy numbers */
+	List	   *indxsubtype;	/* list of strategy subtypes */
+} BitmapIndexScan;
+
+/* ----------------
+ *		bitmap sequential scan node
+ *
+ * This needs a copy of the qual conditions being used by the input index
+ * scans because there are various cases where we need to recheck the quals;
+ * for example, when the bitmap is lossy about the specific rows on a page
+ * that meet the index condition.
+ * ----------------
+ */
+typedef struct BitmapHeapScan
+{
+	Scan		scan;
+	List	   *bitmapqualorig;	/* index quals, in standard expr form */
+} BitmapHeapScan;
+
+/* ----------------
+ *		tid scan node
  * ----------------
  */
 typedef struct TidScan
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 4698e4d8cb..2e4e1834fe 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.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/nodes/relation.h,v 1.104 2005/03/27 06:29:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.105 2005/04/19 22:35:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -342,6 +342,9 @@ typedef struct Path
  * tuples matched during any scan.	(The executor is smart enough not to return
  * the same tuple more than once, even if it is matched in multiple scans.)
  *
+ * XXX bitmap index scans will probably obviate the need for plain OR
+ * indexscans, allowing a lot of this to be simplified.
+ *
  * 'indexinfo' is a list of IndexOptInfo nodes, one per scan to be performed.
  *
  * 'indexclauses' is a list of index qualifications, also one per scan.
@@ -390,6 +393,30 @@ typedef struct IndexPath
 } IndexPath;
 
 /*
+ * BitmapHeapPath represents one or more indexscans that generate TID bitmaps
+ * instead of directly accessing the heap, followed by AND/OR combinations
+ * to produce a single bitmap, followed by a heap scan that uses the bitmap.
+ * Note that the output is always considered unordered, since it will come
+ * out in physical heap order no matter what the underlying indexes did.
+ *
+ * The individual indexscans are represented by IndexPath nodes, and any
+ * logic on top of them is represented by regular AND and OR expressions.
+ * Notice that we can use the same IndexPath node both to represent an
+ * ordered index scan, and as the child of a BitmapHeapPath that represents
+ * scanning the same index in an unordered way.
+ *
+ * BitmapHeapPaths can be nestloop inner indexscans.  The isjoininner and
+ * rows fields serve the same purpose as for plain IndexPaths.
+ */
+typedef struct BitmapHeapPath
+{
+	Path		path;
+	Node	   *bitmapqual;		/* the IndexPath/AND/OR tree */
+	bool		isjoininner;	/* T if it's a nestloop inner scan */
+	double		rows;			/* estimated number of result tuples */
+} BitmapHeapPath;
+
+/*
  * TidPath represents a scan by TID
  *
  * tideval is an implicitly OR'ed list of quals of the form CTID = something.
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 9e379dd0c4..8b1445dadf 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.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/optimizer/cost.h,v 1.63 2005/03/27 06:29:49 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.64 2005/04/19 22:35:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,8 @@ extern double clamp_row_est(double nrows);
 extern void cost_seqscan(Path *path, Query *root, RelOptInfo *baserel);
 extern void cost_index(Path *path, Query *root, IndexOptInfo *index,
 		   List *indexQuals, bool is_injoin);
+extern void cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel,
+							 Node *bitmapqual, bool is_injoin);
 extern void cost_tidscan(Path *path, Query *root,
 			 RelOptInfo *baserel, List *tideval);
 extern void cost_subqueryscan(Path *path, RelOptInfo *baserel);
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 44e9b087b3..308c5daa6c 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.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/optimizer/pathnode.h,v 1.57 2005/03/27 06:29:49 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.58 2005/04/19 22:35:18 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -33,6 +33,9 @@ extern IndexPath *create_index_path(Query *root,
 				  List *restriction_clauses,
 				  List *pathkeys,
 				  ScanDirection indexscandir);
+extern BitmapHeapPath *create_bitmap_heap_path(Query *root,
+											   RelOptInfo *rel,
+											   Node *bitmapqual);
 extern TidPath *create_tidscan_path(Query *root, RelOptInfo *rel,
 					List *tideval);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);