jayzhan211 opened a new issue, #27429:
URL: https://github.com/apache/datafusion/issues/27429
### Is your feature request related to a problem or challenge?
I propose an opt-in `EXPLAIN` option that prints what each physical plan
node states about its output: its orderings, equal expressions and constants
(its `EquivalenceProperties`). These facts decide where the physical optimizer
adds or removes a sort, but `EXPLAIN` doesn't show them (apart from a file
scan's declared `output_ordering`), so finding the node behind a missing or
extra `SortExec` means reading code. @alamb, would an option like this be
welcome?
For example, the wrong results in #27267 come from one false claim, which
the option shows on the window node's line (prototype output, window expression
shortened):
```
ProjectionExec: expr=[ts@0 as ts, MAX(x) OVER (ORDER BY ts)@2 as m],
facts=[order: [ts@0 ASC NULLS LAST] | [m@1 ASC NULLS LAST]]
BoundedWindowAggExec: wdw=[…], mode=[Sorted], facts=[order: [ts@0 ASC
NULLS LAST] | [MAX(x) OVER (ORDER BY ts)@2 ASC NULLS LAST]]
SortExec: expr=[ts@0 ASC NULLS LAST], preserve_partitioning=[false],
facts=[order: [ts@0 ASC NULLS LAST]]
DataSourceExec: partitions=1, partition_sizes=[1], facts=[none]
```
The query ends with `ORDER BY m ASC NULLS LAST`, and there is no sort for it
because the window claims `m` is already sorted that way. A running `MAX` is
NULL until its first non-NULL input, so its NULLs come first and the claim is
false. A `UNION ALL` example (#26625) is in the details below.
### Describe the solution you'd like
A config option such as `datafusion.explain.show_equivalences` (default
`false`), wired like `datafusion.explain.show_schema`. It adds `facts=[...]` to
each line in the indent format and `order`, `equal` and `constant` entries to
each box in the tree format. The prototype always prints NULL placement (the
existing `Display` omits `NULLS FIRST`, so `[column1@0 ASC, column2@1 ASC NULLS
LAST]` is easy to misread), skips classes that hold only literals, and prints
`none` when a node states nothing.
With the option off, plans and `EXPLAIN` output stay the same. With it on,
users can see why a sort was added or removed, and tests can check a node's
claims directly, so a PR that changes a claim shows up as a diff in expected
output.
### Describe alternatives you've considered
- Always on in `EXPLAIN VERBOSE`: longer output for everyone.
- The existing `Display` of `EquivalenceProperties`: it has the NULL and
literal problems above.
### Additional context
A local prototype (about 140 lines: the option, the printer, wiring for both
formats) is below; tests and the generated config docs are not done. Anyone is
welcome to pick this up; please ping me for review.
<details><summary>Union and filter examples, before and after</summary>
Union of `SELECT a AS x, a AS y` arms (the shape in #26625). Before:
```
UnionExec
ProjectionExec: expr=[a@0 as x, a@0 as y]
DataSourceExec: partitions=1, partition_sizes=[1]
ProjectionExec: expr=[a@0 as x, a@0 as y]
DataSourceExec: partitions=1, partition_sizes=[1]
```
After:
```
UnionExec, facts=[none]
ProjectionExec: expr=[a@0 as x, a@0 as y], facts=[equal: {x@0, y@1}]
DataSourceExec: partitions=1, partition_sizes=[1], facts=[none]
ProjectionExec: expr=[a@0 as x, a@0 as y], facts=[equal: {x@0, y@1}]
DataSourceExec: partitions=1, partition_sizes=[1], facts=[none]
```
Filter `WHERE a = b AND c = 5 ... ORDER BY b`. Before:
```
SortExec: expr=[b@1 ASC NULLS LAST], preserve_partitioning=[false]
FilterExec: b@1 = a@0 AND c@2 = 5, projection=[a@0, b@1]
DataSourceExec: partitions=1, partition_sizes=[1]
```
After (`c = 5` is not shown because the filter's projection drops `c`):
```
SortExec: expr=[b@1 ASC NULLS LAST], preserve_partitioning=[false],
facts=[order: [b@1 ASC NULLS LAST]; equal: {b@1, a@0}]
FilterExec: b@1 = a@0 AND c@2 = 5, projection=[a@0, b@1], facts=[equal:
{b@1, a@0}]
DataSourceExec: partitions=1, partition_sizes=[1], facts=[none]
```
</details>
<details><summary>Prototype patch (on main ac1a63d2ce)</summary>
```diff
diff --git a/datafusion/common/src/config.rs
b/datafusion/common/src/config.rs
index 35a987b3d0..a0a73e47e4 100644
--- a/datafusion/common/src/config.rs
+++ b/datafusion/common/src/config.rs
@@ -1987,6 +1987,11 @@ config_namespace! {
/// When set to true, the explain statement will print schema
information
pub show_schema: bool, default = false
+ /// When set to true, the explain statement will print each
physical plan
+ /// node's equivalence properties: the orderings, groupings, equal
+ /// expressions and constants it states about its output
+ pub show_equivalences: bool, default = false
+
/// Display format of explain. Default is "indent".
/// When set to "tree", it will print the plan in a tree-rendered
format.
pub format: ExplainFormat, default = ExplainFormat::Indent
diff --git a/datafusion/core/src/physical_planner.rs
b/datafusion/core/src/physical_planner.rs
index dc81c9ba9f..8c91c5adbd 100644
--- a/datafusion/core/src/physical_planner.rs
+++ b/datafusion/core/src/physical_planner.rs
@@ -3269,6 +3269,7 @@ impl DefaultPhysicalPlanner {
FinalPhysicalPlan,
displayable(optimized_plan.as_ref())
.set_tree_maximum_render_width(config.tree_maximum_render_width)
+ .set_show_equivalences(config.show_equivalences)
.tree_render()
.to_string(),
));
@@ -3311,6 +3312,7 @@ impl DefaultPhysicalPlanner {
.set_show_statistics(show_statistics)
.set_statistics_registry(statistics_registry.clone())
.set_show_schema(show_schema)
+ .set_show_equivalences(config.show_equivalences)
.indent(e.verbose)
.to_string()
};
diff --git a/datafusion/physical-plan/src/display.rs
b/datafusion/physical-plan/src/display.rs
index 6a014cdccf..769ea08ec2 100644
--- a/datafusion/physical-plan/src/display.rs
+++ b/datafusion/physical-plan/src/display.rs
@@ -116,6 +116,9 @@ pub struct DisplayableExecutionPlan<'a> {
registry: StatisticsRegistry,
/// If schema should be displayed. See [`Self::set_show_schema`]
show_schema: bool,
+ /// If equivalence properties should be displayed. See
+ /// [`Self::set_show_equivalences`]
+ show_equivalences: bool,
/// Which metric categories should be included when rendering
metric_types: Vec<MetricType>,
/// Optional filter by semantic category (rows / bytes / timing).
@@ -174,6 +177,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
show_metrics,
show_statistics: false,
show_schema: false,
+ show_equivalences: false,
metric_types: Self::default_metric_types(),
metric_categories: None,
metric_names: None,
@@ -191,6 +195,15 @@ impl<'a> DisplayableExecutionPlan<'a> {
self
}
+ /// Enable display of equivalence properties
+ ///
+ /// If true, the indent format ends each line with the node's
+ /// equivalence properties, e.g. `eq_properties=[order: [[a@0 ASC]]]`
+ pub fn set_show_equivalences(mut self, show_equivalences: bool) -> Self
{
+ self.show_equivalences = show_equivalences;
+ self
+ }
+
/// Enable display of statistics
pub fn set_show_statistics(mut self, show_statistics: bool) -> Self {
self.show_statistics = show_statistics;
@@ -282,6 +295,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
show_statistics: bool,
registry: StatisticsRegistry,
show_schema: bool,
+ show_equivalences: bool,
metric_types: Vec<MetricType>,
metric_categories: Option<Vec<MetricCategory>>,
metric_names: Option<Vec<String>>,
@@ -296,6 +310,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
show_statistics: self.show_statistics,
registry: self.registry.clone(),
show_schema: self.show_schema,
+ show_equivalences: self.show_equivalences,
metric_types: &self.metric_types,
metric_categories: self.metric_categories.as_deref(),
metric_names: self.metric_names.as_deref(),
@@ -310,6 +325,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
show_statistics: self.show_statistics,
registry: self.registry.clone(),
show_schema: self.show_schema,
+ show_equivalences: self.show_equivalences,
metric_types: self.metric_types.clone(),
metric_categories: self.metric_categories.clone(),
metric_names: self.metric_names.clone(),
@@ -381,12 +397,14 @@ impl<'a> DisplayableExecutionPlan<'a> {
struct Wrapper<'a> {
plan: &'a dyn ExecutionPlan,
maximum_render_width: usize,
+ show_equivalences: bool,
}
impl fmt::Display for Wrapper<'_> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
let mut visitor = TreeRenderVisitor {
f,
maximum_render_width: self.maximum_render_width,
+ show_equivalences: self.show_equivalences,
};
visitor.visit(self.plan)
}
@@ -394,6 +412,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
Wrapper {
plan: self.inner,
maximum_render_width: self.tree_maximum_render_width,
+ show_equivalences: self.show_equivalences,
}
}
@@ -490,6 +509,7 @@ impl<'a> DisplayableExecutionPlan<'a> {
show_statistics: self.show_statistics,
registry: self.registry.clone(),
show_schema: self.show_schema,
+ show_equivalences: false,
metric_types: &self.metric_types,
metric_categories: self.metric_categories.as_deref(),
metric_names: self.metric_names.as_deref(),
@@ -572,6 +592,8 @@ struct IndentVisitor<'a, 'b> {
registry: StatisticsRegistry,
/// If schema should be displayed
show_schema: bool,
+ /// If equivalence properties should be displayed
+ show_equivalences: bool,
/// Which metric types should be rendered
metric_types: &'a [MetricType],
/// Optional filter by semantic category (rows / bytes / timing).
@@ -635,6 +657,17 @@ impl ExecutionPlanVisitor for IndentVisitor<'_, '_> {
display_schema(plan.schema().as_ref())
)?;
}
+ if self.show_equivalences {
+ let facts = equivalence_facts(plan)
+ .into_iter()
+ .map(|(key, value)| format!("{key}: {value}"))
+ .collect::<Vec<_>>();
+ if facts.is_empty() {
+ write!(self.f, ", facts=[none]")?;
+ } else {
+ write!(self.f, ", facts=[{}]", facts.join("; "))?;
+ }
+ }
writeln!(self.f)?;
self.indent += 1;
Ok(true)
@@ -1040,6 +1073,8 @@ struct TreeRenderVisitor<'a, 'b> {
f: &'a mut Formatter<'b>,
/// Maximum total width of the rendered tree
maximum_render_width: usize,
+ /// If equivalence properties should be displayed
+ show_equivalences: bool,
}
impl TreeRenderVisitor<'_, '_> {
@@ -1066,7 +1101,7 @@ impl TreeRenderVisitor<'_, '_> {
/// 2. Render node content and vertical connections
/// 3. Render bottom borders and connections
pub fn visit(&mut self, plan: &dyn ExecutionPlan) -> Result<(),
fmt::Error> {
- let root = RenderTree::create_tree(plan);
+ let root = RenderTree::create_tree(plan, self.show_equivalences);
for y in 0..root.height {
// Start by rendering the top layer.
@@ -2257,3 +2292,78 @@ mod tests {
}
}
}
+
+/// Describes a node's equivalence properties for `EXPLAIN` with
+/// `show_equivalences`: one `(key, value)` per kind of fact. NULL placement
+/// is always written out, and classes that only hold literals are skipped.
+pub(crate) fn equivalence_facts(plan: &dyn ExecutionPlan) -> Vec<(&'static
str, String)> {
+ use crate::execution_plan::ExecutionPlanProperties;
+ use datafusion_physical_expr::AcrossPartitions;
+ use datafusion_physical_expr::PhysicalExpr;
+ use datafusion_physical_expr::expressions::Literal;
+
+ let props = ExecutionPlanProperties::equivalence_properties(&plan);
+ let is_literal = |e: &Arc<dyn PhysicalExpr>| e.is::<Literal>();
+ let mut facts = vec![];
+
+ let orders = props
+ .oeq_class()
+ .iter()
+ .map(|ordering| {
+ let keys = ordering
+ .iter()
+ .map(|key| {
+ let direction = if key.options.descending {
+ "DESC"
+ } else {
+ "ASC"
+ };
+ let nulls = if key.options.nulls_first {
+ "FIRST"
+ } else {
+ "LAST"
+ };
+ format!("{} {direction} NULLS {nulls}", key.expr)
+ })
+ .collect::<Vec<_>>();
+ format!("[{}]", keys.join(", "))
+ })
+ .collect::<Vec<_>>();
+ if !orders.is_empty() {
+ facts.push(("order", orders.join(" | ")));
+ }
+ if !props.geq_class().is_empty() {
+ facts.push(("group", props.geq_class().to_string()));
+ }
+ let equal = props
+ .eq_group()
+ .iter()
+ .filter_map(|class| {
+ let members = class
+ .iter()
+ .filter(|e| !is_literal(e))
+ .map(|e| e.to_string())
+ .collect::<Vec<_>>();
+ (members.len() >= 2).then(|| format!("{{{}}}", members.join(",
")))
+ })
+ .collect::<Vec<_>>();
+ if !equal.is_empty() {
+ facts.push(("equal", equal.join(", ")));
+ }
+ let constants = props
+ .constants()
+ .into_iter()
+ .filter(|c| !is_literal(&c.expr))
+ .map(|c| match c.across_partitions {
+ AcrossPartitions::Uniform(Some(value)) => format!("{} =
{value}", c.expr),
+ AcrossPartitions::Uniform(None) => c.expr.to_string(),
+ AcrossPartitions::Heterogeneous => {
+ format!("{} (one value per partition)", c.expr)
+ }
+ })
+ .collect::<Vec<_>>();
+ if !constants.is_empty() {
+ facts.push(("constant", constants.join(", ")));
+ }
+ facts
+}
diff --git a/datafusion/physical-plan/src/render_tree.rs
b/datafusion/physical-plan/src/render_tree.rs
index 594ca6b525..d09508927b 100644
--- a/datafusion/physical-plan/src/render_tree.rs
+++ b/datafusion/physical-plan/src/render_tree.rs
@@ -71,12 +71,12 @@ pub struct RenderTree {
impl RenderTree {
/// Creates a new render tree from an execution plan.
- pub fn create_tree(plan: &dyn ExecutionPlan) -> Self {
+ pub fn create_tree(plan: &dyn ExecutionPlan, show_equivalences: bool)
-> Self {
let (width, height) = get_tree_width_height(plan);
let mut result = Self::new(width, height);
- create_tree_recursive(&mut result, plan, 0, 0);
+ create_tree_recursive(&mut result, plan, 0, 0, show_equivalences);
result
}
@@ -181,6 +181,7 @@ fn create_tree_recursive(
plan: &dyn ExecutionPlan,
x: usize,
y: usize,
+ show_equivalences: bool,
) -> usize {
let display_info = fmt_display(plan).to_string();
let mut extra_info = HashMap::new();
@@ -194,6 +195,15 @@ fn create_tree_recursive(
extra_info.insert(line.to_string(), "".to_string());
}
}
+ if show_equivalences {
+ let facts = crate::display::equivalence_facts(plan);
+ if facts.is_empty() {
+ extra_info.insert("facts".to_string(), "none".to_string());
+ }
+ for (key, value) in facts {
+ extra_info.insert(key.to_string(), value);
+ }
+ }
let mut node = RenderTreeNode::new(plan.name().to_string(), extra_info);
@@ -209,7 +219,13 @@ fn create_tree_recursive(
let child_x = x + width;
let child_y = y + 1;
node.add_child_position(child_x, child_y);
- width += create_tree_recursive(result, child.as_ref(), child_x,
child_y);
+ width += create_tree_recursive(
+ result,
+ child.as_ref(),
+ child_x,
+ child_y,
+ show_equivalences,
+ );
}
result.set_node(x, y, Arc::new(node));
```
</details>
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
