On Wed, Sep 30, 2015 at 10:12 AM, David Rowley
<david.row...@2ndquadrant.com> wrote:
> On 29 September 2015 at 01:59, Tomas Vondra <tomas.von...@2ndquadrant.com>
> wrote:
>> Hi,
>> On 09/27/2015 02:00 PM, David Rowley wrote:
>>> I've been working on this again. I've put back the code that you wrote
>>> for the looping over each combination of relations from either side of
>>> the join.
>>> I've also added some code to get around the problem with eclass joins
>>> and the RestrictInfo having some alternative Vars that don't belong to
>>> the foreign key. Basically I'm just checking if the RestrictInfo has a
>>> parent_ec, and if it does just loop over the members to try and find the
>>> Vars that belong to the foreign key. I've tested it with the following,
>>> and it seems to work:
>> I didn't have time to look into the code yet, but this seems like an
>> interesting idea.
>>> create table a as select i as a_id1, i as a_id2, i as dummy1 from
>>> generate_series(0,999) s(i);
>>> alter table a add unique (a_id1, a_id2);
>>> create table b as select i as b_id1, i as b_id2 from
>>> generate_series(0,332) s(i);
>>> analyze a;
>>> analyze b;
>>> alter table b add foreign key (b_id1, b_id2) references a (a_id1, a_id2);
>>> explain analyze select * from a inner join b on a.dummy1 = b.b_id1 and
>>> a.a_id2 = b.b_id2 where a.a_id1 = a.dummy1;
>>>                                                   QUERY PLAN
>>> -----------------------------------------------------------------------------------------------------------
>>>   Hash Join  (cost=18.57..26.41 rows=2 width=20) (actual
>>> time=0.775..1.046 rows=333 loops=1)
>>>     Hash Cond: ((b.b_id1 = a.dummy1) AND (b.b_id2 = a.a_id2))
>>>     ->  Seq Scan on b  (cost=0.00..5.33 rows=333 width=8) (actual
>>> time=0.013..0.046 rows=333 loops=1)
>>>     ->  Hash  (cost=18.50..18.50 rows=5 width=12) (actual
>>> time=0.737..0.737 rows=1000 loops=1)
>>>           Buckets: 1024  Batches: 1  Memory Usage: 51kB
>>>           ->  Seq Scan on a  (cost=0.00..18.50 rows=5 width=12) (actual
>>> time=0.014..0.389 rows=1000 loops=1)
>>>                 Filter: (dummy1 = a_id1)
>>> The non-patched version estimates 1 row. The patched estimates 2 rows,
>>> but that's due to the bad estimate on dummy1 = a_id1.
>>> The 2 comes from ceil(5 * 0.333).
>>> Perhaps you have a better test case to for this?
>> I think the additional WHERE clause is needlessly confusing. I've been
>> able to come up with an example - pretty much a normalized with a "main"
>> table and auxiliary tables (referencing the main one using FK) with
>> additional info. So not unlikely to happen in practice (except maybe for the
>> multi-column foreign key bit).
>> CREATE TABLE f (id1 INT, id2 INT, PRIMARY KEY (id1, id2));
>> f(id1, id2));
>> f(id1, id2));
>> INSERT INTO f SELECT i, i FROM generate_series(1,1000000) s(i);
>> INSERT INTO d1 SELECT i, i FROM generate_series(1,100000) s(i);
>> INSERT INTO d2 SELECT i, i FROM generate_series(1,300000) s(i);
>> now, both pair-wise joins (f JOIN d1) and (f JOIN d2) are estimated
>> perfectly accurately, but as soon as the query involves both of them, this
>> happens:
>> SELECT * FROM f JOIN d1 ON (f.id1 = d1.id1 AND f.id2 = d1.id2)
>>                 JOIN d2 ON (f.id1 = d2.id1 AND f.id2 = d2.id2);
>>                           QUERY PLAN
>> -------------------------------------------------------------------------
>>  Nested Loop  (cost=3334.43..12647.57 rows=30000 width=24)
>>               (actual time=221.086..1767.206 rows=100000 loops=1)
>>    Join Filter: ((d1.id1 = f.id1) AND (d1.id2 = f.id2))
>>    ->  Hash Join  (cost=3334.00..12647.01 rows=1 width=16)
>>                   (actual time=221.058..939.482 rows=100000 loops=1)
>>          Hash Cond: ((d2.id1 = d1.id1) AND (d2.id2 = d1.id2))
>>          ->  Seq Scan on d2  (cost=0.00..4328.00 rows=300000 width=8)
>>                      (actual time=0.038..263.356 rows=300000 loops=1)
>>          ->  Hash  (cost=1443.00..1443.00 rows=100000 width=8)
>>                    (actual time=220.721..220.721 rows=100000 loops=1)
>>                Buckets: 131072  Batches: 2  Memory Usage: 2982kB
>>                ->  Seq Scan on d1  (cost=0.00..1443.00 rows=100000 ...)
>>                        (actual time=0.033..101.547 rows=100000 loops=1)
>>    ->  Index Only Scan using f_pkey on f  (cost=0.42..0.54 rows=1 ...)
>>                         (actual time=0.004..0.004 rows=1 loops=100000)
>>          Index Cond: ((id1 = d2.id1) AND (id2 = d2.id2))
>>          Heap Fetches: 100000
>> Clearly, the inner join (d1 JOIN d2) is poorly estimated (1 vs. 100000). I
>> assume that's only because we find FK only on the second join with f.
>> So it seems like s a clear improvement, both compared to master and the
>> previous versions of the patch.
> I've been experimenting with this example. Of course, the reason why we get
> the 1 row estimate on the join between d1 and d2 is that there's no foreign
> key between those two relations.
> The attached patch changes things so that the foreign key matching code is
> better able to see foreign keys "hidden" behind eclasses. So it does now in
> fact detect a foreign key on d2 referencing d1, by looking for Vars foreign
> keys which have Vars in the same eclasses as the joinquals are built from.
> This has improved the result
> postgres=# EXPLAIN ANALYZE SELECT * FROM f JOIN d1 ON (f.id1 = d1.id1 AND
> f.id2 = d1.id2) JOIN d2 ON (f.id1 = d2.id1 AND f.id2 = d2.id2);
>                                                                    QUERY
> -------------------------------------------------------------------------------------------------------------------------------------------------
>  Hash Join  (cost=16655.94..26066.95 rows=30000 width=24) (actual
> time=267.322..468.383 rows=100000 loops=1)
>    Hash Cond: ((d2.id1 = f.id1) AND (d2.id2 = f.id2))
>    ->  Seq Scan on d2  (cost=0.00..4328.00 rows=300000 width=8) (actual
> time=0.019..31.396 rows=300000 loops=1)
>    ->  Hash  (cost=14666.94..14666.94 rows=100000 width=16) (actual
> time=266.263..266.263 rows=100000 loops=1)
>          Buckets: 131072  Batches: 2  Memory Usage: 3373kB
>          ->  Merge Join  (cost=9748.32..14666.94 rows=100000 width=16)
> (actual time=104.494..224.908 rows=100000 loops=1)
>                Merge Cond: ((f.id1 = d1.id1) AND (f.id2 = d1.id2))
>                ->  Index Only Scan using f_pkey on f  (cost=0.42..36214.93
> rows=1000000 width=8) (actual time=0.045..35.758 rows=100001 loops=1)
>                      Heap Fetches: 100001
>                ->  Sort  (cost=9747.82..9997.82 rows=100000 width=8) (actual
> time=104.440..122.401 rows=100000 loops=1)
>                      Sort Key: d1.id1, d1.id2
>                      Sort Method: external sort  Disk: 2152kB
>                      ->  Seq Scan on d1  (cost=0.00..1443.00 rows=100000
> width=8) (actual time=0.019..9.443 rows=100000 loops=1)
> The problem is that the code I added is sometimes a bit too optimistic at
> finding a suitable foreign key. When performing estimates for the join
> between (f,d1) <-> (d2), since the code loops over each relation making up
> the set of relations at either side of the join, we find a foreign key on
> 'f' which references d2, this one actually exists. It then goes on and also
> finds a foreign key for (d1) references (d2), of course this one does not
> exists and it's only could due to the eclasses. The problem here is, which
> one do we use? If we multiply the selectivity for each of these foreign keys
> then we'd end up with a selectivty = (1.0 / 1000000) * (1.0 / 300000), which
> is a massive underestimation. Perhaps doing this would be perfectly valid if
> the actual foreign key being around was not the same one as the last one,
> but this seems wrong when we match to the same foreign key in both
> instances.
> I've gone though a few variations on ways to handle this and I'm a bit stuck
> on what's the best way.
> In the attached I've coded it to take the Min() selectivity for when the
> same quals are matched more than once. I know this is not correct, but since
> it seems impossible to obtain an exact estimate in this case, we'd need to
> decide on some logic which does well in the average case.

Is there still an interest for this patch? The last message of this
thread has added a new version of the patch but the patch was still in
"Waiting on author" state for a couple of months. Just guessing that
the status was incorrect, I have moved it to next CF.

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to