Re: Is there value in having optimizer stats for joins/foreignkeys?

I have indeed started by implementing MCV statistics for joins,
because I have not found a case for joins that would benefit only from
ndistinct or functional dependency stats that MCV stats wouldn't help.

In my POC patch, I've made the following catalog changes:

To use them, we can let the planner detect patterns like this:

/*
 * JoinStatsMatch - Information about a detected join pattern
 * Used internally to track what was matched in a join+filter pattern
 */
typedef struct JoinStatsMatch
{
    Oid          target_rel;       /* table OID of the estimation target */
    AttrNumber targetrel_joinkey;    /* target_rel's join column */
    Oid          other_rel;       /* table OID of the filter source */
    AttrNumber otherrel_joinkey;        /* other_rel's join column */
    List      *filter_attnums;       /* list of AttrNumbers for filter columns in other_rel */
    List      *filter_values;    /* list of Datum constant values being filtered */
    Oid          collation;       /* collation for comparisons */

    /* Additional info to avoid duplicate work */
    List      *join_rinfos;      /* list of join clause RestrictInfos */
    RestrictInfo *filter_rinfo;       /* the filter clause RestrictInfo */
} JoinStatsMatch;

and add the detection logic in clauselist_selectivity_ext() and get_foreign_key_join_selectivity(). 

Statistics collection indeed needs the most thinking. For the
purpose of a POC, I added MCV join stats collection as part of ANALYZE
of one table (stxrel in pg_statistic_ext). I can do this because MCV
join stats are somewhat asymmetric. It allows me to have a target
table (referencing table for foreign key join) to ANALYZE, and we can
use the already collected MCVs of the joinkey column on the target
table to query the rows in the other table. This greatly mitigates
performance impact compared to actually joining two tables. However,
if we are to support more complex joins or other types of join stats
such as ndistinct or functional dependency, I found it hard to define
who's the target table (referencing table) and who's the other table
(referenced table) outside of the foreign key join scenario. So I
think for those more complex cases eventually we may as well 
perform the joins and collect the join stats separately. Alvaro
Herrera suggested offline that we could have a dedicated autovacuum
command option for collecting the join statistics.

I have experimented with two ways to define the join statistics:

1. Use CREATE STATISTICS:

CREATE STATISTICS movie_keyword_keyword_join_stats (mcv)

ON k.keyword 

FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id); 

ANALYZE movie_keyword;

-- Create join MCV statistics on multiple filter columns (keyword + phonetic_code):

CREATE STATISTICS movie_keyword_keyword_multicols_join_stats (mcv)

ON k.keyword, k.phonetic_code

FROM movie_keyword mk JOIN keyword k ON (mk.keyword_id = k.id);

ANALYZE movie_keyword;

Initially, I did not implement the CREATE TABLE STATISTICS command to
create the join stats. Instead, I’ve implemented logic in ANALYZE to
detect functional dependency stats on the referenced table through FKs
and create join statistics implicitly for those cases.

I've been using the Join Order Benchmark (JOB) [1] to measure
performance gain. I will post the POC patch and performance numbers in
a followup email.

[1] https://www.vldb.org/pvldb/vol9/p204-leis.pdf

Best,

Alex