
Hi Everyone - this is my first post (but I have been lurking on and off for
a couple of years). Congratulations on a steadily improving product!

This is not a question, just some observations on performance that I thought
might trigger someone's thinking on ways to improve query optimization.

The following is a list of query pairs (one fast, one slow) that must
produce identical results by definition (and do), but have very different
execution times. Especially the last example. I did some development work on
a commercial SQL database product 7 years ago (names will not be used), so
although I am clueless about PostgreSQL internals, I (think) I have a grip
on some of the query optimization issues (though not necessarily a grip on
life). The data set used for all of these queries was very small - most
tables had a few hundred records or less. No, its not very scientific, but I
believe its illustrative none-the-less.

I'll just make a couple of observations on the last query and leave everyone
else to reach their own conclusions.

1) the two versions of the last query must produce identical results by
definition (and they do)
2) it appears that the optimizer is doing all of the join work before ever
considering the impact of where clause restrictions. (this may not be the
case, but it appears so)
3) It could have said, hey, I have a where clause restriction on the primary
key that is equal to a fixed value. So I have a single row from that table
to deal with, all of the columns come from that table too, and further its
left joined to the rest of the crap so I can safely ignore it.

I always think its illustrative to look at extreme examples like this to
point out optimizations that may be overlooked. If I ever get some free
time, I look forward to contributing to this wonderful project!


NOTES:
1) I didn't include the schema to keep this post reasonable. send email to
rdyas@adelphia.net if you want the schema to look into this further.
2) the primary keys for the following tables are
org_milestones.id
tasks.task_id
contacts.contact_id
organizations.org_id


EXPLAIN ANALYZE SELECT DISTINCT org_milestones.completed_on,
org_milestones.id, org_milestones.milestone_id, org_milestones.notes,
org_milestones.org_id FROM org_milestones RIGHT OUTER JOIN organizations ON
(org_milestones.org_id = organizations.org_id) LEFT OUTER JOIN contacts ON
(contacts.org_id = organizations.org_id) LEFT OUTER JOIN tasks ON
(tasks.org_id = organizations.org_id) WHERE (organizations.org_id = 71)
ORDER BY org_milestones.completed_on, org_milestones.id
79.20 msec

EXPLAIN ANALYZE SELECT org_milestones.completed_on, org_milestones.id,
org_milestones.milestone_id, org_milestones.notes, org_milestones.org_id
FROM org_milestones RIGHT OUTER JOIN organizations ON (org_milestones.org_id
= organizations.org_id) WHERE (organizations.org_id = 71) ORDER BY
org_milestones.completed_on, org_milestones.id
6.44 msec
= 12 times faster

---------------
EXPLAIN ANALYZE SELECT DISTINCT tasks.completed, tasks.contact_id,
tasks.created_by, tasks.notes, tasks.objective, tasks.org_id, tasks.outcome,
tasks.priority, tasks.start_date, tasks.start_time, tasks.task_id,
tasks.task_type FROM tasks RIGHT OUTER organizations ON (tasks.org_id =
organizations.org_id) LEFT OUTER JOIN org_milestones ON
(org_milestones.org_id = organizations.org_id) LEFT OUTER JOIN contacts ON
(contacts.org_id = organizations.org_id) WHERE (organizations.org_id = 71)
ORDER BY tasks.start_date, tasks.start_time
2,548.71 msec

EXPLAIN ANALYZE SELECT tasks.completed, tasks.contact_id, tasks.created_by,
tasks.notes, tasks.objective, tasks.org_id, tasks.outcome, tasks.priority,
tasks.start_date, tasks.start_time, tasks.task_id, tasks.task_type FROM
tasks RIGHT OUTER JOIN organizations ON (tasks.org_id =
organizations.org_id) WHERE (organizations.org_id = 71) ORDER BY
tasks.start_date, tasks.start_time
29.21 msec
= 87 times faster

-----------
EXPLAIN ANALYZE SELECT DISTINCT contacts.address_1, contacts.address_2,
contacts.assistant_email, contacts.assistant_name, contacts.assistant_phone,
contacts.city, contacts.contact_id, contacts.email_address,
contacts.first_name, contacts.functional_role, contacts.last_name,
contacts.needs, contacts.notes, contacts.org_id, contacts.pain,
contacts.phone, contacts.reasons, contacts.reports_to, contacts.state,
contacts.title, contacts.zip_code, (contacts.first_name || ' ' ||
contacts.last_name) AS full_name FROM contacts RIGHT OUTER JOIN
organizations ON (contacts.org_id = organizations.org_id) LEFT OUTER JOIN
org_milestones ON (org_milestones.org_id = organizations.org_id) LEFT OUTER
JOIN tasks ON (tasks.org_id = organizations.org_id) WHERE
(organizations.org_id = 71)
2056.83 msec

EXPLAIN ANALYZE SELECT DISTINCT contacts.address_1, contacts.address_2,
contacts.assistant_email, contacts.assistant_name, contacts.assistant_phone,
contacts.city, contacts.contact_id, contacts.email_address,
contacts.first_name, contacts.functional_role, contacts.last_name,
contacts.needs, contacts.notes, contacts.org_id, contacts.pain,
contacts.phone, contacts.reasons, contacts.reports_to, contacts.state,
contacts.title, contacts.zip_code, (contacts.first_name || ' ' ||
contacts.last_name) AS full_name FROM contacts RIGHT OUTER JOIN
organizations ON (contacts.org_id = organizations.org_id) WHERE
(organizations.org_id = 71)
27.41 msec
= 75 times faster
-----------------

EXPLAIN ANALYZE SELECT DISTINCT organizations.city, organizations.inactive,
organizations.java_developers, organizations.name, organizations.org_id,
organizations.overview, organizations.phone, organizations.salesperson,
organizations.state, organizations.time_zone FROM organizations LEFT OUTER
JOIN org_milestones ON (org_milestones.org_id = organizations.org_id) LEFT
OUTER JOIN contacts ON (contacts.org_id = organizations.org_id) LEFT OUTER
JOIN tasks ON (tasks.org_id = organizations.org_id) WHERE
(organizations.org_id = 71) ORDER BY organizations.name
12,567.87 msec

EXPLAIN ANALYZE SELECT organizations.city, organizations.inactive,
organizations.java_developers, organizations.name, organizations.org_id,
organizations.overview, organizations.phone, organizations.salesperson,
organizations.state, organizations.time_zone FROM organizations WHERE
(organizations.org_id = 71)
0.71 msec
= 17,701 times faster
-----------------------


Wed, 23 Apr 2003 14:04:02 -0400
"Robert Dyas" <rdyas@adelphia.net>
query optimization scenarios 17,701 times faster!!!
On Wed, 23 Apr 2003, Robert Dyas wrote:

> 2) it appears that the optimizer is doing all of the join work before ever
> considering the impact of where clause restrictions. (this may not be the
> case, but it appears so)

What version of postgres do you use? I think the current cvs should handle
the joins better then the current released versions. I don't use the cvs
version myself, but I think I've seen people say that the cvs version
optimizes joins better.

If you could try the same examples on the cvs version if would be fun to
see some numbers.

-- 
/Dennis


Wed, 23 Apr 2003 22:20:43 +0200 (CEST)
=?ISO-8859-1?Q?Dennis_Bj=F6rklund?= <db@zigo.dhs.org>
Re: query optimization scenarios 17,701 times faster!!!
"Robert Dyas" <rdyas@adelphia.net> writes:
> The following is a list of query pairs (one fast, one slow) that must
> produce identical results by definition (and do), but have very different
> execution times.

With no details about the table schemas, nor the EXPLAIN ANALYZE output
data, I really wonder how you expect any intelligent comments.  We are
programmers, not mind-readers.

			regards, tom lane


Wed, 23 Apr 2003 22:59:50 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: query optimization scenarios 17,701 times faster!!! 

OK, so you lack mind-reading skills ;-) I wasn't sure if anybody would be
interested in exploring this, but here's the full monty. (full EXPLAIN
ANALYZE output + entire schema) I can't provide the actual data, sorry. But
each table has at most a couple of hundred records. The numbers are actually
a little worse this time (33,623 times faster!!!) because there is slightly
more data in the tables. Performance degrades very rapidly as table size
increases.



EXPLAIN ANALYZE SELECT DISTINCT organizations.city, organizations.inactive,
organizations.java_developers, organizations.name, organizations.org_id,
organizations.overview, organizations.phone, organizations.salesperson,
organizations.state, organizations.time_zone FROM organizations LEFT OUTER
JOIN org_milestones ON (org_milestones.org_id = organizations.org_id) LEFT
OUTER JOIN contacts ON (contacts.org_id = organizations.org_id) LEFT OUTER
JOIN tasks ON (tasks.org_id = organizations.org_id) WHERE
(organizations.org_id = 71) ORDER BY organizations.name
covont_production-# ;

QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------------------------------------
----------------------------------------------------------------------------
-------------------------
 Unique  (cost=53.32..54.08 rows=3 width=884) (actual
time=19200.24..24870.87 rows=1 loops=1)
   ->  Sort  (cost=53.32..53.39 rows=27 width=884) (actual
time=19200.19..19315.98 rows=840 loops=1)
         Sort Key: organizations.name, organizations.city,
organizations.inactive, organizations.java_developers, organizations.org_id,
organizations.overview, organizations.phone, organizations.salesperson,
organizations.state, organizations.time_zone
         ->  Hash Join  (cost=43.68..52.67 rows=27 width=884) (actual
time=18.42..170.69 rows=840 loops=1)
               Hash Cond: ("outer".org_id = "inner".org_id)
               ->  Hash Join  (cost=12.38..20.75 rows=5 width=880) (actual
time=7.18..19.42 rows=42 loops=1)
                     Hash Cond: ("outer".org_id = "inner".org_id)
                     ->  Nested Loop  (cost=0.00..8.24 rows=2 width=876)
(actual time=1.03..6.16 rows=7 loops=1)
                           Join Filter: ("inner".org_id = "outer".org_id)
                           ->  Index Scan using organizations_pkey on
organizations  (cost=0.00..4.66 rows=1 width=872) (actual time=0.32..0.34
rows=1 loops=1)
                                 Index Cond: (org_id = 71)
                           ->  Seq Scan on org_milestones  (cost=0.00..2.15
rows=115 width=4) (actual time=0.04..2.97 rows=116 loops=1)
                     ->  Hash  (cost=8.36..8.36 rows=136 width=4) (actual
time=5.44..5.44 rows=0 loops=1)
                           ->  Seq Scan on contacts  (cost=0.00..8.36
rows=136 width=4) (actual time=0.05..3.21 rows=136 loops=1)
               ->  Hash  (cost=19.92..19.92 rows=292 width=4) (actual
time=10.50..10.50 rows=0 loops=1)
                     ->  Seq Scan on tasks  (cost=0.00..19.92 rows=292
width=4) (actual time=0.06..6.38 rows=294 loops=1)
 Total runtime: 24881.28 msec
(17 rows)

covont_production=# EXPLAIN ANALYZE SELECT organizations.city,
organizations.inactive, organizations.java_developers, organizations.name,
organizations.org_id, organizations.overview, organizations.phone,
organizations.salesperson, organizations.state, organizations.time_zone FROM
organizations WHERE (organizations.org_id = 71)
covont_production-# ;
                                                            QUERY PLAN
----------------------------------------------------------------------------
------------------------------------------------------
 Index Scan using organizations_pkey on organizations  (cost=0.00..4.66
rows=1 width=872) (actual time=0.28..0.29 rows=1 loops=1)
   Index Cond: (org_id = 71)
 Total runtime: 0.74 msec
(3 rows)

covont_production=#



****************************************************************************
**
Here is the complete schema:

CREATE TABLE organizations (
	org_id              SERIAL PRIMARY KEY,
	salesperson         INTEGER REFERENCES users(user_id),
	name                VARCHAR(30) NOT NULL,
	phone               VARCHAR(30),
	city                VARCHAR(30),
	state               VARCHAR(2),
	time_zone           VARCHAR(3),
	overview            TEXT,
	java_developers     INTEGER,
	inactive            BOOLEAN NOT NULL
);

CREATE INDEX organizations_salesperson ON organizations(salesperson);

CREATE TABLE milestones (
	milestone_id        SERIAL PRIMARY KEY,
	name                VARCHAR(60) NOT NULL,
	red_flag_days       INTEGER NOT NULL
);

CREATE TABLE org_milestones (
	id                  SERIAL PRIMARY KEY,
	milestone_id    	  INTEGER NOT NULL REFERENCES milestones(milestone_id),
	org_id              INTEGER NOT NULL REFERENCES organizations(org_id),
	completed_on        DATE NOT NULL,
	notes               VARCHAR(250)
);

CREATE TABLE contacts (
	contact_id          SERIAL PRIMARY KEY,
	org_id              INTEGER NOT NULL REFERENCES organizations(org_id),
	first_name          VARCHAR(30) NOT NULL,
	last_name           VARCHAR(30),
	title               VARCHAR(60),
	phone               VARCHAR(30),
	email_address       VARCHAR(120),
	assistant_name      VARCHAR(30),
	assistant_phone     VARCHAR(30),
	assistant_email     VARCHAR(120),
	functional_role     VARCHAR(30),
	reports_to          INTEGER REFERENCES contacts(contact_id),
	notes               TEXT,
	pain                VARCHAR(120),
	reasons             VARCHAR(250),
	needs               VARCHAR(250),
	address_1           VARCHAR(60),
	address_2           VARCHAR(60),
	city                VARCHAR(30),
	state               VARCHAR(2),
	zip_code            VARCHAR(10),
	time_zone           VARCHAR(3)
);

CREATE INDEX contacts_org_id ON contacts(org_id);

CREATE TABLE tasks (
	task_id             SERIAL PRIMARY KEY,
	org_id              INTEGER NOT NULL REFERENCES organizations(org_id),
	contact_id          INTEGER NOT NULL REFERENCES contacts(contact_id),
	created_by          INTEGER NOT NULL REFERENCES users(user_id),
	start_date          DATE NOT NULL,
	start_time          TIME,
	completed           BOOLEAN NOT NULL,
	task_type           VARCHAR(30) NOT NULL,
	objective           VARCHAR(120) NOT NULL,
	outcome             VARCHAR(120),
	notes               TEXT,
	priority            INTEGER NOT NULL
);

CREATE INDEX tasks_org_id ON tasks(org_id);
CREATE INDEX tasks_contact_id ON tasks(contact_id);
CREATE INDEX tasks_start_date ON tasks(start_date);

CREATE TABLE attachments (
	attach_id           SERIAL PRIMARY KEY,
	task_id             INTEGER NOT NULL REFERENCES tasks(task_id) ON DELETE
CASCADE,
	attachment          BYTEA
);

CREATE INDEX attachments_task_id ON attachments(task_id);




-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Wednesday, April 23, 2003 11:00 PM
To: Robert Dyas
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] query optimization scenarios 17,701 times
faster!!!


"Robert Dyas" <rdyas@adelphia.net> writes:
> The following is a list of query pairs (one fast, one slow) that must
> produce identical results by definition (and do), but have very different
> execution times.

With no details about the table schemas, nor the EXPLAIN ANALYZE output
data, I really wonder how you expect any intelligent comments.  We are
programmers, not mind-readers.

			regards, tom lane


Thu, 24 Apr 2003 10:12:31 -0400
"Robert Dyas" <rdyas@adelphia.net>
Re: query optimization scenarios 17,701 times faster!!! 
On Wed, Apr 23, 2003 at 02:04:02PM -0400, Robert Dyas wrote:
> 
> The following is a list of query pairs (one fast, one slow) that must
> produce identical results by definition (and do), but have very different
> execution times.

I think what you see is what is described in the documentation
too.  If you use outer joins, it will do them in the order of the
query.  I think the reason for that was that the SQL standard
required it.

So if you put your query in an other order, you will get a
different result.

I believe that they removed that restriction in the last/cvs
version of PosgresQL.

> Especially the last example.

Where it's joining alot of tables it doesn't use in the first
place.  You even removed the conditions on how to join the
tables.


Kurt


Thu, 24 Apr 2003 20:07:44 +0200
Kurt Roeckx <Q@ping.be>
Re: query optimization scenarios 17,701 times faster!!!
I was hoping to point out an extreme example in hopes of showing that some
very important optimizations are not taking place.

In a perfect world, two different queries that must by definition return the
same result would run the exact same query plan, which would be the fastest
one available. Yes, I know I'm stating the obvious, but sometimes that
helps.

There are some basic optimizations that I think may not be taking place that
could have a dramatic impact in many different scenarios. The biggest one
that I can see could be stated like this: "if a where clause includes a
restriction on a primary key column with a fixed value, only that row should
be used in subsequent query processing"

Conceptually that seems like an "easy win" for improving performance,
possibly very significantly in a wide variety of circumstances.


-----Original Message-----
From: Q@ping.be [mailto:Q@ping.be]
Sent: Thursday, April 24, 2003 2:08 PM
To: Robert Dyas
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] query optimization scenarios 17,701 times
faster!!!


On Wed, Apr 23, 2003 at 02:04:02PM -0400, Robert Dyas wrote:
>
> The following is a list of query pairs (one fast, one slow) that must
> produce identical results by definition (and do), but have very different
> execution times.

I think what you see is what is described in the documentation
too.  If you use outer joins, it will do them in the order of the
query.  I think the reason for that was that the SQL standard
required it.

So if you put your query in an other order, you will get a
different result.

I believe that they removed that restriction in the last/cvs
version of PosgresQL.

> Especially the last example.

Where it's joining alot of tables it doesn't use in the first
place.  You even removed the conditions on how to join the
tables.


Kurt


Thu, 24 Apr 2003 14:36:41 -0400
"Robert Dyas" <rdyas@adelphia.net>
Re: query optimization scenarios 17,701 times faster!!!

On Thu, 24 Apr 2003, Robert Dyas wrote:

> I was hoping to point out an extreme example in hopes of showing that some
> very important optimizations are not taking place.
>
> In a perfect world, two different queries that must by definition return the
> same result would run the exact same query plan, which would be the fastest
> one available. Yes, I know I'm stating the obvious, but sometimes that
> helps.

Of course in a perfect world doing the optimizations would take no time.
;)

> There are some basic optimizations that I think may not be taking place
that
> could have a dramatic impact in many different scenarios. The biggest one
> that I can see could be stated like this: "if a where clause includes a
> restriction on a primary key column with a fixed value, only that row should
> be used in subsequent query processing"

The particular conversion you're doing for that query requires more than
just that AFAICS. The outerness of the join makes it so you know there
won't be 0 rows after the join, and the distinct cancels out the
possibility of multiple rows. Both of those conditions seem necessary to
make the conversion valid as well.  And for your first example (with
the right join), it seems that you'd need to know that if there were
multiple matching rows with the right join that the output rows were
guaranteed to be distinct (since otherwise the select distinct might roll
the two rows together which would cause the output to change from the
second version of that example).  A more detailed example of what the
actual optimizations you're invisioning (rather than example queries)
might be helpful.

Also, I think there exists some chance of side effects that would be
elided by the second version in the case of views or set returning
functions, although I think we can probably ignore that.


Thu, 24 Apr 2003 12:17:09 -0700 (PDT)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: query optimization scenarios 17,701 times faster!!!
Stephan Szabo <sszabo@megazone23.bigpanda.com> writes:
> The particular conversion you're doing for that query requires more than
> just that AFAICS. The outerness of the join makes it so you know there
> won't be 0 rows after the join, and the distinct cancels out the
> possibility of multiple rows. Both of those conditions seem necessary to
> make the conversion valid as well.

Yeah.  I think the optimization rule being proposed here is something
like "if a table is not used in the SELECT output list, *and* it's on
the nullable side of an outer join (so that it can't cause rows to be
omitted from the output), *and* there's a DISTINCT (so that generating
multiple matched rows isn't interesting either) then don't bother to
include the table in the join tree".  But I'm not convinced that's
a safe transformation --- are there any other conditions that would
have to be checked?  And of course the $64 question is whether the
combination would hit often enough to make it worth the cycles to check
for.  It seems like a fairly unusual case to me.

The variant where you know there are not multiple rows because you're
joining on a unique column, rather than depending on DISTINCT, might
be more useful in practice ... but I'm still not convinced it's worth
checking for.

			regards, tom lane


Thu, 24 Apr 2003 20:30:40 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: query optimization scenarios 17,701 times faster!!! 