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

>
> Right. I have not investigated plans for the JOB queries, but a common
> issue is that we pick a nested loop very early in the plan due to a poor
> estimate, and that leads to a sequence of nested loops. Which just
> amplifies the problem.
>

Even if the plan still uses nested loops, there are other things that
benefit from better row estimates. For instance, I've seen a case where the
planner decided to apply jit to the query because it expected 40 million
rows of results...and it got 4.

> > Catalog changes:
> >
> > pg_statistic_ext:
> > - New stats kind 'c' (join MCV) in stxkind
> > - New field stxotherrel (Oid): the other table in the join
> > - New field stxjoinkeys (int2vector): join column pair [primary_joinkey,
> > other_joinkey]
> > - Existing stxkeys stores the filter column(s) on stxotherrel
> > - New index pg_statistic_ext_otherrel_index on (stxrelid, stxotherrel)
> >
>
> - Why do we need a new stats kind? I'd have expected we'd use the same
> 'm' value as for a single-relation stats, simply because a join result
> is just a relation too.
>
> - For a PoC it's OK to have stxotherrel, but the final patch should not
> be restricted to two relations. I think there needs to be an array of
> the joined rel OIDs, or something like that.
>

A parallel array of joined rel oids could lead to some refetching of
relation tuples unless we insisted that the keys be sorted the way we
currently sort stxkeys.

However, a multi-relation extended statistic object runs into a practical
issue when we fetch the remote rows that join to the local rowsample. We
could do that with an EphemeralNamedRelation and SPI (yuck), or more likely
we would leverage the index defined for the foreign key that we're
requiring (we already do this for referential integrity lookups on
inserts), and fishing out those foreign keys from a multi-table select,
which while do-able doesn't sound like fun. If we go that route then the
inability to find a supporting foreign key (and the index that goes with
it) should fail the statistic object creation.

So an array of RI constraint Oids (InvalidOid means "The attnum in the same
array position represents a local column/expression" would give us the
ability to do MCV combinations of columns from N tables along with the
local table, provided that there are fk constraints for each of the joins.

> FWIW I recognize figuring out the catalog changes is not easy - in fact
> I always found it so intimidation I ended up procrastinating and not
> making any progress on join statistics. So I really appreciate you
> taking a stab at this.
>

+1

>
> > pg_statistic_ext_data:
> > - New field stxdjoinmcv (pg_join_mcv_list): serialized join MCV data
> >
>
> I don't understand why we need this. AFAICS we should just treat the
> join result as a relation, and use the current pg_statistic_ext_data
> fields.
>

As I said above, we'd need a parallel array of constraint keys, rel ids, or
both to make that work.

>
> > How stats are collected:
> >
> > Join statistics are collected during ANALYZE of the primary table
> > (stxrelid). The current approach assumes a dependency relationship
> > between the join key column and the filter column(s) on the other
> > table. Specifically, during ANALYZE, we reuse the already-computed
> > single-column MCV stats for the primary table's join key column. For
> > each MCV value, we look up the matching row in the other table via the
> > join key and extract the filter column values, carrying over the
> > primary-side MCV frequency. This is not accurate in all cases, but
> > works reasonably well for the POC, especially for foreign-key-like
> > joins where the primary table's join key distribution is
> > representative of the join result.
> >
>
> For the PoC it's good enough, but I don't think we can rely on the
> per-column MCV lists like this.
>

Agreed. We must go to the source.

> The best approach I'm aware of is the "Index-Based Join Sampling" paper
> I mentioned earlier in this thread. I think it's OK to allow building
> statistics only for joins compatible with that sampling approach.
>
> It's not clear to me what should trigger building the stats. I assume
> it'd be done by ANALYZE, but that's per-table. So would it be triggered
> by ANALYZE on any of the joined tables, or just the "main" one? Would it
> require a new ANALYZE option, or something else? Not sure.
>

Just the main one. Madness lies in the alternative