[
https://issues.apache.org/jira/browse/CALCITE-7755?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated CALCITE-7755:
------------------------------------
Labels: pull-request-available (was: )
> 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
> Priority: Major
> Labels: pull-request-available
>
> 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://vldb.org/pvldb/vol8/p2074-khayyat.pdf]
> # [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)
