A fair number of the performance problems posted to mailing lists are
the result of the query planner choosing a poor query plan. Some of
these instances are due to a defect in PostgreSQL (e.g. index type
comparisons), but many of them are caused by inaccurate statistics:
either ANALYZE has not been run recently, or the statistics target for
this column needs to be raised.

It occurred to me that these kinds of poor planning decisions could
easily be detected by PostgreSQL itself: after we've finished
executing a plan, we can trivially compare the # of results produced
by each node in the query tree with the # of results the planner
expected that node to produce (look at EXPLAIN ANALYZE, for
example). If the estimate is off by a significant margin (say, 300%),
we could perhaps emit a HINT suggesting that the user re-run ANALYZE
or raise the statistics target for the relevant column. We can add a
GUC to control whether any of these messages are emitted at all, or
perhaps the degree of estimation error that is deemed acceptable.

One potential problem might involve queries that the planner will
almost *never* do a good job on (see [1] for example). Until we get
around to improving the planner, there isn't much universally-
applicable advice we can offer in these situations: running ANALYZE
all day or setting the statistics target arbitrarily high won't
significantly improve the chosen query plan, so you'd continue to see
the hint described above.

BTW, this situation is a simple example of the general technique of
using feedback from the executor to improve query optimization
decisions. If you're interested, there is plenty of discussion of this
topic in the DBMS literature -- I'd be happy to provide pointers to
papers. It might be cool to try implementing some of this stuff for
PostgreSQL in the future.

Comments?

-Neil

[1] http://www.mail-archive.com/pgsql-performance%40postgresql.org/msg02415.html


Wed, 26 Nov 2003 10:11:18 -0500
Neil Conway <neilc@samurai.com>
detecting poor query plans
>>>>> "Neil" == Neil Conway <neilc@samurai.com> writes:

    Neil> It occurred to me that these kinds of poor planning
    Neil> decisions could easily be detected by PostgreSQL itself:
    Neil> after we've finished executing a plan, we can trivially
    Neil> compare the # of results produced by each node in the query
    Neil> tree with the # of results the planner expected that node to
    Neil> produce (look at EXPLAIN ANALYZE, for example). If the

Indeed. This is the approach being followed by the LeO project
(Learning Optimizer) at IBM Almaden. 

http://www.almaden.ibm.com/software/dm/SMART/leo.shtml

There is a vldb paper that describes it .. 

-- 
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh



Wed, 26 Nov 2003 07:59:58 -0800
Sailesh Krishnamurthy <sailesh@cs.berkeley.edu>
Re: detecting poor query plans
Neil Conway <neilc@samurai.com> writes:
> It occurred to me that these kinds of poor planning decisions could
> easily be detected by PostgreSQL itself: after we've finished
> executing a plan, we can trivially compare the # of results produced
> by each node in the query tree with the # of results the planner
> expected that node to produce (look at EXPLAIN ANALYZE, for
> example). If the estimate is off by a significant margin (say, 300%),
> we could perhaps emit a HINT suggesting that the user re-run ANALYZE

I think such a thing would have such a low signal-to-noise ratio as to
be useless :-(.  As you note, there are many places where the planner's
estimate is routinely off by more than 3x (or any other threshold you
might pick instead).  In some situations that doesn't really matter,
as the same plan would have gotten picked anyway.  Also, since 7.2 came
out what we've seen more and more is cases where the row count estimate
is acceptably good, but the wrong plan was picked anyway because of
deficiencies in the cost equations.

The question you really want to know about is not whether the row count
estimate is close, it's whether another plan could have done better.

			regards, tom lane

Wed, 26 Nov 2003 11:00:01 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: detecting poor query plans 

Neil Conway <neilc@samurai.com> writes:

> It occurred to me that these kinds of poor planning decisions could easily
> be detected by PostgreSQL itself: after we've finished executing a plan, we
> can trivially compare the # of results produced by each node in the query
> tree with the # of results the planner expected that node to produce

There's a dual to this as well. If the results were very close but the actual
time taken to run the node doesn't match the cost calculated then some
optimizer parameter needs to be adjusted. Either one of the cost_* parameters
or random_page_cost, or effective_cache_size or...

I'm not sure it's as obvious what to put in the HINT though. Ideally these
results would have to be gathered and pumped through linear optimization
algorithms which is a lot more work.

-- 
greg


26 Nov 2003 11:14:36 -0500
Greg Stark <gsstark@mit.edu>
Re: detecting poor query plans
Tom Lane <tgl@sss.pgh.pa.us> writes:
> I think such a thing would have such a low signal-to-noise ratio as
> to be useless :-(.  As you note, there are many places where the
> planner's estimate is routinely off by more than 3x (or any other
> threshold you might pick instead).

I wonder, perhaps we could add a "certainty" parameter to the
estimated query plan + result sizes + costs produced by the
planner. That way, when we run into a planner deficiency we can
basically mark the relevant portion of the query tree as a WAG, and
not bother with emitting hints for it.

> In some situations that doesn't really matter, as the same plan
> would have gotten picked anyway.

The hint is NOT "the chosen plan was non-optimal"; the hint is "the
query planner did not produce an accurate row count estimate for this
node in the query tree." The chosen query plan may or may not be
optimal -- we're merely pointing out that we chose the plan we did on
shakey grounds. The hint might just as well indicate a problem with
another query that happens to apply a similar predicate to the column
in question.

> The question you really want to know about is not whether the row
> count estimate is close, it's whether another plan could have done
> better.

Perhaps, but is there a reasonable way to answer the second question?

-Neil


Wed, 26 Nov 2003 11:59:33 -0500
Neil Conway <neilc@samurai.com>
Re: detecting poor query plans
On Wed, Nov 26, 2003 at 11:59:33AM -0500, Neil Conway wrote:

> > In some situations that doesn't really matter, as the same plan
> > would have gotten picked anyway.
> 
> The hint is NOT "the chosen plan was non-optimal"; the hint is "the
> query planner did not produce an accurate row count estimate for this
> node in the query tree."

Maybe it could only be done for SeqScan and IndexScan nodes, which are
probably the most common source of bad estimates related to poor
statistics.

-- 
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"At least to kernel hackers, who really are human, despite occasional
rumors to the contrary" (LWN.net)

Wed, 26 Nov 2003 14:38:47 -0300
Alvaro Herrera <alvherre@dcc.uchile.cl>
Re: detecting poor query plans
Greg Stark <gsstark@mit.edu> writes:
> There's a dual to this as well. If the results were very close but
> the actual time taken to run the node doesn't match the cost
> calculated then some optimizer parameter needs to be adjusted.

I was thinking about this, but I couldn't think of how to get it to
work properly:

     (1) The optimizer's cost metric is somewhat bogus to begin with.
         ISTM that translating a cost of X into an expected runtime of
         Y msecs is definitely not trivial to do.

     (2) The size of a node's result relation does not depend upon
         anything outside of PostgreSQL, whereas the exact time it
         takes to produce that result relation depends on a wide
         collection of external factors. For example, if the system is
         under heavy load, queries will take longer than normal to
         run. Or, if the query invokes a function that happens to
         occasionally block waiting on some resource, the execution
         time of the query could be wildly unpredictable.

     (3) ISTM we couldn't produce a really helpful hint message, even
         if we somehow resolved #1 and #2

-Neil


Wed, 26 Nov 2003 15:33:56 -0500
Neil Conway <neilc@samurai.com>
Re: detecting poor query plans
Neil Conway <neilc@samurai.com> writes:

> I was thinking about this, but I couldn't think of how to get it to
> work properly:
> 
>      (1) The optimizer's cost metric is somewhat bogus to begin with.
>          ISTM that translating a cost of X into an expected runtime of
>          Y msecs is definitely not trivial to do.

At least for all the possible plans of a given query at a specific point in
time the intention is that the cost be proportional to the execution time. 

> the exact time it takes to produce that result relation depends on a wide
> collection of external factors.

That's a valid point. The ms/cost factor may not be constant over time.
However I think in the normal case this number will tend towards a fairly
consistent value across queries and over time. It will be influenced somewhat
by things like cache contention with other applications though.

On further thought the real problem is that these numbers are only available
when running with "explain" on. As shown recently on one of the lists, the
cost of the repeated gettimeofday calls can be substantial. It's not really
feasible to suggest running all queries with that profiling.

-- 
greg


26 Nov 2003 15:45:49 -0500
Greg Stark <gsstark@mit.edu>
Re: detecting poor query plans
Greg Stark <gsstark@mit.edu> writes:
> At least for all the possible plans of a given query at a specific
> point in time the intention is that the cost be proportional to the
> execution time.

Why is this relevant? 

Given a cost X at a given point in time, the system needs to derive an
"expected runtime" Y, and compare Y with the actual runtime. I think
that producing Y given an arbitrary X involves so many parameters as
to be practically impossible for us to compute with any degree of
accuracy.

> That's a valid point. The ms/cost factor may not be constant over
> time.  However I think in the normal case this number will tend
> towards a fairly consistent value across queries and over time.

It might be true in the "normal case", but that doesn't seem very
helpful to me: in general, the mapping of plan costs to execution time
can vary wildly over time. Spewing "hints" to the log whenever the
system's workload changes, a checkpoint occurs, or the system's RAID
array hiccups doesn't sound like a useful feature to me.

> On further thought the real problem is that these numbers are only
> available when running with "explain" on. As shown recently on one
> of the lists, the cost of the repeated gettimeofday calls can be
> substantial.

That sounds more like an implementation detail than the "real problem"
to me -- I think this proposed feature has more fundamental issues.

-Neil


Wed, 26 Nov 2003 16:10:01 -0500
Neil Conway <neilc@samurai.com>
Re: detecting poor query plans
Greg Stark <gsstark@mit.edu> writes:
> That's a valid point. The ms/cost factor may not be constant over time.
> However I think in the normal case this number will tend towards a fairly
> consistent value across queries and over time. It will be influenced somewhat
> by things like cache contention with other applications though.

I think it would be interesting to collect the numbers over a long
period of time and try to learn something from the averages.  The real
hole in Neil's original suggestion was that it assumed that comparisons
based on just a single query would be meaningful enough to pester the
user about.

> On further thought the real problem is that these numbers are only available
> when running with "explain" on. As shown recently on one of the lists, the
> cost of the repeated gettimeofday calls can be substantial. It's not really
> feasible to suggest running all queries with that profiling.

Yeah.  You could imagine a simplified-stats mode that only collects the
total runtime (two gettimeofday's per query is nothing) and the row
counts (shouldn't be impossibly expensive either, especially if we
merged the needed fields into PlanState instead of requiring a
separately allocated node).  Not sure if that's as useful though.

			regards, tom lane

Wed, 26 Nov 2003 17:14:36 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: detecting poor query plans 
> > On further thought the real problem is that these numbers are only available
> > when running with "explain" on. As shown recently on one of the lists, the
> > cost of the repeated gettimeofday calls can be substantial. It's not really
> > feasible to suggest running all queries with that profiling.
>
> Yeah.  You could imagine a simplified-stats mode that only collects the
> total runtime (two gettimeofday's per query is nothing) and the row
> counts (shouldn't be impossibly expensive either, especially if we
> merged the needed fields into PlanState instead of requiring a
> separately allocated node).  Not sure if that's as useful though.

How about a PGC_POSTMASTER GUC variable which tells postgres to collect
details on the planner's performance and comparison to actual run times.
Optionally, we could also have the executor run some/all of the possible
plans (presumably only useful for SELECTs) and keep details on the
performance of each. At postmaster shutdown (some other time?) a report
could be produced profiling all queries.

The reason I suggest this is it would have zero impact on production
databases but would allow DBAs to profile their databases with real usage
patterns in development environments.

Gavin

Thu, 27 Nov 2003 10:50:17 +1100 (EST)
Gavin Sherry <swm@linuxworld.com.au>
Re: detecting poor query plans 
Gavin Sherry wrote:
> > > On further thought the real problem is that these numbers are only available
> > > when running with "explain" on. As shown recently on one of the lists, the
> > > cost of the repeated gettimeofday calls can be substantial. It's not really
> > > feasible to suggest running all queries with that profiling.
> >
> > Yeah.  You could imagine a simplified-stats mode that only collects the
> > total runtime (two gettimeofday's per query is nothing) and the row
> > counts (shouldn't be impossibly expensive either, especially if we
> > merged the needed fields into PlanState instead of requiring a
> > separately allocated node).  Not sure if that's as useful though.
> 
> How about a PGC_POSTMASTER GUC variable which tells postgres to collect
> details on the planner's performance and comparison to actual run times.
> Optionally, we could also have the executor run some/all of the possible
> plans (presumably only useful for SELECTs) and keep details on the
> performance of each. At postmaster shutdown (some other time?) a report
> could be produced profiling all queries.
> 
> The reason I suggest this is it would have zero impact on production
> databases but would allow DBAs to profile their databases with real usage
> patterns in development environments.

Great idea.  Under ideal situations, it shouldn't be needed, but things
are often less than idea.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Wed, 26 Nov 2003 21:53:52 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: detecting poor query plans