[FEA] Conditional hash join for inner joins

[jlowe]

Is your feature request related to a problem? Please describe.
Currently the RAPIDS Accelerator for Apache Spark accelerates a hash-based inner join with an inequality condition as an inner-join on the equality condition followed by a filter with the inequality condition. This works fine as long as the equality-join is the primary discriminator, but there are some inner joins in applications that can "explode," generating many output rows due to many replicated keys in either the left or right tables. If the inner join explodes and the inequality condition filters out most rows then the performance approaches that of a nested loop join followed by the filter which is not great. The GPU ends up manifesting many, many rows of the input tables only to have them eliminated by the filter.

It is much more efficient in that case to have the join evaluate not only the equality condition via the hash lookup but also evaluate the inequality after the hash lookup succeeds before declaring the candidate row pair a join match. This avoids manifesting many rows that will not ultimately survive.

Describe the solution you'd like
libcudf supports accepting a supplemental condition represented as an AST expression to the existing hash-based inner join APIs, including the hash_join based APIs. Internally the join kernel performs the hash lookup based on the equality keys then if there's a hit in the hash lookup it evaluates the AST expression to produce a boolean result indicating whether the row should be considered a join match or not. The API can take two sets of table_view pairs, one pair for the left and right equality keys to use and one pair to use for the AST expression evaluation. The result is two gather maps for the left and right tables, respectively, as it is for the hash-based inner join today.

Describe alternatives you've considered
The interface could specify a just two table_views for the left/right table and separately two vectors of ints to specify which columns are the equality keys, but it seems simpler to pass separate table_views for equality vs. AST expression, especially when the application needs to generate the result of an expression for the equality portion of the join (e.g.: t1_col2 + 1 == t2_col3 * 2)

Additional context
This is part of #5401

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.