Re: PATCH: use foreign keys to improve join estimates v1

Hi,

Thanks for the review and time spent on reworking the patch!

On 09/24/2015 07:41 AM, David Rowley wrote:
> On 23 September 2015 at 17:11, David Rowley
> <david(dot)rowley(at)2ndquadrant(dot)com <mailto:david(dot)rowley(at)2ndquadrant(dot)com>> wrote:
>
> find_foreign_key_clauses() should look for the longest match and
> return a Bitmap set of the list indexes to the caller.
> It might be possible to fool the longest match logic by duplicating
> clauses, e.g. a1 = b1 AND a1 = b1 and a1 = b1 AND a2 = b2 AND a3 =
> b3, but I can't imagine that matters, but if it did, we could code
> it to be smart enough to see through that.
>
>
> I took a bash at implementing what I described, and I've ended up with
> the attached.
>
> git diff -stat gives me:
>
> src/backend/optimizer/path/costsize.c | 717
> ++++++++----------------------
> src/backend/optimizer/plan/analyzejoins.c | 1 +
> src/backend/optimizer/util/plancat.c | 112 +++--
> 3 files changed, 228 insertions(+), 602 deletions(-)
>
> So it's removed quite a bit of code. I also discovered that: 1.0 /
> Max(rel->tuples,1.0) is no good for SEMI and ANTI joins. I've coded
> around this in the attached, but I'm not certain it's the best way of
> doing things.
>
> I thought that it might be possible to add some regression test around
> this, if we simply just find a plan the uses a nested loop due to
> underestimation of matching rows, and then make sure that it no longer
> uses a nested loop when the foreign key is added. I've not yet done this
> in the attached.
>
> Patched attached in delta form and complete form.
>
> I still need to perform more analysis on the plancat.c changes.
>
> Have I made any changes that you disagree with?

I think the changes in general are a step in the right direction, but
I've noticed some differences in behavior - some of them may be actually
desirable, other are bugs I believe.

1) (rel)hasindex
----------------

I'm perfectly fine with getting rid of hasindex, it was mostly
cargo-cult programming anyway.

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.

Let me illustrate on a somewhat artificial example (fkjoin1.sql):

create table t1 (a int, b int, c int, d int,
unique(a,b), unique(a,b,c,d));

create table t2 (a int, b int, c int, d int,
foreign key (a,b) references t1(a,b),
foreign key (a,b,c,d) references t2(a,b,c,d));

insert into t1 select i, i, i, i from generate_series(1,1000000) s(i);
insert into t2 select i, i, i, i from generate_series(1,1000000) s(i);

Now, let's say a query joining the tables on (a,b,c). The original code
did this

explain select * from t1 join t2 using (a,b,c);

QUERY PLAN
-------------------------------------------------------------------------
Hash Join (cost=37789.00..79094.01 rows=1 width=20)
Hash Cond: ((t1.a = t2.a) AND (t1.b = t2.b) AND (t1.c = t2.c))
-> Seq Scan on t1 (cost=0.00..15406.00 rows=1000000 width=16)
-> Hash (cost=15406.00..15406.00 rows=1000000 width=16)
-> Seq Scan on t2 (cost=0.00..15406.00 rows=1000000 width=16)

while the new code does this:

QUERY PLAN
-------------------------------------------------------------------------
Hash Join (cost=37789.00..79094.01 rows=1000000 width=20)
Hash Cond: ((t1.a = t2.a) AND (t1.b = t2.b) AND (t1.c = t2.c))
-> Seq Scan on t1 (cost=0.00..15406.00 rows=1000000 width=16)
-> Hash (cost=15406.00..15406.00 rows=1000000 width=16)
-> Seq Scan on t2 (cost=0.00..15406.00 rows=1000000 width=16)

This happens (I believe) because the new code only looks for the longest
match, without the "full match" restriction. So while the old code finds
(a,b)+c, the new code finds (a,b,c,d).

I'm not saying the new code is wrong - the "full match" restriction was
there just to simplify v1 of the patch, because dealing with partial
matches is a bit more complicated. So it's desirable to relax this
condition.

It's also true that the new code works better in some cases, e.g. this

explain select * from t1 join t2 using (a,b,c,d);

QUERY PLAN
-----------------------------------------------------------------------
Hash Join (cost=40289.00..85344.01 rows=1000000 width=16)
Hash Cond: ((t1.a = t2.a) AND (t1.b = t2.b) AND (t1.c = t2.c)
AND (t1.d = t2.d))
-> Seq Scan on t1 (cost=0.00..15406.00 rows=1000000 width=16)
-> Hash (cost=15406.00..15406.00 rows=1000000 width=16)
-> Seq Scan on t2 (cost=0.00..15406.00 rows=1000000 width=16)

was originally estimated like this

QUERY PLAN
------------------------------------------------------------------------
Hash Join (cost=40289.00..85344.01 rows=1 width=16)
Hash Cond: ((t1.a = t2.a) AND (t1.b = t2.b) AND (t1.c = t2.c)
AND (t1.d = t2.d))
-> Seq Scan on t1 (cost=0.00..15406.00 rows=1000000 width=16)
-> Hash (cost=15406.00..15406.00 rows=1000000 width=16)
-> Seq Scan on t2 (cost=0.00..15406.00 rows=1000000 width=16)

because apparently it found (a,b) and then multiplied it with c and d.

Those examples are of course a bit artificial - I'd guess tables with
multiple multi-column fkeys (and matching multiple of those fkeys in a
single query) are rather rare. But if we're willing to handle multiple
foreign keys (as searching for the "best" match suggests we are), we
should probably try to handle these cases better.

Relaxing the "full match" restriction seems valuable on it's own, I
guess - we can't really assume the partial match still has 1/nrows
selectivity, though. We need to increase the selectivity as the
condition may match multiple tuples on the PK end.

I was thinking about two ways to address this:

(a) Assuming each condition contributes equally to the selectivity,
so if the foreign key is on k columns, it's actually

1/nrows = selectivity^k

so for example if the FK is on 2 columns, and there are 1.000.000
rows on the PK side, each column contributes ~1/1000. If there
are 3 columns, it's ~1/100 per column, so matching only 2 columns
on a 3-column key would have selectivity 1/1e4 and not 1/1e6.

(b) The previous approach of course assumes that each column
contributes equally to the selectivity, but that may not really
be true in practice - the cardinality of the columns may be very
different. So I was thinking about somehow using ndistinct for the
columns in this, but I don't have a clear idea on how to do that.

What's your opinion on this?

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.

At least that's my understanding ...

regards
Tomas

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