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

Ouverte
  • Quelque chose ne va pas ?
#27,054 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
35/100
Type d'issue
Fonctionnalité
Clarté
Plutôt claire
Activité
Active
Stack technique
rust, sql
Domaine
databases, performance

Piste de recherche

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.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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.

Langage dominant
Rust
Étoiles
9.6k
Forks
2.6k
Merge moyen
3 j 4 h
PR mergées (30 j)
345

Préparer son environnement

Ouvrir dans Codespaces

Lance le conteneur de développement du projet dans votre navigateur, avec votre propre compte GitHub.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de apache/datafusion

Toutes les issues de apache/datafusion

Issues similaires

Plus d'issues Rust

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.