"Constraint exclusion" is not general enough

I was just looking at Martin Lesser's gripe here:
http://archives.postgresql.org/pgsql-performance/2006-08/msg00053.php
about how the planner is not real bright about the filter conditions
it generates for a simple partitioning layout. In particular it's
generating scans involving self-contradictory conditions:

Result (cost=0.00..33.20 rows=6 width=36)
-> Append (cost=0.00..33.20 rows=6 width=36)
-> Seq Scan on t_parted (cost=0.00..33.20 rows=6 width=36)
Filter: ((id1 >= 0) AND (id1 < 100) AND (id1 >= 900) AND (id1 < 1000))

which it seems we ought to be bright enough to notice. In particular
I would argue that turning on constraint_exclusion ought to instruct
the planner to catch this sort of thing, whereas when it's off we
ought not expend the cycles. I have a preliminary patch (below)
that seems to fix it.

The problem I'm having is that this isn't "constraint exclusion" anymore
--- it will in fact make useful deductions without a table constraint
anywhere in sight. Should we rename the GUC variable, and if so to what?
Or just live with the misnomer? I guess plan C would be to invent a
separate GUC variable for the other kind of test, but I can't see that
it's worth having two. Thoughts?

BTW, the remaining infelicities in Martin's example stem from the fact that
predicate_refuted_by doesn't recognize "x IS NOT TRUE" as refuting "x".
Working on fixing that now.

I'm also thinking that formulating the check as "constraints are
refuted by WHERE clause" might be unnecessarily restrictive. Doesn't
the case where a constraint implies falsity of a WHERE clause likewise
tell us we needn't bother to scan? Seems like we ought to put all the
conditions together and run a symmetric test named something like
"mutually_exclusive_conditions". Maybe "mutual_exclusion" would be
a better name for the GUC variable.

regards, tom lane

*** src/backend/optimizer/util/plancat.c.orig Tue Aug 1 21:59:46 2006
--- src/backend/optimizer/util/plancat.c Fri Aug 4 13:56:18 2006
***************
*** 444,455 ****
--- 444,478 ----
bool
relation_excluded_by_constraints(RelOptInfo *rel, RangeTblEntry *rte)
{
+ List *safe_restrictions;
List *constraint_pred;
+ List *safe_constraints;
+ ListCell *lc;

/* Skip the test if constraint exclusion is disabled */
if (!constraint_exclusion)
return false;

+ /*
+ * Check for self-contradictory restriction clauses. We dare not make
+ * deductions with non-immutable functions, but any immutable clauses that
+ * are self-contradictory allow us to conclude the scan is unnecessary.
+ *
+ * Note: strip off RestrictInfo because predicate_refuted_by() isn't
+ * expecting to see any in its predicate argument.
+ */
+ safe_restrictions = NIL;
+ foreach(lc, rel->baserestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+ if (!contain_mutable_functions((Node *) rinfo->clause))
+ safe_restrictions = lappend(safe_restrictions, rinfo->clause);
+ }
+
+ if (predicate_refuted_by(safe_restrictions, safe_restrictions))
+ return true;
+
/* Only plain relations have constraints */
if (rte->rtekind != RTE_RELATION || rte->inh)
return false;