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.

5 files changed, 215 insertions, 166 deletions

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;
 }