Re: PATCH: use foreign keys to improve join estimates v1 - Mailing list pgsql-hackers

2) find_best_match_foreign_key
------------------------------

I think the comment before the function needs rephrasing (seems a bit broken to me). I do like the approach in general, although it changes the semantics a bit. The original code only considered "fully matching" fkeys, while the new code simply takes the longest match.

The comment before the function mentions it's possible to confuse the code with duplicate quals. Can you give an example?

3) clauselist_join_selectivity
------------------------------

I think this is actually broken, i.e. it does not handle the cases it was handling before - namely the cases where more than 3 tables are joined (fkjoin2.sql).

Imagine a "fact" table referencing two dimensions, using 2-column fkeys:

create table a (a1 int, a2 int, unique (a1,a2));
create table b (b1 int, b2 int, unique (b1,b2));
create table f (a1 int, a2 int, b1 int, b2 int);

insert into a select i,i from generate_series(0,999999) s(i);
insert into b select i,i from generate_series(0,999999) s(i);
insert into f select i/10,i/10,i/10,i/10
                from generate_series(0,9999999) s(i);

alter table f add foreign key (a1,a2) references a(a1,a2);
alter table f add foreign key (b1,b2) references b(b1,b2);

Each dimension has 1M rows, fact has 10M rows (and references each row in dimensions 10x).

Now, let's see this simple star join:

explain select * from f join a using (a1,a2)
                        join b using (b1,b2);

This should return all 10M rows, and originally this was estimated like this:

                                 QUERY PLAN
-----------------------------------------------------------------------
Hash Join  (cost=66664.00..573853.57 rows=10000175 width=16)
  Hash Cond: ((f.b1 = b.b1) AND (f.b2 = b.b2))
  ->  Hash Join  (cost=33332.00..363955.16 rows=10000175 width=16)
       Hash Cond: ((f.a1 = a.a1) AND (f.a2 = a.a2))
       ->  Seq Scan on f  (cost=0.00..154056.75 rows=10000175 width=16)
       ->  Hash  (cost=14425.00..14425.00 rows=1000000 width=8)
           ->  Seq Scan on a  (cost=0.00..14425.00 rows=1000000 width=8)
   ->  Hash  (cost=14425.00..14425.00 rows=1000000 width=8)
         ->  Seq Scan on b  (cost=0.00..14425.00 rows=1000000 width=8)

so pretty much perfectly accurate, while the new code does this:

                                 QUERY PLAN
----------------------------------------------------------------------
 Hash Join  (cost=66664.00..573853.57 rows=10 width=16)
   Hash Cond: ((f.b1 = b.b1) AND (f.b2 = b.b2))
   ->  Hash Join  (cost=33332.00..363955.16 rows=10000175 width=16)
       Hash Cond: ((f.a1 = a.a1) AND (f.a2 = a.a2))
        ->  Seq Scan on f  (cost=0.00..154056.75 rows=10000175 width=16)
        ->  Hash  (cost=14425.00..14425.00 rows=1000000 width=8)
           ->  Seq Scan on a  (cost=0.00..14425.00 rows=1000000 width=8)
   ->  Hash  (cost=14425.00..14425.00 rows=1000000 width=8)
        ->  Seq Scan on b  (cost=0.00..14425.00 rows=1000000 width=8)

I think this is due to this check in clauselist_join_selectivity:

   if (bms_get_singleton_member(sjinfo->min_righthand, &innerrelid) &&
       bms_get_singleton_member(sjinfo->min_lefthand, &outerrelid))

which pretty much says "only work with joins on two base relations". So as long as you have a joinrel, (e.g. a fact + one of the dimensions), it's game over.

I think the restriction is unnecessary, because when estimating joins, we effectively take cardinality of a cartesian product of all the base relations, and then apply selectivities for all the join quals (in a pairwise manner).

So for the three tables we take

   card(join) = card(f) * card(a) * card(b) * sel(f,a) * sel(f,b)

and we can consider the foreign keys in the pairwise selectivities.