Skip to content

Commit 497b608

Browse files
Rich-T-kidclaude
andcommitted
perf: preserve dictionary encoding in substr
Opt substr into dictionary-aware execution so planning no longer inserts CAST(dict -> value_type) around dictionary inputs with scalar start/length. - Mark the string arg with EncodingPreservation::dictionary() so coercion keeps the dict wrapper - Implement return_field_from_args to declare Dictionary(..) when the tail args are scalars, falling back to the value type otherwise - Add a fast path in invoke_with_args that runs substr on the N distinct dict values and reuses the keys via with_values(); per-row start/length materializes the dict first - Unit tests cover Utf8/LargeUtf8/Utf8View value types, null keys, per-row fallback, and the return_field planning behavior - SLT regression asserts arrow_typeof stays Dictionary(..) for scalar args and the plan no longer wraps the column in a CAST Closes apache#26170 Co-Authored-By: Claude Opus 4.7 <[email protected]>
1 parent 1c49b7f commit 497b608

2 files changed

Lines changed: 372 additions & 5 deletions

File tree

‎datafusion/functions/src/unicode/substr.rs‎

Lines changed: 336 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -24,15 +24,16 @@ use arrow::array::{
2424
StringArrayType, StringViewArray,
2525
};
2626
use arrow::buffer::{NullBuffer, ScalarBuffer};
27-
use arrow::datatypes::DataType;
27+
use arrow::datatypes::{DataType, Field, FieldRef};
2828
use datafusion_common::cast::as_int64_array;
2929
use datafusion_common::types::{
3030
NativeType, logical_int32, logical_int64, logical_string,
3131
};
3232
use datafusion_common::{Result, exec_err};
3333
use datafusion_expr::{
34-
Coercion, ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature,
35-
TypeSignature, TypeSignatureClass, Volatility,
34+
Coercion, ColumnarValue, Documentation, EncodingPreservation, ReturnFieldArgs,
35+
ScalarFunctionArgs, ScalarUDFImpl, Signature, TypeSignature, TypeSignatureClass,
36+
Volatility,
3637
};
3738
use datafusion_macros::user_doc;
3839

@@ -73,7 +74,8 @@ impl Default for SubstrFunc {
7374

7475
impl SubstrFunc {
7576
pub fn new() -> Self {
76-
let string = Coercion::new_exact(TypeSignatureClass::Native(logical_string()));
77+
let string = Coercion::new_exact(TypeSignatureClass::Native(logical_string()))
78+
.with_encoding_preservation(EncodingPreservation::dictionary());
7779
let int64 = Coercion::new_implicit(
7880
TypeSignatureClass::Native(logical_int64()),
7981
vec![TypeSignatureClass::Native(logical_int32())],
@@ -115,8 +117,63 @@ impl ScalarUDFImpl for SubstrFunc {
115117
Ok(arg_types[0].clone())
116118
}
117119

120+
fn return_field_from_args(&self, args: ReturnFieldArgs) -> Result<FieldRef> {
121+
let input = &args.arg_fields[0];
122+
// Dictionary encoding is preserved in the output only when the
123+
// start/length arguments are constant scalars (so a single substring
124+
// operation on the dictionary's unique values suffices). When any tail
125+
// argument varies per row, `invoke_with_args` materializes the
126+
// dictionary and returns the plain value type; this method must
127+
// declare the same type so the planner's expected schema matches.
128+
let output_type = match input.data_type() {
129+
DataType::Dictionary(_, value_type)
130+
if !args.scalar_arguments.iter().skip(1).all(Option::is_some) =>
131+
{
132+
value_type.as_ref().clone()
133+
}
134+
other => other.clone(),
135+
};
136+
Ok(Field::new(self.name(), output_type, input.is_nullable()).into())
137+
}
138+
118139
fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
119-
make_scalar_function(substr, vec![])(&args.args)
140+
// Dictionary fast path: when the string column is dictionary-encoded and
141+
// the start/length arguments are scalars, apply `substr` to the
142+
// dictionary's unique values only and reuse the original keys. This
143+
// avoids materializing the dictionary (N_rows strings) when a single
144+
// substring operation can be computed over N_distinct values instead.
145+
if let ColumnarValue::Array(array) = &args.args[0]
146+
&& matches!(array.data_type(), DataType::Dictionary(_, _))
147+
&& args.args[1..]
148+
.iter()
149+
.all(|v| matches!(v, ColumnarValue::Scalar(_)))
150+
{
151+
let dictionary = array.as_any_dictionary();
152+
let values = Arc::clone(dictionary.values());
153+
let mut inner_args = Vec::with_capacity(args.args.len());
154+
inner_args.push(ColumnarValue::Array(values));
155+
inner_args.extend_from_slice(&args.args[1..]);
156+
let new_values = make_scalar_function(substr, vec![])(&inner_args)?
157+
.into_array(dictionary.values().len())?;
158+
return Ok(ColumnarValue::Array(dictionary.with_values(new_values)));
159+
}
160+
161+
// Dictionary with per-row start/length: can't reuse keys because the
162+
// same dictionary value may map to different outputs. Materialize the
163+
// dictionary once, then fall through to the regular path.
164+
let args = if let ColumnarValue::Array(array) = &args.args[0]
165+
&& let DataType::Dictionary(_, value_type) = array.data_type()
166+
{
167+
let materialized =
168+
arrow::compute::kernels::cast::cast(array, value_type.as_ref())?;
169+
let mut new_args = args.args.clone();
170+
new_args[0] = ColumnarValue::Array(materialized);
171+
new_args
172+
} else {
173+
args.args
174+
};
175+
176+
make_scalar_function(substr, vec![])(&args)
120177
}
121178

122179
fn aliases(&self) -> &[String] {
@@ -766,4 +823,278 @@ mod tests {
766823

767824
Ok(())
768825
}
826+
827+
mod dictionary {
828+
use super::*;
829+
use arrow::array::{DictionaryArray, LargeStringArray, StringArray};
830+
use arrow::datatypes::{DataType, Field, FieldRef, Int32Type};
831+
use datafusion_common::config::ConfigOptions;
832+
use datafusion_expr::{ReturnFieldArgs, ScalarFunctionArgs};
833+
834+
/// Invokes `SubstrFunc` through the full `invoke_with_args` pipeline so
835+
/// the dictionary fast-path and the `return_field_from_args`
836+
/// planning-time decision are both exercised.
837+
fn invoke_substr(args: Vec<ColumnarValue>) -> Result<ColumnarValue> {
838+
let func = SubstrFunc::new();
839+
let arg_fields: Vec<FieldRef> = args
840+
.iter()
841+
.enumerate()
842+
.map(|(i, a)| {
843+
Arc::new(Field::new(format!("arg_{i}"), a.data_type(), true))
844+
})
845+
.collect();
846+
let scalar_arguments: Vec<Option<&ScalarValue>> = args
847+
.iter()
848+
.map(|a| match a {
849+
ColumnarValue::Scalar(s) => Some(s),
850+
ColumnarValue::Array(_) => None,
851+
})
852+
.collect();
853+
let return_field = func.return_field_from_args(ReturnFieldArgs {
854+
arg_fields: &arg_fields,
855+
scalar_arguments: &scalar_arguments,
856+
})?;
857+
let number_rows = args
858+
.iter()
859+
.filter_map(|a| match a {
860+
ColumnarValue::Array(a) => Some(a.len()),
861+
ColumnarValue::Scalar(_) => None,
862+
})
863+
.max()
864+
.unwrap_or(1);
865+
func.invoke_with_args(ScalarFunctionArgs {
866+
args,
867+
arg_fields,
868+
number_rows,
869+
return_field,
870+
config_options: Arc::new(ConfigOptions::default()),
871+
})
872+
}
873+
874+
fn dict_utf8(values: StringArray, keys: Vec<i32>) -> ArrayRef {
875+
let keys = arrow::array::Int32Array::from(keys);
876+
Arc::new(
877+
DictionaryArray::<Int32Type>::try_new(keys, Arc::new(values)).unwrap(),
878+
)
879+
}
880+
881+
/// With scalar start/length, substr should preserve dict encoding:
882+
/// run substring on the N_distinct unique values and reuse the keys.
883+
#[test]
884+
fn fast_path_preserves_dictionary_encoding() {
885+
let input = dict_utf8(
886+
StringArray::from(vec!["hello", "world", "rust"]),
887+
vec![0, 1, 0, 2, 1],
888+
);
889+
let expected_keys = input.as_any_dictionary().keys().to_data();
890+
891+
let result = invoke_substr(vec![
892+
ColumnarValue::Array(input),
893+
ColumnarValue::Scalar(ScalarValue::from(1i64)),
894+
ColumnarValue::Scalar(ScalarValue::from(3i64)),
895+
])
896+
.unwrap();
897+
898+
let array = result.into_array(5).unwrap();
899+
assert!(
900+
matches!(array.data_type(), DataType::Dictionary(k, v) if **k == DataType::Int32 && **v == Utf8),
901+
"expected Dictionary(Int32, Utf8), got {:?}",
902+
array.data_type(),
903+
);
904+
let dict = array.as_dictionary::<Int32Type>();
905+
assert_eq!(dict.keys().to_data(), expected_keys);
906+
let values = dict.values().as_string::<i32>();
907+
assert_eq!(values.value(0), "hel");
908+
assert_eq!(values.value(1), "wor");
909+
assert_eq!(values.value(2), "rus");
910+
assert_eq!(values.len(), 3, "values array should still be N_distinct");
911+
}
912+
913+
/// Nulls in the dictionary key buffer must survive the fast path.
914+
#[test]
915+
fn fast_path_preserves_null_keys() {
916+
let keys = arrow::array::Int32Array::from(vec![Some(0), None, Some(1), None]);
917+
let values = StringArray::from(vec!["alpha", "beta"]);
918+
let dict: ArrayRef = Arc::new(
919+
DictionaryArray::<Int32Type>::try_new(keys, Arc::new(values)).unwrap(),
920+
);
921+
922+
let result = invoke_substr(vec![
923+
ColumnarValue::Array(dict),
924+
ColumnarValue::Scalar(ScalarValue::from(1i64)),
925+
ColumnarValue::Scalar(ScalarValue::from(2i64)),
926+
])
927+
.unwrap();
928+
929+
let array = result.into_array(4).unwrap();
930+
let dict = array.as_dictionary::<Int32Type>();
931+
assert_eq!(dict.len(), 4);
932+
assert!(!dict.is_null(0));
933+
assert!(dict.is_null(1));
934+
assert!(!dict.is_null(2));
935+
assert!(dict.is_null(3));
936+
let values = dict.values().as_string::<i32>();
937+
assert_eq!(values.value(0), "al");
938+
assert_eq!(values.value(1), "be");
939+
}
940+
941+
/// Dict with Utf8View values should round-trip the fast path.
942+
#[test]
943+
fn fast_path_handles_utf8view_values() {
944+
let values: ArrayRef =
945+
Arc::new(StringViewArray::from(vec!["dataset", "dataflow"]));
946+
let keys = arrow::array::Int32Array::from(vec![0, 1, 0]);
947+
let dict: ArrayRef =
948+
Arc::new(DictionaryArray::<Int32Type>::try_new(keys, values).unwrap());
949+
950+
let result = invoke_substr(vec![
951+
ColumnarValue::Array(dict),
952+
ColumnarValue::Scalar(ScalarValue::from(5i64)),
953+
ColumnarValue::Scalar(ScalarValue::from(4i64)),
954+
])
955+
.unwrap();
956+
957+
let array = result.into_array(3).unwrap();
958+
assert!(matches!(
959+
array.data_type(),
960+
DataType::Dictionary(_, v) if **v == Utf8View
961+
));
962+
let dict = array.as_dictionary::<Int32Type>();
963+
let values = dict.values().as_string_view();
964+
assert_eq!(values.value(0), "set");
965+
assert_eq!(values.value(1), "flow");
966+
}
967+
968+
/// Dict with LargeUtf8 values should round-trip the fast path.
969+
#[test]
970+
fn fast_path_handles_largeutf8_values() {
971+
let values: ArrayRef =
972+
Arc::new(LargeStringArray::from(vec!["alpha", "omega"]));
973+
let keys = arrow::array::Int32Array::from(vec![0, 1, 1]);
974+
let dict: ArrayRef =
975+
Arc::new(DictionaryArray::<Int32Type>::try_new(keys, values).unwrap());
976+
977+
let result = invoke_substr(vec![
978+
ColumnarValue::Array(dict),
979+
ColumnarValue::Scalar(ScalarValue::from(2i64)),
980+
ColumnarValue::Scalar(ScalarValue::from(3i64)),
981+
])
982+
.unwrap();
983+
984+
let array = result.into_array(3).unwrap();
985+
assert!(matches!(
986+
array.data_type(),
987+
DataType::Dictionary(_, v) if **v == LargeUtf8
988+
));
989+
let dict = array.as_dictionary::<Int32Type>();
990+
let values = dict.values().as_string::<i64>();
991+
assert_eq!(values.value(0), "lph");
992+
assert_eq!(values.value(1), "meg");
993+
}
994+
995+
/// With per-row start/length, the dict must be materialized and the
996+
/// output type is the value type (not Dictionary). The declared return
997+
/// type from `return_field_from_args` must agree.
998+
#[test]
999+
fn per_row_args_materialize_to_value_type() {
1000+
let input =
1001+
dict_utf8(StringArray::from(vec!["hello", "world"]), vec![0, 1, 0, 1]);
1002+
let starts: ArrayRef = Arc::new(Int64Array::from(vec![1, 2, 3, 4]));
1003+
1004+
let result = invoke_substr(vec![
1005+
ColumnarValue::Array(input),
1006+
ColumnarValue::Array(starts),
1007+
])
1008+
.unwrap();
1009+
1010+
let array = result.into_array(4).unwrap();
1011+
assert_eq!(array.data_type(), &Utf8);
1012+
let strings = array.as_string::<i32>();
1013+
assert_eq!(strings.value(0), "hello");
1014+
assert_eq!(strings.value(1), "orld");
1015+
assert_eq!(strings.value(2), "llo");
1016+
assert_eq!(strings.value(3), "ld");
1017+
}
1018+
1019+
/// The dict fast path must produce identical row-wise output to the
1020+
/// equivalent materialized string path.
1021+
#[test]
1022+
fn dict_output_matches_materialized_output() {
1023+
let strings = vec!["foo", "bar", "foo", "baz", "bar", "foo", "qux"];
1024+
let unique = ["foo", "bar", "baz", "qux"];
1025+
let keys: Vec<i32> = strings
1026+
.iter()
1027+
.map(|s| unique.iter().position(|u| u == s).unwrap() as i32)
1028+
.collect();
1029+
1030+
let dict = dict_utf8(StringArray::from(unique.to_vec()), keys);
1031+
let materialized: ArrayRef = Arc::new(StringArray::from(strings.clone()));
1032+
1033+
let dict_result = invoke_substr(vec![
1034+
ColumnarValue::Array(dict),
1035+
ColumnarValue::Scalar(ScalarValue::from(1i64)),
1036+
ColumnarValue::Scalar(ScalarValue::from(2i64)),
1037+
])
1038+
.unwrap()
1039+
.into_array(strings.len())
1040+
.unwrap();
1041+
let flat_result = invoke_substr(vec![
1042+
ColumnarValue::Array(materialized),
1043+
ColumnarValue::Scalar(ScalarValue::from(1i64)),
1044+
ColumnarValue::Scalar(ScalarValue::from(2i64)),
1045+
])
1046+
.unwrap()
1047+
.into_array(strings.len())
1048+
.unwrap();
1049+
1050+
let dict_strings =
1051+
arrow::compute::kernels::cast::cast(&dict_result, &Utf8).unwrap();
1052+
assert_eq!(dict_strings.as_ref(), flat_result.as_ref());
1053+
}
1054+
1055+
/// `return_field_from_args` must declare Dictionary when all tail args
1056+
/// are scalar, so the planner skips the implicit CAST(dict -> value).
1057+
#[test]
1058+
fn return_field_declares_dictionary_for_scalar_tail() {
1059+
let func = SubstrFunc::new();
1060+
let dict_type =
1061+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(Utf8));
1062+
let arg_fields: Vec<FieldRef> = vec![
1063+
Arc::new(Field::new("s", dict_type.clone(), true)),
1064+
Arc::new(Field::new("start", DataType::Int64, false)),
1065+
Arc::new(Field::new("len", DataType::Int64, false)),
1066+
];
1067+
let start = ScalarValue::from(1i64);
1068+
let len = ScalarValue::from(3i64);
1069+
let scalar_arguments = vec![None, Some(&start), Some(&len)];
1070+
let field = func
1071+
.return_field_from_args(ReturnFieldArgs {
1072+
arg_fields: &arg_fields,
1073+
scalar_arguments: &scalar_arguments,
1074+
})
1075+
.unwrap();
1076+
assert_eq!(field.data_type(), &dict_type);
1077+
}
1078+
1079+
/// `return_field_from_args` must declare the dict's value type when any
1080+
/// tail arg is per-row, so the planner expects the materialized output.
1081+
#[test]
1082+
fn return_field_declares_value_type_for_per_row_tail() {
1083+
let func = SubstrFunc::new();
1084+
let dict_type =
1085+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(Utf8));
1086+
let arg_fields: Vec<FieldRef> = vec![
1087+
Arc::new(Field::new("s", dict_type, true)),
1088+
Arc::new(Field::new("start", DataType::Int64, false)),
1089+
];
1090+
let scalar_arguments = vec![None, None];
1091+
let field = func
1092+
.return_field_from_args(ReturnFieldArgs {
1093+
arg_fields: &arg_fields,
1094+
scalar_arguments: &scalar_arguments,
1095+
})
1096+
.unwrap();
1097+
assert_eq!(field.data_type(), &Utf8);
1098+
}
1099+
}
7691100
}

0 commit comments

Comments
 (0)