Horton

Thread

Commits

  1. Fix FK-based join selectivity estimation for semi/antijoins.

  2. Restore foreign-key-aware estimation of join relation sizes.

  1. New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-04T19:44:06Z

    This is a branch of the discussion in
https://www.postgresql.org/message-id/flat/20160429102531.GA13701%40huehner.biz
but I'm starting a new thread as the original title is getting
increasingly off-topic.

I complained in that thread that the FK join selectivity patch had a
very brute-force approach to matching join qual clauses to FK
constraints, requiring a total of seven nested levels of looping to
get anything done, and expensively rediscovering the same facts over
and over.  Here is a sketch of what I think is a better way:

* During the planner's catalog data collection phase, construct a
single list (per PlannerInfo, not per RTE) of all relevant FKs.
In this data structure, each FK's referenced and referencing relations
are identified by relid (that is, RTE index) not just OID.  In the case
of a query containing a self-join, that would mean that the same FK
constraint could give rise to multiple list entries, one for each RTE
occurrence of its referenced or referencing target relation.  FKs not
relating two tables of the query are necessarily not in this list,
and we could also choose not to include single-column FKs.

* After finalizing equivalence classes, make a single pass through
the FK list and check each column-pair to see if it can be matched
to any EC (that is, both source and target columns are in the EC and
the comparison operator is in the EC's opfamily).  Mark each matched
column pair in the FK list data structure with a pointer to the EC.

* When performing join selectivity estimation, run through the FK list
a single time, ignoring entries that do not link a member of the join's
LHS to a member of the join's RHS.  This is a fairly cheap test given
the relid labels; it'd be approximately

	if ((bms_is_member(fkinfo->src_relid, outer_rel->relids) &&
	     bms_is_member(fkinfo->dst_relid, inner_rel->relids)) ||
	    (bms_is_member(fkinfo->dst_relid, outer_rel->relids) &&
	     bms_is_member(fkinfo->src_relid, inner_rel->relids)))

For each potentially interesting FK entry, run through the join
qual list.  A RestrictInfo that was generated from an EC matches
the FK if and only if that EC appears in the per-column markings;
other RestrictInfos are matched to one of the FK columns normally
(I think this path can ignore FK columns that have been matched to ECs).
At the end of that, we can determine whether all the FK columns have
been matched to some qual item, and we have a count and/or bitmapset
of the qual list entries that matched the FK.  Remember the FK entry
with the largest such count.

* After scanning the list, we have our best FK match and can proceed
with making the actual selectivity estimate as in the current code.

With this approach, we have an iteration structure like

  * once per join relation created
    * for each foreign key constraint relevant to the query
        (but skipping the loops below if it's not relevant to this join)
      * for each join qual for the joinrel pair
        * for each key column in that FK

which gets us down from seven nested loops to four, and also makes the
work done in the innermost loops significantly cheaper for the EC case,
which will be the more common one.  It's also much easier to make this
structure do zero extra work when there are no relevant FKs, which is
a pleasant property for extra planner work to have.

Now, we'll also add some per-FK-per-EC setup work, but my guess is
that that's negligible compared to the per-join-relation work.

It's possible that we could reduce the cost of matching non-EC join
quals as well, with some trick along the line of pre-matching non-EC
RestrictInfos to FK items.  I'm unsure that that is worth the trouble
though.

Thoughts?

			regards, tom lane

  2. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-05T14:57:06Z

    I wrote:
> ... Here is a sketch of what I think is a better way:
> ...
> It's possible that we could reduce the cost of matching non-EC join
> quals as well, with some trick along the line of pre-matching non-EC
> RestrictInfos to FK items.  I'm unsure that that is worth the trouble
> though.

After further thought, I believe that may well be worth doing.  That
is, someplace after deconstruct_jointree(), examine all the FKs and
match their columns not only to ECs but to non-EC joinclauses, which
we could find by trawling the joininfo list for either subject relation.
We'd end up with a EC pointer and/or a list of non-EC RestrictInfos
for each FK column.

The thing that makes this attractive is that at the end of this matching,
we would know exactly whether each FK is matched to the query as a whole:
either all its columns have matches, or they don't.  It's not necessary to
re-determine that for each joinrel pair that includes the FK's two subject
relations.  So the per-join-relation work would reduce to scanning the FK
list once to find the matched FK(s) that connect relations on opposite
sides of the join.  Once we've found such an FK, identifying which join
qual list items should be dropped in favor of applying the FK's
selectivity is also really easy: we just check the column markings.

			regards, tom lane

  3. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-06T01:23:27Z

    Hi,

On 06/04/2016 09:44 PM, Tom Lane wrote:
> This is a branch of the discussion in
> https://www.postgresql.org/message-id/flat/20160429102531.GA13701%40huehner.biz
> but I'm starting a new thread as the original title is getting
> increasingly off-topic.
>
> I complained in that thread that the FK join selectivity patch had a
> very brute-force approach to matching join qual clauses to FK
> constraints, requiring a total of seven nested levels of looping to
> get anything done, and expensively rediscovering the same facts over
> and over.  Here is a sketch of what I think is a better way:
>
> * During the planner's catalog data collection phase, construct a
> single list (per PlannerInfo, not per RTE) of all relevant FKs.
> In this data structure, each FK's referenced and referencing relations
> are identified by relid (that is, RTE index) not just OID.  In the case
> of a query containing a self-join, that would mean that the same FK
> constraint could give rise to multiple list entries, one for each RTE
> occurrence of its referenced or referencing target relation.  FKs not
> relating two tables of the query are necessarily not in this list,
> and we could also choose not to include single-column FKs.
>
> * After finalizing equivalence classes, make a single pass through
> the FK list and check each column-pair to see if it can be matched
> to any EC (that is, both source and target columns are in the EC and
> the comparison operator is in the EC's opfamily).  Mark each matched
> column pair in the FK list data structure with a pointer to the EC.
>
> * When performing join selectivity estimation, run through the FK list
> a single time, ignoring entries that do not link a member of the join's
> LHS to a member of the join's RHS.  This is a fairly cheap test given
> the relid labels; it'd be approximately
>
> 	if ((bms_is_member(fkinfo->src_relid, outer_rel->relids) &&
> 	     bms_is_member(fkinfo->dst_relid, inner_rel->relids)) ||
> 	    (bms_is_member(fkinfo->dst_relid, outer_rel->relids) &&
> 	     bms_is_member(fkinfo->src_relid, inner_rel->relids)))
>
> For each potentially interesting FK entry, run through the join
> qual list.  A RestrictInfo that was generated from an EC matches
> the FK if and only if that EC appears in the per-column markings;
> other RestrictInfos are matched to one of the FK columns normally
> (I think this path can ignore FK columns that have been matched to ECs).
> At the end of that, we can determine whether all the FK columns have
> been matched to some qual item, and we have a count and/or bitmapset
> of the qual list entries that matched the FK.  Remember the FK entry
> with the largest such count.
>
> * After scanning the list, we have our best FK match and can proceed
> with making the actual selectivity estimate as in the current code.
>
> With this approach, we have an iteration structure like
>
>   * once per join relation created
>     * for each foreign key constraint relevant to the query
>         (but skipping the loops below if it's not relevant to this join)
>       * for each join qual for the joinrel pair
>         * for each key column in that FK
>
> which gets us down from seven nested loops to four, and also makes the
> work done in the innermost loops significantly cheaper for the EC case,
> which will be the more common one.  It's also much easier to make this
> structure do zero extra work when there are no relevant FKs, which is
> a pleasant property for extra planner work to have.
>
> Now, we'll also add some per-FK-per-EC setup work, but my guess is
> that that's negligible compared to the per-join-relation work.
>
> It's possible that we could reduce the cost of matching non-EC join
> quals as well, with some trick along the line of pre-matching non-EC
> RestrictInfos to FK items.  I'm unsure that that is worth the trouble
> though.
>
> Thoughts?

Firstly thanks for looking into this, and also for coming up with a very 
detailed design proposal.

I do agree this new design seems superior to the current one and it 
seems worth a try. I'd like to see how far we can get over the next few 
days (say, until the end of the week).

One of the recent issues with the current design was handling of 
inheritance / appendrels. ISTM the proposed design has the same issue, 
no? What happens if the relations are partitioned?

regards

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

  4. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-06T15:59:24Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> One of the recent issues with the current design was handling of 
> inheritance / appendrels. ISTM the proposed design has the same issue, 
> no? What happens if the relations are partitioned?

I haven't thought about inheritance in this proposal.  My initial feeling
is that considering the parent table's outgoing FKs (if any) as valid is
not unreasonable.  If it has any, probably all the children do too.
Not sure about incoming FKs, but there probably are none anyhow, since
our implementation doesn't really permit reasonable FK definitions that
reference a partitioned table.  In any case, whatever we might choose
to do differently for inheritance would be no harder in this scheme than
what's there now; plus, whatever it is, we'd do it once not once per join
relation.

			regards, tom lane

  5. Re: New design for FK-based join selectivity estimation

    Simon Riggs <simon@2ndquadrant.com> — 2016-06-13T17:28:36Z

    On 4 June 2016 at 20:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> This is a branch of the discussion in
>
> https://www.postgresql.org/message-id/flat/20160429102531.GA13701%40huehner.biz
> but I'm starting a new thread as the original title is getting
> increasingly off-topic.
>
> I complained in that thread that the FK join selectivity patch had a
> very brute-force approach to matching join qual clauses to FK
> constraints, requiring a total of seven nested levels of looping to
> get anything done, and expensively rediscovering the same facts over
> and over.  Here is a sketch of what I think is a better way:
>

Thanks for your review and design notes here, which look like good
improvements.

Tomas has been discussing that with myself and others, but I just realised
that might not be apparent on list, so just to mention there is activity on
this and new code will be published very soon.


On the above mentioned thread, Tomas' analysis was this...
https://www.postgresql.org/message-id/8344835e-18af-9d40-aed7-bd2261be9162%402ndquadrant.com
> 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 agree with that comment. The relcache code retrieves all FKs, even ones
that have a single column. Yet the planner code never uses them unless
nKeys>1. That was masked somewhat by my two commits, treating the info as
generic and then using only a very specific subset of it.

So a simple change is to make RelationGetFKeyList() only retrieve FKs with
nKeys>1. Rename to RelationGetMultiColumnFKeyList(). That greatly reduces
the scope for increased planning time.

-- 
Simon Riggs                http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/>
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  6. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-13T18:16:25Z

    Simon Riggs <simon@2ndquadrant.com> writes:
> So a simple change is to make RelationGetFKeyList() only retrieve FKs with
> nKeys>1. Rename to RelationGetMultiColumnFKeyList(). That greatly reduces
> the scope for increased planning time.

FWIW, I don't particularly agree with that.  It makes the relcache's fkey
storage extremely specific to this one use-case, a decision I expect we'd
regret later.  And the planner needs to filter the fkey list anyway,
because it only wants fkeys that link to tables that are also in the
current query.  Thus, my recommendation was that we should allow
RelationGetFKeyList to return a pointer directly to the cached info list
and require the planner to immediately copy (only) the entries that it
needs for the current query.

Another point here is that I'm now unconvinced that restricting the logic
to consider only multi-column fkeys is really what we want.  It looks to
me like the code can also improve estimates in the case where there are
multiple single-column FKs linking to the same target relation.  That
might not be too common for two-table queries, but I bet it happens a
lot in three-or-more-table queries.

			regards, tom lane

  7. Re: New design for FK-based join selectivity estimation

    Simon Riggs <simon@2ndquadrant.com> — 2016-06-13T18:52:06Z

    On 13 June 2016 at 19:16, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> Simon Riggs <simon@2ndquadrant.com> writes:
> > So a simple change is to make RelationGetFKeyList() only retrieve FKs
> with
> > nKeys>1. Rename to RelationGetMultiColumnFKeyList(). That greatly reduces
> > the scope for increased planning time.
>
> FWIW, I don't particularly agree with that.  It makes the relcache's fkey
> storage extremely specific to this one use-case, a decision I expect we'd
> regret later.


Hmm, clearly I thought that earlier also; that earlier thinking may be
influencing you. My commits had the concept of generic FK info and then a
specific optimization. So the main part of the planning problem was caused
by stored info that would never be used, in 9.6.

What changes my mind here is 1) point in dev cycle, 2) the point that the
list of FKs doesn't take into account whether the constraints are
deferrable, deferred or immediate and whether they are valid/invalid. ISTM
likely that we would care about those things in the future if we believe
that info is generic.

But then each new usage of the info will have the same planning time
problem to consider if they choose to extend the amount of info they hold.

Rejecting an optimization in 9.6 because it might be undone by later
changes is surely a problem for those later changes to resolve.


> And the planner needs to filter the fkey list anyway,
> because it only wants fkeys that link to tables that are also in the
> current query.  Thus, my recommendation was that we should allow
> RelationGetFKeyList to return a pointer directly to the cached info list
> and require the planner to immediately copy (only) the entries that it
> needs for the current query.
>
> Another point here is that I'm now unconvinced that restricting the logic
> to consider only multi-column fkeys is really what we want.  It looks to
> me like the code can also improve estimates in the case where there are
> multiple single-column FKs linking to the same target relation.  That
> might not be too common for two-table queries, but I bet it happens a
> lot in three-or-more-table queries.
>

Is it realistic that we consider that at this point? Certainly not for
myself, at least.

-- 
Simon Riggs                http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/>
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  8. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-13T19:51:16Z

    Simon Riggs <simon@2ndquadrant.com> writes:
> On 13 June 2016 at 19:16, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Another point here is that I'm now unconvinced that restricting the logic
>> to consider only multi-column fkeys is really what we want.  It looks to
>> me like the code can also improve estimates in the case where there are
>> multiple single-column FKs linking to the same target relation.  That
>> might not be too common for two-table queries, but I bet it happens a
>> lot in three-or-more-table queries.

> Is it realistic that we consider that at this point? Certainly not for
> myself, at least.

It's pretty much built into the redesign I proposed, or so I thought.

			regards, tom lane

  9. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-13T21:09:43Z

    Hi,

Attached is a reworked patch, mostly following the new design proposal 
from this thread.

I'm not entirely happy with the code, but it's the best I've been able 
to come up with by now and I won't be able to significantly improve that 
due to travel over. Inevitably there will be issues in the code, and if 
there's a chance of fixing them I'll do my best to do that over the 
evenings at a hotel.

The filtering and matching to eclasses / join quals is triggered from 
planmain.c - I believe this is the right place and that those pieces are 
reasonably solid.

The estimation still happens in costsize.c, of course, but was modified 
to use the pre-matched info. I have my doubts about this part, and I'm 
sure Tom had something less complex / more efficient in mind (using the 
pre-matched info).


regards

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

  10. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-15T23:00:08Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> Attached is a reworked patch, mostly following the new design proposal 
> from this thread.

I've whacked this around quite a bit and am now reasonably happy with it.
The issue of planning speed hit should be pretty much gone, although I've
not done testing to prove that.  I've rearranged the actual selectivity
calculation some too, because tests I did here did not look very good for
anything but the plain-inner-join case.  It may be that more work is
needed there, but at least there's reasonable commentary about what we're
doing and why.

I have not adopted the plan of ignoring single-column FKs.  While it would
only take a couple more lines to do so, I think the argument that there
will be a material planning speed hit no longer has much force.  And I see
a couple of arguments in favor of allowing this code to trigger on
single-column FKs.  First, it should work well even when pg_statistic data
is missing or out of date, which would be an improvement; and second, we
are likely not going to get much beta testing of the behavior if we
restrict it to multi-col FKs.  So I think we should ship it like this for
beta even if we end up adding a filter against single-column FKs for
release.

Comments and testing appreciated.

			regards, tom lane

  11. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-17T04:15:25Z

    Hi,

On 06/16/2016 01:00 AM, Tom Lane wrote:
> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>> Attached is a reworked patch, mostly following the new design proposal
>> from this thread.
>
> I've whacked this around quite a bit and am now reasonably happy with it.
> The issue of planning speed hit should be pretty much gone, although I've
> not done testing to prove that.  I've rearranged the actual selectivity
> calculation some too, because tests I did here did not look very good for
> anything but the plain-inner-join case.  It may be that more work is
> needed there, but at least there's reasonable commentary about what we're
> doing and why.

Thanks for getting the patch into a much better shape. I've quickly 
reviewed the patch this morning before leaving to the airport - I do 
plan to do additional review/testing once in the air or perhaps over the 
weekend. So at the moment I only have a few minor comments:

1) Shouldn't we define a new macro in copyfuncs.c, to do the memcpy for 
us? Seems a bit strange we have macros for everything else.

2) I'm wondering whether removing the restrict infos when

     if (fkinfo->eclass[i] == rinfo->parent_ec)

is actually correct. Can't the EC include conditions that do not match 
the FK? I mean something like this:

   CREATE TABLE a (id1 INT PRIMARY KEY, id2 INT);
   CREATE TABLE b (id1 INT REFERENCES a (id1), id2 INT);

and then something like

   SELECT * FROM a JOIN b ON (a.id1 = b.id1 AND a.id1 = b.id2)

I've been unable to trigger this issue with your patch, but I do 
remember I've ran into that with my version, which is why I explicitly 
checked the rinfo again before removing it. Maybe that was incorrect, or 
perhaps your patch does something smart. Or maybe it's just masked by 
the fact that we 'push' the EC conditions to the base relations (which 
however means we're stuck with default equality estimate).

3) I think this comment in get_foreign_key_join_selectivity is wrong and 
should instead say 'to FK':

   /* Otherwise, see if rinfo was previously matched to EC */

>
> I have not adopted the plan of ignoring single-column FKs.  While it would
> only take a couple more lines to do so, I think the argument that there
> will be a material planning speed hit no longer has much force.  And I see
> a couple of arguments in favor of allowing this code to trigger on
> single-column FKs.  First, it should work well even when pg_statistic data
> is missing or out of date, which would be an improvement; and second, we
> are likely not going to get much beta testing of the behavior if we
> restrict it to multi-col FKs.  So I think we should ship it like this for
> beta even if we end up adding a filter against single-column FKs for
> release.

OK

regards

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

  12. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-17T14:53:36Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> Thanks for getting the patch into a much better shape. I've quickly 
> reviewed the patch this morning before leaving to the airport - I do 
> plan to do additional review/testing once in the air or perhaps over the 
> weekend. So at the moment I only have a few minor comments:

> 1) Shouldn't we define a new macro in copyfuncs.c, to do the memcpy for 
> us? Seems a bit strange we have macros for everything else.

Perhaps, but it seemed not that compelling since we need bespoke code for
those fields in outfuncs.c etc.  Maybe it would be worth thinking about
macro infrastructure for array-type fields in all of those modules.

> 2) I'm wondering whether removing the restrict infos when
>      if (fkinfo->eclass[i] == rinfo->parent_ec)
> is actually correct. Can't the EC include conditions that do not match 
> the FK?

Doesn't matter.  The point is that it *does* include a condition that
does match the FK, whether it chose to generate exactly that condition
for this join or some related one.

> I mean something like this:
>    CREATE TABLE a (id1 INT PRIMARY KEY, id2 INT);
>    CREATE TABLE b (id1 INT REFERENCES a (id1), id2 INT);
> and then something like
>    SELECT * FROM a JOIN b ON (a.id1 = b.id1 AND a.id1 = b.id2)

Right.  In this case we'll have an EC containing {a.id1, b.id1, b.id2}
which means that equivclass.c will generate a restriction condition
b.id1 = b.id2 to be applied at the scan of b.  At the join level, it
has a choice whether to generate a.id1 = b.id1 or a.id1 = b.id2.
It could generate both, but that would be pointlessly inefficient (and
would likely confuse the selectivity estimators, too).  But even if it
chooses to generate a.id1 = b.id2, we should recognize that the FK is
matched.  What we're effectively doing by dropping that clause in
favor of treating the FK as matched is overridding equivclass.c's
arbitrary choice of which join clause to generate with an equally valid
choice that is easier to estimate for.

> 3) I think this comment in get_foreign_key_join_selectivity is wrong and 
> should instead say 'to FK':
>    /* Otherwise, see if rinfo was previously matched to EC */

Duh, yeah.


I rewrote the comments in this section to clarify a bit:

            /* Drop this clause if it matches any column of the FK */
            for (i = 0; i < fkinfo->nkeys; i++)
            {
                if (rinfo->parent_ec)
                {
                    /*
                     * EC-derived clauses can only match by EC.  It is okay to
                     * consider any clause derived from the same EC as
                     * matching the FK: even if equivclass.c chose to generate
                     * a clause equating some other pair of Vars, it could
                     * have generated one equating the FK's Vars.  So for
                     * purposes of estimation, we can act as though it did so.
                     *
                     * Note: checking parent_ec is a bit of a cheat because
                     * there are EC-derived clauses that don't have parent_ec
                     * set; but such clauses must compare expressions that
                     * aren't just Vars, so they cannot match the FK anyway.
                     */
                    if (fkinfo->eclass[i] == rinfo->parent_ec)
                    {
                        remove_it = true;
                        break;
                    }
                }
                else
                {
                    /*
                     * Otherwise, see if rinfo was previously matched to FK as
                     * a "loose" clause.
                     */
                    if (list_member_ptr(fkinfo->rinfos[i], rinfo))
                    {
                        remove_it = true;
                        break;
                    }
                }
            }


			regards, tom lane

  13. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-18T04:09:39Z

    Hi,

A few more comments, about re-reading the patch more thoroughly. I 
wouldn't say any of those qualify as bugs, but rather as discussion 
about some of the design choices:

1) NULL handling

I'd argue that we should do something about this, although I agree it's 
non-trivial to estimate - at least until we get some sort of correlation 
stats (e.g. my patch already provides most of the pieces, I believe). 
But I'd argue that in the case of multi-column foreign keys we can do 
better even without it - my experience is that in such cases either all 
values are NULL or none of them, and a single NULL value breaks the FK 
of course. So I think max(null_frac) would work.

2) get_foreign_key_join_selectivity vs. incomplete matches

The comment right before checking (removedlist == NIL) says:

  * For a multi-column FK, it's possible that we found matches to some
  * columns but not all, implying that one of the above effects applied
  * to just some of the columns.  For the moment, we go ahead and
  * remove those clauses and apply the FK's selectivity anyway.  It
  * might be better to put back the removed clauses and ignore the FK;
  * but that amounts to betting on independence of the clauses, which
  * doesn't seem like a good bet in such messy cases.

Is this a good idea? I'd probably vote to do what's proposed (and 
rejected) in the second half of the comment, i.e. put back the clauses 
and skip the FK as that pretty much says "improve estimate or keep the 
current one, but don't risk making it worse."

3) ForeignKeyOptInfo->rinfos as a List

Can we actually get a list of matching RestrictInfos for a single 
foreign key? I've been unable to construct such query.


regards

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

  14. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-18T16:52:22Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> A few more comments, about re-reading the patch more thoroughly. I 
> wouldn't say any of those qualify as bugs, but rather as discussion 
> about some of the design choices:

> 1) NULL handling

> I'd argue that we should do something about this, although I agree it's 
> non-trivial to estimate - at least until we get some sort of correlation 
> stats (e.g. my patch already provides most of the pieces, I believe). 

I concur, actually, but I feel that it's out of scope for this particular
patch, which is only trying to replace the functionality that was
committed previously.  If you want to come up with a patch on top of this
that adds some accounting for NULLs, I'd be willing to consider it as
a post-beta2 improvement.

> But I'd argue that in the case of multi-column foreign keys we can do 
> better even without it - my experience is that in such cases either all 
> values are NULL or none of them, and a single NULL value breaks the FK 
> of course. So I think max(null_frac) would work.

Yeah, I was thinking along the same lines: max of the per-column null
fractions is probably an OK estimate.

> The comment right before checking (removedlist == NIL) says:
>   * For a multi-column FK, it's possible that we found matches to some
>   * columns but not all, implying that one of the above effects applied
>   * to just some of the columns.  For the moment, we go ahead and
>   * remove those clauses and apply the FK's selectivity anyway.  It
>   * might be better to put back the removed clauses and ignore the FK;
>   * but that amounts to betting on independence of the clauses, which
>   * doesn't seem like a good bet in such messy cases.

> Is this a good idea? I'd probably vote to do what's proposed (and 
> rejected) in the second half of the comment, i.e. put back the clauses 
> and skip the FK as that pretty much says "improve estimate or keep the 
> current one, but don't risk making it worse."

I would buy that approach when it comes to "loose" quals, but I think
it's not right for EC-derived matches, because of the behavior we
discussed previously that an EC should be considered to have implicitly
generated all the matching quals even though it actually made only one
qual that might not be any of them exactly.

Now on the other side of the coin, if several FKs match the same EC,
we might be overshooting the mark to assume that we can just multiply
their selectivity estimates together.  But I think that's not really
a matter for the matching logic, but rather a question of how we want
to combine the estimates for multiple FKs.

Possibly what we could do here is assume that EC matches succeed,
whether there's a matching qual physically in the list or not, but
require a qual match for each column with non-EC matches.  That
would complicate the logic slightly but not terribly (he says without
having actually tried to code it).

If you have a proposal about adjusting the net selectivity estimate when
multiple FKs match the join, let's hear it.  But again that seems like
something we could address as a post-beta2 refinement.

> 3) ForeignKeyOptInfo->rinfos as a List
> Can we actually get a list of matching RestrictInfos for a single 
> foreign key? I've been unable to construct such query.

I think you'd actually have to write redundant outer join quals,
along the lines of
      select ... a left join b on (a.x = b.y and a.x = b.y)
I don't believe we take the trouble to eliminate such duplicates
unless they get absorbed by an EC, which outer-join quals would
not be.  (Haven't tried this, though, as I don't have the patch
installed right now.)


The beta2 deadline is just about upon us; I feel that if we're going
to get this into this release at all, we need to push it today so
that we get a full buildfarm cycle on it before the wrap.

I plan to spend an hour or two adjusting the qual match logic as
discussed above, and re-reading the whole patch another time for
sanity.  If I've not heard objections by the time I'm done,
I will push it.

			regards, tom lane

  15. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-18T19:27:30Z

    I wrote:
> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>> Is this a good idea? I'd probably vote to do what's proposed (and 
>> rejected) in the second half of the comment, i.e. put back the clauses 
>> and skip the FK as that pretty much says "improve estimate or keep the 
>> current one, but don't risk making it worse."

> I would buy that approach when it comes to "loose" quals, but I think
> it's not right for EC-derived matches, because of the behavior we
> discussed previously that an EC should be considered to have implicitly
> generated all the matching quals even though it actually made only one
> qual that might not be any of them exactly.

After further thought I decided you're right, because one of the main
original goals of ECs was to prevent double-counting the selectivity
of redundant equality quals.  Acting as though the EC had generated
multiple redundant quals is likely to make things worse not better.

I still feel that we're leaving something on the table here, but it
would need to take the form of intelligently combining estimates for
overlapping FKs, not just blindly multiplying them together.  Seems
like a task for later, especially considering that cases of this sort
are likely to be rare.

Pushed with adjustments for that.

			regards, tom lane

  16. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-19T10:44:38Z

    On 06/18/2016 09:27 PM, Tom Lane wrote:
> I wrote:
>> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>>> Is this a good idea? I'd probably vote to do what's proposed (and
>>> rejected) in the second half of the comment, i.e. put back the clauses
>>> and skip the FK as that pretty much says "improve estimate or keep the
>>> current one, but don't risk making it worse."
>
>> I would buy that approach when it comes to "loose" quals, but I think
>> it's not right for EC-derived matches, because of the behavior we
>> discussed previously that an EC should be considered to have implicitly
>> generated all the matching quals even though it actually made only one
>> qual that might not be any of them exactly.
>
> After further thought I decided you're right, because one of the main
> original goals of ECs was to prevent double-counting the selectivity
> of redundant equality quals.  Acting as though the EC had generated
> multiple redundant quals is likely to make things worse not better.
>
> I still feel that we're leaving something on the table here, but it
> would need to take the form of intelligently combining estimates for
> overlapping FKs, not just blindly multiplying them together.  Seems
> like a task for later, especially considering that cases of this sort
> are likely to be rare.
>
> Pushed with adjustments for that.

OK, thanks. The one thing we haven't done is testing the performance, to 
see how this fares. So I've repeated the tests I've done on the original 
version of the patch here

https://www.postgresql.org/message-id/8344835e-18af-9d40-aed7-bd2261be9162@2ndquadrant.com

Sadly I don't have access to the machine used for the previous tests (on 
a vacation and the machine sits under my desk at home), so I had to use 
my laptop. That means a fair amount of variability due to power saving 
built into the CPU, and also VM variability (using Xen VM). So the 
numbers are not directly comparable to the old results, and I believe 
the differences between the patched and unpatched version seem to be 
quite clear despite the variability.

It's true the results are not as bad as with the originally committed 
patch, but there are multiple cases where the planning time gets up to 
~2x compared to master.

See the old-results.ods, and also old-scripts.tgz (the old scripts used 
the GUC we removed, so I had to tweak it a bit, and you'll have to whack 
it a bit to get it working).

Sure, those cases use many foreign keys (generally >=100), but the 
conclusion with the old patch was that it matters and we spent a lot of 
time to get it within 10% of master. There are also two or three cases 
where the planning got quite a bit faster, for some reason.

I've also constructed another script, joining just 2 tables and doing 
some funky things (e.g. adding a lot of overlapping foreign keys), and 
in these cases the slowdown is even more significant - up to ~13x, and 
the stddev also increased. See new-results.ods and new-scripts.tgz.

regards

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

  17. Re: New design for FK-based join selectivity estimation

    Tomas Vondra <tomas.vondra@2ndquadrant.com> — 2016-06-19T10:54:40Z

    Hi

On 06/18/2016 06:52 PM, Tom Lane wrote:
> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>> A few more comments, about re-reading the patch more thoroughly. I
>> wouldn't say any of those qualify as bugs, but rather as discussion
>> about some of the design choices:
>
>> 1) NULL handling
>
>> I'd argue that we should do something about this, although I agree it's
>> non-trivial to estimate - at least until we get some sort of correlation
>> stats (e.g. my patch already provides most of the pieces, I believe).
>
> I concur, actually, but I feel that it's out of scope for this
> particular patch, which is only trying to replace the functionality
> that was committed previously. If you want to come up with a patch on
> top of this that adds some accounting for NULLs, I'd be willing to
> consider it as a post-beta2 improvement.

Sure, fair enough. By post-beta2 you mean for 9.7, or still for 9.6?

>
>> But I'd argue that in the case of multi-column foreign keys we can do
>> better even without it - my experience is that in such cases either all
>> values are NULL or none of them, and a single NULL value breaks the FK
>> of course. So I think max(null_frac) would work.
>
> Yeah, I was thinking along the same lines: max of the per-column null
> fractions is probably an OK estimate.

OK

>
>> 3) ForeignKeyOptInfo->rinfos as a List
>> Can we actually get a list of matching RestrictInfos for a single
>> foreign key? I've been unable to construct such query.
>
> I think you'd actually have to write redundant outer join quals,
> along the lines of
>       select ... a left join b on (a.x = b.y and a.x = b.y)
> I don't believe we take the trouble to eliminate such duplicates
> unless they get absorbed by an EC, which outer-join quals would
> not be.  (Haven't tried this, though, as I don't have the patch
> installed right now.)

OK. Let's look into this post-beta2 then.

>
> The beta2 deadline is just about upon us; I feel that if we're going
> to get this into this release at all, we need to push it today so
> that we get a full buildfarm cycle on it before the wrap.
>
> I plan to spend an hour or two adjusting the qual match logic as
> discussed above, and re-reading the whole patch another time for
> sanity.  If I've not heard objections by the time I'm done,
> I will push it.
>

Thanks!

If I could wish one more thing - could you briefly explain why you 
rewrote the patch the way you did? I'd like to learn from this and while 
I think I kinda understand most of the changes, I'm not really sure I 
got it right.

regards

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

  18. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-20T16:39:11Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> OK, thanks. The one thing we haven't done is testing the performance, to 
> see how this fares. So I've repeated the tests I've done on the original 
> version of the patch here

Hmm.  I'm not that excited about these results, for a couple of reasons:

* AFAICS, all the numbers are collected from the first execution of a
query within a session, meaning caches aren't populated and everything
has to be loaded from disk (or at least shared buffers).

* I do not credit hundreds of completely redundant FKs between the same
two tables as being representative of plausible real-world cases.

I modified your new script as attached to get rid of the first problem.
Comparing HEAD with HEAD minus commit 100340e2d, in non-assert builds,
I get results like this for the 100-foreign-key case (with repeat
count 1000 for the data collection script):

select code, test, avg(time),stddev(time) from data group by 1,2 order by 1,2;
  code  | test  |        avg         |       stddev        
--------+-------+--------------------+---------------------
 head   | t1/t2 |  0.065045045045045 | 0.00312962651081508
 head   | t3/t4 |  0.168561561561562 | 0.00379087132124092
 head   | t5/t6 |  0.127671671671672 | 0.00326275949269809
 head   | t7/t8 |  0.391057057057056 | 0.00590249325300915
 revert | t1/t2 | 0.0613933933933937 |  0.0032082678131875
 revert | t3/t4 | 0.0737507507507501 | 0.00221692725859567
 revert | t5/t6 |  0.123759759759759 | 0.00431225386651805
 revert | t7/t8 |  0.154082082082081 | 0.00405118420422266
(8 rows)

So for the somewhat-credible cases, ie 100 unrelated foreign keys,
I get about 3% - 6% slowdown.  The 100-duplicate-foreign-keys case
does indeed look like about a 2X slowdown, but as I said, I do not
think that has anything to do with interesting usage.

In any case, the situation I was worried about making better was
queries joining many tables, which none of this exercises at all.

			regards, tom lane

  19. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-20T16:43:25Z

    Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> On 06/18/2016 06:52 PM, Tom Lane wrote:
>> I concur, actually, but I feel that it's out of scope for this
>> particular patch, which is only trying to replace the functionality
>> that was committed previously. If you want to come up with a patch on
>> top of this that adds some accounting for NULLs, I'd be willing to
>> consider it as a post-beta2 improvement.

> Sure, fair enough. By post-beta2 you mean for 9.7, or still for 9.6?

I think it'd be legitimate to address the NULLs question for 9.6, as long
as the patch is not very large.  If it does turn out to be invasive or
otherwise hard to review, waiting for 9.7 might be more prudent.  But
I argued upthread that failing to consider nulls was a bug in the original
patch, so dealing with them could be considered a bug fix.

> If I could wish one more thing - could you briefly explain why you 
> rewrote the patch the way you did? I'd like to learn from this and while 
> I think I kinda understand most of the changes, I'm not really sure I 
> got it right.

I don't at the moment recall everything I changed, but I'm happy to
answer questions that are more specific than that one ...

			regards, tom lane

  20. Re: New design for FK-based join selectivity estimation

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2016-06-29T19:18:16Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 > Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
 >> Attached is a reworked patch, mostly following the new design proposal 
 >> from this thread.

 Tom> Comments and testing appreciated.

This blows up (see bug 14219 for testcase) in
match_foreign_keys_to_quals on the find_base_rel call(s) in the
following case:

If the query was produced by rule expansion then the code that populates
fkinfo includes FK references to the OLD and NEW RTEs, but those might not
appear in the jointree (the testcase for the bug is a DELETE rule where
NEW clearly doesn't apply) and hence build_simple_rel was not called
(causing find_base_rel to fail). Not sure what the right fix is.

-- 
Andrew (irc:RhodiumToad)

  21. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-06-29T19:34:25Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> If the query was produced by rule expansion then the code that populates
> fkinfo includes FK references to the OLD and NEW RTEs, but those might not
> appear in the jointree (the testcase for the bug is a DELETE rule where
> NEW clearly doesn't apply) and hence build_simple_rel was not called
> (causing find_base_rel to fail). Not sure what the right fix is.

Meh.  I had a vaguely uneasy feeling that just scanning the rtable was
too simplistic, but hadn't thought hard about it.

For a really correct fix we could search the jointree to see which rels
are in it, but that would add code and cycles.  A slightly cheating way to
do it is to not use find_base_rel() but look into the simple_rel_array for
ourselves, and do nothing if there's no rel corresponding to the RTE
index.

			regards, tom lane

  22. Re: New design for FK-based join selectivity estimation

    Adrien Nayrat <adrien.nayrat@dalibo.com> — 2016-12-13T08:10:47Z

    Hi hackers,

The commit 100340e2dcd05d6505082a8fe343fb2ef2fa5b2a introduce an
estimation error :

create table t3 as select j from generate_series(1,10000)
i,generate_series(1,100) j ;
create table t4 as select j from generate_series(1,100) j ;
create unique index ON t4(j);
alter table t3 add constraint fk foreign key (j) references t4(j);
analyze;

9.5.5
explain analyze select * from t3 where j in (select * from t4 where j<10);
                                                     QUERY PLAN

--------------------------------------------------------------------------------------------------------------------
 Hash Semi Join  (cost=2.36..18053.61 rows=90000 width=4) (actual
time=0.217..282.325 rows=90000 loops=1)
   Hash Cond: (t3.j = t4.j)
   ->  Seq Scan on t3  (cost=0.00..14425.00 rows=1000000 width=4)
(actual time=0.112..116.063 rows=1000000 loops=1)
   ->  Hash  (cost=2.25..2.25 rows=9 width=4) (actual time=0.083..0.083
rows=9 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         ->  Seq Scan on t4  (cost=0.00..2.25 rows=9 width=4) (actual
time=0.019..0.074 rows=9 loops=1)
               Filter: (j < 10)
               Rows Removed by Filter: 91
 Planning time: 0.674 ms
 Execution time: 286.043 ms

On 9.6 HEAD

explain analyze select * from t3 where j in (select * from t4 where j<10);
                                                    QUERY PLAN

-------------------------------------------------------------------------------------------------------------------
 Hash Semi Join  (cost=2.36..18053.61 rows=1000000 width=4) (actual
time=0.089..232.327 rows=90000 loops=1)
   Hash Cond: (t3.j = t4.j)
   ->  Seq Scan on t3  (cost=0.00..14425.00 rows=1000000 width=4)
(actual time=0.047..97.926 rows=1000000 loops=1)
   ->  Hash  (cost=2.25..2.25 rows=9 width=4) (actual time=0.032..0.032
rows=9 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         ->  Seq Scan on t4  (cost=0.00..2.25 rows=9 width=4) (actual
time=0.008..0.030 rows=9 loops=1)
               Filter: (j < 10)
               Rows Removed by Filter: 91
 Planning time: 0.247 ms
 Execution time: 235.295 ms
(10 rows)


Estimated row is 10x larger since 100340e2d

Regards,

-- 
Adrien NAYRAT

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

  23. Re: New design for FK-based join selectivity estimation

    Ronan Dunklau <ronan.dunklau@dalibo.com> — 2016-12-13T18:39:23Z

    On mardi 13 décembre 2016 09:10:47 CET Adrien Nayrat wrote:
> Hi hackers,
> 
> The commit 100340e2dcd05d6505082a8fe343fb2ef2fa5b2a introduce an
> estimation error :
[....]
> 
> Estimated row is 10x larger since 100340e2d
> 
> Regards,

Hello,

I think I understand what the problem is. In get_foreign_key_join_selectiviy, 
we remove the restrict info clauses which match a foreign key. This is done so 
that the selectivy is not applied twice (once in the function itself, once 
when processing the restrictinfos).

The problem is, for semi and anti joins, we assume that we have nohing to do 
(costsize.c:4253):

		else if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
		{
			/*
			 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the
			 * fraction of LHS rows that have matches.  If the referenced
			 * table is on the inner side, that means the selectivity is 1.0
			 * (modulo nulls, which we're ignoring for now).  We already
			 * covered the other case, so no work here.
			 */
		}

This results in assuming that the whole outerrel will match, no matter the 
selectivity of the innerrel.

If I understand it correctly and the above is right, I think we should ignore 
SEMI or ANTI joins altogether when considering FKs, and keep the corresponding 
restrictinfos for later processing since they are already special-cased later 
on. 

Regards,

--
Ronan Dunklau

  24. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-12-13T19:44:07Z

    ronan.dunklau@dalibo.com writes:
> On mardi 13 décembre 2016 09:10:47 CET Adrien Nayrat wrote:
>> The commit 100340e2dcd05d6505082a8fe343fb2ef2fa5b2a introduce an
>> estimation error :

> The problem is, for semi and anti joins, we assume that we have nohing to do 
> (costsize.c:4253):

> 		else if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
> 		{
> 			/*
> 			 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the
> 			 * fraction of LHS rows that have matches.  If the referenced
> 			 * table is on the inner side, that means the selectivity is 1.0
> 			 * (modulo nulls, which we're ignoring for now).  We already
> 			 * covered the other case, so no work here.
> 			 */
> 		}

> This results in assuming that the whole outerrel will match, no matter the 
> selectivity of the innerrel.

Yeah.  In the terms of this example, the FK means that every outer row
would have a match, if the query were

	select * from t3 where j in (select * from t4);

But actually it's

	select * from t3 where j in (select * from t4 where j<10);

so of course we should not expect a match for every row.

> If I understand it correctly and the above is right, I think we should ignore 
> SEMI or ANTI joins altogether when considering FKs, and keep the corresponding 
> restrictinfos for later processing since they are already special-cased later 
> on. 

That seems like an overreaction.  While the old code happens to get this
example exactly right, eqjoinsel_semi is still full of assumptions and
approximations, and it doesn't do very well at all if it lacks MCV lists
for both sides.

I'm inclined to think that what we want to have happen in this case is
to estimate the fraction of outer rows having a match as equal to the
selectivity of the inner query's WHERE clauses, ie the semijoin
selectivity should be sizeof(inner result) divided by sizeof(inner
relation).

			regards, tom lane

  25. Re: New design for FK-based join selectivity estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2016-12-15T20:51:43Z

    I wrote:
> ronan.dunklau@dalibo.com writes:
>> If I understand it correctly and the above is right, I think we should ignore
>> SEMI or ANTI joins altogether when considering FKs, and keep the corresponding
>> restrictinfos for later processing since they are already special-cased later
>> on.

> That seems like an overreaction.  While the old code happens to get this
> example exactly right, eqjoinsel_semi is still full of assumptions and
> approximations, and it doesn't do very well at all if it lacks MCV lists
> for both sides.

> I'm inclined to think that what we want to have happen in this case is
> to estimate the fraction of outer rows having a match as equal to the
> selectivity of the inner query's WHERE clauses, ie the semijoin
> selectivity should be sizeof(inner result) divided by sizeof(inner
> relation).

After further study, I concluded that we can only easily estimate that
when the inner side of the SEMI or ANTI join is just the single referenced
table.  If the inner side is itself a join, it's not easy to determine
what fraction of the referenced table will survive the join clauses.

However, we can still be brighter than to just throw all the FK qual
clauses back into the pool: that would result in multiplying their
selectivity estimates together, which for a multi-column FK results in
exactly the drastic underestimation that 100340e2d intended to avoid.
What seems to make sense here is to take the minimum of the per-clause
selectivities, as we are doing for other outer-join cases.

Hence, I propose the attached patch.  This rearranges the existing code
slightly to avoid duplicating it.

			regards, tom lane