Rethink original decision to use AND/OR Expr nodes to represent bitmap

logic operations during planning.  Seems cleaner to create two new Path
node types, instead --- this avoids duplication of cost-estimation code.
Also, create an enable_bitmapscan GUC parameter to control use of bitmap
plans.

16 files changed, 338 insertions, 193 deletions

diff --git a/doc/src/sgml/runtime.sgml b/doc/src/sgml/runtime.sgml
index e5567abf279..72bc1ff17e3 100644
--- a/doc/src/sgml/runtime.sgml
+++ b/doc/src/sgml/runtime.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/runtime.sgml,v 1.313 2005/04/08 00:59:57 neilc Exp $
+$PostgreSQL: pgsql/doc/src/sgml/runtime.sgml,v 1.314 2005/04/21 19:18:12 tgl Exp $
 -->
 
 <chapter Id="runtime">
@@ -1768,6 +1768,22 @@ archive_command = 'copy "%p" /mnt/server/archivedir/"%f"'  # Windows
       </para>
 
      <variablelist>
+     <varlistentry id="guc-enable-bitmapscan" xreflabel="enable_bitmapscan">
+      <term><varname>enable_bitmapscan</varname> (<type>boolean</type>)</term>
+      <indexterm>
+       <primary>bitmap scan</primary>
+      </indexterm>
+      <indexterm>
+       <primary><varname>enable_bitmapscan</> configuration parameter</primary>
+      </indexterm>
+      <listitem>
+       <para>
+        Enables or disables the query planner's use of bitmap-scan plan
+        types. The default is on.
+       </para>
+      </listitem>
+     </varlistentry>
+
      <varlistentry id="guc-enable-hashagg" xreflabel="enable_hashagg">
       <term><varname>enable_hashagg</varname> (<type>boolean</type>)</term>
       <indexterm>
@@ -4094,7 +4110,7 @@ plruby.bar = true        # generates error, unknown class name
 
        <row>
         <entry>
-          <option>-fi</option>, <option>-fh</option>,
+          <option>-fb</option>, <option>-fh</option>, <option>-fi</option>,
           <option>-fm</option>, <option>-fn</option>,
           <option>-fs</option>, <option>-ft</option><footnote
           id="fn.runtime-config-short">
@@ -4111,8 +4127,9 @@ $ <userinput>postmaster -o '-S 1024 -s'</userinput>
           </footnote>
          </entry>
          <entry>
-          <literal>enable_indexscan = off</>,
+          <literal>enable_bitmapscan = off</>,
           <literal>enable_hashjoin = off</>,
+          <literal>enable_indexscan = off</>,
           <literal>enable_mergejoin = off</>,
           <literal>enable_nestloop = off</>,
           <literal>enable_seqscan = off</>,
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 1ea59314ea2..c1c6ac09f48 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.248 2005/04/21 02:28:01 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.249 2005/04/21 19:18:12 tgl Exp $
  *
  * NOTES
  *	  Every node type that can appear in stored rules' parsetrees *must*
@@ -1042,6 +1042,28 @@ _outBitmapHeapPath(StringInfo str, BitmapHeapPath *node)
 }
 
 static void
+_outBitmapAndPath(StringInfo str, BitmapAndPath *node)
+{
+	WRITE_NODE_TYPE("BITMAPANDPATH");
+
+	_outPathInfo(str, (Path *) node);
+
+	WRITE_NODE_FIELD(bitmapquals);
+	WRITE_FLOAT_FIELD(bitmapselectivity, "%.4f");
+}
+
+static void
+_outBitmapOrPath(StringInfo str, BitmapOrPath *node)
+{
+	WRITE_NODE_TYPE("BITMAPORPATH");
+
+	_outPathInfo(str, (Path *) node);
+
+	WRITE_NODE_FIELD(bitmapquals);
+	WRITE_FLOAT_FIELD(bitmapselectivity, "%.4f");
+}
+
+static void
 _outTidPath(StringInfo str, TidPath *node)
 {
 	WRITE_NODE_TYPE("TIDPATH");
@@ -1853,6 +1875,12 @@ _outNode(StringInfo str, void *obj)
 			case T_BitmapHeapPath:
 				_outBitmapHeapPath(str, obj);
 				break;
+			case T_BitmapAndPath:
+				_outBitmapAndPath(str, obj);
+				break;
+			case T_BitmapOrPath:
+				_outBitmapOrPath(str, obj);
+				break;
 			case T_TidPath:
 				_outTidPath(str, obj);
 				break;
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index 55ad1d74000..174ad4fd0a0 100644
--- a/src/backend/optimizer/README
+++ b/src/backend/optimizer/README
@@ -255,6 +255,7 @@ RelOptInfo      - a relation or joined relations
  Path           - every way to generate a RelOptInfo(sequential,index,joins)
   SeqScan       - a plain Path node with pathtype = T_SeqScan
   IndexPath     - index scans
+  BitmapHeapPath - top of a bitmapped index scan
   TidPath       - scan by CTID
   AppendPath    - append multiple subpaths together
   ResultPath    - a Result plan node (used for variable-free tlist or qual)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index dc5091c69af..9ad3a73e942 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.126 2005/04/19 22:35:15 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.127 2005/04/21 19:18:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -901,6 +901,12 @@ print_path(Query *root, Path *path, int indent)
 		case T_BitmapHeapPath:
 			ptype = "BitmapHeapScan";
 			break;
+		case T_BitmapAndPath:
+			ptype = "BitmapAndPath";
+			break;
+		case T_BitmapOrPath:
+			ptype = "BitmapOrPath";
+			break;
 		case T_TidPath:
 			ptype = "TidScan";
 			break;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index a33ba0f796f..2afaa2a655e 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -49,7 +49,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.143 2005/04/21 02:28:01 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.144 2005/04/21 19:18:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -94,6 +94,7 @@ Cost		disable_cost = 100000000.0;
 
 bool		enable_seqscan = true;
 bool		enable_indexscan = true;
+bool		enable_bitmapscan = true;
 bool		enable_tidscan = true;
 bool		enable_sort = true;
 bool		enable_hashagg = true;
@@ -103,7 +104,7 @@ bool		enable_hashjoin = true;
 
 
 static bool cost_qual_eval_walker(Node *node, QualCost *total);
-static Selectivity cost_bitmap_qual(Node *bitmapqual, Cost *totalCost);
+static void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
 static Selectivity approx_selectivity(Query *root, List *quals,
 				   JoinType jointype);
 static Selectivity join_in_selectivity(JoinPath *path, Query *root);
@@ -292,7 +293,7 @@ cost_index(IndexPath *path, Query *root,
 					 PointerGetDatum(&indexCorrelation));
 
 	/*
-	 * Save amcostestimate's results for possible use by cost_bitmap_scan.
+	 * Save amcostestimate's results for possible use in bitmap scan planning.
 	 * We don't bother to save indexStartupCost or indexCorrelation, because
 	 * a bitmap scan doesn't care about either.
 	 */
@@ -414,19 +415,19 @@ cost_index(IndexPath *path, Query *root,
 }
 
 /*
- * cost_bitmap_scan
+ * cost_bitmap_heap_scan
  *	  Determines and returns the cost of scanning a relation using a bitmap
  *	  index-then-heap plan.
  *
  * 'root' is the query root
  * 'baserel' is the relation to be scanned
- * 'bitmapqual' is an AND/OR tree of IndexPaths for the component scans
+ * 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
  * 'is_injoin' is T if we are considering using the scan as the inside
  *		of a nestloop join (hence, some of the quals are join clauses)
  */
 void
-cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel,
-				 Node *bitmapqual, bool is_injoin)
+cost_bitmap_heap_scan(Path *path, Query *root, RelOptInfo *baserel,
+					  Path *bitmapqual, bool is_injoin)
 {
 	Cost		startup_cost = 0;
 	Cost		run_cost = 0;
@@ -443,15 +444,14 @@ cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel,
 	Assert(baserel->relid > 0);
 	Assert(baserel->rtekind == RTE_RELATION);
 
-	if (!enable_indexscan)		/* XXX use a separate enable flag? */
+	if (!enable_bitmapscan)
 		startup_cost += disable_cost;
 
 	/*
-	 * Estimate total cost of obtaining the bitmap, as well as its total
+	 * Fetch total cost of obtaining the bitmap, as well as its total
 	 * selectivity.
 	 */
-	indexTotalCost = 0;
-	indexSelectivity = cost_bitmap_qual(bitmapqual, &indexTotalCost);
+	cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
 
 	startup_cost += indexTotalCost;
 
@@ -497,82 +497,120 @@ cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel,
 }
 
 /*
- * cost_bitmap_qual
- *		Recursively examine the AND/OR/IndexPath tree for a bitmap scan
- *
- * Total execution costs are added to *totalCost (so caller must be sure
- * to initialize that to zero).  Estimated total selectivity of the bitmap
- * is returned as the function result.
+ * cost_bitmap_tree_node
+ *		Extract cost and selectivity from a bitmap tree node (index/and/or)
  */
-static Selectivity
-cost_bitmap_qual(Node *bitmapqual, Cost *totalCost)
+static void
+cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
 {
-	Selectivity	result;
-	Selectivity	subresult;
-	ListCell   *l;
-
-	if (and_clause(bitmapqual))
+	if (IsA(path, IndexPath))
 	{
-		/*
-		 * We estimate AND selectivity on the assumption that the inputs
-		 * are independent.  This is probably often wrong, but we don't
-		 * have the info to do better.
-		 *
-		 * The runtime cost of the BitmapAnd itself is estimated at 100x
-		 * cpu_operator_cost for each tbm_intersect needed.  Probably too
-		 * small, definitely too simplistic?
-		 *
-		 * This must agree with make_bitmap_and in createplan.c.
-		 */
-		result = 1.0;
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
-		{
-			subresult = cost_bitmap_qual((Node *) lfirst(l), totalCost);
-			result *= subresult;
-			if (l != list_head(((BoolExpr *) bitmapqual)->args))
-				*totalCost += 100.0 * cpu_operator_cost;
-		}
+		*cost = ((IndexPath *) path)->indextotalcost;
+		*selec = ((IndexPath *) path)->indexselectivity;
 	}
-	else if (or_clause(bitmapqual))
+	else if (IsA(path, BitmapAndPath))
 	{
-		/*
-		 * We estimate OR selectivity on the assumption that the inputs
-		 * are non-overlapping, since that's often the case in "x IN (list)"
-		 * type situations.  Of course, we clamp to 1.0 at the end.
-		 *
-		 * The runtime cost of the BitmapOr itself is estimated at 100x
-		 * cpu_operator_cost for each tbm_union needed.  Probably too
-		 * small, definitely too simplistic?  We are aware that the tbm_unions
-		 * are optimized out when the inputs are BitmapIndexScans.
-		 *
-		 * This must agree with make_bitmap_or in createplan.c.
-		 */
-		result = 0.0;
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
-		{
-			subresult = cost_bitmap_qual((Node *) lfirst(l), totalCost);
-			result += subresult;
-			if (l != list_head(((BoolExpr *) bitmapqual)->args) &&
-				!IsA((Node *) lfirst(l), IndexPath))
-				*totalCost += 100.0 * cpu_operator_cost;
-		}
-		result = Min(result, 1.0);
+		*cost = path->total_cost;
+		*selec = ((BitmapAndPath *) path)->bitmapselectivity;
 	}
-	else if (IsA(bitmapqual, IndexPath))
+	else if (IsA(path, BitmapOrPath))
 	{
-		IndexPath *ipath = (IndexPath *) bitmapqual;
-
-		/* this must agree with create_bitmap_subplan in createplan.c */
-		*totalCost += ipath->indextotalcost;
-		result = ipath->indexselectivity;
+		*cost = path->total_cost;
+		*selec = ((BitmapOrPath *) path)->bitmapselectivity;
 	}
 	else
+		elog(ERROR, "unrecognized node type: %d", nodeTag(path));
+}
+
+/*
+ * cost_bitmap_and_node
+ *		Estimate the cost of a BitmapAnd node
+ *
+ * Note that this considers only the costs of index scanning and bitmap
+ * creation, not the eventual heap access.  In that sense the object isn't
+ * truly a Path, but it has enough path-like properties (costs in particular)
+ * to warrant treating it as one.
+ */
+void
+cost_bitmap_and_node(BitmapAndPath *path, Query *root)
+{
+	Cost		totalCost;
+	Selectivity	selec;
+	ListCell   *l;
+
+	/*
+	 * We estimate AND selectivity on the assumption that the inputs
+	 * are independent.  This is probably often wrong, but we don't
+	 * have the info to do better.
+	 *
+	 * The runtime cost of the BitmapAnd itself is estimated at 100x
+	 * cpu_operator_cost for each tbm_intersect needed.  Probably too
+	 * small, definitely too simplistic?
+	 */
+	totalCost = 0.0;
+	selec = 1.0;
+	foreach(l, path->bitmapquals)
 	{
-		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
-		result = 0.0;				/* keep compiler quiet */
+		Path   *subpath = (Path *) lfirst(l);
+		Cost	subCost;
+		Selectivity subselec;
+
+		cost_bitmap_tree_node(subpath, &subCost, &subselec);
+
+		selec *= subselec;
+
+		totalCost += subCost;
+		if (l != list_head(path->bitmapquals))
+			totalCost += 100.0 * cpu_operator_cost;
 	}
+	path->bitmapselectivity = selec;
+	path->path.startup_cost = totalCost;
+	path->path.total_cost = totalCost;
+}
+
+/*
+ * cost_bitmap_or_node
+ *		Estimate the cost of a BitmapOr node
+ *
+ * See comments for cost_bitmap_and_node.
+ */
+void
+cost_bitmap_or_node(BitmapOrPath *path, Query *root)
+{
+	Cost		totalCost;
+	Selectivity	selec;
+	ListCell   *l;
+
+	/*
+	 * We estimate OR selectivity on the assumption that the inputs
+	 * are non-overlapping, since that's often the case in "x IN (list)"
+	 * type situations.  Of course, we clamp to 1.0 at the end.
+	 *
+	 * The runtime cost of the BitmapOr itself is estimated at 100x
+	 * cpu_operator_cost for each tbm_union needed.  Probably too
+	 * small, definitely too simplistic?  We are aware that the tbm_unions
+	 * are optimized out when the inputs are BitmapIndexScans.
+	 */
+	totalCost = 0.0;
+	selec = 0.0;
+	foreach(l, path->bitmapquals)
+	{
+		Path   *subpath = (Path *) lfirst(l);
+		Cost	subCost;
+		Selectivity subselec;
 
-	return result;
+		cost_bitmap_tree_node(subpath, &subCost, &subselec);
+
+		selec += subselec;
+
+		totalCost += subCost;
+		if (l != list_head(path->bitmapquals) &&
+			!IsA(subpath, IndexPath))
+			totalCost += 100.0 * cpu_operator_cost;
+	}
+	path->bitmapselectivity = Min(selec, 1.0);
+	path->path.startup_cost = totalCost;
+	path->path.total_cost = totalCost;
 }
 
 /*
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 0abb900beaa..faaf727da0d 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.181 2005/04/21 02:28:01 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.182 2005/04/21 19:18:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -51,9 +51,9 @@ static IndexScan *create_indexscan_plan(Query *root, IndexPath *best_path,
 static BitmapHeapScan *create_bitmap_scan_plan(Query *root,
 											   BitmapHeapPath *best_path,
 											   List *tlist, List *scan_clauses);
-static Plan *create_bitmap_subplan(Query *root, Node *bitmapqual);
-static List *create_bitmap_qual(Node *bitmapqual);
-static List *create_bitmap_indxqual(Node *bitmapqual);
+static Plan *create_bitmap_subplan(Query *root, Path *bitmapqual);
+static List *create_bitmap_qual(Path *bitmapqual);
+static List *create_bitmap_indxqual(Path *bitmapqual);
 static TidScan *create_tidscan_plan(Query *root, TidPath *best_path,
 					List *tlist, List *scan_clauses);
 static SubqueryScan *create_subqueryscan_plan(Query *root, Path *best_path,
@@ -928,37 +928,41 @@ create_bitmap_scan_plan(Query *root,
  * Given a bitmapqual tree, generate the Plan tree that implements it
  */
 static Plan *
-create_bitmap_subplan(Query *root, Node *bitmapqual)
+create_bitmap_subplan(Query *root, Path *bitmapqual)
 {
 	Plan	   *plan;
-	Plan	   *subplan;
 
-	if (bitmapqual == NULL)
-		return NULL;			/* probably can't happen */
-	if (IsA(bitmapqual, List))
+	if (IsA(bitmapqual, BitmapAndPath))
 	{
-		/* this case is to handle the List arguments of AND/OR */
+		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
 		List	   *newlist = NIL;
 		ListCell   *l;
 
-		foreach(l, (List *) bitmapqual)
+		foreach(l, apath->bitmapquals)
 		{
-			subplan = create_bitmap_subplan(root, lfirst(l));
+			Plan   *subplan = create_bitmap_subplan(root, lfirst(l));
+
 			newlist = lappend(newlist, subplan);
 		}
-		plan = (Plan *) newlist;
-	}
-	else if (and_clause(bitmapqual))
-	{
-		subplan = create_bitmap_subplan(root,
-									(Node *) ((BoolExpr *) bitmapqual)->args);
-		plan = (Plan *) make_bitmap_and((List *) subplan);
+		plan = (Plan *) make_bitmap_and(newlist);
+		copy_path_costsize(plan, bitmapqual);
+		plan->plan_width = 0;	/* meaningless */
 	}
-	else if (or_clause(bitmapqual))
+	else if (IsA(bitmapqual, BitmapOrPath))
 	{
-		subplan = create_bitmap_subplan(root,
-									(Node *) ((BoolExpr *) bitmapqual)->args);
-		plan = (Plan *) make_bitmap_or((List *) subplan);
+		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
+		List	   *newlist = NIL;
+		ListCell   *l;
+
+		foreach(l, opath->bitmapquals)
+		{
+			Plan   *subplan = create_bitmap_subplan(root, lfirst(l));
+
+			newlist = lappend(newlist, subplan);
+		}
+		plan = (Plan *) make_bitmap_or(newlist);
+		copy_path_costsize(plan, bitmapqual);
+		plan->plan_width = 0;	/* meaningless */
 	}
 	else if (IsA(bitmapqual, IndexPath))
 	{
@@ -976,7 +980,6 @@ create_bitmap_subplan(Query *root, Node *bitmapqual)
 									  linitial(iscan->indxqualorig),
 									  linitial(iscan->indxstrategy),
 									  linitial(iscan->indxsubtype));
-		/* this must agree with cost_bitmap_qual in costsize.c */
 		bscan->scan.plan.startup_cost = 0.0;
 		bscan->scan.plan.total_cost = ipath->indextotalcost;
 		bscan->scan.plan.plan_rows =
@@ -999,28 +1002,30 @@ create_bitmap_subplan(Query *root, Node *bitmapqual)
  * The result is expressed as an implicit-AND list.
  */
 static List *
-create_bitmap_qual(Node *bitmapqual)
+create_bitmap_qual(Path *bitmapqual)
 {
 	List	   *result;
 	List	   *sublist;
 
-	if (and_clause(bitmapqual))
+	if (IsA(bitmapqual, BitmapAndPath))
 	{
+		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
 		ListCell   *l;
 
 		result = NIL;
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
+		foreach(l, apath->bitmapquals)
 		{
 			sublist = create_bitmap_qual(lfirst(l));
 			result = list_concat(result, sublist);
 		}
 	}
-	else if (or_clause(bitmapqual))
+	else if (IsA(bitmapqual, BitmapOrPath))
 	{
+		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
 		List	   *newlist = NIL;
 		ListCell   *l;
 
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
+		foreach(l, opath->bitmapquals)
 		{
 			sublist = create_bitmap_qual(lfirst(l));
 			if (sublist == NIL)
@@ -1056,26 +1061,29 @@ create_bitmap_qual(Node *bitmapqual)
  * to enforce, which may be weaker than the original qual expressions.
  */
 static List *
-create_bitmap_indxqual(Node *bitmapqual)
+create_bitmap_indxqual(Path *bitmapqual)
 {
 	List	   *result;
 	List	   *sublist;
 	ListCell   *l;
 
-	if (and_clause(bitmapqual))
+	if (IsA(bitmapqual, BitmapAndPath))
 	{
+		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
+
 		result = NIL;
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
+		foreach(l, apath->bitmapquals)
 		{
 			sublist = create_bitmap_indxqual(lfirst(l));
 			result = list_concat(result, sublist);
 		}
 	}
-	else if (or_clause(bitmapqual))
+	else if (IsA(bitmapqual, BitmapOrPath))
 	{
+		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
 		List	   *newlist = NIL;
 
-		foreach(l, ((BoolExpr *) bitmapqual)->args)
+		foreach(l, opath->bitmapquals)
 		{
 			sublist = create_bitmap_indxqual(lfirst(l));
 			if (sublist == NIL)
@@ -2067,34 +2075,8 @@ make_bitmap_and(List *bitmapplans)
 {
 	BitmapAnd  *node = makeNode(BitmapAnd);
 	Plan	   *plan = &node->plan;
-	ListCell   *subnode;
-
-	/*
-	 * Compute cost as sum of subplan costs, plus 100x cpu_operator_cost
-	 * (a pretty arbitrary amount, agreed) for each tbm_intersect needed.
-	 * This must agree with cost_bitmap_qual in costsize.c.
-	 */
-	plan->startup_cost = 0;
-	plan->total_cost = 0;
-	plan->plan_rows = 0;
-	plan->plan_width = 0;		/* meaningless */
-	foreach(subnode, bitmapplans)
-	{
-		Plan	   *subplan = (Plan *) lfirst(subnode);
-
-		if (subnode == list_head(bitmapplans))	/* first node? */
-		{
-			plan->startup_cost = subplan->startup_cost;
-			plan->plan_rows = subplan->plan_rows;
-		}
-		else
-		{
-			plan->total_cost += cpu_operator_cost * 100.0;
-			plan->plan_rows = Min(plan->plan_rows, subplan->plan_rows);
-		}
-		plan->total_cost += subplan->total_cost;
-	}
 
+	/* cost should be inserted by caller */
 	plan->targetlist = NIL;
 	plan->qual = NIL;
 	plan->lefttree = NULL;
@@ -2109,32 +2091,8 @@ make_bitmap_or(List *bitmapplans)
 {
 	BitmapOr   *node = makeNode(BitmapOr);
 	Plan	   *plan = &node->plan;
-	ListCell   *subnode;
-
-	/*
-	 * Compute cost as sum of subplan costs, plus 100x cpu_operator_cost
-	 * (a pretty arbitrary amount, agreed) for each tbm_union needed.
-	 * We assume that tbm_union can be optimized away for BitmapIndexScan
-	 * subplans.
-	 *
-	 * This must agree with cost_bitmap_qual in costsize.c.
-	 */
-	plan->startup_cost = 0;
-	plan->total_cost = 0;
-	plan->plan_rows = 0;
-	plan->plan_width = 0;		/* meaningless */
-	foreach(subnode, bitmapplans)
-	{
-		Plan	   *subplan = (Plan *) lfirst(subnode);
-
-		if (subnode == list_head(bitmapplans))	/* first node? */
-			plan->startup_cost = subplan->startup_cost;
-		else if (!IsA(subplan, BitmapIndexScan))
-			plan->total_cost += cpu_operator_cost * 100.0;
-		plan->total_cost += subplan->total_cost;
-		plan->plan_rows += subplan->plan_rows; /* ignore overlap */
-	}
 
+	/* cost should be inserted by caller */
 	plan->targetlist = NIL;
 	plan->qual = NIL;
 	plan->lefttree = NULL;
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 823486e2f3b..d0c81073c3f 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.117 2005/04/21 02:28:01 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.118 2005/04/21 19:18:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -475,12 +475,12 @@ create_index_path(Query *root,
  * create_bitmap_heap_path
  *	  Creates a path node for a bitmap scan.
  *
- * 'bitmapqual' is an AND/OR tree of IndexPath nodes.
+ * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
  */
 BitmapHeapPath *
 create_bitmap_heap_path(Query *root,
 						RelOptInfo *rel,
-						Node *bitmapqual)
+						Path *bitmapqual)
 {
 	BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
 
@@ -499,7 +499,53 @@ create_bitmap_heap_path(Query *root,
 	 */
 	pathnode->rows = rel->rows;
 
-	cost_bitmap_scan(&pathnode->path, root, rel, bitmapqual, false);
+	cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, false);
+
+	return pathnode;
+}
+
+/*
+ * create_bitmap_and_path
+ *	  Creates a path node representing a BitmapAnd.
+ */
+BitmapAndPath *
+create_bitmap_and_path(Query *root,
+					   RelOptInfo *rel,
+					   List *bitmapquals)
+{
+	BitmapAndPath *pathnode = makeNode(BitmapAndPath);
+
+	pathnode->path.pathtype = T_BitmapAnd;
+	pathnode->path.parent = rel;
+	pathnode->path.pathkeys = NIL;			/* always unordered */
+
+	pathnode->bitmapquals = bitmapquals;
+
+	/* this sets bitmapselectivity as well as the regular cost fields: */
+	cost_bitmap_and_node(pathnode, root);
+
+	return pathnode;
+}
+
+/*
+ * create_bitmap_or_path
+ *	  Creates a path node representing a BitmapOr.
+ */
+BitmapOrPath *
+create_bitmap_or_path(Query *root,
+					  RelOptInfo *rel,
+					  List *bitmapquals)
+{
+	BitmapOrPath *pathnode = makeNode(BitmapOrPath);
+
+	pathnode->path.pathtype = T_BitmapOr;
+	pathnode->path.parent = rel;
+	pathnode->path.pathkeys = NIL;			/* always unordered */
+
+	pathnode->bitmapquals = bitmapquals;
+
+	/* this sets bitmapselectivity as well as the regular cost fields: */
+	cost_bitmap_or_node(pathnode, root);
 
 	return pathnode;
 }
diff --git a/src/backend/tcop/postgres.c b/src/backend/tcop/postgres.c
index 381d0e61102..2872d939ca8 100644
--- a/src/backend/tcop/postgres.c
+++ b/src/backend/tcop/postgres.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/tcop/postgres.c,v 1.442 2005/02/22 04:37:17 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/tcop/postgres.c,v 1.443 2005/04/21 19:18:13 tgl Exp $
  *
  * NOTES
  *	  this is the "main" module of the postgres backend and
@@ -2371,6 +2371,9 @@ PostgresMain(int argc, char *argv[], const char *username)
 					case 'i':	/* indexscan */
 						tmp = "enable_indexscan";
 						break;
+					case 'b':	/* bitmapscan */
+						tmp = "enable_bitmapscan";
+						break;
 					case 't':	/* tidscan */
 						tmp = "enable_tidscan";
 						break;
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 711ecd077e2..646f9c7a851 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -10,7 +10,7 @@
  * Written by Peter Eisentraut <peter_e@gmx.net>.
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/utils/misc/guc.c,v 1.259 2005/04/13 18:54:56 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/utils/misc/guc.c,v 1.260 2005/04/21 19:18:13 tgl Exp $
  *
  *--------------------------------------------------------------------
  */
@@ -370,6 +370,14 @@ static struct config_bool ConfigureNamesBool[] =
 		true, NULL, NULL
 	},
 	{
+		{"enable_bitmapscan", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables the planner's use of bitmap-scan plans."),
+			NULL
+		},
+		&enable_bitmapscan,
+		true, NULL, NULL
+	},
+	{
 		{"enable_tidscan", PGC_USERSET, QUERY_TUNING_METHOD,
 			gettext_noop("Enables the planner's use of TID scan plans."),
 			NULL
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 6b06afcb7fd..b175236883a 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -137,6 +137,7 @@
 
 # - Planner Method Configuration -
 
+#enable_bitmapscan = true
 #enable_hashagg = true
 #enable_hashjoin = true
 #enable_indexscan = true
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index f8645f030c2..86df578aae2 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -3,7 +3,7 @@
  *
  * Copyright (c) 2000-2005, PostgreSQL Global Development Group
  *
- * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.124 2005/04/07 01:51:39 neilc Exp $
+ * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.125 2005/04/21 19:18:13 tgl Exp $
  */
 
 /*----------------------------------------------------------------------
@@ -533,6 +533,7 @@ psql_completion(char *text, int start, int end)
 		"default_with_oids",
 		"dynamic_library_path",
 		"effective_cache_size",
+		"enable_bitmapscan",
 		"enable_hashagg",
 		"enable_hashjoin",
 		"enable_indexscan",
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 32df3bff0eb..d69734f95e9 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.167 2005/04/19 22:35:17 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.168 2005/04/21 19:18:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -170,6 +170,8 @@ typedef enum NodeTag
 	T_Path,
 	T_IndexPath,
 	T_BitmapHeapPath,
+	T_BitmapAndPath,
+	T_BitmapOrPath,
 	T_NestPath,
 	T_MergePath,
 	T_HashPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 4ae0ae3a2c0..53cd96b6b28 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.106 2005/04/21 02:28:02 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.107 2005/04/21 19:18:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -406,7 +406,7 @@ typedef struct IndexPath
  * 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.
+ * logic on top of them is represented by BitmapAndPath and BitmapOrPath.
  * Notice that we can use the same IndexPath node both to represent a regular
  * IndexScan plan, and as the child of a BitmapHeapPath that represents
  * scanning the same index using a BitmapIndexScan.  The startup_cost and
@@ -420,12 +420,38 @@ typedef struct IndexPath
 typedef struct BitmapHeapPath
 {
 	Path		path;
-	Node	   *bitmapqual;		/* the IndexPath/AND/OR tree */
+	Path	   *bitmapqual;		/* IndexPath, BitmapAndPath, BitmapOrPath */
 	bool		isjoininner;	/* T if it's a nestloop inner scan */
 	double		rows;			/* estimated number of result tuples */
 } BitmapHeapPath;
 
 /*
+ * BitmapAndPath represents a BitmapAnd plan node; it can only appear as
+ * part of the substructure of a BitmapHeapPath.  The Path structure is
+ * a bit more heavyweight than we really need for this, but for simplicity
+ * we make it a derivative of Path anyway.
+ */
+typedef struct BitmapAndPath
+{
+	Path		path;
+	List	   *bitmapquals;		/* IndexPaths and BitmapOrPaths */
+	Selectivity bitmapselectivity;
+} BitmapAndPath;
+
+/*
+ * BitmapOrPath represents a BitmapOr plan node; it can only appear as
+ * part of the substructure of a BitmapHeapPath.  The Path structure is
+ * a bit more heavyweight than we really need for this, but for simplicity
+ * we make it a derivative of Path anyway.
+ */
+typedef struct BitmapOrPath
+{
+	Path		path;
+	List	   *bitmapquals;		/* IndexPaths and BitmapAndPaths */
+	Selectivity bitmapselectivity;
+} BitmapOrPath;
+
+/*
  * 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 1f7ea96ee04..b55c2366cf9 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.65 2005/04/21 02:28:02 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.66 2005/04/21 19:18:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -42,6 +42,7 @@ extern double cpu_operator_cost;
 extern Cost disable_cost;
 extern bool enable_seqscan;
 extern bool enable_indexscan;
+extern bool enable_bitmapscan;
 extern bool enable_tidscan;
 extern bool enable_sort;
 extern bool enable_hashagg;
@@ -53,8 +54,10 @@ extern double clamp_row_est(double nrows);
 extern void cost_seqscan(Path *path, Query *root, RelOptInfo *baserel);
 extern void cost_index(IndexPath *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_bitmap_heap_scan(Path *path, Query *root, RelOptInfo *baserel,
+								  Path *bitmapqual, bool is_injoin);
+extern void cost_bitmap_and_node(BitmapAndPath *path, Query *root);
+extern void cost_bitmap_or_node(BitmapOrPath *path, Query *root);
 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 308c5daa6cd..7881ed17536 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.58 2005/04/19 22:35:18 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.59 2005/04/21 19:18:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -35,7 +35,13 @@ extern IndexPath *create_index_path(Query *root,
 				  ScanDirection indexscandir);
 extern BitmapHeapPath *create_bitmap_heap_path(Query *root,
 											   RelOptInfo *rel,
-											   Node *bitmapqual);
+											   Path *bitmapqual);
+extern BitmapAndPath *create_bitmap_and_path(Query *root,
+											 RelOptInfo *rel,
+											 List *bitmapquals);
+extern BitmapOrPath *create_bitmap_or_path(Query *root,
+										   RelOptInfo *rel,
+										   List *bitmapquals);
 extern TidPath *create_tidscan_path(Query *root, RelOptInfo *rel,
 					List *tideval);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
diff --git a/src/test/regress/expected/rangefuncs.out b/src/test/regress/expected/rangefuncs.out
index 6caa7a1c7b5..7b70766742a 100644
--- a/src/test/regress/expected/rangefuncs.out
+++ b/src/test/regress/expected/rangefuncs.out
@@ -1,15 +1,16 @@
 SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
-       name       | setting 
-------------------+---------
- enable_hashagg   | on
- enable_hashjoin  | on
- enable_indexscan | on
- enable_mergejoin | on
- enable_nestloop  | on
- enable_seqscan   | on
- enable_sort      | on
- enable_tidscan   | on
-(8 rows)
+       name        | setting 
+-------------------+---------
+ enable_bitmapscan | on
+ enable_hashagg    | on
+ enable_hashjoin   | on
+ enable_indexscan  | on
+ enable_mergejoin  | on
+ enable_nestloop   | on
+ enable_seqscan    | on
+ enable_sort       | on
+ enable_tidscan    | on
+(9 rows)
 
 CREATE TABLE foo2(fooid int, f2 int);
 INSERT INTO foo2 VALUES(1, 11);