Discuss partitioned execution for ASOF joins

未關閉
  • 哪裡不對？
#26,901 1 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
5/5
預估耗時
一週以上
新手友好度
25/100
Issue 類型
功能
描述清晰度
基本清楚
活躍度
活躍
技術堆疊
rust
領域
databases, performance

研究方向

Read the discussion and linked context in #26592, especially the feedback on the earlier pull request. The proposal concerns AsOfJoinExec, InputCursor, and hash-partitioned execution; compare its memory benefits with the reported slowdown for skewed keys. Done means reaching agreement on an execution design and a clear approach for a follow-up implementation.

由索引模型根據 Issue 內容生成。

描述

Following #26592, I'd like to discuss the design before attempting another implementation.

I should have discussed the approach before opening the PR. Sorry about that.

Proposed approach

The main issue I'm trying to address is that AsOfJoinExec currently collects the entire right input into memory. This means ASOF joins can run out of memory on large right inputs, even when the upstream sorts can spill.

My idea was to use hash-partitioned execution when equality keys are present. Then i could just sort each partition according to the ordering required by the join and have each left partition stream its corresponding right partition instead of collecting and broadcasting the complete right input. Since InputCursor already advances through the right input, I thought this could reuse much of the existing join logic while removing the need to materialize the complete right side. The join would still need memory for its active batches, candidate matches, and pending output rows, but it would no longer need to collect the entire right input.

Tradeoffs

Hash-partitioning both inputs adds work compared to the existing broadcast approach. If most rows share the same equality key, one partition can end up doing most of the work. In my benchmarks, partitioned execution was nearly twice as slow for skewed keys.

Alternatives

Another possibility would be to make the existing right-input collection spillable. However, this would still require merging the right input into a single stream, and each left partition could end up rereading the spilled data.

I think supporting both broadcast and partitioned execution could make sense, depending on input size and key distribution

Additional context

The comment about my PR mentions proto and config as changes i made, highlighting them as something bad. Are we not allowed to

@Xuanwo implemented the original ASOF joins, so i'd appreciate his perspective on this. I noticed he hasnt been active on DataFusion recently, so I'm not sure if he will see this.

@jayzhan211 @alamb I'd also appreciate your thoughts on the design and on how i should approach it.

One thing I was also wondering about is the mention of config and proto changes in the feedback on my PR. Are these generally changes I should avoid making, or was the concern more about how many parts of DataFusion the PR touched without discussing the design first?

主要語言
Rust
星號
9.6k
分支
2.6k
平均合併
3 天 4 小時
30 天內合併 PR
345

環境準備

在 Codespaces 中開啟

在瀏覽器裡用你自己的 GitHub 帳號啟動這個專案的開發容器。

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

apache/datafusion 的其他 Issue

查看 apache/datafusion 的全部 Issue

相似的 Issue

更多 Rust Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。