You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "adriangb (via GitHub)" <gi...@apache.org> on 2026/09/15 19:02:39 UTC

[I] Projected IN subqueries plan two extra nested-loop mark joins per subquery and become quadratic [datafusion]

adriangb opened a new issue, #25341:
URL: https://github.com/apache/datafusion/issues/25341

   ### Describe the bug
   
   An `IN` or `NOT IN` subquery in a SELECT list plans three mark joins for each subquery. Two of those joins have no join predicate. They become `NestedLoopJoinExec: join_type=RightMark` over the full outer side and the full inner side. The cost of the query is then quadratic in the number of rows.
   
   The results are correct. Only the speed is bad. A query that must take about 0.03 s takes more than 70 s on 200000 rows. If you wrap the subquery in `COALESCE`, the expression is duplicated and you get six mark joins. That query takes more than 140 s.
   
   Projected `IN` subqueries were decorrelated by https://github.com/apache/datafusion/pull/24972 (merged 2026-09-15, which closes https://github.com/apache/datafusion/issues/23022). Before that change these queries were not supported. So this is not a regression against an older release. But the plan that the new code makes is much more costly than necessary.
   
   The cause is in `in_subquery_value_mark_join` in `datafusion/optimizer/src/decorrelate_predicate_subquery.rs`. To make three-valued logic visible in a projected column, it builds three mark joins for each subquery:
   
   1. `matched`, the real predicate.
   2. `subquery_has_null`, the subquery filtered to `col IS NULL` and joined with no predicate.
   3. `subquery_non_empty`, the subquery joined with no predicate.
   
   A `CASE` expression then combines the three mark columns. For an uncorrelated subquery the last two joins have no join predicate at all, so they can only plan as nested loop joins.
   
   ### To Reproduce
   
   Tested on commit 22651d24cc with a release build of `datafusion-cli` (`cargo build -p datafusion-cli --profile ci`) on an Apple Silicon laptop.
   
   ```sql
   CREATE TABLE outer_t AS SELECT CAST(v AS INT) AS id, CAST(v % 1000 AS INT) AS z FROM (SELECT unnest(generate_series(1, 200000)) AS v);
   CREATE TABLE inner_t AS SELECT CASE WHEN v % 97 = 0 THEN NULL ELSE CAST(v * 2 AS INT) END AS id, CAST(v % 1000 AS INT) AS z FROM (SELECT unnest(generate_series(1, 200000)) AS v);
   
   -- B1 bare IN in the SELECT list
   SELECT count(*) FILTER (WHERE m), count(*) FILTER (WHERE m IS NULL) FROM (SELECT id, id IN (SELECT id FROM inner_t) AS m FROM outer_t);
   -- B2 COALESCE shape
   SELECT count(*) FILTER (WHERE m) FROM (SELECT id, COALESCE((id IN (SELECT id FROM inner_t))::boolean, false) AS m FROM outer_t);
   -- B3 correlated equality
   SELECT count(*) FILTER (WHERE m), count(*) FILTER (WHERE m IS NULL) FROM (SELECT id, id IN (SELECT i.id FROM inner_t i WHERE i.z = o.z) AS m FROM outer_t o);
   -- B4 two IN subqueries in separate columns
   SELECT count(*) FILTER (WHERE a), count(*) FILTER (WHERE b) FROM (SELECT id IN (SELECT id FROM inner_t) AS a, id IN (SELECT id FROM inner_t WHERE z < 500) AS b FROM outer_t);
   -- B5 correlated EXISTS
   SELECT count(*) FILTER (WHERE e) FROM (SELECT id, EXISTS (SELECT 1 FROM inner_t i WHERE i.id = o.id) AS e FROM outer_t o);
   ```
   
   Measured times. The column "single mark join" is the same queries with one null aware `LeftMark` hash join for each subquery, which is the approach of https://github.com/apache/datafusion/pull/21363. Both builds give the same results.
   
   | Query | main 22651d24cc | single mark join |
   | --- | --- | --- |
   | B1 | 72.6 s | 0.03 s |
   | B2 | 148.8 s | 0.05 s |
   | B3 | 1.4 s | 0.08 s |
   | B4 | 105.4 s | 0.06 s |
   | B5 | 0.03 s | 0.02 s |
   
   To see the plan shape on small tables, use `t1(id)`, `t2(id)` and `t3(id)` and run `EXPLAIN SELECT id, id IN (SELECT id FROM t3) AS m3, id IN (SELECT id FROM t2) AS m2 FROM t1`. On main you get six mark joins for two subqueries:
   
   ```
   logical_plan
   01)Projection: t1.id, __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_2.mark OR t1.id IS NULL AND __correlated_sq_3.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS m3, __correlated_sq_4.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_5.mark OR t1.id IS NULL AND __correlated_sq_6.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_4.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS m2
   02)--LeftMark Join:
   03)----LeftMark Join:
   04)------LeftMark Join: t1.id = __correlated_sq_4.id null_aware
   05)--------LeftMark Join:
   06)----------LeftMark Join:
   07)------------LeftMark Join: t1.id = __correlated_sq_1.id null_aware
   08)--------------TableScan: t1 projection=[id]
   09)--------------SubqueryAlias: __correlated_sq_1
   10)----------------TableScan: t3 projection=[id]
   11)------------SubqueryAlias: __correlated_sq_2
   12)--------------Filter: t3.id IS NULL
   13)----------------TableScan: t3 projection=[id]
   14)----------SubqueryAlias: __correlated_sq_3
   15)------------TableScan: t3 projection=[id]
   16)--------SubqueryAlias: __correlated_sq_4
   17)----------TableScan: t2 projection=[id]
   18)------SubqueryAlias: __correlated_sq_5
   19)--------Filter: t2.id IS NULL
   20)----------TableScan: t2 projection=[id]
   21)----SubqueryAlias: __correlated_sq_6
   22)------TableScan: t2 projection=[id]
   physical_plan
   01)ProjectionExec: expr=[...]
   02)--NestedLoopJoinExec: join_type=RightMark
   03)----DataSourceExec: partitions=1, partition_sizes=[1]
   04)----NestedLoopJoinExec: join_type=RightMark
   05)------FilterExec: id@0 IS NULL
   06)--------DataSourceExec: partitions=1, partition_sizes=[1]
   07)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
   08)--------HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware
   09)----------CoalescePartitionsExec
   10)------------NestedLoopJoinExec: join_type=RightMark
   11)--------------DataSourceExec: partitions=1, partition_sizes=[1]
   12)--------------NestedLoopJoinExec: join_type=RightMark
   13)----------------FilterExec: id@0 IS NULL
   14)------------------DataSourceExec: partitions=1, partition_sizes=[1]
   15)----------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
   16)------------------HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware
   17)--------------------DataSourceExec: partitions=1, partition_sizes=[1]
   18)--------------------DataSourceExec: partitions=1, partition_sizes=[1]
   19)----------DataSourceExec: partitions=1, partition_sizes=[1]
   ```
   
   ### Expected behavior
   
   One mark join for each subquery. No nested loop join.
   
   A single `LeftMark` join is already exact under three-valued logic when the join filter is hashable only. `build_join` makes the join null aware when the keys can be NULL, which came from https://github.com/apache/datafusion/pull/21585. When the keys cannot be NULL, a plain mark join is exact. The three join materialization is necessary only when a non-equality correlated predicate stays as a residual join filter, because the hash join cannot mark UNKNOWN for a residual predicate.
   
   A pull request that makes this change is in preparation.
   
   ### Additional context
   
   `EXISTS` in a SELECT list is not affected. See B5, which is fast on main, because `EXISTS` has two-valued logic and needs one mark join only.
   
   The same subquery shape in a `WHERE` clause is also not affected. The Filter path builds one semi join, anti join or mark join for each subquery.
   


-- 
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.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: [I] Projected IN subqueries plan two extra nested-loop mark joins per subquery and become quadratic [datafusion]

Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb closed issue #25341: Projected IN subqueries plan two extra nested-loop mark joins per subquery and become quadratic
URL: https://github.com/apache/datafusion/issues/25341


-- 
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