Function expr::relation::canonicalize::rank_complexity

fn rank_complexity(expr: &MirScalarExpr) -> usize

Gives a relative complexity ranking for an expression. Higher numbers mean greater complexity.

Currently, this method weighs literals as the least complex and weighs all other expressions by the number of non-literals. In the future, we can change how complexity is ranked so that repeated substitutions would result in arriving at “better” fixed points. For example, we could try to improve performance by ranking expressions by their estimated computation time.

To ensure we arrive at a fixed point after repeated substitutions, valid complexity rankings must fulfill the following property: For any expression e, there does not exist a SQL function f such that complexity(e) >= complexity(f(e)).

For ease of intuiting the fixed point that we will arrive at after repeated substitutions, it is nice but not required that complexity rankings additionally fulfill the following property: If expressions e1 and e2 are such that complexity(e1) < complexity(e2) then for all SQL functions f, complexity(f(e1)) < complexity(f(e2)).