Hi,
On 05/04/2016 08:54 PM, Tom Lane wrote:
David Rowley <david.row...@2ndquadrant.com> writes:
On 4 May 2016 at 09:18, David Rowley <david.row...@2ndquadrant.com> wrote:
On 4 May 2016 at 02:10, Tomas Vondra <tomas.von...@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
