NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/database/6346

Internet Message Format | 1992-08-26 | 4.3 KB

Xref: sparky comp.databases:6346 comp.databases.theory:401 comp.databases.oracle:1385
Newsgroups: comp.databases,comp.databases.theory,comp.databases.oracle
Path: sparky!uunet!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!watdragon!gnpaulle
From: [e-mail] (Glenn Paulley)
Subject: Re: Is this a bug or a limitation of the SQL language
In-Reply-To: [e-mail]'s message of 26 Aug 92 00:13:05 GMT
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News System)
Organization: University of Waterloo
References: <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
Date: Wed, 26 Aug 1992 19:07:00 GMT
Lines: 76

In article <[e-mail]> [e-mail] (Joseph Hellerstein) writes:

> In article <[e-mail]> [e-mail] (Glenn Paulley) writes:
>    > [I wrote:]
>    >   |select * from emp
>    >   |where salary between
>    >   |(select salary from emp where ename = 'Larry')
>    >   |and
>    >   |(select salary from emp where ename = 'John')
>
>    > You want to avoid subqueries whenever possible.  To get what you need,
>    > try the following:
>
>    2) Sahil's query, if optimized using subqueries for the where predicate,
>    will probably execute much faster than doing a three-way join (the
>    conjuncts in the where clause are single-value lookups; if ename is
>    indexed, for example, the entire result can be found using two indexed
>    retrievals, and a single table scan.... no joins, no sorts).

>This is incorrect.  Subquery processing is identical to *one kind* of
>join processing, namely nested-loop with the subquery as the inner.
>Hence joins will always do at least as well as subqueries, and often
>better, since the space of paths for the optimizer to choose from is
>larger.  To argue that subquery processing is simpler than join
>processing is just wrong.  It's a kind of join processing itself, with
>restricted output semantics.

100% agreed. However, the scalar subqueries above are not correlated, so
I still fail to see how join processing could perform better than (basically)
a single scan- nested loops aren't required. Again, I'm assuming that
ename is indexed, or in some way it's possible to determine Larry
and John's salary quickly.

As an aside:

As pointed out by [e-mail] (Michael Perry) these two
scalar subqueries must return single rows, or a run-time error occurs.
Also, a good point is made by [e-mail] (Paul Kent) that
the semantics of BETWEEN are questionable. My copy of the ISO
SQL2 standard (ISO/IEC JTC1/SC21 N5215, December 1, 1990)
says that "x BETWEEN y AND z" is equivalent to "x>=y AND x<=z"; thus a
NULL result will occur if John earns less than Larry (as correctly assumed
by Paul).

Both of the above also affect your join version in the same way, so
there's no problem there.

> And see the paper by Pirahesh, Hellerstein, and Hasan in SIGMOD '92
> which demonstrates that subquery-to-join *can* be done correctly (and
> is done automatically in Starburst) for all existential subqueries
> that are Boolean Factors (i.e. IN, ANY, or EXISTS subqueries that are
> outer conjuncts of the WHERE clause, not nested under NOT or OR, etc.)

I realize this (I have seen your paper, and others, on this subject).
The point I was trying to make is that I don't believe such transformations
are possible for *all* forms of subqueries (eg. universal quantification
and/or negation), so the heuristic isn't true in all cases (but is true in
this one).

> You have to be careful, but the rewrite I gave him will work
> correctly, may well speed up his query, and may even sneak by his
> limited parser.

Yes. Again, agreed.

I must say it's a pleasure to discuss these issues with someone of Mr.
Hellerstein's reputation. I follow your results on Starburst query
rewrite optimization, and other papers on Starburst, with interest.

Best regards.

--
-- G. N. (Glenn) Paulley                 | Computer Science Department
-- USENET: [e-mail] | University of Waterloo
-- Phone: [phone] x3490           | 200 University Avenue
-- Fax: [phone]   Office: DC3142  | Waterloo, Ontario, Canada N2L 3G1