You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "wiedld (via GitHub)" <gi...@apache.org> on 2023/10/11 21:55:22 UTC
[PR] feat(7181): add cursor slicing [arrow-datafusion]
wiedld opened a new pull request, #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798
## Which issue does this PR close?
Adds cursor slicing as a prerequisite for the cascading merge.
Part of #7181
## Rationale for this change
The need for a sliced cursor is [described here](https://github.com/apache/arrow-datafusion/blob/9b1019853fb3d71f6355ab1d850089332592b3d8/datafusion/physical-plan/src/sorts/batch_cursor.rs#L29-L37), in it's later use of partially yielded record batches.
## What changes are included in this PR?
* Arc around the Rows in RowCursor, so can arc clone on slice.
* define and impl `slice()` in Cursor interface
* test for primitive cursor
## Are these changes tested?
yes
Primitive cursor slicing is unit tested here.
Row cursor slicing is tested/used in the cascading merge.
## Are there any user-facing changes?
No. Cursor interface is crate private.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362672098
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
Review Comment:
But the logic below simply ignores the value of `self.offset`?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362679917
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
Review Comment:
I don't see an issue with slicing the underlying values, my observation is that the following will behave differently between RowCursor and FieldCursor
```
cursor.advance();
cursor.slice(1, 2);
```
In the case of `RowCursor` it will produce a slice that is offset by 2 from the start, whereas FieldCursor will produce one that is only offset by 1? I think...
It should just be a case of changing this method to use `self.offset + offset` instead of just `offset`
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1357207191
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Result<Self> {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Ok(Self {
+ values: values.slice(offset, length)?,
+ offset: 0,
+ null_threshold: *null_threshold,
Review Comment:
You are correct. In order to recalculate the null_threshold, we rely on methods from the original `FieldArray: Array` interface (not the inner `FieldValues`). Is there any reason not to keep the original `FieldArray`?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld closed pull request #7798: feat(7181): add cursor slicing
URL: https://github.com/apache/arrow-datafusion/pull/7798
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1356535464
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Result<Self> {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Ok(Self {
+ values: values.slice(offset, length)?,
+ offset: 0,
+ null_threshold: *null_threshold,
Review Comment:
Is this correct? I think this will shift the nulls out of alignment? Perhaps we could get a test of this?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1358375435
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
+ #[test]
+ fn test_slice_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // NULL == NULL
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // 2 > NULL
Review Comment:
```suggestion
// i32::MIN > NULL
```
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Self {
+ values: values.slice(offset, length),
+ offset: 0,
+ null_threshold: null_threshold.checked_sub(offset).unwrap_or(0),
Review Comment:
```suggestion
null_threshold: null_threshold.saturating_sub(offset),
```
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
+ #[test]
+ fn test_slice_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // NULL == NULL
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // 2 > NULL
+ a = a.slice(1, 1);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Greater);
+
+ // 2 < 3
+ b = b.slice(3, 1);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Less);
+ }
+
+ #[test]
+ fn test_slice_no_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: false,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // 2 < 3
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Less);
+
+ // 2 == 2
+ b = b.slice(1, 3);
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // NULL < 2
Review Comment:
The input arrays are
```
a: [2, i32::MIN, NULL]
b: [3, 2, i32::MIN, NULL]
```
We are comparing `a[1]` with `b[1]`, i.e. `i32::MIN` with `2`
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
+ #[test]
+ fn test_slice_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // NULL == NULL
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // 2 > NULL
+ a = a.slice(1, 1);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Greater);
+
+ // 2 < 3
Review Comment:
```suggestion
// i32::MIN < 2
```
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
+ #[test]
+ fn test_slice_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // NULL == NULL
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // 2 > NULL
+ a = a.slice(1, 1);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Greater);
+
+ // 2 < 3
+ b = b.slice(3, 1);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Less);
+ }
+
+ #[test]
+ fn test_slice_no_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: false,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // 2 < 3
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Less);
+
+ // 2 == 2
+ b = b.slice(1, 3);
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // NULL < 2
+ a = a.slice(1, 2);
+ assert_ne!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Less);
+
+ // NULL == NULL
Review Comment:
Similarly to above this is comparing `a[1]` with `b[2]`, i.e. `i32::MIN` with `i32::MIN`
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Self {
+ values: values.slice(offset, length),
+ offset: 0,
+ null_threshold: null_threshold.checked_sub(offset).unwrap_or(0),
Review Comment:
I would expect this logic to depend on the null ordering. In particular I would expect if nulls are first, to decrement by offset, and otherwise by `self.len - offset - length` or something...
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
Review Comment:
These tests are good, but I think it would be better if we got some tests with multiple nulls as well, to check that the nulls are being decremented appropriately, and not just floored to 0 :smile:
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1360039344
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
+ #[test]
+ fn test_slice_nulls_first() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![2, i32::MIN, 2]);
+ let mut a = new_primitive(options, buffer, 1);
+ let buffer = ScalarBuffer::from(vec![3, 2, i32::MIN, 2]);
+ let mut b = new_primitive(options, buffer, 1);
+
+ // NULL == NULL
+ assert_eq!(a, b);
+ assert_eq!(a.cmp(&b), Ordering::Equal);
+
+ // 2 > NULL
Review Comment:
Fixed the null mask to work properly. Explicit test cases pushed. Let me know if it's correct this time.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#issuecomment-1771208011
We changed the abstractions, and are now separating the Cursor from the CursorValues. After [this PR](https://github.com/apache/arrow-datafusion/pull/7855) merges, will add slicing to the CursorValues.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1357207191
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Result<Self> {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Ok(Self {
+ values: values.slice(offset, length)?,
+ offset: 0,
+ null_threshold: *null_threshold,
Review Comment:
You are correct. Fixing.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362636396
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ let null_threshold = match self.options.nulls_first {
+ true => null_threshold.saturating_sub(offset),
+ false => {
+ let shorter_len = self.values.len().saturating_sub(offset + length + 1);
+ null_threshold.saturating_sub(offset.saturating_sub(shorter_len))
Review Comment:
Now that I think about this more, I am unsure why `null_threshold.saturating_sub(offset)` is incorrect
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
Review Comment:
This seems at odds with the behaviour of RowCursor
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362643134
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
Review Comment:
What would happen if this method was simply
```
Self {
values: self.values.slice(0, self.offset + offset + length),
offset: self.offset + offset
null_threshold: self.null_threshold,
}
```
Or equivalently (I think)
```
Self {
values: self.values.slice(offset + self.offset, length),
offset: 0
null_threshold: self.null_threshold.saturating_sub(offset + self.offset),
}
```
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362677280
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
Review Comment:
We can remove the data slicing of the underlying `FieldCursor.values`. That slicing is a zero-copy of the underlying [ScalarBuffer](https://github.com/apache/arrow-rs/blob/ab87abdd69ab787fdf247cf36f04abc1fbfa6266/arrow-buffer/src/buffer/scalar.rs#L76) or [GenericByteArray](https://github.com/apache/arrow-rs/blob/ab87abdd69ab787fdf247cf36f04abc1fbfa6266/arrow-array/src/array/byte_array.rs#L325).
Would you prefer a switch to using FieldCursor offsets in the same as the RowCursor?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362679917
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
Review Comment:
I don't see an issue with slicing the underlying values, my observation is that the following will behave differently between RowCursor and FieldCursor
```
cursor.advance();
cursor.slice(1, 2);
```
In the case of `RowCursor` it will produce a slice that is offset by 2 from the start, whereas FieldCursor will produce one that is only offset by 1? I think...
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1360039880
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -432,4 +501,119 @@ mod tests {
b.advance();
assert_eq!(a.cmp(&b), Ordering::Less);
}
+
+ #[test]
+ fn test_slice_primitive() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let mut cursor = new_primitive(options, buffer, 0);
+
+ // from start
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice from start"
+ );
+
+ // with offset
+ let sliced = cursor.slice(1, 2);
+ assert_eq!(sliced.num_rows(), 2);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![1]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should slice with offset"
+ );
+
+ // cursor current position != start
+ cursor.advance();
+ let sliced = cursor.slice(0, 1);
+ assert_eq!(sliced.num_rows(), 1);
+ let expected = new_primitive(options, ScalarBuffer::from(vec![0]), 0);
+ assert_eq!(
+ sliced.cmp(&expected),
+ Ordering::Equal,
+ "should ignore current cursor position when sliced"
+ );
+ }
+
+ #[test]
+ #[should_panic(expected = "cursor slice out of bounds")]
+ fn test_slice_panic_can_panic() {
+ let options = SortOptions {
+ descending: false,
+ nulls_first: true,
+ };
+
+ let buffer = ScalarBuffer::from(vec![0, 1, 2]);
+ let cursor = new_primitive(options, buffer, 0);
+
+ cursor.slice(42, 1);
+ }
+
Review Comment:
Done.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1356535464
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Result<Self> {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Ok(Self {
+ values: values.slice(offset, length)?,
+ offset: 0,
+ null_threshold: *null_threshold,
Review Comment:
Is this correct?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1357207191
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Result<Self> {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Ok(Self {
+ values: values.slice(offset, length)?,
+ offset: 0,
+ null_threshold: *null_threshold,
Review Comment:
You are correct. In order to recalculate the null_threshold, we rely on methods from the original `FieldArray: Array` interface (not the inner `FieldValues`). Is there any reason not to keep the original field array?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362643134
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
Review Comment:
What would happen if this method was simply
```
Self {
values: self.values.slice(0, self.offset + offset + length),
offset: self.offset + offset
null_threshold: self.null_threshold,
}
```
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1360039803
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -275,6 +324,26 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
+ null_threshold,
+ options,
+ } = self;
+
+ Self {
+ values: values.slice(offset, length),
+ offset: 0,
+ null_threshold: null_threshold.checked_sub(offset).unwrap_or(0),
Review Comment:
Calculation is different, and a bit more explicit. Lmk if ok.
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1356533299
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -99,19 +102,45 @@ pub trait Cursor: Ord {
/// Advance the cursor, returning the previous row index
fn advance(&mut self) -> usize;
+
+ /// Slice the cursor at a given row index, returning a new cursor
+ ///
+ /// Returns an error if the slice is out of bounds, or memory is insufficient
+ fn slice(&self, offset: usize, length: usize) -> Result<Self>
Review Comment:
Does this interface need to be fallible? It looks like the only error is out of bounds, which would imply a logic error at which point I think a panic is fine?
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362634939
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
+ let FieldCursor {
+ values,
+ offset: _,
Review Comment:
This seems at odds with the behaviour of RowCursor, which takes the current offset into account
--
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] feat(7181): add cursor slicing [arrow-datafusion]
Posted by "wiedld (via GitHub)" <gi...@apache.org>.
wiedld commented on code in PR #7798:
URL: https://github.com/apache/arrow-datafusion/pull/7798#discussion_r1362670181
##########
datafusion/physical-plan/src/sorts/cursor.rs:
##########
@@ -284,6 +333,34 @@ impl<T: FieldValues> Cursor for FieldCursor<T> {
self.offset += 1;
t
}
+
+ fn slice(&self, offset: usize, length: usize) -> Self {
Review Comment:
The RowCursor slicing does not slice the underlying rows, therefore it is `self.offset + offset`.
Whereas the FieldCursor does slice the underlying data, and therefore the offset is reset to 0.
--
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