neilconway commented on code in PR #22343: URL: https://github.com/apache/datafusion/pull/22343#discussion_r3330610653
########## datafusion/optimizer/src/simplify_expressions/reorder_predicates.rs: ########## @@ -0,0 +1,190 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Reorder conjunctive (`AND`) predicates so that cheap predicates run before +//! expensive ones. +//! +//! DataFusion's `AND` evaluator short-circuits the right-hand side when the +//! left-hand side keeps few rows, so leading with a cheap predicate shrinks +//! the batch that expensive ones see. +//! +//! The cost of evaluating a predicate is assessed with a simple, conservative +//! heuristic: we define an allow-list of cheap operations, and consider an +//! expression to be cheap if it consists ONLY of cheap operations; everything +//! else is considered expensive. +//! +//! The sort is stable, so order within each class is preserved. + +use datafusion_common::tree_node::TreeNode; +use datafusion_expr::{BinaryExpr, Expr, Operator}; + +/// Stable partition of `predicates`: cheap first, then expensive. +/// +/// Returns `(predicates, changed)`. When `changed` is `false` the input was +/// already cheap-first and the caller can skip rebuilding the conjunction. +pub(crate) fn reorder_predicates(predicates: Vec<Expr>) -> (Vec<Expr>, bool) { + if predicates.len() <= 1 { + return (predicates, false); + } + + // Volatile predicates may have observable side-effects and reordering + // conjuncts can change how many times they evaluate. Preserve user order + // if any predicate contains a volatile expression. + if predicates.iter().any(Expr::is_volatile) { + return (predicates, false); + } + + let classes: Vec<bool> = predicates.iter().map(is_cheap_predicate).collect(); + + // A reorder is needed iff an expensive predicate precedes a cheap one + let needs_reorder = classes.windows(2).any(|w| !w[0] && w[1]); + if !needs_reorder { + return (predicates, false); + } + + let mut cheap = Vec::with_capacity(predicates.len()); + let mut expensive = Vec::new(); + for (p, is_cheap) in predicates.into_iter().zip(classes) { + if is_cheap { + cheap.push(p); + } else { + expensive.push(p); + } + } + cheap.extend(expensive); + (cheap, true) +} + +/// Returns true if every node in `expr`'s tree is cheap. +fn is_cheap_predicate(expr: &Expr) -> bool { + !expr + .exists(|node| Ok(!is_cheap_node(node))) + .expect("is_cheap_node is infallible") +} + +/// Returns true if `expr` is itself cheap. +/// +/// We use a simple, conservative heuristic to determine if an expression is +/// cheap to evaluate: we enumerate known-cheap operations (e.g., equality +/// comparisons, negations, casts), and consider anything outside this list to +/// be expensive. New/unrecognized expressions therefore default to being +/// expensive. +fn is_cheap_node(expr: &Expr) -> bool { Review Comment: Both of these changes could make sense, but I think this moves us in the direction of having a full-blown function cost model, which is the kind of API I was hoping to avoid committing to right now. IOW, if we start with something minimal and conservative like the current approach, we can always extend it to something much more ambitious in the future. -- 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]
