You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "2010YOUY01 (via GitHub)" <gi...@apache.org> on 2023/06/29 20:52:19 UTC

[GitHub] [arrow-datafusion] 2010YOUY01 opened a new pull request, #6801: parallel csv scan

2010YOUY01 opened a new pull request, #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801

   # Which issue does this PR close?
   
   <!--
   We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
   -->
   
   Closes #6325.
   
   # Rationale for this change
   
   <!--
    Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
    Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.  
   -->
   There are 3 steps to scan a CSV file in parallel:
   * The initial physical plan contains some whole file scans during the planing
     * `CsvExec: file_groups={1 group: [[a.csv:0..100]]} `
   * **Step 1:** `PhysicalOptimizerRule` (`Repartition`) will decide if the `CsvExec` node can be parallelized, it won't be parallelized if the parent node requires certain order or have some other conditions.
   * **Step 2:** Repartition the byte range evenly during physical optimization `Repartition`, and store partitions in `CsvExec.base_config.file_groups`, also this step doesn't care about how to separate lines correctly (partitions may contain half lines)
     * `CsvExec: file_groups={2 groups: [[a.csv:0..50], [a:50..100]]}`
   * **Step 3:** A worker will be spawned for each file group partition (e.g. `[a.csv:0..50]`), and deal with partition boundaries
     * (`[a.csv:0..50] -> Lines:1..5`).
   
   # What changes are included in this PR?
   ### Step 1
   The parallel parquet scan PR has already done it https://github.com/apache/arrow-datafusion/pull/5057, for parallel CSV scan, it only added a rule to not repartition if the CSV file is compressed
   Testing - Added `CsvExec` case along with the existing tests for optimizing rule `Repartition` on `ParquetExec`
   ### Step 2
   Parallel Parquet PR also has done this but inside `ParquetExec`, now the repartition byte range logic is refactored to somewhere else to let `CsvExec` reuse it.
   Testing - Unit test for partitioning byte range has also been well covered by the parallel Parquet PR https://github.com/apache/arrow-datafusion/blob/e91af991c5ae4a6b4afab2cb1b0c9307a69e4046/datafusion/core/src/datasource/physical_plan/parquet.rs#L1924-L2128
   ### Step 3
   The logic for handling line boundaries correctly is done in `CsvOpener`, the rule used is exactly the same as https://github.com/apache/arrow-datafusion/issues/6325 mentioned. Unlike parallel Parquet scan, which can use metadata to decide which row groups to read according to the approximate byte range, CSV scan needs to inspect the file content around partition boundaries to determine the byte range of lines in this partition. In the implementation, it finds the offset to the first newline encountered from the approximate byte partition start or end, calculates the byte range for complete lines of this partition, and reads that actual byte range from the object store.
   Testing - Added some integration tests in `file_format/csv.rs` (also manually run these tests on S3). For more complex query tests, the existing TPCH correctness test under sqllogictest is scanned on CSV files with 4 partitions.
   Some issue:
   1. Range get not working for local filesystem https://github.com/apache/arrow-rs/blob/0d4e6a727f113f42d58650d2dbecab89b22d4e28/object_store/src/lib.rs#L355, need to update implementation after it's fixed
   2. Need 3 get requests to object store for each partition (find head offset, find tail offset, and finally actually get the correct byte range for lines) It's easier to do this way but 3 * `target_partitions` requests on cloud stores(billed by number of requests) might be a problem. This may be improved by some follow on PR, but I haven't come up with a good solution yet, arrow CSV reader now only can handle valid CSV files. Maybe add a wrapper on the byte stream fetched from the object store, and let it skip the first line and read until the first newline after the range length?
   <!--
   There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
   -->
   
   # Are these changes tested?
   See above section.
   A very simple benchmark: scan TPC-H lineitem table (SF1) with very selective predicate (`select * from lineitem where column_1 = 1;`). 6 is # of physical cores for my machine
   ```
   1 partitions: 54.127 s
   2 partitions: 27.176 s
   3 partitions: 20.532 s
   4 partitions: 16.147 s
   5 partitions: 15.061 s
   6 partitions: 13.396 s
   ```
   <!--
   We typically require tests for all PRs in order to:
   1. Prevent the code from being accidentally broken by subsequent changes
   3. Serve as another way to document the expected behavior of the code
   
   If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
   -->
   
   # Are there any user-facing changes?
   No
   <!--
   If there are user-facing changes then we may require documentation to be updated before approving the PR.
   -->
   
   <!--
   If there are any breaking changes to public APIs, please add the `api change` label.
   -->


-- 
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@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "marvinlanhenke (via GitHub)" <gi...@apache.org>.
marvinlanhenke commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437135508


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   > # Alternate idea
   > Another approach that would reduce the number of object store requests would be to read past the initial range and stop at the next newline `\n` like this:
   > 
   > ```
   >   Each partition reads *more* than its assigned ranged to find                     
   >   the trailing new line, and ignores everything afterwards                         
   >                                                                                    
   >                                                                                    
   > ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                          
   > ┌─────────────┬──┬───────┼────────────┬──┬────────────────┬──┬────────┬──┬────────┐
   > │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   > └─────────────┴──┴───────┼────────────┴──┴────────────────┴──┴────────┴──┴────────┘
   > │                                                                                  
   >  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘                                                         
   >   Partition 0                                                                      
   >   Read                                                                             
   > ```
   > 
   > I think the tricky bit of this design would be to ensure enough extra data was read. Initially, maybe we could just pick something sufficiently large for most files, like 1MB and error if the next newline can't be found. As a follow on we could add some fanciness like make another object store request if necessary.
   
   @alamb 
   ...working on #8502; I noticed the same thing.
   
   So I did some testing.
   
   I issued just a single GetRequest to the object store with an extended end_range (factor 1.2); then looped over the result byte stream and computed the start and end offset in a single pass. 
   
   I benchmarked it against 60mil rows of NDJSON - with no difference compared to the other approach. I could not gain any performance. Maybe my implementation is to naive?
   
   ```rust
   let result = store.get_opts(location, options).await?;
   let mut result_stream = result.into_stream();
   
   let mut index = 0;
   let mut buffer = Bytes::new();
   let mut start_delta = 0;
   let mut end_delta = 0;
   
   'outer: loop {
       if buffer.is_empty() {
           match result_stream.next().await.transpose()? {
               Some(bytes) => buffer = bytes,
               None => break,
           }
       }
   
       for byte in &buffer {
           if *byte == b'\n' {
               if start != 0 && start_delta == 0 {
                   start_delta = index;
                   if end == file_size {
                       break 'outer;
                   }
               }
   
               if start + index > end {
                   end_delta = index;
                   break 'outer;
               }
           }
           index += 1;
       }
   
       buffer.clear();
   }
   ```
   



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on a diff in pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1257516647


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   These text charts look awesome 😮 How did you draw that?



##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   These text charts look awesome 😮 How did you draw that?



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1633027010

   Thanks @2010YOUY01  -- I took the liberty of merging up from main to resolve a conflict on this branch and I plan to merge it when the CI has passed


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1622256185

   Hi @2010YOUY01  -- I am having trouble reproducing the benchmark results you reported
   
   # Results
   Master:
   ```
   ❯ select count(*) from lineitem where l_quantity < 10;
   1 row in set. Query took 1.424 seconds.
   1 row in set. Query took 1.374 seconds.
   1 row in set. Query took 1.409 seconds.
   ```
   
   This PR branch:
   ```
   ❯ select count(*) from lineitem where l_quantity < 10;
   1 row in set. Query took 1.918 seconds.
   1 row in set. Query took 1.672 seconds.
   1 row in set. Query took 2.008 seconds.
   ```
   (I also merged up your branch from master and it still had the same performance)
   
   # Methodology:
   
   I tested this branch out using the TPCH SF1 (6M rows,  725 MB) lineitem CSV file (created with `arrow-datafusion/benchmarks$ ./bench.sh data tpch`):
   
   ```shell
   (arrow_dev) alamb@MacBook-Pro-8:~$ du -h  /Users/alamb/Software/arrow-datafusion/benchmarks/data/lineitem.tbl
   725M	/Users/alamb/Software/arrow-datafusion/benchmarks/data/lineitem.tbl
   
   (arrow_dev) alamb@MacBook-Pro-8:~$ wc -l /Users/alamb/Software/arrow-datafusion/benchmarks/data/lineitem.tbl
    6001215 /Users/alamb/Software/arrow-datafusion/benchmarks/data/lineitem.tbl
   ```
   
   And used `datafusion-cli` (built via `cargo build --release`)
   
   ```sql
   CREATE EXTERNAL TABLE lineitem (
           l_orderkey BIGINT,
           l_partkey BIGINT,
           l_suppkey BIGINT,
           l_linenumber INTEGER,
           l_quantity DECIMAL(15, 2),
           l_extendedprice DECIMAL(15, 2),
           l_discount DECIMAL(15, 2),
           l_tax DECIMAL(15, 2),
           l_returnflag VARCHAR,
           l_linestatus VARCHAR,
           l_shipdate DATE,
           l_commitdate DATE,
           l_receiptdate DATE,
           l_shipinstruct VARCHAR,
           l_shipmode VARCHAR,
           l_comment VARCHAR,
           l_rev VARCHAR,
   ) STORED AS CSV DELIMITER '|' LOCATION '/Users/alamb/Software/arrow-datafusion/benchmarks/data/lineitem.tbl';
   
   --- Run a query that scans the entire CSV
   select count(*) from lineitem where l_quantity < 10;
   
   +-----------------+
   | COUNT(UInt8(1)) |
   +-----------------+
   | 1079240         |
   +-----------------+
   ```
   
   
   
   
   


-- 
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@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437852730


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   > I benchmarked it against 60mil rows of NDJSON - with no difference compared to the other approach. I could not gain any performance. Maybe my implementation is to naive? Or the overhead for the object store requests is to small when working with the local Filesystem?
   
   Yes, I think this is the fundamental observation -- multiple requests to an actual remote object store is quite costly (like 10s of ms minimum) and fetching anything less than several MB in one request is likely less efficient than a single large request.
   
   There is more about object storage in  [Exploiting Cloud Object Storage for High-Performance Analytics](https://www.vldb.org/pvldb/vol16/p2769-durner.pdf) : VLDB 2023 paper about running high performance analytics in object stores.



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1627433092

   Thanks @2010YOUY01  -- I am starting to look at this 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: github-unsubscribe@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437877573


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   Sounds like a good plan to me



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1616635601

   I started running some tests with this branch. I will continue tomorrow


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1627778667

   memo for myself: update comments/docs in configurations


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb merged pull request #6801: parallel csv scan

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


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1627777282

   > Thank you @2010YOUY01 -- I tried this out again and it does indeed go (much!) faster -- 3x faster in my initial testing. 👏
   
   Thank you for the review ❤️  I will update this PR as per the comments next week


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1615138360

   Thank you @2010YOUY01  -- I will review this over the coming days. This looks awesoem


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1619054772

   This is on my list to review, but I might not have time for it until later in the week (Wednesday) -- I am somewhat occupied with #6800  at the moment


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1249472774


##########
datafusion/core/Cargo.toml:
##########
@@ -84,6 +84,7 @@ parquet = { workspace = true }
 percent-encoding = "2.2.0"
 pin-project-lite = "^0.2.7"
 rand = "0.8"
+regex = "1.5.4"

Review Comment:
   since this is only used for tests, I think it can be put in the `dev-dependencies` section



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on a diff in pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1253778743


##########
datafusion/core/src/datasource/physical_plan/mod.rs:
##########
@@ -240,6 +242,81 @@ impl FileScanConfig {
                 .collect()
         })
     }
+
+    /// Repartition all input files into `target_partitions` partitions, if total file size exceed
+    /// `repartition_file_min_size`
+    /// `target_partitions` and `repartition_file_min_size` directly come from configuration.
+    ///
+    /// This function only try to partition file byte range evenly, and let specific `FileOpener` to
+    /// do actual partition on specific data source type. (e.g. `CsvOpener` will only read lines
+    /// overlap with byte range but also handle boundaries to ensure all lines will be read exactly once)
+    pub fn repartition_file_groups(
+        file_groups: Vec<Vec<PartitionedFile>>,
+        target_partitions: usize,
+        repartition_file_min_size: usize,
+    ) -> Option<Vec<Vec<PartitionedFile>>> {
+        let flattened_files = file_groups.iter().flatten().collect::<Vec<_>>();
+
+        // Perform redistribution only in case all files should be read from beginning to end
+        let has_ranges = flattened_files.iter().any(|f| f.range.is_some());
+        if has_ranges {
+            return None;
+        }
+
+        let total_size = flattened_files
+            .iter()
+            .map(|f| f.object_meta.size as i64)
+            .sum::<i64>();
+        if total_size < (repartition_file_min_size as i64) || total_size == 0 {
+            return None;
+        }
+
+        let target_partition_size =
+            (total_size as usize + (target_partitions) - 1) / (target_partitions);
+
+        let current_partition_index: usize = 0;
+        let current_partition_size: usize = 0;
+
+        // Partition byte range evenly for all `PartitionedFile`s
+        let repartitioned_files = flattened_files

Review Comment:
   Yes. For now, the physical optimizer will check that, and won't get compressed CSV files repartitioned.



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1622714624

   > Hi @2010YOUY01 -- I am having trouble reproducing the benchmark results you reported
   
   @alamb Thank you for the feedback!
   My initial benchmark run the query under different `target_partition`, just realized that was not effective 😰 
   I reproduced your benchmark. Since streaming byte range get on local FS is not implemented in Arrow yet, 
   >Some issue:
   >1. Range get not working for local filesystem https://github.com/apache/arrow-rs/blob/0d4e6a727f113f42d58650d2dbecab89b22d4e28/object_store/src/lib.rs#L355, need to update implementation after it's fixed
   
   alternative `get_range()` is used (which will copy the range into memory at once instead of in a streaming fashion). It is called when finding the first newline after the start/end of each partition, and multiple unnecessary large disk read caused the performance issue.
   This should be solved after `get_opts()` - `Range` option is supported for local FS. For now, I suppressed this issue with a preset max line length, and re-run the benchmark again:
   This PR:
   ```
   ❯ select count(*) from lineitem where l_quantity < 10;
   1 row in set. Query took 0.894 seconds.
   1 row in set. Query took 0.513 seconds.
   1 row in set. Query took 0.532 seconds.
   ```
   Main branch:
   ```
   ❯ select count(*) from lineitem where l_quantity < 10;
   1 row in set. Query took 1.757 seconds.
   1 row in set. Query took 1.496 seconds.
   1 row in set. Query took 1.498 seconds.
   ```
   


-- 
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@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "marvinlanhenke (via GitHub)" <gi...@apache.org>.
marvinlanhenke commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437135508


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   > # Alternate idea
   > Another approach that would reduce the number of object store requests would be to read past the initial range and stop at the next newline `\n` like this:
   > 
   > ```
   >   Each partition reads *more* than its assigned ranged to find                     
   >   the trailing new line, and ignores everything afterwards                         
   >                                                                                    
   >                                                                                    
   > ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                          
   > ┌─────────────┬──┬───────┼────────────┬──┬────────────────┬──┬────────┬──┬────────┐
   > │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   > └─────────────┴──┴───────┼────────────┴──┴────────────────┴──┴────────┴──┴────────┘
   > │                                                                                  
   >  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘                                                         
   >   Partition 0                                                                      
   >   Read                                                                             
   > ```
   > 
   > I think the tricky bit of this design would be to ensure enough extra data was read. Initially, maybe we could just pick something sufficiently large for most files, like 1MB and error if the next newline can't be found. As a follow on we could add some fanciness like make another object store request if necessary.
   
   @alamb 
   ...working on #8502; I noticed the same thing.
   
   So I did some testing.
   
   I issued just a single GetRequest to the object store with an extended end_range (factor 1.2); then looped over the result byte stream and computed the start and end offset in a single pass. 
   
   I benchmarked it against 60mil rows of NDJSON - with no difference compared to the other approach. I could not gain any performance. Maybe my implementation is to naive? Or the overhead for the object store requests is to small when working with the local Filesystem? 
   
   ```rust
   let result = store.get_opts(location, options).await?;
   let mut result_stream = result.into_stream();
   
   let mut index = 0;
   let mut buffer = Bytes::new();
   let mut start_delta = 0;
   let mut end_delta = 0;
   
   'outer: loop {
       if buffer.is_empty() {
           match result_stream.next().await.transpose()? {
               Some(bytes) => buffer = bytes,
               None => break,
           }
       }
   
       for byte in &buffer {
           if *byte == b'\n' {
               if start != 0 && start_delta == 0 {
                   start_delta = index;
                   if end == file_size {
                       break 'outer;
                   }
               }
   
               if start + index > end {
                   end_delta = index;
                   break 'outer;
               }
           }
           index += 1;
       }
   
       buffer.clear();
   }
   ```
   



-- 
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@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "marvinlanhenke (via GitHub)" <gi...@apache.org>.
marvinlanhenke commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437135508


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   > # Alternate idea
   > Another approach that would reduce the number of object store requests would be to read past the initial range and stop at the next newline `\n` like this:
   > 
   > ```
   >   Each partition reads *more* than its assigned ranged to find                     
   >   the trailing new line, and ignores everything afterwards                         
   >                                                                                    
   >                                                                                    
   > ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                          
   > ┌─────────────┬──┬───────┼────────────┬──┬────────────────┬──┬────────┬──┬────────┐
   > │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   > └─────────────┴──┴───────┼────────────┴──┴────────────────┴──┴────────┴──┴────────┘
   > │                                                                                  
   >  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘                                                         
   >   Partition 0                                                                      
   >   Read                                                                             
   > ```
   > 
   > I think the tricky bit of this design would be to ensure enough extra data was read. Initially, maybe we could just pick something sufficiently large for most files, like 1MB and error if the next newline can't be found. As a follow on we could add some fanciness like make another object store request if necessary.
   
   @alamb 
   ...working on #8502; I noticed the same thing - so am I right; that this "issue" is yet to be resolved? 
   
   One could benchmark the different approaches (this PR vs. alternative Idea); I like the idea of picking a "sufficient large enough range at the beginning" and trying to recover with an additional object_store request. 
   



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] 2010YOUY01 commented on pull request #6801: parallel csv scan

Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1631678169

   Previous review comments should be all addressed in recent commits, it's ready for review now.
   Also filed an issue for the remaining tasks related to this PR.


-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1257458470


##########
datafusion/core/src/datasource/file_format/csv.rs:
##########
@@ -925,4 +931,365 @@ mod tests {
         );
         Ok(())
     }
+
+    /// Explain the `sql` query under `ctx` to make sure the underlying csv scan is parallelized
+    /// e.g. "CsvExec: file_groups={2 groups:" in plan means 2 CsvExec runs concurrently
+    async fn count_query_csv_partitions(
+        ctx: &SessionContext,
+        sql: &str,
+    ) -> Result<usize> {
+        let df = ctx.sql(&format!("EXPLAIN {sql}")).await?;
+        let result = df.collect().await?;
+        let plan = format!("{}", &pretty::pretty_format_batches(&result)?);
+
+        let re = Regex::new(r"CsvExec: file_groups=\{(\d+) group").unwrap();
+
+        if let Some(captures) = re.captures(&plan) {
+            if let Some(match_) = captures.get(1) {
+                let n_partitions = match_.as_str().parse::<usize>().unwrap();
+                return Ok(n_partitions);
+            }
+        }
+
+        Err(DataFusionError::Internal(
+            "query contains no CsvExec".to_string(),
+        ))
+    }
+
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_basic(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let testdata = arrow_test_data();
+        ctx.register_csv(
+            "aggr",
+            &format!("{testdata}/csv/aggregate_test_100.csv"),
+            CsvReadOptions::new().has_header(true),
+        )
+        .await?;
+
+        let query = "select sum(c2) from aggr;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+--------------+",
+            "| SUM(aggr.c2) |",
+            "+--------------+",
+            "| 285          |",
+            "+--------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions);
+
+        Ok(())
+    }
+
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_compressed(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let csv_options = CsvReadOptions::default()
+            .has_header(true)
+            .file_compression_type(FileCompressionType::GZIP)
+            .file_extension("csv.gz");
+        let ctx = SessionContext::with_config(config);
+        let testdata = arrow_test_data();
+        ctx.register_csv(
+            "aggr",
+            &format!("{testdata}/csv/aggregate_test_100.csv.gz"),
+            csv_options,
+        )
+        .await?;
+
+        let query = "select sum(c3) from aggr;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+--------------+",
+            "| SUM(aggr.c3) |",
+            "+--------------+",
+            "| 781          |",
+            "+--------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Compressed csv won't be scanned in parallel
+
+        Ok(())
+    }
+
+    /// Read a single empty csv file in parallel
+    ///
+    /// empty_0_byte.csv:
+    /// (file is empty)
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_empty_file(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        ctx.register_csv(
+            "empty",
+            "tests/data/empty_0_byte.csv",
+            CsvReadOptions::new().has_header(false),
+        )
+        .await?;
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Read a single empty csv file with header in parallel
+    ///
+    /// empty.csv:
+    /// c1,c2,c3
+    #[rstest(n_partitions, case(1), case(2), case(3))]
+    #[tokio::test]
+    async fn test_csv_parallel_empty_with_header(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        ctx.register_csv(
+            "empty",
+            "tests/data/empty.csv",
+            CsvReadOptions::new().has_header(true),
+        )
+        .await?;
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions);
+
+        Ok(())
+    }
+
+    /// Read multiple empty csv files in parallel
+    ///
+    /// all_empty
+    /// ├── empty0.csv
+    /// ├── empty1.csv
+    /// └── empty2.csv
+    ///
+    /// empty0.csv/empty1.csv/empty2.csv:
+    /// (file is empty)
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_multiple_empty_files(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let file_format = CsvFormat::default().with_has_header(false);
+        let listing_options = ListingOptions::new(Arc::new(file_format))
+            .with_file_extension(FileType::CSV.get_ext());
+        ctx.register_listing_table(
+            "empty",
+            "tests/data/empty_files/all_empty/",
+            listing_options,
+            None,
+            None,
+        )
+        .await
+        .unwrap();
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Read multiple csv files (some are empty) in parallel
+    ///
+    /// some_empty
+    /// ├── a_empty.csv
+    /// ├── b.csv
+    /// ├── c_empty.csv
+    /// ├── d.csv
+    /// └── e_empty.csv
+    ///
+    /// a_empty.csv/c_empty.csv/e_empty.csv:
+    /// (file is empty)
+    ///
+    /// b.csv/d.csv:
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_some_file_empty(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let file_format = CsvFormat::default().with_has_header(false);
+        let listing_options = ListingOptions::new(Arc::new(file_format))
+            .with_file_extension(FileType::CSV.get_ext());
+        ctx.register_listing_table(
+            "empty",
+            "tests/data/empty_files/some_empty",
+            listing_options,
+            None,
+            None,
+        )
+        .await
+        .unwrap();
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select sum(column_1) from empty where column_1 > 0;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+---------------------+",
+            "| SUM(empty.column_1) |",
+            "+---------------------+",
+            "| 10                  |",
+            "+---------------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Parappel scan on a csv file with only 1 byte in each line
+    /// Testing partition byte range land on line boundaries
+    ///
+    /// one_col.csv:
+    /// 5\n
+    /// 5\n
+    /// (...10 rows total)
+    #[rstest(n_partitions, case(1), case(2), case(3), case(5), case(10), case(32))]
+    #[tokio::test]
+    async fn test_csv_parallel_one_col(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+
+        ctx.register_csv(
+            "one_col",
+            "tests/data/one_col.csv",
+            CsvReadOptions::new().has_header(false),
+        )
+        .await?;
+
+        let query = "select sum(column_1) from one_col where column_1 > 0;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+-----------------------+",
+            "| SUM(one_col.column_1) |",
+            "+-----------------------+",
+            "| 50                    |",
+            "+-----------------------+",
+        ];
+        let file_size = if cfg!(target_os = "windows") {
+            30 // new line on Win is '\r\n'
+        } else {
+            20
+        };
+        // A 20-Byte file at most get partitioned into 20 chunks
+        let expected_partitions = if n_partitions <= file_size {
+            n_partitions
+        } else {
+            file_size
+        };
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(expected_partitions, actual_partitions);
+
+        Ok(())
+    }
+
+    /// Parappel scan on a csv file with 2 wide rows

Review Comment:
   ```suggestion
       /// Parallel scan on a csv file with 2 wide rows
   ```



##########
datafusion/core/src/datasource/physical_plan/parquet.rs:
##########
@@ -253,75 +244,23 @@ impl ParquetExec {
     }
 
     /// Redistribute files across partitions according to their size
+    /// See comments on `get_file_groups_repartitioned()` for more detail.
     pub fn get_repartitioned(
         &self,
         target_partitions: usize,
         repartition_file_min_size: usize,
     ) -> Self {
-        let flattened_files = self
-            .base_config()
-            .file_groups
-            .iter()
-            .flatten()
-            .collect::<Vec<_>>();
-
-        // Perform redistribution only in case all files should be read from beginning to end
-        let has_ranges = flattened_files.iter().any(|f| f.range.is_some());
-        if has_ranges {
-            return self.clone();
-        }
+        let repartitioned_file_groups_option = FileScanConfig::repartition_file_groups(

Review Comment:
   👍 for this refactor



##########
datafusion/core/tests/sqllogictests/test_files/tpch/q1.slt.part:
##########
@@ -57,9 +57,7 @@ SortPreservingMergeExec: [l_returnflag@0 ASC NULLS LAST,l_linestatus@1 ASC NULLS
 --------------ProjectionExec: expr=[l_extendedprice@1 * (Some(1),20,0 - l_discount@2) as lineitem.l_extendedprice * (Decimal128(Some(1),20,0) - lineitem.l_discount)Decimal128(Some(1),20,0) - lineitem.l_discountlineitem.l_discountDecimal128(Some(1),20,0)lineitem.l_extendedprice, l_quantity@0 as l_quantity, l_extendedprice@1 as l_extendedprice, l_discount@2 as l_discount, l_tax@3 as l_tax, l_returnflag@4 as l_returnflag, l_linestatus@5 as l_linestatus]
 ----------------CoalesceBatchesExec: target_batch_size=8192
 ------------------FilterExec: l_shipdate@6 <= 10471
---------------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
-----------------------CsvExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl]]}, projection=[l_quantity, l_extendedprice, l_discount, l_tax, l_returnflag, l_linestatus, l_shipdate], has_header=false
-
+--------------------CsvExec: file_groups={4 groups: [[WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:0..18561749], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:18561749..37123498], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:37123498..55685247], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:55685247..74246996]]}, projection=[l_quantity, l_extendedprice, l_discount, l_tax, l_returnflag, l_linestatus, l_shipdate], has_header=false

Review Comment:
   ❤️ 



##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   As I understand it, this code does potentially several object store requests to adjust the initial ranges based on where the end of the CSV lines actually fall:
   
   # Initial situation
   ```
   CSV data with the next newlines (\n) after range marked                             
                                                                                       
    ┌─────────────┬──┬────────────────────┬──┬────────────────┬──┬────────┬──┬────────┐
    │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
    └─────────────┴──┴────────────────────┴──┴────────────────┴──┴────────┴──┴────────┘
           ▲                    ▲                     ▲               ▲                
           └─────────────┬──────┴─────────────────────┴───────────────┘                
                         │                                                             
                         │                                                             
                Initial file_meta.range es                                             
   ```
   
   # This PR
   ```
       This PR: adjust the ranges prior to IO start, via                                
     object store operations                                                          
                                                                                      
   ┌ ─ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 
   ┌─────────────┬──┼────────────────────┬──┬────────────────┬──┬────────┬──┬────────┤
   │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   └─────────────┴──┼────────────────────┴──┴────────────────┴──┴────────┴──┴────────┤
   │                │                       │                   │                     
    ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
                                                                                      
    Partition 0       Partition 1            Partition 2       Partition 3            
    Read              Read                   Read              Read                   
   ```
   
   This design has the nice property that each partition reads exactly the bytes it needs
   
   This design has the downside that it requires several object store reads to find the newlines, and the overhead of each object store operation often is much larger than the overhead of reading extra data. 
   
   # Alternate idea
   
   Another approach that would reduce the number of object store requests would be to read past the initial range and stop at the next newline `\n` like this:
   
   ```
     Each partition reads *more* than its assigned ranged to find                     
     the trailing new line, and ignores everything afterwards                         
                                                                                      
                                                                                      
   ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                          
   ┌─────────────┬──┬───────┼────────────┬──┬────────────────┬──┬────────┬──┬────────┐
   │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   └─────────────┴──┴───────┼────────────┴──┴────────────────┴──┴────────┴──┴────────┘
   │                                                                                  
    ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘                                                         
     Partition 0                                                                      
     Read                                                                             
   ```
   
   I think the tricky bit of this design would be to ensure enough extra data was read. Initially, maybe we could just pick something sufficiently large for most files, like 1MB and error if the next newline can't be found. As a follow on we could add some fanciness like make another object store request if necessary.



##########
datafusion/core/src/datasource/physical_plan/parquet.rs:
##########
@@ -253,75 +244,23 @@ impl ParquetExec {
     }
 
     /// Redistribute files across partitions according to their size
+    /// See comments on `get_file_groups_repartitioned()` for more detail.
     pub fn get_repartitioned(
         &self,
         target_partitions: usize,
         repartition_file_min_size: usize,
     ) -> Self {
-        let flattened_files = self
-            .base_config()
-            .file_groups
-            .iter()
-            .flatten()
-            .collect::<Vec<_>>();
-
-        // Perform redistribution only in case all files should be read from beginning to end
-        let has_ranges = flattened_files.iter().any(|f| f.range.is_some());
-        if has_ranges {
-            return self.clone();
-        }
+        let repartitioned_file_groups_option = FileScanConfig::repartition_file_groups(

Review Comment:
   👍 for this refactor



##########
datafusion/core/tests/sqllogictests/test_files/tpch/q1.slt.part:
##########
@@ -57,9 +57,7 @@ SortPreservingMergeExec: [l_returnflag@0 ASC NULLS LAST,l_linestatus@1 ASC NULLS
 --------------ProjectionExec: expr=[l_extendedprice@1 * (Some(1),20,0 - l_discount@2) as lineitem.l_extendedprice * (Decimal128(Some(1),20,0) - lineitem.l_discount)Decimal128(Some(1),20,0) - lineitem.l_discountlineitem.l_discountDecimal128(Some(1),20,0)lineitem.l_extendedprice, l_quantity@0 as l_quantity, l_extendedprice@1 as l_extendedprice, l_discount@2 as l_discount, l_tax@3 as l_tax, l_returnflag@4 as l_returnflag, l_linestatus@5 as l_linestatus]
 ----------------CoalesceBatchesExec: target_batch_size=8192
 ------------------FilterExec: l_shipdate@6 <= 10471
---------------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
-----------------------CsvExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl]]}, projection=[l_quantity, l_extendedprice, l_discount, l_tax, l_returnflag, l_linestatus, l_shipdate], has_header=false
-
+--------------------CsvExec: file_groups={4 groups: [[WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:0..18561749], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:18561749..37123498], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:37123498..55685247], [WORKSPACE_ROOT/datafusion/core/tests/sqllogictests/test_files/tpch/data/lineitem.tbl:55685247..74246996]]}, projection=[l_quantity, l_extendedprice, l_discount, l_tax, l_returnflag, l_linestatus, l_shipdate], has_header=false

Review Comment:
   ❤️ 



##########
datafusion/core/src/datasource/physical_plan/parquet.rs:
##########
@@ -1921,6 +1861,103 @@ mod tests {
         assert_eq!(predicate.unwrap().to_string(), filter_phys.to_string());
     }
 
+    /// Empty file won't get partitioned
+    #[tokio::test]
+    async fn parquet_exec_repartition_empty_file_only() {
+        let partitioned_file_empty = PartitionedFile::new("empty".to_string(), 0);
+        let file_group = vec![vec![partitioned_file_empty]];
+
+        let parquet_exec = ParquetExec::new(
+            FileScanConfig {
+                object_store_url: ObjectStoreUrl::local_filesystem(),
+                file_groups: file_group,
+                file_schema: Arc::new(Schema::empty()),
+                statistics: Statistics::default(),
+                projection: None,
+                limit: None,
+                table_partition_cols: vec![],
+                output_ordering: vec![],
+                infinite_source: false,
+            },
+            None,
+            None,
+        );
+
+        let partitioned_file = parquet_exec
+            .get_repartitioned(4, 0)
+            .base_config()
+            .file_groups
+            .clone();
+
+        assert!(partitioned_file[0][0].range.is_none());
+    }
+
+    // Repartition when there is a empty file in file groups
+    #[tokio::test]
+    async fn parquet_exec_repartition_empty_files() {

Review Comment:
   maybe as a follow on the tests for file repartitioning could be moved to datafusion/core/src/datasource/physical_plan/mod.rs to be in the same module they are testing (as they are now no longer specific to parquet)



##########
datafusion/core/src/physical_optimizer/repartition.rs:
##########
@@ -257,6 +257,17 @@ fn optimize_partitions(
         }
     }
 
+    if let Some(csv_exec) = new_plan.as_any().downcast_ref::<CsvExec>() {
+        // The underlying CsvOpener will only fetch certain part of csv file from the object store, which can't be decompressed separately
+        if repartition_file_scans && !csv_exec.file_compression_type.is_compressed() {
+            let repartitioned_exec_option =
+                csv_exec.get_repartitioned(target_partitions, repartition_file_min_size);
+            if let Some(repartitioned_exec) = repartitioned_exec_option {
+                return Ok(Transformed::Yes(Arc::new(repartitioned_exec)));
+            }

Review Comment:
   I recommend moving the check for compression `csv_exec.file_compression_type.is_compressed()` into `CsvExec::get_repartitioned()` to keep the logic for handling CSV files together. I don't think this is required however.
   
   ```suggestion
           if repartition_file_scans  {
               let repartitioned_exec_option =
                   csv_exec.get_repartitioned(target_partitions, repartition_file_min_size);
               if let Some(repartitioned_exec) = repartitioned_exec_option {
                   return Ok(Transformed::Yes(Arc::new(repartitioned_exec)));
               }
   ```



##########
datafusion/core/src/datasource/file_format/csv.rs:
##########
@@ -925,4 +931,365 @@ mod tests {
         );
         Ok(())
     }
+
+    /// Explain the `sql` query under `ctx` to make sure the underlying csv scan is parallelized
+    /// e.g. "CsvExec: file_groups={2 groups:" in plan means 2 CsvExec runs concurrently
+    async fn count_query_csv_partitions(
+        ctx: &SessionContext,
+        sql: &str,
+    ) -> Result<usize> {
+        let df = ctx.sql(&format!("EXPLAIN {sql}")).await?;
+        let result = df.collect().await?;
+        let plan = format!("{}", &pretty::pretty_format_batches(&result)?);
+
+        let re = Regex::new(r"CsvExec: file_groups=\{(\d+) group").unwrap();
+
+        if let Some(captures) = re.captures(&plan) {
+            if let Some(match_) = captures.get(1) {
+                let n_partitions = match_.as_str().parse::<usize>().unwrap();
+                return Ok(n_partitions);
+            }
+        }
+
+        Err(DataFusionError::Internal(
+            "query contains no CsvExec".to_string(),
+        ))
+    }
+
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_basic(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let testdata = arrow_test_data();
+        ctx.register_csv(
+            "aggr",
+            &format!("{testdata}/csv/aggregate_test_100.csv"),
+            CsvReadOptions::new().has_header(true),
+        )
+        .await?;
+
+        let query = "select sum(c2) from aggr;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+--------------+",
+            "| SUM(aggr.c2) |",
+            "+--------------+",
+            "| 285          |",
+            "+--------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions);
+
+        Ok(())
+    }
+
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_compressed(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let csv_options = CsvReadOptions::default()
+            .has_header(true)
+            .file_compression_type(FileCompressionType::GZIP)
+            .file_extension("csv.gz");
+        let ctx = SessionContext::with_config(config);
+        let testdata = arrow_test_data();
+        ctx.register_csv(
+            "aggr",
+            &format!("{testdata}/csv/aggregate_test_100.csv.gz"),
+            csv_options,
+        )
+        .await?;
+
+        let query = "select sum(c3) from aggr;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+--------------+",
+            "| SUM(aggr.c3) |",
+            "+--------------+",
+            "| 781          |",
+            "+--------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Compressed csv won't be scanned in parallel
+
+        Ok(())
+    }
+
+    /// Read a single empty csv file in parallel
+    ///
+    /// empty_0_byte.csv:
+    /// (file is empty)
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_empty_file(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        ctx.register_csv(
+            "empty",
+            "tests/data/empty_0_byte.csv",
+            CsvReadOptions::new().has_header(false),
+        )
+        .await?;
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Read a single empty csv file with header in parallel
+    ///
+    /// empty.csv:
+    /// c1,c2,c3
+    #[rstest(n_partitions, case(1), case(2), case(3))]
+    #[tokio::test]
+    async fn test_csv_parallel_empty_with_header(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        ctx.register_csv(
+            "empty",
+            "tests/data/empty.csv",
+            CsvReadOptions::new().has_header(true),
+        )
+        .await?;
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions);
+
+        Ok(())
+    }
+
+    /// Read multiple empty csv files in parallel
+    ///
+    /// all_empty
+    /// ├── empty0.csv
+    /// ├── empty1.csv
+    /// └── empty2.csv
+    ///
+    /// empty0.csv/empty1.csv/empty2.csv:
+    /// (file is empty)
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_multiple_empty_files(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let file_format = CsvFormat::default().with_has_header(false);
+        let listing_options = ListingOptions::new(Arc::new(file_format))
+            .with_file_extension(FileType::CSV.get_ext());
+        ctx.register_listing_table(
+            "empty",
+            "tests/data/empty_files/all_empty/",
+            listing_options,
+            None,
+            None,
+        )
+        .await
+        .unwrap();
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select * from empty where random() > 0.5;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "++",
+            "++",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(1, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Read multiple csv files (some are empty) in parallel
+    ///
+    /// some_empty
+    /// ├── a_empty.csv
+    /// ├── b.csv
+    /// ├── c_empty.csv
+    /// ├── d.csv
+    /// └── e_empty.csv
+    ///
+    /// a_empty.csv/c_empty.csv/e_empty.csv:
+    /// (file is empty)
+    ///
+    /// b.csv/d.csv:
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    /// 1\n
+    #[rstest(n_partitions, case(1), case(2), case(3), case(4))]
+    #[tokio::test]
+    async fn test_csv_parallel_some_file_empty(n_partitions: usize) -> Result<()> {
+        let config = SessionConfig::new()
+            .with_repartition_file_scans(true)
+            .with_repartition_file_min_size(0)
+            .with_target_partitions(n_partitions);
+        let ctx = SessionContext::with_config(config);
+        let file_format = CsvFormat::default().with_has_header(false);
+        let listing_options = ListingOptions::new(Arc::new(file_format))
+            .with_file_extension(FileType::CSV.get_ext());
+        ctx.register_listing_table(
+            "empty",
+            "tests/data/empty_files/some_empty",
+            listing_options,
+            None,
+            None,
+        )
+        .await
+        .unwrap();
+
+        // Require a predicate to enable repartition for the optimizer
+        let query = "select sum(column_1) from empty where column_1 > 0;";
+        let query_result = ctx.sql(query).await?.collect().await?;
+        let actual_partitions = count_query_csv_partitions(&ctx, query).await?;
+
+        #[rustfmt::skip]
+        let expected = vec![
+            "+---------------------+",
+            "| SUM(empty.column_1) |",
+            "+---------------------+",
+            "| 10                  |",
+            "+---------------------+",
+        ];
+        assert_batches_eq!(expected, &query_result);
+        assert_eq!(n_partitions, actual_partitions); // Won't get partitioned if all files are empty
+
+        Ok(())
+    }
+
+    /// Parappel scan on a csv file with only 1 byte in each line

Review Comment:
   ```suggestion
       /// Parallel scan on a csv file with only 1 byte in each line
   ```



##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   As I understand it, this code does potentially several object store requests to adjust the initial ranges based on where the end of the CSV lines actually fall:
   
   # Initial situation
   ```
   CSV data with the next newlines (\n) after range marked                             
                                                                                       
    ┌─────────────┬──┬────────────────────┬──┬────────────────┬──┬────────┬──┬────────┐
    │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
    └─────────────┴──┴────────────────────┴──┴────────────────┴──┴────────┴──┴────────┘
           ▲                    ▲                     ▲               ▲                
           └─────────────┬──────┴─────────────────────┴───────────────┘                
                         │                                                             
                         │                                                             
                Initial file_meta.range es                                             
   ```
   
   # This PR
   ```
       This PR: adjust the ranges prior to IO start, via                                
     object store operations                                                          
                                                                                      
   ┌ ─ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 
   ┌─────────────┬──┼────────────────────┬──┬────────────────┬──┬────────┬──┬────────┤
   │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   └─────────────┴──┼────────────────────┴──┴────────────────┴──┴────────┴──┴────────┤
   │                │                       │                   │                     
    ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
                                                                                      
    Partition 0       Partition 1            Partition 2       Partition 3            
    Read              Read                   Read              Read                   
   ```
   
   This design has the nice property that each partition reads exactly the bytes it needs
   
   This design has the downside that it requires several object store reads to find the newlines, and the overhead of each object store operation often is much larger than the overhead of reading extra data. 
   
   # Alternate idea
   
   Another approach that would reduce the number of object store requests would be to read past the initial range and stop at the next newline `\n` like this:
   
   ```
     Each partition reads *more* than its assigned ranged to find                     
     the trailing new line, and ignores everything afterwards                         
                                                                                      
                                                                                      
   ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                          
   ┌─────────────┬──┬───────┼────────────┬──┬────────────────┬──┬────────┬──┬────────┐
   │     ...     │\n│        ...         │\n│      ...       │\n│  ...   │\n│  ...   │
   └─────────────┴──┴───────┼────────────┴──┴────────────────┴──┴────────┴──┴────────┘
   │                                                                                  
    ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘                                                         
     Partition 0                                                                      
     Read                                                                             
   ```
   
   I think the tricky bit of this design would be to ensure enough extra data was read. Initially, maybe we could just pick something sufficiently large for most files, like 1MB and error if the next newline can't be found. As a follow on we could add some fanciness like make another object store request if necessary.



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1257562874


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   I use https://monodraw.helftone.com/ to make the ASCII art -- I haven't found a free alternative yet



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1253475065


##########
datafusion/core/src/datasource/physical_plan/mod.rs:
##########
@@ -240,6 +242,81 @@ impl FileScanConfig {
                 .collect()
         })
     }
+
+    /// Repartition all input files into `target_partitions` partitions, if total file size exceed
+    /// `repartition_file_min_size`
+    /// `target_partitions` and `repartition_file_min_size` directly come from configuration.
+    ///
+    /// This function only try to partition file byte range evenly, and let specific `FileOpener` to
+    /// do actual partition on specific data source type. (e.g. `CsvOpener` will only read lines
+    /// overlap with byte range but also handle boundaries to ensure all lines will be read exactly once)
+    pub fn repartition_file_groups(
+        file_groups: Vec<Vec<PartitionedFile>>,
+        target_partitions: usize,
+        repartition_file_min_size: usize,
+    ) -> Option<Vec<Vec<PartitionedFile>>> {
+        let flattened_files = file_groups.iter().flatten().collect::<Vec<_>>();
+
+        // Perform redistribution only in case all files should be read from beginning to end
+        let has_ranges = flattened_files.iter().any(|f| f.range.is_some());
+        if has_ranges {
+            return None;
+        }
+
+        let total_size = flattened_files
+            .iter()
+            .map(|f| f.object_meta.size as i64)
+            .sum::<i64>();
+        if total_size < (repartition_file_min_size as i64) || total_size == 0 {
+            return None;
+        }
+
+        let target_partition_size =
+            (total_size as usize + (target_partitions) - 1) / (target_partitions);
+
+        let current_partition_index: usize = 0;
+        let current_partition_size: usize = 0;
+
+        // Partition byte range evenly for all `PartitionedFile`s
+        let repartitioned_files = flattened_files

Review Comment:
   One thing I was thinking about for the range based approach is that it isn't likely to work for streaming compressed files (as you need to decompress the data linearly)
   
   I wonder if you have considered that 🤔 



-- 
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@arrow.apache.org

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


[GitHub] [arrow-datafusion] alamb commented on pull request #6801: parallel csv scan

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#issuecomment-1633111387

   Thanks again @2010YOUY01 


-- 
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@arrow.apache.org

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


Re: [PR] parallel csv scan [arrow-datafusion]

Posted by "marvinlanhenke (via GitHub)" <gi...@apache.org>.
marvinlanhenke commented on code in PR #6801:
URL: https://github.com/apache/arrow-datafusion/pull/6801#discussion_r1437870640


##########
datafusion/core/src/datasource/physical_plan/csv.rs:
##########
@@ -270,14 +297,223 @@ impl CsvOpener {
     }
 }
 
+/// Returns the position of the first newline in the byte stream, or the total length if no newline is found.
+fn find_first_newline_bytes<R: std::io::Read>(reader: &mut R) -> Result<usize> {
+    let mut buffer = [0; 1];
+    let mut index = 0;
+
+    loop {
+        let result = reader.read(&mut buffer);
+        match result {
+            Ok(n) => {
+                if n == 0 {
+                    return Ok(index); // End of file, no newline found
+                }
+                if buffer[0] == b'\n' {
+                    return Ok(index);
+                }
+                index += 1;
+            }
+            Err(e) => {
+                return Err(DataFusionError::IoError(e));
+            }
+        }
+    }
+}
+
+/// Returns the offset of the first newline in the object store range [start, end), or the end offset if no newline is found.
+async fn find_first_newline(
+    object_store: &Arc<dyn ObjectStore>,
+    location: &object_store::path::Path,
+    start_byte: usize,
+    end_byte: usize,
+) -> Result<usize> {
+    let options = GetOptions {
+        range: Some(Range {
+            start: start_byte,
+            end: end_byte,
+        }),
+        ..Default::default()
+    };
+
+    let offset = match object_store.get_opts(location, options).await? {
+        GetResult::File(_, _) => {
+            // Range currently is ignored for GetResult::File(...)
+            // Alternative get_range() will copy the whole range into memory, thus set a limit of
+            // max bytes to read to find the first newline
+            let max_line_length = 4096; // in bytes
+            let get_range_end_result = object_store
+                .get_range(
+                    location,
+                    Range {
+                        start: start_byte,
+                        end: std::cmp::min(start_byte + max_line_length, end_byte),
+                    },
+                )
+                .await;
+            let mut decoder_tail = Cursor::new(get_range_end_result?);
+            find_first_newline_bytes(&mut decoder_tail)?
+        }
+        GetResult::Stream(s) => {
+            let mut input = s.map_err(DataFusionError::from);
+            let mut buffered = Bytes::new();
+
+            let future_index = async move {
+                let mut index = 0;
+
+                loop {
+                    if buffered.is_empty() {
+                        match input.next().await {
+                            Some(Ok(b)) => buffered = b,
+                            Some(Err(e)) => return Err(e),
+                            None => return Ok(index),
+                        };
+                    }
+
+                    for byte in &buffered {
+                        if *byte == b'\n' {
+                            return Ok(index);
+                        }
+                        index += 1;
+                    }
+
+                    buffered.advance(buffered.len());
+                }
+            };
+            future_index.await?
+        }
+    };
+    Ok(offset)
+}
+
 impl FileOpener for CsvOpener {
+    /// Open a partitioned CSV file.
+    ///
+    /// If `file_meta.range` is `None`, the entire file is opened.
+    /// If `file_meta.range` is `Some(FileRange {start, end})`, this signifies that the partition
+    /// corresponds to the byte range [start, end) within the file.
+    ///
+    /// Note: `start` or `end` might be in the middle of some lines. In such cases, the following rules

Review Comment:
   @alamb
   Thanks for linking the paper.
   
   So I'll guess the alternate approach is still worth pursuing?
   
   I would proceed by testing the POC against a remote store and if this looks promising - I'd create a separate issue to discuss and refine the approach further?



-- 
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@arrow.apache.org

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