Re: Performance improvement for joins where outer side is unique

Sorry for the dealy, I've returned to this.

> > Performance:
> >
> > I looked on the performance gain this patch gives. For several
> > on-memory joins, I had gains about 3% for merge join, 5% for hash
> > join, and 10% for nestloop (@CentOS6), for simple 1-level joins
> > with aggregation similar to what you mentioned in previous
> > mail like this.
> >
> > =# SELECT count(*) FROM t1 JOIN t2 USING (id);
> >
> > Of course, the gain would be trivial when returning many tuples,
> > or scans go to disk.
> >
> >
> That's true, but joins where rows are filtered after the join condition
> will win here too:

Yes, when not many tuples was returned, the gain remains in
inverse proportion to the number of the returning rows. Heavy
(time-consuming) on-memory join returning several rows should
have gain from this.

> Also queries with a GROUP BY clause. (Since grouping is always performed
> after the join :-( )

And in many cases clinged by additional sorts:p As such, so many
factors affect the performance so improvements which give linear
performance gain are often difficult to gain approval to being
applied. I suppose we need more evidence how and in what
situation we will receive the gain.

> I haven't measured the loss by additional computation when the
> > query is regarded as not a "single join".
> >
> I think this would be hard to measure, but likely if it is measurable then
> you'd want to look at just planning time, rather than planning and
> execution time.

From the another point of view, the patch looks a bit large for
the gain (for me). Addition to it, it loops by many levels.

[mark_unique_joins()]
foreach (joinlist)
[eclassjoin_is_unique_join()]
foreach(joinlist)
foreach(root->eq_classes)
foreach(root->ec_members)

The innermost loop could be roughly said to iterate about 10^3*2
times for a join of 10 tables all of which have index and no
eclass is shared among them. From my expreince, we must have the
same effect by far less iteration levels.

This is caueed the query like this, as a bad case.

create table t1 (a int, b int);
create index i_t1 (a int);
create table t2 (like t1 including indexes);
....
create table t10 (.....);
insert into t1 (select a, a * 10 from generate_series(0, 100) a);
insert into t2 (select a * 10, a * 20 from generate_series(0, 100) a);
...
insert into t10 (select a * 90, a * 100 from generate_series(0, 100) a);

explain select t1.a, t10.b from t1 join t2 on (t1.b = t2.a) join t3 on (t2.b = t3.a) join t4 on (t3.b = t4.a) join t5 on (t4.b = t5.a) join t6 on (t5.b = t6.a) join t7 on (t6.b = t7.a) join t8 on (t7.b = t8.a) join t9 on (t8.b = t9.a) join t10 on (t9.b = t10.a);

The head takes 3ms for planning and the patched version takes
around 5ms while pure execution time is 1ms.. I think it is a too
long extra time.

> > Explain representation:
> >
> > I don't like that the 'Unique Join:" occupies their own lines in
> > the result of explain, moreover, it doesn't show the meaning
> > clearly. What about the representation like the following? Or,
> > It might not be necessary to appear there.
> >
> > Nested Loop ...
> > Output: ....
> > - Unique Jion: Yes
> > -> Seq Scan on public.t2 (cost = ...
> > - -> Seq Scan on public.t1 (cost = ....
> > + -> Seq Scan on public.t1 (unique) (cost = ....
> >
> >
> >
> Yeah I'm not too big a fan of this either. I did at one evolution of the
> patch I had "Unique Left Join" in the join node's line in the explain
> output, but I hated that more and changed it just to be just in the VERBOSE
> output, and after I did that I didn't want to change the join node's line
> only when in verbose mode. I do quite like that it's a separate item for
> the XML and JSON explain output. That's perhaps quite useful when the
> explain output must be processed by software.
>
> I'm totally open for better ideas on names, but I just don't have any at
> the moment.

"Unique Left Join" looks too bold. Anyway changing there is
rather easier.

> > Coding:
> >
> > The style looks OK. Could applied on master.
> > It looks to work as you expected for some cases.
> >
> > Random comments follow.
> >
> > - Looking specialjoin_is_unique_join, you seem to assume that
> > !delay_upper_joins is a sufficient condition for not being
> > "unique join". The former simplly indicates that "don't
> > commute with upper OJs" and the latter seems to indicate that
> > "the RHS is unique", Could you tell me what kind of
> > relationship is there between them?
> >
>
> The rationalisation around that are from the (now changed) version of
> join_is_removable(), where the code read:
>
> /*
> * Must be a non-delaying left join to a single baserel, else we aren't
> * going to be able to do anything with it.
> */
> if (sjinfo->jointype != JOIN_LEFT ||
> sjinfo->delay_upper_joins)
> return false;
>
> I have to admit that I didn't go and investigate why delayed upper joins
> cannot be removed by left join removal code, I really just assumed that
> we're just unable to prove that a join to such a relation won't match more
> than one outer side's row. I kept this to maintain that behaviour as I
> assumed it was there for a good reason.

Yes, I suppose that you thought so and it should work as expected
as a logical calculation for now. But delay_upper_joins is the
condition for not being allowed to be removed and the meaning
looks not to have been changed, right? If so, I think they should
be treated according to their right meanings.

Specifically, delay_upper_joins should be removed from the
condition for unique_join to the original location, at the very
first of join_is_removable.

> > - The naming "unique join" seems a bit obscure for me, but I
> > don't have no better idea:( However, the member name
> > "has_unique_join" seems to be better to be "is_unique_join".
> >
> >
> Yeah, I agree with this. I just can't find something short enough that
> means "based on the join condition, the inner side of the join will never
> produce more than 1 row for any single outer row". Unique join was the best
> I came up with. I'm totally open for better ideas.

It should be good to write the precise definition of "unique
join" in the appropriate comment.

> I agree that is_unique_join is better than has_unique_join. I must have
> just copied the has_eclass_joins struct member without thinking too hard
> about it. I've now changed this in my local copy of the patch.
>
> - eclassjoin_is_unique_join involves seemingly semi-exhaustive
> > scan on ec members for every element in joinlist. Even if not,
> > it might be thought to be a bit too large for the gain. Could
> > you do the equivelant things by more small code?
> >
> >
> I'd imagine some very complex queries could have many equivalence classes
> and members, though I hadn't really thought that this number would be so
> great that processing here would suffer much. There's quite a few fast
> paths out, like the test to ensure that both rels are mentioned
> in ec_relids. Though for a query which is so complex to have a great number
> of eclass' and members, likely there would be quite a few relations
> involved and planning would be slower anyway. I'm not quite sure how else I
> could write this and still find the unique join cases each time. We can't
> really just give up half way through looking.

A rough estimate for a bad case is mentioned above. I had the
similar comment about the complexity for code to find implicitly
uniquely ordered join peer. Perhaps there's many improvable
points implemented easily by looping over join_list and
eclasses. But we would shuold do them without piled loops.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center