Re: Performance improvement for joins where outer side is unique - Mailing list pgsql-hackers
| From | David Rowley |
|---|---|
| Subject | Re: Performance improvement for joins where outer side is unique |
| Date | |
| Msg-id | CAApHDvreGwhgw7fjDXwjNjcFEXov=QQrnvNfkwGzywnTW0Ja7w@mail.gmail.com Whole thread Raw |
| In response to | Re: Performance improvement for joins where outer side is unique (Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>) |
| Responses |
Re: Performance improvement for joins where outer side is unique
Re: Performance improvement for joins where outer side is unique |
| List | pgsql-hackers |
On 13 March 2015 at 20:34, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
David Rowley
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@gmail.com> wrote in <CAApHDvpEXAjs6mV2ro4=3qbzpx=pLrteinX0J2YHq6wrp85pPw@mail.gmail.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
pgsql-hackers by date: