You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/01/26 18:04:45 UTC
[GitHub] [arrow-datafusion] alamb commented on a change in pull request #1687: Make `SortPreservingMergeStream` stable on input stream order
alamb commented on a change in pull request #1687:
URL: https://github.com/apache/arrow-datafusion/pull/1687#discussion_r792905067
##########
File path: datafusion/src/physical_plan/sorts/mod.rs
##########
@@ -160,7 +160,9 @@ impl SortKeyCursor {
}
}
- Ok(Ordering::Equal)
+ // Break ties using stream_idx to ensure a predictable
+ // ordering of rows when comparing equal streams.
+ Ok(self.stream_idx.cmp(&other.stream_idx))
Review comment:
This is the only code change. The rest is comments and tests
##########
File path: datafusion/src/physical_plan/sorts/sort_preserving_merge.rs
##########
@@ -1348,4 +1369,83 @@ mod tests {
Ok(())
}
+
+ #[tokio::test]
+ async fn test_stable_sort() {
+ let runtime = Arc::new(RuntimeEnv::default());
+
+ // Create record batches like:
+ // batch_number |value
+ // -------------+------
+ // 1 | A
+ // 1 | B
+ //
+ // Ensure that the output is in the same order the batches were fed
+ let partitions: Vec<Vec<RecordBatch>> = (0..10)
+ .map(|batch_number| {
+ let batch_number: Int32Array =
+ vec![Some(batch_number), Some(batch_number)]
+ .into_iter()
+ .collect();
+ let value: StringArray = vec![Some("A"), Some("B")].into_iter().collect();
+
+ let batch = RecordBatch::try_from_iter(vec![
+ ("batch_number", Arc::new(batch_number) as ArrayRef),
+ ("value", Arc::new(value) as ArrayRef),
+ ])
+ .unwrap();
+
+ vec![batch]
+ })
+ .collect();
+
+ let schema = partitions[0][0].schema();
+
+ let sort = vec![PhysicalSortExpr {
+ expr: col("value", &schema).unwrap(),
+ options: SortOptions {
+ descending: false,
+ nulls_first: true,
+ },
+ }];
+
+ let exec = MemoryExec::try_new(&partitions, schema, None).unwrap();
+ let merge = Arc::new(SortPreservingMergeExec::new(sort, Arc::new(exec)));
+
+ let collected = collect(merge, runtime).await.unwrap();
+ assert_eq!(collected.len(), 1);
+
+ // Expect the data to be sorted first by "batch_number" (because
+ // that was the order it was fed in, even though only "value"
+ // is in the sort key)
+ assert_batches_eq!(
Review comment:
Example test output before this fix:
```
[
"+--------------+-------+",
"| batch_number | value |",
"+--------------+-------+",
"| 0 | A |",
"| 2 | A |",
"| 6 | A |",
"| 9 | A |",
"| 5 | A |",
"| 1 | A |",
"| 4 | A |",
"| 3 | A |",
"| 8 | A |",
"| 7 | A |",
"| 0 | B |",
"| 6 | B |",
"| 8 | B |",
"| 7 | B |",
"| 4 | B |",
"| 2 | B |",
"| 1 | B |",
"| 3 | B |",
"| 9 | B |",
"| 5 | B |",
"+--------------+-------+",
]
```
--
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