[
https://issues.apache.org/jira/browse/CALCITE-7380?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
TJ Banghart updated CALCITE-7380:
---------------------------------
Description:
This issue proposes introducing worst-case optimal join (WCOJ) algorithms into
Calcite as an opt-in optimization. WCOJs evaluate multi-way joins in a way that
avoids generating large intermediate results and guarantees runtime
proportional to the worst-case output size of the query, which can
significantly outperform traditional binary join plans for certain query
patterns (e.g., cyclic or graph-like joins).
The implementation would follow a hybrid approach, similar to [Freitag et al.
(PVLDB 2020|https://db.in.tum.de/~freitag/papers/p1891-freitag.pdf]), where the
optimizer can choose worst-case optimal joins when beneficial but fall back to
existing join strategies when they are more appropriate.
was:
This issue proposes introducing worst-case optimal join __ (WCOJ) algorithms
into Calcite as an opt-in optimization. WCOJs evaluate multi-way joins in a way
that avoids generating large intermediate results and guarantees runtime
proportional to the worst-case output size of the query, which can
significantly outperform traditional binary join plans for certain query
patterns (e.g., cyclic or graph-like joins).
The implementation would follow a hybrid approach, similar to [Freitag et al.
(PVLDB 2020|https://db.in.tum.de/~freitag/papers/p1891-freitag.pdf]), where the
optimizer can choose worst-case optimal joins when beneficial but fall back to
existing join strategies when they are more appropriate.
> Add support for worst-case optimal join algorithims
> ---------------------------------------------------
>
> Key: CALCITE-7380
> URL: https://issues.apache.org/jira/browse/CALCITE-7380
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Affects Versions: 1.42.0
> Reporter: TJ Banghart
> Assignee: TJ Banghart
> Priority: Major
> Attachments: p1891-freitag.pdf
>
>
> This issue proposes introducing worst-case optimal join (WCOJ) algorithms
> into Calcite as an opt-in optimization. WCOJs evaluate multi-way joins in a
> way that avoids generating large intermediate results and guarantees runtime
> proportional to the worst-case output size of the query, which can
> significantly outperform traditional binary join plans for certain query
> patterns (e.g., cyclic or graph-like joins).
> The implementation would follow a hybrid approach, similar to [Freitag et al.
> (PVLDB 2020|https://db.in.tum.de/~freitag/papers/p1891-freitag.pdf]), where
> the optimizer can choose worst-case optimal joins when beneficial but fall
> back to existing join strategies when they are more appropriate.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
