mz_compute_types/plan/
threshold.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Threshold planning logic.
11//!
12//! The threshold operator produces only rows with a positive cardinality, for example required to
13//! provide SQL except and intersect semantics.
14//!
15//! We build a plan ([ThresholdPlan]) encapsulating all decisions and requirements on the specific
16//! threshold implementation. The idea is to decouple the logic deciding which plan to select from
17//! the actual implementation of each variant available.
18//!
19//! Currently, we provide two variants:
20//! * The [BasicThresholdPlan] maintains all its outputs as an arrangement. It is beneficial if the
21//!     threshold is the final operation, or a downstream operators expects arranged inputs.
22//! * The [RetractionsThresholdPlan] maintains retractions, i.e. rows that are not in the output. It
23//!     is beneficial to use this operator if the number of retractions is expected to be small, and
24//!     if a potential downstream operator does not expect its input to be arranged.
25
26use mz_expr::permutation_for_arrangement;
27use serde::{Deserialize, Serialize};
28
29use crate::plan::AvailableCollections;
30use crate::plan::scalar::LirScalarExpr;
31
32/// A plan describing how to compute a threshold operation.
33#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq, Ord, PartialOrd)]
34pub enum ThresholdPlan {
35    /// Basic threshold maintains all positive inputs.
36    Basic(BasicThresholdPlan),
37}
38
39impl ThresholdPlan {
40    /// Reports all keys of produced arrangements, with optionally
41    /// given types describing the rows that would be in the raw
42    /// form of the collection.
43    ///
44    /// This is likely either an empty vector, for no arrangement,
45    /// or a singleton vector containing the list of expressions
46    /// that key a single arrangement.
47    pub fn keys(&self) -> AvailableCollections {
48        match self {
49            ThresholdPlan::Basic(plan) => {
50                AvailableCollections::new_arranged(vec![plan.ensure_arrangement.clone()])
51            }
52        }
53    }
54}
55
56/// A plan to maintain all inputs with positive counts.
57#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq, Ord, PartialOrd)]
58pub struct BasicThresholdPlan {
59    /// Description of how the input has been arranged, and how to arrange the output
60    pub ensure_arrangement: (Vec<LirScalarExpr>, Vec<usize>, Vec<usize>),
61}
62
63/// A plan to maintain all inputs with negative counts, which are subtracted from the output
64/// in order to maintain an equivalent collection compared to [BasicThresholdPlan].
65#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq, Ord, PartialOrd)]
66pub struct RetractionsThresholdPlan {
67    /// Description of how the input has been arranged
68    pub ensure_arrangement: (Vec<LirScalarExpr>, Vec<usize>, Vec<usize>),
69}
70
71impl ThresholdPlan {
72    /// Construct the plan from the number of columns (`arity`).
73    ///
74    /// Also returns the arrangement and thinning required for the input.
75    pub fn create_from(arity: usize) -> (Self, (Vec<LirScalarExpr>, Vec<usize>, Vec<usize>)) {
76        // Arrange the input by all columns in order.
77        let mut all_columns = Vec::new();
78        for column in 0..arity {
79            all_columns.push(LirScalarExpr::column(column));
80        }
81        let (permutation, thinning) = permutation_for_arrangement(&all_columns, arity);
82        let ensure_arrangement = (all_columns, permutation, thinning);
83        let plan = ThresholdPlan::Basic(BasicThresholdPlan {
84            ensure_arrangement: ensure_arrangement.clone(),
85        });
86        (plan, ensure_arrangement)
87    }
88}
mz_compute_types/plan/threshold.rs

mz_compute_types/plan/
threshold.rs
