16728097825

Committed 04 Aug 2025 04:00PM UTC coverage: 48.355% (-35.1%) from 83.429%

Build # 16728097825

Build Type

Pull #4108

github

Committed by

web-flow

Commit Message

Merge 1b2d27fd8 into 649ba9576

Pull Request Pull Request #4108: perf[vortex-array]: use all_valid instead of `invalid_count() == 0`

Coverage Stats

1 of 1 new or added line in 1 file covered. (100.0%)

11596 existing lines in 378 files now uncovered.

18635 of 38538 relevant lines covered (48.35%)

151786.4 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

61.18

/vortex-expr/src/exprs/list_contains.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::fmt::{Debug, Display, Formatter};
use std::hash::Hash;

use vortex_array::compute::list_contains as compute_list_contains;
use vortex_array::{ArrayRef, DeserializeMetadata, EmptyMetadata};
use vortex_dtype::DType;
use vortex_error::{VortexResult, vortex_bail};

use crate::{
    AnalysisExpr, ExprEncodingRef, ExprId, ExprRef, IntoExpr, LiteralVTable, Scope, StatsCatalog,
    VTable, and, gt, lit, lt, or, vtable,
};

vtable!(ListContains);

#[allow(clippy::derived_hash_with_manual_eq)]
#[derive(Debug, Clone, Hash, Eq)]
pub struct ListContainsExpr {
    list: ExprRef,
    value: ExprRef,
}

impl PartialEq for ListContainsExpr {
    fn eq(&self, other: &Self) -> bool {
        self.list.eq(&other.list) && self.value.eq(&other.value)
    }
}

pub struct ListContainsExprEncoding;

impl VTable for ListContainsVTable {
    type Expr = ListContainsExpr;
    type Encoding = ListContainsExprEncoding;
    type Metadata = EmptyMetadata;

    fn id(_encoding: &Self::Encoding) -> ExprId {
        ExprId::new_ref("list_contains")
    }

    fn encoding(_expr: &Self::Expr) -> ExprEncodingRef {
        ExprEncodingRef::new_ref(ListContainsExprEncoding.as_ref())
    }

    fn metadata(_expr: &Self::Expr) -> Option<Self::Metadata> {
        Some(EmptyMetadata)
    }

    fn children(expr: &Self::Expr) -> Vec<&ExprRef> {
        vec![&expr.list, &expr.value]
    }

    fn with_children(_expr: &Self::Expr, children: Vec<ExprRef>) -> VortexResult<Self::Expr> {
        Ok(ListContainsExpr::new(
            children[0].clone(),
            children[1].clone(),
        ))
    }

    fn build(
        _encoding: &Self::Encoding,
        _metadata: &<Self::Metadata as DeserializeMetadata>::Output,
        children: Vec<ExprRef>,
    ) -> VortexResult<Self::Expr> {
        if children.len() != 2 {
            vortex_bail!(
                "ListContains expression must have exactly 2 children, got {}",
                children.len()
            );
        }
        Ok(ListContainsExpr::new(
            children[0].clone(),
            children[1].clone(),
        ))
    }

    fn evaluate(expr: &Self::Expr, scope: &Scope) -> VortexResult<ArrayRef> {
        compute_list_contains(
            expr.list.evaluate(scope)?.as_ref(),
            expr.value.evaluate(scope)?.as_ref(),
        )
    }

    fn return_dtype(expr: &Self::Expr, scope: &DType) -> VortexResult<DType> {
        Ok(DType::Bool(
            expr.list.return_dtype(scope)?.nullability()
                | expr.value.return_dtype(scope)?.nullability(),
        ))
    }
}

impl ListContainsExpr {
    pub fn new(list: ExprRef, value: ExprRef) -> Self {
        Self { list, value }
    }

    pub fn new_expr(list: ExprRef, value: ExprRef) -> ExprRef {
        Self::new(list, value).into_expr()
    }

    pub fn value(&self) -> &ExprRef {
        &self.value
    }
}

pub fn list_contains(list: ExprRef, value: ExprRef) -> ExprRef {
    ListContainsExpr::new(list, value).into_expr()
}

impl Display for ListContainsExpr {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "contains({}, {})", &self.list, &self.value)
    }
}

impl AnalysisExpr for ListContainsExpr {
    // falsification(contains([1,2,5], x)) =>
    //   falsification(x != 1) and falsification(x != 2) and falsification(x != 5)

    fn stat_falsification(&self, catalog: &mut dyn StatsCatalog) -> Option<ExprRef> {
        let min = self.list.min(catalog)?;
        let max = self.list.max(catalog)?;
        // If the list is constant when we can compare each element to the value
        if min == max {
            let list_ = min
                .as_opt::<LiteralVTable>()
                .and_then(|l| l.value().as_list_opt())
                .and_then(|l| l.elements())?;
            if list_.is_empty() {
                // contains([], x) is always false.
                return Some(lit(true));
            }
            let value_max = self.value.max(catalog)?;
            let value_min = self.value.min(catalog)?;

            return list_
                .iter()
                .map(move |v| {
                    or(
                        lt(value_max.clone(), lit(v.clone())),
                        gt(value_min.clone(), lit(v.clone())),
                    )
                })
                .reduce(and);
        }

        None
    }
}

#[cfg(test)]
mod tests {
    use vortex_array::arrays::{BoolArray, BooleanBuffer, ListArray, PrimitiveArray};
    use vortex_array::stats::Stat;
    use vortex_array::validity::Validity;
    use vortex_array::{Array, ArrayRef, IntoArray};
    use vortex_dtype::PType::I32;
    use vortex_dtype::{DType, Field, FieldPath, FieldPathSet, Nullability, StructFields};
    use vortex_scalar::Scalar;
    use vortex_utils::aliases::hash_map::HashMap;

    use crate::list_contains::list_contains;
    use crate::pruning::checked_pruning_expr;
    use crate::{Arc, HashSet, Scope, and, col, get_item, gt, lit, lt, or, root};

    fn test_array() -> ArrayRef {
        ListArray::try_new(
            PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2, 2, 2, 3, 3, 3]).into_array(),
            PrimitiveArray::from_iter(vec![0, 5, 10]).into_array(),
            Validity::AllValid,
        )
        .unwrap()
        .into_array()
    }

    #[test]
    pub fn test_one() {
        let arr = test_array();

        let expr = list_contains(root(), lit(1));
        let item = expr.evaluate(&Scope::new(arr)).unwrap();

        assert_eq!(
            item.scalar_at(0).unwrap(),
            Scalar::bool(true, Nullability::Nullable)
        );
        assert_eq!(
            item.scalar_at(1).unwrap(),
            Scalar::bool(false, Nullability::Nullable)
        );
    }

    #[test]
    pub fn test_all() {
        let arr = test_array();

        let expr = list_contains(root(), lit(2));
        let item = expr.evaluate(&Scope::new(arr)).unwrap();

        assert_eq!(
            item.scalar_at(0).unwrap(),
            Scalar::bool(true, Nullability::Nullable)
        );
        assert_eq!(
            item.scalar_at(1).unwrap(),
            Scalar::bool(true, Nullability::Nullable)
        );
    }

    #[test]
    pub fn test_none() {
        let arr = test_array();

        let expr = list_contains(root(), lit(4));
        let item = expr.evaluate(&Scope::new(arr)).unwrap();

        assert_eq!(
            item.scalar_at(0).unwrap(),
            Scalar::bool(false, Nullability::Nullable)
        );
        assert_eq!(
            item.scalar_at(1).unwrap(),
            Scalar::bool(false, Nullability::Nullable)
        );
    }

    #[test]
    pub fn test_empty() {
        let arr = ListArray::try_new(
            PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2]).into_array(),
            PrimitiveArray::from_iter(vec![0, 5, 5]).into_array(),
            Validity::AllValid,
        )
        .unwrap()
        .into_array();

        let expr = list_contains(root(), lit(2));
        let item = expr.evaluate(&Scope::new(arr)).unwrap();

        assert_eq!(
            item.scalar_at(0).unwrap(),
            Scalar::bool(true, Nullability::Nullable)
        );
        assert_eq!(
            item.scalar_at(1).unwrap(),
            Scalar::bool(false, Nullability::Nullable)
        );
    }

    #[test]
    pub fn test_nullable() {
        let arr = ListArray::try_new(
            PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2]).into_array(),
            PrimitiveArray::from_iter(vec![0, 5, 5]).into_array(),
            Validity::Array(BoolArray::from(BooleanBuffer::from(vec![true, false])).into_array()),
        )
        .unwrap()
        .into_array();

        let expr = list_contains(root(), lit(2));
        let item = expr.evaluate(&Scope::new(arr)).unwrap();

        assert_eq!(
            item.scalar_at(0).unwrap(),
            Scalar::bool(true, Nullability::Nullable)
        );
        assert!(!item.is_valid(1).unwrap());
    }

    #[test]
    pub fn test_return_type() {
        let scope = DType::Struct(
            StructFields::new(
                ["array"].into(),
                vec![DType::List(
                    Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
                    Nullability::Nullable,
                )],
            ),
            Nullability::NonNullable,
        );

        let expr = list_contains(get_item("array", root()), lit(2));

        // Expect nullable, although scope is non-nullable
        assert_eq!(
            expr.return_dtype(&scope).unwrap(),
            DType::Bool(Nullability::Nullable)
        );
    }

    #[test]
    pub fn list_falsification() {
        let expr = list_contains(
            lit(Scalar::list(
                Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
                vec![1.into(), 2.into(), 3.into()],
                Nullability::NonNullable,
            )),
            col("a"),
        );

        let (expr, st) = checked_pruning_expr(
            &expr,
            &FieldPathSet::from_iter([
                FieldPath::from_iter([Field::Name("a".into()), Field::Name("max".into())]),
                FieldPath::from_iter([Field::Name("a".into()), Field::Name("min".into())]),
            ]),
        )
        .unwrap();

        assert_eq!(
            &expr,
            &and(
                and(
                    or(lt(col("a_max"), lit(1i32)), gt(col("a_min"), lit(1i32)),),
                    or(lt(col("a_max"), lit(2i32)), gt(col("a_min"), lit(2i32)),)
                ),
                or(lt(col("a_max"), lit(3i32)), gt(col("a_min"), lit(3i32)),)
            )
        );

        assert_eq!(
            st.map(),
            &HashMap::from_iter([(
                FieldPath::from_name("a"),
                HashSet::from([Stat::Min, Stat::Max])
            )])
        );
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::{Debug, Display, Formatter};
5	use std::hash::Hash;
6
7	use vortex_array::compute::list_contains as compute_list_contains;
8	use vortex_array::{ArrayRef, DeserializeMetadata, EmptyMetadata};
9	use vortex_dtype::DType;
10	use vortex_error::{VortexResult, vortex_bail};
11
12	use crate::{
13	AnalysisExpr, ExprEncodingRef, ExprId, ExprRef, IntoExpr, LiteralVTable, Scope, StatsCatalog,
14	VTable, and, gt, lit, lt, or, vtable,
15	};
16
17	vtable!(ListContains);
18
19	#[allow(clippy::derived_hash_with_manual_eq)]
20	#[derive(Debug, Clone, Hash, Eq)]
21	pub struct ListContainsExpr {
22	list: ExprRef,
23	value: ExprRef,
24	}
25
26	impl PartialEq for ListContainsExpr {
27	fn eq(&self, other: &Self) -> bool {	558✔
28	self.list.eq(&other.list) && self.value.eq(&other.value)	558✔
29	}	558✔
30	}
31
32	pub struct ListContainsExprEncoding;
33
34	impl VTable for ListContainsVTable {
35	type Expr = ListContainsExpr;
36	type Encoding = ListContainsExprEncoding;
37	type Metadata = EmptyMetadata;
38
39	fn id(_encoding: &Self::Encoding) -> ExprId {	22✔
40	ExprId::new_ref("list_contains")	22✔
41	}	22✔
42
UNCOV 43	fn encoding(_expr: &Self::Expr) -> ExprEncodingRef {	×
UNCOV 44	ExprEncodingRef::new_ref(ListContainsExprEncoding.as_ref())	×
UNCOV 45	}	×
46
UNCOV 47	fn metadata(_expr: &Self::Expr) -> Option<Self::Metadata> {	×
UNCOV 48	Some(EmptyMetadata)	×
UNCOV 49	}	×
50
51	fn children(expr: &Self::Expr) -> Vec<&ExprRef> {	962✔
52	vec![&expr.list, &expr.value]	962✔
53	}	962✔
54
55	fn with_children(_expr: &Self::Expr, children: Vec<ExprRef>) -> VortexResult<Self::Expr> {	78✔
56	Ok(ListContainsExpr::new(	78✔
57	children[0].clone(),	78✔
58	children[1].clone(),	78✔
59	))	78✔
60	}	78✔
61
UNCOV 62	fn build(	×
UNCOV 63	_encoding: &Self::Encoding,	×
UNCOV 64	_metadata: &<Self::Metadata as DeserializeMetadata>::Output,	×
UNCOV 65	children: Vec<ExprRef>,	×
UNCOV 66	) -> VortexResult<Self::Expr> {	×
UNCOV 67	if children.len() != 2 {	×
68	vortex_bail!(	×
69	"ListContains expression must have exactly 2 children, got {}",	×
70	children.len()	×
71	);
UNCOV 72	}	×
UNCOV 73	Ok(ListContainsExpr::new(	×
UNCOV 74	children[0].clone(),	×
UNCOV 75	children[1].clone(),	×
UNCOV 76	))	×
UNCOV 77	}	×
78
79	fn evaluate(expr: &Self::Expr, scope: &Scope) -> VortexResult<ArrayRef> {	58✔
80	compute_list_contains(	58✔
81	expr.list.evaluate(scope)?.as_ref(),	58✔
82	expr.value.evaluate(scope)?.as_ref(),	58✔
83	)
84	}	58✔
85
86	fn return_dtype(expr: &Self::Expr, scope: &DType) -> VortexResult<DType> {	110✔
87	Ok(DType::Bool(
88	expr.list.return_dtype(scope)?.nullability()	110✔
89	\| expr.value.return_dtype(scope)?.nullability(),	110✔
90	))
91	}	110✔
92	}
93
94	impl ListContainsExpr {
95	pub fn new(list: ExprRef, value: ExprRef) -> Self {	104✔
96	Self { list, value }	104✔
97	}	104✔
98
99	pub fn new_expr(list: ExprRef, value: ExprRef) -> ExprRef {	×
100	Self::new(list, value).into_expr()	×
101	}	×
102
103	pub fn value(&self) -> &ExprRef {	×
104	&self.value	×
105	}	×
106	}
107
108	pub fn list_contains(list: ExprRef, value: ExprRef) -> ExprRef {	26✔
109	ListContainsExpr::new(list, value).into_expr()	26✔
110	}	26✔
111
112	impl Display for ListContainsExpr {
113	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
114	write!(f, "contains({}, {})", &self.list, &self.value)	×
115	}	×
116	}
117
118	impl AnalysisExpr for ListContainsExpr {
119	// falsification(contains([1,2,5], x)) =>
120	// falsification(x != 1) and falsification(x != 2) and falsification(x != 5)
121
122	fn stat_falsification(&self, catalog: &mut dyn StatsCatalog) -> Option<ExprRef> {	52✔
123	let min = self.list.min(catalog)?;	52✔
124	let max = self.list.max(catalog)?;	52✔
125	// If the list is constant when we can compare each element to the value
126	if min == max {	52✔
127	let list_ = min	52✔
128	.as_opt::<LiteralVTable>()	52✔
129	.and_then(\|l\| l.value().as_list_opt())	52✔
130	.and_then(\|l\| l.elements())?;	52✔
131	if list_.is_empty() {	52✔
132	// contains([], x) is always false.
133	return Some(lit(true));	×
134	}	52✔
135	let value_max = self.value.max(catalog)?;	52✔
136	let value_min = self.value.min(catalog)?;	52✔
137
138	return list_	52✔
139	.iter()	52✔
140	.map(move \|v\| {	816✔
141	or(	816✔
142	lt(value_max.clone(), lit(v.clone())),	816✔
143	gt(value_min.clone(), lit(v.clone())),	816✔
144	)	816✔
145	})	816✔
146	.reduce(and);	52✔
147	}	×
148
149	None	×
150	}	52✔
151	}
152
153	#[cfg(test)]
154	mod tests {
155	use vortex_array::arrays::{BoolArray, BooleanBuffer, ListArray, PrimitiveArray};
156	use vortex_array::stats::Stat;
157	use vortex_array::validity::Validity;
158	use vortex_array::{Array, ArrayRef, IntoArray};
159	use vortex_dtype::PType::I32;
160	use vortex_dtype::{DType, Field, FieldPath, FieldPathSet, Nullability, StructFields};
161	use vortex_scalar::Scalar;
162	use vortex_utils::aliases::hash_map::HashMap;
163
164	use crate::list_contains::list_contains;
165	use crate::pruning::checked_pruning_expr;
166	use crate::{Arc, HashSet, Scope, and, col, get_item, gt, lit, lt, or, root};
167
168	fn test_array() -> ArrayRef {
169	ListArray::try_new(
170	PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2, 2, 2, 3, 3, 3]).into_array(),
171	PrimitiveArray::from_iter(vec![0, 5, 10]).into_array(),
172	Validity::AllValid,
173	)
174	.unwrap()
175	.into_array()
176	}
177
178	#[test]
179	pub fn test_one() {
180	let arr = test_array();
181
182	let expr = list_contains(root(), lit(1));
183	let item = expr.evaluate(&Scope::new(arr)).unwrap();
184
185	assert_eq!(
186	item.scalar_at(0).unwrap(),
187	Scalar::bool(true, Nullability::Nullable)
188	);
189	assert_eq!(
190	item.scalar_at(1).unwrap(),
191	Scalar::bool(false, Nullability::Nullable)
192	);
193	}
194
195	#[test]
196	pub fn test_all() {
197	let arr = test_array();
198
199	let expr = list_contains(root(), lit(2));
200	let item = expr.evaluate(&Scope::new(arr)).unwrap();
201
202	assert_eq!(
203	item.scalar_at(0).unwrap(),
204	Scalar::bool(true, Nullability::Nullable)
205	);
206	assert_eq!(
207	item.scalar_at(1).unwrap(),
208	Scalar::bool(true, Nullability::Nullable)
209	);
210	}
211
212	#[test]
213	pub fn test_none() {
214	let arr = test_array();
215
216	let expr = list_contains(root(), lit(4));
217	let item = expr.evaluate(&Scope::new(arr)).unwrap();
218
219	assert_eq!(
220	item.scalar_at(0).unwrap(),
221	Scalar::bool(false, Nullability::Nullable)
222	);
223	assert_eq!(
224	item.scalar_at(1).unwrap(),
225	Scalar::bool(false, Nullability::Nullable)
226	);
227	}
228
229	#[test]
230	pub fn test_empty() {
231	let arr = ListArray::try_new(
232	PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2]).into_array(),
233	PrimitiveArray::from_iter(vec![0, 5, 5]).into_array(),
234	Validity::AllValid,
235	)
236	.unwrap()
237	.into_array();
238
239	let expr = list_contains(root(), lit(2));
240	let item = expr.evaluate(&Scope::new(arr)).unwrap();
241
242	assert_eq!(
243	item.scalar_at(0).unwrap(),
244	Scalar::bool(true, Nullability::Nullable)
245	);
246	assert_eq!(
247	item.scalar_at(1).unwrap(),
248	Scalar::bool(false, Nullability::Nullable)
249	);
250	}
251
252	#[test]
253	pub fn test_nullable() {
254	let arr = ListArray::try_new(
255	PrimitiveArray::from_iter(vec![1, 1, 2, 2, 2]).into_array(),
256	PrimitiveArray::from_iter(vec![0, 5, 5]).into_array(),
257	Validity::Array(BoolArray::from(BooleanBuffer::from(vec![true, false])).into_array()),
258	)
259	.unwrap()
260	.into_array();
261
262	let expr = list_contains(root(), lit(2));
263	let item = expr.evaluate(&Scope::new(arr)).unwrap();
264
265	assert_eq!(
266	item.scalar_at(0).unwrap(),
267	Scalar::bool(true, Nullability::Nullable)
268	);
269	assert!(!item.is_valid(1).unwrap());
270	}
271
272	#[test]
273	pub fn test_return_type() {
274	let scope = DType::Struct(
275	StructFields::new(
276	["array"].into(),
277	vec![DType::List(
278	Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
279	Nullability::Nullable,
280	)],
281	),
282	Nullability::NonNullable,
283	);
284
285	let expr = list_contains(get_item("array", root()), lit(2));
286
287	// Expect nullable, although scope is non-nullable
288	assert_eq!(
289	expr.return_dtype(&scope).unwrap(),
290	DType::Bool(Nullability::Nullable)
291	);
292	}
293
294	#[test]
295	pub fn list_falsification() {
296	let expr = list_contains(
297	lit(Scalar::list(
298	Arc::new(DType::Primitive(I32, Nullability::NonNullable)),
299	vec![1.into(), 2.into(), 3.into()],
300	Nullability::NonNullable,
301	)),
302	col("a"),
303	);
304
305	let (expr, st) = checked_pruning_expr(
306	&expr,
307	&FieldPathSet::from_iter([
308	FieldPath::from_iter([Field::Name("a".into()), Field::Name("max".into())]),
309	FieldPath::from_iter([Field::Name("a".into()), Field::Name("min".into())]),
310	]),
311	)
312	.unwrap();
313
314	assert_eq!(
315	&expr,
316	&and(
317	and(
318	or(lt(col("a_max"), lit(1i32)), gt(col("a_min"), lit(1i32)),),
319	or(lt(col("a_max"), lit(2i32)), gt(col("a_min"), lit(2i32)),)
320	),
321	or(lt(col("a_max"), lit(3i32)), gt(col("a_min"), lit(3i32)),)
322	)
323	);
324
325	assert_eq!(
326	st.map(),
327	&HashMap::from_iter([(
328	FieldPath::from_name("a"),
329	HashSet::from([Stat::Min, Stat::Max])
330	)])
331	);
332	}
333	}

vortex-data / vortex / 16728097825

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous