pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedYet another abort-early plan disaster on 9.3
60+ messages / 16 participants
[nested] [flat]
* Yet another abort-early plan disaster on 9.3
@ 2014-09-18 00:11 Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-09-18 00:11 UTC (permalink / raw)
To: pgsql-performance
Folks,
Just encountered another case of critical fail for abort-early query
plans. In this case, it will completely prevent a user from upgrading
to 9.3; this is their most common query, and on 9.3 it takes 1000X longer.
Maybe we should think about removing abort-early plans from 9.5?
Clearly we don't understand them well enough for them to work for users.
Query:
SELECT "categories".* FROM "categories" WHERE "categories"."user_id" IN
( SELECT to_user_id FROM "tags" WHERE "tags"."from_user_id" = 53529975 )
ORDER BY recorded_on DESC LIMIT 20;
Here's the plan from 9.1:
Limit (cost=1613.10..1613.15 rows=20 width=194) (actual
time=0.503..0.509 rows=20 loops=1)
-> Sort (cost=1613.10..1736.14 rows=49215 width=194) (actual
time=0.502..0.505 rows=20 loops=1)
Sort Key: categories.recorded_on
Sort Method: top-N heapsort Memory: 30kB
-> Nested Loop (cost=248.80..303.51 rows=49215 width=194)
(actual time=0.069..0.347 rows=81 loops=1)
-> HashAggregate (cost=248.80..248.81 rows=1 width=4)
(actual time=0.050..0.054 rows=8 loops=1)
-> Index Scan using unique_index_tags on tags
(cost=0.00..248.54 rows=103 width=4) (actual time=0.020..0.033 rows=8
loops=1)
Index Cond: (from_user_id = 53529975)
-> Index Scan using index_categories_on_user_id on
categories (cost=0.00..54.34 rows=29 width=194) (actual
time=0.010..0.028 rows=10 loops=8)
Index Cond: (user_id = tags.to_user_id)
Total runtime: 0.641 ms
And from 9.3:
Limit (cost=1.00..2641.10 rows=20 width=202) (actual
time=9.933..711.372 rows=20 loops=1)
-> Nested Loop Semi Join (cost=1.00..9641758.39 rows=73041
width=202) (actual time=9.931..711.361 rows=20 loops=1)
-> Index Scan Backward using index_categories_on_recorded_on
on categories (cost=0.43..406943.98 rows=4199200 width=202) (actual
time=0.018..275.020 rows=170995 loops=1)
-> Index Scan using unique_index_tags on tags
(cost=0.57..2.20 rows=1 width=4) (actual time=0.002..0.002 rows=0
loops=170995)
Index Cond: ((from_user_id = 53529975) AND (to_user_id =
categories.user_id))
Total runtime: 711.457 ms
So, here's what's happening here:
As usual, PostgreSQL is dramatically undercounting n_distinct: it shows
chapters.user_id at 146,000 and the ratio of to_user_id:from_user_id as
being 1:105 (as opposed to 1:6, which is about the real ratio). This
means that PostgreSQL thinks it can find the 20 rows within the first 2%
of the index ... whereas it actually needs to scan 50% of the index to
find them.
Removing LIMIT causes 9.3 to revert to the "good" plan, as expected.
This is the core issue with abort-early plans; they depend on our
statistics being extremely accurate, which we know they are not. And if
they're wrong, the execution time climbs by 1000X or more. Abort-early
plans are inherently riskier than other types of query plans.
What I'm not clear on is why upgrading from 9.1 to 9.3 would bring about
this change. The stats are no more than 10% different across the
version change.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-19 17:15 Merlin Moncure <mmoncure@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 60+ messages in thread
From: Merlin Moncure @ 2014-09-19 17:15 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-performance
On Wed, Sep 17, 2014 at 7:11 PM, Josh Berkus <josh@agliodbs.com> wrote:
> Folks,
>
> Just encountered another case of critical fail for abort-early query
> plans. In this case, it will completely prevent a user from upgrading
> to 9.3; this is their most common query, and on 9.3 it takes 1000X longer.
>
> Maybe we should think about removing abort-early plans from 9.5?
> Clearly we don't understand them well enough for them to work for users.
>
> Query:
>
> SELECT "categories".* FROM "categories" WHERE "categories"."user_id" IN
> ( SELECT to_user_id FROM "tags" WHERE "tags"."from_user_id" = 53529975 )
> ORDER BY recorded_on DESC LIMIT 20;
>
> Here's the plan from 9.1:
>
> Limit (cost=1613.10..1613.15 rows=20 width=194) (actual
> time=0.503..0.509 rows=20 loops=1)
> -> Sort (cost=1613.10..1736.14 rows=49215 width=194) (actual
> time=0.502..0.505 rows=20 loops=1)
> Sort Key: categories.recorded_on
> Sort Method: top-N heapsort Memory: 30kB
> -> Nested Loop (cost=248.80..303.51 rows=49215 width=194)
> (actual time=0.069..0.347 rows=81 loops=1)
> -> HashAggregate (cost=248.80..248.81 rows=1 width=4)
> (actual time=0.050..0.054 rows=8 loops=1)
> -> Index Scan using unique_index_tags on tags
> (cost=0.00..248.54 rows=103 width=4) (actual time=0.020..0.033 rows=8
> loops=1)
> Index Cond: (from_user_id = 53529975)
> -> Index Scan using index_categories_on_user_id on
> categories (cost=0.00..54.34 rows=29 width=194) (actual
> time=0.010..0.028 rows=10 loops=8)
> Index Cond: (user_id = tags.to_user_id)
> Total runtime: 0.641 ms
>
> And from 9.3:
>
> Limit (cost=1.00..2641.10 rows=20 width=202) (actual
> time=9.933..711.372 rows=20 loops=1)
> -> Nested Loop Semi Join (cost=1.00..9641758.39 rows=73041
> width=202) (actual time=9.931..711.361 rows=20 loops=1)
> -> Index Scan Backward using index_categories_on_recorded_on
> on categories (cost=0.43..406943.98 rows=4199200 width=202) (actual
> time=0.018..275.020 rows=170995 loops=1)
> -> Index Scan using unique_index_tags on tags
> (cost=0.57..2.20 rows=1 width=4) (actual time=0.002..0.002 rows=0
> loops=170995)
> Index Cond: ((from_user_id = 53529975) AND (to_user_id =
> categories.user_id))
> Total runtime: 711.457 ms
>
> So, here's what's happening here:
>
> As usual, PostgreSQL is dramatically undercounting n_distinct: it shows
> chapters.user_id at 146,000 and the ratio of to_user_id:from_user_id as
> being 1:105 (as opposed to 1:6, which is about the real ratio). This
> means that PostgreSQL thinks it can find the 20 rows within the first 2%
> of the index ... whereas it actually needs to scan 50% of the index to
> find them.
>
> Removing LIMIT causes 9.3 to revert to the "good" plan, as expected.
>
> This is the core issue with abort-early plans; they depend on our
> statistics being extremely accurate, which we know they are not. And if
> they're wrong, the execution time climbs by 1000X or more. Abort-early
> plans are inherently riskier than other types of query plans.
>
> What I'm not clear on is why upgrading from 9.1 to 9.3 would bring about
> this change. The stats are no more than 10% different across the
> version change.
Amusingly on-topic rant I happened to read immediately after this by chance:
http://wp.sigmod.org/?p=1075
Is there a canonical case of where 'abort early' plans help? (I'm new
to that term -- is it a recent planner innovation...got any handy
links?)
merlin
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-19 18:40 Josh Berkus <josh@agliodbs.com>
parent: Merlin Moncure <mmoncure@gmail.com>
0 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-09-19 18:40 UTC (permalink / raw)
To: Merlin Moncure <mmoncure@gmail.com>; +Cc: pgsql-performance
On 09/19/2014 10:15 AM, Merlin Moncure wrote:
> On Wed, Sep 17, 2014 at 7:11 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> This is the core issue with abort-early plans; they depend on our
>> statistics being extremely accurate, which we know they are not. And if
>> they're wrong, the execution time climbs by 1000X or more. Abort-early
>> plans are inherently riskier than other types of query plans.
>>
>> What I'm not clear on is why upgrading from 9.1 to 9.3 would bring about
>> this change. The stats are no more than 10% different across the
>> version change.
>
> Amusingly on-topic rant I happened to read immediately after this by chance:
>
> http://wp.sigmod.org/?p=1075
>
> Is there a canonical case of where 'abort early' plans help? (I'm new
> to that term -- is it a recent planner innovation...got any handy
> links?)
Yeah, here's an example of the canonical case:
Table t1 ( a, b, c )
- "b" is low-cardinality
- "c" is high-cardinality
- There are separate indexes on both b and c.
SELECT a, b, c FROM t1
WHERE b = 2
ORDER BY c LIMIT 1;
In this case, the fastest plan is usually to use the index on C and
return the first row where the filter condition matches the filter on b.
This can be an order of magnitude faster than using the index on b and
then resorting by c and taking the first row, if (b=2) happens to match
20% of the table.
This is called an "abort early" plan because we expect to never finish
the scan on the index on c. We expect to scan the index on c, find the
first row that matches b=2 and exit.
The problem with such plans is that they are "risky". As in, if we are
wrong about our (b=2) stats, then we've just adopted a query plan which
will be 10X to 1000X slower than the more conventional plan.
We can see this in the bad plan I posted:
Limit (cost=1.00..2641.10 rows=20 width=202) (actual
time=9.933..711.372 rows=20 loops=1)
-> Nested Loop Semi Join (cost=1.00..9641758.39 rows=73041
width=202) (actual time=9.931..711.361 rows=20 loops=1)
-> Index Scan Backward using index_categories_on_recorded_on
on categories (cost=0.43..406943.98 rows=4199200 width=202) (actual
time=0.018..275.020 rows=170995 loops=1)
Notice how the total cost of the plan is a fraction of the cost of the
two steps which preceeded it? This is an indication that the planner
expects to be able to abort the index scan and nestloop join before it's
more than 2% through it.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-20 06:38 Greg Stark <stark@mit.edu>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 3 replies; 60+ messages in thread
From: Greg Stark @ 2014-09-20 06:38 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 19 Sep 2014 19:40, "Josh Berkus" <josh@agliodbs.com> wrote:
>
> On 09/19/2014 10:15 AM, Merlin Moncure wrote:
> > On Wed, Sep 17, 2014 at 7:11 PM, Josh Berkus <josh@agliodbs.com> wrote:
> >> This is the core issue with abort-early plans; they depend on our
> >> statistics being extremely accurate, which we know they are not. And if
> >> they're wrong, the execution time climbs by 1000X or more. Abort-early
> >> plans are inherently riskier than other types of query plans.
All plans are risky if the stats are wrong. It's one of the perennial
digressions that many postgres newcomers make to track worst case costs and
provide a knob for planner aggressiveness but it always breaks down when
you try to quantify the level of risk because you discover that even such
simple things as indeed scans versus sequential scans can be equally risky
either way.
> >> What I'm not clear on is why upgrading from 9.1 to 9.3 would bring
about
> >> this change. The stats are no more than 10% different across the
> >> version change.
There's no difference. Postgres has been estimating LIMIT costs this way
since before I came to postgres in 7.3.
> > Is there a canonical case of where 'abort early' plans help? (I'm new
> > to that term -- is it a recent planner innovation...got any handy
> > links?)
>
> Yeah, here's an example of the canonical case:
>
> Table t1 ( a, b, c )
>
> - "b" is low-cardinality
> - "c" is high-cardinality
> - There are separate indexes on both b and c.
>
> SELECT a, b, c FROM t1
> WHERE b = 2
> ORDER BY c LIMIT 1;
You badly want a partial index on c WHERE b=2 for each value of 2 which
appears in your queries.
It would be neat to have an opclass which worked like that. Which would
amount to having prefix compression perhaps.
What plan does 9.1 come up with?
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-20 11:51 Claudio Freire <klaussfreire@gmail.com>
parent: Greg Stark <stark@mit.edu>
2 siblings, 0 replies; 60+ messages in thread
From: Claudio Freire @ 2014-09-20 11:51 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: Josh Berkus <josh@agliodbs.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Sat, Sep 20, 2014 at 3:38 AM, Greg Stark <stark@mit.edu> wrote:
>> > Is there a canonical case of where 'abort early' plans help? (I'm new
>> > to that term -- is it a recent planner innovation...got any handy
>> > links?)
>>
>> Yeah, here's an example of the canonical case:
>>
>> Table t1 ( a, b, c )
>>
>> - "b" is low-cardinality
>> - "c" is high-cardinality
>> - There are separate indexes on both b and c.
>>
>> SELECT a, b, c FROM t1
>> WHERE b = 2
>> ORDER BY c LIMIT 1;
>
> You badly want a partial index on c WHERE b=2 for each value of 2 which
> appears in your queries.
>
> It would be neat to have an opclass which worked like that. Which would
> amount to having prefix compression perhaps.
I've been looking at that exactly.
One complexity of it, is that splitting becomes much harder. As in, recursive.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-20 15:01 Tom Lane <tgl@sss.pgh.pa.us>
parent: Greg Stark <stark@mit.edu>
2 siblings, 0 replies; 60+ messages in thread
From: Tom Lane @ 2014-09-20 15:01 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: Josh Berkus <josh@agliodbs.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
Greg Stark <stark@mit.edu> writes:
> On 19 Sep 2014 19:40, "Josh Berkus" <josh@agliodbs.com> wrote:
>> Yeah, here's an example of the canonical case:
>>
>> Table t1 ( a, b, c )
>>
>> - "b" is low-cardinality
>> - "c" is high-cardinality
>> - There are separate indexes on both b and c.
>>
>> SELECT a, b, c FROM t1
>> WHERE b = 2
>> ORDER BY c LIMIT 1;
> You badly want a partial index on c WHERE b=2 for each value of 2 which
> appears in your queries.
Well, if it's *only* b = 2 that you ever search for, then maybe a partial
index would be a good answer. Personally I'd use a plain btree index on
(b, c). The planner's been able to match this type of query to
multicolumn indexes for a long time.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-20 18:33 Josh Berkus <josh@agliodbs.com>
parent: Greg Stark <stark@mit.edu>
2 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-09-20 18:33 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 09/19/2014 11:38 PM, Greg Stark wrote:
>
> On 19 Sep 2014 19:40, "Josh Berkus" <josh@agliodbs.com
> <mailto:josh@agliodbs.com>> wrote:
>>
>> On 09/19/2014 10:15 AM, Merlin Moncure wrote:
>> > On Wed, Sep 17, 2014 at 7:11 PM, Josh Berkus <josh@agliodbs.com
> <mailto:josh@agliodbs.com>> wrote:
>> >> This is the core issue with abort-early plans; they depend on our
>> >> statistics being extremely accurate, which we know they are not. And if
>> >> they're wrong, the execution time climbs by 1000X or more. Abort-early
>> >> plans are inherently riskier than other types of query plans.
>
> All plans are risky if the stats are wrong. It's one of the perennial
> digressions that many postgres newcomers make to track worst case costs
> and provide a knob for planner aggressiveness but it always breaks down
> when you try to quantify the level of risk because you discover that
> even such simple things as indeed scans versus sequential scans can be
> equally risky either way.
I've had a *wee* bit more experience with query plans than most Postgres
newcomers, Greg.
While all query plan changes can result in regressions if they're bad,
there are certain kinds of plans which depend more on accurate stats
than others. Abort-early plans are the most extreme of these. Most
likely we should adjust the cost model for abort-early plans to take in
our level of uncertainty, especially since we *know* that our n-distinct
estimation is crap. For example, we could increase the estimated cost
for an abort-early index scan by 10X, to reflect our weak confidence in
its correctness.
We could also probably do the same for plans which depend on column
correlation estimates being accurate.
>
>> >> What I'm not clear on is why upgrading from 9.1 to 9.3 would bring
> about
>> >> this change. The stats are no more than 10% different across the
>> >> version change.
>
> There's no difference. Postgres has been estimating LIMIT costs this way
> since before I came to postgres in 7.3.
Then why is the plan different in 9.1 and 9.3 with identical stats (I
tested)?
>
> It would be neat to have an opclass which worked like that. Which would
> amount to having prefix compression perhaps.
>
> What plan does 9.1 come up with?
That was the "good" plan from my original post.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-22 13:55 Merlin Moncure <mmoncure@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 60+ messages in thread
From: Merlin Moncure @ 2014-09-22 13:55 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Greg Stark <stark@mit.edu>; pgsql-performance
On Sat, Sep 20, 2014 at 1:33 PM, Josh Berkus <josh@agliodbs.com> wrote:
> For example, we could increase the estimated cost
> for an abort-early index scan by 10X, to reflect our weak confidence in
> its correctness.
Has any progress been made on the performance farm? The problem with
suggestions like this (which seem pretty reasonable to me) is that
we've got no way of quantifying the downside. I think this is one
example of a class of plans that are high risk. Another one off the
top of my head is nestloop joins based on assumed selectivity of
multiple stacked quals. About 90% of the time, my reflective
workaround to these types of problems is to 'disable_nestloop' which
works around 90% of the time and the result are solved with monkeying
around with 'OFFSET 0' etc. In the past, a GUC controlling planner
risk has been much discussed -- maybe it's still worth considering?
merlin
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-22 23:56 Josh Berkus <josh@agliodbs.com>
parent: Merlin Moncure <mmoncure@gmail.com>
0 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-09-22 23:56 UTC (permalink / raw)
To: Merlin Moncure <mmoncure@gmail.com>; +Cc: Greg Stark <stark@mit.edu>; pgsql-performance
On 09/22/2014 06:55 AM, Merlin Moncure wrote:
> Has any progress been made on the performance farm? The problem with
> suggestions like this (which seem pretty reasonable to me) is that
> we've got no way of quantifying the downside.
Yeah, that's certainly an issue. The problem is that we'd need a
benchmark which actually created complex query plans. I believe that
Mark Wong is working on TPCH-based benchmarks, so maybe we'll get that.
> I think this is one
> example of a class of plans that are high risk. Another one off the
> top of my head is nestloop joins based on assumed selectivity of
> multiple stacked quals.
Yeah, that's another good example.
> About 90% of the time, my reflective
> workaround to these types of problems is to 'disable_nestloop' which
> works around 90% of the time and the result are solved with monkeying
> around with 'OFFSET 0' etc. In the past, a GUC controlling planner
> risk has been much discussed -- maybe it's still worth considering?
We've hashed that out a bit, but frankly I think it's much more
profitable to pursue fixing the actual problem than providing a
workaround like "risk", such as:
a) fixing n_distinct estimation
b) estimating stacked quals using better math (i.e. not assuming total
randomness)
c) developing some kind of correlation stats
Otherwise we would be just providing users with another knob there's no
rational way to set.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-26 08:06 Simon Riggs <simon@2ndquadrant.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 3 replies; 60+ messages in thread
From: Simon Riggs @ 2014-09-26 08:06 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 23 September 2014 00:56, Josh Berkus <josh@agliodbs.com> wrote:
> We've hashed that out a bit, but frankly I think it's much more
> profitable to pursue fixing the actual problem than providing a
> workaround like "risk", such as:
>
> a) fixing n_distinct estimation
> b) estimating stacked quals using better math (i.e. not assuming total
> randomness)
> c) developing some kind of correlation stats
>
> Otherwise we would be just providing users with another knob there's no
> rational way to set.
I believe this is a serious issue for PostgreSQL users and one that
needs to be addressed.
n_distinct can be fixed manually, so that is less of an issue.
The problem, as I see it, is different. We assume that if there are
100 distinct values and you use LIMIT 1 that you would only need to
scan 1% of rows. We assume that the data is arranged in the table in a
very homogenous layout. When data is not, and it seldom is, we get
problems.
Simply put, assuming that LIMIT will reduce the size of all scans is
just way wrong. I've seen many plans where increasing the LIMIT
dramatically improves the plan.
If we can at least agree it is a problem, we can try to move forwards.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-29 15:00 Merlin Moncure <mmoncure@gmail.com>
parent: Simon Riggs <simon@2ndquadrant.com>
2 siblings, 2 replies; 60+ messages in thread
From: Merlin Moncure @ 2014-09-29 15:00 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Fri, Sep 26, 2014 at 3:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> The problem, as I see it, is different. We assume that if there are
> 100 distinct values and you use LIMIT 1 that you would only need to
> scan 1% of rows. We assume that the data is arranged in the table in a
> very homogenous layout. When data is not, and it seldom is, we get
> problems.
Hm, good point -- 'data proximity'. At least in theory, can't this be
measured and quantified? For example, given a number of distinct
values, you could estimate the % of pages read (or maybe non
sequential seeks relative to the number of pages) you'd need to read
all instances of a particular value in the average (or perhaps the
worst) case. One way of trying to calculate that would be to look at
proximity of values in sampled pages (and maybe a penalty assigned for
high update activity relative to table size). Data proximity would
then become a cost coefficient to the benefits of LIMIT.
merlin
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-29 20:53 Simon Riggs <simon@2ndquadrant.com>
parent: Merlin Moncure <mmoncure@gmail.com>
1 sibling, 2 replies; 60+ messages in thread
From: Simon Riggs @ 2014-09-29 20:53 UTC (permalink / raw)
To: Merlin Moncure <mmoncure@gmail.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 29 September 2014 16:00, Merlin Moncure <mmoncure@gmail.com> wrote:
> On Fri, Sep 26, 2014 at 3:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> The problem, as I see it, is different. We assume that if there are
>> 100 distinct values and you use LIMIT 1 that you would only need to
>> scan 1% of rows. We assume that the data is arranged in the table in a
>> very homogenous layout. When data is not, and it seldom is, we get
>> problems.
>
> Hm, good point -- 'data proximity'. At least in theory, can't this be
> measured and quantified? For example, given a number of distinct
> values, you could estimate the % of pages read (or maybe non
> sequential seeks relative to the number of pages) you'd need to read
> all instances of a particular value in the average (or perhaps the
> worst) case. One way of trying to calculate that would be to look at
> proximity of values in sampled pages (and maybe a penalty assigned for
> high update activity relative to table size). Data proximity would
> then become a cost coefficient to the benefits of LIMIT.
The necessary first step to this is to realise that we can't simply
apply the LIMIT as a reduction in query cost, in all cases.
The way I'm seeing it, you can't assume the LIMIT will apply to any
IndexScan that doesn't have an index condition. If it has just a
filter, or nothing at all, just an ordering then it could easily scan
the whole index if the stats are wrong.
So plans like this could be wrong, by assuming the scan will end
earlier because of the LIMIT than it actually will.
Limit
IndexScan (no index cond)
Limit
NestJoin
IndexScan (no index cond)
SomeScan
Limit
NestJoin
NestJoin
IndexScan (no index cond)
SomeScan
SomeScan
and deeper...
I'm looking for a way to identify and exclude such plans, assuming
that this captures at least some of the problem plans.
Comments? Test Cases?
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-29 21:54 Josh Berkus <josh@agliodbs.com>
parent: Simon Riggs <simon@2ndquadrant.com>
2 siblings, 2 replies; 60+ messages in thread
From: Josh Berkus @ 2014-09-29 21:54 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 09/26/2014 01:06 AM, Simon Riggs wrote:
> On 23 September 2014 00:56, Josh Berkus <josh@agliodbs.com> wrote:
>
>> We've hashed that out a bit, but frankly I think it's much more
>> profitable to pursue fixing the actual problem than providing a
>> workaround like "risk", such as:
>>
>> a) fixing n_distinct estimation
>> b) estimating stacked quals using better math (i.e. not assuming total
>> randomness)
>> c) developing some kind of correlation stats
>>
>> Otherwise we would be just providing users with another knob there's no
>> rational way to set.
>
> I believe this is a serious issue for PostgreSQL users and one that
> needs to be addressed.
>
> n_distinct can be fixed manually, so that is less of an issue.
It's an issue for the 99.8% of our users who don't know what n_distinct
is, let alone how to calculate it. Also, changing it requires an
exclusive lock on the table. Of course, you and I have been over this
issue before.
One thing I'm wondering is why our estimator is creates n_distinct as a
% so seldom. Really, any time n_distinct is over 10K we should be
estimating a % instead. Now, estimating that % has its own issues, but
it does seem like a peculiar quirk of our stats model.
Anyway, in the particular case I posted fixing n_distinct to realistic
numbers (%) fixed the query plan.
>
> The problem, as I see it, is different. We assume that if there are
> 100 distinct values and you use LIMIT 1 that you would only need to
> scan 1% of rows. We assume that the data is arranged in the table in a
> very homogenous layout. When data is not, and it seldom is, we get
> problems.
>
> Simply put, assuming that LIMIT will reduce the size of all scans is
> just way wrong. I've seen many plans where increasing the LIMIT
> dramatically improves the plan.
>
> If we can at least agree it is a problem, we can try to move forwards.
That is certainly another problem. Does correlation stat figure in the
LIMIT calculation at all, currently? That's what correlation stat is
for, no?
Also, to be fair, physical correlation of rows can also lead to
abort-early plans being extra fast, if everything we want is towards the
beginning of the index. Which means we'd need working multi-column
correlation, which is a known hard problem.
For example, consider the query:
SELECT id, updated_on FROM audit_log
WHERE updated_on < '2010-01-01'
ORDER BY id LIMIT 10;
In an append-only table, that query is liable to be very fast with an
abort-early plan scanning on an ID index (AEP from now on), since the
oldest rows are likely to correspond with the smallest IDs. But then
the user does this:
SELECT id, updated_on FROM audit_log
WHERE updated_on < '2010-01-01'
ORDER BY id DESC LIMIT 10;
... and a completely different plan is called for, because using an AEP
will result in reverse scanning most of the index. However, I'm not
sure the planner knows the difference, since it's only comparing the
estimated selectivity of (updated_on < '2010-01-01') and seeing that
it's 20% of rows. I bet you'd get an AEP in the 2nd case too.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-29 23:00 Tom Lane <tgl@sss.pgh.pa.us>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 2 replies; 60+ messages in thread
From: Tom Lane @ 2014-09-29 23:00 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
Simon Riggs <simon@2ndquadrant.com> writes:
> The way I'm seeing it, you can't assume the LIMIT will apply to any
> IndexScan that doesn't have an index condition. If it has just a
> filter, or nothing at all, just an ordering then it could easily scan
> the whole index if the stats are wrong.
That statement applies with equal force to *any* plan with a LIMIT;
it's not just index scans.
The real question is to what extent are the tuples satisfying the extra
filter condition randomly distributed with respect to the index order
(or physical order, if it's a seqscan). The existing cost estimation
code effectively assumes that they're perfectly uniformly distributed;
which is a good average-case assumption but can be horribly wrong in
the worst case.
If we could settle on some other model for the probable distribution
of the matching tuples, we could adjust the cost estimates for LIMIT
accordingly. I have not enough statistics background to know what a
realistic alternative would be.
Another possibility is to still assume a uniform distribution but estimate
for, say, a 90% probability instead of 50% probability that we'll find
enough tuples after scanning X amount of the table. Again, I'm not too
sure what that translates to in terms of the actual math, but it sounds
like something a statistics person could do in their sleep.
I do not think we should estimate for the worst case though. If we do,
we'll hear cries of anguish from a lot of people, including many of the
same ones complaining now, because the planner stopped picking fast-start
plans even for cases where they are orders of magnitude faster than the
alternatives.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 02:12 Gavin Flower <GavinFlower@archidevsys.co.nz>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 60+ messages in thread
From: Gavin Flower @ 2014-09-30 02:12 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Simon Riggs <simon@2ndquadrant.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 30/09/14 12:00, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
>> The way I'm seeing it, you can't assume the LIMIT will apply to any
>> IndexScan that doesn't have an index condition. If it has just a
>> filter, or nothing at all, just an ordering then it could easily scan
>> the whole index if the stats are wrong.
> That statement applies with equal force to *any* plan with a LIMIT;
> it's not just index scans.
>
> The real question is to what extent are the tuples satisfying the extra
> filter condition randomly distributed with respect to the index order
> (or physical order, if it's a seqscan). The existing cost estimation
> code effectively assumes that they're perfectly uniformly distributed;
> which is a good average-case assumption but can be horribly wrong in
> the worst case.
>
> If we could settle on some other model for the probable distribution
> of the matching tuples, we could adjust the cost estimates for LIMIT
> accordingly. I have not enough statistics background to know what a
> realistic alternative would be.
>
> Another possibility is to still assume a uniform distribution but estimate
> for, say, a 90% probability instead of 50% probability that we'll find
> enough tuples after scanning X amount of the table. Again, I'm not too
> sure what that translates to in terms of the actual math, but it sounds
> like something a statistics person could do in their sleep.
>
> I do not think we should estimate for the worst case though. If we do,
> we'll hear cries of anguish from a lot of people, including many of the
> same ones complaining now, because the planner stopped picking fast-start
> plans even for cases where they are orders of magnitude faster than the
> alternatives.
>
> regards, tom lane
>
If you analyzed the tables in most production databases, you would find that they are almost invariably not uniformly distributed.
Most likely they will be clumped, and if you plotted the frequency of values of a given column in a given range against the number of blocks, you are likely to see one or more distinct peaks. If the table has been CLUSTERed on that column, then they will very likely to be in one clump spanning contiguous blocks.
I suspect that there are two distinct populations: one relating to values present before the last VACUUM, and ones added since.
There are so many factors to consider, pattern of CRUD operations, range of values in query, ... that probably prevent using very sophisticated approaches, but I would be happy to be proved wrong!
Though I am fairly confident that if the distribution is not known in advance for a given table, then the percentage required to process to satisfy the limit is likely to be a lot larger than a uniform distribution would suggest.
Would it be feasible to get a competent statistician to advise what data to collect, and to analyze it? Maybe it is possible to get a better estimate on how much of a table needs to be scanned, based on some fairly simple statistics. But unless research is done, it is probably impossible to determine what statistics might be useful, and how effective a better estimate could be.
I have a nasty feeling that assuming a uniform distribution, may still
end up being the best we can do - but I maybe being unduly pessimistic!.
Cheers,
Gavin
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 03:11 Greg Stark <stark@mit.edu>
parent: Simon Riggs <simon@2ndquadrant.com>
2 siblings, 0 replies; 60+ messages in thread
From: Greg Stark @ 2014-09-30 03:11 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Josh Berkus <josh@agliodbs.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Fri, Sep 26, 2014 at 9:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> If we can at least agree it is a problem, we can try to move forwards.
Well that's a good question. I don't think we do and I think the
reason why is because we haven't actually pinned down exactly what is
the problem.
The real problem here is that the ideal index for the query isn't there
and Postgres is trying to choose between two inappropriatedoes not
exist indexes where that decision is very very hard for it to make. If
it guesses
wrong in *either* direction it'll go very poorly. We can try to
improve the frequency of getting the right decision but it'll never be
100% and even if it was it'll still not perform as well as the right
index would have.
I have seen plenty of applications where the slowdown was in the
reverse direction --
where a query like "find the last login for the current user" was
planned just as Josh is asking for by retrieving all the records for
the user and sorting by login time and it caused large problems in
production when some users had a disproportionately large number of
records.
The real solution for users is to create the compound index on both columns (or
partial index in some cases). Trying to make do with an ordered scan
or a index scan and sort are both going to cause problems in real
world usage.
In fact I think the real story here is that Postgres is doing a
surprisingly good job at making do without the right index and that's
causing users to get surprisingly far before they run into problems.
That may not be the best thing for users in the long run but that's a
problem that should be solved by better development tools to help
users identify scalability problems early.
--
greg
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 07:09 Simon Riggs <simon@2ndquadrant.com>
parent: Josh Berkus <josh@agliodbs.com>
1 sibling, 0 replies; 60+ messages in thread
From: Simon Riggs @ 2014-09-30 07:09 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 29 September 2014 22:54, Josh Berkus <josh@agliodbs.com> wrote:
> On 09/26/2014 01:06 AM, Simon Riggs wrote:
>> On 23 September 2014 00:56, Josh Berkus <josh@agliodbs.com> wrote:
>>
>>> We've hashed that out a bit, but frankly I think it's much more
>>> profitable to pursue fixing the actual problem than providing a
>>> workaround like "risk", such as:
>>>
>>> a) fixing n_distinct estimation
>>> b) estimating stacked quals using better math (i.e. not assuming total
>>> randomness)
>>> c) developing some kind of correlation stats
>>>
>>> Otherwise we would be just providing users with another knob there's no
>>> rational way to set.
>>
>> I believe this is a serious issue for PostgreSQL users and one that
>> needs to be addressed.
>>
>> n_distinct can be fixed manually, so that is less of an issue.
>
> It's an issue for the 99.8% of our users who don't know what n_distinct
> is, let alone how to calculate it. Also, changing it requires an
> exclusive lock on the table. Of course, you and I have been over this
> issue before.
In 9.4 you'll be able to set n_distinct using only a Share Update
Exclusive lock.
So that's no longer a problem.
The quality of the n_distinct itself is an issue, but with no current
solution, but then that is why you can set it manually,
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 09:25 Simon Riggs <simon@2ndquadrant.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 2 replies; 60+ messages in thread
From: Simon Riggs @ 2014-09-30 09:25 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 30 September 2014 00:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
>> The way I'm seeing it, you can't assume the LIMIT will apply to any
>> IndexScan that doesn't have an index condition. If it has just a
>> filter, or nothing at all, just an ordering then it could easily scan
>> the whole index if the stats are wrong.
>
> That statement applies with equal force to *any* plan with a LIMIT;
> it's not just index scans.
Agreed
> The real question is to what extent are the tuples satisfying the extra
> filter condition randomly distributed with respect to the index order
> (or physical order, if it's a seqscan).
Agreed
> The existing cost estimation
> code effectively assumes that they're perfectly uniformly distributed;
> which is a good average-case assumption but can be horribly wrong in
> the worst case.
Agreed. This is the main observation from which we can work.
> If we could settle on some other model for the probable distribution
> of the matching tuples, we could adjust the cost estimates for LIMIT
> accordingly. I have not enough statistics background to know what a
> realistic alternative would be.
I'm not sure that the correlation alone is sufficient to be able to do
that. We'd need to estimate where the values looked for are likely to
be wrt other values, then increase estimate accordingly. That sounds
like a lot of pushups grovelling through quals and comparing against
stats. So my thinking is actually to rule that out, unless you've some
ideas for how to do that?
> Another possibility is to still assume a uniform distribution but estimate
> for, say, a 90% probability instead of 50% probability that we'll find
> enough tuples after scanning X amount of the table. Again, I'm not too
> sure what that translates to in terms of the actual math, but it sounds
> like something a statistics person could do in their sleep.
>
> I do not think we should estimate for the worst case though. If we do,
> we'll hear cries of anguish from a lot of people, including many of the
> same ones complaining now, because the planner stopped picking fast-start
> plans even for cases where they are orders of magnitude faster than the
> alternatives.
Fast start plans still make sense when performing an IndexScan with no
filter conditions. Those types of plan should not be changed from
current costing - they are accurate, good and very important because
of their frequency in real workloads.
What I think we are seeing is Ordered plans being selected too often
in preference to Sorted plans when we make selectivity or stats
errors. As well as data distributions that aren't correctly described
by the statistics causing much longer execution times.
Here are some plan selection strategies
* Cost based - attempt to exactly calculate the cost based upon
existing stats - increase the complexity of cost calc to cover other
aspects. Even if we do that, these may not be that helpful in covering
the cases where the stats turn out to be wrong.
* Risk based - A risk adjusted viewpoint would be that we should treat
the cost as mid-way between the best and the worst. The worst is
clearly scanning (100% - N) of the tuples, the best is just N tuples.
So we should be costing scans with excess filter conditions as a (100%
Scan)/2, no matter the conditions, based purely upon risk.
* Simplified heuristic - deselect ordered plans when they are driven
from scans without quals or indexscans with filters, since the risk
adjusted cost is likely to be higher than the sorted cost. Inspecting
the plan tree for this could be quite costly, so would only be done
when the total cost is $high, prior to it being adjusted by LIMIT.
In terms of practical steps... I suggest the following:
* Implement enable_orderedscan = on (default) | off. A switch to allow
plans to de-select ordered plans, so we can more easily see the
effects of such plans in the wild.
* Code heuristic approach - I can see where to add my heuristic in the
grouping planner. So we just need to do a left? deep search of the
plan tree looking for scans of the appropriate type and bail out if we
find one.
Thoughts?
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 11:34 Graeme B. Bell <grb@skogoglandskap.no>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 2 replies; 60+ messages in thread
From: Graeme B. Bell @ 2014-09-30 11:34 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
>> The existing cost estimation
>> code effectively assumes that they're perfectly uniformly distributed;
>> which is a good average-case assumption but can be horribly wrong in
>> the worst case.
Sorry, just an outsider jumping in with a quick comment.
Every year or two the core count goes up. Can/should/does postgres ever attempt two strategies in parallel, in cases where strategy A is generally good but strategy B prevents bad worst case behaviour? Kind of like a Schrödinger's Cat approach to scheduling. What problems would it raise?
Graeme.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 15:59 Claudio Freire <klaussfreire@gmail.com>
parent: Graeme B. Bell <grb@skogoglandskap.no>
1 sibling, 0 replies; 60+ messages in thread
From: Claudio Freire @ 2014-09-30 15:59 UTC (permalink / raw)
To: Graeme B. Bell <grb@skogoglandskap.no>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Tom Lane <tgl@sss.pgh.pa.us>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Tue, Sep 30, 2014 at 8:34 AM, Graeme B. Bell <grb@skogoglandskap.no> wrote:
>
>>> The existing cost estimation
>>> code effectively assumes that they're perfectly uniformly distributed;
>>> which is a good average-case assumption but can be horribly wrong in
>>> the worst case.
>
>
> Sorry, just an outsider jumping in with a quick comment.
>
> Every year or two the core count goes up. Can/should/does postgres ever attempt two strategies in parallel, in cases where strategy A is generally good but strategy B prevents bad worst case behaviour? Kind of like a Schrödinger's Cat approach to scheduling.
> What problems would it raise?
Interleaved I/O, that would kill performance for both plans if it
happens on rotating media.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 16:32 Tom Lane <tgl@sss.pgh.pa.us>
parent: Graeme B. Bell <grb@skogoglandskap.no>
1 sibling, 1 reply; 60+ messages in thread
From: Tom Lane @ 2014-09-30 16:32 UTC (permalink / raw)
To: Graeme B. Bell <grb@skogoglandskap.no>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
"Graeme B. Bell" <grb@skogoglandskap.no> writes:
> Every year or two the core count goes up. Can/should/does postgres ever attempt two strategies in parallel, in cases where strategy A is generally good but strategy B prevents bad worst case behaviour? Kind of like a Schrödinger's Cat approach to scheduling. What problems would it raise?
You can't run two plans and have them both returning rows to the client,
or performing inserts/updates/deletes as the case may be.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 16:54 Jeff Janes <jeff.janes@gmail.com>
parent: Gavin Flower <GavinFlower@archidevsys.co.nz>
0 siblings, 2 replies; 60+ messages in thread
From: Jeff Janes @ 2014-09-30 16:54 UTC (permalink / raw)
To: Gavin Flower <GavinFlower@archidevsys.co.nz>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Mon, Sep 29, 2014 at 7:12 PM, Gavin Flower <GavinFlower@archidevsys.co.nz
> wrote:
>
> Would it be feasible to get a competent statistician to advise what data to collect, and to analyze it? Maybe it is possible to get a better estimate on how much of a table needs to be scanned, based on some fairly simple statistics. But unless research is done, it is probably impossible to determine what statistics might be useful, and how effective a better estimate could be.
>
> I have a nasty feeling that assuming a uniform distribution, may still
> end up being the best we can do - but I maybe being unduly pessimistic!.
>
As a semi-competent statistician, my gut feeling is that our best bet would
be not to rely on the competence of statisticians for too much, and instead
try to give the executor the ability to abandon a fruitless path and pick a
different plan instead. Of course this option is foreclosed once a tuple is
returned to the client (unless the ctid is also cached, so we can make sure
not to send it again on the new plan).
I think that the exponential explosion of possibilities is going to be too
great to analyze in any rigorous way.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 17:07 Graeme B. Bell <grb@skogoglandskap.no>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 60+ messages in thread
From: Graeme B. Bell @ 2014-09-30 17:07 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
Thanks for your replies everyone.
> You can't run two plans and have them both returning rows to the client,
That wasn't what I had in mind.
I can envisage cases where the worst case behaviour of one plan results in zero rows by the time the alternative plan has generated the complete result, never mind a single row (e.g. anything with LIMIT in it could fall into that category). Maybe it's enough to alleviate the problems caused by planning heuristics known to have bad worst-case performance that is hard to avoid with a single-threaded approach?
Providing we're not modifying data in the query, and providing we kill the 'loser' thread when either (the first result / all results) come in, maybe there's value in letting them race and picking the best plan retrospectively.
I guess it's going into another topic, but I wonder what % of DBs/queries look like this:
- little or no I/O thrash (e.g. tuples mostly in memory already or DB configured to have a relatively low 'random_page_cost')
- ordered results, or, the whole result set is being produced at once.
- SELECTs only
In my own work (national scale GIS) this is what most of our queries & query environments look like.
Graeme
On 30 Sep 2014, at 18:32, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Graeme B. Bell" <grb@skogoglandskap.no> writes:
>> Every year or two the core count goes up. Can/should/does postgres ever attempt two strategies in parallel, in cases where strategy A is generally good but strategy B prevents bad worst case behaviour? Kind of like a Schrödinger's Cat approach to scheduling. What problems would it raise?
>
> You can't run two plans and have them both returning rows to the client,
> or performing inserts/updates/deletes as the case may be.
>
> regards, tom lane
>
>
> --
> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 17:28 Jeff Janes <jeff.janes@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
1 sibling, 1 reply; 60+ messages in thread
From: Jeff Janes @ 2014-09-30 17:28 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Mon, Sep 29, 2014 at 2:54 PM, Josh Berkus <josh@agliodbs.com> wrote:
> On 09/26/2014 01:06 AM, Simon Riggs wrote:
> > On 23 September 2014 00:56, Josh Berkus <josh@agliodbs.com> wrote:
> >
> >> We've hashed that out a bit, but frankly I think it's much more
> >> profitable to pursue fixing the actual problem than providing a
> >> workaround like "risk", such as:
> >>
> >> a) fixing n_distinct estimation
> >> b) estimating stacked quals using better math (i.e. not assuming total
> >> randomness)
> >> c) developing some kind of correlation stats
> >>
> >> Otherwise we would be just providing users with another knob there's no
> >> rational way to set.
> >
> > I believe this is a serious issue for PostgreSQL users and one that
> > needs to be addressed.
> >
> > n_distinct can be fixed manually, so that is less of an issue.
>
> It's an issue for the 99.8% of our users who don't know what n_distinct
> is, let alone how to calculate it. Also, changing it requires an
> exclusive lock on the table. Of course, you and I have been over this
> issue before.
>
If 99.6% of our users don't have a problem with n_distinct in their system,
that would mean that only 50% of the people with the problem don't know how
to solve it. And those people can usually get excellent free help on the
internet.
But if the problem not with n_distinct, but rather with most_common_freqs
(which I encounter more often than problems with n_distinct), all I can do
is shrug and say "yeah I know about that problem. Either crank up
statistics target as high as it will go, or it sucks to be you."
>
> One thing I'm wondering is why our estimator is creates n_distinct as a
> % so seldom. Really, any time n_distinct is over 10K we should be
> estimating a % instead. Now, estimating that % has its own issues, but
> it does seem like a peculiar quirk of our stats model.
>
> Anyway, in the particular case I posted fixing n_distinct to realistic
> numbers (%) fixed the query plan.
>
But wouldn't fixing the absolute number also have fixed the plan? If you
are going to set a number manually and then nail it in place so that
analyze stops changing it, then I can certainly see how the fractional
method is desirable. But if the goal is not to do that but have the
correct value estimated in the first place, I don't really see much benefit
from converting the estimate into a fraction and then back again.
> >
> > The problem, as I see it, is different. We assume that if there are
> > 100 distinct values and you use LIMIT 1 that you would only need to
> > scan 1% of rows. We assume that the data is arranged in the table in a
> > very homogenous layout. When data is not, and it seldom is, we get
> > problems.
> >
> > Simply put, assuming that LIMIT will reduce the size of all scans is
> > just way wrong. I've seen many plans where increasing the LIMIT
> > dramatically improves the plan.
> >
> > If we can at least agree it is a problem, we can try to move forwards.
>
I don't think anyone doubts there is a problem (many more than one of
them), there is just disagreement about the priority and what can be done
about it.
>
> That is certainly another problem. Does correlation stat figure in the
> LIMIT calculation at all, currently? That's what correlation stat is
> for, no?
>
I don't think correlation is up to the task as a complete solution,
although it might help a little. There is no way a simple correlation can
encode that John retired 15 years ago and hasn't logged on since, while
Johannes was hired yesterday and never logged on before then.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 21:11 Gavin Flower <GavinFlower@archidevsys.co.nz>
parent: Jeff Janes <jeff.janes@gmail.com>
1 sibling, 0 replies; 60+ messages in thread
From: Gavin Flower @ 2014-09-30 21:11 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 01/10/14 05:54, Jeff Janes wrote:
> On Mon, Sep 29, 2014 at 7:12 PM, Gavin Flower
> <GavinFlower@archidevsys.co.nz <mailto:GavinFlower@archidevsys.co.nz>>
> wrote:
>
>
> Would it be feasible to get a competent statistician to advise what data to collect, and to analyze it? Maybe it is possible to get a better estimate on how much of a table needs to be scanned, based on some fairly simple statistics. But unless research is done, it is probably impossible to determine what statistics might be useful, and how effective a better estimate could be.
>
> I have a nasty feeling that assuming a uniform distribution, may
> still end up being the best we can do - but I maybe being unduly
> pessimistic!.
>
>
> As a semi-competent statistician, my gut feeling is that our best bet
> would be not to rely on the competence of statisticians for too much,
> and instead try to give the executor the ability to abandon a
> fruitless path and pick a different plan instead. Of course this
> option is foreclosed once a tuple is returned to the client (unless
> the ctid is also cached, so we can make sure not to send it again on
> the new plan).
>
> I think that the exponential explosion of possibilities is going to be
> too great to analyze in any rigorous way.
>
> Cheers,
>
> Jeff
Many moons ago, I passed several 300 level statistics papers.
I looked at this problem and found it was too hard to even properly
characterise the problem (looks 'simple' - if you don't look too
closely), and ended up feeling it was definitely 'way above my pay
grade'! :-)
It might be possible to tackle it more pragmatically, instead of trying
to be all analytic and rigorously list all the possible influences, have
a look at queries of this nature that are taking far too long. Then get
a feel for combinations of issues involved and how they contribute. If
you have enough data, you might be able to use something like Principle
Component Analysis (I was fortunate to meet a scientist who had got
heavily into this area of statistics). Such an approach might yield
valuable insights, even if the problem is not fully characterised, let
alone 'solved'.
Cheers,
Gavin
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 22:14 Merlin Moncure <mmoncure@gmail.com>
parent: Jeff Janes <jeff.janes@gmail.com>
1 sibling, 0 replies; 60+ messages in thread
From: Merlin Moncure @ 2014-09-30 22:14 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Gavin Flower <GavinFlower@archidevsys.co.nz>; Tom Lane <tgl@sss.pgh.pa.us>; Simon Riggs <simon@2ndquadrant.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Tue, Sep 30, 2014 at 11:54 AM, Jeff Janes <jeff.janes@gmail.com> wrote:
> On Mon, Sep 29, 2014 at 7:12 PM, Gavin Flower
> <GavinFlower@archidevsys.co.nz> wrote:
>>
>>
>> Would it be feasible to get a competent statistician to advise what data
>> to collect, and to analyze it? Maybe it is possible to get a better
>> estimate on how much of a table needs to be scanned, based on some fairly
>> simple statistics. But unless research is done, it is probably impossible
>> to determine what statistics might be useful, and how effective a better
>> estimate could be.
>>
>> I have a nasty feeling that assuming a uniform distribution, may still end
>> up being the best we can do - but I maybe being unduly pessimistic!.
>
> As a semi-competent statistician, my gut feeling is that our best bet would
> be not to rely on the competence of statisticians for too much, and instead
> try to give the executor the ability to abandon a fruitless path and pick a
> different plan instead. Of course this option is foreclosed once a tuple is
> returned to the client (unless the ctid is also cached, so we can make sure
> not to send it again on the new plan).
>
> I think that the exponential explosion of possibilities is going to be too
> great to analyze in any rigorous way.
Call it the 'Parking in Manhattan' strategy -- you know when it's time
to pull forward when you've smacked into the car behind you.
Kidding aside, this might be the path forward since it's A. more
general and can catch all kinds of problem cases that our statistics
system won't/can't catch and B. At least in my case it seems like more
complicated plans tend to not return much data until the inner most
risky parts have been involved. Even if that wasn't the case,
withholding data to the client until a user configurable time
threshold had been passed (giving the planner time to back up if
necessary) would be a reasonable user facing tradeoff via GUC:
'max_planner_retry_time'.
merlin
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-09-30 23:01 Simon Riggs <simon@2ndquadrant.com>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-09-30 23:01 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Josh Berkus <josh@agliodbs.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 30 September 2014 18:28, Jeff Janes <jeff.janes@gmail.com> wrote:
>> Anyway, in the particular case I posted fixing n_distinct to realistic
>> numbers (%) fixed the query plan.
>
>
> But wouldn't fixing the absolute number also have fixed the plan?
There are two causes of this issue.
1. Poor estimates of n_distinct. Fixable by user.
2. Poor assumption of homogeneous distribution. No way for user to
fix. Insufficient stats detail to be able to solve in current planner.
I see (2) as the main source of issues, since as we observe, (1) is fixable.
An example is a social media application where the business query is
"Display the last 10 posts". If the user is a frequent, recent user
then the query could come back very quickly, so a reverse scan on
post_id would work great. If the user hasn't logged on for ages, then
that plan needs to scan lots and lots of data to get to find 10 posts.
That gives the problem that only certain users experience poor
performance - even the data isn't consistent in its distribution, so
stats wouldn't help much, even if we could capture the profile of the
"typical user".
>> > The problem, as I see it, is different. We assume that if there are
>> > 100 distinct values and you use LIMIT 1 that you would only need to
>> > scan 1% of rows. We assume that the data is arranged in the table in a
>> > very homogenous layout. When data is not, and it seldom is, we get
>> > problems.
>> >
>> > Simply put, assuming that LIMIT will reduce the size of all scans is
>> > just way wrong. I've seen many plans where increasing the LIMIT
>> > dramatically improves the plan.
>> >
>> > If we can at least agree it is a problem, we can try to move forwards.
>
>
> I don't think anyone doubts there is a problem (many more than one of them),
> there is just disagreement about the priority and what can be done about it.
>> That is certainly another problem. Does correlation stat figure in the
>> LIMIT calculation at all, currently? That's what correlation stat is
>> for, no?
>
>
> I don't think correlation is up to the task as a complete solution, although
> it might help a little. There is no way a simple correlation can encode
> that John retired 15 years ago and hasn't logged on since, while Johannes
> was hired yesterday and never logged on before then.
Ah, OK, essentially the same example.
Which is why I ruled out correlation stats based approaches and
suggested a risk-weighted cost approach.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-01 18:56 Josh Berkus <josh@agliodbs.com>
parent: Simon Riggs <simon@2ndquadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-10-01 18:56 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; Jeff Janes <jeff.janes@gmail.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 09/30/2014 04:01 PM, Simon Riggs wrote:
> On 30 September 2014 18:28, Jeff Janes <jeff.janes@gmail.com> wrote:
>
>>> Anyway, in the particular case I posted fixing n_distinct to realistic
>>> numbers (%) fixed the query plan.
>>
>>
>> But wouldn't fixing the absolute number also have fixed the plan?
>
> There are two causes of this issue.
>
> 1. Poor estimates of n_distinct. Fixable by user.
>
> 2. Poor assumption of homogeneous distribution. No way for user to
> fix. Insufficient stats detail to be able to solve in current planner.
>
> I see (2) as the main source of issues, since as we observe, (1) is fixable.
I disagree that (1) is not worth fixing just because we've provided
users with an API to override the stats. It would unquestionably be
better for us to have a better n_distinct estimate in the first place.
Further, this is an easier problem to solve, and fixing n_distinct
estimates would fix a large minority of currently pathological queries.
It's like saying "hey, we don't need to fix the leak in your radiator,
we've given you a funnel in the dashboard you can pour water into."
I do agree that (2) is worth fixing *as well*. In a first
approximation, one possibility (as Tom suggests) would be to come up
with a mathematical model for a selectivity estimate which was somewhere
*between* homogenous distribution and the worst case. While that
wouldn't solve a lot of cases, it would be a start towards having a
better model.
>> I don't think correlation is up to the task as a complete solution, although
>> it might help a little. There is no way a simple correlation can encode
>> that John retired 15 years ago and hasn't logged on since, while Johannes
>> was hired yesterday and never logged on before then.
>
> Ah, OK, essentially the same example.
>
> Which is why I ruled out correlation stats based approaches and
> suggested a risk-weighted cost approach.
By "risk-weighted" you mean just adjusting cost estimates based on what
the worst case cost looks like, correct? That seemed to be your
proposal from an earlier post. If so, we're in violent agreement here.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-02 08:19 Simon Riggs <simon@2ndquadrant.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-10-02 08:19 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 1 October 2014 19:56, Josh Berkus <josh@agliodbs.com> wrote:
> On 09/30/2014 04:01 PM, Simon Riggs wrote:
>> On 30 September 2014 18:28, Jeff Janes <jeff.janes@gmail.com> wrote:
>>
>>>> Anyway, in the particular case I posted fixing n_distinct to realistic
>>>> numbers (%) fixed the query plan.
>>>
>>>
>>> But wouldn't fixing the absolute number also have fixed the plan?
>>
>> There are two causes of this issue.
>>
>> 1. Poor estimates of n_distinct. Fixable by user.
>>
>> 2. Poor assumption of homogeneous distribution. No way for user to
>> fix. Insufficient stats detail to be able to solve in current planner.
>>
>> I see (2) as the main source of issues, since as we observe, (1) is fixable.
>
> I disagree that (1) is not worth fixing just because we've provided
> users with an API to override the stats. It would unquestionably be
> better for us to have a better n_distinct estimate in the first place.
> Further, this is an easier problem to solve, and fixing n_distinct
> estimates would fix a large minority of currently pathological queries.
> It's like saying "hey, we don't need to fix the leak in your radiator,
> we've given you a funnel in the dashboard you can pour water into."
Having read papers on it, I believe the problem is intractable. Coding
is not the issue. To anyone: please prove me wrong, in detail, with
references so it can be coded.
> I do agree that (2) is worth fixing *as well*. In a first
> approximation, one possibility (as Tom suggests) would be to come up
> with a mathematical model for a selectivity estimate which was somewhere
> *between* homogenous distribution and the worst case. While that
> wouldn't solve a lot of cases, it would be a start towards having a
> better model.
This may have a reasonable solution, but I don't know it. A more
accurate mathematical model will still avoid the main problem: it is a
guess, not certain knowledge and the risk will still remain.
>>> I don't think correlation is up to the task as a complete solution, although
>>> it might help a little. There is no way a simple correlation can encode
>>> that John retired 15 years ago and hasn't logged on since, while Johannes
>>> was hired yesterday and never logged on before then.
>>
>> Ah, OK, essentially the same example.
>>
>> Which is why I ruled out correlation stats based approaches and
>> suggested a risk-weighted cost approach.
>
> By "risk-weighted" you mean just adjusting cost estimates based on what
> the worst case cost looks like, correct? That seemed to be your
> proposal from an earlier post. If so, we're in violent agreement here.
I proposed a clear path for this earlier in the thread and received no
comments as yet. Please look at that.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-02 09:30 Peter Geoghegan <peter.geoghegan86@gmail.com>
parent: Simon Riggs <simon@2ndquadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Peter Geoghegan @ 2014-10-02 09:30 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Josh Berkus <josh@agliodbs.com>; Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> I disagree that (1) is not worth fixing just because we've provided
>> users with an API to override the stats. It would unquestionably be
>> better for us to have a better n_distinct estimate in the first place.
>> Further, this is an easier problem to solve, and fixing n_distinct
>> estimates would fix a large minority of currently pathological queries.
>> It's like saying "hey, we don't need to fix the leak in your radiator,
>> we've given you a funnel in the dashboard you can pour water into."
>
> Having read papers on it, I believe the problem is intractable. Coding
> is not the issue. To anyone: please prove me wrong, in detail, with
> references so it can be coded.
I think it might be close to intractable if you're determined to use a
sampling model. HyperLogLog looks very interesting for n_distinct
estimation, though. My abbreviated key patch estimates the cardinality
of abbreviated keys (and original strings that are to be sorted) with
high precision and fixed overhead. Maybe we can figure out a way to
do opportunistic streaming of HLL. Believe it or not, the way I use
HLL for estimating cardinality is virtually free. Hashing is really
cheap when the CPU is bottlenecked on memory bandwidth.
If you're interested, download the patch, and enable the debug traces.
You'll see HyperLogLog accurately indicate the cardinality of text
datums as they're copied into local memory before sorting.
--
Regards,
Peter Geoghegan
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-02 13:59 Ryan Johnson <ryan.johnson@cs.utoronto.ca>
parent: Merlin Moncure <mmoncure@gmail.com>
1 sibling, 0 replies; 60+ messages in thread
From: Ryan Johnson @ 2014-10-02 13:59 UTC (permalink / raw)
To: pgsql-performance
On 29/09/2014 9:00 AM, Merlin Moncure wrote:
> On Fri, Sep 26, 2014 at 3:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> The problem, as I see it, is different. We assume that if there are
>> 100 distinct values and you use LIMIT 1 that you would only need to
>> scan 1% of rows. We assume that the data is arranged in the table in a
>> very homogenous layout. When data is not, and it seldom is, we get
>> problems.
> Hm, good point -- 'data proximity'. At least in theory, can't this be
> measured and quantified? For example, given a number of distinct
> values, you could estimate the % of pages read (or maybe non
> sequential seeks relative to the number of pages) you'd need to read
> all instances of a particular value in the average (or perhaps the
> worst) case. One way of trying to calculate that would be to look at
> proximity of values in sampled pages (and maybe a penalty assigned for
> high update activity relative to table size). Data proximity would
> then become a cost coefficient to the benefits of LIMIT.
Latecomer to the conversation here, but it seems like this issue (unlike
some) is really easy to recognize at runtime. The optimizer assumed the
scan would access O(1) pages; if the scan has not returned enough
results after k pages, that would be a really good indication that it's
time to rethink the plan, and probably before too much work has been
done higher in the plan (esp. if there's any kind of buffering between
operators, perhaps intentionally so in special cases like this)
Not sure pgsql has any dynamic reoptimization infrastructure in place,
tho. If not, these sorts of dangerous plans are best left alone IMO.
Ryan
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-02 19:56 Josh Berkus <josh@agliodbs.com>
parent: Peter Geoghegan <peter.geoghegan86@gmail.com>
0 siblings, 3 replies; 60+ messages in thread
From: Josh Berkus @ 2014-10-02 19:56 UTC (permalink / raw)
To: Peter Geoghegan <peter.geoghegan86@gmail.com>; Simon Riggs <simon@2ndquadrant.com>; +Cc: Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 10/02/2014 02:30 AM, Peter Geoghegan wrote:
> On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> Having read papers on it, I believe the problem is intractable. Coding
>> is not the issue. To anyone: please prove me wrong, in detail, with
>> references so it can be coded.
>
> I think it might be close to intractable if you're determined to use a
> sampling model. HyperLogLog looks very interesting for n_distinct
> estimation, though. My abbreviated key patch estimates the cardinality
> of abbreviated keys (and original strings that are to be sorted) with
> high precision and fixed overhead. Maybe we can figure out a way to
> do opportunistic streaming of HLL. Believe it or not, the way I use
> HLL for estimating cardinality is virtually free. Hashing is really
> cheap when the CPU is bottlenecked on memory bandwidth.
Yes, it's only intractable if you're wedded to the idea of a tiny,
fixed-size sample. If we're allowed to sample, say, 1% of the table, we
can get a MUCH more accurate n_distinct estimate using multiple
algorithms, of which HLL is one. While n_distinct will still have some
variance, it'll be over a much smaller range.
The n_distinct algo we use in Postgres is specifically designed (by its
author) to choose the smallest reasonable number of distinct values
capable of producing the observed distribution. This made sense when we
added it because we didn't have query plans where underestimating
n_distinct produced a penalty. Now we do, and we ought to change algos.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-03 00:54 Peter Geoghegan <peter.geoghegan86@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
2 siblings, 1 reply; 60+ messages in thread
From: Peter Geoghegan @ 2014-10-03 00:54 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
> Yes, it's only intractable if you're wedded to the idea of a tiny,
> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
> can get a MUCH more accurate n_distinct estimate using multiple
> algorithms, of which HLL is one. While n_distinct will still have some
> variance, it'll be over a much smaller range.
I think that HyperLogLog, as a streaming algorithm, will always
require that the entire set be streamed. This doesn't need to be a big
deal - in the case of my abbreviated key patch, it appears to
basically be free because of the fact that we were streaming
everything anyway. It's a very cool algorithm, with fixed overhead and
constant memory usage. It makes very useful guarantees around
accuracy.
I have this intuition that even though I'm more or less not paying
anything for a great cardinality estimate, it's kind of a shame that I
still throw it away after the sort, each and every time. I have a hard
time actually putting my finger on how it could be put to further use,
though. And besides, this only helps if you happen to need to do a
sort (or something that requires a sequential scan, since the cost
certainly isn't anywhere near "free" when you didn't need to do that
anyway).
Our current lack of block-based sampling probably implies that we are
almost as badly off as if we *did* a sequential scan. Not that I'm
suggesting that we give up on the idea of sampling (which would be
crazy).
Streaming algorithms like HyperLogLog are very recent ideas, as these
things go. I wouldn't be all that discouraged by the fact that it
might not have been put to use in this way (for database statistics)
by somebody before now.
--
Regards,
Peter Geoghegan
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-03 19:58 Jeff Janes <jeff.janes@gmail.com>
parent: Josh Berkus <josh@agliodbs.com>
2 siblings, 1 reply; 60+ messages in thread
From: Jeff Janes @ 2014-10-03 19:58 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Peter Geoghegan <peter.geoghegan86@gmail.com>; Simon Riggs <simon@2ndquadrant.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
> On 10/02/2014 02:30 AM, Peter Geoghegan wrote:
> > On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs <simon@2ndquadrant.com>
> wrote:
> >> Having read papers on it, I believe the problem is intractable. Coding
> >> is not the issue. To anyone: please prove me wrong, in detail, with
> >> references so it can be coded.
> >
> > I think it might be close to intractable if you're determined to use a
> > sampling model. HyperLogLog looks very interesting for n_distinct
> > estimation, though. My abbreviated key patch estimates the cardinality
> > of abbreviated keys (and original strings that are to be sorted) with
> > high precision and fixed overhead. Maybe we can figure out a way to
> > do opportunistic streaming of HLL. Believe it or not, the way I use
> > HLL for estimating cardinality is virtually free. Hashing is really
> > cheap when the CPU is bottlenecked on memory bandwidth.
>
> Yes, it's only intractable if you're wedded to the idea of a tiny,
> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
> can get a MUCH more accurate n_distinct estimate using multiple
> algorithms, of which HLL is one. While n_distinct will still have some
> variance, it'll be over a much smaller range.
>
In my hands, the problems with poor n_distinct were not due to the
insufficient size of the sample, but the insufficient randomness of it.
Increasing default_statistics_target did help but not because it increases
the number of rows sampled, but rather because it increases the number of
blocks sampled. Once substantially all of the blocks are part of the block
sampling, the bias is eliminated even though it was still sampling a small
fraction of the rows (roughly one per block).
So one idea would be go get rid of the 2-stage sampling algorithm (sample
blocks, sample rows from the chosen blocks) and just read the whole table
and sample rows from it unbiased, at least under some conditions. Some low
level benchmarking on my favorite server showed that reading 1% of a
system's blocks (in block number order within each file) was no faster than
reading all of them from an IO perspective. But that is a virtualized
server that wasn't really speced out to be an IO intensive database server
in the first place. It would be interesting to see what people get on real
hardware that they actually designed for the task.
A problem right now is that we only have one knob. I want to compute more
accurate n_distinct and most_common_freqs, but I don't want to store huge
numbers entries for most_common_vals and histogram_bounds.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-03 23:30 Tomas Vondra <tv@fuzzy.cz>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 0 replies; 60+ messages in thread
From: Tomas Vondra @ 2014-10-03 23:30 UTC (permalink / raw)
To: pgsql-performance
On 3.10.2014 21:58, Jeff Janes wrote:
> On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com
> <mailto:josh@agliodbs.com>> wrote:
>
> Yes, it's only intractable if you're wedded to the idea of a tiny,
> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
> can get a MUCH more accurate n_distinct estimate using multiple
> algorithms, of which HLL is one. While n_distinct will still have some
> variance, it'll be over a much smaller range.
>
>
> In my hands, the problems with poor n_distinct were not due to the
> insufficient size of the sample, but the insufficient randomness of it.
> Increasing default_statistics_target did help but not because it
> increases the number of rows sampled, but rather because it increases
> the number of blocks sampled. Once substantially all of the blocks are
> part of the block sampling, the bias is eliminated even though it was
> still sampling a small fraction of the rows (roughly one per block).
I don't think that's entirely accurate. According to [1], there's a
lower boundary on ratio error, depending on the number of sampled rows.
Say there's a table with 10M rows, we sample 30k rows (which is the
default). Then with probability 5% we'll get ratio error over 20. That
is, we may either estimate <5% or >200% of the actual ndistinct value.
Combined with our arbitrary 10% limit that we use to decide whether
ndistinct scales with the number of rows, this sometimes explodes.
By increasing the statistics target, you get much larger sample and thus
lower probability of such error. But nevertheless, it breaks from time
to time, and the fact that statistics target is static (and not scaling
with the size of the table to get appropriate sample size) is not really
helping IMHO. Static sample size may work for histograms, for ndistinct
not so much.
[1]
http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf
> So one idea would be go get rid of the 2-stage sampling algorithm
> (sample blocks, sample rows from the chosen blocks) and just read
> the whole table and sample rows from it unbiased, at least under
> some conditions. Some low level benchmarking on my favorite server
> showed that reading 1% of a system's blocks (in block number order
> within each file) was no faster than reading all of them from an IO
> perspective. But that is a virtualized server that wasn't really
> speced out to be an IO intensive database server in the first place.
> It would be interesting to see what people get on real hardware that
> they actually designed for the task.
I think there was a discussion about the sampling on pgsql-hackers a
while ago ... and yes, here it is [2]. However it seems there was no
clear conclusion on how to change it at that time ...
[2]
http://www.postgresql.org/message-id/CA+TgmoZaqyGSuaL2v+YFVsX06DQDQh-pEV0nobGPws-dNwAwBw@mail.gmail....
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-03 23:41 Tomas Vondra <tv@fuzzy.cz>
parent: Peter Geoghegan <peter.geoghegan86@gmail.com>
0 siblings, 0 replies; 60+ messages in thread
From: Tomas Vondra @ 2014-10-03 23:41 UTC (permalink / raw)
To: pgsql-performance
On 3.10.2014 02:54, Peter Geoghegan wrote:
> On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> Yes, it's only intractable if you're wedded to the idea of a tiny,
>> fixed-size sample. If we're allowed to sample, say, 1% of the
>> table, we can get a MUCH more accurate n_distinct estimate using
>> multiple algorithms, of which HLL is one. While n_distinct will
>> still have some variance, it'll be over a much smaller range.
>
> I think that HyperLogLog, as a streaming algorithm, will always
> require that the entire set be streamed. This doesn't need to be a
> big deal - in the case of my abbreviated key patch, it appears to
> basically be free because of the fact that we were streaming
> everything anyway. It's a very cool algorithm, with fixed overhead
> and constant memory usage. It makes very useful guarantees around
> accuracy.
I think you're mixing two things here - estimating the number of
distinct values in a sample (which can be done very efficiently using
HLL) and estimating the number of distinct values in the whole table.
For that HLL is not usable, unless you process all the data.
Sadly HLL is rather incompatible with the usual estimators, because the
ones I'm aware of need to know the number of occurences for the distinct
values etc.
But couldn't we just piggyback this on autovacuum? One of the nice HLL
features is that it's additive - you can build "partial counters" for
ranges of blocks (say, a few MBs per range), and then merge them when
needed. By keeping the parts it's possible to rebuild it separately.
But maybe this idea is way too crazy ...
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 11:16 Greg Stark <stark@mit.edu>
parent: Josh Berkus <josh@agliodbs.com>
2 siblings, 2 replies; 60+ messages in thread
From: Greg Stark @ 2014-10-10 11:16 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Peter Geoghegan <peter.geoghegan86@gmail.com>; Simon Riggs <simon@2ndquadrant.com>; Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
> Yes, it's only intractable if you're wedded to the idea of a tiny,
> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
> can get a MUCH more accurate n_distinct estimate using multiple
> algorithms, of which HLL is one. While n_distinct will still have some
> variance, it'll be over a much smaller range.
I've gone looking for papers on this topic but from what I read this
isn't so. To get any noticeable improvement you need to read 10-50% of
the table and that's effectively the same as reading the entire table
-- and it still had pretty poor results. All the research I could find
went into how to analyze the whole table while using a reasonable
amount of scratch space and how to do it incrementally.
--
greg
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 12:10 Tomas Vondra <tv@fuzzy.cz>
parent: Greg Stark <stark@mit.edu>
1 sibling, 2 replies; 60+ messages in thread
From: Tomas Vondra @ 2014-10-10 12:10 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: Josh Berkus <josh@agliodbs.com>; Peter Geoghegan <peter.geoghegan86@gmail.com>; Simon Riggs <simon@2ndquadrant.com>; Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
Dne 10 ŘÃjen 2014, 13:16, Greg Stark napsal(a):
> On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> Yes, it's only intractable if you're wedded to the idea of a tiny,
>> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
>> can get a MUCH more accurate n_distinct estimate using multiple
>> algorithms, of which HLL is one. While n_distinct will still have some
>> variance, it'll be over a much smaller range.
>
> I've gone looking for papers on this topic but from what I read this
> isn't so. To get any noticeable improvement you need to read 10-50% of
> the table and that's effectively the same as reading the entire table
> -- and it still had pretty poor results. All the research I could find
> went into how to analyze the whole table while using a reasonable
> amount of scratch space and how to do it incrementally.
I think it's really difficult to discuss the estimation without some basic
agreement on what are the goals. Naturally, we can't get a perfect
estimator with small samples (especially when the sample size is fixed and
not scaling with the table). But maybe we can improve the estimates
without scanning most of the table?
FWIW I've been playing with the adaptive estimator described in [1] and
the results looks really interesting, IMHO. So far I was testing it on
synthetic datasets outside the database, but I plan to use it instead of
our estimator, and do some more tests.
Would be helpful to get a collection of test cases that currently perform
poorly. I have collected a few from the archives, but if those who follow
this thread can provide additional test cases / point to a thread
describing related etc. that'd be great.
It certainly won't be perfect, but if it considerably improves the
estimates then I believe it's step forward. Ultimately, it's impossible to
improve the estimates without increasing the sample size.
[1]
http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 14:21 Craig James <cjames@emolecules.com>
parent: Tomas Vondra <tv@fuzzy.cz>
1 sibling, 1 reply; 60+ messages in thread
From: Craig James @ 2014-10-10 14:21 UTC (permalink / raw)
To: pgsql-performance
On Fri, Oct 10, 2014 at 5:10 AM, Tomas Vondra <tv@fuzzy.cz> wrote:
> > I've gone looking for papers on this topic but from what I read this
> > isn't so. To get any noticeable improvement you need to read 10-50% of
> > the table and that's effectively the same as reading the entire table
> > -- and it still had pretty poor results. All the research I could find
> > went into how to analyze the whole table while using a reasonable
> > amount of scratch space and how to do it incrementally.
>
> I think it's really difficult to discuss the estimation without some basic
> agreement on what are the goals. Naturally, we can't get a perfect
> estimator with small samples (especially when the sample size is fixed and
> not scaling with the table). But maybe we can improve the estimates
> without scanning most of the table?
>
> FWIW I've been playing with the adaptive estimator described in [1] and
> the results looks really interesting, IMHO. So far I was testing it on
> synthetic datasets outside the database, but I plan to use it instead of
> our estimator, and do some more tests.
>
We've solved this problem using an external (non-Postgres) dynamically
optimizing index. In addition to the "early abort," we also require an
efficient "late start", the equivalent of "offset 100 limit 10". It's a
common problem for web sites that let users page through data with just a
tiny amount of state information (a cookie).
Our index is for chemical structures. Chemicals are indexed on chemical
fragments <http://emolecules.com/info/molecular-informatics;. A search
typically starts with 50-200 indexed "columns" (chemical fragments). The
query is always flat, "A and B and ... and Z". The indexed fragments are
both correlated (the existence of one strongly raises the chances of
another) and anti-correlated (certain combinations are very rare).
The dynamic optimizer watches the performance of each index in real time.
It promotes highly selective indexes and demotes or removes redundant
indexes. In a typical query, the initial 50-200 indexes are reduced to 5-10
indexes within the first 100-200 rows examined. The remaining indexes have
little correlation yet retain most of the selectivity. (One critical factor
with a dynamic optimizer is that the data must be randomized before it's
presented to the optimizer. Databases tend to have clusters of similar
data. If the optimizer starts in such a cluster, it will optimize poorly.)
Our query is simple (a flat AND) compared to what Postgres has to handle.
Even so, a dynamic optimizer is the only effective solution.
Static planners simply can't handle the "early abort" condition, even with
good statistics. Many have pointed out that data are "lumpy" rather than
well distributed. A more subtle problem is that you can have evenly
distributed data, but badly distributed correlations. "Agnes" and "Bob" may
be names that are distributed well in a real-estate database, but it might
happen that all of the information about homes whose owners' names are
"Agnes" and "Bob" occurs at the very end of all of your data because they
just got married and bought a house.
The end result is that even with perfect statistics on each column, you're
still screwed. The combinatorial explosion of possible correlations between
indexes is intractable.
Craig
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 16:53 Tomas Vondra <tv@fuzzy.cz>
parent: Craig James <cjames@emolecules.com>
0 siblings, 1 reply; 60+ messages in thread
From: Tomas Vondra @ 2014-10-10 16:53 UTC (permalink / raw)
To: pgsql-performance
On 10.10.2014 16:21, Craig James wrote:
> On Fri, Oct 10, 2014 at 5:10 AM, Tomas Vondra <tv@fuzzy.cz
> <mailto:tv@fuzzy.cz>> wrote:
>
> > I've gone looking for papers on this topic but from what I read this
> > isn't so. To get any noticeable improvement you need to read 10-50% of
> > the table and that's effectively the same as reading the entire table
> > -- and it still had pretty poor results. All the research I could find
> > went into how to analyze the whole table while using a reasonable
> > amount of scratch space and how to do it incrementally.
>
> I think it's really difficult to discuss the estimation without some
> basic
> agreement on what are the goals. Naturally, we can't get a perfect
> estimator with small samples (especially when the sample size is
> fixed and
> not scaling with the table). But maybe we can improve the estimates
> without scanning most of the table?
>
> FWIW I've been playing with the adaptive estimator described in [1] and
> the results looks really interesting, IMHO. So far I was testing it on
> synthetic datasets outside the database, but I plan to use it instead of
> our estimator, and do some more tests.
>
>
> We've solved this problem using an external (non-Postgres) dynamically
> optimizing index. In addition to the "early abort," we also require an
> efficient "late start", the equivalent of "offset 100 limit 10". It's a
> common problem for web sites that let users page through data with just
> a tiny amount of state information (a cookie).
Yeah, paging is a known example, both for the inefficiency once you get
to pages far away, and because of the planning challenges. I think there
are known solutions to this problem
(http://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way),
although those are not applicable to all cases.
But I'm not sure how that's related to the ndistinct estimation problem,
discussed in this thread (or rather in this subthread)?
> Our index is for chemical structures. Chemicals are indexed on
> chemical fragments
> <http://emolecules.com/info/molecular-informatics;. A search
> typically starts with 50-200 indexed "columns" (chemical fragments).
> The query is always flat, "A and B and ... and Z". The indexed
> fragments are both correlated (the existence of one strongly raises
> the chances of another) and anti-correlated (certain combinations are
> very rare).
Maybe I don't understand the problem well enough, but isn't this a
perfect match for GIN indexes? I mean, you essentially need to do
queries like "WHERE substance @@ ('A & B & !C')" etc. Which is exactly
what GIN does, because it keeps pointers to tuples for each fragment.
> Static planners simply can't handle the "early abort" condition,
> even with good statistics. Many have pointed out that data are
> "lumpy" rather than well distributed. A more subtle problem is that
> you can have evenly distributed data, but badly distributed
> correlations. "Agnes" and "Bob" may be names that are distributed
> well in a real-estate database, but it might happen that all of the
> information about homes whose owners' names are "Agnes" and "Bob"
> occurs at the very end of all of your data because they just got
> married and bought a house.
>
> The end result is that even with perfect statistics on each column,
> you're still screwed. The combinatorial explosion of possible
> correlations between indexes is intractable.
Static planners clearly have limitations, but we don't have dynamic
planning in PostgreSQL, so we have to live with them. And if we could
improve the quality of estimates - lowering the probability of poorly
performing plans, it's probably good to do that.
It won't be perfect, but until we have dynamic planning it's better than
nothing.
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 17:53 Tomas Vondra <tv@fuzzy.cz>
parent: Tomas Vondra <tv@fuzzy.cz>
1 sibling, 1 reply; 60+ messages in thread
From: Tomas Vondra @ 2014-10-10 17:53 UTC (permalink / raw)
To: pgsql-performance
On 10.10.2014 14:10, Tomas Vondra wrote:
> Dne 10 ŘÃjen 2014, 13:16, Greg Stark napsal(a):
>> On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>>> Yes, it's only intractable if you're wedded to the idea of a tiny,
>>> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
>>> can get a MUCH more accurate n_distinct estimate using multiple
>>> algorithms, of which HLL is one. While n_distinct will still have some
>>> variance, it'll be over a much smaller range.
>>
>> I've gone looking for papers on this topic but from what I read this
>> isn't so. To get any noticeable improvement you need to read 10-50% of
>> the table and that's effectively the same as reading the entire table
>> -- and it still had pretty poor results. All the research I could find
>> went into how to analyze the whole table while using a reasonable
>> amount of scratch space and how to do it incrementally.
>
> I think it's really difficult to discuss the estimation without some basic
> agreement on what are the goals. Naturally, we can't get a perfect
> estimator with small samples (especially when the sample size is fixed and
> not scaling with the table). But maybe we can improve the estimates
> without scanning most of the table?
>
> FWIW I've been playing with the adaptive estimator described in [1] and
> the results looks really interesting, IMHO. So far I was testing it on
> synthetic datasets outside the database, but I plan to use it instead of
> our estimator, and do some more tests.
Attached is an experimental patch implementing the adaptive estimator.
It was fairly simple (although it's a bit messy). It only computes the
estimates for the "scalar" case (i.e. data types that we can sort).
Implementing this for the "minimal" case is possible, but requires a bit
more work.
It only computes the estimate and prints a WARNING with both the current
and new estimate, but the old estimate is stored.
I also attach a few synthetic examples of synthetic datasets with
distributions stored in various ways, that I used for testing. In all
cases there's a single table with 10M rows and a single INT column.
There are three kinds of skew:
1) smooth skew
- N distinct values (100, 10.000 and 100.000 values)
- average moves to 0 as 'k' increases ('k' between 1 and 9)
- smooth distribution of frequencies
INSERT INTO test
SELECT pow(random(),k) * 10000 FROM generate_series(1,10000000);
2) step skew
- a few very frequent values, many rare values
- for example this generates 5 very frequent and ~10k rare values
INSERT INTO test
SELECT (CASE WHEN (v < 90000) THEN MOD(v,5) ELSE v END)
FROM (
SELECT (random()*100000)::int AS v
FROM generate_series(1,10000000)
) foo;
Results
=======
I tested this with various statistics target settings (10, 100, 1000),
which translates to different sample sizes.
statistics target 100 (default, 30k rows, 0.3% sample)
======================================================
a) smooth skew, 101 values, different skew ('k')
k current adaptive
-------------------------
1 101 102
3 101 102
5 101 102
7 101 102
9 101 102
b) smooth skew, 10.001 values, different skew ('k')
k current adaptive
-------------------------
1 9986 10542
3 8902 10883
5 7579 10824
7 6639 10188
9 5947 10013
c) step skew (different numbers of values)
values current adaptive
------------------------------
106 106 107
106 35 104
1006 259 1262
10006 2823 11047
statistics target 10 (3k rows, 0.03% sample)
============================================
a) smooth skew, 101 values, different skew ('k')
k current adaptive
-------------------------
1 101 102
3 101 102
5 101 102
7 101 102
9 101 102
b) smooth skew, 10.001 values, different skew ('k')
k current adaptive
-------------------------
1 9846 10014
3 4399 7190
5 2532 5477
7 1938 4932
9 1623 1623
c) step skew (different numbers of values)
values current adaptive
------------------------------
106 100 114
106 5 5
1006 37 532
10006 323 20970
statistics target 1000 (300k rows, 3% sample)
=============================================
k current adaptive
-------------------------
1 101 102
3 101 102
5 101 102
7 101 102
9 101 102
b) smooth skew, 10.001 values, different skew ('k')
k current adaptive
-------------------------
1 10001 10002
3 10000 10000
5 9998 10011
7 9973 10045
9 9939 10114
c) step skew (different numbers of values)
values current adaptive
------------------------------
106 106 107
106 101 107
1006 957 1096
10006 9551 10550
Summary
=======
I'm yet to see an example where the adaptive estimator produces worse
results than the current estimator, irrespectedly of the distribution
and sample size / statistics target.
What really matters is the sample size, with respect to the table size,
so I'll use the 0.03%, 0.3%, and 3% instead of the statistics target.
For the large sample (3%) both estimators produce reasonably accurate
results. This however won't work as the tables grow, because the number
of rows we sample is static (does not grow with the table).
As the sample decreases, the adaptive estimator starts winning. For the
0.3% sample the difference is easily 3x for the high-skew cases. E.g.
for one of the "step skew" distributions the actual ndistinct value is
10006, current estimator gives 2823 while adaptive gives 11047. That's
ratio error ~3.5 vs. 1.1x.
For the tiny 0.03% sample the difference gets even more siginficant,
especially for the step-skew cases, where the improvement is often an
order of magnitude.
Proposal
========
I think the adaptive estimator works very well, and I plan to submit it
to the next commitfest after a bit of polishing. Examples of
distributions that break it are welcome of course.
Also, I think it's clear it'd be useful to be able to scale the sample
proportionally to the table (instead of only allowing the current
statistics target approach). I understand it may result in scanning
large part of the table, but I don't see a problem in that's not a
default behavior (and clearly documented). I don't see a way around that
- small samples simply result in poor estimates.
I was thinking that this could be done using statistics target, but it's
already used for other things (e.g. size of MCV list, histogram) and we
don't want to break that by adding yet another function.
Ideas?
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
ndistinct-estimator.patch (text/x-diff, 4.8K) download
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index c09ca7e..7018987 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -110,6 +110,7 @@ static void update_attstats(Oid relid, bool inh,
static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
+static double optimize_estimate(int total_rows, int d, int *f, int r);
/*
* analyze_rel() -- analyze one relation
@@ -2360,6 +2361,11 @@ compute_scalar_stats(VacAttrStatsP stats,
int slot_idx = 0;
CompareScalarsContext cxt;
+ /* f values for the estimator - messy and we likely need much
+ * less memory, but who cares */
+ int f_max = 0; /* max number of duplicates */
+ int *f_count = (int*)palloc0(sizeof(int)*values_cnt);
+
/* Sort the collected values */
cxt.ssup = &ssup;
cxt.tupnoLink = tupnoLink;
@@ -2401,6 +2407,7 @@ compute_scalar_stats(VacAttrStatsP stats,
ndistinct++;
if (dups_cnt > 1)
{
+
nmultiple++;
if (track_cnt < num_mcv ||
dups_cnt > track[track_cnt - 1].count)
@@ -2426,6 +2433,12 @@ compute_scalar_stats(VacAttrStatsP stats,
track[j].first = i + 1 - dups_cnt;
}
}
+
+ /* increment the number of values with this number of
+ * repetitions and the largest number of repetitions */
+ f_count[dups_cnt] += 1;
+ f_max = (f_max < dups_cnt) ? dups_cnt : f_max;
+
dups_cnt = 0;
}
}
@@ -2472,6 +2485,7 @@ compute_scalar_stats(VacAttrStatsP stats,
double numer,
denom,
stadistinct;
+ double adaptdistinct; /* adaptive estimate */
numer = (double) samplerows *(double) d;
@@ -2485,6 +2499,12 @@ compute_scalar_stats(VacAttrStatsP stats,
if (stadistinct > totalrows)
stadistinct = totalrows;
stats->stadistinct = floor(stadistinct + 0.5);
+
+ /* compute the adaptive estimate */
+ adaptdistinct = optimize_estimate(totalrows, d, f_count, f_max);
+
+ elog(WARNING, "ndistinct estimate current=%.2f adaptive=%.2f", stadistinct, adaptdistinct);
+
}
/*
@@ -2810,3 +2830,84 @@ compare_mcvs(const void *a, const void *b)
return da - db;
}
+
+
+/*
+ * We need to minimize this equality (find "m" solving it)
+ *
+ * m - f1 - f2 = f1 * (A + A(m)) / (B + B(m))
+ *
+ * where A, B are effectively constants (not depending on m), and A(m)
+ * and B(m) are functions. This is equal to solving
+ *
+ * 0 = f1 * (A + A(m)) / (B + B(m)) - (m - f1 - f2)
+ *
+ * Instead of looking for the exact solution to this equation (which
+ * might be fractional), we'll look for a natural number minimizing
+ * the absolute difference. Number of (distinct) elements is a natural
+ * number, and we don't mind if the number os slightly wrong. It's
+ * just an estimate, after all. The error from sampling will be much
+ * worse in most cases.
+ *
+ * We know the acceptable values of 'm' are [d,N] where 'd' is the number
+ * of distinct elements in the sample, and N is the number of rows in
+ * the table (not just the sample). For large tables (billions of rows)
+ * that'd be quite time-consuming to compute, so we'll approximate the
+ * solution by gradually increasing the step to ~1% of the current value
+ * of 'm'. This will make it much faster and yet very accurate.
+ *
+ * All this of course assumes the function behaves reasonably (not
+ * oscillating etc.), but that's a safe assumption as the estimator
+ * would perform terribly otherwise.
+ */
+static double
+optimize_estimate(int total_rows, int d, int *f, int r)
+{
+ int i, m;
+ double A = 0.0, B = 0.0;
+ int opt_m = 0;
+ double opt_diff = total_rows;
+ int step = 1;
+ int ndistinct;
+
+ /* compute the 'constant' parts of the equality (A, B) */
+ for (i = 3; i <= r; i++)
+ {
+ double p = i / (double)r;
+ A += pow((1 - p), r ) * f[i];
+ B += i * pow((1 - p), r-1) * f[i];
+ }
+
+ /* find the 'm' value minimizing the difference */
+ for (m = 1; m <= total_rows; m += step)
+ {
+ int k = (f[1] + 2*f[2]);
+ double q = k / ((double)(r * 2 * m));
+
+ double A_m = A + m * pow((1 - q), r );
+ double B_m = B + k * pow((1 - q), r-1);
+
+ double diff = fabs(f[1] * (A_m / B_m) - (m - f[1] - f[2]));
+
+ /* if this is a better solution */
+ if (diff < opt_diff)
+ {
+ opt_diff = diff;
+ opt_m = m;
+ }
+
+ /* tweak the step to 1% to make it faster */
+ step = ((int)(0.01 * m) > 1) ? (int)(0.01 * m) : 1;
+ }
+
+ /* compute the final estimate */
+ ndistinct = d + opt_m - f[1] - f[2];
+
+ /* sanity checks that the estimate is within [d,total_rows] */
+ if (ndistinct < d)
+ ndistinct = d;
+ else if (ndistinct > total_rows)
+ ndistinct = total_rows;
+
+ return ndistinct;
+}
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 17:59 Craig James <cjames@emolecules.com>
parent: Tomas Vondra <tv@fuzzy.cz>
0 siblings, 1 reply; 60+ messages in thread
From: Craig James @ 2014-10-10 17:59 UTC (permalink / raw)
To: Tomas Vondra <tv@fuzzy.cz>; +Cc: pgsql-performance
On Fri, Oct 10, 2014 at 9:53 AM, Tomas Vondra <tv@fuzzy.cz> wrote:
>
> On 10.10.2014 16:21, Craig James wrote:
> > Our index is for chemical structures. Chemicals are indexed on
> > chemical fragments
> > <http://emolecules.com/info/molecular-informatics;. A search
> > typically starts with 50-200 indexed "columns" (chemical fragments).
> > The query is always flat, "A and B and ... and Z". The indexed
> > fragments are both correlated (the existence of one strongly raises
> > the chances of another) and anti-correlated (certain combinations are
> > very rare).
>
> Maybe I don't understand the problem well enough, but isn't this a
> perfect match for GIN indexes? I mean, you essentially need to do
> queries like "WHERE substance @@ ('A & B & !C')" etc. Which is exactly
> what GIN does, because it keeps pointers to tuples for each fragment.
>
On the day our web site opened we were using tsearch. Before the end of the
day we realized it was a bad idea, for the very reasons discussed here. The
early-abort/late-start problem ("offset N limit M") could take minutes to
return the requested page. With the external dynamically-optimized index,
we can almost always get answers in less than a couple seconds, often in
0.1 seconds.
Craig
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-10 18:13 Tomas Vondra <tv@fuzzy.cz>
parent: Craig James <cjames@emolecules.com>
0 siblings, 0 replies; 60+ messages in thread
From: Tomas Vondra @ 2014-10-10 18:13 UTC (permalink / raw)
To: pgsql-performance
On 10.10.2014 19:59, Craig James wrote:
> On Fri, Oct 10, 2014 at 9:53 AM, Tomas Vondra <tv@fuzzy.cz
> <mailto:tv@fuzzy.cz>> wrote:
>
>
> On 10.10.2014 16:21, Craig James wrote:
> > Our index is for chemical structures. Chemicals are indexed on
> > chemical fragments
> > <http://emolecules.com/info/molecular-informatics;. A search
> > typically starts with 50-200 indexed "columns" (chemical fragments).
> > The query is always flat, "A and B and ... and Z". The indexed
> > fragments are both correlated (the existence of one strongly raises
> > the chances of another) and anti-correlated (certain combinations are
> > very rare).
>
> Maybe I don't understand the problem well enough, but isn't this a
> perfect match for GIN indexes? I mean, you essentially need to do
> queries like "WHERE substance @@ ('A & B & !C')" etc. Which is exactly
> what GIN does, because it keeps pointers to tuples for each fragment.
>
>
> On the day our web site opened we were using tsearch. Before the end of
> the day we realized it was a bad idea, for the very reasons discussed
> here. The early-abort/late-start problem ("offset N limit M") could take
> minutes to return the requested page. With the external
> dynamically-optimized index, we can almost always get answers in less
> than a couple seconds, often in 0.1 seconds.
In the early days of tsearch, it did not support GIN indexes, and AFAIK
GiST are not nearly as fast for such queries. Also, the GIN fastscan
implemented by Alexander Korotkov in 9.4 makes a huge difference for
queries combining frequent and rare terms.
Maybe it'd be interesting to try this on 9.4. I'm not saying it will
make it faster than the optimized index, but it might be an interesting
comparison.
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-15 17:20 Josh Berkus <josh@agliodbs.com>
parent: Greg Stark <stark@mit.edu>
1 sibling, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-10-15 17:20 UTC (permalink / raw)
To: Greg Stark <stark@mit.edu>; +Cc: Peter Geoghegan <peter.geoghegan86@gmail.com>; Simon Riggs <simon@2ndquadrant.com>; Jeff Janes <jeff.janes@gmail.com>; Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 10/10/2014 04:16 AM, Greg Stark wrote:
> On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> Yes, it's only intractable if you're wedded to the idea of a tiny,
>> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
>> can get a MUCH more accurate n_distinct estimate using multiple
>> algorithms, of which HLL is one. While n_distinct will still have some
>> variance, it'll be over a much smaller range.
>
> I've gone looking for papers on this topic but from what I read this
> isn't so. To get any noticeable improvement you need to read 10-50% of
> the table and that's effectively the same as reading the entire table
> -- and it still had pretty poor results. All the research I could find
> went into how to analyze the whole table while using a reasonable
> amount of scratch space and how to do it incrementally.
So, right now our estimation is off on large tables by -10X to -10000X.
First, the fact that it's *always* low is an indication we're using the
wrong algorithm. Second, we can most certainly do better than a median
of -1000X.
One interesting set of algorithms is block-based sampling. That is, you
read 5% of the physical table in random blocks, reading every row in the
block. The block size is determined by your storage block size, so
you're not actually reading any more physically than you are logically;
it really is just 5% of the table, especially on SSD.
Then you apply algorithms which first estimate the correlation of common
values in the block (i.e. how likely is it that the table is completely
sorted?), and then estimates of how many values there might be total
based on the correlation estimate.
I no longer have my ACM membership, so I can't link this, but
researchers were able to get +/- 3X accuracy for a TPCH workload using
this approach. A real database would be more variable, of course, but
even so we should be able to achieve +/- 50X, which would be an order of
magnitude better than we're doing now.
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-15 18:02 Tomas Vondra <tv@fuzzy.cz>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 60+ messages in thread
From: Tomas Vondra @ 2014-10-15 18:02 UTC (permalink / raw)
To: pgsql-performance
On 15.10.2014 19:20, Josh Berkus wrote:
> On 10/10/2014 04:16 AM, Greg Stark wrote:
>> On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>>> Yes, it's only intractable if you're wedded to the idea of a tiny,
>>> fixed-size sample. If we're allowed to sample, say, 1% of the table, we
>>> can get a MUCH more accurate n_distinct estimate using multiple
>>> algorithms, of which HLL is one. While n_distinct will still have some
>>> variance, it'll be over a much smaller range.
>>
>> I've gone looking for papers on this topic but from what I read this
>> isn't so. To get any noticeable improvement you need to read 10-50% of
>> the table and that's effectively the same as reading the entire table
>> -- and it still had pretty poor results. All the research I could find
>> went into how to analyze the whole table while using a reasonable
>> amount of scratch space and how to do it incrementally.
>
> So, right now our estimation is off on large tables by -10X to
> -10000X. First, the fact that it's *always* low is an indication
> we're using the wrong algorithm. Second, we can most certainly do
> better than a median of -1000X.
A few days ago I posted an experimental patch with the adaptive
estimator, described in [1]. Not perfect, but based on the testing I did
I believe it's a superior algorithm to the one we use now. Would be nice
to identify a few datasets where the current estimate is way off.
[1]
http://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/pods/towardsestimatimosur.pdf
> One interesting set of algorithms is block-based sampling. That is,
> you read 5% of the physical table in random blocks, reading every row
> in the block. The block size is determined by your storage block
> size, so you're not actually reading any more physically than you are
> logically; it really is just 5% of the table, especially on SSD.
>
> Then you apply algorithms which first estimate the correlation of
> common values in the block (i.e. how likely is it that the table is
> completely sorted?), and then estimates of how many values there
> might be total based on the correlation estimate.
I think we might also use a different approach - instead of sampling the
data when ANALYZE kicks in, we might collect a requested sample of rows
on the fly. Say we want 1% sample - whenever you insert a new row, you
do [random() < 0.01] and if it happens to be true you keep a copy of the
row aside. Then, when you need the sample, you simply read the sample
and you're done - no random access to the main table, no problems with
estimated being off due to block-level sampling, etc.
Not sure how to track deletions/updates, though. Maybe rebuilding the
sample if the number of deletions exceeds some threshold, but that
contradicts the whole idea a bit.
> I no longer have my ACM membership, so I can't link this, but
> researchers were able to get +/- 3X accuracy for a TPCH workload
> using this approach. A real database would be more variable, of
> course, but even so we should be able to achieve +/- 50X, which
> would be an order of magnitude better than we're doing now.
If you know the title of the article, it's usually available elsewhere
on the web - either at the university site, or elsewhere. I found these
two articles about block-based sampling:
http://ranger.uta.edu/~gdas/websitepages/preprints-papers/p287-chaudhuri.pdf
https://www.stat.washington.edu/research/reports/1999/tr355.pdf
Maybe there are more, but most of the other links were about how Oracle
does this in 11g.
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-17 17:25 Greg Stark <stark@mit.edu>
parent: Tomas Vondra <tv@fuzzy.cz>
0 siblings, 1 reply; 60+ messages in thread
From: Greg Stark @ 2014-10-17 17:25 UTC (permalink / raw)
To: Tomas Vondra <tv@fuzzy.cz>; +Cc: pgsql-performance
On Wed, Oct 15, 2014 at 7:02 PM, Tomas Vondra <tv@fuzzy.cz> wrote:
> If you know the title of the article, it's usually available elsewhere
> on the web - either at the university site, or elsewhere. I found these
> two articles about block-based sampling:
>
>
> http://ranger.uta.edu/~gdas/websitepages/preprints-papers/p287-chaudhuri.pdf
There are a series of papers with Chaudhuri as lead author which I
agree sounds like what Josh is talking about. Note that he's Microsoft
Research's database group lead and it would be a pretty safe bet
anything published from there is going to be covered by patents from
here till next Tuesday (and seventeen years beyond).
I think this is all putting the cart before the horse however. If we
could fix our current sampling to use the data more efficiently that
would be a good start before we start trying to read even more data.
We currently read just one row from each block on average instead of
using the whole block. That's what would be needed in the worst case
if the blocks were a very biased sample (which indeed they probably
are in most databases due to the way Postgres handles updates). But we
could at least give users the option to use more than one row per
block when they know it's ok (such as data that hasn't been updated)
or detect when it's ok (such as by carefully thinking about how
Postgres's storage mechanism would bias the data).
But I looked into this and ran into a problem. I think our algorithm
for calculating the most frequent values list is bunk. The more rows I
picked from each block the more biased that list was towards values
seen earlier in the table. What's worse, when that list was biased it
threw off the histogram since we exclude the most frequent values from
the histogram, so all estimates were thrown off.
If we could fix the most frequent values collection to not be biased
when it sees values in a clumpy way then I think we would be okay to
set the row sample size in Vitter's algorithm to a factor of N larger
than the block sample size where N is somewhat smaller than the
average number of rows per block. In fact even if we used all the rows
in the block I think I've convinced myself that the results would be
accurate in most circumstances.
I think to calcualte the most frequent values more accurately it would
take a two pass approach. Scan some random sample of blocks with a
counting bloom filter then do a second pass (possibly for the same
sample?) keeping counts only for values that the counting bloom filter
said hashed to the most common hash values. That might not be exactly
the most common values but should be at least a representative sample
of the most common values.
--
greg
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-18 17:01 Tomas Vondra <tv@fuzzy.cz>
parent: Greg Stark <stark@mit.edu>
0 siblings, 1 reply; 60+ messages in thread
From: Tomas Vondra @ 2014-10-18 17:01 UTC (permalink / raw)
To: pgsql-performance
On 17.10.2014 19:25, Greg Stark wrote:
> On Wed, Oct 15, 2014 at 7:02 PM, Tomas Vondra <tv@fuzzy.cz> wrote:
>> If you know the title of the article, it's usually available
>> elsewhere on the web - either at the university site, or elsewhere.
>> I found these two articles about block-based sampling:
>>
>>
>> http://ranger.uta.edu/~gdas/websitepages/preprints-papers/p287-chaudhuri.pdf
>
>>
> There are a series of papers with Chaudhuri as lead author which I
> agree sounds like what Josh is talking about. Note that he's
> Microsoft Research's database group lead and it would be a pretty
> safe bet anything published from there is going to be covered by
> patents from here till next Tuesday (and seventeen years beyond).
Hmmm. I have 0 experience with handling patents and related issues. Any
idea how to address that?
> I think this is all putting the cart before the horse however. If we
> could fix our current sampling to use the data more efficiently that
> would be a good start before we start trying to read even more data.
>
> We currently read just one row from each block on average instead of
> using the whole block. That's what would be needed in the worst case
> if the blocks were a very biased sample (which indeed they probably
> are in most databases due to the way Postgres handles updates). But
> we could at least give users the option to use more than one row per
> block when they know it's ok (such as data that hasn't been updated)
> or detect when it's ok (such as by carefully thinking about how
> Postgres's storage mechanism would bias the data).
I think this will be very tricky, and in fact it may make the estimates
much worse easily, because all the algorithms assume random sampling.
For example the ndistinct estimator uses the low-frequency values (that
were observed only once or twice in the sample). By using multiple rows
from each block, you'll significantly influence this probability for
columns with values correlated to block (which is quite common.
Take for example fact tables in data warehouses - those are usually
denormalized, mostly append-only. Say each row has "date_id" which is a
sequential number of a day, with 0 sometime in the past. Daily
increments are usually stored on many consecutive blocks, so on each
block there's usually a single date_id value.
By sampling all rows on a block you gain exactly nothing, and in fact it
results in observing no low-frequency values, making the estimator
absolutely useless.
I can imagine fixing this (although I don't see how exactly), but the
thing is we need to fix *all* the estimators we have, not just
ndistinct. And that's going to be tough.
I don't think adding a knob to tune the number of tuples sampled per
block is a good approach. Either we can solve the issues I described
(and in that case it's unnecessary), or we can't solve them and it turns
into a massive foot gun.
> But I looked into this and ran into a problem. I think our algorithm
> for calculating the most frequent values list is bunk. The more rows
> I picked from each block the more biased that list was towards
> values seen earlier in the table. What's worse, when that list was
> biased it threw off the histogram since we exclude the most frequent
> values from the histogram, so all estimates were thrown off.
I think the 'minimal' stats (when we have just '=' for the type) behaves
like this, but fixing it by switching to a two-pass approach should not
be that difficult (but would cost a few more CPU cycles).
Or do you suggest that even the scalar MCV algorithm behaves has this
bias issue? I doubt that, because the MCV works with an array sorted by
number of occurences, so the position within the table is irrelevant.
> If we could fix the most frequent values collection to not be biased
> when it sees values in a clumpy way then I think we would be okay to
> set the row sample size in Vitter's algorithm to a factor of N
> larger than the block sample size where N is somewhat smaller than
> the average number of rows per block. In fact even if we used all the
> rows in the block I think I've convinced myself that the results
> would be accurate in most circumstances.
I don't expect fixing the MCV to be overly difficult (although it will
need a few more CPU cycles).
But making it work with the block sampling will be much harder, because
of the bias. The phrase 'in most circumstances' doesn't sound really
convincing to me ...
> I think to calcualte the most frequent values more accurately it
> would take a two pass approach. Scan some random sample of blocks
> with a counting bloom filter then do a second pass (possibly for the
> same sample?) keeping counts only for values that the counting bloom
> filter said hashed to the most common hash values. That might not be
> exactly the most common values but should be at least a
> representative sample of the most common values.
I don't see why the counting bloom filter would be necessary, in a two
pass approach?
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-10-19 22:24 Greg Stark <stark@mit.edu>
parent: Tomas Vondra <tv@fuzzy.cz>
0 siblings, 0 replies; 60+ messages in thread
From: Greg Stark @ 2014-10-19 22:24 UTC (permalink / raw)
To: Tomas Vondra <tv@fuzzy.cz>; +Cc: pgsql-performance
On Sat, Oct 18, 2014 at 6:01 PM, Tomas Vondra <tv@fuzzy.cz> wrote:
> Hmmm. I have 0 experience with handling patents and related issues. Any
> idea how to address that?
Well there's no real way to address it. But to summarize: 1) We should
not go searching for patents, knowing that something is patented
increases your liability if you end up infringing on it 2) You should
consult your lawyer for advise which he can give under attorney-client
privilege and not expose you to such liability. 3) The whole patent
system is fundamentally broken and serves only to protect incumbents
from innovative competitors :(
I think realistically software patents are so vague and cover so many
basic algorithms which are obvious to anyone in the field because
they're part of the basic knowledge taught in every algorithms course.
So Postgres is probably infringing on hundreds of patents which would
all easily be declared invalid if the owners ever sought to use them
to attack widely used free software.
That doesn't mean we should be specifically seeking out specific
algorithms that are known to have been published in papers coming out
of major proprietary database vendors though. That just seems like
asking for trouble. We should be looking for solutions that seem
obvious to us or were published 17+ years ago or were published by
people who specifically claim they're not patented.
> I think this will be very tricky, and in fact it may make the estimates
> much worse easily, because all the algorithms assume random sampling.
Well this is where Josh and I agree but come to different conclusions.
He wants to use more of each block so he can take larger samples in
the hopes it will produce better statistics. I want to use more of
each block so we can continue to take rigorously justified sample
sizes but without having to read such a large portion of the table.
Either way our current sampling method isn't meeting anyone's needs.
It requires you to do copious amounts of I/O which makes running
analyze after an upgrade or data load a major contributor to your
outage window.
>
> For example the ndistinct estimator
Yes, well, the ndistinct estimator just sucks. It's always going to
suck. Unless it has a chance to see every row of the table there's
absolutely no way it's ever going to not suck. Any attempt to estimate
ndistinct from a sample of any size is going to suck. That's just the
way it is.
Our sample sizes are based on the size needed to build the histogram.
That requires only a fairly small and slow growing sample though our
block based sampling inflates the amount of I/O that leads to.
ndistinct and MCV are a different kind of problem that would require a
proportional sample where the sample needs to grow linearly as the
table grows. To get a good estimate of ndistinct requires a large
enough proportion to effectively require reading the whole table. To
get decent MCV stats only requires a smaller proportion but it's still
a proportion that grows linearly which is going to be impractical for
large data.
There are two strategies for dealing with ndistinct that I can see
here. Either a) We decide that to estimate ndistinct we need to scan
the entire table and just make that a separate type of ANALYZE that
you run less frequently. Basically this is what we did with VACUUM and
indeed we could even invest in infrastructure like the FSM which
allows you to process only the changed pages so it can be
incrementally.
Or we decide gathering periodic statistics isn't the way to handle
ndistinct and instead watch the incoming inserts and outgoing deletes
and keep the statistic up to date incrementally. That can be done
though obviously it's a bit tricky. But there's tons of published
research on updating database statistics incrementally -- which brings
us back to patents...
> I think the 'minimal' stats (when we have just '=' for the type) behaves
> like this, but fixing it by switching to a two-pass approach should not
> be that difficult (but would cost a few more CPU cycles).
>
> Or do you suggest that even the scalar MCV algorithm behaves has this
> bias issue? I doubt that, because the MCV works with an array sorted by
> number of occurences, so the position within the table is irrelevant.
Hum. I'll have to reconstruct the tests I was doing back then and see
what was going on. I never really understand what was causing it.
What I observed was that if I increased the number of rows read per
sampled block then the MCV was more and more dominated by the rows
found early in the table. This was in a column where the values were
actually uniformly distributed so there should have been only any
values which happened to be sampled substantially more than the mean
frequency. They were integers though so should have been covered by
the sorting approach.
> I don't see why the counting bloom filter would be necessary, in a two
> pass approach?
I guess I was imagining it was not keeping all the values in memory
for at the same time. Isn't that the whole point of the lossy =
algorithm? But now that I think of it I don't understand why that
algorithm is needed at all.
--
greg
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-11-21 18:38 Jeff Janes <jeff.janes@gmail.com>
parent: Tomas Vondra <tv@fuzzy.cz>
0 siblings, 1 reply; 60+ messages in thread
From: Jeff Janes @ 2014-11-21 18:38 UTC (permalink / raw)
To: Tomas Vondra <tv@fuzzy.cz>; +Cc: pgsql-performance
On Fri, Oct 10, 2014 at 10:53 AM, Tomas Vondra <tv@fuzzy.cz> wrote:
> On 10.10.2014 14:10, Tomas Vondra wrote:
> > Dne 10 ŘÃjen 2014, 13:16, Greg Stark napsal(a):
> >> On Thu, Oct 2, 2014 at 8:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
> >>> Yes, it's only intractable if you're wedded to the idea of a tiny,
> >>> fixed-size sample. If we're allowed to sample, say, 1% of the table,
> we
> >>> can get a MUCH more accurate n_distinct estimate using multiple
> >>> algorithms, of which HLL is one. While n_distinct will still have some
> >>> variance, it'll be over a much smaller range.
> >>
> >> I've gone looking for papers on this topic but from what I read this
> >> isn't so. To get any noticeable improvement you need to read 10-50% of
> >> the table and that's effectively the same as reading the entire table
> >> -- and it still had pretty poor results. All the research I could find
> >> went into how to analyze the whole table while using a reasonable
> >> amount of scratch space and how to do it incrementally.
> >
> > I think it's really difficult to discuss the estimation without some
> basic
> > agreement on what are the goals. Naturally, we can't get a perfect
> > estimator with small samples (especially when the sample size is fixed
> and
> > not scaling with the table). But maybe we can improve the estimates
> > without scanning most of the table?
> >
> > FWIW I've been playing with the adaptive estimator described in [1] and
> > the results looks really interesting, IMHO. So far I was testing it on
> > synthetic datasets outside the database, but I plan to use it instead of
> > our estimator, and do some more tests.
>
> Attached is an experimental patch implementing the adaptive estimator.
>
> It was fairly simple (although it's a bit messy). It only computes the
> estimates for the "scalar" case (i.e. data types that we can sort).
> Implementing this for the "minimal" case is possible, but requires a bit
> more work.
>
> It only computes the estimate and prints a WARNING with both the current
> and new estimate, but the old estimate is stored.
>
When I run this patch on the regression database, I get a case where the
current method is exact but the adaptive one is off:
WARNING: ndistinct estimate current=676.00 adaptive=906.00
select count(distinct stringu1) from onek;
676
It should be seeing every single row, so I don't know why the adaptive
method is off. Seems like a bug.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-11-23 20:19 Tomas Vondra <tv@fuzzy.cz>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 0 replies; 60+ messages in thread
From: Tomas Vondra @ 2014-11-23 20:19 UTC (permalink / raw)
To: pgsql-performance
On 21.11.2014 19:38, Jeff Janes wrote:
>
> When I run this patch on the regression database, I get a case where
> the current method is exact but the adaptive one is off:
>
> WARNING: ndistinct estimate current=676.00 adaptive=906.00
>
> select count(distinct stringu1) from onek;
> 676
>
> It should be seeing every single row, so I don't know why the
> adaptive method is off. Seems like a bug.
Thanks for noticing this. I wouldn't call it a bug, but there's clearly
room for improvement.
The estimator, as described in the original paper, does not expect the
sampling to be done "our" way (using fixed number of rows) but assumes
to get a fixed percentage of rows. Thus it does not expect the number of
sampled rows to get so close (or equal) to the total number of rows.
I think the only way to fix this is by checking if samplerows is close
to totalrows, and use a straightforward estimate in that case (instead
of a more sophisticated one). Something along these lines:
if (samplerows >= 0.95 * totalrows)
stats->stadistinct = (d + d/0.95) / 2;
which means "if we sampled >= 95% of the table, use the number of
observed distinct values directly".
I have modified the estimator to do the adaptive estimation, and then do
this correction too (and print the values). And with that in place I get
these results
WARNING: ndistinct estimate current=676.00 adaptive=996.00
WARNING: corrected ndistinct estimate current=676.00 adaptive=693.79
So it gets fairly close to the original estimate (and exact value).
In the end, this check should be performed before calling the adaptive
estimator at all (and not calling it in case we sampled most of the rows).
I also discovered an actual bug in the optimize_estimate() function,
using 'f_max' instead of the number of sampled rows.
Attached is a patch fixing the bug, and implementing the sample size check.
regards
Tomas
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
ndistinct-estimator-v2.patch (text/x-diff, 5.2K) download
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index 732ab22..3975fb6 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -110,6 +110,8 @@ static void update_attstats(Oid relid, bool inh,
static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
+static double optimize_estimate(int total_rows, int sample_rows, int ndistinct,
+ int *f, int f_max);
/*
* analyze_rel() -- analyze one relation
@@ -2369,6 +2371,11 @@ compute_scalar_stats(VacAttrStatsP stats,
int slot_idx = 0;
CompareScalarsContext cxt;
+ /* f values for the estimator - messy and we likely need much
+ * less memory, but who cares */
+ int f_max = 0; /* max number of duplicates */
+ int *f_count = (int*)palloc0(sizeof(int)*values_cnt);
+
/* Sort the collected values */
cxt.ssup = &ssup;
cxt.tupnoLink = tupnoLink;
@@ -2410,6 +2417,7 @@ compute_scalar_stats(VacAttrStatsP stats,
ndistinct++;
if (dups_cnt > 1)
{
+
nmultiple++;
if (track_cnt < num_mcv ||
dups_cnt > track[track_cnt - 1].count)
@@ -2435,6 +2443,12 @@ compute_scalar_stats(VacAttrStatsP stats,
track[j].first = i + 1 - dups_cnt;
}
}
+
+ /* increment the number of values with this number of
+ * repetitions and the largest number of repetitions */
+ f_count[dups_cnt] += 1;
+ f_max = (f_max < dups_cnt) ? dups_cnt : f_max;
+
dups_cnt = 0;
}
}
@@ -2481,6 +2495,7 @@ compute_scalar_stats(VacAttrStatsP stats,
double numer,
denom,
stadistinct;
+ double adaptdistinct; /* adaptive estimate */
numer = (double) samplerows *(double) d;
@@ -2494,6 +2509,20 @@ compute_scalar_stats(VacAttrStatsP stats,
if (stadistinct > totalrows)
stadistinct = totalrows;
stats->stadistinct = floor(stadistinct + 0.5);
+
+ /* compute the adaptive estimate */
+ adaptdistinct = optimize_estimate(totalrows, samplerows, d, f_count, f_max);
+
+ elog(WARNING, "ndistinct estimate current=%.2f adaptive=%.2f", stadistinct, adaptdistinct);
+
+ /* if we've seen 'almost' all rows, use the estimate instead */
+ if (samplerows >= 0.95 * totalrows)
+ {
+ adaptdistinct = (d + d/0.95)/2;
+ elog(WARNING, "corrected ndistinct estimate current=%.2f adaptive=%.2f",
+ stadistinct, adaptdistinct);
+ }
+
}
/*
@@ -2819,3 +2848,84 @@ compare_mcvs(const void *a, const void *b)
return da - db;
}
+
+
+/*
+ * We need to minimize this equality (find "m" solving it)
+ *
+ * m - f1 - f2 = f1 * (A + A(m)) / (B + B(m))
+ *
+ * where A, B are effectively constants (not depending on m), and A(m)
+ * and B(m) are functions. This is equal to solving
+ *
+ * 0 = f1 * (A + A(m)) / (B + B(m)) - (m - f1 - f2)
+ *
+ * Instead of looking for the exact solution to this equation (which
+ * might be fractional), we'll look for a natural number minimizing
+ * the absolute difference. Number of (distinct) elements is a natural
+ * number, and we don't mind if the number os slightly wrong. It's
+ * just an estimate, after all. The error from sampling will be much
+ * worse in most cases.
+ *
+ * We know the acceptable values of 'm' are [d,N] where 'd' is the number
+ * of distinct elements in the sample, and N is the number of rows in
+ * the table (not just the sample). For large tables (billions of rows)
+ * that'd be quite time-consuming to compute, so we'll approximate the
+ * solution by gradually increasing the step to ~1% of the current value
+ * of 'm'. This will make it much faster and yet very accurate.
+ *
+ * All this of course assumes the function behaves reasonably (not
+ * oscillating etc.), but that's a safe assumption as the estimator
+ * would perform terribly otherwise.
+ */
+static double
+optimize_estimate(int total_rows, int sample_rows, int d, int *f, int f_max)
+{
+ int i, m;
+ double A = 0.0, B = 0.0;
+ int opt_m = 0;
+ double opt_diff = total_rows;
+ int step = 1;
+ int ndistinct;
+
+ /* compute the 'constant' parts of the equality (A, B) */
+ for (i = 3; i <= f_max; i++)
+ {
+ double p = i / (double)sample_rows;
+ A += pow((1.0 - p), sample_rows ) * f[i];
+ B += i * pow((1.0 - p), sample_rows-1) * f[i];
+ }
+
+ /* find the 'm' value minimizing the difference */
+ for (m = 1; m <= total_rows; m += step)
+ {
+ int k = (f[1] + 2*f[2]);
+ double q = k / ((double)(sample_rows * 2 * m));
+
+ double A_m = A + m * pow((1 - q), sample_rows );
+ double B_m = B + k * pow((1 - q), sample_rows-1);
+
+ double diff = fabs(f[1] * (A_m / B_m) - (m - f[1] - f[2]));
+
+ /* if this is a better solution */
+ if (diff < opt_diff)
+ {
+ opt_diff = diff;
+ opt_m = m;
+ }
+
+ /* tweak the step to 1% to make it faster */
+ step = ((int)(0.01 * m) > 1) ? (int)(0.01 * m) : 1;
+ }
+
+ /* compute the final estimate */
+ ndistinct = d + opt_m - f[1] - f[2];
+
+ /* sanity checks that the estimate is within [d,total_rows] */
+ if (ndistinct < d)
+ ndistinct = d;
+ else if (ndistinct > total_rows)
+ ndistinct = total_rows;
+
+ return ndistinct;
+}
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-05 06:46 Simon Riggs <simon@2ndQuadrant.com>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-12-05 06:46 UTC (permalink / raw)
To: Merlin Moncure <mmoncure@gmail.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 30 September 2014 at 05:53, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 29 September 2014 16:00, Merlin Moncure <mmoncure@gmail.com> wrote:
>> On Fri, Sep 26, 2014 at 3:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>>> The problem, as I see it, is different. We assume that if there are
>>> 100 distinct values and you use LIMIT 1 that you would only need to
>>> scan 1% of rows. We assume that the data is arranged in the table in a
>>> very homogenous layout. When data is not, and it seldom is, we get
>>> problems.
>>
>> Hm, good point -- 'data proximity'. At least in theory, can't this be
>> measured and quantified? For example, given a number of distinct
>> values, you could estimate the % of pages read (or maybe non
>> sequential seeks relative to the number of pages) you'd need to read
>> all instances of a particular value in the average (or perhaps the
>> worst) case. One way of trying to calculate that would be to look at
>> proximity of values in sampled pages (and maybe a penalty assigned for
>> high update activity relative to table size). Data proximity would
>> then become a cost coefficient to the benefits of LIMIT.
>
> The necessary first step to this is to realise that we can't simply
> apply the LIMIT as a reduction in query cost, in all cases.
>
> The way I'm seeing it, you can't assume the LIMIT will apply to any
> IndexScan that doesn't have an index condition. If it has just a
> filter, or nothing at all, just an ordering then it could easily scan
> the whole index if the stats are wrong.
>
> So plans like this could be wrong, by assuming the scan will end
> earlier because of the LIMIT than it actually will.
>
> Limit
> IndexScan (no index cond)
>
> Limit
> NestJoin
> IndexScan (no index cond)
> SomeScan
>
> Limit
> NestJoin
> NestJoin
> IndexScan (no index cond)
> SomeScan
> SomeScan
>
> and deeper...
>
> I'm looking for a way to identify and exclude such plans, assuming
> that this captures at least some of the problem plans.
After looking at this for some time I now have a patch that solves this.
It relies on the observation that index scans with no bounded quals
don't play nicely with LIMIT. The solution relies upon the point that
LIMIT does not reduce the startup cost of plans, only the total cost.
So we can solve the problem by keeping the total cost estimate, just
move some of that into startup cost so LIMIT does not reduce costs as
much as before.
It's a simple patch, but it solves the test cases I know about and
does almost nothing to planning time.
I tried much less subtle approaches involving direct prevention of
LIMIT pushdown but the code was much too complex for my liking.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
avoid_limit_pushdown.v3.patch (application/octet-stream, 1.2K) download
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index ea9150b..ff95e9c 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6455,6 +6455,25 @@ btcostestimate(PG_FUNCTION_ARGS)
costs.indexTotalCost += costs.num_sa_scans * descentCost;
/*
+ * If there are no indexBoundQuals, then adjust the startup cost to
+ * account for the cost of scanning non-matching rows. This is
+ * important for when we apply the effect of LIMIT clauses to the
+ * eventual path costs.
+ */
+ if (indexBoundQuals == NULL)
+ {
+ /*
+ * Our problem here is that we do not know how many non-matching
+ * rows will need to be scanned. In the best case there will be
+ * zero non-matching rows scanned, though in the worst case it
+ * will include all non-matching rows. So lets take a risk
+ * viewpoint and assume that half of the estimated index cost
+ * will be startup cost.
+ */
+ costs.indexStartupCost = costs.indexTotalCost / 2;
+ }
+
+ /*
* If we can get an estimate of the first column's ordering correlation C
* from pg_statistic, estimate the index correlation as C for a
* single-column index, or C * 0.75 for multiple columns. (The idea here
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-05 15:45 Merlin Moncure <mmoncure@gmail.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Merlin Moncure @ 2014-12-05 15:45 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Fri, Dec 5, 2014 at 12:46 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 30 September 2014 at 05:53, Simon Riggs <simon@2ndquadrant.com> wrote:
>> On 29 September 2014 16:00, Merlin Moncure <mmoncure@gmail.com> wrote:
>>> On Fri, Sep 26, 2014 at 3:06 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>>>> The problem, as I see it, is different. We assume that if there are
>>>> 100 distinct values and you use LIMIT 1 that you would only need to
>>>> scan 1% of rows. We assume that the data is arranged in the table in a
>>>> very homogenous layout. When data is not, and it seldom is, we get
>>>> problems.
>>>
>>> Hm, good point -- 'data proximity'. At least in theory, can't this be
>>> measured and quantified? For example, given a number of distinct
>>> values, you could estimate the % of pages read (or maybe non
>>> sequential seeks relative to the number of pages) you'd need to read
>>> all instances of a particular value in the average (or perhaps the
>>> worst) case. One way of trying to calculate that would be to look at
>>> proximity of values in sampled pages (and maybe a penalty assigned for
>>> high update activity relative to table size). Data proximity would
>>> then become a cost coefficient to the benefits of LIMIT.
>>
>> The necessary first step to this is to realise that we can't simply
>> apply the LIMIT as a reduction in query cost, in all cases.
>>
>> The way I'm seeing it, you can't assume the LIMIT will apply to any
>> IndexScan that doesn't have an index condition. If it has just a
>> filter, or nothing at all, just an ordering then it could easily scan
>> the whole index if the stats are wrong.
>>
>> So plans like this could be wrong, by assuming the scan will end
>> earlier because of the LIMIT than it actually will.
>>
>> Limit
>> IndexScan (no index cond)
>>
>> Limit
>> NestJoin
>> IndexScan (no index cond)
>> SomeScan
>>
>> Limit
>> NestJoin
>> NestJoin
>> IndexScan (no index cond)
>> SomeScan
>> SomeScan
>>
>> and deeper...
>>
>> I'm looking for a way to identify and exclude such plans, assuming
>> that this captures at least some of the problem plans.
>
> After looking at this for some time I now have a patch that solves this.
>
> It relies on the observation that index scans with no bounded quals
> don't play nicely with LIMIT. The solution relies upon the point that
> LIMIT does not reduce the startup cost of plans, only the total cost.
> So we can solve the problem by keeping the total cost estimate, just
> move some of that into startup cost so LIMIT does not reduce costs as
> much as before.
>
> It's a simple patch, but it solves the test cases I know about and
> does almost nothing to planning time.
>
> I tried much less subtle approaches involving direct prevention of
> LIMIT pushdown but the code was much too complex for my liking.
Neat -- got any test cases (would this have prevented OP's problem)?
merlin
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-05 16:04 Simon Riggs <simon@2ndQuadrant.com>
parent: Merlin Moncure <mmoncure@gmail.com>
0 siblings, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-12-05 16:04 UTC (permalink / raw)
To: Merlin Moncure <mmoncure@gmail.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 6 December 2014 at 00:45, Merlin Moncure <mmoncure@gmail.com> wrote:
> Neat -- got any test cases (would this have prevented OP's problem)?
No test case was posted, so I am unable to confirm.
A test case I produced that appears to be the same issue is fixed.
I await confirmation from the OP.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-10 01:46 Josh Berkus <josh@agliodbs.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Josh Berkus @ 2014-12-10 01:46 UTC (permalink / raw)
To: Simon Riggs <simon@2ndQuadrant.com>; Merlin Moncure <mmoncure@gmail.com>; +Cc: pgsql-performance
On 12/05/2014 08:04 AM, Simon Riggs wrote:
> On 6 December 2014 at 00:45, Merlin Moncure <mmoncure@gmail.com> wrote:
>
>> Neat -- got any test cases (would this have prevented OP's problem)?
>
> No test case was posted, so I am unable to confirm.
>
> A test case I produced that appears to be the same issue is fixed.
>
> I await confirmation from the OP.
>
So that's proprietary/confidential data. However, the company involved
has a large testbed and I could test their data using a patched version
of Postgres. In 3 months their data distribution has drifted, so I'll
need to do some work to recreate the original bad plan circumstances.
I'll keep you posted on how the patch works for that setup.
It would be great to come up with a generic/public test for a bad
abort-early situation. Ideas?
--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-10 02:09 Simon Riggs <simon@2ndQuadrant.com>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 0 replies; 60+ messages in thread
From: Simon Riggs @ 2014-12-10 02:09 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Merlin Moncure <mmoncure@gmail.com>; pgsql-performance
On 10 December 2014 at 10:46, Josh Berkus <josh@agliodbs.com> wrote:
> On 12/05/2014 08:04 AM, Simon Riggs wrote:
>> On 6 December 2014 at 00:45, Merlin Moncure <mmoncure@gmail.com> wrote:
>>
>>> Neat -- got any test cases (would this have prevented OP's problem)?
>>
>> No test case was posted, so I am unable to confirm.
>>
>> A test case I produced that appears to be the same issue is fixed.
>>
>> I await confirmation from the OP.
>>
>
> So that's proprietary/confidential data. However, the company involved
> has a large testbed and I could test their data using a patched version
> of Postgres. In 3 months their data distribution has drifted, so I'll
> need to do some work to recreate the original bad plan circumstances.
> I'll keep you posted on how the patch works for that setup.
>
> It would be great to come up with a generic/public test for a bad
> abort-early situation. Ideas?
If you could contribute that, it would be welcome.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-12 03:22 Simon Riggs <simon@2ndQuadrant.com>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-12-12 03:22 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 30 September 2014 at 10:25, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 30 September 2014 00:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The existing cost estimation
>> code effectively assumes that they're perfectly uniformly distributed;
>> which is a good average-case assumption but can be horribly wrong in
>> the worst case.
>
> Agreed. This is the main observation from which we can work.
>
>> If we could settle on some other model for the probable distribution
>> of the matching tuples, we could adjust the cost estimates for LIMIT
>> accordingly. I have not enough statistics background to know what a
>> realistic alternative would be.
>
> I'm not sure that the correlation alone is sufficient to be able to do
> that. We'd need to estimate where the values looked for are likely to
> be wrt other values, then increase estimate accordingly. That sounds
> like a lot of pushups grovelling through quals and comparing against
> stats. So my thinking is actually to rule that out, unless you've some
> ideas for how to do that?
>
>> Another possibility is to still assume a uniform distribution but estimate
>> for, say, a 90% probability instead of 50% probability that we'll find
>> enough tuples after scanning X amount of the table. Again, I'm not too
>> sure what that translates to in terms of the actual math, but it sounds
>> like something a statistics person could do in their sleep.
The problem is one of risk. Whatever distribution we use, it will be
wrong in some cases and good in others.
For example, if we look at "10 Most Recent Calls" for a user, then
frequent users would have one distribution, infrequent users another.
So we have multiple distributions in the same data. We just can't hold
enough information to make sense of this.
Think about how much data needs to be scanned if the user has only done 9 calls.
What I've done in the past is to rewrite the query in different ways
to force different plans, then call each plan depending upon the user
characteristics. This is can also be done with hints, in a more
ignorant way.
>> I do not think we should estimate for the worst case though. If we do,
>> we'll hear cries of anguish from a lot of people, including many of the
>> same ones complaining now, because the planner stopped picking fast-start
>> plans even for cases where they are orders of magnitude faster than the
>> alternatives.
>
> Fast start plans still make sense when performing an IndexScan with no
> filter conditions. Those types of plan should not be changed from
> current costing - they are accurate, good and very important because
> of their frequency in real workloads.
>
> What I think we are seeing is Ordered plans being selected too often
> in preference to Sorted plans when we make selectivity or stats
> errors. As well as data distributions that aren't correctly described
> by the statistics causing much longer execution times.
>
> Here are some plan selection strategies
>
> * Cost based - attempt to exactly calculate the cost based upon
> existing stats - increase the complexity of cost calc to cover other
> aspects. Even if we do that, these may not be that helpful in covering
> the cases where the stats turn out to be wrong.
>
> * Risk based - A risk adjusted viewpoint would be that we should treat
> the cost as mid-way between the best and the worst. The worst is
> clearly scanning (100% - N) of the tuples, the best is just N tuples.
> So we should be costing scans with excess filter conditions as a (100%
> Scan)/2, no matter the conditions, based purely upon risk.
>
> * Simplified heuristic - deselect ordered plans when they are driven
> from scans without quals or indexscans with filters, since the risk
> adjusted cost is likely to be higher than the sorted cost. Inspecting
> the plan tree for this could be quite costly, so would only be done
> when the total cost is $high, prior to it being adjusted by LIMIT.
>
>
> In terms of practical steps... I suggest the following:
>
> * Implement enable_orderedscan = on (default) | off. A switch to allow
> plans to de-select ordered plans, so we can more easily see the
> effects of such plans in the wild.
>
> * Code heuristic approach - I can see where to add my heuristic in the
> grouping planner. So we just need to do a left? deep search of the
> plan tree looking for scans of the appropriate type and bail out if we
> find one.
After looking at this for some time I now have a patch that solves this.
It relies on the observation that index scans with no bounded quals
don't play nicely with LIMIT. The solution relies upon the point that
LIMIT does not reduce the startup cost of plans, only the total cost.
So we can solve the problem by keeping the total cost estimate, just
move some of that into startup cost so LIMIT does not reduce costs as
much as before.
It's a simple patch, but it solves the test cases I know about and
does almost nothing to planning time.
I tried much less subtle approaches involving direct prevention of
LIMIT pushdown but the code was much too complex for my liking.
- - -
The only other practical way to do this would be to have a
LimitPlanDisaster node
LimitPlanDisaster
-> PreSortedPath
-> CheapestPath
The PlanDisaster node would read the PreSortedPath for costlimit C
After we reach the limit we switch to the CheapestPath and execute
that instead for the remainder of the Limit.
Or we could do time limits, just harder to make that make sense.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
avoid_limit_pushdown.v4.patch (application/octet-stream, 1.7K) download
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 659daa2..b85b001 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -454,6 +454,34 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
path->path.startup_cost = startup_cost;
path->path.total_cost = startup_cost + run_cost;
+
+ /*
+ * If we have no indexquals then we guesstimate that the startup
+ * cost will be half of the total cost of the query.
+ *
+ * This is a risk-weighted viewpoint; we don't know an accurate
+ * value because we don't keep statistics in sufficient detail.
+ * The minimum startup cost could be almost zero, whereas the
+ * maximum startup cost would be paid when we had to scan the
+ * whole index before we found any tuples. The worst case is
+ * frequently seen in practice, e.g. where scans search
+ * for data not present within the table or where the user
+ * requests LIMIT 10 but there are only 9 matching tuples.
+ *
+ * It might occur to you that we could get a better value for
+ * the startup cost if we had correlation statistics between
+ * columns. That would still be only an estimate since the
+ * distribution of values does vary wildly in practice, based
+ * upon specific values. e.g. finding the last 10 events from
+ * a specific user varies considerably depending upon the user.
+ *
+ * The main effect of this is that it prevents a LIMIT clause
+ * from reducing the cost of index scans without quals,
+ * however this heuristic is our best principled estimate
+ * of the true startup cost, not just a hack to make LIMIT work.
+ */
+ if (path->indexquals == NIL)
+ path->path.startup_cost = path->path.total_cost / 2.0;
}
/*
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-12 03:31 Simon Riggs <simon@2ndQuadrant.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-12-12 03:31 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 12 December 2014 at 03:22, Simon Riggs <simon@2ndquadrant.com> wrote:
> It's a simple patch, but it solves the test cases I know about and
> does almost nothing to planning time.
Test cases attached. The files marked "pettus_*" are written up from
Christophe Pettus' blog.
The other test case is one of my own devising, based upon recent
customer problems.
The "10 most recent calls" is a restatement of actual problems seen in the past.
Also attached is a new parameter called enable_sortedpath which can be
used to turn on/off the sorted path generated by the planner.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
sortedpath.sql (application/octet-stream, 513B) download
pettus_limit.sql (application/octet-stream, 227B) download
pettus_sel.sql (application/octet-stream, 364B) download
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2014-12-17 07:55 Simon Riggs <simon@2ndQuadrant.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Simon Riggs @ 2014-12-17 07:55 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On 12 December 2014 at 03:31, Simon Riggs <simon@2ndquadrant.com> wrote:
> Also attached is a new parameter called enable_sortedpath which can be
> used to turn on/off the sorted path generated by the planner.
Now with attachment. (Thanks Jeff!)
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Attachments:
enable_sorted_path.v1a.patch (application/octet-stream, 3.3K) download
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 659daa2..e97d2fc 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -112,6 +112,7 @@ bool enable_indexonlyscan = true;
bool enable_bitmapscan = true;
bool enable_tidscan = true;
bool enable_sort = true;
+bool enable_sortedpath = true;
bool enable_hashagg = true;
bool enable_nestloop = true;
bool enable_material = true;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index f752ecc..1b38058 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1179,7 +1179,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
standard_qp_extra qp_extra;
RelOptInfo *final_rel;
Path *cheapest_path;
- Path *sorted_path;
+ Path *sorted_path = NULL;
Path *best_path;
long numGroups = 0;
AggClauseCosts agg_costs;
@@ -1393,8 +1393,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
*/
cheapest_path = final_rel->cheapest_total_path;
- sorted_path =
- get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
+ if (enable_sortedpath)
+ sorted_path =
+ get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
root->query_pathkeys,
NULL,
tuple_fraction);
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index b1bff7f..6d87f3e 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -762,6 +762,15 @@ static struct config_bool ConfigureNamesBool[] =
NULL, NULL, NULL
},
{
+ {"enable_sortedpath", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables the planner's use of implicitly ordered steps."),
+ NULL
+ },
+ &enable_sortedpath,
+ true,
+ NULL, NULL, NULL
+ },
+ {
{"enable_hashagg", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of hashed aggregation plans."),
NULL
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index b053659..8e048c7 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -278,6 +278,7 @@
#enable_nestloop = on
#enable_seqscan = on
#enable_sort = on
+#enable_sortedpath = on
#enable_tidscan = on
# - Planner Cost Constants -
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 75e2afb..ec1b366 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -56,6 +56,7 @@ extern bool enable_indexonlyscan;
extern bool enable_bitmapscan;
extern bool enable_tidscan;
extern bool enable_sort;
+extern bool enable_sortedpath;
extern bool enable_hashagg;
extern bool enable_nestloop;
extern bool enable_material;
diff --git a/src/test/regress/expected/rangefuncs.out b/src/test/regress/expected/rangefuncs.out
index 7991e99..52b8d4f 100644
--- a/src/test/regress/expected/rangefuncs.out
+++ b/src/test/regress/expected/rangefuncs.out
@@ -11,8 +11,9 @@ SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
enable_nestloop | on
enable_seqscan | on
enable_sort | on
+ enable_sortedpath | on
enable_tidscan | on
-(11 rows)
+(12 rows)
CREATE TABLE foo2(fooid int, f2 int);
INSERT INTO foo2 VALUES(1, 11);
* Re: Yet another abort-early plan disaster on 9.3
@ 2015-02-13 07:16 Michael Paquier <michael.paquier@gmail.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 60+ messages in thread
From: Michael Paquier @ 2015-02-13 07:16 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Merlin Moncure <mmoncure@gmail.com>; Josh Berkus <josh@agliodbs.com>; pgsql-performance
On Wed, Dec 17, 2014 at 4:55 PM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 12 December 2014 at 03:31, Simon Riggs <simon@2ndquadrant.com> wrote:
>
> > Also attached is a new parameter called enable_sortedpath which can be
> > used to turn on/off the sorted path generated by the planner.
>
> Now with attachment. (Thanks Jeff!)
>
Moved this patch to CF 2015-02 because it did not receive any reviews.
Better to not lose track of it.
--
Michael
^ permalink raw reply [nested|flat] 60+ messages in thread
* Re: Yet another abort-early plan disaster on 9.3
@ 2015-11-05 09:45 Evgeniy Shishkin <itparanoia@gmail.com>
parent: Michael Paquier <michael.paquier@gmail.com>
0 siblings, 0 replies; 60+ messages in thread
From: Evgeniy Shishkin @ 2015-11-05 09:45 UTC (permalink / raw)
To: pgsql-performance
Sorry for disrupting the thread,
i am wondering will it be possible to use BRIN indexes to better estimate distribution?
I mean create btree index and brin index,
probe brin during planning and estimate if abort early plan with btree will be better.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 60+ messages in thread
end of thread, other threads:[~2015-11-05 09:45 UTC | newest]
Thread overview: 60+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2014-09-18 00:11 Yet another abort-early plan disaster on 9.3 Josh Berkus <josh@agliodbs.com>
2014-09-19 17:15 ` Merlin Moncure <mmoncure@gmail.com>
2014-09-19 18:40 ` Josh Berkus <josh@agliodbs.com>
2014-09-20 06:38 ` Greg Stark <stark@mit.edu>
2014-09-20 11:51 ` Claudio Freire <klaussfreire@gmail.com>
2014-09-20 15:01 ` Tom Lane <tgl@sss.pgh.pa.us>
2014-09-20 18:33 ` Josh Berkus <josh@agliodbs.com>
2014-09-22 13:55 ` Merlin Moncure <mmoncure@gmail.com>
2014-09-22 23:56 ` Josh Berkus <josh@agliodbs.com>
2014-09-26 08:06 ` Simon Riggs <simon@2ndquadrant.com>
2014-09-29 15:00 ` Merlin Moncure <mmoncure@gmail.com>
2014-09-29 20:53 ` Simon Riggs <simon@2ndquadrant.com>
2014-09-29 23:00 ` Tom Lane <tgl@sss.pgh.pa.us>
2014-09-30 02:12 ` Gavin Flower <GavinFlower@archidevsys.co.nz>
2014-09-30 16:54 ` Jeff Janes <jeff.janes@gmail.com>
2014-09-30 21:11 ` Gavin Flower <GavinFlower@archidevsys.co.nz>
2014-09-30 22:14 ` Merlin Moncure <mmoncure@gmail.com>
2014-09-30 09:25 ` Simon Riggs <simon@2ndquadrant.com>
2014-09-30 11:34 ` Graeme B. Bell <grb@skogoglandskap.no>
2014-09-30 15:59 ` Claudio Freire <klaussfreire@gmail.com>
2014-09-30 16:32 ` Tom Lane <tgl@sss.pgh.pa.us>
2014-09-30 17:07 ` Graeme B. Bell <grb@skogoglandskap.no>
2014-12-12 03:22 ` Simon Riggs <simon@2ndQuadrant.com>
2014-12-12 03:31 ` Simon Riggs <simon@2ndQuadrant.com>
2014-12-17 07:55 ` Simon Riggs <simon@2ndQuadrant.com>
2015-02-13 07:16 ` Michael Paquier <michael.paquier@gmail.com>
2015-11-05 09:45 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-12-05 06:46 ` Simon Riggs <simon@2ndQuadrant.com>
2014-12-05 15:45 ` Merlin Moncure <mmoncure@gmail.com>
2014-12-05 16:04 ` Simon Riggs <simon@2ndQuadrant.com>
2014-12-10 01:46 ` Josh Berkus <josh@agliodbs.com>
2014-12-10 02:09 ` Simon Riggs <simon@2ndQuadrant.com>
2014-10-02 13:59 ` Ryan Johnson <ryan.johnson@cs.utoronto.ca>
2014-09-29 21:54 ` Josh Berkus <josh@agliodbs.com>
2014-09-30 07:09 ` Simon Riggs <simon@2ndquadrant.com>
2014-09-30 17:28 ` Jeff Janes <jeff.janes@gmail.com>
2014-09-30 23:01 ` Simon Riggs <simon@2ndquadrant.com>
2014-10-01 18:56 ` Josh Berkus <josh@agliodbs.com>
2014-10-02 08:19 ` Simon Riggs <simon@2ndquadrant.com>
2014-10-02 09:30 ` Peter Geoghegan <peter.geoghegan86@gmail.com>
2014-10-02 19:56 ` Josh Berkus <josh@agliodbs.com>
2014-10-03 00:54 ` Peter Geoghegan <peter.geoghegan86@gmail.com>
2014-10-03 23:41 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-03 19:58 ` Jeff Janes <jeff.janes@gmail.com>
2014-10-03 23:30 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-10 11:16 ` Greg Stark <stark@mit.edu>
2014-10-10 12:10 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-10 14:21 ` Craig James <cjames@emolecules.com>
2014-10-10 16:53 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-10 17:59 ` Craig James <cjames@emolecules.com>
2014-10-10 18:13 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-10 17:53 ` Tomas Vondra <tv@fuzzy.cz>
2014-11-21 18:38 ` Jeff Janes <jeff.janes@gmail.com>
2014-11-23 20:19 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-15 17:20 ` Josh Berkus <josh@agliodbs.com>
2014-10-15 18:02 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-17 17:25 ` Greg Stark <stark@mit.edu>
2014-10-18 17:01 ` Tomas Vondra <tv@fuzzy.cz>
2014-10-19 22:24 ` Greg Stark <stark@mit.edu>
2014-09-30 03:11 ` Greg Stark <stark@mit.edu>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox