|
| 1 | +// SPDX-License-Identifier: Apache-2.0 |
| 2 | +// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership |
| 3 | +// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements |
| 4 | + |
| 5 | +//! Randomized partitions against [`KeyRangeBitmap::union`]'s contract: it |
| 6 | +//! never excludes a key any part may hold, equals the bitmap built from all |
| 7 | +//! parts' keys when no part brings its own bitmap, and only widens that |
| 8 | +//! bitmap's buckets when one does. |
| 9 | +
|
| 10 | +use std::future::Future; |
| 11 | +use std::sync::Arc; |
| 12 | + |
| 13 | +use arrow::array::{ArrayRef, Int64Array}; |
| 14 | +use arrow::buffer::BooleanBuffer; |
| 15 | +use datafusion_common::{Result, ScalarValue}; |
| 16 | +use datafusion_physical_plan::joins::key_range_bitmap::{KeyRangeBitmap, KeyRangePart}; |
| 17 | +use rand::rngs::StdRng; |
| 18 | +use rand::{Rng, SeedableRng}; |
| 19 | +use test_utils::fuzz::FuzzTest; |
| 20 | + |
| 21 | +pub(crate) struct KeyRangeBitmapFuzzer; |
| 22 | + |
| 23 | +fn parts_of(b: &KeyRangeBitmap) -> (u64, u64, u32, &BooleanBuffer) { |
| 24 | + (b.offset(), b.span(), b.shift(), b.bits()) |
| 25 | +} |
| 26 | + |
| 27 | +enum Part { |
| 28 | + Keys(ArrayRef), |
| 29 | + Range(ScalarValue, ScalarValue), |
| 30 | + Bitmap(KeyRangeBitmap), |
| 31 | +} |
| 32 | + |
| 33 | +impl FuzzTest for KeyRangeBitmapFuzzer { |
| 34 | + type Dataset = (); |
| 35 | + |
| 36 | + fn name(&self) -> &str { |
| 37 | + "key_range_bitmap_union" |
| 38 | + } |
| 39 | + |
| 40 | + fn prepare_dataset(&self, _seed: u64) -> impl Future<Output = Result<()>> { |
| 41 | + std::future::ready(Ok(())) |
| 42 | + } |
| 43 | + |
| 44 | + fn run_case(&self, _dataset: &(), seed: u64) -> impl Future<Output = Result<()>> { |
| 45 | + let mut rng = StdRng::seed_from_u64(seed); |
| 46 | + // Domain widths from one key per bucket to many keys per bucket, so |
| 47 | + // the union's buckets are sometimes exact and sometimes coarse. |
| 48 | + let width = [64i64, 1 << 12, 1 << 24, 1 << 40][rng.random_range(0..4)]; |
| 49 | + let start = rng.random_range(-(1i64 << 50)..(1i64 << 50)); |
| 50 | + let key = |rng: &mut StdRng| start + rng.random_range(0..width); |
| 51 | + let keys_array = |
| 52 | + |keys: &[i64]| -> ArrayRef { Arc::new(Int64Array::from(keys.to_vec())) }; |
| 53 | + let scalar = |key: i64| ScalarValue::Int64(Some(key)); |
| 54 | + |
| 55 | + // Each part, and every key any part may hold. |
| 56 | + let mut parts = vec![]; |
| 57 | + let mut all_keys = vec![]; |
| 58 | + let mut has_bitmap = false; |
| 59 | + for _ in 0..rng.random_range(1..5) { |
| 60 | + if rng.random_bool(1.0 / 3.0) { |
| 61 | + // Narrow, so every key it may hold can be listed. |
| 62 | + let lo = key(&mut rng); |
| 63 | + let hi = lo + rng.random_range(0..64); |
| 64 | + parts.push(Part::Range(scalar(lo), scalar(hi))); |
| 65 | + all_keys.extend(lo..=hi); |
| 66 | + continue; |
| 67 | + } |
| 68 | + let keys: Vec<i64> = (0..rng.random_range(1..50)) |
| 69 | + .map(|_| key(&mut rng)) |
| 70 | + .collect(); |
| 71 | + let (lo, hi) = (*keys.iter().min().unwrap(), *keys.iter().max().unwrap()); |
| 72 | + let bitmap = rng |
| 73 | + .random_bool(0.5) |
| 74 | + .then(|| { |
| 75 | + KeyRangeBitmap::try_new( |
| 76 | + &keys_array(&keys), |
| 77 | + &scalar(lo), |
| 78 | + &scalar(hi), |
| 79 | + 0, |
| 80 | + ) |
| 81 | + }) |
| 82 | + .flatten(); |
| 83 | + parts.push(match bitmap { |
| 84 | + Some(bitmap) => { |
| 85 | + has_bitmap = true; |
| 86 | + Part::Bitmap(bitmap) |
| 87 | + } |
| 88 | + None => Part::Keys(keys_array(&keys)), |
| 89 | + }); |
| 90 | + all_keys.extend(keys); |
| 91 | + } |
| 92 | + let min = ScalarValue::Int64(all_keys.iter().min().copied()); |
| 93 | + let max = ScalarValue::Int64(all_keys.iter().max().copied()); |
| 94 | + let context = format!( |
| 95 | + "seed {seed}: width {width}, {} parts, {} keys", |
| 96 | + parts.len(), |
| 97 | + all_keys.len() |
| 98 | + ); |
| 99 | + |
| 100 | + let union = KeyRangeBitmap::union( |
| 101 | + &min, |
| 102 | + &max, |
| 103 | + &parts |
| 104 | + .iter() |
| 105 | + .map(|part| match part { |
| 106 | + Part::Keys(keys) => KeyRangePart::Keys(keys.as_ref()), |
| 107 | + Part::Range(min, max) => KeyRangePart::Range { min, max }, |
| 108 | + Part::Bitmap(bitmap) => KeyRangePart::Bitmap(bitmap), |
| 109 | + }) |
| 110 | + .collect::<Vec<_>>(), |
| 111 | + ); |
| 112 | + // Reference: one bitmap built straight from every key any part may hold. |
| 113 | + let exact = KeyRangeBitmap::try_new(&keys_array(&all_keys), &min, &max, 0); |
| 114 | + |
| 115 | + // Never excludes a key any part may hold. |
| 116 | + if let Some(union) = &union { |
| 117 | + for key in &all_keys { |
| 118 | + assert!( |
| 119 | + union.may_contain_range(*key as u64, *key as u64), |
| 120 | + "{context}: dropped key {key}" |
| 121 | + ); |
| 122 | + } |
| 123 | + } |
| 124 | + if has_bitmap { |
| 125 | + // A part's bitmap can only widen buckets: every bucket the exact |
| 126 | + // bitmap sets, the union sets too. |
| 127 | + match (&union, &exact) { |
| 128 | + (_, None) => assert!(union.is_none(), "{context}"), |
| 129 | + (None, Some(_)) => {} |
| 130 | + (Some(union), Some(exact)) => { |
| 131 | + assert_eq!( |
| 132 | + (union.offset(), union.span(), union.shift()), |
| 133 | + (exact.offset(), exact.span(), exact.shift()), |
| 134 | + "{context}" |
| 135 | + ); |
| 136 | + for bucket in exact.bits().set_indices() { |
| 137 | + assert!(union.bits().value(bucket), "{context}: bucket {bucket}"); |
| 138 | + } |
| 139 | + } |
| 140 | + } |
| 141 | + // Each set bucket of a part's bitmap stands for its whole key range, |
| 142 | + // so the union equals the one over those ranges given as `Range`s. |
| 143 | + let ranges: Vec<(ScalarValue, ScalarValue)> = parts |
| 144 | + .iter() |
| 145 | + .flat_map(|part| match part { |
| 146 | + Part::Bitmap(bitmap) => bitmap |
| 147 | + .bits() |
| 148 | + .set_indices() |
| 149 | + .map(|bucket| { |
| 150 | + let lo = (bucket as u64) << bitmap.shift(); |
| 151 | + let hi = lo |
| 152 | + .saturating_add((1u64 << bitmap.shift()) - 1) |
| 153 | + .min(bitmap.span()); |
| 154 | + let key = |
| 155 | + |at: u64| scalar(bitmap.offset().wrapping_add(at) as i64); |
| 156 | + (key(lo), key(hi)) |
| 157 | + }) |
| 158 | + .collect(), |
| 159 | + _ => vec![], |
| 160 | + }) |
| 161 | + .collect(); |
| 162 | + let expanded = KeyRangeBitmap::union( |
| 163 | + &min, |
| 164 | + &max, |
| 165 | + &parts |
| 166 | + .iter() |
| 167 | + .filter_map(|part| match part { |
| 168 | + Part::Keys(keys) => Some(KeyRangePart::Keys(keys.as_ref())), |
| 169 | + Part::Range(min, max) => Some(KeyRangePart::Range { min, max }), |
| 170 | + Part::Bitmap(_) => None, |
| 171 | + }) |
| 172 | + .chain( |
| 173 | + ranges |
| 174 | + .iter() |
| 175 | + .map(|(min, max)| KeyRangePart::Range { min, max }), |
| 176 | + ) |
| 177 | + .collect::<Vec<_>>(), |
| 178 | + ); |
| 179 | + assert_eq!( |
| 180 | + union.as_ref().map(parts_of), |
| 181 | + expanded.as_ref().map(parts_of), |
| 182 | + "{context}: bitmap parts differ from their bucket ranges" |
| 183 | + ); |
| 184 | + } else { |
| 185 | + // Keys and ranges mark exactly the buckets their keys fall in. |
| 186 | + assert_eq!( |
| 187 | + union.as_ref().map(parts_of), |
| 188 | + exact.as_ref().map(parts_of), |
| 189 | + "{context}" |
| 190 | + ); |
| 191 | + } |
| 192 | + |
| 193 | + std::future::ready(Ok(())) |
| 194 | + } |
| 195 | +} |
0 commit comments