Re: [HACKERS] cost_sort() may need to be updated

[Peter Geoghegan]

On Tue, Sep 13, 2016 at 5:59 AM, Robert Haas  wrote:
> I think that the only real way to judge whether cost_sort() is any
> good is to see whether it causes the wrong plan to be chosen in some
> cases.  For example, it could cause merge joins to be picked too
> frequently or too infrequently, or it could cause a wrong decision
> between hash and group aggregates.  Now, there is bound to be an
> argument about whether any test cases that we might pick are
> representative and the results will further differ between hardware
> platforms, but I think changing the formula based on an abstract idea
> about what's happening is probably not a good idea.

I don't disagree with any of this. And, I don't pretend to have the
best understanding of how real world observations on the quality of
plans can make its way back into the query plan, and be integrated,
without regressing too many other things.

The basis of my complaint is that cost_sort() typically costs external
sorts as twice or more as expensive as internal sorts, and that that
does not seem at all consistent with my *recent* observations, without
even bringing caching effects into it. That seems safe enough for
someone that is relatively unfamiliar with the optimizer to have as a
general concern, because external sorts and internal sorts really
aren't so different these days.

> Because it's necessary to set work_mem so conservatively to avoid
> running out of memory, most supposedly-external sorts aren't really
> doing any I/O at all, and therefore arguing about whether we should be
> charging seq_page_cost or random_page_cost for I/O is kinda missing
> the point.

I don't take issue with how internal sorts are costed at all. I think
that the factors that direct the tuning of work_mem might prominently
include the anti-scaling effect of replacement selection. To the DBA,
that can just look like simple memory pressure, perhaps. Time will
tell how true this is.

> Those numbers may just be reflecting other work that the
> sort is doing that isn't being properly accounted for elsewhere, or
> it's possible that the current costing of sorts is fairly far away
> from reality.  How would we know?  The only thing that makes me think
> they probably aren't *too* bad is that in a somewhat-systematic study
> of query performance problems
> (https://sites.google.com/site/robertmhaas/query-performance) done
> several years ago I found no evidence of a problem with sort costing,
> and my experience outside of that study bears that out.  But that's
> pretty back of the envelope.

It's also out of date. As I said, we don't have any real field
experience with the 9.6 external sort changes yet, but we'll have some
soon enough.

I'm happy to leave it at that, for now -- maybe someone will recall
this thread at a later date, when there is a complaint about a
suboptimal query plan from a user.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] cost_sort() may need to be updated

[Robert Haas]

On Sun, Sep 11, 2016 at 12:13 PM, Peter Geoghegan  wrote:
> On Sun, Sep 11, 2016 at 9:01 AM, Tom Lane  wrote:
>> Peter Geoghegan  writes:
>>> I think that we *can* refine this guess, and should, because random
>>> I/O is really quite unlikely to be a large cost these days (I/O in
>>> general often isn't a large cost, actually). More fundamentally, I
>>> think it's a problem that cost_sort() thinks that external sorts are
>>> far more expensive than internal sorts in general. There is good
>>> reason to think that that does not reflect the reality. I think we can
>>> expect external sorts to be *faster* than internal sorts with
>>> increasing regularity in Postgres 10.
>>
>> TBH, if that's true, haven't you broken something?
>
> It's possible for external sorts to be faster some of the time because
> the memory access patterns can be more cache efficient: smaller runs
> are better when accessing tuples in sorted order, scattered across
> memory. More importantly, the sort can start returning tuples earlier
> in the common case where a final on-the-fly merge can be performed. In
> principle, you could adopt internal sorts to have the same advantages,
> but that hasn't and probably won't happen. Finally, the external sort
> I/O costs grow linearly, whereas the CPU costs grow in a linearithmic
> fashion, which will eventually come to dominate. We can hide the
> latency of those costs pretty well, too, with asynchronous I/O.
>
> I'm not arguing that cost_sort() should think that external sorts are
> cheaper under any circumstances, since all of this is very hard to
> model. I only mention this because it illustrates nicely that
> cost_sort() has the wrong idea.

I think that the only real way to judge whether cost_sort() is any
good is to see whether it causes the wrong plan to be chosen in some
cases.  For example, it could cause merge joins to be picked too
frequently or too infrequently, or it could cause a wrong decision
between hash and group aggregates.  Now, there is bound to be an
argument about whether any test cases that we might pick are
representative and the results will further differ between hardware
platforms, but I think changing the formula based on an abstract idea
about what's happening is probably not a good idea.

Because it's necessary to set work_mem so conservatively to avoid
running out of memory, most supposedly-external sorts aren't really
doing any I/O at all, and therefore arguing about whether we should be
charging seq_page_cost or random_page_cost for I/O is kinda missing
the point.  Those numbers may just be reflecting other work that the
sort is doing that isn't being properly accounted for elsewhere, or
it's possible that the current costing of sorts is fairly far away
from reality.  How would we know?  The only thing that makes me think
they probably aren't *too* bad is that in a somewhat-systematic study
of query performance problems
(https://sites.google.com/site/robertmhaas/query-performance) done
several years ago I found no evidence of a problem with sort costing,
and my experience outside of that study bears that out.  But that's
pretty back of the envelope.

Of course, the issue of supposed I/O actually being reads of cached
data is not unique to sorting.  Sequential scans have the same
problem.  We've previously discussed the idea of adding a
cached_page_cost, but this has fallen down over the issue that you
also need to know what percentage of the table is likely to be read
from cache, and you don't want that estimate to be too unstable or
your plans will bounce all over the place.  One idea I had for dealing
with that is to just base it on the size of the table: assume small
tables are probably cached, and large tables probably aren't.  The
latter is certainly true at least in the case where "large" means
"bigger than physical memory", and the former isn't a bad guess
either.  So basically where this would go is to assume that scanning a
small table is cheaper per page than scanning a big one, which I
suspect is probably better than the uniform estimate we're using
today.  However, I haven't got a single test case to prove it, and in
fact I'm not even sure how one could go about figuring out whether
this makes things better or worse in general.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] cost_sort() may need to be updated

[Peter Geoghegan]

On Sun, Sep 11, 2016 at 9:01 AM, Tom Lane  wrote:
> Peter Geoghegan  writes:
>> I think that we *can* refine this guess, and should, because random
>> I/O is really quite unlikely to be a large cost these days (I/O in
>> general often isn't a large cost, actually). More fundamentally, I
>> think it's a problem that cost_sort() thinks that external sorts are
>> far more expensive than internal sorts in general. There is good
>> reason to think that that does not reflect the reality. I think we can
>> expect external sorts to be *faster* than internal sorts with
>> increasing regularity in Postgres 10.
>
> TBH, if that's true, haven't you broken something?

It's possible for external sorts to be faster some of the time because
the memory access patterns can be more cache efficient: smaller runs
are better when accessing tuples in sorted order, scattered across
memory. More importantly, the sort can start returning tuples earlier
in the common case where a final on-the-fly merge can be performed. In
principle, you could adopt internal sorts to have the same advantages,
but that hasn't and probably won't happen. Finally, the external sort
I/O costs grow linearly, whereas the CPU costs grow in a linearithmic
fashion, which will eventually come to dominate. We can hide the
latency of those costs pretty well, too, with asynchronous I/O.

I'm not arguing that cost_sort() should think that external sorts are
cheaper under any circumstances, since all of this is very hard to
model. I only mention this because it illustrates nicely that
cost_sort() has the wrong idea.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] cost_sort() may need to be updated

[Tom Lane]

Peter Geoghegan  writes:
> I think that we *can* refine this guess, and should, because random
> I/O is really quite unlikely to be a large cost these days (I/O in
> general often isn't a large cost, actually). More fundamentally, I
> think it's a problem that cost_sort() thinks that external sorts are
> far more expensive than internal sorts in general. There is good
> reason to think that that does not reflect the reality. I think we can
> expect external sorts to be *faster* than internal sorts with
> increasing regularity in Postgres 10.

TBH, if that's true, haven't you broken something?

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] cost_sort() may need to be updated

[Peter Geoghegan]

For external sorts, cost_sort() assumes the following:

 * The disk traffic is assumed to be 3/4ths sequential and 1/4th random
 * accesses (XXX can't we refine that guess?)

...
/* Assume 3/4ths of accesses are sequential, 1/4th are not */
startup_cost += npageaccesses *
(seq_page_cost * 0.75 + random_page_cost * 0.25);

I think that we *can* refine this guess, and should, because random
I/O is really quite unlikely to be a large cost these days (I/O in
general often isn't a large cost, actually). More fundamentally, I
think it's a problem that cost_sort() thinks that external sorts are
far more expensive than internal sorts in general. There is good
reason to think that that does not reflect the reality. I think we can
expect external sorts to be *faster* than internal sorts with
increasing regularity in Postgres 10.

In one sense, things got worse here in 9.6 when replacement selection
was all but killed, since runs became on average half their size,
which cost_sort() was taught about at the time. But, cost_sort()
didn't care about cases where only one pass is predicted (the great
majority of external sorts), so that didn't really matter. cost_sort()
doesn't seem to care about the size of runs to be merged at all, which
seems limiting. It also seems limiting that cost_sort() doesn't
differentiate between internal and external sort *startup* costs at
all. External sorts can often start returning tuples sooner, due to
the final on-the-fly merge mechanism.

It's pretty common to see cases where merging 4 runs takes only
slightly less time than an internal sort, and yet are thought to cost
more than twice as much. I realize that costs are always a bit fudged,
but I am fairly suspicious of how big the differences between external
and internal sorts regularly are. I suggest that this be revisited
soon.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers