Skip to content

Commit 5700605

Browse files
committed
List the extension types whose storage gives equality and order
Extension types cannot declare yet that their storage gives their equality or their order, so `storage_gives_equality` and `storage_gives_order` answer from fixed lists of extension IDs: `Date`, `Time`, `Timestamp`, and `Uuid` for both, and `Vector` and `FixedShapeTensor` for equality only. The answers cover every depth and reject placeholders of unknown types, the same as the claims that will replace the lists. `Uuid`, `Vector`, and `FixedShapeTensor` live in other crates, so their own tests catch an ID that drifts from the lists. Signed-off-by: Connor Tsui <[email protected]>
1 parent ce239a8 commit 5700605

7 files changed

Lines changed: 247 additions & 2 deletions

File tree

‎encodings/uuid/src/vtable.rs‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -131,6 +131,8 @@ mod tests {
131131
use vortex_array::dtype::PType;
132132
use vortex_array::dtype::extension::ExtDType;
133133
use vortex_array::dtype::extension::ExtVTable;
134+
use vortex_array::dtype::extension::storage_gives_equality;
135+
use vortex_array::dtype::extension::storage_gives_order;
134136
use vortex_array::scalar::Scalar;
135137
use vortex_array::scalar::ScalarValue;
136138
use vortex_error::VortexResult;
@@ -318,6 +320,19 @@ mod tests {
318320
Ok(())
319321
}
320322

323+
/// The storage lists of `vortex-array` name UUIDs by ID, so this fails if the ID changes.
324+
#[test]
325+
fn storage_gives_equality_and_order() -> VortexResult<()> {
326+
let storage_dtype = uuid_storage_dtype(Nullability::NonNullable);
327+
let ext_dtype = ExtDType::<Uuid>::try_new(UuidMetadata::default(), storage_dtype)?;
328+
let dtype = DType::Extension(ext_dtype.erased());
329+
330+
assert!(storage_gives_equality(&dtype));
331+
assert!(storage_gives_order(&dtype));
332+
333+
Ok(())
334+
}
335+
321336
fn uuid_storage_dtype(nullability: Nullability) -> DType {
322337
DType::FixedSizeList(
323338
Arc::new(DType::Primitive(PType::U8, Nullability::NonNullable)),

‎vortex-array/src/dtype/extension/mod.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,8 @@
1313
//! extension plugins in a session before deserializing data that may reference them.
1414
//!
1515
//! Scalar functions and aggregates declare how they use extension operands with [`ExtensionUse`].
16+
//! [`storage_gives_equality`] and [`storage_gives_order`] answer whether a dtype takes the equality
17+
//! and the order of its values from its storage.
1618
//!
1719
//! ## File layout convention
1820
//!
@@ -44,6 +46,9 @@ pub use matcher::*;
4446

4547
mod extension_use;
4648
pub use extension_use::*;
49+
50+
mod storage_semantics;
51+
pub use storage_semantics::*;
4752
use vortex_session::registry::Id;
4853

4954
/// A unique identifier for an extension type
Lines changed: 188 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,188 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! The extension types whose storage gives the equality and the order of their values.
5+
//!
6+
//! Extension types are opaque by default, but a few types in this repository take their equality,
7+
//! and most also their order, from their storage. For example, two timestamps of one dtype are
8+
//! equal exactly when their `i64` storage values are equal, and they order the same way. Extension
9+
//! types cannot declare this themselves yet, so this module lists them until
10+
//! <https://github.com/vortex-data/vortex/issues/11115> lets them. The lists name types by
11+
//! extension ID, because `Uuid`, `Vector`, and `FixedShapeTensor` live in crates that depend on
12+
//! this one. A type outside this repository cannot be listed.
13+
//!
14+
//! Other code answers the same question with a list of its own, such as `register_storage_ordered`,
15+
//! the `Uuid` check of the DuckDB aggregate pushdown, and the temporal check of the DataFusion
16+
//! statistics.
17+
18+
use vortex_session::registry::CachedId;
19+
20+
use crate::dtype::DType;
21+
use crate::dtype::extension::ExtId;
22+
use crate::dtype::extension::ForeignExtDType;
23+
24+
/// The extension types whose storage gives the order of their values, and so also their equality.
25+
static ORDER_IDS: [CachedId; 4] = [
26+
CachedId::new("vortex.date"),
27+
CachedId::new("vortex.time"),
28+
CachedId::new("vortex.timestamp"),
29+
CachedId::new("vortex.uuid"),
30+
];
31+
32+
/// The extension types whose storage gives the equality of their values, but not their order.
33+
static EQUALITY_ONLY_IDS: [CachedId; 2] = [
34+
CachedId::new("vortex.tensor.vector"),
35+
CachedId::new("vortex.tensor.fixed_shape_tensor"),
36+
];
37+
38+
/// Returns whether values of `dtype` are equal exactly when their storage values are equal.
39+
///
40+
/// The answer ignores nullability and covers every depth:
41+
///
42+
/// - It is `true` for [`DType::Null`], [`DType::Bool`], [`DType::Primitive`], [`DType::Decimal`],
43+
/// [`DType::Utf8`], and [`DType::Binary`].
44+
/// - It is `true` for a struct, list, fixed-size list, or map when it is `true` for every child.
45+
/// - It is `false` for [`DType::Union`] and [`DType::Variant`].
46+
/// - It is `true` for an extension dtype when its type is [`Date`], [`Time`], [`Timestamp`],
47+
/// `Uuid`, `Vector`, or `FixedShapeTensor`, whatever its storage dtype. It is `false` for a
48+
/// placeholder of an extension type that the session does not know, even under a listed ID.
49+
///
50+
/// [`Date`]: crate::extension::datetime::Date
51+
/// [`Time`]: crate::extension::datetime::Time
52+
/// [`Timestamp`]: crate::extension::datetime::Timestamp
53+
pub fn storage_gives_equality(dtype: &DType) -> bool {
54+
holds_at_every_depth(dtype, |id| {
55+
ORDER_IDS
56+
.iter()
57+
.chain(&EQUALITY_ONLY_IDS)
58+
.any(|listed| **listed == id)
59+
})
60+
}
61+
62+
/// Returns whether values of `dtype` order like their storage values.
63+
///
64+
/// The answer follows the rules of [`storage_gives_equality`], except that `Vector` and
65+
/// `FixedShapeTensor` are not listed, because their values have no natural order. So a dtype whose
66+
/// storage gives its order also gives its equality.
67+
pub fn storage_gives_order(dtype: &DType) -> bool {
68+
holds_at_every_depth(dtype, |id| ORDER_IDS.iter().any(|listed| **listed == id))
69+
}
70+
71+
/// Applies the rules of [`storage_gives_equality`], where `is_listed` names the extension types
72+
/// that hold the property.
73+
fn holds_at_every_depth(dtype: &DType, is_listed: fn(ExtId) -> bool) -> bool {
74+
match dtype {
75+
DType::Null
76+
| DType::Bool(_)
77+
| DType::Primitive(..)
78+
| DType::Decimal(..)
79+
| DType::Utf8(_)
80+
| DType::Binary(_) => true,
81+
DType::List(element, _) | DType::FixedSizeList(element, ..) => {
82+
holds_at_every_depth(element, is_listed)
83+
}
84+
DType::Map(map, _) => {
85+
holds_at_every_depth(&map.key_dtype(), is_listed)
86+
&& holds_at_every_depth(&map.value_dtype(), is_listed)
87+
}
88+
DType::Struct(fields, _) => fields
89+
.field_dtypes()
90+
.all(|field| holds_at_every_depth(field, is_listed)),
91+
DType::Union(..) | DType::Variant(_) => false,
92+
// A placeholder keeps the ID of the type that it stands in for, but not its semantics.
93+
DType::Extension(ext) => !ext.is::<ForeignExtDType>() && is_listed(ext.id()),
94+
}
95+
}
96+
97+
#[cfg(test)]
98+
mod tests {
99+
use rstest::rstest;
100+
use vortex_error::VortexResult;
101+
102+
use super::storage_gives_equality;
103+
use super::storage_gives_order;
104+
use crate::dtype::DType;
105+
use crate::dtype::Nullability::NonNullable;
106+
use crate::dtype::Nullability::Nullable;
107+
use crate::dtype::PType;
108+
use crate::dtype::UnionVariants;
109+
use crate::dtype::extension::ExtDType;
110+
use crate::dtype::extension::ExtVTable;
111+
use crate::dtype::extension::ForeignExtDType;
112+
use crate::extension::datetime::Date;
113+
use crate::extension::datetime::Time;
114+
use crate::extension::datetime::TimeUnit;
115+
use crate::extension::datetime::Timestamp;
116+
use crate::extension::tests::divisible_int::DivisibleInt;
117+
use crate::extension::tests::divisible_int::Divisor;
118+
119+
fn timestamp() -> DType {
120+
DType::Extension(Timestamp::new(TimeUnit::Milliseconds, Nullable).erased())
121+
}
122+
123+
/// An extension dtype that is on neither list, although its `u64` storage gives both.
124+
fn unlisted() -> VortexResult<DType> {
125+
let dtype = ExtDType::<DivisibleInt>::try_new(Divisor(2), PType::U64.into())?;
126+
127+
Ok(DType::Extension(dtype.erased()))
128+
}
129+
130+
/// A date dtype as read by a session that does not know dates.
131+
fn date_placeholder() -> VortexResult<DType> {
132+
let metadata = Date.serialize_metadata(&TimeUnit::Days)?;
133+
let dtype = ForeignExtDType::from_parts(Date.id(), metadata, PType::I32.into())?;
134+
135+
Ok(DType::Extension(dtype))
136+
}
137+
138+
/// A struct of a timestamp and `field`.
139+
fn struct_with(field: DType) -> DType {
140+
DType::struct_([("at", timestamp()), ("field", field)], NonNullable)
141+
}
142+
143+
/// A union whose variants both give equality and order.
144+
fn union() -> VortexResult<DType> {
145+
let dtypes = vec![timestamp(), PType::I64.into()];
146+
let variants = UnionVariants::new(["at", "count"].into(), dtypes)?;
147+
148+
Ok(DType::Union(variants, Nullable))
149+
}
150+
151+
#[rstest]
152+
#[case::date(Ok(DType::Extension(Date::new(TimeUnit::Days, NonNullable).erased())), true)]
153+
#[case::time(Ok(DType::Extension(Time::new(TimeUnit::Seconds, Nullable).erased())), true)]
154+
#[case::timestamp(Ok(timestamp()), true)]
155+
#[case::unlisted(unlisted(), false)]
156+
#[case::date_placeholder(date_placeholder(), false)]
157+
#[case::list(Ok(DType::list(timestamp(), Nullable)), true)]
158+
#[case::list_of_placeholder(
159+
date_placeholder().map(|dtype| DType::list(dtype, Nullable)),
160+
false
161+
)]
162+
#[case::map(
163+
DType::map(DType::Utf8(NonNullable), timestamp(), false, Nullable),
164+
true
165+
)]
166+
#[case::map_of_variant(
167+
DType::map(DType::Utf8(NonNullable), DType::Variant(Nullable), false, Nullable),
168+
false
169+
)]
170+
#[case::map_with_placeholder_key(
171+
date_placeholder().and_then(|key| DType::map(key, timestamp(), false, Nullable)),
172+
false
173+
)]
174+
#[case::struct_(Ok(struct_with(PType::I64.into())), true)]
175+
#[case::struct_with_variant(Ok(struct_with(DType::Variant(Nullable))), false)]
176+
#[case::union(union(), false)]
177+
fn test_storage_gives_equality_and_order(
178+
#[case] dtype: VortexResult<DType>,
179+
#[case] expected: bool,
180+
) -> VortexResult<()> {
181+
let dtype = dtype?;
182+
183+
assert_eq!(storage_gives_equality(&dtype), expected);
184+
assert_eq!(storage_gives_order(&dtype), expected);
185+
186+
Ok(())
187+
}
188+
}

‎vortex-array/src/extension/mod.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,4 +6,4 @@
66
pub mod datetime;
77

88
#[cfg(test)]
9-
mod tests;
9+
pub(crate) mod tests;

‎vortex-array/src/extension/tests/mod.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,4 +3,4 @@
33

44
//! Test extension types for exercising the [`ExtVTable`] contract.
55
6-
mod divisible_int;
6+
pub(crate) mod divisible_int;

‎vortex-tensor/src/types/fixed_shape_tensor/vtable.rs‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,8 +77,16 @@ impl ExtVTable for FixedShapeTensor {
7777

7878
#[cfg(test)]
7979
mod tests {
80+
use std::sync::Arc;
81+
8082
use rstest::rstest;
83+
use vortex_array::dtype::DType;
84+
use vortex_array::dtype::Nullability;
85+
use vortex_array::dtype::PType;
86+
use vortex_array::dtype::extension::ExtDType;
8187
use vortex_array::dtype::extension::ExtVTable;
88+
use vortex_array::dtype::extension::storage_gives_equality;
89+
use vortex_array::dtype::extension::storage_gives_order;
8290
use vortex_error::VortexResult;
8391

8492
use crate::types::fixed_shape_tensor::FixedShapeTensor;
@@ -119,4 +127,19 @@ mod tests {
119127
) -> VortexResult<()> {
120128
assert_roundtrip(&metadata?)
121129
}
130+
131+
/// The storage lists of `vortex-array` name tensors by ID, so this fails if the ID changes.
132+
#[test]
133+
fn storage_gives_equality_but_not_order() -> VortexResult<()> {
134+
let element = DType::Primitive(PType::F32, Nullability::NonNullable);
135+
let storage = DType::FixedSizeList(Arc::new(element), 6, Nullability::NonNullable);
136+
let metadata = FixedShapeTensorMetadata::new(vec![2, 3]);
137+
let dtype =
138+
DType::Extension(ExtDType::<FixedShapeTensor>::try_new(metadata, storage)?.erased());
139+
140+
assert!(storage_gives_equality(&dtype));
141+
assert!(!storage_gives_order(&dtype));
142+
143+
Ok(())
144+
}
122145
}

‎vortex-tensor/src/types/vector/vtable.rs‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,8 @@ mod tests {
5454
use vortex_array::dtype::PType;
5555
use vortex_array::dtype::extension::ExtDType;
5656
use vortex_array::dtype::extension::ExtVTable;
57+
use vortex_array::dtype::extension::storage_gives_equality;
58+
use vortex_array::dtype::extension::storage_gives_order;
5759
use vortex_error::VortexResult;
5860

5961
use crate::types::vector::Vector;
@@ -124,4 +126,16 @@ mod tests {
124126
assert_eq!(deserialized, EmptyMetadata);
125127
Ok(())
126128
}
129+
130+
/// The storage lists of `vortex-array` name vectors by ID, so this fails if the ID changes.
131+
#[test]
132+
fn storage_gives_equality_but_not_order() -> VortexResult<()> {
133+
let storage = vector_storage_dtype(PType::F32, 128, Nullability::NonNullable);
134+
let dtype = DType::Extension(ExtDType::<Vector>::try_new(EmptyMetadata, storage)?.erased());
135+
136+
assert!(storage_gives_equality(&dtype));
137+
assert!(!storage_gives_order(&dtype));
138+
139+
Ok(())
140+
}
127141
}

0 commit comments

Comments
 (0)