[prev in list] [next in list] [prev in thread] [next in thread]
List: postgresql-general
Subject: Re: [HACKERS] PATCH: use foreign keys to improve join estimates v1
From: David Rowley <david.rowley () 2ndquadrant ! com>
Date: 2015-09-30 1:12:11
Message-ID: CAKJS1f_K3ON13bmpyBwRd=RAPRPN_ju47vSA8GzLk_kNa=smWw () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On 29 September 2015 at 01:59, Tomas Vondra <tomas.vondra@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.57..26.41 rows=2 width ) (actual
> > time=0.775..1.046 rows33 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 rows33 width=8) (actual
> > time=0.013..0.046 rows33 loops=1)
> > -> Hash (cost.50..18.50 rows=5 width) (actual
> > time=0.737..0.737 rows00 loops=1)
> > Buckets: 1024 Batches: 1 Memory Usage: 51kB
> > -> Seq Scan on a (cost=0.00..18.50 rows=5 width) (actual
> > time=0.014..0.389 rows00 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));
>
> CREATE TABLE d1 (id1 INT, id2 INT, FOREIGN KEY (id1, id2) REFERENCES
> f(id1, id2));
> CREATE TABLE d2 (id1 INT, id2 INT, FOREIGN KEY (id1, id2) REFERENCES
> 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 (cost334.43..12647.57 rows0000 width$)
> (actual time"1.086..1767.206 rows0000 loops=1)
> Join Filter: ((d1.id1 = f.id1) AND (d1.id2 = f.id2))
> -> Hash Join (cost334.00..12647.01 rows=1 width)
> (actual time"1.058..939.482 rows0000 loops=1)
> Hash Cond: ((d2.id1 = d1.id1) AND (d2.id2 = d1.id2))
> -> Seq Scan on d2 (cost=0.00..4328.00 rows00000 width=8)
> (actual time=0.038..263.356 rows00000 loops=1)
> -> Hash (cost43.00..1443.00 rows0000 width=8)
> (actual time"0.721..220.721 rows0000 loops=1)
> Buckets: 131072 Batches: 2 Memory Usage: 2982kB
> -> Seq Scan on d1 (cost=0.00..1443.00 rows0000 ...)
> (actual time=0.033..101.547 rows0000 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 loops0000)
> 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
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost655.94..26066.95 rows0000 width$) (actual
time&7.322..468.383 rows0000 loops=1)
Hash Cond: ((d2.id1 = f.id1) AND (d2.id2 = f.id2))
-> Seq Scan on d2 (cost=0.00..4328.00 rows00000 width=8) (actual
time=0.019..31.396 rows00000 loops=1)
-> Hash (cost666.94..14666.94 rows0000 width) (actual
time&6.263..266.263 rows0000 loops=1)
Buckets: 131072 Batches: 2 Memory Usage: 3373kB
-> Merge Join (cost—48.32..14666.94 rows0000 width)
(actual time4.494..224.908 rows0000 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
rows00000 width=8) (actual time=0.045..35.758 rows0001 loops=1)
Heap Fetches: 100001
-> Sort (cost—47.82..9997.82 rows0000 width=8)
(actual time4.440..122.401 rows0000 loops=1)
Sort Key: d1.id1, d1.id2
Sort Method: external sort Disk: 2152kB
-> Seq Scan on d1 (cost=0.00..1443.00 rows0000
width=8) (actual time=0.019..9.443 rows0000 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.
--
David Rowley http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/>
PostgreSQL Development, 24x7 Support, Training & Services
[Attachment #5 (text/html)]
<div dir="ltr"><div class="gmail_extra"><div><div class="gmail_signature"><div \
dir="ltr">On 29 September 2015 at 01:59, Tomas Vondra <span dir="ltr"><<a \
href="mailto:tomas.vondra@2ndquadrant.com" \
target="_blank">tomas.vondra@2ndquadrant.com</a>></span> \
wrote:<br></div></div></div><div class="gmail_quote"><blockquote class="gmail_quote" \
style="margin:0px 0px 0px \
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi,<span \
class=""><br> <br>
On 09/27/2015 02:00 PM, David Rowley wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I've been working on this again. I've put back the code that you wrote<br>
for the looping over each combination of relations from either side of<br>
the join.<br>
<br>
I've also added some code to get around the problem with eclass joins<br>
and the RestrictInfo having some alternative Vars that don't belong to<br>
the foreign key. Basically I'm just checking if the RestrictInfo has a<br>
parent_ec, and if it does just loop over the members to try and find the<br>
Vars that belong to the foreign key. I've tested it with the following,<br>
and it seems to work:<br>
</blockquote>
<br></span>
I didn't have time to look into the code yet, but this seems like an interesting \
idea.<div><div class="h5"><br> <br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
create table a as select i as a_id1, i as a_id2, i as dummy1 from<br>
generate_series(0,999) s(i);<br>
alter table a add unique (a_id1, a_id2);<br>
create table b as select i as b_id1, i as b_id2 from<br>
generate_series(0,332) s(i);<br>
<br>
analyze a;<br>
analyze b;<br>
<br>
alter table b add foreign key (b_id1, b_id2) references a (a_id1, a_id2);<br>
<br>
explain analyze select * from a inner join b on a.dummy1 = b.b_id1 and<br>
a.a_id2 = b.b_id2 where a.a_id1 = a.dummy1;<br>
<br>
QUERY \
PLAN<br>
-----------------------------------------------------------------------------------------------------------<br>
Hash Join (cost=18.57..26.41 rows=2 width=20) (actual<br>
time=0.775..1.046 rows=333 loops=1)<br>
Hash Cond: ((b.b_id1 = a.dummy1) AND (b.b_id2 = a.a_id2))<br>
-> Seq Scan on b (cost=0.00..5.33 rows=333 width=8) (actual<br>
time=0.013..0.046 rows=333 loops=1)<br>
-> Hash (cost=18.50..18.50 rows=5 width=12) (actual<br>
time=0.737..0.737 rows=1000 loops=1)<br>
Buckets: 1024 Batches: 1 Memory Usage: 51kB<br>
-> Seq Scan on a (cost=0.00..18.50 rows=5 width=12) (actual<br>
time=0.014..0.389 rows=1000 loops=1)<br>
Filter: (dummy1 = a_id1)<br>
<br>
The non-patched version estimates 1 row. The patched estimates 2 rows,<br>
but that's due to the bad estimate on dummy1 = a_id1.<br>
<br>
The 2 comes from ceil(5 * 0.333).<br>
<br>
Perhaps you have a better test case to for this?<br>
</blockquote>
<br></div></div>
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).<br> <br>
<br>
CREATE TABLE f (id1 INT, id2 INT, PRIMARY KEY (id1, id2));<br>
<br>
CREATE TABLE d1 (id1 INT, id2 INT, FOREIGN KEY (id1, id2) REFERENCES f(id1, \
id2));<br> CREATE TABLE d2 (id1 INT, id2 INT, FOREIGN KEY (id1, id2) REFERENCES \
f(id1, id2));<br> <br>
INSERT INTO f SELECT i, i FROM generate_series(1,1000000) s(i);<br>
<br>
INSERT INTO d1 SELECT i, i FROM generate_series(1,100000) s(i);<br>
INSERT INTO d2 SELECT i, i FROM generate_series(1,300000) s(i);<br>
<br>
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:<br> <br>
SELECT * FROM f JOIN d1 ON (f.id1 = d1.id1 AND f.id2 = d1.id2)<br>
JOIN d2 ON (f.id1 = d2.id1 AND f.id2 = d2.id2);<br>
<br>
QUERY PLAN<br>
-------------------------------------------------------------------------<br>
Nested Loop (cost=3334.43..12647.57 rows=30000 width=24)<br>
(actual time=221.086..1767.206 rows=100000 loops=1)<br>
Join Filter: ((d1.id1 = f.id1) AND (d1.id2 = f.id2))<br>
-> Hash Join (cost=3334.00..12647.01 rows=1 width=16)<br>
(actual time=221.058..939.482 rows=100000 loops=1)<br>
Hash Cond: ((d2.id1 = d1.id1) AND (d2.id2 = d1.id2))<br>
-> Seq Scan on d2 (cost=0.00..4328.00 rows=300000 width=8)<br>
(actual time=0.038..263.356 rows=300000 loops=1)<br>
-> Hash (cost=1443.00..1443.00 rows=100000 width=8)<br>
(actual time=220.721..220.721 rows=100000 loops=1)<br>
Buckets: 131072 Batches: 2 Memory Usage: 2982kB<br>
-> Seq Scan on d1 (cost=0.00..1443.00 rows=100000 \
...)<br>
(actual time=0.033..101.547 rows=100000 \
loops=1)<br>
-> Index Only Scan using f_pkey on f (cost=0.42..0.54 rows=1 ...)<br>
(actual time=0.004..0.004 rows=1 \
loops=100000)<br> Index Cond: ((id1 = d2.id1) AND (id2 = d2.id2))<br>
Heap Fetches: 100000<br>
<br>
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.<br> <br>
So it seems like s a clear improvement, both compared to master and the previous \
versions of the patch.</blockquote><div><br></div><div>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.</div><div><br></div><div>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</div><div><br></div><div><div>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);</div><div> \
QUERY PLAN</div><div>----------------------------------------------------------------- \
--------------------------------------------------------------------------------</div><div> \
Hash Join (cost=16655.94..26066.95 rows=30000 width=24) (actual \
time=267.322..468.383 rows=100000 loops=1)</div><div> Hash Cond: ((d2.id1 = \
f.id1) AND (d2.id2 = f.id2))</div><div> -> Seq Scan on d2 \
(cost=0.00..4328.00 rows=300000 width=8) (actual time=0.019..31.396 rows=300000 \
loops=1)</div><div> -> Hash (cost=14666.94..14666.94 rows=100000 width=16) \
(actual time=266.263..266.263 rows=100000 loops=1)</div><div> Buckets: \
131072 Batches: 2 Memory Usage: 3373kB</div><div> -> Merge Join \
(cost=9748.32..14666.94 rows=100000 width=16) (actual time=104.494..224.908 \
rows=100000 loops=1)</div><div> Merge Cond: ((f.id1 = d1.id1) \
AND (f.id2 = d1.id2))</div><div> -> 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)</div><div> Heap Fetches: \
100001</div><div> -> Sort (cost=9747.82..9997.82 \
rows=100000 width=8) (actual time=104.440..122.401 rows=100000 loops=1)</div><div> \
Sort Key: d1.id1, d1.id2</div><div> Sort Method: \
external sort Disk: 2152kB</div><div> -> Seq \
Scan on d1 (cost=0.00..1443.00 rows=100000 width=8) (actual time=0.019..9.443 \
rows=100000 loops=1)</div></div><div><br></div><div>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.</div><div><br></div><div>I've gone though a few variations on ways to \
handle this and I'm a bit stuck on what's the best \
way.</div><div><br></div><div>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.</div><div><br></div><div><span \
style="color:rgb(136,136,136);font-size:12.8px">--</span><br></div><div><div \
class="gmail_signature"><div dir="ltr"><span style="font-size:12.8px"><font \
color="#888888"> David Rowley <a \
href="http://www.2ndquadrant.com/" \
target="_blank">http://www.2ndQuadrant.com/</a><br></font></span><div \
style="font-size:12.8px"><div></div><div> PostgreSQL Development, 24x7 Support, \
Training & Services</div></div></div></div></div><div> </div></div></div></div>
["estimation-with-fkeys-v2_davidv4.patch" (application/octet-stream)]
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index c91273c..cc1cb78 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1909,6 +1909,16 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node)
}
static void
+_outForeignKeyOptInfo(StringInfo str, const ForeignKeyOptInfo *node)
+{
+ WRITE_NODE_TYPE("FOREIGNKEYOPTINFO");
+
+ WRITE_OID_FIELD(conrelid);
+ WRITE_OID_FIELD(confrelid);
+ WRITE_INT_FIELD(nkeys);
+}
+
+static void
_outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
{
/*
@@ -3299,6 +3309,9 @@ _outNode(StringInfo str, const void *obj)
case T_IndexOptInfo:
_outIndexOptInfo(str, obj);
break;
+ case T_ForeignKeyOptInfo:
+ _outForeignKeyOptInfo(str, obj);
+ break;
case T_EquivalenceClass:
_outEquivalenceClass(str, obj);
break;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d107d76..50828f2 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,405 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
}
/*
+ * quals_match_foreign_key
+ * Determines if 'joinquals' contains quals which match up to the foreign
+ * key 'fkinfo'. If a complete match is made to the foreign key, then a
+ * bitmap is returned with bits set for each of the 'joinquals' 0 based
+ * list position of each match. If 'joinquals' only partially matches the
+ * foreign key, then NULL is returned.
+ */
+static Bitmapset *
+quals_match_foreign_key(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+ RelOptInfo *fkrel, RelOptInfo *foreignrel,
+ List *joinquals)
+{
+ int i;
+ int nkeys = fkinfo->nkeys;
+ Bitmapset *qualmatches = NULL;
+ Bitmapset *fkmatches = NULL;
+
+ /*
+ * Loop over each column of the foreign key and build a bitmap index
+ * of each joinqual which matches. Note that we don't stop when we find
+ * the first match, as the expression could be duplicated in the
+ * joinquals, and we want to generate a bitmap index which has bits set for
+ * every matching join qual.
+ */
+ for (i = 0; i < nkeys; i++)
+ {
+ ListCell *lc;
+ int quallstidx = -1;
+
+ foreach(lc, joinquals)
+ {
+ RestrictInfo *rinfo;
+ OpExpr *clause;
+ Var *leftvar;
+ Var *rightvar;
+
+ quallstidx++;
+
+ /*
+ * Technically we don't need to, but here we skip this qual if
+ * we've matched it to part of the foreign key already. This
+ * should prove to be a useful optimization when the quals appear
+ * in the same order as the foreign key's keys. We need only bother
+ * doing this when the foreign key is made up of more than 1 set
+ * of columns, and we're not testing the first column.
+ */
+ if (i > 0 && bms_is_member(quallstidx, qualmatches))
+ continue;
+
+ /*
+ * Here since 'usefulquals' only contains bitmap indexes for quals
+ * of type "var op var" we can safely skip checking this.
+ */
+ rinfo = (RestrictInfo *) lfirst(lc);
+ clause = (OpExpr *) rinfo->clause;
+
+ /*
+ * If the operator does not match then there's little point in
+ * checking the operands
+ */
+ if (clause->opno != fkinfo->conpfeqop[i])
+ continue;
+
+ leftvar = (Var *) get_leftop((Expr *) clause);
+ rightvar = (Var *) get_rightop((Expr *) clause);
+
+ /* Foreign keys only support Vars, so ignore anything more complex */
+ if (!IsA(leftvar, Var) || !IsA(rightvar, Var))
+ continue;
+
+ /*
+ * For RestrictInfos built from an eclass we must consider each
+ * member of the eclass as rinfo's operands may not belong to the
+ * foreign key. For efficient tracking of which Vars we've found,
+ * since we're only tracking 2 Vars, we use a bitmask. We can
+ * safely finish searching when both of the least significant bits
+ * are set.
+ */
+ if (rinfo->parent_ec)
+ {
+ EquivalenceClass *ec = rinfo->parent_ec;
+ ListCell *lc2;
+ int foundvarmask = 0;
+
+ foreach(lc2, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+ Var *var = (Var *) em->em_expr;
+
+ if (!IsA(var, Var))
+ continue;
+
+ if (foreignrel->relid == var->varno &&
+ fkinfo->confkeys[i] == var->varattno)
+ foundvarmask |= 1;
+
+ else if (fkrel->relid == var->varno &&
+ fkinfo->conkeys[i] == var->varattno)
+ foundvarmask |= 2;
+
+ /*
+ * Check if we've found both matches. If found we add
+ * this qual to the matched list and mark this key as
+ * matched too.
+ */
+ if (foundvarmask == 3)
+ {
+ qualmatches = bms_add_member(qualmatches, quallstidx);
+ fkmatches = bms_add_member(fkmatches, i);
+ break;
+ }
+ }
+ }
+ else
+ {
+ /*
+ * In this non eclass RestrictInfo case we'll check if the left
+ * and right Vars match to this part of the foreign key.
+ * Remember that this could be written with the Vars in either
+ * order, so we test both permutations of the expression.
+ */
+ if (foreignrel->relid == leftvar->varno &&
+ fkrel->relid == rightvar->varno &&
+ fkinfo->confkeys[i] == leftvar->varattno &&
+ fkinfo->conkeys[i] == rightvar->varattno)
+ {
+ qualmatches = bms_add_member(qualmatches, quallstidx);
+ fkmatches = bms_add_member(fkmatches, i);
+ }
+ else if (foreignrel->relid == rightvar->varno &&
+ fkrel->relid == leftvar->varno &&
+ fkinfo->confkeys[i] == rightvar->varattno &&
+ fkinfo->conkeys[i] == leftvar->varattno)
+ {
+ qualmatches = bms_add_member(qualmatches, quallstidx);
+ fkmatches = bms_add_member(fkmatches, i);
+ }
+ }
+ }
+ }
+
+ /*
+ * We only return the matches if we found a match for every column in
+ * the foreign key.
+ */
+ if (bms_num_members(fkmatches) == nkeys)
+ {
+ bms_free(fkmatches);
+ return qualmatches;
+ }
+
+ bms_free(fkmatches);
+ return NULL;
+}
+
+/*
+ * find_best_foreign_key_quals
+ * Analyzes joinquals to determine if any quals match foreign keys defined
+ * on 'fkrel' which reference 'foreignrel'. We return the number of keys
+ * of the best matching foreign key. We assume the best matching foreign
+ * key is the one with the most keys, not the most quals matching quals,
+ * as quals could be duplicated. We also set 'joinqualsbitmap' bits to
+ * mark which quals in 'joinquals' were matched. Zero is returned if no
+ * match is found. In this case the value of 'joinqualsbitmap' will be set
+ * to NULL. Partial foreign key matches are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+ RelOptInfo *foreignrel, List *joinquals,
+ Bitmapset **joinqualsbitmap)
+{
+ Bitmapset *qualbestmatch;
+ ListCell *lc;
+ int bestmatchnkeys;
+
+ /* fast path out when there's no foreign keys on fkrel */
+ if (fkrel->fkeylist == NIL)
+ {
+ *joinqualsbitmap = NULL;
+ return 0;
+ }
+
+ qualbestmatch = NULL;
+ bestmatchnkeys = 0;
+
+ /* now check the matches for each foreign key defined on the fkrel */
+ foreach(lc, fkrel->fkeylist)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ Bitmapset *qualsmatched;
+
+ /*
+ * We make no attempt in checking that this foreign key actually
+ * references 'foreignrel', the reasoning here is that we may be able
+ * to match the foreign key to an eclass member Var of a RestrictInfo
+ * that's in qualslist, this Var may belong to some other relation.
+ */
+ qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel, foreignrel,
+ joinquals);
+
+ /* Did we get a match? And is that match better than a previous one? */
+ if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+ {
+ /* save the new best match */
+ bms_free(qualbestmatch);
+ qualbestmatch = qualsmatched;
+ bestmatchnkeys = fkinfo->nkeys;
+ }
+ }
+
+ /*
+ * If no match was found, then make one last ditch attempt to find a match
+ * by looking at foreign keys for other rels that we may exist in one of
+ * the eclasses which the joinquals were built from.
+ *
+ * XXX Perhaps we should actually be looking for a better match using this
+ * method, even if the code above already found a match.
+ */
+ if (bestmatchnkeys == 0)
+ {
+ int fkrelid;
+ Bitmapset *otherfkrels = NULL;
+
+ /*
+ * First build a list of all rels seen in eclasses that joinquals were
+ * build from.
+ */
+ foreach(lc, joinquals)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ if (rinfo->parent_ec)
+ otherfkrels = bms_add_members(otherfkrels, rinfo->parent_ec->ec_relids);
+ }
+
+ /*
+ * Remove both 'fkrel' and 'foreignrel' from the bitmap so that we're
+ * left with only the extra rels that were seen.
+ */
+ otherfkrels = bms_del_member(otherfkrels, fkrel->relid);
+ otherfkrels = bms_del_member(otherfkrels, foreignrel->relid);
+
+ if (bms_is_empty(otherfkrels))
+ return 0;
+
+ fkrelid = -1;
+ while ((fkrelid = bms_next_member(otherfkrels, fkrelid)) >= 0)
+ {
+ fkrel = find_base_rel(root, fkrelid);
+
+ /* The eclass may have some dead rels. We'll skip these. */
+ if (fkrel->reloptkind != RELOPT_BASEREL)
+ continue;
+
+ foreach(lc, fkrel->fkeylist)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ Bitmapset *qualsmatched;
+
+ /*
+ * We make no attempt in checking that this foreign key
+ * actually references 'foreignrel', the reasoning here is
+ * that we may be able to match the foreign key to an eclass
+ * member Var of a RestrictInfo that's in qualslist, this Var
+ * may belong to some other relation.
+ */
+ qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel,
+ foreignrel, joinquals);
+
+ /* does this match match more keys than any previous match? */
+ if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+ {
+ bms_free(qualbestmatch);
+ qualbestmatch = qualsmatched;
+ bestmatchnkeys = fkinfo->nkeys;
+ }
+ }
+ }
+ }
+
+ *joinqualsbitmap = qualbestmatch;
+ return bestmatchnkeys;
+}
+
+/*
+ * clauselist_join_selectivity
+ * Estimate selectivity of join clauses either by using foreign key info
+ * or by using the regular clauselist_selectivity().
+ *
+ * Since selectivity estimates for each joinqual are multiplied together, this
+ * can cause significant underestimates on the number of join tuples in cases
+ * where there's more than 1 clause in the join condition. To help ease the
+ * pain here we make use of foreign keys, and we assume that 1 row will match
+ * when *all* of the foreign key columns are present in the join condition, any
+ * additional clauses are estimated using clauselist_selectivity().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+ JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+ int outerid;
+ int innerid;
+ Selectivity sel = 1.0;
+ Bitmapset *foundfkquals = NULL;
+
+ innerid = -1;
+ while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+ {
+ RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+ outerid = -1;
+ while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+ {
+ RelOptInfo *outerrel = find_base_rel(root, outerid);
+ Bitmapset *outer2inner;
+ Bitmapset *inner2outer;
+ int innermatches;
+ int outermatches;
+
+ /*
+ * check which quals are matched by a foreign key referencing the
+ * innerrel.
+ */
+ outermatches = find_best_foreign_key_quals(root, outerrel,
+ innerrel, joinquals, &outer2inner);
+
+ /* do the same, but with relations swapped */
+ innermatches = find_best_foreign_key_quals(root, innerrel,
+ outerrel, joinquals, &inner2outer);
+
+ /*
+ * did we find any matches at all? If so we need to see which one is
+ * the best/longest match
+ */
+ if (outermatches != 0 || innermatches != 0)
+ {
+ double referenced_tuples;
+ bool overlap;
+
+ /* either could be zero, but not both. */
+ if (outermatches < innermatches)
+ {
+ overlap = bms_overlap(foundfkquals, inner2outer);
+
+ foundfkquals = bms_add_members(foundfkquals, inner2outer);
+ referenced_tuples = Max(outerrel->tuples, 1.0);
+ }
+ else
+ {
+ overlap = bms_overlap(foundfkquals, outer2inner);
+
+ foundfkquals = bms_add_members(foundfkquals, outer2inner);
+ referenced_tuples = Max(innerrel->tuples, 1.0);
+ }
+
+ /*
+ * XXX should we ignore these overlapping matches?
+ * Or perhaps take the Max() or Min()?
+ */
+ if (overlap)
+ {
+ if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+ sel = Min(sel,Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0));
+ else
+ sel = Min(sel, 1.0 / referenced_tuples);
+ }
+ else
+ {
+ if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+ sel *= Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0);
+ else
+ sel *= 1.0 / referenced_tuples;
+ }
+ }
+ }
+ }
+
+ /*
+ * If any non matched quals exist then we build a list of the non-matches
+ * and use clauselist_selectivity() to estimate the selectivity of these.
+ */
+ if (bms_num_members(foundfkquals) < list_length(joinquals))
+ {
+ ListCell *lc;
+ int lstidx = 0;
+ List *nonfkeyclauses = NIL;
+
+ foreach (lc, joinquals)
+ {
+ if (!bms_is_member(lstidx, foundfkquals))
+ nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+ lstidx++;
+ }
+ sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+ }
+
+ return sel;
+}
+
+/*
* calc_joinrel_size_estimate
* Workhorse for set_joinrel_size_estimates and
* get_parameterized_joinrel_size.
@@ -3777,11 +4176,11 @@ calc_joinrel_size_estimate(PlannerInfo *root,
}
/* Get the separate selectivities */
- jselec = clauselist_selectivity(root,
- joinquals,
- 0,
- jointype,
- sjinfo);
+ jselec = clauselist_join_selectivity(root,
+ joinquals,
+ jointype,
+ sjinfo);
+
pselec = clauselist_selectivity(root,
pushedquals,
0,
@@ -3794,11 +4193,10 @@ calc_joinrel_size_estimate(PlannerInfo *root,
}
else
{
- jselec = clauselist_selectivity(root,
- restrictlist,
- 0,
- jointype,
- sjinfo);
+ jselec = clauselist_join_selectivity(root,
+ restrictlist,
+ jointype,
+ sjinfo);
pselec = 0.0; /* not used, keep compiler quiet */
}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
#include "catalog/catalog.h"
#include "catalog/dependency.h"
#include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
@@ -40,6 +41,7 @@
#include "rewrite/rewriteManip.h"
#include "storage/bufmgr.h"
#include "utils/lsyscache.h"
+#include "utils/syscache.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
@@ -93,6 +95,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
Relation relation;
bool hasindex;
List *indexinfos = NIL;
+ List *fkinfos = NIL;
+ List *fkoidlist;
+ ListCell *l;
/*
* We need not lock the relation since it was already locked, either by
@@ -140,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
if (hasindex)
{
List *indexoidlist;
- ListCell *l;
LOCKMODE lmode;
indexoidlist = RelationGetIndexList(relation);
@@ -380,6 +384,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
}
rel->indexlist = indexinfos;
+
+ /* load foreign keys */
+ fkoidlist = RelationGetFKeyList(relation);
+
+ foreach(l, fkoidlist)
+ {
+ int i;
+ ArrayType *arr;
+ Datum adatum;
+ bool isnull;
+ int numkeys;
+ Oid fkoid = lfirst_oid(l);
+
+ HeapTuple htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+ Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+ ForeignKeyOptInfo *info;
+
+ Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+ info = makeNode(ForeignKeyOptInfo);
+
+ info->conrelid = constraint->conrelid;
+ info->confrelid = constraint->confrelid;
+
+ /* conkey */
+ adatum = SysCacheGetAttr(CONSTROID, htup,
+ Anum_pg_constraint_conkey, &isnull);
+ Assert(!isnull);
+
+ arr = DatumGetArrayTypeP(adatum);
+ numkeys = ARR_DIMS(arr)[0];
+ info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+ for (i = 0; i < numkeys; i++)
+ info->conkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+
+ /* confkey */
+ adatum = SysCacheGetAttr(CONSTROID, htup,
+ Anum_pg_constraint_confkey, &isnull);
+ Assert(!isnull);
+
+ arr = DatumGetArrayTypeP(adatum);
+ numkeys = ARR_DIMS(arr)[0];
+ info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+ for (i = 0; i < numkeys; i++)
+ info->confkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+
+ /* conpfeqop */
+ adatum = SysCacheGetAttr(CONSTROID, htup,
+ Anum_pg_constraint_conpfeqop, &isnull);
+ Assert(!isnull);
+
+ arr = DatumGetArrayTypeP(adatum);
+ numkeys = ARR_DIMS(arr)[0];
+ info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+ for (i = 0; i < numkeys; i++)
+ info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+ info->nkeys = numkeys;
+
+ ReleaseSysCache(htup);
+
+ fkinfos = lcons(info, fkinfos);
+ }
+
+ list_free(fkoidlist);
+
+ rel->fkeylist = fkinfos;
/* Grab foreign-table info using the relcache, while we have it */
if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9c3d096..3ae9022 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3923,6 +3923,73 @@ RelationGetIndexList(Relation relation)
}
/*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+List *
+RelationGetFKeyList(Relation relation)
+{
+ Relation conrel;
+ SysScanDesc conscan;
+ ScanKeyData skey;
+ HeapTuple htup;
+ List *result;
+ List *oldlist;
+ MemoryContext oldcxt;
+
+ /* Quick exit if we already computed the list. */
+ if (relation->rd_fkeyvalid)
+ return list_copy(relation->rd_fkeylist);
+
+ /*
+ * We build the list we intend to return (in the caller's context) while
+ * doing the scan. After successfully completing the scan, we copy that
+ * list into the relcache entry. This avoids cache-context memory leakage
+ * if we get some sort of error partway through.
+ */
+ result = NIL;
+
+ /* Prepare to scan pg_constraint for entries having conrelid = this rel. */
+ ScanKeyInit(&skey,
+ Anum_pg_constraint_conrelid,
+ BTEqualStrategyNumber, F_OIDEQ,
+ ObjectIdGetDatum(RelationGetRelid(relation)));
+
+ conrel = heap_open(ConstraintRelationId, AccessShareLock);
+ conscan = systable_beginscan(conrel, ConstraintRelidIndexId, true,
+ NULL, 1, &skey);
+
+ while (HeapTupleIsValid(htup = systable_getnext(conscan)))
+ {
+ Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+ /* return only foreign keys */
+ if (constraint->contype != CONSTRAINT_FOREIGN)
+ continue;
+
+ /* Add index's OID to result list in the proper order */
+ result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+ }
+
+ systable_endscan(conscan);
+
+ heap_close(conrel, AccessShareLock);
+
+ /* Now save a copy of the completed list in the relcache entry. */
+ oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
+ oldlist = relation->rd_fkeylist;
+ relation->rd_fkeylist = list_copy(result);
+ relation->rd_fkeyvalid = true;
+ MemoryContextSwitchTo(oldcxt);
+
+ /* Don't leak the old list, if there is one */
+ list_free(oldlist);
+
+ return result;
+}
+
+/*
* insert_ordered_oid
* Insert a new Oid into a sorted list of Oids, preserving ordering
*
@@ -4891,6 +4958,8 @@ load_relcache_init_file(bool shared)
rel->rd_indexattr = NULL;
rel->rd_keyattr = NULL;
rel->rd_idattr = NULL;
+ rel->rd_fkeylist = NIL;
+ rel->rd_fkeyvalid = false;
rel->rd_createSubid = InvalidSubTransactionId;
rel->rd_newRelfilenodeSubid = InvalidSubTransactionId;
rel->rd_amcache = NULL;
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 274480e..5c40b83 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
T_PlannerGlobal,
T_RelOptInfo,
T_IndexOptInfo,
+ T_ForeignKeyOptInfo,
T_ParamPathInfo,
T_Path,
T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 79bed33..8ce35e7 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -472,6 +472,7 @@ typedef struct RelOptInfo
Relids lateral_relids; /* minimum parameterization of rel */
Relids lateral_referencers; /* rels that reference me laterally */
List *indexlist; /* list of IndexOptInfo */
+ List *fkeylist; /* list of ForeignKeyOptInfo */
BlockNumber pages; /* size estimates derived from pg_class */
double tuples;
double allvisfrac;
@@ -566,6 +567,20 @@ typedef struct IndexOptInfo
bool amhasgetbitmap; /* does AM have amgetbitmap interface? */
} IndexOptInfo;
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+ NodeTag type;
+
+ Oid conrelid;
+ Oid confrelid;
+
+ int nkeys;
+ int *conkeys;
+ int *confkeys;
+ Oid *conpfeqop;
+
+} ForeignKeyOptInfo;
/*
* EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,8 @@ extern Expr *adjust_rowcompare_for_index(RowCompareExpr *clause,
int indexcol,
List **indexcolnos,
bool *var_on_left_p);
+extern bool has_matching_fkey(RelOptInfo *rel, RelOptInfo *frel, List *clauses,
+ bool reverse);
/*
* tidpath.h
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
bool rd_isvalid; /* relcache entry is valid */
char rd_indexvalid; /* state of rd_indexlist: 0 = not valid, 1 =
* valid, 2 = temporarily forced */
+ bool rd_fkeyvalid; /* state of rd_fkeylist: 0 = not valid, 1 = valid */
/*
* rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,9 @@ typedef struct RelationData
Oid rd_oidindex; /* OID of unique index on OID, if any */
Oid rd_replidindex; /* OID of replica identity index, if any */
+ /* data managed by RelationGetFKList: */
+ List *rd_fkeylist; /* OIDs of foreign keys */
+
/* data managed by RelationGetIndexAttrBitmap: */
Bitmapset *rd_indexattr; /* identifies columns used in indexes */
Bitmapset *rd_keyattr; /* cols that can be ref'd by foreign keys */
diff --git a/src/include/utils/relcache.h b/src/include/utils/relcache.h
index 6953281..8878478 100644
--- a/src/include/utils/relcache.h
+++ b/src/include/utils/relcache.h
@@ -38,6 +38,7 @@ extern void RelationClose(Relation relation);
* Routines to compute/retrieve additional cached information
*/
extern List *RelationGetIndexList(Relation relation);
+extern List *RelationGetFKeyList(Relation relation);
extern Oid RelationGetOidIndex(Relation relation);
extern Oid RelationGetReplicaIndex(Relation relation);
extern List *RelationGetIndexExpressions(Relation relation);
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic