improve-boolean-index-matching.patch

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 2952bfb..7a1a498 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** relation_has_unique_index_for(PlannerInf
*** 3025,3030 ****
--- 3025,3076 ----
  	return false;
  }
  
+ /*
+  * indexcol_is_bool_constant_for_query
+  *
+  * If an index column is constrained to have a constant value by the query's
+  * WHERE conditions, then it's irrelevant for sort-order considerations.
+  * Usually that means we have a restriction clause WHERE indexcol = constant,
+  * which gets turned into an EquivalenceClass containing a constant, which
+  * is recognized as redundant by build_index_pathkeys().  But if the index
+  * column is a boolean variable (or expression), then we are not going to
+  * see WHERE indexcol = constant, because expression preprocessing will have
+  * simplified that to "WHERE indexcol" or "WHERE NOT indexcol".  So we are not
+  * going to have a matching EquivalenceClass (unless the query also contains
+  * "ORDER BY indexcol").  To allow such cases to work the same as they would
+  * for non-boolean values, this function is provided to detect whether the
+  * specified index column matches a boolean restriction clause.
+  */
+ bool
+ indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
+ {
+ 	ListCell   *lc;
+ 
+ 	/* If the index isn't boolean, we can't possibly get a match */
+ 	if (!IsBooleanOpfamily(index->opfamily[indexcol]))
+ 		return false;
+ 
+ 	/* Check each restriction clause for the index's rel */
+ 	foreach(lc, index->rel->baserestrictinfo)
+ 	{
+ 		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ 
+ 		/*
+ 		 * As in match_clause_to_indexcol, never match pseudoconstants to
+ 		 * indexes.  (It might be semantically okay to do so here, but the
+ 		 * odds of getting a match are negligible, so don't waste the cycles.)
+ 		 */
+ 		if (rinfo->pseudoconstant)
+ 			continue;
+ 
+ 		/* See if we can match the clause's expression to the index column */
+ 		if (match_boolean_index_clause((Node *) rinfo->clause, indexcol, index))
+ 			return true;
+ 	}
+ 
+ 	return false;
+ }
+ 
  
  /****************************************************************************
   *				----  ROUTINES TO CHECK OPERANDS  ----
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 4436ac1..459498c 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** build_index_pathkeys(PlannerInfo *root,
*** 480,496 ****
  											  index->rel->relids,
  											  false);
  
! 		/*
! 		 * If the sort key isn't already present in any EquivalenceClass, then
! 		 * it's not an interesting sort order for this query.  So we can stop
! 		 * now --- lower-order sort keys aren't useful either.
! 		 */
! 		if (!cpathkey)
! 			break;
! 
! 		/* Add to list unless redundant */
! 		if (!pathkey_is_redundant(cpathkey, retval))
! 			retval = lappend(retval, cpathkey);
  
  		i++;
  	}
--- 480,509 ----
  											  index->rel->relids,
  											  false);
  
! 		if (cpathkey)
! 		{
! 			/*
! 			 * We found the sort key in an EquivalenceClass, so it's relevant
! 			 * for this query.  Add it to list, unless it's redundant.
! 			 */
! 			if (!pathkey_is_redundant(cpathkey, retval))
! 				retval = lappend(retval, cpathkey);
! 		}
! 		else
! 		{
! 			/*
! 			 * Boolean index keys might be redundant even if they do not
! 			 * appear in an EquivalenceClass, because of our special treatment
! 			 * of boolean equality conditions --- see the comment for
! 			 * indexcol_is_bool_constant_for_query().  If that applies, we can
! 			 * continue to examine lower-order index columns.  Otherwise, the
! 			 * sort key is not an interesting sort order for this query, so we
! 			 * should stop considering index columns; any lower-order sort
! 			 * keys won't be useful either.
! 			 */
! 			if (!indexcol_is_bool_constant_for_query(index, i))
! 				break;
! 		}
  
  		i++;
  	}
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 44abe83..dbbb686 100644
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern void create_index_paths(PlannerIn
*** 66,71 ****
--- 66,73 ----
  extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  							  List *restrictlist,
  							  List *exprlist, List *oprlist);
+ extern bool indexcol_is_bool_constant_for_query(IndexOptInfo *index,
+ 									int indexcol);
  extern bool match_index_to_operand(Node *operand, int indexcol,
  					   IndexOptInfo *index);
  extern void expand_indexqual_conditions(IndexOptInfo *index,
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index e663f9a..c6dfb26 100644
*** a/src/test/regress/expected/create_index.out
--- b/src/test/regress/expected/create_index.out
*************** explain (costs off)
*** 2953,2958 ****
--- 2953,3000 ----
  (2 rows)
  
  --
+ -- Check matching of boolean index columns to WHERE conditions and sort keys
+ --
+ create temp table boolindex (b bool, i int, unique(b, i), junk float);
+ explain (costs off)
+   select * from boolindex order by b, i limit 10;
+                       QUERY PLAN                       
+ -------------------------------------------------------
+  Limit
+    ->  Index Scan using boolindex_b_i_key on boolindex
+ (2 rows)
+ 
+ explain (costs off)
+   select * from boolindex where b order by i limit 10;
+                       QUERY PLAN                       
+ -------------------------------------------------------
+  Limit
+    ->  Index Scan using boolindex_b_i_key on boolindex
+          Index Cond: (b = true)
+          Filter: b
+ (4 rows)
+ 
+ explain (costs off)
+   select * from boolindex where b = true order by i desc limit 10;
+                            QUERY PLAN                           
+ ----------------------------------------------------------------
+  Limit
+    ->  Index Scan Backward using boolindex_b_i_key on boolindex
+          Index Cond: (b = true)
+          Filter: b
+ (4 rows)
+ 
+ explain (costs off)
+   select * from boolindex where not b order by i limit 10;
+                       QUERY PLAN                       
+ -------------------------------------------------------
+  Limit
+    ->  Index Scan using boolindex_b_i_key on boolindex
+          Index Cond: (b = false)
+          Filter: (NOT b)
+ (4 rows)
+ 
+ --
  -- REINDEX (VERBOSE)
  --
  CREATE TABLE reindex_verbose(id integer primary key);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 71f4f54..822c34a 100644
*** a/src/test/regress/sql/create_index.sql
--- b/src/test/regress/sql/create_index.sql
*************** explain (costs off)
*** 1011,1016 ****
--- 1011,1031 ----
    select * from tenk1 where (thousand, tenthous) in ((1,1001), (null,null));
  
  --
+ -- Check matching of boolean index columns to WHERE conditions and sort keys
+ --
+ 
+ create temp table boolindex (b bool, i int, unique(b, i), junk float);
+ 
+ explain (costs off)
+   select * from boolindex order by b, i limit 10;
+ explain (costs off)
+   select * from boolindex where b order by i limit 10;
+ explain (costs off)
+   select * from boolindex where b = true order by i desc limit 10;
+ explain (costs off)
+   select * from boolindex where not b order by i limit 10;
+ 
+ --
  -- REINDEX (VERBOSE)
  --
  CREATE TABLE reindex_verbose(id integer primary key);