I've been thinking about Josh's recent complaint about poor planning
of queries like

SELECT t1.a, t2.b
FROM t1, t2
WHERE t1.a = t2.a
AND (
	( t1.c = x
	  AND t1.f IN (m, n, o)
	  AND t2.d = v
	  AND t2.e BETWEEN j AND k
	)
	OR
	( t1.c = y
	  AND t1.f IN (n, o, p)
	  AND t2.d = v
	  AND t2.e BETWEEN k AND h
	)
	OR 
	( t1.c = z
	  AND t1.f IN (p, q)
	  AND t2.d = w
	  AND t2.e BETWEEN k AND h
	)
	)

(which is an abstraction of Q19 in the TPC-R benchmark).  I believe that
most of the blame for this problem can be laid at the feet of 
optimizer/prep/prepqual.c, which attempts to transform the WHERE clause
into a canonical form (either CNF AND-of-ORs, or DNF OR-of-ANDs, according
to some heuristics that are not very compelling).  I am not certain
whether prepqual will actually fire on this query (still waiting for those
EXPLAIN results, Josh), but if it doesn't then it'd really be disastrous,
and if it does then it's still not going to improve matters much, because
forcing this WHERE into pure AND-of-ORs form isn't very helpful.

I've worked on prepqual.c some over the years, but it never occurred to me
to question the fundamental premise of creating a normal-form WHERE clause
before.  Yet as I look at this example, I'm wondering why we should try
to.

Josh lied a little bit about the TPC-R query: the form actually given in
the TPC spec is

WHERE
	(
	  t1.a = t2.a
	  AND t1.c = x
	  AND t1.f IN (m, n, o)
	  AND t2.d = v
	  AND t2.e BETWEEN j AND k
	)
	OR
	(
	  t1.a = t2.a
	  AND t1.c = y
	  AND t1.f IN (n, o, p)
	  AND t2.d = v
	  AND t2.e BETWEEN k AND h
	)
	etc

It is absolutely critical that the optimizer recognize that the "t1.a =
t2.a" clause is common to all the OR branches and can be factored out
to give the form Josh showed.  Without that, you don't have any equijoin
clause and you're going to end up with a horrid nested-loop join.
In the TPC query per spec, some of the other single-table restrictions are
also common to all the OR branches (ie, x, y, etc are not all different
constants) and should be pulled out so that they can be applied as
restriction clauses to the input tables before the join.

In other words, we'd like the optimizer to transform
	(a AND b) OR (a AND c)
to
	a AND (b OR c)

Currently, this is accomplished by the roundabout method of converting
the WHERE clause to CNF (AND-of-ORs) and then simplifying duplicate
sub-clauses within an OR:
	(a AND b) OR (a AND c)
expands by repeated application of the distributive law to
	(a OR a) AND (a OR c) AND (b OR a) AND (b OR c)
and then qual_cleanup notices that (a OR a) is redundant, leaving
	a AND (a OR c) AND (b OR a) AND (b OR c)
So we manage to pull out "a" all right, but we've left the query cluttered
with additional, redundant clauses --- there is no logic that will notice
that this could be simplified to
	a AND (b OR c)
The extra clauses make for useless work during planning and during
execution; they also screw up selectivity estimates (since the selectivity
estimator doesn't realize they are redundant).  This is bad.

So as a mechanism for pulling out duplicate clauses, canonicalization
sucks.  Is there anything else that it does for us?  After some thought
the only possible benefit I can see is that it can sometimes manufacture
restriction clauses from what otherwise would be join clauses.  In the
TPC-R example, once we've pulled out duplicate clauses we'd still be left
with an OR of ANDed conditions, some on t1 and some on t2.  If we leave
this as-is, there's not much to be done with it except apply it as a join
filter after the t1/t2 join is made.  However, if we force to CNF form
then some of the resulting sub-clauses will refer only to t1, some only
to t2, and some to both tables.  The ones that mention only t1 or only
t2 would be usable as restriction clauses during the table scans, which
is a big help in cutting the size of the required join.  Also they could
possibly be used as indexscan qualifications (I'm not sure whether TPC-R
expects relevant indexes to be in place).

So it seems to me that a reasonable heuristic for deciding whether to
CNF-ify an OR clause is to check whether any of the resulting subclauses
will refer to fewer relations than the original OR clause does.  If not,
we may as well leave it as an OR clause and avoid generating redundant
clauses.  There is no such test at present.

Pulling out duplicate clauses from the OR arms would probably be better
done directly than by relying on CNF-ification.

Another consideration is that the planner already has logic for generating
multi-indexscans by pulling relevant conditions out of OR-of-AND trees.
So, at least for the case where there's a relevant index, we do not need
any CNF conversion to be able to make a useful indexscan restriction
clause.  This fails to happen in the TPC-R example at the moment, but
only because the OR indexscan logic neglects to consider whether OR
trees that mention multiple relations might contain subclauses that
reference only the indexed relation.  It'd be pretty easy to fix that.
Is it worth doing CNF-ification at all, if the only value is to detect
possible restriction clauses that aren't related to indexes?

Comments?

			regards, tom lane

Wed, 10 Dec 2003 16:54:54 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Canonicalization of WHERE clauses considered harmful
On Wed, Dec 10, 2003 at 16:54:54 -0500,
  Tom Lane <tgl@sss.pgh.pa.us> wrote:
> In other words, we'd like the optimizer to transform
> 	(a AND b) OR (a AND c)
> to
> 	a AND (b OR c)
> 
> Currently, this is accomplished by the roundabout method of converting
> the WHERE clause to CNF (AND-of-ORs) and then simplifying duplicate
> sub-clauses within an OR:
> 	(a AND b) OR (a AND c)
> expands by repeated application of the distributive law to
> 	(a OR a) AND (a OR c) AND (b OR a) AND (b OR c)
> and then qual_cleanup notices that (a OR a) is redundant, leaving
> 	a AND (a OR c) AND (b OR a) AND (b OR c)
> So we manage to pull out "a" all right, but we've left the query cluttered
> with additional, redundant clauses --- there is no logic that will notice
> that this could be simplified to
> 	a AND (b OR c)
> The extra clauses make for useless work during planning and during
> execution; they also screw up selectivity estimates (since the selectivity
> estimator doesn't realize they are redundant).  This is bad.
 
> 
> Comments?

Shouldn't it be possible to simplify
a AND (a OR c) AND (b OR a) AND (b OR c)
to
a AND (b or c)
using
a AND (a OR x) == a
?

Wed, 10 Dec 2003 16:04:39 -0600
Bruno Wolff III <bruno@wolff.to>
Re: Canonicalization of WHERE clauses considered harmful
Bruno Wolff III <bruno@wolff.to> writes:
> Shouldn't it be possible to simplify
> a AND (a OR c) AND (b OR a) AND (b OR c)
> to
> a AND (b or c)
> using
> a AND (a OR x) == a

That would be one possible response, but it strikes me as a band-aid fix.
It would add quite a bit of overhead (looking to see if any OR
subclauses match any top-level clauses) on top of the rather expensive
equality checks qual_cleanup() is already making.  Another problem is
that sometimes prepqual decides not to attempt CNF-ification at all,
which means that the ability to pull out duplicate subclauses is lost
altogether.

I think it'd be cleaner to expend the cycles on a direct check for
duplicate subclauses, which we could apply independently of any decision
to convert what remains to CNF form.

We've had lots of problems with prepqual before, which is why those
heuristics about whether to try for CNF or DNF are in there; but I've
never been very happy about them.  What I'm on about now is the idea
that maybe the whole problem should be thrown overboard ...

			regards, tom lane

Wed, 10 Dec 2003 17:14:22 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Canonicalization of WHERE clauses considered harmful 
On Wed, Dec 10, 2003 at 04:54:54PM -0500, Tom Lane wrote:
> Currently, this is accomplished by the roundabout method of converting
> the WHERE clause to CNF (AND-of-ORs) and then simplifying duplicate
> sub-clauses within an OR:
> 	(a AND b) OR (a AND c)
> expands by repeated application of the distributive law to
> 	(a OR a) AND (a OR c) AND (b OR a) AND (b OR c)

This is wrong.

What would be true however is:

(a OR b) AND (b OR C)
= (a AND b) OR (a AND c) OR (b AND b) OR (b AND C)

(Replace AND by * and OR by +)


Kurt


Wed, 10 Dec 2003 23:19:56 +0100
Kurt Roeckx <Q@ping.be>
Re: Canonicalization of WHERE clauses considered harmful
Kurt Roeckx <Q@ping.be> writes:
> On Wed, Dec 10, 2003 at 04:54:54PM -0500, Tom Lane wrote:
>> (a AND b) OR (a AND c)
>> expands by repeated application of the distributive law to
>> (a OR a) AND (a OR c) AND (b OR a) AND (b OR c)

> This is wrong.

I don't think so.  The distributive law is

	a OR (b AND c) == (a OR b) AND (a OR c)

Starting from

	(a AND b) OR (x AND y)

prepqual.c applies the law once to produce

	((a AND b) OR x) AND ((a AND b) OR y)

and then twice more to obtain

	(a OR x) AND (b OR x) AND (a OR y) AND (b OR y)

Taking a equal to x gives the case I quoted.

The real problem is that we want to run the distributive law backwards,
not forwards ...

			regards, tom lane

Wed, 10 Dec 2003 17:35:11 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Canonicalization of WHERE clauses considered harmful 
On Wed, Dec 10, 2003 at 05:35:11PM -0500, Tom Lane wrote:
> Kurt Roeckx <Q@ping.be> writes:
> > On Wed, Dec 10, 2003 at 04:54:54PM -0500, Tom Lane wrote:
> >> (a AND b) OR (a AND c)
> >> expands by repeated application of the distributive law to
> >> (a OR a) AND (a OR c) AND (b OR a) AND (b OR c)
> 
> > This is wrong.
> 
> I don't think so.  The distributive law is
> 
> 	a OR (b AND c) == (a OR b) AND (a OR c)

Oh, I was reading it wrong.

So basicly it makes a + bc = (a+b)*(a+c) = a + ab + ac + bc
And ab + ac = a * (a+b) * (a+c) * (b+c) = ab + abc + ac


(This is so much easier to read then using AND and OR.)


Kurt


Wed, 10 Dec 2003 23:58:14 +0100
Kurt Roeckx <Q@ping.be>
Re: Canonicalization of WHERE clauses considered harmful