jayzhan211 commented on code in PR #27395:
URL: https://github.com/apache/datafusion/pull/27395#discussion_r4572854624


##########
datafusion/sqllogictest/test_files/projection_pushdown.slt:
##########
@@ -2872,6 +2872,185 @@ SET datafusion.execution.batch_size = 8192;
 statement ok
 SET datafusion.execution.target_partitions = 4;
 
+# An `OFFSET` the source pushes down puts a `GlobalLimitExec` between the scan
+# and the leaf projection, and a second node under it when the scan has more
+# than one file group, which strands `get_field` above them and reads the whole
+# struct again. See `try_split_leaf_projection` in
+# `datafusion/physical-optimizer/src/projection_pushdown.rs`.
+
+# Every `OFFSET` below sets a skip that differs from the fetch -- `OFFSET 1
+# LIMIT 3` for the single-file queries, `OFFSET 1 LIMIT 2` for the multi-file
+# ones -- never `OFFSET n LIMIT n`: the split rebuilds the limit, and with the
+# two numbers equal nothing here would notice them being swapped.
+
+# Values first: these pin the rows, which no plan assertion shows. They are not
+# the only cover for a misplaced `skip`, which reddens the plans below as well,
+# and they are no cover at all for a dropped `fetch`, which nothing in this 
file
+# notices. The unit tests carry that one.
+query I
+SELECT v FROM (SELECT s['value'] AS v FROM leaf_split OFFSET 1 LIMIT 3) ORDER 
BY v;
+----
+150
+200
+300
+
+query II
+SELECT v, w FROM (
+    SELECT s['value'] AS v, id + 1 AS w FROM leaf_split OFFSET 1 LIMIT 3
+) ORDER BY v;
+----
+150 4
+200 3
+300 5
+
+# A bare `get_field` alone in its projection.
+query TT
+EXPLAIN SELECT s['value'] AS v FROM leaf_split OFFSET 1 LIMIT 3;
+----
+logical_plan
+01)Projection: __datafusion_extracted_1 AS v
+02)--Limit: skip=0, fetch=3
+03)----Projection: get_field(leaf_split.s, Utf8("value")) AS 
__datafusion_extracted_1
+04)------TableScan: leaf_split projection=[s], fetch=3, skip=1
+physical_plan
+01)ProjectionExec: expr=[__datafusion_leaf_0@0 as v]
+02)--GlobalLimitExec: skip=1, fetch=3
+03)----DataSourceExec: file_groups={1 group: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split.parquet]]},
 projection=[get_field(s@1, value) as __datafusion_leaf_0], limit=4, 
file_type=parquet
+
+# With a computed sibling, which stays above the limit: only the leaf descends.
+query TT
+EXPLAIN SELECT s['value'] AS v, id + 1 AS w FROM leaf_split OFFSET 1 LIMIT 3;
+----
+logical_plan
+01)Projection: __datafusion_extracted_1 AS v, leaf_split.id + Int64(1) AS w
+02)--Limit: skip=0, fetch=3
+03)----Projection: get_field(leaf_split.s, Utf8("value")) AS 
__datafusion_extracted_1, leaf_split.id
+04)------TableScan: leaf_split projection=[id, s], fetch=3, skip=1
+physical_plan
+01)ProjectionExec: expr=[__datafusion_leaf_0@1 as v, id@0 + 1 as w]
+02)--GlobalLimitExec: skip=1, fetch=3
+03)----DataSourceExec: file_groups={1 group: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split.parquet]]},
 projection=[id, get_field(s@1, value) as __datafusion_leaf_0], limit=4, 
file_type=parquet
+
+# A leaf nested inside a `KeepInPlace` expression. `upper` stays above the
+# limit, so the rows the limit skips do not pay for it, and the scan still
+# reads only the two fields.
+query TT
+EXPLAIN SELECT s['value'] AS v, upper(s['label']) AS l FROM leaf_split OFFSET 
1 LIMIT 3;
+----
+logical_plan
+01)Projection: __datafusion_extracted_1 AS v, upper(__datafusion_extracted_2) 
AS l
+02)--Limit: skip=0, fetch=3
+03)----Projection: get_field(leaf_split.s, Utf8("value")) AS 
__datafusion_extracted_1, get_field(leaf_split.s, Utf8("label")) AS 
__datafusion_extracted_2
+04)------TableScan: leaf_split projection=[s], fetch=3, skip=1
+physical_plan
+01)ProjectionExec: expr=[__datafusion_leaf_0@0 as v, 
upper(__datafusion_leaf_1@1) as l]
+02)--GlobalLimitExec: skip=1, fetch=3
+03)----DataSourceExec: file_groups={1 group: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split.parquet]]},
 projection=[get_field(s@1, value) as __datafusion_leaf_0, get_field(s@1, 
label) as __datafusion_leaf_1], limit=4, file_type=parquet
+
+# No leaf expression in the projection. This is a control, not a guard: the
+# scan prunes to `[id]` either way, so the plan is the same whether or not the
+# rule bails out early. What pins the bail-out is
+# `split_declines_global_limit_without_leaf` in
+# `datafusion/core/tests/physical_optimizer/projection_pushdown.rs`.
+query TT
+EXPLAIN SELECT id + 1 AS w FROM leaf_split OFFSET 1 LIMIT 3;
+----
+logical_plan
+01)Projection: leaf_split.id + Int64(1) AS w
+02)--Limit: skip=0, fetch=3
+03)----TableScan: leaf_split projection=[id], fetch=3, skip=1
+physical_plan
+01)ProjectionExec: expr=[id@0 + 1 as w]
+02)--GlobalLimitExec: skip=1, fetch=3
+03)----DataSourceExec: file_groups={1 group: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split.parquet]]},
 projection=[id], limit=4, file_type=parquet
+
+# A marker inside a lambda body, under an `OFFSET`. The lambda queries further
+# up cover the body without a limit, and the queries just above cover the limit
+# without a lambda; nothing covered both, and this errors before the fix. It is
+# also what pins `rebase_lambda_variable`: the parameter index is rebased
+# against the chain's bottom schema, which the split has just widened.
+# The lambda section above runs with `batch_size = 2`, which inserts a
+# repartition; this one has to stay here, where `batch_size` is high enough 
that
+# the only node between the projection and the scan is the limit.
+statement ok
+SET datafusion.sql_parser.dialect = databricks;
+
+query ?IT
+SELECT a, v, l FROM (
+    SELECT array_transform(arr, x -> x + file_row_index()) AS a,
+           s['value'] AS v, s['label'] AS l
+    FROM leaf_split OFFSET 1 LIMIT 3
+) ORDER BY v;
+----
+[8] 150 gamma
+[5, 6] 200 beta
+[10, 11, 12] 300 delta
+
+statement ok
+SET datafusion.sql_parser.dialect = generic;
+
+# More than one file group: a `CoalescePartitionsExec` sits between the limit
+# and the scan, so the leaf has to descend past two nodes. Stopping at the
+# first one leaves the scan reading the whole struct.
+
+statement ok
+COPY (
+    SELECT column1 AS id, column2 AS s FROM VALUES
+        (1, {value: 100, label: 'alpha'}), (2, {value: 200, label: 'beta'})
+) TO 'test_files/scratch/projection_pushdown/leaf_split_two/a.parquet'
+STORED AS PARQUET;
+
+statement ok
+COPY (
+    SELECT column1 AS id, column2 AS s FROM VALUES
+        (3, {value: 150, label: 'gamma'}), (4, {value: 300, label: 'delta'})
+) TO 'test_files/scratch/projection_pushdown/leaf_split_two/b.parquet'
+STORED AS PARQUET;
+
+statement ok
+CREATE EXTERNAL TABLE leaf_split_two STORED AS PARQUET
+LOCATION 'test_files/scratch/projection_pushdown/leaf_split_two/';
+
+query TT
+EXPLAIN SELECT s['value'] AS v FROM leaf_split_two OFFSET 1 LIMIT 2;
+----
+logical_plan
+01)Projection: __datafusion_extracted_1 AS v
+02)--Limit: skip=0, fetch=2
+03)----Projection: get_field(leaf_split_two.s, Utf8("value")) AS 
__datafusion_extracted_1
+04)------TableScan: leaf_split_two projection=[s], fetch=2, skip=1
+physical_plan
+01)ProjectionExec: expr=[__datafusion_leaf_0@0 as v]
+02)--GlobalLimitExec: skip=1, fetch=2
+03)----CoalescePartitionsExec: fetch=3
+04)------DataSourceExec: file_groups={2 groups: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split_two/a.parquet],
 
[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split_two/b.parquet]]},
 projection=[get_field(s@1, value) as __datafusion_leaf_0], limit=3, 
file_type=parquet
+
+query TT
+EXPLAIN SELECT s['value'] AS v, id + 1 AS w FROM leaf_split_two OFFSET 1 LIMIT 
2;
+----
+logical_plan
+01)Projection: __datafusion_extracted_1 AS v, leaf_split_two.id + Int64(1) AS w
+02)--Limit: skip=0, fetch=2
+03)----Projection: get_field(leaf_split_two.s, Utf8("value")) AS 
__datafusion_extracted_1, leaf_split_two.id
+04)------TableScan: leaf_split_two projection=[id, s], fetch=2, skip=1
+physical_plan
+01)ProjectionExec: expr=[__datafusion_leaf_0@1 as v, id@0 + 1 as w]
+02)--GlobalLimitExec: skip=1, fetch=2
+03)----CoalescePartitionsExec: fetch=3
+04)------DataSourceExec: file_groups={2 groups: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split_two/a.parquet],
 
[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split_two/b.parquet]]},
 projection=[id, get_field(s@1, value) as __datafusion_leaf_0], limit=3, 
file_type=parquet
+
+# Which rows survive the skip depends on the order the partitions are merged
+# in, which is not guaranteed, so this counts them instead of listing them.
+query I
+SELECT count(v) FROM (
+    SELECT s['value'] AS v FROM leaf_split_two OFFSET 1 LIMIT 2
+);
+----
+2
+
+statement ok
+DROP TABLE leaf_split_two;

Review Comment:
   Optional: the issue's own setting, a table bigger than `batch_size`, gives a 
third shape with no test. A `RepartitionExec` lands above the limit, and the 
split then acts on the leaf projection under it. On main this EXPLAIN keeps 
`projection=[id, s]`, and the `file_row_index()` version fails with "source 
dependent". I ran this block in this file at the PR head and it passes:
   
   ```suggestion
   DROP TABLE leaf_split_two;
   
   # A table bigger than `batch_size` also gets a `RepartitionExec`, which lands
   # above the limit. The split then acts on the leaf projection under it.
   statement ok
   SET datafusion.execution.batch_size = 2;
   
   query TT
   EXPLAIN SELECT s['value'] AS v, id + 1 AS w FROM leaf_split OFFSET 1 LIMIT 3;
   ----
   logical_plan
   01)Projection: __datafusion_extracted_1 AS v, leaf_split.id + Int64(1) AS w
   02)--Limit: skip=0, fetch=3
   03)----Projection: get_field(leaf_split.s, Utf8("value")) AS 
__datafusion_extracted_1, leaf_split.id
   04)------TableScan: leaf_split projection=[id, s], fetch=3, skip=1
   physical_plan
   01)ProjectionExec: expr=[__datafusion_extracted_1@0 as v, id@1 + 1 as w]
   02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
   03)----ProjectionExec: expr=[__datafusion_leaf_0@1 as 
__datafusion_extracted_1, id@0 as id]
   04)------GlobalLimitExec: skip=1, fetch=3
   05)--------DataSourceExec: file_groups={1 group: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/projection_pushdown/leaf_split.parquet]]},
 projection=[id, get_field(s@1, value) as __datafusion_leaf_0], limit=4, 
file_type=parquet
   
   query II
   SELECT v, w FROM (SELECT s['value'] AS v, id + 1 AS w FROM leaf_split OFFSET 
1 LIMIT 3) ORDER BY v;
   ----
   150 4
   200 3
   300 5
   
   statement ok
   SET datafusion.execution.batch_size = 8192;
   ```



##########
datafusion/core/tests/physical_optimizer/projection_pushdown.rs:
##########
@@ -2035,3 +2038,354 @@ async fn split_declines_hash_repartition() -> 
Result<()> {
     );
     Ok(())
 }
+
+/// Schema and parquet scan the `GlobalLimitExec` tests below share: a plain
+/// column beside a struct whose `value` field the leaf expression reads.
+fn limit_split_scan() -> Result<(SchemaRef, Arc<dyn ExecutionPlan>)> {
+    let schema: SchemaRef = Arc::new(Schema::new(vec![
+        Field::new("id", DataType::Int64, true),
+        Field::new(
+            "s",
+            DataType::Struct(vec![Field::new("value", DataType::Int64, 
true)].into()),
+            true,
+        ),
+    ]));
+    let config = FileScanConfigBuilder::new(
+        ObjectStoreUrl::parse("test:///").unwrap(),
+        Arc::new(ParquetSource::new(Arc::clone(&schema))),
+    )
+    .with_file(PartitionedFile::new("x".to_string(), 100))
+    .build();
+    Ok((schema, DataSourceExec::from_data_source(config)))
+}
+
+/// `[get_field(s, 'value') as v, id + 1 as w]`: one leaf expression beside one
+/// that has to stay in place.
+fn limit_split_exprs(schema: &SchemaRef) -> Result<Vec<ProjectionExpr>> {
+    let leaf: Arc<dyn PhysicalExpr> = Arc::new(ScalarFunctionExpr::new(
+        "get_field",
+        datafusion_functions::core::get_field(),
+        vec![
+            col("s", schema)?,
+            Arc::new(Literal::new(ScalarValue::from("value"))),
+        ],
+        Arc::new(Field::new("v", DataType::Int64, true)),
+        Arc::new(ConfigOptions::default()),
+    ));
+    Ok(vec![
+        ProjectionExpr {
+            expr: leaf,
+            alias: "v".to_string(),
+        },
+        ProjectionExpr {
+            expr: binary(
+                col("id", schema)?,
+                Operator::Plus,
+                Arc::new(Literal::new(ScalarValue::Int64(Some(1)))),
+                schema,
+            )?,
+            alias: "w".to_string(),
+        },
+    ])
+}
+
+fn optimized_plan_text(plan: Arc<dyn ExecutionPlan>) -> Result<String> {
+    let optimized =
+        ProjectionPushdown::new().optimize(plan, &ConfigOptions::default())?;
+    Ok(displayable(optimized.as_ref())
+        .indent(true)
+        .to_string()
+        .trim()
+        .to_string())
+}
+
+#[tokio::test]
+async fn split_descends_through_global_limit() -> Result<()> {
+    let (schema, scan) = limit_split_scan()?;
+    // What a source that pushes `OFFSET` down builds: the skip becomes a
+    // `GlobalLimitExec` around the scan, below the leaf projection.
+    // `skip` and `fetch` differ on purpose: the split rebuilds the limit, and
+    // with them equal this snapshot would hold just as well if it swapped 
them.
+    let limit: Arc<dyn ExecutionPlan> = Arc::new(GlobalLimitExec::new(scan, 1, 
Some(3)));
+    let projection: Arc<dyn ExecutionPlan> =
+        Arc::new(ProjectionExec::try_new(limit_split_exprs(&schema)?, limit)?);
+
+    // The leaf reaches the scan, which now reads the one field instead of the
+    // whole struct. `id + 1` stays above the limit, so the rows the limit 
skips
+    // do not pay for it, and both of the limit's numbers survive the rebuild.
+    assert_snapshot!(
+        optimized_plan_text(projection)?,
+        @r"    ProjectionExec: expr=[__datafusion_leaf_0@1 as v, id@0 + 1 as w]

Review Comment:
   Optional cleanup: insta prints "Multiline inline snapshot values should 
start and end with a newline. The current value will fail to match in the 
future" for this snapshot and the 9 other new ones (lines 2142, 2163, 2185, 
2206, 2231, 2258, 2344, 2355, 2385). Putting a newline right after `@r"`, like 
the rest of this file, removes all 10 warnings, and the tests still pass:
   
   ```suggestion
           @r"
       ProjectionExec: expr=[__datafusion_leaf_0@1 as v, id@0 + 1 as w]
   ```



##########
datafusion/physical-optimizer/src/projection_pushdown.rs:
##########
@@ -490,29 +497,113 @@ fn leaf_column_name(index: usize) -> String {
     format!("{LEAF_COLUMN_PREFIX}_{index}")
 }
 
+/// Returns the child of `node` if a projection may be split beneath it.
+///
+/// Every arm evaluates no expression of its own and has exactly one child, so
+/// widening that child with the leaf columns cannot change what it does. Each
+/// also hands its child's schema straight through, which is what lets the
+/// outer expressions keep their column indices when the split descends past
+/// several of these in a row.
+///
+/// That last property holds by construction rather than by luck: none of the
+/// three `compute_properties` takes a schema, and each clones its input's
+/// equivalence properties, so a host's schema *is* its child's. There is no
+/// guard here for it. A fourth arm that projects would need one, because
+/// `rewrite_outer_expr` remaps the outer column indices and rebases lambda
+/// parameters against the width of the chain's bottom schema, and a host that
+/// changed the width would leave both against the wrong one.
+fn split_host_child(node: &Arc<dyn ExecutionPlan>) -> Option<&Arc<dyn 
ExecutionPlan>> {
+    if let Some(repartition) = node.downcast_ref::<RepartitionExec>() {
+        // Hash and Range partitioning reference columns by index, which would
+        // have to be remapped against the rewritten child schema. Round robin
+        // carries no column references, and is what `EnsureRequirements`
+        // inserts here.
+        if !matches!(repartition.partitioning(), 
Partitioning::RoundRobinBatch(_)) {
+            return None;
+        }
+        Some(repartition.input())
+    } else if let Some(limit) = node.downcast_ref::<GlobalLimitExec>() {
+        // `LocalLimitExec` qualifies structurally — no expressions of its own,
+        // one child, and `replace_children` keeps its fetch — and the planner
+        // builds one under a `GlobalLimitExec` when the input has more than 
one
+        // partition (`physical_planner.rs`, the `Limit` branch).
+        // The corpus does enter this function at a `LocalLimitExec`, but only
+        // with no leaf to move, never with one stranded above it, so it is 
left
+        // out. `CooperativeExec` and `BufferExec` meet the same three
+        // conditions, and so did `CoalesceBatchesExec` before it was 
deprecated
+        // in 52.0.0: these arms are an allowlist, not whatever those 
conditions
+        // admit. `split_declines_local_limit` pins it.
+        Some(limit.input())
+    } else {
+        // A scan with more than one file group puts this between the limit and
+        // the source. Its own `try_swapping_with_projection` takes a 
projection
+        // only if it narrows, which a leaf projection need not do; the split 
is
+        // still worth it here, because what descends is exactly what the 
source
+        // prunes to.
+        Some(node.downcast_ref::<CoalescePartitionsExec>()?.input())
+    }
+}
+
+/// The hosts a split descends past, and the node that has to absorb the leaf
+/// projection.
+struct SplitHostChain<'a> {
+    /// Outermost first, so the rebuild walks this in reverse.
+    hosts: Vec<&'a Arc<dyn ExecutionPlan>>,
+    /// The first node that is not a host.
+    child: &'a Arc<dyn ExecutionPlan>,
+}
+
+/// Walks the chain of hosts beneath a projection.
+///
+/// `None` when the projection sits on no host at all. A single `OFFSET` on a
+/// multi-file table already stacks two of them, a `GlobalLimitExec` over a
+/// `CoalescePartitionsExec`, so stopping at the first one would leave the leaf
+/// expression stranded exactly where it is today.
+fn split_host_chain(node: &Arc<dyn ExecutionPlan>) -> 
Option<SplitHostChain<'_>> {
+    let mut hosts = vec![];
+    let mut current = node;
+    while let Some(child) = split_host_child(current) {
+        hosts.push(current);
+        current = child;
+    }
+    // A termination guard, not an optimization. With it removed this rule is
+    // handed the same plan over and over: a projection holding a leaf whose
+    // child is another projection, so the chain is empty. The 
`counted_volatile`
+    // queries in `projection_pushdown.slt` are that shape, a volatile inner
+    // projection being what stops `remove_unnecessary_projections` from 
merging
+    // the pair first; that file then runs until the harness gives up while 
every
+    // Rust test stays green. Why the rewrite fails to converge is not pinned
+    // down further.

Review Comment:
   Optional cleanup: the cause this comment leaves open is 
`ProjectionExec::try_swapping_with_projection` 
(`physical-plan/src/projection.rs:508-511`). When the two projections can't 
collapse, it returns `Some(projection.clone())`, so the commit gate passes with 
nothing absorbed. I removed the guard and ran a projection over a 
`ProjectionExec` that can't collapse: the split fired more than 50 times. 
Suggested wording:
   
   ```suggestion
       // A termination guard, not an optimization. With no host, `current` is 
the
       // projection's own input. When that is a `ProjectionExec` the two cannot
       // collapse into (the `counted_volatile` queries in 
`projection_pushdown.slt`),
       // `ProjectionExec::try_swapping_with_projection` returns the lower
       // projection stacked on top of it, so the split commits, and
       // `transform_down` then visits that lower projection and splits it 
again.
   ```



-- 
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: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to