feat(proto): add physical hashJoin & mergeJoin physical relations

[chaojun-zhang]

This PR includes hashJoin and mergeJoin physical plan relations according the spec

[chaojun-zhang]

@jvanstraten , sorry for my mistake that close the original PR , I can't reopen it so raise a new PR here

[westonpace]

Thank you for contributing these. I'm curious about the duplication here, though I don't know if it's a bad thing entirely.

In #331 we decided that trying too hard to avoid duplication (e.g. by basing as-of join on a logical join) was probably a bad idea. However, in this PR we are providing direct physical specializations of the logical join. Do you think it would make sense to use inheritance here? Is there a reason you chose not to? Can you imagine the physical specializations diverging from the logical specifications (other than just adding on new fields) at some point?

[jvanstraten]

I don't know if this is true, but if all physical joins are likely to use the same fields, shouldn't the physical implementation just be an optional field on JoinRel?

If not, for some of the cases like this for the validator-specific protos (especially scalar vs aggregate vs window functions) I made separate messages for the common fields, in this case for example JoinCommon or something. That way, if we add logical-specific or physical-specific fields later, we can do that outside that common structure, but also avoid duplication. It would be a breaking change for JoinRel to add this indirection, though.

[chaojun-zhang]

To avoid duplicate, I think we may have two options:

• option 1: add new field inside JoinRel like below to distinguish logical join , hash join , merge join and nested loop join

JoinKind kind = 7;

 enum JoinKind {
   JOIN_KIND_LOGICAL = 0;
   JOIN_KIND_HASH = 1;
   JOIN_KIND_MERGE = 2;
   JOIN_KIND_NESTED_LOOP = 3;
 }

• option 2: extract join fields to JoinCommon message, and use inheritance for logical join ,hash join ,merge join and nested loop join

I'm not sure which option is prefer to, my thinking the option 1 may be better since these join operator share the same attributes according to the spec in substrait.io?

[jacques-n]

In general, I think we should avoid collapsing these. I think they actually need to be different. They have different physical property maintenance characterististics and will probably develop in different directions.

Once we get a good definition, let's make sure we also update the associated site docs.

[CLAassistant]

All committers have signed the CLA.

[CLAassistant]

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

[westonpace]

This review is long overdue. I have a few more questions.

[westonpace]

Since this is a physical relation do we want to explicitly declare that the left side is the build side and the right side is the probe side (or vice versa)? It looks like you are already making this assumption in your description of left keys and right keys.

[chaojun-zhang]

I think we can leave it to the user to decide which side is probe or build , your thoughts?

[westonpace]

Picking the correct side is generally an optimizer task (requires statistics / heuristics). My assumption for more physical nodes is that they've already gone through an optimizer.

For a single optimizer/consumer pair this wouldn't be a problem. They can both agree offline which side should be build and probe. However, imagine an engine-independent substrait optimizer created this plan and hoped for it to be consumed by many different engines. In that case the different consumers might pick left/right build/probe differently.

That being said, I haven't worked much with optimizers. CC @jacques-n who has more experience here.

[chaojun-zhang]

@jacques-n @westonpace Please take a further review and help trigger the check again.

[westonpace]

Either we should assign these as probe and build (my preference would be to be explicit) or we should specifically explain that consumers should assign probe & build based on whatever criteria they want. As it is, I think this is ambiguous.

[chaojun-zhang]

@westonpace , thanks for your comment, I found that the documentation has mentioned that the right input is build-side, see this. So let's always assume the left input is probe-side and right input is build-side. your thoughts?

I also updated in this section [https://substrait.io/relations/physical_relations/#hash-equijoin-properties].

Please help trigger the check again. thanks.

[chaojun-zhang]

@westonpace I have update the document and help trigger the check again.

[westonpace]

:( It seems our release script is failing (unrelated to this change) I will see if I can fix that real quick.

[westonpace]

Fixed. Please rebase and I will run again.

[westonpace]

This looks good to me. Will also need approval from @jacques-n

[github-actions]

ACTION NEEDED

Substrait follows the Conventional Commits specification for release automation.

The PR title and description are used as the merge commit message. Please update your PR title and description to match the specification.

[chaojun-zhang]

@westonpace PR rebased, Please take a look again. Thanks!

[jacques-n]

LGTM. With @westonpace approval, I'm going to merge.