Skip to content

Commit b13f2bb

Browse files
authored
perf(parquet): skip per-batch key-bounds scan when RLE bit width prov… (apache#11462)
# Which issue does this PR close? - Closes apache#11414 # Rationale for this change - apache/datafusion#24111 - see apache#11414 for more context # split out of apache#11423 , see comment for [context](apache#11423 (review)) Skip the per-batch key bounds scan when the RLE bit width already proves it's safe. `DictionaryBuffer::Dict` now carries an optional key_upper_bound: Option<u64>, populated from the RLE page's bit_width as 2^bit_width, an exclusive upper bound on anything the decoder can produce. if key_upper_bound <= values.len(), every representable key is already a valid dictionary index, so the min/max fold over keys is skipped entirely. **This removes a per-batch O(n) pass that dominated the profile on low-cardinality shapes.**
1 parent 235a93b commit b13f2bb

3 files changed

Lines changed: 167 additions & 31 deletions

File tree

‎parquet/src/arrow/array_reader/byte_array_dictionary.rs‎

Lines changed: 22 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -280,6 +280,8 @@ enum MaybeDictionaryDecoder {
280280
/// This is a maximum as the null count is not always known, e.g. value data from
281281
/// a v1 data page
282282
max_remaining_values: usize,
283+
/// Validated bit width of decoded dictionary keys.
284+
bit_width: u8,
283285
},
284286
Fallback(ByteArrayDecoder),
285287
Fixed(FixedByteArrayDecoder),
@@ -401,6 +403,7 @@ where
401403
MaybeDictionaryDecoder::Dict {
402404
decoder,
403405
max_remaining_values: num_values.unwrap_or(num_levels),
406+
bit_width,
404407
}
405408
}
406409
_ if self.flba_column_descr.is_some() => {
@@ -433,6 +436,7 @@ where
433436
MaybeDictionaryDecoder::Dict {
434437
decoder,
435438
max_remaining_values,
439+
bit_width,
436440
} => {
437441
let len = num_values.min(*max_remaining_values);
438442

@@ -447,11 +451,9 @@ where
447451
return Ok(0); // All data must be NULL
448452
}
449453

450-
match out.as_keys(dict) {
454+
match out.as_keys_with_bit_width(dict, Some(*bit_width)) {
451455
Some(keys) => {
452456
// Happy path - can just copy keys
453-
// Keys will be validated on conversion to arrow
454-
455457
// TODO: Push vec into decoder (#5177)
456458
let start = keys.len();
457459
keys.resize(start + len, K::default());
@@ -492,6 +494,7 @@ where
492494
MaybeDictionaryDecoder::Dict {
493495
decoder,
494496
max_remaining_values,
497+
bit_width: _,
495498
} => {
496499
let num_values = num_values.min(*max_remaining_values);
497500
*max_remaining_values -= num_values;
@@ -963,4 +966,20 @@ mod tests {
963966
"Parquet error: Invalid or corrupted RLE bit width 33. Max allowed is 32"
964967
);
965968
}
969+
970+
#[test]
971+
fn test_dictionary_decoder_rejects_rle_value_exceeding_bit_width() {
972+
let column_desc = utf8_column();
973+
let mut decoder = DictionaryDecoder::<i32, i32>::new(&column_desc);
974+
975+
// Bit width 1, run length 1, value 0xff.
976+
let data = Bytes::from_static(&[1, 2, 0xff]);
977+
let err = decoder
978+
.set_data(Encoding::RLE_DICTIONARY, data, 1, Some(1))
979+
.unwrap_err();
980+
assert_eq!(
981+
err.to_string(),
982+
"Parquet error: Invalid or corrupted RLE value 255 exceeds bit width 1"
983+
);
984+
}
966985
}

‎parquet/src/arrow/buffer/dictionary_buffer.rs‎

Lines changed: 137 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -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`]
4646
pub 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

5165
impl<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
}

‎parquet/src/encodings/rle.rs‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -742,10 +742,16 @@ impl RleDecoder {
742742
} else {
743743
self.rle_left = num_values;
744744
let value_width = bit_util::ceil(self.bit_width as usize, u8::BITS as usize);
745-
self.current_value = bit_reader.get_aligned::<u64>(value_width);
746-
self.current_value.ok_or_else(|| {
745+
let value = bit_reader.get_aligned::<u64>(value_width).ok_or_else(|| {
747746
general_err!("parquet_data_error: not enough data for RLE decoding")
748747
})?;
748+
if self.bit_width < u64::BITS as u8 && value >= (1_u64 << self.bit_width) {
749+
return Err(general_err!(
750+
"Invalid or corrupted RLE value {value} exceeds bit width {}",
751+
self.bit_width
752+
));
753+
}
754+
self.current_value = Some(value);
749755
}
750756
Ok(true)
751757
} else {

0 commit comments

Comments
 (0)