Skip site navigation (1) Skip section navigation (2)

Re: [GENERAL] Long update query ? (also Re: [GENERAL] CNF vs. DNF)

From: Bruce Momjian <maillist(at)candle(dot)pha(dot)pa(dot)us>
To: taral(at)mail(dot)utexas(dot)edu (Taral)
Cc: hackers(at)postgreSQL(dot)org (PostgreSQL-development)
Subject: Re: [GENERAL] Long update query ? (also Re: [GENERAL] CNF vs. DNF)
Date: 1998-10-02 06:02:48
Message-ID: 199810020602.CAA28613@candle.pha.pa.us (view raw or flat)
Thread:
Lists: pgsql-generalpgsql-hackers
[Charset iso-8859-1 unsupported, filtering to ASCII...]
> > It currently convert to CNF so it can select the most restrictive
> > restriction and join, and use those first.  However, the CNF conversion
> > is a memory exploder for some queries, and we certainly need to have
> > another method to split up those queries into UNIONS.  I think we need
> > to code to identify those queries capable of being converted to UNIONS,
> > and do that before the query gets to the CNF section.  That would be
> > great, and David Hartwig has implemented a limited capability of doing
> > this, but we really need a general routine to do this with 100%
> > reliability.
> 
> Well, if you're talking about a routine to generate a heuristic for CNF vs.
> DNF, it is possible to precalculate the query sizes for CNF and DNF
> rewrites...
> 
> For conversion to CNF:
> 
> At every node:
> 
> if nodeType = AND then f(node) = f(left) + f(right)
> if nodeType = OR then f(node) = f(left) * f(right)
> 
> f(root) = a reasonably (but not wonderful) metric
> 
> For DNF just switch AND and OR in the above. You may want to compute both
> metrics and compare... take the smaller one and use that path.
> 
> How to deal with other operators depends on their implementation...

[Moved to Hackers list.]

This is interesting.  Check CNF size and DNF size.  Choose smallest. 
CNF uses existing code, DNF converts to UNIONs.  How do you return the
proper rows with/without proper duplicates?

i.e.

	SELECT * FROM tab1 WHERE x > 1 or x > 2

We need to return all rows where x > 1, even if some there are indentical
rows in tab1.

What I do in the index OR code is to test that rows in index matches
found in 2nd and 3rd index scans are false in earlier index scans.  I am
not sure how to do that with a UNION query, but it may be possible.

We currently have UNION and UNION ALL, and I think we may need a new
UNION type internally to prevent 2nd and 3rd queries from returning rows
returned by earlier UNION queries.

This is interesting.

-- 
  Bruce Momjian                        |  http://www.op.net/~candle
  maillist(at)candle(dot)pha(dot)pa(dot)us            |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026


In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 1998-10-02 06:14:22
Subject: Re: [HACKERS] delete from ..;vacuum crashes
Previous:From: TaralDate: 1998-10-02 05:35:12
Subject: RE: [GENERAL] Long update query ? (also Re: [GENERAL] CNF vs. DNF)

pgsql-general by date

Next:From: Oliver ElphickDate: 1998-10-02 07:20:36
Subject: Re: More PostgreSQL stuff
Previous:From: TaralDate: 1998-10-02 05:35:12
Subject: RE: [GENERAL] Long update query ? (also Re: [GENERAL] CNF vs. DNF)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group