Dandandan commented on code in PR #3787:
URL: https://github.com/apache/arrow-datafusion/pull/3787#discussion_r993824131
##########
datafusion/core/src/physical_plan/join_utils.rs:
##########
@@ -296,6 +299,154 @@ impl<T> Clone for OnceFut<T> {
}
}
+/// A shared state between statistic aggregators for a join
+/// operation.
+#[derive(Clone, Debug, Default)]
+struct PartialJoinStatistics {
+ pub num_rows: usize,
+ pub column_statistics: Vec<ColumnStatistics>,
+}
+
+/// Calculate the statistics for the given join's output.
+pub(crate) fn join_statistics(
+ left: Arc<dyn ExecutionPlan>,
+ right: Arc<dyn ExecutionPlan>,
+ on: JoinOn,
+ join_type: &JoinType,
+) -> Statistics {
+ let left_stats = left.statistics();
+ let right_stats = right.statistics();
+
+ let join_stats = join_cardinality(join_type, left_stats, right_stats, &on);
+ let (num_rows, column_statistics) = match join_stats {
+ Some(stats) => (Some(stats.num_rows), Some(stats.column_statistics)),
+ None => (None, None),
+ };
+ Statistics {
+ num_rows,
+ total_byte_size: None,
+ column_statistics,
+ is_exact: false,
+ }
+}
+
+// Estimate the cardinality for the given join with input statistics.
+fn join_cardinality(
+ join_type: &JoinType,
+ left_stats: Statistics,
+ right_stats: Statistics,
+ on: &JoinOn,
+) -> Option<PartialJoinStatistics> {
+ match join_type {
+ JoinType::Inner | JoinType::Left | JoinType::Right | JoinType::Full =>
{
+ let left_num_rows = left_stats.num_rows?;
+ let right_num_rows = right_stats.num_rows?;
+
+ // Take the left_col_stats and right_col_stats using the index
+ // obtained from index() method of the each element of 'on'.
+ let all_left_col_stats = left_stats.column_statistics?;
+ let all_right_col_stats = right_stats.column_statistics?;
+ let (left_col_stats, right_col_stats) = on
+ .iter()
+ .map(|(left, right)| {
+ (
+ all_left_col_stats[left.index()].clone(),
+ all_right_col_stats[right.index()].clone(),
+ )
+ })
+ .unzip::<_, _, Vec<_>, Vec<_>>();
+
+ let ij_cardinality = inner_join_cardinality(
+ left_num_rows,
+ right_num_rows,
+ left_col_stats,
+ right_col_stats,
+ )?;
+
+ // The cardinality for inner join can also be used to estimate
+ // the cardinality of left/right/full outer joins as long as it
+ // it is greater than the minimum cardinality constraints of these
+ // joins (so that we don't underestimate the cardinality).
+ let cardinality = match join_type {
+ JoinType::Inner => ij_cardinality,
+ JoinType::Left => max(ij_cardinality, left_num_rows),
+ JoinType::Right => max(ij_cardinality, right_num_rows),
+ JoinType::Full => {
+ max(ij_cardinality, left_num_rows)
+ + max(ij_cardinality, right_num_rows)
+ - ij_cardinality
+ }
+ _ => unreachable!(),
+ };
+
+ Some(PartialJoinStatistics {
+ num_rows: cardinality,
+ // We don't do anything specific here, just combine the
existing
+ // statistics which might yield subpar results (although it is
+ // true, esp regarding min/max). For a better estimation, we
need
+ // filter selectivity analysis first.
+ column_statistics: all_left_col_stats
+ .into_iter()
+ .chain(all_right_col_stats.into_iter())
+ .collect(),
+ })
+ }
+
+ JoinType::Semi => None,
+ JoinType::Anti => None,
+ }
+}
+
+/// Estimate the inner join cardinality by using the basic building blocks of
+/// column-level statistics and the total row count. This is a very naive and
+/// a very conservative implementation that can quickly give up if there is not
+/// enough input statistics.
+fn inner_join_cardinality(
+ left_num_rows: usize,
+ right_num_rows: usize,
+ left_col_stats: Vec<ColumnStatistics>,
+ right_col_stats: Vec<ColumnStatistics>,
+) -> Option<usize> {
+ // The algorithm here is partly based on the non-histogram selectivity
estimation
+ // from Spark's Catalyst optimizer.
+
+ let mut join_selectivity = None;
+ for (left_stat, right_stat) in
left_col_stats.iter().zip(right_col_stats.iter()) {
+ if (left_stat.min_value.clone()? > right_stat.max_value.clone()?)
+ || (left_stat.max_value.clone()? < right_stat.min_value.clone()?)
+ {
+ // If there is no overlap, then we can not accurately estimate
+ // the join cardinality. We could in theory use this information
+ // to point out the join will not produce any rows, but that would
+ // require some extra information (namely whether the statistics
are
+ // exact). For now, we just give up.
+ return None;
+ }
+
+ let col_selectivity = max(left_stat.distinct_count,
right_stat.distinct_count);
+ if col_selectivity > join_selectivity {
+ // Seems like there are a few implementations of this algorithm
that implement
+ // exponential decay for the selectivity (like Hive's Optiq
Optimizer). Needs
+ // further exploration.
+ join_selectivity = col_selectivity;
+ }
+ }
+
+ // With the assumption that the smaller input's domain is generally
represented in the bigger
+ // input's domain, we can calculate the inner join's cardinality by taking
the cartesian product
+ // of the two inputs and normalizing it by the selectivity factor.
+ let cardinality = match join_selectivity {
+ Some(selectivity) if selectivity > 0 => {
+ (left_num_rows * right_num_rows) / selectivity
+ }
+ // Since we don't have any information about the selectivity,
+ // we can only assume that the join will produce the cartesian
+ // product.
+ _ => left_num_rows * right_num_rows,
Review Comment:
I think it might be better to give in that case?
There is also this presentation about optimizing the order of joins without
statistics available (which also seems to do fine). We could also see if we can
reuse some of these ideas:
https://www.youtube.com/watch?v=aNRoR0Z3SzU
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
