inverse OR distributive law?

Started by Tatsuo Ishiiover 20 years ago4 messages

t-ishii@sra.co.jp

over 20 years ago

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

DCorbit@connx.com

over 20 years ago

In reply to: Tatsuo Ishii (#1)

Re: inverse OR distributive law?

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)---------------------------

Show quoted text

TIP 4: Have you searched our list archives?

http://archives.postgresql.org

Import Notes

Resolved by subject fallback

tgl@sss.pgh.pa.us

over 20 years ago

In reply to: Tatsuo Ishii (#1)

Re: inverse OR distributive law?

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 OR C))
* 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

Peter Eisentraut

peter_e@gmx.net

over 20 years ago

In reply to: Tom Lane (#3)

Re: inverse OR distributive law?

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/