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

   ### Versions
   
   - DataFusion 55.2.0 (`datafusion-datasource-parquet` 55.2.0), Arrow / 
Parquet 59, macOS (Apple Silicon).
   - Not checked on main or on earlier releases.
   
   ### Describe the bug
   
   `SELECT ... WHERE seq >= x ORDER BY seq LIMIT n [OFFSET k]` returns the 
wrong rows when all of these hold:
   
   - the table's files are declared sorted by `seq` 
(`ListingOptions::with_file_sort_order`), so the sort is removed;
   - there is more than one file;
   - `target_partitions` is more than 1;
   - filter pushdown is on (`datafusion.execution.parquet.pushdown_filters = 
true`);
   - the filter matches the first rows' row group only in part.
   
   The partly matched row group is skipped, and the query returns rows from the 
next whole-matched row group instead. The scan's `limit_pruned_row_groups` 
metric is non-zero in exactly these runs.
   
   The cause, as far as I can tell:
   
   1. The limit reaches the scan (`DataSourceExec ... limit=1, 
output_ordering=[seq@0 ASC]`) under a `SortPreservingMergeExec: [seq@0 ASC 
NULLS LAST], fetch=1`.
   2. The opener prunes row groups by the limit when the scan is not marked 
order-preserving (`opener/mod.rs`, around line 1356):
      ```rust
      if let (Some(limit), false) = (prepared.limit, prepared.preserve_order) {
          row_groups.prune_by_limit(limit, rg_metadata, &prepared.file_metrics);
      ```
   3. `prune_by_limit` (`row_group_filter.rs`, around line 178) keeps only row 
groups the predicate matches whole, whenever those alone hold at least `limit` 
rows. That is right for an unordered `LIMIT`, but here the scan's order is the 
query's order.
   
   With one file, or `target_partitions = 1`, the same queries are right and 
`limit_pruned_row_groups` is 0. The page index plays no part: the result is the 
same with one page per row group.
   
   ### To Reproduce
   
   `Cargo.toml`:
   
   ```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"] }
   ```
   
   `src/main.rs` (arguments: files, target partitions, 
`split_file_groups_by_statistics`, rows per page):
   
   ```rust
   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::prelude::*;
   
   #[tokio::main]
   async fn main() -> Result<()> {
       let args: Vec<String> = std::env::args().collect();
       let files: i64 = args.get(1).map_or(1, |a| a.parse().unwrap());
       let partitions: usize = args.get(2).map_or(1, |a| a.parse().unwrap());
       let split: bool = args.get(3).is_some_and(|a| a == "true");
       let page_rows: usize = args.get(4).map_or(1024 * 1024, |a| 
a.parse().unwrap());
   
       let dir = std::env::temp_dir().join("df-limit-pruning-repro");
       let _ = std::fs::remove_dir_all(&dir);
       std::fs::create_dir_all(&dir)?;
   
       // seq = 3 * i + 1 for i in 0..50 per file, files in sequence order,
       // row groups of 16 rows.
       let schema = Arc::new(Schema::new(vec![
           Field::new("seq", DataType::Int64, false),
           Field::new("label", DataType::Utf8, false),
       ]));
       for file in 0..files {
           let values: Vec<i64> = (file * 50..(file + 1) * 50).map(|i| 3 * i + 
1).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_dictionary_enabled(false)
               .set_max_row_group_row_count(Some(16))
               .set_data_page_row_count_limit(page_rows)
               .set_write_batch_size(page_rows.min(1024))
               .build();
           let path = dir.join(format!("batch_{file:016}.parquet"));
           let mut writer = ArrowWriter::try_new(std::fs::File::create(&path)?, 
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;
       config.options_mut().execution.split_file_groups_by_statistics = split;
       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())?;
       let table = 
ListingTableConfig::new(url).with_listing_options(options).with_schema(schema);
       ctx.register_table("t", Arc::new(ListingTable::try_new(table)?))?;
   
       for sql in [
           // The 5th row is seq 13: the first row group (seq 1..46) matches in 
part.
           "SELECT seq FROM t WHERE seq >= 13 ORDER BY seq LIMIT 1",
           "SELECT seq, label FROM t WHERE seq >= 13 ORDER BY seq LIMIT 1",
           "SELECT seq FROM t WHERE seq >= 13 ORDER BY seq LIMIT 1 OFFSET 2",
           // Control: the filter matches every row group whole or not at all.
           "SELECT seq FROM t WHERE seq >= 49 ORDER BY seq LIMIT 1",
       ] {
           let batches = ctx.sql(sql).await?.collect().await?;
           println!("{sql}\n{}", pretty_format_batches(&batches)?);
           let plan = ctx.sql(&format!("EXPLAIN ANALYZE 
{sql}")).await?.collect().await?;
           println!("{}\n", pretty_format_batches(&plan)?);
       }
       return Ok(());
   }
   ```
   
   Run with `cargo run --release -- 4 8 true 4`, and vary the arguments.
   
   ### Expected behavior
   
   The four queries return `13`, `13 | row 13`, `19` and `49`.
   
   ### Actual behavior
   
   Run on 55.2.0. Each row is one setting; "answers" are the four queries' 
first `seq`; "limit pruned" is `limit_pruned_row_groups` per query:
   
   | files | target_partitions | split by statistics | rows per page | answers 
| limit pruned |
   |---|---|---|---|---|---|
   | 1 | 1 | false | 4 | 13 13 19 49 (right) | 0 0 0 0 |
   | 1 | 8 | false | 4 | 13 13 19 49 (right) | 0 0 0 0 |
   | 4 | 1 | true | 4 | 13 13 19 49 (right) | 0 0 0 0 |
   | 4 | 2 | true | 4 | **49 49 55** 49 | 6 6 6 5 |
   | 4 | 8 | true | 4 | **49 49 55** 49 | 12 12 12 11 |
   | 4 | 8 | true | 1,048,576 (one page per group) | **49 49 55** 49 | 12 12 12 
11 |
   | 4 | 8 | false | 4 | **49 49 55** 49 | 12 12 12 11 |
   
   The plan for the first query at `4 8 true 4`, cut down:
   
   ```
   SortPreservingMergeExec: [seq@0 ASC NULLS LAST], fetch=1
     DataSourceExec: file_groups={8 groups: [...]}, projection=[seq], limit=1, 
output_ordering=[seq@0 ASC],
       file_type=parquet, predicate=seq@0 >= 13, ...
       row_groups_pruned_statistics=16 total → 16 matched -> 15 fully matched,
       limit_pruned_row_groups=12 total → 0 matched, ...
   ```
   
   `49` is the first row of the second row group: the first row group (seq 
1..46, matched in part) was pruned.
   
   ### Suggested fix
   
   When the scan's output ordering is required above it (here by the 
`SortPreservingMergeExec` that replaced the removed sort), treat the scan as 
order-preserving and skip `prune_by_limit`. Alternatively, when the scan has an 
output ordering, have `prune_by_limit` keep every row group before the last one 
it keeps.
   
   ### Additional context
   
   Turning filter pushdown off hides the bug, because the filter then sits 
above the scan and the limit no longer reaches it.
   


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