You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2026/07/28 03:07:22 UTC

[PR] feat(core): rewrite NOT IN subqueries into distributable anti join plans [datafusion-ballista]

andygrove opened a new pull request, #2199:
URL: https://github.com/apache/datafusion-ballista/pull/2199

   # Which issue does this PR close?
   
   Part of #2198.
   
   # Rationale for this change
   
   #2188 made null-aware anti joins correct by collapsing them to a single task, because DataFusion's null-aware hash join coordinates its visited-row bitmap and probe-side NULL state through in-process atomics. That lowering loses all parallelism and caps the build side (the outer table) at `ballista.optimizer.broadcast_join_threshold_bytes`.
   
   This PR implements option 2 from #2198: rewrite uncorrelated `NOT IN (subquery)` filter predicates during logical optimization so that no null-aware join is planned in the first place. For
   
   ```sql
   SELECT a FROM t1 WHERE a NOT IN (SELECT b FROM t2)
   ```
   
   the rewrite produces
   
   ```text
   Projection: t1.a
     Filter: __cnt = 0 OR (t1.a IS NOT NULL AND __cnt = __cnt_non_null)
       CrossJoin
         Aggregate: count(1) AS __cnt, count(b) AS __cnt_non_null   (over t2)
         LeftAnti Join: t1.a = t2.b
           TableScan: t1
           SubqueryAlias: t2
   ```
   
   which is equivalent under SQL three-valued `NOT IN` semantics in a `WHERE` context: an empty subquery passes every row, a matching probe value is dropped by the anti join, and a NULL probe value or a NULL in the subquery drops the remaining rows via the one-row aggregate. Every operator in the rewritten plan is an ordinary distributable one, so the outer table keeps full parallelism and the broadcast threshold no longer applies.
   
   A side effect is that `NOT IN` now also returns correct results under Ballista's default sort-merge-join configuration, where the null-aware flag was previously dropped before scheduler lowering (the practical impact of #2193).
   
   # What changes are included in this PR?
   
   - New `NotInSubqueryRewrite` logical optimizer rule in `ballista-core`, prepended to DataFusion's default rules so it runs before `DecorrelatePredicateSubquery`. The rewrite only fires where null-aware semantics would otherwise be needed: uncorrelated subqueries with a single output column and a nullable key on either side. Correlated, multi-column, volatile, and provably non-nullable predicates are left to DataFusion's own decorrelation, and the #2188 single-task lowering remains as the fallback for anything the rewrite does not cover.
   - Registration in every Ballista session builder: `SessionState::new_ballista_state`, `upgrade_for_ballista`, and the scheduler's `default_session_builder`.
   - New config key `ballista.optimizer.not_in_subquery_rewrite` (Boolean, default `true`); setting it to `false` restores the previous null-aware planning and single-task lowering.
   - Unit tests for the rewrite shape and its skip conditions, and new `default` and `rewrite_disabled` variants in the `null_aware` integration test. The `default` variant fails without this change (wrong results on the sort-merge path) and passes with it.
   - Config table and tuning guide documentation updates.
   
   # Are there any user-facing changes?
   
   `NOT IN` queries with uncorrelated single-column subqueries now execute as fully distributed anti joins under static and adaptive planning, including under the default configuration, and are no longer subject to the broadcast threshold cap or the single-task lowering. The new `ballista.optimizer.not_in_subquery_rewrite` key (default `true`) disables the rewrite if needed. No public API changes.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): rewrite NOT IN subqueries into distributable anti join plans [datafusion-ballista]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #2199:
URL: https://github.com/apache/datafusion-ballista/pull/2199#issuecomment-5099637934

   cc @phillipleblanc 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): rewrite NOT IN subqueries into distributable anti join plans [datafusion-ballista]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #2199:
URL: https://github.com/apache/datafusion-ballista/pull/2199#issuecomment-5099646635

   For reviewers, it may be useful to compare this with how Spark handles the same problem.
   
   Spark plans single column `NOT IN` as a null-aware anti join (SPARK-32290). It broadcasts the subquery side as a special `HashedRelation` that carries two flags computed while building the broadcast: whether the subquery is empty and whether it contains a NULL key. Each streamed partition of the outer table then applies purely local logic. The subquery is empty, so emit the row. The subquery has a NULL, or my key is NULL, or my key matches, so drop the row. No cross partition coordination is needed and the outer table stays fully distributed.
   
   This PR reaches the same place but at the plan level instead of inside the join operator. The one row `count(*)` / `count(b)` aggregate captures exactly the two global facts Spark bakes into its broadcast relation, and the plain anti join takes the place of Spark's special null-aware probe logic. The filter over the cross join is the same local decision Spark makes per streamed row.
   
   A few practical differences:
   
   - Spark makes one pass over the subquery, since the flags are computed while building the broadcast. This rewrite scans the subquery twice, once for the anti join and once for the aggregate. Both scans are cheap relative to the join itself and both distribute.
   - Spark's null-aware anti join requires the subquery to be broadcastable and falls back to `BroadcastNestedLoopJoin` otherwise. The rewritten plan here has no broadcast requirement at all, since the anti join can shuffle on the key, so large subqueries are fine.
   - Both approaches are limited to single column `NOT IN`. Multi column predicates fall through to the existing paths.
   
   The closest structural match to Spark would be a null-aware join that builds on the subquery side, which is the upstream DataFusion improvement tracked as option 1 in #2198. If that lands, the special casing here can eventually go away and the swap optimizations would produce Spark's shape natively.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): rewrite NOT IN subqueries into distributable anti join plans [datafusion-ballista]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove merged PR #2199:
URL: https://github.com/apache/datafusion-ballista/pull/2199


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org