Preserve the order of right table in NestedLoopJoinExec

[alihan-synnada]

Which issue does this PR close?

Closes #11332.

Rationale for this change

See the linked issue.

What changes are included in this PR?

NestedLoopJoinExec now preserves the order of the right table for Inner, Right, RightAnti and RightSemi join types.

Are these changes tested?

Tested with join_maintains_right_order and relevant SQL logic tests

Are there any user-facing changes?

This PR changes the output ordering of some queries with JOIN, as reflected in SQL logic tests. The output values and the API remain unchanged.

[comphead]

I feel it would be great to have some doc on what this method does and return. Specifically what false/true means, what is the benefit of preserving the order

[alihan-synnada]

Addressed in 09a6cee

[berkaysynnada]

LGTM. Let's apply what @comphead suggested, and then it will be ready to be merged.

[korowa]

This PR seems to introduce a performance regression due to the similar reasons as it was in #9830 (comment) -- now apply_batch_filter may be executed way more times. Query used for the comparison:

EXPLAIN ANALYZE SELECT count(1) FROM nation n JOIN lineitem li ON n.n_nationkey < li.l_orderkey

and for the single partition execution I've got the following results:

-- Before:
NestedLoopJoinExec: join_type=Inner, filter=n_nationkey@0 < l_orderkey@1, metrics=[output_rows=150029850, build_input_rows=25, output_batches=733, build_input_batches=1, input_batches=733, input_rows=6001215, build_mem_used=296, join_time=1.257203344s, build_time=541.719µs]

-- After:
NestedLoopJoinExec: join_type=Inner, filter=n_nationkey@0 < l_orderkey@1, metrics=[output_rows=150029850, build_input_batches=1, input_batches=733, output_batches=733, input_rows=6001215, build_input_rows=25, build_mem_used=296, build_time=488.521µs, join_time=9.563931093s]

(join_time metric shows the issue).

Any thoughts on it?

[comphead]

Thanks @korowa for checking this, the join time is 9x now @berkaysynnada @alihan-synnada

[comphead]

Filed #12528

[korowa]

If this PR enforces ordering by the price of slowdown for all types of inputs (the example shows fairly small build side input, but it also may be enough), it, perhaps, should be reverted and reimplemented -- I suppose, there exist more compromise solutions for this issue, since, if the root cause of slowdown demonstrated in the example, is increased number calls to apply_join_filter_to_indices, the problem, perhaps, could be solved by something like #8952 (which could accumulate indices up to batch size and only then apply filters).

[berkaysynnada]

Thanks for reporting this @korowa. I believe it’s possible to maintain the order without affecting performance. We will work on fixing this shortly.