Обсуждение: Optimizer cleanup to avoid redundant work on joins
(This is mostly directed at Bruce, but anyone else who's looked at the
planner/optimizer is welcome to chime in.)
On the way to implementing estimates of WHERE-clause costs, I was
forced to notice that the estimated sizes of join relations are set
*after* all the planning work is done for a rel, instead of before,
which makes it hard to use the info for cost estimation :-(.
In looking at whether the sizes couldn't be set earlier, I saw that
trying to set them early enough to be used in planning would result in
duplicate effort; in fact there is a lot of duplicated effort already.
This is a proposal to rearrange the optimizer to clean that up.
Right now, the sequence of events in constructing a join tree is that
at each join level, make_one_rel_by_joins invokes make_rels_by_joins
to prepare a list of the joins to be considered at this level (where
a "join" means a particular outer rel and inner rel, and each "rel"
might consist of several already-joined base relations). Each join
is represented by a RelOptInfo node constructed by make_join_rel (see
joinrels.c for these routines). Then update_rels_pathlist_for_joins is
called to determine, for each of these joins, the best implementation or
"path". Finally, since different "joins" in this sense may represent
the same set of joined base relations, merge_rels_with_same_relids is
called to match equivalent joinrels together and keep just the best path
for each equivalence class of joinrels.
My beef with this is that we should never be generating distinct
RelOptInfos in the first place for different ways of producing the
same join relation. make_join_rel spends a fair amount of time and
memory space to produce the RelOptInfo and its substructure, and
for an N-component joinrel this price will be paid (at least) N times
over, after which we throw away all but one of the copies. Even more
critically, once one joinrel has been completed for a particular set
of base rels, the implementation paths for other equivalent joinrels
will be considered in a vacuum --- we may have already discovered a
path that will dominate many of the paths for other ways of building
the same join relation, but because that path isn't available to
add_pathlist when we are looking at another joinrel, we will have to
keep paths that could have been discarded instantly.
It seems to me that join RelOptInfos should be managed in the same way
as base-relation RelOptInfos: there ought never be more than one of them
for a given set of Relids. When we are considering a new pair of outer
and inner rels that can produce an already-considered join relation,
we should find the existing RelOptInfo for that join relation. Then
add_pathlist will keep proposed paths only if they survive comparison
against paths already found from the earlier ways of generating the same
join relation.
This looks like it should be a fairly straightforward change: we should
meld make_join_rel and get_join_rel so that a requested join rel is
first searched for in root->join_rel_list, and only built if not present
(like get_base_rel). The join rel would have a flat relids list from the
beginning, since it would be agnostic about which inner and outer subset
rels should be used to produce it. Then update_rels_pathlist_for_joins
would be called *immediately* to process just that one join rel, passing
the outer and inner subset relid lists as separate parameters. It would
generate paths using this pair of outer and inner rels, and would add
them to the join rel's path list only if they survive comparison against
all the already-found paths for that join rel. On return from
make_rels_by_joins, all the work is done, so make_one_rel_by_joins
doesn't need to invoke either update_rels_pathlist_for_joins or
merge_rels_with_same_relids (the latter routine disappears entirely).
We have but to invoke rels_set_cheapest and then advance to the next
level of joining.
With this change, I could add more processing to make_join_rel to set
the estimated output rel size, without fear that it would be repeated
uselessly.
Anyone see a problem with this, or have a better idea about how to do
it?
regards, tom lane
> This looks like it should be a fairly straightforward change: we should > meld make_join_rel and get_join_rel so that a requested join rel is > first searched for in root->join_rel_list, and only built if not present > (like get_base_rel). The join rel would have a flat relids list from the > beginning, since it would be agnostic about which inner and outer subset > rels should be used to produce it. Then update_rels_pathlist_for_joins > would be called *immediately* to process just that one join rel, passing > the outer and inner subset relid lists as separate parameters. It would > generate paths using this pair of outer and inner rels, and would add > them to the join rel's path list only if they survive comparison against > all the already-found paths for that join rel. On return from > make_rels_by_joins, all the work is done, so make_one_rel_by_joins > doesn't need to invoke either update_rels_pathlist_for_joins or > merge_rels_with_same_relids (the latter routine disappears entirely). > We have but to invoke rels_set_cheapest and then advance to the next > level of joining. > > With this change, I could add more processing to make_join_rel to set > the estimated output rel size, without fear that it would be repeated > uselessly. > > Anyone see a problem with this, or have a better idea about how to do > it? Sounds good. The only question is how easy it will be to see if there already is a RelOptInfo for that combination. My guess is that the current code is brain-dead like the many fixes we made long ago. It was carrying around too many versions, instead of keeping the cheapest. Seems you have found another place that should be doing this. -- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
>> This looks like it should be a fairly straightforward change: we should
>> meld make_join_rel and get_join_rel so that a requested join rel is
>> first searched for in root->join_rel_list, and only built if not present
>> (like get_base_rel). The join rel would have a flat relids list from the
>> beginning, since it would be agnostic about which inner and outer subset
>> rels should be used to produce it.
Well, drat. This idea looked good, and I still think it's good, but
implementation turns out to be trickier than I thought. I was thinking
that RelOptInfos for join rels were essentially independent of which
pair of sub-relations were used to produce them --- eg, {1 2 3} doesn't
care if you made it from {1 2} joined to 3 or {1 3} joined to 2, etc.
That's almost true ... but it falls down on the restrictinfo list,
because which qual clauses are restrictions at a particular join level
*does* depend on the path you took to build it. For example, if you
have a qual clause "t1.v1 = t2.v2", this clause will be a restrict
clause for {1 2 3} if you make it from {1 3} joined to 2, but if you
make it from {1 2} joined to 3 then the clause was already handled when
{1 2} was produced.
We could still unify the RelOptInfos for different ways of making the
same joinrel if we stored restrictinfo lists for joins in individual
join paths, rather than in the RelOptInfo. I think that might be worth
doing, but the change is looking larger and subtler than I thought.
Probably best not to try to squeeze it in right before beta.
I will set aside the code I already rewrote for this purpose, and come
back to it after we start 7.1.
regards, tom lane
> I will set aside the code I already rewrote for this purpose, and come
> back to it after we start 7.1.
Wait a minute ... stop the presses ...
I just realized that the bug I was complaining of is *already there
in current sources*, and has been for a while (certainly since 6.5).
Look at prune.c's code that merges together RelOptInfos after-the-
fact:
if (same(rel->relids, unmerged_rel->relids)) { /* * These rels are for the same set
ofbase relations, * so get the best of their pathlists. We assume it's * ok to reassign a path
tothe other RelOptInfo without * doing more than changing its parent pointer (cf. pathnode.c). */
rel->pathlist = add_pathlist(rel, rel->pathlist,
unmerged_rel->pathlist); }
This is wrong, wrong, wrong, because the paths coming from different
RelOptInfos (different pairs of sub-relations) may need different sets
of qual clauses applied as restriction clauses. There's no way to
represent that in the single RelOptInfo that will be left over. The
worst case is that the generated plan is missing a needed restriction
clause (the other possibility is that the clause is evaluated
redundantly, which is much less painful).
I am not sure why we haven't heard bug reports about this. It seems
like it wouldn't be hard at all to provoke the failure (I'm going to
try to make a test case right now). Assuming I can do that, I think
we have no choice but to move join restrictlists into JoinPath nodes.
regards, tom lane
> We could still unify the RelOptInfos for different ways of making the > same joinrel if we stored restrictinfo lists for joins in individual > join paths, rather than in the RelOptInfo. I think that might be worth > doing, but the change is looking larger and subtler than I thought. > Probably best not to try to squeeze it in right before beta. > > I will set aside the code I already rewrote for this purpose, and come > back to it after we start 7.1. What happened to the time-honored tradition of jamming partially-tested features in before the beta feature freeze. Are we getting too conservative in our old age? :-) -- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
> Well, drat. This idea looked good, and I still think it's good, but
> implementation turns out to be trickier than I thought. I was thinking
> that RelOptInfos for join rels were essentially independent of which
> pair of sub-relations were used to produce them --- eg, {1 2 3} doesn't
> care if you made it from {1 2} joined to 3 or {1 3} joined to 2, etc.
> That's almost true ... but it falls down on the restrictinfo list,
> because which qual clauses are restrictions at a particular join level
> *does* depend on the path you took to build it. For example, if you
> have a qual clause "t1.v1 = t2.v2", this clause will be a restrict
> clause for {1 2 3} if you make it from {1 3} joined to 2, but if you
> make it from {1 2} joined to 3 then the clause was already handled when
> {1 2} was produced.
I thought "t1.v1 = t2.v2" would be in t1 RelOptInfo and t2 RelOptInfo.
Of course, this is a join info restriction, not a restrict info
restriction.
> We could still unify the RelOptInfos for different ways of making the
> same joinrel if we stored restrictinfo lists for joins in individual
> join paths, rather than in the RelOptInfo. I think that might be worth
> doing, but the change is looking larger and subtler than I thought.
> Probably best not to try to squeeze it in right before beta.
Aren't the restrict-info/join-info of the Final RelOptInfo set only when
the cheapest is found, and before that, the individual Reloptinfo's
restrict-info/join-info that are part of the Path are used? Maybe these
are stupid questions.
-- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610)
853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill,
Pennsylvania19026
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> I thought "t1.v1 = t2.v2" would be in t1 RelOptInfo and t2 RelOptInfo.
> Of course, this is a join info restriction, not a restrict info
> restriction.
Right, it would appear in t1's joininfo list (showing t2 as unjoined_relids)
and in t2's joininfo list (showing t1 as unjoined_relids). Then when
we make a join rel from t1 + t2, the clause would be put into that rel's
restrictinfo list, since it's no longer a joining clause for the
joinrel; but it does need to be implemented at the time of the join.
(The bug is probably only visible for auxiliary quals that are not
being used as the driving clause of the join method; they need to show
up in the qpquals of the final plan, or they won't get enforced.)
The trouble comes when there are more rels in the picture. If we make
a joinrel from t1 + t3, this clause will still appear in that joinrel's
joininfo list, since it's still a joinclause for that rel. Then when
we make t1+t2+t3 from {t1 t3} and {t2}, the clause propagates up to
become a restrict clause of that rel, and that's where the buck stops
(and where the clause gets enforced at runtime).
*BUT*, if we make {t1 t2 t3} from {t1 t2} and {t3}, it will *not* show
this clause as a restrictclause, because in that path it gets handled at
the {t1 t2} join. So a joinpath for {t1 t3} against {t2}, which needs
this clause to appear as a restrictclause, loses if it is copied into a
{t1 t2 t3} RelOptInfo that was made from the other pair of
sub-relations.
I find that I can exhibit the bug very easily in current sources:
create table t1 (k1 int, d1 int);
create table t2 (k2 int, d2 int);
create table t3 (k3 int, d3 int);
create table t4 (k4 int, d4 int);
insert into t1 values (1, 1);
insert into t1 values (2, 2);
insert into t1 values (3, 3);
insert into t2 values (1, 11);
insert into t2 values (2, 22);
insert into t2 values (3, 33);
insert into t3 values (1, 111);
insert into t3 values (2, 222);
insert into t3 values (3, 333);
insert into t4 values (1, 1111);
insert into t4 values (2, 2222);
insert into t4 values (3, 3333);
select * from t1,t2,t3,t4 where k1 = k2 and k1 = k3 and k2=k4
and d1<d2 and d1<d3 and d1<d4 and d2<d3 and d2<d4 and d3>d4;
k1 | d1 | k2 | d2 | k3 | d3 | k4 | d4
----+----+----+----+----+-----+----+------ 1 | 1 | 1 | 11 | 1 | 111 | 1 | 1111 2 | 2 | 2 | 22 | 2 | 222 | 2 |
22223 | 3 | 3 | 33 | 3 | 333 | 3 | 3333
(3 rows)
which is obviously not meeting the restriction d3>d4. So we have
a problem.
I haven't been able to make 6.5.3 fail similarly, but I do not
understand why not --- it certainly looks like it *ought* to fail given
the right combination of circumstances. I think it may be escaping a
failure by sheer luck having to do with the order that RelOptInfos get
inserted into the query's join_rel_list. Our changes since 6.5 may have
exposed a problem that was only latent before. (Or maybe I just haven't
hit the right combination to trip up 6.5.3 ... but it does seem that
current sources fail more easily.)
Anyway, in the current sources things are certainly broken, and I don't
see any real alternative except to press forward with moving join
restrictinfos into JoinPaths. Even if we figure out exactly why 6.5.*
is somehow failing to fail, I am pretty certain that it must be a
non-robust coincidence rather than a solution that we want to keep using.
regards, tom lane
> Bruce Momjian <pgman@candle.pha.pa.us> writes: > > I thought "t1.v1 = t2.v2" would be in t1 RelOptInfo and t2 RelOptInfo. > > Of course, this is a join info restriction, not a restrict info > > restriction. > > Right, it would appear in t1's joininfo list (showing t2 as unjoined_relids) > and in t2's joininfo list (showing t1 as unjoined_relids). Then when > we make a join rel from t1 + t2, the clause would be put into that rel's > restrictinfo list, since it's no longer a joining clause for the > joinrel; but it does need to be implemented at the time of the join. > (The bug is probably only visible for auxiliary quals that are not > being used as the driving clause of the join method; they need to show > up in the qpquals of the final plan, or they won't get enforced.) I understand. Is it only non-equi-joins that show this, where the join is actually also a restriction in a sense. -- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
> Anyway, in the current sources things are certainly broken, and I don't
> see any real alternative except to press forward with moving join
> restrictinfos into JoinPaths. Even if we figure out exactly why 6.5.*
> is somehow failing to fail,
Er ... um ... ahem ... DUH! The reason 6.5.3 works is that it does in
fact keep join restrictinfo pointers in JoinPaths. I had eliminated
those pointers (the thoroughly undocumented "pathinfo" field) because
I thought that the lists were always the same as the parent relations'
restrictinfo lists. Which they were --- at the time of creation of a
JoinPath. What I missed was that prune.c moved a joinpath to belong
to a different RelOptInfo with (potentially) a different restrictinfo
list, but the joinpath needs to keep its original restrictinfo list.
In other words, I broke it.
Since surgery needs to be done anyway, I'm inclined to press ahead
with the changes I was going to put off. On the other hand, if the
patient had a vote, it might ask for a second opinion ;-)
regards, tom lane
> Er ... um ... ahem ... DUH! The reason 6.5.3 works is that it does in > fact keep join restrictinfo pointers in JoinPaths. I had eliminated > those pointers (the thoroughly undocumented "pathinfo" field) because > I thought that the lists were always the same as the parent relations' > restrictinfo lists. Which they were --- at the time of creation of a > JoinPath. What I missed was that prune.c moved a joinpath to belong > to a different RelOptInfo with (potentially) a different restrictinfo > list, but the joinpath needs to keep its original restrictinfo list. > > In other words, I broke it. > > Since surgery needs to be done anyway, I'm inclined to press ahead > with the changes I was going to put off. On the other hand, if the > patient had a vote, it might ask for a second opinion ;-) Go for it. Beta is for testing. No better time to break things than the present. This is the first time I remember hearing about pre-beta release jitters from many people. -- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> This is the first time I remember hearing about pre-beta release jitters
> from many people.
Maybe our standards have gotten higher than they used to be. I know
I really want 7.0 to be rock-solid, because I expect a lot of people
will be taking a new look at us when it comes out.
regards, tom lane
> Bruce Momjian <pgman@candle.pha.pa.us> writes: > > This is the first time I remember hearing about pre-beta release jitters > > from many people. > > Maybe our standards have gotten higher than they used to be. I know > I really want 7.0 to be rock-solid, because I expect a lot of people > will be taking a new look at us when it comes out. I had a terrible habit of trowing things in. I guess we are getting more professional. -- Bruce Momjian | http://www.op.net/~candle pgman@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026