risingwave_frontend/optimizer/plan_expr_visitor/
strong.rs

1// Copyright 2024 RisingWave Labs
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
15use fixedbitset::FixedBitSet;
16
17use crate::expr::{ExprImpl, ExprType, FunctionCall, InputRef};
18
19/// This utilities are with the same definition in calcite.
20/// Utilities for strong predicates.
21/// A predicate is strong (or null-rejecting) with regards to selected subset of inputs
22/// if it is UNKNOWN if all inputs in selected subset are UNKNOWN.
23/// By the way, UNKNOWN is just the boolean form of NULL.
24///
25/// Examples:
26///
27/// UNKNOWN is strong in `[]` (definitely null)
28///
29/// `c = 1` is strong in `[c]` (definitely null if and only if c is null)
30///
31/// `c IS NULL` is not strong (always returns TRUE or FALSE, nevernull)
32///
33/// `p1 AND p2` is strong in `[p1, p2]` (definitely null if either p1 is null or p2 is null)
34///
35/// `p1 OR p2` is strong if p1 and p2 are strong
36
37#[derive(Default)]
38pub struct Strong {
39    null_columns: FixedBitSet,
40}
41
42impl Strong {
43    fn new(null_columns: FixedBitSet) -> Self {
44        Self { null_columns }
45    }
46
47    /// Returns whether the analyzed expression will *definitely* return null if
48    /// all of a given set of input columns are null.
49    /// Note: we could not assume any null-related property for the input expression if `is_null` returns false
50    pub fn is_null(expr: &ExprImpl, null_columns: FixedBitSet) -> bool {
51        let strong = Strong::new(null_columns);
52        strong.is_null_visit(expr)
53    }
54
55    fn is_input_ref_null(&self, input_ref: &InputRef) -> bool {
56        self.null_columns.contains(input_ref.index())
57    }
58
59    fn is_null_visit(&self, expr: &ExprImpl) -> bool {
60        match expr {
61            ExprImpl::InputRef(input_ref) => self.is_input_ref_null(input_ref),
62            ExprImpl::Literal(literal) => literal.get_data().is_none(),
63            ExprImpl::FunctionCall(func_call) => self.is_null_function_call(func_call),
64            ExprImpl::FunctionCallWithLambda(_) => false,
65            ExprImpl::AggCall(_) => false,
66            ExprImpl::Subquery(_) => false,
67            ExprImpl::CorrelatedInputRef(_) => false,
68            ExprImpl::TableFunction(_) => false,
69            ExprImpl::WindowFunction(_) => false,
70            ExprImpl::UserDefinedFunction(_) => false,
71            ExprImpl::Parameter(_) => false,
72            ExprImpl::Now(_) | ExprImpl::SecretRef(_) => false,
73        }
74    }
75
76    fn is_null_function_call(&self, func_call: &FunctionCall) -> bool {
77        match func_call.func_type() {
78            // NOT NULL: This kind of expression is never null. No need to look at its arguments, if it has any.
79            ExprType::IsNull
80            | ExprType::IsNotNull
81            | ExprType::IsDistinctFrom
82            | ExprType::IsNotDistinctFrom
83            | ExprType::IsTrue
84            | ExprType::QuoteNullable
85            | ExprType::IsNotTrue
86            | ExprType::IsFalse
87            | ExprType::IsNotFalse
88            | ExprType::CheckNotNull => false,
89            // ANY: This kind of expression is null if and only if at least one of its arguments is null.
90            ExprType::Not
91            | ExprType::Equal
92            | ExprType::NotEqual
93            | ExprType::LessThan
94            | ExprType::LessThanOrEqual
95            | ExprType::GreaterThan
96            | ExprType::GreaterThanOrEqual
97            | ExprType::Like
98            | ExprType::Add
99            | ExprType::AddWithTimeZone
100            | ExprType::Subtract
101            | ExprType::Multiply
102            | ExprType::Modulus
103            | ExprType::Divide
104            | ExprType::Cast
105            | ExprType::Trim
106            | ExprType::Ltrim
107            | ExprType::Rtrim
108            | ExprType::Ceil
109            | ExprType::Floor
110            | ExprType::Extract
111            | ExprType::L2Distance
112            | ExprType::CosineDistance
113            | ExprType::L1Distance
114            | ExprType::InnerProduct
115            | ExprType::VecConcat
116            | ExprType::L2Norm
117            | ExprType::L2Normalize
118            | ExprType::Subvector
119            | ExprType::Greatest
120            | ExprType::Least => self.any_null(func_call),
121            // ALL: This kind of expression is null if and only if all of its arguments are null.
122            ExprType::And | ExprType::Or | ExprType::Coalesce => self.all_null(func_call),
123            // TODO: Function like case when is important but current its structure is complicated, so we need to implement it later if necessary.
124            // Assume that any other expressions cannot be simplified.
125            #[expect(deprecated)]
126            ExprType::In
127            | ExprType::Some
128            | ExprType::All
129            | ExprType::BitwiseAnd
130            | ExprType::BitwiseOr
131            | ExprType::BitwiseXor
132            | ExprType::BitwiseNot
133            | ExprType::BitwiseShiftLeft
134            | ExprType::BitwiseShiftRight
135            | ExprType::DatePart
136            | ExprType::TumbleStart
137            | ExprType::MakeDate
138            | ExprType::MakeTime
139            | ExprType::MakeTimestamp
140            | ExprType::SecToTimestamptz
141            | ExprType::AtTimeZone
142            | ExprType::DateTrunc
143            | ExprType::DateBin
144            | ExprType::CharToTimestamptz
145            | ExprType::CharToDate
146            | ExprType::CastWithTimeZone
147            | ExprType::SubtractWithTimeZone
148            | ExprType::MakeTimestamptz
149            | ExprType::Substr
150            | ExprType::Length
151            | ExprType::ILike
152            | ExprType::SimilarToEscape
153            | ExprType::Upper
154            | ExprType::Lower
155            | ExprType::Replace
156            | ExprType::Position
157            | ExprType::Case
158            | ExprType::ConstantLookup
159            | ExprType::RoundDigit
160            | ExprType::Round
161            | ExprType::Ascii
162            | ExprType::Translate
163            | ExprType::Concat
164            | ExprType::ConcatVariadic
165            | ExprType::ConcatWs
166            | ExprType::ConcatWsVariadic
167            | ExprType::Abs
168            | ExprType::SplitPart
169            | ExprType::ToChar
170            | ExprType::Md5
171            | ExprType::CharLength
172            | ExprType::Repeat
173            | ExprType::ConcatOp
174            | ExprType::ByteaConcatOp
175            | ExprType::BoolOut
176            | ExprType::OctetLength
177            | ExprType::BitLength
178            | ExprType::Overlay
179            | ExprType::RegexpMatch
180            | ExprType::RegexpReplace
181            | ExprType::RegexpCount
182            | ExprType::RegexpSplitToArray
183            | ExprType::RegexpEq
184            | ExprType::Pow
185            | ExprType::Exp
186            | ExprType::Chr
187            | ExprType::StartsWith
188            | ExprType::Initcap
189            | ExprType::Lpad
190            | ExprType::Rpad
191            | ExprType::Reverse
192            | ExprType::Strpos
193            | ExprType::ToAscii
194            | ExprType::ToHex
195            | ExprType::QuoteIdent
196            | ExprType::QuoteLiteral
197            | ExprType::Sin
198            | ExprType::Cos
199            | ExprType::Tan
200            | ExprType::Cot
201            | ExprType::Asin
202            | ExprType::Acos
203            | ExprType::Acosd
204            | ExprType::Atan
205            | ExprType::Atan2
206            | ExprType::Atand
207            | ExprType::Atan2d
208            | ExprType::Sind
209            | ExprType::Cosd
210            | ExprType::Cotd
211            | ExprType::Tand
212            | ExprType::Asind
213            | ExprType::Sqrt
214            | ExprType::Degrees
215            | ExprType::Radians
216            | ExprType::Cosh
217            | ExprType::Tanh
218            | ExprType::Coth
219            | ExprType::Asinh
220            | ExprType::Acosh
221            | ExprType::Atanh
222            | ExprType::Sinh
223            | ExprType::Trunc
224            | ExprType::Ln
225            | ExprType::Log10
226            | ExprType::Cbrt
227            | ExprType::Sign
228            | ExprType::Scale
229            | ExprType::MinScale
230            | ExprType::TrimScale
231            | ExprType::Gamma
232            | ExprType::Lgamma
233            | ExprType::Encode
234            | ExprType::Decode
235            | ExprType::Sha1
236            | ExprType::Sha224
237            | ExprType::Sha256
238            | ExprType::Sha384
239            | ExprType::Sha512
240            | ExprType::Crc32
241            | ExprType::Crc32c
242            | ExprType::GetBit
243            | ExprType::GetByte
244            | ExprType::SetBit
245            | ExprType::SetByte
246            | ExprType::BitCount
247            | ExprType::Hmac
248            | ExprType::SecureCompare
249            | ExprType::Left
250            | ExprType::Right
251            | ExprType::Format
252            | ExprType::FormatVariadic
253            | ExprType::PgwireSend
254            | ExprType::PgwireRecv
255            | ExprType::ConvertFrom
256            | ExprType::ConvertTo
257            | ExprType::Decrypt
258            | ExprType::Encrypt
259            | ExprType::Neg
260            | ExprType::Field
261            | ExprType::Array
262            | ExprType::ArrayAccess
263            | ExprType::Row
264            | ExprType::ArrayToString
265            | ExprType::ArrayRangeAccess
266            | ExprType::ArrayCat
267            | ExprType::ArrayAppend
268            | ExprType::ArrayPrepend
269            | ExprType::FormatType
270            | ExprType::ArrayDistinct
271            | ExprType::ArrayLength
272            | ExprType::Cardinality
273            | ExprType::ArrayRemove
274            | ExprType::ArrayPositions
275            | ExprType::TrimArray
276            | ExprType::StringToArray
277            | ExprType::ArrayPosition
278            | ExprType::ArrayReplace
279            | ExprType::ArrayDims
280            | ExprType::ArrayTransform
281            | ExprType::ArrayMin
282            | ExprType::ArrayMax
283            | ExprType::ArraySum
284            | ExprType::ArraySort
285            | ExprType::ArrayReverse
286            | ExprType::ArrayContains
287            | ExprType::ArrayContained
288            | ExprType::ArrayOverlaps
289            | ExprType::ArrayFlatten
290            | ExprType::HexToInt256
291            | ExprType::JsonbAccess
292            | ExprType::JsonbAccessStr
293            | ExprType::JsonbExtractPath
294            | ExprType::JsonbExtractPathVariadic
295            | ExprType::JsonbExtractPathText
296            | ExprType::JsonbExtractPathTextVariadic
297            | ExprType::JsonbTypeof
298            | ExprType::JsonbArrayLength
299            | ExprType::IsJson
300            | ExprType::JsonbConcat
301            | ExprType::JsonbObject
302            | ExprType::JsonbPretty
303            | ExprType::JsonbContains
304            | ExprType::JsonbContained
305            | ExprType::JsonbExists
306            | ExprType::JsonbExistsAny
307            | ExprType::JsonbExistsAll
308            | ExprType::JsonbDeletePath
309            | ExprType::JsonbStripNulls
310            | ExprType::ToJsonb
311            | ExprType::JsonbBuildArray
312            | ExprType::JsonbBuildArrayVariadic
313            | ExprType::JsonbBuildObject
314            | ExprType::JsonbBuildObjectVariadic
315            | ExprType::JsonbPathExists
316            | ExprType::JsonbPathMatch
317            | ExprType::JsonbPathQueryArray
318            | ExprType::JsonbPathQueryFirst
319            | ExprType::JsonbPopulateRecord
320            | ExprType::JsonbToArray
321            | ExprType::JsonbToRecord
322            | ExprType::JsonbSet
323            | ExprType::JsonbPopulateMap
324            | ExprType::ToVariant
325            | ExprType::VariantGet
326            | ExprType::TryVariantGet
327            | ExprType::VariantTypeof
328            | ExprType::MapFromEntries
329            | ExprType::MapAccess
330            | ExprType::MapKeys
331            | ExprType::MapValues
332            | ExprType::MapEntries
333            | ExprType::MapFromKeyValues
334            | ExprType::MapCat
335            | ExprType::MapContains
336            | ExprType::MapDelete
337            | ExprType::MapFilter
338            | ExprType::MapInsert
339            | ExprType::MapLength
340            | ExprType::Vnode
341            | ExprType::VnodeUser
342            | ExprType::TestFeature
343            | ExprType::License
344            | ExprType::Proctime
345            | ExprType::PgSleep
346            | ExprType::PgSleepFor
347            | ExprType::PgSleepUntil
348            | ExprType::CastRegclass
349            | ExprType::PgGetIndexdef
350            | ExprType::ColDescription
351            | ExprType::PgGetViewdef
352            | ExprType::PgGetUserbyid
353            | ExprType::PgIndexesSize
354            | ExprType::PgRelationSize
355            | ExprType::PgGetSerialSequence
356            | ExprType::PgIndexColumnHasProperty
357            | ExprType::PgIsInRecovery
358            | ExprType::PgTableIsVisible
359            | ExprType::RwRecoveryStatus
360            | ExprType::RwClusterId
361            | ExprType::RwFragmentVnodes
362            | ExprType::RwActorVnodes
363            | ExprType::IcebergTransform
364            | ExprType::HasTablePrivilege
365            | ExprType::HasFunctionPrivilege
366            | ExprType::HasAnyColumnPrivilege
367            | ExprType::HasSchemaPrivilege
368            | ExprType::InetAton
369            | ExprType::InetNtoa
370            | ExprType::CompositeCast
371            | ExprType::RwEpochToTs
372            | ExprType::OpenaiEmbedding
373            | ExprType::HasDatabasePrivilege
374            | ExprType::Random
375            | ExprType::ClockTimestamp
376            | ExprType::GenRandomUuid => false,
377            ExprType::Unspecified => unreachable!(),
378        }
379    }
380
381    fn any_null(&self, func_call: &FunctionCall) -> bool {
382        func_call
383            .inputs()
384            .iter()
385            .any(|expr| self.is_null_visit(expr))
386    }
387
388    fn all_null(&self, func_call: &FunctionCall) -> bool {
389        func_call
390            .inputs()
391            .iter()
392            .all(|expr| self.is_null_visit(expr))
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use risingwave_common::types::DataType;
399
400    use super::*;
401    use crate::expr::ExprImpl::Literal;
402
403    #[test]
404    fn test_literal() {
405        let null_columns = FixedBitSet::with_capacity(1);
406        let expr = Literal(crate::expr::Literal::new(None, DataType::Varchar).into());
407        assert!(Strong::is_null(&expr, null_columns.clone()));
408
409        let expr = Literal(
410            crate::expr::Literal::new(Some("test".to_owned().into()), DataType::Varchar).into(),
411        );
412        assert!(!Strong::is_null(&expr, null_columns));
413    }
414
415    #[test]
416    fn test_input_ref1() {
417        let null_columns = FixedBitSet::with_capacity(2);
418        let expr = InputRef::new(0, DataType::Varchar).into();
419        assert!(!Strong::is_null(&expr, null_columns.clone()));
420
421        let expr = InputRef::new(1, DataType::Varchar).into();
422        assert!(!Strong::is_null(&expr, null_columns));
423    }
424
425    #[test]
426    fn test_input_ref2() {
427        let mut null_columns = FixedBitSet::with_capacity(2);
428        null_columns.insert(0);
429        null_columns.insert(1);
430        let expr = InputRef::new(0, DataType::Varchar).into();
431        assert!(Strong::is_null(&expr, null_columns.clone()));
432
433        let expr = InputRef::new(1, DataType::Varchar).into();
434        assert!(Strong::is_null(&expr, null_columns));
435    }
436
437    #[test]
438    fn test_c1_equal_1_or_c2_is_null() {
439        let mut null_columns = FixedBitSet::with_capacity(2);
440        null_columns.insert(0);
441        let expr = FunctionCall::new_unchecked(
442            ExprType::Or,
443            vec![
444                FunctionCall::new_unchecked(
445                    ExprType::Equal,
446                    vec![
447                        InputRef::new(0, DataType::Int64).into(),
448                        Literal(crate::expr::Literal::new(Some(1.into()), DataType::Int32).into()),
449                    ],
450                    DataType::Boolean,
451                )
452                .into(),
453                FunctionCall::new_unchecked(
454                    ExprType::IsNull,
455                    vec![InputRef::new(1, DataType::Int64).into()],
456                    DataType::Boolean,
457                )
458                .into(),
459            ],
460            DataType::Boolean,
461        )
462        .into();
463        assert!(!Strong::is_null(&expr, null_columns));
464    }
465
466    #[test]
467    fn test_divide() {
468        let mut null_columns = FixedBitSet::with_capacity(2);
469        null_columns.insert(0);
470        null_columns.insert(1);
471        let expr = FunctionCall::new_unchecked(
472            ExprType::Divide,
473            vec![
474                InputRef::new(0, DataType::Decimal).into(),
475                InputRef::new(1, DataType::Decimal).into(),
476            ],
477            DataType::Varchar,
478        )
479        .into();
480        assert!(Strong::is_null(&expr, null_columns));
481    }
482
483    /// generate a test case for (0.8 * sum / count) where sum is null and count is not null
484    #[test]
485    fn test_multiply_divide() {
486        let mut null_columns = FixedBitSet::with_capacity(2);
487        null_columns.insert(0);
488        let expr = FunctionCall::new_unchecked(
489            ExprType::Multiply,
490            vec![
491                Literal(crate::expr::Literal::new(Some(0.8f64.into()), DataType::Float64).into()),
492                FunctionCall::new_unchecked(
493                    ExprType::Divide,
494                    vec![
495                        InputRef::new(0, DataType::Decimal).into(),
496                        InputRef::new(1, DataType::Decimal).into(),
497                    ],
498                    DataType::Decimal,
499                )
500                .into(),
501            ],
502            DataType::Decimal,
503        )
504        .into();
505        assert!(Strong::is_null(&expr, null_columns));
506    }
507
508    /// generate test cases for is not null
509    macro_rules! gen_test {
510        ($func:ident, $expr:expr, $expected:expr) => {
511            #[test]
512            fn $func() {
513                let null_columns = FixedBitSet::with_capacity(2);
514                let expr = $expr;
515                assert_eq!(Strong::is_null(&expr, null_columns), $expected);
516            }
517        };
518    }
519
520    gen_test!(
521        test_is_not_null,
522        FunctionCall::new_unchecked(
523            ExprType::IsNotNull,
524            vec![InputRef::new(0, DataType::Varchar).into()],
525            DataType::Varchar
526        )
527        .into(),
528        false
529    );
530    gen_test!(
531        test_is_null,
532        FunctionCall::new_unchecked(
533            ExprType::IsNull,
534            vec![InputRef::new(0, DataType::Varchar).into()],
535            DataType::Varchar
536        )
537        .into(),
538        false
539    );
540    gen_test!(
541        test_is_distinct_from,
542        FunctionCall::new_unchecked(
543            ExprType::IsDistinctFrom,
544            vec![
545                InputRef::new(0, DataType::Varchar).into(),
546                InputRef::new(1, DataType::Varchar).into()
547            ],
548            DataType::Varchar
549        )
550        .into(),
551        false
552    );
553    gen_test!(
554        test_is_not_distinct_from,
555        FunctionCall::new_unchecked(
556            ExprType::IsNotDistinctFrom,
557            vec![
558                InputRef::new(0, DataType::Varchar).into(),
559                InputRef::new(1, DataType::Varchar).into()
560            ],
561            DataType::Varchar
562        )
563        .into(),
564        false
565    );
566    gen_test!(
567        test_is_true,
568        FunctionCall::new_unchecked(
569            ExprType::IsTrue,
570            vec![InputRef::new(0, DataType::Varchar).into()],
571            DataType::Varchar
572        )
573        .into(),
574        false
575    );
576    gen_test!(
577        test_is_not_true,
578        FunctionCall::new_unchecked(
579            ExprType::IsNotTrue,
580            vec![InputRef::new(0, DataType::Varchar).into()],
581            DataType::Varchar
582        )
583        .into(),
584        false
585    );
586    gen_test!(
587        test_is_false,
588        FunctionCall::new_unchecked(
589            ExprType::IsFalse,
590            vec![InputRef::new(0, DataType::Varchar).into()],
591            DataType::Varchar
592        )
593        .into(),
594        false
595    );
596}
risingwave_frontend/optimizer/plan_expr_visitor/strong.rs

risingwave_frontend/optimizer/plan_expr_visitor/
strong.rs
