Long update query ?

This is caused by a semi-well known weakness in the optimizer. The optimizer
rewrites the WHERE clause in conjunctive normal form (CNF):

(A and B) or (C and D) ==> (A or C) and (A or D) and (B or C) and (B or D)

Try this with your statement and you will see the expression explodes. Foe
now, I would suggest that you break this up into multiple statements.

Sergei Chernev wrote:

PostgreSQL 6.3 and lower has a problem with lots of OR's in the where
clause (the optimizer exhaust memory if I'm not mistaken). ProstgreSQL
6.4 will handle OR's better. In the mean time I'd suggest rewriting
your queries (don't forget that you can use IN/NOT IN).
-DEJ

This is caused by a semi-well known weakness in the optimizer.
The optimizer
rewrites the WHERE clause in conjunctive normal form (CNF):

(A and B) or (C and D) ==> (A or C) and (A or D) and (B or C)
and (B or D)

Wouldn't disjunctive normal form be better, since it can be implemented as
the simple union of a set of small queries?

Taral

[Charset iso-8859-1 unsupported, filtering to ASCII...]

This is caused by a semi-well known weakness in the optimizer.
The optimizer
rewrites the WHERE clause in conjunctive normal form (CNF):

(A and B) or (C and D) ==> (A or C) and (A or D) and (B or C)
and (B or D)

Wouldn't disjunctive normal form be better, since it can be implemented as
the simple union of a set of small queries?

Please tell us more.

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

Wouldn't disjunctive normal form be better, since it can be

implemented as

the simple union of a set of small queries?

Please tell us more.

Well, I don't know how the backend processes queries, but one can imagine
this scenario (for DNF):

1) Analyze query and set up columns in result table
2) Rewrite query into DNF
3) Split query into subqueries
4) For each subquery:
a) Process query
b) Append matching tuples to result table
5) Do any post-processing (ORDER BY, etc.)
6) Return result

How is the processing currently done (with CNF)?

Taral

[Charset iso-8859-1 unsupported, filtering to ASCII...]

Wouldn't disjunctive normal form be better, since it can be

implemented as

the simple union of a set of small queries?

Please tell us more.

Well, I don't know how the backend processes queries, but one can imagine
this scenario (for DNF):

1) Analyze query and set up columns in result table
2) Rewrite query into DNF
3) Split query into subqueries
4) For each subquery:
a) Process query
b) Append matching tuples to result table
5) Do any post-processing (ORDER BY, etc.)
6) Return result

How is the processing currently done (with CNF)?

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.

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

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

Taral

[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@candle.pha.pa.us            |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

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?

Create a temporary oid hash? (for each table selected on, I guess)

Taral

[Charset iso-8859-1 unsupported, filtering to ASCII...]

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?

Create a temporary oid hash? (for each table selected on, I guess)

Taral

What I did with indexes was to run the previous OR clause index
restrictions through the qualification code, and make sure it failed,
but I am not sure how that is going to work with a more complex WHERE
clause. Perhaps I need to restrict this to just simple cases of
constants, which are easy to pick out an run through. Doing this with
joins would be very hard, I think.

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

Create a temporary oid hash? (for each table selected on, I guess)

What I did with indexes was to run the previous OR clause index
restrictions through the qualification code, and make sure it failed,
but I am not sure how that is going to work with a more complex WHERE
clause. Perhaps I need to restrict this to just simple cases of
constants, which are easy to pick out an run through. Doing this with
joins would be very hard, I think.

Actually, I was thinking more of an index of returned rows... After each
subquery, the backend would check each row to see if it was already in the
index... Simple duplicate check, in other words. Of course, I don't know how
well this would behave with large tables being returned...

Anyone else have some ideas they want to throw in?

Taral

Create a temporary oid hash? (for each table selected on, I guess)

What I did with indexes was to run the previous OR clause index
restrictions through the qualification code, and make sure it failed,
but I am not sure how that is going to work with a more complex WHERE
clause. Perhaps I need to restrict this to just simple cases of
constants, which are easy to pick out an run through. Doing this with
joins would be very hard, I think.

Actually, I was thinking more of an index of returned rows... After each
subquery, the backend would check each row to see if it was already in the
index... Simple duplicate check, in other words. Of course, I don't know how
well this would behave with large tables being returned...

Anyone else have some ideas they want to throw in?

Taral

But what about unions of join queries? Which OID's then should
be checked against which? And unions from view selects? There
are no OID's at all after rewriting.

Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#======================================== jwieck@debis.com (Jan Wieck) #

[Charset iso-8859-1 unsupported, filtering to ASCII...]

Create a temporary oid hash? (for each table selected on, I guess)

What I did with indexes was to run the previous OR clause index
restrictions through the qualification code, and make sure it failed,
but I am not sure how that is going to work with a more complex WHERE
clause. Perhaps I need to restrict this to just simple cases of
constants, which are easy to pick out an run through. Doing this with
joins would be very hard, I think.

Actually, I was thinking more of an index of returned rows... After each
subquery, the backend would check each row to see if it was already in the
index... Simple duplicate check, in other words. Of course, I don't know how
well this would behave with large tables being returned...

Anyone else have some ideas they want to throw in?

I certainly think we are heading in the direction for a good general
solution.

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

Create a temporary oid hash? (for each table selected on, I guess)

What I did with indexes was to run the previous OR clause index
restrictions through the qualification code, and make sure it failed,
but I am not sure how that is going to work with a more complex WHERE
clause. Perhaps I need to restrict this to just simple cases of
constants, which are easy to pick out an run through. Doing this with
joins would be very hard, I think.

Actually, I was thinking more of an index of returned rows... After each
subquery, the backend would check each row to see if it was already in the
index... Simple duplicate check, in other words. Of course, I don't know how
well this would behave with large tables being returned...

Anyone else have some ideas they want to throw in?

Taral

But what about unions of join queries? Which OID's then should
be checked against which? And unions from view selects? There
are no OID's at all after rewriting.

Yep, you can't just use oid's, I think. Joins and specifiying a table
multiple times using a table alias would break this anyway.

CNF'ify only goes through the tables once, so we somehow need to
simulate this. Perhaps we can restrict the kinds of queries used for
DNF so we can do this easily.

Another idea is that we rewrite queries such as:

SELECT *
FROM tab
WHERE (a=1 AND b=2 AND c=3) OR
(a=1 AND b=2 AND c=4) OR
(a=1 AND b=2 AND c=5) OR
(a=1 AND b=2 AND c=6)

into:

SELECT *
FROM tab
WHERE (a=1 AND b=2) AND (c=3 OR c=4 OR c=5 OR c=6)

and we do this BEFORE calling cnfify(). How much does this do for us?

Seems this would not be too hard, and would be a good performer.

You could even convert:

SELECT *
FROM tab
WHERE (a=1 AND b=2 AND c=3) OR
(a=1 AND b=2 AND c=4) OR
(a=1 AND b=52 AND c=5) OR
(a=1 AND b=52 AND c=6)

into:

SELECT *
FROM tab
WHERE ((a=1 AND b=2) AND (c=3 OR c=4)) OR
WHERE ((a=1 AND b=52) AND (c=5 OR c=6))

This should work OK too. Someone want to try this? David, is this what
your code does?

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

Another idea is that we rewrite queries such as:

SELECT *
FROM tab
WHERE (a=1 AND b=2 AND c=3) OR
(a=1 AND b=2 AND c=4) OR
(a=1 AND b=2 AND c=5) OR
(a=1 AND b=2 AND c=6)

into:

SELECT *
FROM tab
WHERE (a=1 AND b=2) AND (c=3 OR c=4 OR c=5 OR c=6)

Very nice, but that's like trying to code factorization of numbers... not
pretty, and very CPU intensive on complex queries...

Taral

[Charset iso-8859-1 unsupported, filtering to ASCII...]

Another idea is that we rewrite queries such as:

SELECT *
FROM tab
WHERE (a=1 AND b=2 AND c=3) OR
(a=1 AND b=2 AND c=4) OR
(a=1 AND b=2 AND c=5) OR
(a=1 AND b=2 AND c=6)

into:

SELECT *
FROM tab
WHERE (a=1 AND b=2) AND (c=3 OR c=4 OR c=5 OR c=6)

Very nice, but that's like trying to code factorization of numbers... not
pretty, and very CPU intensive on complex queries...

Yes, but how large are the WHERE clauses going to be? Considering the
cost of cnfify() and UNION, it seems like a clear win. Is it general
enough to solve our problems?

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

Very nice, but that's like trying to code factorization of

numbers... not

pretty, and very CPU intensive on complex queries...

Yes, but how large are the WHERE clauses going to be? Considering the
cost of cnfify() and UNION, it seems like a clear win. Is it general
enough to solve our problems?

Could be... the examples I received where the cnfify() was really bad were
cases where the query was submitted alredy in DNF... and where the UNION was
a simple one. However, I don't know of any algorithms for generic
simplification of logical constraints. One problem is resolution/selection
of factors:

SELECT * FROM a WHERE (a = 1 AND b = 2 AND c = 3) OR (a = 4 AND b = 2 AND c
= 3) OR (a = 1 AND b = 5 AND c = 3) OR (a = 1 AND b = 2 AND c = 6);

Try that on for size. You can understand why that code gets ugly, fast.
Somebody could try coding it, but it's not a clear win to me.

My original heuristic was missing one thing: "Where the heuristic fails to
process or decide, default to CNF." Since that's the current behavior, we're
less likely to break things.

Taral

[Charset iso-8859-1 unsupported, filtering to ASCII...]

Very nice, but that's like trying to code factorization of

numbers... not

pretty, and very CPU intensive on complex queries...

Yes, but how large are the WHERE clauses going to be? Considering the
cost of cnfify() and UNION, it seems like a clear win. Is it general
enough to solve our problems?

Could be... the examples I received where the cnfify() was really bad were
cases where the query was submitted alredy in DNF... and where the UNION was
a simple one. However, I don't know of any algorithms for generic
simplification of logical constraints. One problem is resolution/selection
of factors:

SELECT * FROM a WHERE (a = 1 AND b = 2 AND c = 3) OR (a = 4 AND b = 2 AND c
= 3) OR (a = 1 AND b = 5 AND c = 3) OR (a = 1 AND b = 2 AND c = 6);

Try that on for size. You can understand why that code gets ugly, fast.
Somebody could try coding it, but it's not a clear win to me.

My original heuristic was missing one thing: "Where the heuristic fails to
process or decide, default to CNF." Since that's the current behavior, we're
less likely to break things.

OK, but if we use UNION, how to we return the proper rows? Is there any
solution for that, and we are executing the query over and over again.
Any factoring would be faster than running those multiple queries,
wouldn't it?

Also, I amagine the case where we are doing a join, so we have:

SELECT *
FROM tab1, tab2
WHERE tab1.col1 = tab2.col2 AND
((a=1 and b=2 and c=3) OR
(a=1 and b=2 and c=4))

How do we do that with UNION, and return the right rows. Seems the
_join_ happending multiple times would be much worse than the factoring.

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

How do we do that with UNION, and return the right rows. Seems the
_join_ happending multiple times would be much worse than the factoring.

Ok... We have two problems:

1) DNF for unjoined queries.
2) Factorization for the rest.

I have some solutions for (1). Not for (2). Remember that unjoined queries
are quite common. :)

For (1), we can always try to parallel the multiple queries... especially in
the case where a sequential search is required.

Taral