radixdb_executor/
expr_converter.rs

1// Copyright 2026 RadixDB Contributors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Expression Converter for Predicate Pushdown
16//!
17//! This module converts parser AST expressions to storage layer expressions
18//! for predicate pushdown optimization. Only simple, pushable predicates
19//! are converted - complex expressions that can't be pushed down return None.
20//!
21//! ## Supported Conversions
22//!
23//! | AST Expression          | Storage Expression |
24//! |-------------------------|-------------------|
25//! | `column = value`        | `ComparisonExpr`  |
26//! | `column > value`        | `ComparisonExpr`  |
27//! | `a AND b`               | `AndExpr`         |
28//! | `a OR b`                | `OrExpr`          |
29//! | `NOT a`                 | `NotExpr`         |
30//! | `column IN (v1, v2)`    | `InListExpr`      |
31//! | `column BETWEEN a AND b`| `BetweenExpr`     |
32//! | `column LIKE pattern`   | `LikeExpr`        |
33//! | `column IS NULL`        | `NullCheckExpr`   |
34//!
35//! ## Not Pushable (returns None)
36//!
37//! - Function calls (UPPER(col) = 'X')
38//! - Subqueries
39//! - CASE expressions
40//! - Arithmetic expressions
41//! - Column-to-column comparisons
42
43use crate::utils::{extract_column_name, extract_literal_value, flip_operator, infix_to_operator};
44use radixdb_core::Value;
45use radixdb_sql::ast::{self as ast, InfixOperator, PrefixOperator};
46use radixdb_storage::expression::{
47    AndExpr, BetweenExpr, ComparisonExpr, Expression, InListExpr, LikeExpr, NotExpr, NullCheckExpr,
48    OrExpr,
49};
50
51/// Convert an AST expression to a storage expression for predicate pushdown
52///
53/// Returns `Some(expression)` if the expression can be pushed down to storage,
54/// or `None` if it must be evaluated in memory.
55pub fn convert_ast_to_storage_expr(expr: &ast::Expression) -> Option<Box<dyn Expression>> {
56    match expr {
57        // Infix expressions: comparisons and logical operators
58        ast::Expression::Infix(infix) => convert_infix(infix),
59
60        // Prefix expressions: NOT
61        ast::Expression::Prefix(prefix) => convert_prefix(prefix),
62
63        // IN expression
64        ast::Expression::In(in_expr) => convert_in(in_expr),
65
66        // BETWEEN expression
67        ast::Expression::Between(between) => convert_between(between),
68
69        // LIKE expression
70        ast::Expression::Like(like) => convert_like(like),
71
72        // Boolean literal - can be used as constant expression
73        ast::Expression::BooleanLiteral(b) => {
74            // Create a constant true/false expression
75            Some(Box::new(radixdb_storage::expression::ConstBoolExpr::new(
76                b.value,
77            )))
78        }
79
80        // These expressions cannot be pushed down
81        ast::Expression::FunctionCall(_)
82        | ast::Expression::ScalarSubquery(_)
83        | ast::Expression::Exists(_)
84        | ast::Expression::AllAny(_)
85        | ast::Expression::Case(_)
86        | ast::Expression::Cast(_)
87        | ast::Expression::Window(_)
88        | ast::Expression::Parameter(_)
89        | ast::Expression::IntervalLiteral(_)
90        | ast::Expression::BoundValue(_) => None,
91
92        // Simple expressions that don't make sense as filters
93        ast::Expression::Identifier(_)
94        | ast::Expression::QualifiedIdentifier(_)
95        | ast::Expression::IntegerLiteral(_)
96        | ast::Expression::FloatLiteral(_)
97        | ast::Expression::StringLiteral(_)
98        | ast::Expression::NullLiteral(_)
99        | ast::Expression::List(_)
100        | ast::Expression::Distinct(_)
101        | ast::Expression::ExpressionList(_)
102        | ast::Expression::Aliased(_) => None,
103
104        // Table sources and other non-predicate expressions
105        ast::Expression::TableSource(_)
106        | ast::Expression::JoinSource(_)
107        | ast::Expression::SubquerySource(_)
108        | ast::Expression::ValuesSource(_)
109        | ast::Expression::CteReference(_)
110        | ast::Expression::FunctionTableSource(_)
111        | ast::Expression::Star(_)
112        | ast::Expression::QualifiedStar(_)
113        | ast::Expression::Default(_)
114        | ast::Expression::InHashSet(_) => None,
115    }
116}
117
118/// Convert an infix expression (comparison or logical)
119fn convert_infix(infix: &ast::InfixExpression) -> Option<Box<dyn Expression>> {
120    match infix.op_type {
121        // Comparison operators - need column on one side, value on other
122        InfixOperator::Equal
123        | InfixOperator::NotEqual
124        | InfixOperator::LessThan
125        | InfixOperator::LessEqual
126        | InfixOperator::GreaterThan
127        | InfixOperator::GreaterEqual => convert_comparison(infix),
128
129        // Logical operators
130        InfixOperator::And => {
131            let left = convert_ast_to_storage_expr(&infix.left)?;
132            let right = convert_ast_to_storage_expr(&infix.right)?;
133            Some(Box::new(AndExpr::and(left, right)))
134        }
135
136        InfixOperator::Or => {
137            let left = convert_ast_to_storage_expr(&infix.left)?;
138            let right = convert_ast_to_storage_expr(&infix.right)?;
139            Some(Box::new(OrExpr::or(left, right)))
140        }
141
142        // IS NULL / IS NOT NULL
143        InfixOperator::Is | InfixOperator::IsNot => convert_is_null(infix),
144
145        // All other operators can't be pushed down directly
146        _ => None,
147    }
148}
149
150/// Convert a comparison expression (column op value or value op column)
151fn convert_comparison(infix: &ast::InfixExpression) -> Option<Box<dyn Expression>> {
152    // Try column on left, value on right
153    if let Some((column, value)) = try_extract_column_value(&infix.left, &infix.right) {
154        let operator = infix_to_operator(infix.op_type)?;
155        return Some(Box::new(ComparisonExpr::new(column, operator, value)));
156    }
157
158    // Try value on left, column on right (flip the operator)
159    if let Some((column, value)) = try_extract_column_value(&infix.right, &infix.left) {
160        let operator = flip_operator(infix_to_operator(infix.op_type)?);
161        return Some(Box::new(ComparisonExpr::new(column, operator, value)));
162    }
163
164    // Neither pattern matched - can't push down
165    None
166}
167
168/// Try to extract a column name and literal value from two expressions
169fn try_extract_column_value(
170    maybe_column: &ast::Expression,
171    maybe_value: &ast::Expression,
172) -> Option<(String, Value)> {
173    let column = extract_column_name(maybe_column)?;
174    let value = extract_literal_value(maybe_value)?;
175    Some((column, value))
176}
177
178/// Convert IS NULL / IS NOT NULL expression
179fn convert_is_null(infix: &ast::InfixExpression) -> Option<Box<dyn Expression>> {
180    let column = extract_column_name(&infix.left)?;
181
182    // Check if it's IS or IS NOT
183    let is_not = infix.op_type == InfixOperator::IsNot;
184
185    // Check if right side is NULL literal
186    match &*infix.right {
187        ast::Expression::NullLiteral(_) => {
188            if is_not {
189                Some(Box::new(NullCheckExpr::is_not_null(column)))
190            } else {
191                Some(Box::new(NullCheckExpr::is_null(column)))
192            }
193        }
194        _ => None,
195    }
196}
197
198/// Convert a prefix expression (NOT)
199fn convert_prefix(prefix: &ast::PrefixExpression) -> Option<Box<dyn Expression>> {
200    match prefix.op_type {
201        PrefixOperator::Not => {
202            let inner = convert_ast_to_storage_expr(&prefix.right)?;
203            Some(Box::new(NotExpr::new(inner)))
204        }
205        // Arithmetic negation and other operators can't be pushed down
206        _ => None,
207    }
208}
209
210/// Convert an IN expression
211fn convert_in(in_expr: &ast::InExpression) -> Option<Box<dyn Expression>> {
212    let column = extract_column_name(&in_expr.left)?;
213
214    // Extract values from the IN list
215    let values: Option<Vec<Value>> = match &*in_expr.right {
216        ast::Expression::ExpressionList(list) => {
217            list.expressions.iter().map(extract_literal_value).collect()
218        }
219        ast::Expression::List(list) => list.elements.iter().map(extract_literal_value).collect(),
220        _ => return None, // Subquery IN - can't push down
221    };
222
223    let values = values?;
224    if values.is_empty() {
225        return None;
226    }
227
228    let expr = if in_expr.not {
229        InListExpr::not_in(column, values)
230    } else {
231        InListExpr::new(column, values)
232    };
233    Some(Box::new(expr))
234}
235
236/// Convert a BETWEEN expression
237fn convert_between(between: &ast::BetweenExpression) -> Option<Box<dyn Expression>> {
238    let column = extract_column_name(&between.expr)?;
239    let low = extract_literal_value(&between.lower)?;
240    let high = extract_literal_value(&between.upper)?;
241
242    let expr = if between.not {
243        BetweenExpr::not_between(column, low, high)
244    } else {
245        BetweenExpr::new(column, low, high)
246    };
247    Some(Box::new(expr))
248}
249
250/// Convert a LIKE expression
251fn convert_like(like: &ast::LikeExpression) -> Option<Box<dyn Expression>> {
252    let column = extract_column_name(&like.left)?;
253
254    // Extract pattern string
255    let pattern = match &*like.pattern {
256        ast::Expression::StringLiteral(s) => s.value.clone(),
257        _ => return None, // Pattern must be a string literal
258    };
259
260    // Parse operator to determine case-sensitivity and negation
261    let op_upper = like.operator.to_uppercase();
262    let is_not = op_upper.contains("NOT");
263    let is_ilike = op_upper.contains("ILIKE");
264
265    // Note: escape character is not directly supported in our LikeExpr yet
266    // but could be added if needed
267
268    let expr = match (is_not, is_ilike) {
269        (true, true) => LikeExpr::not_ilike(column, pattern),
270        (true, false) => LikeExpr::not_like(column, pattern),
271        (false, true) => LikeExpr::new_ilike(column, pattern),
272        (false, false) => LikeExpr::new(column, pattern),
273    };
274    Some(Box::new(expr))
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    use crate::utils::dummy_token;
281    use radixdb_core::{DataType, Row, Schema, SchemaBuilder};
282    use radixdb_sql::token::TokenType;
283
284    fn test_schema() -> Schema {
285        SchemaBuilder::new("test")
286            .add_primary_key("id", DataType::Integer)
287            .add("name", DataType::Text)
288            .add("age", DataType::Integer)
289            .add_nullable("email", DataType::Text)
290            .build()
291    }
292
293    fn test_row() -> Row {
294        Row::from_values(vec![
295            Value::integer(1),
296            Value::text("Alice"),
297            Value::integer(30),
298            Value::text("alice@example.com"),
299        ])
300    }
301
302    // Helper to create AST identifier
303    fn make_ident(name: &str) -> ast::Expression {
304        ast::Expression::Identifier(ast::Identifier::new(
305            dummy_token(name, TokenType::Identifier),
306            name.to_string(),
307        ))
308    }
309
310    // Helper to create AST integer literal
311    fn make_int(value: i64) -> ast::Expression {
312        ast::Expression::IntegerLiteral(ast::IntegerLiteral {
313            token: dummy_token(&value.to_string(), TokenType::Integer),
314            value,
315        })
316    }
317
318    fn make_float(value: f64) -> ast::Expression {
319        ast::Expression::FloatLiteral(ast::FloatLiteral {
320            token: dummy_token(&value.to_string(), TokenType::Float),
321            value,
322        })
323    }
324
325    // Helper to create AST string literal
326    fn make_str(value: &str) -> ast::Expression {
327        ast::Expression::StringLiteral(ast::StringLiteral {
328            token: dummy_token(value, TokenType::String),
329            value: value.into(),
330            type_hint: None,
331        })
332    }
333
334    // Helper to create AST infix expression
335    fn make_infix(left: ast::Expression, op: &str, right: ast::Expression) -> ast::InfixExpression {
336        ast::InfixExpression::new(
337            dummy_token(op, TokenType::Operator),
338            Box::new(left),
339            op,
340            Box::new(right),
341        )
342    }
343
344    #[test]
345    fn test_convert_simple_equality() {
346        let ast_expr = ast::Expression::Infix(make_infix(make_ident("id"), "=", make_int(1)));
347
348        let storage_expr = convert_ast_to_storage_expr(&ast_expr);
349        assert!(storage_expr.is_some());
350
351        let mut expr = storage_expr.unwrap();
352        let schema = test_schema();
353        expr.prepare_for_schema(&schema);
354
355        let row = test_row();
356        assert!(expr.evaluate(&row).unwrap());
357    }
358
359    #[test]
360    fn test_convert_and_expression() {
361        // id = 1 AND age > 20
362        let left_cond = ast::Expression::Infix(make_infix(make_ident("id"), "=", make_int(1)));
363        let right_cond = ast::Expression::Infix(make_infix(make_ident("age"), ">", make_int(20)));
364        let ast_expr = ast::Expression::Infix(make_infix(left_cond, "AND", right_cond));
365
366        let storage_expr = convert_ast_to_storage_expr(&ast_expr);
367        assert!(storage_expr.is_some());
368
369        let mut expr = storage_expr.unwrap();
370        let schema = test_schema();
371        expr.prepare_for_schema(&schema);
372
373        let row = test_row(); // id=1, age=30
374        assert!(expr.evaluate(&row).unwrap());
375    }
376
377    #[test]
378    fn test_convert_value_on_left() {
379        // 0 < id (should become id > 0)
380        let ast_expr = ast::Expression::Infix(make_infix(make_int(0), "<", make_ident("id")));
381
382        let storage_expr = convert_ast_to_storage_expr(&ast_expr);
383        assert!(storage_expr.is_some());
384
385        let mut expr = storage_expr.unwrap();
386        let schema = test_schema();
387        expr.prepare_for_schema(&schema);
388
389        let row = test_row(); // id=1
390        assert!(expr.evaluate(&row).unwrap()); // 0 < 1
391    }
392
393    #[test]
394    fn test_converted_mixed_numeric_filter_keeps_compiled_dynamic_parity() {
395        const EXACT: i64 = 1_i64 << 53;
396        let schema = SchemaBuilder::new("numeric_boundary")
397            .add("value", DataType::Integer)
398            .build();
399        let row = Row::from_values(vec![Value::Integer(EXACT + 1)]);
400        let ast_expr = ast::Expression::Infix(make_infix(
401            make_ident("value"),
402            "=",
403            make_float(EXACT as f64),
404        ));
405
406        let mut expression = convert_ast_to_storage_expr(&ast_expr).unwrap();
407        expression.prepare_for_schema(&schema);
408        assert!(!expression.evaluate(&row).unwrap());
409        assert!(!expression.evaluate_fast(&row));
410
411        let compiled =
412            radixdb_storage::expression::CompiledFilter::compile(expression.as_ref(), &schema);
413        assert!(compiled.is_fully_compiled());
414        assert!(!compiled.matches(&row));
415        assert!(!compiled.matches_arc_slice(row.as_slice()));
416    }
417
418    #[test]
419    fn test_cannot_convert_function_call() {
420        // Function calls can't be pushed down
421        let ast_expr = ast::Expression::FunctionCall(Box::new(ast::FunctionCall {
422            token: dummy_token("UPPER", TokenType::Identifier),
423            function: "UPPER".into(),
424            arguments: vec![make_ident("name")],
425            is_distinct: false,
426            order_by: vec![],
427            filter: None,
428        }));
429
430        let storage_expr = convert_ast_to_storage_expr(&ast_expr);
431        assert!(storage_expr.is_none());
432    }
433
434    #[test]
435    fn test_convert_string_comparison() {
436        // name = 'Alice'
437        let ast_expr =
438            ast::Expression::Infix(make_infix(make_ident("name"), "=", make_str("Alice")));
439
440        let storage_expr = convert_ast_to_storage_expr(&ast_expr);
441        assert!(storage_expr.is_some());
442
443        let mut expr = storage_expr.unwrap();
444        let schema = test_schema();
445        expr.prepare_for_schema(&schema);
446
447        let row = test_row();
448        assert!(expr.evaluate(&row).unwrap());
449    }
450}
radixdb_executor/expr_converter.rs

radixdb_executor/
expr_converter.rs
