Skip to content

Commit 0a03e40

Browse files
author
Sergey Zhukov
committed
Statistics: Migrate to Distribution from Precision (apache#14896)
1 parent 739cadc commit 0a03e40

2 files changed

Lines changed: 123 additions & 48 deletions

File tree

‎datafusion/expr-common/src/statistics.rs‎

Lines changed: 123 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ use crate::type_coercion::binary::binary_numeric_coercion;
2525
use arrow::array::ArrowNativeTypeOp;
2626
use arrow::datatypes::{DataType, Schema, SchemaRef};
2727
use datafusion_common::rounding::alter_fp_rounding_mode;
28-
use datafusion_common::{internal_err, not_impl_err, DataFusionError, Result, ScalarValue};
28+
use datafusion_common::{internal_err, not_impl_err, Result, ScalarValue};
2929

3030
/// This object defines probabilistic distributions that encode uncertain
3131
/// information about a single, scalar value. Currently, we support five core
@@ -250,9 +250,9 @@ impl ProbabilityDistribution {
250250
pub fn to_inexact(self) -> Result<Self> {
251251
let res = match self {
252252
Uniform(dist) => Generic(GenericDistribution::try_new(ScalarValue::Null, ScalarValue::Null, ScalarValue::Null,dist.range().clone())?),
253-
Exponential(dist) => todo!(),
254-
Gaussian(dist) => todo!(),
255-
Bernoulli(dist) => todo!(),
253+
Exponential(_dist) => todo!(),
254+
Gaussian(_dist) => todo!(),
255+
Bernoulli(_dist) => todo!(),
256256
_ => self,
257257
};
258258
Ok(res)
@@ -289,7 +289,10 @@ impl ProbabilityDistribution {
289289
}
290290

291291
pub fn with_estimated_selectivity(self, selectivity: f64) -> Self {
292-
unimplemented!()
292+
let value = self.get_value().unwrap_or(&ScalarValue::Null);
293+
let selectivity = ScalarValue::Float64(Some(selectivity));
294+
let res = value.mul(selectivity).unwrap_or(ScalarValue::Null);
295+
ProbabilityDistribution::new_exact(res).unwrap_or_default()
293296
}
294297

295298
pub fn min(&self, other: &Self) -> ProbabilityDistribution {
@@ -1001,7 +1004,13 @@ pub fn compute_variance(
10011004

10021005
impl Display for ProbabilityDistribution {
10031006
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1004-
todo!()
1007+
match self {
1008+
Uniform(dist) => write!(f, "Uniform({:?})", dist),
1009+
Exponential(dist) => write!(f, "Exponential({:?})", dist),
1010+
Gaussian(dist) => write!(f, "Gaussian({:?})", dist),
1011+
Bernoulli(dist) => write!(f, "Bernoulli({:?})", dist),
1012+
Generic(dist) => write!(f, "Generic({:?})", dist),
1013+
}
10051014
}
10061015
}
10071016

@@ -1023,6 +1032,11 @@ impl Display for TableStatistics {
10231032
.enumerate()
10241033
.map(|(i, cs)| {
10251034
let s = format!("(Col[{}]:", i);
1035+
let s = format!("{} Min={}", s, cs.min_value);
1036+
let s = format!("{} Max={}", s, cs.max_value);
1037+
let s = format!("{} Sum={}", s, cs.sum_value);
1038+
let s = format!("{} Null={}", s, cs.null_count);
1039+
let s = format!("{} Distinct={}", s, cs.distinct_count);
10261040
s + ")"
10271041
})
10281042
.collect::<Vec<_>>()
@@ -1039,20 +1053,9 @@ impl Display for TableStatistics {
10391053

10401054
impl TableStatistics {
10411055
pub fn new_unknown(schema: &Schema) -> Result<Self> {
1042-
let num_rows = ProbabilityDistribution::new_generic(
1043-
ScalarValue::Null,
1044-
ScalarValue::Null,
1045-
ScalarValue::Null,
1046-
Interval::make_non_negative_infinity_interval(&DataType::UInt64)?,
1047-
)?;
1048-
let total_byte_size = ProbabilityDistribution::new_generic(
1049-
ScalarValue::Null,
1050-
ScalarValue::Null,
1051-
ScalarValue::Null,
1052-
Interval::make_non_negative_infinity_interval(&DataType::UInt64)?,
1053-
)?;
1054-
let column_statistics = vec![ColumnStatistics::new_unknown()?];
1055-
Ok(Self{ num_rows, total_byte_size, column_statistics })
1056+
let unknown = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1057+
let column_statistics = ColumnStatistics::unknown_column(schema)?;
1058+
Ok(Self{ num_rows: unknown.clone(), total_byte_size: unknown.clone(), column_statistics })
10561059
}
10571060

10581061
pub fn to_inexact(mut self) -> Result<Self> {
@@ -1066,18 +1069,79 @@ impl TableStatistics {
10661069
Ok(self)
10671070
}
10681071

1072+
/// Project the statistics to the given column indices.
1073+
///
1074+
/// For example, if we had statistics for columns `{"a", "b", "c"}`,
1075+
/// projecting to `vec![2, 1]` would return statistics for columns `{"c",
1076+
/// "b"}`.
10691077
pub fn project(mut self, projection: Option<&Vec<usize>>) -> Self {
1070-
unimplemented!()
1078+
let Some(projection) = projection else {
1079+
return self;
1080+
};
1081+
1082+
enum Slot {
1083+
/// The column is taken and put into the specified statistics location
1084+
Taken(usize),
1085+
/// The original columns is present
1086+
Present(ColumnStatistics),
1087+
}
1088+
1089+
// Convert to Vec<Slot> so we can avoid copying the statistics
1090+
let mut columns: Vec<_> = std::mem::take(&mut self.column_statistics)
1091+
.into_iter()
1092+
.map(Slot::Present)
1093+
.collect();
1094+
1095+
for idx in projection {
1096+
let next_idx = self.column_statistics.len();
1097+
let slot = std::mem::replace(
1098+
columns.get_mut(*idx).expect("projection out of bounds"),
1099+
Slot::Taken(next_idx),
1100+
);
1101+
match slot {
1102+
// The column was there, so just move it
1103+
Slot::Present(col) => self.column_statistics.push(col),
1104+
// The column was taken, so copy from the previous location
1105+
Slot::Taken(prev_idx) => self
1106+
.column_statistics
1107+
.push(self.column_statistics[prev_idx].clone()),
1108+
}
1109+
}
1110+
1111+
self
10711112
}
10721113

1114+
/// Calculates the statistics after `fetch` and `skip` operations apply.
1115+
/// Here, `self` denotes per-partition statistics. Use the `n_partitions`
1116+
/// parameter to compute global statistics in a multi-partition setting.
10731117
pub fn with_fetch(
10741118
mut self,
10751119
schema: SchemaRef,
10761120
fetch: Option<usize>,
10771121
skip: usize,
10781122
n_partitions: usize,
10791123
) -> Result<Self> {
1080-
unimplemented!()
1124+
let fetch_val = fetch.map(|v| v as u64);
1125+
let fetch_val = ScalarValue::UInt64(fetch_val);
1126+
let skip = ScalarValue::UInt64(Some(skip as u64));
1127+
let fetch = fetch.map(|v| v as u64);
1128+
let fetch = ScalarValue::UInt64(fetch);
1129+
let num_rows = self.num_rows.get_value().unwrap_or(&ScalarValue::Null).clone();
1130+
1131+
self.num_rows = if num_rows <= fetch && skip == ScalarValue::new_one(&DataType::UInt64)? {
1132+
self.num_rows
1133+
} else if num_rows.sub(&skip)? <= fetch_val {
1134+
let n_partitions = ScalarValue::UInt64(Some(n_partitions as u64));
1135+
let value = num_rows.sub(&skip)?.mul_checked(n_partitions)?;
1136+
check_num_rows(Some(value), self.num_rows.is_exact().unwrap())?
1137+
} else {
1138+
let n_partitions = ScalarValue::UInt64(Some(n_partitions as u64));
1139+
let value = fetch_val.mul_checked(n_partitions)?;
1140+
check_num_rows(Some(value), self.num_rows.is_exact().unwrap())?
1141+
};
1142+
self.column_statistics = TableStatistics::unknown_column(&schema)?;
1143+
self.total_byte_size = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1144+
Ok(self)
10811145
}
10821146

10831147
pub fn unknown_column(schema: &Schema) -> Result<Vec<ColumnStatistics>> {
@@ -1089,6 +1153,18 @@ impl TableStatistics {
10891153
}
10901154
}
10911155

1156+
fn check_num_rows(value: Option<ScalarValue>, is_exact: bool) -> Result<ProbabilityDistribution> {
1157+
if let Some(value) = value {
1158+
if is_exact {
1159+
ProbabilityDistribution::new_exact(value)
1160+
} else {
1161+
ProbabilityDistribution::new_unknown(&DataType::UInt64)
1162+
}
1163+
} else {
1164+
ProbabilityDistribution::new_unknown(&DataType::UInt64)
1165+
}
1166+
}
1167+
10921168
/// Statistics for a column within a relation
10931169
#[derive(Clone, Debug, PartialEq)]
10941170
pub struct ColumnStatistics {
@@ -1106,25 +1182,38 @@ pub struct ColumnStatistics {
11061182

11071183
impl Default for ColumnStatistics {
11081184
fn default() -> Self {
1109-
let dist = ProbabilityDistribution::new_unknown(&DataType::UInt64).unwrap_or_default();
1185+
let unknown = ProbabilityDistribution::new_unknown(&DataType::UInt64).unwrap_or_default();
11101186
Self {
1111-
null_count: dist.clone(),
1112-
max_value: dist.clone(),
1113-
min_value: dist.clone(),
1114-
sum_value: dist.clone(),
1115-
distinct_count: dist.clone(),
1187+
null_count: unknown.clone(),
1188+
max_value: unknown.clone(),
1189+
min_value: unknown.clone(),
1190+
sum_value: unknown.clone(),
1191+
distinct_count: unknown.clone(),
11161192
}
11171193
}
11181194
}
11191195

11201196
impl ColumnStatistics {
1197+
/// Returns an unbounded `ColumnStatistics` for each field in the schema.
1198+
pub fn unknown_column(schema: &Schema) -> Result<Vec<ColumnStatistics>> {
1199+
schema
1200+
.fields()
1201+
.iter()
1202+
.map(|_| ColumnStatistics::new_unknown())
1203+
.collect()
1204+
}
1205+
1206+
/// Returns a [`ColumnStatistics`] instance for the given schema by assigning
1207+
/// unknown statistics to each column in the schema.
11211208
pub fn new_unknown() -> Result<Self> {
1122-
let null_count = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1123-
let max_value = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1124-
let min_value = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1125-
let sum_value = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1126-
let distinct_count = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1127-
Ok(Self { null_count, max_value, min_value, sum_value, distinct_count })
1209+
let unknown = ProbabilityDistribution::new_unknown(&DataType::UInt64)?;
1210+
Ok(Self {
1211+
null_count: unknown.clone(),
1212+
max_value: unknown.clone(),
1213+
min_value: unknown.clone(),
1214+
sum_value: unknown.clone(),
1215+
distinct_count: unknown.clone(),
1216+
})
11281217
}
11291218

11301219
pub fn to_inexact(mut self) -> Result<Self> {

‎datafusion/proto-common/src/from_proto/mod.rs‎

Lines changed: 0 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -833,26 +833,12 @@ impl TryFrom<&protobuf::TableStatistics> for TableStatistics {
833833
}
834834
}
835835

836-
// impl TryFrom<&TableStatistics> for protobuf::TableStatistics {
837-
// type Error = DataFusionError;
838-
839-
// fn try_from(value: &TableStatistics) -> Result<Self, Self::Error> {
840-
// todo!()
841-
// }
842-
// }
843-
844836
impl From<&TableStatistics> for protobuf::TableStatistics {
845837
fn from(value: &TableStatistics) -> Self {
846838
todo!()
847839
}
848840
}
849841

850-
// impl From<&protobuf::TableStatistics> for TableStatistics {
851-
// fn from(value: &protobuf::TableStatistics) -> Self {
852-
// todo!()
853-
// }
854-
// }
855-
856842
impl From<protobuf::CompressionTypeVariant> for CompressionTypeVariant {
857843
fn from(value: protobuf::CompressionTypeVariant) -> Self {
858844
match value {

0 commit comments

Comments
 (0)