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/10/15 00:30:29 UTC
[GitHub] [arrow-datafusion] isidentical opened a new pull request, #3837: Infer the count of maximum distinct values from min/max
isidentical opened a new pull request, #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837
# 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.
-->
Part of #3813.
# 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.
-->
This was a point that came out during the initial join cardinality computation PR ([link](https://github.com/apache/arrow-datafusion/pull/3787#discussion_r992751749)) where the logic only gave an estimate when the distinct count information was available directly in the statistics. This was effective for certain use cases where the distinct count was already calculated (e.g. propagated statistics from stuff like aggregates) but for statistics that originate from initial user input, having `distinct_count` is very unlikely (e.g. there is no way to save distinct count when exporting a parquet file from pandas, none of the official backends [pyarrow/fastparquet] even support such a thing in their write APIs). So one main thing we can do is actually use `min`/`max` values (which are nearly universal at this point) to calculate the maximum possible distinct count (which is actually what we need for selectivity).
# 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.
-->
A fallback option for inferring the maximum distinct count when the actual distinct count information is not available. It only works with numeric values (more specifically, integers) at this point (we can technically determine the range for timestamps or floats, but neither of them feels close to accurate since that would be essentially brute forcing every possible value within the precision boundaries, something that feels very unlikely to happen in real world, but open for discussion).
# 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 backwards incompatible changes.
<!--
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] Dandandan merged pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
Dandandan merged PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837
--
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] Dandandan commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
Dandandan commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996292437
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
Shouldn't the count return `1` if `min=max`?
--
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] isidentical commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996338911
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
Ah, my bad (not sure how I thought that was correct 🤦🏻). Thanks for catching it!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] isidentical commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996295008
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
~~Yes, and we should be already handling it (check out the comment in the following line).~~
--
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] isidentical commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996295008
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
Yes, and we should be already handling it (check out the comment in the following line).
--
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 #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
ursabot commented on PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#issuecomment-1279823319
Benchmark runs are scheduled for baseline = e02376ddc431a818e1f19a5bb16fe45307a512e8 and contender = fe0000e6de4f1a2e7e7fd1b0d75ef32f4b61f194. fe0000e6de4f1a2e7e7fd1b0d75ef32f4b61f194 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/0ef177e4bb3e41e0ba476273017a493b...33f5536786274fd99d1beb5b95c2d908/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on test-mac-arm] [test-mac-arm](https://conbench.ursa.dev/compare/runs/d0c8033cde134d2cb02707b795d372f3...3b3b17762f8a4d64867bdc85841b8914/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-i9-9960x] [ursa-i9-9960x](https://conbench.ursa.dev/compare/runs/b52f6bb3ec2b4c12a676462cddeebca6...fd0f985ba73d482e9c8e9d03da558bec/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-thinkcentre-m75q] [ursa-thinkcentre-m75q](https://conbench.ursa.dev/compare/runs/ff83ac662e104707a9362dad74d84a3d...c28bf333950d43b2bc3d157057956386/)
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] Dandandan commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
Dandandan commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996329232
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
What I mean is , the current implementation seems to return `0` when `min==max` but shouldn't that be `+1` as well?
--
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] isidentical commented on a diff in pull request #3837: Infer the count of maximum distinct values from min/max
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #3837:
URL: https://github.com/apache/arrow-datafusion/pull/3837#discussion_r996339299
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -447,6 +450,59 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimate the number of maximum distinct values that can be present in the
+/// given column from its statistics.
+///
+/// If distinct_count is available, uses it directly. If the column numeric, and
+/// has min/max values, then they might be used as a fallback option. Otherwise,
+/// returns None.
+fn max_distinct_count(num_rows: usize, stats: ColumnStatistics) -> Option<usize> {
+ match (stats.distinct_count, stats.max_value, stats.min_value) {
+ (Some(_), _, _) => stats.distinct_count,
+ (_, Some(max), Some(min)) => {
+ // Note that float support is intentionally omitted here, since the computation
+ // of a range between two float values is not trivial and the result would be
+ // highly inaccurate.
+ let numeric_range = get_int_range(min, max)?;
+
+ // The number can never be greater than the number of rows we have (minus
+ // the nulls, since they don't count as distinct values).
+ let ceiling = num_rows - stats.null_count.unwrap_or(0);
+ Some(numeric_range.min(ceiling))
+ }
+ _ => None,
+ }
+}
+
+/// Return the numeric range between the given min and max values.
+fn get_int_range(min: ScalarValue, max: ScalarValue) -> Option<usize> {
+ let delta = &max.sub(&min).ok()?;
+ match delta {
+ ScalarValue::Int8(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int16(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int32(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::Int64(Some(delta)) if *delta >= 0 => Some(*delta as usize),
+ ScalarValue::UInt8(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt16(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt32(Some(delta)) => Some(*delta as usize),
+ ScalarValue::UInt64(Some(delta)) => Some(*delta as usize),
+ _ => None,
+ }
+ // The delta (directly) is not the real range, since it does not include the
+ // first term if it is different from the final term.
+ // E.g. (min=2, max=4) -> (4 - 2) -> 2, but the actual result should be 3 (1, 2, 3).
Review Comment:
Should be fixed with 7a63f6fba09bb05584f5cf25508b031f8ac1c9c1, thanks 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