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 2023/01/19 15:43:11 UTC
[GitHub] [arrow-datafusion] mustafasrepo opened a new pull request, #4989: Feature/range linear
mustafasrepo opened a new pull request, #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989
# 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 #4979
# 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.
-->
During range calculation for window frames, we can use linear search instead of bisect. Since we know that table is already sorted and we would progress only in one direction. Linear search is amortized constant (When window frame boundaries are static). Hence this version is more optimal than current bisect implementation (where search complexity is log(n)). This change decreases overall window range calculation complexity from `O(n*log(n))` to `O(n)`.
# What changes are included in this PR?
<!--
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?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. 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)?
-->
Existing tests verify window range calculation correctness. Unit tests for `linear_search` is also added. We also compared time elapsed during Window result calculation for the query
```sql
SELECT SUM(a) OVER(ORDER BY a RANGE BETWEEN 10 PRECEDING AND 10 FOLLOWING) FROM t1;
```
. Time comparison between linear and bisect version for different conditions can be seen in table below.
n_row | distinct | linear(mean) | linear(median) | bisect(mean) | bisect(median)
-- | -- | -- | -- | -- | --
100 | 10 | 1.199524ms | 772.125ยตs | 2.065253ms | 1.501125ms
100 | 100_000_000 | 1.614941ms | 1.599208ms | 2.30337ms | 2.346416ms
1000 | 10 | 4.521795ms | 4.417125ms | 10.986941ms | 10.994333ms
1000 | 100_000_000 | 11.82327ms | 11.8265ms | 23.83402ms | 23.641541ms
100_000 | 10 | 428.01742ms | 428.022791ms | 1.661792712s | 1.666531666s
100_000 | 100_000_000 | 1.190898003s | 1.18136925s | 3.446534628s | 3.446675916s
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
No.
<!--
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
[GitHub] [arrow-datafusion] ozankabak commented on pull request #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
ozankabak commented on PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#issuecomment-1397344630
@alamb, I think you will like this. As I was reading the segment tree paper from #4904, one of the remarks therein that stood out to me was that in RANGE frames a simple linear search was preferred to bisections due to amortization. We wanted to check if this theoretical gain shows up in practice -- and it does bigly!
This PR uses cuts down on bisect usage in appropriate places and uses a linear search to exploit this amortization.
--
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] mustafasrepo commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
mustafasrepo commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082607725
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
To make it compatible with `bisect` api, we add two versions; where one version takes `sort_options: &[SortOptions]`, other version takes `compare_fn: F`. We want to put both in case anyone need it. In terms of functinality first version is not necessary. However, since constructing comparator function from `SortOptions` is a bit cumbersome, we wanted to have that version also.
--
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] mustafasrepo commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
mustafasrepo commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082669525
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
Review Comment:
`LexicographicalComparator` API, compares values at the two indices and returns their ordering. This useful to find change detection, or partition boundaries. However, in our case we need to search for specific value inside Array (possibly not existing in the array.). However, maybe with some kind of tweak, we maybe able to use `LexicographicalComparator` for our use case. I will think about it in detail.
--
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] mustafasrepo commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
mustafasrepo commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082607725
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
To make it compatible with `bisect` api, we have one version taking `sort_options: &[SortOptions]`, one version taking `compare_fn: F`. We want to put it in case anyone need it. Since constructing comparator function from `SortOptions` is a bit cumbersome.
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1081925799
##########
datafusion/common/src/utils.rs:
##########
@@ -22,8 +22,16 @@ use arrow::array::ArrayRef;
use arrow::compute::SortOptions;
use std::cmp::Ordering;
+/// Given column vectors, returns row at `idx`.
+pub fn get_row_at_idx(columns: &[ArrayRef], idx: usize) -> Result<Vec<ScalarValue>> {
+ columns
+ .iter()
+ .map(|arr| ScalarValue::try_from_array(arr, idx))
Review Comment:
๐ `collect` automagically leverages the info in the return type annotation, as if there was a `let` binding or if we had used `collect::<...>`.
--
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 #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#issuecomment-1397673292
I will plan to review this carefully 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] ursabot commented on pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by "ursabot (via GitHub)" <gi...@apache.org>.
ursabot commented on PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#issuecomment-1399003734
Benchmark runs are scheduled for baseline = 92d0a054c23e5fba91718db32ccd933ce86dd2b6 and contender = b71cae8aa556369bc5ee72b063ed1fc5a81192f1. b71cae8aa556369bc5ee72b063ed1fc5a81192f1 is a master commit associated with this PR. Results will be available as each benchmark for each run completes.
Conbench compare runs links:
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ec2-t3-xlarge-us-east-2] [ec2-t3-xlarge-us-east-2](https://conbench.ursa.dev/compare/runs/b7602ae58f5d4b7ba3324d1ffe741657...ebc718c2b1854f13b01b15b9ab814210/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on test-mac-arm] [test-mac-arm](https://conbench.ursa.dev/compare/runs/a4af3422df424d45b8c593bf88fcdb2e...9c071dfa45984472843f37989cf6184f/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-i9-9960x] [ursa-i9-9960x](https://conbench.ursa.dev/compare/runs/62bf27b1bb66413091df940f3d3c4b2c...84d58f2d947140169e6aa56dc6992ca0/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-thinkcentre-m75q] [ursa-thinkcentre-m75q](https://conbench.ursa.dev/compare/runs/dcbd2be5fd934bd7957e5699f4165edd...3fbb7ffd22844f168faeed49ff4bdbcc/)
Buildkite builds:
Supported benchmarks:
ec2-t3-xlarge-us-east-2: Supported benchmark langs: Python, R. Runs only benchmarks with cloud = True
test-mac-arm: Supported benchmark langs: C++, Python, R
ursa-i9-9960x: Supported benchmark langs: Python, R, JavaScript
ursa-thinkcentre-m75q: Supported benchmark langs: C++, Java
--
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 #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082548503
##########
datafusion/common/src/utils.rs:
##########
@@ -22,8 +22,16 @@ use arrow::array::ArrayRef;
use arrow::compute::SortOptions;
use std::cmp::Ordering;
+/// Given column vectors, returns row at `idx`.
+pub fn get_row_at_idx(columns: &[ArrayRef], idx: usize) -> Result<Vec<ScalarValue>> {
+ columns
+ .iter()
+ .map(|arr| ScalarValue::try_from_array(arr, idx))
+ .collect()
+}
+
/// This function compares two tuples depending on the given sort options.
-fn compare(
+pub fn compare_rows(
Review Comment:
maybe `pub crate` would be better here unless there is some reason to export it
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
Review Comment:
FWIW the arrow kernels have https://docs.rs/arrow/31.0.0/arrow/compute/struct.LexicographicalComparator.html which you might be able to use and avoid having to construct ScalarValues to compare.
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
+ let cmp = compare_rows(current, target, sort_options)?;
+ Ok(if SIDE { cmp.is_lt() } else { cmp.is_le() })
+ };
+ search_in_slice(item_columns, target, compare_fn, low, high)
+}
+
+/// This function searches for a tuple of given values (`target`) among a slice of
+/// the given rows (`item_columns`) via a linear scan. The slice starts at the index
+/// `low` and ends at the index `high`. The boolean-valued function `compare_fn`
+/// specifies the stopping criterion.
+pub fn search_in_slice<F>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ compare_fn: F,
+ mut low: usize,
+ high: usize,
+) -> Result<usize>
+where
+ F: Fn(&[ScalarValue], &[ScalarValue]) -> Result<bool>,
+{
+ while low < high {
Review Comment:
I don't know if this would be faster or not, but I winder if you might be able to use `.iter()` and `find()` to find the relevant index and possibly avoid the bounds checks ๐ค
Like if you could do something like `item_columns.iter().enumerate().find(compare_fn).map(|(i, _)| i).unwrap()`
##########
datafusion/common/src/utils.rs:
##########
@@ -22,8 +22,16 @@ use arrow::array::ArrayRef;
use arrow::compute::SortOptions;
use std::cmp::Ordering;
+/// Given column vectors, returns row at `idx`.
+pub fn get_row_at_idx(columns: &[ArrayRef], idx: usize) -> Result<Vec<ScalarValue>> {
+ columns
+ .iter()
+ .map(|arr| ScalarValue::try_from_array(arr, idx))
Review Comment:
Longer term, I think there is quite a bit more performance to be gained by avoiding the use of `ScalarValue` here and instead using something more optimized like the RowFormat. This is not something for this PR I am just trying to plan a seed if we need more performance, there is a path
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
I didn't see `linear_search` used anywhere in this PR other than tests -- I wonder if the intention was to call it in `datafusion/physical-expr/src/window/window_frame_state.rs` ? It looks like that currently has an inlined version of this function ๐ค
##########
datafusion/physical-expr/src/window/partition_evaluator.rs:
##########
@@ -83,7 +83,7 @@ pub trait PartitionEvaluator: Debug + Send {
fn evaluate_inside_range(
&self,
_values: &[ArrayRef],
- _range: Range<usize>,
+ _range: &Range<usize>,
Review Comment:
๐
##########
datafusion/physical-expr/src/window/window_frame_state.rs:
##########
@@ -285,8 +301,16 @@ impl WindowFrameStateRange {
} else {
current_row_values
};
- // `BISECT_SIDE` true means bisect_left, false means bisect_right
- bisect::<BISECT_SIDE>(range_columns, &end_range, sort_options)
+ let search_start = if SIDE {
+ last_range.start
+ } else {
+ last_range.end
+ };
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
Review Comment:
See the above comment about https://docs.rs/arrow/31.0.0/arrow/compute/struct.LexicographicalComparator.html possibly being another way to improve performance
--
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] mustafasrepo commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
mustafasrepo commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082607725
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
To make it compatible with `bisect` api, we add two versions; where one version takes `sort_options: &[SortOptions]`, other version takes `compare_fn: F`. We wanted to add both versions in case anyone need them. In terms of functionality first version is not necessary. However, since constructing comparator function from `SortOptions` is a bit cumbersome, we wanted to have that version also.
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1083058356
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
+ let cmp = compare_rows(current, target, sort_options)?;
+ Ok(if SIDE { cmp.is_lt() } else { cmp.is_le() })
+ };
+ search_in_slice(item_columns, target, compare_fn, low, high)
+}
+
+/// This function searches for a tuple of given values (`target`) among a slice of
+/// the given rows (`item_columns`) via a linear scan. The slice starts at the index
+/// `low` and ends at the index `high`. The boolean-valued function `compare_fn`
+/// specifies the stopping criterion.
+pub fn search_in_slice<F>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ compare_fn: F,
+ mut low: usize,
+ high: usize,
+) -> Result<usize>
+where
+ F: Fn(&[ScalarValue], &[ScalarValue]) -> Result<bool>,
+{
+ while low < high {
Review Comment:
Yes, exactly. But let's still keep this in our minds in the background, and improve this section in the future if anyone finds neat way.
--
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] mustafasrepo commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
mustafasrepo commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082729694
##########
datafusion/common/src/utils.rs:
##########
@@ -22,8 +22,16 @@ use arrow::array::ArrayRef;
use arrow::compute::SortOptions;
use std::cmp::Ordering;
+/// Given column vectors, returns row at `idx`.
+pub fn get_row_at_idx(columns: &[ArrayRef], idx: usize) -> Result<Vec<ScalarValue>> {
+ columns
+ .iter()
+ .map(|arr| ScalarValue::try_from_array(arr, idx))
+ .collect()
+}
+
/// This function compares two tuples depending on the given sort options.
-fn compare(
+pub fn compare_rows(
Review Comment:
This function is used both in `datafusion/common` and `datafusion/physical_expr.` Hence unfortunately `pub(crate)` wouldn't work.
--
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 #4989: Add support for linear range calculation in WINDOW functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1083023324
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
+ let cmp = compare_rows(current, target, sort_options)?;
+ Ok(if SIDE { cmp.is_lt() } else { cmp.is_le() })
+ };
+ search_in_slice(item_columns, target, compare_fn, low, high)
+}
+
+/// This function searches for a tuple of given values (`target`) among a slice of
+/// the given rows (`item_columns`) via a linear scan. The slice starts at the index
+/// `low` and ends at the index `high`. The boolean-valued function `compare_fn`
+/// specifies the stopping criterion.
+pub fn search_in_slice<F>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ compare_fn: F,
+ mut low: usize,
+ high: usize,
+) -> Result<usize>
+where
+ F: Fn(&[ScalarValue], &[ScalarValue]) -> Result<bool>,
+{
+ while low < high {
Review Comment:
I guess I was wondering if we could get an iter over `item_columns` somehow (and thus avoid all the bounds checks) -- I realize this is not really easy w/ multiple arrays. ๐ค
--
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 #4989: Add support for linear range calculation in WINDOW functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1083023897
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
My hesitation was that the tests are for `linear_search` -- the fact that you plan to use it in the future makes sense 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] avantgardnerio commented on a diff in pull request #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
avantgardnerio commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1081807258
##########
datafusion/common/src/utils.rs:
##########
@@ -22,8 +22,16 @@ use arrow::array::ArrayRef;
use arrow::compute::SortOptions;
use std::cmp::Ordering;
+/// Given column vectors, returns row at `idx`.
+pub fn get_row_at_idx(columns: &[ArrayRef], idx: usize) -> Result<Vec<ScalarValue>> {
+ columns
+ .iter()
+ .map(|arr| ScalarValue::try_from_array(arr, idx))
Review Comment:
What dark magic converts this from an `Vec<Result<ScalarValue>>` to a `Result<Vec<ScalarValue>>`?
##########
datafusion/physical-expr/src/window/window_frame_state.rs:
##########
@@ -85,6 +88,7 @@ impl<'a> WindowFrameContext<'a> {
sort_options,
length,
idx,
+ last_range,
Review Comment:
The last_range being added everywhere is a performance optimization to not throw away the index which was previously calculated?
--
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] ozankabak commented on pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
ozankabak commented on PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#issuecomment-1398641302
Thank you for carefully reviewing @alamb. We will consider further optimizing by leveraging `RowFormat` in a follow-on PR. As @mustafasrepo mentions, it is not obvious to use how we can utilize directly `LexicographicalComparator`, but if we figure out a way, we will make another follow-on PR for that too.
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082791126
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
+ let cmp = compare_rows(current, target, sort_options)?;
+ Ok(if SIDE { cmp.is_lt() } else { cmp.is_le() })
+ };
+ search_in_slice(item_columns, target, compare_fn, low, high)
+}
+
+/// This function searches for a tuple of given values (`target`) among a slice of
+/// the given rows (`item_columns`) via a linear scan. The slice starts at the index
+/// `low` and ends at the index `high`. The boolean-valued function `compare_fn`
+/// specifies the stopping criterion.
+pub fn search_in_slice<F>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ compare_fn: F,
+ mut low: usize,
+ high: usize,
+) -> Result<usize>
+where
+ F: Fn(&[ScalarValue], &[ScalarValue]) -> Result<bool>,
+{
+ while low < high {
Review Comment:
I think you mean something like this:
```rust
Ok((low..high).find(|&idx| {
let val = get_row_at_idx(item_columns, idx)?;
!compare_fn(&val, target)?
}).unwrap_or(high))
```
The problem is with the `?` operators, we would need to change them to `unwrap` calls for this to work. The code would look nicer, but we would be incurring the downside of panicking in case something goes wrong. In general, I prefer to err on the side of being a little more verbose than necessary but retain control over errors, but I don't have a strong opinion on this specific case. What do you 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
[GitHub] [arrow-datafusion] alamb merged pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1081922580
##########
datafusion/physical-expr/src/window/window_frame_state.rs:
##########
@@ -85,6 +88,7 @@ impl<'a> WindowFrameContext<'a> {
sort_options,
length,
idx,
+ last_range,
Review Comment:
Yes, as it goes through batches, the search picks up from where it left off before. This works for fixed-boundary RANGE frames (which is what Datafusion supports).
--
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] avantgardnerio commented on pull request #4989: Add support for linear range calculation
Posted by GitBox <gi...@apache.org>.
avantgardnerio commented on PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#issuecomment-1397506032
> there seems to be an intermittent CI failure
Github is experiencing some serious issues today, so it's probably related to their status. I'll keep an eye on it and kick CI once in a while...
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082640117
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
Review Comment:
Yes, so the same logic has two drivers: One with a comparison function, one with `SortOptions`. We currently use the former, but also anticipate to use the latter in the near future (we plan a follow-up of this PR for GROUPS mode). As @mustafasrepo mentions, it also brings both search APIs in line, which is good too.
--
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] ozankabak commented on a diff in pull request #4989: Add support for linear range calculation in WINDOW functions
Posted by GitBox <gi...@apache.org>.
ozankabak commented on code in PR #4989:
URL: https://github.com/apache/arrow-datafusion/pull/4989#discussion_r1082791126
##########
datafusion/common/src/utils.rs:
##########
@@ -103,6 +111,53 @@ where
Ok(low)
}
+/// This function searches for a tuple of given values (`target`) among the given
+/// rows (`item_columns`) via a linear scan. It assumes that `item_columns` is sorted
+/// according to `sort_options` and returns the insertion index of `target`.
+/// Template argument `SIDE` being `true`/`false` means left/right insertion.
+pub fn linear_search<const SIDE: bool>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ sort_options: &[SortOptions],
+) -> Result<usize> {
+ let low: usize = 0;
+ let high: usize = item_columns
+ .get(0)
+ .ok_or_else(|| {
+ DataFusionError::Internal("Column array shouldn't be empty".to_string())
+ })?
+ .len();
+ let compare_fn = |current: &[ScalarValue], target: &[ScalarValue]| {
+ let cmp = compare_rows(current, target, sort_options)?;
+ Ok(if SIDE { cmp.is_lt() } else { cmp.is_le() })
+ };
+ search_in_slice(item_columns, target, compare_fn, low, high)
+}
+
+/// This function searches for a tuple of given values (`target`) among a slice of
+/// the given rows (`item_columns`) via a linear scan. The slice starts at the index
+/// `low` and ends at the index `high`. The boolean-valued function `compare_fn`
+/// specifies the stopping criterion.
+pub fn search_in_slice<F>(
+ item_columns: &[ArrayRef],
+ target: &[ScalarValue],
+ compare_fn: F,
+ mut low: usize,
+ high: usize,
+) -> Result<usize>
+where
+ F: Fn(&[ScalarValue], &[ScalarValue]) -> Result<bool>,
+{
+ while low < high {
Review Comment:
I think you mean something like this:
```rust
Ok((low..high).find(|&idx| {
let val = get_row_at_idx(item_columns, idx)?;
!compare_fn(&val, target)?
}).unwrap_or(high))
```
The problem is with the `?` operators, we would need to change them to `unwrap` calls for this to work. The code would look nicer, but we would incurring the downside of panicking in case something goes wrong. In general, I prefer to err on the side of being a little more verbose than necessary but retain control over errors, but I don't have a strong opinion on this specific case. What do you 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