Support large input batches in null-aware sort-merge joins under memory limits

未关闭
  • 哪里不对？
#27,054 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

还没有人认领这个 Issue。

评估

难度
5/5
预计耗时
一周以上
新手友好度
35/100
Issue 类型
功能
描述清晰度
基本清楚
活跃度
活跃
技术栈
rust, sql
领域
databases, performance

调研方向

Start with the TODO in datafusion/physical-plan/src/joins/sort_merge_join/exec.rs and review PR #26090’s discussion. Run the provided repro.sql command with the 100 MB memory limit to examine the failure. Done means a giant-batch input completes with regression coverage for constrained-memory execution and the three stated NOT IN semantics.

由索引模型根据 Issue 内容生成。

描述

enhancement
Is your feature request related to a problem or challenge?

This issue originated from PR #26090 and Issue #25546.

PR #26090 adds support for uncorrelated, single-key null-aware LeftAnti sort-merge joins, allowing supported NOT IN queries to use SortMergeJoinExec when datafusion.optimizer.prefer_hash_join = false.

The initial implementation requires single-partition inputs. However the original reproduce from #25546 was reported to still fail under a 100 MB memory limit because unnest(generate_series(...)) produces a single 20-million-row batch (in left partitions). This batch is not split before reaching the sort.

Run:

datafusion-cli -m 100M --mem-pool-type fair -f repro.sql

Contents of repro.sql:

set datafusion.execution.target_partitions = 4;
set datafusion.optimizer.prefer_hash_join = false;

create view big as
select v as x
from (select unnest(generate_series(1, 20000000)) as v);

create view small as
select v as y
from (select unnest(generate_series(1, 1000)) as v);

select count(*) from big where x not in (select y from small);

Reported error on the PR #26090:

Failed to allocate additional 152.7 MB for ExternalSorter[0]

With normally batched input using the table-function form of
generate_series, the reviewer reported that the query succeeds and returns
19999000.

Describe the solution you'd like

Allow this null-aware sort-merge join query to complete under the same
memory limit when its input arrives as a single giant batch.

(Or allow this null-aware sort-merge join query to complete under a 100 MB memory limit even when the input arrives as a single batch containing 20 million rows.)

One possible approach, mentioned in the TODO in PR #26090 SortMergeJoinExec::input_distribution_requirements (file: datafusion/physical-plan/src/joins/sort_merge_join/exec.rs), is to allow multiple left partitions while sharing the right-side summary needed for null-aware semantics. The partitioning and right-input handling would need to preserve
correct join results.

The implementation must preserve the NOT IN semetics:

  • An empty right input retains every left row, including NULL keys.
  • A right input containing a NULL key produces no output.
  • Otherwise, only unmatched, non-NULL left keys are retained.

Add regression coverage for giant input batches under a constrained memory pool, alongside coverage of these null-aware semantics.

Describe alternatives you've considered
  • Split oversized batches before sorting, if this can be done within the memory limit.
Additional context

This is a follow-up to PR #26090 and the original request in Issue #25546.

Review discussion:
https://github.com/apache/datafusion/pull/26090#discussion_r4370152526

The failure above was reported during review of PR #26090 ; it has not been independently reverified for this issue.

主要语言
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 摘要。