Re: Performance improvement for joins where outer side is unique

On 13 March 2015 at 20:34, Kyotaro HORIGUCHI <
horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> wrote:

> Hello. The performance drag was not so large after all.
>
>
Great, thanks for retesting this.

> For all that, I agree that the opition that this kind of separate
> multiple-nested loops on relations, joins or ECs and so on for
> searching something should be avoided. I personally feel that
> additional time to such an extent (around 1%) would be tolerable
> if it affected a wide range of queries or it brought more obvious
> gain.
>
>
Do you have any ideas on an implementation of how we can avoid checking all
eclasses for each combination of joins?

The only thing I can think of would be to add a List of eclasses on
RelOptInfo for all eclasses that the RelOptInfo has. That would save the
looping over every single eclass in eclassjoin_is_unique_join() and save
from having to check if the relation is mentioned in the eclass before
continuing. I could certainly make this change, but I'd be worried that it
would just add bloat to the patch and cause a committed to question it.

I could also almost completely remove the extra plan time of your test case
by either adding a proper pre-check to ensure the relation has unique
indexes, rather than just indexes or I could add a new list to RelOptInfo
which stores unique index, then I could just check if that's NIL before
going any further in eclassjoin_is_unique_join(), but I come from a world
where every relation has a primary key, so I'd just imagine that would not
be hit in enough real cases. I'd imagine that pre-check is only there
because it's so cheap in the first place.

For testing, I added some code to mark_unique_joins() to spit out a NOTICE:

if (eclassjoin_is_unique_join(root, joinlist, rtr))
{
root->simple_rel_array[rtr->rtindex]->is_unique_join = true;
elog(NOTICE, "Unique Join: Yes");
}
else
elog(NOTICE, "Unique Join: No");

and the same below for special joins too.

On running the regression tests I see:

"Unique Join: Yes" 1557 times
"Unique Join: No" 11563 times

I would imagine the regression tests are not the best thing to base this
one as they tend to exercise more unusual cases.
I have an OLTP type application here which I will give a bit of exercise
and see how that compares.

> Unfortunately I can't decide this to be 'ready for commiter' for
> now. I think we should have this on smaller footprint, in a
> method without separate exhauxtive searching. I also had very
> similar problem in the past but I haven't find such a way for my
> problem..
>
>
I don't think it's ready yet either. I've just been going over a few things
and looking at Tom's recent commit b557226 in pathnode.c I've got a feeling
that this patch would need to re-factor some code that's been modified
around the usage of relation_has_unique_index_for() as when this code is
called, the semi joins have already been analysed to see if they're unique,
so it could be just a case of ripping all of that out
of create_unique_path() and just putting a check to say rel->is_unique_join
in there. But if I do that then I'm not quite sure if
SpecialJoinInfo->semi_rhs_exprs and SpecialJoinInfo->semi_operators would
still be needed at all. These were only added in b557226. Changing this
would help reduce the extra planning time when the query contains
semi-joins. To be quite honest, this type of analysis belongs in
analyzejoin.c anyway. I'm tempted to hack at this part some more, but I'd
rather Tom had a quick glance at what I'm trying to do here first.

>
> At Wed, 11 Mar 2015 01:32:24 +1300, David Rowley <dgrowleyml(at)gmail(dot)com>
> wrote in <CAApHDvpEXAjs6mV2ro4=3qbzpx=
> pLrteinX0J2YHq6wrp85pPw(at)mail(dot)gmail(dot)com>
> > > 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.
> > >
> > >
> > This smells quite fishy to me. I'd be quite surprised if your machine
> took
> > an extra 2 ms to do this.
>
> You're right. Sorry. I was amazed by the numbers..
>
> I took again the times for both master and patched on master
> (some conflict arised). Configured with no options so compiled
> with -O2 and no assertions. Measured the planning time for the
> test query 10 times and calcualted the average.
>
> patched: 1.883ms (stddev 0.034)
> master: 1.861ms (stddev 0.042)
>
> About 0.02ms, 1% extra time looks to be taken by the extra
> processing.
>
>
Is this still using the same test query as I attached in my previous email?

This is still 25 times more of a slowdown as to what I witnessed by calling
mark_unique_joins() 1 million times in a tight loop, but of course much
closer to what I would have thought. You're getting 20,000 nanoseconds and
I'm getting 800 nanoseconds, but our overall planning times are very
similar, so I assume our processors are of similar speeds.

It's certainly difficult to know if the extra planning will pay off enough
for it to reduce total CPU time between both planning and executing the
query. There actually are cases where the planning time will be reduced by
this patch. In the case when a LEFT JOIN is removed the master code
currently goes off and re-checks all relations to see if the removal of
that 1 relation has caused it to be possible for other relations to be
removed, and this currently involves analysing unique indexes again to see
if the join is still unique. With this patch I've cut out most of the work
which is done in join_is_removable(), it no longer does that unique
analysis of the join condition as that's done in mark_unique_joins(). The
cases that should be faster are, if a join is already marked as unique then
the code will never test that again.

I have quite a few other ideas lined up which depend on knowing if a join
is unique, all these ideas naturally depend on this patch. Really the
5%-10% join speed-up was the best excuse that I could find have this work
actually accepted. My first email in this thread explains some of my other
ideas.

In addition to those ideas I've been thinking about how that if we could
determine that a plan returns a single row, e.g a key lookup then we could
likely safely cache those plans, as there were never be any data skew in
these situations. I have no immediate plans to go and work on this, but
quite possibly I will in the future if I manage to get unique joins in
first.

Regards

David Rowley