@@ -89,7 +89,7 @@ macro_rules! downcast_supported_integer {
8989/// ```
9090/// The resulting `range` (10) correctly represents the size of the interval `[-5, 5]`.
9191///
92- /// **2. Index Lookup (in `get_matched_indices `)**
92+ /// **2. Index Lookup (in `get_matched_indices_with_limit_offset `)**
9393///
9494/// For a probe value of `0` (which is stored as `0u64`):
9595/// ```text
@@ -157,13 +157,23 @@ impl ArrayMap {
157157 max_val. wrapping_sub ( min_val)
158158 }
159159
160+ #[ inline]
161+ fn key_to_index ( key : u64 , offset : u64 , data_len : usize ) -> Option < usize > {
162+ let idx = key. wrapping_sub ( offset) ;
163+ if idx < data_len as u64 {
164+ Some ( idx as usize )
165+ } else {
166+ None
167+ }
168+ }
169+
160170 /// Creates a new [`ArrayMap`] from the given array of join keys.
161171 ///
162172 /// Note: This function processes only the non-null values in the input `array`,
163173 /// ignoring any rows where the key is `NULL`.
164174 ///
165175 pub ( crate ) fn try_new ( array : & ArrayRef , min_val : u64 , max_val : u64 ) -> Result < Self > {
166- let range = max_val . wrapping_sub ( min_val) ;
176+ let range = Self :: calculate_range ( min_val, max_val ) ;
167177 if range >= usize:: MAX as u64 {
168178 return internal_err ! ( "ArrayMap key range is too large to be allocated." ) ;
169179 }
@@ -207,10 +217,9 @@ impl ArrayMap {
207217 for ( i, val) in arr. iter ( ) . enumerate ( ) . rev ( ) {
208218 if let Some ( val) = val {
209219 let key: u64 = val. as_ ( ) ;
210- let idx = key. wrapping_sub ( offset_val) as usize ;
211- if idx >= data. len ( ) {
220+ let Some ( idx) = Self :: key_to_index ( key, offset_val, data. len ( ) ) else {
212221 return internal_err ! ( "failed build Array idx >= data.len()" ) ;
213- }
222+ } ;
214223
215224 if data[ idx] != 0 {
216225 if next. is_empty ( ) {
@@ -264,6 +273,16 @@ impl ArrayMap {
264273 )
265274 }
266275
276+ /// Looks up `key` (a raw probe value cast to `u64`) in the build side,
277+ /// returning the 1-based build-side slot if the key maps to a non-empty
278+ /// bucket, or `None` otherwise.
279+ #[ inline]
280+ fn get_value ( & self , key : u64 ) -> Option < u32 > {
281+ let idx = Self :: key_to_index ( key, self . offset , self . data . len ( ) ) ?;
282+ let value = self . data [ idx] ;
283+ ( value != 0 ) . then_some ( value)
284+ }
285+
267286 fn lookup_and_get_indices < T : ArrowNumericType > (
268287 & self ,
269288 array : & ArrayRef ,
@@ -294,14 +313,10 @@ impl ArrayMap {
294313 }
295314 // SAFETY: prob_idx is guaranteed to be within bounds by the loop range.
296315 let prob_val: u64 = unsafe { arr. value_unchecked ( prob_idx) } . as_ ( ) ;
297- let idx_in_build_side = prob_val. wrapping_sub ( self . offset ) as usize ;
298-
299- if idx_in_build_side >= self . data . len ( )
300- || self . data [ idx_in_build_side] == 0
301- {
316+ let Some ( build_value) = self . get_value ( prob_val) else {
302317 continue ;
303- }
304- build_indices. push ( ( self . data [ idx_in_build_side ] - 1 ) as u64 ) ;
318+ } ;
319+ build_indices. push ( ( build_value - 1 ) as u64 ) ;
305320 probe_indices. push ( prob_idx as u32 ) ;
306321 }
307322 Ok ( None )
@@ -337,22 +352,17 @@ impl ArrayMap {
337352 return Ok ( Some ( ( prob_side_idx, None ) ) ) ;
338353 }
339354
340- if arr. is_null ( prob_side_idx) {
355+ if have_null && arr. is_null ( prob_side_idx) {
341356 continue ;
342357 }
343358
344359 let is_last = prob_side_idx == arr. len ( ) - 1 ;
345360
346361 // SAFETY: prob_idx is guaranteed to be within bounds by the loop range.
347362 let prob_val: u64 = unsafe { arr. value_unchecked ( prob_side_idx) } . as_ ( ) ;
348- let idx_in_build_side = prob_val. wrapping_sub ( self . offset ) as usize ;
349- if idx_in_build_side >= self . data . len ( )
350- || self . data [ idx_in_build_side] == 0
351- {
363+ let Some ( build_idx) = self . get_value ( prob_val) else {
352364 continue ;
353- }
354-
355- let build_idx = self . data [ idx_in_build_side] ;
365+ } ;
356366
357367 if let Some ( offset) = traverse_chain (
358368 & self . next ,
@@ -381,14 +391,14 @@ impl ArrayMap {
381391
382392 downcast_supported_integer ! (
383393 array. data_type( ) => (
384- contain_hashes_helper ,
394+ contain_keys_helper ,
385395 self ,
386396 array
387397 )
388398 )
389399 }
390400
391- fn contain_hashes_helper < T : ArrowNumericType > (
401+ fn contain_keys_helper < T : ArrowNumericType > (
392402 & self ,
393403 array : & ArrayRef ,
394404 ) -> Result < BooleanArray >
@@ -402,8 +412,7 @@ impl ArrayMap {
402412 }
403413 // SAFETY: i is within bounds [0, arr.len())
404414 let key: u64 = unsafe { arr. value_unchecked ( i) } . as_ ( ) ;
405- let idx = key. wrapping_sub ( self . offset ) as usize ;
406- idx < self . data . len ( ) && self . data [ idx] != 0
415+ self . get_value ( key) . is_some ( )
407416 } ) ;
408417 Ok ( BooleanArray :: new ( buffer, None ) )
409418 }
@@ -414,6 +423,7 @@ mod tests {
414423 use super :: * ;
415424 use arrow:: array:: Int32Array ;
416425 use arrow:: array:: Int64Array ;
426+ use arrow:: array:: UInt64Array ;
417427 use std:: sync:: Arc ;
418428
419429 #[ test]
@@ -506,6 +516,50 @@ mod tests {
506516 Ok ( ( ) )
507517 }
508518
519+ #[ test]
520+ fn test_array_map_rejects_large_out_of_range_probe_key ( ) -> Result < ( ) > {
521+ let build: ArrayRef =
522+ Arc :: new ( UInt64Array :: from ( vec ! [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] ) ) ;
523+ let map = ArrayMap :: try_new ( & build, 0 , 10 ) ?;
524+
525+ assert_eq ! ( ArrayMap :: key_to_index( 3 , 0 , 11 ) , Some ( 3 ) ) ;
526+
527+ // Pick a key for which the computed bucket offset is larger than
528+ // u32::MAX but has low 32 bits equal to 3. It must be bounds-checked
529+ // before casting to usize, otherwise 32-bit targets can truncate it
530+ // into range.
531+ let out_of_range_key = ( 1_u64 << 32 ) + 3 ;
532+ assert_eq ! ( ArrayMap :: key_to_index( out_of_range_key, 0 , 11 ) , None ) ;
533+
534+ let probe = [ Arc :: new ( UInt64Array :: from ( vec ! [
535+ Some ( 3 ) ,
536+ Some ( out_of_range_key) ,
537+ Some ( 11 ) ,
538+ None ,
539+ ] ) ) as ArrayRef ] ;
540+
541+ let mut matched_probe_indices = vec ! [ ] ;
542+ let mut matched_build_indices = vec ! [ ] ;
543+ let next = map. get_matched_indices_with_limit_offset (
544+ & probe,
545+ 10 ,
546+ ( 0 , None ) ,
547+ & mut matched_probe_indices,
548+ & mut matched_build_indices,
549+ ) ?;
550+ assert_eq ! ( matched_probe_indices, vec![ 0 ] ) ;
551+ assert_eq ! ( matched_build_indices, vec![ 3 ] ) ;
552+ assert ! ( next. is_none( ) ) ;
553+
554+ let contains = map. contain_keys ( & probe) ?;
555+ assert ! ( contains. value( 0 ) ) ;
556+ assert ! ( !contains. value( 1 ) ) ;
557+ assert ! ( !contains. value( 2 ) ) ;
558+ assert ! ( !contains. value( 3 ) ) ;
559+
560+ Ok ( ( ) )
561+ }
562+
509563 #[ test]
510564 fn test_array_map_i64_with_negative_and_positive_numbers ( ) -> Result < ( ) > {
511565 // Build array with a mix of negative and positive i64 values, no duplicates
0 commit comments