@@ -44,8 +44,22 @@ use std::sync::Arc;
4444/// An array of variable length byte arrays that are potentially dictionary encoded
4545/// and can be converted into a corresponding [`ArrayRef`]
4646pub enum DictionaryBuffer < K : ArrowNativeType , V : OffsetSizeTrait > {
47- Dict { keys : Vec < K > , values : ArrayRef } ,
48- Values { values : OffsetBuffer < V > } ,
47+ Dict {
48+ keys : Vec < K > ,
49+ values : ArrayRef ,
50+ /// Exclusive upper bound for decoded keys.
51+ key_upper_bound : Option < u64 > ,
52+ } ,
53+ Values {
54+ values : OffsetBuffer < V > ,
55+ } ,
56+ }
57+
58+ fn widen_key_bound ( existing : & mut Option < u64 > , incoming : Option < u64 > ) {
59+ * existing = match ( * existing, incoming) {
60+ ( Some ( current) , Some ( new) ) => Some ( current. max ( new) ) ,
61+ _ => None ,
62+ } ;
4963}
5064
5165impl < K : ArrowNativeType + Ord , V : OffsetSizeTrait > DictionaryBuffer < K , V > {
@@ -57,27 +71,41 @@ impl<K: ArrowNativeType + Ord, V: OffsetSizeTrait> DictionaryBuffer<K, V> {
5771 }
5872 }
5973
60- /// Returns a mutable reference to a keys array
74+ /// Returns the key buffer or `None` if the dictionary must be rebuilt.
6175 ///
62- /// Returns None if the dictionary needs to be recomputed
76+ /// Records an exclusive bound derived from `rle_bit_width`. A missing width
77+ /// discards any previously recorded bound.
6378 ///
6479 /// # Panics
6580 ///
66- /// Panics if the dictionary is too large for `K`
67- pub fn as_keys ( & mut self , dictionary : & ArrayRef ) -> Option < & mut Vec < K > > {
81+ /// Panics if the dictionary is too large for `K`.
82+ pub fn as_keys_with_bit_width (
83+ & mut self ,
84+ dictionary : & ArrayRef ,
85+ rle_bit_width : Option < u8 > ,
86+ ) -> Option < & mut Vec < K > > {
6887 assert ! ( K :: from_usize( dictionary. len( ) ) . is_some( ) ) ;
6988
89+ // Dictionary RLE bit widths are validated to be at most 32.
90+ let incoming_bound = rle_bit_width. map ( |bit_width| 1u64 << bit_width) ;
91+
7092 match self {
71- Self :: Dict { keys, values } => {
93+ Self :: Dict {
94+ keys,
95+ values,
96+ key_upper_bound,
97+ } => {
7298 // Need to discard fat pointer for equality check
7399 // - https://stackoverflow.com/a/67114787
74100 // - https://github.com/rust-lang/rust/issues/46139
75101 let values_ptr = std:: ptr:: from_ref ( values. as_ref ( ) ) . cast :: < ( ) > ( ) ;
76102 let dict_ptr = std:: ptr:: from_ref ( dictionary. as_ref ( ) ) . cast :: < ( ) > ( ) ;
77103 if values_ptr == dict_ptr {
104+ widen_key_bound ( key_upper_bound, incoming_bound) ;
78105 Some ( keys)
79106 } else if keys. is_empty ( ) {
80107 * values = Arc :: clone ( dictionary) ;
108+ * key_upper_bound = incoming_bound;
81109 Some ( keys)
82110 } else {
83111 None
@@ -87,6 +115,7 @@ impl<K: ArrowNativeType + Ord, V: OffsetSizeTrait> DictionaryBuffer<K, V> {
87115 * self = Self :: Dict {
88116 keys : Default :: default ( ) ,
89117 values : Arc :: clone ( dictionary) ,
118+ key_upper_bound : incoming_bound,
90119 } ;
91120 match self {
92121 Self :: Dict { keys, .. } => Some ( keys) ,
@@ -104,7 +133,7 @@ impl<K: ArrowNativeType + Ord, V: OffsetSizeTrait> DictionaryBuffer<K, V> {
104133 pub fn spill_values ( & mut self ) -> Result < & mut OffsetBuffer < V > > {
105134 match self {
106135 Self :: Values { values } => Ok ( values) ,
107- Self :: Dict { keys, values } => {
136+ Self :: Dict { keys, values, .. } => {
108137 let mut spilled = OffsetBuffer :: with_capacity ( 0 ) ;
109138 let data = values. to_data ( ) ;
110139 let dict_buffers = data. buffers ( ) ;
@@ -142,21 +171,27 @@ impl<K: ArrowNativeType + Ord, V: OffsetSizeTrait> DictionaryBuffer<K, V> {
142171 assert ! ( matches!( data_type, ArrowType :: Dictionary ( _, _) ) ) ;
143172
144173 match self {
145- Self :: Dict { keys, values } => {
146- // Validate keys unless dictionary is empty
147- if !values. is_empty ( ) {
174+ Self :: Dict {
175+ keys,
176+ values,
177+ key_upper_bound,
178+ } => {
179+ let keys_provably_in_range = key_upper_bound
180+ . map ( |bound| bound <= values. len ( ) as u64 )
181+ . unwrap_or ( false ) ;
182+
183+ if !values. is_empty ( ) && !keys_provably_in_range {
148184 let min = K :: from_usize ( 0 ) . unwrap ( ) ;
149185 let max = K :: from_usize ( values. len ( ) ) . unwrap ( ) ;
150186
151- // using copied and fold gets auto-vectorized since rust 1.70
152- // all/any would allow early exit on invalid values
153- // but in the happy case all values have to be checked anyway
154- if !keys
155- . as_slice ( )
156- . iter ( )
157- . copied ( )
158- . fold ( true , |a, x| a && x >= min && x < max)
159- {
187+ let ( observed_min, observed_max) = keys. as_slice ( ) . iter ( ) . copied ( ) . fold (
188+ ( max, min) ,
189+ |( current_min, current_max) , key| {
190+ ( current_min. min ( key) , current_max. max ( key) )
191+ } ,
192+ ) ;
193+
194+ if observed_min < min || observed_max >= max {
160195 return Err ( general_err ! (
161196 "dictionary key beyond bounds of dictionary: 0..{}" ,
162197 values. len( )
@@ -521,7 +556,10 @@ mod tests {
521556
522557 // Read some data preserving the dictionary
523558 let values = & [ 1 , 0 , 3 , 2 , 4 ] ;
524- buffer. as_keys ( & d1) . unwrap ( ) . extend_from_slice ( values) ;
559+ buffer
560+ . as_keys_with_bit_width ( & d1, None )
561+ . unwrap ( )
562+ . extend_from_slice ( values) ;
525563
526564 let mut valid = vec ! [ false , false , true , true , false , true , true , true ] ;
527565 let valid_buffer = Buffer :: from_iter ( valid. iter ( ) . copied ( ) ) ;
@@ -576,7 +614,7 @@ mod tests {
576614 assert_eq ! ( buffer. len( ) , 0 ) ;
577615 let d2 = Arc :: new ( StringArray :: from ( vec ! [ "bingo" , "" ] ) ) as ArrayRef ;
578616 buffer
579- . as_keys ( & d2)
617+ . as_keys_with_bit_width ( & d2, None )
580618 . unwrap ( )
581619 . extend_from_slice ( & [ 0 , 1 , 0 , 1 ] ) ;
582620
@@ -596,11 +634,14 @@ mod tests {
596634 assert ! ( matches!( & buffer, DictionaryBuffer :: Values { .. } ) ) ;
597635 assert_eq ! ( buffer. len( ) , 0 ) ;
598636 let d3 = Arc :: new ( StringArray :: from ( vec ! [ "bongo" ] ) ) as ArrayRef ;
599- buffer. as_keys ( & d3) . unwrap ( ) . extend_from_slice ( & [ 0 , 0 ] ) ;
637+ buffer
638+ . as_keys_with_bit_width ( & d3, None )
639+ . unwrap ( )
640+ . extend_from_slice ( & [ 0 , 0 ] ) ;
600641
601642 // Cannot change dictionary as keys not empty
602643 let d4 = Arc :: new ( StringArray :: from ( vec ! [ "bananas" ] ) ) as ArrayRef ;
603- assert ! ( buffer. as_keys ( & d4) . is_none( ) ) ;
644+ assert ! ( buffer. as_keys_with_bit_width ( & d4, None ) . is_none( ) ) ;
604645 }
605646
606647 #[ test]
@@ -610,7 +651,10 @@ mod tests {
610651
611652 let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
612653 let d = Arc :: new ( StringArray :: from ( vec ! [ "" , "f" ] ) ) as ArrayRef ;
613- buffer. as_keys ( & d) . unwrap ( ) . extend_from_slice ( & [ 0 , 2 , 0 ] ) ;
654+ buffer
655+ . as_keys_with_bit_width ( & d, None )
656+ . unwrap ( )
657+ . extend_from_slice ( & [ 0 , 2 , 0 ] ) ;
614658
615659 let err = buffer
616660 . into_array ( None , & dict_type, & mut MutableBuffer :: new ( 0 ) )
@@ -624,7 +668,10 @@ mod tests {
624668
625669 let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
626670 let d = Arc :: new ( StringArray :: from ( vec ! [ "" ] ) ) as ArrayRef ;
627- buffer. as_keys ( & d) . unwrap ( ) . extend_from_slice ( & [ 0 , 1 , 0 ] ) ;
671+ buffer
672+ . as_keys_with_bit_width ( & d, None )
673+ . unwrap ( )
674+ . extend_from_slice ( & [ 0 , 1 , 0 ] ) ;
628675
629676 let err = buffer. spill_values ( ) . unwrap_err ( ) . to_string ( ) ;
630677 assert ! (
@@ -790,4 +837,68 @@ mod tests {
790837 assert_eq ! ( dict. data_type( ) , & dict_type) ;
791838 assert_eq ! ( dict. values( ) . data_type( ) , & ArrowType :: Binary ) ;
792839 }
840+
841+ #[ test]
842+ fn test_key_upper_bound_skip_scan_when_bound_fits_otherwise_scan ( ) {
843+ let dict_type =
844+ ArrowType :: Dictionary ( Box :: new ( ArrowType :: Int32 ) , Box :: new ( ArrowType :: Utf8 ) ) ;
845+ let dict_5 = Arc :: new ( StringArray :: from ( vec ! [ "a" , "b" , "c" , "d" , "e" ] ) ) as ArrayRef ;
846+
847+ let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
848+ buffer
849+ . as_keys_with_bit_width ( & dict_5, Some ( 2 ) )
850+ . unwrap ( )
851+ . extend_from_slice ( & [ 0 , 1 , 2 , 3 ] ) ;
852+ assert ! ( matches!(
853+ buffer,
854+ DictionaryBuffer :: Dict {
855+ key_upper_bound: Some ( 4 ) ,
856+ ..
857+ }
858+ ) ) ;
859+ let array = buffer
860+ . into_array ( None , & dict_type, & mut MutableBuffer :: new ( 0 ) )
861+ . unwrap ( ) ;
862+ assert_eq ! ( array. len( ) , 4 ) ;
863+
864+ let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
865+ buffer
866+ . as_keys_with_bit_width ( & dict_5, Some ( 4 ) )
867+ . unwrap ( )
868+ . extend_from_slice ( & [ 0 , 10 ] ) ;
869+ let err = buffer
870+ . into_array ( None , & dict_type, & mut MutableBuffer :: new ( 0 ) )
871+ . unwrap_err ( )
872+ . to_string ( ) ;
873+ assert ! ( err. contains( "dictionary key beyond bounds" ) , "{err}" ) ;
874+
875+ let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
876+ buffer
877+ . as_keys_with_bit_width ( & dict_5, None )
878+ . unwrap ( )
879+ . extend_from_slice ( & [ 0 , 7 ] ) ;
880+ buffer
881+ . into_array ( None , & dict_type, & mut MutableBuffer :: new ( 0 ) )
882+ . unwrap_err ( ) ;
883+
884+ let mut buffer = DictionaryBuffer :: < i32 , i32 > :: with_capacity ( 0 ) ;
885+ buffer
886+ . as_keys_with_bit_width ( & dict_5, Some ( 2 ) )
887+ . unwrap ( )
888+ . extend_from_slice ( & [ 0 , 1 ] ) ;
889+ buffer
890+ . as_keys_with_bit_width ( & dict_5, Some ( 4 ) )
891+ . unwrap ( )
892+ . extend_from_slice ( & [ 10 ] ) ;
893+ assert ! ( matches!(
894+ buffer,
895+ DictionaryBuffer :: Dict {
896+ key_upper_bound: Some ( 16 ) ,
897+ ..
898+ }
899+ ) ) ;
900+ buffer
901+ . into_array ( None , & dict_type, & mut MutableBuffer :: new ( 0 ) )
902+ . unwrap_err ( ) ;
903+ }
793904}
0 commit comments