pg9.6 segfault using simple query (related to use fk for join estimates)

On Fri, Apr 29, 2016 at 7:25 PM, Stefan Huehner <stefan@huehner.org> wrote:

If you need any more info or testing done just let me know.

The information you are providing is sufficient to reproduce the
problem, thanks! I have added this bug to the list of open items for
9.6.
--
Michael

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

On 29/04/2016 13:20, Michael Paquier wrote:

On Fri, Apr 29, 2016 at 7:25 PM, Stefan Huehner <stefan@huehner.org> wrote:

If you need any more info or testing done just let me know.

The information you are providing is sufficient to reproduce the
problem, thanks! I have added this bug to the list of open items for
9.6.

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

Reordering the common fields of OpExpr and ScalarArrayOpExpr at the
beginning of the struct so the get_*op() work with either (as in
attached patch) fixes the issue.

I'm not sure that assuming this compatibility is the right way to fix
this though.

--
Julien Rouhaud
http://dalibo.com - http://dalibo.org

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

Reordering the common fields of OpExpr and ScalarArrayOpExpr at the
beginning of the struct so the get_*op() work with either (as in
attached patch) fixes the issue.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

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 29/04/2016 18:05, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

Reordering the common fields of OpExpr and ScalarArrayOpExpr at the
beginning of the struct so the get_*op() work with either (as in
attached patch) fixes the issue.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

Agreed. New attached patch handles explicitly each node tag.

--
Julien Rouhaud
http://dalibo.com - http://dalibo.org

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

On 29/04/2016 18:05, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

Agreed. New attached patch handles explicitly each node tag.

No, this is completely nuts. The problem is that quals_match_foreign_key
is simply assuming that every clause in the list it's given is an OpExpr,
which is quite wrong. It should just ignore non-OpExpr quals, since it
cannot do anything useful with them anyway. There's a comment claiming
that non-OpExpr quals were already rejected:

* Here since 'usefulquals' only contains bitmap indexes for quals
* of type "var op var" we can safely skip checking this.

but that doesn't appear to have anything to do with current reality.

While this in itself is about a two-line fix, after reviewing
137805f89acb3611 I'm pretty unhappy that it got committed at all.
I think this obvious bug is a good sign that it wasn't ready.
Other unfinished aspects like invention of an undocumented GUC
don't leave a good impression either.

Moreover, it looks to me like this will add quite a lot of overhead,
probably far more than is justified, because clauselist_join_selectivity
is basically O(N^2) in the relation-footprint of the current join --- and
not with a real small multiplier, either, as the functions it calls
contain about four levels of nested loops themselves. Maybe that's
unmeasurable on trivial test cases but it's going to be disastrous in
large queries, or for relations with large numbers of foreign keys.

I think this should be reverted and pushed out to 9.7 development.
It needs a significant amount of rewriting to fix the performance
issue, and now's not the time to be doing that.

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 Sat, Apr 30, 2016 at 1:35 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

On 29/04/2016 18:05, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

Agreed. New attached patch handles explicitly each node tag.

No, this is completely nuts. The problem is that quals_match_foreign_key
is simply assuming that every clause in the list it's given is an OpExpr,
which is quite wrong. It should just ignore non-OpExpr quals, since it
cannot do anything useful with them anyway. There's a comment claiming
that non-OpExpr quals were already rejected:

* Here since 'usefulquals' only contains bitmap indexes for quals
* of type "var op var" we can safely skip checking this.

but that doesn't appear to have anything to do with current reality.

While this in itself is about a two-line fix, after reviewing
137805f89acb3611 I'm pretty unhappy that it got committed at all.
I think this obvious bug is a good sign that it wasn't ready.
Other unfinished aspects like invention of an undocumented GUC
don't leave a good impression either.

Moreover, it looks to me like this will add quite a lot of overhead,
probably far more than is justified, because clauselist_join_selectivity
is basically O(N^2) in the relation-footprint of the current join --- and
not with a real small multiplier, either, as the functions it calls
contain about four levels of nested loops themselves. Maybe that's
unmeasurable on trivial test cases but it's going to be disastrous in
large queries, or for relations with large numbers of foreign keys.

I think this should be reverted and pushed out to 9.7 development.
It needs a significant amount of rewriting to fix the performance
issue, and now's not the time to be doing that.

If this gets reverted, then probably
015e88942aa50f0d419ddac00e63bb06d6e62e86 should also be reverted.

We need to make some decisions here PDQ. I haven't had time to look
at this issue in any technical detail yet. Simon, anyone else, please
weigh in.

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

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

Hi,

On 04/30/2016 07:35 PM, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

On 29/04/2016 18:05, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

Agreed. New attached patch handles explicitly each node tag.

No, this is completely nuts. The problem is that quals_match_foreign_key
is simply assuming that every clause in the list it's given is an OpExpr,
which is quite wrong. It should just ignore non-OpExpr quals, since it
cannot do anything useful with them anyway. There's a comment claiming
that non-OpExpr quals were already rejected:

* Here since 'usefulquals' only contains bitmap indexes for quals
* of type "var op var" we can safely skip checking this.

but that doesn't appear to have anything to do with current reality.

Yes, I agree - there should be a check that the node is OpExpr in
quals_match_foreign_key. This is clearly a bug :-(

While this in itself is about a two-line fix, after reviewing
137805f89acb3611 I'm pretty unhappy that it got committed at all.
I think this obvious bug is a good sign that it wasn't ready.
Other unfinished aspects like invention of an undocumented GUC
don't leave a good impression either.

The GUC is meant to make testing during development easier. I haven't
realized it got committed, but I assume Simon plans to remove it before
the final release. Can't check right now with Simon, though, as he's is
out of office this week.

In any case, I do agree the GUC should have been documented better, and
we should probably put it on the TODO so that it gets removed before the
actual release.

Moreover, it looks to me like this will add quite a lot of overhead,
probably far more than is justified, because
clauselist_join_selectivity is basically O(N^2) in the
relation-footprint of the current join --- and not with a real small
multiplier, either, as the functions it calls contain about four
levels of nested loops themselves. Maybe that's unmeasurable on
trivial test cases but it's going to be disastrous in large queries,
or for relations with large numbers of foreign keys.

That depends on a lot of factors, I guess. Attached are two SQL scripts
that create 5 tables (f1, f2, f3, f4, f5) and then create N foreign keys
on each of them. The foreign keys reference other tables, which means
the loops won't terminate early (after finding the first match) when
joining the first 5 tables, which makes this the worst case. And then we
join different numbers of tables (2, 3, 4 or 5) and do explain analyze
to measure planning time.

The first script (fk-test.sql) does joins on 2 columns, fk-test-6.sql
does joins on 6 columns (so that we also know how the number of columns
affects the planning time).

Sum of planning time for 100 queries (in milliseconds) with 2 columns,
where "2/on" means "join on 2 tables with enable_fk_estimates=on":

N 2/on 2/off 3/on 3/off 4/on 4/off 5/on 5/off
10 6 4 9 8 22 20 77 68
100 15 11 26 19 64 36 177 93
1000 97 84 217 133 516 233 1246 342

and comparison of the timings:

2 3 4 5
10 155% 115% 114% 113%
100 142% 138% 177% 190%
1000 116% 163% 221% 364%

And with the 6 columns:

2/on 2/off 3/on 3/off 4/on 4/off 5/on 5/off
10 25 7 23 20 96 82 344 297
100 21 14 65 33 233 104 735 328
1000 151 99 492 153 1603 320 4627 593

and comparison:

2 3 4 5
10 371% 120% 117% 116%
100 149% 196% 224% 224%
1000 152% 322% 502% 780%

So yes, the overhead is clearly measurable, no doubt about that.

I think this should be reverted and pushed out to 9.7 development.
It needs a significant amount of rewriting to fix the performance
issue, and now's not the time to be doing that.

There are probably a few reasonably simple things we could do - e.g.
ignore foreign keys with just a single column, as the primary goal of
the patch is improving estimates with multi-column foreign keys. I
believe that covers a vast majority of foreign keys in the wild.

If that's deemed insufficient, we'll have to resort to a more complex
improvement, perhaps something akin to the cache proposed in in the
unijoin patch. But if that's required, that's 9.7 material.

regards

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

Hi,

On 05/02/2016 09:18 PM, Robert Haas wrote:

On Sat, Apr 30, 2016 at 1:35 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

On 29/04/2016 18:05, Tom Lane wrote:

Julien Rouhaud <julien.rouhaud@dalibo.com> writes:

The segfault is caused by quals_match_foreign_key() calling get_leftop()
and get_rightop() on a ScalarArrayOpExpr node.

I'm not sure that assuming this compatibility is the right way to fix
this though.

It certainly isn't.

Agreed. New attached patch handles explicitly each node tag.

No, this is completely nuts. The problem is that quals_match_foreign_key
is simply assuming that every clause in the list it's given is an OpExpr,
which is quite wrong. It should just ignore non-OpExpr quals, since it
cannot do anything useful with them anyway. There's a comment claiming
that non-OpExpr quals were already rejected:

* Here since 'usefulquals' only contains bitmap indexes for quals
* of type "var op var" we can safely skip checking this.

but that doesn't appear to have anything to do with current reality.

While this in itself is about a two-line fix, after reviewing
137805f89acb3611 I'm pretty unhappy that it got committed at all.
I think this obvious bug is a good sign that it wasn't ready.
Other unfinished aspects like invention of an undocumented GUC
don't leave a good impression either.

Moreover, it looks to me like this will add quite a lot of overhead,
probably far more than is justified, because clauselist_join_selectivity
is basically O(N^2) in the relation-footprint of the current join --- and
not with a real small multiplier, either, as the functions it calls
contain about four levels of nested loops themselves. Maybe that's
unmeasurable on trivial test cases but it's going to be disastrous in
large queries, or for relations with large numbers of foreign keys.

I think this should be reverted and pushed out to 9.7 development.
It needs a significant amount of rewriting to fix the performance
issue, and now's not the time to be doing that.

If this gets reverted, then probably
015e88942aa50f0d419ddac00e63bb06d6e62e86 should also be reverted.

Probably. I think the code is fine / correct, but as the FK estimation
patch was the only user, there's not much point in keeping it if that
gets reverted.

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

On 4 May 2016 at 02:10, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

There are probably a few reasonably simple things we could do - e.g. ignore
foreign keys with just a single column, as the primary goal of the patch is
improving estimates with multi-column foreign keys. I believe that covers a
vast majority of foreign keys in the wild.

If that's deemed insufficient, we'll have to resort to a more complex
improvement, perhaps something akin to the cache proposed in in the unijoin
patch. But if that's required, that's 9.7 material.

I had thought that if we had a hashtable of rel OIDs which belong to
relations with has_eclass_joins == true, then we could just skip
foreign keys where the confrelid is not in the hashtable. Perhaps that
could be optimised a bit more and we could have something akin to what
predOK is for IndexOptInfo in ForeignKeyOptInfo which just gets set to
true if the relation referenced by the foreign key is in the
simple_rel_array. It's quite likely that if many foreign keys were
used, then the query would have a great number of joins, and planning
would be slow anyway.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, 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 4 May 2016 at 09:18, David Rowley <david.rowley@2ndquadrant.com> wrote:

On 4 May 2016 at 02:10, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

There are probably a few reasonably simple things we could do - e.g. ignore
foreign keys with just a single column, as the primary goal of the patch is
improving estimates with multi-column foreign keys. I believe that covers a
vast majority of foreign keys in the wild.

If that's deemed insufficient, we'll have to resort to a more complex
improvement, perhaps something akin to the cache proposed in in the unijoin
patch. But if that's required, that's 9.7 material.

I had thought that if we had a hashtable of rel OIDs which belong to
relations with has_eclass_joins == true, then we could just skip
foreign keys where the confrelid is not in the hashtable. Perhaps that
could be optimised a bit more and we could have something akin to what
predOK is for IndexOptInfo in ForeignKeyOptInfo which just gets set to
true if the relation referenced by the foreign key is in the
simple_rel_array. It's quite likely that if many foreign keys were
used, then the query would have a great number of joins, and planning
would be slow anyway.

I've spent a few hours looking at this and I've come up with the
attached patch, which flags each ForeignKeyOptInfo to say whether its
possible to be referenced in any join condition, with the logic that
if the referenced relation is in the simple_rte_array, then it could
be referenced.

I ran some of the tests Tomas posted with 1000 FKs and a 4-way join,
with 2 join columns.

Query:
explain analyze
select * from f1
inner join f2 on f1.a = f2.a and f1.b = f2.b
inner join f3 on f1.a = f3.a and f1.b = f3.b
inner join f4 on f1.a = f4.a and f1.b = f4.b;

SET enable_fkey_estimates = on;
duration: 30 s
number of transactions actually processed: 8173
latency average: 3.671 ms
tps = 272.420508 (including connections establishing)
tps = 272.586329 (excluding connections establishing)

SET enable_fkey_estimates = off;
duration: 30 s
number of transactions actually processed: 9153
latency average: 3.278 ms
tps = 305.098852 (including connections establishing)
tps = 305.286072 (excluding connections establishing)

So there's still a 10% planner slowdown for this worst case test, but
it's far less than what it was previously with the same test case.

I just also want to add that the aim of this patch was to fix a very
real world problem which also manifests itself in TPC-H Q9, where the
join to partsupp is drastically underestimated due to the 2 column
join condition, which in our test cases caused the GROUP BY to perform
a Hash Aggregate rather than a Sort/Group Aggregate and since we don't
spill HashAggs to disk, we get OOM for a large scale test on large
scale hardware.

Here's some sample EXPLAIN output from the query in question, which I
think is a smaller scale than the 3TB test where we had issues, but
still demonstrates the issue;

Hash Join (cost=74686.00..597734.90 rows=2400 width=23) (actual
time=564.038..11645.047 rows=11997996 loops=1)
Hash Cond: ((lineitem.l_suppkey = partsupp.ps_suppkey) AND
(lineitem.l_partkey = partsupp.ps_partkey))

Here the estimate is off 5000x.

The attached patch is intended to assist discussion at the moment.
Likely some naming could be better, and the code would need to find a
better home.

The patch also fixes the missing IsA OpExpr test.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <david.rowley@2ndquadrant.com> writes:

On 4 May 2016 at 09:18, David Rowley <david.rowley@2ndquadrant.com> wrote:

On 4 May 2016 at 02:10, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

There are probably a few reasonably simple things we could do - e.g. ignore
foreign keys with just a single column, as the primary goal of the patch is
improving estimates with multi-column foreign keys. I believe that covers a
vast majority of foreign keys in the wild.

I've spent a few hours looking at this and I've come up with the
attached patch, which flags each ForeignKeyOptInfo to say whether its
possible to be referenced in any join condition, with the logic that
if the referenced relation is in the simple_rte_array, then it could
be referenced.

My fundamental problem with the FK-selectivity patch is that it looks
an awful lot like a preliminary proof-of-concept that got committed.

I do not like the basic design: it's about as brute-force as could
possibly be. It adds code that is executed:

* at least once per join relation created (hence, significantly more than
the number of rels in the query; see also get_joinrel_parampathinfo)
* for each inner relation in the initial input joinrel pair
* for each outer relation in the initial joinrel pair
* for each foreign key constraint on this inner and outer rel
* for each key column in that FK
* for each join qual for the current input joinrel pair
* for each member of the relevant EquivalenceClass

This is at least O(N^3) in the number of baserels in the query, not to
mention the other multipliers. I'm not very impressed by tests that scale
only one of the multipliers (like the number of FK constraints); where the
pain is going to come in is when all of these factors are large.

I spent some time trying to make a test case that was impossibly slow,
without any really impressive result: I saw at most about a 25% growth in
planning time, for a 27-way join with one or two foreign keys per table.
I noted however that with a simple FROM list of tables, you don't really
get the full force of the combinatorial explosion, because
join_search_one_level prefers to generate left-deep trees first, and so
the first creation of a given joinrel is always N left-side rels against 1
right-side rel, causing the second level of looping to always iterate just
once. (GEQO behaves likewise, I think.) I spent a little time trying to
devise join order constraints that would result in a lot of high-level
joinrels being formed with many relations on both sides, which would cause
both of the second and third levels to iterate O(N) times not just once.
I didn't have much luck, but I have zero confidence that our users won't
find such cases.

The reason it's so brute force is that it's rediscovering the same facts
over and over. In all simple (non-outer-join) cases, the only clauses
that are of any interest are derived from EquivalenceClasses, and all
that you really need to know is "are the vars mentioned on each side
of this FK present in the same EquivalenceClass?". ISTM that could be
determined once per FK per query and cached in or near the EC, not
expensively rediscovered at each level of joining. I'm not sure whether
it'd be worth considering non-EC-derived equalities (ie, outer join
clauses) at all, and note that the current patch fails to do so anyway;
see below.

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

Aside from the design being basically wrong, the code quality seems pretty
low. Aside from the missing IsA check that started this thread, I found
the following problems in a quick once-over of 137805f89:

Bugs in quals_match_foreign_key():

* Test for clause->opno == fkinfo->conpfeqop[i] fails to consider
cross-type operators, ie, what's in the clause might be int2 = int4
while the conpfeqop is int4 = int2.

* parent_ec check isn't really the right thing, since EC-derived clauses
might not have that set. I think it may be adequate given that you only
deal with simple Vars, but at least a comment about that would be good.

* Come to think of it, you could probably dodge the commutator operator
problem altogether for clauses with nonnull parent_ec, because they must
contain a relevant equality operator. (Although if it's redesigned as I
suggest above, the code path for a clause with parent_ec set would look
totally different from this anyway.)

* Maintaining the fkmatches bitmapset is useless expense, just use a
counter of matched keys. Or for that matter, why not just fail
immediately if i'th key is not found?

find_best_foreign_key_quals():

* Test on enable_fkey_estimates should be one call level up to dodge the
useless doubly-nested loop in clauselist_join_selectivity (which would
make the "fast path" exit here pretty much useless)

clauselist_join_selectivity():

* "either could be zero, but not both" is a pretty unhelpful comment given
the if-test just above it. What *could* have used some explanation is
what the next two dozen lines are doing, because they're as opaque as can
be; and the XXX comment doesn't leave a warm feeling that the author
understands it either. I'm not prepared to opine on whether this segment
of code is correct at all without better commentary.

calc_joinrel_size_estimate():

* why is clauselist_join_selectivity applied to pushed-down clauses and
not local ones in an outer join? If that's not an oversight, it at least
requires an explanatory comment. Note that this means we are not applying
FK knowledge for "a left join b on x = y", though it seems like we could.

compute_semi_anti_join_factors isn't using clauselist_join_selectivity
either. I don't know whether it should be, but if not, a comment about
why not seems appropriate. More generally, I wonder why this logic
wasn't just folded into clauselist_selectivity.

guc.c:
undocumented GUCs are not acceptable

paths.h:
patch introduces an extern that's referenced noplace

In short, I'm not left with a warm fuzzy feeling about this patch having
been ready to commit. The predecessor patch 015e88942 was also
underreviewed, cf 5306df283.

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 Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

Without prejudice to anything else in this useful and detailed review,
I have a question about this. A unique index proves that no A row
will match more than one B row, and I agree that deriving that from
unique indexes is sensible. However, ISTM that an FK provides
additional information: we know that, modulo filter conditions on B,
every A row will match *exactly* one row B row, which can prevent us
from *underestimating* the size of the join product. A unique index
can't do that.

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

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

Hi,

On 05/04/2016 08:54 PM, Tom Lane wrote:

David Rowley <david.rowley@2ndquadrant.com> writes:

On 4 May 2016 at 09:18, David Rowley <david.rowley@2ndquadrant.com> wrote:

On 4 May 2016 at 02:10, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

There are probably a few reasonably simple things we could do - e.g. ignore
foreign keys with just a single column, as the primary goal of the patch is
improving estimates with multi-column foreign keys. I believe that covers a
vast majority of foreign keys in the wild.

I've spent a few hours looking at this and I've come up with the
attached patch, which flags each ForeignKeyOptInfo to say whether its
possible to be referenced in any join condition, with the logic that
if the referenced relation is in the simple_rte_array, then it could
be referenced.

My fundamental problem with the FK-selectivity patch is that it looks
an awful lot like a preliminary proof-of-concept that got committed.

I do not like the basic design: it's about as brute-force as could
possibly be. It adds code that is executed:

* at least once per join relation created (hence, significantly more than
the number of rels in the query; see also get_joinrel_parampathinfo)
* for each inner relation in the initial input joinrel pair
* for each outer relation in the initial joinrel pair
* for each foreign key constraint on this inner and outer rel
* for each key column in that FK
* for each join qual for the current input joinrel pair
* for each member of the relevant EquivalenceClass

This is at least O(N^3) in the number of baserels in the query, not
to mention the other multipliers. I'm not very impressed by tests
that scale only one of the multipliers (like the number of FK
constraints); where the pain is going to come in is when all of these
factors are large.

I spent some time trying to make a test case that was impossibly
slow, without any really impressive result: I saw at most about a 25%
growth in planning time, for a 27-way join with one or two foreign
keys per table. I noted however that with a simple FROM list of
tables, you don't really get the full force of the combinatorial
explosion, because join_search_one_level prefers to generate
left-deep trees first, and so the first creation of a given joinrel
is always N left-side rels against 1 right-side rel, causing the
second level of looping to always iterate just once. (GEQO behaves
likewise, I think.) I spent a little time trying to devise join order
constraints that would result in a lot of high-level joinrels being
formed with many relations on both sides, which would cause both of
the second and third levels to iterate O(N) times not just once. I
didn't have much luck, but I have zero confidence that our users
won't find such cases.

Don't know. We haven't found such extreme example either.

The reason it's so brute force is that it's rediscovering the same
facts over and over. In all simple (non-outer-join) cases, the only
clauses that are of any interest are derived from EquivalenceClasses,
and all that you really need to know is "are the vars mentioned on
each side of this FK present in the same EquivalenceClass?". ISTM
that could be determined once per FK per query and cached in or near
the EC, not expensively rediscovered at each level of joining. I'm
not sure whether it'd be worth considering non-EC-derived equalities
(ie, outer join clauses) at all, and note that the current patch
fails to do so anyway; see below.

I'm not sure it's that simple, as it also depends on the join order, so
if we only detect that once per query we'll get incorrect estimates for
the intermediate results. I think the approach with cache proposed by
David few days ago is the best approach.

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

No, that's not what the patch does, and it can't use unique indexes
instead. The patch improves estimation with multi-column foreign keys,
when the join matches the constraint. Currently we treat the conditions
as independent and multiply the estimated selectivities, completely
ignoring the guarantee provided by the FK, which leads to significant
under-estimates.

So when you have:

CREATE TABLE t1 (a1 INT, a2 INT, primary key (a1,a2));
CREATE TABLE t2 (b1 INT, b2 INT,
FOREIGN KEY (b1,b2) REFERENCES t1(a1,a2));

and do

SELECT * FROM t1, t2 WHERE a1=b1 AND a2=b2;

the patch realizes that is should not multiply the selectivities.

But unique indexes are insufficient for this - it's the foreign key
between the two tables that allows us to do this.

Consider this:

CREATE TABLE t1 (a1 INT, a2 INT, UNIQUE (a1,a2));
CREATE TABLE t2 (b1 INT, b2 INT);

INSERT INTO t1 SELECT i, i FROM generate_series(1,10000) s(i);
INSERT INTO t2 SELECT 10000*random(), 10000*random()
FROM generate_series(1,10000) s(i);

and do the same query. In this case multiplying the selectivities is the
right thing to do, as the unique index provides no guarantees.

Aside from the design being basically wrong, the code quality seems pretty
low. Aside from the missing IsA check that started this thread, I found
the following problems in a quick once-over of 137805f89:

Bugs in quals_match_foreign_key():

* Test for clause->opno == fkinfo->conpfeqop[i] fails to consider
cross-type operators, ie, what's in the clause might be int2 = int4
while the conpfeqop is int4 = int2.

* parent_ec check isn't really the right thing, since EC-derived clauses
might not have that set. I think it may be adequate given that you only
deal with simple Vars, but at least a comment about that would be good.

* Come to think of it, you could probably dodge the commutator operator
problem altogether for clauses with nonnull parent_ec, because they must
contain a relevant equality operator. (Although if it's redesigned as I
suggest above, the code path for a clause with parent_ec set would look
totally different from this anyway.)

* Maintaining the fkmatches bitmapset is useless expense, just use a
counter of matched keys. Or for that matter, why not just fail
immediately if i'th key is not found?

find_best_foreign_key_quals():

* Test on enable_fkey_estimates should be one call level up to dodge the
useless doubly-nested loop in clauselist_join_selectivity (which would
make the "fast path" exit here pretty much useless)

clauselist_join_selectivity():

* "either could be zero, but not both" is a pretty unhelpful comment given
the if-test just above it. What *could* have used some explanation is
what the next two dozen lines are doing, because they're as opaque as can
be; and the XXX comment doesn't leave a warm feeling that the author
understands it either. I'm not prepared to opine on whether this segment
of code is correct at all without better commentary.

calc_joinrel_size_estimate():

* why is clauselist_join_selectivity applied to pushed-down clauses and
not local ones in an outer join? If that's not an oversight, it at least
requires an explanatory comment. Note that this means we are not applying
FK knowledge for "a left join b on x = y", though it seems like we could.

compute_semi_anti_join_factors isn't using clauselist_join_selectivity
either. I don't know whether it should be, but if not, a comment about
why not seems appropriate. More generally, I wonder why this logic
wasn't just folded into clauselist_selectivity.

guc.c:
undocumented GUCs are not acceptable

paths.h:
patch introduces an extern that's referenced noplace

In short, I'm not left with a warm fuzzy feeling about this patch having
been ready to commit. The predecessor patch 015e88942 was also
underreviewed, cf 5306df283.

OK, thanks for the comments.

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

Robert Haas <robertmhaas@gmail.com> writes:

On Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

Without prejudice to anything else in this useful and detailed review,
I have a question about this. A unique index proves that no A row
will match more than one B row, and I agree that deriving that from
unique indexes is sensible. However, ISTM that an FK provides
additional information: we know that, modulo filter conditions on B,
every A row will match *exactly* one row B row, which can prevent us
from *underestimating* the size of the join product. A unique index
can't do that.

Very good point, but unless I'm missing something, that is not what the
current patch does. I'm not sure offhand whether that's an important
estimation failure mode currently, or if it is whether it would be
sensible to try to implement that rule entirely separately from the "at
most one" aspect, or if it isn't sensible, whether that's a sufficiently
strong reason to confine the "at most one" logic to working only with FKs
and not with bare unique indexes.

On the whole, that seems like another argument why this needs more time.

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

Hi,

On 05/04/2016 11:02 PM, Tom Lane wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

Without prejudice to anything else in this useful and detailed review,
I have a question about this. A unique index proves that no A row
will match more than one B row, and I agree that deriving that from
unique indexes is sensible. However, ISTM that an FK provides
additional information: we know that, modulo filter conditions on B,
every A row will match *exactly* one row B row, which can prevent us
from *underestimating* the size of the join product. A unique index
can't do that.

Very good point, but unless I'm missing something, that is not what the
current patch does. I'm not sure offhand whether that's an important
estimation failure mode currently, or if it is whether it would be
sensible to try to implement that rule entirely separately from the "at
most one" aspect, or if it isn't sensible, whether that's a sufficiently
strong reason to confine the "at most one" logic to working only with FKs
and not with bare unique indexes.

FWIW it's a real-world problem with multi-column FKs. As David pointed
out upthread, a nice example of this issue is Q9 in the TPC-H bench,
where the underestimate leads to HashAggregate and then OOM failure.

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

On Wed, May 4, 2016 at 5:02 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Very good point, but unless I'm missing something, that is not what the
current patch does. I'm not sure offhand whether that's an important
estimation failure mode currently, or if it is whether it would be
sensible to try to implement that rule entirely separately from the "at
most one" aspect, or if it isn't sensible, whether that's a sufficiently
strong reason to confine the "at most one" logic to working only with FKs
and not with bare unique indexes.

Tomas seems to feel that that is what the current patch does, and
indeed that it's the main point of the current patch, but you seem to
think that it doesn't do that. Either I'm misinterpreting what one of
you is saying, or you are missing something, or his patch fails to
accomplish its intended purpose. It seems important to figure out
which of those things is true.

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

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

On Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I spent some time trying to make a test case that was impossibly slow,
without any really impressive result: I saw at most about a 25% growth in
planning time, for a 27-way join with one or two foreign keys per table.
I noted however that with a simple FROM list of tables, you don't really
get the full force of the combinatorial explosion, because
join_search_one_level prefers to generate left-deep trees first, and so
the first creation of a given joinrel is always N left-side rels against 1
right-side rel, causing the second level of looping to always iterate just
once. (GEQO behaves likewise, I think.) I spent a little time trying to
devise join order constraints that would result in a lot of high-level
joinrels being formed with many relations on both sides, which would cause
both of the second and third levels to iterate O(N) times not just once.
I didn't have much luck, but I have zero confidence that our users won't
find such cases.

I'

The reason it's so brute force is that it's rediscovering the same facts
over and over. In all simple (non-outer-join) cases, the only clauses
that are of any interest are derived from EquivalenceClasses, and all
that you really need to know is "are the vars mentioned on each side
of this FK present in the same EquivalenceClass?". ISTM that could be
determined once per FK per query and cached in or near the EC, not
expensively rediscovered at each level of joining. I'm not sure whether
it'd be worth considering non-EC-derived equalities (ie, outer join
clauses) at all, and note that the current patch fails to do so anyway;
see below.

My other design-level complaint is that basing this on foreign keys is
fundamentally the wrong thing. What actually matters is the unique index
underlying the FK; that is, if we have "a.x = b.y" and there's a
compatible unique index on b.y, we can conclude that no A row will match
more than one B row, whether or not an explicit FK relationship has been
declared. So we should drive this off unique indexes instead of FKs,
first because we will find more cases, and second because the planner
already examines indexes and doesn't need any additional catalog lookups
to get the required data. (IOW, the relcache additions that were made in
this patch series should go away too.)

Aside from the design being basically wrong, the code quality seems pretty
low. Aside from the missing IsA check that started this thread, I found
the following problems in a quick once-over of 137805f89:

Bugs in quals_match_foreign_key():

* Test for clause->opno == fkinfo->conpfeqop[i] fails to consider
cross-type operators, ie, what's in the clause might be int2 = int4
while the conpfeqop is int4 = int2.

* parent_ec check isn't really the right thing, since EC-derived clauses
might not have that set. I think it may be adequate given that you only
deal with simple Vars, but at least a comment about that would be good.

* Come to think of it, you could probably dodge the commutator operator
problem altogether for clauses with nonnull parent_ec, because they must
contain a relevant equality operator. (Although if it's redesigned as I
suggest above, the code path for a clause with parent_ec set would look
totally different from this anyway.)

* Maintaining the fkmatches bitmapset is useless expense, just use a
counter of matched keys. Or for that matter, why not just fail
immediately if i'th key is not found?

find_best_foreign_key_quals():

* Test on enable_fkey_estimates should be one call level up to dodge the
useless doubly-nested loop in clauselist_join_selectivity (which would
make the "fast path" exit here pretty much useless)

clauselist_join_selectivity():

* "either could be zero, but not both" is a pretty unhelpful comment given
the if-test just above it. What *could* have used some explanation is
what the next two dozen lines are doing, because they're as opaque as can
be; and the XXX comment doesn't leave a warm feeling that the author
understands it either. I'm not prepared to opine on whether this segment
of code is correct at all without better commentary.

calc_joinrel_size_estimate():

* why is clauselist_join_selectivity applied to pushed-down clauses and
not local ones in an outer join? If that's not an oversight, it at least
requires an explanatory comment. Note that this means we are not applying
FK knowledge for "a left join b on x = y", though it seems like we could.

compute_semi_anti_join_factors isn't using clauselist_join_selectivity
either. I don't know whether it should be, but if not, a comment about
why not seems appropriate. More generally, I wonder why this logic
wasn't just folded into clauselist_selectivity.

guc.c:
undocumented GUCs are not acceptable

paths.h:
patch introduces an extern that's referenced noplace

In short, I'm not left with a warm fuzzy feeling about this patch having
been ready to commit. The predecessor patch 015e88942 was also
underreviewed, cf 5306df283.

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

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

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

On Wed, May 4, 2016 at 5:51 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I spent some time trying to make a test case that was impossibly slow,
without any really impressive result: I saw at most about a 25% growth in
planning time, for a 27-way join with one or two foreign keys per table.
I noted however that with a simple FROM list of tables, you don't really
get the full force of the combinatorial explosion, because
join_search_one_level prefers to generate left-deep trees first, and so
the first creation of a given joinrel is always N left-side rels against 1
right-side rel, causing the second level of looping to always iterate just
once. (GEQO behaves likewise, I think.) I spent a little time trying to
devise join order constraints that would result in a lot of high-level
joinrels being formed with many relations on both sides, which would cause
both of the second and third levels to iterate O(N) times not just once.
I didn't have much luck, but I have zero confidence that our users won't
find such cases.

I'

Well, that wasn't my best-ever email to the list. Sigh.

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

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

On Wed, May 4, 2016 at 2:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I spent some time trying to make a test case that was impossibly slow,
without any really impressive result: I saw at most about a 25% growth in
planning time, for a 27-way join with one or two foreign keys per table.
I noted however that with a simple FROM list of tables, you don't really
get the full force of the combinatorial explosion, because
join_search_one_level prefers to generate left-deep trees first, and so
the first creation of a given joinrel is always N left-side rels against 1
right-side rel, causing the second level of looping to always iterate just
once. (GEQO behaves likewise, I think.) I spent a little time trying to
devise join order constraints that would result in a lot of high-level
joinrels being formed with many relations on both sides, which would cause
both of the second and third levels to iterate O(N) times not just once.
I didn't have much luck, but I have zero confidence that our users won't
find such cases.

Have you looked at the patch David Rowley proposed to fix this by
doing some caching? I am not crazy about accepting even a 25% growth
in planning time on a 27-way join, although maybe 27-way joins are
rare enough and vulnerable enough to bad plans that it would be worth
it if we could convince ourselves that plan quality would go up. But
if that patch drops it to some much lesser number, we should consider
that as a possible fix.

Bugs in quals_match_foreign_key():

* Test for clause->opno == fkinfo->conpfeqop[i] fails to consider
cross-type operators, ie, what's in the clause might be int2 = int4
while the conpfeqop is int4 = int2.

* parent_ec check isn't really the right thing, since EC-derived clauses
might not have that set. I think it may be adequate given that you only
deal with simple Vars, but at least a comment about that would be good.

* Come to think of it, you could probably dodge the commutator operator
problem altogether for clauses with nonnull parent_ec, because they must
contain a relevant equality operator. (Although if it's redesigned as I
suggest above, the code path for a clause with parent_ec set would look
totally different from this anyway.)

* Maintaining the fkmatches bitmapset is useless expense, just use a
counter of matched keys. Or for that matter, why not just fail
immediately if i'th key is not found?

Technically, only the first of these is a clear bug, IMHO. But it
seems like they should all be fixed.

find_best_foreign_key_quals():

* Test on enable_fkey_estimates should be one call level up to dodge the
useless doubly-nested loop in clauselist_join_selectivity (which would
make the "fast path" exit here pretty much useless)

Yes, that's pretty stupid, and should be fixed. Coding style is not
per project spec, either. Also, the header comment for
find_best_foreign_key_quals and in fact the name of the function look
pretty poor. It seems that the return value is the number of columns
in the foreign key and that an out parameter, joinqualsbitmap, whose
exact meaning doesn't seem to be documented in any comment anywhere in
the patch.

clauselist_join_selectivity():

* "either could be zero, but not both" is a pretty unhelpful comment given
the if-test just above it. What *could* have used some explanation is
what the next two dozen lines are doing, because they're as opaque as can
be; and the XXX comment doesn't leave a warm feeling that the author
understands it either. I'm not prepared to opine on whether this segment
of code is correct at all without better commentary.

I'm pretty baffled by this code, too. I think what the overlap stuff
is doing is trying to calculate selectivity when we match multiple
foreign key constraints, but it doesn't look very principled.
find_best_foreign_key_quals discards "shorter" matches entirely,
picking arbitrarily among longer ones, but then we try to deal with
all of the ones that survive that stage even if they overlap. It's
hard to judge whether any of this makes sense without more
explanation.

calc_joinrel_size_estimate():

* why is clauselist_join_selectivity applied to pushed-down clauses and
not local ones in an outer join? If that's not an oversight, it at least
requires an explanatory comment. Note that this means we are not applying
FK knowledge for "a left join b on x = y", though it seems like we could.

compute_semi_anti_join_factors isn't using clauselist_join_selectivity
either. I don't know whether it should be, but if not, a comment about
why not seems appropriate. More generally, I wonder why this logic
wasn't just folded into clauselist_selectivity.

Good questions.

guc.c:
undocumented GUCs are not acceptable

Agreed.

paths.h:
patch introduces an extern that's referenced noplace

Oops.

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

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