Actually, what I'm suggesting first is much more straight forward. Each
operation must take place on a row set. When you've got a bunch of tables
that are joined together, and columns with unique indexes are specified in
the where clause to be equal to some simple value (regalrdless of which
table), then before you do any other processing, make sure you only process
on that single row! Don't join a million rows together only to throw them
all out but one!! Which it appears is exactly what 7.3.1 was doing. It
should be so easy to scan a where clause for columns that contain unique
indexes and are equal to a fixed specified value. If so, in all cases, use
that to limit rows before you do any other processing. That is the simple
case, but that alone will have a major impact on a good percentage of real
world queries. It is a simple optimization and will work in all cases, no
exceptions. If you join tables before ever considering the where clause
restrictions, you've got to be doing a ton of extra work in many, many
cases.

If the above makes sense, then we can talk about the next most general case
(i.e. determining the likely number of rows that will be retunred by a where
clause restriction on a column). But the concept is still the same - don't
spend time joining rows when you are going to later throw them away becuase
of some where clause restriction. Stated another way, "restrict then join"
is far more efficient than "join then restrict".

-----Original Message-----
From: Stephan Szabo [mailto:sszabo@megazone23.bigpanda.com]
Sent: Thursday, April 24, 2003 4:39 PM
To: Robert Dyas
Subject: RE: [HACKERS] query optimization scenarios 17,701 times
faster!!!



On Thu, 24 Apr 2003, Robert Dyas wrote:

> Actually, I wish I would have sent along only the last pair of queries to
> focus the conversation more. So I will focus on the last pair of queries
for
> this comment.

Okay, that one did seem wierder.

> In that case, the first table specified in the from clause is the table
from
> which all of the columns are retrieved. Furthermore, the where clause
> indicates that the table's primary key must equal a single value. This can
> only return one row (or zero rows). So all subsequent processing should
only
> occur on that one row. That is the simple case involving unique indexes,
and
> the easiest to optimize.

Right, but I was pointing out that the particular two queries you gave
aren't necessarily the same without that distinct on the query.  The fact
that it gives you the same results depends on that you know that only one
(or zero because its outer) rows in the right side will match or that
you're doing something like distinct, distinct on, group by afaics.
Otherwise I think you'd get duplicated rows in the first version and not
in the second.

> The more general case would be an estimate (based on index statistics) of
> the number of rows that would be returned by a column equaling some value.
> Those where the estimated number of hits is sufficiently small relative to
> total table size would be processed first (in the case of multiple
> restrictions, those resulting in the least number of estimated result rows
> would be processed first). I would assume this is one of the first
> optimizations somebody would address when writing a query optimizer, yet
it
> appears to be absent or broken in 7.3.1.

The problem is that explicit join syntax is also overloaded right now to
mean do these joins in this order which does inhibit some optimizations.
I think there's been talk of making this optional at some point.
I believe there were cases with outer joins where (A LJ B) LJ C is not the
same as A LJ (B LJ C) as well (admittedly they're really wierd using
things like is not null or coalesce in the on conditions) and so you have
to be careful when reordering them (if that's part of what you're
suggesting).


Thu, 24 Apr 2003 17:08:58 -0400
"Robert Dyas" <rdyas@adelphia.net>
Re: query optimization scenarios 17,701 times faster!!!
On Thu, 24 Apr 2003, Robert Dyas wrote:

> clause restriction on a column). But the concept is still the same - don't
> spend time joining rows when you are going to later throw them away becuase
> of some where clause restriction. Stated another way, "restrict then join"
> is far more efficient than "join then restrict".

True, but "join then restrict" is guaranteed to get the right answer 
through sheer force of will, while restrict then join requires that you 
not only try to optimize the query, but you have to make sure you are not 
throwing away the wrong ones.  I.e. accidentally leaving in extra rows to 
throw away costs you CPU time, accidentally tossing the wrong rows gives 
bogus results.

The real answer here is that SQL is the answer.  It allows you to restrict 
the data sets you're playing with before the join, not after.  Subselects, 
unions, etc... allow you to build a more efficient query that is handling, 
in theory, smaller data sets, and should therefore be faster.

I'd love for the planner to be able to optimize everything, but let's face 
it, since all databases live in the real world where optimzation can never 
be perfect, we should all strive to create SQL queries that hit the fewest 
rows needed to do the job, and THEN let the planner take it from there.

We all benefit from faster sorting algorhythms, better indexing methods, 
etc.   Only people who write very inneficient SQL benefit from the types 
of optimizations you're talking about.  So, if someone has to put in time 
programming, I'd rather it be on things we can all use and benefit from 
the most.

When we have async/sync multi-master multi-slave replication, with bit 
mapped indexes, and super fast hashing, along with maybe a ccNUMA friendly 
caching method that can efficiently handle tens of gigabytes of free RAM, 
sure, maybe someone should get around to optimizing the corner cases.  But 
unconstrained joins or even just poorly thought out ones, are NOT a corner 
case, they're a SQL mistake.


Thu, 24 Apr 2003 15:18:42 -0600 (MDT)
"scott.marlowe" <scott.marlowe@ihs.com>
Re: query optimization scenarios 17,701 times faster!!!

On Thu, 24 Apr 2003, Robert Dyas wrote:

> Actually, what I'm suggesting first is much more straight forward. Each
> operation must take place on a row set. When you've got a bunch of tables
> that are joined together, and columns with unique indexes are specified in
> the where clause to be equal to some simple value (regalrdless of which
> table), then before you do any other processing, make sure you only process
> on that single row! Don't join a million rows together only to throw them
> all out but one!! Which it appears is exactly what 7.3.1 was doing. It

It doesn't look that way to me.  It looks to me from the explain output
that it was doing an index scan getting the one row from the table with
the condition and then joining that with each successive table (possibly
getting additional rows from those), then doing a sort and unique for the
distinct.


Thu, 24 Apr 2003 14:45:49 -0700 (PDT)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: query optimization scenarios 17,701 times faster!!!
On Thu, 24 Apr 2003, Stephan Szabo wrote:

>
> On Thu, 24 Apr 2003, Robert Dyas wrote:
>
> > Actually, what I'm suggesting first is much more straight forward. Each
> > operation must take place on a row set. When you've got a bunch of tables
> > that are joined together, and columns with unique indexes are specified in
> > the where clause to be equal to some simple value (regalrdless of which
> > table), then before you do any other processing, make sure you only process
> > on that single row! Don't join a million rows together only to throw them
> > all out but one!! Which it appears is exactly what 7.3.1 was doing. It
>
> It doesn't look that way to me.  It looks to me from the explain output
> that it was doing an index scan getting the one row from the table with
> the condition and then joining that with each successive table (possibly
> getting additional rows from those), then doing a sort and unique for the
> distinct.

As a note, relooking at the explain analyze output, it looked like most of
the time was in the sort and unique for the distinct.  I wonder if raising
sort_mem would give a gain.  Not sure about that.  (At best it'd still be
on the order of 300x the other query rather than 17000x).


Thu, 24 Apr 2003 14:52:17 -0700 (PDT)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: query optimization scenarios 17,701 times faster!!!