Skip to main content

zero_client/builder/
pushdown.rs

1//! Correlated predicate pushdown
2//! (`packages/zql/src/builder/correlated-predicate-pushdown.ts`).
3
4use crate::ast::{Ast, Condition, CorrelatedSubquery, SimpleOperator, ValuePosition};
5use crate::json::Value;
6use crate::map::OrderedMap;
7use crate::query::simplify_condition;
8use crate::schema::{Column, ValueType};
9
10/// The longest `IN` list copied into a child.
11pub const MAX_PUSHED_IN_VALUES: usize = 32;
12
13/// Copies a parent's conditions on correlation columns into its subqueries.
14/// The result is the same; child rows that cannot join to a parent that
15/// matters are filtered out early.
16pub fn push_down_correlated_predicates(
17    ast: &Ast,
18    columns_of: &dyn Fn(&str) -> OrderedMap<Column>,
19) -> Ast {
20    Pushdown { columns_of }.visit(ast)
21}
22
23struct Pushdown<'a> {
24    columns_of: &'a dyn Fn(&str) -> OrderedMap<Column>,
25}
26
27impl Pushdown<'_> {
28    fn visit(&self, ast: &Ast) -> Ast {
29        let where_ = ast
30            .where_
31            .as_ref()
32            .map(|w| self.visit_condition(w, &ast.table, &[]));
33        let facts = where_.as_ref().map(simple_conjuncts).unwrap_or_default();
34        let mut result = ast.clone();
35        result.related = ast.related.as_ref().map(|related| {
36            related
37                .iter()
38                .map(|csq| {
39                    let mut c = csq.clone();
40                    c.subquery = Box::new(self.visit(&self.push_into(csq, &facts, &ast.table)));
41                    c
42                })
43                .collect()
44        });
45        result.where_ = where_;
46        result
47    }
48
49    fn visit_condition(&self, c: &Condition, table: &str, facts: &[Condition]) -> Condition {
50        match c {
51            Condition::Simple { .. } => c.clone(),
52            Condition::And(_) => {
53                let mut all = facts.to_vec();
54                all.extend(simple_conjuncts(c));
55                self.visit_conjunction(c, table, &all)
56            }
57            Condition::Or(cs) => Condition::Or(
58                cs.iter()
59                    .map(|x| self.visit_condition(x, table, facts))
60                    .collect(),
61            ),
62            Condition::CorrelatedSubquery {
63                related,
64                op,
65                flip,
66                scalar,
67            } => {
68                let mut related = related.clone();
69                related.subquery = Box::new(self.visit(&self.push_into(&related, facts, table)));
70                Condition::CorrelatedSubquery {
71                    related,
72                    op: *op,
73                    flip: *flip,
74                    scalar: *scalar,
75                }
76            }
77        }
78    }
79
80    /// `facts` already has the simple conjuncts of `c` and its nested ANDs.
81    fn visit_conjunction(&self, c: &Condition, table: &str, facts: &[Condition]) -> Condition {
82        let Condition::And(cs) = c else {
83            return c.clone();
84        };
85        Condition::And(
86            cs.iter()
87                .map(|x| match x {
88                    Condition::And(_) => self.visit_conjunction(x, table, facts),
89                    _ => self.visit_condition(x, table, facts),
90                })
91                .collect(),
92        )
93    }
94
95    fn push_into(&self, csq: &CorrelatedSubquery, facts: &[Condition], parent_table: &str) -> Ast {
96        let parent_field = &csq.correlation.parent_field;
97        let child_field = &csq.correlation.child_field;
98        let subquery = &*csq.subquery;
99        let mut conjuncts = subquery
100            .where_
101            .as_ref()
102            .map(simple_conjuncts)
103            .unwrap_or_default();
104        let mut added: Vec<Condition> = Vec::new();
105        let parent_columns = (self.columns_of)(parent_table);
106        let child_columns = (self.columns_of)(&subquery.table);
107        for fact in facts {
108            if !is_pushable(fact) {
109                continue;
110            }
111            let Condition::Simple {
112                op,
113                left: ValuePosition::Column(name),
114                right,
115            } = fact
116            else {
117                continue;
118            };
119            for (p, c) in parent_field.iter().zip(child_field) {
120                if p == name && have_same_scalar_type(parent_columns.get(p), child_columns.get(c)) {
121                    let copy = Condition::Simple {
122                        op: *op,
123                        left: ValuePosition::Column(c.clone()),
124                        right: right.clone(),
125                    };
126                    if !conjuncts.iter().any(|x| is_same_condition(x, &copy)) {
127                        conjuncts.push(copy.clone());
128                        added.push(copy);
129                    }
130                }
131            }
132        }
133        if added.is_empty() {
134            return subquery.clone();
135        }
136        let mut result = subquery.clone();
137        let mut all: Vec<Condition> = subquery.where_.iter().cloned().collect();
138        all.extend(added);
139        result.where_ = Some(simplify_condition(Condition::And(all)));
140        result
141    }
142}
143
144/// The simple conjuncts of `c`, including those of nested ANDs.
145fn simple_conjuncts(c: &Condition) -> Vec<Condition> {
146    match c {
147        Condition::Simple { .. } => vec![c.clone()],
148        Condition::And(cs) => cs.iter().flat_map(simple_conjuncts).collect(),
149        _ => Vec::new(),
150    }
151}
152
153fn is_pushable(c: &Condition) -> bool {
154    let Condition::Simple {
155        op,
156        left: ValuePosition::Column(_),
157        right: ValuePosition::Literal(value),
158    } = c
159    else {
160        return false;
161    };
162    match op {
163        SimpleOperator::Eq | SimpleOperator::Is => true,
164        SimpleOperator::In => matches!(value, Value::Array(a) if a.len() <= MAX_PUSHED_IN_VALUES),
165        _ => false,
166    }
167}
168
169fn is_same_condition(a: &Condition, b: &Condition) -> bool {
170    match (a, b) {
171        (
172            Condition::Simple {
173                op: op_a,
174                left: ValuePosition::Column(name_a),
175                right: ValuePosition::Literal(va),
176            },
177            Condition::Simple {
178                op: op_b,
179                left: ValuePosition::Column(name_b),
180                right: ValuePosition::Literal(vb),
181            },
182        ) => op_a == op_b && name_a == name_b && va == vb,
183        _ => false,
184    }
185}
186
187fn have_same_scalar_type(parent: Option<&Column>, child: Option<&Column>) -> bool {
188    match (parent, child) {
189        (Some(p), Some(c)) => p.type_ == c.type_ && p.type_ != ValueType::Json,
190        _ => false,
191    }
192}