nested loop semijoin estimates

On 05/30/15 01:20, Tomas Vondra wrote:

Notice the cost - it's way lover than the previous plan (9.2 vs
~111k), yet this plan was not chosen. So either the change broke
something (e.g. by violating some optimizer assumption), or maybe
there's a bug somewhere else ...

After a bit more investigation, what I think is happening here is
add_path() does not realize this is a SEMI join and a single tuple is
enough, and discards the simple indexscan path in favor of the bitmap
index scan as that seems cheaper when scanning everything.

So not really a bug, but maybe 'consider_startup' would help?

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

On 05/30/15 03:52, Tomas Vondra wrote:

On 05/30/15 01:20, Tomas Vondra wrote:

Notice the cost - it's way lover than the previous plan (9.2 vs
~111k), yet this plan was not chosen. So either the change broke
something (e.g. by violating some optimizer assumption), or maybe
there's a bug somewhere else ...

After a bit more investigation, what I think is happening here is
add_path() does not realize this is a SEMI join and a single tuple is
enough, and discards the simple indexscan path in favor of the bitmap
index scan as that seems cheaper when scanning everything.

So not really a bug, but maybe 'consider_startup' would help?

A bit more info - the reason why the IndexPath gets discarded (in favor
of BitmapHeapScan) seems to be twofold:

(a) Semijoin does no imply 'consider_startup' for the inner path, so it
gets discarded by the BitmapHeapScan, as it has lower total cost.

I'm not sure where exactly the consider_startup should be set, so
I've forced that at the beginning on add_path() to see what happens.
Sadly, this alone is not sufficient, because of the next point.

(b) To actually use startup costs in compare_path_costs_fuzzily, there
is an additional condition about handling parameterized paths, as
explained in this comment:

* This function also includes special hacks to support a policy
* enforced by its sole caller, add_path(): paths that have any
* parameterization cannot win comparisons on the grounds of having
* cheaper startup cost, since we deem only total cost to be of
* interest for a parameterized path. (Unparameterized paths are
* more common, so we check for this case last.)

so the startup_cost comparisons look like this:

if (consider_startup &&
path2->startup_cost > path1->startup_cost * fuzz_factor &&
path1->param_info == NULL)

Of course, path1 (IndexPath) actually has parameters, which makes
the whole condition false, and the IndexPath gets discarded :-(

ISTM the reported test case seems like a counter example to the
policy, so maybe this should really be relaxed somehow.

To see what happens, I tweaked both (a) and (b) by forcing

consider_startup = true

at the beginning of add_path(), and removing the (param_info==NULL)
conditions (patch attached). It also includes the run_cost tweak
mentioned in the first message.

I'm not claiming this is the correct fix, the only goal was to see what
happens. And it really does produce the 'right' plan:

QUERY PLAN
-----------------------------------------------------------------------
Nested Loop Semi Join (cost=0.99..9.20 rows=1 width=74)
-> Index Scan using term_facttablename_columnname_idx on term t
(cost=0.55..8.57 rows=1 width=74)
Index Cond: (((facttablename)::text =
'facttable_stat_fta4'::text) AND ((columnname)::text =
'berechnungsart'::text))
-> Index Only Scan using facttable_stat_fta4_berechnungsart_idx on
facttable_stat_fta4 f (cost=0.43..310525.02 rows=4870496 width=2)
Index Cond: (berechnungsart = (t.term)::text)
(5 rows)

If I get the comments in pathnode.c about the startup_cost policy, it's
"only" an optimization to reduce the number of parameterized paths, so I
believe this does not break anything. Also, it's no fun if the planning
is a tad faster, but the query runtime is 1000x higher.

Ideas how to relax the policy without significant impact on optimizer?

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

I wonder whether the
run_cost += inner_run_cost;
is actually correct, because this pretty much means we assume scanning
the whole inner relation (once). Wouldn't something like this be more
appropriate?
run_cost += inner_run_cost * inner_scan_frac;

Well, not entirely. The reason why it's like that is explained (evidently
not well enough) in the comment just above:

* A complicating factor is that rescans may be cheaper than first
* scans. If we never scan all the way to the end of the inner rel,
* it might be (depending on the plan type) that we'd never pay the
* whole inner first-scan run cost. However it is difficult to
* estimate whether that will happen, so be conservative and always
* charge the whole first-scan cost once.

The case this is concerned about is something like a Materialize node
above a scan node. The Materialize node makes rescans much cheaper than
the original scan, but only once the data has been fetched to begin with.
So, while the first successful probe should indeed have cost something
like inner_run_cost * inner_scan_frac, once we make this change it's
no longer legitimate for final_cost_nestloop to suppose that the cost
of an unsuccessful probe is just inner_rescan_run_cost. Any unsuccessful
probe will mean we must incur all of inner_run_cost in order to complete
the underlying scan and fully load the Materialize node.

However, in the case where has_indexed_join_quals() is true, I think
your change is correct, because then all the scans will either stop
on the first tuple or quickly determine that no tuples satisfy the
indexquals. (Also, in the cases where has_indexed_join_quals() can
succeed, rescan cost is the same as initial scan cost anyhow.)

So what this seems to mean is that for SEMI/ANTI join cases, we have to
postpone all of the inner scan cost determination to final_cost_nestloop,
so that we can do this differently depending on whether
has_indexed_join_quals() is true. That's a little bit annoying because it
will mean we take the shortcut exit less often; but since SEMI/ANTI joins
aren't that common, it's probably not going to be a big planning time hit.

Not sure yet about your other point about the indexscan getting rejected
too soon. That doesn't seem to be happening for me, at least not in HEAD.

regards, tom lane

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

On 05/30/15 21:50, Tom Lane wrote:

So what this seems to mean is that for SEMI/ANTI join cases, we have
to postpone all of the inner scan cost determination to
final_cost_nestloop, so that we can do this differently depending on
whether has_indexed_join_quals() is true. That's a little bit
annoying because it will mean we take the shortcut exit less often;
but since SEMI/ANTI joins aren't that common, it's probably not
going to be a big planning time hit.

Yay! So I wasn't entirely wrong on this. Do you plan to make this
change, or will you leave that on me?

Not sure yet about your other point about the indexscan getting
rejected too soon. That doesn't seem to be happening for me, at least
not in HEAD.

FWIW I can reproduce that reliably on current HEAD, with the test case I
sent yesterday. I'm using default config (as produced by initdb).

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

I wrote:

So what this seems to mean is that for SEMI/ANTI join cases, we have to
postpone all of the inner scan cost determination to final_cost_nestloop,
so that we can do this differently depending on whether
has_indexed_join_quals() is true. That's a little bit annoying because it
will mean we take the shortcut exit less often; but since SEMI/ANTI joins
aren't that common, it's probably not going to be a big planning time hit.

Attached is a draft patch for that. It fixes the problem for me:

Nested Loop Semi Join (cost=0.99..9.09 rows=1 width=74) (actual time=0.591..1.554 rows=2 loops=1)
-> Index Scan using term_facttablename_columnname_idx on term t (cost=0.55..8.57 rows=1 width=74) (actual time=0.022..0.025 rows=2 loops=1)
Index Cond: (((facttablename)::text = 'facttable_stat_fta4'::text) AND ((columnname)::text = 'berechnungsart'::text))
-> Index Only Scan using facttable_stat_fta4_berechnungsart_idx on facttable_stat_fta4 f (cost=0.43..143244.98 rows=5015134 width=2) (actual time=0.759..0.759 rows=1 loops=2)
Index Cond: (berechnungsart = (t.term)::text)
Heap Fetches: 0
Planning time: 0.545 ms
Execution time: 1.615 ms

Not sure yet about your other point about the indexscan getting rejected
too soon. That doesn't seem to be happening for me, at least not in HEAD.

I do see something of the sort if I turn off enable_indexonlyscan.
Not sure about a good fix for that aspect. It may not be terribly
critical, since AFAICS index-only scans generally ought to apply
in these cases.

regards, tom lane

Hi,

On 05/30/15 23:16, Tom Lane wrote:

I wrote:

So what this seems to mean is that for SEMI/ANTI join cases, we have to
postpone all of the inner scan cost determination to final_cost_nestloop,
so that we can do this differently depending on whether
has_indexed_join_quals() is true. That's a little bit annoying because it
will mean we take the shortcut exit less often; but since SEMI/ANTI joins
aren't that common, it's probably not going to be a big planning time hit.

Attached is a draft patch for that. It fixes the problem for me:

Nested Loop Semi Join (cost=0.99..9.09 rows=1 width=74) (actual time=0.591..1.554 rows=2 loops=1)
-> Index Scan using term_facttablename_columnname_idx on term t (cost=0.55..8.57 rows=1 width=74) (actual time=0.022..0.025 rows=2 loops=1)
Index Cond: (((facttablename)::text = 'facttable_stat_fta4'::text) AND ((columnname)::text = 'berechnungsart'::text))
-> Index Only Scan using facttable_stat_fta4_berechnungsart_idx on facttable_stat_fta4 f (cost=0.43..143244.98 rows=5015134 width=2) (actual time=0.759..0.759 rows=1 loops=2)
Index Cond: (berechnungsart = (t.term)::text)
Heap Fetches: 0
Planning time: 0.545 ms
Execution time: 1.615 ms

Seems to be working OK, but I still do get a Bitmap Heap Scan there (but
more about that later).

Do you plan to push that into 9.5, or 9.6? I assume it's a behavior
change so that no back-patching, right?

Not sure yet about your other point about the indexscan getting
rejected too soon. That doesn't seem to be happening for me, at
least not in HEAD.

I do see something of the sort if I turn off enable_indexonlyscan.
Not sure about a good fix for that aspect. It may not be terribly
critical, since AFAICS index-only scans generally ought to apply
in these cases.

Hmmm, a VACUUM FREEZE fixed that for me. The reason is that right after
loading the testcase, I do get this:

Index Only Scan using facttable_stat_fta4_berechnungsart_idx
on facttable_stat_fta4 f (cost=0.43..280220.51 rows=5000016 width=2)

and after VACUUM FREEZE I do get this:

Index Only Scan using facttable_stat_fta4_berechnungsart_idx
on facttable_stat_fta4 f (cost=0.43..142344.43 rows=5000000 width=2)

and the Bitmap Heap Scan case looks like this:

Bitmap Heap Scan on facttable_stat_fta4 f
(cost=93594.56..200342.76 rows=5000016 width=2)

so it's cheaper (total cost) than the index only scan before freezing,
and more expensive than index only scan after freezing.

I still think this is wrong (or rather "suboptimal") - there are
probably cases where even the "freezed" index only scan is more
expensive than a bitmap heap scan, and in that case the it won't be
used, although it'd be much faster.

Another example is a query with a plain index scan, e.g. consider this
slight modification of the query:

SELECT facttablename, columnname, term FROM term t WHERE
facttablename='facttable_stat_fta4' AND columnname='berechnungsart' AND
EXISTS (SELECT 1 FROM facttable_stat_fta4 f WHERE
f.berechnungsart=t.term AND einheit IS NOT NULL);

This will result in bitmap index scan no matter the visibility.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 05/30/15 23:16, Tom Lane wrote:

Attached is a draft patch for that. It fixes the problem for me:

Seems to be working OK, but I still do get a Bitmap Heap Scan there (but
more about that later).

Attached is an incremental patch (on top of the previous one) to allow
startup cost of parameterized paths to be considered when the relation
is the RHS of a semi or anti join. It seems reasonably clean except
for one thing: logically, we perhaps should remove the checks on
path->param_info from the last half of compare_path_costs_fuzzily(),
so as to increase the symmetry between parameterized paths and
unparameterized ones. However, when I did that, I got changes in some
of the regression test plans, and they didn't seem to be for the better.
So I left that alone. As-is, this patch doesn't seem to affect the
results for any existing regression tests.

Do you plan to push that into 9.5, or 9.6? I assume it's a behavior
change so that no back-patching, right?

Mumble. It's definitely a planner bug fix, and I believe that the effects
are narrowly constrained to cases where significantly better plans are
possible. So personally I'd be willing to back-patch it. But others
might see that differently, especially since it's been like this for a
long time and we only have one field complaint.

regards, tom lane

On 06/01/15 00:08, Tom Lane wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 05/30/15 23:16, Tom Lane wrote:

Attached is a draft patch for that. It fixes the problem for me:

Seems to be working OK, but I still do get a Bitmap Heap Scan there (but
more about that later).

Attached is an incremental patch (on top of the previous one) to
allow startup cost of parameterized paths to be considered when the
relation is the RHS of a semi or anti join. It seems reasonably clean
except for one thing: logically, we perhaps should remove the checks
on path->param_info from the last half of
compare_path_costs_fuzzily(), so as to increase the symmetry between
parameterized paths and unparameterized ones. However, when I did
that, I got changes in some of the regression test plans, and they
didn't seem to be for the better. So I left that alone. As-is, this
patch doesn't seem to affect the results for any existing regression
tests.

Seems to be working fine. I've tried a bunch of queries modifying the
test case in various ways, and all seem to be planned fine. I've been
unable to come up with a query that'd get planned badly.

Regarding the remaining checks in compare_path_costs_fuzzily(), isn't
that simply caused by very small data sets? For example the first
"failing" plan in join.sql looks like this:

Nested Loop Left Join (cost=0.29..22.80 rows=2 width=12)

Nested Loop Left Join (cost=0.29..22.80 rows=2 width=12)
Output: "*VALUES*".column1, i1.f1, (666)
Join Filter: ("*VALUES*".column1 = i1.f1)
-> Values Scan on "*VALUES*" (cost=0.00..0.03 rows=2 width=4)
Output: "*VALUES*".column1
-> Materialize (cost=0.29..22.64 rows=5 width=8)
Output: i1.f1, (666)
-> Nested Loop Left Join (cost=0.29..22.61 rows=5 width=8)
Output: i1.f1, 666
-> Seq Scan on public.int4_tbl i1 (cost=0.00..1.05 ...
Output: i1.f1
-> Index Only Scan using tenk1_unique2 on public....
Output: i2.unique2
Index Cond: (i2.unique2 = i1.f1)

while with the changes it'd look like this:

Hash Right Join (cost=0.34..22.70 rows=2 width=12)
Output: "*VALUES*".column1, i1.f1, (666)
Hash Cond: (i1.f1 = "*VALUES*".column1)
-> Nested Loop Left Join (cost=0.29..22.61 rows=5 width=8)
Output: i1.f1, 666
-> Seq Scan on public.int4_tbl i1 (cost=0.00..1.05 ...
Output: i1.f1
-> Index Only Scan using tenk1_unique2 on public.tenk1 ...
Output: i2.unique2
Index Cond: (i2.unique2 = i1.f1)
-> Hash (cost=0.03..0.03 rows=2 width=4)
Output: "*VALUES*".column1
-> Values Scan on "*VALUES*" (cost=0.00..0.03 rows=2 ...
Output: "*VALUES*".column1
(14 rows)

So the planner actually believes the plan to be cheaper, although only
by a tiny margin. And I see pretty much no difference in planning/exec
time (but I'm on a machine with power-management and VMs, so a lot of
random noise).

But once the int4_tbl gets bigger (say, 160k rows instead of the 5),
even the current the hash join clearly wins. Actually, it switches from
the current plan way sooner (at 500 rows it's already using the hash
join, and I see about the same timings).

I don't really see why you think those plan changes to be bad? And even
if they are, isn't that simply a matter of tuning the cost parameters?

Do you plan to push that into 9.5, or 9.6? I assume it's a
behavior change so that no back-patching, right?

Mumble. It's definitely a planner bug fix, and I believe that the
effects are narrowly constrained to cases where significantly better
plans are possible. So personally I'd be willing to back-patch it.
But others might see that differently, especially since it's been
like this for a long time and we only have one field complaint.

+1 to back-patching from me. It's true we only have one field complaint,
but I believe there are more users impacted by this. They just didn't
notice - we only really got this complaint because of the plan
discrepancy between queries that are almost exactly the same.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 06/01/15 00:08, Tom Lane wrote:

Attached is an incremental patch (on top of the previous one) to
allow startup cost of parameterized paths to be considered when the
relation is the RHS of a semi or anti join. It seems reasonably clean
except for one thing: logically, we perhaps should remove the checks
on path->param_info from the last half of
compare_path_costs_fuzzily(), so as to increase the symmetry between
parameterized paths and unparameterized ones. However, when I did
that, I got changes in some of the regression test plans, and they
didn't seem to be for the better. So I left that alone. As-is, this
patch doesn't seem to affect the results for any existing regression
tests.

Regarding the remaining checks in compare_path_costs_fuzzily(), isn't
that simply caused by very small data sets?

No, I don't think the size of the data set is the issue. The point is
that previously, if we had two parameterized paths of fuzzily the same
total cost, we'd choose which to keep based on factors other than startup
cost. If we change that part of compare_path_costs_fuzzily(), we'll be
changing the behavior in cases that are unrelated to the problem we are
trying to solve, because same-total-cost isn't going to apply to the
bitmap indexscan vs. plain indexscan cases we're worried about here.
(The places where it tends to happen are things like hash left join
vs hash right join with the inputs swapped.) I don't want to change such
cases in a patch that's meant to be back-patched; people don't like plan
instability in stable branches.

It's also not quite clear what the new rule ought to be. Rather than
treating parameterized paths exactly like regular ones, maybe we should
consider their startup cost only if consider_param_startup is true.
It remains the case that in most scenarios for parameterized paths,
startup cost really isn't that interesting and shouldn't drive choices.

Another practical problem is that the regression tests that are being
affected are specifically meant to test particular scenarios in
construction of nested-loop join plans. If the planner stops selecting
a nestloop plan there, the test is effectively broken. We could probably
rejigger the test queries to restore the intended test scenario, but that
wasn't an exercise I was in a hurry to undertake.

Anyway, bottom line is that if we want to change that, it ought to be
a separate HEAD-only patch.

Do you plan to push that into 9.5, or 9.6? I assume it's a
behavior change so that no back-patching, right?

Mumble. It's definitely a planner bug fix, and I believe that the
effects are narrowly constrained to cases where significantly better
plans are possible. So personally I'd be willing to back-patch it.
But others might see that differently, especially since it's been
like this for a long time and we only have one field complaint.

+1 to back-patching from me. It's true we only have one field complaint,
but I believe there are more users impacted by this. They just didn't
notice - we only really got this complaint because of the plan
discrepancy between queries that are almost exactly the same.

Perhaps. It seems like in many cases the planner would accidentally
choose the "right" plan anyway, because even though it was overestimating
the cost, the other alternatives would usually look even worse. So it's
hard to tell how many users will be benefited. But I'm fairly sure the
patch as posted is narrow enough that very few people would be negatively
affected.

Anybody else want to speak for or against back-patching the patch as
posted? I intentionally didn't push it in before today's releases,
but I will push it later this week if there are not objections.

regards, tom lane

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

On 06/01/2015 02:18 PM, Tom Lane wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 06/01/15 00:08, Tom Lane wrote:

Attached is an incremental patch (on top of the previous one) to
allow startup cost of parameterized paths to be considered when the
relation is the RHS of a semi or anti join. It seems reasonably clean
except for one thing: logically, we perhaps should remove the checks
on path->param_info from the last half of
compare_path_costs_fuzzily(), so as to increase the symmetry between
parameterized paths and unparameterized ones. However, when I did
that, I got changes in some of the regression test plans, and they
didn't seem to be for the better. So I left that alone. As-is, this
patch doesn't seem to affect the results for any existing regression
tests.

Regarding the remaining checks in compare_path_costs_fuzzily(), isn't
that simply caused by very small data sets?

No, I don't think the size of the data set is the issue. The point is
that previously, if we had two parameterized paths of fuzzily the same
total cost, we'd choose which to keep based on factors other than startup
cost. If we change that part of compare_path_costs_fuzzily(), we'll be
changing the behavior in cases that are unrelated to the problem we are
trying to solve, because same-total-cost isn't going to apply to the
bitmap indexscan vs. plain indexscan cases we're worried about here.
(The places where it tends to happen are things like hash left join
vs hash right join with the inputs swapped.) I don't want to change such
cases in a patch that's meant to be back-patched; people don't like plan
instability in stable branches.

It's also not quite clear what the new rule ought to be. Rather than
treating parameterized paths exactly like regular ones, maybe we should
consider their startup cost only if consider_param_startup is true.
It remains the case that in most scenarios for parameterized paths,
startup cost really isn't that interesting and shouldn't drive choices.

Another practical problem is that the regression tests that are being
affected are specifically meant to test particular scenarios in
construction of nested-loop join plans. If the planner stops selecting
a nestloop plan there, the test is effectively broken. We could probably
rejigger the test queries to restore the intended test scenario, but that
wasn't an exercise I was in a hurry to undertake.

Anyway, bottom line is that if we want to change that, it ought to be
a separate HEAD-only patch.

Do you plan to push that into 9.5, or 9.6? I assume it's a
behavior change so that no back-patching, right?

Mumble. It's definitely a planner bug fix, and I believe that the
effects are narrowly constrained to cases where significantly better
plans are possible. So personally I'd be willing to back-patch it.
But others might see that differently, especially since it's been
like this for a long time and we only have one field complaint.

+1 to back-patching from me. It's true we only have one field complaint,
but I believe there are more users impacted by this. They just didn't
notice - we only really got this complaint because of the plan
discrepancy between queries that are almost exactly the same.

Perhaps. It seems like in many cases the planner would accidentally
choose the "right" plan anyway, because even though it was overestimating
the cost, the other alternatives would usually look even worse. So it's
hard to tell how many users will be benefited. But I'm fairly sure the
patch as posted is narrow enough that very few people would be negatively
affected.

Anybody else want to speak for or against back-patching the patch as
posted? I intentionally didn't push it in before today's releases,
but I will push it later this week if there are not objections.

I would like Mark Wong to test this on DBT3, if that's possible for him.
I'm very worried about an unanticipated regression.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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

On 06/01/15 23:47, Josh Berkus wrote:

On 06/01/2015 02:18 PM, Tom Lane wrote:

Anybody else want to speak for or against back-patching the patch as
posted? I intentionally didn't push it in before today's releases,
but I will push it later this week if there are not objections.

I would like Mark Wong to test this on DBT3, if that's possible for him.
I'm very worried about an unanticipated regression.

AFAIK Mark is busy with other stuff at the moment, but I can do the
TPC-H (which DBT3 is equal to, IIRC).

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

On 06/01/2015 03:22 PM, Tomas Vondra wrote:

On 06/01/15 23:47, Josh Berkus wrote:

On 06/01/2015 02:18 PM, Tom Lane wrote:

Anybody else want to speak for or against back-patching the patch as
posted? I intentionally didn't push it in before today's releases,
but I will push it later this week if there are not objections.

I would like Mark Wong to test this on DBT3, if that's possible for him.
I'm very worried about an unanticipated regression.

AFAIK Mark is busy with other stuff at the moment, but I can do the
TPC-H (which DBT3 is equal to, IIRC).

Yeah, I just want something which has a chance of catching unanticipated
regression in queries which should be unaffected by the patch.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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

On 06/02/15 01:47, Josh Berkus wrote:

On 06/01/2015 03:22 PM, Tomas Vondra wrote:

On 06/01/15 23:47, Josh Berkus wrote:

On 06/01/2015 02:18 PM, Tom Lane wrote:

Anybody else want to speak for or against back-patching the patch as
posted? I intentionally didn't push it in before today's releases,
but I will push it later this week if there are not objections.

I would like Mark Wong to test this on DBT3, if that's possible
for him. I'm very worried about an unanticipated regression.

AFAIK Mark is busy with other stuff at the moment, but I can do
the TPC-H (which DBT3 is equal to, IIRC).

Yeah, I just want something which has a chance of catching
unanticipated regression in queries which should be unaffected by the
patch.

OK, so I did the testing today - with TPC-H and TPC-DS benchmarks. The
results are good, IMHO.

With TPC-H, I've used 1GB and 4GB datasets, and I've seen no plan
changes at all. I don't plan to run the tests on larger data sets, I do
expect the behavior to remain the same, considering the uniformity of
TPC-H data sets.

With TPC-DS (using the 63 queries supported by PostgreSQL), I've seen
two cases of plan changes - see the plans attached. In both cases
however the plan change results in much better performance. While on
master the queries took 23 and 18 seconds, with the two patches it's
only 7 and 3. This is just the 1GB dataset. I'll repeat the test with
the 4GB dataset and post an update if there are any changes.

While this can't prove there are no regressions, in these two benchmarks
the patches actually improve some of the queries.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

OK, so I did the testing today - with TPC-H and TPC-DS benchmarks. The
results are good, IMHO.

With TPC-H, I've used 1GB and 4GB datasets, and I've seen no plan
changes at all. I don't plan to run the tests on larger data sets, I do
expect the behavior to remain the same, considering the uniformity of
TPC-H data sets.

With TPC-DS (using the 63 queries supported by PostgreSQL), I've seen
two cases of plan changes - see the plans attached. In both cases
however the plan change results in much better performance. While on
master the queries took 23 and 18 seconds, with the two patches it's
only 7 and 3. This is just the 1GB dataset. I'll repeat the test with
the 4GB dataset and post an update if there are any changes.

I'm a bit disturbed by that, because AFAICS from the plans, these queries
did not involve any semi or anti joins, which should mean that the patch
would not have changed the planner's behavior. You were using the second
patch as-posted, right, without further hacking on
compare_path_costs_fuzzily?

It's possible that the change was due to random variation in ANALYZE
statistics, in which case it was just luck.

regards, tom lane

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

On 06/02/15 16:37, Tom Lane wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

OK, so I did the testing today - with TPC-H and TPC-DS benchmarks. The
results are good, IMHO.

I'm a bit disturbed by that, because AFAICS from the plans, these
queries did not involve any semi or anti joins, which should mean
that the patch would not have changed the planner's behavior. You
were using the second patch as-posted, right, without further hacking
on compare_path_costs_fuzzily?

Yes, no additional changes.

It's possible that the change was due to random variation in ANALYZE
statistics, in which case it was just luck.

I don't think so. I simply loaded the data, ran ANALYZE, and then simply
started either master or patched master. There should be no difference
in statistics, I believe. Also, the plans contain pretty much the same
row counts, but the costs differ.

For example look at the 'cs_ui' CTE, right at the beginning of the
analyze logs. The row counts are exactly the same, but the costs are
different. And it's not using semijoins or not nested loops ...

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 06/02/15 16:37, Tom Lane wrote:

It's possible that the change was due to random variation in ANALYZE
statistics, in which case it was just luck.

I don't think so. I simply loaded the data, ran ANALYZE, and then simply
started either master or patched master. There should be no difference
in statistics, I believe. Also, the plans contain pretty much the same
row counts, but the costs differ.

For example look at the 'cs_ui' CTE, right at the beginning of the
analyze logs. The row counts are exactly the same, but the costs are
different. And it's not using semijoins or not nested loops ...

The cost estimates in that CTE all look exactly the same to me, and the
actual runtime's not all that different either. The key runtime
difference in the first query seems to be in the first couple of joins
to the cs_ui CTE:

-> Nested Loop (cost=4.63..724.34 rows=16 width=67) (actual time=8346.904..14024.947 rows=117 loops=1)
Join Filter: (item.i_item_sk = store_returns.sr_item_sk)
-> Nested Loop (cost=0.29..662.07 rows=1 width=59) (actual time=8324.352..13618.106 rows=8 loops=1)
-> CTE Scan on cs_ui (cost=0.00..2.16 rows=108 width=4) (actual time=7264.670..7424.096 rows=17169 loops=1)
-> Index Scan using item_pkey on item (cost=0.29..6.10 rows=1 width=55) (actual time=0.356..0.356 rows=0 loops=17169)
Index Cond: (i_item_sk = cs_ui.cs_item_sk)
Filter: ((i_current_price >= '79'::numeric) AND (i_current_price <= '89'::numeric) AND (i_current_price >= '80'::numeric) AND (i_current_price <= '94'::numeric) AND (i_color = ANY ('{navajo,burlywood,cornflower,olive,turquoise,linen}'::bpchar[])))
Rows Removed by Filter: 1
-> Bitmap Heap Scan on store_returns (cost=4.34..62.05 rows=18 width=8) (actual time=32.525..50.662 rows=15 loops=8)
Recheck Cond: (sr_item_sk = cs_ui.cs_item_sk)
Heap Blocks: exact=117
-> Bitmap Index Scan on idx_sr_item_sk (cost=0.00..4.34 rows=18 width=0) (actual time=19.747..19.747 rows=15 loops=8)
Index Cond: (sr_item_sk = cs_ui.cs_item_sk)

vs patched

-> Nested Loop (cost=4.63..724.34 rows=16 width=67) (actual time=6867.921..7001.417 rows=117 loops=1)
Join Filter: (item.i_item_sk = store_returns.sr_item_sk)
-> Nested Loop (cost=0.29..662.07 rows=1 width=59) (actual time=6867.874..7000.211 rows=8 loops=1)
-> CTE Scan on cs_ui (cost=0.00..2.16 rows=108 width=4) (actual time=6865.792..6924.816 rows=17169 loops=1)
-> Index Scan using item_pkey on item (cost=0.29..6.10 rows=1 width=55) (actual time=0.003..0.003 rows=0 loops=17169)
Index Cond: (i_item_sk = cs_ui.cs_item_sk)
Filter: ((i_current_price >= '79'::numeric) AND (i_current_price <= '89'::numeric) AND (i_current_price >= '80'::numeric) AND (i_current_price <= '94'::numeric) AND (i_color = ANY ('{navajo,burlywood,cornflower,olive,turquoise,linen}'::bpchar[])))
Rows Removed by Filter: 1
-> Bitmap Heap Scan on store_returns (cost=4.34..62.05 rows=18 width=8) (actual time=0.025..0.116 rows=15 loops=8)
Recheck Cond: (sr_item_sk = cs_ui.cs_item_sk)
Heap Blocks: exact=117
-> Bitmap Index Scan on idx_sr_item_sk (cost=0.00..4.34 rows=18 width=0) (actual time=0.017..0.017 rows=15 loops=8)
Index Cond: (sr_item_sk = cs_ui.cs_item_sk)

Those are the exact same plans, and same cost estimates, but for some
reason the master run is 2X slower. The only explanation I can think of
is disk caching effects, or maybe hint-bit setting during the first run.
It's certainly not the planner that deserves either credit or blame for
that.

The part of this plan that's actually different is a different join order
sequence for a lot of follow-on joins that are expected to get single rows
from their other table. I think that's basically irrelevant really, but
again, this patch should not have changed anything there, since those were
plain joins not semijoins.

regards, tom lane

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

On 06/02/15 17:50, Tom Lane wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On 06/02/15 16:37, Tom Lane wrote:

It's possible that the change was due to random variation in ANALYZE
statistics, in which case it was just luck.

I don't think so. I simply loaded the data, ran ANALYZE, and then simply
started either master or patched master. There should be no difference
in statistics, I believe. Also, the plans contain pretty much the same
row counts, but the costs differ.

For example look at the 'cs_ui' CTE, right at the beginning of the
analyze logs. The row counts are exactly the same, but the costs are
different. And it's not using semijoins or not nested loops ...

The cost estimates in that CTE all look exactly the same to me, and the
actual runtime's not all that different either. The key runtime
difference in the first query seems to be in the first couple of joins
to the cs_ui CTE:

D'oh! I was looking at the timings, not costs. EINOTENOUGHCAFFEINE ...

Those are the exact same plans, and same cost estimates, but for
some reason the master run is 2X slower. The only explanation I can
think of is disk caching effects, or maybe hint-bit setting during
the first run. It's certainly not the planner that deserves either
credit or blame for that.

Yes, seems like that.

The part of this plan that's actually different is a different join
order sequence for a lot of follow-on joins that are expected to get
single rows from their other table. I think that's basically
irrelevant really, but again, this patch should not have changed
anything there, since those were plain joins not semijoins.

Yes, it's interesting. I've repeated the tests on 1GB TPC-DS dataset,
and this time I got slightly different set of plan changes. I don't see
the change in join order, for example.

Attached is the whole explain output (all 63 queries), explain.master.1
and explain.patched.1.

The are two kinds of plan changes:

1) minor cost changes (these queries contain semijoins, so it's
expected), but the plan is exactly the same

2) queries with nested loop replaced by hash join, i.e. plan on master
looks like this:

-> Nested Loop
-> Nested Loop
-> Nested Loop
-> Seq Scan
-> Index Scan
-> Index Scan
-> Materialize
-> Seq Scan

while with the patches:

-> Hash Join
-> Hash Join
-> Nested Loop
-> Seq Scan
-> Index Scan
-> Hash
-> Seq Scan
-> Hash
-> Seq Scan

This is slightly surprising, because those queries do not contain
any semijoins. Detailed explain analyze for the three queries with
different plans is attached.

At the end, I repeated the explain on master, and got exactly the same
results as at the beginning (same as explain.master.1) - so there's no
variability in statistics at all.

Another interesting thing is that these plan changes only happen after
the second patch, i.e. with nestloop-semijoin-costing-fix everything is
exactly as on master, but with consider-startup-costs-for-semijoins the
plans change.

I suspected the problem is somewhere in compare_path_costs_fuzzily() but
that doesn't seem to be the case - I've however noticed that the number
of calls to that function changes with the patch.

For example when running the query in tpcds-3.log, compare_fuzzily os
called ~1050x, but with the patch attached it's called only ~730x. I've
checked backtraces for a few of the paths that are not considered with
the patch, and all of them look like this (detailed backtrace attached):

#3 0x0000000000656cd5 in compare_path_costs_fuzzily at pathnode.c:154
#4 0x0000000000657146 in add_path at pathnode.c:438
#5 0x0000000000631bfb in try_nestloop_path at joinpath.c:347
#6 0x0000000000632931 in match_unsorted_outer at joinpath.c:900
#7 add_paths_to_joinrel at joinpath.c:225

That particular part of try_nestloop_path looks like this:

if (add_path_precheck(joinrel,
workspace.startup_cost, workspace.total_cost,
pathkeys, required_outer))
{
add_path(joinrel, (Path *)
create_nestloop_path(...);
}

I wouldn't be surprised if the problem was in add_path_precheck.
Actually, I'm quite sure that's where the problem is - particularly in
how required_outer was replaced with (!consider_startup):

consider_startup
= required_outer ? consider_param_startup : consider_startup;

If both _startup flags are false, the original required_outer value is
lost, and that changes the if() condition which was changed from

if (startup_cost >= old_path->startup_cost || required_outer)

to

if (startup_cost >= old_path->startup_cost || !consider_startup)

So, if required_outer=false and both p->_startup=false, we get
consider_startup=false irrespectedly of the required_outer value, so

(!consider_startupe) != required_outer

so that the conditions are not equivalent. And indeed, by reverting the
if condition to the previous form, we get the same plans as on master.

I don't know whether this is correct behavior or not, but in all three
cases I've observed on TPC-DS, the new plans performed better

Q1 Q2 Q3
--------------------------------------------------------------------
master 518.330 ms 466.539 ms 560.585 ms
patched 405.310 ms 340.506 ms 122.072 ms

This time I've been careful not to produce bogus numbers (also, the
explain analyze timing I mentioned in previous post were significantly
influenced by timing overhead). These results are quite stable.

A few more comments on the patch:

1) Shouldn't the CONSIDER_PATH_STARTUP_COST(p) be defined rather like
this? I mean, if it's a parametric query, use any of the flags?
And same in add_path_precheck()?

#define CONSIDER_PATH_STARTUP_COST(p) \
((p)->param_info == NULL ? (p)->parent->consider_startup :
((p)->parent->consider_param_startup ||
(p)->parent->consider_startup))

2) Is it really possible to get different values for the startup
flags on path1 and path2 in compare_path_costs_fuzzily()? If not
(if I get it right, path1->parent == path2->parent anyway), then
maybe passing that as a function parameter (just like before)
would be better. The macro probably won't be as nice, but I find
it easier to understand.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

I wrote:

I'm a bit disturbed by that, because AFAICS from the plans, these queries
did not involve any semi or anti joins, which should mean that the patch
would not have changed the planner's behavior.

After contemplating my navel for awhile, it occurred to me that maybe the
patch's changes in add_path_precheck could have caused behavioral changes
at the margins. Could you try a run without that (without the last two
hunks in pathnode.c)?

regards, tom lane

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

On 06/02/15 21:39, Tom Lane wrote:

I wrote:

I'm a bit disturbed by that, because AFAICS from the plans, these queries
did not involve any semi or anti joins, which should mean that the patch
would not have changed the planner's behavior.

After contemplating my navel for awhile, it occurred to me that maybe the
patch's changes in add_path_precheck could have caused behavioral changes
at the margins. Could you try a run without that (without the last two
hunks in pathnode.c)?

Yes, I think that's the cause. See the end of the message I sent just
before you posted this.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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