Re: inverse OR distributive law? - Mailing list pgsql-hackers

To find out about boolean logic, take a look here:
http://www.laynetworks.com/Boolean%20Algebra.htm

Where I work, we took the SIS toolkit from Berkeley and did a
simplification of the where clause as if it was a Boolean integrated
circuit.  Of course, you may get answers that you do not expect if the
data has NULL values, so you can turn that simplification option off
also.

After Boolean simplification, this:
SELECT Products.RECORD_NUMBER ,
Products.PRODUCTID ,
Products.PRODUCTNAME ,
Products.PRODUCTPRICE ,
Products.PRODUCTKEYWORDS ,
Products.PRODUCTGROUPID
FROM Products
WHERE ( ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS )
Like '%coffee%' ) AND ( Products.PRODUCTGROUPID < 10 ) AND ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( Products.PRODUCTGROUPID < 10 ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( ( Products.PRODUCTPRICE > 14 ) AND (
Products.PRODUCTGROUPID < 10 ) ) OR ( ( Products.PRODUCTPRICE > 14 ) AND
( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTGROUPID < 10 ) ) AND
( ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( ( Products.PRODUCTPRICE > 14 ) AND (
Products.PRODUCTGROUPID < 10 ) ) OR ( ( Products.PRODUCTPRICE > 14 ) AND
( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTGROUPID < 10 ) ) OR (
( Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTGROUPID < 10 ) ) AND ( ( Products.PRODUCTPRICE > 14 ) OR
( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTGROUPID < 10 ) ) OR (
( Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTGROUPID < 10 ) AND ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTGROUPID < 10 ) OR ( NOT (
Products.PRODUCTPRICE > 14 ) AND NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( NOT ( Products.PRODUCTPRICE > 14 ) AND NOT (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND ( NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( NOT ( Products.PRODUCTPRICE > 14 ) OR NOT (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( Products.PRODUCTGROUPID < 10 ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( Products.PRODUCTGROUPID < 10 ) OR ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTGROUPID < 10 ) OR ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTGROUPID < 10 ) AND ( NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( NOT ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND ( NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( NOT ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND ( Products.PRODUCTPRICE
> 14 ) AND ( ( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) AND ( Products.PRODUCTPRICE > 14 ) AND (
( Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTPRICE > 14 ) AND (
Products.PRODUCTKEYWORDS ) Like '%coffee%' AND ( Products.PRODUCTPRICE >
14 ) AND ( Products.PRODUCTKEYWORDS ) Like '%coffee%' OR (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' OR ( Products.PRODUCTPRICE > 14 ) AND NOT (
Products.PRODUCTKEYWORDS ) Like '%coffee%' AND ( Products.PRODUCTPRICE >
14 ) AND ( Products.PRODUCTKEYWORDS ) Like '%coffee%' OR (
Products.PRODUCTPRICE > 14 ) AND NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' OR ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE
> 14 ) AND ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE >
14 ) OR ( Products.PRODUCTPRICE > 14 ) AND 0 AND ( Products.PRODUCTPRICE
> 14 ) AND 0 OR ( Products.PRODUCTPRICE > 14 ) AND 1 AND (
Products.PRODUCTPRICE > 14 ) AND 1 OR ( Products.PRODUCTPRICE > 14 ) AND
NOT ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE > 14 )
AND NOT ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE > 14
) OR ( ( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR (
Products.PRODUCTGROUPID < 10 ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR ( Products.PRODUCTPRICE > 14 ) OR ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' OR ( Products.PRODUCTPRICE >
14 ) OR ( Products.PRODUCTKEYWORDS ) Like '%coffee%' OR (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTPRICE > 14 ) AND (
Products.PRODUCTKEYWORDS ) Like '%coffee%' AND ( Products.PRODUCTPRICE >
14 ) OR ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS )
Like '%coffee%' AND ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE > 14 ) OR 0 OR
( Products.PRODUCTPRICE > 14 ) OR 0 OR ( Products.PRODUCTPRICE > 14 ) OR
1 OR ( Products.PRODUCTPRICE > 14 ) OR 1 OR ( Products.PRODUCTPRICE > 14
) OR NOT ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTPRICE > 14
) OR NOT ( Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS )
Like '%coffee%' OR ( Products.PRODUCTPRICE > 14 ) OR NOT (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' OR ( Products.PRODUCTPRICE > 14 ) OR NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( ( Products.PRODUCTPRICE > 14 ) AND
( Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND NOT ( (
Products.PRODUCTPRICE > 14 ) AND ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND NOT ( ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR NOT ( (
Products.PRODUCTPRICE > 14 ) OR ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) OR NOT ( NOT ( Products.PRODUCTPRICE > 14 ) ) OR NOT ( NOT
( Products.PRODUCTPRICE > 14 ) ) AND NOT ( Products.PRODUCTPRICE > 14 )
AND ( ( Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS )
Like '%coffee%' ) AND NOT ( Products.PRODUCTPRICE > 14 ) AND ( (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' ) AND NOT ( Products.PRODUCTPRICE > 14 ) AND NOT (
Products.PRODUCTKEYWORDS ) Like '%coffee%' OR NOT (
Products.PRODUCTPRICE > 14 ) AND NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' OR NOT ( Products.PRODUCTPRICE > 14 ) OR NOT (
Products.PRODUCTKEYWORDS ) Like '%coffee%' AND NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' AND NOT ( ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) AND NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%' AND NOT ( ( Products.PRODUCTPRICE > 14 ) OR (
Products.PRODUCTKEYWORDS ) Like '%coffee%' ) OR NOT (
Products.PRODUCTPRICE > 14 ) OR NOT ( Products.PRODUCTKEYWORDS ) Like
'%coffee%'

Becomes this:
SELECT t1.RECORD_NUMBER , t1.PRODUCTID , t1.PRODUCTNAME ,
t1.PRODUCTPRICE , t1.PRODUCTKEYWORDS , t1.PRODUCTGROUPID FROM Products
t1

> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] On Behalf Of Tatsuo Ishii
> Sent: Tuesday, September 13, 2005 4:02 PM
> To: pgsql-hackers@postgresql.org
> Subject: [HACKERS] inverse OR distributive law?
>
> Hi,
>
> I have been looking around optimizer's code and found a comment:
>
> /*
>  * process_duplicate_ors
>  *      Given a list of exprs which are ORed together, try to apply
>  *      the inverse OR distributive law.
>
> Anybody enlighten what "inverse OR distributive law" is?
> --
> SRA OSS, Inc. Japan
> Tatsuo Ishii
>
> ---------------------------(end of
broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
>                http://archives.postgresql.org