A rare error

Looks like it probably is. The spec production
seems to allow query expressions to contain
()ized non-join query expressions or
()ized joined tables.

Stephan Szabo
sszabo@bigpanda.com

On Wed, 25 Oct 2000, DaVinci wrote:

DaVinci <bombadil@wanadoo.es> writes:

An extrange behavior with PostgreSql 7.0.2:
select * from foo where exists
(select * from foo)
works fine. But:
select * from foo where exists
((select * from foo))
shows an error:
ERROR: parser: parse error at or near "("
Is this a bug?

I was fooling around with exactly that point a couple weeks ago. You'd
think it would be easy to allow extra parentheses around a sub-select,
but I couldn't figure out any way to do it that didn't provoke shift/
reduce conflicts or worse.

The main problem is that if parentheses are both part of the expression
grammar (as they'd better be ;-)) and part of the SELECT grammar then
for a construct like
select (((select count(foo) from bar)));
it's ambiguous whether the extra parens are expression parens or part
of the inner SELECT statement. You may not care, but yacc does: it does
not like ambiguous grammars. AFAICS the only solution is not to allow
parentheses at the very top level of a SELECT structure. Then the above
is not ambiguous because all the extra parens are expression parens.

This solution leads directly to your complaint: the syntax is
EXISTS ( SELECT ... )
and you don't get to insert any unnecessary levels of parenthesis.

We could maybe hack something for EXISTS in particular (since we know
a parenthesized SELECT must follow it) but in the general case there
doesn't seem to be a way to make it work. For example, in current
sources this is OK:
select * from foo where exists
((select * from foo) union (select * from bar));
but not this:
select * from foo where exists
((select * from foo) union ((select * from bar)));
ERROR: parser: parse error at or near ")"

If there are any yacc hackers out there who think they can improve on
this, please grab gram.y from current CVS and have at it. It'd be nice
not to have an artificial restriction against redundant parentheses in
SELECT structures.

regards, tom lane

pgsql-hackers-owner@hub.org wrote:

I've been looking into this. I thought it would be easy, but it
doesn't want an easy fix, because it's worse than it at first
appeared.

Were you aware that this is legal:
(select avg(a),b from dummy group by b) order by b;
but this is not:
(select avg(a),b from dummy) group by b order by b;
and if we just allowed lots of nested parens, we would allow:
((((select avg(a),b from dummy group by b)))) order by b;
which just seems silly.

I for one don't like any of these, although I prefer the
one that is currently disallowed -- and it appears to me
that the parens being allowed in select_clause are being
introduced at the wrong level. I'm going to experiment
some with the concept of a "select_term" which will be the
thing that can be parenthesized (in some contexts).

BTW: yacc accepts LALR grammars, which are fairly restricted.
Thus the shift/reduce complaints and such don't mean it's
ambiguous, just that it's pushing the envelope of the LALR
paradigm. A lot of yacc grammars do just that, and work
just fine, but of course you have to know what you're doing.
I don't, at least not to that level of wizardry, so I'll stay
away from shift/reduce, etc. I mention it just to say that
we're not treading on ambiguity here, just the limits of yacc.

Finally, I hereby solicit comments. Because of yacc's limits,
it may turn out to be difficult to do things like have
unlimited parens around a "select_term" and also have
constructs like
NOT IN (select_term)
because yacc might not know how to parse the outer parens.
OTOH, maybe we don't want NOT IN (((SELECT foo FROM bar))).
OTOOH, maybe we do because there could be program-generated
SQL out there that would like that freedom. What do the
readers think?

I don't know yet where the problems could be. I may need
help figuring out what's important to provide and what is
less so. Does anyone know if there are a lot of parens in
the regression tests?

++ kevin

Subject: Re: [GENERAL] A rare error
Date: Wed, 25 Oct 2000 12:28:35 -0400
From: Tom Lane <tgl@sss.pgh.pa.us>
To: DaVinci <bombadil@wanadoo.es>
CC: Lista PostgreSql <pgsql-general@postgresql.org>,
pgsql-hackers@postgresql.org
References: <20001025104758.A7643@fangorn.net>

DaVinci <bombadil@wanadoo.es> writes:

An extrange behavior with PostgreSql 7.0.2:
select * from foo where exists
(select * from foo)
works fine. But:
select * from foo where exists
((select * from foo))
shows an error:
ERROR: parser: parse error at or near "("
Is this a bug?

I was fooling around with exactly that point a couple weeks ago. You'd
think it would be easy to allow extra parentheses around a sub-select,
but I couldn't figure out any way to do it that didn't provoke shift/
reduce conflicts or worse.

The main problem is that if parentheses are both part of the expression
grammar (as they'd better be ;-)) and part of the SELECT grammar then
for a construct like
select (((select count(foo) from bar)));
it's ambiguous whether the extra parens are expression parens or part
of the inner SELECT statement. You may not care, but yacc does: it does
not like ambiguous grammars. AFAICS the only solution is not to allow
parentheses at the very top level of a SELECT structure. Then the above
is not ambiguous because all the extra parens are expression parens.

This solution leads directly to your complaint: the syntax is
EXISTS ( SELECT ... )
and you don't get to insert any unnecessary levels of parenthesis.

We could maybe hack something for EXISTS in particular (since we know
a parenthesized SELECT must follow it) but in the general case there
doesn't seem to be a way to make it work. For example, in current
sources this is OK:
select * from foo where exists
((select * from foo) union (select * from bar));
but not this:
select * from foo where exists
((select * from foo) union ((select * from bar)));
ERROR: parser: parse error at or near ")"

If there are any yacc hackers out there who think they can improve on
this, please grab gram.y from current CVS and have at it. It'd be nice
not to have an artificial restriction against redundant parentheses in
SELECT structures.

regards, tom lane

--
Kevin O'Gorman (805) 650-6274 mailto:kogorman@pacbell.net
Permanent e-mail forwarder: mailto:Kevin.O'Gorman.64@Alum.Dartmouth.org
At school: mailto:kogorman@cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://trixie.kosman.via.ayuda.com/~kevin/index.html

"There is a freedom lying beyond circumstance,
derived from the direct intuition that life can
be grounded upon its absorption in what is
changeless amid change"
-- Alfred North Whitehead

"Kevin O'Gorman" <kogorman@pacbell.net> writes:

Were you aware that this is legal:
(select avg(a),b from dummy group by b) order by b;
but this is not:
(select avg(a),b from dummy) group by b order by b;

The reason for that is that SQL doesn't think that "order by" should
be allowed in subqueries, only in a top-level SELECT.

That restriction makes sense in pure SQL, since tuple order is
explicitly *not* part of the computational model. In the eyes of the
SQL spec, the only reason ORDER BY exists at all is for prettification
of final output.

However, once you add the LIMIT clause, queries like
SELECT * FROM foo ORDER BY bar LIMIT 1
suddenly become quite interesting and useful as subqueries
(this query gives you the whole row associated with the minimum
value of bar, which is something you can't easily get in pure SQL).

As the sources stand tonight, you can have such a query as a subquery,
but only if you hide the ORDER/LIMIT inside a view definition. You'll
get a syntax error if you try to write it in-line as a subquery.
There is no longer any good implementation reason for that; it is
solely a grammar restriction.

So I'm coming around to the idea that we should abandon the SQL
restriction and allow ORDER + LIMIT in subqueries. The trouble is
how to do it without confusing yacc.

BTW: yacc accepts LALR grammars, which are fairly restricted.
Thus the shift/reduce complaints and such don't mean it's
ambiguous, just that it's pushing the envelope of the LALR
paradigm. A lot of yacc grammars do just that, and work
just fine, but of course you have to know what you're doing.

Right. Also, I believe it's possible that such a grammar will behave
differently depending on which yacc you process it with, which would be
bad. (We have not yet taken the step of insisting that pgsql's grammar
is bison-only, and I don't want to.) So ensuring that we get no shift/
reduce conflicts has been a shop rule around here all along.

Anyway, the bottom line of all this rambling is that if you can get
rid of the distinction between SelectStmt and select_clause altogether,
that would be fine with me. You might consider looking at whether you
can write two nonterminals: a SELECT construct that has no outer parens,
and then an additional construct

subselect: SelectStmt | '(' subselect ')'

which would be used for all the sub-select nonterminals in SelectStmt
itself.

OTOH, maybe we don't want NOT IN (((SELECT foo FROM bar))).

If we can't do that then we're still going to get complaints, I think.
The original bug report in this thread was specifically that the thing
didn't like redundant parentheses; we should try to remove that
restriction in all contexts not just some.

regards, tom lane

Date: Thu, 26 Oct 2000 20:49:22 -0400
From: Tom Lane <tgl@sss.pgh.pa.us>

Right. Also, I believe it's possible that such a grammar will behave
differently depending on which yacc you process it with, which would be
bad. (We have not yet taken the step of insisting that pgsql's grammar
is bison-only, and I don't want to.) So ensuring that we get no shift/
reduce conflicts has been a shop rule around here all along.

Actually, even the earliest version of yacc had very simple rules,
which are inherited by all versions. In a shift/reduce conflict,
always shift. In a reduce/reduce conflict, always reduce by the rule
which appears first in the grammar file. shift/shift conflicts
indicate a grammer which is not LALR(1).

I'm pretty sure that all versions of yacc also support %left, %right,
and %nonassoc, which are simply techniques to eliminate shift/reduce
conflicts in arithmetic and other expressions.

I believe it is always possible to rewrite a grammer to eliminate all
conflicts. But the rewrite can require an explosion in the number of
rules.

Reduce/reduce conflicts can be risky because it is easy to
accidentally change the ordering of the rules while editing. But
shift/reduce conflicts are not risky. The C parser in gcc, for
example, written and maintained by parser experts, has 53 shift/reduce
conflicts.

Ian

pgsql-hackers-owner@hub.org wrote:

"Kevin O'Gorman" <kogorman@pacbell.net> writes:
Anyway, the bottom line of all this rambling is that if you can get
rid of the distinction between SelectStmt and select_clause altogether,
that would be fine with me. You might consider looking at whether you
can write two nonterminals: a SELECT construct that has no outer parens,
and then an additional construct

subselect: SelectStmt | '(' subselect ')'

which would be used for all the sub-select nonterminals in SelectStmt
itself.

I'm headed in that direction. I've been calling it 'subquery'.

OTOH, maybe we don't want NOT IN (((SELECT foo FROM bar))).

If we can't do that then we're still going to get complaints, I think.
The original bug report in this thread was specifically that the thing
didn't like redundant parentheses; we should try to remove that
restriction in all contexts not just some.

All that being said, I'm not sure enough notice has been taken of one
aspect of the changes already in place, and likely to become more
pronounced. It may be okay with everybody, but I don't want it to be
a big surprise: queries may no longer begin with SELECT, but instead
with an arbitrary number of left parens. In some cases, the semantics
gets lost in the syntax. Consider:

(SELECT * INTO newtable FROM table1) UNION (SELECT * FROM table2);

Notice the INTO? Doesn't this seem like an odd place for it, in what
appears to be a subordinate query? Where else would it go? How would
it grab you in an expression with five or more levels of parens?
How about five levels of parens and a complicated targetlist before
you get to the INTO?

What I'm suggesting is that the parens be allowed only on the right
hand side of the set operations. How does that strike you?

regards, tom lane

--
Kevin O'Gorman (805) 650-6274 mailto:kogorman@pacbell.net
Permanent e-mail forwarder: mailto:Kevin.O'Gorman.64@Alum.Dartmouth.org
At school: mailto:kogorman@cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://trixie.kosman.via.ayuda.com/~kevin/index.html

"There is a freedom lying beyond circumstance,
derived from the direct intuition that life can
be grounded upon its absorption in what is
changeless amid change"
-- Alfred North Whitehead

Kevin O'Gorman wrote:

pgsql-hackers-owner@hub.org wrote:

"Kevin O'Gorman" <kogorman@pacbell.net> writes:
Anyway, the bottom line of all this rambling is that if you can get
rid of the distinction between SelectStmt and select_clause altogether,
that would be fine with me. You might consider looking at whether you
can write two nonterminals: a SELECT construct that has no outer parens,
and then an additional construct

subselect: SelectStmt | '(' subselect ')'

which would be used for all the sub-select nonterminals in SelectStmt
itself.

I'm headed in that direction. I've been calling it 'subquery'.

OTOH, maybe we don't want NOT IN (((SELECT foo FROM bar))).

If we can't do that then we're still going to get complaints, I think.
The original bug report in this thread was specifically that the thing
didn't like redundant parentheses; we should try to remove that
restriction in all contexts not just some.

All that being said, I'm not sure enough notice has been taken of one
aspect of the changes already in place, and likely to become more
pronounced. It may be okay with everybody, but I don't want it to be
a big surprise: queries may no longer begin with SELECT, but instead
with an arbitrary number of left parens. In some cases, the semantics
gets lost in the syntax. Consider:

(SELECT * INTO newtable FROM table1) UNION (SELECT * FROM table2);

Notice the INTO? Doesn't this seem like an odd place for it, in what
appears to be a subordinate query? Where else would it go? How would
it grab you in an expression with five or more levels of parens?
How about five levels of parens and a complicated targetlist before
you get to the INTO?

This just occurred to me: how would you sort the results of this query?
The path of least resistance from the way things work now would be most
non-obvious: put the ORDER BY on the leftmost query. It looks like this

(SELECT * INTO newtable FROM table1 ORDER BY field1) UNION (SELECT * FROM
table2);

And I have to say that's about the ugliest construct I've seen in
a pretty ugly language.

What I'm suggesting is that the parens be allowed only on the right
hand side of the set operations. How does that strike you?

Anyway, that's the direction I'm going in now, but as always, I solicit
comments.

regards, tom lane

--
Kevin O'Gorman (805) 650-6274 mailto:kogorman@pacbell.net
Permanent e-mail forwarder: mailto:Kevin.O'Gorman.64@Alum.Dartmouth.org
At school: mailto:kogorman@cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://trixie.kosman.via.ayuda.com/~kevin/index.html

"There is a freedom lying beyond circumstance,
derived from the direct intuition that life can
be grounded upon its absorption in what is
changeless amid change"
-- Alfred North Whitehead

--
Kevin O'Gorman (805) 650-6274 mailto:kogorman@pacbell.net
Permanent e-mail forwarder: mailto:Kevin.O'Gorman.64@Alum.Dartmouth.org
At school: mailto:kogorman@cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://trixie.kosman.via.ayuda.com/~kevin/index.html

"There is a freedom lying beyond circumstance,
derived from the direct intuition that life can
be grounded upon its absorption in what is
changeless amid change"
-- Alfred North Whitehead

(SELECT * INTO newtable FROM table1) UNION (SELECT * FROM table2);

Possibly a silly (and definitely not standards-conformant) suggestion:

Maybe grammar should be amended to allow for
(SELECT * FROM table1) UNION (SELECT * FROM table2) INTO newtable

i.e.

union_expr:
(select_expr) union (union_expr) [into into_table]

"Kevin O'Gorman" <kogorman@pacbell.net> writes:

All that being said, I'm not sure enough notice has been taken of one
aspect of the changes already in place, and likely to become more
pronounced. It may be okay with everybody, but I don't want it to be
a big surprise: queries may no longer begin with SELECT, but instead
with an arbitrary number of left parens.

That's no surprise, because it's been true for a long time. It's
certainly true in the 6.5 grammar, which is the oldest I have on hand.

In some cases, the semantics gets lost in the syntax. Consider:

(SELECT * INTO newtable FROM table1) UNION (SELECT * FROM table2);

Notice the INTO? Doesn't this seem like an odd place for it, in what
appears to be a subordinate query? Where else would it go? How would
it grab you in an expression with five or more levels of parens?
How about five levels of parens and a complicated targetlist before
you get to the INTO?

Agreed, it's pretty ugly. This one is only partially SQL92's fault,
since it defines SELECT ... INTO for just a limited context:

<select statement: single row> ::=
SELECT [ <set quantifier> ] <select list>
INTO <select target list>
<table expression>

(<select target list> here appears to mean a list of local variables in
a calling program, a la ECPG, and doesn't really have anything to do
with the table-destination semantics that Postgres puts on the
construct. But I digress.) The above restricted form of SELECT does
not admit UNION/INTERSECT/EXCEPT constructs at the top level. Postgres
has generalized this to allow INTO <target> in a UNION/etc construct,
which means the word SELECT is not necessarily going to be the very
first thing you see. We do require the INTO to be in the leftmost
primitive SELECT, so the only thing you can really see in front of
"SELECT <selectlist> INTO" is some number of left parentheses. To me
the potential hairiness of the <selectlist> seems like a much bigger
readability issue than the leading parens --- but we got that part of
the syntax straight from SQL92.

What I'm suggesting is that the parens be allowed only on the right
hand side of the set operations. How does that strike you?

Will not do, first because EXCEPT is not symmetric, and second because
SQL92 does not describe any such limitation.

regards, tom lane

"Kevin O'Gorman" <kogorman@pacbell.net> writes:

This just occurred to me: how would you sort the results of this query?
The path of least resistance from the way things work now would be most
non-obvious: put the ORDER BY on the leftmost query. It looks like this
(SELECT * INTO newtable FROM table1 ORDER BY field1) UNION (SELECT * FROM
table2);
And I have to say that's about the ugliest construct I've seen in
a pretty ugly language.

No. This is not SQL92: the spec is perfectly definite that it does not
allow such a construct. What it allows is

SELECT ...foo... UNION SELECT ...bar... ORDER BY baz

and here the ORDER BY is to be interpreted as ordering the results of
the UNION, not the results of the righthand sub-SELECT. This is one
of the cases that you'll need to be careful to get right when
rejiggering the syntax.

Purely as an implementation issue, the current gram.y code drills down
to find the leftmost sub-SELECT and attaches the outer-level ORDER BY
clause to that Select node. analyze.c later extracts the ORDER BY and
attaches it to a top-level Query node that doesn't correspond to any
node existing in the gram.y output. That's all behind the scenes,
however, and shouldn't be exposed to the tender eyes of mere mortal
users.

AFAICS, the input
(SELECT * FROM table1 ORDER BY field1) UNION (SELECT * FROM table2);
should either be rejected (as current sources and all prior releases
would do) or else treat the ORDER BY as ordering the leftmost subselect
before it feeds into the UNION. There is no point in such an ORDER BY
by itself, since UNION will feel free to reorder the tuples --- but
OTOH something like
(SELECT ... ORDER BY ... LIMIT 1) UNION (SELECT ...)
seems entirely sensible and useful to me.

In short: there is a considerable difference between

(SELECT ...foo... UNION SELECT ...bar...) ORDER BY baz

SELECT ...foo... UNION (SELECT ...bar... ORDER BY baz)

(SELECT ...foo... ORDER BY baz) UNION SELECT ...bar...

and any attempt to allow ORDER BY on subqueries will have to be
careful to keep these straight. This may well mean that you need
to rejigger the output structures of gram.y as well as the grammar
itself.

regards, tom lane

Tom Lane wrote:

One thing I noticed that may surprise: the "%left UNION" and such that
appear in the source don't seem to do anything. I think our syntax
doesn't look like operators to yacc, and I suspect it's the opt_all
that's doing it. That part of yacc I don't understand.

Hmm, that should work. My reading of the bison manual is that the
precedence of a production is taken from the rightmost terminal symbol
in the production, so

| select_clause UNION opt_all select_clause
| select_clause INTERSECT opt_all select_clause
| select_clause EXCEPT opt_all select_clause

should have the correct relative precedences.

Don't you get shift/reduce errors if you remove those precedence specs?
I'd expect the <select_clause> grammar to be ambiguous without operator
precedence specs ...

regards, tom lane

Yah. I would have thought so too. However, when I comment out the
two %left lines (being careful not to dusturb line numbers) I get the
absolutely identical gram.c output. So at least for those two things
the associativity does nothing at all. I'm inclined to leave them commented
out, so they don't mislead.

Of course, I was pretty sure the syntax there was unambiguous in any
case, so I'm not surprised there's no error; come to think of it, maybe
that's why %left has no effect. There has to be something going on,
because if I comment out the next line (the one with JOIN in it),
I suddenly get 32 shift/reduce errors.

This brings up another point. I'm still very new at reading the
SQL92 spec, so I need help being sure I've got it right. If we're going
to want precedence for these operators, I can do it in the syntax, and
it's only a little work. I don't see precedence in SQL92; set operations
seem to be left associative of equal priority. Be careful what you
ask for, you'll likely get it.

And appropos of another comment you made, when we decide how it's going
to be, we should have a bunch more things put in the regression tests,
not just UNIONs, to make sure it doesn't change unnoticed.

++ kevin

--
Kevin O'Gorman (805) 650-6274 mailto:kogorman@pacbell.net
Permanent e-mail forwarder: mailto:Kevin.O'Gorman.64@Alum.Dartmouth.org
At school: mailto:kogorman@cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://trixie.kosman.via.ayuda.com/~kevin/index.html

"There is a freedom lying beyond circumstance,
derived from the direct intuition that life can
be grounded upon its absorption in what is
changeless amid change"
-- Alfred North Whitehead

"Kevin O'Gorman" <kogorman@pacbell.net> writes:

Don't you get shift/reduce errors if you remove those precedence specs?
I'd expect the <select_clause> grammar to be ambiguous without operator
precedence specs ...

Yah. I would have thought so too. However, when I comment out the
two %left lines (being careful not to dusturb line numbers) I get the
absolutely identical gram.c output. So at least for those two things
the associativity does nothing at all. I'm inclined to leave them commented
out, so they don't mislead.

Not to put too fine a point on it, but are you talking about the
original grammar or your modified one? Your modified one is erroneous
because it will always associate successive UNION/INTERSECT/EXCEPT
operators left-to-right; this does not meet the SQL spec which insists
that INTERSECT binds more tightly than the other two. Given that, I'm
not surprised that the precedences have no effect.

I don't see precedence in SQL92; set operations
seem to be left associative of equal priority.

Better take another look at the <query expression>, <query term>,
<query primary> hierarchy then...

regards, tom lane

Not to put too fine a point on it, but are you talking about the
original grammar or your modified one? Your modified one is erroneous
because it will always associate successive UNION/INTERSECT/EXCEPT
operators left-to-right; this does not meet the SQL spec which insists
that INTERSECT binds more tightly than the other two. Given that, I'm
not surprised that the precedences have no effect.

I don't see precedence in SQL92; set operations
seem to be left associative of equal priority.

Better take another look at the <query expression>, <query term>,
<query primary> hierarchy then...

Is there something here to patch? Hmm, I don't see anything... I will
come back later. :-)

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@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