Function mz_transform::analysis::non_negative::is_superset_of

fn is_superset_of(lhs: &MirRelationExpr, rhs: &MirRelationExpr) -> bool

Returns true only if rhs.negate().union(lhs) contains only non-negative multiplicities once consolidated.

Informally, this happens when rhs is a multiset subset of lhs, meaning the multiplicity of any record in rhs is at most the multiplicity of the same record in lhs.

This method recursively descends each of lhs and rhs and performs a great many equality tests, which has the potential to be quadratic. We should consider restricting its attention to Get identifiers, under the premise that equal AST nodes would necessarily be identified by common subexpression elimination. This requires care around recursively bound identifiers.

These rules are .. somewhat arbitrary, and likely reflect observed opportunities. For example, while we do relate distinct(filter(A)) <= distinct(A), we do not relate distinct(A) <= A. Further thoughts about the class of optimizations, and whether there should be more or fewer, can be found here: https://github.com/MaterializeInc/database-issues/issues/4044.