zzwqqq created CALCITE-7755:
-------------------------------
Summary: Support IEJoin for inequality joins
Key: CALCITE-7755
URL: https://issues.apache.org/jira/browse/CALCITE-7755
Project: Calcite
Issue Type: Improvement
Reporter: zzwqqq
Assignee: zzwqqq
Calcite uses {{EnumerableNestedLoopJoin}} for Enumerable joins without
equi-keys. With two range predicates, it evaluates the condition for every pair
of input rows.
Khayyat et al.[1] use East-Coast and West-Coast cloud transactions to motivate
this problem. The query finds West-Coast transactions that last longer but
produce less revenue:
{code:sql}
SELECT east.id, west.t_id
FROM east, west
WHERE east.dur < west.time
AND east.rev > west.cost
{code}
For one inequality, sorting turns the matching rows into a prefix or suffix. A
second inequality creates another range in a different sort order. IEJoin uses
a permutation array to map positions between the two orders. A bit array is
then used to enumerate their intersection. This avoids building a Cartesian
product before applying the predicates.
IEJoin is useful when both inputs remain large and no selective equality
predicate or filter reduces them. It avoids testing every non-matching pair.
The paper's single-node evaluation summarizes the benefit as follows:
{quote}IEJoin outperforms existing baselines by at least an order of magnitude
for two main reasons: it avoids the use of the expensive Cartesian product and
it nicely exploits memory locality by using memory-contiguous data structures
with a small footprint.
{quote}
The paper also reports that observed performance was proportional to the result
size. The worst-case bound remains quadratic, and producing a large result can
still dominate runtime. IEJoin nevertheless provides a specialized alternative
to nested-loop join for this class of queries.
The initial Calcite implementation would follow the union-array IEJoin
algorithm described by Khayyat et al. It would add IEJoin as an Enumerable
physical alternative for:
* {{INNER JOIN}}
* At least two conjunctive, cross-input inequality predicates
* {{{}<{}}}, {{{}<={}}}, {{{}>{}}}, and {{>=}}
* Direct input references as IEJoin keys
* SQL {{NULL}} semantics and duplicate keys
Two predicates would drive IEJoin. Additional inequalities would be evaluated
above the join, as described in the paper. Unsupported join shapes would
continue to use the existing Enumerable join implementations.
The change would add an {{EnumerableIEJoin}} physical node, a converter rule,
and a linq4j runtime implementation. No new SQL syntax or logical join type
would be required.
# [Zuhair Khayyat et al., "Lightning Fast and Space Efficient Inequality
Joins," PVLDB 8(13), 2015|https://doi.org/10.14778/2831360.2831362]
# [DuckDB
implementation|https://github.com/duckdb/duckdb/blob/master/src/execution/operator/join/physical_iejoin.cpp]
# [ClickHouse
implementation|https://github.com/ClickHouse/ClickHouse/blob/master/src/Processors/QueryPlan/IEJoinStep.cpp]
# [Polars
implementation|https://github.com/pola-rs/polars/tree/main/crates/polars-ops/src/frame/join/iejoin]
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
