Обсуждение: 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
distributivelaw.
 

Anybody enlighten what "inverse OR distributive law" is?
--
SRA OSS, Inc. Japan
Tatsuo Ishii

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

Tatsuo Ishii <t-ishii@sra.co.jp> writes:
>  * 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?

Well, it's defined right above that:
* The following code attempts to apply the inverse OR distributive law:*        ((A AND B) OR (A AND C))  =>  (A AND (B
ORC))* That is, locate OR clauses in which every subclause contains an* identical term, and pull out the duplicated
terms.

I'm not sure that "inverse OR distributive law" is standard terminology,
but I believe the implication in the other direction is usually called
the "OR distributive law".  Anyone know of better terminology?
        regards, tom lane

Am Donnerstag, 15. September 2005 05:04 schrieb Tom Lane:
> I'm not sure that "inverse OR distributive law" is standard terminology,
> but I believe the implication in the other direction is usually called
> the "OR distributive law".  Anyone know of better terminology?

It's still the "OR distributive law", it's just the inverse application 
thereof.

-- 
Peter Eisentraut
http://developer.postgresql.org/~petere/