Method extract_common

src/expr/src/linear.rs:480–630

Extracts common expressions from multiple `Self` into a result `Self`. The argument `mfps` are mutated so that each are functionaly equivalent to their corresponding input, when composed atop the resulting `Self`. The `extract_exprs` argument is temporary, as we roll out the `extract_common_mfp_expressions` flag.

(mfps: &mut [&mut Self])

    ///
    /// The `extract_exprs` argument is temporary, as we roll out the `extract_common_mfp_expressions` flag.
    pub fn extract_common(mfps: &mut [&mut Self]) -> Self {
        match mfps.len() {
            0 => {
                panic!("Cannot call method on empty arguments");
            }
            1 => {
                let output_arity = mfps[0].projection.len();
                std::mem::replace(mfps[0], MapFilterProject::new(output_arity))
            }
            _ => {
                // More generally, we convert each mfp to ANF, at which point we can
                // repeatedly extract atomic expressions that depend only on input
                // columns, migrate them to an input mfp, and repeat until no such
                // expressions exist. At this point, we can also migrate predicates
                // and then determine and push down projections.

                // Prepare a return `Self`.
                let mut result_mfp = MapFilterProject::new(mfps[0].input_arity);

                // We convert each mfp to ANF, using `memoize_expressions`.
                for mfp in mfps.iter_mut() {
                    mfp.memoize_expressions();
                }

                // We repeatedly extract common expressions, until none remain.
                let mut done = false;
                while !done {
                    // We use references to determine common expressions, and must
                    // introduce a scope here to drop the borrows before mutation.
                    let common = {
                        // The input arity may increase as we iterate, so recapture.
                        let input_arity = result_mfp.projection.len();
                        let mut prev: BTreeSet<_> = mfps[0]
                            .expressions
                            .iter()
                            .filter(|e| e.support().last() < Some(&input_arity))
                            .collect();
                        let mut next = BTreeSet::default();
                        for mfp in mfps[1..].iter() {
                            for expr in mfp.expressions.iter() {
                                if prev.contains(expr) {
                                    next.insert(expr);
                                }
                            }
                            std::mem::swap(&mut prev, &mut next);
                            next.clear();
                        }
                        prev.into_iter().cloned().collect::<Vec<_>>()
                    };
                    // Without new common expressions, we should terminate the loop.
                    done = common.is_empty();

                    // Migrate each expression in `common` to `result_mfp`.
                    for expr in common.into_iter() {
                        // Update each mfp by removing expr and updating column references.
                        for mfp in mfps.iter_mut() {
                            // With `expr` next in `result_mfp`, it is as if we are rotating it to
                            // be the first expression in `mfp`, and then removing it from `mfp` and