Re: Performance improvement for joins where outer side is unique

agora inbox for [email protected]  
help / color / mirror / Atom feed

From: Tomas Vondra <[email protected]>
To: David Rowley <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: PostgreSQL-development <[email protected]>
Subject: Re: Performance improvement for joins where outer side is unique
Date: Thu, 17 Dec 2015 01:17:17 +0100
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAKJS1f_i7dGh9ytc0DuaX3JJaN7Gp9AGXNbdtWjj0PkPzNzUeg@mail.gmail.com>
References: <[email protected]>
	<CAPpHfdviphQFjk-gaGZGGxLAyt=YuVdJLnntsxOKnU296s9u-Q@mail.gmail.com>
	<CAKJS1f-=1y0-f5FFV2_r7LtS+CL2Lw-nhJjXB3O_0FmBqnK=3A@mail.gmail.com>
	<27152324.eFKJb4Khb5@dinodell>
	<[email protected]>
	<[email protected]>
	<CAKJS1f-9UTo6fA+h8rojd30CujSKscZamLn5YnKw5+ASbV0Wwg@mail.gmail.com>
	<[email protected]>
	<CAKJS1f_8hrzTDCu0pwERWj_dLZu-6DYFQJAtNT+vM6UeOn0kHw@mail.gmail.com>
	<[email protected]>
	<CAKJS1f8JCt15ngEP8sZO-JYYT8mS6HUP_CT0T6S_0ogk1kQt+Q@mail.gmail.com>
	<CAKJS1f_4hm3qwKeHYKftd+BQuYBgdNR+rk+XP_JW9EY-ALHZbQ@mail.gmail.com>
	<[email protected]>
	<CAKJS1f_i7dGh9ytc0DuaX3JJaN7Gp9AGXNbdtWjj0PkPzNzUeg@mail.gmail.com>
List-Unsubscribe: <mailto:[email protected]?body=unsub%20pgsql-hackers>

Hi,

On 12/16/2015 11:40 PM, David Rowley wrote:
> On 17 December 2015 at 05:02, Tomas Vondra <[email protected]
> <mailto:[email protected]>> wrote:
>
>     0) I know the patch does not tweak costing - any plans in this
>
>         direction? Would it be possible to simply use the costing used by
>         semijoin?
>
>
> Many thanks for looking at this.
>
> The patch does tweak the costings so that unique joins are costed in the
> same way as semi joins. It's a very small change, so easy to miss.

Thanks. I missed that bit somehow.

>
> For example, see the change in initial_cost_nestloop()
>
> -       if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
> +       if (jointype == JOIN_SEMI ||
> +               jointype == JOIN_ANTI ||
> +               unique_inner)
>          {
>
> Also see the changes in final_cost_nestloop() and final_cost_hashjoin()
>
>
>     1) nodeHashjoin.c (and other join nodes)
>
>     I've noticed we have this in the ExecHashJoin() method:
>
>       /*
>        * When the inner side is unique or we're performing a
>        * semijoin, we'll consider returning the first match, but
>        * after that we're done with this outer tuple.
>        */
>       if (node->js.unique_inner)
>           node->hj_JoinState = HJ_NEED_NEW_OUTER;
>
>     That seems a bit awkward because the comment speaks about unique
>     joins *OR* semijoins, but the check only references unique_inner.
>     That of course works because we do this in ExecInitHashJoin():
>
>              switch (node->join.jointype)
>              {
>                      case JOIN_SEMI:
>                              hjstate->js.unique_inner = true;
>                              /* fall through */
>
>     Either some semijoins may not be unique - in that case the naming is
>     misleading at best, and we either need to find a better name or
>     simply check two conditions like this:
>
>       if (node->js.unique_inner || node->join.type == JOIN_SEMI)
>          node->hj_JoinState = HJ_NEED_NEW_OUTER;
>
>     Or all semijoins are unique joins, and in that case the comment may
>     need rephrasing. But more importantly, it begs the question why
>     we're detecting this in the executor and not in the planner? Because
>     if we detect it in executor, we can't use this bit in costing, for
>     example.
>
>
> The reason not to detect that in the planner is simply that unique_join
> is meant to mean that the relation on the inner side of the join will at
> most contain a single Tuple which matches each outer relation tuple,
> based on the join condition. I've added no detection for this in semi
> joins, and I'd rather not go blindly setting the flag to true in the
> planner as it simply may not be true for the semi join. At the moment
> that might not matter as we're only using the unique_join flag as an
> optimization in the join nodes, but I'd prefer not to do this as its
> likely we'll want to do more with this flag later, and I'd rather we
> keep the meaning well defined. You might argue that this is also true
> for semi joins, but if down the road somewhere we want to perform some
> checks on the inner relation before the join takes place, and in that
> case the Tuples of the relation might not have the same properties we
> claim they do.
>
> But you're right that reusing the flag in the join nodes is not ideal,
> and the comment is not that great either. I'd really rather go down the
> path of either renaming the variable, or explaining this better in the
> comment. It seems unnecessary to check both for each tuple being joined.
> I'd imagine that might add a little overhead to joins which are not unique.

I'd be very surprised it that had any measurable impact.

> How about changing the comment to:
>
> /*
> * In the event that the inner side has been detected to be
> * unique, as an optimization we can skip searching for any
> * subsequent matching inner tuples, as none will exist.
> * For semijoins unique_inner will always be true, although
> * in this case we don't match another inner tuple as this
> * is the required semi join behavior.
> */
>
> Alternatively or additionally we can rename the variable in the executor
> state, although I've not thought of a name yet that I don't find overly
> verbose: unique_inner_or_semi_join,  match_first_tuple_only.

I'd go with match_first_tuple_only.

>
>
>     2) analyzejoins.c
>
>     I see that this code in join_is_removable()
>
>          innerrel = find_base_rel(root, innerrelid);
>
>          if (innerrel->reloptkind != RELOPT_BASEREL)
>              return false;
>
>     was rewritten like this:
>
>          innerrel = find_base_rel(root, innerrelid);
>
>          Assert(innerrel->reloptkind == RELOPT_BASEREL);
>
>     That suggests that previously the function expected cases where
>     reloptkind may not be RELOPT_BASEREL, but now it'll error out int
>     such cases. I haven't noticed any changes in the surrounding code
>     that'd guarantee this won't happen, but I also haven't been able to
>     come up with an example triggering the assert (haven't been trying
>     too hard). How do we know the assert() makes sense?
>
>
> I'd have changed this as this should be covered by the if
> (!sjinfo->is_unique_join || a few lines up. mark_unique_joins() only
> sets is_unique_join to true if specialjoin_is_unique_join() returns true
> and that function tests reloptkind to ensure its set to RELOPT_BASEREL
> and return false if the relation is not. Perhaps what is missing is a
> comment to explain the function should only be used on RELOPT_BASEREL
> type relations.

Yeah, I think it'd be good to document this contract somewhere. Either 
in the comment before the function, or perhaps right above the Assert().

regards

--
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

view thread (132+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected]
  Subject: Re: Performance improvement for joins where outer side is unique
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox