On 11/6/21 11:03, Andy Fan wrote:
Hi Tomas:
This is the exact patch I want, thanks for the patch!
Good to hear.
On Thu, Oct 7, 2021 at 3:33 AM Tomas Vondra
<tomas.von...@enterprisedb.com> wrote:
3) estimation by join pairs
At the moment, the estimates are calculated for pairs of relations, so
for example given a query
explain analyze
select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b)
join t3 on (t1.b = t3.b and t2.c = t3.c);
we'll estimate the first join (t1,t2) just fine, but then the second
join actually combines (t1,t2,t3). What the patch currently does is it
splits it into (t1,t2) and (t2,t3) and estimates those.
Actually I can't understand how this works even for a simpler example.
let's say we query like this (ONLY use t2's column to join t3).
select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b)
join t3 on (t2.c = t3.c and t2.d = t3.d);
Then it works well on JoinRel(t1, t2) AND JoinRel(t2, t3). But when comes
to JoinRel(t1, t2, t3), we didn't maintain the MCV on join rel, so it
is hard to
work. Here I see your solution is splitting it into (t1, t2) AND (t2,
t3) and estimate
those. But how does this help to estimate the size of JoinRel(t1, t2, t3)?
Yeah, this is really confusing. The crucial thing to keep in mind is
this works with clauses before running setrefs.c, so the clauses
reference the original relations - *not* the join relation. Otherwise
even the regular estimation would not work, because where would it get
the per-column MCV lists etc.
Let's use a simple case with join clauses referencing just a single
attribute for each pair or relations. And let's talk about how many join
pairs it'll extract:
t1 JOIN t2 ON (t1.a = t2.a) JOIN t3 ON (t1.b = t3.b)
=> first we join t1/t2, which is 1 join pair (t1,t2)
=> then we join t1/t2/t3, but the join clause references just 2 rels, so
1 join pair (t1,t3)
Now a more complicated case, with more complex join clause
t1 JOIN t2 ON (t1.a = t2.a) JOIN t3 ON (t1.b = t3.b AND t2.c = t3.c)
=> first we join t1/t2, which is 1 join pair (t1,t2)
=> then we join t1/t2/t3, but this time the join clause references all
three rels, so we have two join pairs (t1,t3) and (t2,t3) and we can use
all the statistics.
I wonder if this
should actually combine all three MCVs at once - we're pretty much
combining the MCVs into one large MCV representing the join result.
I guess we can keep the MCVs on joinrel for these matches. Take the above
query I provided for example, and suppose the MCV data as below:
t1(a, b)
(1, 2) -> 0.1
(1, 3) -> 0.2
(2, 3) -> 0.5
(2, 8) -> 0.1
t2(a, b)
(1, 2) -> 0.2
(1, 3) -> 0.1
(2, 4) -> 0.2
(2, 10) -> 0.1
After t1.a = t2.a AND t1.b = t2.b, we can build the MCV as below
(1, 2, 1, 2) -> 0.1 * 0.2
(1, 3, 1, 3) -> 0.2 * 0.1
And recording the total mcv frequence as (0.1 + 0.2 + 0.5 + 0.1) *
(0.2 + 0.1 + 0.2 + 0.1)
Right, that's about the joint distribution I whole join.
With this design, the nitems of MCV on joinrel would be less than
either of baserel.
Actually, I think the number of items can grow, because the matches may
duplicate some items. For example in your example with (t1.a = t2.a) the
first first (1,2) item in t1 matches (1,2) and (1,3) in t2. And same for
(1,3) in t1. So that's 4 combinations. Of course, we could aggregate the
MCV by ignoring columns not used in the query.
and since we handle the eqjoin as well, we even can record the items as
(1, 2) -> 0.1 * 0.2
(1, 3) -> 0.2 * 0.1;
About when we should maintain the JoinRel's MCV data, rather than
maintain this just
after the JoinRel size is estimated, we can only estimate it when it
is needed. for example:
select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b)
join t3 on (t2.c = t3.c and t2.d = t3.d);
we don't need to maintain the MCV on (t1, t2, t3) since no others
need it at all. However
I don't check code too closely to see if it (Lazing computing MVC on
joinrel) is convenient
to do.
I'm not sure I understand what you're proposing here.
However, I think that estimating it for pairs has two advantages:
1) Combining MCVs for k relations requires k for loops. Processing 2
relations at a time limits the amount of CPU we need. Of course, this
assumes the joins are independent, which may or may not be true.
2) It seems fairly easy to combine different types of statistics
(regular, extended, ...), and also consider the part not represented by
MCV. It seems much harder when joining more than 2 relations.
I'm also worried about amplification of errors - I suspect attempting to
build the joint MCV for the whole join relation may produce significant
estimation errors.
Furthermore, I think joins with clauses referencing more than just two
relations are fairly uncommon. And we can always improve the feature in
this direction in the future.
But I haven't done that yet, as it requires the MCVs to be combined
using the join clauses (overlap in a way), but I'm not sure how likely
that is in practice. In the example it could help, but that's a bit
artificial example.
4) still just inner equi-joins
I haven't done any work on extending this to outer joins etc. Adding
outer and semi joins should not be complicated, mostly copying and
tweaking what eqjoinsel() does.
Overall, thanks for the feature and I am expecting there are more cases
to handle during discussion. To make the review process more efficient,
I suggest that we split the patch into smaller ones and review/commit them
separately if we have finalized the design roughly . For example:
Patch 1 -- required both sides to have extended statistics.
Patch 2 -- required one side to have extended statistics and the other side had
per-column MCV.
Patch 3 -- handle the case like WHERE t1.a = t2.a and t1.b = Const;
Patch 3 -- handle the case for 3+ table joins.
Patch 4 -- supports the outer join.
I think we can do this if we are sure that each individual patch would work in
some cases and would not make any other case worse. If you agree with this,
I can do that splitting work during my review process.
I'll consider splitting it like this, but I'm not sure it makes the main
patch that much smaller.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
