Add the ability to extract OR indexscan conditions from OR-of-AND

join conditions in which each OR subclause includes a constraint on
the same relation.  This implements the other useful side-effect of
conversion to CNF format, without its unpleasant side-effects.  As
per pghackers discussion of a few weeks ago.

4 files changed, 29 insertions, 16 deletions

diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 010adcc859..14486591da 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.90 2004/01/04 03:51:52 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.91 2004/01/05 05:07:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -321,6 +321,8 @@ typedef struct Path
 {
 	NodeTag		type;
 
+	NodeTag		pathtype;		/* tag identifying scan/join method */
+
 	RelOptInfo *parent;			/* the relation this path can build */
 
 	/* estimated execution costs for path (see costsize.c for more info) */
@@ -329,8 +331,6 @@ typedef struct Path
 	Cost		total_cost;		/* total cost (assuming all tuples
 								 * fetched) */
 
-	NodeTag		pathtype;		/* tag identifying scan/join method */
-
 	List	   *pathkeys;		/* sort ordering of path's output */
 	/* pathkeys is a List of Lists of PathKeyItem nodes; see above */
 } Path;
@@ -389,6 +389,9 @@ typedef struct IndexPath
 
 /*
  * TidPath represents a scan by TID
+ *
+ * tideval is an implicitly OR'ed list of quals of the form CTID = something.
+ * Note they are bare quals, not RestrictInfos.
  */
 typedef struct TidPath
 {
@@ -570,13 +573,17 @@ typedef struct HashPath
  * When we do form the outer join's joinrel, we still need to distinguish
  * those quals that are actually in that join's JOIN/ON condition from those
  * that appeared higher in the tree and were pushed down to the join rel
- * because they used no other rels.  That's what the ispusheddown flag is for;
- * it tells us that a qual came from a point above the join of the specific
- * set of base rels that it uses (or that the JoinInfo structures claim it
- * uses).  A clause that originally came from WHERE will *always* have its
- * ispusheddown flag set; a clause that came from an INNER JOIN condition,
- * but doesn't use all the rels being joined, will also have ispusheddown set
- * because it will get attached to some lower joinrel.
+ * because they used no other rels.  That's what the is_pushed_down flag is
+ * for; it tells us that a qual came from a point above the join of the
+ * specific set of base rels that it uses (or that the JoinInfo structures
+ * claim it uses).  A clause that originally came from WHERE will *always*
+ * have its is_pushed_down flag set; a clause that came from an INNER JOIN
+ * condition, but doesn't use all the rels being joined, will also have
+ * is_pushed_down set because it will get attached to some lower joinrel.
+ *
+ * We also store a valid_everywhere flag, which says that the clause is not
+ * affected by any lower-level outer join, and therefore any conditions it
+ * asserts can be presumed true throughout the plan tree.
  *
  * In general, the referenced clause might be arbitrarily complex.	The
  * kinds of clauses we can handle as indexscan quals, mergejoin clauses,
@@ -602,7 +609,9 @@ typedef struct RestrictInfo
 
 	Expr	   *clause;			/* the represented clause of WHERE or JOIN */
 
-	bool		ispusheddown;	/* TRUE if clause was pushed down in level */
+	bool		is_pushed_down;	/* TRUE if clause was pushed down in level */
+
+	bool		valid_everywhere;	/* TRUE if valid on every level */
 
 	/*
 	 * This flag is set true if the clause looks potentially useful as a
@@ -611,7 +620,7 @@ typedef struct RestrictInfo
 	 * (Whether the operator is actually merge or hash joinable isn't
 	 * checked, however.)
 	 */
-	bool		canjoin;
+	bool		can_join;
 
 	/* The set of relids (varnos) referenced in the clause: */
 	Relids		clause_relids;
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 15540a6664..002edfd91e 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.59 2004/01/04 03:51:52 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.60 2004/01/05 05:07:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -49,6 +49,7 @@ extern bool enable_nestloop;
 extern bool enable_mergejoin;
 extern bool enable_hashjoin;
 
+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,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 3e60d60802..e1a46bcb3f 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.71 2004/01/04 00:07:32 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.72 2004/01/05 05:07:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -43,11 +43,13 @@ extern List *group_clauses_by_indexkey_for_or(RelOptInfo *rel,
 											  Expr *orsubclause);
 extern List *expand_indexqual_conditions(IndexOptInfo *index,
 							List *clausegroups);
+extern void check_partial_indexes(Query *root, RelOptInfo *rel);
 
 /*
  * orindxpath.c
  *	  additional routines for indexable OR clauses
  */
+extern bool create_or_index_quals(Query *root, RelOptInfo *rel);
 extern void create_or_index_paths(Query *root, RelOptInfo *rel);
 
 /*
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 362ed26a61..022bfa253a 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.21 2004/01/04 00:07:32 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.22 2004/01/05 05:07:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,7 +16,8 @@
 
 #include "nodes/relation.h"
 
-extern RestrictInfo *make_restrictinfo(Expr *clause, bool ispusheddown);
+extern RestrictInfo *make_restrictinfo(Expr *clause, bool is_pushed_down,
+									   bool valid_everywhere);
 extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
 extern List *get_actual_clauses(List *restrictinfo_list);
 extern void get_actual_join_clauses(List *restrictinfo_list,