Re: [HACKERS] PoC: full merge join on comparison clause

I tried to fix the things you mentioned and improve the comments. Among
other changes, there is now a description of how merge join works with
inequalities at the top of nodeMergejoin.c. It also explains why we only
support one inequality clause.

Some particular points:

On 07/06/2018 04:01 PM, Ashutosh Bapat wrote:
> - StrategyNumber opstrategy = mergestrategies[iClause];
> + StrategyNumber sort_strategy = mergestrategies[iClause];
> - int op_strategy;
> + int join_strategy;
> I don't see a reason why should we change the name of variable here. These are
> operator strategies and there's no need to change their names. The name change
> is introducing unnecessary diffs.

These variables have different meaning but their names differ only with
an underscore. When I had to change this function, I made mistakes
because of this. I'd keep the descriptive names to avoid further
confusion. Should this be a separate patch?

> I think we should write a wrapper around MJCompare which interprets the result rather
> than changing MJCompare itself. OR at least change the name of MJCompare.

Renamed the function to MJTestTuples to reflect that it decides whether
we join tuples or advance either side.

> - * for get_mergejoin_opfamilies().
> + * for get_equality_opfamilies().
>
> I think we should leave mergejoin word in there or at least indicate that these
> are btree opfamilies so that we don't confuse it with hash equality operator
> families.

Renamed these to get_btree_equality_opfamilies() and
get_btree_comparison_opfamilies().

> + if (parent->mj_Ineq_Present)
> + elog(ERROR, "inequality mergejoin clause must be the last one");
> +
>
> IIUC, this never happens. If it really happens, we have created a path which
> can not be used practically. That should never happen. It will help to add a
> comment here clarifying that situation.

This is just a cross-check for the planner. Added a comment. We should
probably use a separate error code for internal errors as opposed to
user errors, but I'm not sure if we have one, I see just elog(ERROR)
being used everywhere.

>
> + bool have_inequality = have_inequality_mergeclause(mergeclauses);
>
> There will be many paths created with different ordering of pathkeys. So,
> instead of calling have_inequality_mergeclause() for each of those paths, it's
> better to save this status in the path itself when creating the path.

I removed this function altogether, because we can just check the last
merge clause. When we cost the path, we already have a proper
mergejoinable list of clauses, so if there is an inequality clause, it's
the last one.

> /* Make a pathkey list with this guy first */
> if (l != list_head(all_pathkeys))
> + {
> + if (have_inequality && l == list_tail(all_pathkeys))
> + /* Inequality merge clause must be the last, we can't
> move it */
> + break;
> +
>
> I am kind of baffled by this change. IIUC the way we create different orderings
> of pathkeys here, we are just rotating the pathkeys in circular order. This
> means there is exactly one ordering of pathkeys where the pathkey corresponding
> to the inequality clause is the last one.

This code does not rotate the pathkeys circularly, but puts each of them
in the first position, and keeps the rest in the original order.
Say, if we have three equality pathkeys, and one inequality pathkey at
the end (let's denote them as E1, E2, E3, IE), the permutations it tries
will be like this:
E1 E2 E3 IE
E2 E1 E3 IE
E3 E1 E2 IE
Does this sound right?

> /* Might have no mergeclauses */
> if (nClauses == 0)
> return NIL;
>
> + {
> + List *ineq_clauses = find_inequality_clauses(mergeclauses);
> +
> + if (list_length(ineq_clauses) > 1)
> + return NIL;
>
> Without this patch, when there is an inequality clause with FULL JOIN, we will
> not create a merge join path because select_mergejoin_clauses() will set
> mergejoin_allowed to false. This means that we won't call
> sort_inner_and_outer(). I think this patch also has to do the same i.e. when
> there are more than one inequality clauses, select_mergejoin_clauses() should
> set mergejoin_allowed to false in case of a FULL JOIN since merge join
> machinary won't be able to handle that case.
>
> If we do that, we could arrange extra.mergeclause_list such that the inequality
> clause is always at the end thus finding inequality clause would be easy.

I changed select_mergejoin_clauses() to filter multiple inequality
clauses and disable join if needed. Now we can use extra inequalities as
join filter, if it's not full join. I didn't reorder
extra.mergeclause_list there, because this order is ignored later.
select_outer_pathkeys_for_merge() chooses the order of pathkeys using
some heuristics, and then find_mergeclauses_for_outer_pathkeys()
reorders the clauses accordingly.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company