Re: pg9.6 segfault using simple query (related to use fk for join estimates) - Mailing list pgsql-hackers

On 5 May 2016 at 06:54, Tom Lane <tgl@sss.pgh.pa.us> 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 don't disagree that there were some mistakes made. The last time I
saw this work was when I proposed some changes to Tomas' patch, which
was quite a long time ago now. I'd not gotten to look at it since
then.

> 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.

Yes, it's quite a lot of nesting. The patch I sent yesterday helps to
reduce the number of foreign keys considered. The part I'm not all
that happy with now is the fact that quite a bit of repeat work gets
done during the join search. It would be nice to cache some of this
but nothing came to mind, as we need to record the position of each
joinqual so that we only estimate the non-matched ones with the
standard estimation technique. The order of, or items in that list
won't be fixed as more relations are added to the mix during the join
search.

> 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.

Did you test that with or without my patch from yesterday?

> 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.

That's interesting, but requires a good bit of thought to how it might work.

> 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.)

I think your wires are crossed to what this patch actually does. A
unique index could only prove that no more than 1 rows exists. This
goes to prove that exactly 1 exists, then will reduce that estimate by
any other join conditions which were not matched to a foreign key.
Perhaps there is some improvements to be made to the way estimations
work using unique indexes, but that's another problem that Tomas was
not aiming to tackle with this patch.

> 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.

Yes. I did write this and yes that does need to test for the
commutative operator as the order of the condition could be reversed
and the types may not match.

> * 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.

Its not all that clear to me which cases the patch would fail to find
the FK because of this. If there's no parent_ec won't it be matched
manually by the code in the else condition?

> * 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?

I'd say that's a wrong assumption and that check still needs to be
there as a duplicate condition could up the number of matches. We
can't simply count the number of joinquals matched and assume that if
we find that number to be the same as the number of keys in the
foreign key that all is well... One key could be matched twice, and
another not at all.

>
> 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)

If you ask me that GUC needs to be removed. As far as I understand it
that was only ever for testing. He's not around to ask at the moment,
but I'd imagine it was always destine to be removed before release.

> 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.

Yes, I agree.

> 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

It should be removed.

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

That's not great :-(

> 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.

I've started making some improvements to this, but need to talk to
Tomas. It's currently in the middle of his night, but will try to
catch him in his morning to discuss this with him.

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