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

   ### Describe the bug
   
   `ORDER BY seq LIMIT 3 OFFSET 2` followed by a projection that computes 
something (a `CAST` or `concat`) sometimes returns its rows in the wrong order, 
when `target_partitions > 1`.
   
   The physical plan ends with a round-robin repartition *above* the limit, and 
the plan's root then has several output partitions:
   
   ```
   ProjectionExec: expr=[seq@0 as seq, CAST(label@1 AS Utf8) as label]
     RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, 
maintains_sort_order=true
       GlobalLimitExec: skip=2, fetch=3
         DataSourceExec: ..., limit=5, output_ordering=[seq@0 ASC], 
file_type=parquet, predicate=seq@0 >= 13, ...
   ```
   
   Each output partition is sorted, so `maintains_sort_order=true` holds 
partition by partition. But nothing merges them back in order, and 
`DataFrame::collect` interleaves them. The query's `ORDER BY` is then not 
honoured.
   
   With a plain column projection (`select(seq, label)`) there is no 
repartition and no fault.
   
   ### To Reproduce
   
   One Parquet file: `seq` 0..50 ascending (`Int64`, required) and `label` 
(`Utf8`), in row groups of 16 rows. It is registered as a listing table with 
`with_file_sort_order([seq ASC NULLS FIRST])` and its schema inferred, so 
`label` is read as `Utf8View`. Session: `target_partitions = 4`, 
`pushdown_filters = true`.
   
   ```rust
   let df = ctx.table("t").await?
       .filter(col("seq").gt_eq(lit(13_i64)))?
       .sort(vec![col("seq").sort(true, true)])?
       .limit(2, Some(3))?
       .select(vec![col("seq"), cast(col("label"), 
DataType::Utf8).alias("label")])?;
   let batches = df.collect().await?;   // expect seq 15, 16, 17
   ```
   
   Results over 40 runs each:
   
   | Projection | target_partitions | Runs out of order |
   |---|---|---|
   | `CAST(label AS Utf8)` | 1 | 0 / 40 |
   | `CAST(label AS Utf8)` | 2 | 15 / 40 |
   | `CAST(label AS Utf8)` | 4 | 18 / 40 |
   | `CAST(label AS Utf8)` | 8 | 16 / 40 |
   | `concat(label, '!')` | 4 | 17 / 40 |
   | `label` (plain column) | 4 | 0 / 40 |
   
   A typical wrong result is `[16, 17, 15]`.
   
   The full program (`cargo run --release --bin order -- 4 40 cast`):
   
   <details><summary>Cargo.toml and src/bin/order.rs</summary>
   
   ```toml
   [package]
   name = "df-limit-pruning-repro"
   version = "0.1.0"
   edition = "2024"
   publish = false
   
   [workspace]
   
   [dependencies]
   datafusion = { version = "=55.2.0", default-features = false, features = 
["parquet", "sql"] }
   tokio = { version = "1", features = ["rt-multi-thread", "macros"] }
   ```
   
   ```rust
   //! An ordered query whose final projection DataFusion repartitions round
   //! robin: each output partition stays sorted, but collecting the plan
   //! interleaves them, so the rows come back out of order.
   //!
   //! `cargo run --release --bin order -- <target_partitions> <runs> 
<cast|concat|plain>`
   use std::sync::Arc;
   
   use datafusion::arrow::array::{Int64Array, RecordBatch, StringArray};
   use datafusion::arrow::datatypes::{DataType, Field, Schema};
   use datafusion::arrow::util::pretty::pretty_format_batches;
   use datafusion::datasource::file_format::parquet::ParquetFormat;
   use datafusion::datasource::listing::{ListingOptions, ListingTable, 
ListingTableConfig, ListingTableUrl};
   use datafusion::error::Result;
   use datafusion::parquet::arrow::ArrowWriter;
   use datafusion::parquet::file::properties::WriterProperties;
   use datafusion::physical_plan::displayable;
   use datafusion::prelude::*;
   
   #[tokio::main]
   async fn main() -> Result<()> {
       let args: Vec<String> = std::env::args().collect();
       let partitions: usize = args.get(1).map_or(4, |a| a.parse().unwrap());
       let runs: usize = args.get(2).map_or(20, |a| a.parse().unwrap());
       // How the label is projected above the limit: `cast` (to Utf8, from the
       // Utf8View the reader produces), `concat` (a computed expression) or
       // `plain` (the column).
       let mode: String = args.get(3).cloned().unwrap_or_else(|| 
"cast".to_string());
       let projection = |mode: &str| -> Expr {
           return match mode {
               "concat" => concat(vec![col("label"), lit("!")]).alias("label"),
               "plain" => col("label"),
               _ => cast(col("label"), DataType::Utf8).alias("label"),
           };
       };
   
       let dir = std::env::temp_dir().join("df-order-repro");
       let _ = std::fs::remove_dir_all(&dir);
       std::fs::create_dir_all(&dir)?;
       // One file: seq 0..50 ascending, a label, row groups of 16 rows.
       let schema = Arc::new(Schema::new(vec![
           Field::new("seq", DataType::Int64, false),
           Field::new("label", DataType::Utf8, false),
       ]));
       let values: Vec<i64> = (0..50).collect();
       let labels: Vec<String> = values.iter().map(|v| format!("row 
{v}")).collect();
       let batch = RecordBatch::try_new(
           schema.clone(),
           vec![Arc::new(Int64Array::from(values)), 
Arc::new(StringArray::from(labels))],
       )?;
       let props = 
WriterProperties::builder().set_max_row_group_row_count(Some(16)).build();
       let mut writer = 
ArrowWriter::try_new(std::fs::File::create(dir.join("data.parquet"))?, 
schema.clone(), Some(props))?;
       writer.write(&batch)?;
       writer.close()?;
   
       let mut config = SessionConfig::new().with_target_partitions(partitions);
       config.options_mut().execution.parquet.pushdown_filters = true;
       let ctx = SessionContext::new_with_config(config);
       let options = ListingOptions::new(Arc::new(ParquetFormat::default()))
           .with_file_extension(".parquet")
           .with_file_sort_order(vec![vec![col("seq").sort(true, true)]]);
       let url = ListingTableUrl::parse(dir.to_str().unwrap())?;
       // The schema inferred from the file: strings read as Utf8View.
       let table = 
ListingTableConfig::new(url).with_listing_options(options).infer_schema(&ctx.state()).await?;
       ctx.register_table("t", Arc::new(ListingTable::try_new(table)?))?;
   
       // WHERE seq >= 13 ORDER BY seq LIMIT 3 OFFSET 2, then a projection that
       // casts the label (read as Utf8View) back to Utf8.
       let mut wrong: usize = 0;
       let mut last = String::new();
       for _ in 0..runs {
           let df = ctx
               .table("t")
               .await?
               .filter(col("seq").gt_eq(lit(13_i64)))?
               .sort(vec![col("seq").sort(true, true)])?
               .limit(2, Some(3))?
               .select(vec![col("seq"), projection(&mode)])?;
           let plan = df.clone().create_physical_plan().await?;
           last = displayable(plan.as_ref()).indent(true).to_string();
           let batches = df.collect().await?;
           let seqs: Vec<i64> = batches
               .iter()
               .flat_map(|b| 
b.column(0).as_any().downcast_ref::<Int64Array>().unwrap().values().to_vec())
               .collect();
           if seqs != vec![15, 16, 17] {
               wrong += 1;
               println!("wrong order: {seqs:?}\n{}", 
pretty_format_batches(&batches)?);
           }
       }
       println!("{wrong} of {runs} runs out of order (expected seq 15, 16, 
17)\nplan:\n{last}");
       return Ok(());
   }
   ```
   
   </details>
   
   ### Expected behavior
   
   The rows come back in `seq` order. Either no round-robin repartition is 
inserted above a sorted, limited single partition when the plan's output must 
be ordered, or the root restores the order (a `SortPreservingMergeExec`, or 
`CoalescePartitionsExec` with ordering).
   
   ### Suggested fix
   
   When a plan's root must produce an ordered result, either don't insert a 
`RoundRobinBatch` repartition above a sorted single partition (the projection 
can run in that partition), or, if it is inserted, have the root restore the 
order with a `SortPreservingMergeExec` over the repartitioned output. The first 
is cheaper for small limited results.
   
   ### Additional context
   
   - In this plan the repartition presumably exists to parallelise the 
projection. With 3 rows it gains nothing.
   - We found this while working around a different issue on the same pages 
(#27549). Our workaround is to wrap any multi-partition plan that declares an 
output ordering in a `SortPreservingMergeExec` before collecting it.
   - Between 53.1 and 55.2, `EnforceDistribution` and `EnforceSorting` were 
replaced by one `EnsureRequirements` rule. We have not checked whether 53.1 
inserts the same repartition.
   


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